支持向量机(SVM)

2020-02-24 本文已影响0人没天赋的学琴

支持向量机

支持向量机(suport vector machine，简称：SVM)，是一种常用于二分类的学习模型。该模型是寻找在特征空间中间隔最大的线性分类器，而对于非线性可分的数据，可以通过“Kernel method”，也叫核函数，来使SVM也可以很好地处理非线性可分的数据。

SVM的出发点

   在Logistic Regression的模型表达中： $h_\theta(x) = {{1} \over {1+e^{- \theta^Tx} }}$ 代表的是数据 $x$ 的 $p(y=1|x;\theta)$ 。当 $h_\theta(x)$ 的值越大，数据 $x$ 被分类为“ $y=1$ ”的可能性则越大；当 $h_\theta(x)$ 的值越小，数据 $x$ 被分类为“ $y=0$ ”的可能性则越大。换个角度来说，若 $\theta^Tx$ 越大于0， $x$ 归类为“ $y=1$ ”的可能性则越大， $\theta^Tx$ 越小于0， $x$ 归类为“ $y=0$ ”的可能性则越大。
   而SVM的出发点就是得到一个二分类器，不仅可以将训练数据正确分类，并且使得每个训练数据可以尽可能的远离分离平面。
   SVM模型的表达如下：
$h_{w,b}(x) = g(w^Tx+b)$ 其中： $g(z) = \begin{cases} 1 & w^Tx+b \geq 0 \\ -1 & w^Tx+b < 0 \end{cases}$
在SVM中，正负类别不再是以 $\{ 0,1 \}$ 标记，而是以 $\{ 1,-1 \}$ ；并且会把求和中的偏置项独立出来，变成 $h_{w,b}(x) = g(w^Tx+b)$ 而不是 $h_\theta(x) = g(\theta ^Tx)$ 。 $h_{w,b}(x)$ 计算得到的结果，不是概率，而是两个类别之一。

Functional margin && geometric margin

对于一个数据 $(x^{(i)}, y^{(i)})$ ，其functional margin可以定义为： $\hat{\gamma}^{(i)} = y^{(i)} (w^Tx^{(i)} + b)$ 对于一个数据集 $S=\{ (x^{(i)}, y^{(i)}); i=1,\cdots,n \}$ ，设： $\hat {\gamma} = \min_{i=1,\cdots,n} \hat{\gamma}^{(i)}$ 由于 $g(w^Tx+b)$ 仅仅是得到" $-1$ "或" $+1$ "，所以 $g(w^Tx+b)$ = $g(2w^Tx+2b)$ ，这种倍数变化，不会对分类器产生什么影响，但用 $(w,b)$ 和 $(2w,2b)$ 算出来的 $\hat{\gamma}$ 的大小是有倍数差距的。
下图是二分类数据分布及其相应分类超平面，而在此处超平面为一条直线，该超平面的方程为： $w^Tx+b=0$

该超平面的法向量为，A为数据集中的一个样本，为点A到直线的距离，B为点A到直线的距离的交点。通过向量的定义可以得到：因为点B是上的点，因此：则可以化简得到点A到超平面的距离为：
由于引出geometric margin的定义，也是以作为其标号： geometric margin不会因为的倍数变化，而改变其值的大小；并且通过该定义可以很明显地看到，当时，和在数值上是相等。同样，对于一个数据集，设：

最大间隔分类器

那么对SVM进行进一步的抽象，由于是想找到尽可能远离分类平面的分类器，因此可以将其抽象成一个带等式和不等式的约束优化问题：
$\begin{aligned} \max_{\gamma, w, b} &\quad \gamma \\ s.t. & \quad y^{(i)} (w^T x + b) \geq \gamma , \quad i=1,\cdots,n \\ & \quad ||w|| = 1 \end{aligned}$ 由于“ $||w|| = 1$ ”是一个非凸的约束条件，不便于上述优化问题的求解，因此对上述问题进行进一步变换，得到下面的等效问题：
$\begin{aligned} \max_{\hat{ \gamma }, w, b} &\quad { {\hat{ \gamma }} \over {||w||} } \\ s.t. & \quad y^{(i)} (w^T x + b) \geq \hat{ \gamma } , \quad i=1,\cdots,n \\ \end{aligned}$ 同样“ ${ {\hat{ \gamma }} \over {||w||} }$ ”也不是一个非凸的目标函数，也不便于上述问题的求解；因此，利用funtional margin的一个性质，通过改变 $(w,b)$ 的倍数，使得 ${\hat{\gamma}} = 1$ ，则目标函数变为： ${1} \over {||w||}$ ，为了方便起见，上述问题可以进一步等效为：
$\begin{aligned} \min_{w, b} & \quad {{1} \over {2} } ||\omega||^2 \\ s.t. & \quad y^{(i)} (w^T x^{(i)} + b) \geq 1, \quad i=1, \cdots, n \end{aligned}$
上述即为从最大间隔出发，最后抽象出来的一个不等式约束优化问题。并且该问题可以通过一些可求解二次规划问题的程序来解决，最后解决得到的 $(w, b)$ 即为SVM的参数。

对偶形式

虽然已经将SVM抽象成一个不等式约束优化问题，并且已经有现成工具解决该问题；但是，上述形式不利于引入“Kernel method”来使得SVM可以解决非线性数据的划分。有意思的是，可以利用拉格朗日对偶性，将上述优化问题转化其为对偶问题，而其对偶形式可以很方便地引入“Kernel method”，并且有更为高效的算法来解决对偶问题。

拉格朗日对偶性简单介绍

首先，对于一个等式约束优化问题：
$\begin{aligned} \min_w & \quad f(w) \\ s.t. & \quad h_i (x) = 0, \quad i = 1, \cdots, l \end{aligned}$ 利用拉格朗日乘数法，设拉格朗日函数，然后求偏导，设为0，即可求得答案。而现在，对于不等式约束的优化问题，也可以利用上述思路来解决。假设，不等式约束的优化问题如下：
$\begin{aligned} \min_w & \quad f(w) \\ s.t. & \quad g_i(w) \leq 0 , \quad i = 1, \cdots, k \\ & \quad h_i(w) = 0, \quad i = 1, \cdots, l \\ \end{aligned}$ 设拉格朗日函数为： $L(w, \alpha, \beta) = f(w) + \sum _{i=1} ^{k} {\alpha_i g_i(w)} + \sum _{i=1} ^{l} {\beta_i h_i(w)}$
现在设立 $\theta_p(w)$ ，其定义为： $\theta_p(w) = \max_{\alpha, \beta: \alpha_i \geq 0} L(w, \alpha, \beta)$ 而对于 $\theta_p(w)$ 其取值情况如下：
$\begin{aligned} \theta_p(w) = \begin{cases} f(w) & w符合上述问题的约束 \\ \infty & w不符合上述问题约束 \\ \end{cases} \end{aligned}$ 因此原问题可以等效为： $\min_w \theta_p(w) = \min_w \: \max_{\alpha, \beta: \alpha_i \geq 0} L(w, \alpha, \beta)$ 。

然后，定义 $\theta_D(\alpha, \beta)$ ，其定义为： $\theta_D(\alpha, \beta) = \min_w L(w, \alpha, \beta)$ 那么可以定义一个对偶问题为： $\max_{\alpha, \beta: \alpha_i \geq 0} \theta_D(\alpha, \beta) = \max_{\alpha, \beta: \alpha_i \geq 0} \: \min_w L(w, \alpha, \beta)$
对偶问题和原问题的关系：
$d ^* = \max_{\alpha, \beta: \alpha_i \geq 0} \: \min_w L(w, \alpha, \beta) \leq \min_w \: \max_{\alpha, \beta: \alpha_i \geq 0} L(w, \alpha, \beta) = p ^*$ 并且在某些条件(基于一定的假设)下， $d ^* = p ^*$ 。
现在有如下条件：

设 $w^*$ 为原问题 $\min_w \theta_p(w)$ 的解；
设 $\alpha ^* , \beta ^*$ 为对偶问题 $\max_{\alpha, \beta: \alpha_i \geq 0} \theta_D (\alpha, \beta)$ 的解；
$p ^* = d ^* = L(w^*, \alpha ^*, \beta ^*)$

那么 $w ^*, \alpha ^* , \beta ^*$ 就会满足KKT条件： $\begin{aligned} { {\partial} \over {\partial w_i} } L(w ^*, \alpha ^* , \beta ^*) & = 0, & i = 1, \cdots , d \\ { {\partial } \over {\partial \beta_i} } L(w ^*, \alpha ^* , \beta ^*) & = 0, & i = 1, \cdots , l \\ \alpha_i ^* g_i(w ^*) & = 0, & i = 1, \cdots, k \\ g_i(w ^*) & {\leq \ } 0, & i = 1, \cdots, k \\ \alpha ^* & {\geq \ } 0, & i = 1, \cdots, k \\ \end{aligned}$
根据上述条件，当 $\alpha_i ^* > 0$ 时， $g_i(w ^*) = 0$ ，这代表 $w ^*$ 到达了约束条件的边界， $g_i(w ^*) \leq 0$ 的约束起作用。这个性质可以帮助找到SVM的支持向量。
在凸优化中，KKT条件不仅仅是必要条件，也是一个充分条件，即若有 $w , \alpha , \beta$ 符合KKT条件，那 $w$ 则为原问题的解， $\alpha, \beta$ 为对偶问题的解。

SVM问题的对偶形式

SVM的优化原问题是： $\begin{aligned} \min_{w, b} & \quad {{1} \over {2} } ||\omega||^2 \\ s.t. & \quad y^{(i)} (w^T x^{(i)} + b) \geq 1, \quad i=1, \cdots, n \end{aligned}$ 将不等式约束改写为： $g_i(w) = -y^{(i)} (w^T x^{(i)} + b) + 1 \leq 0$ ，然后可以设立拉格朗日函数为： $L(w, b, \alpha) = {1 \over 2} ||w||^2 - \sum _{i = 1} ^{n} {\alpha_i [y^{(i)} (w^Tx^{(i)} + b) - 1] }$
若对 $L(w, b, \alpha)$ 针对参数 $(w, b)$ 进行最小化，把 $\alpha$ 看成常量，然后利用拉格朗日乘数法，可得： $\nabla_w L(w, b, \alpha) = w - \sum _{i = 1} ^{n} {\alpha_i y^{(i)} x^{(i)}} = 0$ 即： $w = \sum _{i = 1} ^{n} {\alpha_i y^{(i)} x^{(i)}}$ 而 ${ {\partial} \over {\partial b} } L(w, b, \alpha) = \sum _{i = 1} ^{n} {\alpha_i y^{(i)}} = 0$
上述过程就是完成一个 $\min_w \theta_p(w)$ 的过程。将上面的 $w$ 回代到 $L(w, b, \alpha)$ 可得： $\begin{aligned} L(w, b, \alpha) =& \sum _{i = 1} ^{n} {\alpha_i} - {1 \over 2 } \sum _{i, j = 1}^{n} {y^{(i)} y^{(j)} \alpha_i \alpha_j (x^{(i)})^T x^{(j)}} - b \sum _{i = 1} ^{n} {\alpha_i y^{(i)}} \\ =& \sum _{i = 1} ^{n} {\alpha_i} - {1 \over 2 } \sum _{i, j = 1} ^{n} {y^{(i)} y^{(j)} \alpha_i \alpha_j (x^{(i)})^T x^{(j)} } \\ =& \sum _{i = 1} ^{n} {\alpha_i} - {1 \over 2 } \sum _{i, j = 1} ^{n} {y^{(i)} y^{(j)} \alpha_i \alpha_j <x^{(i)}, x^{(j)}> } \\ \end{aligned}$ 那么原问题的对偶形式为： $\begin{aligned} \max_{\alpha} W( \alpha ) &= \sum _{i = 1} ^{n} {\alpha_i} - {1 \over 2 } \sum _{i, j = 1} ^{n} {y^{(i)} y^{(j)} \alpha_i \alpha_j <x^{(i)}, x^{(j)}> } \\ s.t. & {\quad} \alpha_i {\geq} 0, \quad i = 1, \cdots, n \\ & {\quad} \sum _{i = 1} ^{n} {\alpha_i y^{(i)}} = 0 \end{aligned}$ 对于上述问题，可以通过更为高效的算法来求解得到 $\alpha$ ，这样就可求解得到 $w$ 的值。回看KKT条件的：“ $\alpha_i g_i(w) = 0$ ” 和 “ $\alpha \geq 0$ ”，当 $\alpha > 0$ 时： $\begin{aligned} g_i(w) & = 0 \\ g_i(w) & = -y^{(i)}(w^Tx^{(i)} + b) + 1 = 0\\ \end{aligned}$ 可得到： $y^{(i)}(w^Tx^{(i)} + b) = 1$ ，因为之前设置 $\hat{\gamma} = 1$ ，因此可以说明， $\alpha_i > 0$ 的点 $(x^{(i)}, y^{(i)})$ 落在最大分类的间隔上，并且称这些点为支持向量。
最后，SVM原问题转换得到的对偶问题，可以利用SMO算法来对上述问题更为高效地求解。并且SVM的模型可以表达为： $\begin{aligned} w^T x + b &= (\sum _{i = 1} ^{n} {\alpha_i y^{(i)}} x^{(i)})^T x + b \\ &= \sum _{i = 1} ^{n} {\alpha_i y^{(i)}} <x^{(i)}, x> + b \end{aligned}$ 若想将核函数运用到SVM中，只需将 $<x^{(i)}, x>$ 替换成相应的 $K(x^{(i)}, x)$ 即可。

个人感想

与前面线性回归、逻辑回归给笔者感觉不同，线性回归、逻辑回归等感觉是从数学角度出发，从而归纳出模型；而SVM的感觉，是从实际出发(要得到分类间隔最大)，然后再抽象出其模型，进一步得抽象到模型训练时候的优化问题，回归到数学本质；SVM感觉更像一个解决实际问题的一个从具体到抽象的过程。
这篇文章对SVM做了一个整体简单的介绍，也是对于学习SVM时的一个简单浅显的总结，还有很多可以深入关注的点。并且