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

UNIT 3: Advanced Machine Learning Topics

I. Neural Networks and Deep Learning

A. Multi-Layer Perceptron (MLP)

1. Architecture

An MLP is a feedforward artificial neural network consisting of:

• Input Layer: Receives the feature vector. Number of neurons equals input feature dimension.

• Hidden Layer(s): One or more layers between input and output. Perform nonlinear transformations. Depth defines "deep" learning.

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

Activation Functions (introduce non-linearity):

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

• Tanh: $$\displaystyle \tanh(z) = \frac{e^z - e^{-z}}{e^z + e^{-z}} $$. Outputs (-1,1). Zero-centered, still vanishing gradient.

• ReLU: $$\displaystyle \text{ReLU}(z) = \max(0, z) $$. Computationally efficient, mitigates vanishing gradient (for positive inputs), can cause "dying ReLU".

2. Learning Process

• Feedforward Propagation: Input data is passed through the network layer-by-layer to compute the output/prediction.

  $$\displaystyle z^{(l)} = W^{(l)}a^{(l-1)} + b^{(l)} $$, $$\displaystyle a^{(l)} = g(z^{(l)}) $$, where $g$ is activation.

• Loss Function: Measures error between prediction $\hat{y}$ and true $y$.

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

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

• Backpropagation: Algorithm to compute gradients of loss w.r.t. all weights ($W, b$).

  1. Forward pass to compute loss.

  2. Backward pass: Apply chain rule to compute $$\displaystyle \frac{\partial L}{\partial W^{(l)}} $$ starting from output layer to input layer.

• Gradient Descent & Weight Updates: Optimizer (e.g., SGD, Adam) uses computed gradients to update parameters:

  $$\displaystyle W^{(l)} \leftarrow W^{(l)} - \eta \frac{\partial L}{\partial W^{(l)}} $$, where $\eta$ is the learning rate.

[!TIP]

Key Exam Point: Be prepared to derive or state the gradient update for a simple 1-hidden-layer MLP using chain rule. Understand the role of each component (activation, loss, backprop).

II. Decision Trees

A. Recursive Induction

• Top-down, greedy construction: Starts at root, selects the best attribute to split on at each node using a splitting criterion. Recursively partitions data until a stopping condition is met.

• Stopping Conditions: All samples at node belong to same class, no remaining attributes, or minimum samples per node reached.

B. Entropy and Information Gain

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

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

where $$\displaystyle p_i $$ is the proportion of samples of class $i$ in $S$, $c$ is number of classes. $$\displaystyle H=0 $$ for pure set.

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

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

where $$\displaystyle S_v $$ is subset of $S$ where attribute $A$ has value $v$.

• Example Calculation (from DEC 2025 paper):

  Dataset S (7 samples): 4 Yes, 3 No.

  $$\displaystyle H(S) = -\left(\frac{4}{7}\log_2\frac{4}{7} + \frac{3}{7}\log_2\frac{3}{7}\right) \approx 0.985 $$.

  For attribute Credit Score (High, Medium, Low):

  • High: 2 Yes, 1 No → $H \approx 0.918$

  • Medium: 1 Yes, 1 No → $$\displaystyle H = 1.0 $$

  • Low: 0 Yes, 3 No → $$\displaystyle H = 0 $$

  $$\displaystyle IG(S, \text{Credit Score}) = 0.985 - \left(\frac{3}{7}*0.918 + \frac{2}{7}*1.0 + \frac{2}{7}*0\right) \approx 0.985 - 0.655 = 0.330 $$.

  \boxed{IG(S, \text{Credit Score}) \approx 0.330}

C. Handling Noisy Data

• Impact: Noise causes overfitting—tree becomes overly complex, capturing noise as patterns, leading to poor generalization.

• Mitigation Strategies:

  1. Pruning: Remove branches that provide little predictive power.

     • Pre-pruning (early stopping): Halt growth based on criteria (min samples per leaf, max depth, min IG threshold).

     • Post-pruning: Grow full tree, then remove nodes using a validation set (e.g., reduced error pruning).

  2. Smoothing: Adjust probability estimates at leaves (e.g., Laplace correction for Naive Bayes, or m-estimate).

  3. Ensemble Methods: Use Bagging (Random Forest) to reduce variance and improve robustness to noise.

[!TIP]

Common Pitfall: Confusing pre-pruning and post-pruning. Pre-pruning is faster but may underfit; post-pruning is more effective but computationally costlier.

III. Ensemble Learning

A. Bagging and Boosting

B. Random Forest

1. Algorithm Mechanism:

   • For $B$ trees:

     1. Draw bootstrap sample from training data.

     2. Grow a decision tree. At each split, consider only a random subset of features (e.g., $\sqrt{p}$ for classification).

     3. Do not prune trees.

   • Aggregation: Classification → majority vote; Regression → average of predictions.

2. Hyperparameters: n_estimators (number of trees), max_features, max_depth, min_samples_split.

3. Advantages:

   • Robust to overfitting (due to bagging & feature randomness).

   • Provides feature importance scores (mean decrease in impurity).

   • Handles high-dimensional data well.

C. Ensemble Robustness

Ensembles outperform single models by:

1. Error Averaging: Random errors of individual models cancel out (variance reduction).

2. Bias Reduction: Boosting explicitly corrects systematic errors.

3. Mitigating Overfitting: Diversity among models (from different data/feature views) leads to smoother, more generalized decision boundaries.

4. Stability: Less sensitive to noise, outliers, and specific hyperparameter choices than a single complex model.

[!TIP]

Key Comparison: Bagging helps when base learners are unstable (high variance, like deep trees). Boosting helps when base learners are weak (slightly better than random, high bias).

IV. Reinforcement Learning

A. Foundations

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

  • $S$: Set of states.

  • $A$: Set of actions.

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

  • $R(s, a, s')$: Immediate reward.

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

• Policy ($\pi$): Strategy mapping states to actions. $\pi(a|s)$ is probability of taking $a$ in $s$.

• Value Functions:

  • State-Value: $$\displaystyle V_\pi(s) = \mathbb{E}_\pi\left[ \sum_{t=0}^{\infty} \gamma^t R_{t+1} \mid S_0 = s \right] $$

  • Action-Value: $$\displaystyle Q_\pi(s, a) = \mathbb{E}_\pi\left[ \sum_{t=0}^{\infty} \gamma^t R_{t+1} \mid S_0 = s, A_0 = a \right] $$

• Bellman Equations:

  • Expectation: $$\displaystyle V_\pi(s) = \sum_a \pi(a|s) \sum_{s',r} P(s',r|s,a)[r + \gamma V_\pi(s')] $$

  • Optimality: $$\displaystyle V_*(s) = \max_a \sum_{s',r} P(s',r|s,a)[r + \gamma V_*(s')] $$

  \boxed{Q_(s,a) = \sum_{s',r} P(s',r|s,a)[r + \gamma \max_{a'} Q_(s',a')]}

  These are fixed-point equations central to planning and RL.

B. Model-Free Learning Methods

• Temporal Difference (TD) Learning: Learns from bootstrapped estimates (updates target using current estimate).

  • TD(0) Update: $$\displaystyle V(S_t) \leftarrow V(S_t) + \alpha [R_{t+1} + \gamma V(S_{t+1}) - V(S_t)] $$

  • vs. Monte Carlo (MC): MC waits for episode end, uses actual return $$\displaystyle G_t $$. TD updates online after each step.

  • Comparison:

    | | TD Learning | Monte Carlo | | :--- | :--- | :--- | | Update | Bootstrapping (uses $$\displaystyle V(S_{t+1}) $$) | Averages full returns $$\displaystyle G_t $$ | | Timing | Online (after each step) | Offline (after episode) | | Variance | Lower (bootstrapping reduces variance) | Higher (depends on full trajectory) | | Convergence | To $$\displaystyle V_\pi $$ (with proper $\alpha$) | To $$\displaystyle V_\pi $$ (with enough episodes) |

• Q-learning (Off-policy TD Control):

  • Learns optimal $$\displaystyle Q_*(s,a) $$ independent of policy $\pi$ (can follow exploratory policy).

  • Update Rule: $$\displaystyle Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t)] $$

  • Exploration-Exploitation: Use $\epsilon$-greedy: with prob $\epsilon$ choose random action, else $$\displaystyle \arg\max_a Q(s,a) $$.

• SARSA (On-policy TD Control):

  • Learns $$\displaystyle Q_\pi $$ for the policy being followed.

  • Update Rule: $$\displaystyle Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)] $$

  • Comparison with Q-learning:

    • SARSA is on-policy, Q-learning is off-policy.

    • SARSA considers the next action $$\displaystyle A_{t+1} $$ (from same policy), so it learns about the exploratory policy. Q-learning learns the optimal policy regardless of exploration.

    • SARSA is more conservative near cliff edges (in gridworld) as it accounts for exploration risk. Q-learning can learn optimal but risky path.

C. Policy Gradient Methods

• Fundamentals: Directly optimize policy $$\displaystyle \pi_\theta(a|s) $$ (parameterized by $\theta$) to maximize expected return $$\displaystyle J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta}[\sum_t R_t] $$.

• Policy Gradient Theorem: $$\displaystyle \nabla_\theta J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta}[\sum_t \nabla_\theta \log \pi_\theta(a_t|s_t) \cdot Q^{\pi_\theta}(s_t, a_t)] $$.

• Key Algorithms:

  1. REINFORCE (Monte Carlo Policy Gradient): Uses full episode return $$\displaystyle G_t $$ as estimator for $Q$. High variance, updates only at episode end.

  2. Actor-Critic: Uses a learned value function (Critic, e.g., $V(s)$) to reduce variance.

     • Actor: Policy $$\displaystyle \pi_\theta $$.

     • Critic: Estimates $Q(s,a)$ or $V(s)$ (e.g., via TD).

     • Advantage: $$\displaystyle A(s,a) = Q(s,a) - V(s) $$ used as lower-variance baseline.

• Advantages over Value-based (Q-learning):

  • Naturally handle continuous action spaces (value-based needs discrete actions for max).

  • Often faster convergence in high-dimensional/continuous spaces.

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

D. Advanced RL Topics

1. Generative Adversarial Imitation Learning (GAIL):

   • Goal: Learn policy $\pi$ that mimics expert demonstrations $$\displaystyle \mathcal{D}_{exp} $$, without a predefined reward function.

   • Mechanism: Adversarial framework:

     • Discriminator $D$: Trained to distinguish state-action pairs from expert vs. agent.

     • Generator (Policy $\pi$): Trained to fool $D$ (i.e., make its state-action pairs look expert-like).

   • Difference from RL: Standard RL optimizes for a given reward. GAIL infers a reward from $D$ (e.g., $$\displaystyle r(s,a) = \log D(s,a) $$) and then performs RL. It's imitation learning, not reward optimization.

2. Value Iteration vs. Policy Iteration:

   • Value Iteration: Repeatedly apply Bellman optimality update to $V$ until convergence. Then extract greedy policy. Faster per iteration, but may require many iterations.

   • Policy Iteration: Alternate between:

     1. Policy Evaluation: Compute $$\displaystyle V_\pi $$ (solve linear system or iterative TD).

     2. Policy Improvement: Make policy greedy w.r.t $$\displaystyle V_\pi $$: $$\displaystyle \pi'(s) = \arg\max_a \sum_{s'} P(s'|s,a)[R + \gamma V_\pi(s')] $$.

     • Comparison: Policy iteration often converges in fewer outer iterations but each iteration is costlier (full policy evaluation). Value iteration is simpler but can be slower.

3. Recent Trends in RL Architectures:

   • Deep RL: Uses deep neural nets as function approximators (e.g., DQN for value-based, A3C/PPO for policy gradient).

   • Model-based RL: Learns a model of environment dynamics $P(s'|s,a)$ and uses it for planning/imagined rollouts.

   • Hierarchical RL (HRL): Learns temporally extended options (sub-policies) for abstraction.

   • Multi-agent RL (MARL): Multiple agents learning jointly (cooperative, competitive, mixed).

   • Meta-RL: "Learning to learn" – algorithms that adapt quickly to new tasks.

V. Special Topics

A. Least Squares Methods

1. Least Squares Regression

• Linear Model: $$\displaystyle y = X\beta + \epsilon $$, where $X$ is design matrix, $\beta$ coefficients, $\epsilon$ error.

• Ordinary Least Squares (OLS): Minimizes sum of squared residuals.

$$\hat{\beta} = \arg\min_\beta \|y - X\beta\|^2$$

• Normal Equations (Closed-form Solution):

$$\nabla_\beta \|y - X\beta\|^2 = 0 \implies X^T X \hat{\beta} = X^T y$$

\boxed{\hat{\beta} = (X^T X)^{-1} X^T y} \quad \text{(if invertible)}

• Assumptions: Linearity, independence, homoscedasticity, no perfect multicollinearity, errors normally distributed (for inference).

• Properties: BLUE (Best Linear Unbiased Estimator) under Gauss-Markov assumptions.

2. Applications in Machine Learning

• Baseline Model: Simple, interpretable linear predictor.

• Reinforcement Learning: Least Squares Temporal Difference (LSTD) – solves Bellman equation in least-squares sense for more stable, sample-efficient value function estimation than TD(0). Used in LSPI (Least-Squares Policy Iteration).

[!TIP]

Exam Focus: You may be asked to derive the OLS normal equations or explain its use in RL (LSTD). Know the formula $$\displaystyle \hat{\beta} = (X^TX)^{-1}X^Ty $$ and its conditions.