线性可分支持向量机与软间隔最大化

作者: shenghaishxt | 来源:发表于2019-03-04 19:24 被阅读0次

本文来自我的个人博客 http://www.zhangshenghai.com/posts/35913/

线性支持向量机

线性支持向量机包含线性可分支持向量机和线性不可分支持向量机。

通常情况下，训练数据中有一些特异点，线性不可分意味着这些特异点 $(x_i, y_i)$ 不能满足函数间隔大于等于1的约束条件。为了解决这个问题，对每个样本点引进一个松弛变量 $\xi_i \geq 0$ ，使得函数间隔加上松弛变量大于等于1，约束条件变为：
$y_{i} \left( w \cdot x_{i} + b \right) \geq 1 - \xi_{i}$
同时，对每个松弛变量 $\xi_i$ 都支付一个代价 $\xi_i$ ，目标函数就由原来的 $\frac12 ||w||^2$ 变成
$\dfrac{1}{2} \| w \|^{2} + C \sum_{i=1}^{N} \xi_{i}$
其中 $C>0$ 为惩罚参数。

目标函数有两层含义:

使 $\frac12 ||w||^2$ 尽量小即间隔尽量大
使误分类点的个数尽量小

这样就将线性不可分的支持向量机的学习问题变成如下凸二次规划问题：
$\begin{align*} \\ & \min_{w,b,\xi} \quad \dfrac{1}{2} \| w \|^{2} + C \sum_{i=1}^{N} \xi_{i} \\ & s.t. \quad y_{i} \left( w \cdot x_{i} + b \right) \geq 1 - \xi_{i} \\ & \xi_{i} \geq 0, \quad i=1,2, \cdots, N \end{align*}$
学习得到分离超平面为：
$\begin{align*} \\& w^{*} \cdot x + b^{*} = 0 \end{align*}$
以及相应的分类决策函数：
$\begin{align*} \\& f \left( x \right) = sign \left( w^{*} \cdot x + b^{*} \right) \end{align*}$
称为线性支持向量机。

学习的对偶算法

构建拉格朗日函数

引入拉格朗日乘子 $\alpha_{i} \geq 0, \mu_{i} \geq 0, i = 1, 2, \cdots, N$ 构建拉格朗日函数：
$\begin{align*} \\ & L \left( w, b, \xi, \alpha, \mu \right) = \dfrac{1}{2} \| w \|^{2} + C \sum_{i=1}^{N} \xi_{i} + \sum_{i=1}^{N} \alpha_{i} \left[- y_{i} \left( w \cdot x_{i} + b \right) + 1 - \xi_{i} \right] + \sum_{i=1}^{N} \mu_{i} \left( -\xi_{i} \right) \\ & = \dfrac{1}{2} \| w \|^{2} + C \sum_{i=1}^{N} \xi_{i} - \sum_{i=1}^{N} \alpha_{i} \left[ y_{i} \left( w \cdot x_{i} + b \right) -1 + \xi_{i} \right] - \sum_{i=1}^{N} \mu_{i} \xi_{i} \end{align*}$
其中， $\alpha = \left( \alpha_{1}, \alpha_{2}, \cdots, \alpha_{N} \right)^{T}$ 以及 $\mu = \left( \mu_{1}, \mu_{2}, \cdots, \mu_{N} \right)^{T}$ 为拉格朗日乘子向量。

求极小

对偶问题是拉格朗日函数的极大极小问题，首先求 $\min_{w,b}L \left( w, b, \xi, \alpha, \mu \right)$ ：
$\begin{align*} \\ & \nabla_{w} L \left( w, b, \xi, \alpha, \mu \right) = w - \sum_{i=1}^{N} \alpha_{i} y_{i} x_{i} = 0 \\ & \nabla_{b} L \left( w, b, \xi, \alpha, \mu \right) = -\sum_{i=1}^{N} \alpha_{i} y_{i} = 0 \\ & \nabla_{\xi_{i}} L \left( w, b, \xi, \alpha, \mu \right) = C - \alpha_{i} - \mu_{i} = 0 \end{align*}$
得
$\begin{align*} \\ & w ＝ \sum_{i=1}^{N} \alpha_{i} y_{i} x_{i} \\ & \sum_{i=1}^{N} \alpha_{i} y_{i} = 0 \\ & C - \alpha_{i} - \mu_{i} = 0\end{align*}$
代入拉格朗日函数，得
$\begin{align*} \\ & L \left( w, b, \xi, \alpha, \mu \right) = \dfrac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j} \left( x_{i} \cdot x_{j} \right) + C \sum_{i=1}^{N} \xi_{i} - \sum_{i=1}^{N} \alpha_{i} y_{i} \left[ \left( \sum_{j=1}^{N} \alpha_{j} y_{j} x_{j} \right) \cdot x_{i} + b \right] \\ & \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad + \sum_{i=1}^{N} \alpha_{i} - \sum_{i=1}^{N} \alpha_{i} \xi_{i} - \sum_{i}^{N} \mu_{i} \xi_{i} \\ & = - \dfrac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j} \left( x_{i} \cdot x_{j} \right) - \sum_{i=1}^{N} \alpha_{i} y_{i} b + \sum_{i=1}^{N} \alpha_{i} + \sum_{i=1}^{N} \xi_{i} \left( C - \alpha_{i} - \mu_{i} \right) \\ & = - \dfrac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j} \left( x_{i} \cdot x_{j} \right) + \sum_{i=1}^{N} \alpha_{i} \end{align*}$

求极大

求 $\max_{\alpha} \min_{w,b, \xi}L \left( w, b, \xi, \alpha, \mu \right)$ ：

$\begin{align} \\ & \max_{\alpha} - \dfrac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j} \left( x_{i} \cdot x_{j} \right) + \sum_{i=1}^{N} \alpha_{i} \\ & s.t. \sum_{i=1}^{N} \alpha_{i} y_{i} = 0 \\ & C - \alpha_{i} - \mu_{i} = 0 \\ & \alpha_{i} \geq 0 \\ & \mu_{i} \geq 0, \quad i=1,2, \cdots, N \end{align}$

等价于
$\begin{align*} \\ & \min_{\alpha} \dfrac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j} \left( x_{i} \cdot x_{j} \right) - \sum_{i=1}^{N} \alpha_{i} \\ & s.t. \sum_{i=1}^{N} \alpha_{i} y_{i} = 0 \\ & 0 \leq \alpha_{i} \leq C , \quad i=1,2, \cdots, N \end{align*}$
于是，可以通过求解此对偶问题而得到原始问题的解，进而确定分离超平面和决策函数。

线性可分支持向量机学习算法

输入：线性可分训练数据集

线性可分训练数据集 $T={(x_1, y_1), (x_2, y_2),...,(x_N, y_N)}$ ，其中 $x_i \in R^n$ ， $y_i \in \{-1, 1\}$ ， $i=1,2,...,N$ 。

输出：分离超平面和分类决策函数

选择惩罚参数 $C \geq 0$ ，构早并求解凸二次规划问题
$\begin{align*} \\ & \min_{\alpha} \dfrac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j} \left( x_{i} \cdot x_{j} \right) - \sum_{i=1}^{N} \alpha_{i} \\ & s.t. \sum_{i=1}^{N} \alpha_{i} y_{i} = 0 \\ & 0 \leq \alpha_{i} \leq C , \quad i=1,2, \cdots, N \end{align*}$
求得最优解 $\alpha^{\star} = \left( \alpha_{1}^{\star}, \alpha_{1}^{\star}, \cdots, \alpha_{N}^{\star} \right)$
计算
$\begin{align*} \\ & w^{*} = \sum_{i=1}^{N} \alpha_{i}^{*} y_{i} x_{i} \end{align*}$
并选择 $\alpha^{\star}$ 的一个分量 $0 < \alpha_{j}^{\star} < C$ ，计算
$\begin{align*} \\ & b^{*} = y_{j} - \sum_{i=1}^{N} \alpha_{i}^{*} y_{i} \left( x_{i} \cdot x_{j} \right) \end{align*}$
求得分离超平面
$\begin{align*} \\ & w^{*} \cdot x + b^{*} = 0 \end{align*}$
以及分类决策函数
$\begin{align*} \\& f \left( x \right) = sign \left( w^{*} \cdot x + b^{*} \right) \end{align*}$

支持向量

实例 $x_i$ 的几何间隔为：
$\begin{align*} \\& \gamma_{i} = \dfrac{y_{i} \left( w \cdot x_{i} + b \right)}{ \| w \|} = \dfrac{| 1 - \xi_{i} |}{\| w \|} \end{align*}$
则实例 $x_i$ 到间隔边界的距离为：
$\begin{align*} \\& \left| \gamma_{i} - \dfrac{1}{\| w \|} \right| = \left| \dfrac{| 1 - \xi_{i} |}{\| w \|} - \dfrac{1}{\| w \|} \right| \\ & = \dfrac{\xi_{i}}{\| w \|}\end{align*}$
对于每一个 $\xi_i \geq 0$ ，有：
$\begin{align*} \xi_{i} \geq 0 \Leftrightarrow \left\{ \begin{aligned} \ & \xi_{i}=0,\quad x_{i}在间隔边界上; \\ & 0 < \xi_{i} < 1, \quad x_{i}在间隔边界与分离超平面之间; \\ & \xi_{i}=1, \quad x_{i}在分离超平面上; \\ & \xi_{i}>1, \quad x_{i}在分离超平面误分类一侧; \end{aligned} \right.\end{align*}$

合页损失函数

线性支持向量机学习还有另外一种解释，就是最小化以下目标函数：
$\sum_{i=1}^N \left[ 1 - y \left(w \cdot x + b \right) \right]_{+} + \lambda||w||^2$
线性支持向量机（软间隔）的合页损失函数为：
$\begin{align*} \\& L \left( y \left( w \cdot x + b \right) \right) = \left[ 1 - y \left(w \cdot x + b \right) \right]_{+} \end{align*}$
其中，“+”为取正函数：
$\begin{align*} \left[ z \right]_{+} = \left\{ \begin{aligned} \ & z,\quad z > 0 \\ & 0, \quad z \leq 0 \end{aligned} \right.\end{align*}$

线性可分支持向量机与软间隔最大化

线性支持向量机

学习的对偶算法

构建拉格朗日函数

求极小

求极大

线性可分支持向量机学习算法

输入：线性可分训练数据集

输出：分离超平面和分类决策函数

支持向量

合页损失函数

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读