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

UNIT 4: ADVANCED MACHINE LEARNING

I. SUPERVISED LEARNING MODELS

A. Multi-Layer Perceptron (MLP)

Architecture:

• Feedforward Neural Network: Composed of an input layer (receives features), one or more hidden layers (perform transformations), and an output layer (produces prediction).

• Activation Functions: Introduce non-linearity.

  • Sigmoid: $$\displaystyle f(x) = \frac{1}{1 + e^{-x}} $$, output in (0,1), prone to vanishing gradient.

  • ReLU (Rectified Linear Unit): $$\displaystyle f(x) = \max(0, x) $$, computationally efficient, mitigates vanishing gradient.

  • Tanh: $$\displaystyle f(x) = \frac{e^x - e^{-x}}{e^x + e^{-x}} $$, output in (-1,1), zero-centered.

Learning Process:

1. Forward Propagation: Input data is passed through the network layer-by-layer to compute the predicted output.

2. Loss Calculation: A loss function (e.g., Mean Squared Error for regression, Cross-Entropy for classification) measures the error between prediction and true label.

3. Backpropagation: The gradient of the loss with respect to each weight is computed using the chain rule, starting from the output layer back to the input layer.

4. Weight Update (Gradient Descent): Weights are updated in the opposite direction of the gradient to minimize loss.

$$W_{new} = W_{old} - \eta \cdot \frac{\partial \mathcal{L}}{\partial W}$$

Where $\eta$ is the **learning rate**.

[!TIP] Exam Focus: Be prepared to draw a simple 3-layer MLP and trace the backpropagation steps for a given small network.

B. Decision Trees

Recursive Induction (Tree Construction):

1. Start with the entire training set at the root node.

2. Select the best attribute to split on using a splitting criterion (e.g., Information Gain, Gini Impurity).

3. Partition the dataset based on the selected attribute's values, creating child nodes.

4. Recurse on each child node with the corresponding subset of data.

5. Stop when a stopping criterion is met.

Stopping Criteria:

• All samples in a node belong to the same class.

• No remaining attributes to split on.

• Node contains fewer than a pre-specified minimum number of samples.

• Maximum tree depth is reached.

Entropy & Information Gain:

• Entropy measures the impurity or uncertainty of 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 belonging to class $i$, and $c$ is the number of classes. $$\displaystyle H(S)=0 $$ for a pure node.

• Information Gain (IG) measures the reduction in entropy achieved by splitting on an attribute $A$.

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

Where $$\displaystyle S_v $$ is the subset of $S$ for which attribute $A$ has value $v$.

Example Calculation (Dec 2025 Question):

Dataset: 7 samples, 2 classes (Yes/No). Overall Entropy $H(S)$?

| Loan Approved | Count |

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

| Yes | 3 |

| No | 4 |

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

Calculate IG for Credit Score (High/Medium/Low).

• $$\displaystyle S_{High} $$: [Yes, Yes, No] → $$\displaystyle H=0.918 $$

• $$\displaystyle S_{Medium} $$: [No, Yes] → $$\displaystyle H=1.0 $$

• $$\displaystyle S_{Low} $$: [No, No] → $$\displaystyle H=0.0 $$

$$IG(S, CreditScore) = 0.985 - \left( \frac{3}{7}*0.918 + \frac{2}{7}*1.0 + \frac{2}{7}*0.0 \right) \approx 0.128$$

Handling Noisy Data:

• Impact: Noise causes trees to overfit by learning irrelevant patterns, creating overly complex, brittle trees with poor generalization.

• Mitigation Strategies:

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

     • Pre-pruning: Stop tree growth early (via stopping criteria).

     • Post-pruning: Grow full tree, then remove non-critical branches (e.g., Reduced Error Pruning, Cost-Complexity Pruning).

  2. Ensemble Methods: Use Random Forests or Gradient Boosting, which average/combine many trees to reduce variance.

  3. Smoothing: Use continuous rather than discrete splits for numeric attributes.

II. ENSEMBLE LEARNING

A. Bagging vs. Boosting

B. Random Forest Algorithm

Working Mechanism:

1. Bootstrap Aggregation (Bagging): For each of $N$ trees:

   • Draw a bootstrap sample (with replacement) from the training data.

   • Train a decision tree on this sample.

2. Feature Randomness: At each node split in a tree, instead of considering all features, consider only a random subset of features (e.g., $\sqrt{\text{total features}}$ for classification). This decorrelates the trees.

3. Prediction: For classification, output the mode (majority vote) of all trees' predictions. For regression, output the mean.

Key Hyperparameters:

• n_estimators: Number of trees (more trees → more stable, but diminishing returns & higher cost).

• max_features: Number of features to consider at each split (critical for diversity; lower = more random, higher = more correlation).

• max_depth, min_samples_split: Control individual tree complexity.

C. Robustness of Ensemble Methods

• Why Ensembles Outperform: They exploit the "wisdom of crowds". Individual models may have high error, but their errors are often uncorrelated. By combining predictions, the ensemble averages out these errors.

• Bias-Variance Trade-off:

  • Bagging (Random Forest): Primarily reduces variance without increasing bias. Ideal for high-variance, low-bias base learners (like deep trees).

  • Boosting: Primarily reduces bias but can increase variance if not regularized (e.g., via shrinkage/learning rate, tree depth). Ideal for weak learners.

• Improved Generalization: The combination of multiple models leads to a smoother, more stable decision boundary that generalizes better to unseen data.

[!TIP] Common Pitfall: Confusing why bagging and boosting work. Remember: Bagging = Parallel, Variance Reduction. Boosting = Sequential, Bias Reduction.

III. REINFORCEMENT LEARNING

A. Fundamental Concepts

• MDP (Markov Decision Process): Defined by $(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 $a$.

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

  • $\gamma \in [0,1]$: Discount factor.

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

• Bellman Equations:

  • State-Value Function: Expected discounted return starting from state $s$ and following policy $\pi$.

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

    **Bellman Expectation Equation:**

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

*   **Action-Value Function (Q-function):** Expected return starting from $s$, taking action $a$, then following $\pi$.

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

    **Bellman Expectation Equation:**

$$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]$$

• Optimal Value Functions: $$\displaystyle V^*(s) = \max_{\pi} V^{\pi}(s) $$, $$\displaystyle Q^*(s,a) = \max_{\pi} Q^{\pi}(s,a) $$. The optimal policy $$\displaystyle \pi^* $$ is greedy w.r.t. $$\displaystyle Q^* $$.

Value Iteration vs. Policy Iteration:

B. Model-Free Methods

Temporal Difference (TD) Learning:

• Core Idea: Bootstrapping—update estimates based on other estimates (like DP), but learn from raw experience (like MC), without a model.

• TD(0) Update (for V):

$$V(S_t) \leftarrow V(S_t) + \alpha \left[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right]$$

The term $$\displaystyle \delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t) $$ is the **TD error**.

• Comparison with Monte Carlo (MC):

  | Feature | TD Learning | Monte Carlo | | :--- | :--- | :--- | | Update Target | Bootstrapped: $$\displaystyle R_{t+1} + \gamma V(S_{t+1}) $$ | Actual return: $$\displaystyle G_t = \sum_{k=0}^{T-t-1} \gamma^k R_{t+k+1} $$ | | Data Requirement | Online, incomplete episodes. Updates after every step. | Complete episodes only. Updates at episode end. | | Bias/Variance | Biased (due to bootstrapping), but lower variance. | Unbiased, but higher variance (depends on full trajectory). | | Sample Efficiency | Generally more sample efficient. | Less efficient, needs many episodes. |

Q-Learning (Off-policy TD Control):

• Learns optimal action-value function $$\displaystyle Q^* $$ independent of the policy being followed.

• Update Rule:

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma \max_{a} Q(S_{t+1}, a) - Q(S_t, A_t) \right]$$

• Exploration: Uses an exploratory policy (e.g., $\epsilon$-greedy) to generate experience, but target uses $$\displaystyle \max_a Q $$, making it off-policy.

• Goal: Find $$\displaystyle \pi^* $$ that is greedy w.r.t. $$\displaystyle Q^* $$.

SARSA (On-policy TD Control):

• Learns the Q-function for the current policy.

• Update Rule:

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) \right]$$

• Policy Dependence: The next action $$\displaystyle A_{t+1} $$ is chosen by the same exploratory policy used to generate $$\displaystyle (S_t, A_t) $$. This makes it on-policy.

• Behavior: More conservative/cautious than Q-learning, as it accounts for the exploration/exploitation trade-off in its updates.

Q-learning vs. SARSA:

C. Policy Gradient Methods

• Concept: Directly optimize the policy $$\displaystyle \pi_{\theta}(a|s) $$ parameterized by $\theta$ to maximize expected return $$\displaystyle J(\theta) = \mathbb{E}_{\pi_{\theta}}[G_t] $$. No value function needed.

• REINFORCE Algorithm (Monte Carlo Policy Gradient):

  1. Generate a full trajectory $$\displaystyle (s_0, a_0, r_1, ..., s_{T-1}, a_{T-1}, r_T) $$ using $$\displaystyle \pi_{\theta} $$.

  2. For each step $t$ in the trajectory, compute the return $$\displaystyle G_t $$.

  3. Update policy parameters:

$$\theta \leftarrow \theta + \alpha \gamma^t G_t \nabla_{\theta} \log \pi_{\theta}(a_t | s_t)$$

• Advantages over Value-Based Methods:

  • Can handle continuous action spaces (value-based methods need to find $$\displaystyle \arg\max_a Q $$).

  • Can learn stochastic policies (useful for exploration, partial observability, multi-agent settings).

  • Directly optimizes the performance objective $J(\theta)$.

D. Advanced Topics

Generative Adversarial Imitation Learning (GAIL):

• Difference from Standard RL: Standard RL learns a policy to maximize a given reward function. GAIL learns a policy to imitate expert demonstrations without an explicit reward function.

• Adversarial Framework:

  • Discriminator $D$: Trained to distinguish between state-action pairs from expert dataset and those from the current agent policy.

  • Generator (Policy $\pi$): Trained to fool the discriminator, i.e., produce state-action pairs that look like expert data.

  • The discriminator's output provides a shaped reward for the policy: $$\displaystyle r(s,a) = \log D(s,a) - \log(1-D(s,a)) $$.

  • This is equivalent to minimizing the Jensen-Shannon divergence between the agent's state-action distribution and the expert's.

Recent Trends in RL Architectures:

• Deep Reinforcement Learning: Combines RL with deep neural networks.

  • DQN (Deep Q-Network): Uses a deep network to approximate $Q(s,a)$ with experience replay and target network for stability.

  • DDPG (Deep Deterministic Policy Gradient): For continuous actions. Actor-critic method with deterministic policy.

• Actor-Critic Methods: Combine value-based (critic) and policy-based (actor) approaches for better sample efficiency and stability.

  • A2C/A3C (Advantage Actor-Critic, Asynchronous Advantage Actor-Critic): Use the advantage function $$\displaystyle A(s,a) = Q(s,a) - V(s) $$ as a lower-variance update target.

  • PPO (Proximal Policy Optimization): Uses a clipped surrogate objective to ensure small, stable policy updates, preventing destructive large steps. Highly popular.

• Hierarchical RL: Decomposes tasks into a hierarchy of sub-policies (options).

• Multi-agent RL: Studies multiple learning agents interacting in a shared environment (cooperation, competition, mixed).

IV. SPECIALIZED TOPICS

A. Least Squares Methods

In Machine Learning Context:

• Linear Regression: Fits a linear model $$\displaystyle y = X\beta + \epsilon $$ by minimizing the sum of squared residuals.

  • Closed-Form Solution (Normal Equation):

$$\hat{\beta} = (X^TX)^{-1}X^Ty$$

*   This is the **least squares estimate** that minimizes $$\displaystyle ||y - X\beta||^2_2 $$.

• Hypothesis Evaluation: The least squares solution provides the best linear unbiased estimator (BLUE) under Gauss-Markov assumptions (linearity, independence, homoscedasticity, normality). The residual sum of squares (RSS) is a key metric for model fit.

Least Squares Temporal Difference (LSTD) in RL:

• A model-free method to estimate the value function $V(s)$ that solves the Bellman equation in a least-squares sense.

• Instead of incremental TD updates, LSTD uses all collected data to solve a linear system, offering faster convergence (no step-size tuning) but higher computational cost per update.

• For a linear value function $$\displaystyle V(s) = \theta^T \phi(s) $$ (where $\phi$ are features), LSTD solves:

$$A\theta = b$$

Where:

$$A = \mathbb{E}[\phi(s)(\phi(s) - \gamma \phi(s'))^T], \quad b = \mathbb{E}[\phi(s)r]$$

These expectations are approximated from a batch of experience.

[!TIP] Key Connection: Both linear regression and LSTD find parameters $\theta$ by solving a linear system derived from minimizing a squared error objective—one for prediction ($y$), one for satisfying the Bellman equation.