Lecture 10 软间隔 SVM 、拉格朗日对偶
主要内容
- 软间隔 SVM
- 直觉和问题的数学表述
- 拉格朗日对偶
- 具有不同训练复杂度的替代数学表述
- 解释支持向量
- 为学习核函数做准备（下节内容）
上节回顾：硬间隔 SVM
- SVM 是一种线性二分类器
- 最大间隔：旨在寻找对噪声具有鲁棒性的边界
- 解决分歧的技巧：$\dfrac{y_{i^*}(\boldsymbol w’\boldsymbol x_{i^*}+b)}{\|\boldsymbol w\|}=\dfrac{1}{\|\boldsymbol w\|}$
- 硬间隔程序：
$\mathop{\operatorname{arg\,min}}\limits_{\boldsymbol w,b}\|\boldsymbol w\|\quad\text{s.t.}\; y_i(\boldsymbol w’\boldsymbol x_i+b)\ge 1 \;\text{for}\; i=1,…,n$
1. 软间隔 SVM
处理线性不可分的情况
1.1 当数据不是线性可分的时候
- 硬间隔的损失函数过于严格
- 真实数据不太可能严格线性可分
-
如果数据不是线性可分的，硬间隔 SVM 会遇到问题
- SVM 提供了 3 种方法来处理这一问题：
- 还是采用硬间隔 SVM，但是需要进行 数据转换（下节内容）
- 放松 约束条件
- 方法 1 与 方法 2 的结合
1.2 软间隔 SVM
-
放松约束条件以允许数据点落在 间隔内部 或者甚至落在分类边界 错误的一侧
- 但是，我们通过 “违反” 的程度来惩罚边界
- 图中，目标函数的惩罚会考虑橙色的距离
1.3 Hinge 损失：软间隔 SVM 的损失函数
-
硬间隔 SVM 的损失函数：
$l_{\infty} =\begin{cases}0\quad\;\, 1-y(\boldsymbol w’\boldsymbol x+b)\le0 \\
\infty\quad \text{otherwise}\end{cases}$ -
软间隔 SVM 的损失函数（Hinge 损失）：
$l_{h} =\begin{cases}0\qquad\qquad\quad\quad 1-y(\boldsymbol w’\boldsymbol x+b)\le0 \\
\\
1-y\color{red}{\underbrace{\color{black}{(\boldsymbol w’\boldsymbol x+b)}}_{\hat{y}}}\quad \text{otherwise}\end{cases}$
对比感知器的损失函数
1.4 软间隔 SVM 的目标函数
-
软间隔 SVM 的 目标函数
\[\mathop{\operatorname{arg\,min}}\limits_{\boldsymbol w,b}\left(\sum_{i=1}^{n}l_h (\boldsymbol x_i,y_i,\boldsymbol w)+\lambda\|\boldsymbol w\|^2\right)\]- 联想岭回归
- Hinge 损失：$l_h=\max(0,1-y_i(\boldsymbol w’\boldsymbol x_i+b))$
-
我们将重构该目标函数，使其更易于分析
1.5 重构软间隔的目标函数
-
定义松弛变量作为损失的上限
\[\xi_i\ge l_h=\max\left(0,1-y_i(\boldsymbol w'\boldsymbol x_i+b)\right)\]或者等效地，$\xi_i\ge 1-y_i(\boldsymbol w’\boldsymbol x_i+b)$ 并且 $\xi_i\ge 0$
-
将软间隔 SVM 的目标函数重写为：
\[\begin{array}{cc}\mathop{\operatorname{arg\,min}}\limits_{\boldsymbol w,b,\boldsymbol \xi}\left(\dfrac{1}{2}\|\boldsymbol w\|^2+C\sum_{i=1}^{n}\xi_i\right)\\\;\\ \text{s.t.}\;\xi_i\ge 1-y_i(\boldsymbol w'\boldsymbol x_i+b) \;\text{for}\; i=1,...,n\\\;\\ \xi_i\ge 0 \;\text{for}\; i=1,...,n \end{array}\]
1.6 SVM 的两种变体
-
硬间隔 SVM 目标函数：
\[\begin{array}{cc}\mathop{\operatorname{arg\,min}}\limits_{\boldsymbol w,b}\dfrac{1}{2}\|\boldsymbol w\|^2\\\\ \text{s.t.}\;y_i(\boldsymbol w'\boldsymbol x_i+b)\ge 1\;\text{for}\;i=1,...,n\end{array}\]注：将 $\|\boldsymbol w\|$ 换成 $0.5\|\boldsymbol w\|^2$ 利用了单调递增的转换。修改后的目标函数的解与之前相同。
-
软间隔 SVM 的目标函数：
\[\begin{array}{cc}\mathop{\operatorname{arg\,min}}\limits_{\boldsymbol w,b,\boldsymbol \xi}\left(\dfrac{1}{2}\|\boldsymbol w\|^2+C\sum_{i=1}^{n}\xi_i\right)\\\;\\ \text{s.t.}\;y_i(\boldsymbol w'\boldsymbol x_i+b)\ge 1-\xi_i \;\text{for}\; i=1,...,n\\\;\\ \xi_i\ge 0 \;\text{for}\; i=1,...,n \end{array}\] -
在第二种情况下，通过引入松弛变量 $\xi_i$ 以允许违反，约束条件被放松（“软化”）了。因此，被称为 “软间隔”。
2. SVM 的拉格朗日对偶
一个等效的公式，具有重要的意义。
2.1 约束优化
-
约束优化：规范形式
\[\begin{array}{cc}\text{minimise}\;f(\boldsymbol x)\\\\ \text{s.t.}\;g_i(\boldsymbol x)\le 0, i=1,...,n\\\\ h_j(\boldsymbol x)= 0, j=1,...,m\end{array}\]
- 例如：找到位于桥的南边，湖中最深的点。
- 适用，但是：并不能直接应用梯度下降
- 硬间隔 SVM：$\mathop{\operatorname{arg\,min}}\limits_{\boldsymbol w}\dfrac{1}{2}\|\boldsymbol w\|^2\quad\text{s.t.}\;1-y_i(\boldsymbol w’\boldsymbol x_i+b)\le 0\;\text{for}\;i=1,…,n$
- 拉格朗日乘子法
- 转换为无约束优化 - 对于求解不是必需的
- 将 原始问题 转换为一个相关的 对偶问题，以替代原始问题
- 分析两个问题求解的必要和充分条件
2.2 拉格朗日和对偶性
- 通过辅助变量引入辅助目标函数：
$\mathcal{L}(\boldsymbol x,\boldsymbol\lambda,\boldsymbol \nu)=f(\boldsymbol x)+\sum_{i=1}^{n}\lambda_ig_i(\boldsymbol x)+\sum_{j=1}^{m}\nu_jh_j(\boldsymbol x)$ （原始约束变成了惩罚项）- 称为 拉格朗日函数
- 新加入的 $\boldsymbol \lambda$ 和 $\boldsymbol \nu$ 称为 拉格朗日乘子 或者 对偶变量
- （旧的）原始问题：$\min_{\boldsymbol x}\max_{\boldsymbol{\lambda\ge0,\nu}}\mathcal{L}(\boldsymbol x,\boldsymbol\lambda,\boldsymbol \nu)$
- （新的）对偶问题：$\max_{\boldsymbol{\lambda\ge0,\nu}}\min_{\boldsymbol x}\mathcal{L}(\boldsymbol x,\boldsymbol\lambda,\boldsymbol \nu)$ （可能更容易解决，有利的）
- 对偶理论将原始问题和对偶问题联系起来：
- 弱对偶：对偶最优解 $\le$ 原始最优解
- 对于凸优化问题（包括 SVM）强对偶：二者最优解一样
2.3 硬间隔 SVM 的对偶问题
-
在最小化了关于原始变量的拉格朗日函数之后，现在将其关于对偶变量进行最大化，得到对偶问题
\[\begin{array}{cc}\mathop{\operatorname{arg\,max}}\limits_{\boldsymbol \lambda}\sum_{i=1}^{n}\lambda_i-\dfrac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\lambda_i\lambda_jy_iy_j\boldsymbol x_i'\boldsymbol x_j\\\\ \text{s.t.}\;\lambda_i\ge 0\;\text{and}\;\sum_{i=1}^{n}\lambda_iy_i=0 \end{array}\] - 强对偶：求解对偶问题，即可得到原始问题的解
- 与原始问题类似的地方：所谓的二次规划 - 现成的软件可以解决 – 稍后
- 与原始问题不同的地方：
- 求解复杂度是 $O(n^3)$ 而非 $O(d^3)$
- 程序仅取决于数据的点积 - 稍后将更多关于核方法
2.4 利用对偶解进行预测
- 恢复原始变量
- 回忆平稳性：$\color{red}{w_j^*}-\sum_{i=1}^{n}\lambda_iy_i(\boldsymbol x_i)_j=0$
- 互补松弛：$\color{red}{b^*}$ 可以从对偶解中得到，注意对于任何样本 $j$ 和 $\lambda_i^{*}>0$，我们有
$y_j(b^*+\sum_{i=1}^{n}\lambda_i^{*}y_i\boldsymbol x_i’\boldsymbol x_j)=1$
- 测试：对新的实例 $\boldsymbol x$ 进行分类，基于下面式子的符号
$s=b^{*}+\sum_{i=1}^{n}\lambda_i^{*} y_i\boldsymbol x_i’\boldsymbol x$
2.5 软间隔 SVM 的对偶问题
-
训练：找到 $\boldsymbol \lambda$ 求解
\[\begin{array}{cc}\mathop{\operatorname{arg\,max}}\limits_{\boldsymbol \lambda}\sum_{i=1}^{n}\lambda_i-\dfrac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\lambda_i\lambda_jy_iy_j\boldsymbol x_i'\boldsymbol x_j\\\\ \text{s.t.}\;\color{red}{\underbrace{\color{black}{C\ge\lambda_i\ge 0}}_{\text{盒子约束}}}\;\text{and}\;\sum_{i=1}^{n}\lambda_iy_i=0\end{array}\] -
进行预测：和硬间隔的情况一样的模式
3. 其他注意事项
3.1 互补松弛、点积
- 回忆 KKT 的条件之一是互补松弛性
$\lambda_i^{*}(y_i((\boldsymbol w^{*})’\boldsymbol x_i+b^{*})-1)=0$ -
回忆 $y_i(\boldsymbol w’\boldsymbol x_i+b)-1>0$ 意味着 $\boldsymbol x_i$ 在间隔外侧
- ( 像大多数 ) 间隔外侧的点必须满足 $\lambda^*=0$
- 那些满足非零 $\lambda$ 的点即 支持向量
$\boldsymbol w^{*}=\sum_{i=1}^{n}\lambda_iy_i\boldsymbol x_i$ - 预测由松弛变量的点积给出
$s=b^{*}+\sum_{i=1}^{n}\lambda_i^{*}y_i\boldsymbol x_i’\boldsymbol x$
3.2 训练 SVM
- SVM 的对偶问题是 二次规划问题。利用标准算法，这类问题可以在 $O(n^3)$ 的时间复杂度内解决。或者对于原始问题，可以在 $O(d^3)$ 的时间复杂度内解决。
- 这可能效率低下；已经有几种专门的求解方法被提出。
- 求解方法主要是对训练数据进行分解，并将问题分解为可以快速解决的较小问题。
- 原始的 SVM 训练算法的分解利用了许多 $\lambda$ 将为零（稀疏性）的这一事实。
- 顺序最小优化（SMO） 是极端分块情况下的另一种算法。一个迭代过程，可以在每次迭代时随机选择几对 $\lambda$ 进行解析优化。
总结
- 软间隔 SVM
- 直觉和问题的数学表述
- 构造对偶问题
- 拉格朗日乘子法、KKT 条件
- 弱对偶和强对偶
- 补充
- 互补松弛性
- 训练注意事项
下节内容：核方法
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。 欢迎转载，并请注明来自：YEY 的博客 同时保持文章内容的完整和以上声明信息！