模式识别和机器学习 笔记 第四章 线性分类模型（一）

转载请标明出处： http://fuliang.iteye.com/blog/1060530

在前面的章节，我们已经看到线性回归模型具有很简单的分析性和计算性。我么现在我们讨论这种类似的模型来解决分类问题。分类的目的是给出一个输入向量X，将它赋值为k个离散的类别Ck之一，通常的情景是类别是不想交的，每一个输入只会有一个类别。这样输入空间被分成决策区域，它的边界被称为决策边界。本章我们考虑用于分类的线性模型，也就是说决策边界是关于输入变量x线性函数，它在D维的输入空间中定义了D-1维的超平面。类别可以被线性决策边缘分开的数据集合被称为线性可分。
在回归问题中，我们可以使用实数的向量来表示预测值t，在分类问题，我们可以采用1-of-K的编码模式，t是一个长度为K的向量，如果类别是Cj，那么除了tj为1，其他的元素tk都是0.比如K=5，C2可以表示为t={0,1,0,0,0)T
在第一章我们已经学习了三种不同的方法来解决分类问题，一种是简单的判别函数(discriminant function)，它直接把输入变量x映射的特定的类别。另一比较强大的方式，建模条件分布p(Ck|x)。建模p（ck|x）的方式有两种：一种是直接建模，比如表示为参数模型，然后用训练数据计算出最优的参数，另一用方法是结合类别条件分布p（x|Ck）和先验概率p(Ck)，然后利用贝叶斯公式计算后验概率：
p(Ck|x) = p(x|Ck)p(Ck) / p(x)
我们在本章讨论以上三种方式。

在第三章的线性回归模型中，模型预测函数y（x，w）是一个参数为w的线性函数，在最简单的情况，模型对于输入变量是线性的，具有如下形式: y= wTx + w0,所以y是个实数，对于分类问题我们希望预测离散的类别标签，或者更一般的区间在[0，1]之间的后验概率。我们可以利用一个非线性函数f(.)来将关于w的线性函数进行转换，即y(x) = f(wTx + w0),类别模型y(x)被认为是线性模型的推广，相对于回归模型而言，由于非线性函数f(.)，对于参数已经不是线性的了。这会比回归模型具有更复杂的分析和计算性，但是对于一般的非线性的模型，这个模型相对已经比较简单了。

本章的算法也会讨论想第三章那样固定非线性基本函数，做一个固定的非线性变换。

4.1 判别函数
一个判别函数是将输入向量x映射到一个K个类别之一Ck。本章我们仅限于线性判别函数，他们的决策边缘是一个超平面。为了简化我们先看2类的问题，然后扩展到K>2的情景。
4.1.1 两类问题
最简单的线性判别函数是关于输入向量x的线性函数，即：
y(x) = wTx + w0
w被称为权重向量，w0被称为偏置(bias)，偏置的负数被称为阈值。
对于输入变量x，如果y(x) >= 0那么分类为C1,否则为C2。所以决策边界定义为y(x) = 0,
为D维输入空间中的D-1维超平面。考虑两个点xA和xB，他们都在决策边缘上，那么
y(xA) = y(xB) = 0，wT(xA - xB) = 0,所以向量w正交于决策边缘，所以w决定了决策边缘的方向。如果x是决策边缘上的一点，那么y(x) = 0,那么原点到决策边缘的距离
为wTx/||w|| = - w0 / ||w||
所以偏置(bias)参数w0决定了决策边缘的位置。
任意一点在x和在决策边缘的x_的关系
x = x_ + r * w / ||w||
我们根据及y(x_) = wTx_ + w0 = 0可以得到
r = y(x) / ||w||
可以将向量w和x，进行扩展得到增广向量W=(w0,w) X=(x0,x)
那么y(x) = WX

4.1.2 多类问题：
现在我们考虑K > 2的线性判别函数的扩展。我们可以组合一些两类的判别函数得到K类
的判别函数，但是这会导致一些困难。
如果我们使用K-1个分类器，每一个解决2类问题，这被称为one-versus-the-rest分类器。但是有一些区域没有被分类（见图4.2的例子）。

另一种选择是引入K(k-1)/2个二元分类器，每一个对应一对类别，这被称为one-versus-one分类器。但是仍然有一些区域不能分开（见图4.2）

我们可以考虑一个单个的k-class的一起函数，他组合了K个线性函数：
yk(x) = wkTx + wk0
如果yk(x) > yj(x),j!=k,那么将点x赋值给类Ck。这个在Ck和Cj的决策边界
由yk(x) = yj(x)给出，因此(D-1)维的超平面被定义为：
(wk - wj)Tx + (wk0 - wj0) = 0
这和2-class的决策边缘类似。
这种判别的决策区域是单联通的，并且是凸。考虑两个点xA和xB，他们都在决策边缘Rk上，任何在连接xA和xB的线上的点x^，可以表示为：
x^ = λxA + (1 − λ)xB 其中 0=< λ <= 1
对于线性的判别函数：
yk(x^) = λyk(xA) + (1-λ)yk(xB)
由于xA和xB都在决策区域Rk内，那么对于所有的j != k,
yk(xA) > yj(xA),yk(xB) > yj(xB)
因此yk(x^) > yj(x^)
所以x^也在决策区域内Rk内。所以Rk是单连通并且是凸的。

我们下面将要介绍三种学习线性判别函数的方法：最小二乘法、Fisher线性判别函数，
感知器算法。
4.1.3 用于分类的最小二乘法
我们在第三章看到，我们考虑了关于参数的线性函数的模型，我们使用最小化错误平方函数的方法得到了简单的关于参数的解，因为我们可以可以看一下是否这种方法可以应用于分类问题。
  考虑一般的分类问题，有k个类别，对于目标向量t使用1-of-k的二元编码方式.一种可以证明可以使用最小二乘法的情形是，给定输入向量x的目标值t逼近条件期望E（t|x)。
对于二元编码，条件期望由后验分类概率给出。不幸的是这种概率的逼近非常的差，事实上这种逼近可能会超出（0，1）的区间，由于线性模型有限的灵活性导致的。
  对于每个类Ck都有他们自己的线性模型，所以
yk(x) = wkTx + w0 k=1,...,k。
我们可以写成：
y(x) = WX
其中W = (wk0,wkT)T, X = (1,XT)T
对于新的输入x被赋值为ck，如果yk=WkTXT最大。
我们通过最小化错误平方和，我们可以得出参数矩阵W,就像我们第三章回归中所做的。
对于训练集{xn,tn)，n=1,...,N，我们定义一个矩阵T,他的第n行是向量tnT，矩阵
X的第n行是xTn。那么平方和错误函数可以写成：
Ed(W) = 1/2 Tr{(XW-T)^T(XW-T)
将关于W的导数设置为0，我们得到
W = (WTW)-1X^TT = X† T
其中X† 是矩阵X的pseduo-inverse，因为W可能不是方阵。
这样我们得到了判别函数：
y(x) = WTX = T^T(X†)^Tx.
另外一个有趣的特性是多目标变量的最小二乘法的解，如果训练集每一个目标向量满足某个线性约束 aTtn + b = 0
那么对于末个常量a和b，对于任意x的模型预测值也满足相同的约束
aTy(x) + b = 0
因此如果我们使用k-class的1-of-k的编码模式，那么模型预测具有以下特性，
对于任意的x，y(x)的元素之和是1
但是这个约束并不能将模型的输出解释为概率，因为他们每个值并不一定在（0，1）
之间。

最小二乘法给出了精确的判别函数参数的解，然而判别函数存在很严重的问题。我们已经看到最小二乘法对离群点(outliers)缺乏健壮性，这个同样适应于分类的应用程序。在第7.1.2节我们会讨论几种对于分类可选的错误函数，他们不会遭受现在的困难。

由于我们假设最大似然函数是高斯条件分布，而二元目标向量的分布和高斯分布差别很大。
所以导致最小二乘法的失败。我们通过采取更恰当的概率模型，会得到比最小二乘法更好的分类技术。然而，现在我们继续介绍可选的非概率的参数化的线性分类模型。

4.1.4 Fisher's 线性判别函数
一种线性分类模型的方法被称为降维。首先考虑一下两类问题，假设我们的输入具有D维，我们y=wTx将其映射到一维，那么
如果对y设置一个阈值：当y >= -w0时分类为C1，否则为C2，我们得到了一个标准的线性分类函数。然而，一般的我们映射到一维会丢失很多信息，在D维能够分开的，在一维空间可能会重叠。然而我们可以通过调整w的权重，选择一个映射能够最大化分类的间隔。
我们考虑二类问题类C1有N1个点，类C2有N2个点，所以这两个类的均值向量为：
m1 = 1/N1 * sum(xn) n∈C1
m2 = 1/N2 * sum(xn) n∈C2
当我们映射到w上，最简单的测量类别间隔的方法是映射类的期望的偏离程度，这样我们选择w，去最大化 m2 - m1 = wT(M2 - M1)
其中mk = wT * Mk是类Ck映射的均值。这个表达式可以通过扩大w来任意增大，所以我们限制w具有单位长度，即sum(wi * wi) = 1
可以使用拉格朗日乘子来解决具有约束条件的最大值。我们发现w∝ M2-M1.
4.1.5
4.1.6
4.1.7 感知机算法
另一个线性判别模型的例子是感知机，这个在模式识别的历史上占据了重要的地位。对于2类的问题，输入矩阵首先通过一个固定的非线性函数转换为特征向量矩阵，然后用来构建一个更一般的线性模型的形式：
y(x) = f(wTφ(x))
这个非线性的函数f由分段函数形式给出：
f(a) = if a >= 0 then +1 else -1 end
向量φ(x）包含偏置组件φ0(x） = 1.

在概率的模型中，我们对目标次的编码t∈{0,1}，对于感知机来说使用
t = if c1 then +1 else -1 end
的编码更方便

感知机的参数w可以通过最小化错误函数来决定，一个很自然的错误函数的选择是错误分类的模式的个数。但是这并不是一个简单的算法，因为这是一个分段不连续的常数函数，这种根据错误函数的梯度来跟新w的算法不能适用，因为梯度几乎处处为0。

我们考虑另外的错误函数：感知器标准（perceptron criterion）。我们注意到我们在寻找一个权重矩阵w，它能够使类c1的模式xn满足wT * φ(xn) > 0，在c2中的模式xn满足wTφ(xn) < 0,如果我们使用t∈{-1,+1}的编码方式，那么wT * φ(xn) * tn > 0
如果每一个模式都能够被正确分类，那么错误为0.即努力去最小化
-wT * φ(xn) * tn
Ep(w) = - sum(wT * φ(xn) * tn) where n ∈ M
M表示所有分类错误的模式。
我们可以对错误函数使用梯度算法（stochastic gradient descent algorithm)
权重向量w每次跟新由下面的式子给出：
w(τ +1) = w(τ ) − η∇EP (w) = w(τ ) + ηφn tn
η是学习率。因为我们将w乘以一个常量，函数y(x,w)不会改变，所以我们可以去η为1
我们可以看到：
−w(τ +1)T φn tn = −w(τ )T φn tn − (φn tn )T φn tn < −w(τ )T φn tn
更新w之后错误分类的模式的贡献将会被减少。但是w的修改可能导致前面正确分类的模式被错误分类，所以在这个学习规则不能够保证每个步骤中都减少错误总和的大小。

然而感知机收敛的理论证明如果有一个精确的解，那么感知机器可以在有限的步骤中找到它。
但是有的收敛很慢，我们无法区分不可分的问题和很慢收敛的问题，即使是线性可分的，它也依赖于最初的参数和点的顺序，对于非线性可分的问题，这个算法是不收敛的。

感知机给出概率输出，也不能泛化成为k > 2的分类，这也是感知机的缺点。
Large Margin Classification Using the Perceptron Algorithm给出一个基于投票的感知机器：
训练：
输入： 标记好的训练集<(x1,y1),...,(xm,ym)>,迭代次数T
输入： 权重感知机<(v1,c1),...,(vk,ck)>列表
1.初始化 k = 0, v1 = 0, c1=0
2.重复T次迭代：
1.upto(m) do
  * 计算预测值 y^ = sign(vk * xi)
  * if y^ = y then ck = ck + 1
              else vk+1 = vk + yixi;
                   ck+1 = 1;
                   k = k+ 1
               end
end
预测：
输入：权重感知机<(v1,c1),...,(vk,ck)>列表 和 未标注的实例 x
计算
s = sum(ci * sign(vi * x)) for i = 1..k
y^ = sign(s)


4.2 概率生成模型
我们开始转向概率观点的分类问题，我们通过对数据分布的简单假设，展示如何使用线性决策边缘去建模。
对于二元分类的问题，C1的后验概率：
p(c1|x) = p(x|c1) * p(c1) / p(x|c1) * p(c1) + p(x|c2) * p(c2)
= 1 / 1 + exp(-a) = σ(a)
其中 a = ln( p(x|c1) * p(c1) / p(x|c2) * p(c2) )
σ(a)是logistic sigmoid函数：
σ(a) = 1 / 1 + exp(-a)
我们可以得到：
a = ln ( σ / 1 - σ )
被称为logit函数，他代表了概率比的log值：ln( p(c1|x) / p(c2|x) )

对于多类问题
p(ck|x) = p(x|ck) * p(ck) / sum( p(x|cj) * p(cj) = exp(ak) / sum( exp(aj) )
其中ak = ln( p(x|ck) * p(ck) )

4.2.1连续型输入ian
如果我们假设类别的条件密度是高斯函数，然后导出其后验概率的形式，我们首先假设所有的类别都有都有相同的协方差矩阵，那么类别Ck的条件概率：
f(x|Ck) = 1 / (2π)^D/2 * 1 / |Σ|1/2 exp {-1/2(x-μk)T * Σ^−1 * (x-μk)}
考虑二元分类问题,我们得到：
p(c1|x) = σ(wTx + w0)
其中
w = Σ−1 * (x-μk)
w0 = −1/2 * μ1T * Σ^−1 * μ1 + 1 / 2 * μ2T * Σ^−1 * μ2 + ln p(C1)
p(C2) .
我们可以看到x关于w是线性的，所以决策边缘在输入空间内是线性的。

对于多类问题
ak(x) = wkT + wk0
其中
wk = Σ^−1 * μk
wk0 = −1 / 2 * μkT * Σ^−1 * μk + lnp(Ck)

看到x关于w是线性的，决策边缘在输入空间内是线性的

如果每个类条件概率p(x|Ck)都有自己的协方差矩阵，那么我们将得到x二次函数。

4.2.2 最大似然法
一旦我们有了关于类别的参数化的条件分布p（x|Ck），我们就可以使用最大似然发来求出
参数的值，包括类别的先验概率p（Ck）

我们考虑两类的问题，每一个都具有关于类别的条件密度，他们共享协方差矩阵，假如我们具有数据集{xn, tn}其中n=1,...,N,tn = 1表示类别C1,tn=0表示类C2。我们用p(c1) = π来表示类别的先验概率，所以p(C2) = 1 - π。
那么,对于c1:
p(xn, c1) = p(c1) * p(xn|c1) = π * N(xn|μ1,Σ)
对于c2:
p(xn, c2) = p(c2) * p(xn|c2) = (1 - π) * N(xn|μ2,Σ)
我们得到似然函数：
p(t|π,μ1,μ2) = mult(1..n){ π * N(xn|μ1,Σ) }^tn {(1 - π) * N(xn|μ2,Σ)}^(1-tn)
依赖于π的似然函数
mult(1..n){ tn * lnπ + (1-tn) * ln(1-π) }
我们对π求导，并使其为0，得到
π = 1/N * sum(1..n)tn = N1 / N = N1 / (N1 + N2)
我们现在考虑关于μ1,我们找出和μ1相关的部分,对μ1求导并使其为0得到：
μ1 = 1 / N1 * sum(1..N)tn * xn
μ2 = 1 / N2 * sum(1..N)tn * xn

我们找出和Σ相关的部分,对Σ求导并使其为0得到：
s = N1 / N s1 + N2 / N * s2
s1 = 1/N1 sum(n∈C1){(xn - μ1)(xn - μ1)^T }
s1 = 1/N2 sum(n∈C2){(xn - μ2)(xn - μ2)^T }
Σ = S,表示两个类别协方差的加权平均

我们很容易将其扩展到k类的问题。由于最大似然估计高斯分布不是很鲁棒，所以这种方法
对离群点不是很健壮。

4.2.3 离散的特征
现在我们考虑离散的特征值xi。为了简化我们先看二元的特征值xi ∈ {0,1}，然后在扩展到一般的离散值的情况。如果有D个输入，对于每一个类对应应2^D个元素的表，他的分布包含
2^D-1个独立的变量。由于这和特征数量成指数级增长，我们需要寻找一个更多限制的表示。
我们对Naive Bayes分布假设其对Ck的条件分布，其特征值之间是独立的。所以我们有：
p(x|Ck) = multiple(1..D){μki^xi * (1-μki)^1-xi
每一个类包含D个独立的参数，替换（4.63）我们得到：
ak(x) = sum{1..D}{xi * ln * ki + (l-xi)*ln(1-μki)} + ln p(Ck)
仍然是输入变量xi的线性函数。

4.2.4 指数族分布
我们前面看到，不管高斯分布还是离散输入，后验类概率都是线性模型在logistic sigmoid (K = 2) 或者 softmax (K > 2) activation 函数的推广。
我们通过假设类条件密度p(x|Ck)是指数族分布，我们得到了一个更一般的结果。
在(2.194)我们可以将指数族分布写成：
p(x|λk) = h(x)g(λk)exp{λkTu(x)}.
现在我们考虑限制u（x）= x得到这类分布的子集。
我们引入一个比例参数s，我们获得受限的指数族条件分布的概率密度形式：
p(x|λk, s) = 1/s * h(1/s * x) * g(λk) * exp{1/s * λkT * x}
我们假设每个类别都有自己的参数向量λk，但是我们假设他们共享比例参数s。
  对于两类问题，我们替换这个表达式到类条件概率密度函数，我们发现类的后验概率仍然
是相对于logistic sigmoid的线性函数：
a(x) = (λ1 − λ2)T *x + lng(λ1) − ln g(λ2) + lnp(C1) − ln p(C2).
类似的对于k-类问题。我们得到：
ak(x) = λkＴ x + lng(λk) + lnp(Ck)
仍然是关于ｘ的线性函数。

评论

3 楼 fuliang 2011-11-29  

MainRed 写道

为什么后面的没有接着写呢？我也在读这本书上，给点借鉴吧。

最近没找到时间写笔记，大体上把这本书看了一遍。建议是结合其他的书和论文一起
读，因为这本书有的地方介绍的有点突兀，每一节可以结合相关的论文、其他书籍看看。
当然要吃透这本书，还得靠仔细琢磨。

2 楼 MainRed 2011-11-28  

为什么后面的没有接着写呢？我也在读这本书上，给点借鉴吧。

1 楼 MainRed 2011-11-28  

哥，你在做翻译吗？