5.1 Linear classification
考虑如下问题：\(\mathbb{R} ^N\) 上的 \(\cal X\) 服从某个未知分布 \(\cal D\)，并由目标函数 \(f:\cal X\to Y\) 映射到 \(\{-1, +1\}\)。根据采样 \(S=(({\bf x} _1, y _1),\dotsb, ({\bf x} _m, y _m))\) 确定一个二分类器 \(h\in \cal H\)，使得其泛化误差 \(R _{\cal D}(h)=\Pr _{{\bf x}\sim \cal D}[h({\bf x})\ne f({\bf x})]\) 尽量小
选择线性分类器 linear classifier 使得复杂度比较小，即：
也就是通过超平面 hyperplane 二分类。另外 \({\bf w\cdot x}+b\) 和 \({\bf -w\cdot x}-b\) 代表同一个超平面但是标签取反，可以把 \(\bf 0\) 代入判断一下正例位置。
5.2 Separable case
本节假设样本 \(S\) 线性可分，也就是样本的标签是某个待学习的超平面 \(({\bf w},b)\) 对样本进行映射得到的：\(\forall i\in[m],y _i({\bf w \cdot x _{\it i}}+b)\ge 0\)
SVM 考虑几何间隔 geometric margin
定义 Geometric margin
点 \(\bf x\) 和超平面 \(h:({\bf w},b)\) 的几何间隔，定义为两者的欧几里得距离 \(\rho _h({\bf x})\)：
小证一下：设沿 \(\bf x\) 方向与平面交于 \(\bf x'\)，那么距离就是 \(\bf x-x'\) 在 \(\bf w\) 方向的投影长度，即 \(\rho={\bf |(x-x')\cdot\frac{w}{\Vert w\Vert}|}=\frac{\bf |w\cdot x-w\cdot x'|}{\bf \Vert w\Vert}=\frac{|({\bf w\cdot x}+b)-({\bf w\cdot x'}+b)|}{\bf \Vert w\Vert}=\frac{|{\bf w\cdot x}+b|}{\bf \Vert w\Vert}\)
定义线性分类器对样本 \(S\) 的几何距离为 \(\rho _h=\min\rho _h({\bf x} _i)\)，而 SVM 应取到最大的几何距离，有：
从而得到如下对 \(({\bf w}, b)\) 的凸优化问题：
\[\min _{{\bf w}, b} \frac{1}{2}\Vert {\bf w} \Vert ^2 \\ subject\ to: g _i({\bf w},b)=1 - y _i({\bf w\cdot x} _i + b)\le 0,\forall i\in [m] \]根据以二阶导定义的凸函数，由于 \(F:{\bf w\to \Vert w\Vert} ^2/2\) 的 Hessian \(\nabla ^2 F=\bf I\) 是正定的，故 \(F\) 是严格的凸函数；而约束 \(g _i\) 均为仿射函数，故该优化问题有唯一解。
（这类目标函数为平方次、约束为仿射的问题，属于二次规划问题 quadratic programming (QP)，已有大量相关算法；对于 SVM 问题有 block coordinate descent 等算法）
由于约束都是仿射，该问题与对偶问题等价，因此转到对偶问题：
引入 Lagrange 变量 \({\boldsymbol{\alpha}}=(\alpha _1, \dotsb, \alpha _m)'\ge 0\)，定义 Lagrangian \({\cal L}({\bf w}, b, {\boldsymbol{\alpha}})\) 并给出最优解的 KKT 条件：
\[{\cal L}({\bf w}, b, {\boldsymbol{\alpha}}) = \frac{1}{2}\Vert {\bf w} \Vert ^2 + \sum _{i=1} ^m \alpha _i [1- y _i({\bf w\cdot x} _i + b)]\\ \begin{aligned} & \nabla _{\bf w}{\cal L}={\bf w}-\sum _{i=1} ^{m}\alpha _i y _i {\bf x} _i = 0 &&\implies {\bf w}=\sum _{i=1} ^{m}\alpha _i y _i {\bf x} _i \\ & \nabla _{b}{\cal L}=-\sum _{i=1} ^{m}\alpha _i y _i = 0 &&\implies \sum _{i=1} ^{m}\alpha _i y _i = 0 \\ & {\boldsymbol{\alpha}}\cdot {\bf g}({\bf w},b)=0 &&\implies \forall i\in [m],\alpha _i =0\vee y _i({\bf w\cdot x} _i + b)=1 \end{aligned} ;\text{KKT} \]根据条件，\(\bf w\) 为若干 \(\alpha _i\) 不为零的样本 \({\bf x} _i\)（称为支持向量 support vector）的线性组合，且这些向量必定落在 \({\bf w\cdot x} + b=\pm 1\) 的平面上。注意到即使 \(({\bf w},b)\) 有唯一解，\(\boldsymbol{\alpha}\) 却不一定唯一，因为只需要 \(N+1\) 个向量就能定义一个 \(N\) 维平面
利用 KKT 条件消去 \({\bf w}, b\)，得到对偶问题：
这个问题同样是凸优化问题（\(\nabla ^2 _{\boldsymbol{\alpha}}{\cal L}\preceq\bf 0\)，concave，且为二次项，是 QP 问题，可用 SMO 算法解决）
解出 \({\boldsymbol{\alpha}}\) 后，就能得到对偶原问题的解：
从而得到假设平面 \(h(\bf x)\)
\[h({\bf x})=\text{sgn}({\bf w\cdot x} + b)=\text{sgn}\left(\sum _{i=1} ^m \alpha _i y _i({\bf x} _i\cdot {\bf x}) + b\right) \]注意到假设平面只用到支持向量与输入向量的内积，我们之后在这一点上可以做文章，例如引入核方法
最后，几何间隔 \(\rho ^2=1/{\Vert\bf w \Vert _2 ^2}=1/\sum _{i=1} ^m \alpha _i=1/{\Vert\boldsymbol{\alpha}\Vert _1}\)，证明只需上述求 \(b\) 的式子两边同乘 \(\sum \alpha y\) 即可
Leave-one-out analysis
依然认为样本标签为通过某个超平面映射、始终是线性可分的
我们给泛化误差（的期望）一个上界，分析式子：
期望式内类似对 \(m+1\) 个样本使用留一法，因此定义算法 \(\cal A\) 对样本 \(S'=((x _1,y _1),\dots, (x _{m+1}, y _{m+1}))\) 的 Leave-one-out error \(\widehat{R} _\text{LOO}({\cal A})\)，为用剩余样本分类留出样本的平均误差，并对其放缩：
\[\widehat{R} _\text{LOO}({\cal A}) = \frac{1}{m+1}\sum _{i=1} ^{m+1} 1 _{h _{S'/\{x _i\}}(x _i)\ne y _i} \le \frac{N _{SV}(S')}{m+1} \]其中 \(N _{SV}(S')\) 是用 SVM 分类 \(S'\) 得到的支持向量个数；显然若某个 \(x _i\) 贡献了误差，那么它必定是支持向量之一，否则去掉它不会对分类平面造成影响
结合上述式子，得到：
这就是我们的上界。一般来说支持向量不会太多，所以右式应该不会很大；但是这个式子只对所有情况的平均值给出上界，并不是之前提到 PAC 形式。后面会给出更强的 high-probability bounds。