从负一开始推导SVM

作者: pipicold | 来源:发表于2019-02-14 13:58 被阅读0次

从负一开始推导SVM
2018-05-14
SVM推导
推导svm
SVM推导过程 - 草稿
SVM面试级推导
超详细白板推导：从模型和优化 2 个角度详解 SVM 核函数
机器学习小组第十周打卡
2019-01-25
SVM推导步骤

0 解析几何知识, 点到平面的距离

参考材料

image.png

如图, 假设一个平面 $N: Ax+By+Cz+D = 0$ , 平面外一点 $P(x_P, y_P, z_P)$ , $P$ 在平面上的投影为 $P'$ , 求点 $P$ 到平面的距离即求 $\overline{PP'}$

我们可以知道平面 $N$ 的法向量为 $\vec N = (A, B, C)$ , 则这个法向量对应的单位向量

$\vec n = \frac{\vec N}{|\vec N|} = \frac{\vec N}{\sqrt{A^2+B^2+C^2}} \ \ \ \ \ \ (0.1)$

假设平面上任意一点 $Q(x_Q, y_Q, z_Q)$ , 则 $Q$ 满足

$Ax_Q + Bx_Q + Cx_Q + D = 0 \ \ \ \ \ \ (0.2)$

点 $P$ 到点 $Q$ 构成的向量 $\vec{PQ} = (x_P - x_Q, y_P- y_Q, z_P-z_Q)$

所以 $\overline{PP'}$ 即为 $\vec{PQ}$ 在法向量 $\vec N$ 方向上的投影, 即与单位法向量 $\vec n$ 的点乘的结果.(这里取了个绝对值, 因为距离只能为正, 避免了向量方向问题的干扰)

$\overline{PP'} = |\vec{PQ} \cdot \vec n|=|\frac{(x_P - x_Q, y_P- y_Q, z_P-z_Q) \cdot \vec N}{\sqrt{A^2+B^2+C^2}}|$

$\overline{PP'} =\frac{|(x_P - x_Q, y_P- y_Q, z_P-z_Q) \cdot (A,B,C)|}{\sqrt{A^2+B^2+C^2}}$

$\overline{PP'} =\frac{|A(x_P - x_Q)+B( y_P- y_Q)+C( z_P-z_Q)|}{\sqrt{A^2+B^2+C^2}} \ \ \ \ \ \ (0.3)$

其中与 $Q$ 点相关的变量 $x_Q, y_Q, z_Q$ 都可以用式 $(0.2)$ 替换

所以合并式 $(0.2), (0.3)$ 可得:

$\overline{PP'} =\frac{|Ax_P +By_P+Cz_P +D|}{\sqrt{A^2+B^2+C^2}} \ \ \ \ \ \ (0.4)$

如果用矩阵来表示, 则我们取

$\omega = \begin{bmatrix}A \\B \\C \end{bmatrix}, x_P = \begin{bmatrix}x_P \\y_P \\z_P \end{bmatrix}, b = D$

则式(0.4)可以写为

$\overline{PP'} =\frac{|\omega^Tx_P +b|}{||\omega||}$

$||\omega||$ 即为L2范式(L2 norm), 就是平方和之后开根号

1 SVM基本问题描述和解决思路

基本问题:

假设有两个类别的数据, $(x_i, y_i)$

其中 $y_i = \begin{cases} +1 \\-1 \end{cases}$

我们试图找到一个分隔平面(超平面) $\omega^Tx+b = 0$ (这里就是 $Ax+By+Cz+D = 0$ 的一个变体)

使得

离分隔平面 $\omega$ 最近的点到分隔平面 $\omega$ 的距离最大
所有点都能被正确分类

目标1: 距离最大

根据之前的预备知识, 我们知道任意一点 $P$ 到平面的距离为(李航的书说是"几何距离")

$r = \frac{|\omega^Tx_P+b|}{||\omega||}$

我们要求分隔平面两边的点都满足条件2: 距离分隔平面的距离最大

所以我们的求解目标是

$\max \min \frac{2}{||\omega||}|\omega^Tx_P+b|$

目标2: 正确分类

同时我们希望能满足条件1, 即所有点能被正确分类

$y_i(\omega^T x+b) > 0$

因为

如果是正确分类的话, 所有类别为+1 的点都会在平面的上方, 类别为-1 的点都会在平面的下方.
在平面上方的点满足 $(\omega^T x+b) > 0$ , 在平面下方的点满足 $(\omega^T x+b) < 0$
所以如果能正确分类就有: $y_i(\omega^T x+b) > 0$

SVM的求解问题的数学表达

$\max_{w,b} \min_i \frac{2}{||\omega||}|\omega^Tx_i+b| \\ s.t.\ y_i(\omega^T x+b) > 0 \ \ \ \ \ \ \ (1.1)$

翻译一下:

找到距离平面最近的一个点, 其距离: $\min_i \frac{1}{||\omega||}|\omega^Tx_i+b|$
把这个距离乘以2, 就是间隔了: $\min_i \frac{2}{||\omega||}|\omega^Tx_i+b|$
把分隔平面挪动翻转一下, 看看是不是能扩大这个间隔: $\max_{w,b} \min_i \frac{2}{||\omega||}|\omega^Tx_i+b|$

求解目标: $\omega, b$

2 如何简化这个问题: 转换为凸二次规划问题

通过把原问题构建成凸二次规划问题来进行求解, 因为凸二次规划可解

凸二次规划问题:

目标函数是凸二次函数: $\min_u \frac{1}{2}u^TQu + t^Tu$ (关于 $u$ 的二次函数)
约束是线性约束: $s.t\ c_i^Tu \geq d_i, i = 1, 2,3,...,m$

现在我们的目标就是, 把原问题凑成凸二次规划问题

目标函数的变换

原问题的目标函数为:

$\max_{w,b} \min_i \frac{2}{||\omega||}|\omega^Tx_i+b|$

变换思路

因为求解目标是 $\omega, b$ , 所以 $\min_i$ 这一项(即变量 $i$ )要想办法忽略掉
目标函数为一个二次函数, 原函数里面其实隐含了一个二次函数: $\frac{1}{||\omega||} = \frac{1}{\sqrt{\omega^T\omega}}$
所以 $|\omega^Tx_i + b|$ 这一项有点没有用, 我们需要想办法忽略它

工具:

我们发现一个事实, 如果把 $\omega, b$ 等比例放大/缩小, 式(1.1)描述的问题不变:
证明
假设一个系数 $r>0$ , 使得 $\omega, b$ 放大为 $r\omega, rb$ ,
则式(1.1)变为:
$\max_{w,b} \min_i \frac{2}{||r\omega||}|r\omega^Tx_i+rb| \\ s.t.\ y_i(r\omega^T x+rb) > 0$
其中目标函数 $\max_{w,b} \min_i \frac{2}{||r\omega||}|r\omega^Tx_i+rb| = \max_{w,b} \min_i \frac{2}{||\omega||}|\omega^Tx_i+b|$ (分母分子同乘一个r, 抵消了)
约束目标 $y_i(r\omega^T x+rb) > 0 \Leftrightarrow y_i(\omega^T x+b) > 0$ (不等式两边同除一个正数, 不等式仍然成立)
这个 $|\omega^Tx_i+b|$ 就是PQ和平面法向量 $\omega$ 点乘的结果，这个结果要除以法向量的模长才是几何间隔(我们的问题要求几何间隔满足一定条件)。所以如果我们只是变换法向量的长度的话，因为无论如何都会除以法向量长度，所以对于原问题并没有任何影响(式(1.1)描述的问题不变)。

变换过程

目标函数的变换

我们假设所有的 $\omega,b$ 都乘上一个系数r，我们证明了乘上这个系数与否不影响问题的描述
于是我们总能找到一个 $r^*$ ，使得 $\min_i |r^*\omega^Tx_i+r^*b|=1$ , 这样的话原问题的目标函数可以写为 $\max_{\omega, b}\frac{2}{||r^*\omega||}$
我之前一直迷惑于这个 $r^*$ 怎么处理的，后来想起来系数和问题的求解无关，因为这是个凸二次函数嘛，想想抛物线的形状，无论系数怎么改变抛物线最低点的值都会出现在固定的位置(系数和开口大小相关)，所以可以直接忽略系数: 求解 $\max_{\omega, b}\frac{2}{||r^*\omega||}$ 等价于求解 $\max_{\omega, b}\frac{1}{||\omega||}$
$\max_{\omega, b}\frac{1}{||\omega||} \Leftrightarrow \min_{\omega, b}||\omega|| \Leftrightarrow \min_{\omega, b} \omega^T\omega \Leftrightarrow \min_{\omega, b} \frac{1}{2}\omega^T\omega$
到这一步, 我们的目标函数变化过程为: $\max_{w,b} \min_i \frac{2}{||\omega||}|\omega^Tx_i+b| = \max_{w,b} \min_i \frac{2}{||r\omega||}|r\omega^Tx_i+rb| = \max_{w,b} \min_i \frac{2}{||r^*\omega||}|r^*\omega^Tx_i+r^*b|$
$= \max_{\omega, b}\frac{2}{||r^*\omega||} = \max_{\omega, b}\frac{1}{||\omega||} \Leftrightarrow \min_{\omega, b} \frac{1}{2}\omega^T\omega$

约束条件的变换

接下来看约束条件的变化, 原问题的约束条件为: $y_i(\omega^T x+b) > 0$ , 由于之前对于 $\omega, b$ 的变换引入了一个新的约束条件: $\min_i |r^*\omega^Tx_i+r^*b|=1$
$\min_i |r^*\omega^Tx_i+r^*b|=1$ , 我们可以视为 $\min_i |\omega'^Tx_i+b'|=1, (\omega' = r^*\omega, b' = r^*b)$ , 在这里, $r^*$ 的作用是对 $\omega, b$ 施加限制, 所以我们可以换个思路, 直接对 $\omega, b$ 施加限制: $\min_i |\omega^Tx_i+b|=1$ , 等价于 $|\omega^Tx_i+b| \geq 1$
所以新的约束条件为: $y_i(\omega^T x+b) > 0$ 且 $|\omega^Tx_i+b| \geq 1$ , 因为 $y_i(\omega^T x+b) > 0$ 的原因, 所以 $|\omega^Tx_i+b| = y_i(\omega^T x+b)$ (分类正确的条件下, 这两个式子都能保证>0(分类正确意味着点不能再分隔平面上, 所以绝对值也不可能等于0)), 所以这两个约束条件可以合并为一个: $y_i(\omega^T x+b) \geq 1$

变换过程的公式推导

原问题为:

$\max_{w,b} \min_i \frac{2}{||\omega||}|\omega^Tx_i+b| \\ s.t.\ y_i(\omega^T x+b) > 0$

找到个系数 $r^*$ 使得 $\min_i |r^*\omega^Tx_i+r^*b|=1$ ,(注意现在 $r^*$ 也是目标函数之一了)

$\max_{w,b} \min_i \frac{2}{||r^*\omega||}|r^*\omega^Tx_i+r^*b|, \\ r* \\ \ \\s.t \ \min_i |r^*\omega^Tx_i+r^*b|=1\\ s.t.\ y_i(\omega^T x+b) > 0$

化简目标函数, 凑二次函数:

$\max_{\omega, b}\frac{2}{||r^*\omega||} = \max_{\omega, b}\frac{1}{||\omega||} \Leftrightarrow \min_{\omega, b} \frac{1}{2}\omega^T\omega$

于是现在的问题为:

$\min_{\omega, b} \frac{1}{2}\omega^T\omega, \\ r* \\ \ \\s.t \ \min_i |r^*\omega^Tx_i+r^*b|=1\\ s.t.\ y_i(\omega^T x+b) > 0$

转换约束条件, 把关于 $r^*$ 的约束条件转变成只与 $\omega, b$ 相关(目标函数中的 $r^*$ 也没了)

$\min_{\omega, b} \frac{1}{2}\omega^T\omega,\\s.t \ \min_i |\omega^Tx_i+b|=1\\ s.t.\ y_i(\omega^T x+b) > 0$

继续转换, 并合并两个约束条件

$\min_{\omega, b} \frac{1}{2}\omega^T\omega\\ s.t.\ y_i(\omega^T x+b) \geq 1$

(这段变换其实是我整个SVM里面一开始最不能理解的地方, 我找到的教材都只是说了一句: 因为缩放并不影响原问题, 所以我们就能得出 $\min_i |\omega^Tx_i+b|=1$ , 之类的解释(包括<统计学习方法>也是类似的跳跃式证明). 我数学太渣真的无法自己就这样接受这么跳跃的证明, 于是想了好久才想出了一个可以自己接受的证明方法. 不确保一定正确, 希望有人能指出错误)

3 通过构造一个新函数, 合成目标函数和约束: 拉格朗日函数

在利用二次凸优化构建了一个新的等价问题之后, 如何解? 现在的思路是把目标函数和约束合成为一个式子, 通过求新式子的最值, 便是原问题的最值

这个方法称为: 拉格朗日函数

拉格朗日函数求解的条件

如果一个带约束优化问题有诸如一下的形式:
$\min_u f(u) \\ s. t.\ g_i(u) \leq 0, \\ s.t.\ h_i(u) = 0 \\ i=1,2,3,....$
并且 $f(u)$ 连续可微

则可以将原问题转换为一下新问题

$\min_u \max_{\alpha, \beta} L(u, \alpha, \beta ) = f(u) + \sum_{i=1}^m \alpha_ig_i(u) + \sum_{j=1}^n\beta_jh_j(u)\\ s.t \ \alpha_i \geq 0$

能进行这样转换的原因

为了能证明新得到的拉格朗日函数是原问题的变形(即拉格朗日函数能变回原问题), 我们最好把 $\min_u \max_{\alpha, \beta} L(u, \alpha, \beta ) = f(u) + \sum_{i=1}^m \alpha_ig_i(u) + \sum_{j=1}^n\beta_jh_j(u)$ 和原问题中的约束条件 $g_i(u) \leq 0, h_i(u) = 0$ 放在一起看,

并且时刻记住: 因为求的是 $\min_u \max_{\alpha, \beta} L(u, \alpha, \beta )$ , 所以 $L(u, \alpha, \beta )$ 对 $\alpha, \beta$ 有最大值, 对 $u$ 有最小值

于是我们有如下的假设:

如果 $g_i(u)$ 不满足条件, 即 $g_i(u) > 0$ : $\max_{\alpha, \beta} L(u, \alpha, \beta )$ 中的 $\alpha_ig_i(u)$ 这一项, 最大值为 $+\infty$ , 导致 $\max_{\alpha, \beta} L(u, \alpha, \beta ) = +\infty$ , 无解.
如果 $g_i(u)$ 满足条件, 即 $g_i(u) \leq 0$ : $\max_{\alpha, \beta} L(u, \alpha, \beta )$ 中的 $\alpha_ig_i(u)$ 这一项, 因为 $\alpha_i \geq 0$ , 所以最大值为 $0$ (正数 $\alpha_i$ 乘以负数 $g_i(u)$ 结果仍为负数), 有可能有解
如果 $h_j(u)$ 不满足条件, 即 $h_j(u) \neq 0$ : $\max_{\alpha, \beta} L(u, \alpha, \beta )$ 中的 $\beta_jh_j(u)$ 这一项, 因为 $\beta_j$ 并没有约束条件约束, 所以可以取任意值, 即 $\max_{\beta} \beta_jh_j(u) = +\infty$ , 导致 $\max_{\alpha, \beta} L(u, \alpha, \beta ) = +\infty$ , 无解.
如果 $h_j(u)$ 满足条件, 即 $h_j(u) = 0$ : 则 $\beta_jh_j(u) =0$ , $\max_{\alpha, \beta} L(u, \alpha, \beta )$ 可能有解

我们可以组合假设2和假设4, 即:

如果 $g_i(u)$ 满足 $g_i(u) \leq 0$ , 且 $h_j(u)$ 满足 $h_j(u) = 0$ , 则 $\max_{\alpha, \beta} L(u, \alpha, \beta ) = f(u)+0+0=f(u)$

所以此时 $\min_u \max_{\alpha, \beta} L(u, \alpha, \beta ) =\min_u f(u)$ , 朗格朗日函数变换回原问题

把凸二次函数问题转换成拉格朗日函数

$u$ 替换为 $\omega, b$ 所以有: $\min_u f(u) \Rightarrow \min_{\omega,b} f(\omega, b)$
$\min_{\omega,b} f(\omega, b)$ 替换为 $\min_{\omega, b} \frac{1}{2}\omega^T\omega$
$g_i(u) \leq 0$ 替换为 $1-y_i(\omega^T x+b) \leq 0$ : 把原约束的左边移到了右边而已
因为原凸二次函数问题中没有类似 $h_j(u) = 0$ 的约束, 所以直接忽略 $\beta_jh_j(u)$ 这一项
原凸二次函数问题变为:
$\min_{\omega, b} \max_{\alpha} L(\omega, b, \alpha) = \min_{\omega, b} \max_{\alpha} \frac{1}{2}\omega^T\omega+\sum_{i=1}^m \alpha_i(1-y_i(\omega^T x+b) )$

4 通过对偶问题解拉格朗日函数

为什么要转成对偶问题:

求解拉格朗日函数的极值的, 由于求极值的运算是从内向外的. 每次运算需要先算 $\max_{\alpha}$ , 而这个 $\alpha_i$ 作为新引入的变量, 只能通过计算所有值来找到最值.

而每次求得一个新的 $\alpha_i$ , 我们就要求一次 $\omega, b$ 的最值, 所以这样非常耗时麻烦

但是如果能先求 $\omega, b$ , 每次找到一个新的 $\alpha_i$ 后就不用再计算了.

对偶问题的转换

只要原问题满足KKT+Slater条件, 我们便可以交换求最大值和最小值的顺序:

$\min_{\omega, b} \max_{\alpha} L(\omega, b, \alpha) \overset{满足KKT+Slater条件}{\Longrightarrow} \max_{\alpha} \min_{\omega, b} L(\omega, b, \alpha)$

KKT条件

主问题可行: $g_i(u) \leq 0, h_i(u)=0$
对偶问题可行: $\alpha_i \geq 0$
互补松弛: $\alpha_ig_i(u) = 0$
(统计学习方法上面的条件)最优解处对 $\omega,b$ 偏导是0: $\nabla_{\omega, b} L(\omega^*, b^*, \alpha^*)=0$

Slater条件

当主问题为凸优化问题, 即 $f(u)$ 和 $g_i(u)$ 为凸函数, $h_j(u)$ 为仿射函数, 且可行域中至少有一点使不等式约束严格成立时, 对偶问题等价于原问题.

对偶问题的证明

原问题为 $\min_{\omega, b} \max_{\alpha} L(\omega, b, \alpha)$ , 对偶问题为 $\max_{\alpha} \min_{\omega, b} L(\omega, b, \alpha)$ , <统计学习方法>写的证明终于理解了, 这里我做一下注释(也把符号统一为我这里使用的符号):

先假设 $\theta_D(\omega,b) = \min_{\omega,b} L(\omega, b, \alpha)$ ,(D=dual problem对偶问题)

$\theta_P(\alpha) = \max_{\alpha} L(\omega, b, \alpha)$ , (P=prime problem原问题)

所以可知对任意 $\omega, b, \alpha$ 都有 $\theta_D(\omega,b) = \min_{\omega,b} L(\omega, b, \alpha) \leq L(\omega, b, \alpha) \leq \max_{\alpha} L(\omega, b, \alpha)= \theta_P(\alpha)$

因为 $\min_{\omega,b} L(\omega, b, \alpha)$ 是对 $L(\omega, b, \alpha)$ 求最小值, $\max_{\alpha} L(\omega, b, \alpha)$ 是对 $L(\omega, b, \alpha)$ 求最大值, 所以最小值一定小于大于最大值

即对任意 $\omega, b, \alpha$ 都有 $\theta_D(\omega,b) \leq \theta_P(\alpha)$

这里的"任意"很重要, 下一步的证明的基础就是这个"任意"

因为原问题和对偶问题都有最优解, 所以: $\max_{\alpha;\alpha \geq 0} \theta_D(\omega, b) \leq \min_{\omega, b} \theta_P(\alpha)$

因为我们有: 对任意 $\omega, b, \alpha$ 都有 $\theta_D(\omega,b) \leq \theta_P(\alpha)$ , 所以就算取 $\theta_D(\omega,b)$ 的最大值和 $\theta_P(\alpha)$ 的最小值, 仍然要满足 $\theta_D(\omega,b) \leq \theta_P(\alpha)$ , 所以 $\max_{\alpha;\alpha \geq 0} \theta_D(\omega, b) \leq \min_{\omega, b} \theta_P(\alpha)$ 成立

相当于: $\max_{\alpha} \min_{\omega, b} L(\omega, b, \alpha) \leq \min_{\omega, b} \max_{\alpha} L(\omega, b, \alpha)$

求解SVM, 得到最简单的计算式

因为我们之前将原问题简化又简化了, 所以求解就变得很简单.

只要对 $\omega, b$ 分别求偏导, 然后找到偏导等于0的时候, 这时候的极值就是最优解

$\frac{\partial L }{\partial \omega} = 0 \Rightarrow \omega = \sum^{m}_{i=1}\alpha_iy_ix_i$

$\frac{\partial L }{\partial b} = 0 \Rightarrow b= \sum^{m}_{i=1}\alpha_iy_i = 0$

然后带入拉格朗日函数的对偶形式里面:

$\max_{\alpha} \min_{\omega, b} \frac{1}{2}\omega^T\omega+\sum_{i=1}^m \alpha_i(1-y_i(\omega^T x+b) ), \\ s.t.\ a_i \geq 0$

就有

$\min_{\alpha} \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^{m} \alpha_i\alpha_jy_iy_jx_i^Tx_j - \sum_{i=1}^{m}\alpha_i, \\ s.t.\ \sum_{i=1}^{m}a_iy_i = 0, \alpha_i \geq 0$

SVM的最朴素算法(线性可分支持向量机算法)

<统计学习方法>

P106 算法7.2

从负一开始推导SVM
0 解析几何知识, 点到平面的距离参考材料如图, 假设一个平面 , 平面外一点 , 在平面上的投影为, 求点...
2018-05-14
SVM手动推导
SVM推导
SVM推导参考链接。问题分析：给定一个标注的数据集(x_{i},y_{i}), i=1,2,3,4……N，其中...
推导svm
梯度垂直于等高线，指向函数变化最快的方向，指向极大值点方向约束条件为等式求极值先来看个简单求极值例子先看下图...
SVM推导过程 - 草稿
title: SVM推导过程 date: 2019-03-12 08:25:33 tags: [svm, ml] ...
SVM面试级推导
序 SVM是面试中常问的模型之一，本次记录一下应对面试时SVM如何进行较为清晰和简洁的推导 SVM面试级推导（自写...
超详细白板推导：从模型和优化 2 个角度详解 SVM 核函数
在 SVM 白板推导| 由最大间隔化目标演化的损失函数推导过程中白板手推了 SVM 的原理，并介绍了硬间隔核函数...
机器学习小组第十周打卡
学习目标知识点描述：致敬真神：支持向量机学习目标： SVM算法原理及数学推导 SVM算法中的核函数 SVM算法...
2019-01-25
写出 svm 原始问题转换至其对偶问题的数学推导过程： 1 导包： from sklearn import svm...
SVM推导步骤
SVM（Support Vector Machine，支持向量机）是最经典的分类算法，本文主要整理（为了应付考试）...