Generative Classifier

• Introduction
  • Maximizing the Posterior Probability
  • Minimizing the Expected Risk
• Parameter Estimation
  • Bernoulli Distribution
  • Multinoulli Distribution
  • Gaussian Distribution
  • Multivariate Gaussian Distribution
• Gaussian Discriminant Analysis

Introduction

Given a set of data points $X$ and their corresponding labels $Y$, a generative classifier attempts to model the distribution $P(X,Y)$ and then uses Bayes’ rule or the chain rule to calculate $P(Y|X)$.

$$X_{D\times N}=\left[\begin{array}{cccc}{x}_{1,1}& x_{1,2}& \dots & x_{1,N}\\ x_{2,1}& x_{2,2}& \dots & x_{2,N}\\ ⋮& ⋮& \ddots & ⋮\\ x_{D,1}& x_{D,2}& \dots & x_{D,N}\end{array}\right]=\left[\begin{array}{cccc}{x}_1& x_2& \dots & x_N\end{array}\right]$$

where $D$ is the number of features and $N$ is the number of data points. The label of each data point $y_i$ is a discrete random variable that can take on one of $K$ values.

$$y_i\in \{1,2,\dots ,K\}$$

Sometimes, $y_i$ is a binary random variable belonging to one of two classes, $y_i\in \{0,1\}$. We can see that the form of the label is not important, as long as it is discrete. It is the goal of the generative classifier to predict the label of a new data point $x_{new}$ given the training data $X$ and $Y$. The generative classifier does this by maximizing the posterior probability (equivalent to minimizing the wrong classification rate) $P(Y|X)$ or minimizing the expected risk $R$.

Maximizing the Posterior Probability

Given a new data point $x$, the wrong classification rate when predicting $x$ as $c$ is

$$P(y\ne c|x)=1-P(y=c|x)$$

Using Bayes’ rule, we can rewrite this as

$$P(y\ne c|x)=1-\frac{P(x|y=c)P(y=c)}{P(x)}$$

To minimize the wrong classification rate, we want to maximize the posterior probability $P(y=c|x)$. Since $P(x)$ is constant, and $P(y=c)$ is the prior probability of $y=c$, we just need to maximize $P(x|y=c)$, the posterior probability of $x$ given $y=c$. And the prediction $\hat{y}$ is

$$\hat{y}=\arg \underset{c}{min}P(y\ne c|x)=\arg \underset{c}{max}P(x|y=c)P(y=c)$$

Minimizing the Expected Risk

The cost of different types of misclassifications can be different. For example, the cost of misclassifying a tumor as benign is much higher than the cost of misclassifying a benign tumor as malignant. In this case, we should define a loss function $L(y,\hat{y})$ that captures the cost of misclassifying $y$ as $\hat{y}$. The expected risk is then

$$R(\hat{y}|x)=\sum _{y=1}^{K}L(y,\hat{y})P(y|x)$$

where $P(y|x)$ is the posterior probability of $y$ given $x$. The prediction $\hat{y}$ is

$$\hat{y}=\arg \underset{c}{min}R(c|x)=\arg \underset{c}{min}\sum _{y=1}^{K}L(y,c)P(y|x)$$

Actually, the expected risk is the weighted sum of the wrong classification rate, where the weights are the costs of misclassifications, since $L(y,y)=0$. A simple example of a loss function is the 0-1 loss function, where

$$L(y,\hat{y})=\{\begin{array}{ll}0& \text{if }y=\hat{y}\\ 1& \text{if }y\ne \hat{y}\end{array}$$

In this case, the expected risk happens to be the wrong classification rate.

$$R(\hat{y}|x)=\sum _{y=1}^{K}L(y,\hat{y})P(y|x)=P(y\ne \hat{y}|x)$$

The short form of the loss function is $L_{\hat{y},y}$, where $\hat{y}$ is the predicted label and $y$ is the true label.

Parameter Estimation

In the following we give common distributions and their corresponding parameter estimates.

Bernoulli Distribution

$$f(x;p)=\{\begin{array}{ll}p& x=1\\ 1-p& x=0\end{array}$$

MLE of $p$:

$$\hat{p}=\frac{N_1}{N}$$

MAP of $p$:

$$\hat{p}=\frac{N_1+\alpha -1}{N+\alpha +\beta -2}$$

The laplace smoothing is

$$\hat{p}=\frac{N_1+1}{N+2}$$

Multinoulli Distribution

$$f(x;p)=\{\begin{array}{ll}{p}_1& x=1\\ p_2& x=2\\ ⋮& ⋮\\ p_K& x=K\end{array}$$

MLE of $p$:

$${\hat{p}}_k=\frac{N_k}{N}$$

MAP of $p$:

$${\hat{p}}_k=\frac{N_k+{\alpha }_k-1}{N+\sum _{k=1}^K{\alpha }_k-K}$$

When ${\alpha }_k=1$, the MAP estimate is the same as the MLE estimate. The laplace smoothing is

$${\hat{p}}_k=\frac{N_k+1}{N+K}$$

Gaussian Distribution

$$f(x;\mu ,{\sigma }^2)=\frac{1}{\sqrt{2\pi {\sigma }^2}}{e}^{-\frac{(x-\mu {)}^2}{2{\sigma }^2}}$$

MLE of $\mu$:

$$\hat{\mu }=\frac{1}{N}\sum _{i=1}^N{x}_i$$

MLE of ${\sigma }^2$:

$${\hat{\sigma }}^2=\frac{1}{N}\sum _{i=1}^N(x_i-\hat{\mu }{)}^2$$

Multivariate Gaussian Distribution

$$f(x;\mu ,\mathrm{\Sigma })=\frac{1}{\sqrt{(2\pi {)}^D|\mathrm{\Sigma }|}}{e}^{-\frac{1}{2}(x-\mu {)}^T{\mathrm{\Sigma }}^{-1}(x-\mu )}$$

MLE of $\mu$:

$$\hat{\mu }=\frac{1}{N}\sum _{i=1}^N{x}_i$$

MLE of $\mathrm{\Sigma }$:

$$\hat{\mathrm{\Sigma }}=\frac{1}{N}\sum _{i=1}^N(x_i-\hat{\mu })(x_i-\hat{\mu }{)}^T$$

Gaussian Discriminant Analysis

The Gaussian Discriminant Analysis (GDA) model assumes that the data points $x$ are generated from a multivariate Gaussian distribution $\mathcal{N}(\mu ,\mathrm{\Sigma })$, where $\mu$ is the mean vector and $\mathrm{\Sigma }$ is the covariance matrix. The model also assumes that the labels $y$ are generated from a multinoulli distribution $\text{Multinoulli}(\varphi )$, the prior probability of each class.

$$\begin{array}{rl}P(y|x)& =\frac{P(x|y)P(y)}{P(x)}\\ & \propto P(x|y)P(y)\\ & =\mathcal{N}(x|{\mu }_y,{\mathrm{\Sigma }}_y){\varphi }_y\\ \ln P(y|x)& =\ln \mathcal{N}(x|{\mu }_y,{\mathrm{\Sigma }}_y)+\ln {\varphi }_y\\ & =-\frac{D}{2}\ln 2\pi -\frac{1}{2}\ln |{\mathrm{\Sigma }}_y|-\frac{1}{2}(x-{\mu }_y{)}^T{\mathrm{\Sigma }}_y^{-1}(x-{\mu }_y)+\ln {\varphi }_y\\ \ln \frac{P(y=i|x)}{P(y=j|x)}& =-\frac{1}{2}\ln \frac{|{\mathrm{\Sigma }}_i|}{|{\mathrm{\Sigma }}_j|}-\frac{1}{2}(x-{\mu }_i{)}^T{\mathrm{\Sigma }}_i^{-1}(x-{\mu }_i)+\frac{1}{2}(x-{\mu }_j{)}^T{\mathrm{\Sigma }}_j^{-1}(x-{\mu }_j)+\ln \frac{{\varphi }_i}{{\varphi }_j}\end{array}$$

Linear discriminant analysis (LDA) is a special case of GDA where the covariance matrix $\mathrm{\Sigma }$ is the same for all classes. In this case, the decision boundary is linear.

$$\begin{array}{rl}\ln \frac{P(y=i|x)}{P(y=j|x)}& =-\frac{1}{2}(x-{\mu }_i{)}^T{\mathrm{\Sigma }}^{-1}(x-{\mu }_i)+\frac{1}{2}(x-{\mu }_j{)}^T{\mathrm{\Sigma }}^{-1}(x-{\mu }_j)+\ln \frac{{\varphi }_i}{{\varphi }_j}\\ & =-\frac{1}{2}{x}^T{\mathrm{\Sigma }}^{-1}x+x^T{\mathrm{\Sigma }}^{-1}{\mu }_i-\frac{1}{2}{\mu }_i^T{\mathrm{\Sigma }}^{-1}{\mu }_i+\frac{1}{2}{x}^T{\mathrm{\Sigma }}^{-1}x-x^T{\mathrm{\Sigma }}^{-1}{\mu }_j+\frac{1}{2}{\mu }_j^T{\mathrm{\Sigma }}^{-1}{\mu }_j+\ln \frac{{\varphi }_i}{{\varphi }_j}\\ & =x^T{\mathrm{\Sigma }}^{-1}({\mu }_i-{\mu }_j)-\frac{1}{2}{\mu }_i^T{\mathrm{\Sigma }}^{-1}{\mu }_i+\frac{1}{2}{\mu }_j^T{\mathrm{\Sigma }}^{-1}{\mu }_j+\ln \frac{{\varphi }_i}{{\varphi }_j}\end{array}$$

where ${\mathrm{\Sigma }}^{-1}$ is symmetric and ${\varphi }_i$ is the prior probability of class $i$.