Ch10 SVM

[TOC]

1-nn vc 维：

vc维是理论的，实际上难以计算。

Hard-Margin SVM

间隔(Margin)：分类超平面到最近支持向量之间的距离。

支持向量(Support Vec)：那些对分类边界的位置和形状起到关键作用的样本点。支持向量是离分类超平面最近的点。边界完全由支持向量决定。

估计Margin

两类情形的决策面方程：\(g(x)=w^Tx+b=0\)

对于任意样本\(x\)，将其向决策面投影：\(x=x_p+r\frac{w}{\|w\|}\),w是法向量。

代入决策函数： \[ \begin{align} g(x)&=w^T\left(x_p+r\frac{w}{\|w\|}\right)+b\\ &=r\|w\|\\ r&=\frac{g(x)}{\|w\|} \end{align} \] 法向量和决策面上向量\(x_p\)做内积=0；且w是单位法向量，后一项二者平行。

决策面到原点的距离：\(\frac b{\|w\|}\)(b也与法向量平行)

计算点x到决策面的距离, margin距离决策面的距离是最近的(min): \[ d(x)=\frac{|w^Tx+b|}{\sqrt{\|w\|^2_2}}=\frac{|w^Tx+b|}{\sqrt{\sum^d_{i=1}w_i^2}}\\ margin=\arg\min_{x\in D}\{d(x)\}=\arg\min_{x\in D}\frac{|w^Tx+b|}{\sqrt{\sum^d_{i=1}w_i^2}} \] 将优化问题转化为博弈论问题

原来的形式是： \[ \arg \max_{w,b} \min_{x_i \in D} \frac{|b + x_i \cdot w|}{\|w\|} \] 这表示在所有可能的超平面参数 \(w, b\) 中，我们希望最大化支持向量距离超平面的最小间隔。但我们现在规定最小间隔=1，这消除了“min”的计算。优化目标从“最大化间隔”变为“最小化” w 的长度（即 \(\|w\|^2\)）：

该形式可以转化成: \[ \arg \min_{w,b} \frac{1}{2} \|w\|^2 \\ \text{s.t. } y_i (w \cdot x_i + b) \geq 1, \forall x_i \in D\\ \]

Margin与超平面的关系

Margin: 两类数据之间的决策边界的宽度（即支持向量与超平面之间的距离的两倍）。

SVM目标: 找到使 Margin 最大的超平面（即“最大间隔分类器”）。

\(w·x + b = 0\) 是分类决策边界。
\(w·x + b = +1\)和\(w·x + b = -1\)是两条平行于决策边界的支持向量平面。
决策边界是中间线，支持向量位于两个平行平面上。

Q：图中提出了问题“如何用 w和b来计算 Margin 宽度 M？。

A: 给定两个平行超平面（公式如 \(ax + by + c_1 = 0\)` 和 \(ax + by + c_2 = 0\)），两平面之间的距离计算公式是：\(d = \frac{|c2 - c1|}{\sqrt{a^2 + b^2}}\)

类比到支持向量机中：

对应的 \(a, b\) 是超平面法向量 \(w\)。
两平面\(w·x + b = +1\)和\(w·x + b = -1\)的距离：\(M = \frac{2}{\|w\|}\)

线性可分支持向量机求解

通过二次规划求解

求解线性可分支持向量机 (SVM) 的最优解通常可以通过 二次规划（Quadratic Programming） 方法完成，而这可以用 拉格朗日乘子法 实现。

线性可分SVM的目标函数是二次凸函数、约束条件是线性的，因此可以使用二次规划求解SVM。

拉格朗日乘子法求解--不记

写上来只是为了逻辑的连贯性。

对于问题： \[ \arg \min_{w,b} \frac{1}{2} \|w\|^2 \\ \text{s.t. } y_i (w \cdot x_i + b) \geq 1, \forall x_i \in D\\ \] 该形式符合凸优化理论，可以使用拉格朗日乘子法解决问题（Lagrangian Dual Problem） \[ \mathcal{L}=\frac 1 2||w||^2-\sum\alpha_i[y_i*(w\cdot x_i+b)-1] \] \(\alpha_i\): Lagrange Multiplier

对\(\mathcal{L}\)求解偏导： \[ \frac{\partial \mathcal{L}}{\partial w}=w-\sum\alpha_iy_ix_i=0\\ w=\sum\alpha_iy_ix_i\\\\ \frac{\partial \mathcal{L}}{\partial b}=\sum\alpha_iy_i=0 \]

\(w\) : is a weighted sum of the input vectors (\(x_i\) )
很多情况下\(\alpha_i=0\): because this point doesn’t contribute to the margin

再把\(w=\sum\alpha_iy_ix_i\)代进\(\mathcal{L}\)中，使得\(\mathcal{L}\)中没有\(w\)，只有\(\alpha_i\)一个参数。 \[ \begin{align} \mathcal{L}=&\frac 1 2w^Tw-\sum\alpha_i[y_i*(w\cdot x_i+b)-1]\\ =&\frac 1 2 (\sum\alpha_iy_ix_i)(\sum\alpha_jy_jx_j)-\sum\alpha_i[y_i\sum\alpha_jy_jx_j\cdot x_i]+b\sum\alpha_iy_i+\sum\alpha_i\end{align} \] 因为：\(\frac{\partial \mathcal{L}}{\partial b}=\sum\alpha_iy_i=0\) \[ \begin{align} \mathcal{L}=&\frac 1 2 (\sum\alpha_iy_ix_i)(\sum\alpha_jy_jx_j)-\sum\alpha_i[y_i\sum\alpha_jy_jx_j\cdot x_i]+\sum\alpha_i\\ =&\sum\alpha_i-\frac 1 2 (\sum\alpha_iy_ix_i)(\sum\alpha_jy_jx_j)\\ =&\sum\alpha_i-\frac 1 2 \sum_i\sum_j\alpha_i\alpha_jy_iy_jx_ix_j \end{align} \]

Soft-Margin SVM

不具有线性可分性的情况下：SVM 原始模型（线性可分 SVM）假设数据是完全线性可分的。但在实际数据中，通常会有一些噪声点（如图中的白点和黑点的异常位置），导致数据集不可线性完全分离。这就需要对原始目标函数进行修改，以适应有噪声的数据。

软间隔 SVM 的优化问题如下：第一项体现了模型的 表达能力（间隔最大化，偏向于低方差）；第二项体现了模型的 经验风险（分类错误惩罚，偏向于低偏差）。 \[ \min \frac 1 2 ||w||^2+C\sum^m_i\xi_i\\ s.t.\ y_i*(w\cdot x+b)\ge 1-\xi_i\\ \xi_i\ge0\\ i=1,2,\dots,n \] \(\xi_i\)：表示第 \(i\) 个样本的松弛变量（slack variable），用于量化样本允许的分类错误或间隔违规程度。C：是一个权衡参数，用于平衡 间隔最大化 和 分类错误惩罚 之间的权重。对于参数\(C\):

Low C: 对分类错误更宽松，更倾向于允许一些错误以换取更大的间隔。(欠拟合)
High C: 更严格地惩罚分类错误，强制模型尽量避免分类错误，即 错误的代价很高。(易导致过拟合)

合页损失(Hinge Loss): 一种常用的损失函数。Hinge Loss用于衡量样本的分类错误和分类边界的间隔。其在soft-margin中的定义如下： \[ \min \frac 1 2||w||^2+C\sum^m_i\max(0,1-y_i*(w\cdot x+b)) \] \(y_i\): 表示样本的真实标签（通常为-1或1）

\(w\cdot x+b\): 表示样本的预测分类（即决策函数输出的值）。

Hinge Loss的目标是使正确分类的样本的损失为0，并增大错误分类样本的损失。在软间隔分类中，Hinge Loss通常与正则化项结合使用，以平衡分类错误和模型复杂度。通过最小化Hinge Loss和正则化项，可以得到一个具有较小间隔违规和较小模型复杂度的分类模型，从而在训练集上和测试集上获得良好的性能。

对偶问题(Dual)

什么是对偶问题？ 在约束优化问题中，可以通过拉格朗日对偶性将原始问题（主问题）转换为对偶问题，目的是使问题的求解更简单或更高效。

为什么使用对偶问题？

对偶问题往往比原始问题更易求解，尤其是在 SVM 的情况下，使用对偶问题可以更自然地引入核函数，扩展到非线性分类问题。
对偶问题的解与原始问题的解是等价的（强对偶性），因此我们可以通过求解对偶问题间接得到原问题的解。

对偶问题求解

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

\[ \nabla_w L(w,b,\alpha)=w-\sum^n_{i=1}\alpha_iy_ix_i=0\Rightarrow w=\sum^n_{i=1}\alpha_iy_ix_i=0\\ \nabla_b L(w,b,\alpha)=\sum^n_{i=1}\alpha_iy_i=0 \]

将得到的偏导代入\(min_{w,b} L(w,b,\alpha)\)中： \[ \begin{align} \min_{w,b} L(w,b,\alpha)&=\frac 1 2(\sum^n_{i=1}\alpha_iy_ix_i)^T(\sum^n_{j=1}\alpha_jy_jx_j)-\sum^n_{i=1}\alpha_i y_i((\sum^n_{j=1}a_jy_jx_j)^Tx_i)+\sum^n_i\alpha_i\\ &=-\frac 1 2 \sum^n_{i=1}\sum^n_{j=1}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum^n_{i=1}\alpha_i \end{align} \]

求\(\min_{w,b} L(w,b,\alpha)\)对\(\alpha\)的极大

\[ \max_{\alpha} \min_{w,b} L(w,b,\alpha)=\max_{\alpha} -\frac 1 2 \sum^n_{i=1}\sum^n_{j=1}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum^n_{i=1}\alpha_i\\ \iff \min_{\alpha}\frac 1 2 \sum^n_{i=1}\sum^n_{j=1}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum^n_{i=1}\alpha_i\\ s.t. \sum^n_{i=1}\alpha_iy_i=0\\ a_i\ge 0,i=1,2,\dots,n \]

对偶问题本质上是一个 凸二次规划问题（convex quadratic programming, QP），其目标函数是凸的。在凸优化问题中，最大化凸函数等价于最小化其负值。

最终对偶问题被转化为一个标准的二次规划问题，既可以通过数学工具（如拉格朗日法）手动求解，也可以利用已有的优化算法（如SMO算法）求解。对于凸优化问题，全局最优解总是可以找到。

对偶问题的KKT条件

\[ \begin{align} &\alpha_i^*\ge 0\\ &y_i(w^{*T}x_i+b^*)-1\ge 0 \\ &a_i^*(y_i(w^{*T}x_i+b^*)-1)=0 \end{align} \]

总结

Margin 是指两类数据之间的决策边界的宽度（即支持向量与超平面之间的距离的两倍\(\frac 2 {\|w\|}\)）。
SVM 的目标是找到使 Margin 最大的超平面（即“最大间隔分类器”）。
支持向量是距离分类超平面最近的点，它们决定了 Margin 的大小。

SVM 的步骤

准备数据矩阵：收集训练数据集 \({(x_i, y_i)}\)，其中 \(x_i\) 是特征向量，\(y_i\) 是对应的标签。
选择核函数：核函数用于将低维数据映射到高维空间，例如线性核、高斯核等。
选择误差参数 C：C 是一个超参数，用于控制分类的软边界（软间隔）的惩罚。
训练系统：利用二次规划（QP）算法求解 \(\alpha_i\) 和 \(b\)。
分类新数据：训练完成后，使用支持向量和对应的 \(\alpha_i\) 值对新数据进行分类。

弱点

训练（测试）速度慢：原因：需要解决约束的二次规划问题（QP），尤其在大数据集上计算复杂度较高。
本质上是一个二分类器：默认情况下只能处理二分类问题，需要扩展才能解决多分类任务（如一对一、一对多策略）。
对噪声非常敏感：数据集中少量的异常点（outliers）可能显著影响分类边界。
核函数选择的困难：
- 没有统一的理论指导如何选择最优核函数，这在实际应用中是一大挑战。
- 一旦选择核函数后，超参数 C 是唯一的可调节参数。

优点

训练相对容易：不需要像神经网络（NN）那样处理局部最小值问题，SVM 的解是全局唯一的。
不受维度灾难的影响：通过核技巧，SVM 能够在高维空间中运行，但仍然只需要计算点积，从而避免了维度灾难问题。
不易过拟合：最大间隔约束使得模型对数据的泛化能力较强。
几何解释简单：通过构造最大间隔超平面，几何意义清晰直观，不需要复杂的网络结构。

模式识别-Ch10-SVM