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

I. Introduction and Foundations

Definition and Importance

Machine Learning (ML) is a subset of artificial intelligence that enables systems to learn patterns from data without explicit programming. It is crucial for automating decision-making, handling large-scale data, and adapting to new scenarios—applications include healthcare diagnostics, financial forecasting, and recommendation systems.

Types of Machine Learning

• Supervised Learning: Uses labeled data (input-output pairs).

  Examples: Classification (spam detection), Regression (price prediction).

• Unsupervised Learning: Finds hidden patterns in unlabeled data.

  Examples: Clustering (customer segmentation), Dimensionality Reduction (PCA).

• Reinforcement Learning: Agent learns via rewards/penalties from environment interactions.

  Examples: Game playing (AlphaGo), robotics control.

Perspectives and Issues

• Design Perspectives: What to learn? How to represent data? How to evaluate?

• Key Issues: Data quality (noise, missing values), overfitting/underfitting, model interpretability, computational cost, ethical concerns (bias, privacy).

Hypothesis Space and Inductive Bias

• Hypothesis Space: Set of all possible models considered during learning.

  • Finite: Limited models (e.g., decision trees with max depth). Lower risk of overfitting but may underfit if too restrictive.

  • Infinite: Unbounded models (e.g., neural networks with unlimited parameters). High capacity, prone to overfitting without regularization.

• Inductive Bias: Assumptions that guide learning toward specific solutions (e.g., smoothness, Occam’s razor). Essential for generalization from finite data.

Basic Statistical Concepts

• Probability distributions, Bayes’ theorem, mean, variance, covariance.

• Central to probabilistic models (e.g., Naive Bayes, GMM) and uncertainty estimation.

[!TIP]

Exam Focus: Distinguish supervised/unsupervised/reinforcement learning with examples. Compare finite vs infinite hypothesis spaces—finite spaces limit complexity but may underfit; infinite spaces need regularization to generalize.

II. Data Preprocessing and Evaluation

Data Preprocessing Techniques

• Normalization: Scale features to a fixed range (e.g., min-max to [0,1]).

• Standardization: Transform to zero mean, unit variance (z-score).

  Why needed? Ensures gradient descent convergence, prevents features with larger scales from dominating (critical for k-NN, SVM, neural networks).

• Categorical Encoding:

  • One-hot: Creates binary columns per category → increases dimensionality.

  • Label: Assigns integer per category → may imply false ordinality.

  Impact: One-hot avoids ordinal assumptions but causes curse of dimensionality; label encoding is compact but risky for nominal data.

Evaluation Metrics

• Regression:

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

  • MAE = $$\displaystyle \frac{1}{n}\sum_{i=1}^{n}|y_i - \hat{y}_i| $$ (robust).

  • R-squared = $$\displaystyle 1 - \frac{SSE}{SST} $$ (proportion of variance explained).

• Classification:

  • Confusion Matrix:

    | | Predicted + | Predicted - | |---|---|---| | Actual + | TP | FN | | Actual - | FP | TN |

  • Accuracy = $$\displaystyle \frac{TP+TN}{Total} $$.

  • 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}} $$ (harmonic mean).

• NLP (BLEU Score):

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

  • Brevity Penalty (BP): $$\displaystyle BP = \begin{cases} 1 & \text{if } c > r \\ e^{(1-r/c)} & \text{otherwise} \end{cases} $$ where $c$ = candidate length, $r$ = reference length.

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

Model Validation and Selection

• Training vs Testing: Train on training set, evaluate on unseen test set to estimate generalization.

• Cross-Validation:

  • k-fold: Split data into $k$ folds, train on $k-1$, test on 1, repeat.

  • Leave-One-Out (LOO): $$\displaystyle k = n $$ (high variance, computationally heavy).

• Overfitting vs Underfitting:

  • Overfitting: Low training error, high test error → high variance.

    Solutions: More data, regularization (L1/L2), dropout, pruning.

  • Underfitting: High training error → high bias.

    Solutions: More features, complex model, reduce regularization.

• Hyperparameter Tuning: Grid search, random search, Bayesian optimization.

• Resampling Methods:

  • Bootstrap: Sample with replacement, estimate model stability/variance.

  • Jackknife: Leave-one-out, estimate bias.

[!TIP]

Exam Focus: Know formulas for MSE, MAE, R², Accuracy, Precision, Recall, F1, BLEU. Understand when to use one-hot vs label encoding. Overfitting detection: gap between train/test performance; solutions include cross-validation and regularization.

III. Supervised Learning Algorithms

Linear Regression and Logistic Regression

Decision Trees

• Entropy: $$\displaystyle H(S) = -\sum_{i=1}^{c} p_i \log_2 p_i $$ (impurity measure).

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

• ID3 Algorithm:

  1. Start with full dataset at root.

  2. Select attribute with highest IG.

  3. Split on attribute values, create child nodes.

  4. Recurse on subsets until all instances belong to same class or no attributes left.

• Issues: Overfitting (prune with reduced-error or cost-complexity), bias toward multi-valued attributes, instability (small data changes alter tree).

Support Vector Machines (SVM)

• Optimal Hyperplane: $$\displaystyle w \cdot x + b = 0 $$ that maximizes margin = $$\displaystyle \frac{2}{\|w\|} $$.

• Support Vectors: Training points lying on margin boundaries ($$\displaystyle y_i(w \cdot x_i + b) = 1 $$).

• Linear SVM for Linearly Separable Data: Solve convex QP:

  Minimize $$\displaystyle \frac{1}{2}\|w\|^2 $$ subject to $$\displaystyle y_i(w \cdot x_i + b) \geq 1 $$.

  Dual form uses Lagrange multipliers $$\displaystyle \alpha_i $$; only support vectors have $$\displaystyle \alpha_i > 0 $$.

• High-Dimensional Spaces: Kernel trick (e.g., RBF $$\displaystyle K(x_i, x_j) = e^{-\gamma \|x_i - x_j\|^2} $$) implicitly maps to higher dimensions; effective in bioinformatics (gene classification) and image recognition (face detection).

• Margin: Distance between hyperplane and nearest points; larger margin → better generalization.

k-Nearest Neighbors (k-NN)

• Algorithm:

  1. Store all training data.

  2. For a query point, compute distances (usually Euclidean: $$\displaystyle d(x_i, x_j) = \sqrt{\sum (x_i^k - x_j^k)^2} $$).

  3. Find $k$ nearest neighbors.

  4. Predict majority class (classification) or average (regression).

• Example Prediction: Given training data with features (speed, agility), for new point (6.75, 3), compute Euclidean distance to all points, pick $$\displaystyle k=3 $$ nearest, take majority vote for class.

Naive Bayes Classifier

• Bayes’ Theorem: $$\displaystyle P(C|X) = \frac{P(X|C) P(C)}{P(X)} $$.

• Assumptions: Features conditionally independent given class: $$\displaystyle P(X|C) = \prod_{i} P(x_i|C) $$.

• Simplification: Compute $P(C)$ and $$\displaystyle P(x_i|C) $$ from training (e.g., Gaussian for continuous, multinomial for discrete). Predict $$\displaystyle \hat{C} = \arg\max_C P(C) \prod_i P(x_i|C) $$.

• Application: Text classification (spam filtering), medical diagnosis.

Ensemble Methods

• Bagging (Bootstrap Aggregating):

  • Train multiple models on bootstrap samples.

  • Combine by voting (classification) or averaging (regression).

  • Reduces variance (e.g., Random Forest: bagging + feature subset at each split).

• Boosting:

  • Train sequentially; each model focuses on errors of previous.

  • Reduces bias (e.g., AdaBoost, Gradient Boosting).

• Stacking:

  • Train base learners (e.g., SVM, decision tree).

  • Use their predictions as features for a meta-learner (e.g., linear regression).

  • Combines strengths, often yields best performance.

• Model Combination Schemes: Voting, averaging, weighted averaging, stacking.

[!TIP]

Exam Focus: Derive SVM margin formula; compare L1/L2 regularization (L1 sparsity, L2 small weights). Know ID3 steps with entropy/IG. For k-NN, practice distance calculation. Ensemble: bagging reduces variance, boosting reduces bias; stacking uses meta-learners.

IV. Unsupervised Learning Algorithms

Clustering

• k-Means:

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

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

  3. Update centroids as mean of assigned points.

  4. Repeat until convergence.

  Example: Given data and initial centroids $$\displaystyle m_1=2, m_2=4 $$, compute distances, assign, update.

• Hierarchical Clustering:

  • AGNES (Agglomerative): Bottom-up; start with each point as cluster, merge closest pairs (using single/complete/average linkage).

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

• Expectation-Maximization (EM):

  • E-step: Compute responsibilities $$\displaystyle \gamma(z_{nk}) = P(z_k = 1 | x_n, \theta) $$ for latent variable $z$.

  • M-step: Update parameters $\theta$ to maximize expected complete-data log-likelihood.

  • Handles missing data by treating as latent variables; iterates until convergence.

• Gaussian Mixture Models (GMM):

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

  • Soft clustering via posterior probabilities $$\displaystyle P(z_k=1|x) $$.

  • Suitable for overlapping clusters (vs k-means hard assignment).

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

• Goals of Clustering: Discover natural groupings, summarize data, detect anomalies.

• Requirements: Scalability, ability to handle noise, insensitivity to order, support for various shapes.

Dimensionality Reduction

• Principal Component Analysis (PCA):

  1. Standardize data.

  2. Compute covariance matrix $\Sigma$.

  3. Eigen decomposition: $$\displaystyle \Sigma v = \lambda v $$; eigenvectors = principal components.

  4. Project data onto top $k$ eigenvectors (maximizing variance).

  Example: Reduce 2D to 1D by finding direction of max variance.

• Locally Linear Embedding (LLE):

  • Preserves local neighborhoods; assumes data lies on a manifold.

  • Prefer over PCA for nonlinear structures (e.g., Swiss roll).

• Partial Least Squares (PLS): Supervised; finds components maximizing covariance between features and response.

• Benefits: Reduce curse of dimensionality, noise removal, visualization, faster training.

Association Rule Mining

• Frequent Pattern Mining: Find itemsets with support $\geq$ min_support.

• Market Basket Analysis: Discover items frequently bought together (e.g., {beer} → {diapers}).

• k-Frequent Itemset Mining (Apriori):

  1. Generate candidate 1-itemsets, prune by support.

  2. Iteratively generate k-itemsets from (k-1)-itemsets, prune.

  3. Generate rules from frequent itemsets, prune by confidence.

[!TIP]

Exam Focus: Compare AGNES vs DIANA (bottom-up vs top-down). EM E-step/M-step for GMM. PCA steps: covariance, eigenvectors. When to use LLE (nonlinear manifolds). Apriori algorithm for association rules.

V. Neural Networks and Deep Learning

Basics of Artificial Neural Networks

• Perceptron:

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

  • Learning: If misclassified, update $$\displaystyle w \leftarrow w + \eta (y_{\text{true}} - y_{\text{pred}}) x $$.

  • Converges for linearly separable data.

• Multilayer Perceptron (MLP):

  • Input layer → one or more hidden layers (nonlinear activations) → output layer.

  • Universal approximation theorem: MLP with one hidden layer can approximate any continuous function.

• Biological Inspiration: Neurons with dendrites (inputs), soma (processing), axon (output); synaptic weights.

Activation Functions

• Vanishing Gradient Problem: Gradients shrink exponentially during backprop for deep nets with sigmoid/tanh → slow/blocked learning. ReLU mitigates but not fully solves.

• Nonlinear Pattern Learning: Without activation, network reduces to linear transformation regardless of layers.

Training Neural Networks

• Backpropagation:

  1. Forward pass: compute loss $\mathcal{L}$.

  2. Backward pass: compute $$\displaystyle \frac{\partial \mathcal{L}}{\partial w} $$ via chain rule.

  3. Update weights: $$\displaystyle w \leftarrow w - \eta \frac{\partial \mathcal{L}}{\partial w} $$.

• Gradient Descent Optimizers:

  • Batch: Use entire dataset per update (stable, slow).

  • Stochastic (SGD): One sample per update (noisy, fast).

  • Mini-batch: Compromise (common).

  • Advanced:

    • Adam: Adaptive learning rate, momentum (first/second moment estimates).

    • RMSprop: Adapts learning rate per parameter (divides by running average of squared gradients).

• Loss Functions:

  • Regression: MSE.

  • Binary Classification: Binary cross-entropy.

  • Multi-class: Categorical cross-entropy.

• Regularization:

  • L1 (Lasso): Add $$\displaystyle \lambda \sum |w_i| $$ to loss → sparsity (some weights exactly zero).

  • L2 (Ridge): Add $$\displaystyle \lambda \sum w_i^2 $$ → small weights, smooth.

  • Prevents overfitting by penalizing complexity.

Convolutional Neural Networks (CNN)

• Architecture:

  • Convolutional Layers: Apply filters (kernels) to extract local features (edges, textures).

  • Pooling/Subsampling: Max pooling (take max over region) → translation invariance, reduce spatial size.

  • Fully Connected (FC) Layers: At end, for classification/regression.

• Convolution Operations:

  • Standard: Filter slides over input, computes dot product.

  • 1×1 Convolution: No spatial context; used for feature reduction/increase (channel-wise), computational efficiency (e.g., Inception modules).

• Padding:

  • Same: Output size = input size (pad with zeros). Preserves spatial features at edges.

  • Valid: No padding; output shrinks.

• Subsampling: Pooling reduces spatial dimensions, increases receptive field, provides translation invariance.

• Flattening: Convert final feature maps to vector for FC layers.

• Inception Modules: Use multiple filter sizes (1×1, 3×3, 5×5) in parallel, concatenate outputs → capture multi-scale features efficiently.

• TensorFlow Implementation: tf.keras.layers.Conv2D(filters, kernel_size, padding='same'), MaxPool2D, Flatten, Dense.

Recurrent Neural Networks (RNN)

• Architecture:

  • Vanilla RNN: $$\displaystyle h_t = \tanh(W_{xh} x_t + W_{hh} h_{t-1} + b) $$. Shares weights across time steps.

  • LSTM: Adds cell state $$\displaystyle C_t $$ and gates (input, forget, output) → handles long-term dependencies.

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

• Differences from Feed-Forward: Cycles (hidden state depends on previous), variable-length sequences, temporal dynamics.

• Applications: NLP (translation, text generation), time series forecasting.

Autoencoders

• Architecture: Encoder (compress input to latent code $z$), Decoder (reconstruct $\hat{x}$ from $z$).

• Unsupervised Learning: Trained to minimize reconstruction loss (MSE).

• Uses: Dimensionality reduction, denoising, anomaly detection.

Attention Models (Brief)

• Compute weighted sum of inputs, weights learned via query-key-value mechanism.

• Enables focus on relevant parts (e.g., in transformers for machine translation).

[!TIP]

Exam Focus: Derive backpropagation steps for a simple MLP. Compare activation functions (ReLU vs sigmoid for vanishing gradient). CNN: purpose of 1×1 convolution (feature reduction), padding types (same vs valid). LSTM gates vs GRU. Autoencoders for unsupervised learning.

VI. Reinforcement Learning

Markov Decision Processes (MDP)

• Defined by $(S, A, P, R, \gamma)$:

  • $S$: states, $A$: actions.

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

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

  • $\gamma$: discount factor (future reward importance).

• Policy $\pi(a|s)$: strategy mapping states to actions.

• Goal: Maximize expected cumulative discounted reward $$\displaystyle G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} $$.

Q-Learning

• Q-value: $Q(s,a)$ = expected cumulative reward starting from $s$, taking $a$, then following optimal policy.

• Update Rule (deterministic rewards/actions):

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

• Algorithm:

  1. Initialize $Q(s,a)$ arbitrarily.

  2. For each episode:

     • Observe state $s$.

     • Choose action $a$ (e.g., $\epsilon$-greedy).

     • Execute $a$, observe $r, s'$.

     • Update $Q(s,a)$.

     • $$\displaystyle s \leftarrow s' $$.

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

SARSA vs Q-Learning

• SARSA: On-policy; update uses action actually taken:

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

where $a'$ is chosen by current policy (e.g., $\epsilon$-greedy).

• Difference: Q-learning uses $$\displaystyle \max_{a'} Q(s',a') $$ (greedy), SARSA uses $Q(s',a')$ (on-policy). SARSA is more conservative, considers exploration.

Actor-Critic Models

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

• Critic: Value network $$\displaystyle V_\phi(s) $$ or $$\displaystyle Q_\omega(s,a) $$ → evaluates actions.

• Interaction:

  1. Actor selects action $$\displaystyle a \sim \pi_\theta(\cdot|s) $$.

  2. Environment returns $r, s'$.

  3. Critic computes TD error $$\displaystyle \delta = r + \gamma V_\phi(s') - V_\phi(s) $$.

  4. Update critic to minimize $$\displaystyle \delta^2 $$.

  5. Update actor to increase probability of actions with positive advantage $$\displaystyle A(s,a) = Q(s,a) - V(s) $$.

• Advanced Examples: A2C (synchronous), A3C (asynchronous), PPO (proximal policy optimization).

Value Iteration vs Policy Iteration

• Value Iteration:

  • Iteratively update value function: $$\displaystyle V(s) \leftarrow \max_a \sum_{s'} P(s'|s,a)[R(s,a) + \gamma V(s')] $$.

  • Converges to optimal $$\displaystyle V^* $$, then derive policy $$\displaystyle \pi^*(s) = \arg\max_a \sum_{s'} P(s'|s,a)[R(s,a) + \gamma V^*(s')] $$.

• Policy Iteration:

  • Alternate:

    a. Policy Evaluation: Compute $$\displaystyle V^\pi $$ for current policy $\pi$ (solve linear system).

    b. Policy Improvement: Update $$\displaystyle \pi(s) = \arg\max_a \sum_{s'} P(s'|s,a)[R(s,a) + \gamma V^\pi(s')] $$.

  • Repeat until policy stable.

• Difference: Value iteration updates values directly; policy iteration evaluates and improves policy alternately (often faster convergence but costly evaluation step).

Applications and Frameworks

• OpenAI Gym: Standardized environments (Atari, robotics).

• TensorFlow Agents: RL library built on TensorFlow.

• Applications: Game playing (AlphaGo, DQN), robotic control, autonomous driving, recommendation systems.

[!TIP]

Exam Focus: Write Q-learning update equation; contrast SARSA (on-policy) vs Q-learning (off-policy). Describe actor-critic roles (actor selects, critic evaluates). Value iteration vs policy iteration steps. MDP components (S, A, P, R, γ).

VII. Advanced Topics and Applications

Transfer Learning

• Feature Extraction: Use pre-trained model (e.g., ResNet on ImageNet) as fixed feature extractor; train new classifier on top.

• Fine-tuning: Unfreeze some top layers of pre-trained model, train with low learning rate to adapt features.

• Benefits: Requires less task-specific data, faster convergence, better performance with small datasets.

One-Shot Learning

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

• Difference from Traditional: Traditional supervised learning needs hundreds/thousands of examples per class.

• Methods: Siamese networks (metric learning), memory-augmented neural networks (MANN), prototypical networks.

• Applications: Face recognition (new person from one photo), rare disease diagnosis, industrial defect detection with few samples.

Generative AI

• Generative Adversarial Networks (GANs):

  • Generator $G(z)$ creates fake data from noise $z$.

  • Discriminator $D(x)$ distinguishes real vs fake.

  • Adversarial training: $$\displaystyle \min_G \max_D V(D,G) = \mathbb{E}_{x\sim p_{\text{data}}}[\log D(x)] + \mathbb{E}_{z\sim p_z}[\log(1-D(G(z)))] $$.

• Variational Autoencoders (VAEs):

  • Encoder outputs distribution $q(z|x)$ (e.g., Gaussian parameters).

  • Sample $z \sim q(z|x)$, decode $p(x|z)$.

  • Maximize ELBO: $$\displaystyle \log p(x) \geq \mathbb{E}_{q(z|x)}[\log p(x|z)] - D_{KL}(q(z|x) \| p(z)) $$.

• Applications: Image synthesis (StyleGAN), data augmentation, drug discovery, art generation.

Self-Supervised Learning

• Idea: Create pretext tasks from unlabeled data (e.g., predict rotation angle, jigsaw puzzle, contrastive learning).

• Benefit: Learn rich representations without manual labels, reduces labeling cost.

Applications of Machine Learning

• Speech Processing:

  • Speech-to-Text (ASR): Convert audio to text using RNN/Transformer (e.g., DeepSpeech, Wav2Vec 2.0).

  • Speaker Identification/Synthesis: Extract speaker embeddings (x-vectors), generate speech (Tacotron, WaveNet).

• Natural Language Processing (NLP):

  • Steps: Tokenization, embedding (Word2Vec, GloVe), sequence modeling (RNN/LSTM/Transformer), task-specific heads.

  • ChatGPT: Based on GPT architecture (transformer decoder), fine-tuned with RLHF (Reinforcement Learning from Human Feedback).

  • Role of LSTMs: Early state-of-the-art for sequence modeling (machine translation, text generation) before transformers; handle long-term dependencies via gating.

• Computer Vision:

  • Tasks: Image classification, object detection, segmentation, face recognition.

  • ImageNet Competition: Large-scale dataset (14M images, 22K categories); ILSVRC drove deep learning breakthroughs (AlexNet 2012, ResNet, etc.).

Convex Optimization in Machine Learning

• Many ML loss functions (linear regression MSE, SVM primal) are convex → gradient descent finds global optimum.

• Importance: Guarantees convergence, theoretical foundation for optimization algorithms.

Parallel Processing in Neural Networks

• Data Parallelism: Split batch across multiple GPUs, compute gradients in parallel, aggregate.

• Model Parallelism: Split layers across devices (for very large models).

• Pipeline Parallelism: Split model into stages, process different micro-batches concurrently.

• Accelerates training, enables larger models.

[!TIP]

Exam Focus: Transfer learning types (feature extraction vs fine-tuning). One-shot learning definition and applications (rare events). GAN vs VAE differences (adversarial vs probabilistic). Self-supervised pretext tasks. ImageNet impact on deep learning. Convex optimization ensures global optimum for convex losses.

VIII. Probabilistic and Bayesian Methods

Bayesian Learning

• Bayes’ Theorem: $$\displaystyle P(\theta|D) = \frac{P(D|\theta) P(\theta)}{P(D)} $$.

  • Posterior $\propto$ Likelihood $\times$ Prior.

• Fundamental Role: Provides probabilistic framework for uncertainty, updates beliefs with evidence.

• Application in Classification: Naive Bayes computes $P(C|X)$; Bayesian networks model joint distributions.

Bayesian Networks (Belief Networks)

• Construction:

  • Nodes: Random variables.

  • Edges: Direct conditional dependencies (acyclic).

  • Conditional Probability Tables (CPTs): $$\displaystyle P(X_i | \text{Parents}(X_i)) $$ for each node.

• Joint Probability: Factorizes as $$\displaystyle P(X_1, ..., X_n) = \prod_{i=1}^{n} P(X_i | \text{Parents}(X_i)) $$.

• Inference: Compute posterior given evidence (exact: variable elimination, junction tree; approximate: MCMC).

• Example:

  • Car Value Network: Nodes: Mileage (M), Engine (E), AirConditioner (AC), CarValue (V). Edges: M→V, E→V, AC→V.

  • Malaria-Headache: $$\displaystyle P(M)=0.03 $$, $$\displaystyle P(H|M)=0.6 $$, $$\displaystyle P(H|\neg M)=0.2 $$. Joint table: $$\displaystyle P(M,H) = P(M)P(H|M) $$ etc.

  • Query: $$\displaystyle P(V|\text{Mileage=Lo, Engine=Bad, AC=Broken}) $$ via inference.

Naive Bayes Classifier (Detailed)

• Assumptions:

  1. Features conditionally independent given class: $$\displaystyle P(x_1, ..., x_n | C) = \prod_i P(x_i|C) $$.

  2. Equal importance (often unrealistic but works in practice).

• Simplification:

  $$\displaystyle P(C|X) \propto P(C) \prod_i P(x_i|C) $$.

  Compute $P(C)$ (class prior) and $$\displaystyle P(x_i|C) $$ (e.g., Gaussian for continuous, multinomial for discrete) from training.

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

• Limitations: Independence assumption often violated; zero-frequency problem (use Laplace smoothing).

Gaussian Mixture Density Estimation

• Model data as mixture of $K$ Gaussians: $$\displaystyle p(x) = \sum_{k=1}^{K} \pi_k \mathcal{N}(x | \mu_k, \Sigma_k) $$ with $$\displaystyle \sum \pi_k = 1 $$.

• EM Algorithm:

  • E-step: $$\displaystyle \gamma(z_{nk}) = \frac{\pi_k \mathcal{N}(x_n|\mu_k,\Sigma_k)}{\sum_j \pi_j \mathcal{N}(x_n|\mu_j,\Sigma_j)} $$.

  • M-step: Update $$\displaystyle \pi_k = \frac{1}{N}\sum_n \gamma(z_{nk}) $$, $$\displaystyle \mu_k = \frac{\sum_n \gamma(z_{nk}) x_n}{\sum_n \gamma(z_{nk})} $$, $$\displaystyle \Sigma_k = \frac{\sum_n \gamma(z_{nk}) (x_n - \mu_k)(x_n - \mu_k)^T}{\sum_n \gamma(z_{nk})} $$.

• Probabilistic Clustering: Soft assignments via posterior $$\displaystyle \gamma(z_{nk}) $$.

[!TIP]

Exam Focus: Write Bayes’ theorem and apply to classification (e.g., spam). Draw Bayesian network for car value or malaria-headache, compute joint probabilities. Naive Bayes independence assumption simplifies multiplication. GMM uses EM for soft clustering.

IX. Specialized Concepts and Techniques

Locally Weighted Linear Regression

• Non-parametric; fits linear model weighted by proximity to query point.

• Weight $$\displaystyle w_i = \exp\left(-\frac{(x_i - x)^2}{2\tau^2}\right) $$ (Gaussian kernel).

• Minimize weighted SSE: $$\displaystyle \sum_i w_i (y_i - w^T x_i)^2 $$.

• Captures local nonlinear trends; sensitive to bandwidth $\tau$.

Expectation-Maximization for Probabilistic Models

• General framework for models with latent variables.

• E-step: Compute expected sufficient statistics of latent variables given current parameters.

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

• Converges to local optimum; used in GMM, HMM, topic models.

Resampling Methods

• Bootstrap: Sample $n$ observations with replacement $B$ times; compute statistic on each sample → estimate standard error, confidence intervals.

• Jackknife: Leave-one-out; compute statistic on $n-1$ samples → estimate bias, standard error.

• Use: Model validation, uncertainty estimation when analytical solution hard.

Model Selection Criteria

• AIC (Akaike): $$\displaystyle AIC = 2k - 2\log(\mathcal{L}) $$ (penalizes complexity).

• BIC (Bayesian): $$\displaystyle BIC = k \log(n) - 2\log(\mathcal{L}) $$ (stronger penalty for large $n$).

• Choose model with lowest AIC/BIC.

Linearity vs Non-linearity

• Linearity: Model is linear in parameters (e.g., $$\displaystyle y = w^Tx + b $$).

  • Pros: Interpretable, convex optimization, less data needed.

  • Cons: Limited expressiveness, cannot capture complex patterns.

• Non-linearity: Model nonlinear in parameters (e.g., neural networks with activations).

  • Pros: Can approximate any function (universal approximation).

  • Cons: Risk overfitting, gradient descent may converge to local minima, requires more data/computation.

• Impact on Gradient Descent: Linear models have convex loss → global optimum; non-linear may have many local minima, need careful initialization, learning rate schedules.

Partial Least Squares (PLS)

• Supervised dimensionality reduction; finds components that maximize covariance between features $X$ and response $Y$.

• Steps:

  1. Compute weight vectors $w$ to maximize $\text{Cov}(Xw, Y)$.

  2. Extract scores $$\displaystyle t = Xw $$, $$\displaystyle u = Yc $$.

  3. Deflate $X$ and $Y$ (regress out $t$).

  4. Repeat.

• Useful when predictors are highly collinear and response is multivariate.

Self-Organizing Maps (SOM)

• Unsupervised neural network for dimensionality reduction and visualization.

• Competitive learning: neurons compete to represent input; winner and neighbors update weights.

• Preserves topological structure; maps high-dim data to 2D grid.

• Applications: clustering, visualization, feature extraction.

Batch Normalization

• Normalize layer inputs to zero mean, unit variance per mini-batch:

  $$\displaystyle \hat{x}^{(k)} = \frac{x^{(k)} - \mu_B}{\sqrt{\sigma_B^2 + \epsilon}} $$, then scale/shift: $$\displaystyle y^{(k)} = \gamma \hat{x}^{(k)} + \beta $$.

• Benefits: Stabilizes training, allows higher learning rates, acts as regularizer (reduces overfitting), reduces internal covariate shift.

Data Augmentation

• Artificially increase training data by applying transformations (rotation, flipping, cropping, color jitter, noise injection).

• Purpose: Improve generalization, reduce overfitting, especially in computer vision and NLP.

• Common in CNNs for image data.

[!TIP]

Exam Focus: Locally weighted regression (kernel weighting). EM steps (E: compute responsibilities, M: update parameters). Bootstrap vs jackknife. AIC vs BIC. Batch normalization steps and benefits. Data augmentation techniques for images.