线性分类模型

线性分类模型


线性分类问题有三种解法,第一种是直接使用判别函数将特征向量关联到某个类别,第二种和第三种分别对条件概率 (p(mathcal{C}_k|mathbf{x})) 和类别条件概率 (p(mathbf{x} | mathcal{C}_k)) 建模。

可以使用广义线性模型对后验(条件)概率进行建模,该概率值被记为

[y(mathbf{x})=f(mathbf{w}^ ext{T}mathbf{x}+w_0), ]

其中 (f(cdot)) 称为激活函数(它的逆也被称为链接(link)函数),尽管激活函数是非线性的,但判决边界是线性于输入向量的。这意味着,假如我们需要解决的是一个二分类问题,那么决策边界仍然是一个超平面,只不过我们决定该超平面的位置不再取决于样本点距离该超平面的欧氏距离,而是该距离的某个非线性函数。你可以想象在 (mathbf{w}) 空间中,误差函数不再是一个超抛物面,而是一个其他形状的曲面,其极值点 (mathbf{w^*}) 依然对应样本空间 (mathbf{x}) 中的一个超平面。
一般说的逻辑斯蒂回归模型(实际是分类)就属于这种广义线性模型。

1 判别函数


1 这里只考虑线性判别函数的情况。先考虑二分类的情况,最简单的线性判别函数形如

[y(mathbf{x})=mathbf{w}^ ext{T}mathbf{x}+w_0, ]

此后我们根据判别函数的正负性决定 (mathbf{x}) 的所属类别。

2 现在考虑将线性判别推广到多分类问题。我们会很自然地想到多次使用二分类解决多分类。通常有两种做法,即使用1v1或1vK(实际是K-1,为简单起见写成K)实现多分类,如果使用的是1v1,一般需要借助投票原则判定样本所属类别。但是这两种方法都有一个很大的缺点,就是不能将样本空间规范完整地划分为 (K) 个子空间,即在某些情况下会出现不确定如何分类的样本。
当然也存在别的思路。回顾上式,(y(mathbf{x})) 实际表示样本 (mathbf{x}) 到判决平面的有向距离,这里“有向”有两层意思,首先是说这个距离可正可负,然后是说正负性取决于原点(O)是否属于当前类别。所以对于二分类问题,某个样本 (mathbf{x}) 属于类别 (mathcal{C}_1) ,它在类别1下的有向距离为 (+d(d>0)) ,那么它在类别2下的有向距离必然为 (-d(d>0)) ,由于 (d_{mathcal{C}_1}(mathbf{x})>d_{mathcal{C}_2}(mathbf{x})) ,从而将 (mathbf{x}) 分类给 (mathcal{C}_1) 。这个性质可以方便地从二元划分推广到多元划分。对于每个类别 (mathcal{C}_k) ,我们假设有一个超平面 ((mathbf{w}_k,w_{k0})) ,它决定任意样本 (mathbf{x}) 属于该类别的“可比似然度”,“可比”指这种似然度可在任意类比之间直接比较,“似然度”是指给定当前类别,该样本点属于该类别的似然程度(类比于似然概率)。从而在所有类别无差别(均匀、等质、同先验)的假设下,我们将样本 (mathbf x) 划给类别 (mathcal{C}_k) 当且仅当它到此类别超平面有向距离最大

[y_k(mathbf x)=mathbf w_k^ ext Tmathbf x+w_{k0}>y_j(mathbf x), j eq k. ]

显然,我们使用这种方法可以将样本空间无歧义地划给(K)类。某种程度上,这种思路类似于K近邻方法(KNN)。可以说明,这种方法下的判决区域(某类别的所属子空间)是单联通的凸区域。可以选取某类别区域任意两点,分析线段上某点的类别所属情况说明之。

图1

以下分别介绍通过最小方差(平方误差/MSE)、Fisher线性判别和感知机算法学习线性判别函数的参数。

3 考虑使用最小方差优化参数,对于类别 (mathcal{C}_k) ,其超平面为

[y_k(mathbf x)=mathbf w_k^ ext Tmathbf x+w_{k0}, ]

(K)类输出值整合在一起,有

[mathbf y(mathbf x)=mathbf W^ ext Tmathbf x, ]

为了记号简便,这里 (mathbf W) 的第 (k) 行为 ((mathbf w_k^ ext T, w_{k0}))(mathbf x)((mathbf x^ ext T, 1)^ ext T)
假设我们的训练数据为 ({mathbf x_n, mathbf t_n}) ,这里目标值使用1-K二元编码。从而对整个训练集,平方误差函数为

[E(mathbf W)=frac{1}{2} ext{Tr}left{ left(mathbf{XW-T} ight)^ ext Tleft(mathbf{XW-T} ight) ight}, ]

这里 (mathbf T) 的第 (k) 行为 (mathbf t_k^ ext T) ,且使用结论 ( ext{Tr}(mathbf{AB})= ext{Tr}(mathbf {BA}))
使用上式误差函数对 (mathbf W) 求导,有

[frac{partial E}{partial mathbf W}=mathbf Xfrac{partial E}{partial(mathbf{XW-T})}=mathbf{X(XW-T)}, ]

令其为零,推得

[mathbf W = (mathbf X^ ext Tmathbf X)^ ext{-1}mathbf X^ ext Tmathbf T=mathbf X^{star}mathbf T. ]

从而预测函数可重新记为

[mathbf y(mathbf x)=mathbf{W}^ ext Tmathbf x=mathbf T^ ext T{mathbf X^{star}}^{ ext T}mathbf x. ]

此外,若训练数据满足,对任意目标向量 (mathbf t_n) ,存在常量 (mathbf a)(b) ,使得

[mathbf a^ ext Tmathbf t_n+b=0, ]

那么对任意样本 (mathbf x) ,模型输出必然也满足

[mathbf a^ ext Tmathbf y(mathbf x)+b=0. ]

特别地,如果我们使用的是1-K编码,这里 (mathbf a^ ext Tequiv(1,...,1), b equiv -1) 。也就是说,模型输出向量各分量之和为 (1) 。特别地,如果我们面临的是二分类问题,属于某类别的样本目标向量在该分量上为 (+1) ,反之为 (-1) ,那么有 (mathbf a^ ext Tequiv(1,1),bequiv 0) ,此时模型输出向量各分量之和为 (0)

下面给出上述结论的一个证明。
在之间的表达中,将 (mathbf x) 视作样本经过增广后的向量( (x^{(1)}equiv 1) ),且对 (mathbf w) 也进行了增广。这为某些情形下的问题求解提供了方便,但在这里需要重新分离出偏置。记

[y_k(mathbf x)=mathbf w_k^ ext Tmathbf x+w_{k0}, ]

[mathbf y(mathbf x)=mathbf W^ ext Tmathbf x+mathbf w_{0}, ]

[mathbf Y(mathbf X)=mathbf{XW}+mathbf 1mathbf w_0^ ext T, ]

其中(1)的长度为(N)(样本总数)的列向量, (mathbf Y(mathbf X)) 的第 (n) 行为第 (n) 个样本的线性判别模型输出向量的转置。
重写误差项

[E_D(mathbf W,mathbf w_0)=frac{1}{2} ext{Tr}left{left(mathbf{XW}+mathbf 1mathbf w_0^ ext T-mathbf T ight)^ ext Tleft(mathbf{XW}+mathbf{1}mathbf w_0^ ext T-mathbf T ight) ight}, ]

首先对 (mathbf w_0) 求梯度有

[frac{partial E_D}{partial mathbf w_0}=left((mathbf {XW-T)}^ ext T+mathbf w_0mathbf 1^ ext T ight)mathbf 1, ]

令其为零,有

[egin{aligned} mathbf w_0=&-frac{1}{N}left(mathbf{XW-T} ight)^ ext Tmathbf 1\=&-frac{1}{N}(mathbf W^ ext Tmathbf X^ ext Tmathbf 1-mathbf T^ ext Tmathbf 1)\=& frac{1}{N}sum mathbf t_n^ ext T-frac{1}{N}mathbf W^ ext Tsummathbf x_n^ ext T\=& mathbf t^+-mathbf W^ ext Tmathbf x^+, end{aligned}]

其中

[mathbf t^+=frac{1}{N}summathbf t_n^ ext T=mathbf T^ ext Tmathbf 1, ]

[mathbf x^+=frac{1}{N}summathbf x_n^ ext T=mathbf X^ ext Tmathbf 1. ]

现在对 (mathbf W) 求梯度,有

[frac{partial E_D}{partial mathbf W}=mathbf X^ ext Tleft(mathbf{XW}+mathbf 1mathbf w_0^ ext T-mathbf T ight), ]

令其为零,有

[mathbf W=(mathbf X^ ext Tmathbf X)^{-1}mathbf X^ ext T(mathbf T-mathbf 1mathbf w_0^ ext T) ]

带入 (mathbf w_0) ,并记 (mathbf T^+=mathbf 1{mathbf t^+}^ ext T,mathbf X^+=mathbf 1{mathbf x^+}^ ext T) ,得

[mathbf W=(mathbf X^ ext Tmathbf X)^{-1}mathbf X^ ext T(mathbf T-mathbf T^++mathbf X^+mathbf W), ]

移项整理后

[mathbf W=mathbf M(mathbf T-mathbf T^+), ]

其中

[mathbf M=left(mathbf E-mathbf X^starmathbf X^+ ight)^{-1}mathbf X^star ]

并且

[mathbf X^star=(mathbf X^ ext Tmathbf X)^{-1}mathbf X^ ext T. ]

从而

[egin{aligned} mathbf a^ ext Tmathbf y(mathbf x)+b=&mathbf a^ ext T(mathbf W^ ext Tmathbf x+mathbf w_0)+b\=& mathbf a^ ext Tleft(left(mathbf T-mathbf T^+ ight)^ ext Tmathbf M^ ext T(mathbf x-mathbf x^+)+mathbf t^+ ight)+b\=& b(mathbf 1-mathbf 1)^ ext Tmathbf M^ ext T(mathbf x-mathbf x^+)+(-b)+b\=& 0 .end{aligned}]

如果我们使用平方误差作为线性分类模型的目标函数,则会面临两个主要的问题,其一是缺乏鲁棒性,对离群值敏感,而实际决策边界应该只由边界点确定;再者就是在某些情况下,分类效果奇差,而本来问题并不难。或许这是因为平方误差对应高斯条件分布假设下的似然估计,而1-K编码分布远离高斯分布【这句我也没看明白】。

4 还有一种实现分类的思路是降维。例如在二维情形下,可以将样本点投影到某条直线上,通过投影点所在区域决定原样本点所属类别。然后我们需要做的就是考虑如何投影达到最佳的分类效果。一般有两条指示标准,一是我们希望不同类别尽可能离得远,二是同类别样本投影尽可能集中。可以分别用样本均值和方差量化之。具体来说,对于二分类问题,有 (N_1)(mathcal C_1) 样本, (N_2)(mathcal C_2) 样本,从而其均值 (mathbf m_1)(mathbf m_2) 分别为

[mathbf m_1=frac{1}{N_1}summathbf x_n^{(1)}, ext{ }mathbf m_2=frac{1}{N_2}summathbf x_n^{(2)}. ]

投影直线的方向向量为 (mathbf w) ,从而在一维坐标系上,两均值的投影点之间的距离为

[m_2-m_1=mathbf w^ ext T(mathbf m_2-mathbf m_1), ]

如果不考虑类间离散度,最大化该量会得到垂直于类别均值连线的投影方向,这种情况下,均值投影点是分得最开的,但可能会出现较多的误分(投影区域重合)。

[egin{aligned} max_{mathbf w}m_2-m_1=&mathbf w^ ext T(mathbf m_2-mathbf m_1)+lambda(||mathbf w||^2-1)\ frac{partial (m_2-m_1)}{partial mathbf w}=&(mathbf m_2-mathbf m_1)+2lambdamathbf w=0 end{aligned}]

现在考虑类间投影离散度,即 (y) 为样本点 (mathbf x) 的投影, (m_k) 为类别 (mathcal C_k) 的均值的投影,从而类间方差为

[s_k^2=sumleft(y_n^{(k)}-m_k ight)^2. ]

在二分类条件下,总的类内方差为 (mathbf s_1^2+mathbf s_2^2) ,从而Fisher标准为下式

[J(mathbf w)=frac{(m_1-m_2)^2}{s_1^2+s_2^2}=frac{mathbf w^ ext T(mathbf m_2-mathbf m_1)(mathbf m_2-mathbf m_1)^ ext Tmathbf w}{sum mathbf w^ ext T(mathbf x_n^{(1)}-mathbf m_1)(mathbf x_n^{(1)}-mathbf m_1)^ ext Tmathbf w+summathbf w^ ext T(mathbf x_n^{(2)}-mathbf m_2)(mathbf x_n^{(2)}-mathbf m_2)^ ext Tmathbf w}=frac{mathbf w^ ext Tmathbf S_ ext{B}mathbf w}{mathbf w^ ext Tmathbf S_ ext{W}mathbf w}, ]

其中 (mathbf S_ ext B)(mathbf S_ ext W) 分别被称为类间(between-class)和类内(within-class)协方差矩阵(二阶矩)。
由于

[frac{partial J}{partial mathbf w}=frac{1}{partialmathbf w}partial frac{ ext{Tr}(mathbf w^ ext Tmathbf S_ ext{B}mathbf w)}{ ext{Tr}(mathbf w^ ext Tmathbf S_ ext{W}mathbf w)}=frac{(mathbf S_ ext B^ ext T+mathbf S_ ext B)mathbf wmathbf w^ ext Tmathbf S_ ext Wmathbf w-mathbf w^ ext Tmathbf S_ ext Bmathbf w(mathbf S_ ext W^ ext T+mathbf S_ ext W)mathbf w}{(mathbf w^ ext Tmathbf S_ ext Wmathbf w)^2}, ]

利用两类协方差矩阵的对称性,并令该梯度为零,交换数量 (mathbf w^ ext Tmathbf Smathbf w) 在矩阵乘法中的位置,得到下式

[(mathbf w^ ext Tmathbf S_ ext Bmathbf w)mathbf S_ ext Wmathbf w=(mathbf w^ ext Tmathbf S_ ext Wmathbf w)mathbf S_ ext Bmathbf w. ]

注意到 (mathbf S_ ext Bmathbf w=(mathbf m_2-mathbf m_1)(mathbf m_2-mathbf m_1)^ ext Tmathbf w) 始终与 ((mathbf m_2-mathbf m_1)) 同向,再处理掉括号里的数量,得出关系

[mathbf S_ ext Wmathbf wpropto (mathbf m_2-mathbf m_1), ]

进而

[mathbf w propto mathbf S_ ext W^{-1}(mathbf m_2-mathbf m_1). ]

当类内样本协方差同心分布时,(mathbf S_ ext W)正比于单位阵,此时投影方向垂直于两类均值的连线。
上述结果即Fisher线性判别,当然目前只给出了投影方向,没有决定在投影直线上何处属于第一类,何处属于第二类,这一步可以使用类别条件分布为高斯分布假设下的似然概率最大化确定需要的阈值。

5 下面考虑最小平方误差与Fisher判别的关系。结论是,在二分类情形下,Fisher判别可作为最小平方误差的特例,当然,这时候最小平方误差不再使用1-K编码作为目标向量的表示。此时若 (mathbf x_n) 属于类别 (mathcal C_1) ,则 (t_n=frac{N}{N_1}) ;若 (mathbf x_n) 属于类别 (mathcal C_2) ,则 (t_n=-frac{N}{N_2}) ,在数值上,此时目标值不再是向量而是数量,且大小等于类别先验概率的倒数。这里 (mathbf x_n) 是对原样本进行增广后的向量,偏置也包含在 (mathbf w) 中。此时平方误差为

[E(mathbf w)=frac{1}{2}sumleft(mathbf w^ ext Tmathbf x_n-t_n ight)^2, ]

从而

[frac{partial E}{partial mathbf w}=sum(mathbf w^ ext Tmathbf x_n-t_n)mathbf x_n, ]

令该梯度为零,得出

[egin{aligned} summathbf w^ ext Tmathbf x_nmathbf x_n=&sum t_nmathbf x_n=N(mathbf m_1-mathbf m_2)\=&summathbf x_nmathbf x_n^ ext Tmathbf w\=&sum(mathbf x_n^{(1)}-mathbf m_1+mathbf m_1)(mathbf x_n^ ext{(1)}-mathbf m_1+mathbf m_1)^ ext Tmathbf w+sum(mathbf x_n^{(2)}-mathbf m_2+mathbf m_2)(mathbf x_n^{(2)}-mathbf m_2+mathbf m_2)^ ext Tmathbf w\=&left(mathbf S_ ext W+N_1mathbf m_1mathbf m_1^ ext{T}+N_2mathbf m_2mathbf m_2^ ext T ight)mathbf w, end{aligned}]

由于

[egin{aligned} Nmathbf m=&N_1mathbf m_1+N_2mathbf m_2\Nmathbf mmathbf m_1^ ext T=&N_1mathbf m_1mathbf m_1^ ext T+N_2mathbf m_2mathbf m_1^ ext T\Nmathbf mmathbf m_2^ ext T=&N_1mathbf m_1mathbf m_2^ ext T+N_2mathbf m_2mathbf m_2^ ext T\ N_1N_2mathbf S_ ext B=& N_1N_2(mathbf m_1mathbf m_1^ ext T+mathbf m_2mathbf m_2^ ext T)-N_1(Nmathbf mmathbf m_1^ ext T-N_1mathbf m_1mathbf m_1^ ext T)-N_2(Nmathbf mmathbf m_2^ ext T-N_2mathbf m_2mathbf m_2^ ext T)\ =&N(N_1mathbf m_1mathbf m_1^ ext T+N_2mathbf m_2mathbf m_2^ ext T)-N^2mathbf mmathbf m^ ext T\N_1mathbf m_1mathbf m_1^ ext T+N_2mathbf m_2mathbf m_2^ ext T=&frac{N_1N_2}{N}mathbf S_ ext B+Nmathbf mmathbf m^ ext T end{aligned}]

代回上式,有

[(mathbf S_ ext W+frac{N_1N_2}{N}mathbf S_ ext B+Nmathbf mmathbf m^ ext T)mathbf w=N(mathbf m_1-mathbf m_2), ]

由于 (mathbf S_ ext Bmathbf w)((mathbf m_1-mathbf m_2)) 同向,且不失一般性地,我们可以对训练数据进行平移预处理,使得 (mathbf m=mathbf 0) ,从而得到

[mathbf wpropto mathbf S_ ext W^{-1}(mathbf m_2-mathbf m_1), ]

这等同于在Fisher判别中得到的结果。基于误差评判标准,分类时,若 (mathbf w^ ext Tmathbf x>0) ,则将其划为类 (mathcal C_1)

6 下面考虑多分类情形下的Fisher判别。这里有个假设,样本空间的维度 (D) 大于需要分类的类别数 (K)(D>K))。基本的思路是相同的,我们想将 (D) 维样本空间的分类问题转化为 (D^prime) 维空间中的分类问题,该空间又称特征空间。同样地,我们希望类内方差小,类间距离远。假设投影矩阵为 (mathbf W^ ext T) ,对于样本 (mathbf x) ,其特征向量为 (mathbf W^ ext Tmathbf x)(mathbf W^ ext T) 的各行分别将 (mathbf x) 映射到特征空间中某维的分量值。类内方差记为各类类内方差(高维,实际是协方差)之和,即

[mathbf S_ ext W=summathbf S_k, ]

类间距离 (mathbf S_ ext B) 间接定义为总方差 (mathbf S_ ext T) 与类内方差之差,即

[mathbf S_ ext B=mathbf S_ ext T-mathbf S_ ext W=sum (mathbf x_n-mathbf m)(mathbf x_n-mathbf m)^ ext T-summathbf S_k, ]

实际上,(mathbf S_ ext B)

[mathbf S_ ext B=sum N_k(mathbf m_k-mathbf m)(mathbf m_k-mathbf m)^ ext T. ]

在特征空间中,记上述各量分别为 (mathbf s_ ext B)(mathbf s_ ext W) ,不难得到 (mathbf s=mathbf Wmathbf Smathbf W^ ext T)
一个Fisher判别尺度是

[J(mathbf W)= ext{Tr}(mathbf s_ ext W^{-1}mathbf s_ ext B), ]

最优化的投影矩阵由 (mathbf S_ ext W^ ext{-1}mathbf S_ ext B) 的最大的 (D^prime) 个特征值所对应的特征向量确定(该矩阵是 (D) 维的)。
假设我们需要面对的是 (K) 分类问题,显然可以看出矩阵 (mathbf S_ ext B(D imes D)) 的秩不超过 (K-1)

7 现在考虑除一般线性判别模型、Fisher线性判别模型外的第三类星星判别模型。它适用于解决二分类问题,样本 (mathbf x) 首先经固定的非线性映射函数 (oldsymbol{phi}(cdot)) 映射到特征 (oldsymbolphi(mathbf x)) ,再使用广义线性模型

[y(mathbf x)=f(mathbf w^ ext Toldsymbolphi(mathbf x)), ]

这里激活函数 (f(cdot)) 是阶跃函数(不连续)。
该模型也即感知机模型。
很自然的想法是通过最小化某个误差函数确定 (mathbf w) ,例如误分类样本数。由于激活函数的特性,通过微分方法不可求解此问题。为此引入感知机准则作为误差函数,首先将二分类问题中样本的目标值分别标记为 (+1)(-1) ,那么我们希望使属于类别 (mathcal C_1) 的样本 (mathbf x_n) 满足 (mathbf w^ ext Toldsymbolphi(mathbf x_n)>0) ,属于类别 (mathcal C_2) 的样本 (mathbf x_n) 满足 (mathbf w^ ext Toldsymbolphi(mathbf x_n)<0) ;即 (mathbf w^ ext Toldsymbolphi(mathbf x_n)t_n>0) ,从而我们不妨尝试最大化不等式左端的内容,并假设其可加,得到可最小化的目标误差函数

[E_P(mathbf w)=-sum mathbf w^ ext Toldsymbolphi_{n:ninmathcal M}t_n, ]

注意上式中只有误分类的样本。误差函数在 (mathbf w) 空间中是分段线性的,试想在 (mathbf w) 的某个邻域,分类结果不变,但 (E_P)(mathbf w) 的线性函数。
使用随机梯度下降(SGD)更新(mathbf w)

[mathbf w^{( au+1)}leftarrowmathbf w^{( au)}-eta abla E_P(mathbf w)=mathbf w^{( au)}+etaoldsymbolphi_nt_n. ]

感知机收敛定理说明,如果二分类问题是完全可分的,那么执行感知机算法(SGD)可在有限步内解决该问题。实际上,可能会需要很多步,以至于不能确定是否完全可分(还是慢速收敛)。

2 概率生成模型


1 继线性判别模型之后,下面将要探讨的是产生线性决策边界的概率分类模型。

一般来说,用于解决分类问题的模型包括判别模型和生成模型。

为此,我们需要对数据的分布(样本空间中样本的分布)进行假设;更具体地,对类别条件概率以及类别先验概率进行建模。在二分类情境下,后验概率可写成

[egin{aligned} p(mathcal C_1|mathbf x)=&frac{p(mathcal C_1,mathbf x)}{p(mathbf x)}=frac{p(mathcal C_1)p(mathbf x|mathcal C_1)}{p(mathcal C_1)p(mathbf x|mathcal C_1)+p(mathcal C_2)p(mathbf x|mathcal C_2)}\=& frac{1}{1+frac{p(mathcal C_2)p(mathbf x|mathcal C_2)}{p(mathcal C_1)p(mathbf x|mathcal C_1)}}=frac{1}{1+exp(-a)}\=& sigma(a), end{aligned}]

其中

[a=lnfrac{p(mathbf x,mathcal C_1)}{p(mathbf x,mathcal C_2)}=lnfrac{p(mathcal C_1|mathbf x)}{p(mathcal C_2|mathbf x)}=lnfrac{p(mathcal C_1|mathbf x)}{1-p(mathcal C_1|mathbf x)}, ]

后验概率的比值又称为几率,从而 (a) 就是所谓的对数几率(log odds)。这里 (sigma(a)) 即逻辑斯蒂(S型)函数, (a(sigma)) 即logit函数。
对于多分类问题,后验概率为

[p(mathcal C_k|mathbf x)=frac{p(mathcal C_k)p(mathbf x|mathcal C_k)}{sum p(mathcal C_j)p(mathbf x|mathcal C_j)}=frac{exp(a_k)}{sumexp(a_j)}, ]

这时

[a_k=ln p(mathcal C_k)p(mathbf x|mathcal C_k). ]

这里规范化的指数函数即softmax函数。
值得注意的是,这里 (a(mathbf x))(a_k(mathbf x)) 均应是 (mathbf x) 的(线性)函数。

2 首先,最自然地,用高斯分布对类别条件概率建模;此外,增加假设,即各类别条件高斯分布中协方差(矩阵)相同,从而,类别 (mathcal C_k) 的条件概率为

[p(mathbf x|mathcal C_k)=frac{1}{(2pi)^{D/2}|mathbfSigma|^{1/2}}expleft{-frac{1}{2}(mathbf x-oldsymbolmu_k)^ ext TmathbfSigma^{-1}(mathbf x-oldsymbolmu_k) ight}. ]

回到二分类问题,在那里,我们给出了 (a(mathbf x)) 的表达式

[a(mathbf x)=lnfrac{p(mathcal C_1)p(mathbf x|mathcal C_1)}{p(mathcal C_2)p(mathbf x|mathcal C_2)}, ]

带入类别条件分布表达式,有

[egin{aligned} a(mathbf x)=&lnfrac{p(mathcal C_1)}{p(mathcal C_2)}-frac{1}{2}left((mathbf x-oldsymbolmu_1)^ ext TmathbfSigma^{-1}(mathbf x-oldsymbolmu_1)-(mathbf x-oldsymbolmu_2)^ ext TmathbfSigma^{-1}(mathbf x-oldsymbolmu_2) ight)\=& lnfrac{p(mathcal C_1)}{p(mathcal C_2)}-frac{1}{2}left[mathbf x^ ext TmathbfSigma^{-1}(oldsymbolmu_2-oldsymbolmu_1)+(oldsymbolmu_2^ ext T-oldsymbolmu_1^ ext T)mathbfSigma^{-1}mathbf x+oldsymbolmu_1^ ext TmathbfSigma^{-1}oldsymbolmu_1-oldsymbolmu_2^ ext TmathbfSigma^{-1}oldsymbolmu_2 ight]\=& lnfrac{p(mathcal C_1)}{p(mathcal C_2)}+left(mathbfSigma^{-1}(oldsymbolmu_1-oldsymbolmu_2) ight)^ ext Tmathbf x-frac{1}{2}left(oldsymbolmu_1^ ext TmathbfSigma^{-1}oldsymbolmu_1-oldsymbolmu_2^ ext TmathbfSigma^{-1}oldsymbolmu_2 ight), end{aligned}]

从而 (a(mathbf x))(mathbf x) 的线性函数,
可记作

[a(mathbf x)=mathbf w^ ext Tmathbf x+w_0. ]

由于在高斯分布中同协方差的假设,生成模型在样本空间中判别边界是线性的。对于多分类情形,由于关系的只是决策边界

[p(mathcal C_k|mathbf x)=p(mathcal C_j|mathbf x)longleftrightarrow a_k=a_j, ]

从而使用 (a_k^prime(mathbf x)) 替换 (a_k(mathbf x)) 并将 (mathbf x) 判定为 (mathcal C_k) 类当且仅当 (a_k^prime(mathbf x)>a_j^prime(mathbf x), k eq j) 得到相同的判决边界,此时

[a_k^prime(mathbf x)=left(mathbfSigma^{-1}oldsymbolmu_k ight)^ ext Tmathbf x-frac{1}{2}oldsymbolmu_k^ ext TmathbfSigma^{-1}oldsymbolmu_k+ln p(mathcal C_k), ]

(mathbf x) 的线性函数。
如果放弃了同协方差假设,该模型将产生关于 (mathbf x) 的二次判决边界。

3 既然有了利用贝叶斯方法通过计算后验概率判定 (mathbf x) 所属类别的模型,下面需要做的就是估计模型中各项参数,包括先验概率、类别均值以及共享协方差(矩阵)。这里考虑使用最大似然概率求解这些待定参数。
先来考虑二分类的情形,类别条件概率依然假设为同协方差的高斯分布。训练数据为 ({mathbf x_n,t_n}) ,当(t_n=1)时, (mathbf x_n) 所属类别为 (mathcal C_1) ;当 (t_n=0) 时, (mathbf x_n) 所属类别为 (mathcal C_2) 。并记先验概率 (p(mathcal C_1)=pi) ,从而 (p(mathcal C_2)=1-pi) 。于是

[p(mathcal C_1,mathbf x)=p(mathcal C_1)p(mathbf x|mathcal C_1)=pimathcal N(mathbf x_n|oldsymbolmu_1,mathbfSigma), ]

[p(mathcal C_2,mathbf x)=p(mathcal C_2)p(mathbf x|mathcal C_2)=(1-pi)mathcal N(mathbf x_n|oldsymbolmu_2,mathbfSigma), ]

似然概率为

[egin{aligned} p(mathbf t,mathbf X|pi,mathbfSigma,oldsymbolmu_1,oldsymbolmu_2)=&prod p^{t_n}(mathcal C_1,mathbf x)p^{1-t_n}(mathcal C_2,mathbf x) \=&prod left[pimathcal N(mathbf x_n|oldsymbolmu_1,mathbfSigma) ight]^{t_n}left[(1-pi)mathcal N(mathbf x_n|oldsymbolmu_2,mathbfSigma) ight]^{1-t_n} end{aligned}]

从而

[ln p(mathbf t)=sum t_nlnleft[pimathcal N(mathbf x_n|oldsymbolmu_1,mathbfSigma) ight]+(1-t_n)ln[(1-pi)mathcal N(mathbf x_n|oldsymbolmu_2,mathbfSigma)], ]

[frac{partial ln p}{partial pi}=sum frac{t_n}{pi}-frac{1-t_n}{1-pi}, ]

令其为零,得对 (pi) 的最大似然估计为

[pi=sum t_n/N=frac{N_{mathcal C_1}}{N_{mathcal C_1}+N_{mathcal C_2}}. ]

由于

[frac{partial ln p}{partial oldsymbolmu_1}=sum-t_n{mathbfSigma^{-1}}^ ext T(mathbf x-oldsymbolmu_1), ]

令其为零,得 (oldsymbolmu_1) 的最大似然估计为

[oldsymbolmu_1=frac{summathbf x^{(1)}}{N_1}, ]

利用对称性,有 (mathbf mu_2) 的最大似然估计值为

[oldsymbolmu_2=frac{summathbf x^{(2)}}{N_2}. ]

最后考虑协方差最大 (mathbfSigma) 的最大似然估计,由于

[egin{aligned} frac{partialln p}{partialmathbfSigma^{-1}}=&-frac{1}{2}sum t_nleft(frac{partial ln |mathbfSigma|}{partial mathbfSigma^{-1}}+frac{partial (mathbf x-oldsymbolmu_1)^ ext TmathbfSigma^{-1}(mathbf x-oldsymbolmu_1)}{partialmathbfSigma ^{-1}} ight)+(1-t_n)left(frac{partial ln |mathbfSigma|}{partial mathbfSigma ^{-1}}+frac{partial (mathbf x-oldsymbolmu_2)^ ext TmathbfSigma^{-1}(mathbf x-oldsymbolmu_2)}{partialmathbfSigma^{-1}} ight)\=&-frac{1}{2}left[Nfrac{partialln|mathbfSigma|}{partialmathbfSigma^{-1}}+sumfrac{ ext{Tr}partial (mathbf x^{(1)}-oldsymbolmu_1)^ ext TmathbfSigma^{-1}(mathbf x^{(1)}-oldsymbolmu_1)}{partial mathbfSigma^{-1}}+sumfrac{partial ext{Tr} (mathbf x^{(2)}-oldsymbolmu_2)^ ext TmathbfSigma^{-1}(mathbf x^{(2)}-oldsymbolmu_2)}{partial mathbfSigma^{-1}} ight]\=& frac{N}{2}mathbfSigma-frac{1}{2}frac{1}{partialmathbfSigma^{-1}}partial ext{Tr}mathbfSigma^{-1}left(sum(mathbf x^{(1)}-oldsymbolmu_1)^ ext T(mathbf x^{(1)}-oldsymbolmu_1)+sum(mathbf x^{(2)}-oldsymbolmu_2)^ ext T(mathbf x^{(2)}-oldsymbolmu_2) ight)\=& frac{N}{2}mathbfSigma-frac{1}{2}frac{1}{partialmathbfSigma ^{-1}}partial ext{Tr}mathbfSigma^{-1}(N_1mathbf S_1+N_2mathbf S_2)\=& frac{N}{2}mathbfSigma-frac{1}{2}(N_1mathbf S_1^ ext T+N_2mathbf S_2^ ext T), end{aligned}]

令其为零,得

[mathbfSigma =frac{N_1}{N}mathbf S_1+frac{N_2}{N}mathbf S_2, ]

(mathbfSigma) 的最大似然估计是两类类内协方差的加权平均。
上述推论可推广至多分类情形。

4 现在考虑样本空间是离散点的情形,先考虑样本各维取值在 ({0,1}) 中的情况。假设样本向量长度为 (D) ,生成方法要对样本分布情况建模。假设我们考虑的是互不相同的样本点,显然空间中共有 (2^D) 个位置可取,考虑到样本在所有位置上的概率之和为 (1) 这一约束条件,实际上需要 (2^D-1) 个参数来确定。进一步假设样本空间各维取值互相独立(朴素贝叶斯假设),可以解决参数数量爆炸的问题,从而只需对 (D) 维分别建模即可。假设属于类别 (mathcal C_k) 的样本 (mathbf x)(i) 维上取值为 (1) 的概率为 (mu_{ki}) ,从而向量 (mathbf x) 的条件类别概率为

[p(mathbf x|mathcal C_k)=prod mu_{ki}^{x_i}(1-mu_{ki})^{1-x_i}, ]

利用式 (a_k=ln p(mathcal C_k)p(mathbf x|mathcal C_k)) ,得

[a_k=ln p(mathcal C_k)+sum x_ilnmu_{ki}+(1-x_i)ln(1-mu_{ki}), ]

从而满足线性条件。

5 实际上只要对类别条件分布的假设属于指数族分布,引入缩放系数(s),类别条件分布如下

[p(mathbf x|oldsymbollambda_k,s)=frac{1}{s}h(frac{mathbf x}{s})g(oldsymbollambda_k)expleft{frac{1}{s}oldsymbollambda_k^ ext Tmathbf x ight}, ]

可以验证,此时 (a(mathbf x)) 仍然是关于 (mathbf x) 的线性函数。

3 概率判别模型


1 在之前讨论的概率生成模型中,我们首先对样本的概率分布建模,通过似然估计确定模型参数,再通过计算后验概率,利用softmax或sigmoid函数确定样本所属类别。逻辑路线是概率分布模型估参 ( ightarrow) 计算后验概率 ( ightarrow) 划分样本类别。当然我们可以跳过对样本分布进行建模,直接对对数几率(log odds)或后验概率进行建模,使用似然估计直接确定该模型的参数。这种方法即概率判别模型。有一种高效算法可以完成此任务,即迭代重加权最小平法误差(最小二乘)算法(Iterative Reweighted Least Squares, IRLS)。

2 首先考虑二分类问题。为了对后验概率直接建模,将sigmoid函数中的对数几率直接表示为样本 (mathbf x) 的特征 (oldsymbolphi) 的线性函数,从而

[p(mathcal C_1|oldsymbolphi)=y(oldsymbolphi)=sigma(mathbf w^ ext Toldsymbolphi), ]

显然这里 (oldsymbolphi) 是增广后的形式。此模型即logistic回归模型。这种概率判别模型相比较生成模型,一个明显的优点是待调参数少(得多)。
现在将训练数据记为 ({oldsymbolphi_n,t_n}),其中(t_nin{0,1}) ;使用似然概率的最大化调节判别模型的参数,从而似然概率为

[p(mathbf t|mathbf w;mathbfPhi)=prod y_n^{t_n}(1-y_n)^{1-t_n}, ]

将误差函数记为似然概率对数的相反数(实际上这也是样本数据集的交叉熵),

[E(mathbf w)=-sumleft(t_nln y_n+(1-t_n)ln(1-y_n) ight), ]

从而关于 (mathbf w) 的导数为

[egin{aligned} frac{partial E}{partialmathbf w}=&-sum t_nfrac{sigma^prime(oldsymbolphi_n)}{sigma(oldsymbolphi_n)}+sum(1-t_n)frac{sigma^prime(oldsymbolphi_n)}{1-sigma(oldsymbolphi_n)}\=& -sum t_n(1-sigma(oldsymbolphi_n))oldsymbolphi_n+sum(1-t_n)sigma(oldsymbolphi_n)oldsymbolphi_n\=& sum(y_n-t_n)oldsymbolphi_n. end{aligned}]

值得注意的是,若无其他限制条件,若源数据在特征空间线性可分,那么 (mathbf w ightarrow infty) ,这是因为, (mathbf w) 总可以在已经正确分类所有样本时增大数值以产生更高的似然概率。似然模型会更易受到过拟合的影响。我们可以增加正则项或提供关于 (mathbf w) 的先验信息,从而最大化 (mathbf w) 的后验概率来避免这种情形。

3 在logistic回归中,误差函数是关于 (mathbf w) 的凸函数,尽管由于 (sigma(cdot)) 函数的存在,无法给出封闭解。但可通过牛顿迭代法(Newton-Raphson method/Newton^primes Method)求解。权值更新规则如下

[mathbf wleftarrowmathbf w-left(frac{partial^2 E}{partial mathbf wpartialmathbf w^ ext T} ight)^{-1}frac{partial E}{partialmathbf w}. ]

由于

[frac{partial E}{partialmathbf w}= abla E(mathbf w)=sum(y_n-t_n)oldsymbolphi_n=mathbfPhi^ ext T(mathbf y-mathbf t), ]

[egin{aligned} frac{partial^2E}{partialmathbf wpartialmathbf w^ ext T}=& abla abla E(mathbf w)=mathbf H=frac{partialmathbfPhi^ ext T(mathbf{y-t})}{partialmathbf w^ ext T}\=& mathbfPhi^ ext Tfrac{partialmathbf y}{partialmathbf w^ ext T}=mathbfPhi^ ext Tmathbf RmathbfPhi, end{aligned}]

其中

[mathbf R= ext{diag}(y_1(1-y_1),...,y_i(1-y_i),...). ]

从而牛顿迭代规则为

[egin{aligned} mathbf wleftarrow& mathbf w-mathbf H^{-1} abla E(mathbf w)\=& mathbf w-(mathbfPhi^ ext Tmathbf RmathbfPhi)^{-1}mathbfPhi^ ext T(mathbf{y-t})\=& (mathbfPhi^ ext Tmathbf RmathbfPhi)^{-1}mathbfPhi^ ext Tmathbf R(mathbf Phimathbf w-mathbf R^{-1}(mathbf{y-t})). end{aligned}]

4 将概率判别模型推广至多分类问题,使用多分类logisitc回归。后验概率形式为softmax函数,于是

[p(mathcal C_k|oldsymbolphi)=y_k(oldsymbolphi)=frac{exp(a_k)}{sumexp(a_j)}, ]

其中

[a_k=mathbf w_k^ ext Toldsymbolphi. ]

仍然使用最大似然概率的方法求参,目标向量使用1-K编码表示,从而似然概率

[p(mathbf T|mathbf W,mathbfPhi)=prod_nprod_k y_{nk}^{t_{nk}}(mathbfphi), ]

从而交叉熵误差函数写为对数似然概率的相反数

[E(mathbf W)=-sum_nsum_k t_{nk}ln y_{nk}(oldsymbolphi). ]

5 考虑一般性的概率判别下的广义线性模型,在二分类问题上

[p(t=1|a)=f(a), ]

其中 (a=mathbf w^ ext Toldsymbolphi) ,且 (f(cdot)) 是激活函数。
在判别样本所属类别时,对于特征 (mathbfphi) ,如果 (a=mathbf w^ ext Toldsymbolphigeq heta) ,将 (oldsymbolphi) 归类为类别 (t=1) ;否则归类为 (t=0) 。除了将 ( heta) 固定为某一常数外,我们还可以将其视为某个随机变量,例如我们假设 ( hetasim mathcal N(0,1)) ,从而

[egin{aligned} f(a)=&p(t=1|a)\=& int_{-infty}^a ext{d} heta p( heta)\=& Phi(a), end{aligned}]

这就引出了所谓的新的激活函数,probit函数 (Phi(cdot)) ,即标准正态分布的分布函数。与sigmoid作为激活函数相比,probit函数更易受离群值影响。

6 现在对上面讨论的概率判别模型作以总结归纳,给出一般性的结论。这里需要给出两个假设,其一是假设样本目标变量(而不是概率生成模型中样本本身的分布)服从指数族分布;此外假设激活函数为规范链接函数(canonical link function)的形式。将样本目标变量分布写成如下形式

[p(t|eta,s)=frac{1}{s}hleft(frac{t}{s} ight)g(eta)expfrac{eta t}{s}, ]

考虑到概率分布的约束条件

[int p(t|eta,s) ext{ d}t=1longleftrightarrow g(eta)int hleft(frac{t}{s} ight)expfrac{eta t}{s} ext{ d}t=s, ]

(eta) 求导,有

[g^prime(eta)int hleft(frac{t}{s} ight)expfrac{eta t}{s} ext{ d}t+g(eta)int hleft(frac t s ight)frac{t}{s}expfrac{eta t}{s} ext{ d}t=0, ]

考虑到

[mathbb E[t|eta,s]=int p(t|eta,s)t ext{ d}t, ]

带入上式,得

[mathbb E[t|eta,s]=-frac{g^prime(eta)}{g(eta)}s=-sfrac{ ext{d}}{ ext deta}ln g(eta). ]

将样本目标值期望记为(y),从而

[yequiv -sfrac{ ext dln g(eta)}{ ext deta}=psi^{-1}(eta). ]

广义线性模型输出

[y=f(mathbf w^ ext Toldsymbolphi), ]

其中 (f(cdot)) 是激活函数(机器学习), (f^{-1}(cdot)) 是链接函数(统计学)。
对数似然概率为(作为 (eta) 的函数,注意对于每个特征 (oldsymbolphi_n)(eta_n)(oldsymbolphi_n) 的函数)

[ln p(mathbf t|eta, s)= ext C+sum ln g(eta_n)+frac{eta_n t_n}{s}, ]

从而

[egin{aligned} frac{partialln p}{partialmathbf w}=&sumfrac{ ext dln g(eta_n)}{ ext deta_n}frac{partial eta_n}{partialmathbf w}+frac{t_n}{s}frac{partialeta_n}{partialmathbf w}\=& sumleft(frac{t_n-y_n}{s} ight)psi^prime(y_n)f^prime(mathbf w^ ext Toldsymbolphi_n)oldsymbolphi_n, end{aligned}]

对于一般性的链接函数 (psi(y)) ,如果我们调整 (g(cdot)) 使得

[f^{-1}(y)equiv psi(y), ]

那么 (f(psi)=y) ,从而 (f^prime(psi)psi^prime(y)=1) ,再由于 (f(mathbf w^ ext Toldsymbolphi)=y) ,于是 (mathbf w^ ext Toldsymbolphi=f^{-1}(y)=psi(y)) ,于是

[psi^prime(y_n)f^prime(mathbf w^ ext Toldsymbolphi_n)=1, ]

带入对数似然概率对 (mathbf w) 的梯度,有

[frac{partialln p}{partialmathbf w}=frac 1 ssum(t_n-y_n)mathbfphi_n. ]

从而误差函数的梯度满足:每个样本对其贡献是特征向量拉伸某个倍数,这个倍数即目标值与当前模型输出值之差。

4 拉普拉斯逼近


1 由于高斯函数的良性质,在某些时候我们希望对一般性质的函数作高斯近似,此过程也称拉普拉斯逼近(近似)。在单变量情形下,考虑在原函数的极大值点进行二阶泰勒展开得到近似的高斯函数。具体地,记需近似的概率密度函数为 (p(z))

[p(z)=frac{1}{Z}f(z), ]

这里(Z)是独立于(z)的规范化系数。假设(z_0)是函数的极大值点(mode),从而 (ln f(z))(z_0) 处的二阶泰勒展开

[ln f(z)simeq ln f(z_0)+frac{1}{2}left(ln f(z_0) ight)^{primeprime}(z-z_0)^2, ]

(A=-left(ln f(z_0) ight)^{primeprime}),从而

[f(z)simeq f(z_0)exp{left(-frac{A}{2}(z-z_0)^2 ight)}, ]

此时 (f(cdot)) 具备了高斯函数的形式,考虑将其规范化得到 (p(cdot)) 的近似 (q(cdot))

[q(z)=sqrt{frac{A}{2pi}}expleft(-frac A 2(z-z_0)^2 ight)^2. ]

这里对于(z_0)的选取有两个要求,其一是作为 (ln f(cdot)) 驻点,从而展开式消去一次项;其二是二阶导为负,从而使得 (A>0)

5 贝叶斯逻辑斯蒂回归


原文地址:https://www.cnblogs.com/astoninfer/p/9278610.html