5月份马上结束了。额，是真的马上结束了，截止我动手写这篇博客的时候，已经是5月最后一天的8点钟了。然后因为5月份在忙一些别的事，一直没有时间停下来总结一下学了什么。想着5月份最后一天了如果再不写点那5月份就真的过去了。之前写了瑞利商的优化问题，那这里就完成一下应用了瑞利商优化的两个降维算法(PCA和FLDA)的推导吧，算是给5月份划个句号。

PCA

PCA的全名叫"主成分分析"(Principal Component Analysis)，这个算法是非常著名的无监督降维方法。无监督降维顾名思义就是它降维的时候不需要给定数据的标签。它的核心是寻找一个最能代表原始数据低维表示的投影方向。

它可以建模为一个线性回归的问题，即找到一条直线能最好地拟合所有的样本点，这样所有的数据点都在一条直线上，就达到了“降维”的目的，而且因为这条直线是所有样本点的最佳拟合，因此样本在该直线上的投影是最能代表原样本的低维表示。要定义最佳拟合，可以借助回归问题的解法，每个数据点到该直线的距离的和最小，即最小平方误差。

定义直线： \[ \mathbf{x} = \mathbf{m} + a \mathbf{e} \tag{1} \] 其中，\(\mathbf{e}\)是单位向量，代表直线的方向。\(\mathbf{m}+a_k \mathbf{e}\)用来代表\(\mathbf{x_k}\)，这样就达到使用一个低维的\(a_k\)来代表高维的\(\mathbf{x_k}\)的目的。

准则函数

下面来处理拟合问题，即让高维的\(\mathbf{x}\)投影到低维的\(a\)时损失的信息最少。定义准则函数： \[ \begin{aligned} J_1(a_1,a_2,\cdots,a_n,\mathbf{e}, \mathbf{m})&=\sum_{i=1}^{n}{||(\mathbf{m} + a_k \mathbf{e}) - \mathbf{x_k} ||^2}\\ &=\sum_{k=1}^{n}{||a_k \mathbf{e} - (\mathbf{x_k} - \mathbf{m}) ||^2} \\ &=\sum_{k=1}^{n}{a_k^2 ||\mathbf{e}||^2} - 2\sum_{k=1}^{n}{a_k} \mathbf{e}^T (\mathbf{x_k-m}) + \sum_{k=1}^{n}{||(\mathbf{x_k-m})||^2}\\ &=\sum_{k=1}^{n}{a_k^2} - 2\sum_{k=1}^{n}{a_k} \mathbf{e}^T (\mathbf{x_k-m}) + \sum_{k=1}^{n}{||(\mathbf{x_k-m})||^2} \end{aligned} \] ### 求解参数

对\(a_i\)求偏导，可得： \[ \frac{\partial J_1}{\partial a_i} = 2a_i - 2\mathbf{e}^T (\mathbf{x_i-m}) \] 令偏导数为0，可得： \[ a_i=\mathbf{e}^T (\mathbf{x_i-m}) \tag{2} \] (2)式其实说明了能代表\(\mathbf{x}_k\)的\(a_k\)只需要沿该直线投影即可获得。那\(a_1,\cdots,a_n\)的优化问题可以由(2)式解决，那如何对\(\mathbf{e,m}\)进行优化呢？将(2)式代回原准则函数中，有： \[ \begin{aligned} J(\mathbf{e}, \mathbf{m}) &= -\sum_{k=1}^{n}{a_k^2} +\sum_{k=1}^{n}{||(\mathbf{x_k-m})||^2}\\ &=- \sum_{k=1}^{n}{[\mathbf{e}^T (\mathbf{x_k-m})]^2} + \sum_{k=1}^{n}{||(\mathbf{x_k-m})||^2}\\ &=- \sum_{k=1}^{n}{\mathbf{e}^T (\mathbf{x_k-m}) (\mathbf{x_k-m})^T \mathbf{e} } + \sum_{k=1}^{n}{||(\mathbf{x_k-m})||^2}\\ \end{aligned} \] 我们定义一个“散布矩阵”或”离散度矩阵“的概念： \[ \mathbf{S} = \sum_{k=1}^n{(\mathbf{x_k-m}) (\mathbf{x_k-m})^T} \tag{3} \] 将(3)代回原准则函数中，有： \[ J(\mathbf{e}, \mathbf{m}) = - {\mathbf{e} ^T \mathbf{Se} }+ \sum_{k=1}^{n}{||(\mathbf{x_k-m})||^2} \] 对于该式，对\(\mathbf{m}\)求偏导可得： \[ \frac{\partial J_1}{\partial \mathbf{m} }=\sum_{k=1}^n{2(\mathbf{x}_k - n\textbf{m})} \]

令该式为0可得：

\[ \mathbf{m} = \frac{1}{n} \sum_{k=1}^n{\mathbf{x}_k} \tag{4} \]

确定了\(\textbf{m}\)之后，只剩下\(\mathbf{e}\)需要优化了，原准则函数可以写为： \[ J(\mathbf{e}) = -{\mathbf{e} ^T \mathbf{Se} }+ \sum_{k=1}^{n}{||(\mathbf{x_k-\frac{1}{n} \sum_{j=1}^n{\mathbf{x}_j} })||^2} \] 要最小化准则函数\(J(\mathbf{e})\)，则最大化\({ \mathbf{e} ^T \mathbf{Se} }\)。这是一个标准的瑞利商优化问题： \[ \begin{aligned} \max \ \ \ \mathbf{e} ^T \mathbf{Se} \newline \textbf{s.t}\ \ \ \mathbf{e} ^T \mathbf{e} = 1 \end{aligned} \] 由拉格朗日乘子法可得： \[ L(\mathbf{e}, \lambda) = {\mathbf{e} ^T \mathbf{Se} } - \lambda(\mathbf{e} ^T \mathbf{e} - 1) \] 对\(\mathbf{e}\)求偏导可得： \[ \frac{\partial L}{\partial \mathbf{e} } = 2\mathbf{Se} - 2\lambda \mathbf{e} \] 令该式为0，可得： \[ \mathbf{Se} = \lambda \mathbf{e} \tag{5} \] 那\(\mathbf{e}\)必须为散布矩阵\(\mathbf{S}\)的特征向量才能取到极值。如果我们想最大化\({ \mathbf{e} ^T \mathbf{Se} } = \lambda \mathbf{e} ^T \mathbf{e}=\lambda\)，那需要取\(\mathbf{e}\)为散布矩阵特征值最大特征值对应的单位特征向量作为\(\mathbf{e}\)。

推广到d'维

这是将d维空间的样本映射到1维，实际可以推广到\(d'\)维，将直线的方程（式(1)）重写为：

\[ \mathbf{x} = \mathbf{m} + \sum_{i=1}^{d'} {a_i \mathbf{e}_i } \]

其中\(d' \leq d\)，新的平方误差准则函数为：

\[ J_{d'} = \sum_{k=1}^n{|| (m + \sum_{i=1}^d{a_i \mathbf{e}_i}) - \mathbf{x}_k ||^2} \tag{6} \]

在向量\[e_1,\cdots,e_{d'}\]分别为散布矩阵\(\mathbf{S}\)的\(d'\)个最大特征值所对应的特征向量时，(6)式可以取得最小值。因为散布矩阵式实对称矩阵，因此这些特征向量都是相互正交的。因此这些特征向量构成了代表任一向量\(\bf{x}\)的基向量，\(a_i\)为向量\(\bf{x}\)对应于基\(\mathbf{e}_i\)的系数，被称为“主成分”。

FLDA

FLDA(Fisher Linear Discriminant Analysis， 线性判别分析)与PCA的优化目标不同，PCA是在寻找最能代表原数据的低维投影，但是最能代表原数据的不一定对将样本分开有帮助。总的来说，PCA方法寻找的是用来有效表示的主轴方向，而判别分析方法寻找的是用来有效分类的方向。

为了达到这个目的，直观的想法就是：

  1. 将不同类分得越开越好
  2. 同一个类的样本尽量聚集起来

LDA就是将这两个直观的思路形式化表示出来，并构造了优化目标求解了这个问题。

首先看LDA是如何衡量类间的距离的：

类间距离

一个用来衡量投影结果分离程度的度量就是样本均值的差，原样本均值为： \[ \mathbf{m}_i = \frac{1}{n} \sum_{\mathbf{x} \in D_i} {\mathbf{x} } \]

经过投影后样本均值为： \[ \begin{aligned} \tilde{m_i} &= \frac{1}{n_i} \sum_{y \in \mathcal{Y_i} } {y}\\ &=\frac{1}{n_i} \sum_{\mathbf{x} \in \mathcal{X_i} } {w^T \mathbf{x}}=w^Tm_i \end{aligned} \] 可用定义类间的距离为样本的均值之差，也即： \[ |\tilde{m_1} - \tilde{m_2} | = |w^T(m_1 - m_2)| \] 然而，可用通过增加\(w\)的模来得到任意大小的投影样本均值之差。因此，投影样本均值之差的大小是相对而言的，否则只优化均值之差并不能达到寻找有效分类的方向的目的。继续看如何衡量类内散布情况。

类内散布

定义类内散布为： \[ \tilde{s}_i^2 = \sum_{y \in \mathcal{Y_i} }{(y-\tilde{m_i})^2} \] 将\(\tilde{s}_1^2 + \tilde{s}_2^2\)称作投影样本的总类内散布。

准则函数

Fisher线性可分性原则要求在投影\(y=w^T\mathbf{x}\)下，准则函数 \[ J(w) = \frac{|\tilde{m_1} - \tilde{m_2} |^2}{\tilde{s}_1^2 + \tilde{s}_2^2} \] 最大化。

求解w

之后讨论如何求解最优的\(w\)，为了把\(J(w)\)写成\(w\)的表达式，先定义类内散布矩阵\(S_i\)和总类内散布矩阵\(S_w\)如下： \[ S_i = \sum_{\mathbf{x} \in D_i}{(\mathbf{x}-m_i)(\mathbf{x}-m_i)^T} \tag{7} \]

\[ S_w = S_1+S_2 \tag{8} \]

有： \[ \begin{aligned} \tilde{s}_i &= \sum_{\mathbf{x} \in D_i}{(w^T\mathbf{x}-w^Tm_i)^2}\\ &=\sum_{\mathbf{x} \in D_i}{[w^T(\mathbf{x}-m_i)][w^T(\mathbf{x}-m_i)]^T} \\ &=\sum_{\mathbf{x} \in D_i}{w^T(\mathbf{x}-m_i)(\mathbf{x}-m_i)^Tw}\\ &=w^TS_iw \end{aligned} \] 因此，各离散度之和可以写成： \[ \tilde{s}_1 + \tilde{s}_2 = w^TS_Ww \] 类似地，投影样本均值之差可以展开为： \[ (\tilde{m}_1-\tilde{m}_2 ) = w^T(m_1-m_2)(m_1-m_2)^Tw=w^TS_Bw \] 其中： \[ S_B = (m_1-m_2)(m_1-m_2)^T \tag{9} \] 使用\(S_B和S_w\)，准则函数可以写为： \[ J(w) = \frac{w^TS_Bw}{w^TS_Ww} \tag{10} \] 要最大化(10)式，可以利用广义瑞利商的优化方法。简单来说就是\(w\)的模与\(J(w)\)的大小无关，因此可以调整使得分母\(w^TS_Ww=1\)，然后将它作为约束条件，最大化分子。之后用拉格朗日乘子法解决。可以证明，使得准则函数最大化的\(w\)必须满足： \[ S_B w = \lambda S_W w \tag{11} \] 这是一个广义特征值问题，满足(11)式的\(w\)是矩阵\(S_W^{-1}S_B\)的特征向量，\(\lambda\)为其特征值（需要\(S_W\)非奇异）。但在该问题中，并没有必要真正计算出特征值和特征向量，因为可知： \[ S_Bw = (m_1-m_2) \textcolor{blue}{(m_1-m_2)^Tw} \] 标蓝色的部分实际上是一个数，那么\(S_Bw\)总是会位于\((m1-m2)\)这个方向上。又因为\(w\)的模对准则函数的值没有影响，那么可以知道\(w\)需要满足： \[ w=S_W^{-1} (m_1-m_2) \tag{12} \] 这样就得到了Fisher可分性判据下\(w\)的解。

求解阈值

有了\(w\)，我们可以将数据集中的\(d\)维样本点\(\mathbf{x}_i\)投影到一维的\(w^T\mathbf{x}_i\)上。之后要讨论如何确定阈值来找到一维空间中把两类分开的那个点的位置，也即阈值。

如果\(p(\mathbf{x}|w_i)\)为多元高斯密度函数，并且各个类别的协方差矩阵\(\Sigma\)相同时，那通过判别函数\(g_1(\mathbf{x})=g_2(\mathbf{x})\)可知最佳分类超平面为： \[ \bar{w}^T(\mathbf{x}-\mathbf{x}_0) = 0 \] 其中： \[ \bar{w} = \Sigma^{-1}(\mu_1-\mu_2) \tag{13} \]

\[ \mathbf{x}_0 = \frac{1}{2} (\mu1 + \mu_2) - \frac{\ln[\frac{P(\omega_1)}{P(\omega_2)}]}{(\mu_1-\mu2)^T \Sigma^{-1} (\mu_1-\mu2)} (\mu_1-\mu_2) \]

如果使用样本均值和样本协方差来估计\(\mu_i\)和\(\Sigma\)，即： \[ \hat{\mu}_i = \frac{1}{n} {\sum_{k=0}^{n} }{\mathbf{x}_k} \]

\[ \hat{\Sigma} = \frac{1}{n} \sum_{k=1}^{n}{(\mathbf{x}_k-\hat{\mu}_i)(\mathbf{x}_k-\hat{\mu}_i)^T} \]

那么(13)式中的\(\bar{w}\)与使准则函数\(J(·)\)最大的\(w\)同方向。在该情况下： \[ w^T \mathbf{x} + w_0 = 0 \] \(w_0\)是一个与\(w\)和先验概率有关的常数，当Fisher线性判别大于某个阈值的时候就判决为\(\omega_1\)，否则判别为\(\omega_2\)。