Linear Methods for Classification¶
Table of Contents
Note
We note that the output here is a categorical rv \(G\in\mathcal{G}\) where \(|\mathcal{G}|=K\).
We therefore associate each observed output \(g_i=k\) where \(k=1,2,\cdots,K\).
For classification, we can always assign a different colour to each datapoint \(x_i\) in the input space \(\mathcal{X}\) as per the output class \(k\) it belongs to.
The decision boundary in that case is the partition boundary in the input space between different coloured inputs.
A classifier is linear if the boundary can be expressed as linear equations involving \(\mathbf{x}_j\).
We can extend linear classifier to create non-linear decision boundary in the original input space by using transforms, such as basis expansion.
Discriminant Classifiers¶
Note
We can define a discriminant function \(\delta_k(x)\) for each class \(k\).
For each \(x\in\mathcal{X}\), the classification prediction then becomes
\[g^*=\underset{k}{\arg\max}\delta_k(x)\]For a linear classifier, we need some monotone transform \(h\) of \(\delta_k\) to be linear.
\(h\) can very well be just the identity function.
The decision boundary between \(k=1\) and \(k=K\) is given by the surface where
\[h(\delta_1(x))-h(\delta_K(x))=0\]
Probabilistic Classifiers¶
Note
For probabilistic classifiers, the discriminant function is usually defined as the posterior probability.
\[\delta_k(x)=\mathbb{P}(G=k|X=x)\]If \(\log\) is used as the monotone transform, then the decision boundary forms the logit function
\[\log\frac{\mathbb{P}(G=1|X=x)}{\mathbb{P}(G=K|X=x)}=\log\delta_1(x)-\log\delta_K(x)\]At the decision boundary, the posterior probabilities are equal.
\[\log\delta_1(x)-\log\delta_K(x)=0\]
Warning
We note that in theory we can just create a table for the conditional pmf enumerating all possible probabilities
\[p_{G|X}(k|x)=\mathbb{P}(G=k|X=x)=\mathrm{Multinoulli}(p_1(x),\cdots,p_K(x))\]and use MLE to estimate the parameters from data.
However, doing so would require estimating \(K-1\) parameters each Multinoulli distribution separately for every single value that \(X\) can take.
This becomes prohibitive when \(x\) is a continuous real or vector.
Even when \(x\) takes finite values, the task becomes tough with the dimension of \(x\).
Discriminative Models¶
Note
Here, we confine ourselves to a smaller subspace of possible probabilities which can be specified with a manageable number of parameters.
\[p_{G|X}(k|x)\approx f(\beta_k,x)\]For binary classification, the posterior can be defined with \(\mathrm{Ber}(p)\) such that
\[\mathbb{P}(G=y|X=x)=f(\beta,x)^y(1-f(\beta,x))^{1-y}\]
Linear Discriminative Models¶
Note
Here, we model the logit as a linear function of \(x\).
For each class \(k=1,2,\cdots,K-1\), we can define the logits in terms of a set of linear equations
\[\log\frac{\mathbb{P}(G=k|X=x)}{\mathbb{P}(G=K|X=x)}=\beta_{k,0}+\beta_{k,1:}^Tx\]Here, each \(\beta_{k,0}\in\mathbb{R}\) is the bias (intercept) term and \(\beta_{k,1:}\in\mathbb{R}^d\) is the weight vector.
We can use the notation \(\beta_k=\text{concat}(\beta_{0,k}, \beta_{1:,k})^T\in\mathbb{R}^{d+1}\).
This can be achieved if we define the density as the softmax
For \(k=1,2,\cdots,K-1\)
\[\mathbb{P}(G=k|X=x)=\frac{\exp(\beta_k^Tx)}{1+\sum_{j=1}^{K-1}\exp(\beta_j^Tx)}\]The final probability can just be defined in terms of others
\[\mathbb{P}(G=K|X=x)=\frac{1}{1+\sum_{j=1}^{K-1}\exp(\beta_j^Tx)}\]
Tip
For the sake of simplicity, we can simply use \(K\) parameters instead of \(K-1\) and use
\[\mathbb{P}(G=k|X=x)=\frac{\exp(\beta_k^Tx)}{\sum_{j=1}^{K-1}\exp(\beta_j^Tx)}\]
Note
This formulation defines a multinoulli for the output variable once we observe \(x\).
We use the notation where \(\boldsymbol{\theta}=(\beta_0,\cdots,\beta_{K-1})\) represents the param vector.
Thus, the posterior density can be expressed as
\[p_k(x)=p_{G|X}(k|x)\approx f(\boldsymbol{\theta},x)=\mathrm{softmax}(\beta_k^Tx)\]
Estimation¶
Warning
For discriminative models, we usually consider the conditional likelihood
\[\mathbb{P}(G_1=g_i,\cdots,G_N=g_N|X_1=x_1,\cdots,X_N=x_N)=\prod_{i=1}^{N}\mathbb{P}(G_i=g_i|X=x_i)=\prod_{i=1}^{N}p_G(g_i|x_i;\theta)\]We use MLE to estimate the parameters \(\theta\).
Prediction¶
Tip
Logistic Regression¶
Note
For \(|\mathcal{G}|=2\) (binary classification), \(G\sim\text{Bernoulli}(p_x(\beta))\) with \(p_G(1|x;\theta)=p_x(\beta)\) and \(p_G(2|x;\theta)=1-p_x(\beta)\) where
\(\beta=(\beta_{0,1},\beta_{1:,1})^T\) and
\(p_x(\beta)=\frac{\exp(\beta^Tx)}{1+\exp(\beta^Tx)}\) is the sigmoid function.
We introduce a dummy output variable \(y\) such that
\(y_i=1\iff g_i=1\)
\(y_i=0\iff g_i=2\)
The log likelihood in this case can be written as
\[l(\theta)=\sum_{i=1}^{N}\log(p_G(g_i|x_i;\theta))=\sum_{i=1}^{N}y_i\log(p_{x_i}(\beta))+(1-y_i)\log(1-p_{x_i}(\beta))=f(\beta)\]This is the Binary Cross Entropy (BCE) loss.
Tip
To estimate, we need to maximise the MLE.
\[\frac{\partial f}{\partial \beta}=\frac{\partial}{\partial \beta}\left(\sum_{i=1}^{N}y_i\log(\frac{\exp(\beta^Tx_i)}{1+\exp(\beta^Tx_i)})+(1-y_i)\log(\frac{1}{1+\exp(\beta^Tx_i)})\right)=\sum_{i=1}^N x_i(y_i-p_{x_i}(\beta))\]This can be rewritten in terms of matrix equations as \(\mathbf{X}^T(\mathbf{y}-\mathbf{p})\).
We can perform gradient descent, or even Newton’s method which involves computing the second derivative
\[\frac{\partial^2 f}{\mathop{\partial\beta}\mathop{\partial\beta^T}}=-\sum_{i=1}^N x_ix_i^Tp_{x_i}(\beta)(y_i-p_{x_i}(\beta))=-\mathbf{X}^T\mathbf{W}\mathbf{X}\]Here \(\mathbf{W}\) is the diagonal matrix with entries of \(p_{x_i}(\beta)(y_i-p_{x_i}(\beta))\).
Generative Models¶
Note
It follows from Bayes theorem that
\[\mathbb{P}(G=k|X=x)\propto\mathbb{P}(G=k)\times\mathbb{P}(X=x|G=k)=\pi_k\times f_k(x)\]\(\pi_k=\mathbb{P}(G=k)\) is the class prior and it parameterises a \(\mathrm{Multinoulli}(\pi_1,\cdots,\pi_k)\) over the classes.
\(f_k(x)=\mathbb{P}(X=x|G=k)\) is the conditional data-density per class \(k\).
Tip
We note that since we’re interested in the arg max, we won’t be needing to compute the normalisation constant in the denominator as that’s the same for all classes.
If we assume that the in-class data density is Gaussian, then we have LDA and QDA classifiers.
Estimation¶
Warning
For generative models, we usually consider the joint likelihood
\[\mathbb{P}(X_1=x_1,\cdots,X_N=x_N,G_1=g_i,\cdots,G_N=g_N)=\prod_{i=1}^{N}\mathbb{P}(G_i=g_i)\times\mathbb{P}(X=x_i|G_i=g_i)=\prod_{i=1}^{N}\pi_{g_i}\times f_{g_i}(x_i)\]If \(f_k\) is parametric in \(\theta\), we use MLE to estimate those parameters.
\[\hat{f}_k(x;\theta)=f_k(x;\hat{\theta}_{\text{MLE}})\]Otherwise. we resort to non-parametric density estimation methods to estimate \(\hat{f}_k(x)\).
Prediction¶
Tip
Quadratic Discriminator Analysis¶
Note
We assume the conditional data density to be Gaussian for each class
\[f_k(x)=\frac{1}{|\boldsymbol{\Sigma}_k|^{1/2}\left(2\pi\right)^{d/2}}\exp(-\frac{1}{2}(x-\mu_k)^T\boldsymbol{\Sigma}_k^{-1}(x-\mu_k))\]We note that
\[\log(\pi_k\times f_k(x))=\log(\pi_k)-\frac{1}{2}\log(|\boldsymbol{\Sigma}_k|)-\frac{d}{2}\log(2\pi)-\frac{1}{2}(x-\mu_k)^T\boldsymbol{\Sigma}_k^{-1}(x-\mu_k)\]We can define \(\delta_k(x)=\log(\pi_k)-\frac{1}{2}\log(|\boldsymbol{\Sigma}_k|)-\frac{1}{2}(x-\mu_k)^T\boldsymbol{\Sigma}_k^{-1}(x-\mu_k)\)
The decision boundary between \(k=1\) and \(k=2\) is given by the surface
\[\log\frac{\delta_1(x)}{\delta_2(x)}=\log\frac{\pi_1}{\pi_2}-\log\frac{|\boldsymbol{\Sigma}_1|}{|\boldsymbol{\Sigma}_2|}-\frac{1}{2}(x-\mu_1)^T\boldsymbol{\Sigma}_1^{-1}(x-\mu_1)+\frac{1}{2}(x-\mu_2)^T\boldsymbol{\Sigma}_2^{-1}(x-\mu_2)=0\]We note that this is quadratic in \(x\).
Linear Discriminator Analysis¶
Note
If we model the conditional density in a way such that they all share the covariance (\(\boldsymbol{\Sigma}\)), then the equation simplifies to a linear one in \(x\) as the quadratic term \(x^T\boldsymbol{\Sigma}^{-1}x\) cancels.
\[x^T\boldsymbol{\Sigma}^{-1}x-\mu_1^T\boldsymbol{\Sigma}^{-1}x-x^T\boldsymbol{\Sigma}^{-1}\mu_1+\mu_1^T\boldsymbol{\Sigma}^{-1}\mu_1-x^T\boldsymbol{\Sigma}^{-1}x+\mu_2^T\boldsymbol{\Sigma}^{-1}x+x^T\boldsymbol{\Sigma}^{-1}\mu_2-\mu_2^T\boldsymbol{\Sigma}^{-1}\mu_2=2x^T\boldsymbol{\Sigma}^{-1}(\mu_2-\mu_1)+\left(\mu_1^T\boldsymbol{\Sigma}^{-1}\mu_1-\mu_2^T\boldsymbol{\Sigma}^{-1}\mu_2\right)\]The decision boundary between \(k=1\) and \(k=2\) is given by the hyperplane
\[\log\frac{\delta_1(x)}{\delta_2(x)}=\log\frac{\pi_1}{\pi_2}+x^T\boldsymbol{\Sigma}^{-1}(\mu_1-\mu_2)-\frac{1}{2}(\mu_1-\mu_2)^T\boldsymbol{\Sigma}^{-1}(\mu_1-\mu_2)=0\]We note that this is linear in \(x\).
Tip
Let \(N_k=\sum_{i=1}^N\mathbb{I}_{g_i=k}\) be the number of labels belonging to a class \(k\).
We estimate the priors using MLE
\[\hat{\pi}_k=\frac{N_k}{N}\]The conditional density parameters are also estimated using MLE.
Mean
\[\hat{\mu}_k=\frac{\sum_{g_i=k}x_i}{N_k}\]Covariance
\[\hat{\boldsymbol{\Sigma}}=\frac{1}{N-K}\sum_{k=1}^K\sum_{g_i=k} (x_i-\hat{\mu}_k)(x_i-\hat{\mu}_k)^T\]
Regularised Discriminator Analysis¶
Note
As a compromise between QDA and LDA, we can decompose each of the class-covariance matrix into a pooled (shared) matrix and a class-specific matrix.
\[\hat{\boldsymbol{\Sigma}}_k(\alpha)=\alpha\hat{\boldsymbol{\Sigma}}_k+(1-\alpha)\hat{\boldsymbol{\Sigma}}\]The shared-covariance matrix can be further decomposed into a diagonal one (uncorrelated covariates) and one which contains the correlations.
\[\hat{\boldsymbol{\Sigma}}(\gamma)=\gamma\hat{\boldsymbol{\Sigma}}+(1-\gamma)\hat{\sigma}^2\mathbf{I}\]Both these versions form a regularised version of the QDA with \(\alpha\) and \(\gamma\) as hyperparameters.
Comparison Between LDA and Logistic Regression¶
Tip
LDA and LR performs similar and they both evaluate to linear logits. But the way we estimate the parameters of this linear model separates them.
LDA assumes additional structure for the marginal data distribution because of Gaussian nature of the class-conditional density.
On the other hand, LR assumes no structure for the marginal data distribution. We can think of it as if we’re free to fit any non-parametric density for the marginal, such as empirical distribution.
Since LDA makes additional assumption about the sturcture, we can estimate them with lower variance if the underlying data density indeed follows a Gaussian.
However, since outliers play a significant role in how the covariance is estimated, it is not robust to outliers/mislabelled examples.
If the data is perfectly separable by a hyperplane, the MLE formulation for LR is ill-defined.
Hyperplane Classifiers¶
Here, instead of relying on a discriminator function, we directly model the separation boundary as a piece-wise hyperplane between classes.
Note
For a hyperplane \(f(\mathbf{x})=\beta_0+\boldsymbol{\beta}^T\mathbf{x}\), we consider the affine set
\[L=\{\mathbf{x}\mathop{|}f(\mathbf{x})=0\}\]If \(\mathbf{x}\in\mathbb{R}^2\), this set traces a line on the \(XY\) plane.
Warning
The co-efficient vector \(\boldsymbol{\beta}\) is orthogonal to this line.
Proof: If \(\mathbf{x_1}\) and \(\mathbf{x_2}\) are two point in \(L\), then the vector joining the two is given by
\[\Delta\mathbf{x}=\mathbf{x_2}-\mathbf{x_1}\]Taking dot product with the co-efficient vector
\[\boldsymbol{\beta}^T\Delta\mathbf{x}=\boldsymbol{\beta}^T(\mathbf{x_2}-\mathbf{x_1})=-\beta_0+\beta_0=0\]The normalised vector is written as \(\boldsymbol{\beta}^*=\frac{1}{||\boldsymbol{\beta}||}\boldsymbol{\beta}\).
The distance of the intersect point from origin along the co-efficient vector is the intercept.
Proof: We can take any point on \(L\) and project onto the co-efficient vector to find the distance, which evaluates to \(-\beta_0\)
The function value at any point is proportional to the signed distance of that point from the set L
Proof: We can take any point \(\mathbf{x}'\in\mathbb{R}^2\) and any point in \(L\), \(\mathbf{x}_0\). The signed distance of \(\mathbf{x}'\) from \(L\) is given by
\[\delta(\mathbf{x}',L)=\boldsymbol{\beta}^*(\mathbf{x}'-\mathbf{x_0})=\frac{1}{||\boldsymbol{\beta}||}(\boldsymbol{\beta}^T\mathbf{x}'-\boldsymbol{\beta}^T\mathbf{x}_0)=\frac{1}{||\boldsymbol{\beta}||}(\boldsymbol{\beta}^T\mathbf{x}'+\beta_0)=\frac{1}{||f'||}f(\mathbf{x}')\]
Tip
Along the direction \(\boldsymbol{\beta}\), the function value increases and it decreases on the opposite direction.
If the intercept is positive, the hyperplane intersects with the \(XY\) plane in the positive orthant.