支持向量机（SVM）（SVM）

1. 线性可分支持向量机 1.1 线性可分假设

首先，我们做一个假设：

假设我们的训练集样本是线性可分的。

线性可分的意思是：对于一个数据集：T=\left\{(x_{1},y_{1}),(x_{},y_{2}),…,(x_{m},y_{ m} ）\正确的\}

其中，x_{i}\in\chi=R^{n}，y_{i}\in Y=\left\{ +1,-1 \right\}，i=1,2,3,4， …m ，可求出超平面 S：

\qquad\qquad\qquad\qquad\qquad\qquad w·x+b=0

从而使数据集中的正负样本完全正确地划分在超平面两侧，用公式表示：

0 & & y_{i}=+1\\ \qquad\qquad\qquad\qquad\qquad w·x_{i}+b=\left\{ \begin{} >0 & & y_{i}=+1 \\

那么这个数据集T就说是线性可分的，否则就是线性不可分的。

线性多样化集合示例：

这里定义一个函数：g(x)=w·x+b。 这个功能以后会多次出现。

1.2 学习策略

如上所述，对于线性可分的数据集，存在一个超平面将两类样本点分开，但一般这样的超平面有无限个：

既然我们有这么多超平面，我们应该选择哪一个呢？ 直观上，我们选择一个能够将数据集完全分离的超平面，并尽可能保持样本点与这个超平面之间的“距离”。 恰好这样的超平面也是最鲁棒的，即泛化能力最强，最重要的是这样的超平面是唯一的。

那么接下来的问题是如何定义样本点到超平面的距离？

1.3 函数区间和几何区间

一般来说，一个点到超平面的距离可以代表分类预测的置信度。 即样本点离超平面越远，则越能确定该样本点被正确分类。

当超平面S：w·x+b =0确定后，我们可以使用\left| w·x_{i}+b \right| 表示 x_{i} 到超平面的距离，与 y_{i} 符号是否与 w·x_{i}+b 相同也表示分类是否正确，因此将两者结合起来我们使用 y_{i }(w·x_{i}+b) 来表示分类的准确率。

定义1.1（函数区间）

对于超平面 w·x+b=0 和样本点\left( x_{i},y_{i} \right)，样本点的函数区间定义为：

\qquad\qquad\qquad\qquad\qquad\qquad\tilde{\{i}}=y_{i}(w·x_{i}+b)

整个数据集的函数区间是所有样本点的函数区间的最小值，即

\qquad\qquad\qquad\qquad\qquad\qquad\tilde{\gamma}= \min_{i=1,2,..m}\tilde{\gamma}_{i}

不过函数区间不太好用，因为当w和b按比例缩放时，超平面不会改变，但函数区间会按比例放大或缩小。 我们自然会想，函数区间除以 \left| 不就够了吗？ \左| w \右| \对|？ 这是正确的，因为除以 \left| \左| w \右| \ 对| 只是得到样本点和超平面之间的真实距离。

我们来解释一下为什么这么说

如上图所示，如果要计算点A到超平面的距离\{i}，设A为x_{1}，其类标签为y=+1，B为A在超平面，设 x_{0 } ，则有

\qquad\qquad\qquad\qquad\qquad\qquad\left\{ \begin{} x_{0}+\{i}*\frac{w}{\left| \左| w \右| \right|} =x_{1}\\ w·x_{0}+b=0\\ \end{} \right.

求解：\{i}=\frac{w}{\left| \左| w \右| \right|}·x+\frac{b}{\left| \左| w\右| \右|}

这是样本呈阳性的情况。

当y=-1时，情况是

\qquad\qquad\qquad\qquad\qquad\{i}=-\left( \frac{w}{\left| \left| w \right| \right|}·x+\frac{b}{\left| \left| w\right| \right|} \right)

结合这两种情况，我们得到一个既包含样本类别信息又包含距离信息的度量，即

\qquad\qquad\qquad\qquad\qquad\{i}=y_{i}\left( \frac{w}{\left| \left| w \right| \right|}·x_{i}+\frac {b}{\left| \left| w\right| \right|} \right)

这是贯穿始终的概念：几何间隔

定义1.2（几何间隔）

对于超平面 w·x+b=0 和样本点\left( x_{i},y_{i} \right)，样本点的几何间隔定义为：

\qquad\qquad\qquad\qquad\qquad\{i}=y_{i}\left( \frac{w}{\left| \left| w \right| \right|}·x_{i}+\frac {b}{\left| \left| w\right| \right|} \right)

整个数据集的函数区间是所有样本点的函数区间的最小值，即

\qquad\qquad\qquad\qquad\qquad\qquad\gamma= \min_{i=1,2,..m}\{i}

从定义可以看出，只有一个\left| \左| w \右|\右| 函数区间与几何区间的乘积关系，即

\qquad\qquad\qquad\qquad\qquad\qquad\{i}=\frac{\tilde{\{i}}}{\left| \左| w \右| \右|}

\qquad\qquad\qquad\qquad\qquad\qquad \gamma=\frac{\tilde{\gamma}}{\left| \左| w \右| \右|}

如果\左| \左| w \右| \右| =1，那么函数区间和几何区间相等，当超平面w、b按比例变化时，曲面平面不变化，几何区间也不变化。 改变。

1.4 边距最大化和最大边距分离超平面

上面获得的样本点与超平面之间距离的一个很好的指标是几何间隔。 然后我们最大化间隔，也就是最大化数据集的几何间隔。

1.4.1 最大间隔分离超平面

上述分析已经明确，需要得到的是几何间隔最大的超平面。 我们可以将这个问题表示为如下的优化约束问题：

\qquad\qquad\qquad\qquad\qquad\qquad \max_{w,b} \gamma

\qquad\qquad\qquad\qquad\qquad st \quad y_{i}\left( \frac{w}{\left| \left| w \right| \right|}*x_{i}+\frac{b }{\left| \left| w \right| \right|} \right)\geq\gamma\quad i=1,2,3,....m

公式的含义是我们最大化数据集的几何区间γ。 约束条件表示所有点的几何间隔必须大于或等于γ，对应于上面数据集的几何间隔的定义。

考虑几何区间和函数区间的关系，上述优化问题等价于以下问题：

\qquad\qquad\qquad\qquad\qquad\qquad\max_{w,b} \ \frac{\tilde{\gamma}}{\left| \左| w \右| \右|}

\qquad\qquad\qquad\qquad\qquad st \quad y_{i}\left( w*x_{i}+b \right)\geq\tilde{\gamma} \quad i=1,2,3,。 ...米

观察上述优化问题，我们可以发现，无论函数区间\tilde{\gamma}取什么值，问题的解都不会改变。 事实上，我们将 w,b 缩放为 \w,\b，函数区间变为 \\tilde{\gamma}。 此更改不会影响目标和约束（已驳回）。 这一事实与上述不能使用功能区间作为区间度量的情况是一致的。 在这种情况下，我们简单地让函数区间为常数1。从处理上来说，问题就变成了：

\qquad\qquad\qquad\qquad\qquad\qquad\max_{w,b} \ \frac{1}{\left| \左| w \右| \右|}

\qquad\qquad\qquad\qquad\qquad st \quad y_{i}\left( w*x_{i}+b \right)\geq1 \quad i=1,2,3,....m

但是，上面的目标函数是一个非凸函数，这对于我们求解问题来说是不方便的，因为最大化\frac{1}{\left| \左| w \右| \right|} 并最小化 \frac{1}{2} \left | \左| w \右| \right|^{2} 是等价的，而 \frac{1}{2} \left| \左| w \右| \right|^{2} 是凸函数，因此我们得到线性可分离支持向量机的优化问题

\qquad\qquad\qquad\qquad\qquad\qquad \min_{w,b}\frac{1}{2} \left| \左| w \右| \右|^{2}

\qquad\qquad\qquad\qquad\qquad st \quad y_{i}\left( w*x_{i}+b \right)\geq1 \quad i=1,2,3,....m

这是一个凸二次规划问题。 此外，在线性可分离的数据集上必须存在最优解。 （证明可以参见李航老师的《统计学习方法》）

ps：凸优化问题的定义是指以下形式的优化问题：

\qquad\qquad\qquad\qquad\qquad\qquad \min_{w} f\left( w \right)

\qquad\qquad\qquad\qquad st \qquad g_{i}\left( w \right)\leq0\ , i=1,2,3...k

\ \ \ \ \ h_{i}\left( w \right)=0\ , i=1,2,3...l

其中，目标函数f\left( w \right)和约束函数g_{i}\left( w \right)是R^{n}上连续可微的凸函数，约束函数h_{i}\ left( w \right) 是 R^{n} 上的仿射函数。 '

仿射函数的定义：如果f(x)=w·x+b，w\in R^{n},b\in R,x\in R^{n}，则称f(x)为仿射函数功能 。

当目标函数f\left(w\right)为二次函数且约束函数g_{i}\left(w\right)均为仿射函数时，上述凸优化为凸二次规划问题。

我们得到了优化问题，那么如果我们能够得到最优解 w^{*},b^{*}，那么我们就得到了我们的分类模型 f\left( x \right)=sign(w^{ *} · 一篇笔记将使用数学方法将优化问题重新转换为更容易解决的对偶问题。

参考：

《机器学习》周志华

《统计学习方法》李航