image.png
image.png
因此我们希望找一条胖胖的线
fatness也就是我们所说的margin，上图中的公式就可以写成
需要满足两点：
- 可以把样本点正确分类
- margin是样本点离直线的最近距离
目标： find largest-margin separating hyperplane
hypothesis表示为h(x) = sign(WTX+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越小越好。
- 通过L函数，可以求得原问题的下限。（最大化和最小化做了交换）
-
满足一定条件(凸，有解，线性条件)。有强对偶关系，解等价。
对偶问题
拉格朗日函数解法
KKT条件
然后取负号：把最大化-->最小化；再把约束写到下面。把平方展开。专心求解a，w是一个藏起来的条件。然后用二次规划求解。
- 存在问题：Q矩阵计算量太大了。用特别为SVM设计的二次规划形式。
- 用KKT条件，求解出w和b。求解b的时候，选一个a！=0 时候计算。 注意到满足a>0的点，一定落在fat boundary上，这些点就是支持向量。
- 支持向量的理解：
- an >0的属于SV（在边界上的点）
- w,b只靠SV算出来。其他的不重要。
SVM和PLA比较
总结
- 原始问题，和在哪个空间有关，d~空间太大的时候就难解
- 对偶问题，切换到a的空间，资料量的大小有关，通过最佳化，找出SV在哪，然后重建胖胖的边界。
第三讲kernel SVM ——简化dual SVM的计算量
弯弯曲曲的d的解决:用kernel。
kernel不同，几何定义不同，距离计算的方式不同。得到的边界不一样。
kernel SVM
使用无限多维？
可以。
线性的kernel(不做任何转换)：
优点：
- 简单，安全
- 不涉及别的问题，所以可以设计特别的QP二次规划的解决办法
- 可以很容易的看出来machine怎么做分类的。哪些点重要
坏处：
有限制，当数据不是线性可分的时候。
线性核
polynomial kernel多项式核：
计算有困难，很多参数要选择，比较困难，心里有想好的Q的时候用
py核
高斯核-无限多维的转换
高斯核
自己定义的核函数：对称，求出来的K是半正定的
