The Bayes Classifier, an Example with Gaussian Class Conditionals
By David Dobor (draft)
Introduction
This is part 2 of a 5-part tutorial on Bayesian
classification. It can be read independently from the other parts,
but requires familiarity with basic probability and
statistics, especially with the Bayes rule.
The classification problem in general, briefly repeated here for
convenience, is as follows. We are given $N$ training objects
$\mathbf{X_1, ... X_N}$, each is a feature vector of dimension
$D$. Each of the $D$ features is either a discrete or a continuous
random variable. The objects are labeled by $y \in \{1, 2, ..., C\}$
that describe to which of the $C$ classes a given object
belongs. Our job is to predict the class $y$ for an unseen
object $\mathbf{X}_{new}$.
In the following example, the features are assumed to be drawn from
Gaussian (normal) distributions. (This differs from the email
classification example discussed previously, in which the features
were discrete (e.g. number of times a certain word occurred in a
message.))
The rest of this page:
- Describes the problem
- Shows how to compute the posterior class distribution of a new
observation using the Bayes rule (without the naive Bayes assumption
first)
- Shows how to predict the class label of a new observation
- Demonstrates how to plot the decision contours
- Exposes possible flaws of the Bayes classification model
- Introduces the Naive Bayes simplification and re-computes the
results
The MATLAB code that generated all the figures that follow can be
found here.
The Problem Setup
We use artificially generated data to illustrate Bayesian
classification. All of the 90 observations in this data set have
been labeled as belonging to one of the 3 different classes. Each
class contains 30 observations. The labels are $y \in \{1, 2,
3\}$. The red circles denote class 1, the green diamonds class 2,
and the blue squares class 3. The observations themselves (I'll call
them data points sometimes) consist of just 2 features and are
represented as points in a plane (in $R^2$). We denote feature
vectors by $\mathbf{X} = (X_1, X_2)$. Each feature vector is drawn
from a bivariate normal distribution. Given class $y$, the
observations are assumed to be drawn from the same bivariate normal
distribution with parameters $\mu_y$ and $\Sigma_y$: $P(\mathbf{X} |
Y = y) = \mathcal{N}(\mu_y, \Sigma_y)$.
|
|
The plot on the right superimposes iso-probability lines on the
data (i.e. the probability density takes the same value at every
point along any contour line). Since the data are generated from
bivariate normal distributions, these lines are
ellipses. (Incidentally, notice that class 3 has relatively high
covariance between its features. This is evident by the
iso-probability ellipses not being aligned with the coordinate axes;
if there were zero correlation between the features, the axes of the
ellipses would be parallel to the coordinate axes. We'll return to
this point at the end of this tutorial.)
The Goal: Assign a label to a new observation. For
example, given a new feature vector, say $\mathbf{X}_{new} = [X_1 =
x_1, X_2 = x_2]^T =[4, 7]^T$, determine which of the 3 class labels
to assign to it. We'll discuss the decision rule we'll use
in order to make this assignment in a minute.
Recall the Bayes formula:
$$ P(Y | X_1, X_2) = \frac{P(Y) \cdot P(X_1, X_2 | Y)} {P(X_1, X_2)}
$$
Also recall that the
terms in this formula are usually refered to as follows:
$$posterior=\frac{prior \cdot likelihood} {evidence} $$
Once we compute this posterior distribution of $Y$ for a new data
point, the decision rule as to which label to assign to the
point is simple: assign to this data point the label with the
highest posterior probability. We will see this on a concrete
example below.
Let's begin by computing all the ingredients for the Bayes formula:
The Terms in the Bayes Formula
Prior: With 30 data points belonging to each class, and
the total of 90 points, we use $P(Y = y) = N_y/N = 30/90 = 1/3$ for the
prior. This represents our prior belief about which class a new data
point might belong to, before we get to observe it.
Likelihood:I've generated these data points from 3
different Gaussian distributions, and I know what the parameters
$(\mu_y, \Sigma_y)$ are for each of the three $y$s. However, the
parameters are not usually known in many real-world applications and
need to be estimated from the data. So I'm going to keep my
parameters a secret and we'll estimate them from the data. (If
you'd really like to know, gen_data.m generated the data
and thus holds the key to the secret.)
I'll use Maximum Likelihood Estimates ( MLE ) for the
parameters. (We'll consider alternatives to this later.)
The MLEs for the Gaussian distribution are derived in every
statistics textbook, so of course I'll skip that. (This is usually
done by differentiating the log-likelihood with respect to each
parameter, setting it to zero, finding the solution, and showing
that it's indeed a maximum.) The result is this:
$$ \mu_y = \frac{1}{N} \sum_{n=1}^{N_y} x_n $$ $$ \Sigma_y =
\frac{1}{N} \sum_{n=1}^{N_y} (x_n - \mu_y) \cdot (x_n - \mu_y)^T $$
The summations here are only over the data points that came from
class $y$.
Step 0: Estimate the Parameters
As just mentioned, the parameters of the three normal
distributions must be estimated. This is itself a machine-learning
task, but here it's not complicated. The following script computes
the $(\mu_y, \Sigma_y)$ MLE:
load data_bayes3 % load the data generated by gen_data.m
labels = unique(y);
for c = 1:length(labels)
pos = find(y==labels(c));
class_mean(c,:) = mean(X(pos,:)); % (2x1)
class_covar(:,:,c) = cov(X(pos,:),1); % (2x2)
end
Step 1: Write a Function that Computes Normal Density
Here we just implement the familiar bivariate normal density
formula:
$$p(\mathbf{x}|\mu,\Sigma) =
\frac{1}{(2\pi)^{D/2}|\Sigma|^{1/2}}\exp\left\{-\frac{1}{2}(\mathbf{x}-\mu)^T\Sigma^{-1}(\mathbf{x}-\mu)\right\}$$
The following MATLAB function takes the parameters of a normal
distribution together with the the point(s) at which to evaluate the
density and returns the density at that point. (Multiple points can
be passed in as rows of X.)
%Implements the normal probability density with parameters mu and cov_mat.
%Rows of X are points at which the density is evaluated
function prob = density_norm(X,mu,cov_mat);
[n,d] = size(X);
% center the data points
X = X-ones(n,1)*mu;
const = 1/((2*pi)^(d/2)*sqrt(det(cov_mat)));
arg = diag(X*inv(cov_mat)*X');
prob = exp((-.5)*arg);
prob = const*prob;
Step 2: Predict
Now we have everything we need to do the prediction, i.e. assign a
label to an unseen data point. Suppose that the new point that we
need to classify is $[4, 7]^T$. We will compute the posterior
probability that this point belongs to class $y$.
First, compute the class-conditional densities by passing this
point to the function from step1. Do this for each class:
x = [4 7];
probs=[];
for c = 1:3
probs(c) = density_norm(x, class_mean(c,:), class_covar(:,:,c));
end
posteriors = (1/3)*probs
max(posteriors) %largest posterior probability
find(posteriors == max(posteriors)) %index of the largest posterior
Multiplying each of the three class-conditional densities by its prior,
1/3, return the desired posterior probability.
The entries in the following table show the results:
| $Y$ |
$P(\mathbf{X} = [4, 7]^T | Y = y)$ |
$P(\mathbf{Y} = y)$ |
$P(\mathbf{X} = [4, 7]^T | Y = y) \times P(\mathbf{Y} = y)$) |
| 1 |
0.0245 |
$\frac {1} {3}$ |
0.0082 |
| 2 |
0.0695 |
$\frac {1} {3}$ |
0.0232 |
| 3 |
0.0000 |
$\frac {1} {3}$ |
0.0000 |
Finally, to classify the point, select the largest entry in the
last column and choose the label corresponding to it. Notice that
this new point is incredibly unlikely to belong to class 3 (its exact
probability returned by MATLAB is 1.9686e-21) and almost 3 times as
likely to belong to class 2 than to class 1. Therefore:
Answer: assign label $\mathbf{2}$ to point $\mathbf{X} =
[4, 7]^T$
Plot the Classification Contours
We can plot the contours for the classification probabilities over
a grid of many points in $R^2$ (MATLAB's meshgrid function
is very helpful in this, see code). For each class, our model will
assign a high probability to the region in the plane where points of
that class congregate and low probability to regions far away from the
points.
This is what the probability contours look like for each of the
classes:
Why Bayes Classification can be Bad for You
Really, it's not that bad, Bayesian Classification often works
very well in practice, even with the naive assumption (see below),
as we'll see later.
However, notice the strange effects in the top left figure
above. The area in the middle lower part of the plot is assigned as
high a probability as the area closer to the cluster of class 1
points. This is explained by the relative 'steepness' of
class-conditional contours for class 3, as compared with the
contours for the other classes. Class 3 density decays so fast that
the density for class 1 is actually higher to the right of class
3. This is kind of unfortunate, because it doesn't seem sensible to
label the points in middle lower region, that are so far away from
class 1, as belonging to class 1. It would be much better if
probabilities became less certain as we moved farther away from the
data.
Naive Bayes Simplification
In the example just considered, we were able to capture the
dependencies between the two features - our covariance matrices had
non-zero off diagonal entries. For example, the data points in class
3, show strong dependency between the features which is reflected by
relatively large off-diagonal entries in the
covariance matrix for this class. (This dependency is also reflected
on the plot: notice that the principal axes of the ellipses, which
represent the iso-probability levels, are not parallel to the
coordinate axes.) In general, fitting 2-dimensional normal involves
choosing 5 parameters: 2 for $\mu$, the means, and 3 for the distinct
entries in the covariance matrix (since $\Sigma$ is symmetric, we
really have 3 possibly distinct entries, not 4). This is perfectly
fine for our small example of just 90 points. However, as the number
of dimensions starts increasing, the $D$-dimensional normal would
require fitting $D + D + \frac{D(D-1)} {2}$ parameters ($D$ for the
mean, the rest for the covariance matrix). So if we only had 30 data
points ans 10 features, we wouldn't be able to reliably fit the 65
parameters.
This problem is overcome in practice by making the naive Bayes
assumption: for a given class the features are assumed to
be independent and therefore the $D$-dimensional
class-conditional distributions are factorized into a product of $D$
univariate distributions. A univariate normal requires just 2
parameters, $\mu$ and $\sigma^2$, so overall we have way fewer
parameters to fit.
But this means that we are also restricting the shapes of the
class-conditional distributions: Now they need to be aligned with
the axes. This is the price exacted by the decrease in the number of
parameters: we give up the model flexibility and are unable to
capture the within-class dependencies.
Anyway, here's the likelihood function with the naive Bayes
assumption:
$$P(X_1, X_2, ..., X_D | Y = y) = \prod_{d = 1}^D P(X_d | Y = y)$$
And here's everything re-plotted with the naive Bayes
assumption. Notice how the principal axes of the ellipses are now
parallel to the coordinate axes.
