线性/树型分类器的纯理论分析

纯理论分析


Preface

​ 周志华老师的《机器学习》看到了第五章,可总感觉看得太快了(可惜起步太晚了,大三下才系统地学ML)。个人认为走马观花地看完全没有用处,最好是能自己将所有碰到的轮子都写一遍(理想情况),但人的精力毕竟有限,开学了时间也比较紧张,实现这一步就先跳过吧,而细致的理论分析与理解是完全必要的。LDA之前实现过Github Algorithm-Plus🔗,决策树倒是连理论都没怎么细看,只调过库。为了不当调库侠,有写轮子的能力,个人将对这两章进行一下梳理,写一下自己的理解。

Figure 1. 西瓜

​ LDA(消歧义:Linear Discriminant Analysis,不是Latent Dirichlet Allocation)和决策树都是两个非常简单但是又很优雅的分类器。


LDA的数学推导

同类样本的类内方差最小,而不同类样本的类间方差最大

​ LDA是给定标签下的有监督降维方式,希望找到更低维度上的投影,可以满足上述属性。而对于高维而言,协方差是描述样本关系的指标。协方差的定义如下(大二下学的,回忆一下):描述n维随机变量X=(X1,X2,...Xn)每个分量之间存在的关系,协方差可以定义为: (1)C=(c11c12...c1nc11c12...c1ncn1cn2...cnn) ​ 其中,cij是两个分量Xi,Xj的协方差Cov(Xi,Xj)=E[(XiEi)(XjEj)]。协方差存在一些性质,比如说: (2)let Cov(X)=ΣCov(AX+b)=AΣAT ​ 证明就省略了,根据期望的性质,推导还是比较简单的。

二分类

​ 假设有两类样本,D1以及D2D1的样本中心(根据矩法可以求出来)为μ1,对应地D2μ2,那么假设存在一个低维过原点的超平面(由于是平行投影,是否过原点不影响结果,但原点较好讨论),这个超平面方程为:wTx=0,那么投影在这个超平面上的数据点应该有什么形式?中心点应该有什么形式?协方差是否改变?wTx=0确实是降了1维(因为有一个约束方程),但如何使用w进行投影?

​ 实际上,每个样本点xi都在:wTx+bi=0 这个超平面上,去掉这个相对原点的偏移,就可以得到每一个样本点在低维上的投影。实际是这样操作的:设xi是超平面wTx=0外一点,那么显然,xi可以表示为超平面上的投影点xi与法向量w的加权组合(因为已经构成基了),比如: (3)xi=xi+λiw ​ 那么λi显然就是xi在单位法向量we上的投影,那么可以知道: (4)xi=xiwTxiww2 ​ 但这是个什么呢?样本中心间的距离又是什么?可以求出样本中心应该在: (5)xc=1Ni=1N(xiwTxiww2) ​ 显然公式(5)是可以进行化简的,对于内积部分(后半部分),需要将内积展开为累加,进行累加次序交换: (6)1Ni=1NwTxiww2=1Nw2i=1N(j=1nwjxij)w=1w2j=1n1ni=1Nwjxijw=ww2j=1nwjμi=wTμww2 ​ 前半部分的化简十分简单。那么投影后的两个集合中心的差向量应该是: (7)dd=μ1μ2wT(μ1μ2)ww2 ​ 实际上,Fisher的处理方法与我的处理方法完全不同,我是真的求了一个这样的投影,但不管是Fisher还是西瓜书上的推导,均值全部都是:wTμ,这让我觉得很奇怪,如果是这样的话,均值的维度不就是1了吗?但实际上维度只应该减1啊?以上都是我看了第一部分产生的想法,但实际上二分类LDA并不是投影到n-1维空间中(特征分量数为n),二分类的LDA直接投影到一维空间上。二分类只需要在一条直线上找到数据的投影即可,在这条直线上判定投影后的新数据离哪一类数据中心最近。

​ 由于这是一下从n维降到1维,所以几何直观上并不好理解。个人觉得这样的降维跨度太大了。

为什么要投影到一条直线上?

​ 由于二分类输出的指示结果为 p1,p2, where p1+p2=1,也就是说分为两个类,落在两个类内的概率满足一个归一约束,那么输出就相当是在一条直线上。也就是说,LDA认为:输出在不同类上的概率实际上是所有输入特征经过w映射的线性组合,二分类问题只需要得到直线上的一个值,就能根据归一约束求出分属于两个类的概率。那么:

  • 三分类问题只需要求得在二维空间上的一个点,就能求出一个样本分属于三个类的概率。也即线性组合输出了一个二维的点
  • 四分类问题只需求出三维空间中的一个点,就能求出一个样本分属于四个类的概率...
  • M分类问题只需要求出M-1为空间中的一个点,就能求出一个样本分属于M个类的概率。

​ 要注意特征空间(n维)和概率空间(M维)的不同。LDA实际上就是在正态分布以及同方差的假设下,认为只要线性组合n个特征,就能求出M维空间中的一个概率解。这也就解释了,为什么我一开始的理解是有问题的。问题的关键就在于:输出分类的概率是输入特征的线性组合。不能简单地想着投影,而要想为什么要这样投影,这样投影如何帮助求得分类概率。

​ 那么数学上就比较好理解了:给定一条直线y=wTx,说是要投影到直线上,实际上要做的是根据w对样本的不同属性进行线性组合:wTx。那么也就有: (center of projected class 1)μ1=wTμ1(center of projected class 2)μ2=wTμ2(projected within-class cov 1)σ1=wTΣ1w(projected within-class cov 2)σ2=wTΣ2w ​ 那么根据类内方差最小,类间方差最大的思想: (8)max wTμ1wTμ22wT(Σ1+Σ2)w ​ 分子展开维转置乘积之后,可以定义两个散度矩阵: (within-class scattermatrix)Sb=(μ1μ2)(μ1μ2)T(between scatter matrix)Sw=Σ1+Σ2 ​ 使用这两个散度矩阵,定义问题(8)带有广义瑞利商的形式。解问题(8)就可以得到最优的w。由于w的长度是不影响结果的(看的就是方向),不妨令分母为1,最大化分子,进一步化简为: (9)min wTSbws.t. wTSww=1 ​ 请Lagrange坐到主席台上来。根据增加了一项乘子项的优化问题(9),KKT条件梯度为0,得到: (10)Sbw=λSww(μ1μ2)=Sww ​ 等式(10)可以化简得原因是:Sb=(μ1μ2)(μ1μ2)T,也就是说,Sbw实际方向就是μ1μ2,根据w尺度任意性,直接令Sbw=λ(μ1μ2)省事。根据(10),进行SVD分解(数值上会比较稳定)就可以得到w

多分类

​ 从上述理解中已经可以知道LDA的“降维分类”方式,实际上是通过原特征的线性组合,将特征空间直接变换到“概率空间”(或者是可以被变换为概率的空间)。当分类数量为M时,只需要知道M-1个类上的概率或者等价概率值就可以求出所有类上的“概率输出”值。

​ 也就是说:LDA的降维过程实际上是由n维特征空间变换为M-1维分类空间的过程。回顾二分类的情况,M = 2,也就是将所有样本投影到一维(直线)上:y=wTx,直线上的值显然是一维的。这是由于参与线性组合的函数实际上是一个标量值函数(wTx映射),要想输出高维的向量,只需要更改w为一个矩阵W即可。对于需要优化得到的结果,推导有些不同: (11)St=i=1m(xiμt)(xiμt)T ​ 定义公式(11)为全局散度,也就是每个样本点到所有样本的平均点的散度和。个人认为,由于类间差异在大多数情况下都会大于类内差异,所以St相当于就是一个类间方差的表征(不同类的均值点到整体均值点的散度)。由于不同于二分类问题,类内散度需要重新定义了。显然类内的散度可以用类内样本与本类均值的差异来衡量: (12)Sw=j=1N(xijμi)(xijμi)T ​ 但是至于为什么西瓜书上要使用(12)(11)作为最后的类间散度矩阵,我不是很清楚。甚至我觉得,(12)的定义是多余的。类间散度实际上可以根据:

​ 类内散度通常小于类间散度,在最优投影取得的情况下就更是这样了。所以每个样本,在类间散度很大的情况下,可以看作一个十分接近类内均值的点(如下图所示)。那么每个样本点都可以近似地被类内均值取代。

Figure 2. 样本与均值的近似性

​ 那么很自然,类间散度可以定义为(每个样本(近似)与全局均值的散度和) (13)Sb=i=1Mmi(μiμ)(μiμ)T ​ 优化目标也需要更改,因为实际的输出式已经变成了如下式所示的多维线性组合矩阵W,输出是多维的,那么可以简单地使用迹进行实现。 (14)WTSbWWTSbW max tr(WTSbW)tr(WTSbW) ​ 对于上式,继续根据拉格朗日乘子法可以得到: (15)SbW=λSwWSw1SbW=λW ​ 可知,W是一个(n * M-1)维矩阵,而显然(15)W的每个列向量分量都是矩阵Sw1Sb的一个特征向量(符合特征向量定义,当然可能是广义特征向量),那么(N1n)种不同的情况,究竟是哪N-1个特征向量组合成了最终的解W?从公式(15)种可以看出,λ越大越好(对应最大化(14))。那么只需要选择Sw1Sb最大的N-1个特征值(或者广义特征值)的特征向量组成解即可。


树型 - 决策树

树越是向往高处的光亮,它的根就越要向下,向泥土,向黑暗的深处。—尼采

​ emmm。这句话只因为有个“树”字就被我拿出来镇一镇文章了。决策树,利用一个个不相互影响的特征(或者我们认为影响不太大的特征,实际上有影响也是可以通过某些操作进行转化的)进行层层分类。正如猜物游戏,每次只能问一个答案只有“是”和“否”的问题,通过答案产生的分支进行推测。通过对待分类样本的层层分解可以获得最终的分类推测。本节只讨论其相关的数学原理,对于具体的生成 / 剪枝算法将不会涉及(因为这没有吸引到我)。

信息论相关

​ 回顾一下信息熵的两个定义: (16)Ent(x)=i=1npilog(pi) or Ent(x)=p(x)log(p(x))dx ​ 左边为常见的离散型随机变量熵的定义,而右边则为连续变量在其PDF意义下的熵。在讲KL散度的时候已经说过了,熵是用于衡量信息编码的一个概念。一个随机事件的不确定性越大,代表信息量越大,编码这个事件所需要的二进制位数也相应越大。

​ 在决策树一章中,《西瓜书》提到:

"信息熵" (information entropy) 是度量样本集合纯度最常用的一种指标。

​ 为什么这么说呢?集合样本纯度又是指什么?纯度在此处指:同一个划分中,由于划分集合内的元素都存在相应的label,如果集合内的label越趋于一致,那么这个集合的纯度也就越高。如果用比例pk表示划分集合中,第k类样本所占的比例,那么这个集合的信息熵(纯度)表示如下: (17)Ent(D)=i=1npilog(pi) ​ 可以看出,公式(17)定义的纯度,当某一类完全占据整个集合时熵取得最小值0。为什么要讨论信息熵或者是纯度?处于决策树的生成考虑,我们使用很多特征生成一棵决策树,但在决策树中,不同的特征地位也是不相同的,naive的情况下,每次分支只选择其中一个特征,那么要选哪一个特征作为本结点向下分支的特征?需要进行优选,优选的指标就是纯度。

​ 显然,如果一种划分模式可以划分出纯度较高的子结点(样本子集合),那么:

  • 全纯结点(只有一类)可以避免进一步分支,减小树结构复杂度
  • 子集合越纯,说明分类效果越好(因为原集合是无序的,熵大,分类可以看作熵减过程)

​ 由此我们定义信息增益:对于公式(17)定义的“纯度”,个人认为应该叫做“杂度”更好,实际上我看Wikipedia称这个为“impurity”,很显然嘛,值越大杂度越高。那么原集合的杂度为Ent(D),如何选取划分才能使得系统的杂度下降最大呢?假设我们选取的属性a存在v个不同的值(也就是v分支),那么每个分支(a属性的每种可能取值)都会有一定样本(可以为0),记为Dv。对应地,Ent(Dv)指的是总体为Dv时,分类的杂度。那么根据|Dv|/|D| 也即每个属性样本的占比对杂度进行加权,划分后的系统杂度为: (18)G(D,a)=Ent(D)j=1v|Dj||D|Ent(Dj) ​ 公式(18)是原系统的杂度 减去 划分后的系统杂度。这也就是分类,这个熵减过程到底让系统的熵减了多少。这被称为信息增益(information gain),实际上衡量的就是分类使系统熵减少的量。显然我们希望,熵减越大越好。那么每次从属性集合中计算 / 选择信息增益最大的属性进行分支即可。

互信息

​ 信息论中,如果需要衡量两个随机变量之间的关系,可以计算 一个随机变量携带的信息包含另一个随机变量信息的量大小,这被定义为互信息(mutual information)。可以这样认为:两个有关联的变量,给定其中一个变量的信息,另一个变量的不确定性随之减小: (19)I(X;Y)=DKL(PXY||PXPY), where xX,yY ​ 上式说的是:x是空间X中的随机变量,y是空间Y中的随机变量,那么互信息是联合分布PXY与边缘分布PX and PY的外积的KL散度。多维空间不好理解的话,讨论一维变量: (20)I(X;Y)=yxp(x,y)log(p(x,y)p(x)p(y))dxdy ​ 为什么这样可以描述相关程度呢?因为显然,X与Y独立时的联合分布为p(x)p(y),此处衡量的即是真实联合分布p(x,y)与独立时的联合分布的差别。

​ 互信息和信息增益是存在关系的[1]。在划分时,如果对属性集合A(也就是a所在的集合)取上一个期望,那么会有什么发现?也即对公式(18)定义的信息增益取A的期望,为了方便数学变换,我们将(18)展开: (21)G(D,a)=k=1Jpklog2pkv=1V|Dv||D|(k=1JpDv,klog2pDv,k) ​ 显然公式(21)可以被表示为(原系统熵 - 给定划分下的新集合熵) (22)G(D,a)=Ent(D)Ent(D|a) ​ 进行期望的求取可以得到: (23)EA(G(D,a))=Ent(D)Ent(D|A) ​ 下面证明一个有关互信息的简单结论: (24)I(X;Y)=Ent(X)Ent(X|Y) ​ 怎么说呢。推了好长时间没有推出来的原因就是:没有学过信息论,概念不清楚。比如(24)右边的第二项,条件信息熵,定义为: (25)Ent(X|Y)=xX,yYp(x,y)log(p(x|y)), but not xXp(x|y)log(p(x|y)) ​ 那么(24)可以展开为: (26)I(X;Y)=yYxXp(x,y)log(p(x))+yYxXp(x,y)log(p(x,y)p(y)) ​ 化简可以得到公式(24)成立。那么可以知道,增益率对于A的期望(也就是对于属性集的概率平均)就是决策树结点与属性集的互信息。

增益率

​ 实际上,纯使用信息增益并不太好。假设某个分支结点只有一个样本,那么显然分支纯度最大(杂度最小),那么假如有一个属性分支极多,可能一下就将所有的样本分到不同结点上了(比如《西瓜书》上提到的,样本序号),这样容易产生过拟合的分支属性是没有意义的,但是只用信息增益的话实际就会选择这个分支方法。所以使用一个因子来限定分支数的影响: (27)IV(a)=v=1V|Dv||D|log(|Dv||D|) ​ 可以发现,当分支数越多,这个值越大(不会出现单分支)。这个值称为:固有值(intrinsic value),只需要使用这个值对增益进行惩罚即可(除以此值)。

基尼指数

​ 针对CART决策树的,而以上所说的决策树使用信息增益作为划分属性选择的度量。基尼指数(Gini impurity)指的是:

Gini impurity is a measure of how often a randomly chosen element from the set would be incorrectly labeled if it was randomly labeled according to the distribution of labels in the subset.[1]

​ 翻译很简单:从集合中随机选择一个元素,再根据这个集合中的类别概率分布随机给这个元素进行分类,分类的错误概率就是基尼指数。 (28)Gini(D)=i=1|Y|pikipk=1k=1|Y|pk2 ​ 显然,纯度越高的集合,内部随机取元素随机分类错误的概率(期望)越小。

变量缺失处理的理解

​ 在贝叶斯决策论中提到:

  • 某一属性组合的变量可能根本不在样本中出现,但是不能直接认为这样的样本不存在。

​ 而在决策树中,我们更多针对的问题是:当某一个样本某个属性值是未知的,如何处理这样的样本?丢弃是显然不可取的,这样可能损失太多的有效信息。而直接使用确实也不是办法,少掉一个属性要如何继续分支?《西瓜书》上将问题总结地很不错:

我们需解决两个问题: (1) 如何在属性值缺失的情况进行划分属性选择 ? (2) 给定划分属性,若样本在该属性上的值缺失,如何对样本进行划分 ?

​ 第一个问题我开始并没有什么很好的想法。而对于第二个问题,个人开始认为,假设已经知道了划分属性,可以根据其他完好样本来估计本样本在这个缺失属性上的分布,进行分布加权(事实上,这个想法类似《西瓜书》上提供的方法)。

​ 问题一实际上比较容易,我想得太复杂了。由于划分属性只考虑一个属性与分类结果的关系,那么完全用不着考虑多属性关系,只需要取出这个属性下对应没有缺失的样本,利用这些样本估计【属性】对【分类结果】的影响即可。以信息增益法为例,考虑(18)定义的信息增益。假设我们讨论属性a,由于有些样本属性是缺失的,在计算时将这些样本剔除再计算新集合D~的信息增益G~(D~,a)。注意,此信息增益计算出来后需要加权: (29)G~(D~,a)×ρ, what is ρ? ​ 其中的ρ是加权因子,是什么权重呢?假设属性a在集合中有|D~|个未缺失样本,那么ρ=|D~|/|D|,也就是说,样本缺失越少,信息增益计算越可信。

​ 问题2实际上是将“让同一个样本以不同的概率划入到不同的子结点中去”(《西瓜书》言)。也可以使用没有缺失属性a的样本信息,假设某一分支分到属性a的v取值av上: (30)rv~=xD~vwxxD~wx ​ 也就是没有缺失属性a的样本中,有rv~比例样本在本属性上取值为v,那么当每个样本权重为wx时,可以按照比例将缺失样本分配给不同分支(相当于按照概率(比例)割裂一个缺失样本)。

Kernelization

​ 普通决策树的分类边界都是垂直于某个轴的(因为决策树是一种“非黑即白”的分类方法)。在某个属性(某个维度)上,只有固定的几种分法:

Figure 3. 决策树在单一维度上的分类边界总是垂直于轴的

​ 啊这?太过于“一维”了,甚至连简单的线性可分分类都需要经过如下的艰难操作:

Figure 4. 决策树扭来扭去

​ 一个简单的想法就是:不适用原属性进行分类,我们可以像PCA那样,使用属性的线性组合形成抽象属性,在这个抽象属性对应的新空间中,虽然分类边界仍然垂直于新的空间轴,但在原空间看起来,就成为一般线性分类器了。而进一步地,如果使用其他的非线性特征组合方法,也就是引入某些 kernel,甚至可以通过决策树达到任意分类边界生成的效果。


Reference

[1] Wikipedia, Decision tree learning