教科书上的LDA为什么长这样?

线性判别分析Linear Discriminant Analysis, LDA)是一种有监督降维方法,有关机器学习的书上一定少不了对 PCA 和 LDA 这两个算法的介绍。LDA 的标准建模形式是这样的(这里以两类版本为例,文章会在几个关键点上讨论多类情况):

其中,是类间散布矩阵,是类内散布矩阵, w 是投影直线:

怎么样,一定非常熟悉吧,经典的 LDA 就是长这个样子的。这个式子的目标也十分直观:将两类样本投影到一条直线上,使得投影后的类间散布矩阵与类内散布矩阵的比值最大。

三个加粗的词隐含着三个问题:

1. 为什么是类间散布矩阵呢?直接均值之差 m1-m2 不是更符合直觉吗?这样求出来的解和原来一样吗? 

2. 为什么是投影到直线,而不是投影到超平面?PCA 是把 d 维样本投影到 c 维 (c<d),LDA 为什么不能也投影到 c 维,而是直接投影到 1 维呢?同样地,在 K 类 LDA 中,为什么书上写的都是投影到 K-1 维,再高一点不行吗?这是必然吗? 

3. 为什么是类间散布与类内散布的比值呢?差值不行吗? 

这篇文章就围绕这三个问题展开。我们先回顾一下经典 LDA 的求解,然后顺次讲解分析这三个问题。

回顾经典LDA

原问题等价于这个形式:

然后就可以用拉格朗日乘子法了:

求导并令其为 0:

得到解:

对矩阵进行特征值分解就可以得到 w。但是有更简单的解法:

而其中是一个标量,所以和 λw 共线,得到:

求解完毕。非常优雅,不愧是教科书级别的经典算法,整个求解一气呵成,标准的拉格朗日乘子法。但是求解中还是用到了一个小技巧:是标量,从而可以免去特征值分解的麻烦。

那么,我们能不能再贪心一点,找到一种连这个小技巧都不需要的求解方法呢?答案是可以,上面的问题在下一节中就能得到解决。

类间散布 & 均值之差

我们不用类内散布矩阵了,改用均值之差 m1-m2 这个更符合直觉的东西:

还是用拉格朗日乘子法:

求导并令其为 0:

得到解:

怎么样,是不是求解更简单了呢?不需要任何技巧,一步一步下来就好了。

为什么说均值之差更符合直觉呢?大家想啊,LDA 的目的是让投影后的两类之间离得更远,类内离得更近。说到类内离得更近能想到的最直接的方法就是让类内方差最小,这正是类内散布矩阵;说到类间离得更远能想到的最直接的方法肯定是让均值之差最大,而不是均值之差与自己的克罗内克积这个奇怪的东西最大。

那么经典 LDA 为什么会用类间散布矩阵呢?我个人认为是这样的表达式看起来更加优雅:分子分母是齐次的,并且这个东西恰好就是广义瑞利商:

虽然经典 LDA 求解没有上面这个方法直接,但是问题表述更加规范,所用到的技巧也非常简单,不会给是使用者带来困扰,所以 LDA 最终采用的就是类间散布矩阵了吧。

直线 & 超平面

上面那个问题只算是小打小闹,没有太大的意义,但是这个问题就很有意义了:LDA 为什么直接投影到直线(一维),而不能像 PCA 一样投影到超平面(多维)呢? 我们试试不就完了。 

假设将样本投影到上,其中每一个 wi 都是经典 LDA 中的 w 。也就相当于我们不是把样本投影到一条直线上,而是投影到 c 条直线上,也就相当于投影到了超平面上。投影后的样本坐标为:

所以样本的投影过程就是:

那么,均值的投影过程也是这样:

投影后的均值之差的二范数

为什么不用第一行的向量内积而偏要用第二行的迹运算呢?因为这样可以拼凑出类间散布来,和经典 LDA 保持形式的一致。

回顾一下经典 LDA 的形式:

现在我们有了,还缺个约束,类比一下就可以得到了:

实际上,约束也可以选择成,这两个约束实际上都是在限制 W 的解空间,得出来的解是等价的,这两个约束有什么区别呢?我只发现了一点: 

回想是 c 条投影直线,为了确保向这 c 条直线投影能等价于向 c 维子空间投影,我们需要保证 c 条直线是线性无关的,即  rank(W) =c。看一下约束:

右边是秩为 c 的单位矩阵,因为矩阵乘积的秩不大于每一个矩阵的秩,所以左边这三个矩阵的秩都要不小于 c,因此我们得到了 rank(W) = c。也就是说,能够保证我们在向一个 c 维子空间投影。而约束中没有显式地表达这一点

我对矩阵的理解还不够深入,不知道是否也隐含了对秩的约束,所以为了保险起见,我选择了带有显式秩约束的,这样就得到了我们的高维投影版 LDA:

下面来求解这个问题。还是拉格朗日乘子法:

求导并令其为 0:

得到了:

在大部分情况下,一些协方差矩阵的和是可逆的。即使不可逆,上面这个也可以用广义特征值问题的方法来求解,但是这里方便起见我们认为可逆:

我们只要对进行特征值分解,就可以得到 d 个特征向量了,挑出最大特征值对应的 c 个特征向量来组成 W,我们不就得到向 c 维子空间的投影了吗?

真的是这样吗?

不是这样的。诚然,我们可以选出 c 个特征向量,但是其中只有 1 个特征向量真正是我们想要的,另外 c-1 个没有意义。

观察:

发现了吗?等式右边的 (m1-m2) 是一个向量,换句话说,是一个秩为 1 的矩阵。那么,这个乘积的秩也不能大于 1,并且它不是 0 矩阵,所以:

秩为 1 的矩阵只有 1 个非零特征值,也只有 1 个非零特征值对应的特征向量 w。

可能有人会问了,那不是还有零特征值对应的特征向量吗,用它们不行吗?

不行。来看一下目标函数

我们刚才得到的最优性条件:

所以目标函数为:

而我们的 W 只能保证 λ1, λ2, ..., λd 中的一个非零,无论我们怎么选取剩下的 c-1 个 w,目标函数也不会再增大了,因为唯一一个非零特征值对应的特征向量已经被选走了。 

所以,两类 LDA 只能向一条直线投影。 

这里顺便解释一下 K 类 LDA 为什么只能投影到 K-1 维,其实道理是一样的。K 类 LDA 的类间散布矩阵是:

可以看出,是 K 个秩一矩阵的和(因为 mk-m 是秩一的向量),所以它的秩最大为 K。并且,所以这 K 项中有一项可以被线性表出。所以,的秩最大为 K-1。也即:

只有 K-1 个非零特征值。所以,K 类 LDA 最高只能投影到 K-1 维。

咦?刚才第三个问题怎么提的来着,可不可以不用比值用差值,用差值的话会不会解决这个投影维数的限制呢?

比值 & 差值

经典 LDA 的目标函数是投影后的类间散布与类内散布的比值,我们很自然地就会想,为什么非得用比值呢,差值有什么不妥吗? 再试试不就完了。 

注意,这一节我们不用向量 w,而使用矩阵 W 来讨论,这也就意味着我们实际上在同时讨论二类 LDA 和多类 LDA,只要把换成对应的就好了。

注意到可以通过放缩 W 来得到任意大的目标函数,所以我们要对 W 的规模进行限制,同时也进行秩限制:

也就得到了差值版的 LDA:

依然拉格朗日乘子法:

求导并令其为 0:

得到了:

,有:

可以得到:

若括号内的东西可逆,则上式可以写为:

注意到, 的秩不大于 K-1,说明等号左边的秩不大于 K-1,那么等号右边的秩也不大于 K-1,即:

所以我们还是会遇到秩不足,无法求出 K-1 个以上的非零特征值和对应的特征向量。这样还不够,我们还需要证明的一点是,新的目标函数在零特征值对应的特征向量下依然不会增加。

目标函数(稍加变形)为:

再利用刚才我们得到的最优性条件(稍加变形):

所以目标函数为:

结论没有变化,新的目标函数依然无法在零特征值的特征向量下增大 

综合新矩阵依然秩不足零特征值依然对新目标函数无贡献这两点,我们可以得到一个结论:用差值代替比值也是可以求解的,但是我们不会因此受益。 

既然比值和差值算出来的解性质都一样,那么为什么经典 LDA 采用的是比值而不是差值呢? 

我个人认为,这可能是因为比值算出来的解还有别的直觉解释,而差值的可能没有,所以显得更优雅一些。什么直觉解释呢? 

在二分类问题下,经典 LDA 是最小平方误差准则的一个特例。若让第一类的样本的输出值等于 N/N1 ,第二类样本的输出值等于 -N/N2 , N 代表相应类样本的数量,然后用最小平方误差准则求解这个模型,得到的解恰好是(用比值的)LDA 的解。这个部分 PRML 上有讲解。

总结

这篇文章针对教科书上 LDA 的目标函数抛出了三个问题,并做了相应解答,在这个过程中一步一步深入理解 LDA。

第一个问题:可不可以用均值之差而不是类间散布?

答案:可以,这样做更符合直觉,并且更容易求解。但是采用类间散布的话可以把 LDA 的目标函数表达成广义瑞利商,并且上下齐次更加合理。可能是因为这些原因,经典 LDA 最终选择了类间散布。

第二个问题:可不可以把 K 类 LDA 投影到大于 K-1 维的子空间中?

答案:不可以,因为类间散布矩阵的秩不足。K 类 LDA 只能找到 K-1 个使目标函数增大的特征值对应的特征向量,即使选择了其他特征向量,我们也无法因此受益。

第三个问题:可不可以用类间散布与类内散布的差值,而不是比值?

答案:可以,在新准则下可以得到新的最优解,但是我们无法因此受益,K 类 LDA 还是只能投影到 K-1 维空间中。差值版 LDA 与比值版 LDA 相比还缺少了一个直觉解释,可能是因为这些原因,经典 LDA 最终选择了比值。

所以,教科书版 LDA 如此经典是有原因的,它在各个方面符合了人们的直觉,本文针对它提出的三个问题都没有充分的理由驳倒它,经典果然是经典。

PaperWeekly
PaperWeekly

推荐、解读、讨论和报道人工智能前沿论文成果的学术平台。

理论LDA
3
相关数据
范数技术

范数(norm),是具有“长度”概念的函数。在线性代数、泛函分析及相关的数学领域,是一个函数,其为向量空间内的所有向量赋予非零的正长度或大小。半范数反而可以为非零的向量赋予零长度。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

协方差矩阵技术

在统计学与概率论中,协方差矩阵(也称离差矩阵、方差-协方差矩阵)是一个矩阵,其 i, j 位置的元素是第 i 个与第 j 个随机向量(即随机变量构成的向量)之间的协方差。这是从标量随机变量到高维度随机向量的自然推广。

线性判别分析技术

线性判别分析 是对费舍尔的线性鉴别方法的归纳,这种方法使用统计学,模式识别和机器学习方法,试图找到两类物体或事件的特征的一个线性组合,以能够特征化或区分它们。所得的组合可用来作为一个线性分类器,或者,更常见的是,为后续的分类做降维处理。

目标函数技术

目标函数f(x)就是用设计变量来表示的所追求的目标形式,所以目标函数就是设计变量的函数,是一个标量。从工程意义讲,目标函数是系统的性能标准,比如,一个结构的最轻重量、最低造价、最合理形式;一件产品的最短生产时间、最小能量消耗;一个实验的最佳配方等等,建立目标函数的过程就是寻找设计变量与目标的关系的过程,目标函数和设计变量的关系可用曲线、曲面或超曲面表示。

分类问题技术

分类问题是数据挖掘处理的一个重要组成部分,在机器学习领域,分类问题通常被认为属于监督式学习(supervised learning),也就是说,分类问题的目标是根据已知样本的某些特征,判断一个新的样本属于哪种已知的样本类。根据类别的数量还可以进一步将分类问题划分为二元分类(binary classification)和多元分类(multiclass classification)。

降维技术

降维算法是将 p+1 个系数的问题简化为 M+1 个系数的问题,其中 M<p。算法执行包括计算变量的 M 个不同线性组合或投射(projection)。然后这 M 个投射作为预测器通过最小二乘法拟合一个线性回归模型。两个主要的方法是主成分回归(principal component regression)和偏最小二乘法(partial least squares)。

推荐文章
暂无评论
暂无评论~