Question

1. 线性判别分析Linear Discriminant Analysis:LDA 基本思想：

   • 训练时：给定训练样本集，设法将样例投影到某一条直线上，使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离。要学习的就是这样的一条直线。
   • 预测时：对新样本进行分类时，将其投影到学到的直线上，在根据投影点的位置来确定新样本的类别。

4.1 二分类模型

1. 考虑二类分类问题。设数据集为： $ MathJax-Element-155 $ 。

4.1.1 投影

1. 设 $ MathJax-Element-156 $ 表示类别为 0 的样例的集合，这些样例的均值向量为 $ MathJax-Element-157 $ ，这些样例的特征之间协方差矩阵为 $ MathJax-Element-158 $ （协方差矩阵大小为 $ MathJax-Element-205 $ ）。

   设 $ MathJax-Element-160 $ 表示类别为 1 的样例的集合，这些样例的均值向量为 $ MathJax-Element-161 $ ，这些样例的特征之间协方差矩阵为 $ MathJax-Element-162 $ （协方差矩阵大小为 $ MathJax-Element-205 $ ）

2. 假定直线为： $ MathJax-Element-164 $ ，其中 $ MathJax-Element-165 $ 。

   这里省略了常量 $ MathJax-Element-166 $ ，因为考察的是样本点在直线上的投影，总可以平行移动直线到原点而保持投影不变，此时 $ MathJax-Element-167 $ 。

   将数据投影到直线上，则：

   • 两类样本的中心在直线上的投影分别为 $ MathJax-Element-168 $ 和 $ MathJax-Element-169 $
   • 两类样本投影的方差分别为 $ MathJax-Element-170 $ 和 $ MathJax-Element-171 $

   由于直线是一维空间，因此上面四个值均为实数

   

3. 根据线性判别分析的思想：

   • 要使得同类样例的投影点尽可能接近，则可以使同类样例投影点的方差尽可能小，即 $ MathJax-Element-172 $ 尽可能小

   • 要使异类样例的投影点尽可能远，则可以使异类样例的中心的投影点尽可能远，即 $ MathJax-Element-173 $ 尽可能大

   • 同时考虑两者，则得到最大化的目标：

     $ J=\frac{||\mathbf{\vec w}^{T} \vec \mu_0-\mathbf{\vec w}^{T} \vec \mu_1||_2^{2}}{\mathbf{\vec w}^{T} \Sigma_0 \mathbf{\vec w}+\mathbf{\vec w}^{T} \Sigma_1 \mathbf{\vec w}}=\frac{\mathbf{\vec w}^{T}(\vec \mu_0-\vec \mu_1)(\vec \mu_0-\vec \mu_1)^{T}\mathbf{\vec w}}{\mathbf{\vec w}^{T}(\Sigma_0+\Sigma_1)\mathbf{\vec w}} $

     .

4.1.2 求解

1. 定义类内散度矩阵和类间散度矩阵：

   • 类内散度矩阵 within-class scatter matrix：

     $ \mathbf S_{w}=\Sigma_0+\Sigma_1=\sum_{\mathbf{\vec x}\in \mathbb D_0}(\mathbf{\vec x}-\vec\mu_0)(\mathbf{\vec x}-\vec\mu_0)^{T} +\sum_{\mathbf{\vec x}\in \mathbb D_1}(\mathbf{\vec x}-\vec\mu_1)(\mathbf{\vec x}-\vec\mu_1)^{T} $

     它是每个类的散度矩阵之和。

   • 类间散度矩阵 between-class scatter matrix： $ MathJax-Element-174 $ 。

     它是向量 $ MathJax-Element-175 $ 与它自身的外积。

2. 利用类内散度矩阵和类间散度矩阵，线性判别分析的最优化目标为：

   $ J=\frac{\mathbf{\vec w}^{T}\mathbf S_b \mathbf{\vec w}}{\mathbf{\vec w}^{T}\mathbf S_w \mathbf{\vec w}} $

   $ MathJax-Element-176 $ 也称作 $ MathJax-Element-177 $ 与 $ MathJax-Element-192 $ 的广义瑞利商 。

3. 现在求解最优化问题：

   $ \mathbf{\vec w}^{*}=\arg\max_{\mathbf{\vec w}}\frac{\mathbf{\vec w}^{T}\mathbf S_b \mathbf{\vec w}}{\mathbf{\vec w}^{T}\mathbf S_w \mathbf{\vec w}} $
   • 考虑到分子与分母都是关于 $ MathJax-Element-181 $ 的二次项，因此上式的解与 $ MathJax-Element-181 $ 的长度无关，只与 $ MathJax-Element-181 $ 的方向有关。令 $ MathJax-Element-182 $ ，则最优化问题改写为：
   $ \mathbf{\vec w}^{*}=\arg\min_{\mathbf{\vec w}} -\mathbf{\vec w}^{T}\mathbf S_b \mathbf{\vec w}\\ s.t. \mathbf{\vec w}^{T}\mathbf S_w \mathbf{\vec w}=1 $

   • 应用拉格朗日乘子法，上式等价于 $ MathJax-Element-183 $

     • 令 $ MathJax-Element-184 $ ，其中 $ MathJax-Element-185 $ 为实数。则 $ MathJax-Element-186 $ 。代入上式有：

       $ \mathbf S_b \mathbf{\vec w}=\lambda_{\mathbf{\vec w}}(\vec \mu_0-\vec \mu_1)=\lambda \mathbf S_w \mathbf{\vec w} $

     • 由于与 $ MathJax-Element-187 $ 的长度无关，可以令 $ MathJax-Element-188 $ 则有：

       $ (\vec \mu_0-\vec \mu_1)= \mathbf S_w \mathbf{\vec w}\Longrightarrow \mathbf{\vec w}=\mathbf S_w ^{-1}(\vec \mu_0-\vec \mu_1) $

     • 考虑数值解的稳定性，在实践中通常是对 $ MathJax-Element-192 $ 进行奇异值分解： $ MathJax-Element-190 $ ，其中 $ MathJax-Element-191 $ 为实对角矩阵，对角线上的元素为 $ MathJax-Element-192 $ 的奇异值 ； $ MathJax-Element-193 $ 均为酉矩阵，它们的列向量分别构成了标准正交基。

       然后 $ MathJax-Element-194 $ 。

4.2 多分类模型

1. 可以将线性判别分析推广到多分类任务中。

2. 假定存在 $ MathJax-Element-195 $ 个类，属于第 $ MathJax-Element-213 $ 个类的样本的集合为 $ MathJax-Element-208 $ ， $ MathJax-Element-208 $ 中的样例数为 $ MathJax-Element-199 $ 。其中： $ MathJax-Element-200 $ ， $ MathJax-Element-201 $ 为样本总数。

   • 定义类别 $ MathJax-Element-213 $ 的均值向量为：所有该类别样本的均值：

     $ \vec \mu_i=(\mu_{i,1},\mu_{i,2},\cdots,\mu_{i,n})^{T}=\frac {1}{m_i}\sum_{\mathbf{\vec x}_i \in \mathbb D_i} \mathbf{\vec x}_i $

     类别 $ MathJax-Element-213 $ 的样例的特征之间协方差矩阵为 $ MathJax-Element-209 $ （协方差矩阵大小为 $ MathJax-Element-205 $ ）。

   • 定义 $ MathJax-Element-206 $ 是所有样例的均值向量。

3. 定义各类别的类内散度矩阵、总的类内散度矩阵、总的类间散度矩阵：

   • 定义类别 $ MathJax-Element-213 $ 的类内散度矩阵为：

     $ \mathbf S_{wi}= \sum_{\mathbf{\vec x}\in \mathbb D_i}(\mathbf{\vec x}-\vec\mu_i)(\mathbf{\vec x}-\vec\mu_i)^{T} $

     它实际上就等于样本集 $ MathJax-Element-208 $ 的协方差矩阵 $ MathJax-Element-209 $ ， 刻画了同类样例投影点的方差。

   • 定义总的类内散度矩阵为： $ MathJax-Element-210 $ 。

     它 刻画了所有类别的同类样例投影点的方差。

   • 定义总的类间散度矩阵为： $ MathJax-Element-211 $ 。

     它刻画了异类样例的中心的投影点的相互距离。

     注意： $ MathJax-Element-212 $ 也是一个协方差矩阵，它刻画的是第 $ MathJax-Element-213 $ 类与总体之间的关系。

     • 由于这里有不止两个中心点，因此不能简单的套用二分类线性判别分析的做法。

       这里用每一类样本集的中心点与总的中心点的距离作为度量。

     • 考虑到每一类样本集的大小可能不同（密度分布不均），对这个距离施加权重，权重为每类样本集的大小。

4. 根据线性判别分析的思想，设 $ MathJax-Element-214 $ 是投影矩阵。经过推导可以得到最大化的目标：

   $ J=\frac{tr(\mathbf W^{T}\mathbf S_b\mathbf W)}{tr(\mathbf W^{T}\mathbf S_w\mathbf W)} $

   其中 $ MathJax-Element-215 $ 表示矩阵的迹。

   • 一个矩阵的迹是矩阵对角线的元素之和，它是一个矩阵不变量，也等于所有特征值之和。
   • 还有一个常用的矩阵不变量就是矩阵的行列式，它等于矩阵的所有特征值之积。

5. 与二分类线性判别分析不同，在多分类线性判别分析中投影方向是多维的，因此使用投影矩阵 $ MathJax-Element-216 $ 。

   二分类线性判别分析的投影方向是一维的（只有一条直线），所以使用投影向量 $ MathJax-Element-217 $ 。

6. 上述最优化问题可以通过广义特征值问题求解： $ MathJax-Element-218 $

   • $ MathJax-Element-219 $ 的解析解为 $ MathJax-Element-220 $ 的 $ MathJax-Element-223 $ 个最大广义特征值所对应的特征向量组成的矩阵。
   • 多分类线性判别分析将样本投影到 $ MathJax-Element-223 $ 维空间。
   • 通常 $ MathJax-Element-223 $ 远小于数据原有的特征数，LDA因此也被视作一种经典的监督降维技术。