Advance Machine Learning (AL-702 (B)) - Unit 5 Short Notes

UNIT 5: Advanced Machine Learning

1. Neural Networks

Multi-Layer Perceptron (MLP)

A feedforward artificial neural network with at least three layers: an input layer, one or more hidden layers, and an output layer. Each neuron (except input) applies a weighted sum followed by a non-linear activation function.

Architecture

• Input Layer: Receives feature vector $$\displaystyle \mathbf{x} \in \mathbb{R}^n $$. No computation.

• Hidden Layers: Compute transformations. Number of layers/neurons is a hyperparameter.

• Output Layer: Produces final prediction (e.g., class probabilities via softmax, regression value via linear activation).

• Activation Functions:

  • Sigmoid: $$\displaystyle \sigma(z) = \frac{1}{1+e^{-z}} $$. Outputs in (0,1). Suffers from vanishing gradients.

  • ReLU: $$\displaystyle \text{ReLU}(z) = \max(0, z) $$. Computationally efficient, mitigates vanishing gradient.

  • Tanh: $$\displaystyle \tanh(z) = \frac{e^z - e^{-z}}{e^z + e^{-z}} $$. Outputs in (-1,1), zero-centered.

Learning Process

1. Forward Propagation:

   For layer $l$ with weights $$\displaystyle \mathbf{W}^{(l)} $$, biases $$\displaystyle \mathbf{b}^{(l)} $$, and activation $$\displaystyle g^{(l)} $$:

$$\mathbf{z}^{(l)} = \mathbf{W}^{(l)}\mathbf{a}^{(l-1)} + \mathbf{b}^{(l)}$$

$$\mathbf{a}^{(l)} = g^{(l)}(\mathbf{z}^{(l)})$$

where $$\displaystyle \mathbf{a}^{(0)} = \mathbf{x} $$.

2. Loss Computation:

   • MSE for regression: $$\displaystyle L = \frac{1}{N}\sum_{i=1}^N (y_i - \hat{y}_i)^2 $$.

   • Cross-Entropy for classification: $$\displaystyle L = -\frac{1}{N}\sum_{i=1}^N \sum_{c=1}^C y_{ic} \log(\hat{y}_{ic}) $$.

3. Backpropagation:

   Compute gradient of loss w.r.t. all parameters using chain rule.

   • Output layer error: $$\displaystyle \delta^{(L)} = \nabla_{\mathbf{a}} L \odot g'^{(L)}(\mathbf{z}^{(L)}) $$.

   • Backpropagate: $$\displaystyle \delta^{(l)} = (\mathbf{W}^{(l+1)})^T \delta^{(l+1)} \odot g'^{(l)}(\mathbf{z}^{(l)}) $$.

   • Gradients: $$\displaystyle \nabla_{\mathbf{W}^{(l)}} L = \delta^{(l)} (\mathbf{a}^{(l-1)})^T $$, $$\displaystyle \nabla_{\mathbf{b}^{(l)}} L = \delta^{(l)} $$.

4. Weight Update (Gradient Descent):

$$\mathbf{W}^{(l)} \leftarrow \mathbf{W}^{(l)} - \eta \nabla_{\mathbf{W}^{(l)}} L$$

where $\eta$ is the learning rate.

[!TIP] Exam Focus

• Be prepared to draw the MLP architecture and label all components.

• Derive backpropagation equations for a 2-layer MLP with sigmoid activation.

• Common Pitfall: Confusing the order of matrix multiplication in backpropagation. Always verify dimensions.

2. Decision Trees

Recursive Induction

Top-down, greedy algorithm that recursively partitions the feature space into axis-aligned rectangles.

1. Start with all training data at root.

2. Select the best split (feature and threshold) using a splitting criterion.

3. Partition data into left/right child nodes.

4. Recurse on child nodes until a stopping condition is met (e.g., max depth, min samples, purity).

Splitting Criteria

Entropy and Information Gain (Exam Calculation)

Given dataset:

Step 1: Overall Entropy (Parent)

• Total samples $$\displaystyle N = 7 $$.

• Yes: 3 samples, $$\displaystyle p_{\text{yes}} = 3/7 $$.

• No: 4 samples, $$\displaystyle p_{\text{no}} = 4/7 $$.

$$H(\text{parent}) = -\left(\frac{3}{7}\log_2\frac{3}{7} + \frac{4}{7}\log_2\frac{4}{7}\right) \approx 0.985$$

Step 2: Entropy for "Credit Score" splits

• High (Samples 1,4,7): Yes=2, No=1 → $$\displaystyle H_{\text{High}} = -\left(\frac{2}{3}\log_2\frac{2}{3} + \frac{1}{3}\log_2\frac{1}{3}\right) \approx 0.918 $$

• Medium (Samples 2,5): Yes=1, No=1 → $$\displaystyle H_{\text{Med}} = 1.0 $$

• Low (Samples 3,6): Yes=0, No=2 → $$\displaystyle H_{\text{Low}} = 0 $$

Step 3: Weighted Child Entropy & IG

$$H(\text{children}) = \frac{3}{7}(0.918) + \frac{2}{7}(1.0) + \frac{2}{7}(0) \approx 0.683$$

$$IG(\text{Credit Score}) = 0.985 - 0.683 = \boxed{0.302}$$

Handling Noisy Data

Effects: Causes overfitting—tree grows overly complex, capturing noise as patterns, leading to poor generalization.

Strategies:

1. Pruning:

   • Pre-pruning: Stop growth early (max depth, min samples split, min impurity decrease).

   • Post-pruning: Grow full tree, then remove branches (e.g., reduced error pruning, cost-complexity pruning).

2. Ensemble Methods: Use Random Forest or Gradient Boosting to average out noise.

3. Robust Splitting Criteria: Use Gain Ratio or Chi-squared tests to reduce bias.

4. Smoothing: Apply Laplace correction for probabilities with zero counts.

[!TIP] Exam Focus

• Always show entropy calculation steps clearly for given datasets.

• Distinguish pre-pruning (stopping criteria) vs post-pruning (trimming after growth).

• Common Pitfall: Forgetting to weight child entropies by sample proportion in IG calculation.

3. Ensemble Learning

Bagging vs Boosting

Random Forest Algorithm

1. Bootstrap Sampling: For each tree $$\displaystyle t=1...T $$, draw $N$ samples with replacement from training data.

2. Random Feature Selection: At each split, consider only $m \ll M$ random features (typically $$\displaystyle m=\sqrt{M} $$ for classification).

3. Tree Growth: Grow each tree to maximum depth (no pruning) using best split from random feature subset.

4. Prediction:

   • Classification: Majority vote across trees.

   • Regression: Average output.

5. Out-of-Bag (OOB) Error:

   • ~36% of samples not in bootstrap sample for a given tree → OOB samples.

   • Use OOB samples as validation to estimate error without separate validation set.

6. Variable Importance:

   • Mean Decrease Impurity: Sum of impurity reduction (Gini/entropy) over all splits where feature used.

   • Mean Decrease Accuracy: Permutation importance—shuffle feature, measure OOB accuracy drop.

Ensemble Robustness

Ensembles reduce variance (bagging) or bias (boosting) by aggregating diverse models.

• Variance Reduction: Averaging multiple high-variance models (e.g., deep trees) smooths out fluctuations.

• Bias Reduction: Boosting sequentially corrects residuals, fitting a strong model from weak learners.

• Bias-Variance Tradeoff: Ensembles often achieve better generalization by balancing both.

• Robustness to Noise/Outliers: Bagging less affected; boosting may overfit noise unless regularized (e.g., shrinkage, subsampling).

[!TIP] Exam Focus

• Draw and explain RF workflow with bootstrap, random features, voting.

• Define OOB error and why it's useful (unbiased estimate, no need for CV).

• Common Pitfall: Confusing Random Forest's random feature selection with random attribute selection in standard bagging trees.

4. Reinforcement Learning

Fundamental Framework: MDP

A Markov Decision Process is defined by $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$:

• $\mathcal{S}$: Set of states.

• $\mathcal{A}$: Set of actions.

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

• $R(s,a,s')$: Reward function (expected immediate reward).

• $\gamma \in [0,1]$: Discount factor (future reward importance).

Policy $\pi(a|s)$: Probability of taking action $a$ in state $s$. Goal: Find optimal policy $$\displaystyle \pi^* $$ maximizing expected discounted return $$\displaystyle G_t = \sum_{k=0}^\infty \gamma^k R_{t+k+1} $$.

Bellman Equations

Define state-value function $$\displaystyle V^\pi(s) $$ and action-value function $$\displaystyle Q^\pi(s,a) $$:

• State-value: $$\displaystyle V^\pi(s) = \mathbb{E}_\pi[G_t | S_t = s] $$

• Action-value: $$\displaystyle Q^\pi(s,a) = \mathbb{E}_\pi[G_t | S_t = s, A_t = a] $$

Bellman Expectation Equations:

$$V^\pi(s) = \sum_{a} \pi(a|s) \sum_{s',r} p(s',r|s,a) \left[ r + \gamma V^\pi(s') \right]$$

$$Q^\pi(s,a) = \sum_{s',r} p(s',r|s,a) \left[ r + \gamma \sum_{a'} \pi(a'|s') Q^\pi(s',a') \right]$$

Bellman Optimality Equations (for $$\displaystyle \pi^* $$):

$$V^*(s) = \max_{a} \sum_{s',r} p(s',r|s,a) \left[ r + \gamma V^*(s') \right]$$

$$Q^*(s,a) = \sum_{s',r} p(s',r|s,a) \left[ r + \gamma \max_{a'} Q^*(s',a') \right]$$

Model-Based Methods

1. Policy Iteration:

   • Policy Evaluation: Compute $$\displaystyle V^\pi $$ for current $\pi$ (solve linear system or iterate).

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

   • Repeat until $\pi$ stable.

2. Value Iteration:

   • Directly approximate $$\displaystyle V^* $$ by iterative Bellman backup:

$$V_{k+1}(s) = \max_{a} \sum_{s',r} p(s',r|s,a)[r + \gamma V_k(s')]$$

• Stop when $$\displaystyle \max_s |V_{k+1}(s) - V_k(s)| < \theta $$.

Model-Free Methods

TD vs Monte Carlo

• Bootstrap: TD uses $V(s')$ (current estimate); MC uses actual $$\displaystyle G_t $$.

• Variance: TD lower (updates based on single step); MC higher (depends on full trajectory).

• Sample Efficiency: TD learns from incomplete episodes, more data-efficient.

• Convergence: Both converge to $$\displaystyle V^\pi $$ under appropriate conditions (diminishing $\alpha$).

Q-learning vs SARSA

Policy-Based Methods

Policy Gradient directly optimize $$\displaystyle \pi_\theta $$ (parameterized by $\theta$) to maximize expected return $$\displaystyle J(\theta) = \mathbb{E}_{\pi_\theta}[G] $$.

• REINFORCE (Monte Carlo Policy Gradient):

$$\theta \leftarrow \theta + \alpha G_t \nabla_\theta \log \pi_\theta(A_t|S_t)$$

Updates after full episode.

• Actor-Critic: Uses critic (value function $V(s)$ or $Q(s,a)$) to reduce variance.

  • Advantage Function: $$\displaystyle A(s,a) = Q(s,a) - V(s) $$ estimates how much better action $a$ is vs average.

  • Update: $$\displaystyle \theta \leftarrow \theta + \alpha A(s,a) \nabla_\theta \log \pi_\theta(a|s) $$.

Generative Adversarial Imitation Learning (GAIL)

Goal: Learn policy $\pi$ that mimics expert demonstrations $$\displaystyle \mathcal{D}_E $$, without reward function.

• Adversarial Framework:

  • Discriminator $D(s,a)$: Distinguishes expert vs agent trajectories (binary classifier).

  • Generator (policy $\pi$): Tries to fool discriminator.

• Objective (minimax):

$$\min_\pi \max_D \mathbb{E}_{\pi}[\log D(s,a)] + \mathbb{E}_{\mathcal{D}_E}[\log(1-D(s,a))]$$

• Difference from Standard RL:

  • Standard RL: Maximize reward via trial-and-error.

  • GAIL: No reward; learn from demonstrations using adversarial training. More sample-efficient, avoids reward design.

Recent Trends in RL Architectures

1. Deep Reinforcement Learning:

   • DQN: Combines Q-learning with deep CNNs, experience replay, target network.

   • Policy Gradients with Deep Networks: A3C, PPO (proximal policy optimization).

2. Hierarchical RL: Decompose tasks into sub-policies (options framework).

3. Multi-agent RL: Independent learners, cooperative/competitive settings (e.g., MADDPG).

4. Model-Based RL Hybrids: Learn dynamics model $P(s'|s,a)$, use for planning (e.g., MBPO, Dreamer).

[!TIP] Exam Focus

• Write Bellman equations for both state-value and action-value forms.

• Differentiate Q-learning (off-policy) vs SARSA (on-policy) with update rules.

• For GAIL, emphasize adversarial training and no reward function.

• Common Pitfall: Confusing policy iteration (alternating evaluation/improvement) with value iteration (direct backup).

5. Least Squares Methods

Least Squares Regression

Goal: Fit linear model $$\displaystyle y = \mathbf{x}^T\beta + \epsilon $$ by minimizing Mean Squared Error (MSE).

• Cost Function: $$\displaystyle J(\beta) = \frac{1}{N}\|\mathbf{y} - \mathbf{X}\beta\|^2_2 $$.

• Normal Equations (closed-form solution):

$$\nabla_\beta J = -2\mathbf{X}^T(\mathbf{y} - \mathbf{X}\beta) = 0$$

$$\boxed{\hat{\beta} = (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y}}$$

(Requires $$\displaystyle \mathbf{X}^T\mathbf{X} $$ invertible; use pseudoinverse if not).

• Gradient Descent: Iterative: $$\displaystyle \beta \leftarrow \beta - \eta \nabla J $$.

Applications in Machine Learning

1. Linear Models: Foundation for Ridge ($$\displaystyle L_2 $$) and Lasso ($$\displaystyle L_1 $$) regularization.

   • Ridge: $$\displaystyle \hat{\beta} = (\mathbf{X}^T\mathbf{X} + \lambda I)^{-1}\mathbf{X}^T\mathbf{y} $$.

   • Lasso: No closed form; use coordinate descent.

2. Least Squares Support Vector Machines (LS-SVM):

   • Reformulates SVM as solving linear equations (instead of QP), using $$\displaystyle L_2 $$ loss.

3. Least Squares Policy Iteration (LSPI) in RL:

   • Approximate $Q(s,a)$ as linear: $$\displaystyle Q(s,a) = \theta^T \phi(s,a) $$.

   • Solve Bellman equation in least-squares sense: $$\displaystyle \hat{\theta} = (\Phi^T D \Phi)^{-1} \Phi^T \mathbf{r} $$, where $\Phi$ is feature matrix, $D$ is state-action distribution.

4. Ordinary Least Squares (OLS): Baseline for regression tasks, interpretable coefficients.

[!TIP] Exam Focus

• Derive normal equations from MSE minimization.

• State assumptions of OLS (linearity, independence, homoscedasticity, no multicollinearity).

• Connect to regularization: Ridge shrinks coefficients; Lasso performs feature selection.

• Common Pitfall: Forgetting that $$\displaystyle (\mathbf{X}^T\mathbf{X})^{-1} $$ exists only if $\mathbf{X}$ has full column rank.