Support Vector Machines - Part 4

支持向量机 - SVM（Support Vector Machines）Part 4

支持向量机 - SVM（Support Vector Machines）Part 1

线性可分支持向量机学习算法 - 最大间隔法
线性可分支持向量机的对偶算法

支持向量机 - SVM（Support Vector Machines）Part 2

线性支持向量机
核函数及非线性支持向量机
常用的核函数及其特点

支持向量机 - SVM（Support Vector Machines）Part 3

序列最小最优化(SMO)算法

支持向量机 - SVM（Support Vector Machines）Part 4

支持向量回归 - SVR

支持向量回归 - SVR

支持向量回归 - SVR

回归和分类从某种意义上讲，本质上是一回事。

SVM分类，就是找到一个平面，让两个分类集合的支持向量或者所有的数据离分类平面最远；
SVR回归，就是找到一个回归平面，让一个集合的所有数据到该平面的距离最近。

假设某个元素到回归平面的距离为$ r = d(x) − g(x) $ 。另外，由于数据不可能都在回归平面上，距离之和还是挺大，因此所有数据到回归平面的距离可以给定一个容忍值$ \epsilon$ 防止过拟合。该参数是经验参数，需要人工给定。如果数据元素到回归平面的距离小于$ \epsilon $，则代价为0。SVR的代价函数可以表示为：

$cost(x) = \max ( 0, \quad \| d(x)-g(x) \| - \epsilon )$

其中$d(x)$为样本的标签。考虑松弛变量$ \zeta_i, \zeta_i^{\ast} $，分别表示上下边界的松弛因子，约束条件即为：

$\begin{cases} d(x_i) - g(x_i) < \epsilon + \zeta_i, \qquad \zeta_i \geq 0 \\ g(x_i) - d(x_i) < \epsilon + \zeta_i^{\ast}, \quad \zeta_i^{\ast} \geq 0 \end{cases}$

实际上要最小化$ \zeta_i, \zeta_i^{\ast} $，为了获得$w$的稀疏解，且假设$w$的计算结果满足正态分布，根据贝叶斯线性回归模型，对$w$有$L_2$范数约束。 SVR可以转化为最优化问题：

$\psi (x) = \sum_i (\zeta_i + \zeta_i^{\ast}) + \frac{1}{2} C' w^T w \\ \Downarrow \\ \psi (x) = C \sum_i (\zeta_i + \zeta_i^{\ast}) + \frac{1}{2} w^T w$

其中$C$是惩罚因子，是人为给定的经验参数。考虑约束条件，引入拉格朗日算子$\alpha, \alpha^{\ast}, \beta, \beta^{\ast}$，将最优化问题转化为对偶问题：

$J=\frac{1}{2} w^T w + C \sum_i (\zeta_i + \zeta_i^{\ast}) +\sum_i \alpha_i \left[ d(x_i) − g(x_i) − \epsilon − \zeta_i \right] + \sum_i \alpha_i^{\ast} \left[ g(x_i) − d(x_i) − \epsilon - \zeta_i^{\ast} \right] −\sum_i \beta_i \zeta_i − \sum_i \beta_i^{\ast} \zeta_i^{\ast}$

然后分别求导得到：

$\begin{equation*} \begin{aligned} \frac{\partial J}{\partial w} &= w − ( \sum_i \alpha_i x_i − \sum_i \alpha_i^{\ast} x_i) = 0 \\ \frac{\partial J}{\partial b} &= \sum_i ( \alpha_i − \alpha_i^{\ast} ) = 0 \\ \frac{\partial J}{\partial \zeta_i} &= C − \alpha_i − \beta_i = 0 \\ \frac{\partial J}{\partial \zeta_i^{\ast}} &= C − \alpha_i^{\ast} − \beta_i^{\ast} = 0 \\ C &= \alpha_i + \beta_i = \alpha_i^{\ast} + \beta_i^{\ast} \\ \end{aligned} \end{equation*}$

将上述式子代入$J$函数有：

$\begin{equation*} \begin{aligned} J &= \frac{1}{2}w^Tw − \sum_i (\alpha_i − \alpha_i^{\ast}) w x_i − b \sum_i (\alpha_i − \alpha_i^{\ast}) − \sum_i (\alpha_i + \alpha_i^{\ast}) \epsilon + \sum_i (\alpha_i − \alpha_i^{\ast})d(x_i) \\ &+ \underbrace{C \sum_i (\zeta_i + \zeta_i^{\ast})− \sum_i \alpha_i \zeta_i − \sum_i \alpha_i^{\ast} \zeta_i^{\ast} − \sum_i (C−\alpha_i)\zeta_i − \sum_i(C−\alpha_i^{\ast}) \zeta_i^{\ast}}_{这部分可以相互抵消，变为0} \\ &= \frac{1}{2} (\sum_i \alpha_i x_i - \sum_i \alpha_i^{\ast} x_i)(\sum_j \alpha_j x_j - \sum_j \alpha_j^{\ast} x_j) − (\sum_i \alpha_i x_i - \sum_i \alpha_i^{\ast} x_i)(\sum_j \alpha_j x_j - \sum_j \alpha_j^{\ast} x_j) − \sum_i ( \alpha_i + \alpha_i^{\ast}) \epsilon + \sum_i (\alpha_i − \alpha_i^{\ast}) d(x_i) \\ &= − \frac{1}{2} \sum_i \sum_j (\alpha_i − \alpha_i^{\ast} ) ( \alpha_j − \alpha_j^{\ast} ) x_i x_j − \sum_i (\alpha_i + \alpha_i^{\ast}) \epsilon + \sum_i (\alpha_i − \alpha_i^{\ast})d(x_i) \\ s.t. \qquad 0 \leq \quad \alpha_i, \alpha_i^{\ast} \quad \leq C \end{aligned} \end{equation*}$

其中$\zeta, \zeta^{\ast}, \beta, \beta^{\ast}$都在计算过程中抵消了。$\epsilon, C$则是人为给定的参数，是常量。如果要使用核函数，可以将上式写成：

$J = − \frac{1}{2} \sum_i \sum_j (\alpha_i − \alpha_i^{\ast} ) (\alpha_j − \alpha_j^{\ast}) K(x_i, x_j) − \sum_i ( \alpha_i + \alpha_i^{\ast} ) \epsilon + \sum_i ( \alpha_i − \alpha_i^{\ast})d(x_i)$

SVR的代价函数和SVM的很相似，但是最优化的对象却不同，对偶式有很大不同，解法同样都是基于拉格朗日的最优化问题解法。求解这类问题的早期解法非常复杂，后来出来很多新的较为简单的解法，对数学和编程水平要求高，对大部分工程学人士来说还是颇为复杂和难以实现，因此大牛们推出了一些SVM库。比较出名的有libSVM，该库同时实现了SVM和SVR。

> SVR支持向量机回归 >