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

UNIT 2: ADVANCED MACHINE LEARNING ALGORITHMS

I. SUPERVISED LEARNING ADVANCED MODELS

A. Decision Trees

Recursive Induction

• Definition: A top-down, greedy algorithm that recursively partitions the feature space into homogeneous subsets.

• Process:

  1. Start with entire training set at root node.

  2. Select best split attribute using a splitting criterion (e.g., Information Gain, Gini Index).

  3. Partition data based on split; create child nodes.

  4. Recur on each child node until a stopping condition is met (e.g., pure node, max depth, min samples).

• [!TIP] Common Pitfall: Trees grow deep quickly → overfitting. Always consider pruning or depth limits.

Entropy and Information Gain

• Entropy ($H$): Measure of impurity/uncertainty in a set of samples.

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

where $$\displaystyle p_i $$ = proportion of samples in class $i$, $c$ = number of classes.

• Information Gain ($IG$): Reduction in entropy after splitting on attribute $A$.

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

where $$\displaystyle S_v $$ = subset where attribute $A$ has value $v$.

Example: Credit Scoring Dataset

| Sample | Credit Score | Loan Approved |

|--------|--------------|---------------|

| 1 | High | Yes |

| 2 | Medium | No |

| 3 | Low | No |

| 4 | High | Yes |

| 5 | Medium | Yes |

| 6 | Low | No |

| 7 | High | No |

Step 1: Overall Entropy $H(S)$:

• Yes: 3/7, No: 4/7

$$H(S) = -\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 attribute Credit Score:

• High (Samples 1,4,7): Yes=2, No=1 → $$\displaystyle H(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(Med) = 1.0 $$

• Low (Samples 3,6): Yes=0, No=2 → $$\displaystyle H(Low) = 0.0 $$

Step 3: Weighted Avg Entropy after split:

$$\frac{3}{7} \times 0.918 + \frac{2}{7} \times 1.0 + \frac{2}{7} \times 0.0 \approx 0.668$$

Step 4: Information Gain:

$$IG(S, \text{Credit Score}) = 0.985 - 0.668 = 0.317$$

\boxed{IG = 0.317 \text{ bits}}

Handling Noisy Data

• Impact: Noise causes overfitting → tree learns irrelevant patterns, poor generalization.

• Strategies:

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

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

  • Ensemble methods (e.g., Random Forest) inherently reduce variance.

  • Use robust splitting criteria less sensitive to noise.

B. Multi-Layer Perceptron (MLP)

Architecture

• Layers:

  • Input Layer: One neuron per feature (no computation).

  • Hidden Layer(s): Apply nonlinear transformations. Depth/width are hyperparameters.

  • Output Layer: Produces prediction (e.g., sigmoid for binary, softmax for multi-class).

• Neuron Computation:

$$z = \mathbf{w}^T \mathbf{x} + b, \quad a = \phi(z)$$

where $\phi$ = **activation function**.

• Common Activations:

  • Sigmoid: $$\displaystyle \phi(z) = \frac{1}{1+e^{-z}} $$ (output 0–1, vanishing gradient).

  • ReLU: $$\displaystyle \phi(z) = \max(0, z) $$ (sparse, mitigates vanishing gradient).

  • Tanh: $$\displaystyle \phi(z) = \frac{e^z - e^{-z}}{e^z + e^{-z}} $$ (output –1 to 1).

Learning Process

1. Forward Propagation: Compute output layer by layer.

2. Loss Calculation: Use loss function $L(y, \hat{y})$ (e.g., Cross-Entropy, MSE).

3. Backpropagation: Apply chain rule to compute gradient $$\displaystyle \frac{\partial L}{\partial w} $$ for each weight.

4. Weight Update: Gradient Descent:

$$w_{new} = w_{old} - \eta \frac{\partial L}{\partial w}$$

where $\eta$ = learning rate.

• [!TIP] Key Insight: Backprop efficiently computes gradients by reusing intermediate derivatives from forward pass.

C. Ensemble Methods

Bagging vs Boosting

Random Forest

• Algorithm Steps:

  1. For $$\displaystyle t=1 $$ to $T$ (number of trees):

     • Draw bootstrap sample from training data.

     • Grow decision tree: at each split, consider random subset of features (not all).

     • No pruning (or minimal pruning).

  2. Aggregation: For classification → majority vote; for regression → average.

• Variance Reduction: Bootstrap + feature randomness decorrelates trees, averaging reduces variance.

• Overfitting Control: Random feature selection + ensemble averaging inherently regularizes.

Robustness of Ensembles

• Why better?

  • Variance Reduction: Averaging multiple high-variance models (like deep trees) stabilizes predictions.

  • Bias-Variance Tradeoff: Bagging reduces variance without increasing bias much; boosting reduces bias.

  • Theoretical Guarantee: If base learners are weak but diverse, ensemble can become strong (Schapire’s theorem).

  • Practical: Handles noise, outliers, and model-specific quirks better.

• \boxed{\text{Ensemble robustness stems from diversity + aggregation, reducing both variance and bias.}}

D. Least Squares Methods

Concept and Applications

• Goal: Find parameters $\mathbf{w}$ that minimize sum of squared errors:

$$J(\mathbf{w}) = \sum_{i=1}^{n} (y_i - \mathbf{w}^T \mathbf{x}_i)^2$$

• Normal Equations (closed-form):

$$\mathbf{w} = (\mathbf{X}^T \mathbf{X})^{-1} \mathbf{X}^T \mathbf{y}$$

where $\mathbf{X}$ = design matrix.

• Applications:

  • Linear Regression: Direct prediction.

  • Classification: Used in Least Squares Classifier (project classes onto hyperplane).

  • Foundation for more advanced methods (Ridge, Lasso, neural nets output layer).

Advanced Considerations: Regularization

• Problem: $$\displaystyle (\mathbf{X}^T \mathbf{X}) $$ may be singular (collinearity) or ill-conditioned → overfitting.

• Ridge Regression (L2):

$$J(\mathbf{w}) = \sum (y_i - \mathbf{w}^T \mathbf{x}_i)^2 + \lambda \|\mathbf{w}\|_2^2$$

Solution: $$\displaystyle \mathbf{w} = (\mathbf{X}^T \mathbf{X} + \lambda \mathbf{I})^{-1} \mathbf{X}^T \mathbf{y} $$

• Shrinks coefficients, handles multicollinearity.

• Lasso Regression (L1):

$$J(\mathbf{w}) = \sum (y_i - \mathbf{w}^T \mathbf{x}_i)^2 + \lambda \|\mathbf{w}\|_1$$

• Produces sparse solutions (feature selection).

• [!TIP] Ridge vs Lasso: Use Ridge when all features are relevant; Lasso for automatic feature selection.

II. REINFORCEMENT LEARNING

A. Fundamental Equations

Bellman Equations

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

$$V^\pi(s) = \mathbb{E}_\pi \left[ R_{t+1} + \gamma V^\pi(S_{t+1}) \mid S_t = s \right]$$

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

$$Q^\pi(s,a) = \mathbb{E}_\pi \left[ R_{t+1} + \gamma Q^\pi(S_{t+1}, A_{t+1}) \mid S_t = s, A_t = a \right]$$

• Optimality Equations (for optimal policy $$\displaystyle \pi^* $$):

$$V^*(s) = \max_a \mathbb{E} \left[ R_{t+1} + \gamma V^*(S_{t+1}) \mid S_t = s, A_t = a \right]$$

$$Q^*(s,a) = \mathbb{E} \left[ R_{t+1} + \gamma \max_{a'} Q^*(S_{t+1}, a') \mid S_t = s, A_t = a \right]$$

• \boxed{\text{Bellman equations express recursive nature of cumulative reward via } \gamma \text{ discount factor.}}

B. Model-Free Methods

Q-learning vs SARSA

[!TIP] Mnemonic: Q-learning = Quick (off-policy, learns optimal); SARSA = Same Action Realized State Action (on-policy).

C. Policy-Based Methods

Policy Gradient Methods

• Objective: Maximize expected return $$\displaystyle J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta} [R(\tau)] $$, where $\theta$ = policy parameters.

• REINFORCE Algorithm (Monte Carlo policy gradient):

  1. Generate trajectory $$\displaystyle \tau = (s_0,a_0,r_1,...,s_T) $$ using policy $$\displaystyle \pi_\theta $$.

  2. Compute return $$\displaystyle R(\tau) = \sum_{t=0}^{T} \gamma^t r_{t+1} $$.

  3. Update:

$$\theta \leftarrow \theta + \alpha \nabla_\theta \log \pi_\theta(a_t|s_t) \cdot R(\tau)$$

• Likelihood Ratio Gradient (score function estimator):

$$\nabla_\theta J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^{T} \nabla_\theta \log \pi_\theta(a_t|s_t) \cdot R(\tau) \right]$$

• Advantages over Value-Based:

  • Directly optimize policy → suitable for continuous action spaces.

  • Can learn stochastic policies (good for exploration, partial observability).

  • No need for max operator (avoids overestimation bias).

• Disadvantages: High variance, slow convergence.

D. Temporal Difference vs Monte Carlo

Temporal Difference (TD) Learning

• Principle: Bootstrapping – update using current estimate of value function.

• TD(0) Update (for state values):

$$V(s_t) \leftarrow V(s_t) + \alpha \left[ r_{t+1} + \gamma V(s_{t+1}) - V(s_t) \right]$$

where $$\displaystyle r_{t+1} + \gamma V(s_{t+1}) $$ is TD target.

• Eligibility Traces (TD($\lambda$)): Combine multi-step returns; trace remembers visited states.

• Pros: Lower variance than MC, online (per-step), can learn before episode ends.

• Cons: Slightly biased due to bootstrapping.

Monte Carlo (MC) Methods

• Principle: No bootstrapping – update only after episode completion using actual return.

• Update:

$$V(s_t) \leftarrow V(s_t) + \alpha \left[ G_t - V(s_t) \right]$$

where $$\displaystyle G_t = \sum_{k=0}^{T-t-1} \gamma^k r_{t+k+1} $$ = total discounted return from $t$.

• Pros: Unbiased (uses true returns), simple.

• Cons: High variance (depends on full trajectory), must wait for episode end, not suitable for continuing tasks.

Key Differences

E. Advanced RL Topics

Generative Adversarial Imitation Learning (GAIL)

• Core Idea: Imitate expert demonstrations without reward function.

• Distinction from Standard RL:

  • Standard RL: Maximize given reward $r(s,a)$.

  • GAIL: Learn policy $\pi$ such that its state-action distribution matches expert’s, by adversarially learning a reward.

• Framework:

  1. Discriminator $D(s,a)$: Trained to distinguish expert vs. agent trajectories (binary classification).

  2. Generator (policy $\pi$): Trained to fool discriminator (i.e., maximize $D$’s error).

  3. Reward from discriminator: $$\displaystyle r(s,a) = -\log(1 - D(s,a)) $$ (or similar).

  4. Use any RL algorithm (e.g., TRPO, PPO) to optimize $\pi$ using this learned reward.

• Advantage: No need to design reward; directly mimics behavior.

Iterative Methods

• Value Iteration:

  • Initialize $$\displaystyle V_0(s) = 0 $$.

  • Repeat until convergence:

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

- Extract greedy policy: $$\displaystyle \pi(s) = \arg\max_a Q(s,a) $$.

- Guaranteed convergence to $$\displaystyle V^* $$ in finite MDPs.

• Policy Iteration:

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

  2. Policy Improvement: Update $\pi$ greedily w.r.t. $$\displaystyle V^\pi $$:

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

  3. Repeat until $\pi$ stable.

  • Often faster than value iteration but each iteration costlier.

Recent Trends in RL Architectures

• Deep Reinforcement Learning:

  • DQN (Deep Q-Network): Uses deep CNN to approximate $Q(s,a)$; experience replay, target network.

  • A3C (Asynchronous Advantage Actor-Critic): Parallel actors, actor-critic architecture, asynchronous updates.

  • PPO (Proximal Policy Optimization): Clipped objective for stable policy updates; popular for continuous control.

• Actor-Critic Methods: Combine value-based (critic estimates $Q$ or $V$) and policy-based (actor updates $\pi$) for lower variance.

• Model-Based RL: Learn environment model $P(s'|s,a)$, use for planning (e.g., Dyna-Q). More sample-efficient but model bias.

• Hybrid Approaches: Model-free on-policy + model-based planning (e.g., MBPO).

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

• Hierarchical RL: Options, meta-controllers for temporally extended actions.

[!TIP] Exam Focus: Be ready to contrast model-free vs model-based, and explain why PPO is widely adopted (stability, simplicity).