机器学习（第6章）6.支持向量机
6.1间隔与支持向量
给定训练样本集D
D
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
m
,
y
m
)
}
,
y
i
∈
{
?
1
,
+
1
}
D=\left\{\left(\boldsymbol{x}_{1}, y_{1}\right),\left(\boldsymbol{x}_{2}, y_{2}\right), \ldots,\left(\boldsymbol{x}_{m}, y_{m}\right)\right\}, y_{i} \in\{-1,+1\}
D={(x1?,y1?),(x2?,y2?),…,(xm?,ym?)},yi?∈{?1,+1}
分类学习最基本的想法就是在训练集D 在样本空间中找到一个划分超平面、将不同类别的样本分开。
? 直观上看，应该去找位于两类训练样本"正中间"的划分超平面，支持向量机就是找就是找距离正负样本最远的超平面，相比于感知机，其解是唯一的，且不偏不倚，泛化性能更好。
6.1.1补充：超平面
6.1.2几何间隔
6.2支持向量机
6.2.1支持向量机
对于划分的正确样本，就+1，划分的错误样本，就-1，这样y最大的就是分类都正确的超平面。
将最大化问题撞边为最小化问题，就得到如下图所示
这个就是支持向量机的基本型
6.2.2拉格朗日对偶问题
6.2.2.1凸优化问题
6.2.2.2一般约束问题
定义域和可行集有所区别，可行集还得满足约束条件，不一定就是定义域，一般可行集是定义域的子集。
inf()函数可以先近似的理解为min()
6.2.2.3拉格朗日对偶问题
6.2.2.4 KTT条件
为什么支持向量机问题常常采用拉格朗日对偶求解？
(1) 无论主问题是何种优化问题，对偶问题恒为凸优化问题，因此更容易求解（尽管支持向量机的主问题本就是凸优化问题），而且原始问题的时间复杂度和特征维数呈正比（因为未知量是ω），而对偶问题和数据量成正比（因为未知量是α ），当特征维数远高于数据量的时候拉格朗日对偶更高效.
(2) 对偶问题能很自然地引入核函数，进而推广到非线性分类问题（主要的原因）。
6.3软间隔与支持向量回归
6.3.1算法原理
(1)在前面的讨论中,我们一直假定训练样本在样本空间或特征空间中是线性可分的，即存在一个超平面能将不同类的样本完全划分开，在现实任务往往很难确定合适的核函数使得训练样本在特征空间中线性可分;
(2) 退一步说即使恰好找到了某个核函数使训练集在特征空间中线性可分，也很难断定这个貌似线性可分的结果不是由于过拟合所造成的。
缓解该问题的一个办法是允许支持向量机在些样本上出错.为此，要引入"软间隔" (soft margin) 的概念，
从数学角度来说，软间隔就是允许部分样本（但要尽可能的少）不满足下式的约束条件
min
?
w
,
b
1
2
∥
w
∥
2
s
.
t
.
y
i
(
w
T
x
i
+
b
)
?
1
,
i
=
1
,
2
,
…
,
m
\begin{array}{ll} \min _{\boldsymbol{w}, b} & \frac{1}{2}\|\boldsymbol{w}\|^{2} \\ \mathrm{s.t.} & y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1, \quad i=1,2, \ldots, m \end{array}
minw,b?s.t.?21?∥w∥2yi?(wTxi?+b)?1,i=1,2,…,m?
必须严格执行的约束条件转化为具有一定灵活性的损失，合格的损失函数要求如下：
- 当满足约束条件时，损失为0；
- 当不满足约束条件时，损失不为0；
- 当不满足约束条件时，损失与其违反约束条件的程度成正比。（可选）
只有满足以上要求，才能保证在最小化损失时，保证不满足约束条件的样本尽可能少。
于是优化目标可以写为
min
?
w
,
b
1
2
∥
w
∥
2
+
C
∑
i
=
1
m
?
0
/
1
(
y
i
(
w
T
x
i
+
b
)
?
1
)
\min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \ell_{0 / 1}\left(y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)-1\right)
w,bmin?21?∥w∥2+Ci=1∑m??0/1?(yi?(wTxi?+b)?1)
?
0
/
1
是
0
/
1
损
失
函
数
?
0
/
1
(
z
)
=
{
1
,
?if?
z
<
0
0
,
?otherwise?
\ell_{0 / 1} 是 0 / 1 损失函数\\ \ell_{0 / 1}(z)=\left\{\begin{array}{ll} 1, & \text { if } z<0 \\ 0, & \text { otherwise } \end{array}\right.
?0/1?是0/1损失函数?0/1?(z)={1,0,??if?z<0?otherwise??
C>0是一个常数，用来调节损失的权重，当C趋向正无穷时，再最小化的过程中会迫使所有样本损失为0，进而退化为严格执行的约束条件，即为硬间隔。
由于0/1损失函数非凸，非连续，数学性质不好，使优化目标不易求解，故常用**“替代损失函数”来替代，软间隔支持向量机通常采用的是hinge(合页)**损失来替代0/1函数
?hinge?损失:?
?
hinge?
(
z
)
=
max
?
(
0
,
1
?
z
)
;?
\text { hinge 损失: } \ell_{\text {hinge }}(z)=\max (0,1-z) \text {; }
?hinge?损失:??hinge??(z)=max(0,1?z);?
替换上式可得
min
?
w
,
b
?
1
2
∥
w
∥
2
+
C
∑
i
=
1
m
max
?
(
0
,
1
?
y
i
(
w
T
x
i
+
b
)
)
\min _{\boldsymbol{w}, b} \cdot \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \max \left(0,1-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)\right)
w,bmin??21?∥w∥2+Ci=1∑m?max(0,1?yi?(wTxi?+b))
再引入松弛变量ξ
min
?
w
,
b
,
ξ
i
1
2
∥
w
∥
2
+
C
∑
i
=
1
m
ξ
i
?s.t.?
y
i
(
w
T
x
i
+
b
)
?
1
?
ξ
i
ξ
i
?
0
,
i
=
1
,
2
,
…
,
m
\begin{array}{cl} \min _{\boldsymbol{w}, b, \xi_{i}} & \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \xi_{i} \\ \text { s.t. } & y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1-\xi_{i} \\ & \xi_{i} \geqslant 0, i=1,2, \ldots, m \end{array}
minw,b,ξi???s.t.??21?∥w∥2+C∑i=1m?ξi?yi?(wTxi?+b)?1?ξi?ξi??0,i=1,2,…,m?
证明：
max
?
(
0
,
1
?
y
i
(
w
T
x
i
+
b
)
)
=
ξ
i
?显然?
ξ
i
?
0
,
?当?
1
?
y
i
(
w
T
x
i
+
b
)
>
0
?
ξ
i
=
1
?
y
i
(
w
T
x
i
+
b
)
,
y
i
(
w
T
x
i
+
b
)
?
0
?
ξ
i
=
0
,
1
?
y
i
(
w
T
x
i
+
b
)
?
ξ
i
?
y
i
(
w
T
x
i
+
b
)
?
1
?
ξ
i
\begin{array}{c} \max \left(0,1-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)\right)=\xi_{i} \\ \text { 显然 } \xi_{i} \geqslant 0, \text { 当 } 1-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)>0 \Rightarrow \xi_{i}=1-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right), \\ y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \leqslant 0 \Rightarrow \xi_{i}=0, \\ 1-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \leqslant \xi_{i} \Rightarrow y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1-\xi_{i} \end{array}
max(0,1?yi?(wTxi?+b))=ξi??显然?ξi??0,?当?1?yi?(wTxi?+b)>0?ξi?=1?yi?(wTxi?+b),yi?(wTxi?+b)?0?ξi?=0,1?yi?(wTxi?+b)?ξi??yi?(wTxi?+b)?1?ξi??
6.3.2支持向量回归
基本思想：落在带子上的样本不计算损失（类比线性回归在线上的点预测误差为0），不在带子上的则以偏离带子的距离作为损失（类比线性回归的均方误差），然后以最小化损失的方式迫使间隔带从样本最密集的地方（中心地带）穿过，进而达到拟合训练样本的目的。
