算法理论——Linear SVM
2024-08-28 21:41:05
问题引入
下面的三个超平面都起到分类的效果,哪个最好?
答案显然是第三个。为什么?
直觉上,如果现在我们有个测试点,非常靠近右下角的那个红叉叉,也就是说这个点的特征与那个红叉叉非常接近,这时候,我们希望我们的分类器能够将这个测试点划分为与红叉叉相同的类。
也就是说,我们希望,找到的超平面能够远离所有的点,也就是要最小化超平面到离它最近的那个点的距离。
于是,用公式表达就是:
第一行是我们要求的东西,最大margin(margin的定义在第二个约束条件给出)的分割超平面。实质上我们要求的是使得margin最大的W。
第二行约束了超平面要把所有样本正确分类
第三行约束了margin的定义,就是离超平面最近的点的距离。
注意:这里的W是包含了w0, 即:W=(w0, w1, w2, ... , wd)T。 同理Xn=(1, x1, x2, ... , xd)T
如何求这个最大值?
现在问题变成求:
接下来,
现在吧约束条件中的min想办法去掉:
所以问题描述变成:
认真观察会发现,我们的问题现在属于二次规划问题(quadratic programming)。
二次规划标准形式:
其中,Q为二次项系数对角矩阵,p为一次项系数向量,A为约束条件中M个一次向系数向量amT组成的矩阵,C为M个cm组成的向量。输入这4个参数,就可以通过QP的工具得到u的最佳解。
把我们的问题写成二次规划的形式:
我们的输入参数为:
这样就能够求到(b,W)的最优解了。
什么是hard-margin?
就是能够完全分割数据集的胖胖的边界
什么是support vector?
就是控制超平面和margin的那几个最近的点,除了这些点,其他的点没有了,并不影响超平面和margin
最新文章
- ASP.NET MVC5 网站开发实践(二) Member区域 - 添加文章
- 图像映射map
- django基于正则的url匹配
- 黄聪:wordpress伪静态的原理
- STL&;quot;源码&;quot;剖析-重点知识总结
- Java 去除HTML标签转化成纯文本
- libjingle开发人员指南
- 【分享】我们用了不到200行代码实现的文件日志系统,极佳的IO性能和高并发支持,附压力测试数据
- &;,^,|,的简化计算与理解
- 《JavaScript设计模式与开发实践》笔记第一章
- list遍历时删除的坑
- Vue项目分环境打包的实现步骤
- vue之——从彩笔的进步之路
- URAL 1099 Work Scheduling (一般图最大匹配) 模板题【带花树】
- 5款最好的免费在线网站CSS验证器
- 【APP测试(Android)】--升级更新
- C# 常用验证
- 【luogu4320】道路相遇 (圆方树 + LCA)
- js-权威指南学习笔记20
- 第二阶段Sprint8