塞进裤子ヾ(≧O≦)〃嗷~

0%

支持向量机 机器学习实战

  • 确定目标函数$min(\frac{||w|}{2})$

  • 因为带有不等式约束,利用拉格朗日乘子转化为拉格朗日目标函数

  • 转换对偶问题

  • 利用SMO算法更新$\alpha$

  • 更新$\alpha$ 后更新b

具体公式推导见笔记本及文档末的推荐网址

代码:

简易SMO

https://github.com/drawStar/Machine-Learning/blob/master/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0%E5%AE%9E%E6%88%98/ch06/svm-smoSimple.py

完整版SMO

mark

对于上述的苹果和香蕉,我们想象为2种水果类型的炸弹。(保证距离最近的炸弹(支持向量),距离它们最远)

确定超平面分类正确(同号即预测正确):

$y_i(W^T x_i + b) > 0 $

$y_i$为标签,值为1或-1

但0~1之间的点依然存在误判的可能性,保证$y_i(W^T x_i + b) >= 1$能更好地降低噪音数据的影响
$y_i(W^T x_i + b)$也叫做函数间隔

但是函数间隔存在一定的问题,上述定义的函数间隔虽然可以表示分类预测的正确性和确信度,但在选择分类 超平面时,只有函数间隔还远远不够,因为如果成比例的改变 w 和 b,虽然此时超 平面没有改变,但函数间隔的值 yf (x) 却变大了。所以,需要将$w$的大小固定,如$||w|| =1$,使得函数间隔固定。这时的间隔也就是几何间隔 。

所以在实际中,我们定义点到超平面的距离时,采用的是几何间隔,定义如下。

$$ y_i (\frac{W^Tx_i+b}{ ||W|| }) $$

mark

我们的最优化问题为

mark

上述问题属于不等式约束的优化问题,根据以下进行优化mark

利用拉格朗日函数,将有约束的原始目标函数转换为无约束的新构造的拉格朗日目标函数

mark

SVM例子参考
https://blog.csdn.net/c406495762/article/details/78072313 推荐

https://www.cnblogs.com/steven-yang/p/5658362.html

https://www.cnblogs.com/wjy-lulu/p/7977952.html

拉格朗日乘子

https://www.cnblogs.com/ooon/p/5721119.html

如何理解拉格朗日乘子法? - 戏言玩家的回答 - 知乎
https://www.zhihu.com/question/38586401/answer/105588901

KKT条件是必要条件

松弛变量

引入松弛变量后,允许某些样本点的函数间隔小于1,即在最大间隔区间里面,或者函数间隔是负数,即样本点在对方的区域中。

C为容忍度因子,可以理解为SVM对“软间隔”的支持度。若C为无穷大,则所有的训练样本均必须满足SVM的约束条件,C值越小就允许越多的样本不满足约束条件。

https://blog.csdn.net/wusecaiyun/article/details/49659183

简化板SMO算法

https://cloud.tencent.com/developer/article/1084673

https://blog.csdn.net/BIT_666/article/details/79879977 推荐

完整版SMO算法

https://zhuanlan.zhihu.com/p/62898859

简化版SMO算法:

检查训练样本中每个点 [公式] 是否满足KKT条件,如果不满足,则它对应的 [公式] 可以被优化,然后随机选择另一个变量 [公式] 进行优化

完整版SMO算法:

简化版的SMO算法在小数据集上没什么问题,但遇到大数据集速度就会变得很慢。完整版的算法与简化版的算法唯一不同的就是 [公式] 的选择。

具体地,先通过一个外循环来选择第一个$\alpha _i$,并且其选择过程会再两种方式之间进行交替:一种方式是在所有数据集上进行单遍扫描,另一种方式则是在非边界$\alpha$中实现单遍扫描。所谓非边界 $\alpha$即那些$0< \alpha < C$的 $\alpha$。对整个数据集扫描很容易,而实现非边界扫描,首先要建立这些的$\alpha$列表,然后再对这个表进行遍历。同时,该步骤会跳过那些已知的不会改变的 $\alpha$值。

在选择第一个$\alpha _i$后,算法会通过一个内循环来选择第二个$\alpha _j$ 。优化过程中会通过最大化步长的方式来获取第二个 $\alpha _j$ 。

每次优化完两个变量以后,都需要重新计算阈值$b$。

1遍历一遍整个数据集,对每个不满足KKT条件的参数,选作第一个待修改参数alpha1

2 内循环选择 |Ei-Ej|最大的作为alpha2

3 整个数据集遍历后,进行非边界遍历大于0小于c的alpha1

4内循环选择 |Ei-Ej|最大的作为alpha2

循环1234直到没更新

注意 这里的边界指的是alpha 的边界,即0和C,而不是决策边界

为什么选择非边界变量的alpha?

答:边界变量倾向于留在边界,而非边界变量倾向于波动,这一步启发式的选择算法是基于节省时间考虑的,

先遍历全集,若全集遍历中未修改任何alpha,说明alpha均满足KKT条件,循环停止; 2. 若全集遍历中修改了alpha值,则在下一轮循环进入边界遍历(边界指0<alpha<C的点,是支持向量); 3. 在边界遍历中,修改边界点的alpha,直到无alpha可修改(此时alphaPairChanged=0),再次进入全集遍历; 4. 如此循环往复,直到全集遍历中未修改任何alpha,循环停止 - 内循环中通过选择相较ai具有最大步长(即Ei-Ej)的aj - 每次修改ai aj后,紧跟着修改Ei Ej

if help:小手一抖点个广告 or 大手一挥资助一下