技法的课，相对更关注算法，希望1个月内搞掂~
课程介绍
共计16周课程，主要内容：哲学上直观的理解、关键理论、核心算法和实际操作的注意点。围绕特征变换，本次课程涉及到以下三个方向：
1. 如何对大量的特征进行开发和正则化操作：SVM模型
2. 组合预测特征，构建和融合预测特征：AdaBoost算法
3. 识别和学习潜藏的特征：Deep Learning
线性支持向量机的引入
回顾《机器学习基石》中的PLA，对于线性可分的数据，能找到多个超平面正确的分开两类数据。
那么这些超平面中哪一个是最优的？
仅凭直觉，可以认为第三条直线最好。因为旁边的点离他们比较远，两个问题：
- 离得远为什么好
- 怎么量化/计算这个距离
点距离超平面远，可以理解成对误差的容忍度高，即如果观测受噪声影响出现部分偏差，距离大的超平面仍然能够正确区分两类数据。如下图：
距离定义为：离超平面最近的点到分类超平面的距离，用margin表示。
那么在样本数据线性可分条件下找到间隔最大的超平面可以这样描述：
参数求解
w0,w1,...,wd w 0 , w 1 , . . . , w d 中的w0 w 0 拿出来用b b 表示。同时省去x0x0项。这样hypothesis变为h(x)=sign(wTx+b) h ( x ) = s i g n ( w T x + b ) 。这里要注意一下，为什么后面会出现yn(wTxn+b)≥0 y n ( w T x n + b ) ≥ 0 。
距离计算
distance
d
i
s
t
a
n
c
e
，初中数学就学过点到直线的距离，点到面的距离可以理解成向量往超平面的法向量方向的投影。具体如下：
上图主要分两步：第一步证明w
w
是超平面的法向量，第二步求点到直线距离，目标点和超平面上任意一点构成向量，该向量往超平面的法向量上投影即可得点到超平面的距离。∣∣wT∥w∥(x−x′)∣∣=∣∣wT∥w∥x−wT∥w∥x′∣∣=∣∣wT∥w∥x+b∣∣|wT‖w‖(x−x′)|=|wT‖w‖x−wT‖w‖x′|=|wT‖w‖x+b|即可得出距离公式。那么目标函数转换为：
投影的计算：
由下图的推导，容易得到上述投影的计算
缩放
w,b
w
,
b
同时缩放，从而使得
这样缩放并不会改变超平面的性质，也不会改变点到超平面的距离。经过缩放，目标函数可以写成：
又min yn(wTxn+b)=1 m i n y n ( w T x n + b ) = 1 ，因此所有yn(wTxn+b)≥1 y n ( w T x n + b ) ≥ 1 ，那么此时分类一定是准确的，所以第一个条件一定可以满足。对第二个条件做一些修改，min yn(wTxn+b)=1 m i n y n ( w T x n + b ) = 1 变为yn(wTxn+b)≥1 y n ( w T x n + b ) ≥ 1 ，这样处理可能会导致最小距离大于1，但是可以同样对w,b w , b 做缩放使得最小距离等于1。具体逻辑如下：
二次规划求解
通过上节一系列变换，原始问题转换为二次规划问题。先举一个简单的例子做说明。二维平面上有四个点，两个正类两个负类。具体求解逻辑如下：
这种求最大间隔超平面的方法称为SVM，因为超平面的确定依靠的是最近的几个点，其余点没有影响。而这几个点称为支撑向量，利用支撑向量得到最大间隔超平面的方法称为支持向量机。
SVM的一般化求解方法是利用相关软件求解二次规划问题，即Quadratic Programming。具体求解需要对目标函数做一些整体，使其满足二次规划一般化的表达方式。具体如下：
SVM的优点
从直觉上讲，SVM可以找到最大间隔超平面，从而对噪声的容忍度更高，分类想过相对更好。但是它背后的逻辑是什么呢？SVM的思想和之前regularization的思想类似，调换了目标和限制条件，具体如下：
从另外一方面看，Large-Margin会限制Dichotomies的个数，并且可能shatter的点更少。回忆Dichotomies和shatter、break point 的定义：
1. 类似的某一种线可以把点二分，如果hypothesis可以把点二分，则称为一个dichotomy
2. 如果N
N
个点有2N2N个dichotomy，称N
N
个点被shatter
3. 如果kk个点有小于2k
2
k
个dichotomy，称k
k
为HH的break point
直观上看，线越胖，Dichotomies越少，那么模型复杂度就越低，模型的泛化性能越强。
Summary
本节课主要是介绍用线性支持向量机解决PLA问题，通过转换目标函数，得到二次规划的形式。并且介绍了SVM背后的逻辑，即减少dichotomies的个数，减少VC维，使得模型有更好的泛化能力。
2018-03-20 于杭州