[人工智能]线性可分支持向量机与硬间隔最大化（更新中）

线性可分支持向量机与硬间隔最大化

1. 支持向量机简介

支持向量机（SVM）是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器。它的学习策略是间隔最大化。可形式化为一个求解凸二次规划的问题。支持向量机的学习算法是求解凸二次规划的最优化算法。

• 当训练数据线性可分时，通过硬间隔最大化，学习一个线性的分类器，即线性可分支持向量机，又称为硬间隔支持向量机；
• 当训练数据近似线性可分时，通过软间隔最大化，也学习一个线性的分类器，即线性支持向量机，又称为软间隔支持向量机；
• 当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。

当输入空间为欧氏空间或离散集合、特征空间为希尔伯特空间时，核函数表示将输入从输入空间映射到特征空间得到的特征向量之间的内积。通过使用核函数可以学习非线性支持向量机，等价于隐式地在高维的特征空间中学习线性支持向量机。这样的方法称为核技巧。

2. 线性可分支持向量机

考虑一个二类分类问题。假设输入空间与特征空间为两个不同的空间。输入空间为欧氏空间或离散集合，特征空间为欧氏空间或希尔伯特空间。线性可分支持向量机、线性支持向量机假设这两个空间的元素一一对应，并将输入空间中的输入映射为特征空间中的特征向量。非线性支持向量机利用一个从输入空间到特征空间的非线性映射将输入映射为特征向量。所以。输入都由输入空间转换到特征空间，支持向量机的学习是在特征空间进行的。

假设给定一个特征空间上的训练数据集：
T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } (1) T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\} \tag 1 T={(x1?,y1?),(x2?,y2?),...,(xN?,yN?)}(1)
其中，$x_i\in \chi =R^n$， y i ∈ γ = { + 1 , ? 1 } y_i \in \gamma=\{+1,-1\} yi?∈γ={+1,?1},$i=1,2,...,N$。$x_i$为第$i$个特征向量，也称为实例，$y_i$为$x_i$的类标记。当$y_i=+1$时，称$x_i$为正例；当$y_i=?1$时，称$x_i$为负例。$(x_i,y_i)$称为样本点。假设训练样本集是线性可分的（检查凸包（convex hull）是否相交）。
学习的目标是在特征空间中找到一个分离超平面，能将实例分到不同的类。分离超平面对应于方程$w?x+b=0$，它由法向量$w$和截距$b$决定，可用$(w,b)$来表示。分离超平面将特征空间划分为两部分，一部分是正类，一部分是负类。法向量指向的一侧为正类，另一侧为负类。
一般地，当训练数据集线性可分时，存在无穷个分离超平面可将两类数据正确分开。
感知机利用误分类最小的策略，求得分离超平面，不过这时的解有无穷多个。线性可分支持向量机利用间隔最大化求最优分离超平面，这时，解是唯一的。
分离超平面：
$$w^{?}?x+b^{?}=0\text{\hspace{1em}(2)}$$
相应的分类决策函数：
$$f(x)=sign(w^{?}?x+b^{?})\text{\hspace{1em}(3)}$$

3. 函数间隔与几何间隔

形象引入：
如果有三个点A、B、C，表示3个实例，均在分离超平面的正类一侧，预测它们的类。点A距分离超平面较远，若预测点为正类，就比较确信预测是正确的；点C距分离超平面较近，若预测点为正类就不那么确信；点B介于点A与点C之间，预测其为正类的确信度也在A与C之间。
概念引入：
一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度。在超平面$w?x+b=0$确定的情况下，$|w?x+b|$能够相对地表示点$x$距离超平面的远近。而$w?x+b$的符号与类标记$y$的符号是否一致能够表示分类是否正确。所以可用量$y(w?x+b)$来表示分类的正确性及确信度，这就是函数间隔的概念。
定义：
对于给定的训练数据集$T$和超平面$(w,b)$，定义超平面$(w,b)$关于样本点$(x_i,y_i)$的函数间隔为：
$$\widehat{{\gamma }_i}=y_i(w?x_i+b)\text{\hspace{1em}(4)}$$
定义超平面$(w,b)$关于训练数据集$T$的函数间隔为超平面$(w,b)$关于$T$中所有样本点$(x_i,y_i)$的函数间隔之最小值，即：
$$\hat{\gamma }=\underset{i=1,...,N}{\min }\widehat{{\gamma }_i}\text{\hspace{1em}(5)}$$
函数间隔可以表示分类预测的正确性及确信度。但是选择分离超平面时，只有函数间隔还不够。因为只要成比例地改变$w$和$b$，例如将它们改为$2w$和$2b$，超平面并没有改变，但是函数间隔却成为原来的2倍。
我们得到如下启示，可以对分离超平面的法向量$w$加某些约束，如规范化，$||w||=1$，使得间隔是确定的。由此引出几何间隔：
点A与超平面$(w,b)$的距离由线段AB给出，记作${\gamma }_i$：
$${\gamma }_i=\frac{w}{||w||}?x_i+\frac{b}{||w||}\text{\hspace{1em}(6)}$$
其中，$||w||$为$w$的$L_2$范数。这是点A在超平面正的一侧的情形。如果点A在超平面负的一侧，即$y_i=?1$，那么点与超平面的距离为：
$${\gamma }_i=?(\frac{w}{||w||}?x_i+\frac{b}{||w||})\text{\hspace{1em}(7)}$$
一般地，当样本点$(x_i,y_i)$被超平面$(w,b)$正确分类时，点$x$与超平面$(w,b)$的距离是：
$${\gamma }_i=y_i(\frac{w}{||w||}?x_i+\frac{b}{||w||})\text{\hspace{1em}(8)}$$
几何间隔的定义：
对于给定的训练数据集$T$和超平面$(w,b)$，定义超平面$(w,b)$关于样本点$(x_i,y_i)$的函数间隔为：
$${\gamma }_i=y_i(\frac{w}{||w||}?x_i+\frac{b}{||w||})\text{\hspace{1em}(9)}$$
定义超平面$(w,b)$关于训练数据集$T$的函数间隔为超平面$(w,b)$关于$T$中所有样本点$(x_i,y_i)$的函数间隔之最小值，即：
$$\gamma =\underset{i=1,...,N}{\min }{\gamma }_i\text{\hspace{1em}(10)}$$
函数间隔和几何间隔有下面的关系：
$$\gamma =\frac{\hat{\gamma }}{||w||}\text{\hspace{1em}(11)}$$

4. 间隔最大化

间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。也就是说，不仅将正负实例分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度将它们分开。这样的超平面应该对未知的新实例有很好的分类预测能力。

4.1 最大间隔分离超平面

问题转化为：
$$\begin{gathered} \underset{w,b}{\max }\gamma \\ s.t.y_i(\frac{w}{||w||}?x_i+\frac{b}{||w||})\ge \gamma ,i=1,2,...,N\text{\hspace{1em}(12)} \end{gathered}$$
即我们希望最大化超平面$(w,b)$关于训练数据集的几何间隔$\gamma$，约束条件表示的是超平面$(w,b)$关于每个训练样本点的几何间隔至少是$\gamma$。
考虑式$(11)$，问题转化为：
$$\begin{gathered} \underset{w,b}{\max }\frac{\hat{\gamma }}{||w||} \\ s.t.y_i(w?x_i+b)\ge \hat{\gamma },i=1,2,...,N\text{\hspace{1em}(13)} \end{gathered}$$
函数间隔$\hat{\gamma }$的取值并不影响最优化问题的解。事实上，假设将$w$和$b$按比例改变为$\lambda w$和$\lambda b$，这是函数间隔成为$\lambda \hat{\gamma }$。但是这一改变对不等式约束没有影响。取$\hat{\gamma }=1$，将$\hat{\gamma }=1$代入上面的最优化问题，将最大化$\frac{1}{||w||}$和最小化$\frac{1}{2}||w|{|}^2$是等价的。线性可分支持向量机学习的最优化问题：
$$\begin{gathered} \underset{w,b}{\min }\frac{1}{2}||w|{|}^2 \\ s.t.y_i(w?x_i+b)\ge 1,i=1,2,...,N\text{\hspace{1em}(14)} \end{gathered}$$
该问题是一个凸二次规划问题。

4.2 线性可分支持向量机学习算法—最大间隔法

输入：线性可分支持向量机数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\} T={(x1?,y1?),(x2?,y2?),...,(xN?,yN?)}，其中，$x_i\in \chi =R^n$， y i ∈ γ = { + 1 , ? 1 } y_i \in \gamma=\{+1,-1\} yi?∈γ={+1,?1},$i=1,2,...,N$；
输出：最大间隔分离超平面和分类决策函数。

1. 构造并求解约束最优化问题：
   $$\begin{gathered} \underset{w,b}{\min }\frac{1}{2}||w|{|}^2 \\ s.t.y_i(w?x_i+b)\ge 1,i=1,2,...,N \end{gathered}$$
   求得最优解$w^{?},b^{?}$。
2. 得到分离超平面：
   $$w^{?}?x+b^{?}=0$$
   相应的分类决策函数：
   $$f(x)=sign(w^{?}?x+b^{?})$$

存在唯一性的证明