MACHINE LEARNING

UNIT II -- Complete Study Notes

GGSIPU Syllabus | [Link] AIML

Supervised Learning: Regression * Classification

KNN * Naive Bayes * Decision Trees * SVM * Random Forest

UNIT II SYLLABUS -- Supervised Learning

OK Linear Regression | Multiple Regression | Logistic Regression

OK Classification Concepts | K-Nearest Neighbor (KNN) | Naive Bayes

OK Decision Trees | Support Vector Machine (SVM) | Random Forest

ML Unit II Notes | GGSIPU | [Link] AIML Page 1

 1. Supervised Learning -- Overview
In Supervised Learning, the model is trained on a labelled dataset where each input X has a known output Y.
The algorithm learns a mapping f(X) -> Y and uses it to predict outputs for new, unseen inputs.

Category Goal Output Type Key Algorithms

Regression Predict a continuous value Real number Linear Reg, Multiple Reg, Ridge, Lasso

Classification Assign input to a category Discrete label Logistic Reg, KNN, Naive Bayes, SVM,
DT, RF

Supervised Learning Workflow

1. Collect labelled data -> 2. Pre-process -> 3. Train model -> 4. Evaluate -> 5. Predict on new data

Train/Test Split: Typically 80:20 or 70:30. Use cross-validation to reduce variance in evaluation.

ML Unit II Notes | GGSIPU | [Link] AIML Page 2

 2. Linear Regression
Linear Regression models the relationship between a single independent variable X and a continuous
dependent variable Y by fitting a straight line through the data.

Equation of Simple Linear Regression

Y = b0 + b1*X + e
Where: Y = predicted output | X = input feature | b0 = intercept | b1 = slope | e = error term

Finding the Best Fit Line -- Ordinary Least Squares (OLS)

The goal is to minimize the Sum of Squared Errors (SSE) between actual and predicted values.

OLS Formulas

b1 = Sum[(Xi - X_mean)(Yi - Y_mean)] / Sum[(Xi - X_mean)^2]

b0 = Y_mean - b1 * X_mean

SSE = Sum(Yi - Y_predicted)^2 <-- this is what we minimize

Assumptions of Linear Regression

Assumption Description Violation Fix

Linearity Relationship between X and Y is linear Use polynomial or non-linear regression

Independence Observations are independent of each other Check for autocorrelation (Durbin-Watson)

Homoscedasticity Constant variance of residuals (errors) Log transform the target variable

Normality Residuals are normally distributed Check Q-Q plot; use robust regression

No Multicollinearity Features are not highly correlated with each Remove/combine correlated features; use
other PCA

Evaluation Metrics for Regression

Metric Formula Interpretation

MAE (Mean Absolute Mean(|Yi - Y_pred|) Average absolute error; robust to outliers
Error)

MSE (Mean Squared Mean((Yi - Y_pred)^2) Penalizes large errors more; sensitive to outliers
Error)

RMSE (Root MSE) sqrt(MSE) Same unit as Y; easier to interpret than MSE

R-squared (R2) 1 - SSE/SST Proportion of variance explained (0 to 1; higher =

better)

Adjusted R2 1 - [(1-R2)(n-1)/(n-k-1)] R2 penalized for extra features; use for multiple

regression

EXAM TIPS

* SSE minimization (OLS) formula for b0 and b1 -- often asked in numericals

* R-squared vs Adjusted R-squared -- difference is important for multiple regression

ML Unit II Notes | GGSIPU | [Link] AIML Page 3

 * Assumptions of linear regression -- list all 5 with one-line explanation each

* MAE vs MSE vs RMSE -- which penalizes outliers more? (Ans: MSE/RMSE)

ML Unit II Notes | GGSIPU | [Link] AIML Page 4

 3. Multiple Regression
Multiple Regression extends linear regression to use two or more independent variables to predict a continuous
outcome.

Equation of Multiple Linear Regression

Y = b0 + b1*X1 + b2*X2 + ... + bn*Xn + e

Each bi is the coefficient for feature Xi, showing how much Y changes when Xi changes by 1 unit, holding all
other features constant.

Regularization in Regression (to prevent overfitting)

Method Penalty Added to Loss Effect When to Use

Ridge (L2) lambda * Sum(bi^2) Shrinks coefficients; none Many small/medium features
become exactly zero

Lasso (L1) lambda * Sum(|bi|) Drives some coefficients to Sparse feature space
exactly zero (feature selection)

Elastic Net Mix of L1 + L2 Balances feature selection and When both needed
coefficient shrinkage

Multicollinearity Problem

Problem: When two or more independent variables are highly correlated, coefficients become unstable and
unreliable.

Detection: VIF (Variance Inflation Factor). VIF > 10 indicates serious multicollinearity.

Fix: Remove one of the correlated features, combine them, or use Ridge/PCA.

ML Unit II Notes | GGSIPU | [Link] AIML Page 5

 4. Logistic Regression
Despite its name, Logistic Regression is a classification algorithm. It predicts the probability that an input
belongs to a particular class (0 or 1) using the Sigmoid function.

Sigmoid (Logistic) Function

P(Y=1 | X) = 1 / (1 + e^(-z))
where z = b0 + b1*X1 + b2*X2 + ... + bn*Xn (the linear combination)

Output: always between 0 and 1. If P >= 0.5 -> Class 1; if P < 0.5 -> Class 0 (default threshold)

Why not Linear Regression for Classification?

* Linear regression can predict values outside [0,1], which is not valid for probabilities.
* Logistic regression uses log-odds (logit) to model the probability correctly.
* Log-Odds (Logit) = log[P/(1-P)] = b0 + b1*X1 + ... -- this is linear, but the probability is S-shaped.

Types of Logistic Regression

Type Output Classes Example

Binary 2 classes (0 or 1) Spam / Not Spam, Disease / Healthy

Multinomial 3+ unordered classes Classify news: Sports/Politics/Tech

Ordinal 3+ ordered classes Rating: Poor / Average / Good / Excellent

Cost Function: Log Loss (Binary Cross-Entropy)

Log Loss Formula

Loss = -[Y*log(P) + (1-Y)*log(1-P)]

Optimized using Gradient Descent (no closed-form solution like OLS).

Gradient Descent updates: bi = bi - learning_rate * dLoss/dbi

Evaluation Metrics for Classification

Metric Formula What it Measures

Accuracy (TP+TN)/(TP+TN+FP+FN) Overall correct predictions (misleading for imbalanced data)

Precision TP / (TP+FP) Of predicted positives, how many are truly positive

Recall TP / (TP+FN) Of actual positives, how many were correctly identified

F1-Score 2 * Precision * Recall / (P+R) Harmonic mean; balances Precision and Recall

AUC-ROC Area under ROC curve Discriminative power across all thresholds (1.0 = perfect)

Specificity TN / (TN+FP) Of actual negatives, how many were correctly identified

Confusion Matrix

TP (True Positive): Predicted positive, actually positive

TN (True Negative): Predicted negative, actually negative

ML Unit II Notes | GGSIPU | [Link] AIML Page 6

 FP (False Positive / Type I Error): Predicted positive, actually negative

FN (False Negative / Type II Error): Predicted negative, actually positive

EXAM TIPS

* Sigmoid function formula and shape (S-curve) -- draw it!

* Log Loss formula -- understand why not MSE for classification

* Confusion matrix: TP, TN, FP, FN -- draw 2x2 table in exam

* Precision vs Recall tradeoff -- when do you prefer one over the other?

* Linear vs Logistic regression -- key difference is the output type and sigmoid

ML Unit II Notes | GGSIPU | [Link] AIML Page 7

 5. K-Nearest Neighbor (KNN)
KNN is a simple, non-parametric, lazy learning algorithm. It classifies a new data point based on the majority
class of its K nearest neighbours in the feature space. For regression, it predicts the average of K neighbours'
values.

KNN Algorithm Steps

Step Action Note

Step 1 Choose K (number of neighbours) K is a hyperparameter; odd K avoids ties in binary

classification

Step 2 Calculate distance from new point to all training points Euclidean, Manhattan, or Minkowski distance

Step 3 Sort distances and select K nearest neighbours Pick the K points with smallest distances

Step 4 Vote (Classification) or Average (Regression) Majority class wins for classification

Step 5 Assign predicted class/value to the new point Final prediction

Distance Metrics
Distance Formula Use Case

Euclidean sqrt(Sum(Xi - Yi)^2) Continuous features; most common

Manhattan Sum(|Xi - Yi|) When outliers present; city-block distance

Minkowski (Sum(|Xi-Yi|^p))^(1/p) Generalization; p=2 is Euclidean, p=1 is Manhattan

Hamming Count of differing bits Categorical/binary features

Choosing K -- The Bias-Variance Tradeoff in KNN

K Value Effect Problem

Small K (e.g. K=1) Very flexible decision boundary; fits training High variance; overfitting; sensitive to noise
data closely

Large K (e.g. K=N) Very smooth boundary; averages over many High bias; underfitting; ignores local patterns
points

Optimal K Balance of flexibility and smoothness Found using cross-validation (try odd values; use
elbow method)

KNN Pros and Cons

Pros: Simple, no training phase, naturally handles multi-class, non-parametric (no assumption about data
distribution).

Cons: Slow prediction O(n*d) for large datasets; sensitive to irrelevant features; needs feature scaling
(normalize data!); high memory usage.

Important: Always apply Min-Max or Z-score normalization before KNN -- otherwise features with large scales
dominate distance.

EXAM TIPS

* KNN is lazy learner -- no model built during training; all computation at prediction time

ML Unit II Notes | GGSIPU | [Link] AIML Page 8

 * Effect of K on bias-variance tradeoff -- classic exam question

* Why feature scaling is mandatory for KNN -- large-scale features dominate Euclidean distance

* Distance metrics: Euclidean vs Manhattan -- formula and when to use each

ML Unit II Notes | GGSIPU | [Link] AIML Page 9

 6. Naive Bayes Classifier
Naive Bayes is a probabilistic classifier based on Bayes' Theorem. It assumes all features are conditionally
independent given the class label (the 'naive' assumption), which makes computation tractable even for many
features.

Bayes' Theorem

P(C | X) = P(X | C) * P(C) / P(X)

P(C|X) = Posterior probability of class C given features X

P(X|C) = Likelihood: probability of observing X given class C

P(C) = Prior probability of class C (from training data)

P(X) = Evidence: probability of observing X (same for all classes; ignored in comparison)

Naive Bayes Classification Rule

Prediction

Predicted Class = argmax_C [ P(C) * Product of P(xi | C) for each feature xi ]

The 'naive' assumption: P(X1,X2,...Xn | C) = P(X1|C) * P(X2|C) * ... * P(Xn|C)

Types of Naive Bayes

Type Distribution Assumption Best For

Gaussian NB Features follow Normal distribution Continuous features (e.g. height, weight)

Multinomial NB Features are counts/frequencies Text classification (word counts)

Bernoulli NB Features are binary (0 or 1) Document classification (word present/absent)

Complement NB Complement of each class modelled Imbalanced text data

Zero Probability Problem and Laplace Smoothing

Problem: If a feature value never appears with a class in training, P(xi|C) = 0, making the entire product 0.

Laplace Smoothing: Add a small constant (alpha, usually 1) to all counts:

P(xi | C) = (count(xi, C) + alpha) / (count(C) + alpha * V)

V = number of unique values of feature xi. This prevents zero probabilities.

Naive Bayes Pros and Cons

Pros: Very fast (O(n*d) training); works well with small data; excellent for text classification; handles multi-class
naturally.

Cons: Naive independence assumption rarely holds in real data; poor probability estimates (but classification is
still good); struggles with feature correlations.

EXAM TIPS

* Bayes Theorem formula -- P(C|X) = P(X|C)*P(C)/P(X) -- must memorize

ML Unit II Notes | GGSIPU | [Link] AIML Page 10

 * Why is it called 'Naive'? -- conditional independence assumption

* Laplace Smoothing -- what problem it solves and the formula

* Gaussian vs Multinomial vs Bernoulli NB -- when to use each

* Spam detection example is the classic NB application -- practice a worked example

ML Unit II Notes | GGSIPU | [Link] AIML Page 11

 7. Decision Trees
A Decision Tree is a flowchart-like tree structure where each internal node represents a feature test, each
branch represents an outcome, and each leaf node represents a class label or predicted value. It recursively splits
the data to maximize purity at each node.

Key Terminology
Term Definition

Root Node The topmost node; represents the best splitting feature for the whole dataset

Internal Node A node with children; represents a test on a feature (e.g. Age > 30)

Branch / Edge Outcome of a feature test; path from parent to child node

Leaf Node Terminal node with no children; contains the final class label or value

Depth Length of longest path from root to leaf; controls model complexity

Pruning Removing branches that have little power; reduces overfitting

Splitting Criteria -- How to choose the best feature to split?

Information Gain (ID3 Algorithm)
* Measures reduction in Entropy after a split.

* Entropy H(S) = -Sum[ P(c) * log2(P(c)) ] (P(c) = proportion of class c in set S)

* Information Gain IG(S,A) = H(S) - Sum[ (|Sv|/|S|) * H(Sv) ] for each split v of feature A

* Choose the feature with HIGHEST Information Gain. If IG=0, no information gained. If H=0, pure node.

* Example: H([5+,5-]) = 1.0 (maximum impurity); H([10+,0-]) = 0 (pure leaf)

Gini Impurity (CART Algorithm)

* Measures probability of misclassifying a randomly chosen element.

* Gini(S) = 1 - Sum[ P(c)^2 ] (ranges from 0 = pure to 0.5 = maximum impurity for binary)

* Gini Gain = Gini(parent) - weighted sum of Gini(children)

* Choose the feature with LOWEST Gini Impurity. Computationally faster than entropy.

* Used by sklearn's DecisionTreeClassifier by default.

Variance Reduction (Regression Trees)

* For regression, split on the feature that most reduces variance in the target variable.

* Variance(S) = (1/n) * Sum[(Yi - Y_mean)^2]

* Choose split that minimizes weighted variance of child nodes.

Overfitting and Pruning

Type Description

Pre-pruning (Early Stopping) Stop growing tree before it fully fits: set max_depth, min_samples_split,
min_samples_leaf as stopping criteria

Post-pruning (Reduced Error Grow full tree first, then remove branches that don't improve validation accuracy
Pruning)

ML Unit II Notes | GGSIPU | [Link] AIML Page 12

 Type Description

Cost Complexity Pruning (CCP) Add penalty for tree size to cost function; used by sklearn's ccp_alpha parameter

Algorithms: ID3, C4.5, CART

Algorithm Splitting Criterion Features Notes

ID3 Information Gain (Entropy) Categorical only Biased toward features with many
values

C4.5 Gain Ratio (normalizes IG) Categorical + Continuous Overcomes ID3's bias; handles missing
values

CART Gini Impurity / Variance Both; binary splits only Used by sklearn; creates binary trees;
Reduction handles regression too

EXAM TIPS

* Entropy formula and Information Gain calculation -- numerical questions are common

* Gini Impurity formula -- and compare to Entropy

* ID3 vs C4.5 vs CART -- differences in splitting criterion and feature types

* Overfitting in DT -- pre-pruning vs post-pruning with hyperparameters

* When Entropy = 0 (pure node) and Entropy = 1 (maximum impurity) -- for binary class

ML Unit II Notes | GGSIPU | [Link] AIML Page 13

 8. Support Vector Machine (SVM)
SVM is a powerful supervised learning algorithm that finds the optimal hyperplane which best separates
classes with the maximum margin. It is effective in high-dimensional spaces and works well even when classes
are not linearly separable (using the kernel trick).

Core Concepts
Term Definition

Hyperplane Decision boundary that separates classes. In 2D it's a line; in 3D a plane; in nD a

hyperplane.

Support Vectors The data points closest to the hyperplane (from both classes). They define the margin.

Margin Distance between the hyperplane and the nearest support vectors from each class. SVM
maximizes this.

Hard Margin SVM No misclassifications allowed. Only works for perfectly linearly separable data.

Soft Margin SVM Allows some misclassifications (controlled by C). More practical for real data.

C Parameter Regularization. Small C = wider margin, more misclassification allowed. Large C = narrow
margin, fewer errors.

The Kernel Trick -- Handling Non-Linearly Separable Data

When classes are not linearly separable in the original space, the kernel trick maps data into a
higher-dimensional space where a linear separator exists, without explicitly computing the transformation
(computationally efficient).

Kernel Formula (approximate) Use Case

Linear K(x,y) = x.y Linearly separable data; text classification

Polynomial K(x,y) = (x.y + c)^d Non-linear; polynomial boundary

RBF / Gaussian K(x,y) = exp(-gamma * ||x-y||^2) Most common; works for most non-linear problems

Sigmoid K(x,y) = tanh(alpha*x.y + c) Neural network-like behavior

SVM Hyperparameters

C (Regularization): Controls margin width. Low C = high bias (underfitting). High C = low bias but potential
overfitting.

Gamma (RBF kernel): Controls influence of each training point. Low gamma = far influence (smooth boundary).
High gamma = close influence (complex boundary).

Degree (Polynomial kernel): Degree of the polynomial. Higher degree = more complex boundary.

SVM Pros and Cons

Pros: Works well in high dimensions; effective when features > samples; memory efficient (only support vectors
stored); versatile with kernels.

Cons: Slow on large datasets O(n^2 to n^3); not ideal for noisy data; results hard to interpret; feature scaling
required.

EXAM TIPS

ML Unit II Notes | GGSIPU | [Link] AIML Page 14

 * Hyperplane, Support Vectors, Margin -- define all three clearly

* Hard Margin vs Soft Margin -- when does each apply?

* Kernel Trick -- what problem it solves and list 4 kernels with use cases

* C parameter effect -- high C vs low C on margin and overfitting

* SVM vs Logistic Regression -- SVM maximizes margin; LR maximizes likelihood

ML Unit II Notes | GGSIPU | [Link] AIML Page 15

 9. Random Forest
Random Forest is an ensemble learning method that constructs a large number of Decision Trees during
training and combines their outputs (voting for classification, averaging for regression) to produce a more accurate
and robust prediction.

Building Blocks: Bagging + Random Feature Selection

Step 1 -- Bootstrap Aggregating (Bagging)
* Draw N random samples WITH replacement from training data (= bootstrap sample).

* Train one Decision Tree on each bootstrap sample.

* Each tree sees a slightly different dataset -> diverse trees -> reduces variance.

* About 1/3 of data is not selected for each tree (called 'Out-of-Bag' or OOB samples -- used for validation).

Step 2 -- Random Feature Selection at Each Split

* At each node split, only a RANDOM SUBSET of features is considered (not all features).

* For classification: typically sqrt(total features) features are tried at each split.

* For regression: typically total_features/3 features are tried at each split.

* This decorrelates trees -- prevents all trees from looking similar and making the same errors.

Step 3 -- Aggregation (Ensemble)

* Classification: MAJORITY VOTING -- class predicted by most trees is the final prediction.

* Regression: AVERAGING -- final prediction is the mean of all tree predictions.

* More trees = more stable predictions (but diminishing returns after ~100-500 trees).

Why Random Forest > Single Decision Tree?

Property Single Decision Tree Random Forest

Variance High (very sensitive to training data) Low (averaging reduces variance)

Bias Low (deep tree fits data closely) Slightly higher (but acceptable tradeoff)

Overfitting Prone to overfitting Resistant due to ensemble averaging

Interpretability Easy to visualize and understand Black box (hard to interpret)

Accuracy Lower on complex datasets Higher on most real-world problems

Speed Fast to train and predict Slower (multiple trees)

Feature Importance in Random Forest

Random Forest provides a built-in feature importance score for each feature, measured as the average
decrease in Gini Impurity (or MSE for regression) across all trees when that feature is used for splitting. Higher
score = more important feature.

Key Hyperparameters

ML Unit II Notes | GGSIPU | [Link] AIML Page 16

 Parameter Effect Typical Value

n_estimators Number of trees in the forest; more = better (diminishing 100-500

returns)

max_depth Max depth of each tree; controls complexity None (grow fully) or tune

max_features Features considered at each split; 'sqrt' for classification 'sqrt' or 'log2'

min_samples_split Min samples required to split a node; prevents tiny splits 2-10

oob_score Use OOB samples for validation without a separate val True/False
set

EXAM TIPS

* Bagging vs Boosting -- Random Forest uses Bagging (parallel trees); AdaBoost/XGBoost uses Boosting (sequential)

* How Random Forest reduces variance -- ensemble averaging and OOB validation

* Feature importance -- how it is calculated (Gini decrease) -- common 5-mark question

* Random Forest vs Decision Tree -- 6-point comparison table is a classic exam format

* max_features = sqrt(n) for classification -- this is the standard rule to remember

ML Unit II Notes | GGSIPU | [Link] AIML Page 17

 10. Algorithm Comparison -- All Supervised Learning Models
Algorithm Type Key Idea Pros Cons Best For

Linear Reg. Regression Fit best line minimizing Simple, interpretable Assumes linearity Continuous output, linear
SSE relationship

Multiple Reg. Regression Multiple features -> Handles many Multicollinearity Multi-feature prediction
OLS/Regularization features issue problems

Logistic Reg. Classification Sigmoid maps linear to Probabilistic, fast Not for non-linear Binary/multi-class,
probability data linearly separable

KNN Both Vote of K nearest Simple, no training Slow prediction, Small datasets,
neighbours needed needs scaling non-linear boundary

Naive Bayes Classification Bayes Theorem + Very fast, good for Naive independence Text classification, spam
independence text assumption detection

Decision Tree Both Recursive feature-based Interpretable, no Overfits easily Mixed features, rule
splits scaling extraction

SVM Both Maximum margin High-dim, kernel Slow, hard to High-dimensional, clear
hyperplane + kernels versatility interpret margin data

Random Both Ensemble of Decision High accuracy, robust Slow, black box General-purpose,
Forest Trees (Bagging) handles non-linearity

UNIT II -- Quick Revision Summary

Topic Key Points to Remember

Linear Regression Y=b0+b1X; OLS minimizes SSE; R-squared measures fit; 5 assumptions

Multiple Regression Multiple features; Adjusted R2; Ridge/Lasso prevent overfitting; VIF for multicollinearity

Logistic Regression Sigmoid function; Log Loss; Confusion Matrix; Precision/Recall/F1/AUC

KNN Lazy learner; K controls bias-variance; always normalize; Euclidean/Manhattan distance

Naive Bayes Bayes theorem; naive independence; Laplace smoothing; Gaussian/Multinomial/Bernoulli

types

Decision Trees Entropy/IG or Gini; ID3/C4.5/CART; Pre/Post pruning; overfitting risk

SVM Max-margin hyperplane; support vectors; kernel trick (RBF, Linear, Poly); C and gamma

Random Forest Bagging + random features; majority vote; OOB validation; feature importance; robust to
overfitting

EXAM TIPS

* GATE 2027: Focus on Entropy/IG numericals, SVM margin concepts, Bayesian classifier derivation

* 10-mark: Compare all 8 algorithms with pros/cons and real-world applications

* 5-mark numericals: KNN classification example, Naive Bayes spam example, Entropy calculation

* Draw diagrams: Sigmoid curve, Decision Tree, SVM margin with support vectors

* Logistic Reg. vs Linear Reg -- this comparison appears in almost every exam

ML Unit II Notes | GGSIPU | [Link] AIML Page 18

 UNIT II -- Question and Answer Bank
Q1. What is Linear Regression? Explain OLS method with formulas. [5 marks]
Linear Regression models the relationship between one independent variable X and a continuous dependent variable Y
using: Y = b0 + b1*X + e.
The Ordinary Least Squares (OLS) method finds b0 and b1 by minimizing the Sum of Squared Errors (SSE = Sum(Yi -
Y_predicted)^2).
Formulas: b1 = Sum[(Xi - X_mean)(Yi - Y_mean)] / Sum[(Xi - X_mean)^2]; b0 = Y_mean - b1 * X_mean.
Evaluation: R-squared = 1 - SSE/SST measures the proportion of variance explained by the model.

Q2. What is Logistic Regression? How does it differ from Linear Regression? [5 marks]
Logistic Regression is a classification algorithm that predicts the probability of a binary outcome using the Sigmoid
function: P(Y=1|X) = 1 / (1 + e^(-z)) where z is the linear combination of inputs.
Differences: Linear Regression predicts continuous values; Logistic Regression predicts probabilities (0 to 1). Linear
uses MSE as loss; Logistic uses Log Loss (Binary Cross-Entropy). Linear has a straight-line output; Logistic has an
S-shaped sigmoid output. Linear can predict any real number; Logistic output is always between 0 and 1.

Q3. Explain the KNN algorithm with its distance metrics and effect of K. [5/10 marks]
KNN (K-Nearest Neighbor) is a lazy, non-parametric algorithm. Steps: (1) Choose K; (2) Compute distance from new
point to all training points; (3) Select K nearest neighbours; (4) Assign majority class (classification) or average value
(regression).
Distance metrics: Euclidean = sqrt(Sum(Xi-Yi)^2); Manhattan = Sum(|Xi-Yi|); Minkowski is the general form.
Effect of K: Small K -> high variance, overfitting, sensitive to noise. Large K -> high bias, underfitting, over-smooth
boundary. Optimal K found via cross-validation.
Important: Feature scaling (normalization) is mandatory before KNN.

Q4. Explain Naive Bayes with Bayes' Theorem and Laplace Smoothing. [5/10 marks]
Bayes' Theorem: P(C|X) = P(X|C) * P(C) / P(X). Naive Bayes applies this with the 'naive' assumption that all features
are conditionally independent given class C.
Prediction: Choose class C that maximizes P(C) * Product[P(xi|C)].
Types: Gaussian NB for continuous features; Multinomial NB for word counts; Bernoulli NB for binary features.
Laplace Smoothing: Adds alpha (usually 1) to all counts to prevent zero probabilities when a feature value is unseen
for a class: P(xi|C) = (count(xi,C) + alpha) / (count(C) + alpha*V).
Application: Spam detection -- calculate P(spam|words) vs P(not spam|words) and classify.

Q5. Explain Decision Trees with Entropy, Information Gain, and Gini Impurity. [10 marks]
A Decision Tree recursively splits data on feature tests to maximize node purity.
Entropy: H(S) = -Sum[P(c)*log2(P(c))]. Ranges from 0 (pure) to 1 (maximum impurity for binary). Example: H([5+,5-]) =
-0.5*log2(0.5) - 0.5*log2(0.5) = 1.0.
Information Gain: IG(S,A) = H(S) - Sum[(|Sv|/|S|)*H(Sv)]. Choose the feature with HIGHEST IG. Used by ID3
algorithm.
Gini Impurity: Gini(S) = 1 - Sum[P(c)^2]. Ranges from 0 (pure) to 0.5 (max impurity for binary). Used by CART;
computationally faster than Entropy.
Algorithms: ID3 (categorical, Info Gain), C4.5 (Gain Ratio, handles continuous), CART (Gini, binary splits).
Pruning: Pre-pruning = max_depth, min_samples_split; Post-pruning = remove branches on validation set.

ML Unit II Notes | GGSIPU | [Link] AIML Page 19

 Q6. Explain SVM with the concept of maximum margin and kernel trick. [5/10 marks]
SVM finds the optimal hyperplane that separates classes with maximum margin.
Key terms: Hyperplane = decision boundary; Support Vectors = closest points to hyperplane from each class; Margin =
2/||w|| distance between support vectors.
Soft Margin (C parameter): Allows some misclassifications. Small C = wide margin, more errors allowed. Large C =
narrow margin, fewer errors but risk of overfitting.
Kernel Trick: Maps data to higher-dimensional space where linear separation is possible. Kernels: Linear (K=x.y),
Polynomial (K=(x.y+c)^d), RBF/Gaussian (K=exp(-gamma*||x-y||^2)), Sigmoid.
RBF is the default and works for most non-linear classification problems.

Q7. Explain Random Forest. How does it differ from a single Decision Tree? [5/10 marks]
Random Forest is an ensemble of Decision Trees built using Bagging + Random Feature Selection.
Steps: (1) Draw N bootstrap samples with replacement; (2) Train one Decision Tree on each, considering only sqrt(d)
features at each split; (3) Final prediction = majority vote (classification) or average (regression).
vs Decision Tree: DT has high variance and overfits; RF reduces variance by averaging diverse trees. DT is
interpretable; RF is a black box. DT is fast; RF is slower. RF provides feature importance scores.
OOB Score: ~1/3 of samples not used per tree are used for validation (Out-of-Bag), giving a free validation score
without a separate validation set.

Q8. Compare and contrast all 8 supervised learning algorithms covered in Unit II. [10 marks]
See the comparison table on the previous page for a structured overview. In paragraph form:
Linear/Multiple Regression are for continuous outputs, interpretable, but assume linearity. Logistic Regression
extends regression to classification using Sigmoid, fast and probabilistic. KNN is lazy, instance-based, requires no
training but is slow at prediction and needs scaling. Naive Bayes is the fastest, works extremely well for text, but
assumes feature independence. Decision Trees are interpretable and handle mixed features but overfit without
pruning. SVM is powerful in high-dimensional spaces and uses kernels for non-linearity but is slow on large data.
Random Forest is the most robust general-purpose algorithm, trading interpretability for accuracy.

ML Unit II Notes | GGSIPU | [Link] AIML Page 20