Machine Learning (CY-701) - Unit 5 Short Notes

UNIT 5: MACHINE LEARNING - COMPREHENSIVE NOTES

I. FOUNDATIONS & OVERARCHING CONCEPTS

Definition & Importance of Machine Learning

• Definition: A field of AI focused on developing systems that learn from data without explicit programming. It builds models from example inputs to make predictions or decisions.

• Perspectives:

  • AI: Enables systems to adapt and improve.

  • Statistics: Focuses on inference from data, uncertainty.

  • Engineering: Solves practical problems with scalable algorithms.

• Key Issues: Data quality/quantity, model selection, evaluation metrics, computational scalability, interpretability.

• Applications: Spam detection, recommendation systems, medical diagnosis, autonomous vehicles, natural language processing.

[!TIP] Exam Focus: Be ready to define ML and contrast its perspectives with examples.

Data Preprocessing & Feature Engineering

• Importance: Raw data is often noisy, incomplete, or in an unsuitable format. Preprocessing improves model convergence, stability, and performance.

• Normalization/Standardization:

  • Normalization (Min-Max Scaling): Rescales features to a fixed range, usually [0, 1].

$$X_{\text{norm}} = \frac{X - X_{\min}}{X_{\max} - X_{\min}}$$

*   **Standardization (Z-score):** Transforms data to have mean=0, std=1. 

$$X_{\text{std}} = \frac{X - \mu}{\sigma}$$

*   **Impact:** Essential for gradient descent-based algorithms (faster convergence) and distance-based algorithms (K-NN, SVM).

• Encoding Categorical Variables:

  • Label Encoding: Assigns an integer to each category. Can imply ordinal relationship (misleading for nominal data).

  • One-Hot Encoding: Creates a binary column for each category. No ordinal implication but increases dimensionality significantly (curse of dimensionality).

Model Evaluation & Validation

• Regression Metrics:

  • MSE (Mean Squared Error):

$$MSE = \frac{1}{n}\sum_{i=1}^{n}(y_i - \hat{y}_i)^2$$

(Sensitive to outliers).

*   **MAE (Mean Absolute Error):** 

$$MAE = \frac{1}{n}\sum_{i=1}^{n}\|y_i - \hat{y}_i\|$$

(Robust to outliers).

*   **R² (Coefficient of Determination):** Proportion of variance explained. 

$$R^2 = 1 - \frac{\sum(y_i - \hat{y}_i)^2}{\sum(y_i - \bar{y})^2}$$

• Classification Metrics (from Confusion Matrix):

  • Accuracy: $$\displaystyle \frac{TP+TN}{Total} $$ (Misleading for imbalanced data).

  • Precision: $$\displaystyle \frac{TP}{TP+FP} $$ (Of predicted positives, how many are correct?).

  • Recall (Sensitivity): $$\displaystyle \frac{TP}{TP+FN} $$ (Of actual positives, how many found?).

  • F1-Score: Harmonic mean of Precision & Recall.

$$F1 = 2 \times \frac{\text{Precision} \times \text{Recall}}{\text{Precision} + \text{Recall}}$$

*   **ROC-AUC:** Area under ROC curve (trade-off between TPR & FPR).

• Cross-Validation (k-fold): Data split into k folds; model trained k times, each time on k-1 folds, validated on the held-out fold. Provides robust performance estimate.

• Overfitting vs. Underfitting:

  • Overfitting: High training accuracy, low validation/test accuracy. Model learns noise. Solutions: More data, regularization, simpler model, pruning, dropout.

  • Underfitting: Low training & validation accuracy. Model too simple. Solutions: More complex model, feature engineering, reduce regularization.

• Data Splits: Training set (fit model), Validation set (tune hyperparameters), Test set (final evaluation, never used in training/tuning).

[!TIP] Common Pitfall: Using test set for model selection leads to overfitting to the test set. Always keep test set untouched until final evaluation.

Theoretical & Optimization Foundations

• Hypothesis Space (H): Set of all possible models/algorithms considered. Inductive Bias: Assumptions used to select one hypothesis over others (e.g., Occam's razor, smoothness).

• Convex Optimization: Optimization problem where any local minimum is a global minimum. Crucial for guaranteeing gradient descent finds the optimal solution for linear models.

• Linearity vs. Non-linearity:

  • Linear Models: Decision boundary is a straight line/hyperplane. Simple, interpretable, but limited to linearly separable data.

  • Non-linear Models: Use kernels (SVM) or multiple layers (NN) to capture complex patterns. Require more data and computation.

• Gradient Descent (GD): Iterative optimization algorithm to minimize loss function $J(\theta)$. Update rule:

$$\theta_{t+1} = \theta_t - \eta \nabla J(\theta_t)$$

where $\eta$ is learning rate.

• Loss Functions (Cost Functions): Measure error between predicted and actual values. Guides backpropagation.

  • Regression: MSE, MAE.

  • Classification: Cross-Entropy (Log Loss), Hinge Loss (SVM).

II. SUPERVISED LEARNING: CORE ALGORITHMS & THEORY

Linear & Logistic Regression

[!TIP] Key Difference: Linear regression predicts a value; logistic regression predicts a probability for classification.

Support Vector Machines (SVM)

• Goal: Find the optimal hyperplane that maximally separates classes by maximizing the margin (distance between hyperplane and nearest data points).

• Support Vectors: The critical training points lying on the margin boundaries. They solely define the decision boundary.

• Margin: For linearly separable data with weights $\mathbf{w}$ and bias $b$, margin $$\displaystyle = \frac{2}{\|\mathbf{w}\|} $$. Maximizing margin $\Rightarrow$ minimizing $$\displaystyle \frac{1}{2}\|\mathbf{w}\|^2 $$ subject to constraints.

• Kernel Trick: Maps data to a higher-dimensional space implicitly using a kernel function (e.g., Polynomial, RBF) to handle non-linear separation without explicit transformation.

• Applications: Bioinformatics (gene classification), image recognition (handwritten digits).

• Linear vs. Non-linear SVM: Linear SVM uses no kernel; Non-linear SVM uses kernel trick.

[!TIP] Exam Point: SVM is effective in high-dimensional spaces because the margin depends on support vectors, not total features. Kernel trick avoids computational cost of high-dimensional mapping.

Decision Trees

• Algorithm: Recursive partitioning. At each node, choose the feature and split point that maximally reduces impurity.

• Entropy & Information Gain:

  • Entropy (measure of impurity):

$$Entropy(t) = -\sum_{i=1}^{c} p_i \log_2 p_i$$

where $$\displaystyle p_i $$ is proportion of class $i$ at node $t$.

*   **Information Gain:** 

$$IG = Entropy(\text{parent}) - \sum \frac{N_{\text{child}}}{N_{\text{parent}}} Entropy(\text{child})$$

. Choose split with highest IG.

• Issues: Prone to overfitting (deep trees). Pruning (pre or post) removes branches to improve generalization.

• Other Splitting Criteria: Gini Impurity (CART):

$$Gini = 1 - \sum p_i^2$$

.

Instance-Based Learning: K-Nearest Neighbors (K-NN)

• Algorithm: For a new instance, find the k closest training instances (neighbors) in feature space, predict the majority class (classification) or average value (regression).

• Distance Metrics: Euclidean (most common), Manhattan, Minkowski, Hamming (categorical).

• Choice of k: Small k → high variance (overfitting); Large k → high bias (underfitting). Odd k avoids ties in binary classification.

• Lazy Learner: No explicit training phase; computation deferred until prediction.

Ensemble Methods (from Nov 2022)

• Bagging (Bootstrap Aggregating): Train multiple instances of same model on different bootstrapped subsets, combine by voting (classification) or averaging (regression). Reduces variance. Example: Random Forest.

• Boosting: Train models sequentially, each new model focuses on errors of previous ones. Combine by weighted sum. Reduces bias. Examples: AdaBoost, Gradient Boosting.

• Random Forest: Extension of bagging using decision trees. Uses random feature subset at each split. Regression output: Average of all trees' predictions.

• Stacking: Train multiple diverse base models, then use their predictions as input features for a final meta-learner (blender).

III. NEURAL NETWORKS & DEEP LEARNING FUNDAMENTALS

Artificial Neural Network (ANN) Basics

• Biological Inspiration: Neurons (dendrites, soma, axon) → computational model.

• Multi-Layer Perceptron (MLP): Feedforward network with input layer, one or more hidden layers, output layer. Each neuron: weighted sum + bias → activation function.

• Perceptron Learning Algorithm: For a single neuron.

  1. Initialize weights $\mathbf{w}$, bias $b$ randomly.

  2. For each training example $(\mathbf{x}, y)$:

     • Compute output: $$\displaystyle \hat{y} = f(\mathbf{w}^T\mathbf{x} + b) $$ (step function).

     • Update: $$\displaystyle w_i \leftarrow w_i + \eta (y - \hat{y}) x_i $$, $$\displaystyle b \leftarrow b + \eta (y - \hat{y}) $$.

  3. Repeat until convergence.

Training Neural Networks: Backpropagation

• Goal: Compute gradient of loss w.r.t. all weights to update them via gradient descent.

• Chain Rule: Core of backprop. Gradient flows backward from output layer to input layer.

• Steps (for one example):

  1. Forward Pass: Compute output and loss $L$ for given input.

  2. Backward Pass:

     • Compute $$\displaystyle \frac{\partial L}{\partial \text{output}} $$ (e.g., for cross-entropy with softmax).

     • Apply chain rule layer by layer: $$\displaystyle \frac{\partial L}{\partial w_{ij}^{(l)}} = \delta_j^{(l)} a_i^{(l-1)} $$, where $$\displaystyle \delta_j^{(l)} $$ is error term for neuron $j$ in layer $l$.

     • For hidden layer $l$: $$\displaystyle \delta_j^{(l)} = \left( \sum_k w_{jk}^{(l+1)} \delta_k^{(l+1)} \right) f'(z_j^{(l)}) $$.

  3. Update Weights: $$\displaystyle w_{ij}^{(l)} \leftarrow w_{ij}^{(l)} - \eta \frac{\partial L}{\partial w_{ij}^{(l)}} $$.

Activation Functions

[!TIP] Vanishing Gradient: In deep networks, gradients shrink exponentially during backprop through sigmoid/tanh, making early layers learn very slowly. ReLU helps but introduces dying ReLU.

Regularization Techniques

• L1 (Lasso) vs. L2 (Ridge):

  • Loss Function: $$\displaystyle J(\mathbf{w}) = \text{Original Loss} + \lambda \|\mathbf{w}\|_p $$

  • L1 ($$\displaystyle p=1 $$): $$\displaystyle \lambda \sum |w_i| $$. Drives some weights to exactly zero → automatic feature selection, sparse model.

  • L2 ($$\displaystyle p=2 $$): $$\displaystyle \lambda \sum w_i^2 $$. Shrinks weights uniformly but rarely to zero. Prevents any single weight from becoming too large.

  • Impact: Both prevent overfitting by penalizing large weights. L1 yields sparse solutions; L2 yields dense but small weights.

• Dropout: During training, randomly "drop" (set to 0) a fraction $p$ of neurons in a layer. Forces network to learn redundant representations, reduces co-adaptation. Not used during testing (use all neurons, scale activations by $1-p$ or use inverted dropout).

• Batch Normalization: Normalizes layer inputs (mini-batch) to have zero mean, unit variance. Then scales ($\gamma$) and shifts ($\beta$) with learnable parameters.

  • Purpose: Reduces internal covariate shift, allows higher learning rates, acts as regularizer.

  • Process: For mini-batch $B$: $$\displaystyle \mu_B = \frac{1}{m}\sum x_i $$, $$\displaystyle \sigma_B^2 = \frac{1}{m}\sum (x_i - \mu_B)^2 $$, $$\displaystyle \hat{x}_i = \frac{x_i - \mu_B}{\sqrt{\sigma_B^2 + \epsilon}} $$, $$\displaystyle y_i = \gamma \hat{x}_i + \beta $$.

Optimizers

• Types of Gradient Descent:

  • Batch GD: Uses entire dataset to compute gradient. Stable but slow for large data.

  • Stochastic GD (SGD): Uses one random example per update. Noisy but fast, can escape shallow minima.

  • Mini-batch GD: Uses a small random subset (mini-batch). Most common – balances noise and computational efficiency.

• Advanced Optimizers (adaptive learning rates):

  • RMSprop: Adapts learning rate per parameter using moving average of squared gradients.

$$v_t = \beta v_{t-1} + (1-\beta) g_t^2$$

,

$$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{v_t + \epsilon}} g_t$$

*   **Adam (Adaptive Moment Estimation):** Combines ideas from RMSprop and Momentum. Maintains moving averages of both gradient ($$\displaystyle m_t $$) and squared gradient ($$\displaystyle v_t $$). Includes bias-correction terms. **Default choice** for many deep learning tasks.

IV. CONVOLUTIONAL NEURAL NETWORKS (CNNs) - ARCHITECTURE & DESIGN

Core CNN Operations & Architecture

• Convolutional Layer: Applies filters (kernels) to input, producing feature maps. Captures local patterns (edges, textures).

  • Parameters: Filter size ($k \times k$), number of filters, stride, padding.

• Pooling/Sub-sampling (Max, Average): Reduces spatial dimensions (width, height), provides translation invariance, reduces parameters/computation.

  • Max Pooling: Takes maximum value in window. Most common, preserves dominant features.

  • Average Pooling: Takes average. Used in some architectures (e.g., Inception).

• Fully Connected (FC) Layers: At the end, flatten feature maps and use standard MLP for classification/regression.

• Flattening: Converts multi-dimensional feature map output from convolutional/pooling layers into a 1D vector for FC layers.

[!TIP] Why Downscale Image Size & Increase Filters? Early layers detect simple features (edges) on large feature maps. Deeper layers detect complex patterns (object parts) on smaller spatial maps but with more filters to capture diverse high-level features.

Convolutional Layer Design Choices

• 1x1 Convolution:

  • Purpose: Channel-wise feature transformation/reduction. Acts as a bottleneck to reduce computational cost before applying expensive $k \times k$ convolutions (e.g., in Inception). Increases non-linearity without changing spatial dimensions.

  • Example: In Inception module, 1x1 conv reduces channels before 3x3/5x5 convs.

• Padding:

  • Valid (No padding): Output size shrinks. $(W - F + 1) \times (H - F + 1)$.

  • Same (Zero padding): Output size same as input (if stride=1). Preserves spatial information at edges. Padding size = $$\displaystyle \frac{F-1}{2} $$.

• Stride: Number of pixels filter shifts each step. Larger stride → smaller output size, less overlap, more aggressive downsampling.

Advanced CNN Architectures & Concepts

• Inception Module/Network (GoogLeNet):

  • Structure: Parallel convolutions with different filter sizes (1x1, 3x3, 5x5) + max pooling, all concatenated at output.

  • 1x1 Convolution Role: Used as bottleneck before 3x3/5x5 to drastically reduce channel depth, making network computationally efficient.

  • Benefit: Captures multi-scale features efficiently in one module.

• Transfer Learning in CNNs:

  • Feature Extraction: Use pre-trained CNN (e.g., ResNet on ImageNet) as fixed feature extractor. Remove top FC layers, add new classifier for your task. Train only new layers.

  • Fine-Tuning: Unfreeze some of the top layers of the pre-trained network and jointly train them with new classifier. Requires more data.

• Designing CNN Depth/Width: Deeper networks (more layers) can learn hierarchical features but risk vanishing gradients (addressed by ResNet's skip connections). Wider networks (more filters per layer) increase capacity but also parameters/computation.

CNN Applications & Analysis

• Applications: Image classification, object detection (YOLO, Faster R-CNN), semantic segmentation (U-Net), face recognition.

• Identifying Overfitting/Underfitting in CNNs:

  • Overfitting: Training accuracy >> validation accuracy. Remedies: Data augmentation, dropout (after FC layers), L2 regularization, reduce network size, early stopping.

  • Underfitting: Both accuracies low. Remedies: Increase network depth/width, reduce regularization, train longer.

• Implementation (TensorFlow/Keras): Sequential/Functional API. Typical pattern: Conv2D -> Activation (ReLU) -> BatchNorm -> MaxPool2D repeated, then Flatten -> Dense -> Dropout -> Dense(softmax).

V. RECURRENT NEURAL NETWORKS (RNNs) & SEQUENTIAL MODELS

Vanilla RNN

• Architecture: Has a hidden state $$\displaystyle h_t $$ that is updated at each time step $t$ based on current input $$\displaystyle x_t $$ and previous hidden state $$\displaystyle h_{t-1} $$. Shared weights across time steps.

  • Equations: $$\displaystyle h_t = \tanh(W_{xh} x_t + W_{hh} h_{t-1} + b_h) $$, $$\displaystyle y_t = W_{hy} h_t + b_y $$.

  • Unfolding in Time: RNN can be seen as a deep network with one layer per time step, sharing weights.

• Limitations:

  • Vanishing/Exploding Gradients: During backprop through time (BPTT), gradients can shrink/vanish or grow/explode exponentially, making learning long-range dependencies difficult.

  • Short-term memory: Struggles to remember information from many steps ago.

Long Short-Term Memory (LSTM) & Gated Recurrent Unit (GRU)

• LSTM Architecture: Introduces a cell state $$\displaystyle c_t $$ (the "memory") and three gates to regulate information flow.

  • Forget Gate: $$\displaystyle f_t = \sigma(W_f \cdot [h_{t-1}, x_t] + b_f) $$ – decides what to discard from cell state.

  • Input Gate: $$\displaystyle i_t = \sigma(W_i \cdot [h_{t-1}, x_t] + b_i) $$, $$\displaystyle \tilde{c}_t = \tanh(W_c \cdot [h_{t-1}, x_t] + b_c) $$ – decides what new information to store.

  • Cell State Update: $$\displaystyle c_t = f_t \odot c_{t-1} + i_t \odot \tilde{c}_t $$.

  • Output Gate: $$\displaystyle o_t = \sigma(W_o \cdot [h_{t-1}, x_t] + b_o) $$, $$\displaystyle h_t = o_t \odot \tanh(c_t) $$.

  • How it handles long-term dependencies: The additive cell state update ($$\displaystyle c_t = f_t \odot c_{t-1} + ... $$) allows gradients to flow relatively unchanged through many time steps, mitigating vanishing gradient.

• GRU: Simpler variant with two gates (reset, update). Merges forget and input gates into a single update gate $$\displaystyle z_t $$. No separate cell state; hidden state $$\displaystyle h_t $$ acts as memory.

  • Update Gate: $$\displaystyle z_t = \sigma(W_z \cdot [h_{t-1}, x_t]) $$ – how much past to keep.

  • Reset Gate: $$\displaystyle r_t = \sigma(W_r \cdot [h_{t-1}, x_t]) $$ – how much past to forget for candidate activation.

  • $$\displaystyle h_t = (1 - z_t) \odot h_{t-1} + z_t \odot \tilde{h}_t $$.

• Comparison:

  • Vanilla RNN: Simple, fails on long sequences.

  • LSTM: More parameters, more powerful, better for long sequences.

  • GRU: Fewer parameters, faster, often comparable performance to LSTM.

Applications in Natural Language Processing (NLP)

• Role in ChatGPT/Text Generation: Modern models (Transformers) have largely replaced RNNs/LSTMs for generation due to parallelization. However, RNNs were foundational for early sequence models (e.g., in encoder-decoder for machine translation).

• N-gram Models & BLEU Score:

  • N-gram: Probabilistic model predicting next word based on previous $n-1$ words. Simple but suffers from sparsity.

  • BLEU (Bilingual Evaluation Understudy): Metric for machine translation.

    • N-gram Precision: Fraction of candidate n-grams that appear in reference(s). Modified to avoid overcounting (clip counts).

    • Brevity Penalty (BP): Penalizes short candidate translations.

$$BP = \begin{cases} 1 & \text{if } c > r \\ \exp(1 - r/c) & \text{if } c \leq r \end{cases}$$

where $c$ = candidate length, $r$ = reference length.

    *   **BLEU Score:** 

$$BLEU = BP \cdot \exp\left(\sum_{n=1}^{N} w_n \log p_n\right)$$

where $$\displaystyle p_n $$ is n-gram precision, $$\displaystyle w_n $$ usually uniform.

• General NLP Pipeline: Text preprocessing (tokenization, lowercasing, stop word removal), feature extraction (Bag-of-Words, TF-IDF, embeddings), model training (RNN/LSTM/Transformer), evaluation (accuracy, BLEU, perplexity).

VI. UNSUPERVISED LEARNING & DIMENSIONALITY REDUCTION

Clustering

• K-Means Clustering:

  • Algorithm:

    1. Initialize $k$ centroids (randomly or k-means++).

    2. Repeat until convergence:

       • Assignment: Assign each point to nearest centroid (Euclidean distance).

       • Update: Recompute centroids as mean of assigned points.

  • Objective: Minimize within-cluster sum of squares (WCSS):

$$J = \sum_{i=1}^{k} \sum_{\mathbf{x} \in C_i} \|\mathbf{x} - \boldsymbol{\mu}_i\|^2$$

*   **Centroid Initialization:** Critical for avoiding local minima. **k-means++** chooses initial centroids far apart.

• Expectation-Maximization (EM) Algorithm:

  • Use Case: Parameter estimation for models with latent variables (e.g., Gaussian Mixture Models).

  • E-step: Compute expected values of latent variables given current parameters (soft assignment).

  • M-step: Maximize expected complete-data log-likelihood to update parameters.

  • Handles Missing Data: Treats missing values as latent variables; iteratively fills them (E-step) and re-estimates model (M-step).

• Hierarchical Clustering:

  • Agglomerative (Bottom-up): Start with each point as cluster, merge closest pairs. DIANA is actually divisive (top-down). Common linkage: single, complete, average, Ward.

  • Divisive (Top-down): Start with one cluster, split recursively. DIANA (DIvisive ANAlysis) is an example.

• Adaptive Hierarchical Clustering: Dynamically decides number of clusters based on data density/structure (e.g., using a threshold on distance or cluster size).

• Requirements & Goals of Clustering:

  • Requirements: Scalability, ability to handle different attribute types, discovery of arbitrary-shaped clusters, minimal domain knowledge, ability to handle noise/outliers.

  • Goals: High intra-cluster similarity, low inter-cluster similarity.

Dimensionality Reduction

• Principal Component Analysis (PCA):

  • Goal: Find orthogonal axes (principal components) that capture maximum variance.

  • Procedure:

    1. Standardize data (mean=0, variance=1).

    2. Compute covariance matrix $$\displaystyle \mathbf{C} = \frac{1}{n-1} \mathbf{X}^T\mathbf{X} $$.

    3. Compute eigenvectors and eigenvalues of $\mathbf{C}$.

    4. Sort eigenvectors by decreasing eigenvalues.

    5. Choose top $k$ eigenvectors as principal components.

    6. Project data: $$\displaystyle \mathbf{Z} = \mathbf{X} \mathbf{W}_k $$ (where $$\displaystyle \mathbf{W}_k $$ is matrix of top $k$ eigenvectors).

  • Variance Preservation: Eigenvalue $$\displaystyle \lambda_i $$ = variance explained by PC $i$. Total variance = sum of all $$\displaystyle \lambda_i $$.

• Feature Extraction vs. Feature Selection:

  • Feature Extraction: Transform original features into new, fewer features (e.g., PCA, Autoencoders). New features may not be interpretable.

  • Feature Selection: Select a subset of original features (e.g., filter methods, wrapper methods like backward elimination). Retains interpretability.

• Backward Elimination Technique (Wrapper Method):

  1. Start with all features.

  2. Train model, evaluate performance (e.g., using cross-validation).

  3. Remove the feature whose removal improves performance the most (or degrades least).

  4. Repeat steps 2-3 until performance starts to degrade significantly.

• Benefits of Dimensionality Reduction:

  • Curse of Dimensionality: Data becomes sparse, distance metrics lose meaning.

  • Visualization: Reduce to 2D/3D for plotting.

  • Efficiency: Less storage, faster training, reduced overfitting risk.

  • Noise Reduction: Remove irrelevant features.

Autoencoders

• Architecture:

  • Encoder: Compresses input $\mathbf{x}$ into a low-dimensional latent representation $\mathbf{z}$ (bottleneck).

  • Decoder: Reconstructs $\hat{\mathbf{x}}$ from $\mathbf{z}$.

  • Loss: Reconstruction loss (e.g., MSE for continuous, binary cross-entropy for binary).

• Use in Unsupervised Learning:

  • Representation Learning: Latent space $\mathbf{z}$ captures essential features of data.

  • Denoising: Train to reconstruct clean input from noisy version (Denoising Autoencoder).

  • Anomaly Detection: High reconstruction error for anomalies.

  • Pre-training: Initialize weights for deep networks.

VII. REINFORCEMENT LEARNING (RL)

Fundamental Framework: Markov Decision Process (MDP)

• Components:

  • State (s): Situation of the agent.

  • Action (a): Choice available in state $s$.

  • Reward (r): Immediate scalar feedback from environment.

  • Transition Probability $P(s'|s,a)$: Probability of next state $s'$ given state $s$ and action $a$.

  • Policy ($\pi$): Strategy mapping states to actions (deterministic or stochastic).

  • Discount Factor $\gamma \in [0,1]$: Weights immediate vs. future rewards.

• Goal: Find policy $\pi$ that maximizes expected cumulative discounted reward (Return):

$$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ...$$

• Difference from Supervised/Unsupervised:

  • Supervised: Labeled data, correct answer provided.

  • Unsupervised: Find structure in unlabeled data.

  • RL: Agent learns by trial-and-error interaction with environment, delayed reward signal, trade-off between exploration (try new actions) and exploitation (use known good actions).

Value-Based Methods

• Value Function: Measures "goodness" of a state/state-action pair under policy $\pi$.

  • State-Value: $$\displaystyle V_\pi(s) = \mathbb{E}_\pi[G_t | S_t = s] $$

  • Action-Value (Q-value): $$\displaystyle Q_\pi(s,a) = \mathbb{E}_\pi[G_t | S_t = s, A_t = a] $$

• Bellman Equation (for optimal Q):*

$$Q^*(s,a) = \mathbb{E}[r + \gamma \max_{a'} Q^*(s', a') | s,a]$$

• Q-Learning (Off-policy):

  • Learns $$\displaystyle Q^*(s,a) $$ independent of policy being followed.

  • Update Rule:

$$Q(s,a) \leftarrow Q(s,a) + \alpha \left[ r + \gamma \max_{a'} Q(s',a') - Q(s,a) \right]$$

*   Uses greedy action ($$\displaystyle \max_{a'} Q $$) for update, but can follow $\epsilon$-greedy for exploration.

• SARSA (On-policy):

  • Learns $$\displaystyle Q_\pi $$ for the policy currently being followed.

  • Update Rule:

$$Q(s,a) \leftarrow Q(s,a) + \alpha \left[ r + \gamma Q(s',a') - Q(s,a) \right]$$

where $a'$ is action actually taken in $s'$ (from current policy).

*   **Difference from Q-learning:** Q-learning uses $$\displaystyle \max_{a'} Q(s',a') $$ (optimistic, off-policy); SARSA uses $Q(s',a')$ (on-policy, follows actual action).

• Value Iteration vs. Policy Iteration:

  • Value Iteration: Repeatedly apply Bellman optimality update to $V(s)$ until convergence, then derive greedy policy. Simpler, but each step requires full backup.

  • Policy Iteration: Alternate between Policy Evaluation (compute $$\displaystyle V_\pi $$ for current $\pi$) and Policy Improvement (make $\pi$ greedy w.r.t. $$\displaystyle V_\pi $$). Often converges faster but policy evaluation step can be costly.

Policy-Based & Actor-Critic Methods

• Actor-Critic Model:

  • Architecture:

    • Actor: Policy network $$\displaystyle \pi_\theta(a|s) $$ that selects actions.

    • Critic: Value network (e.g., $$\displaystyle V_w(s) $$ or $$\displaystyle Q_w(s,a) $$) that evaluates the actor's actions.

  • Interaction:

    1. Actor proposes action $$\displaystyle a_t $$ in state $$\displaystyle s_t $$.

    2. Environment returns reward $$\displaystyle r_t $$ and next state $$\displaystyle s_{t+1} $$.

    3. Critic evaluates state (or state-action pair) and computes TD error (advantage): $$\displaystyle \delta_t = r_t + \gamma V_w(s_{t+1}) - V_w(s_t) $$.

    4. Update Critic: Minimize $$\displaystyle \delta_t^2 $$ (or use MSE).

    5. Update Actor: Use $$\displaystyle \delta_t $$ as signal for policy gradient: $$\displaystyle \theta \leftarrow \theta + \alpha \delta_t \nabla_\theta \log \pi_\theta(a_t|s_t) $$.

  • Benefit: Lower variance than pure policy gradient (critic provides baseline), more stable than pure value-based (actor handles continuous actions).

• Advanced Actor-Critic Models:

  • A2C (Advantage Actor-Critic): Uses advantage function $$\displaystyle A(s,a) = Q(s,a) - V(s) $$ instead of TD error.

  • A3C (Asynchronous Advantage Actor-Critic): Multiple agents in parallel environments, asynchronously update global network. Improves exploration and training speed.

  • PPO (Proximal Policy Optimization): Constrains policy update to avoid large destructive steps. Uses clipped objective or adaptive KL penalty. State-of-the-art for many tasks.

Practical RL

• Popular Frameworks:

  • OpenAI Gym: Standard API for RL environments (Atari, robotics, classic control). Provides env.step(), env.reset().

  • TensorFlow Agents (TF-Agents): Library of RL algorithms (DQN, PPO, SAC) built on TensorFlow, modular components (agents, networks, policies, replay buffers).

• Example Applications:

  • Game Playing: DQN for Atari, AlphaGo (MCTS + RL), AlphaStar (StarCraft II).

  • Robotics: Sim-to-real transfer for control tasks (walking, grasping).

  • Recommendation Systems: Sequential recommendation as MDP.

VIII. PROBABILISTIC & BAYESIAN METHODS

Bayes' Theorem

• Formulation:

$$P(A|B) = \frac{P(B|A) P(A)}{P(B)}$$

*   $P(A|B)$: Posterior (updated belief after evidence B).

*   $P(B|A)$: Likelihood (probability of evidence given A).

*   $P(A)$: Prior (initial belief).

*   $P(B)$: Evidence (normalizing constant).

• Application in Classification (Naive Bayes):

  • Assumes features are conditionally independent given class $C$.

  • Predict class $c$ that maximizes:

$$P(C=c|\mathbf{x}) \propto P(C=c) \prod_{i} P(x_i|C=c)$$

*   **Fundamental Role:** Provides a probabilistic framework for updating beliefs with evidence. Forms basis for many models (Naive Bayes, Bayesian Networks, Bayesian Linear Regression).

Bayesian Learning & Networks

• Bayesian Learning Perspective:

  • Prior $P(\theta)$: Belief about parameters $\theta$ before seeing data.

  • Likelihood $P(D|\theta)$: Probability of data $D$ given parameters.

  • Posterior $P(\theta|D)$: Updated belief after seeing data.

$$P(\theta|D) = \frac{P(D|\theta) P(\theta)}{P(D)}$$

*   **Prediction:** Marginalize over posterior: $$\displaystyle P(\text{new}|\mathbf{D}) = \int P(\text{new}|\theta) P(\theta|\mathbf{D}) d\theta $$.

• Bayesian Networks (Belief Networks):

  • Structure: Directed Acyclic Graph (DAG). Nodes = random variables, edges = direct conditional dependencies.

  • Conditional Probability Tables (CPTs): For each node, specify $P(\text{node} | \text{parents})$.

  • Example: "Car Value" network might have nodes: Mileage (M), Engine (E), AirConditioner (AC), Car Value (V). Edges: M→V, E→V, AC→V.

• Inference in Bayesian Networks: Compute posterior probability of query variables given evidence. Example: $$\displaystyle P(V|\text{Mileage=Lo, Engine=Bad, AC=Broken}) $$. Can be done by enumeration, variable elimination, or sampling.

IX. ADVANCED TOPICS & EMERGING TRENDS

Specialized Learning Paradigms

• One-Shot Learning:

  • Definition: Learning from very few examples (often one or a few per class), unlike traditional supervised learning requiring hundreds/thousands.

  • Difference: Traditional: learn from many examples; One-shot: leverage prior knowledge (meta-learning, embeddings, data augmentation) to generalize from few.

  • Beneficial Applications: Rare species identification, new object recognition in robotics, medical diagnosis for rare diseases.

• Self-Supervised Learning:

  • Paradigm: Create pretext tasks from unlabeled data itself, where the target is part of the input. Model learns useful representations without human labels.

  • Examples: Predict missing part of image (inpainting), predict rotation angle, contrastive learning (SimCLR, MoCo – pull similar samples together, push dissimilar apart).

• Generative AI:

  • Overview: Models that generate new data samples resembling training data.

  • GANs (Generative Adversarial Networks): Generator $G$ creates fake data, Discriminator $D$ tries to distinguish real vs. fake. Min-max game: $$\displaystyle \min_G \max_D V(D,G) = \mathbb{E}[\log D(x)] + \mathbb{E}[\log(1-D(G(z)))] $$.

  • VAEs (Variational Autoencoders): Probabilistic autoencoder. Learns latent distribution $q(z|x)$ (encoder) and generates by sampling $z \sim p(z)$, then $x \sim p(x|z)$ (decoder). Optimizes ELBO (Evidence Lower Bound).

  • Large Language Models (LLMs): Transformer-based models (GPT, BERT) trained on massive text corpora. Generate coherent text, perform few-shot learning.

Transfer Learning

• Types:

  • Feature Extraction: Use pre-trained model as fixed feature extractor. Only train new classifier on top.

  • Fine-Tuning: Unfreeze some/all layers of pre-trained model and train with lower learning rate. Adapts features to new task.

• Benefits: Requires less task-specific data, faster training, better performance when target data is scarce.

• Common Practices: Start with model pre-trained on large dataset (ImageNet for vision, BERT for NLP). For small datasets, only train top layers. For larger datasets, fine-tune more layers.

Historical & Benchmark Context: ImageNet Competition

• Significance: Annual competition (ILSVRC) starting 2010, benchmark for image classification/object detection.

• Impact on CNN Development:

  • AlexNet (2012): First deep CNN (8 layers) to win, used ReLU, dropout, GPU training. Catalyzed deep learning revolution.

  • VGG (2014): Showed depth matters (19 layers), simple 3x3 convs.

  • ResNet (2015): Introduced skip connections (residual blocks) to train very deep networks (100+ layers) without vanishing gradients. Won with 152 layers.

• Result: Established deep CNNs as dominant approach for computer vision.

Application-Specific ML

• Speech Processing:

  • Speech-to-Text (ASR): Pipeline: Audio → MFCC/Filterbank features → Acoustic model (DNN, LSTM, Transformer) → Language model (n-gram, RNN, Transformer) → Text. Modern: End-to-end models (DeepSpeech, Wav2Vec 2.0).

  • Speaker Identification: Extract speaker embeddings (x-vector, d-vector) from speech using DNN, then classify with SVM or softmax.

• Computer Vision: Image classification, object detection, segmentation, facial recognition, medical image analysis.

• Bioinformatics: SVM for gene expression classification, protein structure prediction (AlphaFold), sequence alignment, drug discovery.

X. ALGORITHMIC & EXPERIMENTAL DESIGN

Resampling Methods

• Bootstrap: Sample n observations with replacement from original dataset (size n) to create a "bootstrap sample". Used to estimate variability (confidence intervals) of a statistic.

• Cross-Validation: As described in Section I. Primary use: model assessment (estimate generalization error) and model selection (choose hyperparameters).

Designing ML Experiments

1. Problem Formulation: Define objective, success metric.

2. Data Collection & Preprocessing: Gather data, clean, split (train/val/test), normalize, encode.

3. Algorithm Selection: Choose candidate models based on problem type, data size, interpretability needs.

4. Training & Hyperparameter Tuning: Train models on training set, tune hyperparameters on validation set using strategies like grid/random search.

5. Evaluation: Assess final model on held-out test set using chosen metrics.

6. Analysis & Interpretation: Analyze errors, feature importance, model behavior.

7. Deployment & Monitoring: Deploy best model, monitor performance in production, retrain periodically.

Hyperparameter Tuning

• Impact: Directly controls model capacity, regularization, learning dynamics. Poor choices lead to under/overfitting.

• Common Strategies:

  • Grid Search: Exhaustive search over predefined grid of hyperparameters. Computationally expensive.

  • Random Search: Sample hyperparameters randomly from distributions. More efficient, often finds good values faster.

  • Bayesian Optimization: Builds probabilistic model (surrogate) of objective function, uses it to select next promising hyperparameters (e.g., using Gaussian Processes or Tree-structured Parzen Estimators). More sample-efficient.

Specific Algorithmic Notes (from Short-Note Prompts)

• Partial Least Squares (PLS): Supervised dimensionality reduction. Finds components (latent variables) that maximize covariance between predictors $\mathbf{X}$ and response $\mathbf{Y}$. Similar to PCA but considers $\mathbf{Y}$.

• Attention Model: Mechanism allowing model to focus on different parts of input sequence when producing output. Computes weighted sum of values, where weights (attention scores) are learned. Core component of Transformers (e.g., "Attention Is All You Need").

• Data Augmentation (in CV): Artificially increase training data by applying label-preserving transformations: rotations, flips, crops, color jitter, cutout. Purpose: Reduce overfitting, improve model robustness and generalization.

• BIRCH Algorithm (Clustering): Balanced Iterative Reducing and Clustering using Hierarchies. Designed for large datasets. Uses Clustering Feature (CF) tree to summarize data incrementally. Phase 1: build CF tree (scan data). Phase 2: apply clustering (e.g., k-means) on CF leaf entries.

• Gaussian Mixture Models (GMM): Probabilistic model assuming data generated from mixture of several Gaussian distributions. Parameters: means $$\displaystyle \mu_k $$, covariances $$\displaystyle \Sigma_k $$, mixing coefficients $$\displaystyle \pi_k $$. Density Estimation: $$\displaystyle p(\mathbf{x}) = \sum_{k=1}^{K} \pi_k \mathcal{N}(\mathbf{x}|\mu_k, \Sigma_k) $$. Fit via EM algorithm.

[!TIP] Final Exam Strategy: For 7-mark questions, structure answer: 1-2 sentence definition, 3-4 bullet points of key concepts/mechanism, 1-2 lines on applications/importance. Use diagrams where possible (describe them if drawing not allowed). Always highlight key formulas and compare/contrast when asked (e.g., L1 vs L2, Q-learning vs SARSA).