Machine Learning for Bioinformatics
Cambiago Silvia Academic Year 2024-2025 Prof. Richard Hugues
CLASSIFICATION
Machine learning refers to the ability of computers to learn patterns from data, without being
explicitly programmed for every single task. It can be divided into two main types:
Y Supervised: each input comes with an associated output, so there are examples of the
correct answers. The objective is to learn a function that, given a new input, can
accurately predict the corresponding output;
Y Unsupervised: data comes without labels or outputs, and the goal is rather to discover
hidden patterns, groupings, or structures within the data itself.
Mathematically, in supervised learning, the training data is denoted by a matrix D = (xi, yi)i
where each xi represents an input feature vector and yi is the corresponding output. The task is
to find a function f such that, when given an input x, it predicts the correct output f(x) = y.
SUPERVISED LEARNING PROBLEMS
Supervised learning problems can themselves be divided into classification and regression
tasks. In classification, the outputs y are categorical. For instance, in binary classification, y
can be 0 or 1, indicating two possible classes. In multiclass classification, y can take on more
than two discrete values, corresponding to multiple categories. The goal in classification is to
minimize the number of misclassified examples, which formally amounts to minimizing the
misclassification error, essentially counting how many times the model’s predictions differ
from the true labels.
$
𝑎𝑟𝑔 𝑚𝑖𝑛!" ( )𝑓+(𝑥# ) − 𝑦# )
%'(
On the other hand, in regression problems, the outputs are real-valued quantities. Instead of
counting misclassifications, the goal is to minimize some notion of distance between the
predicted values and the true values. This is usually formalized through a loss function, such
as the squared error or the absolute error.
Once the basic framework is set, the model is able to make its predictions. Generally, the
process starts by observing data (xi, yi) and specifying a probabilistic model that captures how
inputs and outputs are related, denoted as ℙ(𝑋, 𝑌 | Θ), where Θ represents the model
parameters, that must be estimated from the data. For example, it is possible to estimate:
Y Class-specific parameters, Θ 7) , by maximizing the probability of observing the input
given the class label. These describe the distribution of inputs x, given the class y = c;
Y Class priors, π9,) by maximizing the probability of the class itself. These are the
probabilities of each class, before seeing any input data.
This approach is known as using a generative classifier, because it models the way the data is
generated. It contrasts with discriminative classifiers, which directly model the probability of
the output given the input without trying to model the full joint distribution.
There are several advantages to using generative models. In fact, they are often more
interpretable, providing insights into how different classes are distributed. On the other hand,
they typically make strong assumptions about the form of the data distribution, and, if these
1
,assumptions do not hold in practice, the model’s performance can degrade significantly.
Furthermore, even under ideal conditions, generative classifiers often achieve lower
classification accuracy compared to discriminative models, because they focus on modeling
the entire data distribution, not just the decision boundary between classes.
MAXIMUM A POSTERIORI VS MAXIMUM LIKELIHOOD
Maximum Likelihood (ML) and Maximum a Posteriori (MAP) are two fundamental techniques
for estimating the parameters of generative models. In the context of a Naive Bayes classifier,
for example, they are used to estimate the probability that a word appears in a message from a
given class.
Y Maximum Likelihood: assumes no prior knowledge and seeks the parameter values that
make the observed data most probable. It relies solely on the training data and can be
seen as purely data-driven. Mathematically, ML chooses the parameter 𝑦 that
maximized the likelihood function: 𝑦*+ = 𝑎𝑟𝑔 𝑚𝑎𝑥) 𝑃(𝑥|𝑦 = 𝑐)
Y Maximum a Posteriori: combines the likelihood of the data with a prior belief about
what parameter values are plausible. MAP uses Bayes’ Theorem and chooses y that
maximizes the function: 𝑦*,- = 𝑎𝑟𝑔𝑚𝑎𝑥) 𝑃(𝑥|𝑦 = 𝑐)𝑃(𝑦 = 𝑐). 𝑃(𝑦 = 𝑐) is the
prior.
ML is preferrable when the dataset is clean, large and with little noise, or when is needed to
make inferences without introducing assumptions or biases. MAP is better when the dataset is
small, sparse or noisy, prior knowledge is available and safer assumptions are required.
NAIVE BAYES CLASSIFIERS
A Naive Bayes classifier is a probabilistic model used for classification tasks, based on Bayes’
Theorem, which describes how to update the probability of a hypothesis as more evidence
becomes available. It is considered naïve because of the strong assumption it makes: it assumes
that all features (like words in a message) are conditionally independent given the class.
In simpler terms, the model assumes that the presence (or frequency) of one word in a message
is unrelated to the presence of any other word, once known whether the message is spam or
ham. It works following three main steps:
Y Probability modeling: it learns the prior probability of each class (P(spam), P(ham))
and the likelihood of each feature given a class (P(wi | spam), P(wi | ham)). These
probabilities are typically estimated using ML or MAP estimation;
Y Applying Bayes’ Theorem: for a new message x, the classifier computes the posterior
probability of each class: P(c | x) µ P(c) × ∏# 𝑃(𝑤# |𝑐) for each class c;
Y Choosing the most probable class: it compares the two posterior probabilities and
assigns the class with the higher value. So, if P(spam | x) > P(ham | x) the message is
spam.
UNSUPERVISED LEARNING
Sometimes, the dataset given has no labels nor categories, just rows and columns of numbers,
and the goal is to make sense out of it. This is the core of unsupervised learning: discovering
patterns in data without any predefined answers. Two techniques are typically used in this
context: clustering and latent representation (dimensionality reduction).
2
,CLUSTERING
Clustering is about dividing data into groups (clusters) such that points within the same group
are more similar to each other than to those in other groups. The aim is to find a partition C of
the dataset of n points that groups these points into K clusters: C = {C1, …, CK}. To decide
how close or far data points are from each other, a dissimilarity measure d is introduced (like
Euclidean distance). The objective is to minimize the within-cluster point scatter, denoted
W(C), which is a measure of how tightly grouped the points in each cluster are. Lower W(C)
means better clustering.
This equation sums the distances between all pairs of points within each cluster and across all
clusters. Comparing two given clusters is easy, because it is enough to compare the W(C)
values. However, enumerating all possible clusters is computationally infeasible for large
datasets due to combinatorial explosion. Hence, heuristics like k-means or hierarchical
clustering are used.
HIERARCHICAL CLUSTERING: it starts with each
data point as its own cluster, and iteratively merges the
two closest ones. Then, the distance between clusters
is updated using a linkage rule (single linkage,
complete linkage or average linkage). The process
results in a dendrogram, a tree-like diagram that shows
how clusters were merged. By cutting this tree at a
certain height, a fixed number of clusters can be
extracted.
K-MEANS CLUSTERING: the goal of this clustering algorithm is to minimize W(C). Each
(
class has a representative 𝑥. = / ∑0" ∈2! 𝑥# , called centroid. The cost function to minimize is:
!
4
𝑊(𝐶) = ( 𝑁. ( ∥ 𝑥# − 𝑥̅. ∥3
.'( 0" ∈2!
where:
Y Ck: the k-th cluster;
Y Nk: the number of points in cluster k;
Y 𝑥̅. : the centroid of cluster Ck, computed as the mean of the points in that cluster;
Y ∥ 𝑥# − 𝑥̅ . ∥3 : the squared Euclidean distance between point xi and its centroid.
The K-means algorithm finds a local minima of W(C) by sequential updates of 𝑥̅. . It proceeds
in these steps:
EEEEE
(6) EEEEE
(6)
Y Initialization: initializes K random clusters with centroids 𝑥( , … , 𝑥4
Y Repeat until convergence:
o Assignment: each data point xi is assigned to the nearest cluster;
EEEEE
(8) EEEEE
(8)
o Update: the cluster centroids 𝑥( , … , 𝑥4 are recomputed.
3
, CLUSTERING FROM A PROBABILISTIC PERSPECTIVE
Instead of simply grouping data points based on distances, the idea is to model how the data is
generated by probabilistic processes. In fact, real-world data often come from multiple
subpopulations, and each subgroup may follow a different statistical pattern. A mixture model
is a way to describe a population made up of several sub-populations, each modeled by a
probability distribution. Mixture models assume that the observed data is generated by
combining several underlying probability distributions (like Gaussians). Each point in the
dataset is generated by one of these distributions, but in the beginning it is not known which
one. That’s what mixture models are there for.
For example, consider two classes c1 and c2 with equal
probability of 0.5. Data is generated from either
N(-10, 5) or N(10, 5) depending on the class. The
histogram shows how this produces a bimodal
distribution with two distinct peaks, one for each
Gaussian. Each data point has a certain probability to
belong from a distribution or the other.
To simulate this kind of data:
Y First, draw the group Z from a categorical distribution. For example, P(Z = 1) = 0,5,
P(Z = 2) = 0,5;
Y Then, given Z = 1, sample X from Gaussian (µ( , σ(3 ). Same if Z = 2.
Suppose to observe only the data points {x1, …, xn} but not their cluster labels {z1, …, zn}.
Computing the likelihood of the data given the parameters of the model Θ becomes more
complex. It is necessary to sum over all possible clusters from each point:
where:
Y 𝑃(𝑥# |𝑍# = 𝑘): probability of observing 𝑥# assuming it came from cluster k;
Y π. : the prior for cluster k.
From this equation, to make the optimization easier, it is necessary to take the log:
This is what’s optimized in algorithms like EM (see following paragraph). The sum inside the
log makes it impossible to find a closed-form solution for Θ. That’s why EM is needed.
EXPECTATION MAXIMIZATION ALGORITHM
K-means makes hard assignments: it places each data point in one cluster and updates the group
center accordingly. It does not consider the different probabilities that a point has to belong to
each cluster. In Gaussian Mixture Models, each data point is assigned a probability of
belonging to each cluster (soft assignments). Each group is modeled as a Gaussian distribution,
and it is assumed that the data is generated from a mix of these distributions. Each group is
4
Cambiago Silvia Academic Year 2024-2025 Prof. Richard Hugues
CLASSIFICATION
Machine learning refers to the ability of computers to learn patterns from data, without being
explicitly programmed for every single task. It can be divided into two main types:
Y Supervised: each input comes with an associated output, so there are examples of the
correct answers. The objective is to learn a function that, given a new input, can
accurately predict the corresponding output;
Y Unsupervised: data comes without labels or outputs, and the goal is rather to discover
hidden patterns, groupings, or structures within the data itself.
Mathematically, in supervised learning, the training data is denoted by a matrix D = (xi, yi)i
where each xi represents an input feature vector and yi is the corresponding output. The task is
to find a function f such that, when given an input x, it predicts the correct output f(x) = y.
SUPERVISED LEARNING PROBLEMS
Supervised learning problems can themselves be divided into classification and regression
tasks. In classification, the outputs y are categorical. For instance, in binary classification, y
can be 0 or 1, indicating two possible classes. In multiclass classification, y can take on more
than two discrete values, corresponding to multiple categories. The goal in classification is to
minimize the number of misclassified examples, which formally amounts to minimizing the
misclassification error, essentially counting how many times the model’s predictions differ
from the true labels.
$
𝑎𝑟𝑔 𝑚𝑖𝑛!" ( )𝑓+(𝑥# ) − 𝑦# )
%'(
On the other hand, in regression problems, the outputs are real-valued quantities. Instead of
counting misclassifications, the goal is to minimize some notion of distance between the
predicted values and the true values. This is usually formalized through a loss function, such
as the squared error or the absolute error.
Once the basic framework is set, the model is able to make its predictions. Generally, the
process starts by observing data (xi, yi) and specifying a probabilistic model that captures how
inputs and outputs are related, denoted as ℙ(𝑋, 𝑌 | Θ), where Θ represents the model
parameters, that must be estimated from the data. For example, it is possible to estimate:
Y Class-specific parameters, Θ 7) , by maximizing the probability of observing the input
given the class label. These describe the distribution of inputs x, given the class y = c;
Y Class priors, π9,) by maximizing the probability of the class itself. These are the
probabilities of each class, before seeing any input data.
This approach is known as using a generative classifier, because it models the way the data is
generated. It contrasts with discriminative classifiers, which directly model the probability of
the output given the input without trying to model the full joint distribution.
There are several advantages to using generative models. In fact, they are often more
interpretable, providing insights into how different classes are distributed. On the other hand,
they typically make strong assumptions about the form of the data distribution, and, if these
1
,assumptions do not hold in practice, the model’s performance can degrade significantly.
Furthermore, even under ideal conditions, generative classifiers often achieve lower
classification accuracy compared to discriminative models, because they focus on modeling
the entire data distribution, not just the decision boundary between classes.
MAXIMUM A POSTERIORI VS MAXIMUM LIKELIHOOD
Maximum Likelihood (ML) and Maximum a Posteriori (MAP) are two fundamental techniques
for estimating the parameters of generative models. In the context of a Naive Bayes classifier,
for example, they are used to estimate the probability that a word appears in a message from a
given class.
Y Maximum Likelihood: assumes no prior knowledge and seeks the parameter values that
make the observed data most probable. It relies solely on the training data and can be
seen as purely data-driven. Mathematically, ML chooses the parameter 𝑦 that
maximized the likelihood function: 𝑦*+ = 𝑎𝑟𝑔 𝑚𝑎𝑥) 𝑃(𝑥|𝑦 = 𝑐)
Y Maximum a Posteriori: combines the likelihood of the data with a prior belief about
what parameter values are plausible. MAP uses Bayes’ Theorem and chooses y that
maximizes the function: 𝑦*,- = 𝑎𝑟𝑔𝑚𝑎𝑥) 𝑃(𝑥|𝑦 = 𝑐)𝑃(𝑦 = 𝑐). 𝑃(𝑦 = 𝑐) is the
prior.
ML is preferrable when the dataset is clean, large and with little noise, or when is needed to
make inferences without introducing assumptions or biases. MAP is better when the dataset is
small, sparse or noisy, prior knowledge is available and safer assumptions are required.
NAIVE BAYES CLASSIFIERS
A Naive Bayes classifier is a probabilistic model used for classification tasks, based on Bayes’
Theorem, which describes how to update the probability of a hypothesis as more evidence
becomes available. It is considered naïve because of the strong assumption it makes: it assumes
that all features (like words in a message) are conditionally independent given the class.
In simpler terms, the model assumes that the presence (or frequency) of one word in a message
is unrelated to the presence of any other word, once known whether the message is spam or
ham. It works following three main steps:
Y Probability modeling: it learns the prior probability of each class (P(spam), P(ham))
and the likelihood of each feature given a class (P(wi | spam), P(wi | ham)). These
probabilities are typically estimated using ML or MAP estimation;
Y Applying Bayes’ Theorem: for a new message x, the classifier computes the posterior
probability of each class: P(c | x) µ P(c) × ∏# 𝑃(𝑤# |𝑐) for each class c;
Y Choosing the most probable class: it compares the two posterior probabilities and
assigns the class with the higher value. So, if P(spam | x) > P(ham | x) the message is
spam.
UNSUPERVISED LEARNING
Sometimes, the dataset given has no labels nor categories, just rows and columns of numbers,
and the goal is to make sense out of it. This is the core of unsupervised learning: discovering
patterns in data without any predefined answers. Two techniques are typically used in this
context: clustering and latent representation (dimensionality reduction).
2
,CLUSTERING
Clustering is about dividing data into groups (clusters) such that points within the same group
are more similar to each other than to those in other groups. The aim is to find a partition C of
the dataset of n points that groups these points into K clusters: C = {C1, …, CK}. To decide
how close or far data points are from each other, a dissimilarity measure d is introduced (like
Euclidean distance). The objective is to minimize the within-cluster point scatter, denoted
W(C), which is a measure of how tightly grouped the points in each cluster are. Lower W(C)
means better clustering.
This equation sums the distances between all pairs of points within each cluster and across all
clusters. Comparing two given clusters is easy, because it is enough to compare the W(C)
values. However, enumerating all possible clusters is computationally infeasible for large
datasets due to combinatorial explosion. Hence, heuristics like k-means or hierarchical
clustering are used.
HIERARCHICAL CLUSTERING: it starts with each
data point as its own cluster, and iteratively merges the
two closest ones. Then, the distance between clusters
is updated using a linkage rule (single linkage,
complete linkage or average linkage). The process
results in a dendrogram, a tree-like diagram that shows
how clusters were merged. By cutting this tree at a
certain height, a fixed number of clusters can be
extracted.
K-MEANS CLUSTERING: the goal of this clustering algorithm is to minimize W(C). Each
(
class has a representative 𝑥. = / ∑0" ∈2! 𝑥# , called centroid. The cost function to minimize is:
!
4
𝑊(𝐶) = ( 𝑁. ( ∥ 𝑥# − 𝑥̅. ∥3
.'( 0" ∈2!
where:
Y Ck: the k-th cluster;
Y Nk: the number of points in cluster k;
Y 𝑥̅. : the centroid of cluster Ck, computed as the mean of the points in that cluster;
Y ∥ 𝑥# − 𝑥̅ . ∥3 : the squared Euclidean distance between point xi and its centroid.
The K-means algorithm finds a local minima of W(C) by sequential updates of 𝑥̅. . It proceeds
in these steps:
EEEEE
(6) EEEEE
(6)
Y Initialization: initializes K random clusters with centroids 𝑥( , … , 𝑥4
Y Repeat until convergence:
o Assignment: each data point xi is assigned to the nearest cluster;
EEEEE
(8) EEEEE
(8)
o Update: the cluster centroids 𝑥( , … , 𝑥4 are recomputed.
3
, CLUSTERING FROM A PROBABILISTIC PERSPECTIVE
Instead of simply grouping data points based on distances, the idea is to model how the data is
generated by probabilistic processes. In fact, real-world data often come from multiple
subpopulations, and each subgroup may follow a different statistical pattern. A mixture model
is a way to describe a population made up of several sub-populations, each modeled by a
probability distribution. Mixture models assume that the observed data is generated by
combining several underlying probability distributions (like Gaussians). Each point in the
dataset is generated by one of these distributions, but in the beginning it is not known which
one. That’s what mixture models are there for.
For example, consider two classes c1 and c2 with equal
probability of 0.5. Data is generated from either
N(-10, 5) or N(10, 5) depending on the class. The
histogram shows how this produces a bimodal
distribution with two distinct peaks, one for each
Gaussian. Each data point has a certain probability to
belong from a distribution or the other.
To simulate this kind of data:
Y First, draw the group Z from a categorical distribution. For example, P(Z = 1) = 0,5,
P(Z = 2) = 0,5;
Y Then, given Z = 1, sample X from Gaussian (µ( , σ(3 ). Same if Z = 2.
Suppose to observe only the data points {x1, …, xn} but not their cluster labels {z1, …, zn}.
Computing the likelihood of the data given the parameters of the model Θ becomes more
complex. It is necessary to sum over all possible clusters from each point:
where:
Y 𝑃(𝑥# |𝑍# = 𝑘): probability of observing 𝑥# assuming it came from cluster k;
Y π. : the prior for cluster k.
From this equation, to make the optimization easier, it is necessary to take the log:
This is what’s optimized in algorithms like EM (see following paragraph). The sum inside the
log makes it impossible to find a closed-form solution for Θ. That’s why EM is needed.
EXPECTATION MAXIMIZATION ALGORITHM
K-means makes hard assignments: it places each data point in one cluster and updates the group
center accordingly. It does not consider the different probabilities that a point has to belong to
each cluster. In Gaussian Mixture Models, each data point is assigned a probability of
belonging to each cluster (soft assignments). Each group is modeled as a Gaussian distribution,
and it is assumed that the data is generated from a mix of these distributions. Each group is
4
