机器学习技法-1~3讲

三条直线都正确，哪条直线最好： image.png 会选择第三条，原因： image.png

因此我们希望找一条胖胖的线

fatness也就是我们所说的margin，上图中的公式就可以写成

需要满足两点：

• 可以把样本点正确分类
• margin是样本点离直线的最近距离

目标： find largest-margin separating hyperplane
hypothesis表示为h(x) = sign(W^TX+b)
点到直线的距离计算公式：

目标变为：

继续简化-放缩

min 公式=1的必要条件是 min 公式>=1,解等价。
把条件放松之后，目标变为：
image.png
接下来的任务
求解SVM
转变成二次规划的形式求解

SVM的理论保证：和之前学习过的正则化比较。

另一个方面
consider ‘large-margin algorithm’ Aρ :
either returns g with margin(g) ≥ ρ (if exists), or 0 otherwise

对偶问题2

拉格朗日函数：

原问题有条件-->无条件的

选出b,w

• （坏的，1-y大于0 ）结果会越大。无限大
• （好的1-y小于0），结果a越小越好。

1. 通过L函数，可以求得原问题的下限。（最大化和最小化做了交换）

2. 满足一定条件(凸，有解，线性条件)。有强对偶关系，解等价。

   
   对偶问题

拉格朗日函数解法
经过推到，原问题解和a有关，满足三个条件 KKT条件

然后取负号：把最大化-->最小化；再把约束写到下面。把平方展开。专心求解a，w是一个藏起来的条件。然后用二次规划求解。

• 存在问题：Q矩阵计算量太大了。用特别为SVM设计的二次规划形式。
• 用KKT条件，求解出w和b。求解b的时候，选一个a！=0 时候计算。 注意到满足a>0的点，一定落在fat boundary上，这些点就是支持向量。
• 支持向量的理解：
  • a_n >0的属于SV（在边界上的点）
  • w,b只靠SV算出来。其他的不重要。

SVM和PLA比较

总结

• 原始问题，和在哪个空间有关，d^~空间太大的时候就难解
• 对偶问题，切换到a的空间，资料量的大小有关，通过最佳化，找出SV在哪，然后重建胖胖的边界。

• 第二讲笔记

第三讲kernel SVM ——简化dual SVM的计算量

弯弯曲曲的d的解决:用kernel。
kernel不同，几何定义不同，距离计算的方式不同。得到的边界不一样。

kernel SVM

使用无限多维？
可以。

线性的kernel(不做任何转换)：
优点：

1. 简单，安全
2. 不涉及别的问题，所以可以设计特别的QP二次规划的解决办法
3. 可以很容易的看出来machine怎么做分类的。哪些点重要

坏处：
有限制，当数据不是线性可分的时候。

线性核

polynomial kernel多项式核：
计算有困难，很多参数要选择，比较困难，心里有想好的Q的时候用

py核

高斯核-无限多维的转换

高斯核

自己定义的核函数：对称，求出来的K是半正定的