从负一开始推导SVM

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

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 解析几何知识, 点到平面的距离

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

目标1: 距离最大

目标2: 正确分类

SVM的求解问题的数学表达

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

目标函数的变换

变换思路

工具:

变换过程

目标函数的变换

约束条件的变换

变换过程的公式推导

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

拉格朗日函数求解的条件

能进行这样转换的原因

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

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

对偶问题的转换

KKT条件

Slater条件

对偶问题的证明

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

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

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读