目录
支持向量机
支持向量分类
线性可分数据和硬间隔
支持向量机的学习策略为间隔（margin）最大化，间隔的测量需要在特征空间中选择。
首先考虑线性可分的数据，输入为 \(\pmb x\)，特征为 \(\pmb\Phi(\pmb x)\)，标签为 \(y\in\lbrace-1,1\rbrace\)。数据的判定函数为
\[\begin{align*} f(\pmb x)&=\pmb w^T\pmb\Phi(\pmb x)+b \end{align*} \]一般来说，分离这种数据的超平面有无穷多个，而在支持向量机中，使用间隔最大化来选择一个唯一的超平面。
在特征空间中，特征可以被分解为位于分界超平面上的一部分 \(\pmb\Phi_0\) （满足 \(\pmb w^T\pmb\Phi_0+b=0\)）和垂直于分界超平面的另一部分。如果选择距离超平面的欧式距离最短的点的距离为间隔，则间隔计算方法为
\[\begin{align*} \pmb\Phi(\pmb x)&=\pmb\Phi_0(\pmb x)+r{\pmb w\over\Vert\pmb w\Vert_2}\\ \pmb w^T\pmb\Phi(\pmb x)&=\pmb w^T\pmb\Phi_0(\pmb x)+r{\pmb w^T\pmb w\over\Vert\pmb w\Vert_2}\\ &=-b+r\Vert\pmb w\Vert_2\\ r&={\pmb w^T\pmb\Phi(\pmb x)+b\over\Vert\pmb w\Vert_2}\\ \operatorname{margin}(\pmb w,b)&:=\min_{(\pmb x,y)\in(\mathcal X,Y)}yr\\ &=\min_{(\pmb x,y)\in(\mathcal X,Y)}y{\pmb w^T\pmb\Phi(\pmb x)+b\over\Vert\pmb w\Vert_2}\\ &=\frac1{\Vert\pmb w\Vert_2}\min_{(\pmb x,y)\in(\mathcal X,Y)}y(\pmb w^T\pmb\Phi(\pmb x)+b) \end{align*} \]其中 \(y\) 是用来将正负类的距离设置为非负值的。取 \(\hat y:=y(\pmb w^T\pmb\Phi(\pmb x)+b)\)
\[\begin{align*} \pmb w^\star,b^\star&:=\underset{\pmb w,b}{\arg\max}\operatorname{margin}(\pmb w,b)\\ &=\underset{\pmb w,b}{\arg\max}\frac1{\Vert\pmb w\Vert_2}\min_{(\pmb x,y)\in(\mathcal X,Y)}\hat y \end{align*} \]从公式可以看出，如果 \(\pmb w,b\) 乘以一个系数 \(c\)，则 \(\hat y\) 也相应的变为 \(c\) 倍，但 \(\pmb w^\star,b^\star\) 却不会发生改变。不妨取 \(\min\hat y=1\)（即固定间隔为 \(\Vert\pmb w\Vert_2^{-1}\)，只与权重相关），相应地为问题添加了一个约束。
\[\begin{align*} \pmb w^\star,b^\star&=\underset{\pmb w,b}{\arg\max}\frac1{\Vert\pmb w\Vert_2}\qquad\text{s.t.}\quad\min\hat y=1\\ &=\underset{\pmb w,b}{\arg\min}\ \,\Vert\pmb w\Vert_2\qquad\,\text{s.t.}\quad\min\hat y=1\\ &=\underset{\pmb w,b}{\arg\min}\frac12\Vert\pmb w\Vert_2^2\qquad\!\text{s.t.}\quad\hat y\ge1\quad\forall (\pmb x,y)\in(\mathcal X,Y)\\ \end{align*} \]如果将 \(\min\hat y\) 分解，则从一个约束变为了多个约束，可以使用拉格朗日函数将约束与问题结合，取 \(\vert\mathcal X\vert\) 为样本的数量。因为是求优化问题的下界，所以使用拉格朗日乘子 \(\lambda_i\) 将问题转为等价的 \(\min\max\) 问题。
\[\begin{align*} \mathcal L(\pmb w,b,\pmb\lambda)&:=\frac12\Vert\pmb w\Vert_2^2-\sum_{i\in\vert\mathcal X\vert}\lambda_i(\hat y_i-1)\\ &=\frac12\Vert\pmb w\Vert_2^2-\sum_{i\in\vert\mathcal X\vert}\lambda_i[y(\pmb w^T\pmb\Phi(\pmb x)+b)-1]\\ \pmb w^\star,b^\star&=\underset{\pmb w,b}{\arg\min}\max_{\lambda\ge0}\mathcal L(\pmb w,b,\pmb\lambda) \end{align*} \]如果 \(\hat y\) 不满足约束，则 \(\lambda(\hat y-1)\to\infty\)，必定不会是解；相反如果满足约束，则 \(\mathcal L(\pmb w,b,\pmb\lambda)=\Vert\pmb w\Vert_2^2\)。由于 \(\mathcal L\) 的第一项为 \(\pmb w\) 的二次项，第二项为 \(\pmb w,b\) 的一次项，所以接下来通过拉格朗日的强对偶定理对问题进行进一步的转换。
\[\begin{align*} \min_{\pmb w,b}\max_{\lambda_i\ge0}\mathcal L(\pmb w,b,\pmb\lambda)=\max_{\lambda_i\ge0}\min_{\pmb w,b}\mathcal L(\pmb w,b,\pmb\lambda) \end{align*} \]于是对 \(L(\pmb w,b,\pmb\lambda)\) 求导，求极小值
\[\begin{align*} \nabla_{\pmb w}\mathcal L(\pmb w,b,\pmb\lambda)&=\pmb w-\sum_{i\in\vert\mathcal X\vert}\lambda_iy_i\pmb\Phi(\pmb x_i)=\pmb0\\ \nabla_b\mathcal L(\pmb w,b,\pmb\lambda)&=-\sum_{i\in\vert\mathcal X\vert}\lambda_iy_i=0\\ \mathcal L(\pmb w,b,\pmb\lambda)&=\frac12\Vert\pmb w\Vert_2^2-\sum_{i\in\vert\mathcal X\vert}\lambda_i[y(\pmb w^T\pmb\Phi(\pmb x)+b)-1]\\ &=\sum_{i\in\vert\mathcal X\vert}\lambda_i-\frac12\pmb w^T\pmb w\\ &=\sum_{i\in\vert\mathcal X\vert}\lambda_i-\frac12\sum_{i\in\vert\mathcal X\vert}\sum_{j\in\vert\mathcal X\vert}\lambda_i\lambda_jy_iy_j\pmb\Phi(\pmb x_i)^T\pmb\Phi(\pmb x_j)\\ \pmb\lambda^\star&=\underset{\pmb\lambda}{\arg\max}\ \mathcal L(\pmb w,b,\pmb\lambda),\qquad\text{s.t.}\ \quad\lambda_i\ge0,\sum_{i\in\vert\mathcal X\vert}\lambda_iy_i=0\\ &=\underset{\pmb\lambda}{\arg\max}\left\lbrace\sum_{i\in\vert\mathcal X\vert}\lambda_i-\frac12\sum_{i\in\vert\mathcal X\vert}\sum_{j\in\vert\mathcal X\vert}\lambda_i\lambda_jy_iy_j\pmb\Phi(\pmb x_i)^T\pmb\Phi(\pmb x_j)\right\rbrace\\ &\quad\ \,\text{s.t.}\ \quad\lambda_i\ge0,\sum_{i\in\vert\mathcal X\vert}\lambda_iy_i=0 \end{align*} \]虽然公式已经变形了很多，但它仍然和原始的 \(\mathcal L(\pmb w,b,\pmb\lambda)=\frac12\Vert\pmb w\Vert_2^2-\sum_{i\in\vert\mathcal X\vert}\lambda_i(\hat y_i-1)\) 是等价的。问题由求解 \(\pmb w^\star,b^\star\) 变为了求解 \(\pmb\lambda^\star\)，减少了一个变量，而通过核技巧，还可以继续简化这一表达式。
当 \(\lambda_i\ne0\) 时，则有 \(\hat y_i=1\)，即设置的间隔，相应的点就是离超平面最近的点，这些点就是支持向量机中的支持向量。将这些点设为 \((\pmb x^\star,y^\star)\in\mathcal S\)。求得最优解 \(\pmb\lambda^\star\) 后得出 \(\pmb w^\star,b^\star\)
\[\begin{align*} \pmb w^\star&=\sum_{i\in\vert\mathcal X\vert}\lambda_i^\star y_i\pmb\Phi(\pmb x_i)\\ b^\star&=y^\star-{\pmb w^\star}^T\pmb\Phi(\pmb x^\star)\text{ or }\frac1{\vert\mathcal S\vert}\sum_{i\in\vert\mathcal S\vert}y_i^\star-{\pmb w^\star}^T\pmb\Phi(\pmb x_i^\star)\\ f^\star(\pmb x)&={\pmb w^\star}^T\pmb\Phi(\pmb x)+b^\star\\[0.8em] &=\sum_{i\in\vert\mathcal X\vert}\lambda_i^\star y_i\pmb\Phi(\pmb x_i)^T\pmb\Phi(\pmb x)+b^\star\\ &=\sum_{i\in\vert\mathcal S\vert}\lambda_i^\star y_i\pmb\Phi(\pmb x_i)^T\pmb\Phi(\pmb x)+b^\star\\ \end{align*} \]\(i\in\vert\mathcal S\vert\) 说明，新的点将会与每个支持向量进行对比从而决定这个点的类，符合支持向量的含义；而 \(\lambda_i^\star\) 代表着每个支持向量对新的点分类的权重。
弱对偶：
\[\begin{align*} \max_y\min_xf(x,y)\le\min_x\max_yf(x,y) \end{align*} \]强对偶：
原始问题
\[\begin{align*} &\min_{x\in\mathcal X\in\mathbb R^n}f(x)\\ &\text{s.t.}\quad c_i(x)\le0,\quad i\in\vert\mathcal I\vert\\ &\text{s.t.}\quad d_i(x)=0,\quad i\in\vert\mathcal E\vert\\ \end{align*} \]对偶问题
\[\begin{align*} \mathcal L(x,\pmb\alpha,\pmb\beta)&=f(x)+\sum_{i\in\vert\mathcal I\vert}\alpha_ic_i(x)+\sum_{i\in\vert\mathcal E\vert}\beta_id_i(x),\quad\text{s.t.}\quad\alpha_i\ge0 \end{align*} \]强对偶性需要 \(f(x),c_i(x)\) 为凸函数，\(d_i(x)\) 为仿射函数，且 \(\exists x\forall i\in\vert\mathcal I\vert[c_i(x)<0]\)，即 \(c_i(x)\) 严格可行。
\[\begin{align*} \max_{\pmb\alpha,\pmb\beta:\alpha_i\ge0}\min_x\mathcal L(x,\pmb\alpha,\pmb\beta)=\min_x\max_{\pmb\alpha,\pmb\beta:\alpha_i\ge0}L(x,\pmb\alpha,\pmb\beta) \end{align*} \]
非线性可分数据集和软间隔
通过引入一个松弛变量 \(\pmb\xi\)，创建软间隔来应对非线性可分的数据，相应的权重和偏置的最优化问题变为
\[\begin{align*} \pmb w^\star,b^\star&=\underset{\pmb w,b}{\arg\min}\frac12\Vert\pmb w\Vert_2^2\qquad\,\text{s.t.}\quad\hat y\ge1\quad\forall(\pmb x,y)\in(\mathcal X,Y)\\ &\xlongequal{\text{add }\pmb\xi}\underset{\pmb w,b}{\arg\min}\min_{\xi_i\ge0}\left\lbrace\frac12\Vert\pmb w\Vert_2^2+C\sum_{i\in\vert\mathcal X\vert}\xi_i\right\rbrace\\ &\qquad\quad\text{s.t.}\quad\hat y_i\ge1-\xi_i \end{align*} \]添加了松弛变量后，可以将误分类的情况考虑进去。可以考虑 \(\hat y_i\) 对 \(\xi_i\) 的影响，比如在超平面上的情况 \(\hat y_i=0\) 和误分类的情况 \(\hat y_i<0\)。
\[\begin{align*} \hat y_i\ge1&\implies\min\xi_i=0\\ \hat y_i=0&\implies\min\xi_i=1\\ \hat y_i<0&\implies\min\xi_i=1-\hat y_i \end{align*} \]如果 \(0<\hat y_i<1\)，此时实际上并没有出现误分类的情况，可以通过等比例增大 \(\pmb w,b\) 来增大到 \(\hat y_i\ge0\)，也可以为其添加相应的松弛变量 \(\xi_i>0\)，而这两者都与目标优化问题相悖，究竟采用哪种方法要考虑到作为松弛变量的系数 \(C\)，也就是对误分类的惩罚系数。更大的 \(C\) 强调训练正确分类（减小 \(\xi_i\)），更小的 \(C\) 强调减小 \(\pmb w\)。
重新创建拉格朗日函数，求导。
\[\begin{align*} \mathcal L(\pmb w,b,\pmb\xi,\pmb\lambda,\pmb\mu)&=\frac12\Vert\pmb w\Vert_2^2+C\sum_{i\in\vert\mathcal X\vert}\xi_i-\sum_{i\in\vert\mathcal X\vert}\lambda_i[y(\pmb w^T\pmb\Phi(\pmb x)+b)-1+\xi_i]-\sum_{i\in\vert\mathcal X\vert}\mu_i\xi_i\\ \nabla_{\pmb w}\mathcal L(\pmb w,b,\pmb\xi,\pmb\lambda,\pmb\mu)&=\pmb w-\sum_{i\in\vert\mathcal X\vert}\lambda_iy_i\pmb\Phi(\pmb x_i)=\pmb0\\ \nabla_b\mathcal L(\pmb w,b,\pmb\xi,\pmb\lambda,\pmb\mu)&=-\sum_{i\in\vert\mathcal X\vert}\lambda_iy_i=0\\ \nabla_{\pmb\xi}\mathcal L(\pmb w,b,\pmb\xi,\pmb\lambda,\pmb\mu)&=C-\pmb\lambda-\pmb\mu=0\\[1em] \mathcal L(\pmb w,b,\pmb\xi,\pmb\lambda,\pmb\mu)&=\sum_{i\in\vert\mathcal X\vert}\lambda_i-\frac12\sum_{i\in\vert\mathcal X\vert}\sum_{j\in\vert\mathcal X\vert}\lambda_i\lambda_jy_iy_j\pmb\Phi(\pmb x_i)^T\pmb\Phi(\pmb x_j)\\ \pmb\lambda^\star&=\underset{\pmb\lambda}{\arg\max}\left\lbrace\sum_{i\in\vert\mathcal X\vert}\lambda_i-\frac12\sum_{i\in\vert\mathcal X\vert}\sum_{j\in\vert\mathcal X\vert}\lambda_i\lambda_jy_iy_j\pmb\Phi(\pmb x_i)^T\pmb\Phi(\pmb x_j)\right\rbrace\\ &\quad\ \,\text{s.t.}\ \quad0\le\lambda_i\le C,\sum_{i\in\vert\mathcal X\vert}\lambda_iy_i=0 \end{align*} \]从结果上来看，\(\pmb\lambda^\star\) 的约束添加了一条 \(\lambda_i\le C\)，除此之外与硬间隔的版本相同，支持向量的条件不变（\(\lambda_i>0\)）但从满足 \(\hat y_i=1\) 变为满足 \(\hat y_i\le1\)。
核技巧
\[\begin{align*} \pmb\lambda^\star&=\underset{\pmb\lambda}{\arg\max}\left\lbrace\sum_{i\in\vert\mathcal X\vert}\lambda_i-\frac12\sum_{i\in\vert\mathcal X\vert}\sum_{j\in\vert\mathcal X\vert}\lambda_i\lambda_jy_iy_j\pmb\Phi(\pmb x_i)^T\pmb\Phi(\pmb x_j)\right\rbrace\\ &\quad\ \,\text{s.t.}\ \quad0\le\lambda_i\le C,\sum_{i\in\vert\mathcal X\vert}\lambda_iy_i=0\\ b^\star&=\frac1{\vert\mathcal S\vert}\sum_{j\in\vert\mathcal S\vert}\left[y_j^\star-\sum_{i\in\vert\mathcal X\vert}\lambda_i^\star y_i\pmb\Phi(\pmb x_i)^T\pmb\Phi(\pmb x_j^\star)\right]\\ f^\star(\pmb x)&=\sum_{i\in\vert\mathcal S\vert}\lambda_i^\star y_i\pmb\Phi(\pmb x_i)^T\pmb\Phi(\pmb x)+b^\star\\ \end{align*} \]观察上面三个公式，可以看到三者的计算都需要特征空间的内积 \(\pmb\Phi(\pmb x_i)^T\pmb\Phi(\pmb x_j)\)。因此舍弃直接计算特征矩阵 \(\pmb\Phi=[\pmb\Phi(\pmb x_1),\pmb\Phi(\pmb x_2),\ldots,\pmb\Phi(\pmb x_N)]^T\) 再计算内积，考虑核矩阵 \(\pmb K=\pmb\Phi\pmb\Phi^T\) 和核函数 \(K(\pmb x_i,\pmb x_j)=\pmb K_{i,j}=\pmb\Phi(\pmb x_i)^T\pmb\Phi(\pmb x_j)\)，\(K:\mathcal X\times\mathcal X\to\mathbb R\)。因为特征空间一般远大于输入空间，如果能跳过特征空间的计算，直接获得核函数的值，那么计算量会大大减小。此时不是在计算数据的特征，而是两个数据之间的关系。
核函数
考虑如何构建核函数。显然 \(\pmb K\) 为对称的半正定矩阵（\(\pmb x^T\pmb K\pmb x\ge0,\forall\pmb x\in\mathbb R^N\)），也是关于 \(\pmb\Phi\) 行向量的 Gram 矩阵。而反过来对于任何一个对称的半正定的关于 \(K(\pmb x_i,\pmb x_j)\) 的 Gram 矩阵，也必定可以构造某个从欧几里得空间下的输入空间到希尔伯特空间下的特征空间的函数 \(\pmb\Phi:\mathcal X\to\mathcal H,\text{ where }\mathcal X\subseteq\mathbb R^N\) 使得 \(\pmb K=\pmb\Phi\pmb\Phi^T\)。保证 \(\pmb K\) 作为 Gram 矩阵的半正定性，可以导出如下构建方法。（证明略）
如果存在两个核函数 \(K_1,K_2\)，那么可以根据如下规则构建新的核函数
\[\begin{align*} K(\pmb x_i,\pmb x_j)&=cK_1(\pmb x_i,\pmb x_j),c>0\\ K(\pmb x_i,\pmb x_j)&=K_1(\pmb x_i,\pmb x_j)+K_2(\pmb x_i,\pmb x_j)\\ K(\pmb x_i,\pmb x_j)&=K_1(\pmb x_i,\pmb x_j)K_2(\pmb x_i,\pmb x_j)\\ K(\pmb x_i,\pmb x_j)&=f(\pmb x_i)K_1(\pmb x_i,\pmb x_j)f(\pmb x_j) \end{align*} \]组合这些规则，可以得到核函数的任意（包括无穷）线性组合 \(\sum_{k=0}^\infty\alpha_kK\)。如果取 \(\alpha_k=1/k!\)，则 \(\sum_{k=0}^\infty\alpha_kK=\exp K\)，可以发现与其相对应的特征空间达到了无穷维。而根据泰勒级数展开，实际上可以获得绝大多数基本函数，但其中最基本的 \(K\) 还是两个向量的某种线性或非线性转换的内积。其中 \(f(\pmb x)\) 也赋予了核函数选择很大的自由性，\(f(\pmb x)\) 可以是选择向量的某一维，也可以是其他复杂的函数。
由于选择核函数的自由性，所以选择和设计核需要观察数据的特征。比较常见的高斯核 \(\exp(-\gamma\Vert\pmb x_i-\pmb x_j\Vert_2^2)\) 实际上等同于 \(1,\Vert\pmb x_i\Vert_2^2,\Vert\pmb x_i\Vert_2^4,\ldots\) 这无穷多个核的线性组合，只不过每个核的权重为 \(\sqrt{2/k!}\)，下降得比较快。分解高斯核，不失一般性地令 \(\gamma=1\)，可以看到特征空间确实是无限维的。
\[\begin{align*} \exp(-\Vert\pmb x_i-\pmb x_j\Vert_2^2)&=\exp(-\pmb x_i^T\pmb x_i-\pmb x_j^T\pmb x_j+2\pmb x_i^T\pmb x_j)\\ &={\exp(2\pmb x_i^T\pmb x_j)\over\exp\Vert\pmb x_i\Vert_2^2\cdot\exp\Vert\pmb x_j\Vert_2^2}\\ &={\sum_{k=0}^\infty(2\pmb x_i^T\pmb x_j)^k/k!\over\exp\Vert\pmb x_i\Vert_2^2\cdot\exp\Vert\pmb x_j\Vert_2^2}\\ &=\sum_{k=0}^\infty{(\sqrt2\pmb x_i^T)^k\over\sqrt{k!}\exp\Vert\pmb x_i\Vert_2^2}{(\sqrt2\pmb x_j)^k\over\sqrt{k!}\exp\Vert\pmb x_j\Vert_2^2}\\ &=\pmb\Phi(\pmb x_i)^T\pmb\Phi(\pmb x_j),\\ \pmb\Phi(\pmb x)&=\exp(-\Vert\pmb x\Vert_2^2)\begin{bmatrix} \sqrt{2^0\over0!}\Vert\pmb x\Vert_2^0\\ \sqrt{2^1\over1!}\Vert\pmb x\Vert_2^2\\ \sqrt{2^2\over2!}\Vert\pmb x\Vert_2^4\\ \vdots \end{bmatrix} \end{align*} \]只有维数够多，理论上来说甚至可以做的让每个维中都只有一个数据为正类，其余数据为负类，使得所有数据都是线性可分的。
核函数是基函数内积的线性组合这点很重要，\(K(\pmb x_i,\pmb x_j)=\sum\alpha\pmb\Phi(\pmb x_i)^T\pmb\Phi(\pmb x_j)\)
多分类
在应对多分类的情况时与逻辑回归 Logistic Regression 有着相同的两种策略，one-vs-one 和 one-vs-rest，再选择其中 \(f^\star(\pmb x)\) 最大的一个类即可。
与岭回归的关系
软间隔的优化问题
\[\begin{align*} \min_{\pmb w,b,\pmb\xi}\left\lbrace\frac12\Vert\pmb w\Vert_2^2+C\sum_{i\in\vert\mathcal X\vert}\xi_i\right\rbrace\quad\ \,\text{s.t.}\quad\hat y_i\ge1-\xi_i,\xi_i\ge0 \end{align*} \]实际上等价于
\[\begin{align*} \min_{\pmb w,b}\left\lbrace\sum_{i\in\vert\mathcal X\vert}\max[0,1-\hat y_i]+\lambda\Vert\pmb w\Vert_2^2\right\rbrace \end{align*} \]是常见的损失函数加权重惩罚的形式，不过这里损失函数为 \(\sum\max[0,1-\hat y]\)，其中 \(\hat y=y(\pmb w^T\pmb\Phi(\pmb x)+b)\)，只有支持向量才会被损失函数计算到。
比较之下，岭回归的损失函数为 \(\sum[y-\pmb w^T\pmb\Phi(\pmb x)-b]^2\)。
- \(y=1\)，\(\max[0,1-\pmb w^T\pmb\Phi(\pmb x)-b]\) 和 \([1-\pmb w^T\pmb\Phi(\pmb x)-b]^2\)；
- \(y=-1\)，\(\max[0,1+\pmb w^T\pmb\Phi(\pmb x)+b]\) 和 \([1+\pmb w^T\pmb\Phi(\pmb x)+b]^2\)；
岭回归更加平缓，软间隔更加陡峭。对于误分类情况不多的情况，软间隔表现得更好；反之，岭回归会表现得更好。
总结
从支持向量机和岭回归的对比可以看出，支持向量机的结构实际上是比较简单的。对于支持向量机，需要学习的点在于
- 通过拉格朗日函数和对偶问题解决最优化问题的方法；
- 具有普遍适用性的核技巧和核函数。