Module-1

Introduction to
Machine Learning

Dr. Shagun Sharma

Assistant Professor (SCOPE)
VIT Bhopal University, Sehore Date: 02.07.2025

1
 1. Preface of Machine Learning
2. Types of Learning :
❖ Supervised
❖ Unsupervised Learning
❖ Reinforcement
3. Theory of learning – feasibility of learning – error
Contents and noise – training versus testing
4. Theory of generalization – generalization bound –
approximation-generalization tradeoff – bias and
variance – learning curve
5. Finite and Infinite Hypothesis Spaces, Probably
Approximately Correct (PAC) Learning-Bayes
theorem
Dr. Shagun Sharma 6. MDL principle. 2
 01
Preface of
Machine Learning

3 Dr. Shagun Sharma VIT Bhopal University, Sehore

 4

Preface of Machine Learning

Machine Learning
● Machine Learning (ML) is a field of computer science that
focuses on building systems that can learn from data and
improve their performance over time without being explicitly
programmed. Instead of writing rules manually, we feed
examples to a machine and let it learn patterns automatically.
OR
● Machine learning (ML) is a branch of artificial intelligence (AI)
focused on enabling computers and machines to imitate the way
that humans learn, to perform tasks autonomously, and to
improve their performance and accuracy through experience
and exposure to more data.
Dr. Shagun Sharma VIT Bhopal University, Sehore
4
 5

Preface of Machine Learning

Process of Machine Learning

Dr. Shagun Sharma VIT Bhopal University, Sehore

5
 02
Types of
Machine Learning

6 Dr. Shagun Sharma VIT Bhopal University, Sehore

 7

Types of Learning
Types of Machine Learning

Dr. Shagun Sharma VIT Bhopal University, Sehore

7
 8

Types of Machine Learning

Supervised Machine Learning
● Supervised machine learning is a type of machine learning
where an algorithm learns from a labeled dataset to make
predictions or classifications. The algorithm is trained on data
that includes both input features and the corresponding correct
output, allowing it to learn the relationship between them and
apply that knowledge to new, unseen data.

Dr. Shagun Sharma VIT Bhopal University, Sehore

8
 9

Types of Machine Learning

Supervised Machine Learning

Dr. Shagun Sharma VIT Bhopal University, Sehore

9
 10

Types of Machine Learning

Unsupervised Machine Learning
● Unsupervised machine learning is a type of machine learning
where algorithms learn from unlabeled data without explicit
guidance or labeled outputs. The goal is to discover hidden
patterns, relationships, and structures within the data by
exploring it. Unlike supervised learning, there are no correct
answers or pre-defined categories provided to the algorithm.

Dr. Shagun Sharma VIT Bhopal University, Sehore

10
 11

Types of Machine Learning

Unsupervised Machine Learning

Dr. Shagun Sharma VIT Bhopal University, Sehore

11
 12

Types of Machine Learning

Reinforcement Learning
● Reinforcement learning (RL) is a machine learning paradigm
where an agent learns to make decisions by interacting with an
environment to maximize a cumulative reward. It's a
trial-and-error approach where the agent explores different
actions, receives feedback in the form of rewards or penalties,
and adjusts its behavior to achieve the best long-term outcome.

Dr. Shagun Sharma VIT Bhopal University, Sehore

12
 13

Types of Machine Learning

Concept of reinforcement Learning: How it Works
● Exploration: The agent starts by exploring the environment,
trying different actions.
● Feedback: The agent receives feedback (rewards or penalties)
based on its actions.
● Learning: The agent adjusts its policy to favor actions that lead
to higher rewards.
● Iteration: This process repeats, allowing the agent to gradually
learn the optimal policy for maximizing its cumulative reward.

Dr. Shagun Sharma VIT Bhopal University, Sehore

13
 14

Types of Machine Learning

Reinforcement Learning

Dr. Shagun Sharma VIT Bhopal University, Sehore 14

 03
Theory of learning –
feasibility of learning –
error and noise –
training versus testing
15 Dr. Shagun Sharma VIT Bhopal University, Sehore
 16

Theory of learning

● The Theory of Learning in machine learning studies how and

when a machine can learn a function (or pattern) from data. It
answers questions like:
○ Can a machine learn a task just by seeing examples?
○ How many examples are needed?
○ How accurate will the learned function be?

Dr. Shagun Sharma VIT Bhopal University, Sehore

16
 17

Feasibility of learning
This focuses on whether learning is practically possible:

● Can we learn a hypothesis with limited data and time?

● Does a hypothesis class (the space of functions the model can
learn) contain a function close to the true one?
Feasibility depends on:
● The complexity of the target function
● The amount of training data
● The learning algorithm’s capability
If learning is not feasible, no matter how good the algorithm is, it
won’t learn a useful pattern.

Dr. Shagun Sharma VIT Bhopal University, Sehore

17
 18

Error and noise

In any learning system, two key challenges are:
🔹 Error
● Training Error (Empirical Risk): The error on the training data.
● Generalization Error: The error on new, unseen data.

🔹 Noise
● Noise is random variation or irrelevant information in the data. It
can come from:
● Measurement errors
● Inconsistent human labels
● Random fluctuations
Noise makes it harder to find accurate patterns, and may cause
overfitting. 18
Dr. Shagun Sharma VIT Bhopal University, Sehore
 19

Training Vs Testing
Training
● Training is the phase in machine learning where the model learns
from data. During this phase, the model is provided with a
labeled dataset containing both input features and their
corresponding outputs.
● The algorithm uses this data to identify patterns, adjust internal
parameters like weights, and minimize the prediction error. The
goal of training is to make the model learn how to make accurate
predictions based on past examples. The better the training
process, the more effective the model becomes at capturing the
underlying structure of the data.
Dr. Shagun Sharma VIT Bhopal University, Sehore
19
 20

Training Vs Testing
Testing
● Testing is the phase where the trained model is evaluated on
new, unseen data to measure its performance. The testing data
is separate from the training data and is used to check how well
the model generalizes to real-world or future cases.
● By comparing the model’s predictions on the test data with the
actual values, we can assess its accuracy, precision, recall, and
other metrics. If a model performs well on training data but
poorly on testing data, it indicates overfitting—meaning the
model has memorized rather than learned. Testing ensures the
model is reliable and robust for practical use.
Dr. Shagun Sharma VIT Bhopal University, Sehore
20
 21

Difference between Training Vs Testing Data

Features Training Data Testing Data

Purpose Used to train the model (learn patterns) Used to evaluate model performance

Model Access Model has access to this data during training Model never sees this data during training

Used For Learning weights, parameters, and making the model better Validating generalization ability

Size Usually larger (e.g., 70-80% of the total dataset) Smaller (e.g., 20-30% of the total dataset)

Evaluation Helps reduce training error Helps measure test error (generalization error)

Overfitting Cannot detect overfitting alone Helps detect if model is overfitting the training data
Check

Examples Historical labeled data used to "teach" the model New unseen examples used to "quiz" the model

Dr. Shagun Sharma VIT Bhopal University, Sehore

21
 22

Overfitting Vs Underfitting
Overfitting
● Overfitting occurs when a model learns the training data too
well, including its noise, leading to poor performance on new,
unseen data
Underfitting
● Underfitting happens when the model is too simple to capture
the underlying patterns in the training data, resulting in poor
performance on both training and new data.

Dr. Shagun Sharma VIT Bhopal University, Sehore

22
 04
Theory of generalization –
generalization bound –
approximation-generalizatio
n tradeoff – bias and
variance – learning curve
23 Dr. Shagun Sharma VIT Bhopal University, Sehore
 24

Theory of generalization
Theory of generalization
● The theory of generalization refers to a model’s ability to
perform well on new, unseen data after being trained on a
specific dataset.
● It's a crucial concept because the ultimate goal is for a model to
be useful in real-world scenarios, not just with the data it was
initially trained on.
● It answers: "How well will the model do on future data?"

● Goal in ML: Minimize not just the training error but also the
generalization error (i.e., error on test data).
Dr. Shagun Sharma VIT Bhopal University, Sehore
24
 25

Generalization Bound
Generalization Bound
● A mathematical bound on the difference between training error
and generalization error.

● It shows how likely it is that the model will perform well on

unseen data.

● Key insight: More training data and simpler models usually lead
to tighter (better) bounds.

● PAC Learning helps in deriving such bounds (Probably

Approximately Correct).
Dr. Shagun Sharma VIT Bhopal University, Sehore
25
 26

Generalization Bound

Dr. Shagun Sharma VIT Bhopal University, Sehore

26
 27

Approximation-generalization tradeoff
Approximation error
● How well the model can fit the true function (depends on model
capacity).
Generalization error
● How well it performs on unseen data.
Trade-off
● Balancing the complexity of the model to reduce both errors
simultaneously.
High-capacity models (complex): Low approximation error, but risk
overfitting (high generalization error).
Low-capacity models (simple): High approximation error, but may
generalize better.
Dr. Shagun Sharma VIT Bhopal University, Sehore
27
 28

Bias and Variance

In machine learning, bias and variance are two key sources of error
that affect how well a model performs on unseen data
(generalization). Understanding them helps in choosing the right
model and avoiding underfitting or overfitting.

Bias: Bias is the error due to overly simplistic assumptions made by

the model. (Wrong Learning)

● It reflects how far the model’s predictions are from the actual
values.
● High bias means the model is too simple and can’t capture the
underlying patterns in the data.
28
 29

Bias and Variance

Imagine a student preparing for a math test.
Let's see how bias and variance affect their performance.

Example of Bias

● The student learns only basic formulas and simple examples.

● They ignore complex problems or misunderstand the concepts.
So in the exam, they make the same kinds of mistakes on every
question, even if the questions are different.
This is high bias — the student (or model) is too simple and can't
understand the real problem.
In ML terms: The model is too simple → underfitting.
29
 30

Bias and Variance

In machine learning, bias and variance are two key sources of error
that affect how well a model performs on unseen data
(generalization). Understanding them helps in choosing the right
model and avoiding underfitting or overfitting.

Variance: Variance is the error due to the model's sensitivity to small

changes in the training data. (Too Much Learning (Even the Noise))

30
 31

Bias and Variance

Example of Variance

● Another student memorizes every single example from their

notes.
● If the teacher changes even a little part of the question, the
student gets confused.
This student did too much rote learning, and didn’t learn the actual
concept.
This is high variance — the student (or model) becomes too sensitive
to training data.
In ML terms: The model is too complex → overfitting.
31
 32

Difference Between Bias and Variance

Feature Bias Variance

🔍 Definition Error due to wrong assumptions or an overly simple Error due to too much sensitivity to the training data
model

🎯 Focus How far off are the predictions from actual values (on How spread out are the predictions across different
average)? training sets?

📉 Effect Leads to underfitting (poor performance on both train and Leads to overfitting (good on train but poor on test
test data) data)

🧠 Cause Model is too simple, doesn't learn enough patterns Model is too complex, memorizes the data (including
noise)

📊 Training High training error Low training error

Error

📊 Test Error High test error High test error (but training error is low)

🛠 Fix it by Making model more complex (add layers, features) Making model simpler (regularization, pruning, etc.)

🎓 Example Linear model trying to fit non-linear data Deep decision tree fitting every point exactly
32
 33

Bias and Variance

Finding the balance between Bias and Variance

Model Type Bias Variance Outcome

Too Simple (e.g., Linear) High Low Underfitting

Too Complex (e.g., Deep Tree) Low High Overfitting

Just Right Low Low Good generalization

33
 34

Bias and Variance (Dart Board Example)

Low Bias – Low Variance (Best Case)
● Accurate and consistent.
Darts are scattered all over the board, some
near the center. (LB, and HV)
● The model guesses differently each time.
● The model is confused by training data →
Overfitting.
Darts are grouped together but far from the
center. (HB, and LV)
● The model always guesses wrong in the
same way.
● The model makes systematic mistakes →
Underfitting.
High Bias – High Variance
● Darts are far from the center and
scattered.
● The model is both wrong and
inconsistent.
● The worst case – bad predictions and 34
 35

Ways to balance Bias and Variance

1. Choose the Right Model Complexity

2. Use Cross-Validation

3. Apply Regularization

4. Get More Training Data

5. Use Ensemble Methods

6. Data Augmentation
35
 36

Learning Curve

Why is a Tradeoff?

● If you try to reduce bias (by making the model more complex),
you increase variance.

● If you try to reduce variance (by making the model simpler), you
increase bias.

● So, you can’t reduce both at the same time.

● You must find a balance.

36
 37

Learning Curve

37
 05
Finite and Infinite
Hypothesis Spaces, Probably
Approximately Correct (PAC)
Learning- Bayes theorem

38 Dr. Shagun Sharma VIT Bhopal University, Sehore

 39

Finite and Infinite Hypothesis Spaces

Hypothesis
● A hypothesis is a possible solution (model) that can explain the
relationship between inputs and outputs in your data.
● The hypothesis space is the set of all models your algorithm can
possibly choose from during training.
Finite Hypothesis Space
● The total number of possible models is limited (countable).
● Example: A decision tree with only 3 possible splits, or a
classifier that can only choose between 10 different rules.
● Easy to analyze, less complex, but might be too small to capture
the real pattern → may lead to high bias.
Dr. Shagun Sharma VIT Bhopal University, Sehore
39
 40

Finite and Infinite Hypothesis Spaces

Infinite Hypothesis Space
● The number of possible models is unlimited or uncountably
large.

● Example: A linear regression model with real-valued weights →

weights can be any number on the number line.

● More flexible, can capture complex patterns, but can also overfit
→ may lead to high variance.

Dr. Shagun Sharma VIT Bhopal University, Sehore

40
 41

Probably Approximately Correct (PAC) Learning

PAC: PAC (Probably Approximately Correct) Learning is a theoretical

framework that helps us understand:
● Can a machine learning algorithm learn a good model from a
limited amount of data, with high confidence?
Word Meaning (in ML terms)

Probably With high probability (e.g., 95%)

Approximately The model may not be perfect, but it is "good enough" (within some small error ε)

Correct The model makes few mistakes on new, unseen data

The model will, with high probability, make predictions that are
approximately correct (i.e., the error is small)
41
 42

Probably Approximately Correct (PAC) Learning

Example:
You're training a spam email detector.

● You don’t expect zero errors.

● But you want the detector to be right most of the time (say,
95%).
● And you want to be confident that it will work just as well on new
emails.
PAC Learning helps you mathematically guarantee that this can
happen if:
● You have a good learning algorithm
● You provide enough training data
42
 43

Probably Approximately Correct (PAC) Learning

Key Terms in PAC

Term Symbol What it means

Accuracy (Approximation) ε (epsilon) Allowed error between predicted and true values

Confidence (Probability) δ (delta) Allowed chance that the algorithm fails

Hypothesis space H Set of all models the algorithm can choose from

Sample size m Number of training examples needed

43
 44

Probably Approximately Correct (PAC) Learning

Solve the following example:

● Suppose we have a hypothesis space with one thousand possible
models.
● We want the model to make predictions with an error of at most
ten percent.
● We also want to be ninety-five percent confident that the model
will perform well on new data.
● How many training examples are needed to achieve this?

44
 45

Probably Approximately Correct (PAC) Learning

Solve the following example:

● (|H| = 1000)
● (ε = 0.1)
● (δ = 0.05)

ln(1000)≈6.91
ln(1/0.05)=ln(20)≈2.99
m≥10×(6.91+2.99)=10×9.90=99

You need at least 99 training examples to ensure the model is

probably (95%) approximately correct (error ≤ 10%).
45
 46

Bayes Theorem

Bayes' Theorem is a mathematical formula that describes the

probability of an event based on prior knowledge of conditions
related to the event. It essentially allows you to update the
probability of a hypothesis as you receive new evidence.

Term Meaning

Prior Probability What you believed before seeing the new data

Likelihood How likely the evidence is if the cause is true

Posterior Probability Updated belief after seeing the evidence

Evidence Overall chance of seeing the evidence, under all causes

46
 47

Bayes Theorem

Where,
● P(A) and P(B) are the probabilities of events A and B; also, P(B) is
never equal to zero.
● P(A|B) is the probability of event A when event B happens,
(Posterior probability)
● P(B|A) is the probability of event B when A happens.
The probability of an event A occurring given that event B has
occurred is equal to the product of the likelihood of B given A and
the prior probability of A, divided by the probability of B occurring.” 47
 06
MDL Principle

48 Dr. Shagun Sharma VIT Bhopal University, Sehore

 49

MDL Principle

The Minimum Description Length (MDL) principle is a formal method

from information theory that helps in model selection.
● Choose the model that explains the data with the least amount
of information.
● In machine learning, we often face overfitting (too complex
model) and underfitting (too simple model). MDL gives a
principled way to choose the model that balances complexity
and accuracy.
MDL = Model Description + Data Description

49
 50

MDL Principle

● A very simple model just predicts the average price → easy to

describe, but inaccurate → high error.

● A very complex model memorizes every price → accurate, but

long to describe → model is too big.

● MDL prefers a model that gives a good balance — not too simple,
not too complex.

50
 51

MDL Principle is used in the following

● Decision Trees

● Model Selection (e.g., comparing SVM vs. Logistic Regression)

● Compression algorithms

● Deep learning (implicitly via regularization)

51
Thank You!

Date: 02.07.2025

52