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 使得复杂度比较小，即：
\[{\cal H}=\{{\bf x}\mapsto \text{sign}({\bf w\cdot x}+b):{\bf w}\in \mathbb{R} ^N-\{{\bf 0}\}, b\in \mathbb{R}\}
\]
也就是通过超平面 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})\)：
\[\rho _h({\bf x})=\frac{|{\bf w\cdot x}+b|}{\Vert {\bf w}\Vert _2}
\]
小证一下：设沿 \(\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 应取到最大的几何距离，有：
\[\begin{aligned}
{\bf w},b &= \argmax _{{\bf w},b\ :\ y _i({\bf w\cdot x} _i+b)\ge 0}\min _i \frac{|{\bf w\cdot x} _i+b|}{\Vert {\bf w}\Vert} \\
&= \argmax _{{\bf w},b}\ \min _i \frac{y _i({\bf w\cdot x} _i+b)}{\Vert {\bf w}\Vert} \qquad;\text{假设样本线性可分} \\
&= \argmax _{{\bf w},b\ :\ \min y _i({\bf w\cdot x} _i+b)=1}\ \frac{1}{\Vert {\bf w}\Vert} \qquad;\text{加条件约束分式上下变动} \\
&= \argmax _{{\bf w},b\ :\ y _i({\bf w\cdot x} _i+b)\ge 1}\ \frac{1}{\Vert {\bf w}\Vert} = \argmin _{{\bf w},b\ :\ y _i({\bf w\cdot x} _i+b)\ge 1}\ \frac{1}{2}{\Vert \bf w\Vert} ^2
\end{aligned}
\]
从而得到如下对 \(({\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\)，得到对偶问题：
\[{\boldsymbol{\alpha}} = \argmax _{\boldsymbol{\alpha}} {\cal L}=\argmax _{\boldsymbol{\alpha}} \sum _{i=1} ^m \alpha _i - \frac{1}{2}\sum _{i=1} ^m \sum _{j=1} ^m (\alpha _i y _i {\bf x} _i) \cdot (\alpha _j y _j {\bf x} _j) \\
subject\ to: {\boldsymbol{\alpha}}\ge {\bf 0}\wedge \Sigma _{i=1} ^{m}\alpha _i y _i = 0
\]
这个问题同样是凸优化问题（\(\nabla ^2 _{\boldsymbol{\alpha}}{\cal L}\preceq\bf 0\)，concave，且为二次项，是 QP 问题，可用 SMO 算法解决）
解出 \({\boldsymbol{\alpha}}\) 后，就能得到对偶原问题的解：
\[{\bf w}=\sum _{i=1} ^{m}\alpha _i y _i {\bf x} _i,\quad b=y _{sv} - {\bf w \cdot x} _{sv}\quad;\text{for any support vector $sv$}
\]
从而得到假设平面 \(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
依然认为样本标签为通过某个超平面映射、始终是线性可分的
我们给泛化误差（的期望）一个上界，分析式子：
\[\begin{aligned}
\mathbb{E} _{S\sim \cal D ^m}[R(h _S)]
&= \mathbb{E} _{S\sim \cal D ^m}\left[\mathbb{E} _{x\sim \cal D}[1 _{h _S(x)\ne y}]\right] \\
&= \mathbb{E} _{S\sim \cal D ^m, x\sim \cal D}\left[1 _{h _S(x)\ne y}\right] \\
&= \mathbb{E} _{S'\sim \cal D ^{m+1}}\left[1 _{h _{S‘/{x _1}}(x _1)\ne y _1}\right]=\mathbb{E} _{S'\sim \cal D ^{m+1}}\left[1 _{h _{S’/{x _2}}(x _2)\ne y _2}\right]=\cdots \\
&= \mathbb{E} _{S'\sim \cal D ^{m+1}}\left[\frac{1}{m+1}\sum _{i=1} ^{m+1} 1 _{h _{S'/\{x _i\}}(x _i)\ne y _i}\right]
\end{aligned}
\]
期望式内类似对 \(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\) 贡献了误差，那么它必定是支持向量之一，否则去掉它不会对分类平面造成影响
结合上述式子，得到：
\[\mathbb{E} _{S\sim \cal D ^m}[R(h _S)]\le \mathbb{E} _{S'\sim \cal D ^{m+1}}[\frac{N _{SV}(S')}{m+1}]
\]
这就是我们的上界。一般来说支持向量不会太多，所以右式应该不会很大；但是这个式子只对所有情况的平均值给出上界，并不是之前提到 PAC 形式。后面会给出更强的 high-probability bounds。
5.3 Non-separable case