Chapter 2: 线性学习器(Linear Learning Machines)

2.1 线性分类(Linear Classification)

两类问题函数可以写成: \(f({\bf{x}}) = \left\langle {{\bf{w}}\cdot{\bf{x}}} \right\rangle  + b = \sum\limits_{i = 1}^n {{w_i}{x_i}}  + b \). 这里\(\left( {{\bf{w}},b} \right) \in {{\rm{R}}^{\rm{n}}} \times {\rm{R}}\)是控制函数的参数, 决策规则由\({\mathop{\rm sgn}} (f({\bf{x}}))\)给出, 惯例, \({\mathop{\rm sgn}} (0) = 1\).

几何解释是,式\(\left\langle {{\bf{w}}\cdot{\bf{x}}} \right\rangle  + b = 0\)定义的超平面将输入空间\(X\)分为两部分. 超平面是\(n – 1\)维的仿射子空间, 它将空间分为两部分, 这两部分对应输入类中的两类. 当\(b\)值变化时, 超平面平行于自身移动. 因此, 如果想表达\({{\rm{R}}^{\rm{n}}}\)中所有可能超平面, 包括\(n + 1\)个可调参数的表达式是必要的. 统计学家和神经网络的研究者经常使用这种称为线性判别平面(linear discriminants)或感知机(perceptron)的简单分类器.

20世纪60年代就已经提出了几个简单的迭代算法来优化代价函数, 这些代价函数使用超平面把点分为两类, 下面各节回顾一些最著名的算法.

2.1.1 Rosenblatt感知机(Rosenblatt’s Perceptron)

线性分类器的第一个迭代算法是1956年由Frank Rosenblatt提出的. 这个算法被提出后, 受到了很大的关注. 感知器在神经网络发展的历史上占据着特殊的位置: 它是第一个从算法上完整描述的神经网络. 在20世纪60年代和70年代, 受感知器的启发, 工程师, 物理学家以及数学家们纷纷投身于神经网络不同方面的研究. 这个算法在今天看来依然是有效的. 其中, \({\bf{w}}\)为权重向量, \(b\)为偏置.

用Matlab实现上面感知机算法, 样例集采用上图的数据, 是一个非平凡训练集\(S\), 注: 所有样例的标记相同时, 训练集\(S\)是平凡的. 有不同时为非平凡训练集. 感知机的M文件代码如下:

生成的分割超平面如图(红色线是最优超平面, 蓝色线是根据感知机算法生成的).

从图中可以看出, 感知机算法可以通过简单迭代对线性可分数据生成正确分类的超平面, 但不是最优效果. 后面介绍的最大间隔平面会解决此问题.

 下面来展示一下迭代次数是与间隔量相关的.

 我们定义函数间隔(function margin)为样例\(\left( {{x_i},{y_i}} \right)\)对应于超平面\(\left( {{\bf{w}},b} \right)\)的量: \({\gamma _i} = {y_i}(\left\langle {{\bf{w}}\cdot{x_i}} \right\rangle  + b)\). 如果\({\gamma _i} > 0\)表示样例\(\left( {{x_i},{y_i}} \right)\)被正确分类. 有时所谓间隔分布的最小值指超平面\(\left( {{\bf{w}},b} \right)\)对应于训练集\(S\)的间隔. 我们用几何间隔(geometric margin)来替换函数间隔得到等价的归一化(normalized)线性函数\(\left( {\frac{1}{{\left\| {\bf{w}} \right\|}}{\bf{w}},\frac{1}{{\left\| {\bf{w}} \right\|}}b} \right)\), 它度量了input空间中的点到decision boundary的欧式距离(Euclidean distances). 注意区分单个样例点到超平面的间隔和训练集到超平面的间隔.

 Novikoff定理(这里略)证明了当间隔是正的时候算法会在有限次数的迭代中收敛. 如果分类超平面存在, 仅需在序列\(S\)上迭代几次, 在界为\({\left( {\frac{{2R}}{\gamma }} \right)^2}\)的错误次数下就可以找到分类超平面, 算法停止. 这里\(R{\rm{ = }}\mathop {\max }\limits_{1 \le i \le l} \left\| {{\bf{x}}_i } \right\|
\), \(
\gamma
\)为扩充间隔. 根据误分次数公式可知, 迭代次数与对应于扩充(包括偏置)权重的训练集的间隔有关.

 这里引入outliers, outliers是样例中的噪音数据, 偏离正常位置很远的数据, 影响会比较大. 为了解决这个问题引入松弛变量(slack variable) \({\xi _i}\), 即允许对应数据\({x_i}\)偏离functional margin的量.

根据感知机的工作原理可以推出, 如果初始权重向量是零向量, 这样最终的假设将是训练点的线性组合:

 \({\bf{w}}{\rm{ = }}\sum\limits_{i=1}^l {\alpha _i y_i {\bf{x}}_i }\)

这里, 误分次数较小的点将有较小的  \(\alpha _i\), 而难分类的点将有较大的值. 这就引出了比较重要的对偶形式. 在对偶坐标中把决策函数重写为:\[\begin{array}{l}
h({\bf{x}}) = {\mathop{\rm sgn}} (\left\langle {{\bf{w}} \cdot {\bf{x}}} \right\rangle  + b)\\
 = {\mathop{\rm sgn}} (\left\langle {\sum\limits_{j = 1}^l {{\alpha _j}{y_j}{{\bf{x}}_j}}  \cdot {\bf{x}}} \right\rangle  + b)\\
 = {\mathop{\rm sgn}} (\sum\limits_{j = 1}^l {{\alpha _j}{y_j}\left\langle {{{\bf{x}}_j} \cdot {\bf{x}}} \right\rangle }  + b)
\end{array}\]

从简单的感知机算法的分析中, 已经发现很多SVM理论将要用到的重要概念: 间隔, 间隔分布, 对偶表示.

 2.1.2 其他线性分类器(Other Linear Classifiers)

感知机算法仅在数据线性可分时保证收敛. 不受此限制的一个方法是Fisher判别. 它寻找数据投影分开最大的超平面\(\left( {{\bf{w}},b} \right)\). 

2.1.3 多类判别(Multi-class Discrimination)

多类分类问题, 输出域是\(Y = \left\{ {1,2,…,m} \right\}\). 线性学习器推广到\(m\)类是很直接的: 对\(m\)类中的每个类关联一个权重向量和一个偏置, \(\left( {{{\bf{w}}_i},{b_i}} \right)\), \(i \in \left\{ {1,…,m} \right\}\), 则决策函数给出如下:

\(c(x) = \arg \mathop {\max }\limits_{1 \le i \le m} (\left\langle {{{\bf{w}}_i}\cdot\bf{x}} \right\rangle  + {b_i})\), 从几何角度, 这等价于给每个类关联一个超平面, 然后将新点\({\bf{x}}\)赋予超平面离其最远的一类. Input空间分为\(m\)个简单相连的凸区域.

 2.2 线性回归(Linear Regression)

线性回归问题就是求线性函数: \(f({\bf{x}}) = \left\langle {{\bf{w}}\cdot{x_i}} \right\rangle  + b\), 使其能够最好地拟合一个给定标记为\(Y \subseteq {\rm{R}}\)的训练点集\({\rm{S}}\). 从几何角度讲是寻找一个拟合给定点的超平面.

 2.2.1 最小二乘法(Least Squares)

给定一个训练集\({\rm{S}}\), 其中\({x_i} \in X \subseteq {\rm{R}}\), \({y_i} \in Y \subseteq {\rm{R}}\), 线性回归的问题是寻找(线性)函数\(f\)来对数据建模: \(y = f({\bf{x}}) = \left\langle {{\bf{w}}\cdot{\bf{x}}} \right\rangle  + b\). 最小二乘的方法通过最小化偏离数据的误差平方和来选择参数\(\left( {{\bf{w}},b} \right)\): \(L\left( {{\bf{w}},b} \right) = \sum\limits_{i = 1}^l {{{({y_i} – \left\langle {{\bf{w}},{x_i}} \right\rangle  – b)}^2}} \)函数\(L\)就是平方损失函数(the square loss function).

2.2.2 岭回归(Ridge Regression)

最小二乘问题的解是: \({\bf{\hat w}} = {\left( {{\bf{\hat X’\hat X}}} \right)^{ – 1}}{\bf{\hat X’}}y\), 如果在最小二乘法中\({\bf{\hat X’\hat X}}\)矩阵不是满秩, 活着在其他情况下数值解不稳定, 则可以使用下面的解: \({\bf{\hat w}} = {\left( {{\bf{\hat X’\hat X}} + \lambda {\bf{I}}{}_{\rm{n}}} \right)^{ – 1}}{\bf{\hat X’}}y\). 上面的公式可以通过在矩阵\({\bf{\hat X’\hat X}}\)上增加对角矩阵\({\bf{I}}{}_{\rm{n}}\)的乘子\(\lambda  \in {{\rm{R}}^ + }\)来得到.这个解称为岭回归. 最初是在统计领域因为数值稳定性的原因提出的.