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, $$Pr(G=k|X=x)=\frac{f_k(x){\pi }_k}{\sum _{l=1}^K{f}_l(x){\pi }_l}$$
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. $$f_k(x)=\frac{1}{(2\pi {)}^{p/2}|{\mathrm{\Sigma }}_k{|}^{1/2}}{e}^{-\frac{1}{2}(x-{\mu }_k{)}^T{\mathrm{\Sigma }}_k^{-1}(x-{\mu }_k)}$$ Clear that $$\begin{gathered} 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{gathered}$$ Now expression $\frac{f_k(x)}{f_l(x)}$ can be simplified as follows. Note $\mathrm{\Sigma }$ is assumed to be same for all the classes. $$log\left(\frac{f_k(x)}{f_l(x)}\right)=[-\frac{1}{2}(x-{\mu }_k{)}^T{\mathrm{\Sigma }}^{-1}(x-{\mu }_k)+\frac{1}{2}(x-{\mu }_l{)}^T{\mathrm{\Sigma }}^{-1}(x-{\mu }_l)]$$ And $$=-\frac{1}{2}[x^T{\mathrm{\Sigma }}^{-1}x-x^T{\mathrm{\Sigma }}^{-1}{\mu }_k-{\mu }_k^T{\mathrm{\Sigma }}^{-1}x+{\mu }_k^T{\mathrm{\Sigma }}^{-1}{\mu }_k-x^T{\mathrm{\Sigma }}^{-1}x+x^T{\mathrm{\Sigma }}^{-1}{\mu }_k+{\mu }_l{\mathrm{\Sigma }}^{-1}x-{\mu }_l^T{\mathrm{\Sigma }}^{-1}{\mu }_l]$$ Next $$=\frac{1}{2}[-x^T{\mathrm{\Sigma }}^{-1}x+x^T{\mathrm{\Sigma }}^{-1}{\mu }_k+{\mu }_k^T{\mathrm{\Sigma }}^{-1}x-{\mu }_k^T{\mathrm{\Sigma }}^{-1}{\mu }_k+x^T{\mathrm{\Sigma }}^{-1}x-x^T{\mathrm{\Sigma }}^{-1}{\mu }_l-{\mu }_l^T{\mathrm{\Sigma }}^{-1}x+{\mu }_l^T{\mathrm{\Sigma }}^{-1}{\mu }_l]$$
Before simplying, we should note the following:

• Since $\mathrm{\Sigma }$ is a covariance matrix and since covariance between $i$ and $j$ is same as $j$ and $i$, then ${\mathrm{\Sigma }}^T=\mathrm{\Sigma }={\mathrm{\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{\mathrm{\Sigma }}^{-1}{\mu }_l$ have dimensions $1\times p\ast p\times p\ast p\times 1=1\times 1$ or scalars aka reals.

Second term and fifth term with leading $x^T$ can be simplified as $$\frac{1}{2}{x}^T{\mathrm{\Sigma }}^{-1}({\mu }_k-{\mu }_l)$$ Collecting third and seventh terms $x$ at end. $${[\frac{1}{2}({\mu }_k^T-{\mu }_l^T){\mathrm{\Sigma }}^{-1}x]}^T=\frac{1}{2}{x}^T{\mathrm{\Sigma }}^{-1}({\mu }_k-{\mu }_l)$$ The remaining terms are $$\begin{gathered} -\frac{1}{2}{\mu }_k^l{\mathrm{\Sigma }}^{-1}{\mu }_l+\frac{1}{2}{\mu }_l^T{\mathrm{\Sigma }}^{-1}{\mu }_l+\frac{1}{2}{\mu }_k^T{\mathrm{\Sigma }}^{-1}{\mu }_l-\frac{1}{2}({\mu }_k^T{\mathrm{\Sigma }}^{-1}{\mu }_l{)}^T \\ =\frac{1}{2}({\mu }_k+{\mu }_l{)}^T{\mathrm{\Sigma }}^{-1}({\mu }_k-{\mu }_l) \end{gathered}$$ Combining all those simplification, $$\begin{gathered} 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{\mathrm{\Sigma }}^{-1}({\mu }_k-{\mu }_l)+x^T{\mathrm{\Sigma }}^{-1}({\mu }_k-{\mu }_l) \end{gathered}$$ At the line that divides class $k,l$ has probabilities $Pr(G=k|X=x)=Pr(G=l|X=x)$ $$log(1)=0=log({\pi }_k)-log({\pi }_l)-\frac{1}{2}{\mu }_k^T{\mathrm{\Sigma }}^{-1}{\mu }_k+x^T{\mathrm{\Sigma }}^{-1}{\mu }_k+\frac{1}{2}{\mu }_l^T{\mathrm{\Sigma }}^{-1}{\mu }_l-x^T{\mathrm{\Sigma }}^{-1}{\mu }_l$$ From here, the linear discriminant can be written as $${\delta }_k=log({\pi }_k)-\frac{1}{2}{\mu }_k^T{\mathrm{\Sigma }}^{-1}{\mu }_k+x^T{\mathrm{\Sigma }}^{-1}{\mu }_k$$

Sets of Measure Zero.

Heard the saying - What happens in Las Vegas, stays in Las Vegas? Sets of measure zero are kind of like that.

For example, say $f(x),g(x)$ are functions that are equal to each other in measurable space $E$, except on a subset $N$. Say a given measure on ``disagreeable'' space $N$ is equal to zero. Now $N$ is like Las Vegas and we are given license to forget about what happens in this space $N$ and assert that $f(x)=g(x)$ a.e where a.e stands for almost everwhere. To be more precise (just to prevent extra point from being leaked out of your exam paper!), we need to state $f(x)=g(x)$ a.e[$\mu$]. That is we need to specify which measure.

Mathematically, $$\mu \{x:f(x)\ne g(x)\}=0$$

where $x \in N$. The above criteria specifies the points of $N$. Here $f$ ~ $g$ and it is not too difficult to prove that this is an equivalence relation.

Reflexive property: Clearly $f$ ~ $f$. The disagreeable set $N$ in this case is a null set and measure of null set is $0$. $f=f$ on the whole set. Symmetric: Clearly $f$ ~ $g$ also means that set of disagreeable space remains same when we switch $f$ to the right. Reflexive: Say $f$ ~ $g$ and let $N_1$ be the disagreeable set. Say $g$ ~ $h$ and let $N_2$ be the disagreeable set, then $N_1 \cup N_2$ where $f,g,h$ are not equal to each other. Hence $f$ ~ $h$.

Note all the above statements were made based on a property that $f=g$. Generally, we don't have to be specific about a property. Above assertions and proofs hold in a more abstract sense, that is for any property $P$.

R&C - Lebesgue's Dominated Convergence Theorem

Dominated Conv Theorem

If $f\in \mathcal{L}(\mu )$, then $$\left|{\int }_{X}fd\mu \right|\le {\int }_x|f|d\mu$$

Proof uses the previously proven identity -

If $f$ is a complex measurable function on $X$, there is a complex measurable function $\alpha$ on $X$ such that $|\alpha |=1$ and $f=\alpha |f|$. This is an extension of property of complex numbers.

Start off by setting $z={\int }_{X}fd\mu$. Then there is another complex number $\alpha$ such that $|\alpha |=1$ and $\alpha z=|z|$.

Let $u$ be real part of $\alpha f$. Then, $u\le |\alpha f|=|f|$. Hence,

$$\begin{array}{r}\left|{\int }_{X}fd\mu \right|=|z|=\alpha z=\alpha {\int }_{X}fd\mu \\ ={\int }_X\alpha fd\mu ={\int }_{X}ud\mu \le {\int }_X|f|d\mu \end{array}$$ Suppose $\{f_n\}$ is a sequence of complex measurable functions on $X$ such that $$f(x)=li{m}_{n\to \mathrm{\infty }}{f}_n(x)$$ exists for every $x\in X$. If there is a function $g\in {\mathcal{L}}^{\mathcal{1}}\mathcal{(}\mu \mathcal{)}$ such that $$|f_n(x)|\le g(x)(n=1,2,\cdots |x\in )$$ then $f\in {\mathcal{L}}^{\mathcal{1}}\mathcal{(}\mu \mathcal{)}$, $$li{m}_{n\to \mathrm{\infty }}{\int }_X|f_n-f|d\mu =0$$ and $$li{m}_{n\to \mathrm{\infty }}{\int }_X{f}_{n}d\mu ={\int }_{X}fd\mu$$

Clear that $|f|\le g$. Since $f_n$ are measurable, the limit $f$ is measurable, $f\in {\mathcal{L}}^{\mathcal{1}}\mathcal{(}\mu \mathcal{)}$. $$\begin{array}{r}|f-f_n|\le |f|+|f_n|\le 2g\end{array}$$ This means, $2g-|f_n-f|$ is a sequence of functions whose range is in $[0,\mathrm{\infty }]$. Hence, precondition to satisfy Fatou’s lemma is satisfied. This yield $$\begin{array}{r}{\int }_{X}2gd\mu \le li{m}_{n\to \mathrm{\infty }}inf{\int }_X(2g-|f_n-f|)d\mu \\ ={\int }_{X}2gd\mu +li{m}_{n\to \mathrm{\infty }}inf(-{\int }_X|f_n-f|d\mu )\\ ={\int }_{X}2gd\mu -limsu{p}_{n\to \mathrm{\infty }}{\int }_X|f_n-f|d\mu \end{array}$$ Taking advantage of finiteness of $\int 2gd\mu$, $$\begin{array}{r}limsu{p}_{n\to \mathrm{\infty }}{\int }_X|f_n-f|d\mu \le 0\end{array}$$ If sequence of nonnegative real numbers fails to converge to $0$, then its upper limit is positive. Then above equation implies $$\begin{array}{r}li{m}_{n\to \mathrm{\infty }}{\int }_X|f_n-f|d\mu =0.\end{array}$$ Hence, $$\begin{array}{r}li{m}_{n\to \mathrm{\infty }}{\int }_X{f}_{n}d\mu ={\int }_{X}fd\mu \end{array}$$