Preface

本文对于SVM（Support Vector Machine，支持向量机）的做了一些准备工作，并在接下来的几篇文章正式初步学习SVM。
主要内容：
Notation（符号约定）
Functional Margins And Geometric Margins（函数间隔和几何间隔 ）
Optimal Margin Classifier（最有间隔分类器）
Primal Problem（原始问题）
Dual Optimization Problem（对偶优化问题）

Notation

在SVM学习中我们将改变之前的学习习惯：

1. 分类标识由 y∈{0,1}→y∈{−1,1}$y\in \{0,1\}\to y\in \{-1,1\}$ ，来作为分类的标识来区分不同类别。例如 y=−1$y=-1$ 标识类别一， y=1$y=1$ 标识类别二。
2. 假设函数由 hθ(x)=g(θTx),x∈Rn+1→hw,b(x)=g(wTx+b),x∈Rn$h_{\theta }(x)=g({\theta }^{T}x),x\in {\mathbb{R}}^{n+1}\to h_{w,b}(x)=g(w^{T}x+b),x\in {\mathbb{R}}^n$ 。
   其中，hw,b(x)=g(wTx+b),x∈Rn$h_{w,b}(x)=g(w^{T}x+b),x\in {\mathbb{R}}^n$ 中的w与b分别对应于 hθ(x)=g(θTx)$h_{\theta }(x)=g({\theta }^{T}x)$ 中的对应关系为：
   ω=[θ1,θ2...θn]T$\omega =[{\theta }_1,{\theta }_2...{\theta }_n{]}^T$
   b=θ0$b={\theta }_0$

Functional Margins

定义：一个超平面 (w,b)$(w,b)$ 和某个特定的训练样本 (xi,yi)$(x_i,y_i)$ 相关的函数间隔为：

γ^(i)=y(i)(wTx(i)+b)(1)$\begin{array}{}\text{(1)}& {\hat{\gamma }}^{(i)}=y^{(i)}(w^T{x}^{(i)}+b)\end{array}$

超平面 (w,b)$(w,b)$ 表示的是由参数 w,b$w,b$ 确定的分界。

如果需要 γ^(i)${\hat{\gamma }}^{(i)}$ 获得一个较大的值，那么：
当 y(i)=1$y^{(i)}=1$ 时，需要 wTx(i)+b$w^T{x}^{(i)}+b$ 远大于0；
当 y(i)=−1$y^{(i)}=-1$ 时，需要 wTx(i)+b$w^T{x}^{(i)}+b$ 远小于0；

以及当 γ^(i)=y(i)(wTx(i)+b)>0${\hat{\gamma }}^{(i)}=y^{(i)}(w^T{x}^{(i)}+b)>0$ 时，我们认为分类结果是正确的。

定义：一个超平面 (w,b)$(w,b)$ 和整个的训练集中的所有训练样本 (xi,yi)$(x_i,y_i)$ 相关的函数间隔为：

γ^(i)=mini=1,2,...,mγ^(i)(2)$\begin{array}{}\text{(2)}& {\hat{\gamma }}^{(i)}={\text{min}}_{i=1,2,...,m}{\hat{\gamma }}^{(i)}\end{array}$

Geometric Margins

通过上图我们可以知道，一个样本 (x(i),y(i))$(x^{(i)},y^{(i)})$ A点到超平面 wTx+b=0$w^{T}x+b=0$ 的几何间隔为 γ(i)${\gamma }^{(i)}$ ，且 w∥w∥$\frac{w}{\Vert w\Vert }$ 为超平面 wTx+b=0$w^{T}x+b=0$ 指向A点方向的单位向量，A点 (x(i),y(i))$(x^{(i)},y^{(i)})$ 在超平面 wTx+b=0$w^{T}x+b=0$ 上的投影B点为：

x(i)−γ(i)w∥w∥(3)$\begin{array}{}\text{(3)}& x^{(i)}-{\gamma }^{(i)}\frac{w}{\Vert w\Vert }\end{array}$

同时，由于B在超平面上，所以：

wT(x(i)−γ(i)w∥w∥)+b=0(4)$\begin{array}{}\text{(4)}& w^T(x^{(i)}-{\gamma }^{(i)}\frac{w}{\Vert w\Vert })+b=0\end{array}$

• 注：wTw=∥w∥2$w^{T}w=\Vert w{\Vert }^2$ 。

所以，我们可以得出几何间隔为 γ(i)${\gamma }^{(i)}$ ：

γ(i)=wTx(i)+b∥w∥=(w∥w∥)Tx(i)+b∥w∥(5)$\begin{array}{}\text{(5)}& {\gamma }^{(i)}=\frac{w^T{x}^{(i)}+b}{\Vert w\Vert }=(\frac{w}{\Vert w\Vert }{)}^T{x}^{(i)}+\frac{b}{\Vert w\Vert }\end{array}$

由于我们总是考虑对训练样本的争取分类，所以将几何间隔为 γ(i)${\gamma }^{(i)}$ 一般化为：

γ(i)=y(i)(wTx(i)+b∥w∥=(w∥w∥)Tx(i)+b∥w∥)(6)$\begin{array}{}\text{(6)}& {\gamma }^{(i)}=y^{(i)}(\frac{w^T{x}^{(i)}+b}{\Vert w\Vert }=(\frac{w}{\Vert w\Vert }{)}^T{x}^{(i)}+\frac{b}{\Vert w\Vert })\end{array}$

如果 ∥w∥=1$\Vert w\Vert =1$ ，γ^(i)=γ(i)${\hat{\gamma }}^{(i)}={\gamma }^{(i)}$ 。更一般的有，γ(i)=γ^(i)∥w∥${\gamma }^{(i)}=\frac{{\hat{\gamma }}^{(i)}}{\Vert w\Vert }$ 。

定义：一个超平面 (w,b)$(w,b)$ 和整个的训练集中的所有训练样本 (xi,yi)$(x_i,y_i)$ 相关的几何间隔为：

γ(i)=mini=1,2,...,mγ(i)(7)$\begin{array}{}\text{(7)}& {\gamma }^{(i)}={\text{min}}_{i=1,2,...,m}{\gamma }^{(i)}\end{array}$

Optimal Margin Classifier

最优间隔是指调整参数 w,b$w,b$ 使得几何间隔 γ(i)${\gamma }^{(i)}$ 最大。

Step1：条件假设

∥w∥=1$\Vert w\Vert =1$ ， |w1|=1$|w_1|=1$ ， ∥w∥+|w|2=?$\Vert w\Vert +{|w|}^2=?$ 只需要选一个条件。
对于上述条件的解释：
调整参数 w,b$w,b$ 对于超平面 wTx+b=0$w^{T}x+b=0$ 无影响，例如将 w,b$w,b$ 扩大两倍 2w,2b$2w,2b$ 得到 2wTx+2b=0→2∗(wTx+b)=0$2w^{T}x+2b=0\to 2\ast (w^{T}x+b)=0$ ，即超平面位置不发生变化。所以我们可以通过缩放 w,b$w,b$ 来满足上述条件。
|w1|$|w_1|$ 表示 w$w$ 的第一个位置的数字为1。

Step2：公式推演

首先看看函数间隔，你给参数前乘一个大于零的数，函数间隔就会变大，这个不好。再来看看几何间隔，由于要将参数单位化，所以就不受参数的非因素影响，就是说当几何间隔最大的时候，真的就是训练样本距离超平面最大。这样用几何间隔就可以非常健壮的描述样本与超平面之间的距离。

形式一：
maxγ,w,bγs.t.y(i)(wTx(i)+b)≥γ，i=1,...,m∥w∥=1(8)$$\begin{gathered} \begin{array}{}\text{(8)}& {\text{max}}_{\gamma ,w,b}\gamma \\ s.t.y^{(i)}(w^T{x}^{(i)}+b)\ge \gamma ，i=1,...,m \\ \Vert w\Vert =1\end{array} \end{gathered}$$
形式二：
maxγ,w,bγ^∥w∥s.t.y(i)(wTx(i)+b)≥γ^，i=1,...,m(9)$$\begin{gathered} \begin{array}{}\text{(9)}& {\text{max}}_{\gamma ,w,b}\frac{\hat{\gamma }}{\Vert w\Vert } \\ s.t.y^{(i)}(w^T{x}^{(i)}+b)\ge \hat{\gamma }，i=1,...,m\end{array} \end{gathered}$$
形式三：
minγ,w,b∥w∥2s.t.y(i)(wTx(i)+b)≥γ^，i=1,...,mγ^=1s.t.miny(i)(wTx(i)+b)=1ormaxγ,w,b1∥w∥s.t.y(i)(wTx(i)+b)≥γ^，i=1,...,mγ^=1s.t.miny(i)(wTx(i)+b)=1(10)$$\begin{gathered} \begin{array}{}\text{(10)}& {\text{min}}_{\gamma ,w,b}{\Vert w\Vert }^2 \\ s.t.y^{(i)}(w^T{x}^{(i)}+b)\ge \hat{\gamma }，i=1,...,m \\ \hat{\gamma }=1s.t.\text{min}{y}^{(i)}(w^T{x}^{(i)}+b)=1 \\ or \\ {\text{max}}_{\gamma ,w,b}\frac{1}{\Vert w\Vert } \\ s.t.y^{(i)}(w^T{x}^{(i)}+b)\ge \hat{\gamma }，i=1,...,m \\ \hat{\gamma }=1s.t.\text{min}{y}^{(i)}(w^T{x}^{(i)}+b)=1\end{array} \end{gathered}$$

Lagrange Duality

我们会使用拉格朗日乘数法来解决关于约束优化问题：
我们的目标函数是：

接下来我们构造拉格朗日算子：

然后分别对参数进行求导，并令其为零：

然后解上述等式构成的方程组，求得 wi,βi$w_i,{\beta }_i$ 。最后将 wi,βi$w_i,{\beta }_i$ 带回到目标函数。

Primal Problem

在这里我们构造出原始优化问题的目标函数：

现在我们开始使用拉格朗日乘数法来解决原始优化问题：
我们定义一个增广拉格朗日函数，在这里 αi${\alpha }_i$ 与 βi${\beta }_i$ 为拉格朗日乘数：

定义一个 θp(w)${\theta }_p(w)$ 函数，这里的下标p表示primal：

所以：

所以 minθp(w)$\text{min}{\theta }_p(w)$ 就是我们的目标问题——原始优化问题：

Dual Optimization Problem

我们定义函数 θD(α,β)${\theta }_D(\alpha ,\beta )$ ，其中D表示duo（对偶）：

现在我们定义对偶优化问题：

定义： p∗$p^{\ast }$ 是原始优化问题 minθp(w)$\text{min}{\theta }_p(w)$ 的最优值。

定义： d∗$d^{\ast }$ 是原始优化问题 maxθD(α,β)$\text{max}{\theta }_D(\alpha ,\beta )$ 的最优值。

有这样一个在通常条件下成立的事实： d∗≤p∗$d^{\ast }\le p^{\ast }$ ，即对偶优化问题的最优值小于等于原始优化问题的最优值。更一般的有，对于某个函数 f(x)$f(x)$ 而言，总是存在 maxminf(x)≤minmaxf(x)$\text{max}\text{min}f(x)\le \text{min}\text{max}f(x)$ 。
For example：maxy∈{0,1}(minx∈{0,1}1{x=y})≤minx∈{0,1}(maxy∈{0,1}1{x=y})${\text{max}}_{y\in \{0,1\}}({\text{min}}_{x\in \{0,1\}}1\{x=y\})\le {\text{min}}_{x\in \{0,1\}}({\text{max}}_{y\in \{0,1\}}1\{x=y\})$ 。

关于对偶理论可以参考 运筹学（第四版） 清华大学出版社 第64页
对偶问题的一些性质：
1. 目标函数值相同时，各自的解为最优解
2. 若原问题有最优解，那么对偶问题也有最优解，且目标函数值相同
3. 还有互补松弛性，无界性，对称性等等

当原问题和对偶问题都取得最优解得时候，那么他们分别的目标函数也就到达了最优值。根据对偶问题的性质2，可以得到 p∗=d∗$p^{\ast }=d^{\ast }$ 那么我们就可以求解对偶问题来得到原问题 θp(w)${\theta }_p(w)$ 的最优值。

为了使得 p∗=d∗$p^{\ast }=d^{\ast }$ 我们需要满足一些条件，接下来我们开始推演 p∗=d∗$p^{\ast }=d^{\ast }$ ：
假设一： f$f$ 是一个凸函数（ f$f$ 的Hessian矩阵是半正定矩阵）。
假设二：hi$h_i$ 是仿射函数（ hi(w)=θTw+b$h_i(w)={\theta }^{T}w+b$ ，仿射的意思是这个函数任何时候都是线性的）。
假设三： gi$g_i$ 是严格可执行的（ ∃w,使得∀i,gi(w)<0$\mathrm{\exists }w,使得\mathrm{\forall }i,g_i(w)<0$）

通过这三个假设，我们得到KKT(Karush-Kuhn-Tucker conditions)条件（∃w∗,α∗,β∗，w∗是原始最优问题的解，α∗,β∗$\mathrm{\exists }{w}^{\ast },{\alpha }^{\ast },{\beta }^{\ast }，w^{\ast }是原始最优问题的解，{\alpha }^{\ast },{\beta }^{\ast }$是对偶最优问题的解，p∗=d∗$p^{\ast }=d^{\ast }$ ），我们得到KKT：

其中，α∗igi(w∗)=0${\alpha }_i^{\ast }{g}_i(w^{\ast })=0$ 成为KKT互补条件，对于 α∗i>0${\alpha }_i^{\ast }>0$ ，必有 gi(w∗)=0$g_i(w^{\ast })=0$ 。

参考资料

https://blog.****.net/xiaocainiaodeboke/article/details/50443680