CSEN2031

ARTIFICIAL INTELLIGENCE
Module 5
Uncertainty and Learning
Prof. M. Subramaniam
Dept. of CSE – GITAM University, Bengaluru
Uncertainty and Learning

• Uncertainty
• Acting under Uncertainty,
• Conditional Probabilities,
• Full Joint Distributions,
• Bayes Rule and its Applications:
• Bayesian Networks.
• Basics of Learning
• Supervised Learning,
• Learning Decision Trees,
• Evaluating and Choosing the Best Hypothesis,
• Unsupervised Learning.
2
Uncertainty
• In real-world environments, intelligent systems rarely have access to
complete, accurate, and deterministic information. Instead, they
must operate under uncertainty, making decisions based on
incomplete, noisy, or ambiguous data.
• Why Uncertainty Arises
• Partial observability (agent cannot see entire environment)
• Noisy sensors (measurement errors)
• Incomplete knowledge (missing data)
• Complex environments (too many variables)
• Stochastic nature of systems (randomness)
• Example: A medical diagnosis system cannot be 100% certain about a
disease based on symptoms alone.

3
Uncertainty and its causes
Defining Uncertainty:
• The knowledge representation, A→B, means if A is true then B is true,
but a situation where not sure about whether A is true or not then
cannot express this statement, this situation is called uncertainty.
• So to represent uncertain knowledge, uncertain reasoning or
probabilistic reasoning is used.
• Causes of uncertainty:
• Causes of uncertainty in the real world
• Information occurred from unreliable sources.
• Experimental Errors
• Equipment fault
• Temperature variation
• Climate change.

4
Types of Uncertainty
• Epistemic Uncertainty (Knowledge-based)
• Due to lack of knowledge
• Can be reduced with more data
• Example: Unknown patient history
• Aleatory Uncertainty (Randomness)
• Inherent randomness in the system
• Cannot be reduced
• Example: Weather variations
• Sources of Uncertainty in AI Systems
• Sensor Noise (e.g., camera blur)
• Ambiguity in Data (multiple interpretations)
• Dynamic Environments
• Model Limitations
• Human Factors (bias, incomplete inputs)
5
Representation of Uncertainty
• AI systems must represent uncertainty mathematically to reason effectively.
• Probability Theory (Primary Framework)
• Uses numerical values between 0 and 1
• Represents degree of belief
• Key Idea:
• 𝑃(𝐴) = Probability that event A occurs

• Alternative Representations
• Fuzzy Logic
• Deals with vagueness (partial truth)
• Truth values between 0 and 1
• Dempster-Shafer Theory
• Represents belief and plausibility
• Useful when evidence is incomplete
• Possibility Theory
• Focuses on possibility rather than probability
6
Probability Basics (Foundation for Uncertainty)
• Sample Space
• Set of all possible outcomes
𝑆 = 𝑠1 𝑠2 . . . 𝑠𝑛
• Events
• Subset of sample space
• Probability Axioms
• 0≤𝑃 𝐴 ≤1
• 𝑃 𝑆 =1
• For mutually exclusive events:
𝑃 𝐴∪𝐵 =𝑃 𝐴 +𝑃 𝐵
• Degree of Belief
In AI, probability is often interpreted as:
• Subjective belief
• Confidence level in a hypothesis
• Example:
7
𝑃 Rain = 0.8 →Strong belief that it will rain
Probability and the probability of occurrence
• Probability can be defined as a chance that an uncertain event will
occur.
• The value of probability always remains between 0 and 1 that
represent ideal uncertainties.
• 0 ≤ P(A) ≤ 1, where P(A) is the probability of an event A.
• P(A) = 0, indicates total uncertainty in an event A.
• P(A) =1, indicates total certainty in an event A
• Formula to find the probability of an uncertain event

8
Importance of Uncertainty in AI
• Real-World Applications
• Medical diagnosis systems, Autonomous vehicles, Speech recognition, Financial
forecasting, Robotics
• Benefits
• Handles incomplete data
• Supports better decision-making
• Models real-world complexity
• Challenges in Handling Uncertainty
• High computational complexity
• Data scarcity
• Model selection issues
• Overfitting / underfitting
• Interpretability issues
• Example (Illustrative)
• Problem: A patient has symptoms: fever and cough.
• Probability of Flu given symptoms: 𝑃(Flu ∣ Fever, Cough)=0.7
• Interpretation:
9
• There is a 70% chance the patient has flu — not certainty.
Acting under Uncertainty
• In uncertain environments, an AI agent must not only reason about
uncertainty but also act optimally despite it. “Good decisions are not
those that guarantee success, but those that maximize expected success
under uncertainty.”
• Agent Framework under Uncertainty
• Rational Agent
• A rational agent selects actions that maximize its expected performance measure,
given:
• Available evidence
• Probabilistic knowledge of the environment
• Components of Decision Making
• States – Possible situations of the environment
• Actions – Choices available to the agent
• Outcomes – Results of actions
• Probabilities – Likelihood of outcomes
• Utilities – Preferences over outcomes 10
Decision Theory (Core Framework)
• Decision theory combines:
• Probability Theory → Handling uncertainty
• Utility Theory → Handling preferences
• Expected Utility Principle
• The best action is the one that maximizes Expected Utility (EU):

• Interpretation
• Choose action with highest expected benefit
• Accounts for both:
• Likelihood of outcomes 11
• Desirability of outcomes
Utility Theory
• What is Utility?
• A numerical measure of preference
• Higher value → more desirable outcome
• Types of Utility
• Cardinal Utility
• Quantitative measure (e.g., 0–100)
• Ordinal Utility
• Ranking only (e.g., prefer A over B)
• Risk Attitudes
• Risk-Averse
• Prefers safer outcomes
• Risk-Seeking
• Prefers uncertain but high-reward outcomes
• Risk-Neutral
• Focuses only on expected value 12
Decision Networks (Influence Diagrams)
• A decision network extends Bayesian networks with:
• Decision nodes (actions)
• Utility nodes (preferences)
• Components
• Chance nodes (uncertain variables)
• Decision nodes (choices)
• Utility nodes (objective function)

13
Sequential Decision Making
• Real-World Scenario
• Actions are not one-time — they occur in sequence over time.
• Markov Decision Process (MDP)
• An MDP is defined by:
• States (S)
• Actions (A)
• Transition probabilities (P)
• Reward function (R)
• Markov Property
• Future state depends only on the current state, not past history.
• Policy
• A policy (π) defines action selection: π(s)=a
• Goal
• Find an optimal policy that maximizes expected cumulative reward.
14
Partially Observable Environments
• Problem : Agent cannot directly observe the true state.
• Solution: Belief State, A probability distribution over possible states
• POMDP (Partially Observable MDP)
• Extends MDP with:
• Observations
• Belief updates

• Value of Information (VOI)

• Concept
• Information has value if it improves decision-making.
• Key Idea
• Sometimes it is worth delaying action to gather more information
• Example
• Medical test before treatment:
• Test cost vs improved diagnosis accuracy
15
Applications
• Autonomous vehicles (navigation under uncertainty)
• Robotics (sensor noise handling)
• Medical decision systems
• Financial portfolio optimization
• Game AI
• Challenges
• Computational complexity
• State space explosion
• Accurate probability estimation
• Designing utility functions
• Partial observability

16
Conditional Probabilities
• In real-world AI systems, we often revise our beliefs when new evidence
becomes available.
• Example:
• Probability of disease changes after observing symptoms
• Probability of rain changes after seeing dark clouds
• This process is captured by conditional probability.,

• Definition of Conditional Probability

• Formal Definition
𝑃 𝐴∩𝐵
𝑃 𝐴∣𝐵 = ,𝑃 𝐵 > 0
𝑃 𝐵
• Interpretation
• Probability of event A given that B has occurred
• Updates belief about A using evidence B
17
Conditional Probability

• Conditional probability is the likelihood of an event occurring,

given that another related event has already taken place. It
updates the probability of an event based on new information,
calculated as Formula:
• It is denoted as,
𝑃 𝐴∩𝐵
𝑃 𝐴∣𝐵 = ,𝑃 𝐵 > 0
𝑃 𝐵
• Interpretation
• Probability of event A given that B has occurred
• Updates belief about A using evidence B

18
Intuition Behind Conditional Probability with Example

• Restrict the sample space to outcomes where B is true

• Then evaluate how often A occurs within that restricted space
• Example
• If:
• 100 people total
• 40 have fever
• 20 have fever and flu
• Then:

19
Multiplication Rule (Product Rule)
• Formula

• Interpretation
• Joint probability can be decomposed into:
• Conditional probability × prior probability
• Extension to Multiple Variables
20
Chain Rule of Probability

• General Form

• Importance
• Foundation for:
• Bayesian Networks
• Probabilistic reasoning
• Machine learning models

21
Independence

• Two events are independent if:

• Equivalent Form
• Types of Independence
• Marginal Independence
• Conditional Independence

• Interpretation
• A is independent of B given C
• Once C is known, B provides no additional information about A
• Importance in AI
• Reduces complexity of models
• Key idea in Bayesian Networks 22
Law of Total Probability

• Formula:

23
Bayes’ Rule (Preview)

• Formula:

• Used in:
• Diagnosis
• Classification
• Updating beliefs
• Applications in AI
• Medical Diagnosis
• Probability of disease given symptoms
• Spam Filtering
• Probability email is spam given words
• Speech Recognition
• Probability of word given sound
• Computer Vision 24
• Probability of object given image features
Bayes’ Rule - Example

• Problem : A test for a disease:

• 𝑃 𝐷𝑖𝑠𝑒𝑎𝑠𝑒 = 0.01
• 𝑃 𝑃𝑜𝑠𝑖𝑡𝑖𝑣𝑒 ∣ 𝐷𝑖𝑠𝑒𝑎𝑠𝑒 = 0.99
• 𝑃 𝑃𝑜𝑠𝑖𝑡𝑖𝑣𝑒 ∣ 𝑁𝑜𝐷𝑖𝑠𝑒𝑎𝑠𝑒 = 0.05
• Find:
• 𝑃 𝐷𝑖𝑠𝑒𝑎𝑠𝑒 ∣ 𝑃𝑜𝑠𝑖𝑡𝑖𝑣𝑒

• Solution (Using Bayes’ Rule)

𝑃 𝑃𝑜𝑠𝑖𝑡𝑖𝑣𝑒 = 0.99 × 0.01 + 0.05 × 0.99
= 0.0099 + 0.0495 = 0.0594
0.99 × 0.01
𝑃 𝐷𝑖𝑠𝑒𝑎𝑠𝑒 ∣ 𝑃𝑜𝑠𝑖𝑡𝑖𝑣𝑒 = ≈ 0.1667
0.0594

Even with a positive test, probability of disease is only ~16.7% due to low prior 25
probability.
Proving from first principles of conditional probability that P(a | b ∧ a) = 1
• Definition of Conditional Probability:
𝑃(𝑎 ∧ (𝑏 ∧ 𝑎))
𝑃(𝑎 ∣ 𝑏 ∧ 𝑎) =
𝑃(𝑏 ∧ 𝑎)
• Simplify the Numerator
• Using associativity and idempotent law:
𝑎 ∧ (𝑏 ∧ 𝑎) = 𝑎 ∧ 𝑎 ∧ 𝑏 = 𝑎 ∧ 𝑏
So,
𝑃(𝑎 ∧ (𝑏 ∧ 𝑎)) = 𝑃(𝑎 ∧ 𝑏)
• Substitute Back
𝑃(𝑎 ∧ 𝑏)
𝑃(𝑎 ∣ 𝑏 ∧ 𝑎) =
𝑃(𝑏 ∧ 𝑎)
• Use Commutativity
𝑎∧𝑏 =𝑏∧𝑎
• Thus,
𝑃(𝑎 ∧ 𝑏) = 𝑃(𝑏 ∧ 𝑎)
• Final Result
𝑃(𝑏 ∧ 𝑎)
𝑃(𝑎 ∣ 𝑏 ∧ 𝑎) = =1
𝑃(𝑏 ∧ 𝑎)
(provided 𝑃(𝑏 ∧ 𝑎) ≠ 0)
26
Hence, 𝑃(𝑎 ∣ 𝑏 ∧ 𝑎) = 1
Full Joint Distributions
• In probabilistic AI, we often deal with multiple random variables
simultaneously. To fully describe the uncertainty in a system, we use a
Full Joint Probability Distribution (FJPD).
• Key Idea: The full joint distribution specifies the probability of every possible
combination of variable values.

• Definition of Full Joint Distribution

• Formal Definition

• Interpretation
• Represents the probability of all variables taking specific values simultaneously

27
Example

• For two variables:

• Weather (Rain, No Rain)
• Traffic (Heavy, Light)
• The full joint distribution includes:
• 𝑃(𝑅𝑎𝑖𝑛, 𝐻𝑒𝑎𝑣𝑦)
• 𝑃(𝑅𝑎𝑖𝑛, 𝐿𝑖𝑔ℎ𝑡)
• 𝑃(𝑁𝑜𝑅𝑎𝑖𝑛, 𝐻𝑒𝑎𝑣𝑦)
• 𝑃(𝑁𝑜𝑅𝑎𝑖𝑛, 𝐿𝑖𝑔ℎ𝑡)

28
Properties of Full Joint Distributions

• Non-Negativity
𝑃(𝑥1 , 𝑥2 , . . . , 𝑥𝑛 ) ≥ 0
• Normalization
෍ 𝑃( 𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = 1
𝑥1 ,𝑥2 ,…,𝑥𝑛
• Completeness
• Fully specifies the probabilistic model
• All other probabilities can be derived from it

29
Marginalization

• To find the probability of a subset of variables, we sum out the

others.
• Formula
𝑃(𝑋) = ෍ 𝑃(𝑋, 𝑌)
𝑌
• Example
𝑃(𝑅𝑎𝑖𝑛) = 𝑃(𝑅𝑎𝑖𝑛, 𝐻𝑒𝑎𝑣𝑦) + 𝑃(𝑅𝑎𝑖𝑛, 𝐿𝑖𝑔ℎ𝑡)

30
Proving that any probability distribution on a discrete random variable must sum to 1,
Using the axioms of probability,

31
Contd…

32
Bayes’ Rule and its Application
• In AI, we frequently need to update our beliefs when new evidence arrives.
Bayes’ Rule provides a principled way to do this.
• Key Idea: Posterior = Likelihood × Prior / Evidence.
• Bayes’ Rule: Formal Definition

Prior 𝑃(𝐴)→ Initial belief before evidence

Likelihood 𝑃(𝐵 ∣ 𝐴)→ Probability of evidence given hypothesis
Evidence 𝑃(𝐵)→ Total probability of evidence 33
Posterior 𝑃(𝐴 ∣ 𝐵)→ Updated belief after evidence
Derivation of Bayes’ Rule

Bayes' theorem can be derived using product rule and conditional probability
of event A with known event B:

From conditional probability:

𝑃(𝐴, 𝐵) 𝑃(𝐴, 𝐵)
𝑃(𝐴 ∣ 𝐵) = , 𝑃(𝐵 ∣ 𝐴) =
𝑃(𝐵) 𝑃(𝐴)
Rewriting:
𝑃(𝐴, 𝐵) = 𝑃(𝐵 ∣ 𝐴)𝑃(𝐴)
Substituting:
𝑃(𝐵 ∣ 𝐴)𝑃(𝐴)
𝑃(𝐴 ∣ 𝐵) =
𝑃(𝐵)
Intuition Behind Bayes’ Rule
• Start with an initial belief (prior)
• Adjust it using observed data (likelihood)
• Normalize using total probability (evidence)
34
It answers: “How likely is hypothesis A, given observed evidence B?”
Extended Bayes’ Rule (Multiple Hypotheses)

When we have multiple hypotheses 𝐻1 , 𝐻2 , . . . , 𝐻𝑛 :

𝑃(𝐸 ∣ 𝐻𝑖 )𝑃(𝐻𝑖 )
𝑃(𝐻𝑖 ∣ 𝐸) =
෌𝑗 𝑃(𝐸 ∣ 𝐻𝑗 )𝑃(𝐻𝑗 )
• Interpretation
• Compares competing hypotheses
• Normalizes probabilities across all possibilities

35
Bayesian Inference

• Concept
• Use Bayes’ Rule to update beliefs repeatedly
• Core idea in probabilistic learning
• Process
• Define prior
• Observe evidence
• Compute likelihood
• Update posterior
• Repeat if new evidence arrives

36
Bayesian Inference

• Bayesian inference is a probabilistic approach to machine learning that

provides estimates of the probability of specific events.
• Bayesian inference is a statistical method for understanding the
uncertainty inherent in prediction problems.
• Bayesian inference algorithm can be viewed as a Markov Chain Monte
Carlo algorithm that uses prior probability distributions to optimize the
likelihood function.
• The basis of Bayesian inference is the notion of apriori and a posteriori
probabilities.
• The priori probability is the probability of an event before any evidence
is considered.
• The posteriori probability is the probability of an event after taking into
account all available evidence.
• For example, if we want to know the probability that it will rain
tomorrow, our priori probability would be based on our knowledge of37
the weather patterns in our area.
Applications in Artificial Intelligence

1. Medical Diagnosis
Example:
𝑃(𝐷𝑖𝑠𝑒𝑎𝑠𝑒) = 0.01
𝑃(𝑆𝑦𝑚𝑝𝑡𝑜𝑚 ∣ 𝐷𝑖𝑠𝑒𝑎𝑠𝑒) = 0.9
𝑃(𝑆𝑦𝑚𝑝𝑡𝑜𝑚 ∣ 𝑁𝑜𝐷𝑖𝑠𝑒𝑎𝑠𝑒) = 0.05
• Bayes’ Rule computes:
𝑃(𝐷𝑖𝑠𝑒𝑎𝑠𝑒 ∣ 𝑆𝑦𝑚𝑝𝑡𝑜𝑚)
Helps avoid false assumptions due to rare diseases

2. Spam Email Classification (Naïve Bayes)

Classify email as Spam or Not Spam
Based on words in the email
𝑃(𝑆𝑝𝑎𝑚 ∣ 𝑊𝑜𝑟𝑑𝑠) ∝ 𝑃(𝑊𝑜𝑟𝑑𝑠 ∣ 𝑆𝑝𝑎𝑚)𝑃(𝑆𝑝𝑎𝑚) 38
Applications in Artificial Intelligence

3. Machine Learning (Naïve Bayes Classifier)

• Assumption: Features are conditionally independent
• Formula:
𝑃(𝐶 ∣ 𝑋1 , . . . , 𝑋𝑛 ) ∝ 𝑃(𝐶) ෑ 𝑃( 𝑋𝑖 ∣ 𝐶)
𝑖
4. Fault Diagnosis Systems
• Identify system failure causes
• Example: Network failure detection
5. Computer Vision
• Object recognition using probabilistic inference
6. Speech Recognition
• Determine most likely word given sound signal
39
Example Numerical Problem
• A test for a disease:
• 𝑃(𝐷) = 0.02
• 𝑃(𝑃𝑜𝑠 ∣ 𝐷) = 0.95
• 𝑃(𝑃𝑜𝑠 ∣ ¬𝐷) = 0.10

• Step 1: Compute Evidence

𝑃(𝑃𝑜𝑠) = (0.95 × 0.02) + (0.10 × 0.98)
= 0.019 + 0.098 = 0.117
Step 2: Apply Bayes’ Rule
0.95 × 0.02
𝑃(𝐷 ∣ 𝑃𝑜𝑠) = ≈ 0.162
0.117
Interpretation
• Even with a positive test → only 16.2% chance of disease
• Demonstrates importance of prior probability

40
Bayesian Networks
• As seen in Full Joint Distributions, representing all variables explicitly leads
to exponential complexity.
• Bayesian Networks (BNs) provide a compact and structured representation
of joint probability distributions by exploiting conditional independence.
"Represent complex probabilistic relationships using a directed graph + local
probability tables“
• A Bayesian Network is a, Directed Acyclic Graph (DAG) where:
• Nodes → Random variables
• Edges → Probabilistic dependencies
• Each node is associated with a Conditional Probability Table (CPT)
• Components of Bayesian Networks
• Nodes
• Represent random variables
• Can be:
• Discrete (e.g., Rain: Yes/No)
• Continuous
• Directed Edges
• Represent causal or dependency relationships 41
• Example:
• Rain → WetGrass
Bayesian Networks
• Joint Distribution Representation
• Factorization Property
𝑛
𝑃(𝑋1 , 𝑋2 , … , 𝑋𝑛 ) = ෑ 𝑃( 𝑋𝑖 ∣ 𝑃𝑎𝑟𝑒𝑛𝑡𝑠(𝑋𝑖 ))
𝑖=1
• Interpretation
• Each variable depends only on its parent nodes
• Reduces complexity drastically

• Conditional Probability Tables (CPTs)

• Define probability of a node given its parents
• Each node in the Bayesian network has condition probability distribution
P(Xi |Parent(Xi) ), which determines the effect of the parent on that node.
• Example:
𝑃(𝑊𝑒𝑡𝐺𝑟𝑎𝑠𝑠 ∣ 𝑅𝑎𝑖𝑛)
42
Bayesian Networks
• Each node corresponds to the random variables, and a variable can be
continuous or discrete.
• Arc or directed arrows represent the causal relationship or conditional
probabilities between random variables.
• These directed links or arrows connect the pair of nodes in the graph.
• These links represent that one node directly influence the other node, and if
there is no directed link that means that nodes are independent with each other.
• Example

43
 …Contd
• In the above figure A, B, C, and D are random variables represented by
the nodes of the network graph.
• Considering node B, which is connected with node A by a directed arrow,
then node A is called the parent of Node B.
• Node C is independent of node A.
• The Bayesian network graph does not contain any cyclic graph. Hence, it
is known as a directed acyclic graph or DAG.
• The Bayesian network has mainly two components:
• Causal Component
• Actual numbers
• Bayesian network is based on Joint probability distribution and
conditional probability.

44
Bayesian Networks – Example Problem
A patient may have a disease. The disease affects whether a test result is positive.
Where variables are D: Disease (True/False), T: Test Result (Positive/Negative) and
Structure D → T and CPTs are ,
(i) P(D=True)=0.01, P(D=False)=0.99
(ii) P(T=Positive |D=True)=0.9 and
(iii) P(T=Positive| D=False)=0.2.
Find probability patient has disease given positive test using Bayes Theorem.

• Solution:
P(D|T)= [P(T|D)P(D)] / P(T)
P(T)=0.9*0.01 + 0.2*0.99 = 0.009 + 0.198 = 0.207
P(D|T)= (0.9*0.01)/0.207 = 0.009/0.207 ≈ 0.043

45
Basics of Learning
Learning is a fundamental capability of intelligent systems. Instead of being
explicitly programmed, AI systems can improve performance by learning from
experience.
Learning = Improving performance on a task using experience.
Definition of Learning
A computer program is said to learn from experience 𝐸with respect to:
• Task 𝑇
• Performance measure 𝑃
• if its performance at task 𝑇, as measured by 𝑃, improves with experience 𝐸.
• Components of a Learning System
• Task (T)
• What the system is supposed to do
• Example: Classify emails as spam or not
• Experience (E)
• Data or interactions used for learning
• Example: Past emails
• Performance Measure (P) 46
• Metric to evaluate performance
• Example: Accuracy, precision, recall
Types of Learning
1. Supervised Learning
The system learns from labelled data
Each input has a corresponding correct output
Goal
Learn a function: f(x)→y
Example
Email classification:
Input: Email text
Output: Spam / Not Spam
The model learns from examples labelled as spam or not spam.
2. Unsupervised Learning
Learning from unlabelled data
No predefined output
Goal
Discover hidden patterns or structure
Example
Customer segmentation:
Group customers based on purchasing behavior 47
No labels are given
Types of Learning
3. Reinforcement Learning
Learning through interaction with environment
Receives rewards or penalties
Goal
Maximize cumulative reward
Example
Game playing (chess, video games):
Agent learns best moves by trial and error
Gets reward for winning
4. Semi-Supervised Learning
Uses both labeled and unlabeled data
Goal
Improve learning accuracy when labeled data is limited
Example
Image classification:
Few labeled images + many unlabeled images 48
Model learns better patterns
Types of Learning
5. Self-Supervised Learning
The system generates its own labels from data
Example
Predicting missing words in a sentence
Used in language models
6. Online vs Batch Learning
(a) Online Learning
Learns continuously as new data arrives
Example:
Stock price prediction updated in real time
(b) Batch Learning
Learns from the entire dataset at once
Example:
Training a model once on historical data

49
Types of Learning
7. Instance-Based Learning
Stores examples and compares new cases to them
Example
K-Nearest Neighbors (KNN):
Classifies based on closest data points
8. Model-Based Learning
Builds a general model from data
Example
Linear regression:
Finds equation to predict outputs

50
Concept of Ensemble learning
Ensemble learning is a machine learning approach in which multiple
models (called base learners or weak learners) are combined to produce a
stronger and more accurate model. The central idea is that a group of
models working together can achieve better performance than any
individual model. That is by combining diverse learners, it enhances
performance and is widely used in real-world applications such as
classification, regression, and predictive analytics.
Concept
Instead of relying on a single hypothesis, ensemble methods aggregate
predictions from several models to improve:
•Accuracy
•Robustness
•Generalization
This works because different models may capture different patterns in
data, and combining them reduces errors. 51
Why Ensemble Learning Works
• Individual models may suffer from:
• High variance (overfitting)
• High bias (underfitting)
• Noise sensitivity
• Ensemble methods reduce these issues by:
• Averaging predictions (reducing variance)
• Combining diverse models (reducing bias)
• Stabilizing results

52
Types of Ensemble Methods
1. Bagging (Bootstrap Aggregating)
• Multiple models are trained on different random subsets of data
• Final prediction is made by majority voting (classification) or
averaging (regression)
• Example:
• Random Forest (collection of decision trees)
2. Boosting
• Models are trained sequentially
• Each new model focuses on correcting errors of previous models
• Examples:
• AdaBoost
• Gradient Boosting

53
Types of Ensemble Methods
3. Stacking
Combines multiple models using a meta-learner
Outputs of base models are used as input for a final model
Example
Suppose we want to predict whether an email is spam:
Model 1: Decision Tree
Model 2: Logistic Regression
Model 3: Naïve Bayes
Each model gives a prediction. The ensemble combines them (e.g.,
majority vote) to produce a final decision, which is usually more
accurate than any single model.

54
Pros & Cons of Ensemble Learning
• Advantages
• Improves prediction accuracy
• Reduces overfitting
• Handles complex data effectively
• More stable and reliable
• Limitations
• Increased computational cost
• Harder to interpret
• Requires careful model selection

55
Machine Learning - Supervised Learning
• Learning from labelled data
• Input-output pairs are provided
• Goal : Learn a mapping: 𝑓: 𝑋 → 𝑌
• The computer is presented with example inputs and their desired
outputs, given by a “teacher”, and the goal is to learn a general rule that
maps inputs to outputs.
• The training process continues until the model achieves the desired level
of accuracy on the training data.
• Some real-life examples are:
• Image Classification: You train with images/labels. Then in the future you
give a new image expecting that the computer will recognize the new object.
• Market Prediction/Regression: You train the computer with historical
market data and ask the computer to predict the new price in the future.
• Types
• Classification (discrete output)
• Regression (continuous output)
56
Classification
• Inputs are divided into two or more classes, and the learner must
produce a model that assigns unseen inputs to one or more (multi-
label classification) of these classes.
• This is typically tackled in a supervised way.
• Spam filtering is an example of classification, where the inputs are
email messages and the classes are “spam” and “not spam”.

57
Regression
• It is also a supervised learning problem, but the outputs are
continuous rather than discrete. For example, predicting the stock
prices using historical data.
• An example of classification and regression on two different
datasets is shown below

58
Supervised Learning Algorithms
1. Linear Regression
2. Logistic Regression
3. SVM (Support Vector Machines)
4. Naive Bayes
5. Random Forest
6. Decision Trees
7. KNN (K Nearest Neighbors)

59
Learning Decision Trees
• A Decision Tree is a supervised learning model used for:
• Classification (most common)
• Regression
• "A decision tree recursively splits data based on features to reach a decision
(class label)".
• Structure of a Decision Tree & Its Components
• Root Node → Top-most decision
• Internal Nodes → Feature tests
• Branches → Outcomes of tests
• Leaf Nodes → Final class labels
• Example (Conceptual)
Outlook?
├── Sunny → Humidity?
│ ├── High → No
│ └── Normal → Yes
├── Overcast → Yes
└── Rain → Wind?
├── Strong → No
60
└── Weak → Yes
Functioning of Decision Tree Algorithm
• The algorithm works in a top-down, recursive manner.
• Step-by-Step Process
• Step 1: Start with Training Data - Dataset contains input features and
output labels
• Step 2: Select Best Attribute
• Choose attribute that best splits data
• Common criteria:
• Information Gain
• Gini Index
• Step 3: Split the Data - Divide dataset based on attribute values
• Step 4: Repeat Recursively - Apply same process to each subset
• Step 5: Stop Condition
• Stop when:
• All examples have same class, OR
• No attributes left, OR
• Data is insufficient
• Step 6: Assign Leaf Node - Assign class label (Yes/No, etc.) 61
Example: Play Tennis Decision
Dataset Attributes
Outlook (Sunny, Rain, Overcast)
Humidity (High, Normal)
Wind (Strong, Weak)
Output: Play (Yes/No)
Tree Construction
Step 1: Root Node
Choose Outlook (highest information gain)
Step 2: Branches
Overcast → Yes (always play)
Sunny → Check Humidity
High → No
Normal → Yes
Rain → Check Wind
Strong → No
Weak → Yes
Using the Tree
Example Prediction
Input:
Outlook = Sunny
Humidity = High
Path:
Sunny → Humidity → High → No 62
Output: Do not play
Decision Tree Learning Problem & Algorithm
• Given: Training examples: 𝑥1 , 𝑦1 ), . . . , (𝑥𝑛 , 𝑦𝑛
• Goal: Learn a function that maps inputs to outputs
• Algorithm: ID3 (Iterative Dichotomiser 3)
• Core Idea: (i) Select the attribute that provides maximum information gain
(ii) Split the dataset recursively
Pseudocode

63
Entropy (Measure of Impurity)

𝐻(𝑆) = − σ𝑖 𝑝𝑖 log2 𝑝𝑖
• Measures uncertainty or impurity
• Range:
• 0 → Pure (all same class)
• 1 → Maximum uncertainty (binary case)
• Example
• Dataset: 9 Yes, 5 No

9 9 5 5
• 𝐻(𝑆) = − log2 log2 ≈ 0.94
14 14 14 14

64
Information Gain
∣ 𝑆𝑣 ∣
𝐼𝐺(𝑆, 𝐴) = 𝐻(𝑆) − ෎ 𝐻(𝑆𝑣 )
∣𝑆∣
𝑣
• Reduction in entropy after splitting on attribute 𝐴
• Higher gain → better attribute
• Example Play Tennis Dataset Summary
Outlook Play
Sunny No
Sunny No
Overcast Yes
Rain Yes
Rain Yes
Rain No
Overcast Yes
Sunny No
Sunny Yes
Rain Yes
Sunny Yes
Overcast Yes
Overcast Yes 65
Rain No
Solution
Step 1: Compute Entropy : By computing we get: 𝐻(𝑆) ≈ 0.94
Step 2: Compute Information Gain for Outlook
Split:
Sunny: 5 → (2 Yes, 3 No)
Overcast: 4 → (4 Yes, 0 No)
Rain: 5 → (3 Yes, 2 No)
Entropies:
Sunny:
2 2 3 3
𝐻 = − log2 log2 ≈ 0.97
5 5 5 5
Overcast:
𝐻=0
Rain:
𝐻 ≈ 0.97
Weighted Entropy:
5 4 5
(0.97) + (0) + (0.97) ≈ 0.69
14 14 14
Information Gain:
𝐼𝐺(𝑆, 𝑂𝑢𝑡𝑙𝑜𝑜𝑘) = 0.94 − 0.69 = 0.25
Repeat for other attributes (Humidity, Wind, Temperature) 66
Choose attribute with highest gain
Tree Construction & Overfitting in Decision Trees

• Root = Attribute with highest IG

• Recursively apply ID3 on subsets
• Handling Continuous Attributes
• Convert into binary splits:
• Example: Temperature > 30°C
• Overfitting in Decision Trees
• Problem
• Tree becomes too complex
• Fits noise instead of pattern
• Solutions
• Pre-pruning
• Stop early
• Post-pruning
• Remove unnecessary branches 67
Problem
• Suppose we generate a training set from a decision tree and then apply decision-tree
learning to that training set. Will the learning algorithm eventually return the correct
tree as the training-set size goes to infinity? Explain.
• Solution:
• Decision tree learning algorithms (such as ID3, C4.5) attempt to learn a target function by
constructing a tree based on training examples. The question is whether, given infinite
training data generated from a true decision tree, the algorithm will recover the exact
original tree.
• Ideal Case: Convergence to Correct Tree
• Under certain ideal conditions, the algorithm can learn the correct tree:
• The training data is noise-free
• The target function is perfectly representable as a decision tree
• All relevant attributes are available
• The dataset is sufficiently large (approaching infinity)
• Reason:
• With infinite data, all possible input combinations are observed
• Probabilities used in measures like information gain become accurate
• The best attribute at each node is correctly identified
68
• Thus, the algorithm can converge to a functionally correct hypothesis. However, in
practice, the algorithm may not return the exact original tree, even with infinite data.
Solution contd…
1. Greedy Nature of Algorithm
Decision tree algorithms use a top-down greedy approach
They select the best attribute locally at each step
Once a split is made, it is not reconsidered
This can lead to a tree different from the original.
2. Multiple Equivalent Trees
A given function can be represented by many different trees
The algorithm may learn a different structure that gives the same output
3. Irrelevant or Redundant Attributes
Extra attributes can influence splitting decisions
May result in a more complex or different tree structure
4. Presence of Noise
Real-world data may contain errors
The algorithm may overfit noise rather than learn the true pattern
5. Effect of Pruning
Pruning is used to avoid overfitting
It may remove parts of the actual tree, preventing exact recovery

As the result, "With infinite data, decision-tree learning converges to a correct 69

hypothesis, but not necessarily the original tree".
Advantages & Limitations of Decision Trees

• Advantages
• Easy to understand and interpret
• No need for feature scaling
• Handles both categorical and numerical data
• Fast inference
• Limitations
• Overfitting
• Bias towards attributes with many values
• Unstable (small data changes → different tree)

70
Evaluating and Choosing the Best Hypothesis

• In machine learning, many hypotheses (models) can fit the training data.
• The challenge is to select the best hypothesis that generalizes well to
unseen data.
• The best hypothesis is not the one that fits training data perfectly, but
the one that performs best on unseen data.
• Hypothesis
• A function/model that maps inputs to outputs
• Example: Decision tree, linear model, neural network
• Training Error vs Generalization Error
• Training Error: Error on training data
• Generalization Error: Error on unseen data
• Overfitting vs Underfitting
• Overfitting: Model memorizes data, poor generalization
• Underfitting: Model too simple, fails to capture patterns
71
Dataset Splitting

• Hold-Out Method
• Split dataset into: (i) Training set (ii) Test set
• Validation Set
• (i) Used for model selection and (ii) Final evaluation done on test set
• Typical Split
• (70% training + 15% validation + 15% testing)
• Cross-Validation
• k-Fold Cross-Validation
• Split data into 𝑘equal parts
• Train on 𝑘 − 1, test on remaining
• Repeat 𝑘times
• Benefits
• Better estimation of performance
72
• Reduces variance
Evaluation Metrics (Classification)
• Confusion Matrix Predicted Predicted
+ -
Actual + TP FN
Actual - FP TN

• Accuracy
𝑇𝑃 + 𝑇𝑁
𝐴𝑐𝑐𝑢𝑟𝑎𝑐𝑦 =
𝑇𝑃 + 𝑇𝑁 + 𝐹𝑃 + 𝐹𝑁
• Precision
𝑇𝑃
𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 =
𝑇𝑃 + 𝐹𝑃
• Recall (Sensitivity)
𝑇𝑃
𝑅𝑒𝑐𝑎𝑙𝑙 =
𝑇𝑃 + 𝐹𝑁
• F1-Score
𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 ⋅ 𝑅𝑒𝑐𝑎𝑙𝑙
𝐹1 = 2 ⋅
𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 + 𝑅𝑒𝑐𝑎𝑙𝑙
When to Use What? Metric Use Case
Accuracy Balanced datasets
Precision When false positives are costly
73
Recall When false negatives are costly
F1-score Balanced precision & recall
Evaluation Metrics (Regression)

• Mean Squared Error (MSE)

1
𝑀𝑆𝐸 = σ(𝑦𝑖 − 𝑦ො𝑖 )2
𝑛

• Mean Absolute Error (MAE)

1
𝑀𝐴𝐸 = σ ∣ 𝑦𝑖 − 𝑦ො𝑖 ∣
𝑛

• R-Squared
𝑆𝑆𝑟𝑒𝑠
𝑅2 =1−
𝑆𝑆𝑡𝑜𝑡

74
Bias-Variance Tradeoff

• Concept
Error= 𝐵𝑖𝑎𝑠 2 + 𝑉𝑎𝑟𝑖𝑎𝑛𝑐𝑒 + 𝑁𝑜𝑖𝑠𝑒
• Interpretation
Component Meaning
Bias Error due to wrong assumptions
Variance Sensitivity to training data
Noise Irreducible error

• Insight
• High bias → Underfitting
• High variance → Overfitting

75
Model Selection & Regularization

• Choosing the Best Hypothesis

• Criteria:
• Low generalization error
• Good balance of bias and variance
• Simplicity (Occam’s Razor)
• Occam’s Razor
• Prefer the simplest hypothesis that fits the data
• Regularization
• Purpose : Prevent overfitting
• Types: (i) L1 Regularization (Lasso) (ii) L2 Regularization (Ridge)
• Idea : Add penalty term to loss function

76
Learning Curves

• Plot of performance vs training size

• Interpretation
• Diagnose
• Overfitting
• Underfitting
• Example (Conceptual)
• Scenario: Two models: Training Test
Model
Accuracy Accuracy
A 95% 60%
B 85% 82%
• Analysis:
• Model A → Overfitting
• Model B → Better generalization
• Choose Model B 77
Practical Considerations & Applications

• Practical Considerations
• Use cross-validation
• Avoid data leakage
• Choose appropriate metric
• Balance model complexity
• Consider computational cost
• Applications
• Model comparison
• Hyperparameter tuning
• Feature selection
• Performance benchmarking

78
Exercise - 1
You are training a deep neural network to classify images of cancerous cells. Your
training set accuracy is 99%, but your validation set accuracy is only 75%. Diagnose the
problem and explain whether the model has high bias or high variance. Propose three
specific, actionable techniques to improve the generalization of this hypothesis without
simply acquiring more data.
• Solution:
• Diagnosis of the Problem
• Training accuracy = 99%
• Validation accuracy = 75%
• This shows a large gap between training and validation performance. The model
performs extremely well on training data but poorly on unseen data.
• As the Nature of the Problem is this model suffers from HIGH VARIANCE (overfitting)
for the reason (i) High training accuracy → Model has learned training data very well
(ii) Low validation accuracy → Poor generalization
• The model is likely memorizing noise and specific patterns in training data instead of
learning general features.
• Why Not High Bias?
• High bias would mean: 79
• Low training accuracy
Exercise - 2
Explain why it is improper to evaluate a hypothesis using the same data used for
training. Discuss the roles of validation sets versus test sets in selecting the best model
among multiple candidates.
• Solution:
• In machine learning, evaluating a hypothesis (model) requires estimating how
well it performs on unseen data. Using the same data for both training and
evaluation leads to misleading results because the model may simply memorize
the data rather than learn general patterns.
• (a) Overfitting Problem
• The model may fit the training data too closely, including noise
• This leads to low training error but high error on new data
The evaluation becomes overly optimistic.
• (b) Overfitting Problem
• The goal is to test generalization ability
• Training data does not represent unseen scenarios
Hence, it fails to measure real-world performance.
• (c) Biased Estimate of Accuracy
• The model has already “seen” the data 80
• Predictions are not independent of training
Results in biased (inflated) accuracy
Example for Exercise - 2
• A model achieves:
• 100% accuracy on training data
• 70% accuracy on new data
• This shows that training accuracy is not reliable.
1. Training Set
• Purpose is to learn model parameters
• Example:
• Train weights in neural network
• Build decision tree
2. Role of Validation Set
• A validation set is a subset of data used to: (i) Tune model parameters (ii) Compare
different models
• Purpose: (i) Helps in model selection (ii) Used during training process
• Uses
• Choosing hyperparameters (e.g., depth of tree)
• Selecting best model among candidates
• Note: Validation data influences model choice, so it cannot be used for final 81
evaluation
 Contd…
3. Role of Test Set
• A test set is a separate dataset used to evaluate the final chosen model for the
purpose of providing an unbiased estimate of model performance
• Key Characteristics (i) Not used during training or model selection (ii) Used only
once at the end
4. Difference Between Validation and Test Sets
Aspect Validation Set Test Set
Purpose Model selection Final evaluation
Usage During training After training
Bias May be biased Unbiased

Frequency Used multiple times Used once

5. Model Selection Process

• Split data into: (i) Training set (ii) Validation set (iii) Test set
• Train multiple models on training data
• Use validation set to: (i) Tune parameters (ii) Select best model 82
• Use test set to, estimate final performance
Exercise - 3
Describe the following methods along with their procedures, advantages and
limitations, (i) Hold-Out Method (ii) k-Fold Cross-Validation (iii) Leave-One-Out Cross-
Validation (LOOCV) (iv) Stratified Cross-Validation (v) Bootstrap Method.
• In machine learning, the true accuracy of a hypothesis refers to its performance
on unseen data. Since only limited data is available, we use statistical techniques
to estimate generalization accuracy. These methods ensure that the model does
not overfit and performs well in real-world scenarios.
1. Hold-Out Method
• Here, the dataset is divided into two parts: (i) Training set (to train the model) (ii)
Test set (to evaluate accuracy)
• Procedure
• Train the model on training data
• Test on unseen test data
• Compute accuracy
• Advantages : Simple and fast
• Disadvantages (i) Less reliable (depends on split) (ii) Inefficient use of data

83
 Contd…
2. k-Fold Cross-Validation
• Data is divided into k equal parts (folds)
• Each fold is used once as test data
• Procedure
[Link] on ( k-1 ) folds
[Link] on remaining fold
[Link] ( k ) times
[Link] the results
• Advantages: (i) Better use of data (ii) More reliable estimate
• Disadvantages is Higher computational cost
3. Leave-One-Out Cross-Validation (LOOCV)
• Special case of k-fold where, k=n(number of data points)
• Procedure
• Train on all data except one point
• Test on that point
• Repeat for all data points
84
• Advantages, is Maximum use of data
• Disadvantages is Very time-consuming
 Contd…
4. Stratified Cross-Validation
• Ensures that each fold has the same class distribution as the full dataset
• Advantages: More accurate for imbalanced datasets
5. Bootstrap Method
• Sampling is done with replacement
• Multiple datasets are generated
• Procedure
• [Link] bootstrap samples
• [Link] and test model repeatedly
• [Link] the results
• Special Case
• 0.632 bootstrap improves estimation accuracy
• Advantages, Effective for small datasets
• Disadvantages is More complex

85
Exercise - 4
Hypothesis H1 (a linear model) has an error of 10% on the training set and 12% on the
test set. Hypothesis H2 (a complex decision tree) has 0% error on the training set and
18% error on the test set. Which hypothesis should be chosen for deployment? Justify
your choice based on the principles of generalization and the bias-variance trade-off.
• Given
• Hypothesis H_1(Linear Model):
• Training error = 10%
• Test error = 12%
• Hypothesis H_2(Complex Decision Tree):
• Training error = 0%
• Test error = 18%
• Goal is to Select the hypothesis that generalizes better to unseen data.
Analysis Based on Generalization
• Hypothesis 𝑯𝟏
• Small gap between training and test error: 12% − 10% = 2%
• Indicates good generalization
• Hypothesis 𝑯𝟐
• Large gap between training and test error: 18% − 0% = 18%
• Indicates poor generalization
86
• Model performs perfectly on training data but poorly on test data → overfitting
 Contd…
• Bias–Variance Trade-off
• 𝐻1 :
• Slightly higher training error → moderate bias
• Small variance → stable predictions
• 𝐻2 :
• Zero training error → very low bias
• Very high variance → unstable predictions
• Interpretation
• 𝐻2 memorizes training data → captures noise
• 𝐻1 captures general pattern → more reliable
• Decision : "Choose Hypothesis " H_1 " for deployment"
• Justification
• Lower test error (12% vs 18%)
• Better generalization performance
• Balanced bias–variance trade-off
• More robust to unseen data
87
• As a result, "A model with slightly higher training error but lower test error is
preferred, as it generalizes better."
Machine Learning - Unsupervised Learning

• No labels are given to the learning algorithm, leaving it

on its own to find structure in its input.
• It is used for clustering population in different groups.
• Unsupervised learning can be a goal in itself
(discovering hidden patterns in data).
• Clustering: You ask the computer to separate similar data into
clusters, this is essential in research and science.
• High Dimension Visualization: Use the computer to help us
visualize high dimension data.
• Generative Models: After a model captures the probability
distribution of your input data, it will be able to generate more
data. This can be very useful to make your classifier more
robust. 88
Clustering
• Here, a set of inputs is to be divided into groups. Unlike in
classification, the groups are not known beforehand, making this
typically an unsupervised task.
• As you can see in the example below, the given dataset points
have been divided into groups identifiable by the colors red,
green and blue.

89
Dimensionality Reduction

• Density estimation:
• The task is to find the distribution of inputs in some space.
• Assign likelihood scores to data, generate new similar data,
understand data structure.
• Dimensionality reduction:
• Reduce the number of features (dimensions) while preserving
essential information.
• It simplifies inputs by mapping them into a lower-dimensional
space.
• Topic modeling is a related problem, where a program is given
a list of human language documents and is tasked to find out
which documents cover similar topics.

90
Unsupervised Learning Algorithms
▪ KNN (K Nearest Neighbors)
▪ K-Means
▪ Hierarchical Clustering.
▪ Agglomerative (Bottom-Up)
▪ Divisive (Top-Down)
▪ Density-Based Clustering (DBSCAN)
▪ Dimensionality Reduction
▪ Principal Component Analysis (PCA)
▪ t-SNE (t-Distributed Stochastic Neighbour Embedding)

91
k-Means Clustering
• Minimize within-cluster variance:
𝑘

𝐽=෎ ෍ ∥ 𝑥 − 𝜇 𝑖 ∥2
𝑥∈𝐶𝑖
𝑖=1
• Algorithm Steps
• Choose k (number of clusters)
• Initialize k centroids randomly
• Assign each point to nearest centroid
• Update centroids as mean of assigned points
• Repeat steps 3–4 until convergence
• Worked Example: Given Data Points: (1,1), (2,1), (4,3), (5,4)
• Step 1:
• k = 2, initial centroids: C1 = (1,1), C2 = (5,4)
• Step 2: Assignment
• Points near (1,1): (1,1), (2,1)
• Points near (5,4): (4,3), (5,4)
• Step 3: Update Centroids
• C1 = (1.5, 1)
• C2 = (4.5, 3.5)
• Repeat until stable
• Advantages (i) Simple and fast (ii) Scales well
• Limitations (i) Requires k in advance (ii) Sensitive to initialization (iii) Assumes spherical 92
clusters
Hierarchical Clustering
• 1. Agglomerative (Bottom-Up)
• Start with individual points
• Merge clusters iteratively
• 2. Divisive (Top-Down)
• Start with all data
• Split recursively
• Linkage Methods
• Single linkage (min distance)
• Complete linkage (max distance)
• Average linkage
• Output : Dendrogram (tree structure)
• Advantages: (i) No need to specify k (ii) Captures hierarchy
• Limitations: (i) Computationally expensive (ii) Sensitive to noise

93
Density-Based Clustering (DBSCAN)
• Clusters are dense regions separated by sparse regions
• Key Concepts
• Core points
• Border points
• Noise points
• Advantages
• Detects arbitrary shapes
• Handles noise
• Limitations
• Sensitive to parameters
• Not suitable for varying densities

94
Dimensionality Reduction
• Motivation
• Reduce number of features
• Improve efficiency
• Remove redundancy
• Principal Component Analysis (PCA)
• Idea
• Transform data into new axes (principal components)
• Maximize variance
• Steps
• Standardize data
• Compute covariance matrix
• Find eigenvectors & eigenvalues
• Select top components
• Benefits
• Reduces complexity
• Removes noise
95
• Visualization
Dimensionality Reduction
• t-SNE (t-Distributed Stochastic Neighbour Embedding)
• Non-linear technique
• Preserves local structure
• Real-World Applications

Technique Application
Clustering Customer segmentation, fraud detection

PCA Image compression, noise reduction

t-SNE Data visualization

Hierarchical Bioinformatics, taxonomy

96
Diagram- supervised and unsupervised learning

• The data in supervised learning is labeled, where as data in

unsupervised learning is unlabeled

97
Semi-supervised learning
• Problems where you have a large amount of input
data and only some of the data is labeled, are called
semi-supervised learning problems.
• These problems sit in between both supervised and
unsupervised learning.
• For example, a photo archive where only some of the
images are labeled, (e.g. dog, cat, person) and the
majority are unlabeled.

98
Reinforcement learning

• A computer program interacts with a dynamic environment in

which it must perform a certain goal (such as driving a vehicle
or playing a game against an opponent).
• The program is provided feedback in terms of rewards and
punishments as it navigates its problem space

99
Exercise - 1
A decision graph is a generalization of a decision tree that allows nodes (i.e., attributes used for
splits) to have multiple parents, rather than just a single parent. The resulting graph must still
be acyclic. Now, consider the XOR function of three binary input attributes, which produces the
value 1 if and only if an odd number of the three input attributes has value 1.
(a) Draw a minimal-sized decision tree for the three-input XOR function. (b) Draw a minimal-
sized decision graph for the three-input XOR function.
Solution: This is a classic comparison between decision trees and decision graphs
for representing the 3-input XOR (parity) function.
Given Function: 3-input XOR
Let inputs be ( A, B, C )
XOR(A,B,C) = 1 if an odd number of inputs are 1
Truth Table
A B C Output
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0 100
1 1 0 0
1 1 1 1
 Contd…
(a) Minimal Decision Tree
• A decision tree cannot reuse substructures, so it must represent all cases
separately.
• Tree (One Possible Minimal Form)

• Explanation
• Root splits on ( A )
• Then on ( B ), then ( C )
• Each path corresponds to one row in the truth table
• Number of leaves = 8 (minimum for full representation)
No subtree sharing → larger structure 101
(b) Minimal Decision Graph
A decision graph allows sharing of identical subtrees → reduces size.
For XOR: XOR(A,B,C) = XOR(XOR(A,B), C), So we reuse the same XOR structure.
• Graph Structure
• More Clearly (Layered View)
• First compute: D = XOR(A,B)
• Then compute: Output = XOR(D,C)

• This is Smaller because,

• The XOR of ( A ) and ( B ) is computed once
• Reused for both branches
• Avoids duplication of subtrees
• Fewer nodes than tree and uses shared substructure
• Conclusion
• (a) Decision tree requires full expansion → larger size
• (b) Decision graph reuses computations → minimal and efficient 102
• Finally Decision graphs are more compact than decision trees for functions like XOR.
Exercise - 2
A major challenge in unsupervised learning is the lack of "ground truth" labels. Critically
analyze the techniques used to evaluate clustering results (e.g., Silhouette Score, Davies-
Bouldin Index) without external labels. What are the limitations of these intrinsic metrics, and
how can domain knowledge be incorporated to validate patterns?
In unsupervised learning, especially clustering, there are no ground truth labels to directly
measure accuracy. Hence, evaluation relies on intrinsic (internal) metrics that assess the quality
of clusters based on data properties such as cohesion and separation.
• Intrinsic Evaluation Metrics
(a) Silhouette Score
• Measures how similar a data point is to its own cluster compared to other
clusters.
b ⅈ −a ⅈ
s(i) =
max a ⅈ , b ⅈ
a ⅈ : Average distance to points in same cluster
𝑏(𝑖): Minimum distance to points in other clusters
• Range
−1 ≤ 𝑠(𝑖) ≤ 1
• Close to 1 → well-clustered
103
• Close to 0 → overlapping clusters
• Negative → misclassified
(b) Davies–Bouldin Index (DBI)

1 𝑆𝑖+𝑆𝑗
Measures average similarity between clusters. 𝐷𝐵𝐼 = σ𝑖 max
𝑘 𝑗≠𝑖 𝑀𝑖𝑗
Si : Intra-cluster distance
𝑀𝑖𝑗 : Distance between cluster centers

Interpretation
Lower DBI → better clustering
High DBI → poor separation
Key Idea of Intrinsic Metrics
Cohesion → points in same cluster should be close
Separation → clusters should be far apart

104
 Limitations of Intrinsic Metrics
(a) No Ground Truth Validation
Metrics evaluate structure, not correctness
Clusters may be mathematically good but not meaningful
(b) Bias Toward Specific Shapes
Metrics favor spherical clusters
Poor performance for: (i) Irregular shapes (ii) Varying densities
(c) Sensitivity to Distance Measures
Results depend on chosen distance metric (Euclidean, etc.)
Different metrics → different evaluations
(d) Curse of Dimensionality
In high dimensions, distances become less meaningful
Metrics lose reliability
(e) Ignores Application Context
Does not consider: (i) Business goals (ii) Practical usefulness

Incorporating Domain Knowledge, Since intrinsic metrics are limited, domain105

knowledge is essential.
(a) Expert Validation
Domain experts interpret clusters
Check if clusters are meaningful
Example: In healthcare, clusters should correspond to real disease categories
(b) Use of Proxy Labels
Compare clusters with partial or indirect labels
Example: Customer segments vs purchase categories
(c) Visualization Techniques
Use tools like PCA or t-SNE to visualize clusters
Helps identify meaningful patterns
(d) Application-Based Validation
Evaluate usefulness in real tasks
Example: Marketing: Do clusters improve targeting?
Fraud detection: Do clusters identify anomalies?
(e) Stability Analysis
Check if clusters remain consistent across:
Different samples
Different parameters
Hence, Intrinsic metrics provide structural evaluation but are insufficient alone;106
combining them with domain knowledge ensures meaningful clustering.
Exercise - 3
A financial institution has millions of transactions but only 0.01% are labeled as fraudulent.
They want to detect new, unknown fraud patterns. (1). Propose an unsupervised learning
strategy to detect anomalies. (2). Which algorithms would you choose, and why? (3). How
would you preprocess the data to handle numerical and categorical features? (4). How would
you define the success of your model, given the lack of labels?
Given Problem
Dataset: Millions of transactions
Fraud labels: Extremely rare (0.01%)
Goal: Detect unknown and evolving fraud patterns

This is an anomaly detection problem suited for unsupervised learning

1. Propose an unsupervised learning strategy to detect anomalies.

Approach: Anomaly Detection
Assume fraudulent transactions are rare and different from normal behavior
Learn the pattern of normal transactions
Identify deviations as anomalies (potential frauds) 107
2. Which algorithms would you choose, and why?
• (a) Isolation Forest
• Randomly partitions data
• Anomalies are isolated faster (shorter paths)
• Why suitable: Scales well to large datasets, works efficiently with high-dimensional
data, and does not require distance calculations.
• (b) One-Class SVM
• Learns boundary around normal data
• Points outside boundary → anomalies
• Why suitable, Good for detecting novel patterns and Works when only normal data is
available
• (c) Autoencoders (Deep Learning)
• Neural network reconstructs input data
• High reconstruction error → anomaly
• Why suitable, Captures complex, non-linear patterns and Effective for large-scale
financial data
• (d) DBSCAN (Optional)
• Density-based clustering
• Points in low-density regions → anomalies 108
• Why suitable, Detects irregular-shaped clusters and Identifies noise naturally
3. How would you preprocess the data to handle numerical and categorical
features?
• (a) Handling Numerical Features
• Normalize or standardize (e.g., Z-score, Min-Max scaling)
• Reduces bias due to scale differences
• (b) Handling Categorical Features
• One-hot encoding (for low-cardinality features)
• Target/frequency encoding (for high-cardinality features like merchant IDs)
• (c) Feature Engineering
• Transaction frequency per user
• Average transaction amount
• Time-based features (hour, day patterns)
• (d) Handling Imbalance
• Focus on modeling normal behavior
• Treat anomalies as rare deviations
• (e) Noise and Outlier Handling
• Remove extreme noise if necessary
• Ensure data quality 109
4. How would you define the success of your model, given the lack of labels?
• Since labels are scarce, we rely on indirect evaluation methods.
• (a) Anomaly Score Distribution
• Check if anomalies are clearly separated
• Identify meaningful thresholds
• (b) Expert Validation
• Domain experts review flagged transactions
• Assess usefulness of detected anomalies
• (c) Stability of Results
• Consistency across:
• Different samples
• Different model runs
• (d) Business Metrics
• Reduction in financial loss
• Increase in detected suspicious cases
• (e) Proxy Evaluation
• Use small labeled subset (if available)
• Measure precision/recall on known fraud cases
• Unsupervised anomaly detection using models like Isolation Forest and
Autoencoders is effective for rare fraud detection
• Focus on learning normal behaviour 110
• Use preprocessing to handle mixed data types
• Combine intrinsic evaluation + domain knowledge for validation