The Principle of LDA
Given data $\mathbf{X}\in \mathbb{R}^{N\times p}$ together with $\mathbf{y}\in \{0,1\}$, we form the input–output training pairs $D=\{(\mathbf{x}_1,\mathbf{y}_1),...,(\mathbf{x}_N,\mathbf{y}_N)\}$. The training set $D$ means that the whole training set contains $N$ samples, each of dimension $p$, and that every sample belongs to one of only two classes, corresponding to the output $\mathbf{y}$ taking the value 0 or 1.
Assume first that the first class, $\mathbf{x}_{c1}$, contains $|\mathbf{x}_{c1}|=N_1$ samples and the second class contains $|\mathbf{x}_{c2}|=N_2$ samples, with $N_1+N_2=N$. The means and variances of the two classes can be written as:
$$ \bar{\mathbf{x_1}}=\frac{1}{N_1}\sum_{i=1}^{N_1}\mathbf{x}_i $$$$ \bar{\mathbf{x_2}}=\frac{1}{N_2}\sum_{i=1}^{N_2}\mathbf{x}_i $$$$ \mathbf{S}_{x1}=\frac{1}{N_1}\sum_{i=1}^{N_1}(\mathbf{x}_i-\bar{\mathbf{x_1}})(\mathbf{x}_i-\bar{\mathbf{x_1}})^T $$$$ \mathbf{S}_{x2}=\frac{1}{N_2}\sum_{i=1}^{N_2}(\mathbf{x}_i-\bar{\mathbf{x_2}})(\mathbf{x}_i-\bar{\mathbf{x_2}})^T $$Dimensionality reduction of the input $p$-dimensional features is given by $\mathbf{z}_i=\mathbf{W}^T\mathbf{x}_i$, where $\mathbf{z}$ denotes the data after reduction. The means and variances of the reduced data are then:
$$ \bar{\mathbf{z_1}}=\frac{1}{N_1}\sum_{i=1}^{N_1}\mathbf{W}^T\mathbf{x}_i $$$$ \mathbf{S}_1=\frac{1}{N_1}\sum_{i=1}^{N_1}(\mathbf{W}^T\mathbf{x}_i-\bar{\mathbf{z_1}})(\mathbf{W}^T\mathbf{x}_i-\bar{\mathbf{z_1}})^T $$$$ \bar{\mathbf{z_2}}=\frac{1}{N_2}\sum_{i=1}^{N_2}\mathbf{W}^T\mathbf{x}_i $$$$ \mathbf{S}_2=\frac{1}{N_2}\sum_{i=1}^{N_2}(\mathbf{W}^T\mathbf{x}_i-\bar{\mathbf{z_2}})(\mathbf{W}^T\mathbf{x}_i-\bar{\mathbf{z_2}})^T $$
The figure above is a schematic of LDA. Its ultimate goal is to gather samples of the same class as tightly as possible and to separate the two classes as much as possible. First, making samples of the same class cluster together is equivalent to making the variances of the two classes as small as possible, $\min \mathbf{S}_1+\mathbf{S}_2$. Second, making samples from different classes as far apart as possible can be achieved by making the distance between the class centers—that is, the means—as large as possible, $\max|| \bar{\mathbf{z}_1}-\bar{\mathbf{z}_2}||_F^2$.
The objective function of LDA can finally be written as:
Simplifying the numerator first gives:
$$ \begin{aligned} || \bar{\mathbf{z}_1}-\bar{\mathbf{z}_2}||_F^2&=||\frac{1}{N_1}\sum_{x=1}^{N_1}\mathbf{W}^T\mathbf{x}_i-\frac{1}{N_2}\sum_{x=1}^{N_2}\mathbf{W}^T\mathbf{x}_i||_F^2\\ &=||\mathbf{W}^T(\frac{1}{N_1}\sum_{t=1}^{N_1}\mathbf{x}_i-\frac{1}{N_2}\sum_{t=1}^{N_2}\mathbf{x}_i)||_F^2\\ &=||\mathbf{W}^T(\bar{\mathbf{x_1}}-\bar{\mathbf{x_2}})||_F^2\\ &=\mathbf{W}^T(\bar{\mathbf{x_1}}-\bar{\mathbf{x_2}})(\bar{\mathbf{x_1}}-\bar{\mathbf{x_2}})^T\mathbf{W} \end{aligned} $$Simplifying the denominator gives:
$$ \begin{aligned} \mathbf{S_1+S_2}&=\frac{1}{N_1}\sum_{i=1}^{N_1}(\mathbf{W}^T\mathbf{x}_i-\bar{\mathbf{z_1}})(\mathbf{W}^T\mathbf{x}_i-\bar{\mathbf{z_1}})^T+\frac{1}{N_2}\sum_{i=1}^{N_2}(\mathbf{W}^T\mathbf{x}_i-\bar{\mathbf{z_2}})(\mathbf{W}^T\mathbf{x}_i-\bar{\mathbf{z_2}})^T\\ &=\frac{1}{N_1}\sum_{i=1}^{N_1}(\mathbf{W}^T\mathbf{x}_i-\frac{1}{N_1}\sum_{i=1}^{N_1}\mathbf{W}^T\mathbf{x}_i)(\mathbf{W}^T\mathbf{x}_i-\frac{1}{N_1}\sum_{i=1}^{N_1}\mathbf{W}^T\mathbf{x}_i)^T\\ &+\frac{1}{N_2}\sum_{i=1}^{N_2}(\mathbf{W}^T\mathbf{x}_i-\frac{1}{N_2}\sum_{i=1}^{N_2}\mathbf{W}^T\mathbf{x}_i)(\mathbf{W}^T\mathbf{x}_i-\frac{1}{N_2}\sum_{i=1}^{N_2}\mathbf{W}^T\mathbf{x}_i)^T\\ &=\mathbf{W}^T\frac{1}{N_1}\sum_{i=1}^{N_1}(\mathbf{x}_i-\frac{1}{N_1}\sum_{i=1}^{N_1}\mathbf{x}_i)(\mathbf{x}_i-\frac{1}{N_1}\sum_{i=1}^{N_1}\mathbf{x}_i)^T\mathbf{W}\\ &=\mathbf{W}^T\frac{1}{N_2}\sum_{i=1}^{N_2}(\mathbf{x}_i-\frac{1}{N_2}\sum_{i=1}^{N_2}\mathbf{x}_i)(\mathbf{x}_i-\frac{1}{N_2}\sum_{i=1}^{N_2}\mathbf{x}_i)^T\mathbf{W}\\ &=\mathbf{W}^T\frac{1}{N_1}\sum_{i=1}^{N_1}(\mathbf{x}_i-\bar{\mathbf{x}_1})(\mathbf{x}_i-\bar{\mathbf{x}_1})^T\mathbf{W}+\mathbf{W}^T\frac{1}{N_2}\sum_{i=1}^{N_2}(\mathbf{x}_i-\bar{\mathbf{x}_2})(\mathbf{x}_i-\bar{\mathbf{x}_2})^T\mathbf{W}\\ &=\mathbf{W}^T(\mathbf{S}_{x1}-\mathbf{S}_{x2})\mathbf{W} \end{aligned} $$The objective function of LDA can finally be written as:
$$ L = \frac{\mathbf{W}^T(\bar{\mathbf{x_1}}-\bar{\mathbf{x_2}})(\bar{\mathbf{x_1}}-\bar{\mathbf{x_2}})^T\mathbf{W}}{\mathbf{W}^T(\mathbf{S}_{x1}-\mathbf{S}_{x2})\mathbf{W}} $$Setting $\mathbf{S}_{w}= (\bar{\mathbf{x_1}}-\bar{\mathbf{x_2}})(\bar{\mathbf{x_1}}-\bar{\mathbf{x_2}})^T$ and $\mathbf{S}_{b}= \mathbf{S}_{x1}-\mathbf{S}_{x2}$ gives:
$$ L = \frac{\mathbf{W}^T\mathbf{S}_w\mathbf{W}}{\mathbf{W}^T\mathbf{S}_b\mathbf{W}} $$Solving the objective function for $\mathbf{W}$ yields the final solution.
Algorithm Implementation
| |
