SVM探讨

SVM探讨

目录

• SVM探讨
  • SVM算法
  • 硬间隔最大化的优化目标
    • 软间隔的支持向量探讨

SVM算法

根据处理问题的复杂度，SVM 可由简到繁分为三种：

• 线性可分支持向量机：硬间隔最大化。
• 线性支持向量机：数据分布近似线性可分，可通过软间隔最大化(惩罚因子，松弛变量)来线性分隔样本点。
• 非线性支持向量机：通过核函数提升特征维度，做个一个非线性的变换，来将非线性问题转化为线性问题。

先写出SVM定义损失函数的策略：
　　求得的超平面能够让所有点中离它最近的点具有最大间距。这样我们可以得出结论，我们更应该关心靠近中间分割面的点，让它们尽可能地远离分割面，而不是在所有点上达到最优。因此，SVM考虑局部（不关心已经确定远离的点），logistic回归考虑全局（已经远离的点可能通过调整中间线使其能够更加远离）。

硬间隔最大化的优化目标

\[\min_{w,b}{ \dfrac{1}{2} {\left\| w \right\|}^{2} }$$$$s.t.\quad y_i(wx_i + b)\ge 1,\ \ i=1,2,\ldots,m \]

　　接着构建拉格朗日函数，对每个不等式约束引入另个拉格朗日乘子 $\alpha_i \ge 0,\ i=1,2,\ldots,m $，定义拉格朗日函数：

\[\begin{eqnarray}L(w,b,\alpha) &=&\dfrac{1}{2} {\left\| w \right\|}^{2}-\sum _{ i=1 }^{ m }{ \alpha_i \left[ y_i(wx_i+b)-1 \right] }\\ &=&\dfrac{1}{2} {\left\| w \right\|}^{2}-\sum _{ i=1 }^{ m }{ \alpha_i y_i(wx_i+b) + \sum _{ i=1 }^{ m }{\alpha_i} }\\ \end{eqnarray}\]

注意：为什么构造拉格朗日函数的时候，用的是“—”而不是“+”？
　　因为标准的凸优化问题再构造拉格朗日函数的时候，不等式的优化问题是“ \(\le\) ”，而 SVM 中的不等式约束都是“ \(\ge\) ”，所以在构造拉格朗日函数的时候，取负号“—”.

由于$$\max_{w,b,\alpha}{L(w,b,\alpha)}=\dfrac{1}{2} {\left| w \right|}^{2}$$这样我们的优化目标的 原始问题 转化为等价的 广义拉格朗日函数的极小极大问题，如果将其最优解记作 \(p^*\)，则有：

\[p^*=\min_{w,b}{\max_{\alpha}{L(w,b,\alpha)}} \]

因此，对偶问题 为 广义拉格朗日函数的极大极小 问题，记其最优解为 \(d^*\)，则有：

\[d^*= \max_{\alpha}\min_{w,b}{L(w,b,\alpha)} \]

　　这里，由于原始问题先求的 max，满足：\(p^* \ge q^*\)，这称作“弱对偶”，在一些情况下，有 “\(p^* = q^*\)” ，称作“强对偶”。

　　但是由于，SVM 的优化目标和约束不等式都是凸函数(凸优化问题)，因此这里有 \(p^*=q^*\) 。同时，不等式的约束关系满足 KKT 条件——对于凸优化问题，KKT 条件是原始问题和对偶问题具有相同解(强对偶)的充分必要条件；非凸优化问题，KKT 条件为必要条件。【拉格朗日对偶性和 KKT 条件相关详细内容，可参考 李航P225】

下面是具体的求解过程：

　　(1) 求 \(\min_{w,b}{L(w,b,\alpha)}\)

　　将拉格朗日函数 \(L(w,b,\alpha)\) 对 \(w,b\) 求导，并令其等于\(0\).

\[\nabla_w L(w,b,\alpha)=w- \sum _{ i=1 }^{ m }{\alpha_iy_ix_i}$$$$\nabla_b L(w,b,\alpha)=-\sum _{ i=1 }^{ m }{\alpha_iy_i}=0$$得：$$w=\sum _{ i=1 }^{ m }{\alpha_iy_ix_i}$$$$\sum _{ i=1 }^{ m }{\alpha_iy_i}=0 \]

　　将这两个结果代回公式回到拉格朗日函数，得到 \(L(w,b,\alpha)\) 以 \(w,b\) 为自变量函数的极小值：

\[\begin{eqnarray}\min_{w,b}L(w,b,\alpha) &=&\dfrac{1}{2} {\left\| w \right\|}^{2}-\sum _{ i=1 }^{ m }{ \alpha_i y_i(wx_i+b) + \sum _{ i=1 }^{ m }{\alpha_i} }\\ &=&\dfrac{1}{2} w\bullet\sum _{ i=1 }^{ m }{\alpha_iy_ix_i} -w\sum _{ i=1 }^{ m }{ \alpha_i y_ix_i- b\sum _{ i=1 }^{ m }{ \alpha_i y_i} + \sum _{ i=1 }^{ m }{\alpha_i} }\\ &=&-\dfrac{1}{2} w\bullet\sum _{ i=1 }^{ m }{\alpha_iy_ix_i}+ \sum _{ i=1 }^{ m }{\alpha_i}\\ &=&-\dfrac{1}{2} \sum _{ i=1 }^{ m }\sum _{ j=1 }^{ m }{\alpha_i\alpha_jy_iy_jx_ix_j}+ \sum _{ i=1 }^{ m }{\alpha_i} \end{eqnarray}\]

　　(2) 求 \(\min_{w,b}{L(w,b,\alpha)}\) 对 \(\alpha\) 的极大值，将 \(min_{w,b}L(w,b,\alpha)\) 取个负号，由求极大值转化成最小值，就得到下面的最优化问题：

\[\min _{\alpha} { \dfrac{1}{2} \sum _{ i=1 }^{ m }\sum _{ j=1 }^{ m }{\alpha_i\alpha_jy_iy_jx_ix_j} - \sum _{ i=1 }^{ m }{\alpha_i} }$$$$s.t.\quad \begin{cases} \sum _{ i=1 }^{ m }{\alpha_iy_i}=0 \\ \alpha_i \ge 0,\ \ i=1,2,\ldots,m \end{cases} \]

再通过 SMO 算法得到 \(\alpha^*\) 为我们的最终解。同时再代回，可得到：

\[w^* = \sum _{ i=1 }^{ m }{\alpha^*_iy_ix_i}$$再根据分隔超平面 $y_j(wx_j + b) = 1$，得：$$b^* = y_j-\sum _{ i=1 }^{ m }{\alpha^*_iy_i\left}$$于是，我们就得到分隔超平面 $w^*x+b^*=0$ 也可写为： $$\sum _{ i=1 }^{ m }{\alpha^*_iy_i\left< x,x_i\right> + b^*}=0$$分类决策函数可写为：$$f(x)=sign (\sum _{ i=1 }^{ m }{\alpha^*_iy_i\left< x,x_i\right> + b^*})$$也就是说，分类决策函数依赖于输入样本和训练样本的内积。 #### 硬间隔最大化的支持向量 　　特别注意的是：训练数据中对应于 $\alpha^*_i > 0$ 的样本点 $(x_i,y_i)$的样本称为“**==支持向量==**” 。 　　证明：有 KKT 互补条件可知，$$\alpha_i \left[ y_i(wx_i+b)-1 \right]=0, \quad i=1,2,\ldots,m$$有，因此对应于 $\alpha^*>0$的样本 $x_i$，有 $$y_i(wx_i+b)=1$$即 $x_i$ 一定在间隔的边界上。 　　 ### 软间隔最大化 $$\min_{w,b}{ \dfrac{1}{2} {\left\| w \right\|}^{2} } + C\sum_{ i=1 }^{ m }{\xi_i}$$$$s.t.\quad \begin{cases} y_i(wx_i + b)\ge 1-\xi_i\ ,\ i=1,2,\ldots,m \\ \xi_i \ge 0\ ,\ \ i=1,2,\ldots,m \end{cases} \]

其中，惩罚因子 \(C\) 为大于0的常数，\(\xi_i\)(克西)为松弛变量。构建拉格朗日函数，对两类不等式约束引入两类拉格朗日乘子 $\alpha_i \ge 0,\ \beta_i \ge 0,\ i=1,2,\ldots,m $。定义拉格朗日函数：

\[L(w,b,\xi,\alpha,\beta)=\dfrac{1}{2} {\left\| w \right\|}^{2} + C\sum_{ i=1 }^{ m }{\xi_i}-\sum _{ i=1 }^{ m }{ \alpha_i \left[ y_i(wx_i+b)-1+\xi_i \right] - \sum_{ i=1 }^{ m }{\beta_i\xi_i}} \]

　　同样原始问题为极小极大问题，现在转化为极大极小对偶问题的解，且原问题和对偶问题具有相同的解。首先求 \(L(w,b,\xi,\alpha,\beta)\) 的关于变量 \(w,b,\xi\) 的极小值：

\[\nabla_w L(w,b,\xi,\alpha,\beta)=w- \sum _{ i=1 }^{ m }{\alpha_iy_ix_i}$$$$\nabla_b L(w,b,\xi,\alpha,\beta)=-\sum _{ i=1 }^{ m }{\alpha_iy_i}=0$$$$\nabla_{\xi_i} L(w,b,\xi,\alpha,\beta)=C-\alpha_i-\beta_i=0 \]

得：

\[w=\sum _{ i=1 }^{ m }{\alpha_iy_ix_i}$$$$\sum _{ i=1 }^{ m }{\alpha_iy_i}=0$$$$C-\alpha_i-\beta_i=0 \]

将以上结果代回来格朗日函数，得：$$\min_{w,b,\xi}L(w,b,\xi,\alpha,\beta)=-\dfrac{1}{2} \sum _{ i=1 }^{ m }\sum _{ j=1 }^{ m }{\alpha_i\alpha_jy_iy_j \left}+ \sum _{ i=1 }^{ m }{\alpha_i} $$

接着再求 \(\min_{w,b,\xi}L(w,b,\xi,\alpha,\beta)\) 对 \(\alpha\) 的极大值，同样取个负号，极大值转化为极小值问题(注意，参数 \(\beta\) 被神奇的约掉了，简化了计算；同时，虽然跟硬间隔优化目标的函数形式一样，但是约束条件不一样)：$$\min _{\alpha} { \dfrac{1}{2} \sum _{ i=1 }^{ m }\sum _{ j=1 }^{ m }{\alpha_i\alpha_jy_iy_jx_ix_j} - \sum _{ i=1 }^{ m }{\alpha_i} }$$$$\begin{eqnarray}s.t.\quad
&& \sum _{ i=1 }^{ m }{\alpha_iy_i}=0\ && C-\alpha_i-\beta_i=0\
&& \alpha_i \ge 0,\ \ i=1,2,\ldots,m\
&& \beta_i \ge 0,\ \ i=1,2,\ldots,m\
\end{eqnarray}$$第二个于是带入第四个约束约掉 \(\beta_i\) ，约束条件和简写为：$$\begin{eqnarray}s.t.\quad
&& \sum _{ i=1 }^{ m }{\alpha_iy_i}=0\
&& 0 \le \alpha_i \le C,\ \ i=1,2,\ldots,m\
\end{eqnarray}$$　　现在再比较与硬间隔的区别，发现，唯一的在于对 \(\alpha_i\) 取值上限做了个约束。

软间隔的支持向量探讨

　　同样，根据KKT 的互补条件：

\[\alpha_i \left[ y_i(wx_i+b)-1+\xi_i \right]=0, \quad i=1,2,\ldots,m$$有==软间隔的支持向量有四种情况==： 1. 若 $0<\alpha^*_i1$， 则分类错误， $x_i$ 在分隔超平面分错的一侧(图中 $x_3, x_4$)。 **软间隔支持向量机的解**：$$w^* = \sum _{ i=1 }^{ m }{\alpha^*_iy_ix_i}$$有了刚才对软间隔中对支持向量的探讨，那么在计算 $b^*$ 的时候跟硬间隔有所差异。在计算：$$b^* = y_j-\sum _{ i=1 }^{ m }{\alpha^*_iy_i\left}$$时，需要==选择一个满足条件 $0<\alpha^*_i

合页损失函数如下图【李航 P115】：

---

Tips：由于在凸优化中，仿射函数很重要，这里记录一下
仿射函数：
　　仿射函数是特殊的凸函数。既是凸函数，又是凹函数的函数称为仿射函数。它必定是线性函数与常数之和。在有限维空间上，仿射函数就是一次函数。仿射函数的重要性在于局部凸空间(包括赋范线性空间、有限维空间)上的下半连续凸函数一定是连续仿射函数族的上包络。$$f(x_1,\ldots,x_n)=A_1x_1+\cdots+A_nx_n+b$$　　仿射函数就是一个线性函数，其输入是n维向量，参数A可以是常数，也可以是m*n的矩阵，b可以是常数，也可以是m维的列向量，输出是一个m维的列向量。在几何上，仿射函数是一个线性空间到另一个线性空间的变换。