1 Bayesian approach
11 Bayes’ Theorem for Probability Densities
The conditional probability mass function of a random variable given another random variable can be expressed as:
Where: is the conditional pmf
is the joint distribution
12 Likelihood
The joint probability of an object and its class can be decomposed in two equivalent ways:
Where: is the distribution of
is the probability of a class
is the likelihood function of a class
is the a posterior probability of a class
is the Bayes’ formula
The term “likelihood” may seem confusing since we’re talking about probabilities. However, the likelihood function measures how likely the data is, given a specific class . While it’s a probability, we interpret it as the “likelihood of observing if the true class is “.
Objects and class labels are produced by a joint distribution:
The term is called the likelihood as it assesses how likely the data (objects ) comes from a particular class . For example, if is weight and is one of two classes, ‘cat’ or ‘dog’, is the probability for a particular animal to have weight assuming it is a cat. If this probability is low, the animal is unlikely to be a cat.
13 Maximum Likelihood Classifier (Bayes Optimal Classifier)
Where: is the error cost for class
is the distribution of (independent of , so dropped from argmax)
is the probability of class (prior)
is the likelihood function of class
is the posterior probability of class
The Bayes optimal classifier is derived by minimizing expected risk. The error cost allows us to assign different penalties to different types of misclassification. For example, in medical diagnosis, falsely classifying a sick patient as healthy (false negative) might be more costly than falsely classifying a healthy patient as sick (false positive).
This classifier is considered “optimal” because it minimizes the probability of classification error:
by selecting the hypothesis that maximizes the posterior probability given the data.
In practice, empirical probability densities are used, so the classifier is not truly optimal. The term from the Bayes formula can be eliminated from argmax over as it depends only on :
If the probabilities of all classes are equal , then can also be eliminated from argmax:
The main idea of this method is to assign the object to the class whose probability density is maximized in a given region.
The key insight of Bayesian classification is that we incorporate both prior knowledge (class probabilities) and observed evidence (likelihood) to make decisions. This matches human intuition - we often make judgments based on both our prior beliefs and new observations.
However, it’s optimal only if we know the true distributions or , which are unknown in practice. Overfitting occurs when the empirical estimations or are used.
2 Discriminative vs Generative Models
21 Key Characteristics
A discriminative classification model focuses on learning the decision boundary between classes by modeling the conditional probability , where is the class label and is the input data. These models do not attempt to model the distribution of the data itself, but rather directly predict the label given the features. A generative classification model aims to model the joint probability distribution , meaning they model how the data is generated for each class. From this, they can derive the conditional probability .
| Aspect | Discriminative Models | Generative Models |
| Goal | Learn the decision boundary between classes | Model the joint probability |
| Probability Modeled | (conditional probability) | (joint probability) |
| Example Algorithms | Logistic regression, GLM, SVMs, neural networks | Naive Bayes, GMMs, Fisher’s Linear Discriminant, HMMs |
| Accuracy | Often more accurate for classification tasks | Can be less accurate for classification |
| Data Generation | Cannot generate new data | Can generate new data (e.g., by sampling from ) |
| Insight into Data | Focuses on boundaries between classes | Models the distribution of the data |
| Complexity | Simpler, as only the boundary is learned | More complex, as the full data distribution is modeled. Require more data. |
| Use Case | When classification accuracy is the priority | When understanding data distribution or data synthesis is needed |
In practice, the choice between discriminative and generative models depends on:
In a discriminative approach, it’s important to accurately describe only the points near the decision boundary, while other points can be ignored. Methods like SVM are sensitive to outliers since they build their decision boundary based on these points.
In a generative approach, the probability distribution that generated the observed data is recovered. These methods are more robust to outliers that are far from the decision boundaries.
Generative approaches should be used when density distribution recovery is required, such as for data interpretation. For simple classification tasks, discriminative approaches will work better, though they are more complex and require more data.
22 Error and Empirical Risk
The error (empirical risk) of the optimal Bayesian classifier is:
Where: is the error cost for class
is the probability of class (marginal dist.)
defines the region of space where the algorithm made an error
The integral exactly equals the total probability of error: the probability is integrated over the region of space where the algorithm makes an error.
The empirical risk formulation allows us to understand Bayesian classification from a risk minimization perspective. The decision rule minimizes the expected cost of misclassification by choosing the class that minimizes the posterior expected loss.
The form of the Bayesian classification algorithm (maximum likelihood classifier) follows from minimizing this empirical risk:
The Bayesian classifier is optimal in the sense that it minimizes the error . This optimality is proven when the density distributions or are exactly known, but in reality, they are unknown. Overfitting occurs when empirical estimates of distributions or are used to build the classifier.
If the error costs and/or class probabilities are equal for all classes, they can be removed from the operator.
A generalization of the optimal Bayesian classifier formula for when the error cost depends not only on the true class but also on the erroneous class predicted by the algorithm:
This generalized form allows for sophisticated cost modeling. For example, in multiclass medical diagnosis, misclassifying a malignant tumor as benign might have a much higher cost than misclassifying it as any other non-benign condition. The cost matrix encodes these domain-specific priorities.
This records the total probability that the algorithm will confuse the true class with another class, taking penalties into account. The original formulation treats the error cost as a class weight; the more dangerous it is to make a mistake on a class, the greater its weight.
The minimal error value is achieved if the class is chosen for which the probability of error is minimal:
In the original formulation, the posterior probability of class is maximized, and is used over the true classes. In this generalization, the class is chosen for which the prediction of error probability is lowest.
3 Naïve Bayes Classifier
31 General Naïve Bayes
The Naïve Bayes classifier is expressed as:
Where: , meaning features are independent
is the empirical probability density
is the 1D empirical distribution for the th feature
The “naïve” in Naïve Bayes refers to the strong independence assumption between features. While this assumption rarely holds in real data, the algorithm often performs well in practice. This is partly because classification only requires getting the decision boundary right, not the exact probability values.
From the optimal Bayes classifier:
Restoring one-dimensional densities is a much simpler task than restoring an -dimensional one. The method is called “naive” because features are assumed to be independent. Density estimation can be modeled in any framework:
- parametric density estimation
- non-parametric density estimation
- mixture of distributions
32 Training Process
The Naïve Bayes model can be expressed as:
Naïve Bayes assumes independence of all features. We need to train a 1D empirical probability distribution per feature. Using the exponential family, which encompasses many distributions:
The training process for Naïve Bayes is computationally efficient - we only need to calculate sufficient statistics for each feature within each class. For categorical features, we simply count frequencies; for continuous features, we estimate distribution parameters like mean and variance.
The empirical risk for all objects, features, and classes can be split per class and per feature, resulting in separate 1D optimization problems:
The empirical risk per separate problem:
Finding the extremum of the empirical risk:
Thus, the mean parameter equals the average feature value per class:
And the canonical parameters can be found with the canonical link function depending on the specific distribution:
It’s quite easy to train Naïve Bayes, as you only need to compute the average feature value per class and then use it to compute the canonical parameters. After that, the classifier can be used immediately.
33 Linear vs. Non-linear Naïve Bayes
When using some distributions (like Bernoulli), Naïve Bayes becomes an ensemble of per-class linear models:
The linearity or non-linearity of Naïve Bayes depends on the choice of probability distribution for features. With Bernoulli or multinomial distributions (for binary or categorical features), the classifier is linear. With Gaussian distributions (for continuous features), the classifier becomes quadratic if variance differs between classes.
For other distributions, the algorithm is non-linear. For example, with the commonly used Gaussian distribution, the non-linear term is quadratic. Also, a dispersion parameter can occur.
The Naïve Bayes classifier becomes a linear model when:
When the dispersion parameter does not depend on the class, we can eliminate under as it does not depend on :
- For most distributions from the exponential family, , so the classifier is linear.
- For non-standard Gaussian distributions described by a generalized exponential family, if the data is normalized, again and can be canceled. If the data is not normalized, but does not depend on class , can still be eliminated and the classifier remains linear.
- For Gaussian distributions with heteroscedasticity (variance depends on class), the Naïve Bayes classifier is non-linear. It will have a quadratic term .
Different features may be described by different distributions (e.g., feature 1 by Poisson, feature 2 by Gaussian, feature 3 by Bernoulli), and the classifier can still be linear.
34 Text Classification with Naïve Bayes
In text classification, Poisson distribution models word occurrence in a document:
The Naïve Bayes approach to text classification treats documents as “bags of words” where word order doesn’t matter. This simplification, while naive, works surprisingly well for many text classification tasks like spam detection or topic classification.
The Naïve Bayes classifier depends on the average document length:
Poisson distribution models the probability of an event occurring exactly times with a given parameter (the average/expected number of events in the modeled time interval).
Poisson distribution is used in text classification models. Any document is represented as an object with occurrences of specific words from an ordered dictionary of words :
The parameter represents the average occurrence of the word in class .
The expected occurrence of word in documents of class :
The average length of documents in class is:
Finally:
The adjustment for document length () is an important feature of the Naïve Bayes text classifier. Without it, the classifier would have a bias toward assigning longer documents to classes with higher average word frequencies.
The more words in a document, the more non-zero elements in and the larger the linear part . This is compensated by subtracting the average document length . Long documents with many words don’t have priority over short ones.
If the average occurrence of a word doesn’t depend on class , it’s part of the common vocabulary and doesn’t affect classification. This means Naïve Bayes has a built-in feature selection mechanism.
For text representation in Naïve Bayes classifiers:
- Text is a sequence of random events, where each word is a random event
- Each word in a document occurs independently of other words
- Each word is generated by a Poisson process (distribution)
- To obtain an object representation of text , it’s treated as a bag of words with integer frequencies , where is the word’s position in the dictionary, and these frequencies are recorded in vector
35 Multinomial Bayes Classifier
From the optimal Bayes classifier, we can derive the multinomial Bayes classifier:
The multinomial variant of Naïve Bayes is especially popular for text classification. Instead of modeling the occurrence of each word with Poisson, it models the probability of seeing each word given a class. This works well when words follow a multinomial distribution (e.g., when drawing words from documents with replacement).
A word is represented by its index in a dictionary of size . Each word in a document is represented as number , and the document is represented by a sequence (order not important) of all its words. Objects may have different dimensions and are not represented as a matrix .
Let’s define counters for a word in document and in corpus of documents :
Also define empirical probability for each word for a given class , i.e., the frequency of in documents of class :
Write the logarithm of empirical probability using multinomial distribution:
Finally:
The linear part is a weighted logarithm of each word’s (non-unique) occurrences. The classifier depends on the document’s size (in contrast to Poisson Naïve Bayes).
36 Advantages of Naïve Bayes
Naïve Bayes has several advantages:
- It trains in linear time, as it only requires computing average feature estimates by class and the dispersion/spread parameter (for some distributions)
- It rarely overfits, as the solution depends on average feature values, and these estimates are reliable, stable, and controlled by the law of large numbers
- It can uniformly handle features of different types, as different distributions can be used to describe them
- It has built-in feature importance through maximizing posterior probabilities
- It has built-in feature selection through equal posterior probabilities — if a feature equally affects the probability of all classes, it’s uninformative, allowing for filtering of stop words and common vocabulary in text classification
- It can be used as a strong baseline model, but the independence assumption of features is too strong for more complex applications
Despite its simplicity and “naïve” assumptions, Naïve Bayes often performs surprisingly well in practice, especially for text classification tasks. It serves as an excellent baseline model and can provide reasonable performance with minimal computational resources, even when training data is limited.
4 Discriminant Analysis
41 Connection Between Metric and Bayesian Classifiers
The optimal Bayesian classifier (without logarithm of density):
Non-parametric Parzen-Rosenblatt density estimation:
The connection between metric-based methods like kNN and probabilistic methods like Bayesian classification reveals the theoretical foundations underlying many machine learning algorithms. What seems like different approaches are often just different views of the same fundamental principles.
Substituting the density estimate into the Bayesian classifier, assuming the same window width is used for all classes:
If the window width doesn’t depend on the class, we can exclude normalization by window width — it ensures that the empirical estimate is actually a density (normalization by the number of objects is introduced separately).
However, if different window widths are required for different classes, we need to calculate:
Thus, the metric classifier (generalization of kNN) can be derived from more general principles — Bayes’ theorem and kernel density estimation.
42 Quadratic Discriminant
Where: are distribution parameters for class
is a quadratic form of features
Quadratic Discriminant Analysis (QDA) makes more flexible assumptions than Linear Discriminant Analysis (LDA) by allowing each class to have its own covariance matrix. This results in quadratic decision boundaries rather than linear ones, allowing the model to capture more complex class relationships.
Substituting parametric density estimates for each class into the optimal Bayesian classifier:
The expression under is a quadratic form, creating a quadratic separating surface between classes. If covariance matrices are identical, the quadratic discriminant degenerates into a linear one.
If classes have equal prior probabilities and equal error costs, the first term disappears and the separating surface is a linear hyperplane passing exactly between the densities. If the error cost for a class is higher, it draws the separating surface closer.
In some cases, the density of one class can outweigh that of another at a distance, then the separating surface will have two regions. In the example, the left region would belong to the gray class, although it would be more logical to assign it to the red; this is a disadvantage of the generative approach.
If two Gaussians overlap (classes are inseparable), the separating surface will be a doughnut, and the density separation approach won’t work.
When the covariance matrices for different classes are equal, the separating surface between them is linear. This can be shown by starting with the equation for the surface separating classes and :
After logarithmic transformation and substituting density estimates with equal covariance matrices, the quadratic terms cancel out, resulting in a linear form in terms of :
43 Linear Discriminant Analysis (LDA)
LDA is a supervised learning method for classification and dimensionality reduction. It works by finding a linear combination of features that best separates two or more classes.
LDA can be viewed from multiple perspectives:
LDA assumes different classes generate data based on Gaussian distributions with the same covariance matrix but different means. The method maximizes the ratio of between-class variance to within-class variance to ensure maximum class separability. The resulting decision boundary is linear, and LDA can also reduce feature space dimension by projecting data onto a lower-dimensional subspace that preserves class separability.
44 Fisher’s Linear Discriminant
Fisher’s linear discriminant (FLD) is a supervised linear classification method used to separate two or more classes of data. The technique aims to find a linear combination of features that maximizes the separation between classes while minimizing the within-class scatter. It is often applied in dimensionality reduction and classification problems.
The method assumes all classes have the same covariance matrix (i.e., all class distributions have the same shape but different bias), so it can be used to estimate the covariance matrix for small datasets. It seeks to project the data onto a line such that the separation between different class means is maximized while the variance within each class is minimized.
- The whole dataset scatter matrix can be divided into two separate terms:
- Within-class scatter matrix is estimated as the mean covariance matrix of all classes.
- Between-class scatter matrix is estimated as the covariance matrix of the classes themselves.
- The idea is to find a projection of a data vector onto a 1D line:
- The variance of this projection is decomposed into 2 terms:
- That projection must maximize the ratio of the between-class variance to within-class variance:
- Linear discriminant function represents the distance from to a class center in the new projected space:
- Finally, we use this distance (discriminant function) in the discriminant rule to choose the closest class:
Fisher’s approach offers a geometric interpretation: it finds the direction in feature space along which the classes are most separated relative to their within-class spread. This makes it both a classification method and a dimensionality reduction technique.
45 Linear Discriminant Function
A linear discriminant function is defined as:
This is a mapping from the feature space to a set of categories , defined by partitioning into disjoint regions , where each region corresponds to a different category in .
This is achieved by maximizing discriminant functions for each category, so is classified into when exceeds the discriminant values for all other categories: , where maps from to .
46 Multiclass LDA
For multiclass problems, LDA can be applied in two different settings:
- One-vs-one: Train pairwise models
And aggregate them using some kind of voting, e.g.,
Different strategies for handling multiclass problems lead to different decision boundaries. One-vs-one approaches tend to be more robust but require training more models, while one-vs-all approaches are more efficient but may suffer when classes are imbalanced.
The result is a decision boundary combined of multiple one-vs-one lines, which may be smooth depending on the voting approach used.
- One-vs-all: Train exactly models and determine which class maximizes:
This effectively selects the hyperplane with the maximum distance to . The final decision boundary is defined by distance; blue lines lie between hyperplanes at equal distances, and the decision is based on which side of the blue line the object lies.
5 Gaussian Mixture Models
51 Model Structure
In a Gaussian Mixture Model (GMM), the density of each class is described by a weighted sum of multivariate Gaussian densities:
GMMs provide a way to model complex data distributions by combining multiple Gaussian components. This makes them more flexible than single-distribution models, allowing them to capture multimodal class distributions and complex cluster shapes.
All features are assumed independent, so all covariance matrices are diagonal. Multivariate Gaussian densities can be represented as products of one-dimensional densities:
Each class is described by a mixture of multivariate Gaussians, each of which decomposes into a product of one-dimensional Gaussians due to feature independence. However, this doesn’t mean the model assumes feature independence overall: a sum of “orthogonal” Gaussians can describe any density, though it might require more components than “non-orthogonal” Gaussians. Nevertheless, their mixture is a universal approximator.
52 EM Algorithm for GMM
The Expectation-Maximization (EM) algorithm is used to find the parameters , , for , :
Initialization: Set , ,
Repeat iteration to optimize distribution parameters , , :
The EM algorithm alternates between two steps: This process continues until convergence, maximizing the likelihood of the observed data.
Expectation: For all , estimate a posteriori probability (weights) to come from :
Maximization: For all mixture components and classes , reestimate parameters:
Stop if , , or do not change significantly
53 Connection to Metric Classifiers
The density of data can be described by a mixture of simple Gaussian distributions (features are considered independent, i.e., covariance matrices are diagonal):
The connection between GMMs and metric-based methods reveals that many classification approaches are related. GMMs can be viewed as a generalization of kernel density estimation with tunable parameters, combining aspects of both generative and discriminative methods.
Dependency between features is already accounted for in the sense that a mixture of simple Gaussians is a universal approximator; any density can be described by a sum of “orthogonal” Gaussians, though more might be needed than with “non-orthogonal” ones.
Diagonal covariance matrices are easy to invert and have simple determinants, making GMMs quick to train. In fact, GMMs are a generalization of non-parametric kernel density estimation, where each Gaussian has tunable parameters.
The density of each class can be modeled by a mixture of simple Gaussian distributions:
The estimated density is used in a Bayesian classifier:
This algorithm explicitly contains an RBF kernel:
Effectively, the algorithm is a metric algorithm that evaluates the metric proximity of each object to each class through a sum of weighted RBF kernels. Each RBF kernel contains a learned metric that measures the distance from the class to the object, weighing features in an optimal way:
The dual nature of GMMs - both generative and metric-based - makes them versatile tools. They can be used for:
Key insights:
- The generative Gaussian Mixture Model, when substituted into a Bayesian classifier, also functions as a discriminative (metric) classification method
- GMM is a density estimation method but can be used for clustering
- The algorithm is equivalent to a three-layer neural network, where the 1st layer calculates “one-dimensional distances” from the object to the class center, the 2nd layer weighs these distances, and the 3rd chooses the best class
- GMM = generative + discriminative + neural network
The RBF (radial basis function) kernel can be used in both discriminative and generative approaches to classification:
- In SVM (discriminative), the RBF kernel is used in the kernel trick, and the method identifies support objects to build the separating surface, making it sensitive to outliers
- In EM (generative), the RBF kernel arises from parametric estimation of class densities, primarily identifying objects in cluster centers, making the algorithm robust to noise
The EM algorithm converges quickly but is sensitive to initial approximation. Selecting the number of components (hyperparameter) can be challenging, and simple heuristics may not work.