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

Unit 3: Machine Learning – Comprehensive Short Notes

1. Foundations of Machine Learning

Definition and Importance

Machine Learning (ML) is a subset of AI that enables systems to learn and improve from experience without being explicitly programmed. It is crucial for solving complex, data-driven problems where traditional programming is infeasible.

[!TIP]

Exam Focus: Be ready to define ML and cite real-world applications (e.g., recommendation systems, medical diagnosis).

Perspectives and Issues

• Perspectives:

  • Practical: Focus on algorithms that work on real data.

  • Theoretical: Study computational learning theory, sample complexity.

• Issues:

  • Data quality (noise, missing values)

  • Overfitting/Underfitting

  • Curse of dimensionality

  • Computational scalability

  • Model interpretability

Hypothesis Space & Inductive Bias

• Hypothesis Space (H): Set of all possible models/algorithms considered for a problem.

• Inductive Bias: Assumptions made by the learning algorithm to generalize from training data (e.g., Occam’s razor in decision trees). Determines which hypothesis is chosen from H.

Data Preprocessing

Statistical Theory

• Hypothesis Testing: Assess if observed effect is statistically significant (null vs. alternative hypothesis).

• p-value: Probability of observing data given null hypothesis is true. p < 0.05 typically indicates significance.

• Confidence Interval: Range likely to contain true population parameter (e.g., 95% CI).

Training vs. Testing Data & Model Selection

• Training Data: Used to fit model parameters.

• Testing Data: Used to evaluate generalization performance.

• Model Selection Criteria:

  • AIC (Akaike Information Criterion): AIC = 2k - 2ln(L) (k = parameters, L = likelihood). Prefers simpler models.

  • BIC (Bayesian Information Criterion): BIC = k·ln(n) - 2ln(L). Stronger penalty for complexity.

Cross-Validation Techniques

Resampling Methods

• Bootstrapping: Sample with replacement to estimate statistics (e.g., confidence intervals).

• Jackknifing: Leave-one-out resampling; bias correction.

Evaluation Metrics

Classification:

• Confusion Matrix: [[TP, FP], [FN, TN]]

• Accuracy: (TP+TN)/Total

• Precision: TP/(TP+FP)

• Recall: TP/(TP+FN)

• F1-score: 2·(Precision·Recall)/(Precision+Recall)

• ROC-AUC: Area under ROC curve (trade-off TPR vs. FPR)

Regression:

• MSE: (1/n) Σ(y_i - ŷ_i)²

• MAE: (1/n) Σ|y_i - ŷ_i|

• R²: 1 - (Σ(y_i - ŷ_i)² / Σ(y_i - ȳ)²)

NLP (BLEU Score):

• n-gram Precision: Modified precision for n-grams (clips to max count in reference).

• Brevity Penalty (BP): BP = 1 if c > r, else exp(1 - r/c) (c = candidate length, r = reference length).

• BLEU: BP · exp(Σ w_n log p_n) (geometric mean of n-gram precisions).

Clustering:

• Silhouette Score: (b - a)/max(a, b) (a = intra-cluster distance, b = nearest-cluster distance). Range [-1, 1].

• Davies-Bouldin Index: Avg. similarity between clusters (lower = better).

Probability in ML

• Bayes’ Theorem: P(A|B) = [P(B|A)·P(A)] / P(B)

• Naive Bayes Classifier: Assumes feature independence. P(y|x) ∝ P(y) Π P(x_i|y). Efficient for text classification.

Data Science

• Lifecycle: Data collection → Preprocessing → Exploration → Modeling → Evaluation → Deployment.

• Applications: Business analytics (churn prediction), healthcare (disease detection), fraud detection.

2. Supervised Learning Algorithms

2.1 Linear Models

Linear Regression:

• Assumptions: Linearity, independence, homoscedasticity, normality of errors, no multicollinearity.

• Least Squares Estimation: Minimize Residual Sum of Squares (RSS). β = (XᵀX)⁻¹Xᵀy.

• Interpretation: Coefficients represent change in y per unit change in x.

Logistic Regression:

• Sigmoid Function: σ(z) = 1/(1 + e^{-z}). Outputs probability ∈ (0,1).

• Odds Ratio: odds = p/(1-p). Log-odds (logit) is linear in predictors.

• MLE: Maximize L(β) = Σ [y_i log(p_i) + (1-y_i) log(1-p_i)].

Locally Weighted Linear Regression:

• Kernel smoothing: weights decrease with distance from query point x_q.

• Weight: w_i = exp(-(x_i - x_q)² / (2τ²)) (τ = bandwidth).

• Solve weighted least squares for local fit.

2.2 Instance-Based Learning: K-NN

• Algorithm: For a query point, find k nearest training points (by distance metric), predict majority class (classification) or average (regression).

• Distance Metrics: Euclidean, Manhattan, Cosine.

• Choice of k: Small k → high variance (noise-sensitive); large k → high bias.

• Lazy Learning: No explicit training; stores all data.

[!TIP]

Exam Calculation: Given data points, compute distances, find k nearest, predict.

2.3 Decision Trees

Algorithms:

• ID3: Uses Information Gain (IG). IG(D, A) = Entropy(D) - Σ (|D_v|/|D|) Entropy(D_v).

• C4.5: Uses Gain Ratio to correct IG bias towards multi-valued attributes. Gain Ratio = IG / SplitInfo.

• CART: Uses Gini Impurity. Gini(D) = 1 - Σ p_i². Split minimizes weighted Gini.

Entropy Calculation: Entropy(D) = - Σ p_i log₂ p_i (p_i = proportion of class i).

Issues:

• Overfitting: Pruning (pre/post-pruning).

• Missing Values: Fractional instance splitting.

• Attribute Selection Bias: Multi-valued attributes favored by IG.

Appropriate Problems: When features are mixed (numeric/categorical), interpretability needed.

2.4 Support Vector Machines (SVM)

• Linear SVM: Find maximum margin hyperplane w·x + b = 0 that separates classes.

• Support Vectors: Training points closest to hyperplane; define margin.

• Margin: 2/||w||. Maximize margin ⇔ minimize ½||w||² subject to y_i(w·x_i + b) ≥ 1.

• Kernel Trick: Map data to high-dimensional space via kernel (without explicit transformation).

  • Polynomial Kernel: K(x_i, x_j) = (γ x_i·x_j + r)^d.

  • RBF Kernel: K(x_i, x_j) = exp(-γ ||x_i - x_j||²).

• High-Dimensional Applications: Bioinformatics (gene classification), image recognition.

• Advantages: Effective in high dimensions, robust to overfitting (margin maximization), versatile via kernels.

2.5 Ensemble Methods

Random Forest:

• Bagging: Bootstrap aggregating; train multiple trees on bootstrapped samples.

• Feature Randomness: At each split, consider subset of features.

• Out-of-Bag (OOB) Error: Estimate using samples not in bootstrap (≈ 37%).

• Variable Importance: Mean decrease in impurity or accuracy.

Bagging vs. Boosting:

Stacking:

• Meta-learner: Combines predictions of heterogeneous base models (e.g., SVM, RF, K-NN).

• Train meta-model on base models’ outputs.

3. Unsupervised Learning

3.1 Clustering

K-means:

• Algorithm:

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

  2. Assign each point to nearest centroid.

  3. Update centroids as mean of assigned points.

  4. Repeat until convergence.

• Elbow Method: Plot SSE vs. k; choose k at "elbow".

• Limitations: Sensitive to initialization, assumes spherical clusters, requires k.

Hierarchical Clustering:

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

  • Linkage Methods:

    • Single: min distance

    • Complete: max distance

    • Average: avg distance

    • Ward: increase in SSE

• Divisive (DIANA): Top-down; start with one cluster, split recursively.

• Dendrogram: Tree diagram showing cluster merges/splits.

Adaptive Hierarchical Clustering: Dynamically determines number of clusters based on density or connectivity (e.g., OPTICS).

Expectation-Maximization (EM) for GMM:

• E-step: Compute responsibility γ(z_i) = P(z_i=k|x_i, θ) for each cluster k.

• M-step: Update parameters:

  • μ_k = Σ γ(z_i) x_i / Σ γ(z_i)

  • Σ_k = Σ γ(z_i) (x_i - μ_k)(x_i - μ_k)ᵀ / Σ γ(z_i)

  • π_k = Σ γ(z_i) / n

• Handles Missing Data: Treat missing as latent variables; EM iterates until convergence.

BIRCH Algorithm:

• CF Tree: Clustering Feature tree stores summaries: (N, LS, SS) (count, linear sum, squared sum).

• Efficiency: Incremental, single-pass; suitable for large datasets.

3.2 Dimensionality Reduction

Principal Component Analysis (PCA):

1. Standardize data.

2. Compute covariance matrix Σ = (1/(n-1)) XᵀX.

3. Compute eigenvectors/eigenvalues of Σ.

4. Sort eigenvectors by decreasing eigenvalues; choose top k.

5. Transform: Z = X W_k (W_k = top k eigenvectors).

• Reconstruction Error: Minimized by PCA (orthogonal projection).

Partial Least Squares (PLS):

• Supervised; finds components that maximize covariance with response y.

• Steps: Similar to PCA but uses Xᵀy for direction.

Feature Selection vs. Extraction:

• Selection: Choose subset of original features (filter, wrapper, embedded).

• Extraction: Create new features (PCA, LDA, Autoencoders).

Backward Elimination:

• Start with all features; iteratively remove least significant (highest p-value > threshold).

• Use AIC/BIC or p-values to decide removal.

• Stop when all remaining features significant.

Benefits of Dimensionality Reduction:

• Mitigates curse of dimensionality (sparsity, distance concentration).

• Improves visualization, reduces noise, speeds up training.

Challenges of High-Dimensional Data:

• Exponential increase in volume (sparsity).

• Overfitting risk.

• Distance metrics become less discriminative.

3.3 Density Estimation

Gaussian Mixture Models (GMM):

• Probability density: p(x) = Σ_{k=1}^K π_k N(x|μ_k, Σ_k).

• Parameters estimated via EM (as above).

Kernel Density Estimation (KDE):

• p(x) = (1/(n h^d)) Σ K((x - x_i)/h).

• Bandwidth h: Critical; too small → noisy, too large → oversmoothed. Use cross-validation or Silverman’s rule.

4. Neural Networks and Deep Learning

4.1 Fundamentals

Biological vs. Artificial Neuron:

• Biological: Dendrites (input), soma (processing), axon (output), synapses (weights).

• Artificial: Weighted sum + bias → activation function.

Perceptron:

• Learning Rule: w_i ← w_i + η (t - o) x_i (t = target, o = output).

• Convergence Theorem: Guaranteed if data linearly separable.

• Limitation: Cannot learn non-linear patterns (XOR problem).

Multi-Layer Perceptron (MLP):

• Architecture: Input layer → Hidden layers (non-linear) → Output layer.

• Universal Approximation Theorem: Single hidden layer with sufficient neurons can approximate any continuous function.

Activation Functions:

Backpropagation:

1. Forward Pass: Compute activations layer by layer.

2. Compute Loss: L(θ).

3. Backward Pass: Compute gradients via chain rule.

   • δ^L = ∇_a L ⊙ σ'(z^L) (output layer).

   • δ^l = (W^{l+1})ᵀ δ^{l+1} ⊙ σ'(z^l) (hidden layers).

4. Update: W^l ← W^l - η δ^l a^{l-1}ᵀ, b^l ← b^l - η δ^l.

[!TIP]

Exam Algorithm: Be prepared to write pseudocode and compute weight updates for a given network.

Parallel Processing: GPUs accelerate matrix operations (convolution, matrix multiply); distributed training splits data/model across devices.

4.2 Convolutional Neural Networks (CNN)

Architecture:

• Convolutional Layers: Apply filters → feature maps.

• Pooling Layers: Downsample (max/average) → translation invariance.

• Fully Connected (Dense) Layers: Final classification/regression.

• Flatten Layer: Converts 3D feature maps to 1D vector for dense layers.

Convolution Operation:

• Filter/Kernel: K ∈ ℝ^{k×k×c_in} (k = size, c_in = input channels).

• Feature Map: F_{i,j} = Σ_{m,n} K_{m,n} · X_{i+m, j+n} + b.

• Stride (s): Step size; output size ⌊(W - k)/s⌋ + 1.

• Padding: Add zeros around input to preserve size.

  • 'Same': Output size = input size (pad appropriately).

  • 'Valid': No padding; output shrinks.

• Dilation: Spacing between kernel elements; increases receptive field.

1×1 Convolution:

• Purpose:

  • Feature reduction (change depth/channels).

  • Channel mixing (linear combination across channels).

  • Introduce non-linearity without spatial change.

• Efficiency: Few parameters; used in Inception, ResNet bottlenecks.

Subsampling (Pooling):

• Max Pooling: Takes max in window → retains prominent features.

• Average Pooling: Average in window → smoother downsampling.

• Role: Reduces spatial size, provides translation invariance, increases receptive field.

Architectural Innovations:

• Inception Module: Parallel convolutions (1×1, 3×3, 5×5) + pooling; concatenate outputs. Captures multi-scale features efficiently.

• Residual Block (ResNet): Skip connection: y = F(x) + x. Solves vanishing gradient; enables very deep networks (100+ layers).

Batch Normalization:

• Normalize layer inputs: x̂ = (x - μ_B)/√(σ_B² + ε).

• Then scale and shift: y = γ x̂ + β (γ, β learned).

• Benefits: Faster convergence, reduces internal covariate shift, slight regularization.

Downscaling Images & Increasing Filters:

• Early layers: small filters (detect edges, textures), few filters.

• Deeper layers: larger receptive fields (via stacking/pooling), more filters (complex patterns).

Overfitting/Underfitting in CNNs:

• Diagnosis: Training loss ↓, validation loss ↑ → overfitting; both high → underfitting.

• Solutions:

  • Overfitting: Data augmentation, dropout, L2 regularization, early stopping.

  • Underfitting: Increase model capacity, reduce regularization, more features.

CNN in TensorFlow:

model = Sequential([

    Conv2D(filters=32, kernel_size=(3,3), activation='relu', input_shape=(28,28,1)),

    MaxPool2D(pool_size=(2,2)),

    Conv2D(64, (3,3), activation='relu'),

    MaxPool2D((2,2)),

    Flatten(),

    Dense(128, activation='relu'),

    Dense(10, activation='softmax')

])

model.compile(optimizer='adam', loss='categorical_crossentropy', metrics=['accuracy'])

4.3 Recurrent Neural Networks (RNN)

Vanilla RNN:

• Equations:

  • h_t = tanh(W_hh h_{t-1} + W_xh x_t + b_h)

  • y_t = softmax(W_hy h_t + b_y)

• Unfolding in Time: Recurrent connection expanded to a deep network with shared weights.

• Problems: Vanishing/exploding gradients (due to repeated multiplication), short-term memory.

Long Short-Term Memory (LSTM):

• Cell State (C_t): "Conveyor belt" for long-term info.

• Gates:

  • Forget Gate: f_t = σ(W_f · [h_{t-1}, x_t] + b_f) → what to discard from C_{t-1}.

  • Input Gate: i_t = σ(W_i · [h_{t-1}, x_t] + b_i), C̃_t = tanh(W_C · [h_{t-1}, x_t] + b_C) → candidate values.

  • Update State: C_t = f_t ⊙ C_{t-1} + i_t ⊙ C̃_t.

  • Output Gate: o_t = σ(W_o · [h_{t-1}, x_t] + b_o), h_t = o_t ⊙ tanh(C_t).

• Handles Long-Term Dependencies: Gradient flow through cell state is near-constant.

Gated Recurrent Unit (GRU):

• Simpler: no cell state; reset gate (r_t) and update gate (z_t).

• h_t = (1 - z_t) ⊙ h_{t-1} + z_t ⊙ h̃_t (h̃_t = candidate hidden state).

• Fewer parameters than LSTM; often comparable performance.

Comparison:

Backpropagation Through Time (BPTT): Unfold network, apply standard backprop; gradients accumulated across time steps.

Applications in NLP: Language modeling, text generation, machine translation (early models like LSTMs in GPT-1).

4.4 Autoencoders

• Structure:

  • Encoder: z = f(x) (compresses to latent space).

  • Decoder: x̂ = g(z) (reconstructs).

• Training: Minimize reconstruction loss (MSE for real-valued, cross-entropy for binary).

• Types:

  • Denoising Autoencoder: Train to reconstruct clean input from corrupted version.

  • Variational Autoencoder (VAE): Learns probabilistic latent space; loss = reconstruction + KL divergence (regularization).

• Applications: Dimensionality reduction, anomaly detection (high reconstruction error), generative modeling (VAE).

4.5 Attention and Transformers

Attention Mechanism:

• Query (Q), Key (K), Value (V): Compute attention weights as similarity of Q and K.

• Scaled Dot-Product: Attention(Q,K,V) = softmax(QKᵀ/√d_k) V.

• Self-Attention: Q, K, V all from same sequence (captures contextual relationships).

Transformer Architecture:

• Encoder-Decoder: Both consist of stacked identical layers.

• Each Layer:

  1. Multi-Head Attention (parallel attention heads).

  2. Add & Norm (residual + layer norm).

  3. Position-wise Feed-Forward Network.

  4. Add & Norm.

• Positional Encoding: Add sinusoidal or learned embeddings to input to inject sequence order.

• Role in NLP:

  • BERT: Encoder-only, masked language modeling.

  • GPT/ChatGPT: Autoregressive decoder-only, next-token prediction.

• Advantages over RNNs: Parallelizable (no recurrence), handles long-range dependencies effectively.

5. Regularization and Optimization

5.1 Regularization Techniques

L1 Regularization (Lasso):

• Penalty: λ Σ |w_i|.

• Effect: Drives some weights to exactly zero → sparsity, feature selection.

• Geometry: Diamond-shaped constraint; solutions at corners.

L2 Regularization (Ridge):

• Penalty: λ Σ w_i².

• Effect: Shrinks weights uniformly; no sparsity.

• Weight Decay: Update rule: w ← w - η(∇L + 2λw).

• Handles Multicollinearity: Stabilizes solutions.

Comparison L1 vs L2:

Dropout:

• Randomly deactivate neurons (probability p) during training.

• Prevents co-adaptation; acts as ensemble approximation.

• At test time, use all neurons but scale activations by p.

Data Augmentation:

• Images: Rotation, flipping, cropping, color jitter, noise.

• Text: Synonym replacement, back-translation, random deletion.

• Audio: Noise injection, pitch shift, time stretching.

• Importance: Increases effective dataset size, improves generalization.

5.2 Loss Functions

Role in Backprop: Loss gradient ∇_θ L guides weight updates; choice affects optimization landscape and convergence.

5.3 Optimization Algorithms

Gradient Descent Variants:

• Batch GD: Use entire dataset per update → stable but slow.

• Stochastic GD (SGD): One sample per update → noisy but fast escape from local minima.

• Mini-batch GD: Compromise; standard in practice.

Momentum:

• v ← β v + (1-β) ∇L, θ ← θ - η v.

• Accelerates convergence, dampens oscillations.

Adaptive Methods:

• AdaGrad: G ← G + (∇L)², θ ← θ - η ∇L / (√G + ε). Accumulates squared gradients → aggressive early, small later.

• RMSprop: E[g²] ← ρ E[g²] + (1-ρ) g², θ ← θ - η g / (√E[g²] + ε). Decays past gradients.

• Adam: Combines Momentum + RMSprop.

  • m ← β1 m + (1-β1) g, v ← β2 v + (1-β2) g².

  • Bias-corrected: m̂ = m/(1-β1^t), v̂ = v/(1-β2^t).

  • Update: θ ← θ - η m̂ / (√v̂ + ε).

  • Default: β1=0.9, β2=0.999, ε=1e-8.

Learning Rate Schedules:

• Step Decay: Reduce LR by factor every k epochs.

• Exponential Decay: η_t = η_0 exp(-kt).

• Cosine Annealing: η_t = η_min + ½(η_max - η_min)(1 + cos(π t/T)).

5.4 Hyperparameter Tuning

• Importance: Directly impacts model performance (accuracy, convergence speed).

• Methods:

  • Grid Search: Exhaustive over predefined grid → computationally expensive.

  • Random Search: Sample random combinations → often more efficient.

  • Bayesian Optimization: Builds surrogate model (e.g., Gaussian Process) to guide search.

  • Hyperband: Uses early stopping to allocate resources; bandit-based.

• Cross-Validation: Use CV folds to evaluate each hyperparameter set; select best based on validation score.

6. Reinforcement Learning

6.1 Fundamentals

• Agent: Learner/decision-maker.

• Environment: World agent interacts with.

• State (s): Representation of environment.

• Action (a): Agent’s move.

• Reward (r): Immediate scalar feedback.

• Policy (π): Strategy mapping states to actions (stochastic or deterministic).

• Value Function: V^π(s) = E[Σ γ^t r_t | s_0=s, π] (expected discounted return).

• Markov Decision Process (MDP): (S, A, P, R, γ) where P(s'|s,a) is transition probability.

• Bellman Equation: V^π(s) = Σ_a π(a|s) Σ_{s'} P(s'|s,a)[R(s,a,s') + γ V^π(s')].

• Discount Factor γ ∈ [0,1]: Near 1 = far-sighted; 0 = myopic.

Value Iteration:

• Initialize V(s)=0; repeat until convergence:

  • V_{k+1}(s) = max_a Σ_{s'} P(s'|s,a)[R(s,a,s') + γ V_k(s')].

• Extract greedy policy: π(s) = argmax_a Σ_{s'} P(s'|s,a)[R + γ V(s')].

• Convergence: Guaranteed; faster than policy iteration (no policy evaluation step).

Policy Iteration:

1. Policy Evaluation: Compute V^π for current π (solve linear system or iterate).

2. Policy Improvement: π'(s) = argmax_a Σ_{s'} P(s'|s,a)[R + γ V^π(s')].

3. Repeat until π = π' (stable).

• Comparison: Policy iteration often converges in fewer iterations but each iteration costlier (solving linear system).

6.2 Model-Free Methods

Q-learning (Off-policy):

• Learns action-value Q(s,a).

• Update Rule: Q(s,a) ← Q(s,a) + α [r + γ max_{a'} Q(s',a') - Q(s,a)].

• Exploration-Exploitation: ε-greedy: with prob ε choose random action, else argmax Q.

• Deterministic Rewards/Actions: Converges to optimal Q*.

SARSA (On-policy):

• Updates using action actually taken: Q(s,a) ← Q(s,a) + α [r + γ Q(s',a') - Q(s,a)] (where a' is next action from π).

• Difference: Q-learning learns optimal policy regardless of behavior policy; SARSA learns policy π (on-policy). SARSA is more conservative (accounts for exploration).

Comparison Q-learning vs SARSA:

6.3 Actor-Critic Methods

• Actor: Policy network (π_θ); outputs actions.

• Critic: Value network (V_φ or Q_φ); evaluates states/actions.

• Interaction: Actor selects action; Critic computes TD error δ = r + γ V(s') - V(s); Actor updates policy via gradient ∇_θ log π_θ(a|s) δ.

• Advantage Actor-Critic (A2C): Synchronous; uses advantage function A(s,a) = Q(s,a) - V(s) (or TD residual) to reduce variance.

• Asynchronous Advantage Actor-Critic (A3C): Multiple actors in parallel environments; asynchronous gradient updates.

• Proximal Policy Optimization (PPO): Clipped objective: L(θ) = E[min(r_t(θ) A_t, clip(r_t(θ), 1-ε, 1+ε) A_t)] where r_t = π_θ/π_θ_old. Ensures small policy updates → stable training.

6.4 Applications and Frameworks

• Applications: Game playing (AlphaGo, DQN), robotics control, autonomous driving, resource management (data centers).

• Frameworks:

  • OpenAI Gym: Standard API for RL environments (Atari, MuJoCo).

  • TensorFlow Agents (TF-Agents): Library of RL algorithms (DQN, PPO) built on TensorFlow.

6.5 Specialized Paradigms

One-Shot Learning:

• Definition: Learn from very few examples (often one per class).

• Difference from Traditional: Traditional requires many examples; one-shot uses prior knowledge/metric learning.

• Applications: Face recognition (new person from one photo), rare event detection.

• Methods:

  • Metric Learning: Learn embedding space where similar items close (Siamese networks, triplet loss).

  • Memory-Augmented Networks: Neural Turing Machines, Differentiable Neural Computers.

7. Applications of Machine Learning

7.1 Natural Language Processing (NLP)

NLP Pipeline:

1. Text Preprocessing: Tokenization, stop-word removal, stemming/lemmatization.

2. Feature Extraction:

   • Bag-of-Words (BoW): Word counts.

   • TF-IDF: TF·IDF (term frequency × inverse document frequency).

   • Word Embeddings: Dense vectors (Word2Vec, GloVe, BERT).

3. Modeling: n-gram, RNN/LSTM, Transformer (BERT, GPT).

BLEU Score (Machine Translation):

• n-gram Precision: For each n, compute modified precision p_n = (Σ_{candidate} min(count_{candidate}(ngram), count_{reference}(ngram))) / (total candidate n-grams).

• Brevity Penalty (BP): BP = 1 if c > r, else exp(1 - r/c).

• BLEU-N: BP · exp(Σ_{n=1}^N w_n log p_n) (usually N=4, w_n=1/4).

Language Models:

• n-gram: Count-based, sparse.

• RNN/LSTM: Sequential, captures context but slow training.

• Transformer (GPT, BERT): Self-attention; parallel, long-range dependencies.

ChatGPT: Autoregressive Transformer (GPT architecture) fine-tuned with RLHF (Reinforcement Learning from Human Feedback): supervised fine-tuning → reward model training → PPO optimization.

Other Applications: Sentiment analysis, named entity recognition, machine translation.

7.2 Computer Vision

CNN Applications:

• Image Classification: ImageNet challenge; models: AlexNet (2012), VGG, GoogLeNet/Inception, ResNet.

• Object Detection: YOLO (single-stage), Faster R-CNN (two-stage).

• Image Segmentation: U-Net (encoder-decoder with skip connections).

ImageNet Competition:

• Large-scale dataset (1.2M images, 1000 classes).

• Annual challenge; AlexNet (2012) breakthrough with deep CNN + ReLU + Dropout + GPU training.

• Spurred deep learning revolution.

Short Note: Computer Vision enables machines to interpret visual data. Tasks: classification (what?), detection (where?), segmentation (pixel-level). Approaches: traditional (SIFT, HOG) → ML (SVM) → DL (CNN, Transformers).

7.3 Speech Processing

Speech-to-Text (ASR):

1. Feature Extraction: MFCC (Mel-Frequency Cepstral Coefficients), filter banks.

2. Acoustic Model:

   • Traditional: HMM (temporal) + GMM/DNN (emission).

   • End-to-End: DeepSpeech (RNN/CTC), Wav2Vec 2.0 (self-supervised).

3. Language Model: n-gram, RNN, Transformer (rescoring).

4. Decoder: Combines acoustic + language scores (e.g., beam search).

Speaker Identification/Verification:

• Feature Extraction: i-vectors (low-dimensional representation), x-vectors (DNN-based).

• Embedding Models: ECAPA-TDNN (state-of-the-art).

• Scoring: Cosine similarity, PLDA (Probabilistic Linear Discriminant Analysis).

How ML Applied: Supervised learning with labeled audio; deep learning for feature learning; end-to-end systems (audio → text).

8. Advanced and Emerging Topics

8.1 Transfer Learning

• Concept: Use knowledge (weights) from a pre-trained model on a large dataset (source task) for a new related task (target) with limited data.

• Types:

  • Feature Extraction: Freeze pre-trained layers; train new classifier on top.

  • Fine-Tuning: Unfreeze some deeper layers; train with smaller LR.

• Benefits: Faster convergence, better performance with small data, reduces need for large labeled datasets.

• Examples: ImageNet pre-trained ResNet for medical imaging; BERT fine-tuned for sentiment analysis.

8.2 Self-Supervised Learning

• Definition: Learn representations from unlabeled data by designing pretext tasks (supervision from data itself).

• Examples:

  • SimCLR, MoCo: Contrastive learning (pull similar augmentations together, push others apart).

  • MAE (Masked Autoencoder): Randomly mask patches, reconstruct.

  • BERT: Masked language modeling (predict masked tokens).

• Benefits: Reduces dependency on labeled data; learns robust, general features.

8.3 Generative AI

Generative Models:

• GANs: Generator G(z) creates fake data; Discriminator D(x) distinguishes real vs. fake. Adversarial training: min_G max_D V(D,G).

• VAEs: Encoder outputs distribution parameters (μ, σ); sample latent z; decoder reconstructs. Loss = reconstruction + KL divergence.

• Autoregressive Models: PixelCNN (images), WaveNet (audio), GPT (text). Factorize joint probability as product of conditionals: p(x) = Π p(x_i|x_{<i}).

• Diffusion Models:

  • Forward Process: Gradually add noise (Markov chain) until data becomes Gaussian.

  • Reverse Process: Learn neural network to denoise step-by-step.

  • Score-Based: Estimate score (gradient of log density).

Applications: Art generation (DALL-E, Midjourney), drug discovery (molecule generation), synthetic data creation.

8.4 Bayesian Methods

• Bayes’ Theorem: P(θ|D) = [P(D|θ) P(θ)] / P(D).

  • Prior P(θ): Belief before seeing data.

  • Likelihood P(D|θ): Probability of data given parameters.

  • Posterior P(θ|D): Updated belief after data.

• Bayesian Learning: Treat parameters as random variables; infer posterior distribution (not point estimate).

• Bayesian Networks: Directed acyclic graph (DAG) with nodes = random variables, edges = conditional dependencies. Each node has CPT (Conditional Probability Table).

  • Inference: Exact (variable elimination, junction tree) or approximate (MCMC, variational).

• Naive Bayes: Assumes features conditionally independent given class. P(y|x) ∝ P(y) Π P(x_i|y).

• Benefits: Quantifies uncertainty, incorporates prior knowledge, robust to overfitting (especially with small data).

8.5 Mathematical Foundations

Convex Optimization:

• Convex Set: Line segment between any two points lies within set.

• Convex Function: f(λx + (1-λ)y) ≤ λf(x) + (1-λ)f(y) for λ∈[0,1].

• Importance in ML: Many loss functions (linear regression, logistic regression) are convex → global optimum guaranteed.

• Algorithms: Gradient descent, interior-point methods.

Linearity vs Non-linearity:

• Linear Models: Decision boundary is linear (hyperplane). E.g., linear regression, logistic regression. Convex optimization → global optimum.

• Non-linear Models: Can learn complex boundaries (neural networks, kernel SVM). Non-convex → multiple local minima; gradient descent may get stuck.

• Effect on Gradient Descent:

  • Convex: Converges to global minimum (with appropriate LR).

  • Non-convex: May converge to local minimum/saddle point; needs tricks (momentum, initialization, batch norm).

8.6 Miscellaneous Important Topics

Attention Models: Compute weighted sum of values, weights from query-key similarity. Enables focus on relevant parts (e.g., in translation, attend to relevant source words).

Data Augmentation: (See 5.1) Key for regularization, especially in vision/audio.

Flattening in CNN: Operation after convolutional/pooling layers to convert 3D feature maps (height × width × channels) into 1D vector for dense layers.

Batch Normalization: (See 4.2) Normalizes layer inputs; accelerates training, acts as regularizer.

Goals of Clustering:

• Exploration (discover patterns)

• Summarization (representative prototypes)

• Density estimation (estimate probability distribution)

• Outlier detection (points far from clusters)

Factors in Clustering:

• Distance Metric: Euclidean (spherical clusters), Manhattan (robust to outliers), Cosine (orientation, text).

• Number of Clusters (k): Often unknown; use elbow, silhouette.

• Initialization Sensitivity: K-means++ improves.

• Scalability: K-means O(n); hierarchical O(n²) or O(n³).

Final Note: This summary covers high-frequency exam topics from past RGPV papers. Focus on definitions, formulas, algorithms (step-by-step), comparisons, and applications. Practice numerical problems (K-means, backprop, BLEU, EM). Use diagrams where possible (CNN architecture, LSTM gates, transformer).