Inductive Learning

Inductive Learning 1 / 28
Session Outcomes

Inductive Learning
Hypothesis Space
Dataset Spilt
Cross validation

Inductive Learning 2 / 28
Inductive Learning

Machine learning is given a set of training examples:

(x̂, y )

x̂ represents the input feature vector.

y represents the target or output attribute.
The feature vector consists of multiple features:

x̂ = (x1 , x2 , . . . , xn )

The goal is to learn a function: f (x̂) such that

y = f (x̂)

Inductive Learning 3 / 28
Machine Learning Formulation

Learning Objective
Learn a function
f :X →Y
Such that
y = f (x)
The learned function should correctly predict the output for unseen
inputs.

Inductive Learning 4 / 28
Types of Learning Problems
Classification

f (x) ∈ {c1 , c2 , . . . , ck }
Output is discrete.
Predicts one among a finite set of classes.

Regression

f (x) ∈ R
Output is continuous.
Predicts a numerical value.

Probability Estimation

f (x) = P(y | x)
Estimates the probability of an outcome.
Inductive Learning 5 / 28
Inductive Learning
Given training examples

D = {(x1 , y1 ), (x2 , y2 ), . . . , (xm , ym )}

Learn a function

f ∈H
where H is the hypothesis space.
The learning algorithm searches for a function that best explains the
observed data.
This process of deriving a general rule from specific examples is called
Induction.

D → Learning Algorithm → f (x)

Hence, classification, regression, and probability estimation are collectively
known as inductive learning problems
Inductive Learning 6 / 28
Hypothesis

In machine learning, the true relationship between input and output is

represented by an unknown function:

y = f (x)

Machine learning attempts to learn an approximation of this function.

The learned function is called a Hypothesis and is denoted by:

h(x)

Thus,
h(x) ≈ f (x)

Inductive Learning 7 / 28
Hypothesis Space

A learning algorithm does not consider only one hypothesis.

It searches through a collection of possible hypotheses.
The set of all candidate hypotheses is called the Hypothesis Space.
It is denoted by:
H = {h1 , h2 , h3 , . . .}
The learning algorithm searches the hypothesis space and selects the
best hypothesis.
Therefore,
h∈H

Training Data → Learning Algorithm → h

Inductive Learning 8 / 28
Classification Problem and Hypothesis Space

+ +
++ +
+
+ h1
h2
− h
−
−
− − −
−

Each line represents a possible hypothesis.

All possible hypotheses form the hypothesis space H.
The learning algorithm selects the best hypothesis:

h∈H

Inductive Learning 9 / 28
Testing Machine Learning Algorithms

The goal of machine learning is to make accurate predictions.

Performance cannot be judged only using the training data.
A model should perform well on unseen data.
Therefore, machine learning models must be evaluated using separate
datasets.

Training Data → Learn Model → Test on New Data

Inductive Learning 10 / 28
Overfitting

A model should learn the underlying pattern in the data.

If training continues excessively, the model may memorize the training
examples.
This phenomenon is called Overfitting.
An overfitted model performs well on training data but poorly on
unseen data.

Desired Behaviour

Learn Pattern ̸= Memorize Data

Inductive Learning 11 / 28
Training, Validation and Test Sets

(
Training Set
Dataset →
Test Set

Training Set
Train the model.
Learn patterns from data.
Test Set
Evaluate the final model.
Measure performance on unseen data.
Training and test sets should not overlap.

Training Set ∩ Test Set = ∅

This ensures an unbiased estimate of model performance on unseen
data.

Inductive Learning 12 / 28
Training and Validation Split

(
Train
Training Set →
Validation

Train
Learn model parameters.
Validation
Hyperparameter tuning.
Model selection.
Train and Validation sets should be independent:

Train ∩ Validation = ∅

The sets should not share examples

Inductive Learning 13 / 28
Training and Validation split

Figure: 50:25:25 (large Data) 60:20:20 (Average Data)

Inductive Learning 14 / 28
Hypothesis Space and Model Selection
Training Data
Data x y
Training 1 2
Training 2 4
Validation 3 6
Testing 4 8

The learning algorithm searches for a function that explains the data.

H = {h1 , h2 , h3 , . . .}
where
h1 : Degree 1 polynomial
h2 : Degree 2 polynomial
h3 : Degree 3 polynomial
The set of all candidate models is called the Hypothesis Space.
Inductive Learning 15 / 28
Hypothesis Space and Model Selection
The set of all candidate models considered by a learning algorithm is called
the Hypothesis Space.

H = {y = ax + b, y = ax 2 + bx + c, y = ax 3 + bx 2 + cx + d, . . .}
Each candidate model is called a Hypothesis. Training Data Validation
Example:
x = 3, y =6

Hypothesis Space

H = {h1 , h2 , h3 }
Hypothesis Model
h1 y = 2x
h2 y = x2 − x + 2
h3 y = x 3 − 2x 2 + 3x
Inductive Learning 16 / 28
Validation Error for Different Hypotheses

Validation Point: (x, y ) = (3, 6)

Hypothesis Prediction (ŷ ) Error Formula Error
h1 6 (6 − 6)2 0
h2 8 (6 − 8)2 4
h3 18 (6 − 18)2 144

Observation
h1 produces the smallest validation error.
h2 and h3 are more complex models.
Increasing model complexity does not necessarily improve
performance.
The validation set helps us choose the best hypothesis.

Selected Hypothesis = h1 (x) = 2x

Inductive Learning 17 / 28
Testing the Selected Hypothesis
Selected model:

h1 (x) = 2x
Test point:

(x, y ) = (4, 8)
Prediction:

ŷ = h1 (4) = 2(4) = 8
Test Error:

(8 − 8)2 = 0

Test Error = 0

Inductive Learning 18 / 28
Discussion
A hypothesis is a candidate model that can explain the data.
The collection of all candidate models is called the Hypothesis
Space.

H = {h1 , h2 , h3 , . . .}
The learning algorithm searches the hypothesis space.
Each hypothesis is evaluated using the validation data.
The hypothesis with the lowest validation error is selected.
In this example,

h1 (x) = 2x
gives the smallest validation error and is therefore chosen as the final
hypothesis.
Since the test error is also zero, the chosen model generalizes well.

h1 ∈ H
Inductive Learning 19 / 28
Disadvantages of Validation Approach

Validation approach is sensitive to the specific split used.

Cross-validation reduces variance by testing across multiple splits.
It ensures all samples are used in validation at least once.

Inductive Learning 20 / 28
Cross Validation

Sometimes the available data is limited.

The dataset is divided into K equal parts.
One part is used for validation while the remaining parts are used for
training.
The process is repeated K times.

Inductive Learning 21 / 28
Types of Cross Validation

Cross Validation is used to obtain a reliable estimate of model

performance.

Common techniques are:

1 Leave-One-Out Cross Validation (LOOCV)
2 Leave-p-Out Cross Validation (LpOCV)
3 K-Fold Cross Validation
4 Stratified K-Fold Cross Validation

Inductive Learning 22 / 28
Leave-One-Out Cross Validation (LOOCV)

Suppose the dataset contains 500 records.

For each experiment:
One sample is used for validation.
Remaining n − 1 samples are used for training.
Experiment 1 :1 Validation + 499 Training
Experiment 2 : 1 Validation + 499 Training
..
.

Experiment 500:1 Validation + 499 Training Final Accuracy

ACC1 + ACC2 + · · · + ACC500

=
500
Validation data differs at each training

Inductive Learning 23 / 28
Advantages and Disadvantages of LOOCV

Advantages
Almost all data is used for training.
Every sample is used for validation once.

Disadvantages
Only one record is used for validation.
Computational cost is very high.
Model must be trained n times.

Inductive Learning 24 / 28
Leave-p-Out Cross Validation

Instead of leaving one sample out, we leave p samples out.

Examples:

p = 10, p = 20, p = 30

Procedure:
Select p samples for validation.
Use remaining samples for training.
Repeat for different combinations.

Final performance is obtained by averaging all validation results.

Inductive Learning 25 / 28
K-Fold Cross Validation

Assume

n = 500, k=5

Validation size:
500
= 100
5

The dataset is divided into 5 equal folds.

Fold 1 used for validation
Remaining folds used for training
Repeat until every fold becomes validation once

Inductive Learning 26 / 28
K-Fold Cross Validation Example
Experiment Validation Fold
1 Fold 1
2 Fold 2
3 Fold 3
4 Fold 4
5 Fold 5

Final Accuracy

ACC1 + ACC2 + ACC3 + ACC4 + ACC5

Accuracy =
5
For classification problems:
Class distribution may not be preserved.
One fold may contain more samples from one class.
Another fold may contain fewer samples from that class.
This may lead to unreliable validation results.
Inductive Learning 27 / 28
Stratified K-Fold Cross Validation

Stratified K-Fold preserves the class distribution in every fold. Example:

n=500, k=5
Each fold contains samples of:
500
= 100
5
If the original dataset contains 60% Class A and 40% Class B then every
fold approximately contains 60% Class A and 40% Class B

Inductive Learning 28 / 28