手推SVM

发表于 分类于 评论数： 本文字数： 869

间隔；对偶；核技巧；

手推SVM；

整里SVM相关问题；

Large-Margin Linear Classification

最大间隔线性分类器

决策函数为 $f(x) = sign(\omega^{}x+b^{})$

推导过程因为本人写字习惯斜着，所以比较乱。对此表示抱歉。附录里会放一张整体的推导过程图片，比较清晰。

整体推导图

0x01 间隔

1-1 硬间隔

基本硬间隔的优化表示

image-20210304160908917

展开

image-20210304165031720

将后边部分缩放为1，再经过变形之后得到：

image-20210304165205054

整理一下，原问题为：

image-20210304165231998

带约束的不好优化，所以引入拉格朗日乘子

image-20210304165354347

原问题就没有了w,b的约束，再因为原问题具有强对偶性，求解原问题等价于求解对偶问题，所以转化为对偶问题

image-20210304165607819

下一步，利用凸优化的特性求解最小化的拉格朗如对偶问题

image-20210304165740781

得到

image-20210304165753233

最后结合KKT条件解除最终解

image-20210304165852279

1-2 软间隔

由于很多情况下数据集中存在噪声等情况，无法求解到最终解，所以引入了含有噪声的优化函数。

image-20210304170526706

  • Quadratic Programming 二次规划问题

  • SVM的分类结果只与支持向量有关，除了支持向量以外，其他的系数均为0. 这也是SVM高效的原因。

0x02 拉格朗日对偶性

目的在于不求解带有约束的原问题，通过引入拉格朗日乘子的方式来直接求解。第一节中已经说明，从label处开始。

0x03 核技巧

把输入数据映射到一个新的(更高维)的特征空间，本质思想类似于加入非线性

具体实现在于将原公式中的内积替换成核函数

image-20210303171620564

RBF

image-20210303174002791

0x04 SMO 序列最小化优化

QP问题最坏时间复杂度为$O(N_{3})$，我们要做的就是利用优化算法尽量避免最坏时间复杂度。

将原N的参数的问题分解为2个2个的子问题，直到全部满足KKT条件为止。

因为子问题存在解析解，所以就算子问题很多，整体上也是加速效果。

image-20210303180740172

合页损失，随机SVM

合页损失 hinge loss，看起来比较像relu，$max{0, 1-y_{i}(\omega·x+b)}$

image-20210303191721173image-20210303191729994image-20210303191738649

image-20210303191801718

最后这一部分比较乱，大体理解SMO思想即可。

参考资料

  1. 猫都能看懂的SVM【从概念理解、优化方法到代码实现】
  2. 机器学习-白板推导系列(六)-支持向量机SVM（Support Vector Machine）

附录

整体推导过程

image-20210304170727875