第五章 线性分类 Linear Classification

线性分类概念

判别函数、概率生成模型、概率判别模型

逻辑回归、朴素贝叶斯分类器

5.1 分类概述

★回归与分类

在回归中，输入特征被映射到一个或多个连续目标变量。线性回归有简单的闭式解和很好的计算性质。

在分类中，输入特征 $x$ 被 映射到 $K$ 个离散类别之一 $C_k$ 。

★三种分类方法

1 判别函数 Discriminant function

判别函数是一个以向量 $x$ 为输入，把它分配到 $K$ 个类别中的某一个类别（记作 $C_k$）的函数。

直接找到⼀个函数 $f(x)$，把每个输⼊ $x$ 直接映射为类别标签。

例如：Fisher 判别函数，感知机，SVM …

⼆分类问题中， f(·)可能是⼀个⼆元的数值， f = 0表⽰类别C1， f = 1表⽰类别C2

2 概率判别式模型 Probabilistic Discriminative Models

直接对后验概率 $p(C_k|x)$ 建模，再使⽤决策论来确定每个新的输⼊ $x$ 的类别。

例如：logistic 回归、神经网络

比如预测猫狗，是猫则为1，狗为0，则为判别模型，如果设两个分类器，分别输出猫狗的概率，哪个高就分类到哪

3 概率生成式模型 Probabilistic Generative Models

先对类条件密度 $p(C_k|x)$ 和先验类概率分布 $p(C_k)$ 建模，然后再使⽤贝叶斯定理计算后验类概率分布 $p(C_k|x)$

$$p(C_k|x)=\frac{p(x|C_k)p(C_k)}{p(x)}$$

最后，使⽤决策论来确定每个输⼊ $x$ 的类别。

等价地，直接对联合概率分布 $p(x,C_k)$ 建模，再归一化得到后验概率。

例如：朴素贝叶斯分类器

生成式模型可还原出联合概率分布；学习收敛速度更快；存在隐变量时，也可以学习。

判别式模型直接学习后验概率，直接面对预测，学习准确率更高；可简化学习问题 。

生成式模型

$$P(c\mid \mathbf{x})=\frac{P(\mathbf{x},c)}{P(\mathbf{x})}$$

基于贝叶斯定理，有

$$P(c\mid \mathbf{x})=\frac{P(c)P(\mathbf{x}\mid c)}{P(\mathbf{x})}$$

• $P(c)$：样本空间中各类样本所占的比例，可通过各类样本出现的频率估计（大数定理）

• $P(\mathbf{x}\mid c)$：类标记c相对于样本x的“类条件概率” (class-conditional probability), 或称“似然”

• $P(\mathbf{x})$：“证据”（evidence）因子，与类标记无关

线性分类模型

从回归到分类

回归问题：线性回归模型中，模型的预测 $y(x,w)$ 由参数 $w$ 的线性函数给出：

$$y(\mathbf{x})={\mathbf{w}}^T\mathbf{x}+w_0$$

即 $y$ 是一个实数。

分类问题：预测位于区间(0, 1)的后验概率分布。

推⼴：使⽤⾮线性函数f(·)对w的线性函数进⾏变换得到推⼴的线性模型：

$$y(\mathbf{x})=f({\mathbf{w}}^T\mathbf{x}+w_0)$$

$f(\cdot )$ 被称为激活函数（activation function）。

激活函数

决策面

决策面对应于 $y(x)=常数$：

$${\mathbf{w}}^T\mathbf{x}+w_0=常数$$

因此决策面是 $x$ 的线性函数，即使函数 $f(\cdot )$ 是⾮线性函数也是如此。

推广的模线性型

推广的模线性型：不再是参数的线性模型，因为引⼊了⾮线性函数 $f(\cdot )$。计算⽐线性回归模型更加复杂。

线性分类模型

最常见的情况是，类别互不相交： 每个输⼊被分到唯⼀的⼀个类别中。

输⼊空间被划分为不同的决策区域(decision region)，边界被称为决策边界（decision boundary）或者决策面（decision surface）

分类线性模型，是指决策面是输⼊向量x的线性函数，因此被定义为D维输⼊空间中的(D - 1)维超平面。

如果数据集可以被线性决策面精确地分类，那么我们说这个数据集是线性可分的（linearly separable）

例子

1D 数据

2D 数据

3D 数据

5.2 判别函数

判别函数

判别函数是⼀个以向量x为输⼊，把它分配到K个类别中的某⼀个类别（记作Ck）的函数。

线性判别函数

线性判别函数（linear discriminant function），即那些决策⾯是超平⾯的判别函数

• ⼆分类
• 多分类

线性判别函数的几何性质

二分类线性判别函数：

$$y(\mathbf{x})={\mathbf{w}}^T\mathbf{x}+w_0$$

• $w$ 被称为权向量（weight vector）
• $w_0$ 被称为偏置（bias）
• 偏置的相反数有时被称为阈值（threshold）

对于⼀个输⼊向量 $x$，如果 $y(x)\ge 0$，那么它被分到 $C_1$ 中，否则被分到 $C_2$ 中。

对应的决策边界由 $y(x)=0$ 确定，它对应着 $D$ 维空间的⼀个 $(D-1)$ 维的超平⾯。

考虑两个点 $x_A$ 和 $x_B$，两个点都位于决策⾯上：

$$\begin{gathered} y({\mathbf{x}}_A)=y({\mathbf{x}}_B)=0 \\ {\mathbf{w}}^T({\mathbf{x}}_A-{\mathbf{x}}_B)=0 \end{gathered}$$

向量 $w$ 与决策⾯内的任何向量都正交，从⽽ $w$ 确定了决策⾯的⽅向。

如果 $x$ 是决策⾯内的⼀个点，那么 $y(x)=0$，因此从原点到决策⾯的垂直距离为：

$$\frac{{\mathbf{w}}^{\text{T}}\mathbf{x}}{\Vert \mathbf{w}\Vert }=-\frac{w_0}{\Vert \mathbf{w}\Vert }$$

因此我们看到偏置参数 $w_0$ 确定了决策⾯的位置。

此外，我们注意到 $y(x)$ 的值给出了点 $x$ 到决策⾯的垂直距离 $r$ 的⼀个有符号的度量。为了说明这⼀点，考虑任意一点 $\mathbf{x}$ 和它在决策面上的投影 ${\mathbf{x}}_{\perp }$ 上，我们有

$$\mathbf{x}={\mathbf{x}}_{\perp }+r\frac{\mathbf{w}}{\Vert \mathbf{w}\Vert }$$

将这个等式的两侧同时乘以 ${\mathbf{w}}^T$，然后加上 $w_0$，并且使用 $y(\mathbf{x})={\mathbf{w}}^T\mathbf{x}+w_0$ 以及 $y({\mathbf{x}}_{\perp })={\mathbf{w}}^T{\mathbf{x}}_{\perp }+w_0$，我们有：（任意一点 $x$ 到决策⾯的有符号的距离 $r$）

$$r=\frac{y(\mathbf{x})}{\Vert \mathbf{w}\Vert }$$

线性判别函数的决策规则

多分类情形

(1) 1 对其他（one-versus-the-rest）分类器

$K-1$ 个二分类

(2) 1 对 1（one-versus-one）分类器

$\frac{K(K-1)}{2}$ 个二分类

(3) K 类判别函数

$$y_k(x)=w_k^{T}x+w_{k0}$$

如果对于所有的 $j\ne k$ 都有 $y_k(x)>y_j(x)$ ，那么就把它分到 $C_k$。

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

用最小二乘解分类问题？

最小二乘法对于离群点缺少鲁棒性，它的误差函数惩罚了“过于正确”的预测，因为他们在正确的⼀侧距离决策边界太远了。

Fisher 线性判别函数

二分类的Fisher判别函数

当投影到连接均值的直线上时，就有了⼀定程度的重叠。如果类概率分布的协⽅差矩阵与对⾓化矩阵差距较⼤，那么这种问题就会出现。

多分类的Fisher判别函数

感知机

感知机 (Rosenblatt 1962)

推广的线性模型

$$\begin{gathered} y(\mathbf{x})=f\left({\mathbf{w}}^{\mathrm{T}}\varphi (\mathbf{x})\right) \\ f(a)=\{\begin{array}{ll}+1,& a⩾0\\ -1,& a<0\end{array} \end{gathered}$$

误差函数，被称为感知器准则（perceptron criterion）

$$E_{\mathrm{P}}(\mathbf{w})=-\sum _{n\in \mathcal{M}}{\mathbf{w}}^{\mathrm{T}}{\varphi }_n{t}_n$$

where $\mathcal{M}$ denotes the set of all misclassified patterns.

随机梯度下降算法

$${\mathbf{w}}^{(\tau +1)}={\mathbf{w}}^{(\tau )}-\eta \nabla E_{\mathrm{P}}(\mathbf{w})={\mathbf{w}}^{(\tau )}+\eta {\varphi }_n{t}_n$$

模拟生物神经元行为的机器，有与生物神经元相对应的部件，如权重（突触）、偏置（阈值）及激活函数（细胞体），输出为+1或-1。

$$\hat{y}=\{\begin{array}{ll}+1& 当{\mathbf{w}}^T\mathbf{x}>0\\ -1& 当{\mathbf{w}}^T\mathbf{x}\le 0\end{array}$$

感知器的学习过程

感知器算法收敛性的说明

5.3 概率判别式模型

问题提出:一维数据的二分类问题示例

★逻辑回归 Logistic Regression

逻辑回归

其中 𝑔(⋅) 通常称为激活函数(Activation Function)，其作用是把线性函数的值域从实数区间“挤压”到了(0, 1)之间，可以用来表示概率。

公式(3.18)为样本𝒙为正反例后验概率的比值，称为几率(Odds)。几率的对数称为对数几率(Log Odds，或Logit)。

公式(3.17)中等号的左边是线性函数，这样 Logistic 回归可以看作预测值为“标签的对数几率”的线性回归模型。
因此， Logistic回归也称为对数几率回归(Logit Regression)。

参数学习

Logistic回归采用交叉熵作为损失函数，并使用梯度下降法来对参数进行优化

使用交叉熵损失函数，其风险函数为

风险函数ℛ(𝒘)关于参数𝒘的偏导数为

采用梯度下降法，Logistic回归的训练过程为：初始化 ${\mathbf{w}}_0\leftarrow 0$，然后通过下式来迭代更新参数：

Logistic 回归总结

Logistic回归分类模型的三要素：

线性模型

基于梯度下降的参数学习

5.4 概率生成式模型

概率生成式模型

二分类情形

⾸先考虑二分类的情形。类别 ${\mathcal{C}}_1$ 的后验概率可以写成

$$\begin{array}{c}p({\mathcal{C}}_1\mid \mathbf{x})=\frac{p(\mathbf{x}\mid {\mathcal{C}}_1)p({\mathcal{C}}_1)}{p(\mathbf{x}\mid {\mathcal{C}}_1)p({\mathcal{C}}_1)+p(\mathbf{x}\mid {\mathcal{C}}_2)p({\mathcal{C}}_2)}\\ =\frac{1}{1+\exp (-a)}=\sigma (a)\end{array}$$

其中我们定义了

$$a=\ln \frac{p(\mathbf{x}\mid {\mathcal{C}}_1)p({\mathcal{C}}_1)}{p(\mathbf{x}\mid {\mathcal{C}}_2)p({\mathcal{C}}_2)}$$

且 $\sigma (a)$ 是 logistic sigmoid 函数，定义为

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

“sigmoid”的意思是“S形”。这种函数有时被称为“挤压函数”，因为它把整个实数轴映射到了⼀个有限的区间中。这个函数在许多分类算法中都有着重要的作⽤。它满⾜下⾯的对称性

$$\sigma (-a)=1-\sigma (a)$$

这个性质很容易证明。logistic sigmoid的反函数为

$$a=\text{ln}\left(\frac{\sigma }{1-\sigma }\right)$$

被称为 logit 函数。它表⽰两类的概率⽐值的对数 $\ln \left[\frac{p({\mathcal{C}}_1|x)}{p({\mathcal{C}}_2|x)}\right]$，也被称为 log odds 函数。

注意在公式中，我们只是把后验概率写成了⼀个等价的形式，因此 logistic sigmoid 函数的出现似乎相当没有意义。然⽽，假设a(x)的函数形式相当简单，那么这种表⽰⽅法就很有⽤了。我们稍后会考虑a(x)是x的线性函数的情形。这种情况下，后验概率由⼀个通⽤的线性模型确定。

多分类情形

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

$$\begin{array}{rl}p({\mathcal{C}}_k\mid \mathbf{x})=& \frac{p(x\mid {\mathcal{C}}_k)p({\mathcal{C}}_k)}{{\sum }_{j}p(\mathbf{x}\mid {\mathcal{C}}_j)p({\mathcal{C}}_j)}\\ =& \frac{\exp (a_k)}{{\sum }_j\exp (a_j)}\end{array}$$

它被称为归⼀化指数（normalized exponential），可以被当做logistic sigmoid函数对于多类情况的推⼴。

这⾥ $a_k$ 被定义为

$$a_k=\ln p((\mathbf{x}\mid {\mathcal{C}}_k)p({\mathcal{C}}_k))$$

归⼀化指数也被称为 softmax 函数，因为它表⽰“max”函数的⼀个平滑版本。这是因为，如果对于所有的 $j\ne k$ 都有 $a_k\gg a_j$，那么 $p(C_k|x)\simeq 1$ 且 $p(C_j|x)\simeq 0$。

我们现在考虑选择具体的类条件概率密度形式的情况下的结果，⾸先讨论连续输⼊变量 $x$ 的情形，然后简短地讨论离散输⼊的情形。

连续输入

让我们假设类条件概率密度是高斯分布，然后求解后验概率的形式。

⾸先，我们假定所有的类别的协⽅差矩阵相同。这样类别 ${\mathcal{C}}_k$ 的类条件概率为

$$p(\mathbf{x}\mid {\mathcal{C}}_k)=\frac{1}{(2\pi {)}^{\frac{D}{2}}}\frac{1}{|\mathbf{\Sigma }{|}^{\frac{1}{2}}}\exp \left\{-\frac{1}{2}(x-{\mathbf{\mu }}_k{)}^T{\mathbf{\Sigma }}^{-1}(\mathbf{x}-{\mathbf{\mu }}_k)\right\}$$

两类的情形

⾸先考虑两类的情形。根据上面的公式，我们有

$$p({\mathcal{C}}_1\mid \mathbf{x})=\sigma ({\mathbf{w}}^T\mathbf{x}+w_0)$$

其中我们定义了

$$\begin{gathered} \mathbf{w}={\mathbf{\Sigma }}^{-1}({\mathbf{\mu }}_1-{\mathbf{\mu }}_2) \\ {w}_0=-\frac{1}{2}{\mathbf{\mu }}_1^T{\mathbf{\Sigma }}^{-1}{\mathbf{\mu }}_1+\frac{1}{2}{\mathbf{\mu }}_2^T{\mathbf{\Sigma }}^{-1}{\mathbf{\mu }}_2+\ln \frac{p({\mathcal{C}}_1)}{p({\mathcal{C}}_2)} \end{gathered}$$

我们看到，⾼斯概率密度的指数项中x的⼆次型消失了（这是因为我们假设类概率的协⽅差矩阵相同），从⽽得到了参数为 x 的线性函数的 logistic sigmoid 函数。

图4.10给出了⼆维输⼊空间x的情况下的结果。最终求得的决策边界对应于后验概率 $p({\mathcal{C}}_k\mid \mathbf{x})$ 为常数的决策⾯，因此由x的线性函数给出，从⽽决策边界在输⼊空间是线性的。

先验概率密度 $p({\mathcal{C}}_k)$ 只出现在偏置参数 $w_0$ 中，因此先验的改变的效果是平移决策边界，即平移后验概率中的常数轮廓线。

K个类别的⼀般情形

对于K个类别的⼀般情形，根据和公式，我们有

$$a_k(\mathbf{x})={\mathbf{w}}_k^T\mathbf{x}+w_{k0}$$

其中我们定义了

$$\begin{gathered} w_k={\Sigma }^{-1}{\mu }_k \\ {w}_{k0}=-\frac{1}{2}{\mathbf{\mu }}_k^T{\mathbf{\Sigma }}^{-1}{\mathbf{\mu }}_k+\ln p({\mathcal{C}}_k) \end{gathered}$$

我们看到 $a_k(\mathbf{x})$ 与之前⼀样是 $x$ 的线性函数，这是因为各个类别的协⽅差矩阵相同，使得⼆次项被消去。最终的决策边界，对应于最⼩错误分类率，会出现在后验概率最⼤的两个概率相等的位置，因此由 $x$ 的线性函数定义，从⽽我们再次得到了⼀个⼀般的线性模型。

如果我们不假设各个类别的协⽅差矩阵相同，允许每个类条件概率密度 $p(\mathbf{x}|{\mathcal{C}}_k)$ 有⾃⼰的协⽅差矩阵 ${\mathbf{\Sigma }}_k$，那么之前⼆次项消去的现象不会出现，从⽽我们会得到 $\mathbf{x}$ 的⼆次函数，这就引出了⼆次判别函数（quadratic discriminant）。

图4.11给出了线性决策边界和⼆次决策边界。

最大似然解

略

见 PRML 中文版 P114 - 115：4.2.2 最⼤似然解

离散输入

现在让我们考虑离散特征值 $x_i$ 的情形。为了简化起见， 我们⾸先考察⼆元特征值 $x_i\in \{0,1\}$，稍后会讨论如何推⼴到更⼀般的离散特征。

如果有 $D$ 个输⼊，那么⼀般的概率分布会对应于⼀个⼤⼩为 $2^D$ 的表格，包含 $2^D-1$ 个独⽴变量（由于要满⾜加和限制）。

由于这会随着特征的数量指数增长，因此我们想寻找⼀个更加严格的表⽰⽅法。这⾥，我们做出朴素贝叶斯（naive Bayes）的假设，这个假设中，特征值被看成相互独⽴的，以类别 $C_k$ 为条件。

因此我们得到类条件分布，形式为

$$p(\mathbf{x}|{\mathcal{C}}_k)=\prod _{i=1}^D{\mu }_{ki}^{x_i}(1-{\mu }_{ki}{)}^{1-x_i}$$

其中对于每个类别，都有 $D$ 个独⽴的参数。代⼊公式，我们有

$$a_k(\mathbf{x})=\sum _{i=1}^D\{x_i\ln {\mu }_{ki}+(1-x_i)\ln (1-{\mu }_{ki})\}+\ln p({\mathcal{C}}_k)$$

与之前⼀样，这是输⼊变量 $x_i$ 的线性函数。对于 $K=2$ 个类别的情形，我们可以考虑另⼀种⽅法，即 logistic sigmoid 函数。离散变量也有类似的结果，其中，每个离散变量有 $M>2$ 种状态。

★朴素贝叶斯分类器

估计后验概率主要困难：类条件概率是所有属性上的联合概率，难以从有限的训练样本估计获得。

朴素贝叶斯分类器(Naïve Bayes Classifier)采用了“属性条件独立性假设”(attribute conditional independence assumption)：每个属性独立地对分类结果发生影响。

基于属性条件独立性假设，后验概率可重写为

$$\begin{array}{r}P(c\mid \mathbf{x})=\frac{P(c)P(\mathbf{x}\mid c)}{P(\mathbf{x})}=\frac{P(c)}{P(\mathbf{x})}\prod _{i=1}^{d}P(x_i\mid c)\end{array}$$

其中 $d$ 为属性数目， $x_i$ 为 $x$ 在第 $i$ 个属性上的取值。

由于对所有类别来说 $P(x)$ 相同，基于贝叶斯判定准则有

$$\begin{array}{r}{h}_{nb}(\text{x})=\underset{c\in y}{\mathrm{argmax}}P(c)\prod _{i=1}^{d}P(x_i\mid c)\end{array}$$

即对每个样本 $x$, 选择能使后验概率最大的类别标记。

训练器的训练过程就是基于训练集估计类先验概率 $P(c)$，并为每个属性估计条件概率 $P(x_i|c)$。

令 $D_c$ 表示训练集 $D$ 中第 $c$ 类样本组合的集合，若有充足的独立同分布样本，则容易估计出类先验概率

$$P(c)=\frac{|D_c|}{D}$$

令 $D_{c,x_i}$ 表示 $D_c$ 中在第 $i$ 个属性上取值为 $x_i$ 的样本组成的集合，则条件概率 $P(x_i|c)$ 可估计为

$$P(x_i\mid c)=\frac{|D_{c,x_i}|}{|D_c|}$$

朴素贝叶斯分类器例题

例题1

例题2

5.5 分类的性能度量

对学习器的泛化能力进行评估

• 有效可行的实验评估方法
• 衡量模型泛化能力的评价标准

性能度量是衡量模型泛化能力的评价标准，反映了任务需求；使用不同的性能度量往往会导致不同的评判结果。

均方误差

在预测任务中，给定样例集 $D=\{({xx}_1,y_1),({xx}_2,y_2),\dots ,({xx}_m,y_m)\}$ 评估学习器的性能 $f$ 也即把预测结果 $f(xx)$ 和真实标记比较.

回归任务最常用的性能度量是“均方误差”：

$$E(f;D)=\frac{1}{m}\sum _{i=1}^m{\left(f\left({\mathbf{x}}_i\right)-y_i\right)}^2$$

对于数据分布 $\mathcal{D}$ 和概率密度函数 $p(\cdot )$,均方误差：

$$E(f;\mathcal{D})={\int }_{\mathbf{x}\sim \mathcal{D}}{\left(f\left(\mathbf{x}\right)-y\right)}^{2}p(\mathbf{x})\mathrm{d}\mathbf{x}$$

错误率和精度

错误率：分错样本占样本总数的比例
精度： 分对样本占样本总数的比率

查准率和查全率

信息检索、Web搜索等场景中经常需要衡量正例被预测出来的比率或者预测出来的正例中正确的比率，此时查准率和查全率比错误率和精度更适合。

统计真实标记和预测结果的组合可以得到“混淆矩阵”

查准率 $P=\frac{TP}{TP+FP}$：所有预测为正的样例中，真的正例所占比例

查全率 $R=\frac{TP}{TP+FN}$：所有真实为正的样例中，真的正例所占比例

性能度量：P-R曲线

根据学习器的预测结果按正例可能性大小对样例进行排序，并逐个把样本作为正例进行预测，则可以得到查准率-查全率曲线，简称“P-R曲线”

平衡点是曲线上 “查准率=查全率” 时的取值，可用来用于度量P-R曲线有交叉的分类器性能高低。

性能度量：F1 度量

比P-R曲线平衡点更常用的是F1度量：