People's Democratic Republic of Algeria

Ministry of higher education and scientific research

Ecole supérieure en sciences et technologies de l’informatique et du numérique

Machine Learning

01/02/2024 Dr. Daoudi Meroua 1

Outline
• What is machine learning?
• Why machine learning?
• Machine learning as process
• Data and algorithms in ML
• Machine learning applications

01/02/2024 Dr. Daoudi Meroua 2

Machine Learning: ML

01/02/2024 Dr. Daoudi Meroua 3

Machine Learning: ML
• The name ‘Machine Learning was coined in 1959 by Arthur Samuel
Thom who provides the definition:

’ Machine Learning enables a machine to

automatically learn from data, improve performance
from experiences, and predict things without being
explicitly programmed’

01/02/2024 Dr. Daoudi Meroua 4

Machine Learning ML
Traditional Programming

Machine Learning

01/02/2024 Dr. Daoudi Meroua 5

Machine Learning: ML

Definition by Tom Mitchell (1998) :

Machine learning is the study of algorithms that :
➢ improve their performance P
➢ At some task T
➢ With experience E
A well defined learning task is given by <P,T,E>

01/02/2024 Dr. Daoudi Meroua 6

Machine Learning: ML
Example : Spam filtering
➢T : identifying spam emails
➢ p : % of spam emails that have been filtered
% spams emails / Non spams emails that have been incorrectly
filtered
➢ E: A database of labeled emails

01/02/2024 Dr. Daoudi Meroua 7

Why Machine Learning?
Machine learning can be used to solve problems:
➢ That we don’t know how to solve (purchase prediction)
➢ That we know how to solve, but cannot formalize in terms of
algorithms (image recognition)
➢ That we know how to solve but with procedures that are too
resource-intensive (prediction of interactions between large
molecules)

01/02/2024 Dr. Daoudi Meroua 8

Machine Learning as Process
Data
collection

Data
Deployment
preparation

Model
Test model
building

Train model

01/02/2024 Dr. Daoudi Meroua 9

ML as process: Data collection
• Identify and obtain all data related problems.

Identify various Data

Collect Data
data sources integration

• A coherent set of data is called as a dataset

01/02/2024 Dr. Daoudi Meroua 10

ML as process: Data pre-processing
Data preprocessing is a process of preparing the raw data and making it
suitable for a machine learning model
There are 4 major tasks in data preprocessing:
• Data cleaning
• Data integration
• Data reduction
• Data transformation

01/02/2024 Dr. Daoudi Meroua 11

ML as process: Data pre-processing
Data cleaning:
Data cleaning is the process of removing incorrect data, incomplete
data, and inaccurate data from the datasets.

Handling missing values:

• Standard value: ‘NAN’ or ‘Not Available’
• Can be replaced by ‘mean value’ /’median value’
• Using regression or decision tree

01/02/2024 Dr. Daoudi Meroua 12

ML as process: Data pre-processing
Handling noisy data:
Binning: can be used for smoothing the data

• Smoothing by equal frequency bins

• Smoothing by bin means
• Smoothing by bin boundary

Example: 8,16,9,15,21,21,24,30,26,27,30,34
Step 1: sort the data
8,9,15,16,21,21,24,26,27,30,30,34
01/02/2024 Dr. Daoudi Meroua 13
ML as process: Data pre-processing
Handling noisy data:
Smoothing data by equal frequency bins
Bin 1: 8,9,15,16
Bin 2: 21,21,24,26
Bin 3: 27, 30,30,34

01/02/2024 Dr. Daoudi Meroua 14

ML as process: Data pre-processing
Means of bin 1 = ((8+9+15+16)/4)= 12
Bin 1: 12, 12, 12,12
Means of bin2=((21+12+24+26)/4)=23
Bin 2: 23,23,23,23
Means of bin 3= ((27+30+30+34)/4)=30
Bin 3: 30,30,30,30

01/02/2024 Dr. Daoudi Meroua 15

ML as process: Data pre-processing
Handling noisy data:
Smoothing data by bin boundaries :
Bin1: 8,8,16,16
Bin 2: 21,21,26,26
Bin 3: 27,27,27,34
• Regression : Helps to decide the variable which is suitable for our
analysis
• Clustering: groups Data and find outliers

01/02/2024 Dr. Daoudi Meroua 16

ML as process: Data pre-processing
Data integration:
There are some problems to be considered during data integration:
• Shema integration
• integrate metadata from different sources
• Entity identification problem: identify real world entities from
multiple data sources, e.g., [Link]-id  [Link]-#
• Detecting and resolving data value conflicts
• for the same real world entity, attribute values from different sources are
different, e.g., different scales, metric vs. British units
• Removing duplicates and redundant data
01/02/2024 Dr. Daoudi Meroua 17
ML as process: Data pre-processing
Data reduction: This process helps in the reduction of the volume of
the data.
• Dimensionality reduction
• Numerosity reduction
• Data compression

01/02/2024 Dr. Daoudi Meroua 18

 ML as process: Data pre-processing
Data Transformation
A function that maps the entire set of values of a given attribute
to a new set of replacement values each old value can be
identified with one of the new values
Methods
Smoothing: Remove noise from data
Attribute/feature construction :New attributes constructed from
the given ones
01/02/2024 Dr. Daoudi Meroua 19
ML as process: Data pre-processing
Data Transformation
Aggregation: Summarization, data cube construction
Normalization: Scaled to fall within a smaller, specified range
Discretization: Concept hierarchy climbing

01/02/2024 Dr. Daoudi Meroua 20

ML as process: Model building
This step consists of selecting the right model. There are many models
which can be used for many different purposes. Once the model is
selected, it needs to meet the business goal.
Examples:
• Decision Trees
• Random Forest
• Linear Regression
• Support Vector Machines (SVM)

01/02/2024 Dr. Daoudi Meroua 21

ML as process: Train Model
• Training a model forms the basis of machine learning. The goal is to
use our training data and improve the predictions of our model.
• Every cycle in training a model involves updating
the weights and biases in each training step
• Every cycle in training a model involves updating the weights ans
biases in each training step
• The goal of training is to evaluate and further improve our model
accuracy and performance.
• Training happens in the form of iterations which is called a training
step.

01/02/2024 Dr. Daoudi Meroua 22

ML as process: Test Model
▪ Study models accuracy

• Work better than the naïve approach or previous system

• Do the results make sense in the context of the problem

▪ Performance metrics are used to measure the performance of the

model. These include precision, recall, accuracy, specificity, etc.

01/02/2024 Dr. Daoudi Meroua 23

ML as process: Deployment
• The last step of machine learning life cycle is deployment, where we
deploy the model in the real-world system.
• If the model is producing an accurate result as per our requirement
with acceptable speed, then we deploy the model in the real system

01/02/2024 Dr. Daoudi Meroua 24

Data in machine learning
• Data is crucial component in the field of machine learning
• It refers to the set of observations or measurements that can
be used to train a machine-learning model
• Data can be in various forms such as numerical, categorical, or
time-series data, and can come from various sources
• Machine learning algorithms use data to learn patterns and
relationships between input variables and target outputs,

01/02/2024 Dr. Daoudi Meroua 25

Data in machine learning
Data is typically divided into two types:
• Labeled data
• Unlabeled data
Labeled data includes a label or target variable that the model is
trying to predict, whereas unlabeled data does not include a
label or target variable

01/02/2024 Dr. Daoudi Meroua 26

Data in machine learning
Labels
Features

attribut 1 attribut 2 attribut 3 classe

X1 0

X2 1
Samples
…………… 1

XN 0

01/02/2024 Dr. Daoudi Meroua 27

Data in machine learning
How do we split data in machine learning ?

Data in Machine
Learning

Training Data Validation Data Testing Data

01/02/2024 Dr. Daoudi Meroua 28

Data in machine learning
• Training Data: The part of data we use to train our model. This
is the data that your model actually sees(both input and
output) and learns from.
• Validation Data: This part of data is used to evaluate of the
model, and tuning the hyperparameters This data plays its
part when the model is actually training.
• Testing Data: Once our model is completely trained, testing
data provides an unbiased evaluation. When we feed in the
inputs of Testing data, our model will predict some
values(without seeing actual output).

01/02/2024 Dr. Daoudi Meroua 29

Data in machine learning
• Different Forms of Data
• Numeric Data : If a feature represents a characteristic measured in
numbers , it is called a numeric feature.
• Categorical Data : A categorical feature is an attribute that can take
on one of the limited , and usually fixed number of possible values
on the basis of some qualitative property . A categorical feature is
also called a nominal feature.
• Ordinal Data : This denotes a nominal variable with categories
falling in an ordered list . Examples include clothing sizes such as
small, medium , and large , or a measurement of customer
satisfaction on a scale from “not at all happy” to “very happy”.

01/02/2024 Dr. Daoudi Meroua 30

Types of machine learning problems
Supervised Learning:
Supervised machine learning is based on supervision, it means we train the
model using ‘labelled dataset’, and based on the training, the machine
predict the output.
Classification:
Classification algorithms are used to solve the classification problems in
which the output variable is categorical (SVM, RF, Decision Tree)
Regression:
Regression algorithms are used to solve regression problems in which there
is a relationship between input and output variables. (linear Regression,
polynomial regression, …)

01/02/2024 Dr. Daoudi Meroua 31

Types of machine learning problems
Unsupervised Learning:
in unsupervised machine learning, the model is trained using the
unlabeled dataset, and the machine predicts the output without any
supervision.
The main aim of the unsupervised learning algorithm is to group or
categories the unsorted dataset according to the similarities, patterns,
and differences

01/02/2024 Dr. Daoudi Meroua 32

Types of machine learning problems
Semi supervised Learning:
Semi-Supervised learning is a type of Machine Learning algorithm that
lies between Supervised and Unsupervised machine learning. It
represents the intermediate ground between Supervised (With
Labelled training data) and Unsupervised learning (with no labelled
training data) algorithms and uses the combination of labelled and
unlabeled datasets during the training period.

01/02/2024 Dr. Daoudi Meroua 33

Types of machine learning problems
Reinforcement learning:
Reinforcement Learning (RL) is a type of machine learning paradigm
where an agent learns to make decisions by interacting with an
environment. Unlike supervised learning, where the model is trained
on labeled data, reinforcement learning involves an agent that takes
actions in an environment to maximize some notion of cumulative
reward.

01/02/2024 Dr. Daoudi Meroua 34

Machine learning techniques

Apprentissage
automatique

Apprentissage non Apprentissage Apprentissage Apprentissage par

supervisé supervisé semi supervisé renforcement

Variables Données
Donnés non étiquetées +
continues Variables discrètes positif negatif
étiquetés données non
étiquetées

Classification+
Régression classification Clustering Association
clustering

01/02/2024 Dr. Daoudi Meroua 35

Machine Learning Applications
• Image recognition
• Speech recognition
• Traffic prediction
• Product recommendations
• Self-driving cars
• Spam filtering
• Medical diagnosis
• Automatic Language Translation…etc

01/02/2024 Dr. Daoudi Meroua 36

Machine Learning Applications
Image recognition:
• Image recognition is one of the most common applications of
machine learning. It is used to identify objects, persons, places, digital
images, etc.

Example : Face ID authentication by Apple

01/02/2024 Dr. Daoudi Meroua 37

Machine Learning Applications
Speech recognition:
• Speech recognition is a process of converting voice instructions into
text, and it is also known as "Speech to text", or "Computer speech
recognition."
Examples: Google assistant and Alexa
Traffic prediction
• If we want to visit a new place, we take help of Google Maps, which
shows us the correct path with the shortest route and predicts the
traffic conditions.

01/02/2024 Dr. Daoudi Meroua 38

Machine Learning Applications
Product recommandations:
• Machine learning is widely used by various e-commerce and
entertainment companies such as Amazon, Netflix, etc., for product
recommendation to the user.
Self-driving cars:
• One of the most exciting applications of machine learning is self-
driving cars. Machine learning plays a significant role in self-driving
cars. Tesla, the most popular car manufacturing company is working
on self-driving car. It is using unsupervised learning method to train
the car models to detect people and objects while driving.
01/02/2024 Dr. Daoudi Meroua 39
Machine Learning Applications
Email spam filtering

• Whenever we receive a new email, it is filtered automatically as

important, normal, and spam. We always receive an important mail in
our inbox with the important symbol and spam emails in our spam
box, and the technology behind this is Machine learning.

01/02/2024 Dr. Daoudi Meroua 40

Machine Learning Applications
Medical Diagnosis:
• In medical science, machine learning is used for diseases diagnoses.
With this, medical technology is growing very fast and able to build
3D models that can predict the exact position of lesions in the brain.
• It helps in finding brain tumors and other brain-related diseases
easily.

01/02/2024 Dr. Daoudi Meroua 41

Machine Learning Applications
Automatic Language Translation:
• machine learning helps us by converting the text into our known
languages. Google's GNMT (Google Neural Machine Translation)
provide this feature, which is a Neural Machine Learning that
translates the text into our familiar language, and it called as
automatic translation.

01/02/2024 Dr. Daoudi Meroua 42

 People's Democratic Republic of Algeria
Ministry of higher education and scientific research

Ecole supérieure en sciences et technologies de l’informatique et du numérique

Supervised Learning

01/02/2024 Dr. Daoudi Meroua 1

Supervised Learning: Formulation
Supervised learning involves training a model using Labelled Data.
Formulation:
A supervised learning problem can be formalized as follows: Given M
observations {x1,x2…Xm} and their labels {y1,y2…ym} .
Such that:
x X : Observation space
y Y: Label space
The goal of machine learning is to find a function f: x → y, where x
belongs to the observation space X and y belongs to the label space Y.
01/02/2024 Dr. Daoudi Meroua 2
Supervised Learning Problems
We can mainly distinguish between two types of problems:

• Regression:
If y is continuous, y ∈ ℝ Example: prediction of rent based on the area,
location, etc.
• Classification:
In this case, the variable to predict is discrete.

01/02/2024 Dr. Daoudi Meroua 3

Supervised Learning Problems
We can distinguish two types of classification:

• Binary Classification: y ∈ {0,1} or {-1,1} Example: Predicting whether a

tumor is malignant or benign.

• Multi-class Classification: y ∈ {1,2, … ,C} Example: Predicting the class

of an image among 'dog,' 'cow,' and 'cat.'

01/02/2024 Dr. Daoudi Meroua 4

Decision function
In a classification problem, the function f can predict values in {0,1}, or
alternatively, an intermediate function g with real-valued outputs can
be used to decide the class of a variable based on a score.

g: x→R f(x)=0 si g(x)<0

f(x)=1 si g(x)>0
In the case of multi-class classification, there are c decision functions.

01/02/2024 Dr. Daoudi Meroua 5

Binary classification for multi-class
classification
Any binary classification algorithm can solve a multi-class classification
problem
One-vs-All (OvA) :
• This involves training N binary classifiers.
• Each classifier C uses all examples from class C as positive examples
and all other examples as negative examples.
• The label for x is determined by the decision function that returns the
highest score.
𝑓 𝑥 = 𝑚𝑎𝑥𝑐=1..𝐶 𝑔𝑐 (x)

01/02/2024 Dr. Daoudi Meroua 6

Binary classification for multi-class
classification

•Classifier 1:- [Green] vs [Red, Blue]

•Classifier 2:- [Blue] vs [Green, Red]
•Classifier 3:- [Red] vs [Blue, Green]

01/02/2024 Dr. Daoudi Meroua 7

Binary classification for multi-class
classification
•
One-vs-One (OvO):
• Involves creating c(c-1)/2 classifiers, with each classifier separating
one class from another.
• To predict a new input, the decision functions are calculated, where
𝑔𝑐𝑘 separates class c from class k. The label for x is determined as:
𝑓 𝑥 = 𝑚𝑎𝑥1..𝑐 (෍ 𝑔𝑐𝑘 x )
𝑘≠𝑐

01/02/2024 Dr. Daoudi Meroua 8

Binary classification for multi-class
classification

•Classifier 1: Green vs. Blue

•Classifier 2: Green vs. Red
•Classifier 3: Blue vs. Red
01/02/2024 Dr. Daoudi Meroua 9
Cost function
• The cost function allows evaluating the performance of the created
model.
• In regression, the function can be considered as the sum of errors
between the model's prediction f(xi​) and and the associated values yi
(RMSE, MAE, etc.).

01/02/2024 Dr. Daoudi Meroua 10

Cost function
• In classification, the cost function can be calculated by measuring the
number of examples that our model has misclassified.

• Le cout = 2/10
• Il existe plusieurs fonction de couts tels que: accuracy, F1 score, La
précision….
01/02/2024 Dr. Daoudi Meroua 11
Performances Metrics: Classification
Confusion Matrix and Derived Rates: We describe the number of
errors as a fraction of the number of examples (1%, 2%, ...).
The confusion matrix is a square matrix where each entry is the
number of examples for which label k has been predicted

01/02/2024 Dr. Daoudi Meroua 12

Performances Metrics: Classification
• True Positive: We predicted positive and it’s true.
• True Negative: We predicted negative and it’s true,
• False Positive (Type 1 Error): We predicted positive and it’s false,
• False Negative (Type 2 Error): We predicted negative and it’s false.

01/02/2024 Dr. Daoudi Meroua 13

Performances Metrics : Classification
It is possible to derive several performance metrics from the confusion
matrix:
Accuracy: Measures the total number of correct predictions divided by
the total number of samples.

Recall: Calculates the proportion of true positives among all truly

positive examples.
𝑻𝒑
𝑹𝒆𝒄𝒂𝒍𝒍 =
𝑻𝑷 + 𝑭𝑵

01/02/2024 Dr. Daoudi Meroua 14

Performances Metrics : Classification
Precision:
Indicates the proportion of true positives among examples predicted as
positive.
𝑻𝒑
𝒑𝒓𝒆𝒄𝒊𝒔𝒊𝒐𝒏 =
𝑻𝑷 + 𝑭𝑷

F1 Score:
A measure of precision and recall that combines both into a single value.

𝟐𝑻𝑷
𝑭=
𝟐𝑻𝑷+𝑭𝑷+𝑭𝑵

01/02/2024 Dr. Daoudi Meroua 15

Performances Metrics : Classification

AUC-ROC (Area Under the Receiver Operating Characteristic):

• The Receiver Operator Characteristic (ROC) is a probability curve that
plots the TPR(True Positive Rate) against the FPR(False Positive Rate)
at various threshold values
• The Area Under the Curve (AUC) is the measure of the ability of a
classifier to distinguish between classes. From the graph, we simply
say the area of the curve ABDE and the X and Y-axis.

01/02/2024 Dr. Daoudi Meroua 16

Performances Metrics : Classification

01/02/2024 Dr. Daoudi Meroua 17

Performances Metrics : Regression

RMSE, or Root Mean Squared Error, is a commonly used metric for

evaluating the performance of regression models. It provides a
measure of how well the predicted values align with the actual values
in a regression problem. The formula for RMSE is as follows:

𝑛
1
𝑅𝑀𝑆𝐸 = ෍(𝑦𝑖 − f(𝑥𝑖 ))2
𝑛
𝑖=1

01/02/2024 Dr. Daoudi Meroua 18

Performances Metrics : Regression
MAE calculates the absolute differences between the actual and
predicted values, averages these absolute differences, and provides a
straightforward measure of how well the model's predictions align with
the true values. Unlike RMSE, MAE is less sensitive to outliers because
it doesn't involve squaring the differences.
𝑛
1
𝑀𝐴𝐸 = ෍ห𝑦𝑖 −𝑓(𝑥𝑖 )ȁ
𝑛
𝑖=1

01/02/2024 Dr. Daoudi Meroua 19

The learning phase : Parameters optimization
Machine learning is the stage that seeks the model parameters that
minimize the cost function.
Several optimization methods can be used to minimize the cost
function.
The most popular method involves treating the cost function as a
convex function and searching for the minimum using the technique
called gradient descent

01/02/2024 Dr. Daoudi Meroua 20

The learning phase : Parameters optimization
Let f be a function with multiple variables p={a1​,a2​,…,an​} for which we
can compute the gradient grad(p).
Given:
• An initial point P0​.
• A tolerance level ε>0.
• Iteration: We compute a sequence of points P1​,P2​,… recursively as
follows: assuming we have already obtained the point Pk,
[Link] the gradient grad(Pk​).
[Link] αk, and compute: Pk+1​=Pk​−αk​grad(Pk​).
• Termination: Stop when grad(Pk​)≤ε.
01/02/2024 Dr. Daoudi Meroua 21
Generalization and overfitting
• Generalization:

• Definition: Generalization refers to the ability of a model to perform

well on new data that it has not seen during training.
• Objective: The primary goal of machine learning is to create models
that generalize well, making accurate predictions on previously
unseen data.

01/02/2024 Dr. Daoudi Meroua 22

Generalization and overfitting
Overfitting:
• Definition: Overfitting occurs when a model fits too closely to the
specific training data at the expense of its ability to generalize to new
data.
• Causes: Overfitting can happen when the model is too complex
relative to the amount of training data, leading to memorization
rather than an understanding of underlying patterns.
• Manifestation: An overfit model may exhibit excellent performance
on training data but could poorly generalize to new data as it
memorized specific features that do not generalize well.
01/02/2024 Dr. Daoudi Meroua 23
Generalization and overfitting
• Cross-validation: Use techniques like cross-validation to assess a
model's generalization performance.
• Regularization: Introduce regularization terms in the cost function to
prevent overfitting by discouraging excessive complexity.
• Larger Dataset: Having a larger dataset can help reduce the risk of
overfitting by providing a more diverse range of situations.
• The overall goal is to strike a balance, aiming for a model that fits well
to training data while maintaining robust generalization capabilities
for new data.

01/02/2024 Dr. Daoudi Meroua 24

Underfitting
Definition:
Underfitting occurs when a machine learning model is too simple to
capture the underlying patterns in the training data.
Causes:
It can happen when the model is not complex enough to represent the
relationships present in the data, or when the training process is
insufficient

01/02/2024 Dr. Daoudi Meroua 25

Underfitting
Signs of Underfitting:
• Training and validation errors are both high.
• The model struggles to make accurate predictions even on the
training data.
Addressing Underfitting:
• Increase the model complexity by using more complex algorithms or
adding features.
• Ensure an adequate amount of training data is available.
• Adjust hyperparameters to make the model more expressive.
01/02/2024 Dr. Daoudi Meroua 26
Model Selection and validation
• Minimizing the error on an observed dataset does not guarantee
minimizing the error over the entire data space.
• Therefore, strategies must be applied to evaluate a model while
avoiding overfitting.
• Thus, it is necessary to distinguish between the evaluation of a model
and its selection.

01/02/2024 Dr. Daoudi Meroua 27

Model Selection and validation
Model Selection:
Definition: Model selection involves choosing the type of model or
learning algorithm to use for solving a specific problem.
Process: This can involve evaluating multiple models based on criteria
such as complexity, performance on training data, and generalization
ability.
Selection Criteria: Factors like accuracy, generalization ability, training
time, and interpretability may influence model selection.

01/02/2024 Dr. Daoudi Meroua 28

Model Selection and validation
Validation:
Definition: Validation is the process of assessing a model's performance
on a separate dataset called the validation set, which has not been used in
the initial training.
Objective: The goal is to ensure that the model generalizes well to new
data and does not overfit the training data.
Validation Techniques: Common techniques include cross-validation,
holdout validation, and bootstrap validation.

01/02/2024 Dr. Daoudi Meroua 29

Model Selection and validation
Key Considerations:
Hyperparameter Tuning: Adjust hyperparameters to find the optimal
configuration for the chosen model.

Performance Metrics: Use appropriate metrics (accuracy, precision,

recall, etc.) to evaluate the model's performance during selection and
validation.

01/02/2024 Dr. Daoudi Meroua 30

Model Selection and validation
• Test Data/Training Data: To evaluate a model, we use data that was
not used to build it. Therefore, a portion of the dataset is reserved for
evaluating the model (test set). The portion of data used to build the
model is called the training set.

• Validation Data: Selecting a model from k models trained on the

training dataset will generate K decision functions f1, f2, ... fk.'

01/02/2024 Dr. Daoudi Meroua 31

Cross Validation
Cross-validation is a technique used for evaluating the performance of
machine learning models. It provides a robust way to estimate a
model's performance on new and unseen data, helping to assess its
generalization ability. Here's an overview of cross-validation:
Objective:
Estimate a model's performance on unknown data and evaluate its
generalization capability.
K-Fold Cross-Validation:
Commonly used version of cross-validation where the dataset is divided
into k folds, and the model is trained and tested k times.

01/02/2024 Dr. Daoudi Meroua 32

Cross Validation
K-Fold Cross-Validation
Commonly used version of cross-validation where the dataset is divided
into k folds, and the model is trained and tested k times.
Stratified K-Fold Cross-Validation:
Similar to K-Fold Cross-Validation, but it ensures that each fold
maintains the same distribution of the target variable as the original
dataset.
Particularly useful when dealing with imbalanced datasets.

01/02/2024 Dr. Daoudi Meroua 33

Cross Validation
Leave-One-Out Cross-Validation (LOOCV):
• Each data point is treated as a single-fold.
• The model is trained on all data points except one and validated on
the left-out data point.
• Repeated N times, where N is the number of data points.

01/02/2024 Dr. Daoudi Meroua 34

Cross Validation
Shuffle-Split Cross-Validation
involves randomly shuffling and splitting the dataset into training and
testing sets multiple times. It provides a flexible approach to cross-
validation, allowing for a customizable ratio of training to testing data
in each iteration.

01/02/2024 Dr. Daoudi Meroua 35

KFold Cross Validation

01/02/2024 Dr. Daoudi Meroua 36

KFold Cross Validation
Process:
Data Splitting: Divide the dataset into k subsets or folds.
Training and Testing: Iteratively use k-1 folds for training the model and
the remaining fold for testing. Repeat this process k times, each time
using a different fold as the test set.
Performance Evaluation: Calculate the model's performance metric
(such as accuracy, precision, or others) for each iteration.
Average Performance: Average the performance metrics obtained from
all iterations to get a final estimation of the model's performance.

01/02/2024 Dr. Daoudi Meroua 37

Conclusion
The main steps of supervised learning include:

• DATA
• Model
• Cost function
• Learning algorithms

Generalization and overfitting are major concerns of machine learning

01/02/2024 Dr. Daoudi Meroua 38

Conclusion
• To avoid overfitting, it is essential during the model selection step to
validate the different models tested on a dataset different from the
one used for training.
• To estimate generalization performance, it is necessary to evaluate
the model on data that is not used in either the training or model
selection steps.
• The choice of performance metrics for a model depends on the
specific application.

01/02/2024 Dr. Daoudi Meroua 39

 People's Democratic Republic of Algeria
Ministry of higher education and scientific research

Ecole supérieure en sciences et technologies de l’informatique et du numérique

Parametric Regression
01/02/2024 Dr. Daoudi Meroua 1
Parametric Regression
• A parametric regression model assumes that the analytical form of
the decision function is known
• In this chapter we focus on linear regression problems, that is, those
for which the decision function is a linear function of the descriptors:
o Simple linear regression
o Multiple Linear regression
o Polynomial regression
o Logistic regression

01/02/2024 Dr. Daoudi Meroua 2

Parametric model
• We refer to a parametric model when using a learning algorithm
whose goal is to find the optimal values for the parameters of a model
with a predefined analytical form based on descriptors.
Example:

A learning algorithm that learns the coefficients α, β, and

γ in the following decision function f:x↦αx1​+βx24​+γex3​
−x5​ is learning a parametric model. Regardless of the
number of observations, this model remains unchanged.

01/02/2024 Dr. Daoudi Meroua 3

Linear Regression
Formulation
We choose a decision function f in the form:

• f is the decision function,

• x represents the input or features,
• β0​is the intercept or bias term,
• βj​are the coefficients associated with the features x j​,
• p is the number of features.

01/02/2024 Dr. Daoudi Meroua 4

Linear regression
Simple linear regression
• This is the base model for all statistical machine learning
• x is a one feature data variable
• y is the value we are trying to predict
• The regression model is:

Examples:
Predict blood pressure based on age
01/02/2024 Dr. Daoudi Meroua 5
Linear regression: Least square
Multiple linear regression
• The regression model is:
• Y is the dependent variable.
• X1​,X2​,…,Xp​are the independent variables.
• β0​is the intercept.
• β1​,β2​,…,βp​ are the coefficients associated with the independent
variables.
• Example: predict the price of a used car. Inputs are the car attributes:
brand, year, engine capacity, mileage
01/02/2024 Dr. Daoudi Meroua 6
Linear regression
• The goal of linear regression is to find the values of the coefficients
that best fit the observed data. This is done by minimizing:

• Solve the problem of Linear regression:

 Least square method
 Gradient decent method

01/02/2024 Dr. Daoudi Meroua 7

Least square Method
• The least squares solution for the coefficients β∗ is given by the
expression:

• This formula provides the values for the coefficients that minimize the
sum of squared differences between the observed and predicted
values, assuming the matrix is invertible.

01/02/2024 Dr. Daoudi Meroua 8

Least square Method
• X: The matrix of independent variables (features), where each row
represents an observation and each column represents a different
feature.
• We add a column of 1's to X, it helps incorporate the intercept term
into the model.
• Y: The vector of observed values for the dependent variable.
• XT: The transpose of X
• (XTX)−1: The inverse of the transpose of X multiplied by X

01/02/2024 Dr. Daoudi Meroua 9

Least square Method:
• Applicative example:
Let's consider a simple linear regression problem where Y
is the variable to be explained, and X is the explanatory
variable. We have 7 observations, and the measurements
for these are given below:

01/02/2024 Dr. Daoudi Meroua 10

Least square Method:
• The inverse matrix is given as follows:

0.71428571 -0.14285714
-0.14285714 0.03571429

We propose to use a parametric method and to set up the following linear

model: ∀ i: yi = a0 + a1xi + εi
• Determine the ordinary least squares estimators
• Calculate the error
01/02/2024 Dr. Daoudi Meroua 11
 Gradient Descent Method:
The Gradient Descent Method is an optimization algorithm used to find the
minimum of a function. It is widely used in machine learning, particularly for
minimizing the loss or cost function, such as in linear regression or neural
networks.
The cost function (Mean Squared Error, MSE) is

For linear regression, the hypothesis (prediction function) can be written as:

Dr. Daoudi Meroua 12

Gradient Descent Method:

The gradient of each weight Bj​is calculated as :

The weights are updated using the gradient descent rule:

Where:

βj​is the current value of the j-th weight,

α is the learning rate, which controls the step size.
Dr. Daoudi Meroua 13
 Descent Gradient Method:
Given the mean square error as:

In the cas of simple linear regression :

• Calculate the gradient
• Give formulas to update parameters values

01/02/2024 Dr. Daoudi Meroua 14

Descent Gradient Method:
Solution:
The gradients:

Update B1 and B0:

01/02/2024 Dr. Daoudi Meroua 15

Polynomial Regression
Polynomial regression is a type of regression analysis in which the relationship
between the independent variable (X) and the dependent variable (Y) is
modeled as an n-th degree polynomial.

01/02/2024 Dr. Daoudi Meroua 16

Polynomial Regression
In the case of polynomial regression of degree d, we are now seeking a decision
function of the following form:

This is essentially a linear regression on p×d variables:

01/02/2024 Dr. Daoudi Meroua 17

Logistic Regression
• Logistic regression is a statistical method used for binary classification, where
the dependent variable is categorical and has two possible outcomes, usually
represented as 0 and 1. The logistic regression model is well-suited for
predicting the probability of an event occurring.
• The logistic regression model uses the logistic function (also known as the
sigmoid function) to model the relationship between the independent
variables and the probability of the dependent variable taking the value 1

01/02/2024 Dr. Daoudi Meroua 18

Logistic Regression : Probabilistic foundation

Before diving into logistic regression, it’s important to understand two key
concepts: probability and odds.

Probability: The likelihood or chance of an event occurring, ranging from 0 to 1.
For instance, if the probability of a disease is 0.8, this means there's an 80%
chance of the event "being sick" occurring.

Odds: The odds of an event are the ratio of the probability of the event
happening to the probability of it not happening. If p is the probability of an
event, the odds are given by:

Dr. Daoudi Meroua 19

Logistic Regression : Probabilistic foundation
Logistic regression aims to model the probability that an event belongs to a given
class. The probabilistic foundation is based on the idea that we assume the
probability of the event follows a logistic (sigmoid) function.

Logistic regression models the probability p of the positive class (i.e., Y=1) as a
function of input variables X, through a linear model that is then transformed by a
sigmoid function to produce a probability between 0 and 1.

The equation is:

Dr. Daoudi Meroua 20

Logistic Regression : Probabilistic foundation
Where:

p is the probability that Y=1 (the positive class).


X=(x1,x2,…,xn) are the input features.


θ0,θ1,…,θn are the model parameters (weights).


is the sigmoid (logistic) function, which transforms the output of a linear combination


into a probability between 0 and 1.

Dr. Daoudi Meroua 21

Logistic Regression : Probabilistic foundation
The logit is the transformation that allows you to move from the probability space
to a more flexible and linear space. It is the inverse of the sigmoid function. The
logit of a probability p is defined as the logarithm of the odds of the event:

In logistic regression, we assume that the logit is a linear combination of the input
features:

Dr. Daoudi Meroua 22

Logistic Regression : Probabilistic foundation
This allows us to rewrite the probability ppp as a function of this linear
combination:

Thus, the logit links the probability p to a linear model of the input features, and
the role of logistic regression is to find the parameters θ that minimize the error in
predicting the probabilities.
Dr. Daoudi Meroua 23
Logistic Regression : Probabilistic foundation
The goal of logistic regression is to maximize the likelihood of the observed data
under the model. The probabilistic model is based on the likelihood function.
The likelihood function for logistic regression is:

Where:
m is the number of training examples.
pi is the predicted probability for the i-th example.
yi is the true label of the iii-th example (0 or 1).

Dr. Daoudi Meroua 24

Logistic Regression
The log-likelihood function is the logarithmic form of the likelihood function,
which simplifies the computation of maximization:

The goal of logistic regression is to maximize the log-likelihood to obtain the

best parameters θ. This is equivalent to minimizing the cost function (which
is the negative of the log-likelihood)

Dr. Daoudi Meroua 25

Logistic Regression
The cost function in logistic regression is the cross-entropy (log loss), which
measures the difference between the predicted probabilities and the true labels.
This cost function is defined as:

Where hθ(x) is the predicted probability for the positive class.

Dr. Daoudi Meroua 26

Regularization
Regularization is a technique used to prevent overfitting in machine learning models.
Overfitting occurs when a model learns the noise in the training data rather than the
underlying patterns, resulting in poor performance on unseen data. Regularization
helps improve the model’s generalization ability by penalizing overly complex
models.

Overfitting: A model that performs well on training data but poorly on unseen (test)
data.

Regularization: A method to reduce model complexity and avoid overfitting by adding

a penalty term to the loss function.

Dr. Daoudi Meroua 27

Regularization : Why?
When training a machine learning model, we aim to strike a balance between:

Bias: The error due to overly simplistic models.

Variance: The error due to overly complex models that fit the training data too
closely.

Regularization helps to increase bias slightly but decreases variance, leading to a

model that generalizes better to unseen data.

Dr. Daoudi Meroua 28

Regularization techniques
L2 Regularization (Ridge Regression)

L2 regularization, also known as Ridge Regression when applied to linear models,

adds a penalty term to the loss function based on the sum of the squared values of
the model parameters. The modified loss function becomes:

Where:

Loss is the original loss function (e.g., Mean Squared Error).

λ is the regularization parameter and θi are the model parameters.

The term λ∑θi penalizes large weights, encouraging smaller weights, thus reducing
model complexity.
Dr. Daoudi Meroua 29
Regularization
L1 Regularization (Lasso Regression)

L1 regularization, also known as Lasso Regression, adds a penalty term to the loss
function based on the absolute values of the model parameters. The modified loss
function becomes:

Unlike L2 regularization, L1 regularization can lead to sparse models where some

coefficients are exactly zero. This can be useful for feature selection in high-dimensional
datasets.

Dr. Daoudi Meroua 30

Regularization
Elastic Net combines both L1 and L2 regularization. It adds a mix of both penalties,
which can be controlled by two hyperparameters: λ1 (for L1) and λ2 (for L2).

The modified loss function becomes:

Elastic Net is particularly useful when there are many correlated features in the
dataset.

Dr. Daoudi Meroua 31

 People's Democratic Republic of Algeria
Ministry of higher education and scientific research

Ecole supérieure en sciences et technologies de l’informatique et du numérique

Classification partie 1

01/02/2024 Dr. Daoudi Meroua 1

Classification
• Classification is a supervised learning method that involves
categorizing objects into classes based on quantitative and/or
qualitative features characterizing these objects
• The dataset with known classifications is used to learn the
classification rules

01/02/2024 Dr. Daoudi Meroua 2

Classification
Given a set of training data for examples i=1..n, where each example or
individual i is characterized by:
• A feature vector 𝑥 𝑖
• The value of its label such that 𝑌 𝑖 ∈{−1,1} (for binary classification)
• 𝑌 𝑖 ∈{1,2,….k}
The goal is :
• Predicting the value 𝑦 + for a new feature vector 𝑥 +
• To achieve this, the training data is used to construct a classifier �c in
such a way that: 𝑦 + = 𝑐(𝑥 + )
01/02/2024 Dr. Daoudi Meroua 3
Classification
Classification can be applied in:
• Medical diagnosis
• Image processing
• Agriculture
• Chemistry
• Geology
• Automatic document processing ...etc

01/02/2024 Dr. Daoudi Meroua 4

Classification
There are several classification algorithms, including:
• K-nearest neighbors
• Support Vector Machines (SVM)
• Decision tree
• Random Forests
• Naive Bayesian model

01/02/2024 Dr. Daoudi Meroua 5

K-nearest neighbors: KNN
• "K-Nearest Neighbor" (KNN) is one of the simplest supervised
machine learning methods
• It allows classifying a new example based on similarity.
• It is a non-parametric algorithm.
• Also known as a "lazy learner"

01/02/2024 Dr. Daoudi Meroua 6

K-nearest neighbors: KNN

K=3: The three nearest points to the new point are distributed as
follows: 2 points belong to class A and 1 point belongs to class B.
Therefore, the new point will be classified into class A.
01/02/2024 Dr. Daoudi Meroua 7
K-nearest neighbors: KNN
There are different methods to calculate the distance between the new
point and each training point:

Euclidean distance: the square root of the squared differences

between two points.
𝑘

𝑑𝑖𝑠𝑡 𝑥, 𝑦 = ෍(𝑥𝑖 − 𝑦𝑖 )2
𝑖=1

01/02/2024 Dr. Daoudi Meroua 8

K-nearest neighbors: KNN
• Manhattan distance: calculates the difference between two points by
using the sum of the absolute values of their differences.
𝑘

𝑑𝑖𝑠𝑡 𝑥, 𝑦 = ෍ห𝑥𝑖 − 𝑦𝑖 ȁ
𝑖=1
• Hamming distance: It allows comparing two binary bit strings and
represents the number of positions where the bits are different between
the two strings.
𝑘

𝐷𝐻 𝑥, 𝑦 = ෍ห𝑥𝑖 − 𝑦𝑖 ȁ
𝑖=1
If x= y : DH(x,y)=0
01/02/2024 Dr. Daoudi Meroua 9
K-nearest neighbors: KNN
The KNN algorithm is described as follows:
Step 1. Select the number k of neighbors.
Step 2. Calculate the distance between the new point and the other
points.
Step 3. Take the K nearest neighbors.
Step 4. Among the K neighbors, count the number of elements in each
class.
Step 5. Assign the new point to the class for which the number of
neighbors is maximal.

01/02/2024 Dr. Daoudi Meroua 10

K-nearest neighbors: choosing K?
Choosing the value of K in the KNN algorithm is an important decision
and can significantly impact the model's performance. Here are some
commonly used methods for selecting the optimal value of K:
[Link]:
Try multiple values of K and assess the model's performance on a
validation set. Choose the K value that provides the best performance.
[Link] Search:
Conduct a search over a predefined range of K values and evaluate the
model's performance for each value. Choose the K value that offers the
best performance.

01/02/2024 Dr. Daoudi Meroua 11

K-nearest neighbors: choosing K?
[Link] Root of n:
An empirical rule suggests choosing the square root of the total
number of observations as the value of K. This can work well in many
cases.
[Link] Method:
Plot an error curve against different K values. Identify the point where
the error ceases to decrease significantly, forming an elbow. This point
can be considered a good estimate of K.

01/02/2024 Dr. Daoudi Meroua 12

K-nearest neighbors: Applicative example

• Calculate the distance between example 5 and all the other examples
with k=3.

01/02/2024 Dr. Daoudi Meroua 13

K-nearest neighbors: Applicative example
• Solution:

01/02/2024 Dr. Daoudi Meroua 14

Weighted K-nearest neighbors:
This basic k-NN algorithm works quite well in many cases, but it treats
all neighbors equally.

01/02/2024 Dr. Daoudi Meroua 15

Weighted K-nearest neighbors:
Steps involved in weighted k-NN:
1. Calculate the distance between the new data point and all data points in
the training dataset, just like in basic k-NN.
2. Select the k-nearest data points like in k-NN.
3. Assign a weight to each of the k-nearest neighbors inversely proportional
to their distance from the query point. In simpler terms, closer neighbors get
higher weights, while farther neighbors get lower weights.
[Link] classification tasks, when determining the predicted class, the
contributions of neighbors are scaled by their weights. Closer neighbors have
a stronger influence on the prediction.

01/02/2024 Dr. Daoudi Meroua 16

Support Vector Machine: SVM
• Support Vector Machine (SVM), also known as separators with large
margins, is a supervised method proposed in 1992.
• SVM can be characterized as a supervised learning algorithm capable
of solving linear and non-linear binary classification problems.
• It is based on the construction of a hyperplane that separates positive
examples from negative examples.

01/02/2024 Dr. Daoudi Meroua 17

Support Vector Machine
• Multiple decision surfaces exist to separate the classes; which one to
choose?

01/02/2024 Dr. Daoudi Meroua 18

Support Vector Machine

To minimize sensitivity to noise, the decision boundary should be as far

away as possible from the data of each class.

01/02/2024 Dr. Daoudi Meroua 19

Support Vector Machine
• The margin is the minimum
distance between the hyperplane
and the support vectors
• L’hyperplan est construit à partir
des points vecteur de support
donnée par l’équation
𝑤 ∗ 𝑥𝑖 + 𝑏 = 0

01/02/2024 Dr. Daoudi Meroua 20

Support Vector Machine
With:

𝑤 ∗ 𝑥𝑖 + 𝑏 ≥ +1 𝑠𝑖 𝑦𝑖 = +1
𝑤 ∗ 𝑥𝑖 + 𝑏 ≤ +1 𝑠𝑖 𝑦𝑖 = −1

Les deux contraintes peuvent être

combinées comme suit:

𝑦𝑖 (𝑤 ∗ 𝑥𝑖 + 𝑏) ≥ +1

01/02/2024 Dr. Daoudi Meroua 21

Support Vector Machine
• The margin p can be calculated as the distance between H1 and H2.

1 − 𝑏 −1 − 𝑏 2
𝑝= − =
ȁ𝑤ȁ 𝑤 𝑤
ȁ𝑤ȁ
• Maximizing the margin p is equivalent to minimizing .
2
• The optimal hyperplane can be constructed by solving the primal
𝟏 𝒕
optimization problem: minimize 𝒘 ∗ 𝐰 subject to the constraint
𝟐
∀𝒊 𝒚𝒊 (𝒘 ∗ 𝒙𝒊 + 𝒃) ≥ +𝟏

01/02/2024 Dr. Daoudi Meroua 22

Support Vector Machine
The dual problem is :
𝒏 𝒏 𝒏
𝟏
𝒍 𝒘, 𝒃, ∝ = ෍ ∝𝒊 − ෍ ෍ ∝𝒊 ∝𝒋 𝒙𝒊 𝒙𝒋 𝒚𝒊 𝒚𝒋
𝟐
𝒊=𝟏 𝒊=𝟏 𝒋=𝟏
Resolving for αi​ provides the values for the vector w.
The class of a new object is obtained by the function:
𝒏

𝑓 𝑥 = 𝑠𝑖𝑔𝑛𝑒(෍ ∝𝒊 𝒙𝒊 𝒚𝒊 𝒙 + 𝒃)
𝒊=𝟏

01/02/2024 Dr. Daoudi Meroua 23

Support Vector Machine
• SVM can be used to classify non-linearly separable data by projecting
the data into a higher-dimensional space where linear separation
between classes can be achieved using a kernel function.
• The function f is given by: 𝑓 𝑥 =∝𝑖 𝐾 𝑥𝑖 , 𝑥 + 𝐶
• The αi are the weights to be optimized to maximize the separation of
class +1 and class -1 as much as possible
• The parameter C is optimized to adjust the training.

01/02/2024 Dr. Daoudi Meroua 24

Support Vector Machine
There are several kernel functions:
• Linear kernel: This is the simplest kernel, given by the inner product
⟨x,y⟩ plus an optional constant C. The linear kernel function is as
follows:
𝑘 𝑥, 𝑦 = (𝑥 𝑡 y + c)
Polynomial kernel: This is a non-linear kernel. Polynomial kernels are
well-suited for problems where all data is normalized. This type of
kernel has two parameters: the degree of the polynomial and the slope
alpha. The notation for the function is given by:

𝑘 𝑥, 𝑦 =∝ (𝑥 𝑡 y + c) 𝑑
01/02/2024 Dr. Daoudi Meroua 25
Support Vector Machine
• Gaussian kernel: It is an example of the radial basis function:

𝑘 𝑥, 𝑦 = 𝑒𝑥𝑝(−γȁ 𝑥 − 𝑦 ȁ2 )

• Sigmoid kernel: Also known as the hyperbolic tangent and multi-layer

perceptron (MLP) kernel. It originates from the field of neural
networks, where the bipolar sigmoid function is often used as the
activation function for artificial neurons.

𝑘 𝑥, 𝑦 = 𝑡𝑎𝑛ℎ(∝ 𝑥 𝑡 y + c)

01/02/2024 Dr. Daoudi Meroua 26

 People's Democratic Republic of Algeria
Ministry of higher education and scientific research

Ecole supérieure en sciences et technologies de l’informatique et du numérique

Classification part 2
01/02/2024 Dr. Daoudi Meroua 1
Decision Tree
• A prediction model presented in the form off a tree
• Each node of the tests a condition on a variable, and each children
corresponds to a label
• Originally, it applies to qualitative values
• Extended to take into consideration qualitative values

01/02/2024 Dr. Daoudi Meroua 2

Decision Tree: Space partitioning
• A decision tree partitions the observation space X in a recursive
manner until it reaches pure leaves (homogeneous regions) or a
stopping criterion
xi is quantitative
xi is qualitative

State X1<v

A B oui Non

01/02/2024 Dr. Daoudi Meroua 3

Decision Tree: Space partitioning
X0<=-12
10
10

10
4
X0<=9 6

10
2 X1<=9 4

2
10

01/02/2024 Dr. Daoudi Meroua 4

Decision Tree: Space partitioning

The decision tree contains two types of nodes :

Decision node: Contains a condition to split the data
Leaf node or pure node: Contains only one class of data; it is used to
determine the class of an object.

01/02/2024 Dr. Daoudi Meroua 5

Decision Tree: Classification
 Let x= (15,7)

 To classify X, we will traverse the tree until we reach a pure node.

X0<=-12

X0<=9

X1<=9

01/02/2024 Dr. Daoudi Meroua 6

 Decision Tree: Learning Process
10
X0<=4 10 X0<=-12
10
10

4 10
8 2
4 6
6

Which is the best split?

How does the model decide on the same split?

01/02/2024 Dr. Daoudi Meroua 7

Decision Tree: Learning Process

We need to know what the correct conditions are to build our model in
the form of a decision tree.
What features should be considered?
What value should be considered optimal?"
Where to Stop?

01/02/2024 Dr. Daoudi Meroua 8

Decision Tree: Metrics
Different algorithms use different metrics for mesuring the best
These generally mesure the homogeneity of the target variable within
the subsets
The model will consider the split that maximizes the information gain
What is information gain?

01/02/2024 Dr. Daoudi Meroua 9

Decision Tree: Information Gain
Information Gain (IG(X, Y)): It measures what information X provides
about Y. (ID3 algorithm)
For example, the root node contains 50% pink class and 50% blue class,
so falling into the correct class of an object is 50%, and it is the highest
uncertain impurity."

is the relative size of a child node respecting the parent

01/02/2024 Dr. Daoudi Meroua 10
Decision Tree: Information Gain
We use entropy to measure information in a state.
P_i is the probability of class i.
X0<=-12 10
10

4 10
6
Entropy of the root = -0.5 * log(0.5) - 0.5 * log(0.5) = 1.
Entropy of the right child = 0.57 * log(0.57) - 0.43 * log(0.43) = 0.99.
Entropy of a pure node = 0."
Decision Tree: Information Gain

X0<=-12 10
X0<=4 10 10
10

4 10
8 2 6
6 4

IG1= 1- 14/20 *0,99 – 6/20*0,91=0,034

IG2=1-4/20 * 0-16/20*0,95=0,25

IG2 > IG1; therefore, we will choose the second split.

Decision Tree: Gini impurity
• Used by the CART
• It measure incorrectly labeled of randomly chosen element. 
• Gini impurity can be computed by summing the probability of each
item being chosen times the probability of a mistake in categorizing
that item.
• It reaches its minimum (zero) when all cases in the node fall into a
single target category.
Applicative example

01/02/2024 Dr. Daoudi Meroua 14

Decision Tree: Pruning
• is a technique used in decision tree algorithms to reduce the size of
the tree by removing certain branches
• The goal is to prevent overfitting and improve the generalization of the
mode
• Pruning involves cutting off branches that do not provide significant
additional predictive power, thereby simplifying the tree.
Decision Tree: Pruning
Pruning can be performed in different ways, such as:
• pre-pruning: branches are removed during the tree construction
process
• post-pruning: the tree is initially grown to its full size and then
unnecessary branches are pruned.
Decision Tree: Pre-Pruning
Pre-pruning, also known as "early stopping". The growth of the tree is
halted based on certain criteria or conditions:

Maximum Depth Limit: Restricting the maximum depth of the tree. Once a
certain depth is reached, further splitting is stopped.

Minimum Samples for Split: Setting a threshold for the minimum number
of samples required to make a split. If a node has fewer samples than this
threshold, it is not split further.
Decision Tree: Pre-Pruning
Maximum Leaf Nodes: Limiting the total number of terminal nodes (leaves)
in the tree. Once this limit is reached, further splitting is prevented.

Minimum Impurity Decrease: Specifying a minimum improvement in

impurity (e.g., Gini impurity or information gain) that a split must achieve.
If a split doesn't meet this criterion, it is not performed.
Decision Tree: Post-Pruning

Build the complete model and then prune the elements contributing to
overfitting.

Either replace a node with a leaf or replace two nodes with one.

1. At each non leaf node in the tree, calculate expected error rate if that
sub tree is pruned
2. Calculate the expected error rate for that node if that tree is not pruned
3. if pruning node leads to greater expected error rate than keep the
subtree, otherwise prune it
Post-Pruning: Minimum error pruning

W (Tk,d) = MC(d,k)-MCT(d,k) / n(k)*(nt(d,k)-1)

MC(d,k): The number of individuals from the training set misclassified by
node d of tk when we assume it has been transformed into a leaf

MCT(d,k)=The number of individuals from the training set misclassified by

the leaves of tk located under node d

n(k) : The number of leaves in Tk

nt(d,k) : The number of leaves in the subtree of Tk located under node d

 Decision Tree: Post-Pruning
Node n1:
0: 10
x>a n1
1: 9
w(T, n1)= 9-0 / 5(5-1)= 0.45

n2 y>c y>b n3 Node n2:

0: 1
1:7
W (T,n2)= 1-0 / 5(3-1)= 0.10
n4 y>d 1 1 0
Node n3:
4 2 9 0: 9
1:2
1 0 W(T,n3)= 2-0 / 5(2-1) = 0.40

Node n4 :
3 1 0:1
1: 3
W (T,n4)= 1-0/5(2-1)= 0.20
Decision Tree: Post-Pruning
Node n1:
0: 10
x>a n1
1: 9
w(T, n1)= 9-0 / 5(5-1)= 0.45

y>b n2 Node n2:

1 0: 1
1:7
7/1 W (T,n2)= 2-0 / 3(2-1)= 0.66
1 0

2 9
Decision Tree: Post-Pruning
Node n1:
x>a n1 0: 9
1: 7

n2
1 0 9>7, So we assume that the erroneous values are
the 1

7/1 9/2 The final tree is :

10/9
Random Forest
Let's take the example of trees generated from the same dataset

X2<4,1 X0<4,3

0 X2<4,7 X1<6,1 1

1 0 0 1
Random Forest
• A very popular and powerful method
• It is less sensitive to training data
• Uses multiple decision trees
• Based on the principle of bagging
Random Forest

It is mainly based on two ideas: bootstrapping and aggregation:

Bootstrapping: allows the generation of random data from our original
dataset. The process is as follows:
• Select a random number of rows.
• Perform random sampling with replacement.
Random Forest:Boostrapping
Id x1 x2 x3 x4 x5 y Id Id Id Id
0 4,3 4,9 4,1 4,7 5,5 0 2 2 4 3
1 3,9 6,1 5,9 5,5 5,9 0 0 1 1 3
2 2,7 4,8 4,1 5 5,6 0 2 3 3 2
3 6,6 4,4 4,5 3,9 5,9 1 4 1 0 5
4 6,5 2,9 4,7 4,6 6,1 1 5 4 0 1
5 2,7 6,7 4,2 5,3 4,8 1 5 4 2 2
Random Forest:Boostrapping
Let's take an example of data with 5 dimensions.
After bootstrapping, we will create a decision tree for each generated data
point

X1<=4,9 X3<=4,6 X2<=4,1 X1<=4,4

X1<=6,1
X2<=4,7
0 1
X0<=4,3 1 1 0

1 0
0 1 0
Random Forest: Aggregation
How are we going to use this algorithm to classify objects?
Given a new data point:

2,8 6,2 4,3 5,3 5,5

We will pass the object through each tree:

• Arbre 1: 1
• Arbre 2: 0
• Arbre 3: 1
• Arbre 4: 1
Random Forest
• The process of combining results from multiple models is called
aggregation.
• Bootstrapping + aggregation = Bagging.
• It is a random forest since two random processes were used: data
generation and feature selection. The optimal number of selected
features: researchers have found that the log and sqrt of the total
number of features are a good choice.
Random Forest
Advantages:

• Can handle large volumes of data with high dimensionality.

• Generally avoids overfitting.
• Provides excellent results for classification.

Disadvantages:

• While it excels in classification, it may not perform as well in regression.

• There is not much control over the model; multiple tests are needed to
achieve good results.
Naïve bayes
• The statistical approach to classification formalizes the concept of class
through probabilistic models.
• The n observations x1, x2, ..., xn represent the random variable X.
• The labels y1, y2, ..., yn represent the random variable y.
• The probability that an observation belongs to a class is determined by:
• An inference problem: involves determining the probability
distributions.
• A prediction problem: involves using these distributions to
predict the class of an observation.
Naïve bayes:Inference and prediction
• Given a set of features x = (x1, x2, ..., xn). For prediction, we will
consider these variables (X and Y) as random.
• To find the label y, we need to evaluate this expression for all possible
values of y.
• The expression means, what is the probability that Y equals c given X
equals (x1, x2, ..., xn). Therefore, finding y aims to find the value of y
that maximizes this probability.
Bayes' theorem
• Probabilistic reasoning heavily relies on Bayes' theorem, which allows us
to express the conditional distribution

• p(y=c) : is the prior distribution of labels before observing the data.

• p(x|y=c) : It is the likelihood, quantifying how likely we observe the

realization of xi from X given y = c.
Bayes' theorem

p(y=c|x) : It is the posterior distribution of labels after observing the
data.

p(x) : is the marginal probability that x is observed

For comparing probabilities, we can ignore the denominator
Bayes' theorem: Example

y 0 1 1 1 0 0 1 0 0 0
x1 0 0 1 0 2 1 0 2 2 1
x2 0 1 2 0 2 1 2 0 1 0

Estimate y for x=(0,2)

P(y=0)= 6/16=0,6
P(y=1)=4/10=0,4

P(x=(0,2)|y=1)= 1/4 * p(y)= 1/10

P(x=(0,2)|y=0)= 0
Naif bayes classifier
The naive Bayes assumes that the variables xi are independent

• To calculate p(x|y):

Categorical variables:

Continuous variables:An attribute with a continuous value is generally

assumed to have a Gaussian distribution with a standard deviation σ
and a mean μ
Naif bayes classifier
y 0 1 1 1 0 0 1 0 0 0
x1 0 0 1 0 2 1 0 2 2 1
x2 0 1 2 0 2 1 2 0 1 0

Estimate y for (x,2) ?


P(x=(0,2)|y=1)= p(x1=0|y=1)* p(x=2|y=1)
=3/4 * 2/4
= 6/16

P(x=(0,2)|y=0)= p(x1=0|y=0)* p(x=2|y=0)
=1/6 * 1/6
= 2/36
Naif bayes classifier
Advantages:

Simple and quick to implement

Uses a small amount of data to estimate parameters

Produces good results in many cases

Disadvantages:

Assumes that variables are independent"
 People's Democratic Republic of Algeria
Ministry of higher education and scientific research

Ecole supérieure en sciences et technologies de l’informatique et du numérique

Clustering
01/02/2024 Dr. Daoudi Meroua 1
Clustering
Clustering is the process of grouping a set of objects into classes of similar
objects:

• Objects within a cluster should be similar.

• Objects from different clusters should be different.

• It is the most common form of unsupervised learning.

• Unsupervised learning allows learning from unlabeled data.

01/02/2024 Dr. Daoudi Meroua 2
Clustering

• Labeling is expensive

• Better understanding data structure

• Finding prototypes in the data

01/02/2024 Dr. Daoudi Meroua 3

Clustering: objective
Given a set of data points:

The objective of clustering is to:

• Maximize intra-class similarity
• Minimize inter-class similarity
Require the definition of similarity measures : Euclidean distance, Manhattan distance, Minkowski
distance

01/02/2024 Dr. Daoudi Meroua 4

Similarity measure: numerical attributes
Euclidean distance:

●
Works well with compact, spherical clusters.
●
Commonly used in K-Means clustering.
●
Sensitive to scale (so feature normalization is important).

01/02/2024 Dr. Daoudi Meroua 5

Similarity measure: numerical attributes
Manhattan distance:

●
Better when dealing with high-dimensional or sparse data.
●
More robust to outliers than Euclidean.
●
Often used in clustering methods like K-Medoids.

01/02/2024 Dr. Daoudi Meroua 6

Similarity measure: numerical attributes
Minkowski distance:

●
A flexible distance metric:
●
p=1 → Manhattan distance
●
p=2 → Euclidean distance
●
p→∞∞ → Chebyshev distance
●
Useful when you want to tune the distance metric based on data characteristics.

01/02/2024 Dr. Daoudi Meroua 7

Similarity measure: categorical attributes
Simple Matching Coefficient (SMC)

●
Value range: [0, 1] (1 = perfect match)
●
Best for: Nominal attributes (no natural order).

01/02/2024 Dr. Daoudi Meroua 8

Similarity measure: categorical attributes
Jaccard Similarity Coefficient

Where:
M11: both attributes = 1
M01, M10: mismatch cases
Use case: Binary attributes, especially when 1 is more meaningful than 0
(e.g., presence/absence).
01/02/2024 Dr. Daoudi Meroua 9
Similarity measure: categorical attributes
Hamming Distance : Counts the number of positions where the
corresponding categorical values differ.

• Use case: Categorical strings of equal length.

01/02/2024 Dr. Daoudi Meroua 10

Similarity measure: categorical attributes
Gower’s Similarity Coefficient Handles mixed data types (numeric +
categorical).
For categorical data:

Then averages across all features

01/02/2024 Dr. Daoudi Meroua 11
Similarity measure: categorical attributes
One-hot Encoding + Euclidean Distance
• Convert categorical attributes into binary vectors using one-hot
encoding.
• Then apply Euclidean or cosine similarity.
• Works well for algorithms that require numerical input (e.g., K-
Means), but increases dimensionality.

01/02/2024 Dr. Daoudi Meroua 12

Clustering techniques

Clustering techniques can be classified into:

• Partitioning clustering
• Hierarchical clustering
• Density-based clustering
• Grid-based clusterin

01/02/2024 Dr. Daoudi Meroua 13

Partitioning clustering

Partition-based clustering is a technique that divides a dataset DDD into

subsets called partitions or clusters. Each cluster must contain at least
one object, and each object must belong to exactly one cluster.
Formal Definition:
We aim to find a partition of the dataset D, denoted as τ(D) , such that:

01/02/2024 Dr. Daoudi Meroua 14

Partitioning clustering

1. No cluster is empty:

2. Clusters are pairwise disjoint (no overlap):

3. The union of all clusters equals the entire dataset:

01/02/2024 Dr. Daoudi Meroua 15

Partitioning clustering
There are two types of partitioning algorithms:
• Centroid-based algorithms
• Medoid-based algorithms
Centroid-based algorithms: The center of gravity of instances is used to
represent each cluster. The most popular algorithm in this category is
the K-means algorithm.
Kmeans :
●
An iterative algorithm used to partition data D into k clusters
●
Minimize the squared distance between points and the centroid
●
Make inter-cluster points as similar as possible
01/02/2024 Dr. Daoudi Meroua 16
K-means
• Specify number of clusters K.
• Initialize centroids by first shuffling the dataset and then randomly
selecting K data points for the centroids without replacement.
• Keep iterating until there is no change to the centroids. i.e assignment of
data points to clusters isn’t changing.
• Compute the sum of the squared distance between data points and all
centroids.
• Assign each data point to the closest cluster (centroid).
• Compute the centroids for the clusters by taking the average of the all data
points that belong to each cluster.
01/02/2024 Dr. Daoudi Meroua 17
K-means
The algorithm aims to minimize the following objective function:

Where:
●
d(xj,μi) is the chosen distance measure between the data point xj and the
cluster center (centroid) μi
●
Ci is the set of data points assigned to cluster iii,
●
μi is the centroid of cluster i,
●
Kis the total number of clusters.
01/02/2024 Dr. Daoudi Meroua 18
K-means

01/02/2024 Dr. Daoudi Meroua 19

K-means

01/02/2024 Dr. Daoudi Meroua 20

K-means

01/02/2024 Dr. Daoudi Meroua 21

K-means

Reassignment of the 3
points

01/02/2024 Dr. Daoudi Meroua 22

K-means

01/02/2024 Dr. Daoudi Meroua 23

K-means
• K-means works well when the data clouds are compact and well-
separated from each other.
• The method is scalable and quite efficient for large datasets with a
complexity of O(nkl), where k is the number of clusters, n is the
number of objects, and l is the number of iterations.
• However, it can only be applied when the mean of a cluster is defined;
if there are categorical (nominal or binary) data, this may not be
possible.
• The algorithm is sensitive to noise and outliers.

01/02/2024 Dr. Daoudi Meroua 24

K-means
The k-means algorithm heavily depends on the choice and initialization
of k.
There are methods to estimate the value of k:
• The elbow method
• Silhouette analysis

01/02/2024 Dr. Daoudi Meroua 25

K-means
Elbow Method:
• Apply the k-means algorithm with different values of k.
• For each k, calculate the mean of the sum of squared distances
between points and the centers.
• Plot the curve of the objective function against the number of k.
• The location of the elbow is considered an indicator of the
appropriate number of k.

01/02/2024 Dr. Daoudi Meroua 26

K-means
Average Silhouette Method
●
Allows to measure the quality of the cluster, i.e., determine how well
each object fits into its cluster.
●
For each data point iii, the silhouette coefficient s(i)s(i)s(i) is calculated
using:

• a(i) = average distance from point i to all other points in the same
cluster (measures cohesion).
• b(i) = minimum average distance from point i to all points in any other
cluster (measures separation).
01/02/2024 Dr. Daoudi Meroua 27
K-means
Average Silhouette Method
• Silhouette coefficients close to +1 indicate that the sample is far away
from neighboring clusters,
• A value of 0 indicates that the sample is on or very close to the
decision boundary between two neighboring clusters,
• negative values indicate that these samples may have been assigned
to the wrong cluster.

01/02/2024 Dr. Daoudi Meroua 28

K-means
Average Silhouette Method
• Calculer l'algorithme de clustering pour différentes valeurs de k.
• Pour chaque k, calculez la silhouette moyenne des observations
• Tracer la courbe de silhouette moyenne en fonction du nombre de
clusters k.
• L'emplacement du maximum est considéré comme le nombre
approprié de clusters

01/02/2024 Dr. Daoudi Meroua 29

The medoid-based methods
• Each cluster contains instances that are closest to the medoid (median),
which is a representative point of a set of observations.
• For example:
For the set: 1, 3, 5, 7, 9, the median is 5.
• Not affected by extreme values:
For the set: 1, 3, 5, 7, 9, 1009, the mean is 205.
• For the same set, the median is still 5.

01/02/2024 Dr. Daoudi Meroua 30

K-medoids algorithm
• Choose a number of clusters k
Repeat
• Assign each point to the nearest cluster (nearest medoid)
• Randomly select a non-medoid object Orandom
• For each medoid object Omed:
• Calculate the cost of permutation of Orandom with Omed
• If the cost s is minimized, then swap Orandom with Omed to form the new k
medoids
Until convergence

01/02/2024 Dr. Daoudi Meroua 31

Hierarchical clustering
In this type of clustering, the number of clusters cannot be known in
advance. The system takes the input dataset and outputs a hierarchy of
clusters.
There are two types of hierarchical clustering:
• Agglomerative clustering
• Divisive clustering

01/02/2024 Dr. Daoudi Meroua 32

Agglomerative clustering (bottom-up method)
Agglomerative Clustering is a type of hierarchical clustering that
follows a bottom-up strategy:
• Start: Each data point begins as its own singleton cluster.
• Merge step-by-step: At each iteration, the two closest clusters are
merged.
• End: The process continues until all points are merged into a single
cluster, or until a desired number of clusters is reached.
Example:
• Consider the following data points: X1(0,2), X2(0,0), X3(1,5,0), X4(5,0),
X5(5,2).
01/02/2024 Dr. Daoudi Meroua 33
Agglomerative clustering (bottom-up method)
We use Euclidean distance to measure the distance between the data
points.
D(x1,x2)=2
D(x1,x3)= 2,5
…
D(x2,x3)=1,5
We sort these distances and find that X2 and X3 are the closest. We
merge them into the same cluster and calculate its center as (0.75, 0).
We recalculate the distances, replacing X2 and X3 with the new cluster,
sort them again, and choose the shortest distance, and so on.

01/02/2024 Dr. Daoudi Meroua 34

Agglomerative clustering (bottom-up method)
At the end, we obtain the following dendrogram representing the
hierarchical clustering of the data:

01/02/2024 Dr. Daoudi Meroua 35

Agglomerative clustering (bottom-up method)
We know how to measure the distance between two objects, but
defining the distance between an object and a cluster, or between
two clusters, is not straightforward.

• Single linkage (nearest neighbor): In this method, the distance

between two clusters is determined by the distance of the two closest
objects (nearest neighbors) in the different clusters.

01/02/2024 Dr. Daoudi Meroua 36

Agglomerative clustering (bottom-up method)
● Complete linkage (furthest neighbor): In this method, the distances
between clusters are determined by the largest distance between any
two objects in the different clusters (i.e., by the "furthest neighbors").

● Average group linkage: In this method, the distance between two

clusters is calculated as the average distance between all pairs of
objects in the two different clusters.

● Centroid Linkage : It measures the distance between the centroids

(geometric centers) of two clusters.

01/02/2024 Dr. Daoudi Meroua 37

Divisive Clustering
The divisive clustering algorithm is a top-down clustering approach.
Initially, all data points belong to a single cluster, and the division is
done recursively as we descend the hierarchy.
Steps of divisive clustering:
• Initially, all points in the dataset belong to a single cluster.
• Partition the cluster into the two least similar clusters.
• Proceed recursively to form new clusters until the desired number of
clusters is achieved.

01/02/2024 Dr. Daoudi Meroua 38

Divisive Clustering

01/02/2024 Dr. Daoudi Meroua 39

Divisive Clustering
How to choose which cluster to divide?

• You can check the sum of squared errors (SSE) of each cluster and
choose the one with the highest value.

How to divide the chosen cluster above?

• One way is to look for the largest reduction in the SSE criterion as a
result of the division.
01/02/2024 Dr. Daoudi Meroua 40
Density-based clustering

01/02/2024 Dr. Daoudi Meroua 41

Density-based clustering
Density-based clustering involves forming clusters of observations that
are close to each other.
Principle:
• It uses density instead of distance.
• A point is considered a neighbor of another point if it is within a
distance less than ε.
• A point is dense if the number of its neighbors exceeds a certain
threshold MinPts.

01/02/2024 Dr. Daoudi Meroua 42

Density-based clustering
Let D be the dataset to partition, d a distance on X, and ϵ>0.
• We call the ϵ-neighborhood of an element X the set of observations in
D whose distance to X is less than ϵ.
• X is a core point if its ϵ-neighborhood contains at least MINPTS points.
• If the ϵ-neighborhood of an element contains fewer than MINPTS
points, then the point is classified as a border point.
• If the epsilon neighborhood of an element is an empty set, then the
point is classified as an outlier.

01/02/2024 Dr. Daoudi Meroua 43

Density-based clustering

01/02/2024 Dr. Daoudi Meroua 44

Density-based clustering
Directly density-reachable point

X is density-reachable from Y if X belongs to the epsilon neighborhood and Y is a core point.

01/02/2024 Dr. Daoudi Meroua 45

Density-based clustering
Density-reachable point

X is density-reachable from Y with X being directly density-reachable from

P2, P2 being density-reachable from P3, and P3 being density-reachable
from Y.
01/02/2024 Dr. Daoudi Meroua 46
Density-based clustering
• Density connectivity

X is density-connected from Y if there exists a point O where both X and

Y are density-reachable from O.
01/02/2024 Dr. Daoudi Meroua 47
Density-based clustering
DBSCAN (Density-Based Spatial Clustering of Applications wz

01/02/2024 Dr. Daoudi Meroua 48

Density-based clustering
●
MinPts Derived from the number of dimensions of the data such that
MinPts >= D + 1.

●
MinPts = 1 does not make sense because each point would be a
cluster.

●
MinPts should be at least 3, the higher the better.
●
The larger the dataset, the higher the value of MinPts should be
chosen.

01/02/2024 Dr. Daoudi Meroua 49

Density-based clustering

• If the epsilon value is very small, a large portion of the data will not be
clustered.
• If the epsilon value is too large, a large portion of the data will be in
the same cluster.

01/02/2024 Dr. Daoudi Meroua 50

Density-based clustering: Advantages
• Robustness to outliers: DBSCAN automatically identifies and removes
outliers during the partitioning process. This allows for the detection
of outliers while also avoiding contamination of the automatic
classification (k-means is particularly sensitive to outliers).

01/02/2024 Dr. Daoudi Meroua 51

Density-based clustering: Advantages
• The groups obtained by DBSCAN are not necessarily linearly
separable: This reduces the constraint on the shape of the obtained
groups. Non-convex groups are more likely to be over-partitioned
compared to k-means.

• DBSCAN does not require specifying the number of desired groups

beforehand: The number of groups is automatically estimated based
on the number of connected components in the accessibility graph by
density.

01/02/2024 Dr. Daoudi Meroua 52

Density-based clustering: Disadvantages
• DBSCAN assumes uniform density across all groups : impossible to
find a single threshold ε that defines a suitable neighborhood in the
case of variable density.
• Data in low-density regions are automatically eliminated as outliers ,
this is not always the case.
• DBSCAN is a transductive method: the partitioning is built from the
dataset, and it's not possible to classify a new point without redoing
the entire classification.

01/02/2024 Dr. Daoudi Meroua 53

Hard clustering an soft clustering

Kmeans: hard clustering : Assign each point to one and
only one cluster.

Em: Expectation Maximisation : Assign each data point to
each cluster with a different probability.

01/02/2024 Dr. Daoudi Meroua 54

Expectation Maximization
The Expectation-Maximization (EM) algorithm is a popular iterative
method used to find maximum likelihood estimates of parameters in
probabilistic models, especially when the model depends on latent
(hidden) variables. In the context of clustering, EM is often used with
Gaussian Mixture Models (GMMs) to assign data points to clusters.
• Objective:
Estimate the parameters of a mixture model (e.g., means, covariances,
and mixing coefficients for Gaussian clusters) such that the model best
explains the observed data.
• Latent Variables:
In clustering, the latent variable represents the unknown cluster
membership of each data point. These are not directly observed.
01/02/2024 Dr. Daoudi Meroua 55
Gaussian Mixture Model (GMM) :
A mixture is a set of K probability distributions representing K
clusters. The GMM combines several Normal distributions. Each
distribution has a mean and a standard deviation.
Expectation Maximization
Two Main Steps of EM
• Step E: Estimation of unknown data given the observed data and the
determined parameter values from the previous phase.
• Step M: Proceed with maximizing likelihood by using the unknown
estimation from Step E

Step E Step M

01/02/2024 Dr. Daoudi Meroua 57

Expectation Maximization
Expectation Step : Compute the posterior probabilities (or responsibilities) that each
data point belongs to each cluster, given the current estimates of the parameters.

Process: For each data point xi each cluster k, calculate:

where:
πk_is the mixing coefficient for cluster k.
N(xi∣μk,Σk) is the Gaussian probability density function for cluster k evaluated at xi.
γik represents the responsibility or the probability that data point xi was generated by
cluster k.
Expectation Maximization
Maximization Step (M-Step):
Goal: Update the parameters of the model using the responsibilities calculated in
the E-Step.
Process: Update the parameters for each cluster kkk using formulas such as:
Mixing Coefficients:
Expectation Maximization
Means:

Covariances:
Expectation Maximization
Iterative Process
1. Initialization:
Start with initial guesses for the parameters {πk,μk,Σk} for all k clusters.
2. Alternate Steps:
●
E-Step: Compute responsibilities γik.
●
M-Step: Update parameters based on the new responsibilities.
●
Repeat until convergence, meaning that the change in the parameters (or the
log-likelihood) is smaller than a predefined threshold.
Expectation Maximization
Convergence and Practical Considerations
●
Convergence:
EM is guaranteed to converge to a local maximum of the likelihood function,
though not necessarily the global maximum.
●
Initialization Sensitivity:
The algorithm's result can depend on the initial parameter values. Common
practices include running the algorithm multiple times with different initializations
and choosing the best solution.
●
Applications in Clustering:
By assigning probabilities (rather than hard assignments), EM for GMMs allows
clusters to overlap. This is useful in scenarios where clusters are not well-
separated.
 People's Democratic Republic of Algeria
Ministry of higher education and scientific research

Ecole supérieure en sciences et technologies de l’informatique et du numérique

Classification part 2
01/02/2024 Dr. Daoudi Meroua 1
Neural Network: Introduction
A neural network is a supervised learning system composed of a set of
nodes called neurons connected to each other. The main objective of
neural networks is to simulate artificial intelligence, mathematically
modeling the brain in order to reproduce certain characteristics:
• Memory Capacity
• Learning Capacity
• Ability to Process Incomplete Information

01/02/2024 Dr. Daoudi Meroua 2

Neural Network

01/02/2024 Dr. Daoudi Meroua 3

Artificial neuron or perceptron

Inputs Outputs

Inputs: dendrites Outputs: axons

01/02/2024 Dr. Daoudi Meroua 4

Multilayer perceptron
A multilayer perceptron or multilayer perception is composed of more
than one perceptron. They consist of three main types of layers: an
input layer, an output layer, and between these two, a number of
hidden layers. MLPs with more than two layers are called deep
networks

01/02/2024 Dr. Daoudi Meroua 5

Local connectivity networks
It is a multi-layer structure. Each neuron maintains relations with a
reduced and localized number of neurons from the lower layer.
Therefore, the connections are fewer than in the case of a classic
multilayer network.

01/02/2024 Dr. Daoudi Meroua 6

Recurrent Neural Networks
The recurrent connections bring information backward compared to
the propagation direction defined in a multilayer network. These
connections are most often local.

01/02/2024 Dr. Daoudi Meroua 7

 Fully Connected Networks
This is the most general interconnection structure. Each neuron is
connected to all neurons in the network

01/02/2024 Dr. Daoudi Meroua 8

Perceptron: detailed view

Each neuron j receives input values x_i associated with weights w_i,
which evaluate the importance of the inputs, and produces an output
that can be sent to other neurons

01/02/2024 Dr. Daoudi Meroua 9

Perceptron: detailed view
The transfer function sums the responses and sends the result to the
activation function

An activation function is then applied to generate the output Y.

01/02/2024 Dr. Daoudi Meroua 10

Activation functions
An activation function is a nonlinear function. It is specific to each layer
and is used to transform the data. The most common types are:
● ReLU
● Sigmoid
● Tanh

01/02/2024 Dr. Daoudi Meroua 11

Activation functions : Relu
The Rectified Linear Unit (ReLU) activation function is the simplest and
most widely used. It returns x if x is greater than 0, and 0 otherwise. In
other words, it computes the maximum between x and 0.

01/02/2024 Dr. Daoudi Meroua 12

Activation functions : Segmoid
The Sigmoid function returns a value between 0 and 1, representing a
probability. It is commonly used for binary classification, where a model
needs to determine only two labels

01/02/2024 Dr. Daoudi Meroua 13

Activation functions : Tanh
The tanh function is simply the hyperbolic tangent function. It is, in fact,
a mathematically shifted version of the sigmoid function: sigmoid gives a
result between 0 and 1, while tanh gives a result between -1 and 1

01/02/2024 Dr. Daoudi Meroua 14

Perceptron Learning:
Learning a perceptron involves learning the connection weights to
minimize the prediction error on the training set.
We assume that our N observations are sequentially observable, one after
the other. The learning process is iterative.
After each observation, we adjust the connection weights to reduce the
prediction error made by the perceptron in its current state

01/02/2024 Dr. Daoudi Meroua 15

Perceptron Learning:
The error function is a convex function, so to minimize it, we use the
gradient descent method.

01/02/2024 Dr. Daoudi Meroua 16

Perceptron Learning:
● Initially, we choose random values for the initial weights.
● After each observation, we apply the following update rule to each
weight

● We typically iterate either until the algorithm converges or, more

commonly, for a fixed number of iterations

01/02/2024 Dr. Daoudi Meroua 17

Training phases of a neural network model
There are several types of artificial neural networks and a multitude of
approaches and strategies to train them. Here are the main steps:
Data preparation:
● Arrangement of neurons in the network;
● The number and type of neuron layers;
● The type of connections between neurons;
● The nature of the data itself: temporal data, etc.;
● The format of the data: visual data, transactional data, etc.

01/02/2024 Dr. Daoudi Meroua 18

Training phases of a neural network model

Initialization of the neural network:

This involves randomly initializing the weights.
Forward propagation:
During the forward propagation phase, the data is propagated through
the neural network from the input layer to the output layer, passing
through the intermediate layers. The output layer determines the
output result of the neural network.

01/02/2024 Dr. Daoudi Meroua 19

Training phases of a neural network model
Backpropagation:
At the output layer, the artificial neural network has assigned a label to
the example introduced into its input layer. Knowing that the training
data is accompanied by the expected results, the neural network will
recognize that the result of forward propagation is an error. The
objective is to reduce this error during the next iterations of the neural
network, which involves correcting an error function through the
"gradient descent" algorithm.

01/02/2024 Dr. Daoudi Meroua 20

Training phases of a neural network model

Training phase:
Once all the training mechanisms are in place, all that remains is to
execute a multitude of iterations using the training data to refine the
artificial neural network.
Inference phase:
Once trained, the neural network is ready to be used.

01/02/2024 Dr. Daoudi Meroua 21

Backpropagation algorithm

01/02/2024 Dr. Daoudi Meroua 22

Example
X=[2,-1] Y=1

01/02/2024 Dr. Daoudi Meroua 23