Artificial Intelligence Study Notes

AI is the branch of computer science concerned with making computers behave like humans — reasoning, learning, and problem-solving. [2023]

An agent is anything that can perceive its environment through sensors and act through actuators. [2021]

Performance measure, Environment, Actuators, Sensors.

A test proposed by Alan Turing (1950) where a human interrogator chats with both a human and a machine. If the interrogator cannot reliably tell the machine apart, the machine is said to exhibit intelligent behaviour.

The 1956 summer workshop at Dartmouth College, co-organised by John McCarthy, Marvin Minsky, Claude Shannon and Nathaniel Rochester. It coined the term "Artificial Intelligence" and marked the birth of AI as a field.

A rational agent does the right thing given its percept sequence. An omniscient agent would know the actual outcome of every action — an unrealistic ideal. Rationality ≠ omniscience.

The set of all possible states reachable from the initial state by any sequence of actions. Represented as a graph where nodes are states and edges are actions.

The process of defining precisely: (1) initial state, (2) actions/ successor function, (3) goal test, and (4) path cost. This converts a real-world problem into a formal search problem.

(1) Simple reflex agent, (2) Model-based reflex agent, (3) Goal-based agent, (4) Utility-based agent.

(1) Simple Reflex Agent: Acts only on current percept, ignoring history. Uses condition-action rules. Example: a thermostat that turns heat ON when T < 20°C.

(2) Model-Based Reflex Agent: Maintains an internal model of the world (current state). Updates the model using percept history. Example: a robot with a map of the room.

(3) Goal-Based Agent: Has explicit goals and chooses actions to achieve them. Needs search/planning. Example: a navigation app choosing route to destination.

(4) Utility-Based Agent: Uses a utility function to rank outcomes. Chooses actions that maximise expected utility. Example: stock trading bot balancing profit vs risk.

Environments are classified along several dimensions:

• Fully vs Partially Observable: Does the agent have access to the complete state?
• Single vs Multi-agent: One agent or multiple competing agents?
• Deterministic vs Stochastic: Is the next state fully determined by current state + action?
• Episodic vs Sequential: Are decisions independent episodes or does each affect the future?
• Static vs Dynamic: Does the environment change while the agent deliberates?
• Discrete vs Continuous: Are states/time/actions countable?
• Known vs Unknown: Are the rules/outcomes known to the designer?

Chess is: fully observable, multi-agent, deterministic, sequential, static, discrete, known.

• 1943: McCulloch & Pitts — first computational model of neurons.
• 1950: Turing publishes "Computing Machinery and Intelligence" and proposes the Turing Test.
• 1956: Dartmouth Conference — "Artificial Intelligence" term coined. Birth of AI.
• 1959: Arthur Samuel's checkers program — first self-learning program.
• 1966: ELIZA — first chatbot by Joseph Weizenbaum.
• 1969: Shakey the Robot — first general-purpose mobile robot at SRI.
• 1974–80 (First AI Winter): Funding cut, limitations exposed.
• 1997: Deep Blue defeats Garry Kasparov at chess.
• 2011: Watson wins Jeopardy!
• 2016: AlphaGo defeats Lee Sedol at Go.
• 2022–present: Large Language Models (GPT, Claude, etc.) — generative AI revolution.

Problem solving in AI means finding a sequence of actions that transforms the world from an initial state to a goal state.

8-Queen Problem formulation:

• Initial state: Empty board.
• Actions: Place a queen in any unattacked square of the first non-empty row.
• Goal test: 8 queens placed, none attacking each other.
• Path cost: Number of queens placed (each costs 1).

State space size is 64! / (56! · 8!) ≈ 4.4 × 10⁹ — a constraint satisfaction approach is preferred over general search.

The Turing Test (1950): Alan Turing proposed an "Imitation Game." A human interrogator communicates via text with two hidden entities — one human, one machine. If the interrogator cannot reliably distinguish the machine from the human (more than 30% of the time over 5 minutes), the machine is said to have passed.

Strength:

• Practical, behaviour-based — focuses on what a system does, not how it thinks.
• Subjective bias avoided — the interrogator does not know which is which.
• Applicable to any behaviour (text, speech, image).

Limitations:

• Does not measure understanding or consciousness — only behavioural mimicry.
• Anthropocentric — designed around human-level interaction.
• Can be "gamed" by ELIZA-style tricks (evasion, keyword matching).
• Does not distinguish between simulating intelligence and actually being intelligent.
• Chinese Room argument (Searle, 1980): syntax is not semantics.

Modern view: The Turing Test is a useful benchmark for conversational AI, but not a definitive test of general intelligence.

(1) Simple Reflex Agent — acts only on the current percept.

function SIMPLE-REFLEX-AGENT(percept) returns action
  static: rules, a set of condition-action rules
  rule ← RULE-MATCH(percept, rules)
  action ← rule.ACTION
  return action

Example: A vacuum cleaner that turns RIGHT when it bumps into a wall.

(2) Model-Based Reflex Agent — maintains internal state.

function MODEL-BASED-AGENT(percept) returns action
  static: model, rules
  model ← UPDATE-MODEL(model, action, percept)
  state ← MODEL-STATE(model, action, percept)
  rule ← RULE-MATCH(state, rules)
  action ← rule.ACTION
  return action

Example: A robot that remembers which rooms it has cleaned using a map.

(3) Goal-Based Agent — has explicit goals and reasons about future.

function GOAL-BASED-AGENT(percept) returns action
  goals ← INFER-GOALS(percept)
  state ← UPDATE-STATE(percept)
  action ← FIND-ACTION(goals, state)
  return action

Example: A taxi driver navigating to a destination — the goal is the destination address.

(4) Utility-Based Agent — maximises expected utility.

function UTILITY-BASED-AGENT(percept) returns action
  state ← UPDATE-STATE(percept)
  action ← argmaxa in ACTIONS(state) EXPECTED-UTILITY(a, state)
  return action

Example: A medical diagnosis system choosing treatments ranked by expected patient quality-of-life.

A search strategy that expands the shallowest node first. Uses a FIFO queue. It is complete and optimal for uniform step cost.

A search strategy that expands the deepest node first. Uses a LIFO stack. Not complete for infinite spaces and not optimal.

UCS expands the node with the smallest path cost g(n). It generalises BFS to non-uniform step costs and is always optimal.

DFS with a predefined depth limit l. If the goal is deeper than l, DLS fails. Problem: choosing the right limit l.

It performs DFS with increasing depth limits: 0, 1, 2, ... until the goal is found. Combines BFS's completeness with DFS's low memory.

Search that simultaneously runs forward from the initial state and backward from the goal state, meeting in the middle. Effective branching factor becomes √b.

Time: O(b^d), Space: O(b^d), where b = branching factor and d = depth of shallowest goal.

DFS is not complete (can loop in infinite paths) and not optimal. It can get stuck in deep, irrelevant branches.

Here b = branching factor, d = depth of shallowest goal, m = max depth of tree, C* = optimal cost, ε = minimum non-zero step cost.

IDDFS performs repeated depth-limited DFS with increasing limits: depth 0, 1, 2, ..., d.

Algorithm:

function IDDFS(problem) returns solution
  for depth = 0 to ∞:
    result ← DLS(problem, depth)
    if result ≠ cutoff: return result

Why preferred over BFS:

• Space complexity: O(bd) vs O(b^d) for BFS — a huge saving for large b, d.
• Complete for finite branching factor.
• Optimal for unit step costs.
• The overhead of revisiting nodes is small (< 11% for b=10).
• Time complexity is asymptotically the same as BFS: O(b^d).

BFS Algorithm:

function BFS(problem) returns solution
  node ← NODE(problem.INITIAL)
  if problem.IS-GOAL(node.STATE): return node
  frontier ← FIFOQueue([node])
  reached ← {problem.INITIAL}
  while not frontier.EMPTY?:
    node ← POP(frontier)
    for child in EXPAND(node, problem):
      s ← child.STATE
      if problem.IS-GOAL(s): return child
      if s not in reached:
        reached.ADD(s)
        PUSH(frontier, child)
  return failure

DFS Algorithm (recursive):

function DFS(problem, limit) returns solution/failure/cutoff
  node ← NODE(problem.INITIAL)
  return RECURSIVE-DLS(node, problem, limit)

function RECURSIVE-DLS(node, problem, limit) returns solution/failure/cutoff
  if problem.IS-GOAL(node.STATE): return node
  else if limit = 0: return cutoff
  else:
    cutoff_occurred? ← false
    for child in EXPAND(node, problem):
      result ← RECURSIVE-DLS(child, problem, limit-1)
      if result = cutoff: cutoff_occurred? ← true
      else if result ≠ failure: return result
    if cutoff_occurred?: return cutoff else return failure

Properties:

• BFS: Complete, Optimal (unit cost), Time O(b^d), Space O(b^d).
• DFS: Not complete, Not optimal, Time O(b^m), Space O(bm).

Problem graph:

BFS (Queue-based, level by level):

Frontier evolution:
  [A]
  [B, C]          ← expand A
  [C, D, E]       ← expand B
  [D, E, G, G]    ← expand C → D, E added; D expands → G
  [G, G]          ← goal reached: path A-B-D-G cost=10

DFS (Stack-based, deepest first):

Stack evolution:
  [A]
  [B, C]          ← expand A
  [D, E, C]       ← expand B
  [G, E, C]       ← expand D
  [E, C]          ← expand G → GOAL! path A-B-D-G cost=10

Both BFS and DFS find the same path here: A → B → D → G with cost 2+3+5 = 10. However, BFS explores all nodes at depth 2 before depth 3, while DFS dives deep immediately. In a different graph, DFS could find a different (possibly non-optimal) path first.

Romania Road Map (selected cities & distances in km):

UCS Expansion Order (lowest path cost first):

Step 1: Expand Arad        path cost = 0
  Frontier: Zerind(75), Sibiu(140), Timisoara(118)

Step 2: Expand Zerind      path cost = 75
  Frontier: Timisoara(118), Sibiu(140), Oradea(71+152=223)

Step 3: Expand Timisoara   path cost = 118
  Frontier: Sibiu(140), Lugoj(118+111=229), ...

Step 4: Expand Sibiu       path cost = 140
  Frontier: Rimnicu Vilcea(140+80=220), Fagaras(140+99=239), ...

Step 5: Expand Rimnicu Vilcea  path cost = 220
  Frontier: Pitesti(220+97=317), ...

Step 6: Expand Pitesti     path cost = 317
  Frontier: Bucharest(317+101=418), Craiova(317+138=455)

Step 7: Expand Bucharest   path cost = 418  ← GOAL!

Optimal Path: Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest
Optimal Cost: 140 + 80 + 97 + 101 = 418 km

A function that estimates the cost from node n to the goal. It guides search towards promising regions of the state space.

A heuristic that never overestimates the true cost to reach the goal: h(n) ≤ h*(n). Admissibility guarantees optimality of A*.

f(n) = g(n) + h(n), where g(n) is the actual cost from start to n, and h(n) is the estimated cost from n to the goal.

A metaheuristic that sometimes accepts worse moves with probability e^(-ΔE/T), where T is temperature that slowly cools. Helps escape local optima.

A problem defined by variables X with domains D and constraints C. The goal is to find an assignment where all constraints are satisfied.

An operator that combines two parent chromosomes to produce offspring. Common types: single-point, two-point, and uniform crossover.

AO* finds optimal solutions in AND-OR graphs by propagating cost values from goal nodes backward, choosing the minimum-cost subgraph.

A function that evaluates how good a solution (chromosome) is. Higher fitness → higher chance of being selected for reproduction.

Algorithm:

function A*(problem, h) returns solution
  node ← NODE(problem.INITIAL)
  frontier ← PriorityQueue ordered by f = g+h, containing node
  reached ← {problem.INITIAL: node}
  while not frontier.EMPTY?:
    node ← POP(frontier)
    if problem.GOAL?(node.STATE): return node
    for child in EXPAND(node, problem):
      s ← child.STATE
      if s not in reached or child.PATH-COST < reached[s].PATH-COST:
        reached[s] ← child
        ADD(frontier, child)
  return failure

Proof of Optimality:

1. Let G be an optimal goal node with cost C*.
2. A* expands nodes in order of increasing f.
3. Since h is admissible, for every node n on the optimal path, f(n) = g(n) + h(n) ≤ g(n) + h*(n) = g(n) + (C* - g(n)) = C*.
4. Thus no node on the optimal path has f > C*.
5. When A* selects a goal node G for expansion, its f(G) = g(G) ≤ C* (since h(G)=0 and h is admissible).
6. Therefore g(G) = C*, i.e., the solution is optimal.

(1) Simple Hill Climbing: Pick any neighbour better than current. Move to it. Stop when no neighbour is better. Fast but very basic.

(2) Steepest-Ascent Hill Climbing: Examine ALL neighbours and move to the best one. More thorough than simple HC.

(3) First-Choice Hill Climbing: Randomly generate successors until one is better than current. Efficient when many neighbours exist.

(4) Random-Restart Hill Climbing: Run hill climbing from many random initial states; keep the best result. Probabilistically complete.

(5) Simulated Annealing: Occasionally accept worse moves with probability P = e^(-ΔE/T), where T starts high and decreases. Escapes local optima.

Limitations of all variants:

• Local maxima — stuck at a peak lower than the global maximum.
• Ridges — sequence of local maxima makes progress zigzag and slow.
• Plateaux — flat area where no neighbour is better.

Genetic Algorithms (GAs) are population-based search algorithms inspired by natural evolution. They work on a population of candidate solutions (chromosomes).

1. Selection: Choose fitter individuals for reproduction. Common methods:

• Roulette Wheel Selection: probability proportional to fitness.
• Tournament Selection: pick k individuals at random; the best wins.
• Rank Selection: rank individuals by fitness; probability based on rank.

2. Crossover: Combine two parents to produce offspring. Single-point crossover: pick a crossover point and swap tails.

Parent 1:  11001 | 101    →   11001 011
Parent 2:  10110 | 011    →   10110 101
                  ↑ crossover point (after position 5)

3. Mutation: Randomly flip a bit in a chromosome with low probability (e.g., 0.01). Maintains genetic diversity and prevents premature convergence.

4. Fitness Function: Evaluates each chromosome. Problem-specific. Higher fitness → higher survival probability.

A CSP has: variables X = {X1, ..., Xn}, domains D = {D1, ..., Dn}, and constraints C specifying allowed value combinations.

Backtracking Search: Assign variables one at a time. If a constraint is violated, backtrack to the last decision point and try a different value.

Example — Map Colouring (Australia): Variables: WA, NT, Q, NSW, V, SA, T. Domain: {Red, Green, Blue}. Constraint: adjacent regions must have different colours.

Forward Checking: When a variable Xi is assigned value vi, prune the domain of each unassigned neighbour Xj by removing values inconsistent with vi. If any domain becomes empty, backtrack immediately.

Graph:

A* Step-by-Step:

Step 1: Expand S
  g(S)=0,  h(S)=6,  f(S)=0+6=6
  Children: A(g=1, f=1+4=5),  B(g=4, f=4+3=7)
  Frontier sorted: A(5), B(7)

Step 2: Expand A (lowest f=5)
  Children: C(g=1+3=4, f=4+2=6), D(g=1+7=8, f=8+1=9)
  Frontier sorted: C(6), B(7), D(9)

Step 3: Expand C (lowest f=6)
  Children: G(g=4+8=12, f=12+0=12)
  Frontier sorted: B(7), D(9), G(12)

Step 4: Expand B (lowest f=7)
  Children: D(g=4+5=9 → worse than existing 8, skip), G(g=4+6=10, f=10+0=10)
  Frontier sorted: D(9), G(10), G(12)

Step 5: Expand D (lowest f=9)
  Children: G(g=8+2=10 → same as existing, skip)
  Frontier sorted: G(10), G(12)

Step 6: Expand G (lowest f=10) ← GOAL!
  Path: S → A → B → G, total cost = 10

A* explores 5 nodes (S, A, C, B, D) before reaching the goal. The optimal path cost is 10 via S → A → B → G.

GA Framework:

1. Initialise: Create random population of chromosomes.
2. Evaluate: Compute fitness of each chromosome.
3. Select: Choose parents proportionally to fitness.
4. Crossover: With probability Pc, recombine pairs.
5. Mutate: With probability Pm, flip random bits.
6. Replace: Form new population; repeat from step 2.
7. Terminate: After fixed generations or convergence.

Application to maximise f(x) = x² (x ∈ [0, 31]):

Represent x as 5-bit binary: 0 = 00000, 31 = 11111. f(x) = x² is the fitness.

Generation 0 (random):

Total fitness = 169+576+121+324 = 1190. Selection probabilities: 14.2%, 48.4%, 10.2%, 27.2%.

Selection (roulette wheel): Select 11000 (f=576) and 10010 (f=324) as parents.

Crossover (Pc=0.7, crossover at bit 2):

P1: 11 | 000  →  11000 (x=24)
P2: 10 | 010  →  10010 (x=18)
Offspring:  11 | 010  = 11010 (x=26, f=676)
             10 | 000  = 10000 (x=16, f=256)

Mutation (Pm=0.01, flip bit 4 of offspring2): 10000 → 10001 (x=17, f=289)

Generation 1: {11010(x=26,f=676), 10001(x=17,f=289), 01101(x=13,f=169), 11000(x=24,f=576)}

Repeating this process, the population converges toward x=31 (11111, f=961).

Logical representation (propositional, predicate), Semantic networks, Frames/Scripts, Production rules, Conceptual dependencies.

A rule of the form IF (condition) THEN (action). Used in expert systems and rule-based systems. Also called IF-THEN rules.

A graph where nodes represent objects/concepts and labelled edges represent relationships between them. Example: IS-A, HAS-A links.

A data structure for representing stereotypical situations. Contains slots with default values and procedural attachments (if-needed, if-added).

FOL (predicate logic) extends propositional logic with quantifiers (∀, ∃), variables, predicates, and functions. It can express statements about objects and their relationships.

The process of finding a substitution that makes two logical expressions identical. It is the basic matching mechanism for resolution and logical inference.

A complete inference rule for FOL. Given two clauses containing complementary literals, derive a new clause (resolvent) by removing the complementary pair and merging the rest.

A program that encodes the knowledge of a human expert in a specific domain and uses inference rules to solve problems like the expert would.

Forward Chaining (Data-driven): Starts from known facts and applies rules forward until a goal is reached. Bottom-up reasoning. Used in OPS5, CLIPS.

R1: IF rainy THEN wet
R2: IF wet AND cold THEN slippery
Facts: rainy, cold
→ Apply R1: wet (inferred)
→ Apply R2: slippery (GOAL reached)

Backward Chaining (Goal-driven): Starts from the goal and works backward, finding rules that could prove the goal, then proving their antecedents. Top-down reasoning. Used in Prolog, MYCIN.

Goal: slippery
→ Need: wet AND cold
→ Prove wet: use R1 → need rainy (TRUE)
→ Prove cold: (TRUE)
→ Goal proved ✓

Components:

• Knowledge Base: Stores domain knowledge as facts and rules. The most critical component.
• Inference Engine: Applies reasoning (forward/backward chaining) to derive conclusions from the knowledge base.
• Explanation Facility: Answers "why" and "how" questions from the user, making the reasoning transparent.
• User Interface: Allows users to input queries and view results in natural language or structured form.
• Knowledge Acquisition Module: Helps experts add or modify rules in the knowledge base.

Types:

• Rule-based: MYCIN (medical diagnosis), DENDRAL (chemical analysis).
• Frame-based: Uses frames/schemas with slots and default values.

Unification finds the most general substitution that makes two expressions identical.

Algorithm:

function UNIFY(x, y, θ) returns substitution
  if θ = failure: return failure
  else if x = y: return θ
  else if VARIABLE?(x): return UNIFY-VAR(x, y, θ)
  else if VARIABLE?(y): return UNIFY-VAR(y, x, θ)
  else if COMPOUND?(x) and COMPOUND?(y):
    return UNIFY(x.ARGS, y.ARGS, UNIFY(x.OP, y.OP, θ))
  else if LIST?(x) and LIST?(y):
    return UNIFY(x.REST, y.REST, UNIFY(x.FIRST, y.FIRST, θ))
  else: return failure

Example: Unify P(x, f(y)) and P(A, f(B))

Step 1: unify P with P → θ = {}
Step 2: unify x with A → θ = {x/A}
Step 3: unify f(y) with f(B) → unify y with B → θ = {x/A, y/B}
MGU = {x/A, y/B}

Knowledge Base:

1. A → B
2. B → C
3. A

Goal: Prove C

Method 1: Forward Chaining

1. A is TRUE (given).
2. A → B, A is TRUE → B is TRUE (Modus Ponens).
3. B → C, B is TRUE → C is TRUE (Modus Ponens).
∴ C is proved. ✓

Method 2: Resolution

Step 1: Convert KB to CNF:
  (A → B)       ≡  (¬A ∨ B)           ... Clauses: {¬A, B}
  (B → C)       ≡  (¬B ∨ C)           ... Clauses: {¬B, C}
  A                              ... Clause:  {A}

Step 2: Negate the goal: ¬C

Step 3: Add to clause set: {¬C}

Step 4: Resolve:
  Resolve {A} and {¬A, B} → {B}
  Resolve {B} and {¬B, C} → {C}
  Resolve {C} and {¬C} → {} (empty clause)

Step 5: Empty clause derived → contradiction → Goal C is TRUE. ✓

Step 1: Encode in FOL

(1) ∀x (Man(x) → Mortal(x))
(2) Man(Socrates)
Goal: Mortal(Socrates)

Step 2: Convert to CNF (Skolemisation)

(1) ∀x (¬Man(x) ∨ Mortal(x))    → Clause: {¬Man(x), Mortal(x)}
(2) Man(Socrates)               → Clause: {Man(Socrates)}

Step 3: Negate the goal

¬Mortal(Socrates)               → Clause: {¬Mortal(Socrates)}

Step 4: Apply Resolution with Unification

Clause set:  {¬Man(x), Mortal(x)}
              {Man(Socrates)}
              {¬Mortal(Socrates)}

Resolve {Man(Socrates)} and {¬Man(x), Mortal(x)}:
  Unify: x = Socrates (MGU = {x/Socrates})
  Resolvent: {Mortal(Socrates)}

Resolve {Mortal(Socrates)} and {¬Mortal(Socrates)}:
  Unify: Mortal(Socrates) with Mortal(Socrates) (MGU = {})
  Resolvent: {}  (EMPTY CLAUSE) → Contradiction!

∴ ¬Mortal(Socrates) is FALSE → Mortal(Socrates) is TRUE. ✓

P(H|E) = P(E|H) × P(H) / P(E), where H = hypothesis, E = evidence.

A directed acyclic graph where nodes represent random variables and edges represent conditional dependencies. Used for probabilistic reasoning.

A form of many-valued logic where truth values range from 0 (false) to 1 (true) rather than just 0 or 1. Handles partial membership and reasoning with uncertainty.

A function μ(x) ∈ [0,1] that defines the degree of membership of element x in a fuzzy set. Example: μ_tall(180) = 0.8 means 180cm is 80% tall.

A tree structure where internal nodes test attributes, branches represent outcomes, and leaf nodes represent class labels. Used for classification in ML.

Entropy(S) = -Σ p_i log­₂(p_i), where p_i is the proportion of samples in class i. It measures impurity/uncertainty in a dataset.

Gain(S, A) = Entropy(S) - Σ (|S_v|/|S|) × Entropy(S_v). It measures the reduction in entropy when splitting on attribute A. ID3 selects the attribute with highest gain.

An algorithm for training neural networks. It computes the gradient of the loss function with respect to each weight using the chain rule, then updates weights via gradient descent.

Bayes' Theorem: P(H|E) = P(E|H) × P(H) / P(E)

Where P(E) = P(E|H)×P(H) + P(E|¬H)×P(¬H)

Example — Medical Diagnosis:

Disease D occurs in 1% of population: P(D) = 0.01, P(¬D) = 0.99.
Test T is 95% accurate: P(T+|D) = 0.95, P(T+|¬D) = 0.05.
A person tests positive. What is P(D|T+)?

P(D|T+) = P(T+|D) × P(D) / P(T+)
P(T+) = P(T+|D)×P(D) + P(T+|¬D)×P(¬D)
      = 0.95×0.01 + 0.05×0.99
      = 0.0095 + 0.0495 = 0.059

P(D|T+) = 0.95 × 0.01 / 0.059
         = 0.0095 / 0.059
         ≈ 0.161 (16.1%)

Despite a positive test, the probability of disease is only ~16% because the disease is rare (base rate fallacy).

Fuzzy Logic extends Boolean logic to handle partial truth values between 0 (completely false) and 1 (completely true).

Membership Function: Maps an input value to a degree of membership in a fuzzy set.

Example: Temperature "Hot" with triangular membership:

        1.0 ──┐
             │＼
             │ ＼
        0.5 ─┼──＼────
             │    ＼
        0.0 ─┴─────＼──
             25    30  35  (°C)

μ_hot(28°C) ≈ 0.6,  μ_hot(32°C) ≈ 0.4

Fuzzy Rules: IF-THEN rules with fuzzy conditions and fuzzy conclusions.

R1: IF temperature is HOT  THEN fan_speed is HIGH
R2: IF temperature is WARM THEN fan_speed is MEDIUM
R3: IF temperature is COOL  THEN fan_speed is LOW

Fuzzy Inference Steps: Fuzzification → Rule evaluation → Aggregation → Defuzzification.

Decision Tree is a flowchart-like structure for classification. Each internal node tests an attribute, each branch represents an outcome, and each leaf assigns a class.

ID3 Algorithm (Iterative Dichotomiser 3):

1. Compute entropy of the target variable for the current dataset.
2. For each attribute A, compute information gain.
3. Select the attribute with the highest gain as the splitting node.
4. Recursively repeat for each branch until all instances are classified or no attributes remain.

Entropy: Entropy(S) = -Σ p_i × log­₂(p_i) — measures impurity.

Information Gain: Gain(S, A) = Entropy(S) - Σ (|S_v|/|S|) × Entropy(S_v)

Dataset — Play Tennis:

Step 1: Compute Entropy of entire dataset (S):

Total = 14,  Yes = 9,  No = 5
Entropy(S) = -(9/14)log₂(9/14) - (5/14)log₂(5/14)
           = -(0.643 × -0.637) - (0.357 × -1.485)
           = 0.409 + 0.530 = 0.940

Step 2: Compute Gain for each attribute:

Gain(S, Outlook):

Sunny(5): Yes=2, No=3 → Entropy = -(2/5)log₂(2/5) - (3/5)log₂(3/5) = 0.971
Overcast(4): Yes=4, No=0 → Entropy = 0.0
Rain(5): Yes=3, No=2 → Entropy = -(3/5)log₂(3/5) - (2/5)log₂(2/5) = 0.971

Gain(Outlook) = 0.940 - [(5/14)×0.971 + (4/14)×0 + (5/14)×0.971]
             = 0.940 - [0.347 + 0 + 0.347]
             = 0.940 - 0.694 = 0.246

Gain(S, Humidity):

High(7): Yes=3, No=4 → Entropy = 0.985
Normal(7): Yes=6, No=1 → Entropy = 0.592

Gain(Humidity) = 0.940 - [(7/14)×0.985 + (7/14)×0.592]
               = 0.940 - [0.492 + 0.296]
               = 0.940 - 0.788 = 0.152

Gain(S, Wind):

Weak(8): Yes=6, No=2 → Entropy = 0.811
Strong(6): Yes=3, No=3 → Entropy = 1.000

Gain(Wind) = 0.940 - [(8/14)×0.811 + (6/14)×1.000]
            = 0.940 - [0.464 + 0.429]
            = 0.940 - 0.893 = 0.047

Step 3: Root node = Outlook (highest gain = 0.246)

Step 4: For Outlook=Overcast (pure node): Leaf → Play = Yes

Step 5: For Outlook=Sunny (5 samples): Gain(Humidity) = 0.971 - [(3/5)×0 + (2/5)×0] = 0.971, Gain(Wind) = 0.971 - [(2/5)×0 + (3/5)×0] = 0.971

Pick Humidity (or Wind): Humidity → Leaf Normal=Yes, Leaf High=No

Step 6: For Outlook=Rain (5 samples): Gain(Wind) = 0.971 - [(2/5)×0 + (3/5)×0] = 0.971

Pick Wind: Weak → Yes, Strong → No

Final Decision Tree:

         [Outlook]
         /    |    \
    Sunny  Overcast  Rain
      |       |       |
   [Humidity] Yes   [Wind]
   /      \          /   \
 High    Normal  Weak   Strong
  |        |       |       |
  No      Yes     Yes     No

Backpropagation is an algorithm for computing gradients in a feedforward neural network. It applies the chain rule of calculus layer by layer, from the output back to the input.

Network: 2 inputs, 1 hidden layer (2 neurons), 1 output

  x1 ──→ h1 ──→ y
    ↘  ↗     ↘  ↗
  x2 ──→ h2 ──→

Forward Pass:

z_h = w1·x1 + w2·x2 + b_h     (hidden pre-activation)
h   = σ(z_h)                       (hidden activation)

z_o = w3·h + b_o                 (output pre-activation)
ŷ   = σ(z_o)                       (predicted output)

Loss: L = (1/2) × (y - ŷ)² (MSE)

Backward Pass (gradient computation):

δ_o = (ŷ - y) × σ'(z_o)           (output error signal)

∂L/∂w3 = δ_o × h                  (gradient for output weights)
∂L/∂b_o = δ_o                     (gradient for output bias)

δ_h = (δ_o × w3) × σ'(z_h)        (hidden error signal)

∂L/∂w1 = δ_h × x1                 (gradient for hidden weights)
∂L/∂w2 = δ_h × x2
∂L/∂b_h = δ_h

Weight Update Rule (gradient descent):

w_new = w_old - η × ∂L/∂w

Where η (eta) is the learning rate (typically 0.01 to 0.1).

Complete Algorithm:

1. Initialise all weights and biases randomly.
2. For each epoch:
   a. Forward pass: compute predictions ŷ for all training samples.
   b. Compute loss L.
   c. Backward pass: compute ∂L/∂w for each weight using chain rule.
   d. Update: w ← w - η × ∂L/∂w
3. Repeat until loss converges.

Key insight: The chain rule allows gradients to propagate backward through the network: ∂L/∂w = (∂L/∂ŷ) × (∂ŷ/∂z) × (∂z/∂w).