UNIT 2: MACHINE LEARNING - COMPREHENSIVE NOTES

I. FOUNDATIONS & CORE CONCEPTS

Definition & Importance

• Definition: Machine Learning (ML) is a subset of AI that enables systems to learn and improve from experience (data) without being explicitly programmed.

• Perspectives:

  • AI: Building intelligent agents.

  • Statistics: Drawing inferences from data.

  • Engineering: Solving practical problems with data-driven solutions.

• Importance: Solves complex, non-linear problems (image/speech recognition, NLP), handles massive data, adapts to new situations, automates decision-making.

• [!TIP] Exam Focus: Be ready to explain ML from all three perspectives with examples.

Types of Machine Learning

Key Issues & Design

• Overfitting vs. Underfitting (Bias-Variance Tradeoff):

  • Underfitting (High Bias): Model too simple, fails on training data. Solution: Increase model complexity, add features.

  • Overfitting (High Variance): Model too complex, memorizes noise, fails on new data. Solution: Regularization, more data, reduce complexity.

  • Tradeoff: Decreasing bias increases variance and vice-versa. Goal is to find optimal complexity.

  [!TIP] Common Pitfall: High training accuracy + low validation accuracy = Overfitting. Low training accuracy = Underfitting.

• Curse of Dimensionality: As feature dimensions increase, data becomes sparse, distance metrics lose meaning, and model complexity explodes. Solution: Dimensionality reduction (PCA, feature selection).

• Data Issues: Noise, missing values, outliers require robust preprocessing.

• Model Selection: Choosing the right algorithm and hyperparameters using validation sets and cross-validation.

Data Preprocessing & Feature Engineering

• Why Needed: Raw data is often incompatible with ML algorithms (different scales, missing values, non-numeric).

• Key Steps:

  1. Cleaning: Handle missing values (impute/remove), smooth noise, detect outliers.

  2. Transformation:

     • Normalization (Min-Max): Scales to [0,1]. $$\displaystyle X_{\text{norm}} = \frac{X - X_{\min}}{X_{\max} - X_{\min}} $$

     • Standardization (Z-score): Scales to mean=0, std=1. $$\displaystyle X_{\text{std}} = \frac{X - \mu}{\sigma} $$

  3. Encoding Categorical Data:

     • Label Encoding: Assigns integer (e.g., "Red"=0, "Green"=1). Risk: Implies ordinal relationship.

     • One-Hot Encoding: Creates binary column per category. Impact: Increases dimensionality (curse of dimensionality).

  4. Feature Engineering: Creating new features (e.g., ratios, polynomials) or selecting most relevant ones.

II. PROBABILITY & STATISTICAL FOUNDATIONS

Role of Probability

• Provides mathematical framework for uncertainty.

• Forms basis for probabilistic models (Naïve Bayes, HMMs, Bayesian networks).

• Enables principled decision-making under uncertainty.

Bayes' Theorem & Naïve Bayes

• Bayes' Theorem: $$\displaystyle P(A|B) = \frac{P(B|A) \cdot P(A)}{P(B)} $$

  • $P(A|B)$: Posterior (updated belief).

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

  • $P(B|A)$: Likelihood.

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

• Naïve Bayes Classifier:

  • Assumes feature independence given the class: $$\displaystyle P(x_1, x_2, ..., x_n | y) = \prod_{i=1}^{n} P(x_i | y) $$.

  • Predicts class: $$\displaystyle \hat{y} = \arg\max_y P(y) \prod_{i=1}^{n} P(x_i | y) $$.

  • Advantages: Simple, fast, works well with high-dimensional data (text).

  • Limitation: Independence assumption rarely holds true.

  [!TIP] Exam Focus: Derive the Naïve Bayes classification rule from Bayes' Theorem. Know Laplace smoothing for zero probabilities.

Evaluation Metrics

Statistical Concepts

• Entropy (Decision Trees): $$\displaystyle H(S) = -\sum_{i=1}^{c} p_i \log_2 p_i $$. Measures impurity/uncertainty of set S.

• Information Gain: $$\displaystyle IG(S, A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} H(S_v) $$. Used for splitting in ID3/C4.5.

• Maximum Likelihood Estimation (MLE): Finds parameters $\theta$ that maximize likelihood of observed data: $$\displaystyle \hat{\theta}_{\text{MLE}} = \arg\max_{\theta} P(\text{Data}|\theta) $$.

• Convex Optimization: Many ML loss functions are convex. Guarantees any local minimum is global. Gradient descent finds optimum if learning rate is appropriate.

III. NEURAL NETWORKS & DEEP LEARNING FUNDAMENTALS

Artificial Neural Network (ANN) Basics

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

• Perceptron: Single neuron. $$\displaystyle y = f(\sum_{i=1}^{n} w_i x_i + b) $$. f = activation function.

• Multi-Layer Perceptron (MLP): Input layer → Hidden layer(s) → Output layer. Universal approximator with non-linear activations.

Activation Functions

[!TIP] Rule of Thumb: Use ReLU for hidden layers. Use Softmax for multi-class output, Sigmoid for binary output.

Training Neural Networks

• Loss Functions:

  • MSE: For regression.

  • Cross-Entropy: For classification. $$\displaystyle L = -\sum y_i \log(\hat{y}_i) $$.

  • Hinge Loss: For SVMs/max-margin.

  • Purpose: Quantifies error; guides backpropagation to minimize it.

• Gradient Descent & Optimizers:

  • Batch GD: Uses entire dataset per update. Stable but slow.

  • Stochastic GD (SGD): 1 sample per update. Noisy, fast, can escape minima.

  • Mini-batch GD: Compromise (common). Uses b samples (e.g., 32, 64).

  • Advanced Optimizers:

    • Momentum: Adds velocity: $$\displaystyle v_t = \gamma v_{t-1} + \eta \nabla J(\theta) $$. Accelerates convergence.

    • AdaGrad: Adapts learning rate per parameter (accumulates squared grads). Can shrink lr too much.

    • RMSProp: Fixes AdaGrad with decaying sum of squared grads.

    • Adam: Most popular. Combines Momentum + RMSProp. Adaptive + bias-corrected.

• Backpropagation Algorithm:

  1. Forward Pass: Compute output and loss for a mini-batch.

  2. Backward Pass: Compute gradient of loss w.r.t. each weight using chain rule.

  3. Weight Update: $$\displaystyle w_{ij} \leftarrow w_{ij} - \eta \frac{\partial L}{\partial w_{ij}} $$.

  • Enables training of deep networks by efficiently computing gradients.

  [!TIP] Key Concept: Backpropagation is gradient computation, not the update rule itself. The update is done by an optimizer (SGD, Adam).

Regularization Techniques

Advanced Training Concepts

• Batch Normalization:

  • Normalizes layer inputs (per mini-batch) to zero mean, unit variance.

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

  • Mechanism: $$\displaystyle \hat{x} = \frac{x - \mu_B}{\sqrt{\sigma_B^2 + \epsilon}} $$; then scale/shift: $$\displaystyle y = \gamma \hat{x} + \beta $$.

• Vanishing/Exploding Gradients:

  • Cause: Deep networks, activation functions with small derivatives (sigmoid/tanh) → gradients shrink (vanish) or grow (explode) through layers.

  • Mitigation: Use ReLU, BatchNorm, ResNet skip connections, gradient clipping, proper weight initialization (He/Xavier).

IV. CONVOLUTIONAL NEURAL NETWORKS (CNNs)

CNN Architecture & Core Operations

[Input Image]

     ↓

[Convolutional Layer] → (Feature Maps: detects local patterns like edges)

     ↓

[Activation Function (ReLU)]

     ↓

[Pooling/Sub-sampling Layer] → (Downsampling: Max/Avg Pooling, provides translation invariance)

     ↓

[Repeat (Conv → ReLU → Pool) multiple times] → (Hierarchical features: edges → textures → object parts)

     ↓

[Flatten] → (Converts 3D feature maps to 1D vector)

     ↓

[Fully Connected (FC) Layers] → (High-level reasoning, classification)

     ↓

[Output (Softmax)]

• Convolutional Layer:

  • Filter/Kernel: Small matrix (e.g., 3x3, 5x5) that slides over input.

  • Feature Map: Output of a filter. Each filter learns to detect a specific feature.

  • Parameter Sharing: Same filter used across spatial locations → translation invariance, fewer parameters.

• Pooling Layer (Sub-sampling):

  • Max Pooling: Takes maximum value in window. Most common. Preserves dominant feature.

  • Average Pooling: Takes average. Smoothes features.

  • Purpose: Reduces spatial size (parameters, computation), provides translation invariance, increases receptive field.

• Fully Connected (FC) Layer: Standard neural network layer at the end for classification/regression.

Key Architectural Design Choices

• Padding:

  • 'Valid' (No padding): Output size shrinks. $$\displaystyle O = \frac{W - F}{S} + 1 $$.

  • 'Same' (Zero padding): Output size same as input (if stride=1). Preserves spatial information at edges.

• Stride (S): Step size of filter movement.

  • Larger stride → smaller output, less overlap, less computation.

  • Stride=1 is most common for detailed feature capture.

• Flattening: Converts final pooled feature maps (e.g., 5x5x256) into a 1D vector (e.g., 6400) to feed into FC layers.

Specialized Convolutions & Modules

• 1x1 Convolution:

  • Purpose: Acts as a channel mixer / feature reduction layer.

  • Benefits: Increases non-linearity without changing spatial dimensions, reduces/increases number of channels (depth), computationally cheap. Used in Network-in-Network, Inception, ResNet.

• Inception Module (Inception Net):

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

  • Benefits: Multi-scale feature capture in one layer. 1x1 convs reduce channels before expensive 3x3/5x3 convs → computational efficiency.

  • Diagram Concept:

    DiagramCANVAS: Inception module showing parallel paths: 1x1 conv, 1x1->3x3 conv, 1x1->5x5 conv, 3x3 max pool, all concatenated.

CNN Design Rationale

• Why downsample (reduce spatial size) and increase filters (depth)?

  • Early layers: Small receptive fields, few filters → capture low-level features (edges, colors). Preserve spatial info.

  • Later layers: Larger receptive fields (via stacking/pooling), many filters → capture high-level, abstract features (object parts, whole objects). Depth increases to represent complex patterns.

  • Analogy: Vision system: retina (high res) → visual cortex (abstract concepts).

Applications & Historical Context

• ImageNet Competition (ILSVRC): Catalyst for deep learning revolution.

  • AlexNet (2012): First deep CNN (8 layers), won by huge margin. Introduced ReLU, Dropout, GPU training.

  • VGGNet (2014): Showed depth matters with small (3x3) filters. Very uniform architecture.

  • ResNet (2015): Introduced skip connections (residual blocks) to train very deep networks (100+ layers) by solving vanishing gradient.

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

[!TIP] Exam Focus: Be prepared to draw a simple CNN block (Conv->ReLU->Pool) and explain each component. Know the impact of stride/padding on output size: $$\displaystyle O = \frac{W - F + 2P}{S} + 1 $$.

V. RECURRENT NEURAL NETWORKS (RNNs) & SEQUENCE MODELS

Vanilla RNN

• Architecture: Has hidden state $$\displaystyle h_t $$ that acts as memory. $$\displaystyle h_t = f(W_{xh}x_t + W_{hh}h_{t-1} + b) $$. Output $$\displaystyle y_t = g(W_{hy}h_t + c) $$.

• Process: Unfolds through time steps. Same weights shared across time.

• Limitations:

  • Short-term memory: Struggles with long-term dependencies.

  • Vanishing/Exploding Gradients: Gradients multiplied repeatedly through time steps → shrink/vanish or grow/explode.

Long Short-Term Memory (LSTM)

• Architecture: Addresses RNN limitations with cell state $$\displaystyle C_t $$ (information highway) and gates.

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

  • Input Gate: Decides what new information to store. $$\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) $$

  • Cell State Update: $$\displaystyle C_t = f_t \odot C_{t-1} + i_t \odot \tilde{C}_t $$

  • Output Gate: Decides what to output based on cell state. $$\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: Cell state allows gradients to flow with minimal interference (additive operations), gates regulate information flow.

• Role in NLP: Language modeling, machine translation (historically), text generation.

Gated Recurrent Unit (GRU)

• Simplified LSTM: Merges forget & input gates into update gate $$\displaystyle z_t $$. Has reset gate $$\displaystyle r_t $$.

  • $$\displaystyle z_t = \sigma(W_z \cdot [h_{t-1}, x_t]) $$, $$\displaystyle r_t = \sigma(W_r \cdot [h_{t-1}, x_t]) $$

  • $$\displaystyle \tilde{h}_t = \tanh(W \cdot [r_t \odot h_{t-1}, x_t]) $$

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

• Comparison: Fewer parameters than LSTM, often similar performance. Faster to train.

Comparison Table

[!TIP] Historical Context: LSTMs/GRUs dominated sequence modeling before Transformers (used in ChatGPT). They are still used for smaller datasets or real-time applications due to sequential computation.

VI. REINFORCEMENT LEARNING (RL)

Fundamentals & Framework

• Key Components:

  • Agent: Learner/decision maker.

  • Environment: World agent interacts with.

  • State (s): Current situation.

  • Action (a): Agent's move.

  • Reward (r): Immediate feedback from environment.

  • Policy (π): Agent's strategy (maps state to action).

• Goal: Maximize cumulative discounted reward: $$\displaystyle G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} $$, where $\gamma \in [0,1]$ is discount factor.

• Markov Decision Process (MDP): Formal framework. Defined by $(S, A, P, R, \gamma)$.

  • $P(s'|s,a)$: State transition probability.

  • $R(s,a,s')$: Expected immediate reward.

  • Markov Property: Future depends only on current state/action, not history.

• Difference from Supervised/Unsupervised:

  • Supervised: Fixed labeled dataset.

  • Unsupervised: Find structure in unlabeled data.

  • RL: No fixed dataset. Agent explores environment, learns from delayed, sparse rewards. Trade-off between exploration (try new actions) and exploitation (use known good actions).

RL Problem Solving Approaches

• Value-Based Methods: Learn value function (expected cumulative reward). Derive policy from it.

  • Q-Learning (Off-policy):

    • Learns Q-function: $Q(s,a)$ = expected future reward of taking a in s.

    • Update Rule: $$\displaystyle Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma \max_{a'} Q(s',a') - Q(s,a)] $$

    • Exploration: ε-greedy (with probability ε, choose random action).

    • Key: Uses $$\displaystyle \max_{a'} Q(s',a') $$ (greedy) regardless of current policy → off-policy.

  • SARSA (On-policy):

    • Update: $$\displaystyle Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma Q(s',a') - Q(s,a)] $$

    • Key: Uses actual next action $a'$ taken by current policy → on-policy.

    • More conservative, learns about policy actually followed.

• Policy-Based Methods: Directly optimize policy $\pi(a|s)$ (e.g., REINFORCE).

• Actor-Critic Models (Hybrid):

  • Actor: Policy network. Outputs actions.

  • Critic: Value network (e.g., Q or V). Evaluates actions.

  • Interaction: Actor proposes action, Critic evaluates it, Actor is updated based on Critic's feedback (TD error: $$\displaystyle \delta = r + \gamma V(s') - V(s) $$).

  • Examples: A2C (Advantage Actor-Critic), A3C (Asynchronous), DDPG (for continuous actions).

  • Rise: More stable and sample-efficient than pure policy or value methods.

Algorithmic Concepts

• Value Iteration: Iteratively apply Bellman optimality equation: $$\displaystyle V_{k+1}(s) = \max_a \sum_{s'} P(s'|s,a)[R(s,a,s') + \gamma V_k(s')] $$.

• Policy Iteration: Alternate between Policy Evaluation (compute V for fixed π) and Policy Improvement (make π greedy w.r.t V).

• Exploration Strategies: ε-greedy, Softmax (Boltzmann), Upper Confidence Bound (UCB).

RL Frameworks & Applications

• Frameworks: OpenAI Gym (standard environments), Stable Baselines3 (implementations), TensorFlow Agents.

• Applications:

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

  • Robotics: Control, locomotion.

  • Autonomous Systems: Self-driving cars (high-level decisions).

  • Recommendation Systems: Sequential recommendation.

[!TIP] Exam Focus: Contrast Q-Learning vs SARSA clearly (off-policy vs on-policy, max vs actual next action). Draw Actor-Critic diagram.

VII. SUPPORT VECTOR MACHINES (SVMs)

Core Objective & Hyperplane

• Goal: Find the optimal maximum margin hyperplane that separates classes.

• Hyperplane: $$\displaystyle w^T x + b = 0 $$.

• Margin: Distance between hyperplane and nearest data points (support vectors). Maximize margin for better generalization.

• Support Vectors: Subset of training points that lie on the margin boundaries (or inside for soft-margin). They define the decision boundary. Only they matter for the final model.

Linear SVM for Linearly Separable Data (Hard Margin)

• Mathematical Formulation (Primal):

  • Minimize: $$\displaystyle \frac{1}{2} \|w\|^2 $$

  • Subject to: $$\displaystyle y_i (w^T x_i + b) \geq 1 $$ for all $i$.

  • $$\displaystyle \|w\|^2 $$ minimization maximizes margin ($$\displaystyle \text{margin} = \frac{2}{\|w\|} $$).

• Solution via Lagrange Dual: Leads to quadratic programming problem. Solution: $$\displaystyle w = \sum_{i=1}^{n} \alpha_i y_i x_i $$, where $$\displaystyle \alpha_i > 0 $$ only for support vectors.

Handling Non-Linearity & High-Dimensional Spaces

• Kernel Trick:

  • Map input data to a higher-dimensional feature space where it becomes linearly separable.

  • Kernel Function: Computes dot product in high-dim space without explicit mapping: $$\displaystyle K(x_i, x_j) = \phi(x_i)^T \phi(x_j) $$.

  • Common Kernels:

    • Linear: $$\displaystyle K(x_i, x_j) = x_i^T x_j $$

    • Polynomial: $$\displaystyle K(x_i, x_j) = (x_i^T x_j + c)^d $$

    • Radial Basis Function (RBF/Gaussian): $$\displaystyle K(x_i, x_j) = \exp(-\gamma \|x_i - x_j\|^2) $$. Most powerful, maps to infinite dimensions.

• Performance in High Dimensions: SVM excels because:

  1. Margin maximization inherently combats overfitting.

  2. Only support vectors are stored → memory efficient.

  3. Kernel trick handles non-linearity without explicit high-dim computation.

Soft-Margin SVM

• Purpose: Handle outliers and non-separable data.

• Introduces Slack Variables $$\displaystyle \xi_i \geq 0 $$: Allows some points to violate margin.

• Primal: Minimize $$\displaystyle \frac{1}{2}\|w\|^2 + C \sum_{i=1}^{n} \xi_i $$

  • Subject to: $$\displaystyle y_i(w^T x_i + b) \geq 1 - \xi_i $$, $$\displaystyle \xi_i \geq 0 $$.

• C Parameter: Regularization parameter.

  • Large C: Penalize violations heavily → narrow margin, risk overfitting.

  • Small C: Allow more violations → wider margin, risk underfitting.

Advantages of SVM

1. Effective in high-dimensional spaces (even when dimensions > samples).

2. Memory efficient (uses support vectors only).

3. Versatile via kernel trick.

4. Clear geometric interpretation (max margin).

[!TIP] Key Distinction: Hard Margin = perfectly separable data, no errors. Soft Margin = real-world data, allows errors controlled by C.

VIII. ADVANCED TOPICS & APPLICATIONS

Autoencoders

• Architecture: Encoder (compresses input to latent code/bottleneck) → Bottleneck (low-dim representation) → Decoder (reconstructs input from code).

• Purpose: Unsupervised learning of efficient data representations.

• Applications:

  • Dimensionality Reduction: Learn better non-linear manifold than PCA.

  • Anomaly Detection: Train on normal data; high reconstruction error on anomalies.

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

  • Feature Extraction: Pre-training for deep networks.

Generative AI (Overview)

• Generative Adversarial Networks (GANs):

  • Two networks: Generator (creates fake data) vs. Discriminator (distinguishes real vs fake).

  • Adversarial training: Generator tries to fool Discriminator, Discriminator tries to get better. Minimax game.

  • Applications: Image synthesis (StyleGAN), super-resolution, data augmentation.

• Variational Autoencoders (VAEs):

  • Probabilistic autoencoder. Encoder outputs parameters (mean, variance) of latent distribution.

  • Learns latent space that is continuous and structured.

  • Applications: Image generation, interpolation, semi-supervised learning.

• Large Language Models (LLMs): Transformer-based models (GPT, BERT) trained on massive text corpora for language tasks.

• Diffusion Models: Generative process that gradually adds noise to data and learns to reverse it. State-of-the-art for image generation (DALL-E 2, Stable Diffusion).

Self-Supervised Learning

• Paradigm: Create pretext tasks from unlabeled data to learn useful representations. No human labels needed.

• Mechanisms:

  • Contrastive Learning: Learn by comparing similar (positive) and dissimilar (negative) pairs (e.g., SimCLR, MoCo).

  • Masked Modeling: Predict missing parts (e.g., mask words in BERT, mask patches in MAE).

• Benefit: Reduces need for expensive labeled data. Pre-trained models can be fine-tuned for downstream tasks.

One-Shot / Few-Shot Learning

• Definition: Learning a new concept from very few examples (1 or few).

• Difference from Traditional SL: Traditional SL requires hundreds/thousands of examples per class. One/Few-shot aims for rapid generalization.

• Motivation: Real-world scenarios where data is scarce (rare species, new medical conditions).

• Techniques: Metric learning (Siamese networks), memory-augmented networks, meta-learning (learning to learn).

• Applications: Face recognition (new person), specialized medical diagnosis, rare event detection.

Transfer Learning

• Concept: Leverage knowledge (features, weights) from a pre-trained model (on large dataset like ImageNet) for a new, related task with limited data.

• Types:

  1. Feature Extraction: Freeze pre-trained base network, replace and train only new classifier head.

  2. Fine-Tuning: Unfreeze some/all layers of base network and train with lower learning rate on new data. Can be partial (unfreeze top layers) or full.

• Benefits: Faster convergence, better performance with small datasets, reduces computational cost.

Domain-Specific Applications

• Natural Language Processing (NLP):

  • Steps: Tokenization → Embedding (Word2Vec, GloVe, BERT) → Modeling (RNN/LSTM/Transformer) → Task-specific output.

  • Applications: Machine translation (Seq2Seq), sentiment analysis, text summarization, question answering.

• Computer Vision:

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

• Speech Processing:

  • Automatic Speech Recognition (ASR): Audio → Text. Uses spectrograms + RNNs/Transformers (e.g., DeepSpeech, Wav2Vec 2.0).

  • Speaker Identification: Recognize who is speaking (x-vector systems).

  • Text-to-Speech (TTS): Text → Natural speech (Tacotron, WaveNet).

IX. CLUSTERING & UNSUPERVISED LEARNING

Clustering Fundamentals

• Goal: Group data points so that intra-cluster similarity is high and inter-cluster similarity is low.

• Requirements: Scalability, ability to handle various attributes, discovery of arbitrary-shaped clusters, minimal domain knowledge, robustness to noise/outliers.

K-Means Clustering

• Algorithm:

  1. Initialize: Choose K random centroids.

  2. Assign: Assign each point to nearest centroid (using Euclidean distance).

  3. Update: Recalculate centroids as mean of assigned points.

  4. Repeat 2-3 until convergence (centroids stable or max iterations).

• Distance Metric: Typically Euclidean: $$\displaystyle d(x,y) = \sqrt{\sum_{i=1}^{n}(x_i - y_i)^2} $$.

• Advantages: Simple, fast, scalable.

• Limitations:

  • Requires pre-specifying K.

  • Sensitive to initial centroid selection (use k-means++).

  • Assumes spherical clusters of similar size.

  • Sensitive to outliers.

  [!TIP] Exam Focus: Be ready to perform a manual K-means iteration (as in past papers).

Hierarchical Clustering

• Agglomerative (Bottom-up): Start with each point as cluster, merge closest pairs until one cluster.

  • Linkage Criteria (distance between clusters):

    • Single: Min distance between points (can cause chaining).

    • Complete: Max distance (produces compact clusters).

    • Average: Avg distance (compromise).

• Divisive (Top-down): Start with one cluster, split recursively (e.g., DIANA).

• Dendrogram: Tree diagram showing cluster merges/splits. Cut at a level to get K clusters.

• Advantage: No need to specify K upfront; dendrogram provides hierarchy.

Expectation-Maximization (EM) for GMM

• Application: Fits Gaussian Mixture Models (soft clustering, probabilistic).

• GMM Assumption: Data generated from mixture of K Gaussians.

• EM Steps:

  1. E-step (Expectation): Compute responsibilities $$\displaystyle \gamma(z_{ik}) = P(z_i=k|x_i, \theta) $$ = probability point i belongs to cluster k given current parameters.

  2. M-step (Maximization): Update parameters (means $$\displaystyle \mu_k $$, covariances $$\displaystyle \Sigma_k $$, weights $$\displaystyle \pi_k $$) using responsibilities as soft counts.

  3. Repeat until log-likelihood converges.

• Handling Missing/Incomplete Data: EM naturally handles latent variables (cluster assignments z are missing). E-step "fills in" missing data probabilistically.

Dimensionality Reduction

• Purpose: Combat curse of dimensionality, visualization, noise reduction, speed up training.

• Principal Component Analysis (PCA):

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

  • Algorithm:

    1. Standardize data.

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

    3. Compute eigenvectors & eigenvalues of C.

    4. Sort eigenvectors by decreasing eigenvalues.

    5. Select top k eigenvectors → projection matrix W.

    6. Transform: $$\displaystyle X_{\text{reduced}} = X W $$.

  • Interpretation: PCs are directions of highest variance. First PC captures most variance.

• Other Techniques:

  • Linear Discriminant Analysis (LDA): Supervised. Maximizes class separability (between-class variance / within-class variance).

  • t-SNE: Non-linear, excellent for visualization (preserves local structure).

• Feature Selection Methods:

  • Filter: Pre-processing step (e.g., correlation, chi-square).

  • Wrapper: Uses model performance as evaluation (e.g., recursive feature elimination).

  • Embedded: Feature selection built into model training (e.g., L1 regularization, tree-based importance).

X. MODEL EVALUATION, VALIDATION & OPTIMIZATION

Experimental Design & Validation

• Train/Validation/Test Split:

  • Train: Fit model parameters.

  • Validation: Tune hyperparameters, select model.

  • Test: Final, unbiased performance estimate. Never use for tuning.

• Cross-Validation (CV):

  • K-Fold CV: Split data into K folds. Iteratively use K-1 folds for training, 1 for validation. Average K validation scores.

  • Purpose: Robust performance estimate, especially with limited data. Reduces variance of estimate compared to single train-val split.

  • Stratified K-Fold: Maintains class distribution in each fold (for classification).

Performance Measurement

• Beyond Accuracy: Use confusion matrix derived metrics (Precision, Recall, F1) for imbalanced data.

• Resampling Methods:

  • Bootstrapping: Sample with replacement to create many datasets. Estimate statistic confidence intervals.

  • Cross-validation: As above.

Hyperparameter Tuning

• Hyperparameters vs. Parameters:

  • Parameters: Learned from data (weights, biases).

  • Hyperparameters: Set before training (learning rate, C in SVM, K in K-means, number of layers/units).

• Tuning Methods:

  • Grid Search: Exhaustive search over specified parameter grid. Computationally expensive.

  • Random Search: Sample random combinations from distributions. Often finds good params faster than grid search.

• Justification: Hyperparameters control model capacity and learning dynamics. Poor choice leads to underfitting/overfitting. Tuning is crucial for optimal performance.

Identifying & Solving Model Problems (CNN Focus)

• Diagnosing:

  • Overfitting: Training accuracy ↑, Validation/Test accuracy ↓/plateaus.

  • Underfitting: Both training and validation accuracy low.

• Solutions for CNNs:

  • Overfitting: Data augmentation, Dropout, L2 regularization, reduce model complexity (fewer layers/filters), Early stopping, more training data.

  • Underfitting: Increase model complexity (more layers/filters), reduce regularization, train longer, better features.

XI. DECISION TREES, ENSEMBLES & OTHER ALGORITHMS

Decision Tree Learning

• Algorithms: ID3 (Entropy), C4.5 (Gain Ratio), CART (Gini Impurity).

• Splitting Criteria:

  • Entropy: $$\displaystyle H(S) = -\sum p_i \log_2 p_i $$. Information Gain: $$\displaystyle IG(S,A) = H(S) - \sum \frac{|S_v|}{|S|} H(S_v) $$.

  • Gini Impurity: $$\displaystyle G(S) = 1 - \sum p_i^2 $$. CART uses this. Faster to compute than entropy.

  • Gain Ratio: Adjusts Information Gain for intrinsic information of split (handles bias towards many-valued attributes).

• Handling Continuous Attributes: Find threshold that maximizes information gain/gini reduction.

• Pruning:

  • Pre-pruning: Stop splitting early (min samples per leaf, max depth).

  • Post-pruning: Grow full tree, then remove branches (e.g., reduced error pruning).

• Issues: Prone to overfitting (solved by pruning), unstable (small data change → different tree), biased towards features with more levels.

Ensemble Methods

• Goal: Combine multiple weak learners to create a strong learner. Reduce variance (bagging) or bias (boosting).

• Bagging (Bootstrap Aggregating):

  • Train multiple models (e.g., decision trees) on bootstrap samples (random subsets with replacement).

  • Aggregate: Majority vote (classification) or average (regression).

  • Example: Random Forest (bagging + feature randomness). Reduces variance, robust to overfitting.

• Boosting:

  • Train models sequentially. Each new model focuses on errors of previous ones.

  • Weighting: Increase weight of misclassified instances.

  • Examples: AdaBoost (adaptive boosting), Gradient Boosting (fits residuals).

  • Reduces bias, can overfit if too many rounds.

• Stacking:

  • Train multiple base models (level-0).

  • Use their predictions as features to train a meta-learner (level-1).

  • Can capture complex relationships between models.

• Bagging vs. Boosting:

  | Aspect | Bagging | Boosting | | :--- | :--- | :--- | | Sampling | Bootstrap (random) | Weighted (focus on errors) | | Weights | Equal for all models | Sequential, weighted | | Goal | Reduce variance | Reduce bias | | Parallel? | Yes (independent) | No (sequential) | | Overfitting | Less prone | Can overfit |

Other Notable Algorithms

• K-Nearest Neighbors (KNN):

  • Lazy learning: No explicit training. Stores all data.

  • Prediction: For a query point, find K nearest neighbors (using distance metric like Euclidean), majority vote (classification) or average (regression).

  • Curse of Dimensionality: Distance metrics become meaningless in high-D → performance degrades.

• Linear Regression vs. Logistic Regression:

  • Linear Regression: Predicts continuous output. $$\displaystyle y = w^T x + b $$. Loss = MSE.

  • Logistic Regression: For classification. Uses sigmoid: $$\displaystyle P(y=1|x) = \frac{1}{1+e^{-(w^T x + b)}} $$. Loss = Cross-Entropy.

• Locally Weighted Linear Regression (LWLR):

  • Non-parametric. For each query point, fit a linear model weighted by proximity (kernel) to that point.

  • Captures local patterns, but computationally expensive and no explicit model stored.

[!TIP] Ensemble Focus: Know Random Forest (bagging + feature randomness) and Gradient Boosting (sequential residual fitting) as they are extremely popular in practice.