Module – 5

Uncertainty & Learning

Agenda
 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

Uncertainty

I. Definition:
Uncertainty refers to situations where an agent does not have complete knowledge about the
environment, the outcomes of its actions, or both. It reflects the inherent unpredictability and
incomplete information that agents face when operating in real-world scenarios.

II. Types of Uncertainty

1. State Uncertainty:
 The agent does not know exactly what the current state of the environment is.
 Example: A robot trying to localize itself in a room with noisy sensors, unsure of its
exact position.

2. Action Uncertainty:
 The outcomes of actions are probabilistic; an intended action may not always
produce the same result.
  Example: A drone attempting to hover may drift due to wind.

3. Perception Uncertainty:
 Information (E.g., sensor readings) may be noisy, ambiguous, or incomplete.
 Example: A camera may misclassify objects or fail to detect obstacles.

4. Model Uncertainty:
 The agent's knowledge of the environment's dynamics may be incomplete or
inaccurate.
 Example: Not knowing the exact behavior of a new robot component.

III. Significance of Uncertainty

 Real-world environments are often unpredictable: Sensors are noisy, environments

change, and outcomes are not deterministic.
 Decision quality depends on managing uncertainty: Properly reasoning about
uncertainty allows agents to make better-informed decisions, leading to more robust
and adaptive behavior.
 Modeling uncertainty enables probabilistic reasoning: It facilitates effective planning,
learning, and acting in complex environments.

IV. Handling Uncertainty

 Probabilistic Models: Use probability distributions to represent uncertain

information.
 Bayesian Inference: Update beliefs based on new evidence.
 Decision Theory: Choose actions that maximize expected utility considering
uncertainty.
 Partially Observable Markov Decision Processes (POMDPs): Frameworks that
model decision-making under uncertainty with incomplete information.

V. Illustration: Weather Forecasting

Imagine you're planning a picnic, and the weather forecast indicates a 70% chance of sunshine
and a 30% chance of rain. This uncertainty influences your decision:
o You might decide to postpone or proceed with plans, weighing the risks.
o Your decision-making process involves reasoning under this uncertainty.
 A. Acting under Uncertainty

I. Definition:
Acting under uncertainty refers to the challenge of making decisions and taking actions in
environments where the outcomes are not deterministic and are instead governed by probabilistic
or unknown factors. Unlike classical AI problems where the agent has complete knowledge of the
environment, in uncertain settings, the agent must reason with incomplete, noisy, or ambiguous
information, and choose actions that maximize expected utility or success despite the inherent
unpredictability.

II. Core Ideas:

 Uncertainty in the Environment: The environment’s response to an agent’s action
may be stochastic, meaning the same action in the same state can lead to different
outcomes with some probability.
 Belief States: Since the agent cannot be certain about the true state of the
environment, it maintains a ‘belief state’, which is a probability distribution over
possible states.
 Decision-Making Under Uncertainty: The agent selects actions based on expected
outcomes, often utilizing probabilistic models such as Bayesian networks or Markov
decision processes (MDPs).

III. Approach:
 The agent models the environment using probabilistic models.
 It updates its beliefs based on new observations using Bayesian updating.
 It uses decision-theoretic frameworks to choose actions that maximize expected
utility or reward.

IV. Illustrative Example: Robot Navigation in a Partially Observable

Environment

Scenario:
Imagine a robot navigating through a grid-based environment, such as a simplified house floor
plan. The robot's goal is to reach a specific location (e.g., a charging station) while avoiding
obstacles such as furniture and walls. The challenge is that the robot's sensors are noisy, and it
cannot always accurately determine its exact position.
Details:
1. Environment:
 A 5x5 grid representing rooms and corridors.
 Certain cells contain obstacles.
 The robot’s starting position is unknown; it only has probabilistic beliefs about its
location.
2. Sensor Model:
 The robot has proximity sensors that detect obstacles.
 Sensor readings are noisy: sometimes they report obstacles when none are present, or
fail to detect actual obstacles.
3. Actions:
 Move forward, turn left, turn right.
 Each movement has a probability of succeeding or slipping into an unintended cell due
to slippage or sensor errors.
4. Uncertainty:
 Because of noisy sensors and imperfect movements, the robot's exact position is
uncertain.
 The robot maintains a ‘belief state’—a probability distribution over all grid cells
indicating where it might be.

Operational Steps:
1. Initial Belief:
 The robot starts with a uniform distribution over all possible positions, reflecting
complete ignorance.
2. Action and Observation:
 The robot chooses an action, say "move forward."
 After executing the action, it receives sensor readings, which may be noisy.

3. Belief Update:
 Using the observed sensor data, the robot updates its belief state via Bayesian filtering.
 It computes the probability of being in each cell given the previous belief, the action
taken, and the new sensor reading.

4. Decision Making:
 The robot plans its next move based on the current belief, aiming to reach the goal with
high probability.
 It might select actions that maximize the expected probability of success, considering
the uncertainty.

5. Repetition:
  This cycle continues—move, observe, update belief, decide—until the robot reaches the
goal location with satisfactory confidence.

In this example, the robot acts under uncertainty because:

 Its true state (position) is not directly observable.

 Its actions are stochastic.
 It relies on probabilistic reasoning to make decisions that maximize the likelihood of
success despite incomplete information.

B. Basic Probability Notations

1. Probability of an event P(A):

 Represents the likelihood that event A occurs.
 Values range between 0 and 1, where 0 indicates impossibility and 1 indicates certainty.
 Example: P(Sunny) = 0.7 means there is a 70% chance that it will be sunny.

2. Sample space (Ω):

 The set of all possible outcomes of a random experiment.
 For example, the sample space for flipping a coin is Ω = {Heads, Tails}.

3. Events:
 Subsets of the sample space.
 An event can be simple (a single outcome) or compound (multiple outcomes).
 Example: The event "the die shows an even number" corresponds to {2, 4, 6}.

4. Conditional probability (P(A|B):

 The probability that event A occurs given that B has occurred.
 Defined as:


 Represents a refined estimate of A’s likelihood after knowing B.
5. Joint probability P(A ∩ B):
 The probability that both A and B occur simultaneously.
 For independent events, P(A ∩ B) = P(A) * P(B).

6. Marginal probability:
 The probability of an event regardless of other variables.
 Can be derived from joint probabilities by summing over the relevant variables.

7. Bayes’ theorem:
 A fundamental rule for computing conditional probabilities:

 Enables updating beliefs based on new evidence.

8. Probability distributions:
 Functions that assign probabilities to each outcome in the sample space.
 Can be discrete (for countable outcomes) or continuous (for uncountable outcomes).

C. Conditional Probabilities

Definition:
Conditional probability quantifies the probability of an event ‘A’ occurring given that another
event ‘B’ has already occurred. It is denoted as P(A∣B) and is defined as:
P(A ∩ B)
P( A ∣ B ) = provided P(B) > 0
P(B)
where:
- P(A∩B) is the probability that both events ‘A’ and ‘B’ occur simultaneously.
- P(B) is the probability that event ‘B’ occurs.
Intuition:
Conditional probability adjusts our belief about the likelihood of ‘A’ based on the new information
that ‘B’ has occurred. If knowing ‘B’ makes ‘A’ more likely, then P(A∣B) will be higher than P(A).
Conversely, if ‘B’ makes ‘A’ less likely, then P(A∣B) will be lower.

Why is Conditional Probability Important?

 It allows us to update beliefs with new evidence.
 It forms the foundation for Bayesian reasoning.
 It helps in modeling real-world situations where information is incomplete or uncertain.

Example Scenario
Scenario: Suppose a medical test is designed to detect a disease. The following probabilities are
known:

 P(D)=0.01: The prior probability that a randomly selected individual has the disease.
 P(Test positive ∣ D)=0.99: The probability that the test is positive given the person has the
disease (sensitivity).
 P(Test positive ∣ ¬D)=0.05: The probability that the test is positive given the person does
not have the disease (false positive rate).
Question: What is the probability that a person actually has the disease given that they tested
positive? In other words, find:
P(D∣Test positive)

Step-by-step Calculation:
 Using ‘Bayes' Theorem’, which relates these probabilities:
𝑃(𝑇𝑒𝑠𝑡 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒 ∣ 𝐷) × 𝑃(𝐷)
𝑃(𝐷 ∣ 𝑇𝑒𝑠𝑡 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒) =
𝑃(𝑇𝑒𝑠𝑡 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒)

where:

 P(Test positive)=P(Test positive∣D)×P(D)+P(Test positive∣¬D)×P(¬D)

 P(¬ D) = 1 - P(D) = 0.99

 Calculating the denominator:

P(Test positive)=(0.99×0.01)+(0.05×0.99)=0.0099+0.0495=0.0594
Now, applying Bayes’ theorem:
 0.99 × 0.01 0.0099
𝑃(𝐷 ∣ 𝑇𝑒𝑠𝑡 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒) = = ≈ 0.1667
0.0594 0.0594

 Interpretation:
Despite the test being highly sensitive, the low prevalence of the disease means that “if a person
tests positive, there is approximately a 16.67% chance they actually have the disease”. This
illustrates how conditional probability helps us interpret test results in the context of prior
information.

D. Full Joint Distributions

Definition:
Full joint probability distribution over a set of random variables is a probability distribution that
specifies the probability of every possible combination of values for these variables. It provides a
comprehensive description of the probabilistic relationships among all variables simultaneously.
Suppose we have ‘n’ random variables 𝑋1, 𝑋2,…, 𝑋𝑛
The full joint probability distribution is:
P(𝑋1=𝑥1 , 𝑋2=𝑥2 ,…, 𝑋𝑛 =𝑥𝑛 )
for all possible combinations of values {𝑥1 , 𝑥2 , … , 𝑥𝑛 }.

Key points:
 It encodes the complete probabilistic information about the variables.
 The sum over all possible combinations equals 1:

 From the full joint distribution, you can derive any marginal or conditional probability by
summing or dividing appropriately.

Why is it Important?
 It serves as the foundational representation in probabilistic modeling.
 Many probabilistic models, such as Bayesian networks, factor the full joint into smaller,
manageable parts.
 It allows for exact computation of probabilities involving any subset of variables.
Example Scenario
Consider two binary variables:

 A: whether it rains today ‘A = rain’ or ‘A = no rain’

 B: whether the sprinkler is on ‘B = on’ or ‘B = off’
Suppose the full joint probability distribution over ‘A’ and ‘B’ is given as follows:

Explanation of the Distribution:

 The probabilities sum to 1:

0.05 + 0.15 + 0.20 + 0.60 = 1.00

 This distribution fully characterizes the joint behavior of rain and sprinkler status.
Deriving Marginal Probabilities:
For example,
o The probability it rains:
P(rain) = P(A=rain) = P(rain,on) + P(rain,off) = 0.05+0.15 = 0.20
o Similarly, the probability the sprinkler is on:
P(B=on) = P(rain,on) + P(no rain,on) = 0.05 + 0.20 = 0.25

Using the Full Joint for Inference:

a. How does inference work with full joint distributions?

Given a set of variables 𝑋1, 𝑋2,…, 𝑋𝑛 , and some observed evidence ‘E’ (a set of variable
assignments), the goal is to compute the probability of some query variable(s) ‘Q’, possibly
conditioned on ‘E’.
Mathematically, this is:
P(Q, E)
P(Q ∣ E) =
P(E)
Where,
 - P(Q,E) is the joint probability of the query and evidence,
- P(E) is the marginal probability of the evidence.

b. How to compute ‘P(Q, E)’ using the full joint distribution?

Since the full joint distribution specifies the probability of every possible combination of
variables, inference involves:

 Identify all configurations of variables that satisfy the query ‘Q’ and evidence ‘E’.
 Sum the probabilities of all these configurations from the full joint distribution.

c. Numerical Example
Recall the previous scenario:

Question:
What is the probability that it rains given that the sprinkler is on?
Mathematically:
P(rain, on)
P( rain ∣ on ) =
P(on)
Step 1: Compute P(rain,on)
From the joint distribution, this is directly:
P(rain,on)=0.05
Step 2: Compute P(on):
Sum over all configurations where B=on:
P(on)=P(rain,on)+P(no rain,on)=0.05+0.20=0.25
Step 3: Calculate the conditional probability
P(rain∣on)=0.250.05=0.20
0.05
P( rain ∣ on ) = = 0.20
0.25
Interpretation: Given that the sprinkler is on, there’s a 20% chance it’s raining.

General Steps for Inference with Full Joint Distributions

 Identify the variables involved in the query and evidence.

 Extract the relevant joint probabilities directly from the full joint distribution.
 Sum over all configurations that match the evidence and query conditions.
 Divide the joint probability of the combined event by the marginal of the evidence to get
the conditional probability.

E. Axioms of Probability

In probability theory, axioms are the fundamental principles that govern the way probabilities are
assigned and manipulated. These axioms provide a rigorous foundation for making reasoning
about uncertainty and probability.
The three axioms of probability are:

1. Non-Negativity Axiom
For any event ‘A’, the probability P(A) must be non-negative:
P(A)≥0
This means that we cannot assign a negative probability to any event.
2. Normalization Axiom
The probability of the entire sample space must be 1:
P(S)=1
where ‘S’ is the sample space. This axiom ensures that the probabilities of all possible outcomes
add up to 1.
3. Countable Additivity Axiom
For any sequence of mutually exclusive events 𝐴1 , 𝐴2 ,…, 𝐴𝑛 ,, the probability of their union is the
sum of their individual probabilities:

This axiom allows us to calculate the probability of a union of mutually exclusive events by simply
adding the probabilities of each event.
Example
Suppose we are rolling a fair six-sided die. Let's define the events:
A: the event that the die lands on an even number (2, 4, or 6)
B: the event that the die lands on an odd number (1, 3, or 5)
C: the event that the die lands on a 2

We want to calculate the probability of the event that the die lands on an even number or a 2.
Using the countable additivity axiom, we can write:
P(A∪C) = P(A)+P(C)
=P(even)+P(2)
=1/2 + 1/6
= 2/3
This means that the probability of the event that the die lands on an even number or on 2 is 2/3.

Bayes Rule and its Applications

A. Bayesian Networks

A Bayesian network is a probabilistic graphical model that represents a set of variables and their
conditional dependencies using a directed acyclic graph (DAG). It is a powerful tool for reasoning
under uncertainty and is widely used in artificial intelligence, machine learning, and data analysis.
Key Components:
1. Nodes: Represent random variables, which can be either discrete or continuous.
2. Edges: Represent conditional dependencies between nodes.
3. Conditional Probability Tables (CPTs): Assign probabilities to each node given its parents.

Example Scenario:
Suppose we want to model the relationship between the following variables:

 `Rain` (R): Whether it will rain or not.

 `Windy` (W): Whether it will be windy or not.
  `Sunny` (S): Whether it will be sunny or not.
 `PlayGolf` (PG): Whether a golfer will play golf or not.
We can represent these variables using a Bayesian network as follows:

Step-wise Explanation:
1. Node `Rain (R)`: We assign probabilities to `Rain` as follows: P(R=Yes) = 0.3, P(R=No)
= 0.7.
2. Node `Windy (W)`: We assign conditional probabilities to `Windy` given `Rain`: P(W|Yes)
= 0.5, P(W|No) = 0.5.
3. Node `Sunny (S)`: We assign conditional probabilities to `Sunny` given `Rain`: P(S|No)
= 0.6, P(S|Yes) = 0.4.
4. Node `PlayGolf (PG)`: We assign conditional probabilities to `PlayGolf` given `Rain` and
`Sunny`: P(PG|Yes,S) = 0.8, P(PG|No,S) = 0.2, P(PG|Yes,W) = 0.2, P(PG|No,W) = 0.8.

Inference:
 Suppose we want to find the probability that a golfer will play golf given that it will be
sunny and rainy: P(PG|S,Yes) =?
 Using the CPTs, we can calculate this probability as follows:
P(PG|S,Yes) = P(PG|Yes,S) * P(S|Yes) * P(Yes) + P(PG|No,S) * P(S|Yes) * P(No)
= 0.8 * 0.4 * 0.3 + 0.2 * 0.4 * 0.7
= 0.096 + 0.056
= 0.152
Therefore, the probability that a golfer will play golf given that it will be sunny and rainy
is approximately 15.2%.
Basics of Learning

Machine Learning
 Definition
 A Machine Learning system learns from historical data, builds the prediction models,
and whenever it receives new data, predicts the output for it.
 The accuracy of predicted output depends upon the amount of data, as the huge
amount of data helps to build a better model which predicts the output more
accurately.

 Importance of ML
 Finding hidden patterns and extracting useful information from data
 Solving complex problems and decision making in many fields (applications)

 Feature of ML: Data-Driven Technology

 similar to data mining as it also deals with huge amount of data.
 uses data to detect various patterns in a given dataset
 learn from past data and improve automatically.

Lifecycle of Machine Learning

 Gathering Data
 To identify the different data sources, as data can be collected from various sources such
as files, database or internet.
 The quantity and quality of the collected data will determine the accuracy of the
prediction and efficiency of the output.
 This step includes the below tasks:
 Identify various data sources
 Collect data
 Integrate the data obtained from different sources – This coherent set of data is
called dataset

 Data Preparation: This step can be further divided into two processes:
 Data exploration: To understand the characteristics, format, and quality of data to find
Correlations, general trends, and outliers for an effective outcome.
 Data pre-processing: Cleaning of data is required to address the quality issues: Missing
Values, Duplicate data, Invalid data and Noise, which can be solved using filtering
techniques.
 Data Wrangling
 Reorganizing, mapping and transforming raw, unstructured data to a useable format.
 This step involves data aggregation and data visualization.

 Data Analysis
 The aim of this step is to build a machine learning model to analyze the data and review
the outcome.

 Train Model
 Datasets are used to train the model using various machine learning algorithms – to
understand various patterns, rules, and, features.

 Test Model
 Tests accuracy of the model with respect to the requirements of project or problem.

 Deployment
 Performance of the project is checked with the available data and deployed which is
similar to making the final report for a project.

Types of Machine Learning

Machine Learning (ML) is broadly categorized based on the nature of the learning process and
the type of data available. The main types are:

1. Supervised Learning
 Definition: The system learns from labeled data, where each training example has an input
and a corresponding correct output.
 Goal: To learn a mapping from inputs to outputs so that the model can predict the output
for new, unseen inputs.
 Examples: Email spam detection, handwriting recognition, house price prediction.
 Key Techniques: Classification, Regression.
2. Unsupervised Learning
 Definition: The system learns patterns from unlabeled data without predefined outputs.
 Goal: To discover inherent structures, patterns, or groupings in data.
 Examples: Clustering customers into segments, reducing dimensionality with PCA,
anomaly detection.
 Key Techniques: Clustering, Dimensionality Reduction, Association Rule Learning.

3. Semi-Supervised Learning
 Definition: Uses a small amount of labeled data along with a large amount of unlabeled
data.
 Goal: To improve learning accuracy when labeling data is expensive or time-consuming.
 Examples: Image classification with limited labeled images.

4. Reinforcement Learning
 Definition: The system learns by interacting with an environment, receiving feedback in
the form of rewards or penalties.
 Goal: To learn a policy that maximizes cumulative reward over time.
 Examples: Game playing (e.g., AlphaGo), robotics, autonomous driving.
 Key Concepts: Agent, Environment, Rewards, States, Actions.

A. Supervised Learning

Definition
Supervised learning is a core concept in machine learning where the goal is to learn a function that
maps inputs to outputs based on example input-output pairs provided during training. It is called
"supervised" because the learning process is guided by a supervisor (the labeled data), which
provides the correct answers.

Fundamental Idea
Provided with the dataset consisting of pairs (x, y), where:
- ‘x’ represents the input features (e.g., features of an object, measurements, or data points).
- ‘y’ represents the corresponding label or output (e.g., class labels, numerical values).
The objective is to learn a function f(x) that predicts ‘y’ from ‘x’ accurately for new, unseen data.
Process of Supervised Learning

1. Training Data Collection: Gather a dataset of input-output pairs.

2. Model Selection: Choose a model (e.g., linear regression, neural network).
3. Learning: Use the training data to adjust the model parameters to minimize prediction errors.
4. Evaluation: Test the model on new data to assess its accuracy and generalization.

Scenario-Based Explanation
Scenario: Email Spam Detection
Suppose you want to develop a spam filter for emails. You have a dataset of emails, each labeled
as "spam" or "not spam" (ham). Here’s how supervised learning applies:
- Input features ‘x’: Characteristics of each email such as the presence of certain keywords,
sender reputation, email length, or the number of links.
- Output label ‘y’: Whether the email is "spam" or "not spam".

Training Phase:

 You compile a large dataset of emails with known labels (spam/not spam).
 The learning algorithm examines this data to find patterns that distinguish spam from
legitimate emails.
 For example, it might learn that emails containing the phrase "Win a prize" are likely spam.
Prediction Phase:

 When a new email arrives, the trained model analyzes its features.
 It predicts whether the email is spam or not based on what it learned.
 If the model predicts "spam" with high confidence, the email can be filtered out.
Key Aspects
 Labeled Data: Supervised learning relies on labeled datasets, where each example is
annotated with the correct output.
 Error Minimization: The learning process involves minimizing the difference between the
predicted outputs and the true labels, often through techniques like least squares, cross-
entropy, or other loss functions.
 Generalization: The ultimate goal is for the model to perform well on new, unseen data,
not just the training data.

Additional Examples
 Handwritten Digit Recognition: Input images of handwritten digits (0-9), with labels
indicating which digit each image represents.
 Medical Diagnosis: Patient data (symptoms, test results) as inputs, with disease diagnosis
as labels.
 House Price Prediction: Features like size, location, and number of bedrooms as inputs;
house prices as outputs.

Types of Supervised Learning

Supervised learning can be broadly classified into:
1. Regression
 Purpose: Predict continuous, real-valued outputs.
 Example: Predict house prices based on features like size, location, and age.
 Model Types: Linear regression, polynomial regression, neural networks.

2. Classification
 Purpose: Assign inputs to discrete categories or classes.
 Example: Spam detection (spam vs. not spam), handwriting digit recognition (digits 0-9).
 Model Types: Logistic regression, decision trees, support vector machines, neural
networks.

Advantages of Supervised Learning

 Clear Objective: The availability of labeled data provides a clear target for learning.
 Performance: When sufficient high-quality data is available, supervised learning models
often achieve high accuracy.
 Interpretability: Some models (like decision trees) are interpretable, making it easier to
understand the decision process.
 Broad Applicability: Suitable for many real-world tasks where labeled data is accessible.
Disadvantages of Supervised Learning
 Requires Labeled Data: Gathering labeled datasets can be expensive and time-consuming.
 Overfitting Risks: Models may perform well on training data but poorly on unseen data if
they overfit.
 Limited to Known Labels: Cannot handle tasks where labels are unknown or ambiguous.
 Data Bias: Biased training data can lead to biased models, affecting fairness and accuracy.
 Poor Performance with Insufficient Data: When training data is scarce, models may not
learn effectively.

B. Learning Decision Trees

Introduction
A decision tree is a supervised machine learning model used for classification and regression tasks.
It models decisions and their possible consequences in a tree-like structure, where each internal
node represents a test on an attribute, each branch represents the outcome of that test, and each
leaf node represents a class label (for classification) or a numerical value (for regression).

Core Concepts
 Root Node: The topmost node, representing the first decision.
 Internal Nodes: Decision points based on attribute tests.
 Branches: Outcomes of a test, leading to subsequent nodes.
 Leaf Nodes: Final classification or output.

Decision trees are built using a recursive partitioning process, selecting the attribute that best
separates the data at each step, typically based on a measure like information gain or Gini impurity.
Decision Tree Algorithm- Working
• Step-1: Begin the tree with the root node, says S, which contains the complete dataset.
• Step-2: Find the best attribute in the dataset using Attribute Selection Measure (ASM).
• Step-3: Divide the S into subsets that contains possible values for the best attributes.
• Step-4: Generate the decision tree node, which contains the best attribute.
• Step-5: Recursively make new decision trees using the subsets of the dataset created in
step -3. Continue this process until a stage is reached where you cannot further classify the
nodes and called the final node as a leaf node.

Attribute Selection Measures

1. Entropy:
Entropy is a measure of impurity, disorder or uncertainty within a dataset, typically ranging
from 0 to 1 for binary classification.

2. Information Gain
 Information gain is the measurement of changes in entropy after the segmentation of
a dataset based on an attribute.
 It calculates how much information a feature provides us about a class.
 According to the value of information gain, we split the node and build the decision
tree.
 A decision tree algorithm always tries to maximize the value of information gain, and
a node/attribute having the highest information gain is split first. It can be calculated
using the below formula:
 Information Gain= Entropy(S)- [(Weighted Avg) *Entropy (each feature)]

3. Gini Index
 Gini index is a measure of impurity or purity used while creating a decision tree in the
CART (Classification and Regression Tree) algorithm.
 An attribute with the low Gini index should be preferred as compared to the high
Gini index.
 It only creates binary splits, and the CART algorithm uses the Gini index to create
binary splits.
 Gini index can be calculated using the below formula:
o Gini Index= 1 - ∑jPj2
Scenario: Suppose we want to classify whether an email is spam or not spam based on two
attributes:
• Contains the word "offer" (Yes/No)
• Contains the word "buy" (Yes/No)
Our dataset:

1. Calculating the Overall Entropy

The goal in building a decision tree is to split the data to maximize information gain (reduce
entropy).
Total data:
Spam: 2
Not Spam: 2
Total instances = 4

Entropy of the entire dataset:

Where,

2. Calculating Information Gain for Each Attribute

a. Attribute: "Contains 'offer'"

 Yes: 2 instances (Emails 1 and 2)

- Spam: 2
- Not Spam: 0
 No: 2 instances (Emails 3 and 4)
 - Spam: 0
- Not Spam: 2
Entropy after split:

 For "Yes" branch:

 For "No" branch:

 Weighted entropy:

 Information gain:

b. Attribute: "Contains 'buy'"

 Yes: 2 instances (Emails 1 and 3)

- Spam: 1
- Not Spam: 1
 No: 2 instances (Emails 2 and 4)
- Spam: 1
- Not Spam: 1

Entropy for "Yes" branch:

Similarly, for "No" branch:

Weighted entropy:
Information gain:

3. Choosing the Attribute to Split

Since "Contains 'offer'" yields the highest information gain (1 bit), we select "Contains 'offer'" as
the root node.

Summary of the Process

- Calculate the entropy of the entire dataset.
- Compute the information gain for each attribute.
- Choose the attribute with the highest information gain as the decision node.
- Split the dataset based on this attribute, and recursively repeat the process for each subset
until all data are classified or no attributes remain.

C. Evaluating and Choosing the Best Hypothesis

Introduction
In machine learning and inductive learning, the process of evaluating hypotheses involves assessing
how well a candidate hypothesis explains the observed data. The goal is to select the best
hypothesis from a set of candidates that most accurately models the underlying concept or pattern.
This process is fundamental because the quality of the learned hypothesis directly impacts the
system's ability to make correct predictions on new, unseen data.

Scenario-Based Example
Scenario: Learning to Classify Fruits
Suppose we have a small dataset of fruits characterized by two attributes:
Our goal: Learn a hypothesis that accurately classifies fruits based on color and size.

Step 1: Generate Candidate Hypotheses

From the data, the system generates several hypotheses:
H1: Fruit is an Apple if color is Red.
H2: Fruit is an Apple if size is Large.
H3: Fruit is an Apple if color is Green OR size is Large.
H4: Fruit is a Banana if color is Yellow.

Step 2: Evaluate Each Hypothesis

Evaluate the hypotheses based on consistency — how many data points they correctly classify.
1. H1: Color is Red
Classifies:
Fruit 1 (Red, Large): Correctly classified as Apple.
Fruit 2 (Red, Small): Correctly classified as Cherry? Since H1 classifies all Red as Apple, it would
misclassify Fruit 2.
Fruit 3 (Green): Not Red, so not classified as Apple.
Fruit 4 (Yellow): Not Red.
Correct classifications:
Fruit 1: Yes
Fruit 2: No (misclassified)
Fruit 3: No
Fruit 4: No

Accuracy: 1 out of 4 → 25%

2. H2: Size is Large

Classifies:
Fruit 1 (Large): Apple → correct
Fruit 2 (Small): Cherry? Not Apple.
Fruit 3 (Large): Apple → correct
Fruit 4 (Small): Banana? Not Apple.
Correct classifications:
Fruits 1 and 3: correct
Fruits 2 and 4: misclassified

Accuracy: 2 out of 4 → 50%

3. H3: Color is Green OR Size is Large

Classifies:
Fruit 1 (Red, Large): Size is Large → Apple → correct
Fruit 2 (Red, Small): Neither Green nor Large → misclassified as Cherry
Fruit 3 (Green, Large): Green or Large → Apple → correct
Fruit 4 (Yellow, Small): Neither Green nor Large → misclassified as Banana
Correct classifications:
Fruits 1 and 3: correct
Fruits 2 and 4: misclassified

Accuracy: 2 out of 4 → 50%

4. H4: Color is Yellow

Classifies:
Fruit 4 (Yellow): Banana → correct
Other fruits: not Yellow, so no classification, or classify as Not Banana.
Since the hypothesis only classifies Yellow as Banana, it only correctly classifies one fruit.

Accuracy: 1 out of 4 → 25%

Step 3: Select the Best Hypothesis
Based on the evaluation:

H2 and H3 are the best candidates with 50% accuracy.

Step 4: Handling Trade-offs and Overfitting

While H2 and H3 perform equally on training data, further criteria such as simplicity (prefer
hypotheses with fewer conditions) or validation on unseen data are used to select the best
hypothesis.

Suppose we prefer the simpler hypothesis:

H2: Size is Large (simple and interpretable)
H3: Color is Green OR Size is Large (more complex)

Thus, we would select H2.

Summary of the Evaluation Process

 Generate a set of candidate hypotheses.

 Measure how well each hypothesis fits the existing data (e.g., accuracy, consistency).
 Choose the hypothesis with the highest evaluation score, considering simplicity and
generalization.

D. Unsupervised Learning

Definition:
Unsupervised learning is a type of machine learning where the system is provided with unlabeled
data — that is, data without explicit instructions on what to predict or classify. The goal of
unsupervised learning is to discover underlying patterns, structures, or relationships within the data
itself without predefined labels or outputs.
Core Idea:
Unlike supervised learning, where models learn from labeled examples to make predictions,
unsupervised learning explores the data to find natural groupings (clustering), detect anomalies, or
reduce the data's dimensionality. It aims to understand the data's structure rather than predict
specific outcomes.

Scenario-Based Explanation
Scenario: Customer Segmentation for a Retail Business
Imagine a retail company has collected data on thousands of customers. This data includes features
such as age, income, shopping frequency, and purchase history. The company wants to segment
customers into distinct groups to tailor marketing strategies but does not have predefined labels
like "high-value customers" or "bargain hunters."

How Unsupervised Learning Applies:

- Without labels, the system analyzes the raw data.

- It identifies natural groupings or clusters of similar customers based on their features.
- These clusters might reveal, for example:
o Young, high-income, frequent shoppers.
o Older, moderate-income, infrequent shoppers.
o Budget-conscious, frequent bargain hunters.

Outcome: The company can now target each segment with customized marketing campaigns,
improving customer engagement and sales efficiency.
Key Techniques in Unsupervised Learning
1. Clustering:
- Purpose: Group similar data points together.
- Example algorithms: K-means, hierarchical clustering, DBSCAN.
- Use case: Market segmentation, image segmentation, document clustering.

2. Dimensionality Reduction:
- Purpose: Reduce the number of features while preserving the structure.
- Example algorithms: Principal Component Analysis (PCA), t-SNE.
- Use case: Visualizing high-dimensional data, noise reduction.
3. Association Rule Learning:
- Purpose: Find rules that describe large portions of data.
- Example algorithms: Apriori, Eclat.
- Use case: Market basket analysis (e.g., "people who buy bread often buy butter").

Advantages of Unsupervised Learning

 No need for labeled data: Collecting labels can be expensive and time-consuming.
 Discovery of hidden patterns: Can reveal insights that are not apparent through labeled
data.
 Pre-processing: Useful for feature extraction, data compression, and noise reduction.

Challenges
 Evaluation: It's often difficult to measure the correctness of the learned patterns because
there's no ground truth.
 Interpretability: Results such as clusters may not always be meaningful or easy to
interpret.
 Choice of parameters: Algorithms like k-means require selecting the number of clusters,
which may not be obvious.