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

UNIT 1: ADVANCED MACHINE LEARNING FOUNDATIONS AND CORE ALGORITHMS

1. Foundations of Machine Learning

1.1 Algorithmic Foundations

• Characteristics of Algorithms: Finiteness (terminates), Definiteness (precise steps), Input/Output, Effectiveness (feasible steps).

• Tools for Algorithm Analysis:

  • Time Complexity: Measures steps as function of input size (Big O notation).

    Example: $$\displaystyle O(n^2) $$ for naive nested loops.

  • Space Complexity: Measures memory usage.

• Divide and Conquer Technique:

  Break problem into subproblems, solve recursively, combine solutions.

  Example: Merge sort ($$\displaystyle T(n) = 2T(n/2) + O(n) $$).

1.2 Probabilistic Modeling and Inference

• Probabilistic Models: Represent uncertainty using probability distributions.

  Examples: Bayesian networks, Hidden Markov Models (HMMs), Naive Bayes.

• Probabilistic Inference: Compute posterior probabilities given evidence.

  Example: In Naive Bayes, $$\displaystyle P(\text{class}|\text{features}) \propto P(\text{class}) \prod P(\text{feature}|\text{class}) $$.

1.3 Data Description and Preparation

• Data Extraction: From databases (SQL), APIs, web scraping (requests, BeautifulSoup), files (CSV, JSON).

• Cleaning & Preprocessing: Handle missing values (imputation, deletion), outliers (capping, transformation), normalization (min-max, z-score).

• Transformation: Encoding categorical variables (one-hot, label encoding), feature scaling.

1.4 Learning Paradigms and Problem Formulation

• Well-Posed Learning Problem: Defined by task (e.g., classification), performance measure (e.g., accuracy), and source of experience (training data).

• Lazy vs. Eager Learning:

  | Lazy Learning | Eager Learning | |---|---| | Delays generalization until query time (e.g., k-NN). | Builds model during training (e.g., decision trees, neural networks). | | Fast training, slow prediction. | Slow training, fast prediction. |

• Learning Types:

  • Supervised: Labeled data (classification, regression).

  • Unsupervised: Unlabeled data (clustering, dimensionality reduction).

  • Reinforcement: Agent learns via rewards/penalties from environment.

[!TIP]

Exam Focus: Differentiate lazy/eager with examples. Define well-posed learning problem clearly.

2. Decision Trees

2.1 Core Concepts: Entropy and Information Gain

• Entropy: Measures impurity/uncertainty in dataset $S$.

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

where $$\displaystyle p_i $$ = proportion of 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 \text{Values}(A)} \frac{|S_v|}{|S|} H(S_v)$$

• Gini Impurity: Alternative measure: $$\displaystyle G(S) = 1 - \sum_{i=1}^{c} p_i^2 $$. Faster computation, similar results.

Example Calculation (from Dec 2025 paper):

Dataset: 7 samples, 3 "Yes", 4 "No".

Overall entropy: $$\displaystyle H(S) = -\frac{3}{7}\log_2\frac{3}{7} - \frac{4}{7}\log_2\frac{4}{7} \approx 0.985 $$.

Split on Credit Score:

• High (3 samples: 2 Yes, 1 No): $H(\text{High}) \approx 0.918$

• Medium (2 samples: 1 Yes, 1 No): $$\displaystyle H(\text{Medium}) = 1 $$

• Low (2 samples: 0 Yes, 2 No): $$\displaystyle H(\text{Low}) = 0 $$

IG = $$\displaystyle 0.985 - \left( \frac{3}{7} \times 0.918 + \frac{2}{7} \times 1 + \frac{2}{7} \times 0 \right) \approx 0.328 $$.

2.2 Tree Construction: Recursive Induction

• Top-Down, Greedy Recursive Partitioning: At each node, select attribute with highest IG (or lowest Gini) to split.

• Handling Attributes:

  • Categorical: Split by each category.

  • Numerical: Find threshold that maximizes IG (e.g., sort values, try midpoints).

• Stopping Conditions: Pure node (all same class), max depth reached, min samples per node, IG below threshold.

2.3 Overfitting and Noisy Data

• Impact of Noise: Causes trees to learn spurious patterns, leading to overfitting (high variance).

• Strategies to Overcome Noise:

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

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

• Handling Missing Values:

  • Surrogate splits (use alternative attribute).

  • Impute missing values (mean, mode, or predictive modeling).

2.4 Applications and Extensions

• Decision Trees in Game Development: Extract human-readable rules for NPC behavior (e.g., "if health < 30% and enemy near → flee").

• Rule Extraction: Convert tree paths to IF-THEN rules for interpretable AI systems.

[!TIP]

Common Pitfall: Forgetting to handle numerical attributes properly—always discretize or find optimal threshold.

3. Ensemble Methods

3.1 Bagging and Random Forest

• Bootstrap Aggregating (Bagging):

  1. Create $B$ bootstrap samples (with replacement).

  2. Train base learner (e.g., decision tree) on each.

  3. Aggregate: majority vote (classification) or average (regression).

• Random Forest:

  • Extends bagging with feature randomness: at each split, consider only random subset of features.

  • Increases diversity among trees, reduces correlation.

• Feature Importance: Measured by total decrease in impurity (Gini/entropy) averaged over all trees.

• Out-of-Bag (OOB) Error: Estimate generalization error using samples not in bootstrap (~37% left out).

3.2 Boosting Algorithms

• AdaBoost:

  • Weighted voting: each weak learner trained on reweighted data (misclassified samples get higher weight).

  • Final prediction: $$\displaystyle \hat{y} = \text{sign}\left( \sum_{b=1}^{B} \alpha_b h_b(x) \right) $$, where $$\displaystyle \alpha_b = \frac{1}{2} \ln \frac{1 - \epsilon_b}{\epsilon_b} $$.

• Gradient Boosting:

  • Sequentially fits residuals (negative gradients) of loss function.

  • Each new learner corrects errors of previous ensemble.

  • Uses gradient descent in function space.

3.3 Comparative Analysis: Bagging vs. Boosting

3.4 Ensemble Robustness

• Why Ensembles Reduce Overfitting:

  Averaging multiple models reduces variance (law of large numbers). Diversity ensures errors are uncorrelated and cancel out.

• Theoretical Foundation:

  If base learners have error rate $$\displaystyle < 0.5 $$ and are diverse, ensemble error decreases exponentially with number of learners.

[!TIP]

Exam Key: Bagging for high-variance models (trees), boosting for high-bias models. Random Forest’s feature randomness decorrelates trees.

4. Neural Networks

4.1 Multi-Layer Perceptron (MLP) Architecture

• Structure:

  Input layer → Hidden layer(s) (non-linear activation) → Output layer.

• Activation Functions:

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

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

  • ReLU: $$\displaystyle \text{ReLU}(x) = \max(0, x) $$, sparse activation, mitigates vanishing gradient.

• Universal Approximation Theorem:

  An MLP with one hidden layer and sufficient neurons can approximate any continuous function on compact sets.

4.2 Learning Process: Backpropagation

1. Forward Propagation: Compute output $\hat{y}$ layer by layer.

2. Loss Calculation: e.g., Mean Squared Error (MSE) $$\displaystyle E = \frac{1}{2} \sum (y - \hat{y})^2 $$.

3. Backward Propagation:

   Compute gradients $$\displaystyle \frac{\partial E}{\partial w} $$ via chain rule from output to input.

4. Weight Update:

   $$\displaystyle w_{ij} \leftarrow w_{ij} - \eta \frac{\partial E}{\partial w_{ij}} $$, where $\eta$ = learning rate.

4.3 Least Squares Methods in Neural Networks

• Least Squares Error as Loss: $$\displaystyle E = \frac{1}{2} \| \mathbf{y} - \hat{\mathbf{y}} \|^2 $$.

• Connection to Linear Regression:

  If output layer is linear (no activation) and hidden layer uses linear activation, MLP reduces to linear regression. With non-linear hidden layers, it becomes non-linear regression.

[!TIP]

Common Pitfall: Forgetting that backpropagation requires differentiable activation functions (ReLU is piecewise linear, differentiable except at 0).

5. Reinforcement Learning

5.1 Foundations: Markov Decision Processes (MDPs)

• Components:

  • $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')$: Immediate reward.

  • $\gamma$: Discount factor ($$\displaystyle 0 \leq \gamma < 1 $$).

• Bellman Equations:

  • State-Value Function: $$\displaystyle V^\pi(s) = \sum_{a} \pi(a|s) \sum_{s'} P(s'|s,a) [R(s,a,s') + \gamma V^\pi(s')] $$

  • Optimal State-Value: $$\displaystyle V^*(s) = \max_a \sum_{s'} P(s'|s,a) [R(s,a,s') + \gamma V^*(s')] $$

  • Action-Value Function: $$\displaystyle Q^\pi(s,a) = \sum_{s'} P(s'|s,a) [R(s,a,s') + \gamma \sum_{a'} \pi(a'|s') Q^\pi(s',a')] $$

5.2 Planning Algorithms

• Value Iteration:

  1. Initialize $V(s)$ arbitrarily.

  2. Iterate: $$\displaystyle V_{k+1}(s) \leftarrow \max_a \sum_{s'} P(s'|s,a)[R(s,a,s') + \gamma V_k(s')] $$.

  3. Stop when $$\displaystyle \Delta < \theta $$ (small threshold).

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

• Policy Iteration:

  1. Initialize policy $\pi$.

  2. Policy Evaluation: Solve $$\displaystyle V^\pi(s) = \sum_{a} \pi(a|s) \sum_{s'} P(s'|s,a)[R(s,a,s') + \gamma V^\pi(s')] $$ (system of linear equations).

  3. Policy Improvement: $$\displaystyle \pi_{\text{new}}(s) = \arg\max_a \sum_{s'} P(s'|s,a)[R(s,a,s') + \gamma V^\pi(s')] $$.

  4. Repeat until policy stable.

5.3 Temporal Difference (TD) Learning

• TD(0) Update:

  $$\displaystyle V(s) \leftarrow V(s) + \alpha [r + \gamma V(s') - V(s)] $$, where $\alpha$ = step size.

• Bootstrapping: Update based on current estimate $V(s')$ (like DP), not full return.

• vs Monte Carlo (MC):

  | TD Learning | Monte Carlo | |---|---| | Bootstrapping (updates from other estimates) | Full returns (waits until episode end) | | Lower variance, some bias | Unbiased, high variance | | Can learn from incomplete episodes | Requires complete episodes | | More sample efficient | Less sample efficient |

5.4 Model-Free Control Algorithms

• Q-learning (Off-policy):

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

  • Learns optimal $$\displaystyle Q^* $$ independent of behavior policy (greedy in the limit).

• SARSA (On-policy):

  • Update: $$\displaystyle Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma Q(s',a') - Q(s,a)] $$, where $a'$ is action actually taken.

  • More conservative, accounts for exploration.

• Exploration-Exploitation Dilemma:

  • $\epsilon$-greedy: With probability $\epsilon$, random action; else greedy.

  • Softmax: Sample action proportionally to $$\displaystyle e^{Q(s,a)/\tau} $$ (temperature $\tau$).

5.5 Policy Gradient Methods

• REINFORCE (Monte Carlo Policy Gradient):

  • Update policy parameters $\theta$:

    $$\displaystyle \theta \leftarrow \theta + \alpha \nabla_\theta \log \pi_\theta(a|s) G_t $$,

    where $$\displaystyle G_t $$ = total return from time $t$.

  • Uses full trajectory, high variance.

• Actor-Critic:

  • Actor: Policy $$\displaystyle \pi_\theta $$ updated via policy gradient.

  • Critic: Value function $$\displaystyle V_w(s) $$ or $$\displaystyle Q_w(s,a) $$ estimates to reduce variance.

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

• Advantages over Value-Based:

  • Can learn stochastic policies (important in partial observability).

  • Better for continuous action spaces.

5.6 Advanced Topics

• Generative Adversarial Imitation Learning (GAIL):

  • Idea: Learn policy by mimicking expert demonstrations, without reward function.

  • Mechanism: Adversarial training— discriminator distinguishes expert vs. agent trajectories, policy updated to fool discriminator.

    Equivalent to inverse RL with cost function from discriminator.

• Recent Trends in RL Architectures:

  • Deep RL: Combine deep neural networks with RL (e.g., DQN, PPO).

  • Model-Based RL: Learn environment model, plan with it (e.g., Dyna-Q).

  • Hierarchical RL: Decompose tasks into subtasks with options/meta-actions.

[!TIP]

Exam Focus: Distinguish Q-learning (off-policy, max) vs SARSA (on-policy, actual). GAIL vs standard RL: GAIL uses demonstrations, no reward engineering.

6. Optimization and Model Evaluation

6.1 Gradient Descent Techniques

• Batch GD: Update after full dataset. Slow, stable convergence.

• Stochastic GD (SGD): Update after each sample. Noisy, fast, can escape local minima.

• Mini-Batch GD: Compromise—update after mini-batch (e.g., 32, 64 samples). Most common in practice.

• Gradient Descent Delta Rule: For perceptron: $$\displaystyle \Delta w = \eta (t - y) x $$, where $t$ = target, $y$ = output.

• Convergence & Scheduling: Learning rate decay (e.g., $$\displaystyle \eta_t = \eta_0 / (1 + \text{decay} \times t) $$) to stabilize.

6.2 Implementation in TensorFlow

import tensorflow as tf

model = tf.keras.Sequential([...])

optimizer = tf.keras.optimizers.SGD(learning_rate=0.01)

for epoch in range(epochs):

    with tf.GradientTape() as tape:

        loss = compute_loss(model, x_batch, y_batch)

    gradients = tape.gradient(loss, model.trainable_variables)

    optimizer.apply_gradients(zip(gradients, model.trainable_variables))

• Automatic Differentiation: tf.GradientTape records operations for gradient computation.

• Optimizers: SGD, Adam, RMSprop.

6.3 Evaluation Metrics for Classification

• Confusion Matrix:

  | | Predicted Positive | Predicted Negative | |---|---|---| | Actual Positive | TP | FN | | Actual Negative | FP | TN |

• Precision = $$\displaystyle \frac{TP}{TP+FP} $$ (exactness).

• Recall = $$\displaystyle \frac{TP}{TP+FN} $$ (completeness).

• F1-Score = $$\displaystyle 2 \times \frac{\text{Precision} \times \text{Recall}}{\text{Precision} + \text{Recall}} $$ (harmonic mean).

• ROC Curve: Plot TPR vs FPR at various thresholds. AUC = area under curve.

6.4 Overfitting and Underfitting

• Bias-Variance Decomposition:

  $$\displaystyle \text{Error} = \text{Bias}^2 + \text{Variance} + \text{Irreducible Error} $$.

  • High bias → underfitting (simple model).

  • High variance → overfitting (complex model).

• Regularization:

  • L1 (Lasso): $$\displaystyle \lambda \sum |w| $$, induces sparsity.

  • L2 (Ridge): $$\displaystyle \lambda \sum w^2 $$, shrinks weights.

  • Dropout: Randomly deactivate neurons during training.

• Cross-Validation:

  • Holdout: Split data into train/test (e.g., 70/30).

  • k-Fold CV: Rotate $k$ folds as test set, average performance.

6.5 Loss Functions

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

• Classification: Cross-Entropy

  • Binary: $$\displaystyle -\frac{1}{n} \sum [y \log \hat{y} + (1-y) \log(1-\hat{y})] $$.

  • Multi-class: $$\displaystyle -\frac{1}{n} \sum_{i=1}^{n} \sum_{c=1}^{C} y_{ic} \log \hat{y}_{ic} $$.

• SVM: Hinge Loss: $\max(0, 1 - y \cdot \hat{y})$.

[!TIP]

Exam Focus: Know formulas for precision, recall, F1. Understand bias-variance tradeoff and when to use L1 vs L2.

7. Practical Implementation with Python

7.1 Data Handling and Extraction

• CSV: import pandas as pd; df = pd.read_csv('file.csv')

• JSON: df = pd.read_json('file.json') or import json; data = json.load(open('file.json'))

• Web Scraping:

  
  import requests
  
  from bs4 import BeautifulSoup
  
  response = requests.get(url)
  
  soup = BeautifulSoup(response.content, 'html.parser')
  
  

7.2 Numerical Computing with NumPy

• Array Operations: np.array(), np.dot(), np.transpose().

• Linear Algebra: np.linalg.inv(A) for matrix inverse, np.linalg.eig() for eigenvalues.

• Statistics: np.mean(arr), np.var(arr), np.std(arr).

7.3 Data Visualization with Matplotlib

import matplotlib.pyplot as plt

# Bar chart

subjects = ['English', 'Hindi', 'Maths', 'Science', 'GK']

marks = [69, 90, 76, 88, 91]

plt.bar(subjects, marks)

plt.xlabel('Subject'); plt.ylabel('Marks'); plt.title('Student Marks')

plt.show()

• Histogram: plt.hist(data, bins=10)

• Scatter Plot: plt.scatter(x, y)

7.4 Text Processing Libraries

• NLTK: Tokenization (word_tokenize), stemming (PorterStemmer), lemmatization (WordNetLemmatizer).

• spaCy: Industrial-strength NLP, pre-trained models, entity recognition.

• Vectorization:

  • Bag-of-Words: CountVectorizer() from sklearn.feature_extraction.text.

  • TF-IDF: TfidfVectorizer(), weights words by inverse document frequency.

[!TIP]

Exam Practicals: Be ready to write concise code for reading files, matrix inversion (np.linalg.inv), and basic plots. Know key functions for text preprocessing.