与神经网络的发展类比

当样本是线性可分的时候，感知器法和松弛法给了我们许多寻找分类向量的简单方法。这些都被称为“误差校正方法”(error-correcting procedure)，这是因为它们只在遇到错分样本时才对权向量进行校正。它们对可分问题的成功之处在于对求得一个无错解进行坚持不懈的搜索。实际上只有在有理由认为最优线性判别函数的误差率比较低的时候才会考虑使用这些方法。

当然，即使对训练样本的分离向量已经找到，也不能保证它对独立的测试数据都能很好地分类。我们感觉有种直觉印象，它表明数目少于 $2\hat{d}$ 的样本集很可能是线性可分的——我们会在第9章再次考察这一点。因此有人可能会想到：对设计好的样本集使用多次，综合多种因素来获得分类器，并由此确保它在训练和实际数据上的分类性能是相同的。不幸的是，如果使用非常多的数据的话，它们往往不是线性可分的。这样，当样本不是线性可分时了解“误差校正方法”的效果如何就变得非常重要了。

由于不存在可以将不可分数据集中的样本都能正确分类的权向量（由定义可知），显然误差校正过程永远不会结束。这些算法都将产生一个无限的权向量序列，所有的成员都有可能或者不可能得到有用的“解”。在一些特殊的例子中，这些算法在不可分的情况下的行为被全面的研究过。比如，固定增量算法得到的权向量的幅值总是有界的。从经验上得知，校正过程的终止取决于权向量的某个极限点附近时其幅值波动的趋势。从理论的观点来看，如果样本的分量是整数值的话，固定增量算法将产生一个有限状态过程。如果校正过程停在任意一个状态上，权向量可能正处于，也可能不处于好的状态上。如果对校正算法得到的权向量求均值的话，就可以降低偶然选到处于不好状态上的坏向量的风险。（杜达在说人话吗？）

我们已经考虑的准则函数都将注意力放在被错分的样本上。现在我们考虑一种包含所有样本的准则函数。前面我们是寻找一个使得所有内积 ${\mathbf{\theta }}^{\top }{\mathbf{z}}_i$ 都为正数的权向量，现在我们尝试使得 ${\mathbf{\theta }}^{\top }{\mathbf{z}}_i=b_i$ 的情况，这里的 $b_i$ 是一些任意取定的正常数。因此我们就将线性不等式求解的问题改为更强的，但也更容易理解的问题，即线性方程组的求解。

在线性不可分的情况下，不等式组
$${\mathbf{\theta }}^{\top }{\mathbf{z}}_i>0,i=1,2,\cdots ,N\text{\hspace{1em}(1)}$$
不可能同时满足。一种直观的想法是，希望求解一个$\mathbf{\theta }$使被错分的样本尽可能少，即不满足不等式 (1) 的样本尽可能少，这种方法是通过解线性不等式组来最小化错分样本数目，通常采用搜索算法求解。

但是，求解线性不等式组并不方便，为了避免此问题，可以引进一系列待定的常数（余量），把不等式组 (1) 转变成下列方程组
$${\mathbf{\theta }}^{\top }{\mathbf{z}}_i=y_i>0,i=1,2,\cdots ,N$$

或写成矩阵形式
$$\mathbf{Z}\mathbf{\theta }=\mathbf{y}$$

假设一组$d$维样本集${\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_N$，其中$N_1$个标记为$C_1$的样本记为子集${\mathcal{D}}_1$,$N_2$个标记为$C_2$的样本记为子集${\mathcal{D}}_2$。进一步，假设一个从${\mathbf{x}}_i$生成的样本${\mathbf{z}}_i$，它通过加上一个阈值分量$x_0\equiv 1$而得到“增广样本向量”。而且如果它被归为$C_2$，那么整个模式向量都乘以$-1$，即“规范化”操作。不失一般性，可以假设前$N_1$个样本标记$C_1$，后$N_2$个样本标记$C_2$。这样矩阵$\mathbf{Z}$可以写成分块矩阵
$$\mathbf{Z}=\left[\begin{array}{cc}{1}_1& {\mathbf{X}}_1\\ -1_2& -{\mathbf{X}}_2\end{array}\right]$$
其中，$1_i$是$N_i$个 1 的列向量，${\mathbf{X}}_i$是一个$N_i\times d$矩阵，它的行是标记$C_i$的样本。

同样将$\mathbf{\theta }$和$\mathbf{y}$分块：
$$\mathbf{\theta }=\left[\begin{array}{c}{w}_0\\ \mathbf{w}\end{array}\right]$$
且
$$\mathbf{y}=\left[\begin{array}{c}{1}_1\\ 1_2\end{array}\right]$$
同样地，负号可以放在右端项
$$\mathbf{Z}=\left[\begin{array}{cc}{1}_1& {\mathbf{X}}_1\\ 1_2& {\mathbf{X}}_2\end{array}\right]$$
$$\mathbf{y}=\left[\begin{array}{c}{1}_1\\ -1_2\end{array}\right]$$

从此，$\mathbf{y}$有了新的物理解释，可以看成是类别标记，对于标记为$C_1$的类别，$y=1$，标记为$C_2$的类别，$y=-1$。从样本空间{C1,C2}\{C_1, C_2\}{C1​,C2​}到数值的映射。机器学习因为是从输入到输出的映射，因此用数值表示类别标记。（注：凡事把C_1, C_2当集合的，都是概念不清，因为Duda用的${\omega }_1$, ${\omega }_2$，但Duda数学功底扎实，没有数学概念错误，某人誊抄他的，自以为聪明的用了集合语言）

为了表述方便，仍用$\mathbf{X}$表示规范化增广样本矩阵，$\mathbf{w}$表示增广权向量。
通常情况下，$n>d+1$ ，所以式(3 37)中方程个数大于未知数个数，属于超定方程组，没有精确解。方程组的误差为$\mathbf{e}=\mathbf{y}-\mathbf{X}\mathbf{w}$ ，可以求解方程组的最小平方误差解，即寻找解向量 $\mathbf{w}$，使误差的平方和最小：
$$J_S\left(\mathbf{w}\right)=\Vert \mathbf{e}{\Vert }_2^2=\Vert \mathbf{y}-\mathbf{X}\mathbf{w}{\Vert }_2^2=\sum _{i=1}^n{\left({\mathbf{y}}_i-{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i\right)}^2$$

可以用伪逆解或者梯度下降法求解。

最小二乘准则的目标是使误差平方和最小，而不是错误分类样本数最小。对于线性可分样本集，决策面也不一定能将两类样本完全正确分开，不能确保每个样本都被正确分类。

MSE 解是由 $b$ 决定的，我们将会看到 $b$ 的不同选择给解带来不同的性质。如果 $b$ 是任意一个固定的值，没有理由相信 MSE 的解在线性可分情况下能得到一个分类向量。
但我们却有理由希望通过最小化平方误差准则函数，能够得到一个在可分和不可分情况下都是很有用的判别函数。