Machine Learning (IT-802 (A)) - Unit 5 Short Notes

UNIT 5: Machine Learning

I. Foundations of Machine Learning

Definition & Importance

Machine Learning (ML) is a subset of AI that enables systems to learn from data without explicit programming. It's crucial for handling complex, data-driven problems (e.g., image recognition, predictive analytics) where rule-based systems fail.

Hypothesis Space & Inductive Bias

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

• Inductive Bias: Assumptions made by the learning algorithm to generalize from training data (e.g., preferring simpler models).

• Finite vs. Infinite H:

  | Finite H | Infinite H | |--------------|----------------| | Limited models (e.g., decision trees with depth ≤ d) | Unbounded models (e.g., neural networks with unlimited weights) | | Lower risk of overfitting | Higher capacity, risk of overfitting without regularization |

Data Preprocessing

• Normalization: Scales features to [0,1] range.

$$x' = \frac{x - x_{\min}}{x_{\max} - x_{\min}}$$

• Standardization: Scales to mean=0, variance=1.

$$x' = \frac{x - \mu}{\sigma}$$

• Encoding Categorical Variables:

  • One-Hot Encoding: Creates binary columns for each category (increases dimensionality).

  • Label Encoding: Assigns integers (implies ordinality—use cautiously).

• Curse of Dimensionality: As dimensions increase, data becomes sparse, distance metrics lose meaning, and computational cost rises.

Evaluation Metrics

• Classification:

  | Metric | Formula | Focus | |------------|-------------|-----------| | Accuracy | $$\displaystyle \frac{TP+TN}{TP+TN+FP+FN} $$ | Overall correctness | | Precision | $$\displaystyle \frac{TP}{TP+FP} $$ | False positive control | | Recall | $$\displaystyle \frac{TP}{TP+FN} $$ | False negative control | | F1-Score | $$\displaystyle 2 \times \frac{\text{Precision} \times \text{Recall}}{\text{Precision} + \text{Recall}} $$ | Balance of P & R |

• Regression:

  • MSE: $$\displaystyle \frac{1}{n}\sum(y_i - \hat{y}_i)^2 $$ (sensitive to outliers).

  • MAE: $$\displaystyle \frac{1}{n}\sum|y_i - \hat{y}_i| $$ (robust).

  • R²: $$\displaystyle 1 - \frac{\sum(y_i - \hat{y}_i)^2}{\sum(y_i - \bar{y})^2} $$ (variance explained).

• BLEU Score (NLP):

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

where $$\displaystyle p_n $$ = n-gram precision, $BP$ = brevity penalty.

• Cross-Validation:

  • k-fold: Split data into k subsets; train on k-1, test on 1; repeat k times.

  • Purpose: Reduce variance in performance estimate, detect overfitting.

Model Performance Assessment

• Overfitting: High training accuracy, low validation accuracy (model memorizes noise).

• Underfitting: Low training & validation accuracy (model too simple).

• Solutions:

  • Overfitting: Regularization (L1/L2), dropout, more data, pruning.

  • Underfitting: Increase model complexity, feature engineering.

• Hyperparameter Tuning: Directly impacts model capacity (e.g., SVM C, tree depth).

• Data Splits:

  • Training: Model learning.

  • Validation: Hyperparameter tuning.

  • Testing: Final unbiased evaluation.

[!TIP]

Common Pitfall: Using test data for hyperparameter tuning leads to overfitting to test set. Always keep test set untouched until final evaluation.

II. Supervised Learning Algorithms

A. Regression

• Linear Regression:

  • Assumptions: Linearity, independence, homoscedasticity, normal errors.

  • Cost Function: SSE (Sum of Squared Errors).

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

• Goal: Minimize SSE via gradient descent.

• Multiple Linear Regression: Extends to multiple features: $$\displaystyle \hat{y} = \beta_0 + \beta_1 x_1 + ... + \beta_p x_p $$.

• Logistic Regression:

  • Uses sigmoid: $$\displaystyle \sigma(z) = \frac{1}{1+e^{-z}} $$.

  • Outputs probability for binary classification.

  • Cost: Log loss (cross-entropy).

• Locally Weighted Linear Regression:

  • Fits linear models weighted by proximity to query point (non-parametric).

B. Classification

Support Vector Machines (SVM)

• Optimal Hyperplane: Maximizes margin (distance to nearest points of each class).

• Support Vectors: Training points lying on margin boundaries; define the hyperplane.

• Linear SVM (separable):

$$\min_{w,b} \frac{1}{2}||w||^2 \quad \text{s.t.} \quad y_i(w \cdot x_i + b) \geq 1$$

• Applications: Bioinformatics (gene classification), image recognition (high-dimensional efficiency).

• High-Dimensional Performance: Effective due to kernel trick; margin maximization reduces overfitting.

Decision Trees

• ID3 Algorithm:

  1. Start with all examples at root.

  2. Select attribute with highest information gain to split.

  3. Recurse on subsets.

• Entropy (impurity measure):

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

• Information Gain:

$$IG(S,A) = Entropy(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} Entropy(S_v)$$

• Issues: Overfitting (solution: pruning—pre or post-pruning), bias toward multi-valued attributes.

K-Nearest Neighbors (K-NN)

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

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

• Example (Player Drafting):

  Given features (speed, agility), compute distances to all players, pick k=3 nearest, majority vote.

C. Ensemble Methods

[!TIP]

Key Difference: Bagging reduces variance (parallel, independent learners); Boosting reduces bias (sequential, error-correcting).

III. Neural Networks and Deep Learning

A. Basics

• Perceptron:

  • Output: $$\displaystyle y = f(w \cdot x + b) $$, where $f$ is step function.

  • Learning: $$\displaystyle w_{new} = w_{old} + \eta (t - y) x $$ (for misclassified points).

• Multilayer Perceptron (MLP): Input → Hidden (non-linear) → Output layers.

• Backpropagation:

  1. Forward pass: compute output and loss.

  2. Backward pass: compute gradients via chain rule.

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

  • Role: Enables training deep networks by efficiently computing gradients layer-by-layer.

• Parallel Processing: Operations (matrix multiplies) are highly parallelizable (GPU-friendly).

B. Activation Functions

[!TIP]

Vanishing Gradient: Gradients shrink exponentially during backprop through deep nets with sigmoid/tanh. Exploding Gradient: Opposite—gradients grow uncontrollably (mitigate via gradient clipping).

C. Convolutional Neural Networks (CNN)

• Convolution Operation:

  • Filter (kernel) slides over input, computes dot product → feature map.

  • Detects local patterns (edges, textures).

• Padding:

  • Same: Output size = input size (preserves spatial info).

  • Valid: No padding (output shrinks).

• 1×1 Convolution:

  • Purpose: Feature reduction/channel mixing (e.g., Inception modules).

  • Reduces computational cost without losing spatial resolution.

• CNN Architecture Trend: Downscale spatial dimensions (pooling) while increasing filters (depth) → hierarchical features.

• Inception Module:

  • Parallel convolutions (1×1, 3×3, 5×5) + pooling, concatenate outputs.

  • Efficiency: Multi-scale feature extraction in one block.

• Flattening Layer: Converts 3D feature maps to 1D vector for fully connected layers.

• Sub-sampling (Pooling): Max/average pooling reduces spatial size, provides translation invariance.

• Applications: ImageNet competition (AlexNet 2012 breakthrough), object detection, medical imaging.

D. Recurrent Neural Networks (RNN)

• Architecture: Hidden state $$\displaystyle h_t = f(W_{hh} h_{t-1} + W_{xh} x_t + b) $$; loops over sequence.

• Types:

  • Vanilla RNN: Simple recurrence, struggles with long-term dependencies (gradient vanishing/exploding).

  • LSTM: Gates (input, forget, output) control information flow; mitigates long-term dependency issue.

  • GRU: Simplified LSTM (reset, update gates).

• Long-Term Dependencies: LSTMs/GRUs use gating to retain/forget information over many timesteps.

• Role in NLP (ChatGPT): Early NLP models used LSTMs/GRUs for sequential generation; now largely replaced by Transformers (attention).

E. Specialized Architectures & Techniques

• Autoencoders:

  • Unsupervised; encoder compresses input to latent space, decoder reconstructs.

  • Used for dimensionality reduction, denoising, anomaly detection.

• Transfer Learning:

  • Feature Extraction: Freeze pretrained layers, add new classifier.

  • Fine-tuning: Unfreeze some layers, train with low LR on new data.

• One-Shot Learning:

  • Learn from one/few examples per class (vs. supervised needing many).

  • Uses metric learning (Siamese networks) or data augmentation.

  • Applications: Face recognition, rare event detection.

• Batch Normalization:

  • Normalizes layer inputs (mean=0, var=1) during training.

  • Purpose: Stabilizes training, allows higher learning rates, reduces internal covariate shift.

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

IV. Unsupervised Learning

A. Clustering

• K-means:

  1. Initialize k centroids randomly.

  2. Assign each point to nearest centroid (Euclidean).

  3. Update centroids as cluster means.

  4. Repeat until convergence.

  • Goal: Minimize intra-cluster variance.

• Expectation-Maximization (EM):

  • E-step: Compute responsibility (probability) of each cluster for each point (given current parameters).

  • M-step: Update cluster parameters (mean, covariance) to maximize expected log-likelihood.

  • Handles Missing Data: Treats missing values as latent variables; iteratively estimates them.

• Hierarchical Clustering:

  • AGNES (Agglomerative): Bottom-up; merge closest clusters (linkage: single/complete/average).

  • DIANA (Divisive): Top-down; split clusters recursively.

  • Comparison:

    | AGNES | DIANA | |-----------|-----------| | Simpler, but once merged cannot split | More complex, can refine splits | | Sensitive to noise/outliers | Can be more accurate |

• BIRCH: Builds CF-tree (Clustering Feature) for large datasets; incremental, memory-efficient.

B. Dimensionality Reduction

• Principal Component Analysis (PCA):

  1. Standardize data.

  2. Compute covariance matrix.

  3. Eigen-decomposition → eigenvectors (principal components) sorted by eigenvalue.

  4. Project data onto top k eigenvectors.

  • Benefits: Removes multicollinearity, speeds up learning, visualization.

• Locally Linear Embedding (LLE):

  • Preserves local linear relationships; non-linear.

  • vs PCA: PCA is linear global; LLE captures manifold structure locally.

  • Prefer LLE when: Data lies on a non-linear manifold (e.g., Swiss roll).

• Partial Least Squares (PLS): Supervised dimensionality reduction; maximizes covariance between features and target.

C. Probabilistic Clustering

• Gaussian Mixture Models (GMM):

  • Assumes data from mixture of Gaussians; each cluster = Gaussian distribution.

  • Soft clustering: Assigns probabilities of cluster membership.

  • Suitability for Overlapping Clusters: Probabilistic assignments handle ambiguity better than hard K-means.

V. Reinforcement Learning

A. Fundamentals

• Difference from Supervised/Unsupervised:

  • Supervised: Labeled data, fixed dataset.

  • Unsupervised: Find structure in unlabeled data.

  • RL: Agent learns by interacting with environment; delayed rewards, sequential decisions.

• Markov Decision Process (MDP):

  • Components: States (S), Actions (A), Transition probabilities $P(s'|s,a)$, Rewards $R(s,a,s')$, Discount factor $\gamma$.

  • Goal: Find policy $\pi(a|s)$ maximizing expected cumulative reward.

• Value Iteration vs. Policy Iteration:

  | Value Iteration | Policy Iteration | |---------------------|----------------------| | Iteratively updates value function $V(s)$ | Alternates policy evaluation + improvement | | No explicit policy until end | Maintains explicit policy | | Slower convergence per iteration | Faster per iteration, but evaluation costly |

B. Algorithms

• Q-learning:

  • Q-value: $Q(s,a)$ = expected cumulative reward for taking a in s.

  • Update (deterministic):

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

• Action Selection: $\epsilon$-greedy (explore with prob $\epsilon$, exploit otherwise).

• Off-policy: Learns optimal policy independent of behavior policy.

• SARSA:

  • Update:

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

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

• On-policy: Updates based on current policy's actions.

• Difference: SARSA is more conservative (accounts for exploration).

• Actor-Critic Models:

  • Actor: Policy network (selects actions).

  • Critic: Value network (evaluates actions).

  • Interaction: Critic guides actor updates (policy gradient).

  • Advanced: A2C (synchronous), A3C (asynchronous), PPO (clip surrogate objective).

• Frameworks: OpenAI Gym (environments), TensorFlow Agents (TF implementations).

VI. Probabilistic and Bayesian Methods

A. Bayes' Theorem

• Definition:

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

• Role in Classification: Computes posterior probability of class given features (e.g., Naive Bayes).

• Fundamental: Provides probabilistic framework for uncertainty, integrates prior knowledge.

B. Naive Bayes Classifier

• Assumption: Conditional Independence—features independent given class:

$$P(x_1,...,x_n|C) = \prod_i P(x_i|C)$$

• Posterior:

$$P(C|x) \propto P(C) \prod_i P(x_i|C)$$

• Simplification: Avoids joint probability over all features (exponential complexity → linear).

C. Bayesian Networks

• Construction:

  • Nodes: Random variables.

  • Edges: Direct dependencies (acyclic).

  • CPTs: Conditional Probability Tables for each node given parents.

• Joint Probability:

$$P(X_1,...,X_n) = \prod_i P(X_i | \text{Parents}(X_i))$$

• Inference Example (Car Value):

  Given evidence (Mileage=Lo, Engine=Bad, AC=Broken), use CPTs to compute $P(CarValue|evidence)$ via variable elimination.

D. Bayesian Learning

• Impact: Updates beliefs with data (posterior ∝ likelihood × prior).

• Applications: Spam filtering (Naive Bayes), medical diagnosis, A/B testing.

VII. Advanced Topics and Applications

A. Advanced Paradigms

• Self-Supervised Learning:

  • pretext tasks (e.g., predicting image rotation, masked language modeling) to learn representations from unlabeled data.

  • Importance: Reduces need for massive labeled datasets.

• Generative AI:

  • Models that generate new data (images, text).

  • GANs: Generator vs. discriminator adversarial training.

  • VAEs: Latent variable models with reconstruction + regularization loss.

• Attention Mechanisms:

  • Allows model to focus on relevant parts of input (e.g., "attend" to specific words in translation).

  • Role in Transformers: Core component (self-attention) enabling parallel processing and long-range dependencies.

B. Applications

• NLP Pipeline: Tokenization → embedding → (RNN/Transformer) → task-specific head.

  • BLEU: Machine translation evaluation (n-gram precision + brevity penalty).

• Computer Vision:

  • ImageNet competition (2012 AlexNet breakthrough → deep learning era).

  • Tasks: Classification, detection, segmentation.

• Speech Processing:

  • Speech-to-Text: Acoustic model (features → phonemes) + language model.

  • Speaker Identification/Synthesis: i-vectors, x-vectors; Tacotron/VITS for synthesis.

C. Optimization & Theory

• Loss Functions:

  • Regression: MSE, MAE.

  • Classification: Cross-entropy, hinge loss (SVM).

• Gradient Descent Variants:

  | Type | Batch Size | Pros/Cons | |----------|----------------|---------------| | Batch | Full dataset | Stable, slow, memory heavy | | Stochastic | 1 sample | Noisy, fast updates | | Mini-batch | b samples (common) | Balance of speed/stability |

• Convex Optimization:

  • Importance: Guarantees global optimum for convex loss (e.g., linear regression).

  • Non-convex (neural nets) → local minima, but empirical success.

• Linearity vs. Non-linearity:

  • Linear models: Limited capacity, gradient descent converges to global optimum.

  • Non-linear (via activation functions): Universal approximation, but non-convex optimization.

• Regularization:

  • L1 (Lasso): Adds $$\displaystyle \lambda \sum |w_i| $$ → sparse weights (feature selection).

  • L2 (Ridge): Adds $$\displaystyle \lambda \sum w_i^2 $$ → small weights (shrinks coefficients).

  • Prevent Overfitting: Penalize large weights, reduce model complexity.

• Frequent Pattern Mining:

  • Market Basket Analysis: Find itemsets with support ≥ min_support (e.g., Apriori algorithm).

  • Applications: Recommendation systems, cross-selling.

D. Additional Topics

• Data Augmentation (CNNs): Synthetic data via transformations (rotate, flip, crop) → improves generalization.

• Resampling Methods:

  • Bootstrapping: Sample with replacement to estimate uncertainty.

  • Cross-validation: Model evaluation (see Unit I).

• Clustering Evaluation:

  • Internal: Silhouette score, Davies-Bouldin (no ground truth).

  • External: Adjusted Rand Index (with ground truth).

• Factors in ML Experiments: Data quality, feature engineering, hyperparameters, random seeds, compute resources.

[!SUMMARY EXAM TIPS]

1. CNN Architecture: Always explain convolution → activation → pooling → (repeat) → flatten → FC layers. Highlight 1×1 conv for bottleneck, Inception for multi-scale.

2. Regularization: Contrast L1 (sparsity) vs L2 (weight decay).

3. RL Algorithms: Q-learning (off-policy, max Q) vs SARSA (on-policy, current Q). Actor-critic = policy + value.

4. Bayesian: Naive Bayes assumes feature independence; Bayes' theorem updates prior → posterior.

5. Activation Functions: ReLU default for hidden layers; output layer choice depends on task (sigmoid for binary, softmax for multi-class).

6. Overfitting in CNN: Signs: training loss ↓, validation loss ↑. Solutions: dropout, data augmentation, L2, early stopping.

7. BLEU: Emphasize brevity penalty prevents short translations from scoring high.

8. PCA vs LLE: PCA linear global; LLE non-linear local manifold.