最大间隔分类器
对感知机，只选择第一个完全分离开样本的超平面（如果样本线性可分）。所有可以分离开样本的超平面对于感知机来讲都是同样好的。而最大间隔分类器的目标是减少预测误差，使得每个类别中离超平面最近的那个点与超平面的距离尽量大。这个距离叫做间隔（margin）。如果我们知道两个类别应该满足什么分布，那么可以使用贝叶斯分类器；但是如果我们不对分布进行任何假设，那么最大间隔分类器应该是最好的
最大间隔分类器实际上只由数据集中最“靠外”的点决定，内部点不能决定。从几何角度看，可以用一个最小凸集把每个类中的所有点包含起来。这个最小凸集称作凸包。实际上，对凸包内（包括边界上）的任何一个点\(x_0\)，该点都可以被表示成该数据集所有点的一个加权平均数，即假设\(x_1, \ldots, x_n\)为已知的数据点，有 \[ x_0 = \sum_{i=1}^n \alpha_i x_i,\ \alpha_i \ge 0,\ \sum_{i=1}^n \alpha_i = 1 \]
分类超平面\(H\)的间隔是它到任何类中任意一点距离的最小值（也就是它到任何类其所对应的凸包距离的最小值）。如果我们最大化这个间隔，那么实际上就是把\(H\)放在了两个凸包的正中间。问题是，如何找到满足要求的这个\(H\)
SVM
SVM的问题实际上就是，对于\(n\)个线性可分的点\((x_1, y_1), \ldots, (x_n, y_n)\)，且\(y_i \in \{\pm 1\}\)，求解 \[ \begin{align*} \min_{w,w_0} & \ \ \ \frac{1}{2}|\!|w|\!|^2 \\ {\rm subject\ to} & \ \ \ y_i(x_i^\mathsf{T}w + w_0) \ge 1\ \ \ {\rm for}\ i = 1,\ldots, n \end{align*} \]
仍然是从几何的意义上讲，满足要求的\(H\)可以这么寻找：由之前所述，两个类的数据点实际上形成了两个凸包。可以从这两个凸包上各找一个点，使得它们之间的距离最短。将这两个点用线连接，在线的中点处做一个超平面垂直于这条线，这个超平面就是最优的\(H\)。考虑之前凸包上和凸包内所有点都可以用已知数据集所有点的加和表示，记两个凸包分别为\(S_0\)和\(S_1\)，则实际上我们是要找到两个权重向量\(\alpha_0\)和\(\alpha_1\)以最小化 \[ \left|\!\left|\left(\sum_{x_i \in S_1}\alpha_{1i}x_i\right) - \left(\sum_{x_i \in S_0}\alpha_{0i}x_i\right)\right|\!\right|_2 \]
之前引入的问题称为原始问题，可以引入Lagrange乘数\(\alpha_i > 0, i = 1, \ldots, n\)，则有 \[ \begin{align*} \mathcal{L} &= \frac{1}{2} |\!|w|\!|^2 - \sum_{i=1}^n \alpha_i (y_i(x_i^\mathsf{T}w + w_0) - 1) \\ &= \frac{1}{2} |\!|w|\!|^2 - \sum_{i=1}^n \alpha_i y_i(x_i^\mathsf{T}w + w_0) + \sum_{i=1}^n \alpha_i \end{align*} \] 目标是对\(w\)和\(w_0\)最小化，对\(\alpha_i\)最大化\(\mathcal{L}\) 因此有 \[ \begin{align*} \nabla_w \mathcal{L} = w - \sum_{i=1}^n \alpha_iy_ix_i = 0 &\Rightarrow w = \sum_{i=1}^n \alpha_iy_ix_i \\ \frac{\partial \mathcal{L}}{\partial w_0} = -\sum_{i=1}^n \alpha_i y_i = 0 &\Rightarrow \sum_{i=1}^n \alpha_i y_i = 0 \end{align*} \]
将这些值代回到原式，可以得到对偶问题： \[ \begin{align*} \max_{\alpha_1, \ldots, \alpha_n}\ \ \ & \mathcal{L} = \sum_{i=1}^n \alpha_i - \frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j (x_i^\mathsf{T}x_j) \\ {\rm subject\ to}\ \ \ &\sum_{i=1}^n \alpha_iy_i = 0,\ \ \alpha_i \ge 0\ {\rm for}\ i= 1, \ldots, n \end{align*} \]
现在要对\(\alpha\)最大化上式（凸优化问题不做进一步讨论）
在得到\(\alpha_i\)以后，我们需要将其代回原式求解\(w\)和\(w_0\)，这样对新的\(x_0\)才能预测其对应的\(y_0\)，即\(y_0 = {\rm sign}(x_0^\mathsf{T}w + w_0)\)。对\(w\)，由\(\nabla_w \mathcal{L} = 0\)可知\(w = \sum_{i=1}^n \alpha_iy_ix_i\)
而由于对所有\(i\)有\(\alpha_i (y_i(x_i^\mathsf{T}w + w_0) - 1) = 0\)，而\(\alpha_i \ge 0\)，\(y_i(x_i^\mathsf{T}w + w_0) - 1 \ge 0\)，如果对某个\(i\)有这两个值同时大于0，则\(\mathcal{L}\)可以更小，与\(w, w_0\)取得了最小的\(\mathcal{L}\)相矛盾，因此这两个里面最多只能有一个大于0.因此，只需要找到使\(\alpha_i>0\)的某个\(i\)，然后用刚才得出的\(w\)求解\(y_i(x_i^\mathsf{T}w + w_0) - 1 = 0\)就可以（所有满足条件的\(i\)都能给出同样的解）
下面进一步理解对偶问题。由于\(y_i \in \{-1, +1\}\)，因此由约束条件\(\sum_{i=1}^n \alpha_i y_i = 0\)，可以知道对应于\(y_i = 1\)的\(\alpha_i\)的和，应该等于对应于\(y_j = -1\)的\(\alpha_j\)的和，即\(\sum_{i \in S_1} \alpha_i = \sum_{j \in S_0} \alpha_j\)。记这个和为\(C\)，因此有 \[ \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j (x_i^\mathsf{T}x_j) = \left|\!\left|\sum_{i=1}^n \alpha_i y_i x_i \right|\!\right|^2 = \left|\!\left|\sum_{i \in S_1} \alpha_i x_i - \sum_{j \in S_0} \alpha_j x_j \right|\!\right|^2 = C^2 \left|\!\left|\sum_{i \in S_1} \frac{\alpha_i}{C} x_i - \sum_{j \in S_0} \frac{\alpha_j}{C} x_j \right|\!\right|^2 \]
因此对偶问题可以写作 \[ \begin{align*} \max_{\alpha_1, \ldots, \alpha_n}\ \ \ & \mathcal{L} = 2C - \frac{1}{2}C^2 \left|\!\left|\sum_{i \in S_1} \frac{\alpha_i}{C} x_i - \sum_{j \in S_0} \frac{\alpha_j}{C} x_j \right|\!\right|^2 \\ {\rm subject\ to}\ \ \ &C := \sum_{i \in S_1} \alpha_i = \sum_{j \in S_0} \alpha_j,\ \ \alpha_i \ge 0 \end{align*} \]
可以看到，优化目标和前面讲的求凸包最近两个点之间的最小距离一致
由于\(w\)垂直于\(H\)，与凸包间最近两点连线方向一致（更严谨地，在一条直线上，但是方向指向由正类样本决定），因此实际上最小化\(|\!|u-v|\!|^2, u \in S_1, v \in S_0\)也是在最小化\(|\!|w|\!|^2\)。此外，由前面的推导，也有 \[ w = \sum_{i=1}^n \alpha_iy_ix_i = C \left(\sum_{i \in S_1} \frac{\alpha_i}{C} x_i - \sum_{j \in S_0} \frac{\alpha_j}{C} x_j \right) \]
软间隔SVM与核SVM
如果数据不是完全线性可分的怎么办？这个时候我们可以通过允许训练数据在分类超平面“错的”一边来放松之前的限制（不过需要付出一定的代价）。因此我们可以引入松弛变量\(\xi_i\)，约束条件变为 \[ y_i(x_i^\mathsf{T}w+w_0) \ge 1 - \xi_i \] 当\(0 < \xi_i < 1\)时，该点比支持向量（这里没讲但是概念懂的）更靠近超平面；当\(\xi > 1\)时，该点在超平面的另一边
再引入对高维空间的映射函数\(\phi(x_i)\)，则新的求解问题变成了 \[ \begin{align*} \min_{w,w_0,\xi_1, \ldots, \xi_n} \ \ \ &\frac{1}{2}|\!|w|\!|^2 + \lambda \sum_{i=1}^n \xi_i\\ {\rm subject\ to} \ \ \ &y_i(\phi(x_i)^\mathsf{T}w + w_0) \ge 1 - \xi_i\ \ \ {\rm for}\ i = 1,\ldots, n \\ & \xi_i \ge 0,\ \ \ {\rm for}\ i=1,\ldots, n \end{align*} \]
如果\(\lambda \rightarrow 0\)，则对错分的容忍度变大，反之则表示不允许错分（通常使用交叉验证来选择）
其对偶问题为，以每个\((\alpha_i, \mu_i)\)最大化，以\(w,w_0, \xi_1, \ldots, \xi_n\)最小化 \[ \mathcal{L} = \frac{1}{2}|\!|w|\!|^2 + \lambda \sum_{i=1}^n \xi_i - \sum_{i=1}^n \alpha_i(y_i(\phi(x_i)^\mathsf{T}w+w_0)-1+\xi_i) - \sum_{i=1}^n \mu_i\xi_i \\ {\rm subject\ to}\ \alpha_i \ge 0,\ \mu_i \ge 0,\ y_i(\phi(x_i)^\mathsf{T}w+w_0)-1+\xi_i \ge 0 \] 可以解得 \[ w = \sum_{i=1}^n \alpha_iy_i\phi(x_i),\ \sum_{i=1}^n \alpha_iy_i = 0,\ \lambda - \alpha_i - \mu_i = 0 \]
将\(w\)和\(\mu_i = \lambda - \alpha_i\)代回，可知对偶问题为 \[ \begin{align*} \max_{\alpha_1, \ldots, \alpha_n}\ \ \ &\mathcal{L} = \sum_{i=1}^n \alpha_i- \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n \alpha_i\alpha_jy_iy_j\phi(x_i)^\mathsf{T}\phi(x_j) \\ {\rm subject\ to}\ \ \ &\sum_{i=1}^n \alpha_iy_i = 0,\ \ \ 0 \le \alpha_i \le \lambda \end{align*} \]
其中\(\phi(x_i)^\mathsf{T}\phi(x_j)\)可以用核函数\(K(x_i, x_j)\)替换
分类预测变为求 \[ {\rm sign}\left(\sum_{i=1}^n \alpha_iy_i K(x_0, x_i) + w_0\right) \] 注意到对于大多数\(i\)，有\(\alpha_i = 0\)，因此实际上预测的时候只会用到那些\(\alpha_i\)不为0的点，称这些点为支持向量
