支持向量机 | wsztrush

JerryXia 发表于 2018-12-04 16:24:24 , 阅读 (0)

平面上有两种不同类型的点：

用支持向量机将他们分开的思路是：

找到一个划分平面，将蓝色和红色分开，同时尽量离他们比较远（间隔越大越好）。

显然上面的并不是最好，找最优解的过程比较精彩，慢慢来看。

模型

假设空间中有训练数据集$(x_1, y_1),(x_2, y_2),…,(x_n, y_n)$，得到的划分平面为：

$$
w · x + b = 0
$$

$(x_i, y_i)$到平面的函数间隔为：

$$
\hat{\gamma} = \min \quad y_i \times (w·x_i + b)
$$

在$w,b$同比例变化时，平面没有动，但是函数间隔却增大了，于是有了几何间隔：

$$
\gamma = \min \quad y_i \times (\frac{w}{\left \| w \right \|}·x_i + \frac{b}{\left \| w \right \|})
$$

模型要将数据划分开，并且在最差（异类接近）的数据上也分的最开：

$$
\begin{align}
\max & \quad \gamma \\
st. & \quad y_i \times (\frac{w}{\left \| w \right \|} · x_i + \frac{b}{\left \| w \right \|}) \geqslant \gamma
\end{align}
$$

等价于(假设$\gamma \times \|w\| = 1$)：

$$
\begin{align}
\min& \quad \frac{1}{2} ·\left \| w \right \|^2 \\
st.& \quad y_i \times (w·x_i + b) - 1 \geqslant 0
\end{align}
$$

然而有的训练集无法分割，此时可以通过松弛变量$\xi_i$来做一些放宽（C为惩罚系数）：

$$
\begin{align}
\min& \quad \frac{1}{2} ·\left \| w \right \|^2 + C \sum \xi_i\\
st.& \quad y_i \times (w·x_i + b) - 1 \geqslant \xi_i
\end{align}
$$

算法

构造原问题的拉格朗日函数：

$$
L(w,b,\alpha) = \frac{1}{2} \left \|w \right \|^2 - \sum \alpha_i(y_i \times (w·x_i+b )-1)
$$

等价于：

$$
\min_{w,b} \max_{\alpha_i \geqslant 0} L(w, b, \alpha)
$$

对偶形式为：

$$
\max_{\alpha_i \geqslant 0} \min_{w,b} L(w, b, \alpha)
$$

根据$\min L(w, b, \alpha)$于是有：

$$
\begin{cases}
\frac{\partial }{\partial w}L(w, b, \alpha) & = 0 & \Rightarrow & w = \sum \alpha_iy_ix_i & ① \\
\frac{\partial }{\partial b}L(w, b, \alpha) & = 0 & \Rightarrow & \sum a_iy_i = 0 & ②
\end{cases}
$$

将①②带入$L(w, b, \alpha)$中得到：

$$
\begin{align}
L(w, b, \alpha) & = \frac{1}{2} \sum_i \sum_j \alpha_i \alpha_j y_i y_j (x_i·x_j) - \sum_i \alpha_i y_i \left ( \left ( \sum \alpha_j y_j x_j \right ) · x_i + b \right ) + \sum_i \alpha_i & from \; ①\\
& = -\frac{1}{2} \sum_i \sum_j \alpha_i \alpha_j y_i y_j (x_i·x_j) + \sum_i \alpha_i & from \; ②
\end{align}
$$

在最优解时存在$\alpha_i > 0$，即有$y_i \times (wx_i+b) - 1 = 0$，将①带入得到：

$$
b = y_j - \sum_i \alpha_i y_i (x_i·x_j) \quad ③
$$

将①带入原方程，得到超平面方程为：

$$
\sum \alpha_i y_i (x · x_i) + b = 0
$$

其中$\alpha_i > 0$对应的$x_i$为支持向量。类似这个过程，可以求得带有松弛变量$\xi_i$的对偶问题为：

$$
\begin{align}
\min \quad & \frac{1}{2} \sum \sum \alpha_i \alpha_j y_i y_j (x_i · x_j) - \sum \alpha_i \\
st. \quad & \sum \alpha_i y_i = 0 \\
& 0 \leqslant \alpha_i \leqslant C
\end{align}
$$

而超平面方程相同。对一些问题本身就是非线性可分的，此时就需要利用Kernel Trick（低维映射到高维之后线性可分）：

核函数的定义为：

如果存在从$X$到$H$的映射：$\phi (x) : X \rightarrow H$，使得所有$x,z \in X$函数$K(x,z)$满足$K(x,z)=\phi (x)·\phi (z)$，则称$K(x,z)$为核函数。

核函数定义了映射之后的内积，所以我们只需要知道核函数而不再需要关心映射。引入核函数之后，目标函数变为：

$$
W(\alpha) = \frac{1}{2} \sum \sum \alpha_i \alpha_j y_i y_j K(x_i, x_j) - \sum \alpha_i
$$

分类决策函数变为：

$$
f(x) = sign \left ( \sum \alpha_iy_iK(x_i, x) + b \right )
$$

当训练集越来越大，常用的凸二次优化算法会非常低效，常用的方法是SMO算法。

拉格朗日函数

有条件的优化问题：

$$
\begin{align}
min& \quad f(x) \\
st.& \quad g_i(x) = 0
\end{align}
$$

构造函数$F(x) = f(x) + \sum \lambda_i·g_i(x)$，求偏导方程：

$$
\begin{cases}
& \partial F / \partial x = 0 \\
& \partial F / \partial \lambda = 0
\end{cases}
$$

得到的便是原问题的极值点。一种理解方式如下图（约束$g(x)$是一条曲线）：

当$f(x)$与$g(x)$的法向量相反时$f(x)$可以取得极值：

$$
\frac{\partial f}{\partial x} = - \lambda \frac{\partial g}{\partial x} \quad \Rightarrow \quad \frac{\partial f + \lambda · \partial g}{\partial x} = 0
$$

另外，换个跟简单的思路：

在$F(x)$中引入的变量$\lambda$是可以随便变的，如果$g(x)\neq0$则一定没有极值。

对偶与KKT

更一般的有条件的优化问题：

$$
\begin{align}
\min& \quad f(x) \\
st.& \quad g_i(x) \leqslant 0 \\
& \quad h_j(x) = 0
\end{align}
$$

得到拉格朗日函数$L(x, \alpha, \beta) = f(x) + \sum \alpha_i · g_i(x) + \sum \beta_j · h_j(x)$，$\alpha_i，\beta_j$为偶变量，此时：

如果$g_i(x) > 0$，无限增大$\alpha_i$会导致$L(x, \alpha, \beta)$无限地变大。

于是构造新函数（不满足约束时一定不存在极值）：

$$
\theta_p(x) = \max_{\alpha_i \geqslant 0,\beta_i} \; L(x, \alpha, \beta) =
\begin{cases}
& f(x) \quad 存在最大值 \\
& \infty
\end{cases}
$$

这样原问题变为（两种形式等价）：

$$
\min \; f(x) = \min \; \theta_p(x) = \min_x \; \max_{\alpha_i \geqslant 0,\beta_i} \; L(x, \alpha, \beta)
$$

在固定$\alpha，\beta$时，调整$x$有函数：

$$
\theta_d(\alpha, \beta) = \min_x L(x, \alpha, \beta)
$$

得到原问题的对偶形式：

$$
\max_{\alpha_i \geqslant 0,\beta_i} \; \min_x \; L(x, \alpha, \beta)
$$

显然有：

$$
\theta_p(x) \geqslant \theta_p(x^\star) \geqslant L(x^\star, \alpha, \beta) \geqslant \theta_d(\alpha, \beta)
$$

于是有$\min \theta_p \geqslant \max \theta_d$。相等时满足KKT条件（必要性）：

$$
\begin{cases}
\frac{\partial }{\partial x}L(x, \alpha, \beta) & = 0 \quad from \; \theta_d \\
\frac{\partial }{\partial \beta}L(x, \alpha, \beta) \quad = h(x) & = 0 \quad from \; \theta_p \\
\alpha_i · g(x_i) & = 0 \quad from \; \theta_p \\
g(x_i) & \leqslant 0 \\
\alpha_i & \geqslant 0
\end{cases}
$$

如果有$(x^\star, \alpha^\star,\beta^\star)$满足KKT条件（充分性），根据①有：

$$
L(x^\star, \alpha^\star, \beta^\star) = \theta_d(\alpha^\star, \beta^\star)
$$

根据②③④⑤有：

$$
L(x^\star, \alpha^\star, \beta^\star) = \theta_p(x^\star)
$$

又根据$\theta_p(x) \geqslant \theta_p(\alpha, \beta)$，于是必然有$\min \theta_p(x^\star) = \max \theta_p(\alpha^\star, \beta^\star) = L(x^\star, \alpha^\star, \beta^\star)$。

正定核

设$K:X \times X \rightarrow R$是对称函数，则$K(x,z)$为正定核函数的充分必要条件是对任意的$x_i \in X$，$K(x,z)$对应的$Gram$矩阵：

$$
K = [K(x_i, x_j)]
$$

是半正定的。首先证明必要性：

$$
\begin{align}
\sum c_i c_j K(x_i, x_j) & = \sum c_i c_j ( \phi(x_i) · \phi(x_j)) \\
& = \left ( \sum c_i \phi(x_i) \right ) · \left ( \sum c_i \phi(x_i) \right ) \\
& = \left \| \sum c_i \phi(x_i) \right \|^2 \\
& \geqslant 0
\end{align}
$$

充分性的证明比较麻烦，首先构造映射：

$$
\phi : x \rightarrow K(·,x)
$$

对任意的$x_i \in X, \alpha_i \in R$，定义线性组合：

$$
f(·) = \sum \alpha_i K(·,x_i)
$$

由线性组合组成的集合$S$对加法和数乘都是封闭的。接着在该空间上定义内积，对于线性组合：

$$
f(·) = \sum \alpha_i K(·,x_i) \\
g(·) = \sum \beta_j K(·,z_j)
$$

它们的内积为：

$$
f * g = \sum_i \sum_j \alpha_i \beta_j K(x_i, z_j)
$$

可证明该计算满足：

$$
\begin{cases}
& (cf) * g = c(f*g) \\
& (f+g)*h = f*h + g*h \\
& f*g = g*f \\
& f*f \geqslant 0 \\
& f*f = 0 \Leftrightarrow f = 0
\end{cases}
$$

最后将$S$完备化成希尔伯特空间。

序列最小最优化算法

直接训练相当慢，SMO算法的思路是循环优化，迭代步骤为：

选择两个变量（固定其他变量）
将原问题变为针对这两个变量的凸二次优化问题并求解

假设固定的变量是$\alpha_1$、$\alpha_2$，则问题变为（求解好像比较简单）：

$$
\begin{align}
\min_{\alpha_1,\alpha_2} \quad W(\alpha_1,\alpha_2) & = \frac{1}{2} K_{11}\alpha_1^2 + \frac{1}{2} K_{22}\alpha_2^2 + y_1y_2K_{12}\alpha_1\alpha_2 \\
& - (\alpha_1+\alpha_2) + y_1 \alpha_1 \sum_{i=3} y_i \alpha_i K_{i1} + y_2 \alpha_2 \sum_{i=3} y_i \alpha_i K_{i1} \\
st. \quad & \alpha_1y_1 + \alpha_2y_2 = - \sum_{i=3}y_i\alpha_i \\
& 0 \leqslant \alpha_1, \alpha_2 \leqslant C
\end{align}
$$

选择第一个变量的策略是：

违反KKT条件最严重的样本点。

而第二个变量则尽量选取能优化较多的变量。

工具

大部分人应该会选择用LIBSVM，附SKLEARN的例子：

import numpy as np

from sklearn.svm import SVC

X = np.array([[-1, -1], [-2, -1], [1, 1], [2, 1]])

y = np.array([1, 1, 2, 2])

clf = SVC()

clf.fit(X, y)

print(clf.predict([[-0.8, -1]]))

参考

[ 技术文章推荐 ]