• 线性模型：指通过样本特征的线性组合进行预测的模型
  • 
  • 是 D 维的权重向量，b 是偏置

上一章的线性回归中，预测输出目标直接
但对于分类问题，预测输出目标的值是离散的标签，因此无法直接使用 进行预测，需引入非线性的决策函数 ，预测输出目标为

• 判别函数：，线性的
• 决策函数/激活函数：，非线性的
  • 典型的二分类问题的决策函数（符号函数）：
• 线性分类模型/线性分类器：由一个（或多个）线性的判别函数 和非线性的决策函数 组成

本章主要介绍四种不同的线性分类模型，主要区别在于使用了不同的损失函数：

3.1 线性判别函数和决策边界

3.1.1 二分类

• 二分类类别标签 的取值： or
• 正例：属于类别 +1 的样本

• 负例：属于类别 -1 的样本

• 决策边界/决策平面：特征空间 中所有满足 的点组成的分割超平面，称为决策边界，将特征空间划分为两个区域，分别代表两个类别

• 线性分类模型就是指其分割超平面是线性超平面
• 特征空间中，决策平面与权重向量 正交
• 特征空间中每个样本点到决策平面的有向距离 ，即点 x 在 w 方向上的投影

• 两类线性可分：对于训练集 ，如果存在权重向量 ，对所有样本都满足 ，那么训练集 是线性可分的

• 二分类问题最直接的损失函数是 0-1 损失函数

3.1.2 多分类

• 多分类一般需要多个线性判别函数，设计这些判别函数的常用方式：
  • “一对其余”方式：将多分类问题转化为 C 个“一对其余”的二分类问题，需 C 个判别函数，第 c 个判别函数 用于将类别 c 的样本和其余样本分开
  • “一对一”方式：将多分类问题转化为 C(C-1)/2 个“一对一”的二分类问题，需 C(C-1)/2 个判别函数，第 (i, j) 个判别函数 用于将类别 i 和类别 j 分开
  • “argmax”方式：改进的“一对其余”方式，需 C 个判别函数
    • 
    • 解决了“一对其余”和“一对一”方式的缺陷：特征空间中存在一些难以确定类别的区域。

• 多类线性可分：对于训练集 ，如果存在 C 个权重向量 ，使得第 c 类的所有样本都满足 ，那么训练集 是线性可分的
• 如果数据集是多类线性可分的，那么一定存在一个“argmax”方式的线性分类器可以将它们正确分开

3.2 Logistic 回归（二分类）

Logistic 回归是处理二分类问题的线性模型，是一种概率模型，通过使用 Logistic 函数将一个实数值映射到 [0, 1] 之间

• 引入非线性的决策函数 （称为激活函数），来预测类别标签的后验概率
• 激活函数：作用是把线性函数的值域从实数区间挤压到 (0, 1) 之间，可以用来表示概率

• Logistic 回归采用 Logistic 函数作为激活函数，即

  • 标签 y=1 的后验概率：

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

3.3 Softmax 回归（多分类）

Softmax 回归，也称为多项或多类的 Logistic 回归，是 Logistic 回归在多分类问题上的推广

• Softmax 回归采用 Softmax 函数作为激活函数
  • 标签 y=c 的条件概率：， 是第 c 类的权重向量
  • Softmax 回归的决策函数：
• Softmax 回归采用交叉熵损失函数，并采用梯度下降法对参数进行优化

3.4 感知器（二分类）

感知器是用于二分类的线性分类模型，是虽简单的人工神经网络，只有一个神经元

• 感知器的分类准则为：
• 感知器是错误驱动的，每次分错一个样本 (x, y)，即 时，才用这个样本更新权重：

• 如果训练集 D 线性可分，则上述算法会在 （R 是训练集中最大的特征向量的模）步内收敛，单存在以下不足：

  • 数据集线性可分时，感知器可以找到一个超平面将两类数据分开，但无法保证其泛化能力，可能过拟合，也就是说没法保证找到的判别函数是最优的
  • 感知器对样本顺序比较敏感，每次迭代的顺序不一致，找到的分割超平面也往往不一致。迭代次序排在后面的错误样本比前面的错误样本，对最终权重向量的影响更大
    • eg. 由1000个训练样本，迭代100个样本后已经学习到一个很好的权重向量，在接下来的899个样本上都预测正确，没有更新权重向量，但在最后一个样本时预测错误，并更新权重，那么这次更新可能反而使权重向量变差
  • 如果训练集不是线性可分的，就永远不会收敛

• 参数平均感知器：为了解决上面提到的前两个不足，以提高感知器的鲁棒性和泛化能力，提出了投票感知器 以及简化的 平均感知器，对学习到的所有权重向量分别赋予权重，不同权重的感知机投票决定最终分类结果

• 扩展到多分类：感知器可以扩展到多分类问题，甚至是更一般的结构化学习问题
  • 为了使感知器可以处理更复杂的输出，引入一个构建在输入输出联合空间上的特征函数 ，将样本对 (x, y) 映射到一个特征向量空间
  • 广义的感知器模型：
  • 在 C 分类问题中，一种常用的特征函数 是 x 和 y 的外积

3.5 支持向量机（二分类）

支持向量机是一个经典的二分类算法

• 样本 到分割超平面 的距离为：
• 间隔 ：，即整个数据集 D 中所有样本到分割超平面的最短距离
• 支持向量机的目标：找到一个超平面 ，使得间隔最大
  • 如果间隔越大，其分割超平面对两个数据集的划分越稳定，不容易受噪声等因素影响
• 一个线性可分的数据集，其分割屏幕有很多个，但间隔最大的超平面是唯一的
• 支持向量机的主优化问题是凸优化问题

• 支持向量：数据集中所有满足 的样本点

  • 在约束边界上的点，即离决策平面距离最近的点

• 核函数

• 松弛变量

• 软间隔

3.6 损失函数对比

Logistic 回归、感知器、支持向量机都是二分类模型，其决策函数相同，但使用了不同的损失函数以及相应的优化方法，因而在实际任务上的表现存在差异

• 对二分类来说：
  • 当 时，分类器预测正确，并且 越大，模型的预测越正确
  • 当 时，分类器预测错误，并且 越小，模型的预测越错误
• 一个好的损失函数因该随着 的增大而减少，因此由上图可知，除了平方损失函数，其他损失函数都比较适用于二分类问题

3.7 总结和深入阅读

• 分类问题的目标标签 y 是离散的类别标签，因此分类问题的决策函数需要输出离散值或是标签的后验概率

• 线性分类模型一般是一个广义线性函数，即一个或多个线性判别函数 + 一个非线性激活函数，所谓线性是指决策界面由一个或多个超平面组成

• 几种常见的线性模型的对比

习题

习题3-1 证明在两类线性分类中，权重向量 w 与决策平面正交

习题3-2 在线性空间中，证明一个点 x 到平面 的距离为

习题3-3 在线性分类中， 决策区域是凸的． 即若点 和 被分为类别 𝑐， 则点 也会被分为类别 𝑐， 其中𝜌 ∈ (0, 1)

习题3-4 给定一个多分类的数据集，证明：1）如果数据集中每个类的样本都和除该类之外的样本是线性可分的， 则该数据集一定是线性可分的； 2）如果数据集中每两个类的样本是线性可分的， 则该数据集不一定是线性可分的

习题3-5 在Logistic回归中， 是否可以用 去逼近正确的 y， 并用平方损失 最小化来优化参数𝒘？

习题3-6 在 Softmax 回归的风险函数（ 公式 (3.39)） 中， 如果加上正则化项会有什么影响？

习题3-7 验证平均感知器训练算法3.2中给出的平均权重向量的计算方式和公式(3.77)等价

习题3-8 证明定理3.2

习题3-9 若数据集线性可分， 证明支持向量机中将两类样本正确分开的最大间隔分割超平面存在且唯一

习题3-10 验证公式(3.97)

习题3-11 在软间隔支持向量机中， 试给出原始优化问题的对偶问题， 并列出其KKT条件

编程练习