PRML 和 ESL 的学习基本上是学十得一。稳扎稳打再来一次

分类的线性模型

在本章中我们考虑分类的线性模型。所谓分类线性模型，是指决策面是输入向量x的线性函数。在本章中讨论的演算法同样适用于下面的情形：我们对输入变数进行一个固定的非线性变换，这个变换使用一个基函数向量 phi(x) 。

4.1 判别函数

判别函数是一个以向量x为输入，把它分配到K个类别中的某一个类别(记为 C_{k} )的函数。在本章中我们集中精力于线性判别函数，即那些决策面是超平面的判别函数。

接下来我们介绍三种学习先行判别函数的参数的方法：最小平方的方法、Fisher线性判别函数、感知器演算法。

4.1.1 二分类

线性判别函数的最简单的形式是输入向量的线性函数，即：

y(x) = w^{T}x + w_{0}

其中w被称为权向量， w_{0} 被称为偏置，偏置的相反数有时被称为阈值。如果x是决策面内的一个点，那么 y(x)=0 ，因此远点到决策面的垂直距离为：

frac{w^{T}x}{||w||} = - frac{w_{0}}{||x||}

因此我们看到偏置参数 w_{0} 确定了决策面的位置。

4.1.2 多分类

K类判别函数由K个现行函数组成，形式为：

y_{k}(x) = w_{k}^{T}x + w_{k0}

对于点x，如果对于所有的 j eq k 都有 y_{k}(x) > y_{j}(x) ，那么就把它分到 C_{k} 。于是类别 C_{k} 和 C_{j} 之间的决策面为 y_{k}(x) = y_{j}(x) ，并且对应于一个(D-1)维超平面，形式为：

(w_{k} - w_{j})^{T}x + (w_{k0} - w_{j0}) = 0

这样的判别函数的决策区域总是单连通的，并且是凸的。

4.1.3 用于分类的最小平方方法

每个类别 C_{k} 由我们自己的线性模型描述，我们可以很容易的把这些向量聚集在一起表示，即

y(x) = ilde{W}^{T} ilde{x}

其中 ilde{W} 是一个矩阵，第k列由D+1维向量 ilde{w_{k}} = (w_{k0}, w_{k}^{T})^{T} 组成， ilde{x} 是对应的增广输入向量 (1, x^{T})^{T} ，它带有一个虚输入 x_{0}=1 表示。这样，一个新的输入x被分配到输出 y_{k} = ilde{w}^{T} ilde{x} 最大的类别中。

我们现在通过最小化平方和误差函数来确定参数矩阵 ilde{W} 。平方和误差函数可以写成：

E_{D}( ilde{W}) = frac{1}{2}Trleft{ ( ilde{X} ilde{W} - T)^{T}( ilde{X} ilde{W} - T) ight}

令上式关于 ilde{W} 的导数等于零，整理可以得到 ilde{W} 的解，形式为：

ilde{W} = ( ilde{X}^{T} ilde{X})^{-1} ilde{X}^{T}T = ilde{X}^{dag}T

其中 ilde{X}^{dag} 是矩阵的伪逆矩阵，这样我们就得到了判别函数，形式为：

y(x) = ilde{W}^{T} ilde{x} = T^{T}( ilde{X}^{dag})^{T} ilde{x}

最小平方的方法对于判别函数的参数给出了精确地解析解。但是即使作为一个判别函数，它仍然有很严重的问题。最直观的问题是缺少对于离群点的鲁棒性。除此之外，由于最小平方法对应于高斯条件分布假设下的最大似然法，当数据点不满足该假设，如二值目标时其效果会很差。

4.1.4 Fisher线性判别函数

我们可以从维度降低的角度考察线性分类模型。首先考察二分类的情形。假设我们由一个D维输入向量x，然后使用某种变换 y = w^{T}x 投影到一维。如果我们在y上设置一个阈值 w_{0} ，然后把 y leq -w_{0} 的样本分为 C_{1} 类，其与样本分为 C_{2} 类，那么我们就得到了之前讨论的线性分类器。

为了避免数据在投影空间的相互重叠，我们可以调整权向量w使得两类数据样本的均值差最大化。即:

max(m_{2} - m_{1}) = w^{T}(mathbf{m_{2} - m_{1}})

其中 m_{k} = w^{T}m_{k} 是来自 C_{k} 的投影数据的均值。但是通过增大w这个表达式可以任意大，因此我们将限制w为单位长度，即 sum_{i}w_{i}^{2} = 1 。使用拉格朗日乘数法来进行有限制条件的最大化问题的求解，我们可以发现 w propto(m_{2} - m_{1}) 。

然后对于上述方法，当我们投影到连接它们的均值的直线上时，就产生一定程度的重叠。如果概率分布的协方差矩阵与对角化矩阵差距较大就会出现这种问题，因此Fisher提出的思想是最大化一个函数，这个函数能够让类均值的投影分开的较大，同时让每个类别内部的方差较小，从而最小化了类别的重叠。

来自类别 C_{k} 的数据经过变换后的类内方差为：

s_{k}^{2} = sum_{nin C_{k}}(y_{n} - m_{k})^{2}

Fisher准则为：

J(w) = frac{(m_{2} - m_{1})^{2}}{s_{1}^{2} - s_{2}^{2}}

重写上述公式，定义类间协方差矩阵 S_{B} 与类内协方差矩阵 S_{W} ：

S_{B} = (m_{2} - m_{1})(m_{2} - m_{1})^{T}

S_{W} = sum_{nin C_{1}}(x_{n} - m_{1})(x_{n} - m_{1})^{T} + sum_{nin C_{2}}(x_{n}-m_{2})(x_{n} - m_{2})^{T}

J(w) = frac{w^{T}S_{B}w}{w^{T}S_{W}w}

对于上式，我们发现J取最大值的条件为：

(w^{T}S_{B}w)S_{W}w = (w^{T}S_{W}w)S_{B}w

忽略标量因子后得：

w propto S_{W}^{-1}(m_{2} - m_{1})

上式被称为Fisher线性判别函数。虽然严格来说它并不是一个判别函数，但投影数据接下来可以用来构建判别函数(在投影坐标上选择一个阈值，分类即可)。

对于二分类问题，Fisher准则可以看成最小平方的一个特列。

对于多分类问题，根据Fisher思想，我们有很多准则选择方式，其中一种选择是：

J(W) = Tr{s_{w}^{-1}s_{B}}

4.1.7 感知器演算法

它对应于一个二分类模型，这个模型中，输入向量x首先使用一个固定的非线性变换得到一个特征向量 phi(x) ，这个特征向量然后被用于构造一个一般的线性模型，形式为：

y(x) = f(w^{T}phi(x))

其中非线性激活函数 f(*) 是一个阶梯函数，形式为：

f(a) = left{ egin{aligned} +1, ~~~ageq 0 \ -1, ~~~alt 0 end{aligned} ight.

我们采用感知器准则作为我们的误差函数：

E_{P}(w) = -sum_{nin M}w^[T]phi_{n}t_{n}

其中 phi_{n} 和M表示所有误分类模式的集合，总的误差函数的分段线性的。使用梯度下降演算法可以优化权向量。感知收敛定理表明，如果存在一个精确的解(即，如果训练数据线性可分)，那么感知器演算法就可以保证在有限的步骤内找到一个精确解。

4.2 概率生成式模型

现在我们对类条件概率密度 p(x | C_{k}) 和类先验概率分布 p(C_{k}) 建模，然后使用这两个概率密度通过贝叶斯定理计算后验概率密度 p(C_{k} | x) 。

对于二分类问题，类别 C_{1} 的后验概率可以写为sigmoid函数的形式：

p(C_{1} | x) = sigma(a)

a = lnfrac{p(x|C_{1})p(C_{1})}{p(x|C_{2})p(C_{2})}

其中 sigma(a) 是 logistic sigmoid函数，定义为：

sigma(a) = frac{1}{1 + exp(-1)}

对于K>2个类别的情形，我们有：

p(C_{k} | x) = frac{p(x|C_{k})p(C_{k})}{sum_{j}p(x|C_{j})p(C_{j})} = frac{exp(a_{k})}{sum_{j}exp(a_{j})}

a_{k} = ln p((x | C_{k})p(C_{k}))

被称为归一化指数。也被称为 softmax 函数，因为它表示"max"函数的一个平滑版本。

4.2.1 连续输入

现在考虑类条件概率密度是高斯分布，然后求解后验概率的形式。首先假定所有的类别的协方差矩阵相同(假如没这个假设，那么二次项就不会被消去，会得到二次判别函数)。这样类别 C_{k} 的类条件概率为：

p(x | C_{k}) = frac{1}{2pi^{frac{D}{2}}}frac{1}{|Sigma|^{frac{1}{2}}}expleft{ -frac{1}{2}(x-mu_{k})^{T}Sigma^{-1}(x-mu_{k}) ight}

考虑二类问题，此时：

p(C_{1} | x) = sigma(w^{T}x + w_{0})

其中我们定义了：

w = Sigma^{-1}(mu_{1} - mu_{2})

w_{0} = -frac{1}{2}mu_{1}^{T}Sigma^{-1}mu_{1} + frac{1}{2}mu_{2}^{T}Sigma^{-1}mu_{2} + lnfrac{p(C_{1})}{p(C_{2})}

我们看到，高斯概率密度的指数项中，x的二次型消失了(由于协方差矩阵相同导致的)，从而得到了参数为x的线性函数的 logistic sigmoid 函数。最终求得的决策边界对应于后验概率 p(C_{k} | x) 为常数的决策面，因此由x的线性函数给出，从而决策边界在输入空间是线性的。先验概率密度 p(C_{k}) 只出现在偏置参数 w_{0} 中，因此先验改变的效果是平移决策边界，即平移后验概率中的常数轮廓线。

对于K个类别的一般情形，也可以得到类似结论。

4.2.2 最大似然解

在确定类条件概率密度后，我们就能够使用最大似然发确定参数的值，以及先验类概率 p(C_{k}) 。

对于两类情形，似然函数为：

p(mathbf{t}, mathbf{X} | pi, mu_{1}, mu_{2}, Sigma) = prod_{n=1}^{N}[pi N(x_{1} | mu_{1}, Sigma)]^{t_{n}}[(1-pi)N(x_{n} | mu_{2}, Sigma)]^{1-t_{n}}

与之前一样，最大化似然函数的对数比较方便。首先考虑关于 pi 的最大化对数似然函数中与 pi 相关的项为：

sum_{n=1}^{N}{ t_{n}lnpi + (1-t_{n})ln(1-pi) }

令其关于 pi 的导数等于零，整理可得：

pi = frac{1}{N}sum_{n=1}^{N}t_{n} = frac{N_{1}}{N} = frac{N_{1}}{N_{1} + N_{2}}

其中 N_{1} 表示类别 C_{1} 的总数， N_{2} 表示类别 C_{2} 的总数。因此 pi 的最打死然估计就是类别 C_{1} 所占的比例。

同理我们可以求 mu_{1} 的最大化，整理除与 mu_{1} 相关的量并令其导数为零，可得：

mu_{1} = frac{1}{N_{1}}sum_{n=1}^{N}t_{n}x_{n}

这就是属于类别 C_{1} 的输入向量 x_{n} 的均值。同理 mu_{2} 的最大似然解为：

mu_{2} = frac{1}{N_{2}}sum_{n=1}^{N}(1-t_{n})x_{n}

最后考虑协方差矩阵 Sigma 的最大似然解：

Sigma = frac{N_{1}}{N}S_{1} + frac{N_{2}}{N}S_{2}

S_{1} = frac{1}{N_{1}}sum_{nin C_{1}}(x_{n} - mu_{1})(x_{n} - mu_{1})^{T}

S_{2} = frac{1}{N_{2}}sum_{nin C_{2}}(x_{n} - mu_{2})(x_{n} - mu_{2})^{T}

上述结果很容易推广到K类问题，得到参数的最大似然解。

4.2.4 指数族分布

可以看到，上述分布都是指数族分布的成员，因此通过假定类条件概率密度是指数族分布的成员，我们可以得到上述结果的更一般形式。

x的分布可以写为：

p(x | lambda_{k}, s) = frac{1}{s}h(frac{1}{s}x)g(lambda_{k})expleft{frac{1}{s}lambda_{k}^{T}x ight}

其中s是缩放参数，对于K类问题：

a_{k}(x) = frac{1}{s}mathbf{lambda_{k}^{T}x} + ln g(lambda_{k}) + ln p(C_{k})

这又是x的线性函数。

4.3 概率判别模型

判别式方法最大化由条件概率分布 p(C_{k} | x) 定义的似然函数。

4.3.1 固定基函数

到目前为止，我们考虑的都是直接对输入向量x进行分类的分类模型。然而如果我们使用一个基函数向量 phi(x) 对输入变数进行一个固定的非线性变换，所有的这些演算法同样适用。恰当的适用非线性变换能够让后验概率的建模过程更简单。这样固定基函数的模型有著更重要的局限性，但当我们允许基函数自身根据数据进行调节，我们可以解决这些局限性。

4.3.2 logistic 回归

对于二分类情况，在相当一般的假设条件下，类别 C_{1} 的后验概率可以写成作用在特征向量 phi 的线性函数上的 logistic-sigmoid 函数的形式，即：

p(C_{1} | phi) = y(x) = sigma(w^{T}phi)

其中 sigma(a) 是 logistic- sigmoid 函数，这个模型被称为 logistic回归，虽然它是一个分类模型而不是一个回归模型。

我们现在使用最大似然法确定 logistic 回归模型的参数。首先写出似然函数：

p(mathbf{t} | w) = prod_{n=1}^{N}y_{n}^{t_{n}}{1-y_{n}}^{1-t_{n}}

其中 mathbf{t} = (t_{1}, dots, t_{N}) 且 y_{n} = p(C_{1} | phi_{n}) 。

取似然函数的负对数定义一个误差函数：

E(w) = -ln p(mathbf{t} | w) = -sum_{n=1}^{N}{ t_{n}ln y_{n} + (1-t_{n})ln(1-y_{n}) }

其中 y_{n} = sigma(a_{n}) 且 a_{n} = w^{T}phi_{n} 。可以看出上式为交叉熵误差函数。

两侧关于w取误差函数的梯度，我们有：

abla E(w) = sum_{n=1}^{N}(y_{n} - t_{n})phi_{n}

4.3.3 迭代重加权最小平方

我们看到， logistic sigmoid 函数是飞一个非线性的函数，因此不再有解析解了。但误差函数为凸函数，因此有一个唯一的最小值。此外，误差函数可以通过一种高效的迭代方法求出最小值，这种迭代方法基于 Newton-Raphson 迭代最优化框架，使用了对数似然函数的局部近似。

为了最小化函数 E(w) ， Newton-Raphson 对权值更新的形式为：

w^{新} = w^{旧} - mathbf{H}^{-1} abla E(w)

其中 mathbf{H} 是一个 关于w的Hessian矩阵。

将Newton-Raphson 用到 logistic 回归模型的交叉熵误差函数上，得到一阶梯度和二阶梯度为：

abla E(w) = sum_{n=1}^{N}(y_{n} - t_{n})phi_{n} = Phi^{T}(mathbf{y} - t)

H = abla abla E(w) = sum_{n=1}^{N}y_{n}(1-y_{n})phi_{n}phi_{n}^{T} = Phi^{T}RPhi

R_{nn} = y_{n}(1-y_{n})

其中 Phi 是 N imes M 设计矩阵，第n行为 phi_{n}^{T} 。可以看到 Hessian矩阵 H是正定的，因此误差函数是w的一个凸函数，从而有唯一的最小值。这样 logistic 回归模型的 Newton-Raphson 更新公式为：

w^{新} = w^{旧} - (Phi^{T}RPhi)^{-1}Phi^{T}(mathbf{y} - mathbf{t}) = (Phi^{T}RPhi)^{-1}Phi^{T}Rz

z = Phi w^{旧} - R^{-1}(mathbf{y} - mathbf{t})

可以看到更新共识的形式为一组加权最小平房问题的规范方程。由于权矩阵R不是常亮而依赖于w，因此我们必须迭代地应用规范方程。每次使用新的w计算一个修正的R，因此被称为迭代重加权最小平方。

对于多类 logistic 回归，我们可以根据相似流程得到对应的一阶导数和Hessian矩阵。

4.3.5 probit 回归

假设概率密度 p( heta) 是零均值、单位方差的高斯概率密度。对应的累积分布函数：

Phi(a) = int_{-infty}^{a} N( heta | 0, 1) d heta

这被称为逆 probit 函数，它的形状为sigmoid形。使用更一般的高斯分布不会改变模型，只会对w进行重新缩放。

许多用于计算这个函数的数值计算都与下面这个函数紧密相关：

erf(a) = frac{2}{sqrt{pi}}int_{0}^{a}exp(- heta^{2})d heta

它被成为erf 函数或者被称为 error函数。它与逆 probit 函数的关系为：

Phi(a) = frac{1}{2}{ 1 + erf( frac{a}{sqrt{2}})}

基于 probit 激活函数的一般的线性模型被称为 probit 回归。 probit模型的一个重要特性是对离群点的敏感性。

如果假设目标变数的条件分布来自于指数族分布，对应的激活函数选为标准链接函数(链接函数是激活函数的逆)，那么我们有：

abla E(w) = frac{1}{s}sum_{n=1}^{N}{y_{n} - t_{n}}phi_{n}

对于高斯分布， s = eta^{-1} 。对于 logistic 模型 s = 1。

4.4 拉普拉斯近似

拉普拉斯近似的目标是找到定义在一组连续变数上的概率密度的高斯近似。

首先考虑M维空间上变数z的情形，假设分布 p(z) 的定义为：

p(z) = frac{1}{z}f(z)

其中Z是归一化系数。我们假定Z是为止的。在拉普拉斯方法中，目标是寻找一个高斯近似 q(z) ，它的中心位于 p(z) 的众数的位置。第一步是寻找 p(z) 的众数，即寻找一个点 z_{0} 使得 p{}(z_{0}) = 0 。

高斯分布有一个性质，即它的对数是变数的二次函数，于是我们将 ln(z) 以众数 z_{0} 为中心的泰勒展开：

ln f(z) simeq ln f(z_{0}) - frac{1}{2}(z-z_{0})^{T}A(z-z_{0})

其中 M imes M 的 Hessian矩阵A的定义为：

A = - abla ablaln f(z)|{z=z{0}}

两边同时取指数，我们有：

f(z) = simeq f(z_{0})exp left{ -frac{1}{2}(z - z_{0})^{T}A(z-z_{0}) ight}

分布 q(z) 正比于 f(z) ，归一化系数可以通过官产归一化多元高斯分布的标准形式得到，因此：

q(z) = frac{|A|^{frac{1}{2}}}{(2pi)^{frac{M}{2}}}exp left{ -frac{1}{2}(z-z_{0})^{T}A(z-z_{0}) ight} = N(z | z_{0}, A^{-1})

为了应用拉普拉斯近似，我们首先需要寻找众数 z_{0} ，然后计算在那个众数位置上的 Hessian矩阵。在实际应用中，众数通常可以通过运行某种形式的数值最优化演算法得到。

4.5 贝叶斯 logistic 回归

对于 logistic 回归，精确地贝叶斯推断是无法处理的，因此我们考虑使用拉普拉斯近似来处理贝叶斯 logistic回归的问题。

4.5.1 拉普拉斯近似

前面我们知道，为了获得拉普拉斯近似，我们首先要寻找后验概率分布的众数，然后调节一个以众数为中心的高斯分布。这需要计算对数后验概率的二阶导数，等价于寻找 Hessian矩阵。

首先选择高斯分布作为先验概率，而后计算w的后验概率分布，取对数：

ln p(w | t) = -frac{1}{2}(w - w_{0})^{T}S_{0}^{-1}(w - w_{0}) + sum_{n=1}^{N}{ t_{n}ln y_{n} + (1-t_{n})ln(1-y_{n})} + const

为了获得后延概率的高斯近似，我们首先最大化后验概率分布，得到 MAP解 w_{MAP} ，它定义了高斯分布的均值。这样协方差矩阵就是福对数似然函数的二阶导数矩阵的逆矩阵，形式为：

S_{N}^{-1} = - abla abla ln p(w | t) = S_{0}^{-1} + sum_{n=1}^{N}y_{n}(1-y_{n})phi_{n}phi_{n}^{T}

于是后验概率分布的高斯近似的形式为：

q(w) = N(w | w_{MAP}, S_{N})

获得后验概率分布的高斯近似之后，剩下的任务就是关于这个概率分布求积分来进行预测。这里直接给出预测分布的近似：

p(C_{1} | t) = int sigma(a)p(a)d a = intsigma(a)N(a | mu_{a}, sigma_{a}^{2})da


推荐阅读：
查看原文 >>
相关文章