【TODO】支持向量机学习笔记

？？拉格朗日乘子法
？？Soft Margin的优化

SVM基本思想

SVM用来解决线性不可分问题。
基本思想是，把原始空间映射到高维空间，转化为线性可分问题。


overview

SVM解决线性可分问题

SVM本质上是一个线性分类器，wx+b形成一个超平面。

  1. w在哪？如图3所示，是和超平面垂直的一个向量。证明过程如图3所示。
    线性分类器

  2. 空间中的一个点，到超平面的距离如何计算？原点到超平面的距离？


    到超平面的距离

    如何挑选模型？A和B的训练误差都为0。但是B更好，分割得平均，无偏，有更强的泛化能力。


    image.png

    如何量化B比A好呢？引入margin。如图7所示，B的margin更大。“Support Vectors”就是，恰好在margin上的样本。
    margin

目标函数

定义两个margin超平面分别为：wx+b=1和wx+b=-1。

image.png

共有两个目标：一是，把样本分对；二是，最大化margin。
然后得到目标函数，一个带约束的二次优化问题。
image.png

如何优化？

？？用“拉格朗日乘子法”


拉格朗日乘子法

image.png

image.png

Soft Margin

实际中可能不存在一个解，能把所有训练样本都分对。所以就想出了Soft Margin来解决这个问题。
Soft Margin的基本思想是，允许支持向量机在一些样本上出错。如图15所示，通过修改约束条件，在左侧加一个\xi_i，这样即使有些样本出错，因为加了一个数，使得仍能满足约束条件，可以得到解。

image.png

image.png

SVM解决线性不可分问题

一个例子：如图18所示，在一维空间线性不可分问题，映射到二维空间后，就线性可分了。


一个例子

原始问题很复杂，做一个映射后，就变得很简单。


image.png

映射函数怎么选？

其实我们根本不需要知道映射函数是什么，只需要知道kernel函数就行了。怎么做到的，看下面：
如下图所示，我们假设了一个映射函数，它把m维映射到\frac{m^2}{2}维。

image.png

支持向量机的优化过程中，时间复杂度最高的地方是输入向量间做内积。我们增加输入维度后，时间复杂度由
O(m)
提高到
O(m^2)
，计算量变得很大。但是这个问题已经被被解决了，我们能够让增加维度后的时间复杂度保持不变，仍为
O(m)
。
经过图22、图23的推导，发现增加维度后的映射函数点积，能够通过原始输入向量点积得到。
image.png

image.png

这个方法叫做Kernel Trick，是支持向量机最巧妙的地方。图24是Kernel Trick的总结。
image.png

常用的kernel函数：
Kernels

如何优化？

求解w和b过程中，发现根本不需要知道映射函数是什么，就能求出w和b。


image.png

支持向量机的发展路径

image.png
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容