Linear Discriminant Analysis -1

Computing classification means computing class posterior probabilities \(Pr(G|X)\) - that is probability that class is G given input X. If \(f_k(x)\) is the class conditional density of \(X\) in class \(Gk\) and if \(\pi_k\) is prior probability, then Bayes theorem gives, \[\begin{equation} Pr(G=k|X=x) = \frac{f_k(x)\pi_k}{\sum_{l=1}^K f_l(x)\pi_l} \end{equation}\]
Depending on the models for class density, different techniques emerge.

* linear and quadratic discrimnant analysis use Gaussian densities
* Mixture of Gaussians lead to non-linear decision boundaries.
* Navie Bayes models assume that each class density is product of marginal densities.

Derivations:
Suppose that each class density is modelled as multivariate Gaussian. \[\begin{equation} f_k(x)=\frac{1}{(2\pi)^{p/2} |\Sigma_k|^{1/2}} e^{-\frac{1}{2}(x-\mu_k)^T\Sigma_k^{-1}(x-\mu_k)} \end{equation}\] Clear that \[\begin{equation} Pr(G=k|X=x) = \frac{f_k(x)\pi_k}{\sum_{l=1}^K f_l(x)\pi_l} \\ Pr(G=l|X=x) = \frac{f_l(x)\pi_l}{\sum_{p=1}^K f_p(x)\pi_p} \\ \frac{Pr(G=k|X=x)}{Pr(G=l|X=x)} = \frac{f_k(x)\pi_k}{f_l(x)\pi_l} \\ log\left(\frac{Pr(G=k|X=x)}{Pr(G=l|X=x)} \right) = log\frac{f_k(x)}{f_l(x)}+log\frac{\pi_k(x)}{\pi_l(x)} \end{equation}\] Now expression \(\frac{f_k(x)}{f_l(x)}\) can be simplified as follows. Note \(\Sigma\) is assumed to be same for all the classes. \[\begin{equation} log\left(\frac{f_k(x)}{f_l(x)}\right) = \left[ -\frac{1}{2}(x-\mu_k)^T\Sigma^{-1}(x-\mu_k)+\frac{1}{2}(x-\mu_l)^T\Sigma^{-1}(x-\mu_l)\right] \end{equation}\] And \[\begin{equation} = -\frac{1}{2} [x^T\Sigma^{-1}x-x^T\Sigma^{-1}\mu_k-\mu_k^T\Sigma^{-1}x+\mu_k^T\Sigma^{-1}\mu_k - x^T\Sigma^{-1}x + x^T\Sigma^{-1}\mu_k + \mu_l \Sigma^{-1} x - \mu_l^T\Sigma^{-1}\mu_l ] \end{equation}\] Next \[\begin{equation} = \frac{1}{2} [-x^T\Sigma^{-1}x + x^T\Sigma^{-1}\mu_k + \mu_k^T\Sigma^{-1}x -\mu_k^T\Sigma^{-1}\mu_k+x^T\Sigma^{-1}x-x^T\Sigma^{-1}\mu_l-\mu_l^T\Sigma^{-1}x + \mu_l^T\Sigma^{-1}\mu_l ] \end{equation}\]
Before simplying, we should note the following:

• Since \(\Sigma\) is a covariance matrix and since covariance between \(i\) and \(j\) is same as \(j\) and \(i\), then \(\Sigma^T=\Sigma = \Sigma^{-1}\).
• The mean matrices \(\mu_k\) for class \(k\) and \(\mu_l\) for class \(l\) are \(p \times 1\) matrix.
• Terms such as \(\mu_k \Sigma^{-1}\mu_l\) have dimensions \(1\times p * p \times p * p \times 1=1\times 1\) or scalars aka reals.

Second term and fifth term with leading \(x^T\) can be simplified as \[\begin{equation} \frac{1}{2}x^T\Sigma^{-1}(\mu_k-\mu_l) \end{equation}\] Collecting third and seventh terms \(x\) at end. \[\begin{equation} \left[\frac{1}{2}(\mu_k^T - \mu_l^T)\Sigma^{-1}x\right]^T = \frac{1}{2}x^T\Sigma^{-1}(\mu_k-\mu_l) \end{equation}\] The remaining terms are \[\begin{equation*} -\frac{1}{2}\mu_k^l\Sigma^{-1}\mu_l+\frac{1}{2}\mu_l^T\Sigma^{-1}\mu_l+\frac{1}{2}\mu_k^T\Sigma^{-1}\mu_l-\frac{1}{2}(\mu_k^T\Sigma^{-1}\mu_l)^T \\ = \frac{1}{2}(\mu_k+\mu_l)^T\Sigma^{-1}(\mu_k-\mu_l) \end{equation*}\] Combining all those simplification, \[\begin{equation*} log\left(\frac{Pr(G=k|X=x)}{Pr(G=l|X=x)}\right) = log\left(\frac{\pi_k}{\pi_l}\right) \\ -\frac{1}{2}(\mu_k+\mu_l)^T\Sigma^{-1}(\mu_k-\mu_l)+x^T\Sigma^{-1}(\mu_k-\mu_l) \end{equation*}\] At the line that divides class \(k,l\) has probabilities \(Pr(G=k|X=x)=Pr(G=l|X=x)\) \[\begin{equation*} log(1)=0=log(\pi_k)-log(\pi_l) - \frac{1}{2}\mu_k^T\Sigma^{-1}\mu_k+x^T\Sigma^{-1}\mu_k + \frac{1}{2}\mu_l^T\Sigma^{-1}\mu_l-x^T\Sigma^{-1}\mu_l \end{equation*}\] From here, the linear discriminant can be written as \[\begin{equation} \delta_k=log(\pi_k)-\frac{1}{2}\mu_k^T\Sigma^{-1}\mu_k+x^T\Sigma^{-1}\mu_k \end{equation}\]