2.1 分类问题的刻画

首先考虑 k =2的情况。在 空间中有有限个点，每个点都有两个分量，为了简化记号，将这些点记为

每个点都赋予一个值 y _i ∈{-1，1}。也可以想象成平面上的这些点被染成两种颜色。其目的就是试图找出最简单的函数来区分这些点。区分点的方法可以使用函数，如 。函数值为1的点是一种颜色，函数值为-1的点是另外一种颜色。

从使用参数最少的角度来考量，最简单的函数是线性函数，对应的几何形状就是空间中的超平面。下面使用向量和矩阵的语言。在 中的向量记为列向量的形式，为了节省空间，也可以使用转置的写法

来表示一个 k 维向量。在空间 中的超平面函数是

其中， 。超平面的一边满足 f （ x ）＞0，另一边满足 f （ x ）＜0。所以希望找到一个超平面，即 w ，b 满足

为了简化计算和符号，可以扩充维数，如果 x _i 是有 k 个分量的向量

那么添加第一个分量1成为

同样，对于

也可以添加一个分量成为

所以有

在达到这个共识以后，可以忽略掉新的记号，还是沿用旧的记号来表达新的内容。

现在的目的是找出合适的 w ，使得线性函数

可以区分开平面上的点集，即对于每个 i ，都有

如果这个问题可以得到解决，就需要一个基础假设，可以假设这些点集本来就在一个超平面的两边，那么问题就归结于如何找到这个超平面。

数学上的存在性是解决问题的前提，但是我们更关心在实际操作中的算法问题。算法问题可归结为：给出一个有限的、在平面（二维）或者空间（高维）可分的点集，如何在有限步骤之内找到这个超平面。

为此，可以尝试迭代方法。下面来回顾几种使用迭代方法求解的经典问题。

对于一个连续函数 ，如果 f （ a ） f （ b ）＜0，那么根据中间值定理一定有 c ∈（ a ; b ），使得 f （ c ）=0。为了实际寻找这个零点，可以采用二分法。

另外一个例子是关于连续函数的收缩映像定理。如果一个函数 满足| f （ x ）- f （ y ）|＜ λ | x - y |，那么一定有一个点满足 f （ x ）= x 。这个点称为不动点。为了得到这个点，可以使用

x _{n +1} = f （ x _n ）

来进行迭代，最终会收敛到所需要的不动点上。

又如利用牛顿法求解函数的零点，其迭代方式为

在一定条件下也可以逐渐收敛到所需要的函数零点上。

这些方法都使得计算机在不断更新的过程中逐渐得到一个我们希望得到的解。所以机器学习的一些方法也是通过不断迭代以期达到学习的目的。

回到本节的问题，先从一个超平面开始，这意味着有了一个 w ，超平面就是 f （ x ）= w ^T x 。如果分类已经完全正确，那么对于每个 i 都有sign（ w ^T x _i ）= y _i 。否则，至少有一个 n 使得sign（ w ^T x _n ）≠ y _n 。例如， w ^T x _n ＞0，但 y _n =-1。这样 w ′= w - x _n 作为超平面就会把 x _n 试图拉到超平面负面的一侧。又如 w ^T x _n ＜0，但 y _n =1，这样 w ′= w + x _n 作为新的超平面就会把 x _n 试图拉到超平面正面的一侧。所以 w ′= w + y _n x _n 就会同时满足上面两种情况。

一般来讲，从任意的一个 w ₀ 开始，如果这个点已经正确完成分类，那么我们就有了结果。如果有一个 k 使得

sign（ w ^T x _n ）≠ y _n

成立，则迭代的方式如下

w _{n +1} = w _n + y _n x _n

然后持续更新 w ，直到最后完成所有正确的分类为止。

定理2.1 如果这些点本来就是可以区分的，那么上述算法必然会在有限步骤内结束。

证明 可以从两个方面来看 w _n 的增长。一方面，因为序列更新

其中 n 满足 ，所以有

考虑到 ，从而有常数使得

其中 A 是正实数，可以选为所有| x _i | ² 的上界。

另一方面，因为有向量 w *可以区分平面上的点，所以将式（2.1）等号两边同时和 w *做内积，得到

又因为有 ，所以有

其中， C 可以选择为所有 中最小的正值。从上面两个不等式可以看到

从而可以得到这样的 n 一定是有限的，无法持续更新下去。这就说明一定会在某一步终止，最后达到完全可分状态。证毕

上面是为了简化记号而做出的算法和证明。现在来看不简化记号时，迭代算法应该是什么样子。回到样本点

（ x ₁ ，y ₁ ），（ x ₂ ，y ₂ ），···，（ x _n ，y _n ）

其中 ，且 y _i ∈{-1，1}。目标是寻找 和 ，使得

y _i （ w ^T x _i + b ）＞0

其迭代算法是先选择初始值 ，假设在选择了 以后，有 x _n 使得

那么有

w _{n +1} = w _n + y _n x _n

b _{n +1} = b _n + y _n

这个过程就是不简化记号的迭代过程。

感知机模型迭代收敛如图2.1所示。

感知机的模型算法是可以加强的，在后面会看到各种加强的探索。但无论如何，这个简单算法都让我们看到了机器学习的基本想法，那就是不断地优化探索，直到找到最优或者局部最优的算法为止。 0EWJFTR5vHHv6KRaGmplnHRttl9IH83d6nSLs8oBzY56PYV5b5cinTykZ0REwEhG