Artificial Intelligence | Semester 6 Complete Core Notes
Semester 6 - Page 1: Artificial Intelligence. 27 numbered topics, highlighted rules, worked reasoning/search examples, answered exam questions, diagrams, comparison tables and five complete Python demos. General common-core guide, not an official syllabus or a validated decision system.
Topic map
- AI, agents and rationality
- PEAS and environment properties
- Agent architectures and state
- Search problem formulation
- BFS, DFS and iterative deepening
- Uniform-cost search and best costs
- Heuristics, greedy search and A*
- Local search and optimization
- Constraint satisfaction and backtracking
- Constraint propagation and consistency
- Minimax and adversarial assumptions
- Alpha-beta and expectimax
- Propositional logic and entailment
- First-order logic and quantifiers
- Inference, unification and knowledge bases
- Planning and action models
- Probability, conditioning and independence
- Bayes rule and base rates
- Bayesian networks and temporal models
- MDPs, rewards and Bellman reasoning
- Reinforcement learning and exploration
- Supervised learning and evaluation
- Unsupervised learning and representation
- Neural networks and gradient learning
- NLP, perception and application limits
- Responsible AI and uncertainty
- Exam and implementation checklist
1. AI, agents and rationality
AI studies agents selecting actions from observations to meet a performance measure. Rational choice concerns expected outcomes given available information, not imitation of a person.
Answer: No. Uncertainty and unavailable information limit guarantees.
2. PEAS and environment properties
PEAS names performance, environment, actuators and sensors. Classify observability, determinism, episodic/sequential structure, dynamics and action/state discreteness.
Answer: It exposes assumptions that determine which agent/search model fits.
3. Agent architectures and state
Reflex, model-based, goal-based, utility-based and learning architectures organize different decision needs. Internal state can summarize history when observations are incomplete.
Answer: No. It can be an estimate or partial summary.
4. Search problem formulation
Specify initial state, actions, transition, goal and path cost. A search state describes a configuration; a search node also records path/cost/parent information.
Answer: No. Equal step costs are needed for that equivalence.
S --2--> A --6--> G \--5--> B --1--> G S-A-G = 8; S-B-G = 6
5. BFS, DFS and iterative deepening
BFS uses a queue and finds minimum edge depth under standard finite-branching assumptions. DFS uses a depth-first frontier and is not generally shortest/complete on infinite paths. Iterative deepening repeats depth limits.
Answer: No. Stack/path and graph visited-state storage still consume space.
6. Uniform-cost search and best costs
UCS prioritizes accumulated cost and updates better paths. Nonnegative costs and suitable termination/finite conditions matter; accept a goal when selected correctly from the frontier, not merely first generated.
Answer: Not safely. Better-cost paths must be handled correctly.
7. Heuristics, greedy search and A*
Greedy ranks h alone; A* ranks g+h. Admissibility means no overestimate; consistency bounds each edge estimate. Graph-search duplicate/reopening rules affect optimality.
Answer: No. Cost updates, reopenings and goal termination rules also matter.
Uniform-cost and A* with best-cost updates
from heapq import heappush, heappop
from itertools import count
graph = {"S": [("A", 2), ("B", 5)], "A": [("G", 6)], "B": [("G", 1)], "G": []}
def search(heuristic):
serial = count()
queue = [(heuristic["S"], next(serial), 0, "S", ["S"])]
best = {"S": 0}
while queue:
_, _, cost, node, path = heappop(queue)
if cost != best[node]: continue
if node == "G": return cost, path
for child, weight in graph[node]:
if weight < 0: raise ValueError("nonnegative costs required")
new = cost + weight
if new < best.get(child, float("inf")):
best[child] = new
heappush(queue, (new+heuristic[child], next(serial), new, child, path+[child]))
return None
for name, h in [("UCS", dict.fromkeys(graph, 0)), ("A*", {"S": 6, "A": 4, "B": 1, "G": 0})]:
print(name, search(h))
Checked output:
UCS (6, ['S', 'B', 'G']) A* (6, ['S', 'B', 'G'])
8. Local search and optimization
Hill climbing follows local improvement and can get stuck on plateaus/local optima. Simulated annealing allows some worse moves under a schedule; random restarts explore alternatives.
Answer: No. Many formulations seek a final configuration rather than a path.
9. Constraint satisfaction and backtracking
A CSP specifies variables, domains and constraints. Backtracking assigns compatible values; MRV, degree and least-constraining-value heuristics influence search order.
Answer: No. Constraints define allowed solutions; heuristics guide search order.
Triangle coloring by backtracking
vertices = ["A", "B", "C"]
edges = {frozenset(pair) for pair in [("A","B"), ("B","C"), ("A","C")]}
def solve(colors):
assigned = {}
def visit(index):
if index == len(vertices): return dict(assigned)
vertex = vertices[index]
for color in colors:
if any(frozenset((vertex,other)) in edges and value == color for other,value in assigned.items()):
continue
assigned[vertex] = color
answer = visit(index+1)
if answer is not None: return answer
del assigned[vertex]
return None
return visit(0)
print("two colors:", solve(["red", "blue"]))
print("three colors:", solve(["red", "blue", "green"]))
Checked output:
two colors: None
three colors: {'A': 'red', 'B': 'blue', 'C': 'green'}
10. Constraint propagation and consistency
Forward checking removes incompatible future values; arc consistency ensures every retained value has support across each relevant binary constraint. Propagation can prune without solving all global constraints.
Answer: No. Local consistency does not resolve every global interaction.
11. Minimax and adversarial assumptions
Minimax evaluates MAX/MIN choices for suitable deterministic two-player zero-sum games under its model. Depth cutoffs rely on evaluation quality.
Answer: The opponent controls the MIN response.
MAX
/ \
MIN A MIN B
3 5 2 9
-> 3 -> 2
MAX chooses A with value 312. Alpha-beta and expectimax
Alpha-beta prunes branches unable to change minimax's result; move order affects work saved. Expectimax uses probabilities at chance nodes and different risk assumptions.
Answer: No. Chance-value bounds and assumptions differ.
Minimax and alpha-beta on the same finite tree
tree = [[3, 5], [2, 9]]
def minimax(node, maximizing):
if isinstance(node, int): return node
values = [minimax(child, not maximizing) for child in node]
return max(values) if maximizing else min(values)
def alphabeta(node, maximizing, alpha=float("-inf"), beta=float("inf")):
if isinstance(node, int): return node
value = float("-inf") if maximizing else float("inf")
for child in node:
score = alphabeta(child, not maximizing, alpha, beta)
if maximizing:
value = max(value, score); alpha = max(alpha, value)
else:
value = min(value, score); beta = min(beta, value)
if alpha >= beta: break
return value
print("minimax:", minimax(tree, True))
print("alpha-beta:", alphabeta(tree, True))
assert minimax(tree, True) == alphabeta(tree, True) == 3
print("agreement check passed")
Checked output:
minimax: 3 alpha-beta: 3 agreement check passed
13. Propositional logic and entailment
Propositions, connectives and truth assignments express statements. Entailment means every model satisfying premises also satisfies the conclusion; implication is false only for true antecedent/false consequent.
Answer: No. Affirming the consequent is invalid.
14. First-order logic and quantifiers
First-order logic adds objects, predicates, variables and quantifiers. Quantifier order matters; existential and universal claims are different.
Answer: No. The object's premise must be provided separately.
15. Inference, unification and knowledge bases
Inference derives supported conclusions; unification finds substitutions matching logical expressions under its rules. Knowledge bases need consistent representation and explicit unknowns.
Answer: No. Open/closed-world assumptions must be stated.
16. Planning and action models
Planning uses states/actions with preconditions and effects to reach goals. Ordering, resources and uncertainty affect execution beyond a symbolic plan.
Answer: No. Validate assumptions and respond to changed state.
17. Probability, conditioning and independence
Probability distributions quantify uncertainty under a model. Conditional probability changes with evidence; independence is a claim requiring support, not a default for convenient arithmetic.
Answer: Not without a justified independence model.
18. Bayes rule and base rates
Bayes relates posterior, likelihood and prior through evidence normalization. Rare conditions can yield a low positive predictive value despite high sensitivity.
Answer: No. Base rate and false positives affect the posterior.
Bayes posterior using exact rational arithmetic
from fractions import Fraction
prior, sensitivity, false_positive = Fraction(1,100), Fraction(9,10), Fraction(1,10)
true_flag = prior*sensitivity
false_flag = (1-prior)*false_positive
posterior = true_flag/(true_flag+false_flag)
print("posterior exact:", posterior)
print("posterior decimal:", format(float(posterior), ".6f"))
print("flagged spam per 1000:", true_flag*1000)
print("flagged nonspam per 1000:", false_flag*1000)
Checked output:
posterior exact: 1/12 posterior decimal: 0.083333 flagged spam per 1000: 9 flagged nonspam per 1000: 99
19. Bayesian networks and temporal models
Bayesian networks factor a joint distribution using directed dependencies and local conditional probabilities. Temporal models describe hidden/state evolution and observations under stated assumptions.
Answer: No. A probabilistic graph and a causal claim need different supporting assumptions.
20. MDPs, rewards and Bellman reasoning
An MDP specifies states, actions, transition probabilities and rewards with a horizon/discount. A policy selects actions; Bellman reasoning compares immediate and future expected return.
Answer: No. Risk constraints and reward design remain separate choices.
State -> policy action
-> probabilistic transition
-> reward + next state
-> future decisionOne-step expected-reward comparison
actions = {"safe": [(1.0, 2.0)], "risky": [(0.6, 5.0), (0.4, -1.5)]}
values = {}
for action, outcomes in actions.items():
assert abs(sum(p for p, reward in outcomes)-1.0) < 1e-12
values[action] = sum(p*reward for p,reward in outcomes)
print(action + ":", format(values[action], ".2f"))
print("expected-reward choice:", max(values, key=values.get))
print("This comparison has no risk constraint and is not a safety guarantee.")
Checked output:
safe: 2.00 risky: 2.40 expected-reward choice: risky This comparison has no risk constraint and is not a safety guarantee.
21. Reinforcement learning and exploration
RL learns from action/reward experience; model-based and model-free approaches use different information. Exploration trades learning against cost; unsafe actions need limits.
Answer: No. A poorly chosen reward can encourage unwanted behavior.
22. Supervised learning and evaluation
Supervised models fit labeled examples for classification/regression. Hold out evaluation matching real units/time and fit learned preprocessing on training folds only.
Answer: No. Freeze choices before final evaluation.
23. Unsupervised learning and representation
Clustering and representation methods seek structure without supplied target labels. Scaling, initialization and objective affect the result; clusters are not automatically meaningful classes.
Answer: No. Data access/use still needs permission and safeguards.
24. Neural networks and gradient learning
Layers compose weighted transformations and activations. Backpropagation computes gradients through the chain rule; an optimizer updates parameters under a loss.
Answer: No. Capacity, data, optimization and regularization interact.
25. NLP, perception and application limits
Language and vision systems depend on representation, training data and evaluation. Fluent text or a confident recognition score is not grounded truth or authority.
Answer: No. Measure performance and verify claims appropriate to the stakes.
26. Responsible AI and uncertainty
Assess data permission, fairness, calibration, group performance, human review and harmful consequences. Optimization of one metric can conflict with broader goals.
Answer: No. Proxies and unequal data can preserve harmful effects.
27. Exam and implementation checklist
State model, assumptions, algorithm, trace, complexity where relevant and limitations. Test edge cases and compare independent methods on small examples.
Answer: A worked trace/calculation with assumptions, checks and limits.
Search comparison
| Method | Priority | Key limitation |
|---|---|---|
| BFS | Edge depth/FIFO | Least edges, not arbitrary weighted cost |
| DFS | Depth-first/LIFO | Not generally shortest; cycles/infinite paths |
| UCS | Accumulated g | Nonnegative costs and proper best-cost handling |
| Greedy | Estimated h | Not generally optimal |
| A* | g+h | Heuristic and graph-search rules matter |
Inference and choice distinctions
| Concept | Uses | Does not establish |
|---|---|---|
| Logical entailment | All satisfying premise models | Truth from unsupported premises |
| Bayes posterior | Prior, likelihood, evidence | Causal explanation or guaranteed outcome |
| Minimax | Worst modeled adversarial reply | Probabilistic expected payoff |
| Expectimax | Chance probabilities | Worst-case safety |
| MDP expected return | Transition/reward policy model | Complete real-world user goal |
Worked arithmetic
| Example | Calculation | Result |
|---|---|---|
| Route via A | 2+6 | 8 |
| Route via B | 5+1 | 6 |
| Bayes flags | 9 / (9+99) | 1/12 = 0.083333 rounded |
| Risky expected reward | 0.6x5 + 0.4x(-1.5) | 2.40 |
| Safe reward | 1x2 | 2.00 |
Revision and exam checklist
Define agent/environment, formulate states and costs, trace search/minimax, distinguish logic from probability, compute base-rate-aware Bayes and state reward/risk assumptions. Compare methods on small examples and explain where guarantees stop.
Resources and sources
Open AI teaching references support the concepts. Examples, diagrams and all demos here are original; exact program output is shown rather than claimed accuracy on a real dataset.
Comments
Post a Comment