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^Tx。如果分类已经完全正确，那么对于每个i都有sign（w^Tx_i）=y_i。否则，至少有一个n使得sign（w^Tx_n）≠y_n。例如，w^Tx_n＞0，但y_n=−1。这样w′=w−x_n作为超平面就会把x_n试图拉到超平面负面的一侧。又如w^Tx_n＜0，但y_n=1，这样w′=w+x_n作为新的超平面就会把x_n试图拉到超平面正面的一侧。所以w′=w+y_nx_n就会同时满足上面两种情况。

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

sign（w^Tx_n）≠y_n

成立，则迭代的方式如下

w_n+1=w_n+y_nx_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^Tx_i+b）＞0

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

那么有

w_n+1=w_n+y_nx_n

b_n+1=b_n+y_n

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

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

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