最佳判别界
对相同的数据集，PLA可能得到不同的判别界，如上图所示，那条判别界最好呢？
- 测量是有误差的，能容忍误差越大的分界线越好，如上图上排所示，灰色的圆半径越大表示对误差的容忍度越大。噪声是导致过拟合的主要原因，对误差的容忍度越好，过拟合的可能性越低。
- 判别界能膨胀得越胖越鲁棒，如上图下排所示。
根据上两条标准，最右的判别界最佳。判别界的胖瘦程度称为边界（margin），最大边界的判别界最佳，也就是离判别界距离最近的点离判别界距离越大越好，
\begin{equation*} \begin{aligned} \max\limits_{\mathbf w} &\quad\mbox{margin}(\mathbf w)\\ \mbox{subject to}& \quad\mbox{every } y_n\mathbf w^T\mathbf x_n > 0\\ &\quad\mbox{margin}(\mathbf w)=\min\limits_{n=1,\ldots,N}\mbox{distance}(\mathbf x_n, \mathbf w)。 \end{aligned} \end{equation*}
$y_n\mathbf w^T\mathbf x_n > 0$表示点被正确的分类，$\mbox{margin}(\mathbf w)$的定义可以保证判别界在两类的“中间”，不会偏向任何一边。
支持向量机
与线性感知器的定义不同，定义$b= w_0, \mathbf w=\left[ w_1, \ldots, w_d\right]^T$，$\mathbf x=\left[ x_1, \ldots, x_d\right]^T$。点到判别界的距离可表示为 \begin{equation*} \mbox{distance}(\mathbf x, b, \mathbf w)=\frac{1}{\lVert\mathbf w\rVert}\left\lvert\mathbf w^T\mathbf x + b\right\rvert， \end{equation*} 因此可得最大间隔 \begin{equation} \begin{aligned} \max\limits_{b, \mathbf w} &\quad\mbox{margin}(b, \mathbf w)\\ \mbox{subject to}& \quad\mbox{every } y_n\left(\mathbf w^T\mathbf x_n + b\right) > 0\\ &\quad\mbox{margin}(b, \mathbf w)=\min\limits_{n=1,\ldots,N}\frac{1}{\lVert\mathbf w\rVert}y_n\left(\mathbf w^T\mathbf x_n + b\right)。 \end{aligned} \label{eq:hard-margin-svm-origin-model} \end{equation} 通过系数缩放，总可以做到$\min\limits_{n=1,\ldots,N}y_n\left(\mathbf w^T\mathbf x_n + b\right) = 1$，最大间隔问题可以转化为等价问题 \begin{equation*} \begin{aligned} \max\limits_{b, \mathbf w} &\quad{1\over\lVert\mathbf w\rVert}\\ \mbox{subject to}& \min\limits_{n=1,\ldots,N}y_n\left(\mathbf w^T\mathbf x_n + b\right) = 1。 \end{aligned} \end{equation*} 上述条件$\min\limits_{n=1,\ldots,N}y_n\left(\mathbf w^T\mathbf x_n + b\right) = 1$可以用等价的条件$y_n\left(\mathbf w^T\mathbf x_n + b\right) \geq 1$代替。如果仅仅是$y_n\left(\mathbf w^T\mathbf x_n + b\right) > 1$而无法取“$=$”，那么不等式两边可以除以大于$1$的系数，使得条件仍然成立，$\mathbf w$除以大于$1$的系数后，${1\over\lVert\mathbf w\rVert}$会更大。因此，标准形式的最优化是 \begin{equation} \begin{aligned} \min\limits_{b, \mathbf w} &\quad{1\over 2}\mathbf w^T\mathbf w\\ \mbox{subject to}& \quad y_n\left(\mathbf w^T\mathbf x_n + b\right) \geq 1\mbox{ for all }n。 \end{aligned} \label{eq:linear-svm-model} \end{equation}
通过求解可以发现，只有部分点对解有作用，如上图边界上方框内的点，这些点称为候选支持向量（support vector）。支持向量机就是利用支持向量学习“最胖”判别界。
二次规划求解
求解最佳判别界的是一个二次规划问题（QP，quadratic programming）。二次规划的标准形式为
\begin{equation}
\begin{aligned}
\mbox{optimal} &\quad\mathbf u\leftarrow QP(\mathbf Q, \mathbf p, \mathbf A, \mathbf c) \\
\min\limits_{\mathbf u} &\quad{1\over 2}\mathbf u^T\mathbf Q\mathbf u + \mathbf p^T\mathbf u\\
\mbox{subject to}&\quad\mathbf a_n^T\mathbf u\geq c_n\mbox{ for }n=1,2,\ldots,N。
\end{aligned}
\label{eq:qp-standard-format}
\end{equation}
支持向量机利用二次规划求解时参数为
\begin{equation*}
\mathbf u =
\begin{bmatrix}
b\\
\mathbf w
\end{bmatrix}
，
\end{equation*}
目标函数系数为
\begin{equation*}
\mathbf Q =
\begin{bmatrix}
0 &\mathbf 0_d^T\\
\mathbf 0_d &\mathbf I_d
\end{bmatrix};
\mathbf p=\mathbf 0_{d+1}
，
\end{equation*}
约束条件系数为
\begin{equation*}
\mathbf a_n^T=y_n\left[1\quad\mathbf x_n^T\right];c_n=1。
\end{equation*}
这里所讲的支持向量机叫做线性hard-margin支持向量机，其中hard-margin是指所有的点能被正确分类。
利用$\mathbf z_n=\Phi\left(\mathbf x_n\right)$，用$\mathbf z_n$替代$\mathbf x_n$，可以得到非线性的支持向量机。
最大边界的价值
正则化（regularization）通过约束条件$\mathbf w^T\mathbf w\leq C$最小化$E_{in}$，支持向量机通过$E_{in}=0$等约束条件最小化$\mathbf w^T\mathbf w$。因此，支持向量机也可以看作是一种特殊的正则化方法。
对于最大边界算法$\mathcal A_{\rho}$，脚标表示分界线的宽度要大于$\rho$。当$\rho = 0$时就是PLA，它可以打碎2维平面的3个输入点；若$\rho＝1.126$，如上图所示，无法打碎3个点。
如果加入了$\rho$条件的限制，可能的二分类情况少了，可认为VC维更小了，有更好的泛化性能。对于算法的VC维，有数据依赖的VC维比没有依赖的要低，$d_{VC}\left(\mathcal A_\rho\right)<d_{VC}(\mathcal H)$，有数据依赖意味着加入了跟多的约束条件。
当$\mathcal X$是上图所示半径为$R$的单位圆上点时， \begin{equation} d_{VC}\left(\mathcal A_\rho\right)\leq\min\left({R^2\over \rho^2},d\right)+1\leq d+1。 \end{equation}
几种情况的判别界对比如上图所示，large-margin的判别界简单且数量较少，有特征变换$\Phi$的判别界较复杂但是数量较多。
较少的判别界对$d_{VC}$和泛化有利，复杂的判别界可能得到更好的$E_{in}$。非线性支持向量机同时具备大边界的判别界和采用多种特征变换$\Phi$，因此判别界较少而且比较复杂，兼顾了这两方面的优点。
