支持向量机（SVM）是定义在特征空间上的间隔最大的线性分类器，支持向量机还包括核技巧（kernel method）使得能解决非线性分类问题。SVM的学习主要是间隔最大化（max margin），可以转化为求解凸二次规划的问题.
- 当训练样本线性可分时，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机；
- 当训练数据近似线性可分时，引入松弛变量，通过软间隔最大化，学习一个线性分类器，即线性支持向量机；
- 当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。
**需要关注的一些推导：**硬间隔最大化（几个间隔）、学习的对偶问题、软间隔最大化（引入松弛变量）、非线性支持向量机（核技巧）。
SVM为什么采用间隔最大化？
当训练数据线性可分时，存在无穷个分离超平面可以将两类数据正确分开。
感知机利用误分类最小策略，求得分离超平面，不过此时的解有无穷多个。
线性可分支持向量机利用间隔最大化求得最优分离超平面，这时，解是唯一的。另一方面，此时的分隔超平面所产生的分类结果是最鲁棒的，对未知实例的泛化能力最强。
为什么要将求解SVM的原始问题转换为其对偶问题？
一、是对偶问题往往更易求解（当我们寻找约束存在时的最优点的时候，约束的存在虽然减小了需要搜寻的范围，但是却使问题变得更加复杂。为了使问题变得易于处理，我们的方法是把目标函数和约束全部融入一个新的函数，即拉格朗日函数，再通过这个函数来寻找最优点。）
函数margin：
几何margin：
两者关系：
对于超平面$w^Tx+b=0$，样本空间任意点到超平面的距离为$r=\frac{\left | w^Tx+b \right |}{\left | w \right |}$。
假设超平面$w^Tx+b=0$能够将样本正确分类，则有以下不等式：
$\begin{equation} \begin{cases} w^Tx_i+b\geq0, & y_i=+1; \ w^Tx_i+b\leq0, & y_i=-1. \end{cases} \end{equation} $
**支持向量：**距离超平面最近的训练样本使以上不等式成立，称为支持向量。
**间隔：**两个异类支持向量到超平面的距离之和称为间隔（margin）。
**间隔最大化：**通过函数间隔和几何间隔的关系，将问题最终转化为最大化$\frac{2}{\left | w \right |}$，等同于求最小化$\left | w \right |^2$，为了求解时求导方便，即等同于求解最小化$\frac{1}{2}\left | w \right |^2$，这是一个凸二次规划问题。
输入：线性可分训练数据集$T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$，其中，$x_i\in\chi=R^n，y_i\in Y={-1,+1},i=1,2,...,N$；
输出：最大间隔分离超平面和分类决策函数（实质上就是解$w,b$）。
算法过程：
-
构造并求解约束最优化问题：
$min_{w,b} \frac{1}{2}\left |w\right|^2$ $s.t.y_i(w\cdot x_i+b)-1\geq0,i=1,2,...,N$ 求解得出最优解$w^,b^$。
-
超分离平面为：$w^x+b^=0$
分类决策函数为：$f(x)=sign(w^x+b^)$。
为了求解原始最优化问题，通过引入拉格朗日乘子，得到以下拉格朗日函数：
分别对$w,b$求导，可得$w=\sum_{i=1}^N\alpha_iy_ix_i以及\sum_{i=1}^N\alpha_iy_i=0$,代入上面的拉格朗日函数可以得到其对偶形式：
再次转换为求极小问题，如下：
解出$\alpha^$之后，即可求解原始问题中的$w^,b^$，分别为：
$w^=\sum_{i=1}^N\alpha^_iy_ix_i以及b^=y_j-\sum_{i=1}^N\alpha^*_iy_i(x_i\cdot x_j)$;（具体证明见李航统计学习方法定理7.2）
对应的超平面为：
$\sum_{i=1}^N\alpha^_iy_ix_i^Tx_i+b^=0$
决策函数为：
$f(x)=sign(\sum_{i=1}^N\alpha^_iy_ix_i^Tx_i+b^)$
对应的数据不再是线性可分，而是近似线性可分，此时硬间隔SVM就无法使用，由此引入了软间隔SVM这个概念。在软间隔SVM中，我们的分类超平面既要能够尽可能地将数据类别分对，又要使得支持向量到超平面的间隔尽可能地大。具体来说，因为线性不可分意味着某些样本点不能满足函数间隔大于等于1的条件，所以对每一个样本增加一个松弛变量$\xi_i\geq0$，对于不满足原约束条件的样本点，使得函数间隔加上松弛变量之后大于等于1，所以此时的约束条件为：
超平面两侧对称的虚线为支持向量，支持向量到超平面的间隔为1。在硬间隔SVM中本应该是在虚线内侧没有任何的样本点的，而在软间隔SVM中，因为不是完全的线性可分，所以虚线内侧存在有样本点，通过向每一个在虚线内侧的样本点添加松弛变量$\xi_i$，将这些样本点搬移到支持向量虚线上。而本身就是在虚线外的样本点的松弛变量则可以设为0。
所以，可以得到软间隔SVM的问题变为：
同理，通过转化为对偶形式求解，对偶问题如下：
上述的C>0为惩罚参数，C值大时对误分类惩罚增大，表示我们想要犯更少的错误，C比较的小的时候对误分类惩罚减小，表示我们想要更大的间隔。
同理（与硬间隔形式一样），解出$\alpha^$之后，即可求解原始问题中的$w^,b^$，分别为：
$w^=\sum_{i=1}^N\alpha^_iy_ix_i以及b^=y_j-\sum_{i=1}^N\alpha^*_iy_i(x_i\cdot x_j)$;（具体证明见李航统计学习方法定理7.2）
对应的超平面为：
$\sum_{i=1}^N\alpha^_iy_ix_i^Tx_i+b^=0$
决策函数为：
$f(x)=sign(\sum_{i=1}^N\alpha^_iy_ix_i^Tx_i+b^)$
对应的数据是非线性可分，利用核技巧将线性分类问题的学习方法应用到非线性问题上；这里只需要将线性SVM对偶形式中的内积$x_i\cdot x_j$换成核函数。
输入：线性不可分训练数据集$T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$，其中，$x_i\in\chi=R^n，y_i\in Y={-1,+1},i=1,2,...,N$；
输出：最大间隔分离超平面和分类决策函数（实质上就是解$w,b$）。
算法过程：
-
获取合适的核函数$K(x,z)$和适当的参数$C$，构造并求解约束最优化问题：
$min_{\alpha} \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK({x_i, x_j})-\sum_{i=1}^N\alpha_i$ $s.t.\sum_{i=1}^N\alpha_iy_i=0$ $0\leq\alpha_i\leq C,i=1,2,...,N$ 求解得出最优解$\alpha^*$。
-
选择一个$\alpha^$的正分量$0<\alpha^<C$，求得:
$w^=\sum_{i=1}^N\alpha^iy_iK(\cdot ,x_i)以及b^*=y_j-\sum{i=1}^N\alpha^*_iy_iK(x_i\cdot x_j)$
-
超分离平面为：$\sum_{i=1}^N\alpha^_iy_iK(x_i\cdot x_j)+b^=0$
分类决策函数为：$f(x)=sign(\sum_{i=1}^N\alpha^_iy_iK(x_i\cdot x_j)+b^)$。
题目1
解：构造最优化问题：
通过求解不等式解得：
题目2
解：根据对偶问题构造：
将等式约束代入方程可以求得与第一题相同解，这里可以看出转换为对偶问题后解的方便性：将不等式约束转换为等式约束使得更易求解极值问题。
-
用线性分类方法求解非线性分类问题分为两步:
-
首先使用一个变换将原空间的数据映射到新空间;
-
然后在新空间里用线性分类学习方法从训练数据中学习分类模型。
-
核技巧就属于这样的方法
-
核技巧应用到支持向量机，其基本想法：
-
通过一个非线性变换将输入空间(欧氏空间R”或离散集合)对应于一个特征空间(希尔伯特空间)，使得在输入空间中的超曲面模型对应于特征空间中的超平面模型(支持向量机)。分类问题的学习任务通过在特征空间中求解线性支持向量机就可以完成.
-
核函数定义：
-
设X是输入空间(欧氏空间Rn的子集或离散集合)，又设H为特征空间(希尔伯特空间)，如果存在一个从X到H的映射
-
使得对所有$x,z\in \chi$
-
函数K(x,z)满足条件$K(x,z)=\phi(x)\cdot \phi(z)$
-
则称$K(x,z)$为核函数，
$\phi(x)$ 为映射函数，式中$\phi(x)\cdot \phi(z)$为$\phi(x)$ 和$\phi(z)$的内积 -
核技巧的想法是：
-
在学习与预测中只定义核函数K(x,z)，而不显式地定义映射函数，通常，直接计算K(x,z)比较容易。
-
注意：φ是输入空间Rn到特征空间H的映射，特征空间H一般是高维，映射可以不同。
-
线性支持向量机对偶问题中，无论是目标函数还是决策函数都只涉及输入实例和实例之间的内积。
-
目标函数中的内积$x_i \cdot x_j$用核函数$K(x_i,x_j)=\phi(x_i)\cdot \phi(x_j)$ 代替;
-
目标函数:$W(\alpha)=\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^N\alpha_i$
-
决策函数：$f(x)=sign(\sum_{i=1}^{N_s})\alpha_i^y_i\phi(x_i)\cdot \phi(x)+b^=sign(\sum_{i=1}^{N_s})\alpha_i^y_iK(x_i,x)+b^)$
-
问题：
-
己知映射函数φ，可以通过内积求得核函数K(x,z).
-
不用构造映射φ, 能否直接判断一个给定的函数K(x,z)是不是核函数?
-
或者说，函数K(x,z)满足什么条件才能成为核函数?
-
假设K(x,z)是定义在XxX上的对称函数，并且对任意的$x_1,x_2,...,x_m\in\chi$
-
K(x,z)的 Gram矩阵是半正定的，可以依据函数K(x,z)，构成一个希尔伯特空间(Hilbert space)；
-
其步骤是首先定义映射φ ，并构成向量空间S，然后在S上定义内积构成内积空间; 最后将S完备化构成希尔伯特空间.
-
K(x,z)是定义在$\chi \times \chi $对称函数，如果对任意的$x_i\in\chi,i=1,2,...,m$，K(x,z)对应的Gram矩阵$K=[K(x_i,x_j)]_{m\times m}$半正定的，则称K(x,z)为正定核。
-
这一定义在构造核函数时很有用。但对于一个具体函数K(x,z) 来说，检验它是否为正定核函数并不容易，因为要求对任意有限输入集${x_1,x_2,...,x_m}$验证K对应的Gram矩阵是否为半正定的。
-
在实际问题中往往应用己有的核函数。
-
常用核函数
-
1、多项式核函数（Polynomial kernel function)
-
$K(x,z)=(x\cdot z+1)^p$ -
对应的支持向量机为P次多项式分类器，分类决策函数：
-
$f(x)=sign(\sum_{i=1}^{N_i}\alpha_i^y_i(x_i\cdot x+1)^p+b^)$
-
2、高斯核函数 （Gaussian Kernel Function)
-
$K(x,z)=exp(-\frac{\left |x-z\right |^2}{2\sigma^2})$ -
决策函数：
-
$f(x)=sign(\sum_{i=1}^{N_i}\alpha_i^y_iexp(-\frac{\left |x-z\right |^2}{2\sigma^2}+b^)$
-
非线性支持向量机学习算法
-
输入：线性可分训练数据集$T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$，其中，$x_i\in\chi=R^n，y_i\in Y={-1,+1},i=1,2,...,N$；
输出：最大间隔分离超平面和分类决策函数（实质上就是解$w,b$）。
算法过程：
-
获取合适的核函数$K(x,z)$和适当的参数$C$，构造并求解约束最优化问题：
$min_{\alpha} \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK({x_i, x_j})-\sum_{i=1}^N\alpha_i$ $s.t.\sum_{i=1}^N\alpha_iy_i=0$ $0\leq\alpha_i\leq C,i=1,2,...,N$ 求解得出最优解$\alpha^=(\alpha_1^,\alpha_2^,...,\alpha_N^)^T$。
-
选择一个$\alpha^$的正分量$0<\alpha^<C$，求得:
$w^=\sum_{i=1}^N\alpha^iy_iK(\cdot ,x_i)以及b^*=y_j-\sum{i=1}^N\alpha^*_iy_iK(x_i\cdot x_j)$
-
超分离平面为：$\sum_{i=1}^N\alpha^_iy_iK(x_i\cdot x_j)+b^=0$
分类决策函数为：$f(x)=sign(\sum_{i=1}^N\alpha^_iy_iK(x_i\cdot x_j)+b^)$。
-
当K(x,z)是正定核函数时，是凸二次规划问题，解是存在的。