Bayesian Learning

Bayesian Learning helps in making decisions when information is uncertain. It uses probability
to update predictions based on available evidence.

Introduction to Probability-Based Learning

 Probability-based learning combines prior knowledge or prior probabilities with
observed data.
 It uses probability theory to model randomness, uncertainty, and noise for predicting
future events.
 It helps in modelling large datasets and uses Bayes rule to infer unknown quantities,
predict, and learn from data.
 In a probabilistic model, randomness plays a major role and gives probability
distribution as a solution, whereas
o a deterministic model has no randomness.

Example:
Weather Prediction
Suppose a weather forecasting system predicts rain.
 The system uses previous weather information (prior knowledge) and current
observations such as temperature, humidity, and wind speed.
 Since weather conditions are uncertain, the model predicts probabilities like:
o 80% chance of rain
o 20% chance of no rain
 This is a probabilistic model because randomness and uncertainty are considered.

In contrast, a deterministic model would simply state:

 “It will rain” or “It will not rain,” without giving any probability.
Probabilistic learning uses probability theory to model uncertainty and make predictions from
data. The probabilities are usually derived from observed data and statistical calculations.

Bayesian learning is a type of probabilistic learning that uses subjective probabilities based
on prior beliefs or knowledge. These probabilities are updated whenever new evidence
becomes available using Bayes’ rule.

 Subjective probabilities are probabilities based on a person’s belief, experience,

judgment, or interpretation about an event rather than exact calculations or fixed data.
o These probabilities may differ from one person to another and can change when
new information is available.

Bayesian learning works like this:

Old Belief + New Evidence = Updated Belief
or
Prior Probability + New Data → New Probability

Example

Before Exam

A student believes: Probability of passing = 60%

After Preparation and Mock Test

The student studies well and scores high in a mock test.

Now the belief changes: Probability of passing = 90%

So,

Initial belief (60%) + New evidence (good preparation) = Updated belief (90%)

This changing of probabilities based on new information is called Bayesian learning.

Two important Bayesian learning algorithms are:

1. Naïve Bayes Learning
2. Bayesian Belief Network (BBN)

Both use prior probabilities and observed data to make predictions.

Fundamentals of Bayes Theorem
Naïve Bayes Model relies on Bayes theorem and works on three kinds of probabilities:
Prior Probability
Prior probability is the general probability of an uncertain event before any observation is seen
or evidence is collected. It is the initial probability believed before collecting new information.
 Example
o If past records show that 20% of students fail an exam, then before seeing
current results, the prior probability of failure is 0.2.

Likelihood Probability
Likelihood probability is the relative probability of an observation occurring for each class or
the sampling density for the evidence given the hypothesis. It is represented as:

P (Evidence ∣ Hypothesis)

It denotes the likelihood of occurrence of evidence given the parameters.

P (High Marks ∣ Regular Study)

 If a student studies regularly, what is the probability of getting high marks?
This checks how likely the evidence is.

Posterior Probability
Posterior probability is the updated or revised probability of an event after considering
observations from training data. It is represented as:
P (Hypothesis ∣ Evidence)
It represents the belief about the hypothesis after considering evidence from training data.
Posterior probability = prior probability + new evidence
 Example
P (Regular Study ∣ High Marks)

 After seeing high marks, what is the probability that the student studied regularly?
This is the updated belief after observing evidence.
What do we now believe after seeing the evidence?”
Classification Using Bayes Model
Naïve Bayes Classification uses Bayes theorem to classify data into different categories by
calculating posterior probability.
P (Hypothesis h ∣ Evidence E)
where:
 Hypothesis (h) → Target class to be predicted
 Evidence (E) → Input data or test instance
The classifier checks which class has the highest probability for the given evidence.

Bayes Theorem Formula

Posterior probability is calculated using:
 Prior probability P (Hypothesis h)
 Likelihood probability P (Evidence E ∣ Hypothesis h)
 Marginal probability P (Evidence E)

Bayes theorem is written as:

where:
 P(h) is the prior probability of the hypothesis before observing training data.
 P(E) is the prior probability of evidence from the training dataset and is also called
marginal probability.
 P (E ∣ h) is the likelihood probability of evidence given hypothesis.
 P (h ∣ E) is the posterior probability after observing training data.

From Bayes equation:

Posterior Probability ∝ Prior Probability × Likelihood Probability

Bayes theorem helps in calculating posterior probability for multiple hypotheses and
selecting the hypothesis with the highest probability.
Example – Disease Prediction
Suppose a doctor wants to know whether a patient has a disease after a medical test.
Given Data
 5% of people have the disease
P (h) = 0.05
 If a person has the disease, the test becomes positive 90% of the time
P (E ∣ h) = 0.90
 Overall probability of getting a positive test result is 10%
P(E) = 0.10

Apply Bayes Theorem

Calculate

So, after observing the positive test result, the probability that the patient has the disease
becomes 45%.

 Prior Probability → Initial belief before test

 Likelihood Probability → Chance of positive test if disease exists
 Posterior Probability → Updated belief after seeing test result

Thus, Bayes theorem updates old belief using new evidence.

Maximum A Posteriori (MAP) Hypothesis

Given a set of candidate hypotheses, the hypothesis having the maximum value is considered
the most probable hypothesis. This is called the Maximum A Posteriori (MAP) Hypothesis.

 MAP (Maximum A Posteriori) hypothesis means selecting the hypothesis that has
the highest posterior probability after observing evidence.

MAP hypothesis chooses:

“The hypothesis with the highest posterior probability after considering evidence.”
Maximum Likelihood (ML) Hypothesis
If all hypotheses are considered equally probable, then prior probability P(h) is ignored, and
only:
P (E ∣ h)
is used to determine the most probable hypothesis.

Maximum Likelihood (ML) Hypothesis selects the hypothesis that gives the highest likelihood
probability is called the Maximum Likelihood (ML) Hypothesis.

It is represented as:

Example:
Suppose a system wants to identify a fruit.

Possible hypotheses are:

 h1: Fruit is Apple

 h2: Fruit is Orange

Before observing the fruit, assume:

P(h1) = P(h2) = 0.5

This means:
 Apple and Orange are considered equally probable.

Observed Evidence
The fruit is:
 Orange in color
 Round in shape
Now the system checks likelihood:
P (E ∣ h1) = 0.2
P (E ∣ h2) = 0.9
 These features are more likely for an orange.
Since both hypotheses had equal prior probability, the decision depends only on likelihood.
So, the system selects:
hML = Orange
Naïve Bayes Algorithm

Naïve Bayes is a supervised binary class or multi-class classification algorithm based on Bayes
theorem. The algorithm assumes that features are independent of each other.

It works well for:

 Large datasets

 Fast classification

 Binary and multi-class problems

The main advantage of Naïve Bayes is that it independently considers each feature during
classification, making the algorithm simple and efficient.

Some important applications are:

 Text classification

 Recommendation systems

 Spam filtering
Job Offer Prediction

A student’s performance is analyzed using:

 CGPA
 Interactiveness
 Practical Knowledge
 Communication Skills
Target class:

 Job Offer = Yes/No

The dataset contains 10 training instances.

The test data is:

CGPA Interactiveness Practical Knowledge Communication Skills Job Offer

≥9 Yes Average Good ?

Job Offer = ? is the target class to be predicted using the Naïve Bayes algorithm.

The goal is to predict whether the student gets a job offer.

Step 1: Prior Probability
Compute the prior probability for the target feature ‘Job Offer’.
Brute Force Bayes Algorithm
 Considers all possible hypotheses in the hypothesis space H.
 Computes posterior probability for every hypothesis hi ∈ H.
 Selects the hypothesis with maximum probability using MAP hypothesis hMAP.

The algorithm is called “Brute Force” because:

 It checks every possible hypothesis.

 Computation becomes expensive when hypotheses are large.

Bayes Optimal Classifier

Bayes optimal classifier is a probabilistic model, which in fact, uses Bayes theorem to find the
most probable classification for a new instance given the training data by combining the
predictions of all posterior hypotheses.

 Combines predictions from all hypotheses.

 Computes weighted probabilities.

 Selects the class with maximum probability.

 MAP Hypothesis → Chooses only the single best hypothesis.

 Bayes Optimal Classifier → Combines predictions from all hypotheses
Gibbs Algorithm
The main drawback of Bayes optimal classifier is that

 it computes the posterior probability for all hypotheses in the hypothesis space and then
combines the predictions to classify a new instance.

Gibbs algorithm

 is a sampling technique which randomly selects a hypothesis from the hypothesis

space according to the posterior probability distribution and classifies a new instance.
 It is found that the prediction error curve with the Gibbs algorithm when compared to
Bayes Optimal classifier.
Naïve Bayes Algorithm for Continuous Attributes
Naïve Bayes can also handle continuous attributes.

Two methods:

1. Discretize continuous features into discrete features (categories).

2. Apply Gaussian (Normal) Distribution for Continuous features.

Gaussian Naïve Bayes Algorithm

Continuous features are assumed to be sampled from a Gaussian distribution.
Example continuous feature: CGPA
Discrete feature: Interactiveness
VALIDATING AND PRUNING OF DECISION TREES
Since many possible solutions can fit the same training data, the algorithm needs some
“preference” to choose one solution.

That preference is called inductive bias.

Suppose we have training data:

Weather Play Cricket
Sunny Yes
Rainy No
Cloudy Yes
From this small data, many possible decision trees can be created.

The algorithm must decide:

 Which attribute to split first?

 Which tree is best?

 Whether to build a small tree or a large tree?

Without assumptions, the algorithm cannot choose.

So, ID3 uses inductive bias.

Inductive Bias in ID3

ID3 follows two important assumptions:

1. Prefer Shorter Trees

ID3 assumes:

 Smaller and simpler trees are better

than large complex trees.
 This is based on Occam’s Razor
Principle.

Occam’s Razor

 “The simplest solution is the best

solution.”
Both may classify training data correctly. But ID3 prefers Tree 1 because it is simpler.
2. Choose Attribute with Highest Information Gain

While constructing the tree, ID3 selects the attribute that gives maximum information gain.

Suppose attributes are:

Attribute Information Gain
Study Hours 0.8
Attendance 0.5
Internal Marks 0.3
ID3 chooses: Study Hours; because it has the highest information gain.

Complete Flow of ID3 Bias

1. Many possible trees exist

2. ID3 prefers:
o simpler trees
o attributes with highest information gain
3. It builds the tree step-by-step
4. It never backtracks
5. Final tree may not be globally best
6. But it is usually efficient and accurate

Validation in Decision Trees

 Validation means checking whether the decision tree works correctly for new unseen
data.
 A tree may work perfectly for training data but fail for test data. This problem is called
overfitting.

What is Overfitting?
Overfitting happens when the decision tree becomes
too detailed and memorizes the training data.
Example
Suppose a teacher predicts student results using:
 Attendance
 Study hours
 Assignment marks
What is Pruning?

Pruning means removing unnecessary branches from the decision tree to make it simpler and
more accurate.

Purpose of pruning:

 Reduce overfitting

 Improve prediction accuracy

 Simplify the tree

Types of Pruning

Pre-Pruning Post-Pruning

The tree growth is stopped early. First construct the full tree, then remove
unnecessary branches.
Example

While building the tree: Example

Original Tree:

So unnecessary branches are avoided.

Advantage

 Faster Suppose the attendance condition does not

improve accuracy.
 Smaller tree

After pruning:
Disadvantage

 May stop too early

The simpler tree performs better.

Cross Validation (k-Fold Validation)
The dataset is divided into k parts.
Example: 5-fold validation
 Train using 4 parts
 Test using 1 part
 Repeat 5 times
Average error is calculated.
The tree with minimum error is selected.

Occam’s Razor Principle

It says:
“The simplest solution is usually the best.”
So smaller decision trees are preferred over complex trees.

CART and C4.5

CART
 Uses post-pruning
 Uses 10-fold cross validation
C4.5
 Uses heuristic error estimation
 Performs post-pruning

Real-Life Example of Pruning

Without Pruning After Pruning
A bank loan approval tree may check: Only important attributes remain:
 Salary  Salary
 Age  Credit score
 City  Loan history
 Mobile brand This improves prediction for new
 Favorite color customers.

Some conditions are unnecessary.

 Different Pruning Techniques Impact on Overfitting
Reduced Error Pruning  Strong reduction in
overfitting
 Remove a branch
 Improves generalization
 Check validation accuracy
 Keep pruning if accuracy improves
Minimum Error Pruning (MEP)  Reduces unnecessary
branches
Uses probability estimates to calculate expected error.
 Handles noisy data better
Pessimistic Pruning  Avoids over-complex trees
Future error may be worse than training error.  Useful when validation data
is unavailable
It adds a penalty to training error before deciding pruning.
No validation dataset required.
Error-Based Pruning (EBP)  Good balance between
complexity and accuracy
 Estimates error rate statistically
 Reduces overfitting
 Prunes nodes with high estimated error
effectively
Optimal Pruning  Produces highly accurate
tree
Searches for the best possible pruned tree.
Attempts to minimize:
 tree size
 classification error
Minimum Description Length (MDL)  Avoids unnecessary
complexity
Based on information theory.
 Strong control over
Best tree =
overfitting
 smallest encoding size
 minimum classification error
Minimum Message Length (MML) Pruning  Produces compact models
Chooses the tree requiring minimum message length to
describe:
 tree structure
 errors
Critical Value Pruning  Removes statistically weak
branches
Uses statistical tests like:
 Chi-square test
 critical threshold values