Learning & Decision Making — Reading Notes - MLAI401 Foundational AI & ML

1.Supervised Machine Learning

In classical knowledge engineering, rules are handcrafted by humans. In Supervised Machine Learning, the agent receives a dataset of labeled training examples D = {(⟨x₁, y₁⟩), …, (⟨x_N, y_N⟩)} and learns a statistical hypothesis function h: X → Y that generalizes accurately to unseen test instances.

1.1Text Features: Bag-of-Words & TF-IDF

Text is unstructured. To classify text with machine learning algorithms, documents must be mapped into numerical feature vectors.

Tokenization & Vocabulary: The raw text is split into tokens, normalized to lowercase, and mapped against a vocabulary index V = {w₁, …, w_|V|}.
Bag-of-Words (BoW): Represents document d as a multiset count vector x = ⟨c(w₁, d), …, c(w_|V|, d)⟩. Word order is discarded, but term frequencies provide strong topical signals.
Term Frequency (TF): The relative frequency of term t in document d: TF(t, d) = count(t, d) / |d|.
Inverse Document Frequency (IDF): Quantifies how much discriminative information a term carries across all N documents in corpus D:
IDF(t, D) = log[ N / DF(t) ] (where DF(t) is document frequency of term t)
TF-IDF Weighting: High TF-IDF means a word is frequent in the specific document but rare across the general corpus:
TF-IDF(t, d, D) = TF(t, d) × IDF(t, D)

1.2Naive Bayes Classification

Naive Bayes is a generative probabilistic classifier rooted in Bayes' Rule. Given a feature vector x = ⟨x₁, …, x_d⟩, the agent finds the class c ∈ C that maximizes the posterior probability (Maximum A Posteriori / MAP):

c^* = argmax_{c ∈ C} P(c | x) = argmax_{c ∈ C} [ P(c) · P(x | c) ]

The Conditional Independence Assumption asserts that all feature attributes are conditionally independent given the class:

P(x₁, …, x_d | c) = ∏_i=1^d P(x_i | c)

For text classification (Multinomial Naive Bayes), word counts multiply across the document. To prevent unseen words from multiplying the total probability to zero (the zero-probability trap), Laplace (Add-1) Smoothing is applied:

P̂(w | c) = [ count(w, c) + 1 ] / [ ∑_w' count(w', c) + |V| ]

In practice, computations are performed in log-space to prevent floating-point underflow:

c^* = argmax_{c ∈ C} [ log P(c) + ∑_i=1^d log P(x_i | c) ]

1.3Model Evaluation & Performance Metrics

Evaluating a classifier on held-out test data produces a 2×2 Confusion Matrix:

	Predicted Positive (1)	Predicted Negative (0)
Actual Positive (1)	True Positive (TP)	False Negative (FN) [Type II]
Actual Negative (0)	False Positive (FP) [Type I]	True Negative (TN)

Accuracy = (TP + TN) / (TP + TN + FP + FN)
Precision = TP / (TP + FP) [Quality of positive alarms]
Recall (Sensitivity) = TP / (TP + FN) [Completeness of detections]
F1-Score = 2 × (Precision × Recall) / (Precision + Recall) = 2TP / (2TP + FP + FN)

Accuracy Paradox: On imbalanced datasets (e.g. 99% legitimate emails, 1% spam), a degenerate model predicting everything as legitimate achieves 99% accuracy but 0% recall on spam. F1-Score balances precision and recall via the harmonic mean.

2.Neural Networks & Gradient Optimization

2.1The Perceptron Model & Linear Separability

The Perceptron computes a weighted linear sum of its inputs, shifts it by bias b, and passes it through an activation threshold:

z = w^T x + b = ∑_j=1^d w_j x_j + b → ŷ = step(z) = { 1 if z ≥ 0 else 0 }

A single perceptron defines a linear hyperplane in ℝ^d. In 1969, Minsky and Papert proved that single perceptrons cannot solve non-linearly separable problems like XOR (Exclusive OR).

2.2Multi-Layer Networks & Activation Functions

A Multi-Layer Perceptron (MLP) overcomes linear separability by inserting one or more hidden layers with non-linear activation functions:

Hidden Layer: h = g(W₁ x + b₁)
Output Layer: ŷ = σ(W₂ h + b₂)

Sigmoid (σ): σ(z) = 1 / (1 + e^-z) — maps ℝ → (0, 1) for binary probabilities.
ReLU (Rectified Linear Unit): ReLU(z) = max(0, z) — modern default; avoids vanishing gradients for positive inputs.

2.3Loss Functions & Gradient Descent

To train network weights w, we define a scalar Loss Function (e.g. Binary Cross-Entropy) and iteratively step in the direction of steepest descent:

Cross-Entropy Loss: L(w) = - [ y log(ŷ) + (1 - y) log(1 - ŷ) ]
Weight Update: w ← w - α ∇_w L(w)

where α > 0 is the learning rate governing the step size.

2.4Deep Learning Overview & Backpropagation

Deep neural networks learn hierarchical representations (e.g., Pixels → Edges → Textures → Parts → Objects). Gradients of the loss with respect to all layer weights are computed efficiently via the chain rule using the Backpropagation algorithm.

3.Unsupervised Learning: K-Means Clustering

3.1The K-Means Clustering Algorithm

In unsupervised learning, data points x₁, …, x_N have no teacher labels y. K-Means partitions N data points into K disjoint clusters C₁, …, C_K by minimizing the Within-Cluster Sum of Squares (WCSS):

WCSS = ∑_k=1^K ∑_{x ∈ C_k} ||x - μ_k||²

The algorithm alternates between two steps until convergence (Lloyd's Algorithm):

Assignment Step: Assign each point x_i to the nearest centroid: c_i = argmin_k ||x_i - μ_k||².
Update Step: Recalculate each centroid as the center of mass of its assigned points: μ_k = (1 / |C_k|) ∑_{x ∈ C_k} x.

3.2Voronoi Partitions & The Elbow Method

Cluster centroids partition the space into convex Voronoi Polygons. To choose the number of clusters K, the Elbow Method plots WCSS against K. The optimal K is located at the inflection bend ("elbow") where further clusters provide diminishing variance reduction.

4.Reinforcement Learning

4.1Markov Decision Processes (MDPs)

Reinforcement Learning studies agents that learn sequential decision policies through environmental interaction. A discrete-time Markov Decision Process is formally defined by the 5-tuple ⟨S, A, P, R, γ⟩:

State Space (S): Set of all valid environment states.
Action Space (A): Set of available actions in each state.
Transition Model (P): P(s' | s, a) = P(S_t+1=s' | S_t=s, A_t=a).
Reward Function (R): R(s, a, s') received after transition.
Discount Factor (γ ∈ [0, 1)): Discount factor for future rewards. Cumulative Return: G_t = ∑_k=0^∞ γ^k R_t+k+1.

State-Value Function: V^π(s) = 𝔼_π [ G_t | S_t = s ]
Action-Value Function: Q^π(s, a) = 𝔼_π [ G_t | S_t = s, A_t = a ]

4.2Bellman Equations & Value Iteration

The Bellman Optimality Equation expresses the value of a state under the optimal policy π^*:

V^*(s) = max_{a ∈ A} ∑_s' P(s' | s, a) [ R(s, a, s') + γ V^*(s') ]

Value Iteration turns this equation into an iterative dynamic programming update rule. Once values converge, the optimal policy is extracted greedily:

π^*(s) = argmax_{a ∈ A} ∑_s' P(s' | s, a) [ R(s, a, s') + γ V^*(s') ]

4.3Model-Free RL: Tabular Q-Learning & SARSA

When transition probabilities P and rewards R are unknown, the agent learns directly from experience transitions (s, a, r, s') via Temporal Difference learning:

TD Target = r + γ max_a' Q(s', a')
TD Error: δ = TD Target - Q(s, a)
Q-Learning Update Rule: Q(s, a) ← Q(s, a) + α [ r + γ max_a' Q(s', a') - Q(s, a) ]

To balance Exploration vs. Exploitation, the agent uses an ε-greedy policy: selecting the best known action with probability 1 - ε and a random exploratory action with probability ε.

5.Paradigm Comparison

5.1Comparing Learning & Decision Paradigms

Dimension	1. Naive Bayes (Supervised)	2. Neural Networks	3. K-Means (Unsupervised)	4. Value Iteration (MDP)	5. Q-Learning (Model-Free RL)
Task Goal	Classify text `x → y`	Non-linear mapping `x → y`	Cluster unlabeled `x`	Optimal policy in known MDP	Learn policy by interaction
Feedback	Ground-truth labels `y`	Ground-truth labels `y`	None (unlabeled)	Known transition & reward	Scalar delayed reward `r`
Optimization	MLE counts + Laplace	Gradient Descent	Lloyd's Algorithm (EM)	Bellman Dynamic Prog	Temporal Difference TD(0)
Complexity	O(N · d) Linear	O(N · epochs · \|W\|)	O(N · K · d · iters)	O(\|A\| · \|S\|²)	O(1) per step

6.Practice Exercises & Worked Solutions

Exercise 1

Bag-of-Words & TF-IDF Calculation

Consider a corpus of N = 3 documents:

d1: "win cash prize" (3 words)
d2: "win lottery bonus cash" (4 words)
d3: "team project meeting" (3 words)

Compute the Term Frequency TF("cash", d1), Inverse Document Frequency IDF("cash", D), and the resulting TF-IDF("cash", d1) (using standard natural log formula IDF = log(N / DF)).

Step-by-step Calculation

1. Term Frequency in d1:
   count("cash", d1) = 1, total words in d1 = 3
   TF("cash", d1) = 1 / 3 ≈ 0.3333

2. Document Frequency DF across corpus:
   "cash" appears in d1 and d2 → DF("cash") = 2
   Total documents N = 3
   IDF("cash", D) = ln(3 / 2) = ln(1.5) ≈ 0.4055

3. TF-IDF Score:
   TF-IDF("cash", d1) = 0.3333 × 0.4055 ≈ 0.1352

Exercise 2

Naive Bayes Spam Classification with Laplace Smoothing

Given training counts across a vocabulary |V| = 6 (words: lottery, prize, cash, meeting, report, project):

Spam (N=4 docs): Total words = 12. Word counts: lottery=4, prize=4, cash=3, meeting=0, report=0, project=1. Prior P(Spam) = 4/10 = 0.4.
Ham (N=6 docs): Total words = 18. Word counts: lottery=0, prize=0, cash=1, meeting=6, report=6, project=5. Prior P(Ham) = 6/10 = 0.6.

Classify the test message "lottery prize" using Laplace Add-1 smoothing.

Likelihood & Posterior Calculation

Denominator with Add-1 smoothing:
  Spam denominator = 12 + |V| = 12 + 6 = 18
  Ham denominator  = 18 + |V| = 18 + 6 = 24

Word Likelihoods:
  P(lottery | Spam) = (4 + 1) / 18 = 5/18 ≈ 0.2778
  P(prize | Spam)   = (4 + 1) / 18 = 5/18 ≈ 0.2778

  P(lottery | Ham)  = (0 + 1) / 24 = 1/24 ≈ 0.0417
  P(prize | Ham)    = (0 + 1) / 24 = 1/24 ≈ 0.0417

Unnormalized Posteriors:
  Spam Score = P(Spam) × P(lottery|Spam) × P(prize|Spam)
             = 0.4 × (5/18) × (5/18) = 0.4 × 0.07716 ≈ 0.03086

  Ham Score  = P(Ham) × P(lottery|Ham) × P(prize|Ham)
             = 0.6 × (1/24) × (1/24) = 0.6 × 0.001736 ≈ 0.00104

Normalized Probability:
  P(Spam | "lottery prize") = 0.03086 / (0.03086 + 0.00104) ≈ 96.7%

Decision: SPAM (MAP Rule)

Exercise 3

Confusion Matrix, Precision, Recall, and F1-Score

A spam filter is tested on 1,000 emails resulting in: TP = 80, FP = 20, FN = 10, TN = 890. Compute Accuracy, Precision, Recall, and F1-Score.

Metrics Calculation

Accuracy  = (TP + TN) / Total = (80 + 890) / 1000 = 970 / 1000 = 97.0%
Precision = TP / (TP + FP)    = 80 / (80 + 20)   = 80 / 100  = 80.0%
Recall    = TP / (TP + FN)    = 80 / (80 + 10)   = 80 / 90   = 88.89%
F1-Score  = 2 × (0.80 × 0.8889) / (0.80 + 0.8889)
          = 1.4222 / 1.6889 ≈ 0.8421 (84.21%)

Exercise 4

Perceptron Learning Rule Update Step

Given weights w = [0.2, -0.4], bias b = 0.1, learning rate α = 0.5, and an input sample x = [1, 2] with true target y = 1. Perform one step of the Perceptron learning rule.

Perceptron Step

1. Forward activation:
   z = w1·x1 + w2·x2 + b = 0.2(1) + (-0.4)(2) + 0.1 = 0.2 - 0.8 + 0.1 = -0.5
   ŷ = step(z) = step(-0.5) = 0

2. Error:
   error = y - ŷ = 1 - 0 = 1

3. Weight Update (w ← w + α · error · x):
   w1' = 0.2 + 0.5(1)(1) = 0.2 + 0.5 = 0.7
   w2' = -0.4 + 0.5(1)(2) = -0.4 + 1.0 = 0.6
   b'  = 0.1 + 0.5(1) = 0.6

New Weights: w' = [0.7, 0.6], b' = 0.6

Exercise 5

K-Means Centroid Assignment & Shift

Consider 4 2D points: A(1, 1), B(2, 1), C(4, 5), D(5, 5) and initial centroids μ₁ = (1, 2) and μ₂ = (5, 4). Assign each point to its closest centroid and compute the new centroids.

Assignment & Update Step

Squared Euclidean Distances to μ1(1,2) vs μ2(5,4):
  Point A(1,1): dist²(μ1) = (1-1)² + (1-2)² = 1
                dist²(μ2) = (1-5)² + (1-4)² = 16 + 9 = 25 → Cluster 1
  Point B(2,1): dist²(μ1) = (2-1)² + (1-2)² = 1 + 1 = 2
                dist²(μ2) = (2-5)² + (1-4)² = 9 + 9 = 18  → Cluster 1
  Point C(4,5): dist²(μ1) = (4-1)² + (5-2)² = 9 + 9 = 18
                dist²(μ2) = (4-5)² + (5-4)² = 1 + 1 = 2   → Cluster 2
  Point D(5,5): dist²(μ1) = (5-1)² + (5-2)² = 16 + 9 = 25
                dist²(μ2) = (5-5)² + (5-4)² = 0 + 1 = 1   → Cluster 2

Centroid Update:
  μ1' = mean(A, B) = ((1+2)/2, (1+1)/2) = (1.5, 1.0)
  μ2' = mean(C, D) = ((4+5)/2, (5+5)/2) = (4.5, 5.0)

Exercise 6

Bellman Value Iteration Step on 4×3 Grid World

In the 4×3 Grid World, state (3, 3) is adjacent to the goal state (4, 3) with value +1.0. Living reward R = -0.04 and discount γ = 0.99. Current values: V(3,3)=0.70, V(3,2)=0.65, V(2,3)=0.60. Transition probabilities: intended direction 0.8, left slip 0.1, right slip 0.1. Compute the expected value for action Right.

Action Value Calculation

Action Right from (3,3):
- Intended (0.8) → Goal (4,3) with value 1.0
- Slip Left (0.1) → North wall bounce (stays at 3,3 with value 0.70)
- Slip Right (0.1) → South (3,2 with value 0.65)

Expected Future Value:
  E[V(s')] = 0.8(1.0) + 0.1(0.70) + 0.1(0.65)
           = 0.800 + 0.070 + 0.065 = 0.935

Q((3,3), Right) = R + γ · E[V(s')]
                = -0.04 + 0.99(0.935)
                = -0.04 + 0.92565 = 0.88565

Exercise 7

Q-Learning Step-by-Step TD Update

An RL agent in state s = (3,3) has prior Q((3,3), Right) = 0.50. It takes action Right, receives living reward r = -0.04, and lands in terminal goal state (4,3) with terminal value 0.0. Given learning rate α = 0.2 and discount γ = 0.99, compute the TD target, TD error δ, and updated Q((3,3), Right).

Q-Learning Update

1. TD Target (Goal reward + terminal max Q):
   TD Target = r_goal + γ · max Q(terminal, a') = 1.0 + 0.99(0.0) = 1.00

2. TD Error δ:
   δ = TD Target - Q((3,3), Right) = 1.00 - 0.50 = +0.50

3. Q-Value Update:
   Q_new = Q_old + α · δ = 0.50 + 0.2(0.50) = 0.50 + 0.10 = 0.60