在 SVM(一) 中从感知机说到硬间隔线性可分SVM的损失函数，此时损失函数是有约束条件的，无法直接计算导数为0时的参数，需要转换一下将目标函数和约束条件放到一个拉格朗日函数中 ，这也就是为什么要构造拉格朗日函数，同时引出 拉格朗日对偶式，利用对偶式来求解，并且有利于引出核函数的思想，这里简单讨论一下SVM对偶式，并给出一个具体例子来思考原始问题和对偶问题的异同点。
拉格朗日乘子
首先给定线性可分数据集 \( D={(x^{(1)}, y^{(1)}), (x^{(2)},y^{(2)}),\cdots,(x^{(N)}, y^{(N)})}\) ，其中 \( x^{(i)}\in R^n\) ， \( y^{(i)}\in {-1, +1}\) \( i = 1,2...,N\)，观察SVM的损失函数，这是一个有约束条件的损失函数，也就是说要在 约束条件中找到目标函数的最小值 ，即 \(\theta\) 在满足 \( s.t. \space y^{(i)}(\theta^Tx^{(i)}+b)\geq1\) 的基础上，最小化 \( \frac{1}{2}||\theta||^2\) ，而且是 不等式优化
$$
\begin{aligned}
&\mathop{min}_{\theta}\frac{1}{2}||\theta||^2\\
&s.t. \space y^{(i)}(\theta^Tx^{(i)}+b)\geq1
\end{aligned}\\
$$
针对此约束条件，考虑一般形式 \( f(x); \space\space s.t. \space g(x)\leq 0\) ，有2种情况(图中绿色和蓝色的两种条件)
第一种 ：图中蓝色 \( g(x)\leq 0\) 部分，目标函数的 最优解在约束条件范围外，此时就相当于约束条件为 \( g(x)=0\) ，因为 \( g(x)<0\) 的部分相较于 \( g(x)=0\) 肯定不是最优的(不够靠近目标函数的最优解嘛)，这里通过图中可以直观的看出， 切线交点 \( p^*\) 为最优点 ，是符合约束条件时的最小值，此时二者导数的方向相反，这里与2个注意点需要解释
- 为什么 \( p^*\) 是切线交点？ 可以利用反证法的思想，假如 \( p^*\) 不是切线交点，那么 一定有不为 \( 0\) 的分量使得目标函数更小一些 ，那么显然那个点不是最优点，一直移动到 \( p^*\) 点时为最优
- 为什么导数的方向相反？ 首先 \( \bigtriangledown g(x)\) 是垂直 \( g(x)=0\) 的，而最小化的目标函数 \( \bigtriangledown f(x)\) 在切线交点 \( p^*\) 位置也是垂直 \( g(x)=0\) 的， 且相反的时候为最小值 ， 相同的时候为最大值 ，这样一来就可以写成 \( \bigtriangledown f(x) + \lambda\bigtriangledown g(x) = 0\) ，这里 \( \lambda > 0\) 为一个系数， 二者向量总是可以通过 \( \lambda\) 这个系数转化为大小相等的 ，那么这样就可以构造出
$$
L(x, \lambda) = f(x) + \lambda g(x)\\
$$
为什么要这么构造也很容易理解，对 \( L(x, \lambda)\) 这个公式网回算，分别对 \( x, \lambda\) 求导等于 \( 0\)
$$
\begin{aligned}
\frac{\partial L(x, \lambda)}{\partial x} &= \bigtriangledown f(x) +\lambda\bigtriangledown g(x)&= 0\\
\frac{\partial L(x, \lambda)}{\partial \lambda} &= g(x)&= 0
\end{aligned}\\
$$
此时正好满足 \( p^*\) 点的位置二者导数相反且有一个 \( \lambda > 0\) 的系数关系和约束条件 \( g(x)=0\) ，函数 \( L(x, \lambda)\) 叫做拉格朗日函数， \( \lambda\) 为拉格朗日乘子
第二种 ：图中绿色 \( g'(x)\leq 0\) 部分，目标函数的最优解在约束条件范围内，此时就更好处理了，其实此时约束条件相当于没有，所以 \( \lambda=0\) ，综合这两种情况可以推导出
$$
\begin{cases}
\bigtriangledown f(x) +\lambda\bigtriangledown g(x) = 0 & p^* point\\
g(x)\leq 0 & origin \space s.t. \\
\lambda \geq 0 & lagrange\space multiplier\\
\lambda g(x) = 0 \end{cases}\\
$$
前三个很容易理解，上文中已经论证过了，但是 \( \lambda g(x) = 0\) 这是个什么玩意？其实该等式是上面第一种情况 \( \lambda>0 \space \& \space g(x)=0\) 和第二种情况 \(\lambda=0 \space \& \space g(x)<0\) 整合出来的，这几个不等式就是 KKT(Karush-Kuhn-Tucker)条件 ，这里需要注意的是： 原优化条件是对可行解的约束，KKT条件是对最优解的约束
此时针对最初的SVM损失函数来说，就可以转化成这样（很多的书中拉格朗日乘子会用 \( \alpha,\beta\) 表示，这里因为最初是用 \( \lambda\) 的所以一下都用 \( \lambda\) 来表示）
$$
\mathop{min}_{\theta,b}L(\theta, b, \lambda) = \frac{1}{2}||\theta||^2 + \sum_{i=1}^{N}{\lambda^{(i)}(1-y^{(i)}(\theta^Tx^{(i)}+b))} \\ s.t. \lambda^{(i)} \geq 0 ，\space i = 1,2...,N \\
$$
至此虽然是找到了 \( p^*\) 点，但是求解还是很不容易，因为目前构造拉格朗日函数目的是优化方向一样，但是如何让朗格朗日函数和原始问题的解是一样的呢？这里多出来的 \(\lambda\) 应该怎么处理掉呢？
拉格朗日对偶
为了解决上面拉格朗日函数的问题，首先直接的想法就是 让这个函数和原始问题一致 ，然后求解这个拉格朗日函数就可以了，但是如今加进来一个 \( \lambda\) 结合 KKT条件 如何让这两个问题一致呢？
首先的想法就是 在可行解区域内，也就是符合原始问题的约束条件，拉格朗日函数与原始问题一样；在可行解区域外，让拉格朗日函数取到 \( +\infty\) ，这样一来在求解 \( min\) 问题的时候，这俩问题就一样了，所以可以构造函数，设其可行解区域为 \( \Omega\) ，这里为了书写方便，不直接写SVM的形式，而是用更一般的形式目标函数为 \( f(x)\) ，约束条件为 \( g(x)\)
$$
\Theta_p(x) = \mathop{max}_{\lambda}L(x, \lambda) = f(x) +\mathop{max}_{\lambda}[\sum_{i=1}^{N}{\lambda^{(i)}g(x)}]\\
$$
对于在可行解区域内 \( x\in\Omega\) ，根据 \( \lambda^{(i)}\geq0\) ， \( g(x^{(i)})\leq0\) 可得
$$
\mathop{max}_{\lambda}[\sum_{i=1}^{N}{\lambda^{(i)}g(x)}]=0\\
$$
如果不在可行解区域内 \( x\notin\Omega\) ，则至少有1组约束条件没有满足即 \(
g_j(x)>0\) ，这时候调整 \( \lambda_j>0\) ，取 \( +\infty\) 就可以得到
$$
\mathop{max}_{\lambda}[\sum_{i=1}^{N}{\lambda^{(i)}g(x)}]=+\infty\\
$$
此时我们构造的函数
$$\Theta_p(x) = \mathop{max}_{\lambda}L(x, \lambda) =f(x) + \mathop{max}_{\lambda}[\sum_{i=1}^{N}{\lambda^{(i)}g(x)}]
$$
就与原始问题等价了，原始问题的约束条件也就没有了，然后再最小化 \( \Theta_p(x)\) 即 \( min\space\Theta_p(x)\) ，注意此时问题为 极小极大问题 ，拉格朗日对偶性就是可以把此时的极小极大问题转化为极大极小问题 （此部分的证明个人水平有限，没看懂o(╯□╰)o）即 原始问题的对偶问题如下
$$
\mathop{max}_{\lambda}\mathop{min}_{\theta, b}L(\theta, b,\lambda)=\frac{1}{2}||\theta||^2+\sum_{i=1}^{N}{\lambda^{(i)}(1-y^{(i)}(\theta^Tx^{(i)}+b))}\\
$$
这样就先求解 \( min\) 再求解 \( max\) ，求解 \(\mathop{min}_{\theta, b}L(\theta, b, \lambda)\) 即 对 \( \theta,b\) 求导为 \( 0\) 求得
$$
\begin{cases}
\frac{\partial L}{\partial \theta} = \theta -\sum_{i=1}^{N}{\lambda^{(i)}y^{(i)}x^{(i)}}=0\\
\frac{\partial L}{\partial b}=-\sum_{i=1}^{N}{\lambda^{(i)}y^{(i)}}=0
\end{cases}\\
$$
$$
\begin{cases}
\theta=\sum_{i=1}^{N}{\lambda^{(i)}y^{(i)}x^{(i)}}\\
\sum_{i=1}^{N}{\lambda^{(i)}y^{(i)}}=0
\end{cases}\\
$$
将上式带入到原始问题的对偶问题中，此部分可能看起来比较麻烦，但是并不难，带入式子即可，这里的 \( i,j\) 也只是为了区分而已，实际上并没什么区别
$$
\begin{aligned}
\mathop{min}_{\theta, b}L(\theta, b, \lambda) &=\frac{1}{2}||\theta||^2+\sum_{i=1}^{N}{\lambda^{(i)}(1-y^{(i)}(\theta^Tx^{(i)}+b))}\\
&=\frac{1}{2}||\theta||^2-\sum_{i=1}^{N}{\lambda^{(i)}y^{(i)}\theta^Tx^{(i)}}-b\sum_{i=1}^{N}{\lambda^{(i)}y^{(i)}+\sum_{i=1}^{N}{\lambda^{(i)}}}\\
&=\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}{\lambda^{(i)}\lambda^{(j)}y^{(i)}y^{(j)}x^{(i)}x^{(j)}}-\sum_{i=1}^{N}\sum_{j=1}^{N}{\lambda^{(i)}\lambda^{(j)}y^{(i)}y^{(j)}x^{(i)}x^{(j)}}+\sum_{i=1}^{N}{\lambda^{(i)}}\\
&=\sum_{i=1}^{N}{\lambda^{(i)}}-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}{\lambda^{(i)}\lambda^{(j)}y^{(i)}y^{(j)}x^{(i)}x^{(j)}}
\end{aligned}\\
$$
考虑上式的 极大化取负号变成最小化 ，结合对 \( \theta,b\) 求导为 \( 0\)
和 \( \lambda\geq0\) 就可以转化成，注意这里新增了一个约束条件为对 \( b\)
求导为 \( 0\) 时候的条件 \(\sum_{i=1}^{N}{\lambda^{(i)}y^{(i)}}=0\)
$$
\begin{aligned}
min \space & \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}{\lambda^{(i)}\lambda^{(j)}y^{(i)}y^{(j)}x^{(i)}x^{(j)}}-\sum_{i=1}^{N}{\lambda^{(i)}}\\
s.t. \space &\sum_{i=1}^{N}{\lambda^{(i)}y^{(i)}}=0\\
\space & \lambda^{(i)}\geq0，i=1,2,\cdots,N
\end{aligned}\\
$$
考虑 \( \theta=\sum_{i=1}^{N}{\lambda^{(i)}y^{(i)}x^{(i)}}\) ，假如
\( \lambda^*=(\lambda^{*(1)},\lambda^{*(2)},...,\lambda^{*(l)})^T\)
是对偶问题的解，那么肯定至少有1个 \( \lambda^{*(j)}>0\) 使得 \(y^{(j)}(\theta^*\cdot x^{(j)}+b^*)-1=0\) ，因为 间隔上至少存在1个支持向量 ，同时考虑 \( (y^{(j)})^2=1，y^{(i)}\in{-1，+1}\) 则有
$$
\begin{aligned}
&y^{(j)}(\theta^*\cdot x^{(j)}+b^*)-1=0\\
&y^{(i)}(\sum_{i=1}^{N}{\lambda^{(i)}y^{(i)}x^{(i)}x^{(j)}+b^*})=(y^{(j)})^2\\
&b^*=y^{(j)}-\sum_{i=1}^{N}{\lambda^{*(i)}y^{(i)}(x^{(i)}\cdot x^{(j)})}
\end{aligned}\\
$$
至此 \( \theta^*，b^*\) 都已经求得
$$
\begin{cases}
\theta^*=\sum_{i=1}^{N}{\lambda^{*(i)}y^{(i)}x^{(i)}}\\
b^*=y^{(j)}-\sum_{i=1}^{N}{\lambda^{*(i)}y^{(i)}(x^{(i)}\cdot x^{(j)})}
\end{cases}\\
$$
所以分类决策函数就可以写成为如下形式，注意到这里还有前面的推导中 \( (x^{(i)}\cdot x^{(j)})\) 都是单独括起来的 ，其实是表示SVM在分类决策函数中只 依赖输入 \( x\) 和训练样本的内积，这也是为什么对偶式更直接引出核函数，核函数所做的事情，就是把这个内积映射到高维空间中从而把线性不可分变为线性可分
$$
f(x)=sign(\sum_{i=1}^{N}{\lambda^{*(i)}y^{(i)}(x\cdot x^{(i)})+b^*})\\
$$
具体例子
通过上面的一通论证已经对SVM的对偶问题有了大概的理解，为了更清晰的看到是如何计算的，这里举个例子（例子来源李航老师的《统计学习方法 第二版》）分别计算原始问题和对偶问题
有3个样本点分别为 \( x^{(1)}=(3,3)^T; x^{(2)}=(4,3)^T;x^{(3)}=(1,1)^T\)
，其中 \( x^{(1)},x^{(2)}\) 为正例， \( x^{(3)}\) 为负例，求这样最大间隔分离超平面，作图如下
首先求解原始问题 ，这里为了书写公式方便，将上角标 \( i\) 挪到下角标处
$$
\begin{aligned}
\mathop{min}_{\theta,b} \space &\frac{1}{2}(\theta_1^2+\theta_2^2)\\
s.t.\space&3\theta_1+3\theta_2+b\geq1\\
&4\theta_1+3\theta_2+b\geq1\\
&-\theta_1-\theta2-b\geq1
\end{aligned}\\
$$
可解得 \( \theta_1=\theta_2=\frac{1}{2}，b=-2\) 时取得最小值，所以最大间隔超平面如下，其中 \( x^{(1)},x^{(3)}\) 为支持向量
$$
\frac{1}{2}x_1+\frac{1}{2}x_2-2=0\\
$$
然后再求解对偶问题 ， $ \theta^ , b^ $ 都与 $ \lambda^ $ 相关，则先求解 $ \lambda^ $ ，得到了 $ \lambda^* $ 也就求得了超平面参数
$$
\begin{equation} \begin{aligned}
\mathop{min}_{\lambda} \space &\frac{1}{2}\sum_{i-1}^{N}\sum_{j=1}^{N}{\lambda_i \lambda_j y_i y_j (x_i\cdot x_j)}-\sum_{i=1}^{N}{\lambda_i}\\
&=\frac{1}{2}(18\lambda_1^2+25\lambda_2^2+2\lambda_3^2+42\lambda_1 \lambda_2-12\lambda_1 \lambda_3-14\lambda_2 \lambda_3)-\lambda_1-\lambda_2-\lambda_3\\
s.t.\space&\lambda_1+\lambda_2-\lambda_3=0\\
&\lambda_i\geq0，i=1,2,3
\end{aligned} \end{equation}\\
$$
\( \lambda_3=\lambda_1+\lambda_2\) 带入目标函数中
$$
\begin{aligned}
J(\lambda_1, \lambda_2) &= 4\lambda_1^2+\frac{13}{2}\lambda_2^2+10\lambda_1 \lambda_2-2\lambda_1-2\lambda_2\\
\Rightarrow \space& \begin{cases} \frac{\partial J}{\partial \lambda_1}=8\lambda_1+10\lambda_2-2=0\\
\frac{\partial J}{\partial \lambda_2}=13\lambda_2+10\lambda_1-2=0 \end{cases}
\end{aligned}\\
$$
可以解出 \( J(\lambda_1, \lambda_2)\) 在点 \((\frac{3}{2},-1)^T\) 处取到极值，但是 注意到这里的 \( -1\) 不满足约束条件 \( \lambda_2\geq0\) ，所以 此时最小值就不在边界内而是在边界上 ，就要分别考虑 \( \lambda_1,\lambda_2\) 为 \( 0\) 的情况
$$
\begin{cases}
J(0, \frac{2}{13})=-\frac{2}{13} \space,for \space \lambda_1=0\\
J(\frac{1}{4},0)=-\frac{1}{4} \space\space\space\space, for \space \lambda_2=0
\end{cases}\\
$$
所以 \( (\lambda_1, \lambda_2, \lambda_3)=(\frac{1}{4}, 0,\frac{1}{4})^T\) 时对偶式取到极小值，通过拉格朗日乘子的特点就可以知道 \( x^{(1)},x^{(3)}\) 为支持向量， 因为该拉格朗日乘子不为 \( 0\) 所以约束条件 \( g(x)=0\) ，所以该点就是在间隔边界上的 ，然后再带入前面的 $ \theta^ , b^ $ 求得
$$
\begin{cases}
\theta^*&=\sum_{i=1}^{N}{\lambda^{*(i)}y^{(i)}x^{(i)}}&=\frac{1}{4}\times1\times(3,3)^T+0\times1\times(4,3)^T-\frac{1}{4}\times1\times(1,1)^T&=(\frac{1}{2},\frac{1}{2})^T\\
b^*&=y^{(1)}-\sum_{i=1}^{N}{\lambda^{*(1)}y^{(i)}(x^{(i)}\cdot x^{(1)})} &=1-(\frac{1}{4}\times1\times18+0\times1\times21-\frac{1}{4}\times1\times6)&=-2
\end{cases}\\
$$
与求解原始问题的一样的
总结
综上所述，硬间隔线性可分SVM对于给定的线性可分训练数据集，可以首先求解原始问题的对偶形式 \( \lambda^*\) ，再计算分类决策函数的参数 \( \theta^*,b^*\) ，从而解决问题。但是截止到目前为止，都是假设数据的硬间隔线性可分的 ，就说硬间隔是客观存在的，而在真实世界中往往有很多噪声，比如在间隔中存在杂乱的正例和负例，此时是找不出硬间隔的，这时候怎么办？ 又或者 数据本身就不是线性可分的又该如何？ 这些问题在下一次 SVM(三) 中讨论。
😛