机器学习算法之支持向量机

数学描述

训练数据及标签：
$\{(x_1,y_1), (x_2,y_2), \cdots, (x_N,y_N)\}$
超平面(Hyper plane)线性模型：
$\omega^Tx + b = 0$
线性可分定义：
$\{(x_i,y_i)\}_{i=1,\cdots,N}$
$\exists(\omega,b)$ ,使得对 $\forall i=1,\cdots,N$
$\begin {cases} \omega^Tx_i+b \geq 0 & y_i=+1 \\ \omega^Tx_i+b < 0 & y_i=-1 \end {cases}$
综合上述公式：
$y_i(\omega^Tx_i+b) \geq 0$

SVM线性模型：

目标函数：
$\min\limits_{\omega,b} \frac{1}{2} \mid \mid \omega \mid \mid^2$
约束条件：
$y_i(\omega^Tx_i+b) \geq 1, \quad i=1,2,\cdots,m$
上述优化问题是凸优化问题（二次规划问题，Quadratic Programming）或者无解，或者只有一个极值

目标条件（Objective Function）是二次项
限制条件是一次项

性能指标：

距离超平面最近的几个训练样本点，称为支持向量（Support Vectors），两个异类支持向量到超平面的距离之和为间隔（Margin），即性能指标。

定理1：

$\omega^Tx+b=0$ 和 $a\omega^Tx+ab=0$ 表示同一超平面，其中 $a\in\Re^+$ 。即 $(\omega,b)$ 满足公式，则 $(a\omega,ab)$ 也满足公式

定理2：点到平面的距离公式

平面方程： $\omega_1x+\omega_2y+b=0$ ，则点 $(x_0,y_0)$ 到该平面的距离：
$d = \frac {|\omega_1x_0 + \omega_2 y_0 + b|} {\sqrt {\omega_1^2 + \omega_2^2}}$
向量 $x_0$ 到超平面的距离：
$d = \frac {|\omega^Tx_0 + b|}{||\omega||}$
于是， $\exists a$ 使得 $(a\omega,ab)$ 在支持向量 $x_0$ 上有 $|\omega^Tx_0+b|=1$ ，则此时支持向量到平面的距离：
$d = \frac {1}{||\omega||}$
$y_i(\omega^Tx_i + b) \geq 1, \quad i=1,2,\cdots,m$

SVM非线性模型：

处理方法：在线性模型的基础上，修改目标函数和限制条件，于是:
目标函数：
$\min \frac {1}{2}||\omega||^2 + C\sum_{i=1}^N \xi_i$
限制条件：
$y_i(\omega^Tx_i + b) \geq 1 - \xi_i$
$\xi_i \geq 0$
注：在线性模型中加上松弛变量 $\xi_i \geq 0$ 和 $y_i(\omega^Tx_i + b) \geq 1 - \xi_i$ 的意义是允许部分数据未被正确分类（即提高泛化能力），而当 $\xi_i$ 值过大时模型无法有效分类，于是需要对 $\xi_i$ 的值进行限制。对于 $\frac {1}{2}||\omega||^2 + C\sum_{i=1}^N \xi_i$ ，其中 $C$ 为事先设定的参数， $\xi_i$ 值越大，对应的目标函数值越大，则参数越不满足最小化的要求。

SVM非线性模型

处理方法：低维到高维映射

原始样本空间并不存在一个能正确划分两类样本的线性超平面
解决方法：将样本从原始空间映射到一个更高维的特征空间，使其在该特征空间内线性可分。
证明：在特征空间中对部分数据点进行随机标注，特征空间的维度越高，线性可分的概率越大。当在无限维特征空间中，线性可分的概率为1.
核函数：已知将原始空间映射到更高维空间可使样本集线性可分，接下来只需要找到一个符合条件的映射 $\phi(x)$ ，即可解决线性不可分问题。

通过公式推导可知，我们可以不知道无限维映射 $\phi(x)$ 的显示表达，只要知道存在一个核函数（kernel function）映射后的目标函数仍然有解
$K(x_1,x_2) = \phi(x_1)^T\phi(x_2)$

常用的核函数：

线性内核(Linear)
$K(x_1,x_2) = x_1^Tx_2$
高斯核(Rbf)
$K(x_1,x_2) = e^{-\frac{||x_1-x_2||^2}{2\sigma^2}}=\phi(x_1)^T\phi(x_2)$
多项式核(Ploy)
$K(x_1,x_2) = (x_1^Tx_2 + 1)^d = \phi(x_1)^T\phi(x_2)$
Tanh核
$K(x_1,x_2) = \tanh (\beta x_1^Tx_2 + b)$
$\tanh(x) = \frac {e^x - e^{-x}}{e^x + e^{-x}}$
$K(x_1,x_2)$ 能写成 $\phi(x_1)^T\phi(x_2)$ 的充要条件:

交换性：
$K(x_1,x_2) = K(x_2,x_1)$
半正定性
$\forall c_i,x_i(i=1,\cdots,N)$ ，有：
$\sum_{i=1}^N \sum_{j=1}^N c_ic_jK(x_i,x_j) \geq 0$

原问题和对偶问题理论介绍：

已知映射 $\phi(x)$ ，则原优化问题的目标函数：
$\min\frac {1}{2}||\omega||^2 + C\sum_{i=1}^N \xi_i$
限制条件：
$y_i(\omega^T\phi(x_i) + b) \geq 1-\xi_i(i=1,\cdots,N)$
当下的问题是，在已知核函数 $K(x_1,x_2)$ ，不知 $\phi(x)$ 的情况下，如何求解优化问题？

对偶理论

原问题(Prime Problem)目标函数：
$\min f(\omega)$
限制条件：
$g_i(\omega) \leq 0 (i=1,\cdots,K)$
$h_i(\omega) = 0 (i=1,\cdots,M)$
对偶问题(Dual Problem)目标函数：
$\max \theta(\alpha,\beta) = \inf _{\forall \omega}\{L(\omega,\alpha,\beta)\}$
其中：
$L(\omega,\alpha,\beta) = f(\omega) + \sum_{i=1}^K \alpha_ig_i(\omega) + \sum_{i=1}^M \beta_ih_i(\omega) = f(\omega) + \alpha^Tg(\omega) + \beta^Th(\omega)$
限制条件：
$\alpha_i \geq 0 (i=1,\cdots,K)$
$\inf _ {\omega}\{L(\omega,\alpha,\beta)\}$ 表示在限定 $\alpha,\beta$ 的条件下，遍历全部的 $\omega$ 的最小值。于是，每确定一组 $\alpha,\beta$ 值都能得到一个最小值，对偶问题的解就是所有最小值中的最大值。

定理1：

如果 $\omega^*$ 是原问题的解，而 $\alpha^*,\beta^*$ 是对偶问题的解，则有：
$f(\omega^*) \geq \theta(\alpha^*,\beta^*)$

定理2：

$G=f(\omega^*) - \theta(\alpha^*,\beta^*) \geq 0$ 叫做原问题与对偶问题的间距(Duality Gap)

定理3：强对偶定理

若 $f(\omega)$ 为凸函数，且 $g(\omega) = A\omega + b,h(\omega) = c\omega + d$ ，则此优化问题的原问题与对偶问题间距为0，即 $f(\omega^*) = \theta(\alpha^*,\beta^*)$

定理4：KKT条件

对于 $\forall i=1,\cdots,K$ ，或者 $\alpha_i^*=0$ ，或者 $g_i^*(\omega^*) = 0$

综合上述公式：

非线性模型的原问题(Prime Problem)目标函数：
$\min f(\omega)$
限制条件：
$g_i(\omega) \leq 0 \mid i=1,\cdots,K$
对偶问题(Dual Problem)目标函数：
$\max \theta (\alpha,\beta) = \inf_{\forall \omega}\{L(\omega,\alpha,\beta)\}$
其中：
$L(\omega,\alpha,\beta) = f(\omega) + \sum_{i=1}^K \alpha_ig_i(\omega) + \sum_{i=1}^M \beta_ih_i(\omega)$
限制条件：
$\alpha_i \geq 0 \mid i=1,\cdots,K$
KKT条件：

对于 $\forall i=1,\cdots,K$ ，或者 $\alpha_i^*=0$ ，或者 $g_i^*(\omega^*) = 0$

SVM非线性模型将SVM原问题化成对偶问题

改变原问题形式，满足强对偶定理
原问题的目标函数:
$\min \frac {1}{2} ||\omega||^2 - C\sum_{i=1}^N\xi_i$
限制条件：
$\begin {cases} 1+\xi_i-y_i\omega^T\phi(x_i) - y_ib \leq 0 \\ \xi_i \leq 0 \end {cases}$
对偶问题的目标函数:
$\max \theta (\alpha,\beta) = \inf_{\omega, \xi_i,b} \{\frac{1}{2}||\omega||^2 - C\sum_{i=1}^N\xi_i + \sum_{i=1}^N\beta_i\xi_i + \sum_{i=1}^N\alpha_i[1 + \xi_i - y_i\omega^T\phi(x_i) - y_ib]\}$
限制条件：
$\begin {cases} \alpha_i \geq 0 \mid i=1,\cdots,N \\ \beta_i \geq 0 \mid i=1,\cdots,N \end {cases}$

推导过程

$L(\omega,\alpha,\beta)$ 的极值点在偏导为0处，于是：
$\frac {\partial L}{\partial \omega} = 0 \rightarrow \omega = \sum_{i=1}^N \alpha_i y_i \phi(x_i)$
$\frac {\partial L}{\partial \xi_i} = 0 \rightarrow \beta_i + \alpha_i = C$
$\frac {\partial L}{\partial b} = 0 \rightarrow \sum_{i=1}^N \alpha_i y_i = 0$
处理 $\frac {1} {2} \mid \mid \omega \mid \mid ^2$ ，可得：
$\frac {1}{2} ||\omega||^2 = \frac {1}{2} \omega^T\omega = \frac {1}{2} (\sum_{i=1}^N \alpha_iy_i\phi(x_i))^T (\sum_{j=1}{N} \alpha_jy_j\phi(x_j)) = \frac {1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i\alpha_jy_iy_j\phi(x_i)^T\phi(x_j)$
对偶问题化简，目标函数：
$\max \theta(\alpha,\beta) = \sum_{i=1}^N \alpha_i - \frac {1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j K(x_i,x_j)$
限制条件：
$\begin {cases} 0 \leq \alpha_i \leq C \\ \sum_{i=1}^N \alpha_iy_i = 0 \end {cases}$
利用SMO算法求解上述最优化问题
注：正常流程是根据对偶问题的解求出参数 $\omega,\phi,b$ ，没必要
$\omega^T\phi(x) = \sum_{i=1}^T [\alpha_iy_i\phi(x_i)]^T\phi(x) = \sum_{i=1}^N \alpha_iy_i\phi(x_i)^T\phi(x) = \sum_{i=1}^N \alpha_iy_iK(x_i,x)$
利用KKT条件求 $b$ , $\forall i = 1, \cdots, N$
第一种情况：
要么 $\beta_i = 0$ ，要么 $\xi_i = 0$
第二种情况：
要么 $\alpha_i = 0$ ，要么 $1 + \xi_i - y_i\omega^T\phi(x_i)-y_ib=0$
于是，取一个 $0 < \alpha_i < C \rightarrow \beta_i = C - \alpha_i >0$ 。此时， $\beta_i \neq 0 \rightarrow \xi_i = 0$ ，同时， $\alpha_i \neq 0 \rightarrow 1 - y_i\omega^T\phi(x_i) - y_ib = 0$
最终解得：
$b = \frac {1 - y_i\omega^T\phi(x_i)}{y_i} = \frac {1 - y_i\sum_{j=1}^N \alpha_jy_jK(x_i,y_j)}{y_i}$

SVM算法流程：

训练流程：

输入：
$\{ (x_i, y_i) \} _{i=1,\cdots,N}$
目标函数：
$\max \theta(\alpha) = \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i\alpha_jy_iy_jK(x_i,x_j)$
限制条件：
$\begin {cases} 0 \leq \alpha_i \leq C \\ \sum_{i=1}^N \alpha_iy_i = 0 \end {cases}$
计算 $b$ ，找一个 $0<\alpha_i<C$
$b = \frac {1 - y_i \sum_{j=1}^N \alpha_jy_jK(x_i,x_j)}{y_i}$

SVM测试流程：

输入测试样本 $x$ ，其中：
$\begin{cases} \sum_{i=1}^N \alpha_iy_iK(x_i,x)+b \geq 0 & y = +1 \\ \sum_{i=1}^N \alpha_iy_iK(x_i,x)+b < 0 & y = -1 \end{cases}$

机器学习算法之支持向量机

机器学习算法之支持向量机