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

UNIT 4: Machine Learning - Short Notes

I. 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 explicit programming. It's crucial for handling large-scale data, pattern recognition, and automating decision-making in domains like healthcare, finance, and autonomous systems.

Types of Machine Learning

Key Perspectives & Issues

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

• Interpretability: Complex models (e.g., deep learning) are often "black boxes."

• Scalability: Algorithm efficiency with large datasets.

• Data Quality: Garbage in, garbage out.

Hypothesis Space & Inductive Bias

• Hypothesis Space: Set of all possible models/algorithms considered.

• Inductive Bias: Assumptions made to generalize from training data (e.g., Occam's razor, smoothness).

Statistical Foundations

• Bayesian Learning: Uses Bayes' theorem to update hypothesis probability given evidence.

$$P(H|D) = \frac{P(D|H) P(H)}{P(D)}$$

• Probability Theory: Foundation for uncertainty modeling.

• Hypothesis Testing: Statistical significance of model performance.

AI vs. ML vs. Deep Learning

Data Science

• Definition: Interdisciplinary field using scientific methods to extract knowledge from data.

• Applications: Predictive analytics, recommendation systems, NLP, computer vision.

[!TIP] Exam often asks to compare AI/ML/DL and define ML with real-world examples. Use the table above for quick recall.

II. Data Preprocessing and Feature Engineering

Normalization & Standardization

• Normalization (Min-Max Scaling): Rescales features to [0,1].

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

• Standardization (Z-score): Transforms to mean=0, std=1.

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

• Why? Improves convergence, stability, and performance of distance-based algorithms (e.g., SVM, k-NN).

Encoding Categorical Variables

• One-Hot Encoding: Creates binary columns for each category. Increases dimensionality.

• Label Encoding: Assigns integer to each category. Can imply ordinal relationship (use cautiously).

Curse of Dimensionality

• High-dimensional data leads to sparsity, increased computation, and overfitting.

• Solutions: Dimensionality reduction, feature selection.

Dimensionality Reduction Techniques

1. Principal Component Analysis (PCA)

   • Linear transformation to orthogonal components maximizing variance.

   • Steps: Standardize data → Compute covariance matrix → Eigen decomposition → Select top k eigenvectors.

2. Partial Least Squares (PLS)

   • Supervised alternative to PCA; maximizes covariance between features and target.

3. Feature Selection Methods

   • Backward Elimination: Start with all features, iteratively remove least significant.

   • Filter (e.g., correlation), Wrapper (e.g., RFE), Embedded (e.g., L1 regularization).

Data Augmentation

• Artificially increases training data by applying transformations (e.g., rotation, flipping for images). Reduces overfitting.

[!TIP] PCA vs. PLS: PCA is unsupervised (maximizes feature variance); PLS is supervised (maximizes feature-target covariance).

III. Model Evaluation and Validation

Performance Metrics

Resampling Methods

• Cross-Validation: Splits data into k folds; rotates validation fold.

• Bootstrapping: Samples with replacement to estimate uncertainty.

Overfitting & Underfitting

• Overfitting: Model fits noise; high training accuracy, low test accuracy.

• Underfitting: Model too simple; low training/test accuracy.

• Remedies: Regularization, more data, simpler model, early stopping, dropout.

Hyperparameter Tuning

• Grid Search, Random Search, Bayesian Optimization.

• Use validation set or cross-validation to select best hyperparameters.

Designing ML Experiments

1. Define problem & metrics.

2. Collect & preprocess data.

3. Choose model & hyperparameters.

4. Train & validate (cross-validation).

5. Test on held-out set.

6. Analyze results & iterate.

[!TIP] Confusion Matrix derived metrics: Precision = TP/(TP+FP), Recall = TP/(TP+FN), F1 = 2*(Precision*Recall)/(Precision+Recall).

IV. Supervised Learning Algorithms

Regression

• Linear Regression: Models linear relationship.

$$y = \beta_0 + \beta_1 x_1 + ... + \beta_n x_n$$

Assumptions: Linearity, independence, homoscedasticity, normality of errors.

• Locally Weighted Linear Regression: Fits linear model weighted by proximity to query point.

Classification

1. Logistic Regression: Uses sigmoid to estimate probability.

$$P(y=1|x) = \frac{1}{1 + e^{-(\beta^T x)}}$$

2. Decision Trees

   • Splitting Criteria: Entropy (information gain), Gini impurity.

$$\text{Entropy}(S) = -\sum p_i \log_2 p_i$$

$$\text{Gini}(S) = 1 - \sum p_i^2$$

• Pruning: Reduce overfitting by removing branches (pre/post-pruning).

3. Support Vector Machines (SVM)

   • Optimal Hyperplane: Maximizes margin between classes.

$$\text{Margin} = \frac{2}{\|w\|}$$

• Support Vectors: Training points on margin boundaries.

• Kernel Trick: Maps data to higher dimension (e.g., RBF, polynomial) for non-linear separation.

• High-Dimensional Performance: Effective due to margin maximization; used in bioinformatics, text classification.

4. k-Nearest Neighbors (k-NN)

   • Non-parametric; classifies based on majority vote of k nearest neighbors (distance metric: Euclidean).

Ensemble Methods

• Bagging (Bootstrap Aggregating): Reduces variance (e.g., Random Forest).

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

• Random Forest: Multiple decision trees on bootstrapped samples; feature randomness.

• Stacking: Combines multiple models via meta-learner.

[!TIP] SVM kernel trick avoids explicit high-dimensional mapping; uses kernel function $$\displaystyle K(x_i, x_j) = \phi(x_i)^T \phi(x_j) $$.

V. Unsupervised Learning Algorithms

Clustering

1. k-Means

   • Algorithm: Initialize centroids → Assign points → Update centroids → Repeat.

   • Initialization: Random or k-means++.

   • Distance: Euclidean (default).

2. Expectation-Maximization (EM)

   • E-step: Estimate latent variables (e.g., cluster responsibilities).

   • M-step: Maximize likelihood to update parameters.

   • Handles Missing Data: Treats missing values as latent variables.

3. Hierarchical Clustering

   • DIANA (Divisive): Top-down splitting.

   • BIRCH: Efficient for large datasets; uses CF tree.

4. Clustering Goals: High intra-cluster similarity, low inter-cluster similarity. Requirements: Scalability, ability to handle noise, insensitivity to order.

Density Estimation

• Gaussian Mixture Models (GMM): Probabilistic model assuming data from mixture of Gaussians. Parameters estimated via EM.

[!TIP] k-Means vs. EM: k-Means is hard assignment; EM (GMM) is soft assignment with probabilistic clusters.

VI. Neural Networks and Deep Learning Fundamentals

Perceptron & MLP

• Perceptron: Single neuron; linear classifier.

• MLP: Multiple layers; universal approximator.

Activation Functions

Backpropagation

• Derivation: Chain rule to compute gradients.

• Steps:

  1. Forward pass: Compute output & loss.

  2. Backward pass: Compute $$\displaystyle \frac{\partial L}{\partial w} $$ layer by layer.

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

Gradient Descent & Optimizers

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

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

• Mini-batch GD: Compromise (common).

• Advanced:

  • Momentum: Accelerates with velocity $$\displaystyle v = \beta v + (1-\beta) \nabla L $$.

  • RMSprop: Adapts learning rate per parameter.

  • Adam: Combines momentum & RMSprop.

Loss Functions

• MSE: Regression.

• Cross-Entropy: Classification (binary: $-[y\log(p) + (1-y)\log(1-p)]$).

Batch Normalization

• Normalizes layer inputs (mean=0, var=1) during training. Reduces internal covariate shift, speeds up training.

Parallel Processing

• Neural networks leverage GPUs for matrix operations (e.g., convolution, matrix multiply) in parallel.

Architecture Representation

• Graphical: Nodes (neurons), edges (weights). Tabular: Layer-wise dimensions and connections.

[!TIP] Backpropagation is not an optimization algorithm—it's a gradient computation method; optimizers (e.g., Adam) update weights.

VII. Convolutional Neural Networks (CNNs)

Architecture

• Convolutional Layers: Extract features via filters.

• Pooling Layers: Downsample (max/average).

• Fully Connected Layers: Classification/regression.

Convolution Operation

• Filter (kernel) slides over input, computing dot product.

• Output size: $$\displaystyle O = \frac{W - K + 2P}{S} + 1 $$, where $W$=input width, $K$=kernel size, $P$=padding, $S$=stride.

Padding

• Same: Output size = input size ($$\displaystyle P = \frac{K-1}{2} $$).

• Valid: No padding ($$\displaystyle P=0 $$); output shrinks.

1×1 Convolutions

• Purpose: Feature reduction (channel-wise), increase non-linearity, reduce parameters.

• Example: Inception modules, network-in-network.

Subsampling (Pooling)

• Max Pooling: Takes maximum in window. Preserves dominant features.

• Average Pooling: Takes average. Smoothens features.

Advanced Architectures

• Inception Module: Parallel convolutions (1×1, 3×3, 5×5) + pooling; concatenated. Efficient multi-scale feature extraction.

• ResNet: Residual blocks with skip connections; solves vanishing gradient in deep nets.

• Transfer Learning: Pre-train on large dataset (e.g., ImageNet), fine-tune on target task.

CNN Implementation (TensorFlow)

model = Sequential([

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

    MaxPooling2D(pool_size=(2,2)),

    Flatten(),

    Dense(128, activation='relu'),

    Dense(10, activation='softmax')

])

Overfitting in CNNs & Solutions

• Dropout: Randomly deactivate neurons during training.

• Data Augmentation: Rotate, flip, crop images.

• Regularization: L2 weight decay.

• Early Stopping: Monitor validation loss.

[!TIP] 1×1 convolutions act as "feature transformers" across channels; they don't capture spatial info but reduce/increase depth.

VIII. Recurrent Neural Networks (RNNs) and Sequence Models

RNN Architecture

• Vanilla RNN: $$\displaystyle h_t = \tanh(W_{hh} h_{t-1} + W_{xh} x_t + b_h) $$.

  • Issues: Vanishing/exploding gradients, short-term memory.

• LSTM (Long Short-Term Memory):

  • Gates: Forget ($$\displaystyle f_t $$), Input ($$\displaystyle i_t $$), Output ($$\displaystyle o_t $$).

  • Cell State: $$\displaystyle c_t = f_t \odot c_{t-1} + i_t \odot \tilde{c}_t $$.

  • Handles long-term dependencies via gated flow.

• GRU (Gated Recurrent Unit):

  • Reset ($$\displaystyle r_t $$) & Update ($$\displaystyle z_t $$) gates.

  • Simpler than LSTM; fewer parameters.

Applications

• NLP: Machine translation, text generation.

• Speech Processing: Speech recognition, synthesis.

NLP Evaluation Metrics

• BLEU Score:

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

• $$\displaystyle p_n $$: n-gram precision.

• BP (Brevity Penalty): Penalizes overly short outputs.

$$\text{BP} = \begin{cases} 1 & \text{if } c > r \\ \exp(1 - r/c) & \text{otherwise} \end{cases}$$

($c$=candidate length, $r$=reference length).

[!TIP] LSTM vs. GRU: LSTM has separate cell state and hidden state (more parameters); GRU merges them (faster, often comparable performance).

IX. Regularization Techniques

L1 Regularization (Lasso)

• Adds $$\displaystyle \lambda \sum |w_i| $$ to loss.

• Effect: Drives some weights to zero → sparse model, feature selection.

L2 Regularization (Ridge)

• Adds $$\displaystyle \lambda \sum w_i^2 $$ to loss.

• Effect: Shrinks weights uniformly → reduces model complexity.

Dropout

• Randomly sets neuron outputs to zero during training (probability p).

• Prevents co-adaptation; acts like ensemble of sub-networks.

Early Stopping

• Stop training when validation performance degrades.

• Prevents overfitting by limiting training epochs.

[!TIP] L1 yields sparsity (good for feature selection); L2 does not (weights small but non-zero).

X. Reinforcement Learning

Basics

• Agent interacts with environment; learns policy to maximize cumulative reward.

• vs. Supervised: No labeled data; vs. Unsupervised: Reward signal vs. structure discovery.

Markov Decision Process (MDP)

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

  • $S$: States, $A$: Actions.

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

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

  • $\gamma$: Discount factor.

Value Iteration

• Iteratively updates value function until convergence:

$$V_{k+1}(s) = \max_a \sum_{s'} P(s'|s,a) [R(s,a,s') + \gamma V_k(s')]$$

Policy Iteration

• Alternates between policy evaluation and improvement:

  1. Evaluate $$\displaystyle V^\pi $$.

  2. Improve $\pi$ greedily: $$\displaystyle \pi'(s) = \arg\max_a \sum_{s'} P(s'|s,a)[R + \gamma V(s')] $$.

Q-Learning

• Off-policy TD learning. Learns action-value function $Q(s,a)$.

• Update Rule:

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

• Exploration-Exploitation: $\epsilon$-greedy (random action with prob $\epsilon$).

SARSA

• On-policy TD learning. Updates using current policy's action $a'$:

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

Actor-Critic Models

• Actor: Policy network (selects actions).

• Critic: Value network (evaluates actions).

• Interaction: Critic guides actor updates (e.g., A2C, A3C).

• Advanced: PPO, SAC (stable, sample-efficient).

Frameworks

• OpenAI Gym: Standardized environments.

• TensorFlow Agents: RL algorithms in TF.

Applications

• Robotics, game AI (AlphaGo), autonomous driving, resource management.

[!TIP] Q-learning vs. SARSA: Q-learning uses $$\displaystyle \max_{a'} Q(s',a') $$ (off-policy, optimistic); SARSA uses $Q(s',a')$ from current policy (on-policy, cautious).

XI. Advanced Topics and Applications

Autoencoders

• Architecture: Encoder (compress) → Latent space → Decoder (reconstruct).

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

• Applications: Dimensionality reduction, anomaly detection, denoising.

Generative AI

• GANs (Generative Adversarial Networks):

  • Generator (creates fake data) vs. Discriminator (distinguishes real/fake).

  • Minmax game: $$\displaystyle \min_G \max_D V(D,G) = \mathbb{E}[\log D(x)] + \mathbb{E}[\log(1-D(G(z)))] $$.

• Diffusion Models: Gradually add noise to data, then learn to reverse process.

• Applications: Image synthesis, data augmentation.

Self-Supervised Learning

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

• Reduces need for labeled data.

One-Shot Learning

• Learns from very few examples (often 1 per class).

• vs. Traditional: Traditional needs many examples; one-shot uses prior knowledge/metric learning (e.g., Siamese networks).

• Applications: Rare disease diagnosis, facial recognition.

Attention Mechanisms & Transformers

• Attention: Weighted sum of values based on query-key similarity.

$$\text{Attention}(Q,K,V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V$$

• Transformers: Stacked self-attention + feed-forward layers. No recurrence.

• Applications: BERT, GPT (ChatGPT), machine translation.

Applications

• Speech Processing:

  • Speech-to-Text: ASR (e.g., DeepSpeech, Wav2Vec).

  • Speaker Identification: x-vector systems.

• Computer Vision:

  • ImageNet Competition: Drove CNN advances (AlexNet, ResNet).

  • Object Detection: YOLO, Faster R-CNN.

  • Image Recognition: Classification, segmentation.

• Natural Language Processing:

  • Steps: Tokenization → Embedding → Model (RNN/Transformer) → Output.

  • Models: ChatGPT (GPT architecture), BERT (encoder-only).

[!TIP] Transformers use positional encoding (since no recurrence) and multi-head attention to capture different relationship types.

XII. Specialized Concepts

Bayesian Theorem & Probabilistic Models

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

• Naive Bayes: Assumes feature independence; $$\displaystyle P(y|x) \propto P(y) \prod P(x_i|y) $$.

• Bayesian Networks: Directed acyclic graph representing conditional dependencies.

Convex Optimization in ML

• Many ML problems (e.g., linear regression with L2) are convex → global optimum guaranteed.

• Gradient descent converges to global minimum if loss is convex.

Linearity vs. Non-linearity

• Linear Models: Decision boundary is hyperplane (e.g., linear regression, logistic regression without feature transformation).

• Non-linear Models: Capture complex patterns (e.g., SVM with kernel, neural networks).

• Impact on Gradient Descent: Non-linear models have non-convex loss → multiple local minima; careful initialization needed.

Flattening in CNNs

• Converts multi-dimensional feature maps (e.g., from conv/pool layers) into 1D vector for fully connected layers.

• Example: After last pooling, output $H \times W \times C$ → flatten to $HWC$-dim vector.

Factors Influencing ML Performance

1. Data Quality: Size, noise, representativeness.

2. Feature Engineering: Relevance, scaling.

3. Model Selection: Complexity vs. data.

4. Hyperparameters: Learning rate, regularization strength.

5. Algorithm Suitability: Match problem type (classification/regression).

6. Computational Resources: Memory, GPU availability.

[!TIP] Convex optimization ensures gradient descent finds global optimum; non-convex (deep nets) requires heuristics (e.g., Adam, batch norm) to avoid bad local minima.

BOXED KEY FORMULAS

• Bayes' Theorem: $$\displaystyle P(H|D) = \frac{P(D|H) P(H)}{P(D)} $$

• Linear Regression: $$\displaystyle y = \beta^T x + \epsilon $$

• Logistic Regression: $$\displaystyle P(y=1|x) = \frac{1}{1+e^{-\beta^T x}} $$

• SVM Margin: $$\displaystyle \text{Margin} = \frac{2}{\|w\|} $$

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

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

• Attention: $$\displaystyle \text{Attention}(Q,K,V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V $$

DIAGRAM REFERENCES

• DiagramSEARCH: CNN architecture diagram showing conv-pool-fc layers
• DiagramSEARCH: LSTM cell diagram with input/forget/output gates
• DiagramSEARCH: SVM margin and support vectors
• DiagramSEARCH: Transformer architecture with multi-head attention
• DiagramCANVAS: Backpropagation flow through MLP with chain rule