Machine Learning

Machine Learning (ML) is a subset of Artificial Intelligence (AI) where systems learn from data to improve performance on a task without being explicitly programmed.

Definition (Tom Mitchell, 1997):

> A computer program is said to learn from experience E with respect to task T and performance measure P, if its performance on T, as measured by P, improves with experience E.

Traditional Programming vs ML:

Objective:

• Build systems that learn patterns from data
• Make predictions/decisions without hard-coded rules
• Generalize to unseen data

Scope:

• Classification, Regression, Clustering, Ranking
• Any domain with large data & complex patterns

Course Outcomes:

• Understand types of learning
• Apply supervised/unsupervised algorithms
• Evaluate and select appropriate ML models
• Understand deep learning basics

Three Main Types of Machine Learning:

1. Supervised Learning:

• Training data has labeled input-output pairs
• Model learns mapping: f(X) → Y
• Goal: Predict output for new inputs
• Sub-types:
• Classification: Predicts discrete class (spam/not spam)
• Regression: Predicts continuous value (house price)
• Examples: Linear Regression, Decision Tree, SVM, KNN

2. Unsupervised Learning:

• Training data has no labels
• Model finds hidden patterns/structure
• Goal: Discover groups or associations in data
• Sub-types:
• Clustering: Group similar items (K-Means)
• Association: Find item relationships (Apriori)
• Dimensionality Reduction: PCA, SVD
• Examples: K-Means, Hierarchical Clustering, GMM

3. Reinforcement Learning:

• Agent learns by interacting with environment
• Receives rewards for correct actions
• Goal: Maximize cumulative reward
• Examples: Q-Learning, SARSA, AlphaGo, Game AI

4. Semi-Supervised Learning:

• Uses small labeled + large unlabeled data
• Combines supervised + unsupervised techniques
• Cost-effective when labeling is expensive

Mnemonic: SUR = Supervised, Unsupervised, Reinforcement

Applications of Machine Learning:

Why ML is Growing?

• Exponential growth in data (Big Data)
• Powerful GPUs for computation
• Open-source libraries (TensorFlow, Scikit-learn)
• Cloud computing availability

Key Challenges:

• Data quality and quantity
• Overfitting vs Underfitting
• Interpretability (black box problem)
• Bias and fairness
• Privacy concerns

ML Pipeline:

Data Collection → Preprocessing → Feature Engineering
→ Model Training → Evaluation → Deployment → Monitoring

Linear Regression predicts a continuous output (Y) from input features (X) using a linear equation.

Simple Linear Regression (1 feature):

ŷ = w₀ + w₁·x

where w₀ = intercept (bias), w₁ = slope (weight)

Multiple Linear Regression (n features):

ŷ = w₀ + w₁x₁ + w₂x₂ + ... + wₙxₙ
   = Xw  (matrix form)

Cost Function — Mean Squared Error (MSE):

MSE = (1/m) Σᵢ (yᵢ - ŷᵢ)²

Goal: Find w that minimizes MSE

Training Methods:

1. Ordinary Least Squares (OLS) / Normal Equation:

w = (XᵀX)⁻¹ Xᵀy

• Closed-form solution
• Expensive if features are large (O(n³))

2. Gradient Descent:

w := w - α · (∂MSE/∂w)
∂MSE/∂w = (2/m) Xᵀ(Xw - y)

α = learning rate, repeat until convergence

Assumptions of Linear Regression:

• Linearity: Y and X are linearly related
• Independence: Residuals are independent
• Homoscedasticity: Constant variance of residuals
• Normality: Residuals are normally distributed
• No Multicollinearity among features

Evaluation Metrics:

• R² (coefficient of determination): closer to 1 = better
• MSE, RMSE, MAE

Naive Bayes is a probabilistic classifier based on Bayes' Theorem with a 'naive' assumption that all features are independent.

Bayes' Theorem:

P(C|X) = P(X|C) × P(C)
          ─────────────
              P(X)

Where:

• P(C|X) = posterior (probability of class C given features X)
• P(X|C) = likelihood
• P(C) = prior probability of class
• P(X) = evidence (normalizing constant)

Naive Assumption: Features are conditionally independent

P(X|C) = P(x₁|C) × P(x₂|C) × ... × P(xₙ|C)

Classification Rule:

ŷ = argmax_C [P(C) × ∏ P(xᵢ|C)]

Types of Naive Bayes:

Example (Spam Detection):

• Features: word frequencies
• Classes: Spam / Not Spam

Laplace Smoothing (handles zero probability):

P(xᵢ|C) = (count(xᵢ,C) + 1) / (count(C) + |V|)

Advantages: Fast, works well with small data, good for text

Disadvantages: Independence assumption rarely holds in practice

Decision Tree is a tree-like model where:

• Root Node = best splitting feature
• Internal Nodes = feature tests / conditions
• Leaf Nodes = class label or value
• Branches = outcomes of the test

Tree Construction Algorithm (ID3/C4.5/CART):

1. Select best feature to split (using criterion)
2. Create branch for each value of that feature
3. Recursively repeat for each sub-tree
4. Stop when: all samples same class, no more features,
   or max depth reached

Splitting Criteria:

1. Information Gain (ID3):

Entropy H(S) = -Σ pᵢ log₂(pᵢ)
IG(S,A) = H(S) - Σ |Sᵥ|/|S| × H(Sᵥ)

Choose feature A with highest IG

2. Gini Index (CART):

Gini(S) = 1 - Σ pᵢ²

Choose feature with lowest Gini (most pure split)

3. Gain Ratio (C4.5): IG / Split Information (handles multi-valued features)

Example — Play Tennis:

Outlook?
├── Sunny → Humidity?
│   ├── High → NO
│   └── Normal → YES
├── Overcast → YES
└── Rain → Wind?
    ├── Strong → NO
    └── Weak → YES

Overfitting Prevention:

• Pre-pruning: Stop early (min_samples, max_depth)
• Post-pruning: Build full tree, then prune (Reduced Error Pruning)

Advantages: Interpretable, handles mixed data, no scaling needed

Disadvantages: Prone to overfitting, unstable (small data change → big tree change)

K-Nearest Neighbor (KNN) is a lazy, non-parametric algorithm that classifies a new point based on the majority class of its K nearest training points.

Algorithm:

1. Store all training data
2. For new query point q:
   a. Compute distance to ALL training points
   b. Select K nearest neighbors
   c. Classification: majority vote
      Regression: average of K neighbors
3. Return predicted class/value

Distance Metrics:

Euclidean: d = √(Σ(xᵢ - yᵢ)²)    [most common]
Manhattan: d = Σ|xᵢ - yᵢ|
Minkowski: d = (Σ|xᵢ - yᵢ|^p)^(1/p)
Hamming:   For categorical features

Choosing K:

• Small K → Low bias, High variance (overfitting)
• Large K → High bias, Low variance (underfitting)
• Rule of thumb: K = √n, always use odd K for binary classification
• Use cross-validation to find optimal K

Example (K=3):

Query: new house (size=1200, rooms=3)
Find 3 nearest houses → 2 say "expensive", 1 says "cheap"
Prediction → "expensive"

Pros & Cons:

Feature Scaling: Always normalize/standardize features before KNN!

Logistic Regression is a classification algorithm (not regression) that predicts the probability of belonging to a class.

Sigmoid (Logistic) Function:

σ(z) = 1 / (1 + e^(-z))     z ∈ (-∞, +∞)
Output: σ(z) ∈ (0, 1)

Model:

z = w₀ + w₁x₁ + w₂x₂ + ... + wₙxₙ   (linear combination)
P(Y=1|X) = σ(z) = 1 / (1 + e^(-z))  (probability)

Prediction: ŷ = 1  if P(Y=1|X) ≥ 0.5
                0  if P(Y=1|X) < 0.5

Decision Boundary: z = 0 → σ(z) = 0.5

Cost Function — Binary Cross-Entropy (Log Loss):

L(w) = -(1/m) Σ [yᵢ log(ŷᵢ) + (1-yᵢ) log(1-ŷᵢ)]

(MSE not used because sigmoid makes it non-convex)

Training: Gradient Descent on Log Loss

Multi-class Classification:

• OvR (One-vs-Rest): Train K classifiers (one per class)
• Softmax Regression: Extension for multi-class

P(Y=k|X) = e^(wₖᵀx) / Σⱼ e^(wⱼᵀx)

Regularization (prevent overfitting):

• L2 (Ridge): Adds w² penalty → small weights

LR vs Linear Regression:

SVM finds the optimal hyperplane that maximizes the margin between two classes.

Key Concepts:

Hyperplane: Decision boundary in n-dimensional space

w·x + b = 0

Support Vectors: Data points closest to the hyperplane (they define the margin)

Margin: Distance between the two parallel hyperplanes touching support vectors

Margin = 2 / ||w||

SVM maximizes margin → Max-Margin Classifier

Optimization Problem (Hard Margin):

Minimize: (1/2)||w||²
Subject to: yᵢ(w·xᵢ + b) ≥ 1  ∀i

Soft Margin SVM (for non-separable data):

Minimize: (1/2)||w||² + C·Σξᵢ
Subject to: yᵢ(w·xᵢ + b) ≥ 1 - ξᵢ

C = regularization parameter:

• Large C → hard margin (less tolerance for misclassification)
• Small C → soft margin (more tolerance)

Kernel Trick (for non-linear data):

Map data to higher dimensional space without computing it explicitly

SVM for Regression (SVR): Fit data within an ε-tube

Pros: Works in high dimensions, kernel flexibility, robust to outliers

Cons: Slow training on large data, kernel choice is tricky

Random Forest is an ensemble of multiple Decision Trees, each trained on a random subset of data and features. Final prediction is by majority voting (classification) or averaging (regression).

Core Concept — Bagging (Bootstrap Aggregating):

1. Create B bootstrap samples (random sampling with replacement)
2. Train one Decision Tree on each sample
3. Each tree uses random subset of features at each split (√p features)
4. Aggregate predictions:
   - Classification: majority vote
   - Regression: average

Algorithm Steps:

For b = 1 to B:
  1. Draw bootstrap sample Sᵦ from training data
  2. Grow tree Tᵦ on Sᵦ:
     - At each node, randomly select m features
     - Split on best among m features
     - Grow tree to maximum depth
Final Prediction = MajorityVote{T₁(x), T₂(x), ..., Tᴮ(x)}

Feature Importance:

Measures how much each feature reduces impurity across all trees

Importance(fᵢ) = mean decrease in Gini/Entropy for feature i

Out-of-Bag (OOB) Error:

• ~37% of data not used in each bootstrap sample
• Use as validation set → OOB error = unbiased estimate

Hyperparameters:

Random Forest vs Decision Tree:

K-Means Clustering partitions n data points into K clusters, minimizing intra-cluster variance.

Objective (Cost Function):

Minimize: J = Σₖ Σ_{x∈Cₖ} ||x - μₖ||²

Where μₖ = centroid of cluster k

Algorithm Steps:

1. Initialize: Choose K random centroids μ₁, μ₂, ..., μₖ
2. Assignment Step:
   For each point xᵢ:
   Assign to nearest centroid:
   cᵢ = argmin_k ||xᵢ - μₖ||²
3. Update Step:
   Recompute centroids:
   μₖ = (1/|Cₖ|) Σ_{xᵢ∈Cₖ} xᵢ
4. Repeat steps 2-3 until centroids don't change
   (convergence) or max_iterations reached

Choosing K — Elbow Method:

• Plot J (inertia) vs K
• Look for the 'elbow' point where J stops decreasing rapidly
• That K is optimal

Silhouette Score:

s(i) = (b(i) - a(i)) / max(a(i), b(i))
a(i) = mean intra-cluster distance
b(i) = mean nearest-cluster distance
Range: [-1, 1]  → closer to 1 = better

Initialization Strategies:

• Random: Pick K random points (may converge to local minimum)
• K-Means++: Choose centroids far apart (better convergence)

Limitations:

• Must specify K in advance
• Sensitive to initialization and outliers
• Assumes spherical, equal-size clusters
• Stuck in local minima

Time Complexity: O(n·K·d·I) — n=points, K=clusters, d=dims, I=iterations

Hierarchical Clustering builds a tree of clusters (dendrogram) without needing to specify K in advance.

Two Types:

1. Agglomerative (Bottom-Up) — more common:

1. Start: Each point is its own cluster (n clusters)
2. Find the two closest clusters
3. Merge them into one cluster
4. Update distance matrix
5. Repeat steps 2-4 until one cluster remains

2. Divisive (Top-Down):

1. Start: All points in one cluster
2. Split into two sub-clusters
3. Recursively split each sub-cluster
4. Stop when each cluster has one point

Linkage Methods (Distance between clusters):

Dendrogram:

• Y-axis = distance/dissimilarity at which clusters merge
• Cut at height h → get number of clusters
• No need to specify K beforehand

Advantages over K-Means:

• No need to specify K
• Produces dendrogram (full hierarchy)
• Works with any distance metric
• Can capture non-spherical clusters

Disadvantages:

• O(n²) memory, O(n²log n) time — slow on large data
• Cannot undo merges (greedy)
• Sensitive to noise and outliers

Association Rule Mining discovers interesting relationships (rules) between items in large datasets.

Market Basket Example: {Bread, Butter} → {Milk}

If a customer buys Bread and Butter, they also buy Milk.

Key Metrics:

1. Support: How often itemset appears

Support(A) = Count(A) / Total Transactions
Support(A→B) = Count(A∪B) / Total Transactions

2. Confidence: Reliability of the rule

Confidence(A→B) = Support(A∪B) / Support(A)
                = P(B|A)

3. Lift: Rule strength vs. random chance

Lift(A→B) = Confidence(A→B) / Support(B)
           = P(A∪B) / (P(A) × P(B))

• Lift > 1 → A and B are positively correlated
• Lift = 1 → A and B are independent
• Lift < 1 → A and B are negatively correlated

Apriori Algorithm:

Key Property (Apriori Principle):

> If an itemset is frequent, ALL its subsets are also frequent.

> If an itemset is infrequent, ALL its supersets are infrequent.

Steps:

1. Find all frequent 1-itemsets (support ≥ min_support)
2. Generate candidate 2-itemsets from frequent 1-itemsets
3. Prune using Apriori principle
4. Find frequent 2-itemsets
5. Repeat until no new frequent itemsets found
6. Generate rules from frequent itemsets (confidence ≥ min_conf)

Limitation: Many database scans, large candidate sets → FP-Growth is faster

FP-Growth (Frequent Pattern Growth) finds frequent itemsets without generating candidates, using a compact tree structure.

Advantages over Apriori:

• Only 2 database scans (Apriori needs many)
• No candidate generation
• Much faster on large databases

FP-Tree Construction:

Scan 1: Find frequent 1-itemsets + their support
Order: Sort items by decreasing support

Scan 2: Build FP-Tree
- Root node = null
- For each transaction:
  - Remove infrequent items
  - Sort remaining by frequency order
  - Insert into FP-Tree (share prefixes)

Header Table: Links all occurrences of each item in the tree

Mining FP-Tree:

For each frequent item i (bottom-up):
1. Find conditional pattern base
   (all prefix paths ending at i)
2. Build conditional FP-tree for i
3. If conditional FP-tree ≠ empty:
   → Mine it recursively
4. Generate frequent itemsets with i as suffix

Example:

Transactions (min_sup=2):
T1: {A,B,C}   T2: {A,C}   T3: {B,C}   T4: {A,B,C,D}

Frequent items (sorted by freq): C:4, A:3, B:3, D:1
Build FP-Tree sharing common prefixes

Comparison:

Gaussian Mixture Model (GMM) is a probabilistic clustering model that assumes data is generated from a mixture of K Gaussian distributions.

Model:

P(x) = Σₖ πₖ × N(x | μₖ, Σₖ)
Where:
- πₖ = mixing coefficient (weight of component k)
- N(x|μₖ,Σₖ) = Gaussian with mean μₖ, covariance Σₖ
- Σπₖ = 1

GMM vs K-Means:

EM Algorithm for GMM:

E-Step (Expectation): Assign responsibilities

rₙₖ = πₖ N(xₙ|μₖ,Σₖ) / Σⱼ πⱼ N(xₙ|μⱼ,Σⱼ)
rₙₖ = P(component k | data point n)

M-Step (Maximization): Update parameters

Nₖ = Σₙ rₙₖ   (effective number of points in cluster k)
μₖ = (1/Nₖ) Σₙ rₙₖ xₙ
Σₖ = (1/Nₖ) Σₙ rₙₖ (xₙ-μₖ)(xₙ-μₖ)ᵀ
πₖ = Nₖ / N

Repeat E and M steps until log-likelihood converges:

log P(X) = Σₙ log Σₖ πₖ N(xₙ|μₖ,Σₖ)

Applications: Image segmentation, speech recognition, anomaly detection

Selecting K: Use BIC (Bayesian Information Criterion) or AIC

PCA is a dimensionality reduction technique that transforms data into a new coordinate system where directions of maximum variance are called Principal Components.

Goal: Reduce p features to d dimensions (d << p) while retaining maximum variance

PCA Algorithm Steps:

1. Standardize data: z = (x - μ) / σ
   (zero mean, unit variance)

2. Compute Covariance Matrix:
   C = (1/n) XᵀX   [p×p matrix]

3. Compute Eigenvalues (λ) and Eigenvectors (v) of C:
   Cv = λv

4. Sort eigenvectors by eigenvalues (descending)
   PC1 = direction of highest variance (λ₁)
   PC2 = direction of 2nd highest variance (λ₂)
   (PC2 ⊥ PC1)

5. Select top d eigenvectors: W = [v₁, v₂, ..., vd]

6. Project data: Z = XW   [n×d matrix]

Variance Explained:

Variance explained by PCᵢ = λᵢ / Σλⱼ
Cumulative variance = Σᵢ λᵢ / Σλⱼ

Choose d such that cumulative variance ≥ 95%

Properties:

• PCs are orthogonal (uncorrelated)
• PC1 explains most variance
• Linear transformation (no information about non-linear structure)

Applications:

• Face recognition (Eigenfaces)
• Gene expression analysis
• Noise reduction
• Visualization of high-D data
• Preprocessing before classification

Limitations: Linear only; PCA on sensitive data may lose discriminative info

SVD decomposes any matrix A into three matrices:

A = U Σ Vᵀ
Where:
A = m×n matrix (original data)
U = m×m orthogonal matrix (left singular vectors)
Σ = m×n diagonal matrix (singular values σ₁ ≥ σ₂ ≥ ... ≥ 0)
Vᵀ= n×n orthogonal matrix (right singular vectors)

Singular Values (σᵢ): Square roots of eigenvalues of AᵀA

Truncated SVD (for dimensionality reduction):

A ≈ Uₖ Σₖ Vₖᵀ   (keep top-k singular values)

This is the best rank-k approximation of A (Eckart-Young theorem)

SVD vs PCA:

Applications of SVD:

1. Image Compression:

Store only U_k, Σ_k, V_k instead of full image
Compression ratio = k(m+n+1) / mn

2. Latent Semantic Analysis (LSA):

• Document-term matrix → SVD → topic vectors

3. Collaborative Filtering (Matrix Factorization):

User-Item matrix R ≈ U Σ Vᵀ
→ Fill missing ratings

4. Pseudoinverse (Moore-Penrose):

A⁺ = V Σ⁺ Uᵀ

Solves least squares: x = A⁺b

Feature Selection removes irrelevant/redundant features to improve model performance, reduce overfitting, and speed up training.

1. Filter Methods:

Select features based on statistical properties, independent of ML model.

[Feature Ranking by Statistics] → [Select top-k features] → [Train Model]

Techniques:

• Correlation Coefficient: Pearson r between feature and target
• Chi-Square Test (χ²): For categorical features vs categorical target
• ANOVA F-test: Continuous features vs categorical target
• Mutual Information: How much info feature provides about target
• Variance Threshold: Remove low-variance features

Pros: Fast, scalable, no model dependency

Cons: Ignores feature interactions, model-agnostic

2. Wrapper Methods:

Use ML model performance to evaluate feature subsets.

[Feature Subset] → [Train Model] → [Evaluate] → [Update Subset]

Techniques:

• Forward Selection: Start empty, add best feature one by one
• Backward Elimination: Start with all, remove worst one by one
• RFE (Recursive Feature Elimination): Train model, rank features by importance, remove weakest, repeat

Pros: Considers feature interactions, model-specific

Cons: Computationally expensive (O(2^n) subsets)

3. Embedded Methods:

Feature selection happens during model training (built-in).

[Train Model with Regularization] → [Automatically selects features]

Techniques:

• LASSO (L1): Drives some weights to exactly zero
• Ridge (L2): Shrinks weights but rarely to zero
• Decision Tree / Random Forest: Feature importance via impurity reduction
• ElasticNet: L1 + L2 combination

Pros: No separate selection step, considers all features together

Cons: Model-specific

Model Evaluation measures how well a model generalizes to unseen data.

Confusion Matrix (Binary Classification):

                 Predicted
              Positive  Negative
Actual Pos |   TP    |   FN   |
Actual Neg |   FP    |   TN   |

• TP = True Positive (correctly predicted positive)
• TN = True Negative (correctly predicted negative)
• FP = False Positive (Type I error)
• FN = False Negative (Type II error)

Metrics:

Accuracy  = (TP+TN) / (TP+TN+FP+FN)
Precision = TP / (TP+FP)    [of predicted +ve, how many correct?]
Recall    = TP / (TP+FN)    [of actual +ve, how many detected?]
F1-Score  = 2×(P×R)/(P+R)  [harmonic mean of P and R]
Specificity = TN/(TN+FP)

When to use which:

• Accuracy: When classes are balanced
• Precision: When FP is costly (spam filter)
• Recall: When FN is costly (cancer detection)
• F1: When both FP and FN matter

ROC Curve & AUC:

• Plot TPR (Recall) vs FPR at different thresholds
• AUC (Area Under Curve): 0.5 = random, 1.0 = perfect

Cross-Validation (k-fold):

1. Split data into k folds
2. For each fold i: train on k-1 folds, test on fold i
3. Average performance across k folds

Typically k=5 or k=10

Bias-Variance Tradeoff:

• Underfitting: High bias, high training error (too simple model)
• Overfitting: High variance, low training but high test error (too complex)
• Goal: Balance bias and variance via regularization/model complexity

Semi-Supervised Learning uses a small amount of labeled data and a large amount of unlabeled data for training.

Why it matters: Labeling data is expensive (e.g., medical images need experts). Unlabeled data is cheap and abundant.

Assumptions:

• Smoothness Assumption: Points close together likely have same label
• Cluster Assumption: Points in same cluster likely have same label
• Manifold Assumption: Data lies on low-dimensional manifold

Common Approaches:

1. Self-Training:

1. Train model on labeled data
2. Predict labels for unlabeled data
3. Add high-confidence predictions to labeled set
4. Retrain model
5. Repeat until no more confident predictions

2. Label Propagation:

• Build graph where nodes = data points, edges = similarity
• Propagate labels from labeled to unlabeled nodes through edges
• Labels spread to similar unlabeled points

3. Co-Training:

• Split features into two views
• Train two classifiers on each view
• Each classifier labels unlabeled data for the other

4. Generative Models (GMM/VAE):

• Learn data distribution from all data (labeled + unlabeled)
• Use distribution to improve classification

Applications:

• Web page classification (few labeled, many unlabeled pages)
• Medical image analysis
• Speech recognition
• NLP (few labeled sentences, large unlabeled corpus)

vs. Supervised vs Unsupervised:

Markov Decision Process (MDP) is the mathematical framework for Reinforcement Learning.

MDP is defined by a 5-tuple (S, A, P, R, γ):

Markov Property:

> The future depends only on the present state, NOT the history.

P(Sₜ₊₁ | Sₜ, Aₜ, Sₜ₋₁, Aₜ₋₁...) = P(Sₜ₊₁ | Sₜ, Aₜ)

Policy π:

π(a|s) = P(Action=a | State=s)

A policy maps states to actions. Goal: Find optimal policy π*.

Return (Cumulative Reward):

Gₜ = Rₜ₊₁ + γRₜ₊₂ + γ²Rₜ₊₃ + ...
   = Σₖ γᵏ Rₜ₊ₖ₊₁

γ near 0 → shortsighted; γ near 1 → far-sighted

Value Function:

Vπ(s) = Eπ[Gₜ | Sₜ=s] = Expected return from state s under policy π

Q-Function (Action-Value):

Qπ(s,a) = Eπ[Gₜ | Sₜ=s, Aₜ=a] = Expected return from state s, taking action a

Optimal Policy:

π* = argmax_π Vπ(s)  ∀s
V*(s) = max_π Vπ(s)

Bellman Expectation Equation:

Vπ(s) = Σ_a π(a|s) Σ_{s'} P(s'|s,a) [R(s,a) + γ Vπ(s')]

Value of state = expected immediate reward + discounted future value

Bellman Optimality Equation:

V*(s) = max_a Σ_{s'} P(s'|s,a) [R(s,a) + γ V*(s')]
Q*(s,a) = Σ_{s'} P(s'|s,a) [R(s,a) + γ max_{a'} Q*(s',a')]

Policy Evaluation (Prediction):

Given policy π, compute Vπ(s) for all states

Repeat until convergence:
  Vₙₑw(s) = Σ_a π(a|s) Σ_{s'} P(s'|s,a)[R(s,a) + γ·Vₒₗd(s')]

Policy Improvement:

Given Vπ, find better policy π':

π'(s) = argmax_a Σ_{s'} P(s'|s,a)[R(s,a) + γ Vπ(s')]

Policy Iteration (GPI):

1. Initialize π randomly
2. Policy Evaluation: compute Vπ
3. Policy Improvement: π' = greedy(Vπ)
4. If π' ≠ π: set π = π', go to step 2
5. Return π* (optimal policy)

Converges in finite steps for finite MDPs

Value Iteration:

Repeat until convergence:
  V(s) ← max_a Σ_{s'} P(s'|s,a)[R(s,a) + γ·V(s')]
Extract policy: π*(s) = argmax_a Σ_{s'} P(s'|s,a)[R(s,a) + γ·V(s')]

Combines policy evaluation + improvement in one step

Comparison:

Monte Carlo (MC) Methods:

Learn directly from complete episodes of experience (no model of environment needed).

MC Policy Evaluation:

1. Generate complete episode: S₀,A₀,R₁,S₁,A₁,R₂,...,Sₜ
2. Compute return Gₜ for each state visited
3. Update V(s) = average of all returns for state s:
   V(s) ← V(s) + (1/N(s))[G - V(s)]
   or with learning rate α:
   V(s) ← V(s) + α[G - V(s)]

First-Visit MC: Update only on first visit to state in episode

Every-Visit MC: Update on every visit to state

Temporal Difference (TD) Learning:

Learn from incomplete episodes — update at every step (bootstrapping)

TD(0) Update:

V(Sₜ) ← V(Sₜ) + α[Rₜ₊₁ + γ·V(Sₜ₊₁) - V(Sₜ)]
         └──────────────────────────────────────┘
                     TD Error (δ)

TD Target: Rₜ₊₁ + γ·V(Sₜ₊₁) (one-step estimate)

Comparison:

TD(λ) — Bridge between MC and TD:

• λ=0: TD(0), λ=1: MC
• Eligibility traces: Credit assignment to past states

Q-Learning (Off-Policy TD Control):

Learns optimal Q* directly regardless of the policy being followed.

Q-Learning Update Rule:

Q(Sₜ,Aₜ) ← Q(Sₜ,Aₜ) + α[Rₜ₊₁ + γ·max_{a'} Q(Sₜ₊₁,a') - Q(Sₜ,Aₜ)]

• Uses max over next actions (greedy)
• Converges to Q* regardless of exploration policy
• Off-policy: Behavior policy (ε-greedy) ≠ Target policy (greedy)

Q-Learning Algorithm:

Initialize Q(s,a) = 0 for all s,a
For each episode:
  Initialize S
  Repeat:
    Choose A from S using ε-greedy policy
    Take action A → observe R, S'
    Q(S,A) ← Q(S,A) + α[R + γ·max_a Q(S',a) - Q(S,A)]
    S ← S'
  Until S is terminal

SARSA (On-Policy TD Control):

Learns Q for the policy actually being followed.

SARSA Update Rule:

Q(Sₜ,Aₜ) ← Q(Sₜ,Aₜ) + α[Rₜ₊₁ + γ·Q(Sₜ₊₁,Aₜ₊₁) - Q(Sₜ,Aₜ)]

• Uses actual next action Aₜ₊₁ (not max)
• Name comes from: (S, A, R, S', A') — the 5 elements used
• On-policy: Same policy used for behavior and learning

Q-Learning vs SARSA:

Exploration-Exploitation:

• ε-greedy: With prob ε explore random, with 1-ε exploit best
• Decrease ε over time for convergence

Recommendation Systems suggest relevant items to users (movies, products, songs).

1. Collaborative Filtering (CF):

Recommends items based on similar users' behavior — no item features needed.

User-Item Rating Matrix:

         Movie1  Movie2  Movie3  Movie4
User1:     5       ?       3       4
User2:     4       5       ?       2
User3:     ?       4       5       ?
User4:     2       ?       4       5

? = missing ratings to predict

a) Memory-Based CF:

• User-User CF: Find similar users → borrow their ratings

  Similarity = cosine(user_a, user_b) or Pearson correlation
  Predicted rating = weighted average of similar users' ratings

• Item-Item CF: Find similar items → predict from items user rated

b) Model-Based CF (Matrix Factorization):

R ≈ P × Qᵀ   (P=user factors, Q=item factors, k=latent dims)
Minimize: ||R - PQᵀ||² + λ(||P||² + ||Q||²)

ALS (Alternating Least Squares) or SGD used for training

2. Content-Based Filtering:

Recommends items similar to what the user liked, based on item features.

1. Build item feature profile (genre, director, keywords)
2. Build user preference profile from items they rated
3. Recommend items with highest cosine similarity to user profile
Sim(A,B) = (A·B) / (||A|| × ||B||)

3. Hybrid Systems:

Combine CF + Content-Based (e.g., Netflix)

Challenges: Cold Start problem (new users/items), scalability, data sparsity

Perceptron is the simplest neural network unit — a mathematical model of a biological neuron.

Perceptron Structure:

Inputs: x₁, x₂, ..., xₙ
Weights: w₁, w₂, ..., wₙ
Bias: b (or w₀)

Net input: z = w₁x₁ + w₂x₂ + ... + wₙxₙ + b = wᵀx + b
Output: ŷ = f(z)

Activation Functions:

Perceptron Learning Rule:

For each training example (x, y):
  1. Compute output: ŷ = f(wᵀx + b)
  2. Compute error: e = y - ŷ
  3. Update weights:
     w ← w + α·e·x
     b ← b + α·e
α = learning rate (small positive value)

Perceptron Convergence Theorem:

> If training data is linearly separable, the perceptron algorithm will converge in finite steps.

Limitations (Minsky & Papert, 1969):

• Can only classify linearly separable data
• Cannot solve XOR problem
• Solution: Multilayer Perceptron (MLP) + non-linear activations

Multilayer Perceptron (MLP) = Feedforward Neural Network with:

• Input Layer: Receives raw features
• Hidden Layer(s): Learn intermediate representations
• Output Layer: Produces predictions

Network Notation:

Layer l has nˡ neurons
Wˡ = weight matrix (nˡ × nˡ⁻¹)
bˡ = bias vector (nˡ × 1)
aˡ = activation vector (nˡ × 1)

Forward Pass:

For l = 1 to L:
  zˡ = Wˡ·aˡ⁻¹ + bˡ     (linear combination)
  aˡ = f(zˡ)              (apply activation function)

Final output: ŷ = aᴸ

Universal Approximation Theorem:

> A neural network with one hidden layer and enough neurons can approximate ANY continuous function.

Why Deep Networks?

• More layers → hierarchical feature learning
• Layer 1: edges → Layer 2: shapes → Layer 3: objects
• Exponentially more expressive than shallow networks

Backpropagation = Efficient algorithm to compute gradients of loss w.r.t. all weights using chain rule.

Loss Function:

MSE (Regression): L = (1/m)Σ(ŷ - y)²
Cross-Entropy (Classification): L = -Σ y log(ŷ)

Backpropagation Steps:

Step 1: Forward Pass

Compute z¹,a¹,z²,a²,...,aᴸ = ŷ and Loss L

Step 2: Backward Pass (Compute δ = Error Signals)

Output layer:    δᴸ = ∂L/∂zᴸ = (aᴸ - y) [for MSE + linear output]
Hidden layer l:  δˡ = (Wˡ⁺¹)ᵀ δˡ⁺¹ ⊙ f'(zˡ)  [chain rule]

Step 3: Compute Gradients

∂L/∂Wˡ = δˡ · (aˡ⁻¹)ᵀ
∂L/∂bˡ = δˡ

Step 4: Update Weights (Gradient Descent)

Wˡ ← Wˡ - α · ∂L/∂Wˡ
bˡ ← bˡ - α · ∂L/∂bˡ

Optimizers:

Vanishing Gradient Problem:

• Deep networks: gradients shrink to near-zero in early layers
• Solutions: ReLU activation, Batch Normalization, ResNets, proper initialization

Deep Learning = Machine Learning using deep neural networks (many layers) to automatically learn hierarchical representations.

Deep Learning vs Classical ML:

Why Deep Learning Works:

• Hierarchical representations (edges→shapes→objects)
• Universal approximators with depth
• GPU-accelerated matrix operations
• Large labeled datasets (ImageNet, Common Crawl)

Key Architectures:

1. CNN (Convolutional Neural Network):

Input Image → [Conv→ReLU→Pool]×n → Flatten → FC layers → Output

• Convolution: detect local features with filters
• Pooling: reduce spatial dimensions
• Applications: Image classification, detection, segmentation

2. RNN (Recurrent Neural Network):

hₜ = f(Wₕ hₜ₋₁ + Wₓ xₜ + b)

• Hidden state carries memory of past inputs
• LSTM/GRU: solve vanishing gradient in RNNs
• Applications: NLP, time-series, speech

3. Transformers (Attention-based):

• Self-attention mechanism
• Basis for GPT, BERT, modern LLMs

Regularization Techniques:

• Dropout: Randomly deactivate neurons (p=0.5) during training
• Batch Normalization: Normalize layer inputs
• L1/L2 Weight Decay: Penalize large weights
• Data Augmentation: Artificially expand training data