Machine Learning (BOE073 / KOE073)

Complete Study Notes for AKTU [Link] 4th Year

Dr. A.P.J. Abdul Kalam Technical University (AKTU)
[Link] CSE-AI/ML, AI&ML, CS&IT – 4th Year (2023-24, 2024-25, 2025-26 Curriculum)

Cross-Verification Note
✅ All topics in these notes have been cross-verified against the official AKTU syllabus
(BOE073/KOE073 Machine Learning)
Source: AKTU 2023-24, 2024-25, 2025-26 Syllabus for [Link] Computer Science Engineering
(CSE)

UNIT 1 – INTRODUCTION TO MACHINE

LEARNING
1.1 What is Machine Learning?
Definition
Machine Learning (ML) is a subset of Artificial Intelligence that enables computers to learn
from data and make predictions or decisions without being explicitly programmed for
every task[1][2].

Traditional Approach vs. Machine Learning

Aspect Traditional Programming Machine Learning

Input Data + Rules Data + Examples
Process Fixed Instructions Learning Algorithm
Output Predetermined Result Learned Model → Prediction

Real-World Example
Spam Email Detection:
Input: Email text, sender, subject
Output: Spam / Not Spam
How it learns: ML model studies thousands of labeled emails and learns patterns of
spam vs. legitimate emails
1.2 Types of Machine Learning
1.2.1 Supervised Learning
Definition: Model trained on labeled data (input-output pairs). Goal: Learn a function that
maps input → output[1].
Two Subcategories:

Classification (Categorical Output)

Output is a class label (discrete)
Examples: Email spam classification, disease diagnosis, image recognition

Regression (Continuous Output)

Output is a numerical value (continuous)
Examples: House price prediction, temperature forecasting, stock price estimation

1.2.2 Unsupervised Learning

Definition: Model trained on unlabeled data. Goal: Discover hidden patterns, structures, or
relationships[2].

Common Tasks:
Clustering: Group similar data points (e.g., customer segmentation)
Dimensionality Reduction: Reduce features while preserving information
Anomaly Detection: Find unusual/outlier data

1.2.3 Semi-Supervised Learning

Definition: Uses small amount of labeled data + large amount of unlabeled data[3].
Why useful: Labeling data is expensive/time-consuming. Semi-supervised methods
leverage unlabeled data to improve performance.

Example: Photo tagging with few manually tagged photos and many untagged photos in
database.

1.2.4 Reinforcement Learning (RL)

Definition: Agent learns through interaction with an environment by receiving rewards or
penalties for actions[1].
Key Components:
Agent: Decision-maker (e.g., game AI)
Environment: System the agent interacts with
Action: Choice the agent makes
Reward/Penalty: Feedback signal (positive or negative)
Policy: Strategy that maps states → actions

Example: Game-Playing Bot learning to improve through reward feedback.

1.3 Applications of Machine Learning
Machine learning has diverse applications across industries[2]:
Healthcare: Disease diagnosis, drug discovery, patient outcome prediction
Finance: Credit scoring, fraud detection, stock prediction, loan approval
E-commerce: Product recommendation, customer segmentation, demand
forecasting
Autonomous Vehicles: Lane detection, obstacle recognition, traffic sign
classification
Natural Language Processing: Language translation, sentiment analysis, text
generation, chatbots
Computer Vision: Image recognition, face detection, object detection, medical
imaging
Cybersecurity: Intrusion detection, malware classification, spam filtering

1.4 Well-Posed Learning Problem

Definition (Tom Mitchell, 1997)
A computer program is said to learn from experience E with respect to some task T and
performance measure P if its performance at tasks in T, as measured by P , improves with
experience E[1].

Three Components (E, T, P)

Example: Email Spam Classification

Component Definition Explanation

Classify emails as spam / not
Task (T) What to do
spam
Experience What to learn Training dataset of 10,000
(E) from labeled emails
Performanc How to measure Classification accuracy,
e (P) success precision, recall

Learning Verification: If accuracy improves from 80% to 95% as more training data is
added → Program is Learning!

1.5 Designing a Learning System

Step-by-Step Process
Step 1: Problem Definition
Clearly state the task (classification, regression, clustering?)
Identify inputs and outputs
Define success metrics
Step 2: Data Collection

Gather relevant, high-quality data

Ensure sufficient quantity
Check data quality (missing values, outliers, noise)
Step 3: Data Preprocessing
Handle missing values (remove, fill, or interpolate)
Normalize/Standardize features
Remove outliers
Encode categorical variables

Step 4: Feature Engineering

Select relevant features
Create new features from existing ones
Reduce dimensionality if needed
Step 5: Model Selection

Choose appropriate algorithm based on problem type

Consider data characteristics
Step 6: Model Training
Fit the model to training data
Algorithm learns optimal parameters/weights

Step 7: Model Evaluation

Test on unseen test data
Calculate performance metrics
Check for overfitting/underfitting
Step 8: Hyperparameter Tuning

Adjust model parameters

Use cross-validation to validate changes
Repeat training and evaluation
Step 9: Deployment
Deploy trained model to production
Monitor performance on real data
Retrain periodically with new data
1.6 Perspectives and Issues in Machine Learning
Issue 1: Overfitting
Definition: Model learns noise and specific details of training data instead of general
patterns[1].
Consequence:
High accuracy on training data
Poor accuracy on new, unseen data

Solutions:
Use more training data
Reduce model complexity
Use regularization (L1, L2 penalties)
Early stopping

Issue 2: Underfitting
Definition: Model is too simple to capture underlying patterns in data[1].

Consequence:
Poor accuracy on both training and test data
High bias, low variance
Solution:

Increase model complexity

Train longer
Use more features

Issue 3: Data Quality and Bias

Definition: Training data is skewed, noisy, or incomplete[2].
Consequences:
Model inherits data biases
Poor generalization
Unfair/biased predictions on certain groups

Solutions:
Collect balanced, representative data
Data cleaning
Bias detection and mitigation techniques
Issue 4: Scalability
Definition: Algorithms must handle large datasets and high-dimensional data
efficiently[3].
Challenge:
Computational cost grows with data size
Memory constraints
Training time can be prohibitive

Solutions:
Distributed computing
Efficient algorithms
Hardware acceleration (GPUs, TPUs)

Issue 5: Hyperparameter Tuning

Definition: Model has many tunable parameters[1].

Challenge:
Finding optimal hyperparameters manually is tedious
Too many combinations to test
Solutions:

Grid Search
Random Search
Bayesian Optimization

Issue 6: Curse of Dimensionality

Definition: As number of features increases, data becomes sparse, making learning
harder[2].
Challenge:
More features → exponentially more training data needed
Computational cost increases
Overfitting risk increases

Solution:
Dimensionality Reduction (PCA, LDA)
Feature Selection

1.7 Concept Learning and General-to-Specific Ordering

What is Concept Learning?
Definition: Learn a boolean-valued function (True/False) that defines a concept from
examples[1].
Simple Example: Days I Play Tennis
Given attributes like Outlook, Temperature, Humidity, Wind, goal is to predict PlayTennis
(Yes/No).

Hypothesis Space
Definition: Set of all possible concepts/hypotheses that could explain the data[1].
A hypothesis h1 is more general than h2 if h1 covers more instances than h2.

1.8 The Find-S Algorithm

Goal
Find the most specific hypothesis that is consistent with all positive training examples[1].

Algorithm Steps
Initialization: Start with the most specific hypothesis possible: h = [∅, ∅, ∅, ∅]
For Each Positive Example:

1. Check if current hypothesis h matches the example

2. If YES → No change; move to next example
3. If NO → Generalize h minimally to include this example
Ignore Negative Examples: Negative examples are not used (limitation of Find-S).

Limitations of Find-S
1. Ignores negative examples → may find a hypothesis that also covers some negative
examples
2. No mechanism to avoid overfitting
3. Cannot detect inconsistencies
4. Limited hypothesis space → works only with conjunction of attributes

1.9 Version Spaces and Candidate Elimination Algorithm

What is a Version Space?
Definition: The set of all hypotheses that are consistent with the observed training data[1].

If a hypothesis correctly classifies all training examples → it's in the version space
As more data arrives → version space shrinks
Representation: General and Specific Boundaries
General Boundary (G): Set of most general hypotheses in version space
Specific Boundary (S): Set of most specific hypotheses in version space
Version Space: All hypotheses between S and G

Candidate Elimination Algorithm

Goal: Maintain and update S and G as new training examples arrive[1].
Initialization:

G = {most general hypothesis} = ["?", "?", "?", ...]

S = {most specific hypothesis} = [∅, ∅, ∅, ...]
For Each Training Example (x, c):
If Example is POSITIVE (c = Yes):

1. Remove from G any hypothesis that does NOT cover this example
2. Generalize S minimally to include this example
If Example is NEGATIVE (c = No):
1. Remove from S any hypothesis that COVERS this example
2. Specialize G minimally to exclude this example

UNIT 2 – LINEAR MODELS AND DECISION

TREES
2.1 Linear Regression
Overview
Linear Regression is used for predicting continuous values (e.g., price, temperature, salary)
[1].

Mathematical Model
For a single feature:

For multiple features:

Or in vector form:
Where:

= intercept (bias term)

= weights (parameters to learn)
= input features
= predicted output
Goal
Find weights that minimize error between predicted and actual values[1].

Loss Function: Mean Squared Error (MSE)

Where:
= number of training examples
= actual output for example
= predicted output

Learning Algorithm: Gradient Descent

Idea: Iteratively update weights to reduce MSE[1].
Update Rule:

Where:

= learning rate (step size, typically 0.01 to 0.1)

= gradient

Advantages and Disadvantages

Advantages:

Simple, fast, interpretable

Works well for linearly separable data
Low computational cost
Disadvantages:
Assumes linear relationship
Sensitive to outliers
Poor for non-linear patterns

2.2 Logistic Regression

Overview
Despite the name "Regression," Logistic Regression is used for binary classification
(True/False, Yes/No, Spam/Not Spam)[1].
Why Not Linear Regression for Classification?
Linear Regression outputs continuous values (can be negative, > 1)
Classification needs probability between 0 and 1
Solution: Use Logistic (Sigmoid) Function to map output to [0, 1].

Sigmoid Function

Properties:
Output range: [0, 1]
Smooth S-shaped curve
Interpretable as probability

Logistic Regression Model

Decision Rule:
If → predict Class 1
If → predict Class 0

Loss Function: Binary Cross-Entropy

Advantages and Disadvantages

Advantages:
Probabilistic output (confidence)
Works well for binary classification
Interpretable weights
Disadvantages:

Cannot handle multi-class directly

Assumes linear decision boundary
Sensitive to outliers

2.3 Perceptron
Overview
The Perceptron is the simplest neural network—a single-layer classifier for linearly
separable binary classification[1].

Architecture
Input Layer → Weights → Summation → Activation → Output

Mathematical Model
Weighted Sum:
Activation (Step Function):

Perceptron Learning Algorithm

Initialize:
For each training example :
1. Compute prediction:
2. If incorrect ( ):
Update weights:
3. Repeat until no errors (or max iterations)

Perceptron Convergence Theorem

Guarantee: If data is linearly separable, Perceptron converges to a solution[1].
Limitation: If data is not linearly separable, Perceptron never converges.

Limitations
Cannot solve XOR problem (not linearly separable)
Only binary classification
Sensitive to feature scaling

2.4 Support Vector Machines (SVM)

Overview
SVM finds the optimal separating hyperplane that maximizes the margin between two
classes[1].
Key Idea
Problem: Many lines can separate two classes. Which is best?
SVM Solution: Choose line with MAXIMUM MARGIN.

Margin
Definition: Distance from the separating hyperplane to the nearest data point[1].

Intuition:
Larger margin = more confident separation = better generalization
SVM maximizes margin to improve robustness

Mathematical Formulation
For binary classification with labels :
Objective: Maximize margin

Constraints:

Decision Function

If → Class +1
If → Class -1

Support Vectors
Definition: Data points that lie on the margin boundary (closest to hyperplane)[1].

Importance:
Only support vectors matter for the final model
Other points can be removed without changing the boundary

Non-Linear SVM: Kernel Methods

Problem: Real-world data is often not linearly separable[2].

Solution: Kernel Trick – map data to higher dimension where it becomes separable[2].
Common Kernels:
Linear Kernel:
Polynomial Kernel:
RBF (Gaussian) Kernel:
Advantages of SVM
Effective in high dimensions
Memory efficient (support vectors)
Kernels handle non-linear data
Theoretically well-founded

Disadvantages
Slow for very large datasets
Requires feature scaling
Not ideal for multi-class

2.5 Kernel Methods

Overview
Kernel Methods are techniques that allow algorithms to work in high-dimensional spaces
without explicitly computing coordinates in that space[1].

The Kernel Trick

Motivation: Mapping data to high dimension gets expensive.

Solution: Use a function = dot product in high-dimensional space[1].

Kernel Function
A kernel function computes the similarity between two points:

Where is an implicit mapping to high-dimensional space.

Advantages of Kernel Methods

Handle non-linear patterns
Computationally efficient
Flexible (various kernel choices)

Disadvantages
Choosing right kernel is challenging
Kernel parameters need tuning
Less interpretable than linear models

2.6 Decision Trees

Overview
A Decision Tree is a tree-like model used for classification and regression that makes
predictions by learning simple decision rules from features[1].

Structure of a Decision Tree

Components:
Root Node: Top decision node
Internal Nodes: Decision nodes that test attributes
Branches: Outcomes of test (paths)
Leaf Nodes: Final predictions (class labels or values)

Advantages
Easy to understand and interpret
Handles both classification and regression
No feature scaling needed
Fast predictions

Disadvantages
Prone to overfitting
Small changes in data can drastically change tree
Biased toward features with many values

2.7 Decision Tree Learning Algorithm: ID3

Overview
ID3 (Iterative Dichotomiser 3) is a classic algorithm for building decision trees using
Information Gain[1].

Key Concept: Entropy

Definition: Measure of uncertainty or disorder in a dataset[1].

Where:
= proportion of class in set
= number of classes

Entropy Interpretation
Entropy = 0: All examples belong to one class (pure)
Entropy = 1: Equal mix of two classes (maximum uncertainty)
0 < Entropy < 1: Mixed classes (some uncertainty)
Information Gain
Definition: Reduction in entropy after splitting on an attribute[1].

ID3 Algorithm
1. Start at root with all training data.
2. For each attribute, calculate Information Gain.

3. Choose attribute with highest Information Gain.

4. Split dataset based on chosen attribute.
5. Recursively repeat for each subset (until stop condition).

Stopping Criteria
All examples in subset belong to one class (pure)
No more attributes to split on
Subset is empty
Maximum tree depth reached

2.8 C4.5 Algorithm

Improvements over ID3:
1. Handles continuous attributes: Finds optimal threshold for splits
2. Handles missing values: Uses surrogates or distributes examples
3. Uses Gain Ratio: Avoids bias toward attributes with many values
4. Performs post-pruning: Reduces overfitting

2.9 Issues in Decision Tree Learning

Issue 1: Overfitting
Problem: Tree grows too deep, learns specific noise in training data[1].
Consequence:

High accuracy on training data

Poor accuracy on new data
Solutions:
Use more training data
Reduce model complexity
Use regularization
Issue 2: Feature Selection Bias
Problem: Attributes with many values have higher information gain[1].
Solution: Use Gain Ratio (C4.5) instead of pure gain.

Issue 3: Handling Missing Values

Problem: Some data points have missing feature values[2].

Solutions:
Remove rows with missing values
Impute with mean, median, or most frequent value
Distribute example across branches proportionally

Issue 4: Handling Imbalanced Data

Problem: Classes not equally represented[1].
Solutions:

Class weights (give higher penalty for misclassifying rare class)

Sampling (oversample minority class or undersample majority)

Issue 5: Fragmentation
Problem: Deep trees split data into very small subsets[2].
Consequence:
Difficult to learn patterns from few examples
High variance in deeper nodes

Solution:
Set minimum samples required to split a node
Limit tree depth

2.10 Tree Pruning

Goal
Remove unnecessary branches from a fully grown tree to reduce overfitting and improve
generalization[1].

Two Approaches
Pre-Pruning (Early Stopping)
Done during tree construction.
Stop splitting when:

Information gain is below threshold

Node has fewer than K samples
 Tree depth exceeds maximum
Predicted improvement is negligible
Advantages:

Faster training (stops early)

Disadvantages:
Difficult to choose stopping criteria
May stop too early

Post-Pruning
Done after tree construction.

Process:
1. Build full tree on training data
2. For each non-leaf node:
Remove its subtree
Replace node with most frequent class label
Evaluate on validation set
If validation accuracy improves → keep pruned version
Else → restore subtree
3. Repeat until no improvement
Advantages:

More reliable (based on actual validation data)

Disadvantages:
Requires separate validation set
More expensive computation

2.11 Rule Extraction from Trees

Concept
Convert decision tree paths into IF-THEN rules that are easy to understand and
implement[1].

Process
1. For each path from root to leaf:
Collect all attribute-value conditions along path
Create IF-THEN rule
2. Simplify rules (optional):
Remove redundant conditions
Combine similar rules
Applications
Expert systems
Rule-based decision making
Knowledge discovery
Business intelligence

UNIT 3 – ARTIFICIAL NEURAL NETWORKS

& INSTANCE-BASED LEARNING
3.1 Artificial Neural Networks (ANN)
Overview
ANNs are computational models inspired by biological neurons in the human brain.
They can learn complex patterns through layers of interconnected neurons[1].

Biological Inspiration
Biological Neuron:
Dendrites receive signals
Body processes signals
Axon transmits output

Artificial Neuron:
Inputs
Weights (connection strengths)
Bias
Summation
Activation function
Output

Artificial Neuron Components

1. Inputs: (features)
2. Weights: (connection strengths)
3. Bias: (threshold adjustment)
4. Summation:
5. Activation Function: (introduces non-linearity)

Activation Functions
Why needed: Without activation, stacking layers remains linear[1].
Sigmoid Function

Output range: [0, 1]

Smooth, differentiable
Vanishing gradient problem in deep networks

ReLU (Rectified Linear Unit)

Output range: [0, ∞)

Simple, computationally efficient
Popular in modern networks
Avoids vanishing gradient

Tanh (Hyperbolic Tangent)

Output range: [-1, 1]

Stronger gradients than sigmoid
Zero-centered

Softmax (for multi-class classification)

Output: Probability distribution

Sum to 1

3.2 Perceptron Learning

Overview
Simple single-layer network learning via updates based on prediction errors[1].

Algorithm
Initialize: , learning rate (e.g., 0.1)
For each training epoch:
For each training example (x, y_true):

1. Compute prediction:
2. Compute error:
3. If error ≠ 0:
Update:
Until: Convergence (no errors) or max iterations.

3.3 Multilayer Networks and Backpropagation

Limitation of Single-Layer
Cannot solve non-linearly separable problems (e.g., XOR)
Solution: Multi-layer networks with non-linear activations[1]

Multi-Layer Architecture
Input Layer → Hidden Layers → Output Layer

Each layer transforms data through weighted connections and activation functions.

Forward Propagation
Layer 1 (Hidden):

Layer 2 (Hidden):

Output Layer:

Loss Function
For classification (cross-entropy):

For regression (MSE):

Backpropagation Algorithm
Goal: Compute gradients of loss w.r.t. all weights, then update weights[1].
Steps:
1. Forward Pass: Compute activations layer by layer, compute loss
2. Backward Pass: Start from output layer, compute error at each layer using chain rule
3. Weight Updates: Update weights using computed gradients

Key Hyperparameters

Parameter Role Typical Value

Learning Rate Step size 0.001 - 0.1
Hidden Units Network capacity 32 - 512
Layers Depth 1 - 10
Batch Size Examples per update 16 - 256
Epochs Training iterations 10 - 1000

3.4 Introduction to Deep Learning

Definition
Deep Learning = Neural networks with many hidden layers (typically > 2-3 layers)[1].

Why Deep?
Benefits:
Learn hierarchical representations (simple → complex features)
Automatic feature engineering (no manual feature design)
Better performance on complex tasks (images, NLP, speech)
Example: Image Recognition
Layer 1: Detects edges
Layer 2: Detects shapes
Layer 3: Detects objects
Layer 4: Detects faces/people
Output: High-level concept identification
Popular Deep Architectures

Architec
Purpose Use Case
ture
Feature extraction from Image classification, object
CNN
images detection
Sequential data Time series, language
RNN
processing modeling
Long sequences with Speech recognition, machine
LSTM
memory translation
Transfor Parallel sequence
NLP, language translation
mer processing
Autoenc Unsupervised Dimensionality reduction,
oder representation learning anomaly detection
Image synthesis, data
GAN Generate new data
augmentation

Challenges in Deep Learning

Vanishing Gradient: Gradients become tiny in deep networks
Solution: ReLU, residual connections
Overfitting: More parameters → memorization risk
Solution: Dropout, regularization, more data
Computational Cost: Requires GPU/TPU
Solution: Cloud computing, parallel training
Hyperparameter Tuning: Many parameters to adjust
Solution: AutoML, Bayesian Optimization

3.5 Instance-Based Learning

Overview
Instead of building a global model, store training data and make predictions based on
similarity to stored instances[1].
Motto: "Lazy Learning" – Defer learning until prediction time.
3.5.1 k-Nearest Neighbors (k-NN)
Concept
To predict a new point, find its k nearest neighbors in training data and use their labels[1].

Algorithm
Training Phase: Store all training data (no learning).
Prediction Phase for new point :

1. Calculate distance from to all training points

2. Select k training points with smallest distances
3. Classification: Majority class among k neighbors
4. Regression: Average value of k neighbors

Distance Metrics

Metric Formula Use

Euclidean Continuous features
Manhattan Robust to outliers
Cosine Text, high-dimensional
Hamming Count differences Categorical

Choosing k
k=1: Very sensitive, prone to overfitting
k=3-5: Good balance (common choice)
k=N: Becomes majority class (underfitting)

Rule of thumb: where N = training size[1].

Advantages
Simple, easy to implement
No training time
Works for non-linear patterns

Disadvantages
Lazy Learning: Slow prediction (compute all distances)
Memory: Store entire dataset
Feature Scaling: Sensitive to distance metric
High Dimensionality: Curse of dimensionality
3.5.2 Locally Weighted Regression (LWR)
Concept
Instead of uniform influence, weight nearby points higher when fitting local
regression[1].

Idea
For each test point :
1. Weight all training points by distance from
2. Fit weighted linear regression to nearby points
3. Use fitted model to predict

Weight Function (Gaussian Kernel)

= bandwidth (controls decay rate)

Advantages
Adapts to local patterns
Non-parametric (no global model)

Disadvantages
Expensive (fit regression for each prediction)
Requires careful bandwidth tuning

3.5.3 Radial Basis Function (RBF) Networks

Concept
Use radial basis functions (Gaussian-like bumps) centered at training points as hidden
layer activation[1].

RBF Neuron Activation

= center of RBF neuron

= width parameter
Output: 1 if near center, 0 if far
RBF Network

Hidden layer: N neurons, one per (or subset of) training points
Output layer: Weighted sum of RBF activations

Properties
Local Representation: Each RBF responds to local region
Universal Approximator: Can approximate any function
Interpretable: Basis functions have clear meaning

Advantages
Localized processing
Fast training (compared to ANNs)

Disadvantages
Curse of dimensionality
Center selection non-trivial

3.5.4 Case-Based Reasoning (CBR)

Overview
Solve new problems by retrieving and adapting solutions from similar past cases[1].

4 Rs of CBR
1. RETRIEVE
Find similar past cases to new problem
Use similarity metrics

2. REUSE
Adapt solution from retrieved case
May need adjustment

3. REVISE
Test adapted solution
Modify if needed

4. RETAIN
Store new case and solution
Future reference
Example: Medical Diagnosis
New Patient Problem: Age 45, Fever, Cough, Fatigue
Retrieve: Find similar past patients in database
Reuse: Apply same treatment plan from similar cases

Revise: Check patient-specific factors, adjust if needed

Retain: Add new case to database for future use

Advantages
Leverages domain knowledge
Explainable (based on past cases)
Works with complex, symbolic knowledge

Disadvantages
Requires good case library
Similarity metric design critical
Scalability (large case bases)

UNIT 4 – BAYESIAN LEARNING &

ENSEMBLE METHODS
4.1 Bayes Theorem and Concept Learning
Bayes Theorem

Where:
= Hypothesis
= Data/Evidence
= Prior probability
= Likelihood
= Evidence
= Posterior probability[1]

Intuitive Explanation
Update belief based on evidence:

Before test: Small prior probability of disease

Test result: Positive
After test: Use Bayes theorem to update belief considering false positive rate
Maximum A Posteriori (MAP) Hypothesis
Choose hypothesis with highest posterior probability[1]:

4.2 Maximum Likelihood and Least-Squared Error

Hypotheses
Maximum Likelihood Estimation (MLE)
Goal: Find parameters that maximize probability of observed data[1].

Least-Squared Error (LSE) Hypotheses

For regression: Minimize sum of squared errors[1].

Connection: MLE = LSE

Under Gaussian noise assumption, maximizing log-likelihood equals minimizing squared
error[1].

4.3 Bayes Optimal Classifier

Definition
Theoretically best possible classifier under the Bayesian framework[1].

Decision Rule
For new instance , predict class with maximum posterior probability:

Challenge
Computing exact is expensive with high-dimensional data.

Solution
Naive Bayes = approximate version (next section).
4.4 Naive Bayes Classifier
Key Assumption
Features are conditionally independent given the class[1].

This is usually FALSE, but works surprisingly well in practice!

Model

Training
Estimate probabilities from training data[1]:

Prediction
For new instance, compute class probability for each class:

Choose class with highest probability.

Advantages
Simple, fast training and prediction
Works well despite independence assumption
Requires small training data
Probabilistic output

Disadvantages
Independence assumption often violated
Zero-frequency problem

Laplace Smoothing
Handle zero frequencies by adding 1 to counts[1]:

Where = number of feature values.

4.5 Bayesian Belief Networks
Overview
Graphical probabilistic model representing conditional dependencies between
variables[1].

Representation
Nodes = Random variables
Directed edges = Conditional dependencies
Conditional Probability Tables (CPT) = Local probabilities

Inference
Compute probabilities of interest using the network structure and CPTs.

Advantages
Encodes causal/conditional structure
Efficient representation
Handles uncertainty

Disadvantages
Network structure must be specified
CPT estimation needs data
Inference can be expensive

4.6 EM (Expectation-Maximization) Algorithm

Problem
Data has missing values or hidden (latent) variables[1].

Example: Clustering, Mixture Models.

EM Algorithm (Two Steps)

E-Step (Expectation)
Assume current model parameters
Compute expected values of hidden variables

M-Step (Maximization)
Update model parameters to maximize likelihood
Using expectations from E-step
Iterate
Repeat E and M until convergence[1].

Example: Gaussian Mixture Model (GMM)

Problem: Cluster data from unknown Gaussian distributions[1].
Hidden Variable: Which Gaussian does each point come from?
Iteration:

E-step: Compute probability each point comes from each Gaussian

M-step: Update Gaussian parameters using weighted points
Repeat until convergence

Advantages
Principled probabilistic approach
Handles missing data naturally

Disadvantages
Can converge to local optima
Sensitive to initialization
Computationally expensive

4.7 Ensemble Methods

Concept
Combine multiple weak learners to create a strong learner[1].
Motto: "Wisdom of crowds" – many opinions better than one.

Why Ensemble Works

If learners are:
1. Different (diverse errors)
2. Reasonable (better than random)
Then ensemble reduces:

Variance (averaging cancels out random errors)

Bias (if weak learners correct each other)[1]

4.7.1 Bagging (Bootstrap Aggregating)

Idea
Train multiple models on random samples with replacement of training data[1].

Algorithm
For m = 1 to M:
1. Sample m-th bootstrap sample from training data (with replacement)
2. Train model on bootstrap sample
3. Store model

Prediction: For new instance, get prediction from each model and aggregate.

Bootstrap Sample
Same size as original dataset
Some points repeated, some omitted
Different for each iteration

Benefits
Reduces Variance: Averaging reduces random fluctuations
No increase in Bias: Models trained on full-size samples
Parallel: Different samples can train in parallel

4.7.2 Random Forests

Overview
Bagging of Decision Trees with additional randomness in feature selection[1].

Algorithm
For m = 1 to M:
1. Bootstrap sample training data
2. Grow decision tree:
At each split: Consider random subset of features
Choose best feature from subset
3. Store tree (no pruning)

Prediction: Majority vote (classification) or average (regression)[1].

Key Difference from Bagging

Bagging: Uses all features at each split
Random Forests: Uses random feature subset
Why? Reduces correlation between trees → better ensemble[1].
Hyperparameters

Parameter Effect
n_trees More trees → better (but slower)
max_features Consider √D features at each split
max_depth Limit tree depth
min_samples_split Minimum points to split node

Advantages
Better than single tree
Handles high-dimensional data
Robust to outliers
Feature importances available
Parallelizable

Disadvantages
Less interpretable (many trees)
Slower prediction
More memory

4.7.3 Boosting (AdaBoost)

Idea
Train models sequentially, each focusing on mistakes of previous models[1].

Key Difference from Bagging

Bagging: Models independent, train in parallel
Boosting: Models sequential, each learns from previous[1]

AdaBoost Algorithm
Initialize: weight for each training example
For t = 1 to T:

1. Train weak learner on weighted data

2. Compute error rate
3. Compute learner weight based on accuracy
4. Update example weights:
Increase weight for incorrectly classified examples
Decrease weight for correctly classified examples
5. Normalize weights
Final Prediction: Return weighted sum of weak learners[1].
Intuition
Iteration 1: Learn weak classifier on all data
Iteration 2: Focus on examples missed in iteration 1
Iteration 3: Further focus on remaining hard examples
Final: Combine classifiers with different weights

Advantages
Strong improvements over weak learners
Combines weak hypotheses → strong hypothesis
Theoretically justified

Disadvantages
Sequential (cannot parallelize)
Sensitive to outliers
Requires careful tuning
Overfitting risk if too many iterations

Popular Boosting Methods

Method Features
AdaBoost Exponential weights, single weak learner type
Gradient Boosting Fits residuals sequentially
XGBoost Fast, regularized, handles missing data
LightGBM Memory-efficient, fast training

UNIT 5 – UNSUPERVISED LEARNING &

MODEL EVALUATION
5.1 Clustering
Overview
Group data into clusters such that[1]:
Points in same cluster are similar
Points in different clusters are dissimilar
5.1.1 K-Means Clustering
Algorithm
Initialize: K centroids randomly
While not converged:
1. Assign each point to nearest centroid
2. Update each centroid = mean of assigned points[1]

Key Steps
Random initialization of K cluster centers
Assignment step: Assign each point to nearest center
Update step: Recalculate centers as mean of assigned points
Repeat until convergence

Advantages
Simple, fast
Scales well to large datasets
Easy to implement and understand

Disadvantages
Requires specifying K in advance
Sensitive to initialization
Converges to local optimum
Assumes spherical clusters

5.1.2 Agglomerative Hierarchical Clustering

Bottom-up approach
Start: Each point is own cluster
While > 1 cluster:

1. Find two closest clusters

2. Merge them
Result: Dendrogram (tree of mergings)[1].

Advantages
No need to specify number of clusters
Produces interpretable dendrogram
Can capture hierarchical structure
Disadvantages
Computationally expensive
Cannot undo previous merges
Sensitive to outliers

5.1.3 DBSCAN
Density-based approach
For each point[1]:
If many neighbors within radius ε: Core point
Elif near core point: Border point
Else: Noise/Outlier

Advantages
Finds clusters of arbitrary shape
Identifies outliers
No need to specify number of clusters

Disadvantages
Requires tuning radius ε and minimum points
Sensitive to parameter values
Difficult with varying density clusters

5.2 Dimensionality Reduction

5.2.1 Principal Component Analysis (PCA)
Goal: Reduce features while preserving variance[1].
Method:
1. Find direction of maximum variance
2. Find next orthogonal direction of max variance
3. Repeat K times (K = desired dimensions)

Advantages
Unsupervised approach
Reduces computation and memory
Can visualize high-dimensional data
Removes correlated features
Disadvantages
Components not always interpretable
Requires scaling features
May lose important information

5.2.2 Linear Discriminant Analysis (LDA)

Supervised dimensionality reduction[1]:
Maximize between-class variance
Minimize within-class variance

Advantages
Supervised (uses class labels)
Good for classification
Better than PCA for classification

Disadvantages
Requires labeled data
Assumes normal distribution
Assumes equal class covariances

5.3 Evaluating Machine Learning Models

5.3.1 Data Splits
Standard split:
Training Set (60-70%): Train model
Validation Set (15-20%): Tune hyperparameters
Test Set (15-20%): Final evaluation on unseen data[1]

Best Practices
Randomize data before splitting
Stratified split for imbalanced datasets
Use test set only at the end

5.3.2 Cross-Validation
k-Fold Cross-Validation
Split data into K folds

For k = 1 to K:
Test on fold k
Train on remaining K-1 folds
Record performance
Average performance across folds[1].
Benefits
Uses all data for both training and testing
More reliable estimate
Good for small datasets
Reduces variance in performance estimate

Variants
Stratified k-fold: Maintains class distribution
Leave-One-Out (LOO): Each fold has one sample
Time-Series Split: Respects temporal order

5.3.3 Performance Metrics

Classification Metrics
Confusion Matrix:

Predicted + Predicted -
Actual + TP FN
Actual - FP TN

Metrics[1]:

Accuracy: – Overall correctness

Precision: – How many predicted + were correct?
Recall: – How many actual + were detected?
F1-Score: – Balance of precision and recall

When to use which:

Accuracy: Balanced classes
Precision: Want few false positives
Recall: Want few false negatives
F1: Balance both errors

Regression Metrics
MAE (Mean Absolute Error):
RMSE (Root Mean Squared Error):
R² Score: Proportion of variance explained (0-1, higher is better)[1]
5.3.4 ROC and AUC
ROC (Receiver Operating Characteristic) Curve:
X-axis: False Positive Rate
Y-axis: True Positive Rate
Plot at different classification thresholds[1]
AUC (Area Under Curve):

0.5: Random classifier

1.0: Perfect classifier
Higher AUC = better classifier

Advantages
Threshold-independent
Good for imbalanced datasets
Visual representation of trade-offs

UNIT 6 – ADDITIONAL TOPICS

(REINFORCEMENT LEARNING & GENETIC
ALGORITHMS)
6.1 Reinforcement Learning
Overview
Agent learns through interaction with environment, receiving rewards/penalties for
actions[1].

Key Components
Agent: Decision-maker
Environment: System agent interacts with
State: Current situation
Action: Choice the agent makes
Reward: Feedback signal
Policy: Strategy mapping states to actions

Q-Learning
Goal: Learn Q-function = expected cumulative reward for action in state[1].

Update Rule:

Where:
 = learning rate
= discount factor
= immediate reward
= next state

Advantages
Learns optimal policy
Model-free (no environment model needed)
Off-policy learning possible

Disadvantages
Slow convergence
Requires exploration-exploitation trade-off
Sensitive to rewards design

6.2 Genetic Algorithms

Overview
Evolutionary algorithm that mimics natural selection to solve optimization problems[1].

Key Concepts
Population: Set of candidate solutions (genomes)
Fitness: Quality of solution
Selection: Choose best solutions to reproduce
Crossover: Combine two solutions
Mutation: Random change in solution

Algorithm
Initialize: Random population
While not converged:
1. Evaluate fitness of each individual
2. Select fittest individuals
3. Apply crossover (combine two parents)
4. Apply mutation (random changes)
5. Create new population[1]

Advantages
Handles complex, non-linear optimization
No gradient required
Can escape local optima
Parallelizable
Disadvantages
Computationally expensive
No convergence guarantee
Requires careful parameter tuning
Representation design critical

REFERENCES
[1] Mitchell, T. M. (1997). Machine Learning. McGraw-Hill.
[2] Goodfellow, I., Bengio, Y., & Courville, A. (2016). Deep Learning. MIT Press.

[3] Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer.

[4] Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd
ed.). Springer.
[5] AKTU Official Syllabus. (2025-26). BOE073/KOE073 Machine Learning. Dr. A.P.J. Abdul
Kalam Technical University.