UNIT 2: MACHINE LEARNING - COMPREHENSIVE NOTES

I. FOUNDATIONS & CONCEPTS

Definition and Importance of Machine Learning

• Definition: ML is a subset of AI that provides systems the ability to automatically learn and improve from experience without being explicitly programmed.

• Importance in Real-World Problem-Solving:

  • Handles massive, complex datasets (Big Data).

  • Enables pattern recognition and prediction in domains like healthcare, finance, and marketing.

  • Powers adaptive systems (recommendation engines, autonomous vehicles).

  • Automates decision-making processes.

• Perspectives:

  • AI: Broad field of creating intelligent machines.

  • ML: The primary tool/approach for achieving AI through data-driven learning.

  • Deep Learning (DL): A subfield of ML using deep neural networks with multiple layers.

• Basic Design Issues & Approaches:

  • Goal: Prediction, classification, clustering, etc.

  • Data: Type (labeled/unlabeled), quality, size.

  • Model Selection: Choosing the right algorithm (bias-variance tradeoff).

  • Evaluation: How to measure success.

  • Approaches: Supervised, Unsupervised, Reinforcement Learning.

[!TIP] Exam Focus: Be prepared to contrast AI, ML, and DL with examples. Common question: "Explain ML by taking an example."

Hypothesis Space and Inductive Bias

• Hypothesis Space (H): The set of all possible models (functions) a learning algorithm can consider.

  • Finite H: Limited set of possible hypotheses (e.g., all decision trees with depth ≤ 5). Easier to search but may not contain the true target function.

  • Infinite H: Unbounded set (e.g., all possible linear functions). More expressive but requires careful regularization to avoid overfitting.

• Inductive Bias: The assumptions a learning algorithm uses to make predictions on unseen data. It guides the search through the hypothesis space.

  • Example: Occam's Razor (prefer simpler hypotheses) is a common inductive bias.

• Implications:

  • Model Complexity: Larger/infinite H can lead to higher complexity.

  • Generalization: The right inductive bias helps the model generalize well from training to unseen data.

[!TIP] Exam Focus: Key distinction: Finite H is searchable but restrictive; Infinite H is expressive but needs bias/regularization.

Statistical Learning Theory & Bayes' Theorem

• Role of Probability: Provides a framework for dealing with uncertainty, noise in data, and making probabilistic predictions.

• Bayes' Theorem (Fundamental):

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

Where:

*   $P(A|B)$ = Posterior probability (updated belief after seeing evidence B).

*   $P(B|A)$ = Likelihood.

*   $P(A)$ = Prior probability (initial belief).

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

• Bayesian Learning: Treats parameters as random variables. Updates prior beliefs about parameters to posterior beliefs given data.

  • Impact: Provides a principled way to incorporate prior knowledge and quantify uncertainty in predictions.

[!TIP] Exam Focus: Bayes' theorem is crucial for Naïve Bayes and Bayesian networks. Be ready to compute a posterior probability (e.g., "probability someone who tests positive is actually taking drugs").

Limitations and Challenges of Machine Learning

• Data Dependency: Requires large amounts of high-quality, relevant data. "Garbage in, garbage out."

• Lack of Explainability/Interpretability: Many complex models (especially deep learning) are "black boxes."

• Bias and Fairness: Models can perpetuate and amplify biases present in training data.

• Overfitting & Underfitting: The core challenge of balancing model complexity.

• Computational Cost: Training complex models, especially on large datasets, requires significant resources.

• Concept Drift: Model performance degrades over time as underlying data distributions change.

• Security & Adversarial Attacks: Models can be fooled by carefully crafted inputs.

II. DATA PREPROCESSING & EVALUATION

Data Preprocessing

• Importance & Necessity: Raw data is often noisy, inconsistent, and unsuitable for direct modeling. Preprocessing improves data quality, model convergence, and performance.

• Data Normalization/Standardization:

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

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

  • Impact: Essential for gradient descent convergence (prevents features with large scales from dominating), distance-based algorithms (KNN, K-means, SVM with RBF kernel), and regularization.

• Encoding Categorical Variables:

  • Label Encoding: Assigns an integer to each category (e.g., "Red"=1, "Blue"=2). Risk: Imposes ordinal relationship where none exists. Suitable for tree-based models.

  • One-Hot Encoding: Creates a binary column for each category. Impact: Increases dimensionality (curse of dimensionality). Suitable for linear models and distance-based algorithms.

  • Dimensionality Impact: One-Hot can explode feature space if a categorical variable has many unique values (high cardinality).

[!TIP] Exam Focus: Know why normalization is needed (convergence, stability). Know the trade-off between One-Hot (no ordinal bias) vs. Label Encoding (lower dim).

Evaluation Metrics

Model Validation & Selection

• Training vs. Testing Data: Split data to evaluate generalization. Never evaluate on training data.

• Cross-Validation (CV): Technique to assess model performance robustly.

  • k-fold CV: Data split into k folds. Train on k-1, test on 1. Repeat k times. Average performance.

  • Purpose: Reduces variance of performance estimate, uses data efficiently.

• Resampling Methods:

  • Bootstrap: Sample n observations with replacement from training set. Train on bootstrap sample, validate on "out-of-bag" samples.

• Overfitting vs. Underfitting:

  • Overfitting: High training accuracy, low test accuracy. Model learns noise. Solutions: More data, regularization (L1/L2), reduce model complexity, early stopping, dropout, data augmentation.

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

• Hyperparameter Tuning: Critical for model performance. Use techniques like Grid Search or Random Search with CV.

• Model Selection Criteria: Use a hold-out validation set or nested CV to compare different algorithms/hyperparameters based on a chosen metric (e.g., F1-score, R²).

III. SUPERVISED LEARNING ALGORITHMS

A. Regression

• Linear Regression: Models relationship as $$\displaystyle y = \beta_0 + \beta_1 x + \epsilon $$.

  • Assumptions: Linearity, Independence, Homoscedasticity, Normality of errors, No multicollinearity (for multiple).

  • Cost Function (SSE): $$\displaystyle J(\theta) = \frac{1}{2m} \sum_{i=1}^{m} (h_\theta(x^{(i)}) - y^{(i)})^2 $$. Minimized via Gradient Descent.

• Multiple Linear Regression: $$\displaystyle y = \beta_0 + \beta_1 x_1 + ... + \beta_p x_p + \epsilon $$.

• Logistic Regression: Used for classification (binary). Models probability $$\displaystyle P(y=1|x) = \frac{1}{1 + e^{-(\beta_0 + \beta^T x)}} $$. Uses log loss (cross-entropy) cost function.

• Locally Weighted Linear Regression (LWLR): Non-parametric. Fits a linear model to a subset of data weighted by proximity to the query point. Good for capturing local patterns but computationally expensive.

B. Classification

Decision Trees (ID3 Algorithm)

• Goal: Partition feature space into regions with homogeneous class labels.

• ID3 Algorithm Steps:

  1. Start with all training examples at root.

  2. If all examples belong to same class, make leaf with that class.

  3. Else, for each attribute, compute Information Gain.

  4. Select attribute with highest Information Gain to split on.

  5. Repeat recursively for each branch.

• Entropy (Measure of Impurity): $$\displaystyle Entropy(t) = -\sum_{i=1}^{c} p_i(t) \log_2 p_i(t) $$

• Information Gain: $$\displaystyle Gain(S, A) = Entropy(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} Entropy(S_v) $$

• Issues: Overfitting (pruning needed), bias towards attributes with many values, instability (small data changes → different tree).

Support Vector Machines (SVM)

• Core Idea: Find the optimal hyperplane that maximizes the margin (distance) between classes.

• Support Vectors: The training points closest to the hyperplane that support (define) the margin. Only these points matter for the final model.

• Linear SVM for Separable Data:

  • Primal Problem: Minimize $$\displaystyle \frac{1}{2}||w||^2 $$ subject to $$\displaystyle y^{(i)}(w^T x^{(i)} + b) \geq 1 $$.

  • Margin: $$\displaystyle \gamma = \frac{1}{||w||} $$. Maximizing margin is equivalent to minimizing $$\displaystyle ||w||^2 $$.

• Performance in High-Dimensional Spaces: SVM's kernel trick allows it to operate efficiently in high-dimensional spaces without explicitly computing coordinates. Effective in bioinformatics (gene classification) and image recognition (where pixels = high dim).

[!TIP] Exam Focus: Know the margin maximization objective. Be able to define support vectors and explain why they are critical.

Naïve Bayes Classifier

• Based on Bayes' Theorem: $$\displaystyle P(y|x) = \frac{P(x|y) P(y)}{P(x)} $$

• "Naïve" Assumption: Features are conditionally independent given the class label.

$$P(x|y) = P(x_1|y) \cdot P(x_2|y) \cdot ... \cdot P(x_n|y)$$

• Simplification: Avoids curse of dimensionality. Only need to estimate $$\displaystyle P(x_i|y) $$ for each feature independently.

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

• Posterior vs. Prior: $P(y)$ is prior (before seeing features). $P(y|x)$ is posterior (after seeing features).

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

• Algorithm:

  1. Store all training examples.

  2. For a new query point, compute distance (usually Euclidean: $$\displaystyle d(x,y) = \sqrt{\sum (x_i - y_i)^2} $$) to all training points.

  3. Identify the k nearest neighbors.

  4. For classification: majority vote of neighbors' classes.

  5. For regression: average of neighbors' target values.

• Characteristics: Simple, no training phase (lazy learning), sensitive to irrelevant features and scale (hence needs normalization), sensitive to k choice.

C. Ensemble Methods

• Goal: Combine multiple weak learners to create a strong learner, improving accuracy and robustness.

• Bagging (Bootstrap Aggregating):

  • Method: Create m bootstrap samples. Train m base models independently. Final prediction = average (regression) or majority vote (classification).

  • Effect: Reduces variance (especially for unstable models like trees). Example: Random Forest.

• Boosting:

  • Method: Train models sequentially. Each new model focuses on instances misclassified by previous ones (by re-weighting data).

  • Effect: Reduces bias. Can overfit if too many rounds. Examples: AdaBoost, Gradient Boosting, XGBoost.

• Stacking:

  • Method: Train multiple diverse base models (level-0). Use their predictions as input features for a meta-learner (level-1) which learns how to best combine them.

  • Role of Meta-Learner: Learns the optimal combination strategy (e.g., via linear regression or another classifier).

• Comparison:

  | Scheme | Training | Primary Goal | Example | | :--- | :--- | :--- | :--- | | Bagging | Parallel | Variance Reduction | Random Forest | | Boosting | Sequential | Bias Reduction | AdaBoost, XGBoost | | Stacking | Parallel (base), then sequential (meta) | Accuracy Boost | Heterogeneous model combos |

IV. UNSUPERVISED LEARNING

A. Clustering

Partitional Clustering: K-Means

• Algorithm Steps:

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

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

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

  4. Repeat 2-3 until convergence (centroids stabilize).

• Requirements/Goals: Clusters should be:

  • Intra-cluster compact (low variance).

  • Inter-cluster separated (high distance).

  • Shape: Assumes spherical, equally sized clusters (due to Euclidean distance & mean).

• Centroid Initialization: Critical. Poor init leads to suboptimal local minima. k-means++ helps by seeding centroids far apart.

Hierarchical Clustering

• AGNES (Agglomerative Nesting): Bottom-up. Start with each point as a cluster. Iteratively merge closest clusters.

  • Linkage Criteria: Defines "closest clusters":

    • Single: min distance between points.

    • Complete: max distance.

    • Average: avg distance.

    • Ward: increase in SSE (variance).

• DIANA (Divisive Analysis): Top-down. Start with all points in one cluster. Iteratively split the most heterogeneous cluster.

• Adaptive Hierarchical Clustering: Methods that determine the number of clusters automatically from the data structure (e.g., by analyzing dendrogram gaps or using statistical tests).

Probabilistic Clustering: EM for GMM

• Gaussian Mixture Model (GMM): Assumes data generated from a mixture of several Gaussian distributions. Can model overlapping clusters (soft assignment).

$$p(x) = \sum_{k=1}^{K} \pi_k \mathcal{N}(x|\mu_k, \Sigma_k)$$

Where $$\displaystyle \pi_k $$ = mixing coefficient (prior prob of cluster k).

• Expectation-Maximization (EM) Algorithm:

  • E-step: Compute responsibility $$\displaystyle \gamma(z_k) $$ = probability that point x belongs to cluster k, given current parameters.

  • M-step: Update parameters ($$\displaystyle \pi_k, \mu_k, \Sigma_k $$) to maximize expected complete-data log-likelihood, using responsibilities as weights.

  • Iterate until log-likelihood converges.

• Why EM for GMM? Handles missing data (cluster assignments) naturally. Suitable for overlapping clusters due to soft assignment.

[!TIP] Exam Focus: Contrast K-means (hard, spherical) vs. GMM/EM (soft, elliptical, overlapping). Know E-step vs. M-step.

B. Dimensionality Reduction

Principal Component Analysis (PCA)

• Goal: Find orthogonal axes (principal components) of maximum variance in the data. Used for feature extraction.

• Procedure:

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

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

  3. Compute eigenvectors and eigenvalues of $\Sigma$.

  4. Sort eigenvectors by decreasing eigenvalues.

  5. Select top k eigenvectors (principal components). Project data: $$\displaystyle X_{reduced} = X \cdot W_k $$.

• Example: If data lies along a line, 1st PC captures that direction.

PCA vs. Locally Linear Embedding (LLE)

• PCA: Global linear method. Preserves global variance structure. Assumes data lies on/near a linear subspace.

• LLE: Local non-linear method. Preserves local linear relationships (neighborhood structure). Unfolds non-linear manifolds (e.g., Swiss roll).

• Prefer LLE when: Data lies on a non-linear manifold. PCA fails to capture such intrinsic geometry.

Partial Least Squares (PLS)

• Similar to PCA but supervised. Finds components that maximize covariance between features and target variable(s). Used for regression/classification with high-dimensional, correlated features.

Benefits of Dimensionality Reduction:

• Reduces noise and redundancy.

• Improves model performance (less overfitting, faster training).

• Enables visualization (2D/3D plots).

• Feature Extraction vs. Selection: Extraction creates new features (e.g., PCA components). Selection chooses a subset of original features.

C. Association Rule Mining

• Frequent Pattern Mining: Discover interesting patterns (itemsets, subsequences) that appear frequently in a database.

• Market Basket Analysis: Classic application. Finds rules like {Diapers} -> {Beer}.

• k-Frequent Itemset Mining (Apriori-like):

  • Step 1 (Find Frequent Items): Scan DB, count item occurrences. Keep items with support ≥ min_sup.

  • Step 2 (Generate k-itemsets): Join frequent (k-1)-itemsets to form candidate k-itemsets. Prune those with infrequent subsets.

  • Step 3: Scan DB again to count support of candidates. Keep those ≥ min_sup.

  • Repeat until no more frequent itemsets.

• Example: For min_sup=2, from transactions {A,B}, {A,C}, {B,C}, {A,B,C}, frequent 1-itemsets: A(3), B(3), C(3). Frequent 2-itemsets: {A,B}(2), {A,C}(2), {B,C}(2). Frequent 3-itemset: {A,B,C}(1) -> not frequent.

V. NEURAL NETWORKS & DEEP LEARNING

A. Fundamentals

Artificial Neural Networks (ANN)

• Biological vs. Artificial: Inspired by neurons (dendrites = inputs, soma = processing, axon = output). Artificial: simplified, layered, weighted connections.

• Multi-Layer Perceptron (MLP) Architecture:

  • Input Layer: Feature vector.

  • Hidden Layer(s): One or more layers with non-linear activation functions. Enables learning complex functions.

  • Output Layer: Produces prediction (e.g., class probabilities via softmax).

  • Diagram: Fully connected between consecutive layers.

    DiagramCANVAS: A standard 3-layer MLP with input nodes, one hidden layer with multiple neurons, and output layer. Show weighted connections.

• Parallel Processing: Computations for all neurons in a layer can be done simultaneously (matrix operations), enabling efficient hardware (GPU) acceleration.

Activation Functions

• Vanishing Gradient Problem: In deep networks with sigmoid/tanh, gradients become extremely small during backpropagation, slowing or stopping learning in early layers. ReLU mitigates this.

Backpropagation Algorithm

• Role: Efficiently compute gradients of the loss function w.r.t. all weights in a feedforward network using the chain rule. Enables gradient descent training.

• Weight Adjustment: Propagates error backwards from output layer to input layer, adjusting weights proportionally to their contribution to the error.

• Algorithm Steps (for one example):

  1. Forward Pass: Compute output $\hat{y}$ for input $x$.

  2. Compute Loss: $$\displaystyle L = \text{Loss}(y, \hat{y}) $$ (e.g., MSE, cross-entropy).

  3. Backward Pass:

     • Compute $$\displaystyle \frac{\partial L}{\partial \text{output layer weights}} $$ (using output error).

     • Propagate error backwards: $$\displaystyle \delta^{(l)} = ((W^{(l+1)})^T \delta^{(l+1)}) \odot f'(z^{(l)}) $$.

     • Compute gradient: $$\displaystyle \frac{\partial L}{\partial W^{(l)}} = \delta^{(l)} (a^{(l-1)})^T $$.

  4. Update Weights: $$\displaystyle W^{(l)} := W^{(l)} - \eta \frac{\partial L}{\partial W^{(l)}} $$ (with learning rate $\eta$).

• Example Calculation: For a single-layer network with sigmoid, given input, target, and initial weights, compute forward pass, error, then $\delta$ for output layer, and finally weight updates.

Optimization

• Gradient Descent (GD): Update parameters to minimize loss.

  • Batch GD: Use entire dataset to compute gradient. Stable but slow per update.

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

  • Mini-batch GD: Use a small random subset (mini-batch). Most common – balances speed and stability.

• Loss Functions:

  • Regression: Mean Squared Error (MSE) $$\displaystyle = \frac{1}{n}\sum (y-\hat{y})^2 $$.

  • Binary Classification: Binary Cross-Entropy (Log Loss) $$\displaystyle = -\frac{1}{n}\sum [y\log\hat{y} + (1-y)\log(1-\hat{y})] $$.

  • Multi-class: Categorical Cross-Entropy.

• Optimizers (improve upon basic GD):

  • SGD with Momentum: Adds velocity term to accelerate in consistent directions.

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

  • Adam (Adaptive Moment Estimation): Combines Momentum and RMSprop. Most popular – computes adaptive learning rates using estimates of first (mean) and second (uncentered variance) moments.

Regularization Techniques

• Goal: Prevent overfitting by adding a penalty to the loss function to discourage complex models.

• L1 Regularization (Lasso): Adds $$\displaystyle \lambda \sum |w_j| $$ to loss.

  • Impact: Drives some weights exactly to zero, performing feature selection. Produces sparse models.

• L2 Regularization (Ridge): Adds $$\displaystyle \lambda \sum w_j^2 $$ to loss.

  • Impact: Shrinks all weights towards zero smoothly but rarely to zero. Prevents any single weight from becoming too large.

• Other Techniques:

  • Dropout: Randomly "drop" (set to zero) a fraction of neurons during training. Forces network to learn redundant representations.

  • Early Stopping: Monitor validation loss; stop training when it starts increasing.

  • Batch Normalization: Normalizes layer inputs to have zero mean and unit variance. Stabilizes and accelerates training, has slight regularization effect.

Batch Normalization

• Operation: For a mini-batch, normalize activations of a layer: $$\displaystyle x_{norm} = \frac{x - \mu_B}{\sqrt{\sigma_B^2 + \epsilon}} $$, then scale and shift: $$\displaystyle y = \gamma x_{norm} + \beta $$.

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

Data Augmentation

• Technique: Artificially increase training data size by applying label-preserving transformations to existing data.

• Examples: Images (rotation, flipping, cropping, color jittering), Text (synonym replacement, back-translation), Audio (noise injection, pitch shift).

• Purpose: Reduces overfitting, improves model generalization by exposing it to more variations.

B. Convolutional Neural Networks (CNN)

Architecture and Operations

• Typical Layers:

  1. Convolutional (CONV): Applies filters/kernels to extract local features (edges, textures). Output depth = number of filters.

  2. Pooling (Sub-sampling): Downscales spatial dimensions (width, height). Max Pooling (most common) takes max value in window. Provides translation invariance, reduces computation.

  3. Fully Connected (FC): At the end, for classification/regression.

• Why Downscale Images & Increase Filters?

  • Downscaling (Pooling/Stride >1): Reduces spatial size, decreases parameters/computation, increases receptive field (subsequent layers see larger image regions).

  • Increase Filters (Depth): As spatial size decreases, we can afford more filters to learn more complex, abstract features (from edges to patterns to objects).

• Flattening: Operation before FC layers. Converts the 3D feature maps (width × height × depth) into a 1D vector.

Convolutional Techniques

• 1x1 Convolutions:

  • Purpose: 1) Feature reduction/channel mixing: Apply across depth dimension to combine channels, reduce or increase depth without spatial change. 2) Introduce non-linearity. 3) Used in architectures like Inception and ResNet for bottleneck layers.

• 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). Padding = $(F-1)/2$. Preserves spatial information at boundaries.

• Sub-sampling (Pooling): Reduces spatial dimensions, provides translation invariance (small shifts don't change output), and increases the field of view for subsequent layers.

Advanced Architectures

• Inception Module (GoogLeNet):

  • Structure: Parallel convolutions with different filter sizes (1x1, 3x3, 5x5) and a max-pooling branch, all concatenated.

  • Efficiency Benefit: 1x1 convolutions are used as bottlenecks before expensive 3x3/5x5 convs to reduce depth, drastically cutting computation. Allows multi-scale feature capture in one block.

• Transfer Learning:

  • Feature Extraction: Use pre-trained CNN (e.g., VGG16) as fixed feature extractor. Remove top FC layers, add new classifier on top. Freeze pre-trained layers.

  • Fine-Tuning: Unfreeze some top layers of pre-trained network and continue training with new data (small learning rate). Adapts higher-level features to new task.

  • Rationale: Leverages knowledge (features) learned on large datasets (ImageNet) for new, smaller datasets.

C. Recurrent Neural Networks (RNN)

Architecture and Types

• Vanilla RNN:

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

  • Issue: Suffers from vanishing/exploding gradients with long sequences, struggles with long-term dependencies.

• LSTM (Long Short-Term Memory):

  • Architecture: Has cell state $$\displaystyle C_t $$ (the "memory highway") and three gates: Forget Gate (what to drop from cell), Input Gate (what new info to store), Output Gate (what to output from cell).

  • Advantage: Gates allow controlled information flow, mitigating vanishing gradient, and explicitly modeling long-term dependencies.

• GRU (Gated Recurrent Unit):

  • Simplified LSTM: Combines forget and input gates into a single update gate ($$\displaystyle z_t $$). Has a reset gate ($$\displaystyle r_t $$). Fewer parameters than LSTM, often similar performance.

• Differences: Vanilla RNN < LSTM ≈ GRU in ability to handle long sequences. LSTM more expressive, GRU more efficient.

Handling Sequential Data & Long-Term Dependencies

• Role in NLP/Time-Series: Process sequences of variable length (words, time steps). Maintain state that summarizes past information.

• Long-Term Dependencies: LSTM/GRU gates allow gradients to flow unchanged through the cell state over many time steps, enabling learning of relationships between distant elements (e.g., subject-verb agreement across long sentences).

• ChatGPT (Transformer-based): While ChatGPT uses Transformers (not RNNs), RNNs/LSTMs were foundational for sequential modeling. Transformers use self-attention to handle long-range dependencies more effectively without recurrence.

D. Specialized Architectures

• Autoencoders:

  • Goal: Unsupervised learning for dimensionality reduction or feature learning. Learn efficient data encoding.

  • Architecture: Encoder (compresses input to latent code), Decoder (reconstructs input from code). Trained to minimize reconstruction loss (e.g., MSE).

  • Types: Denoising AE (robust features), Variational AE (VAE - generative).

• Attention Models (Brief):

  • Core Idea: Allow model to "focus" on different parts of the input sequence when producing each part of the output. Computes a weighted sum of values, where weights (attention scores) are learned.

  • Significance: Key component of Transformers, enabling parallel processing and superior handling of long-range dependencies in NLP (e.g., BERT, GPT).

VI. REINFORCEMENT LEARNING (RL)

A. Fundamentals

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

  • States (S): Set of all possible environment states.

  • Actions (A): Set of all possible actions.

  • Transition Probability $P(s'|s,a)$: Probability of reaching state $s'$ from $s$ taking action $a$.

  • Reward $R(s,a,s')$: Immediate scalar feedback.

  • Discount Factor $\gamma \in [0,1]$: Values future rewards less than immediate ones.

• Markov Property: Future state depends only on current state and action, not on the sequence of events that preceded it. $P(s'|s,a)$ captures this.

• Policy ($\pi$): Strategy of the agent. Mapping from states to actions: $\pi(a|s)$ (stochastic) or $$\displaystyle a = \pi(s) $$ (deterministic).

• Value Functions:

  • State-Value $$\displaystyle V^\pi(s) $$: Expected discounted return starting from state $s$ and following policy $\pi$.

  • Action-Value $$\displaystyle Q^\pi(s,a) $$: Expected discounted return starting from state $s$, taking action $a$, then following $\pi$.

  • Optimal Value Functions ($$\displaystyle V^*, Q^* $$): Maximum possible value over all policies.

B. Solution Methods

• Value Iteration vs. Policy Iteration:

  | Aspect | Value Iteration | Policy Iteration | | :--- | :--- | :--- | | Steps | 1. Update $V(s)$ using Bellman optimality eq. (no explicit policy). 2. Extract greedy policy at end. | 1. Policy Evaluation: Compute $$\displaystyle V^\pi $$ for current $\pi$. 2. Policy Improvement: Make $\pi$ greedy w.r.t. $$\displaystyle V^\pi $$. Repeat. | | Convergence | Often faster per iteration (no full policy eval). | Can be slower due to full policy evaluation, but often fewer iterations to optimal policy. |

• Q-Learning (Off-Policy):

  • Q-value: $Q(s,a)$ estimates the value of taking action $a$ in state $s$.

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

  • Key: Uses $$\displaystyle \max_{a'} Q(s',a') $$ – learns optimal policy independently of the agent's current (exploratory) policy. Off-policy.

  • Algorithm (Deterministic Rewards/Actions): Initialize Q arbitrarily. For each episode: start in s, choose a (e.g., $\epsilon$-greedy), execute a, observe r, s', update Q. Repeat until terminal.

• SARSA (On-Policy):

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

  • Key: Uses the actual next action $a'$ taken by the current policy. Learns the value of the policy being followed. On-policy.

  • Difference from Q-Learning: SARSA's update uses $Q(s',a')$ (actual next action), Q-Learning uses $$\displaystyle \max_{a'} Q(s',a') $$ (greedy next action). SARSA is more conservative, considers exploration.

• Actor-Critic Models:

  • Basic Architecture:

    • Actor: Policy function $\pi(a|s)$. Outputs actions.

    • Critic: Value function $V(s)$ or $Q(s,a)$. Evaluates actions taken by actor.

  • Interaction: Actor proposes action based on policy. Critic evaluates state (or state-action) and computes TD Error $$\displaystyle \delta = r + \gamma V(s') - V(s) $$. This error is used to:

    1. Update Critic (reduce TD error).

    2. Update Actor (policy gradient: increase prob. of actions that led to positive $\delta$).

  • Advanced Models (A2C, A3C, PPO): More stable and sample-efficient variants. PPO (Proximal Policy Optimization) is state-of-the-art, using clipped objective to prevent large policy updates.

[!TIP] Exam Focus: Crucial to contrast Q-Learning (off-policy, max) vs. SARSA (on-policy, actual). Understand Actor (action) and Critic (evaluation) roles.

C. Frameworks & Applications

• Frameworks:

  • OpenAI Gym / Gymnasium: Standard API for RL environments (Atari, robotics simulators).

  • TensorFlow Agents (TF-Agents): Flexible library for RL using TensorFlow.

  • Stable-Baselines3: High-quality implementations of common algorithms (PPO, SAC, etc.) based on PyTorch.

• Example Applications:

  • Games: AlphaGo (Go), DQN (Atari), ChatGPT training (RLHF).

  • Robotics: Control, locomotion, manipulation.

  • Resource Management: Data center cooling, inventory control.

  • Finance: Trading, portfolio optimization.

VII. ADVANCED & EMERGING TOPICS

One-Shot Learning

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

• vs. Traditional Supervised Learning: Requires massive labeled datasets (thousands/millions per class).

• How it works: Uses prior knowledge (e.g., from a large base dataset) or special architectures (Siamese networks, metric learning, memory-augmented networks) to generalize from few examples.

• Applications: Facial recognition (new person from 1 photo), rare species identification, new product classification.

Self-Supervised Learning

• Paradigm: Automatically generate supervision signals from the unlabeled data itself. Pretext task is designed so that solving it forces the model to learn useful representations.

  • Examples: Predicting missing image patches (MAE), next word prediction (BERT's masked LM), contrastive learning (SimCLR).

• Benefits: Reduces need for expensive human labeling. Learns robust, general-purpose features that transfer well to downstream tasks.

Generative AI

• Models & Applications:

  • Generative Adversarial Networks (GANs): Generator creates fake data, Discriminator tries to distinguish real vs fake. Used for image synthesis, style transfer.

  • Variational Autoencoders (VAEs): Learn latent distribution, can generate new samples. Used for image/audio generation.

  • Autoregressive Models (GPT, PixelRNN): Generate sequences by predicting next token/pixel. Powers ChatGPT, DALL-E 2 (image gen).

  • Diffusion Models: State-of-the-art for image/speech generation (Stable Diffusion, Midjourney). Gradually denoise data from random noise.

  • Applications: Text/Image/Audio generation, drug discovery, data augmentation, creative design.

Bayesian Belief Networks (BBNs)

• Construction:

  • Nodes: Represent random variables (discrete/continuous).

  • Edges: Direct probabilistic dependencies (causal or correlational). No cycles (DAG).

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

• Joint Probability: Factorizes according to DAG structure.

$$P(X_1, ..., X_n) = \prod_{i=1}^{n} P(X_i | \text{Parents}(X_i))$$

• Example Inference (Car Value):

  • Given network structure (e.g., Mileage → Engine → Car Value, AirConditioner → Car Value).

  • To compute $$\displaystyle P(\text{Car Value} = \text{High} | \text{Mileage}=\text{Lo}, \text{Engine}=\text{Bad}, \text{AirConditioner}=\text{Broken}) $$:

    1. Use CPTs to get probabilities for each parent configuration.

    2. Apply Bayes' rule or use inference algorithms (exact: variable elimination; approximate: MCMC).

Convex Optimization

• Role in ML: Many ML problems (linear regression with L2, SVM, logistic regression) can be formulated as convex optimization problems.

• Why Convex? A convex loss function has a single global minimum and no local minima. Gradient descent is guaranteed to converge to the global optimum (given appropriate step size).

• Key Property: For function $f$, $$\displaystyle f(\theta) \geq f(\theta_0) + \nabla f(\theta_0)^T (\theta - \theta_0) $$ for all $$\displaystyle \theta, \theta_0 $$. This ensures any local minimum is global.

VIII. APPLICATIONS OF MACHINE LEARNING

Speech Processing

• Speech-to-Text (Automatic Speech Recognition - ASR):

  • Pipeline: Audio → Feature extraction (MFCCs) → Acoustic Model (often DNN/RNN/Transformer) → Language Model → Text.

  • Models: Deep learning models (CTC loss with RNNs/Transformers, end-to-end models like Wav2Vec 2.0).

• Speaker Identification/Verification: Extract speaker embeddings (e.g., using x-vector system) from speech, compare to enrolled models.

• Speech Synthesis (Text-to-Speech - TTS):

  • Pipeline: Text → Linguistic features → Acoustic features → Waveform generation.

  • Models: Tacotron 2 (seq2seq with attention), WaveNet (autoregressive raw audio), VITS (variational inference with GAN).

Computer Vision

• Image Recognition: Classifying entire image. ImageNet Competition (ILSVRC) history: 2012 AlexNet (deep CNN, ReLU, GPU) revolutionized field, drastically reducing top-5 error.

• Object Detection: Locate and classify multiple objects. Models: R-CNN family (two-stage), YOLO/SSD (single-stage).

• Applications:

  • Bioinformatics: Cell image analysis, protein structure prediction (AlphaFold).

  • Medical Imaging: Tumor detection (X-ray, MRI), diagnosis assistance.

Natural Language Processing (NLP)

• Steps in NLP Pipeline:

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

  2. Feature Extraction: Bag-of-Words, TF-IDF, Word Embeddings (Word2Vec, GloVe), Contextual Embeddings (BERT, GPT).

  3. Modeling: Task-specific architecture (classification, seq2seq, etc.).

• Applications:

  • Machine Translation: Seq2seq with attention, Transformers.

  • Sentiment Analysis: Classify text polarity (positive/negative).

  • Named Entity Recognition (NER): Identify entities (person, location).

  • Chatbots & Dialogue Systems: Using large language models (LLMs).

• BLEU Score: Primary metric for machine translation. Computes n-gram precision (modified to avoid overcounting) and applies brevity penalty for overly short translations.

IX. MISCELLANEOUS TOPICS

Linearity vs. Non-linearity

• Linear Models: Logistic regression (linear decision boundary), Linear Regression. Decision boundary is a hyperplane. Gradient Descent: Loss surface is convex → guaranteed global optimum. Simple, interpretable.

• Non-linear Models: Neural Networks with non-linear activations, SVM with kernel trick, Decision Trees. Can model complex relationships. Gradient Descent: Non-convex loss surface → many local minima, saddle points. Requires careful initialization, learning rate scheduling.

• Making Model Non-linear: Add non-linear activation functions (ReLU, sigmoid) in neural networks, or use polynomial features/kernels.

Perceptron Learning Algorithm

• Unit: Simple neuron. $$\displaystyle y = f(\sum_{i} w_i x_i + b) $$, where $f$ is step function.

• Weight Adjustment: For misclassified example $(x, y)$:

  $$\displaystyle w_i \leftarrow w_i + \Delta w_i = w_i + \eta (y - \hat{y}) x_i $$

  $$\displaystyle b \leftarrow b + \eta (y - \hat{y}) $$

  Where $\eta$ is learning rate, $y \in \{-1,1\}$ or $\{0,1\}$.

• Guarantee: Converges to a separating hyperplane if data is linearly separable. Otherwise, does not converge.

Gaussian Mixture Density Estimation

• Goal: Estimate the underlying probability distribution of data as a mixture of Gaussians.

• Model: $$\displaystyle p(x) = \sum_{k=1}^{K} \pi_k \mathcal{N}(x|\mu_k, \Sigma_k) $$.

• Parameters: Mixing coefficients $$\displaystyle \pi_k $$ (sum to 1), means $$\displaystyle \mu_k $$, covariances $$\displaystyle \Sigma_k $$.

• Estimation: Typically done via Expectation-Maximization (EM) algorithm (as in GMM clustering). E-step: compute responsibilities. M-step: update parameters.

Frequent Pattern Mining (Market Basket Analysis)

• Goal: Find itemsets that appear together frequently in transaction databases.

• Key Measures:

  • Support: $P(\text{itemset})$. Fraction of transactions containing itemset.

  • Confidence: $$\displaystyle P(B|A) = \frac{\text{support}(A \cup B)}{\text{support}(A)} $$. Strength of implication rule $$\displaystyle A \rightarrow B $$.

  • Lift: $$\displaystyle \frac{\text{confidence}(A \rightarrow B)}{\text{support}(B)} $$. >1 indicates positive correlation.

• Algorithm: Apriori (candidate generation & pruning) or FP-Growth (FP-tree).

Factors Affecting ML Performance

1. Data Quality & Quantity: Noise, missing values, label errors, insufficient data.

2. Feature Engineering: Relevance, informativeness, representation.

3. Model Selection & Complexity: Bias-variance tradeoff.

4. Hyperparameters: Learning rate, regularization strength, network depth.

5. Training Procedure: Optimization algorithm, early stopping, data shuffling.

6. Evaluation Metric: Choice must align with business objective.

Steps in Designing ML Experiments

1. Define Problem & Metric: What to predict? How to measure success?

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

3. Model Selection: Choose candidate algorithms based on problem type, data size, interpretability needs.

4. Training & Hyperparameter Tuning: Train models, use validation set & techniques (Grid/Random Search, CV) for tuning.

5. Evaluation & Comparison: Assess final models on held-out test set using chosen metric. Statistical tests if needed.

6. Deployment & Monitoring: Deploy best model, monitor performance over time (concept drift).

Measuring Classifier Performance (Comprehensive)

• From Confusion Matrix (TP, TN, FP, FN):

  • Accuracy, Precision, Recall (Sensitivity), Specificity ($TN/(TN+FP)$), F1-Score.

  • ROC Curve & AUC: Plot TPR (Recall) vs. FPR at various thresholds. AUC = probability model ranks a random positive higher than random negative.

  • Precision-Recall Curve: Especially useful for imbalanced datasets.

• Imbalanced Data Metrics:

  • Matthews Correlation Coefficient (MCC): Balanced measure for binary classification.

  • Cohen's Kappa: Measures agreement corrected for chance.

• Multi-class: Macro/Micro/Weighted averages of Precision, Recall, F1.

\boxed{\text{Always use a held-out test set for final evaluation. Use CV for model selection/tuning.}}