SVM相关问题

支持向量

支持向量机（Support Vector Machine）是一种二分类模型，它的学习策略是“间隔最大化”，也就是找到特征空间的最大间隔超平面。

1. 支持向量在几何上是看指离这种超平面最近的点，从而在决策边界上“撑”起超平面，如下图加粗标记点所示。
2. 当我们用凸优化的角度去看支持向量机，那么支持向量就可以被定义为对偶变量 $\alpha _i >0$αi​>0 的样本点，且可以证明支持向量机的参数 $(\bm{w},b)$(w,b) 仅由支持向量决定，而与其他样本无关。
   

SVM的推导

之前说过，SVM本质上是一个线性分类器，也就是一个”线“或”面“来把样本点分开。那么首先可以我们先从线性分类器的定义开始：给定数据集 $D=\{(\bm{x}_1,y_1),(\bm{x}_2,y_2),... ,(\bm{x}_n,y_n)\}$D={(x1​,y1​),(x2​,y2​),...,(xn​,yn​)}，其中 $\bm{x}_i \in \mathbb{R}^d, y_n \in \{ -1,1 \}$xi​∈Rd,yn​∈{−1,1}。那么分类任务的目标就是学习到一个假设函数 $h: \mathbb{R} → \{1,-1\}, s.t. \forall i, y_ih(\bm{x}_i)=1$h:R→{1,−1},s.t.∀i,yi​h(xi​)=1。由于线性分类，假设函数是特性 $\bm{x}_i$xi​ 的线性组合，即：$h(\bm{x}_i):= \textup{sign}(\bm{w}^T\bm{x}_i+b)$h(xi​):=sign(wTxi​+b)其中 $\bm{w}^T \in \mathbb{R}^d$wT∈Rd，$b \in \mathbb{R}$b∈R。那么，线性分类器的任务就是找到一组 $(\bm{w}^T,b)$(wT,b) 实现分类。但问题是，满足以上约束条件的组很多，我们想要从中找一个效果最好的，也就是对于新的样本，仍然能准确地实现分类。如下图所示，黑蓝两线都表示两个参数组对应的分类器，但是对于新的样本点（黄点），二者的分类效果的差别一目了然。

因此，我们需要再定义一个”指标“来评价不同的线性分类器——间隔（margin），即超平面与样本之间的距离。$\gamma:= 2\min_i \frac{1}{||\bm{w}||}|\bm{w}^T\bm{x}_i + b|$γ:=2imin​∣∣w∣∣1​∣wTxi​+b∣需要注意的是，这里的间隔 $\gamma$γ 实际上表示的是超平面到不同类（两类）中的最近样本（支持向量）的距离之和。

那么，支持向量机就可以定义为：找到一组 $(\bm{w}^T,b)$(wT,b)，使得如下式子成立$\max_{\bm{w},b}\min_i \frac{2}{||\bm{w}||}|\bm{w}^T\bm{x}_i + b|$w,bmax​imin​∣∣w∣∣2​∣wTxi​+b∣$s.t. \quad y_i( \bm{w}^T\bm{x}_i + b)>0, i=1,2,...,m$s.t.yi​(wTxi​+b)>0,i=1,2,...,m对上面的式子还可以继续简化，使得成为经典的可解凸二次规划（Quadratic Programming, QP）问题。可以证明对 $(\bm{w}^T,b)$(wT,b) 放缩不会影响解，这样我们就可以约束 $(\bm{w}^T,b)$(wT,b) ，使得$\min_i|\bm{w}^T\bm{x}_i + b|=1$imin​∣wTxi​+b∣=1那么我们就得到了原支持向量机的优化问题就等价于：找到一组合适的参数 $(\bm{w}^T,b)$(wT,b) 使得下列式子成立 $\min_{\bm{w},b} \frac{1}{2}\bm{w}^T\bm{w}$w,bmin​21​wTw$s.t. \quad y_i( \bm{w}^T\bm{x}_i + b)\geq1, i=1,2,...,m$s.t.yi​(wTxi​+b)≥1,i=1,2,...,m 优化目标也就等价于$\argmin_{\bm{w},b} \frac{1}{2} ||\bm{w}||$w,bargmin​21​∣∣w∣∣

参考资料

[1]：周志华 《机器学习》
[2]：张皓 《从零推导支持向量机(SVM)》
[3]：李航 《统计学习方法（第二版）》