统计学习方法 笔记二
逻辑斯蒂回归与最大熵模型
都可用于二分类或多分类，都是对数线性模型
支持向量机
二分类模型，与感知机不同的是SVM模型选取准则是间隔最大化，而且当应用核函数时还可用于非线性可分的数据集；感知机模型的选取规准则是最小化误分类点数，且只能用于线性可分数据集；再一个不同就是感知机超平面选取结果可有多种，而支持向量机则是确定的
分类：
- 线性可分SVM -> 训练数据线性可分 -> 硬间隔最大化
- 支持向量、硬间隔、支撑超平面、分离超平面
- 线性SVM -> 训练数据近似线性可分 -> 软间隔最大化
- 非线性SVM -> 训练数据线性不可分 -> 核函数+软间隔最大化
注：学习都是在特征空间进行，所以需要将输入空间映射到特征空间
线性可分SVM
求几何间隔最大的分离超平面，可表示为下面的约束最优化问题：
$\max\limits_{w, b} \gamma$
$s.t.\quad y_{i}\left(\frac{w}{|w|} \cdot x_{i}+\frac{b}{|w|}\right) \geqslant \gamma, \quad i=1,2, \cdots, N$
考虑几何间隔和函数间隔的关系，可改写为：
$\max\limits_{w, b} \frac{\hat{\gamma}}{|w|}$
s.t. $\quad y_{i}\left(w \cdot x_{i}+b\right) \geqslant \hat{\gamma}, \quad i=1,2, \cdots, N$
因函数间隔$\hat{\gamma}$的取值并不影响最优化问题的解，所以可取$\hat{\gamma}=1$，又因为最大化$\frac{1}{\Vert w \Vert}$和最小化$\frac{1}{2}\Vert w \Vert^2$等价，故可转化为：
$\min\limits_{w, b} \frac{1}{2}|w|^{2}$
s.t. $\quad y_{i}\left(w \cdot x_{i}+b\right)-1 \geqslant 0, \quad i=1,2, \cdots, N$
求解方法通过拉格朗日对偶性来求解
线性SVM
由线性可分SVM可知，其主要由支持向量决定，而支持向量的数量又很少，所以当支持向量收到扰动时，分离超平面会收到很大的干扰；而且线性可分SVM是不能处理线性不可分数据集的 也就是说相对于线性可分SVM，其允许一部分点在间隔里边，但整体上对大多数点还是要保证线性可分的
设在间隔里边的点到支持超平面的函数距离为$\xi$，则其到分离超平面的距离就为$1-\xi$。随之地在度量函数中加入对这些点的惩罚项$\xi$
$\min\limits_{w, b, \xi} \frac{1}{2}|w|^{2}+C \sum_{i=1}^{N} \xi_{i}$
s.t. $\quad y_{i}\left(w \cdot x_{i}+b\right) \geqslant 1-\xi_{i}, \quad i=1,2, \cdots, N$ ，其中 $\xi_{i} \geqslant 0, \quad i=1,2, \cdots, N$
非线性SVM
允许数据集非线性可分,如圆作为分类超平面
方法：将输入空间映射到高维的特征空间
核函数：$K(x, z)=\phi(x) \cdot \phi(z)$
核函数更准确地应成为核技巧，因为通过它只是方便了在高维特征空间中的计算
核函数的分类：
- 线性核(Linear) 主要应用与线性可分的情形，参数少，速度块，对于一般的数据可以尝试首先运用线性核。
- RBF也就是径向基函数，也叫高斯核，应用最为广泛，主要应用线性不可分的情形，参数多，分类结果非常依赖于参数。通过交叉验证来寻找合适的参数，通过大量的训练可以达到比线性核更好的效果。
- 多项式核需要确定的参数要比RBF多，而参数多少直接影响了模型的复杂度。
- Sigmoid核，对于某些参数RBF和sigmoid具有相似的性能。
提升方法
提升方法(boosting)是属于集成学习中的序列方法，其将弱可学习方法提升为强可学习方法
AdaBoost
Adaptive Boosting(自适应提升)用于二分类问题，是基础的提升方法
模型：加法模型
损失函数：指数函数 $L(y,f(x))=e^{-yf(x)}$
特点：
- 能在学习过程中不断减少训练误差
- 训练误差是以指数速率下降的
对基分类器进行考量，决定每个分类器的权重；对分类器中每个样本进行考量，决定每个样本的权重
基分类器的分类误差率$e_m$是要小于0.5的，因为其是若分类器，但也比随机分类的结果要好，而随机分类的误差率就是0.5，所以可认为基分类器的误差率小于0.5。若出现大于0.5的情况，那么就分类的结果反转，即正变负，负变正，那么误差率就在0.5之内了，然而在这种情况时，要重新设定所有样本的权值，即相当于重新运行一样
模型构建过程：
重要的是$\alpha_m$和$w_{m+1,i}$的更新，其中$w_{m+1,i}$正比于$m_ie^{-\alpha_m}$，为什么要用$e$是因为当其幂指小于0时其值在0-1之间，当幂指大于0时，其值大于1，所以就保证了对原$w_i$的缩小和放大，即分类正确时，对权重进行缩小，当分类错误时，加大对应权重
前向分步算法
每一步都通过前一个累积的模型来最小化当前模型的损失函数
$argmin L(y,f(x))$
$f_m(x)=f_{m-1}(x)+\alpha_m G_m(x)$
AdaBoost算法算是前向分步算法的一个特例
提升树
提升树就是以决策树为基函数的提升方法
对残差进行拟合
提升树针对不同的问题， 选择不同的损失函数：指数损失（分类问题），平方损失（回归问题）， 一般损失（一般问题）， 针对一般问题， 优化方法采用梯度提升就有了GBDT
梯度提升树
对于平方损失函数，残差的计算是很容易的，但对于一般性的损失函数来说，残差的计算比较困难，所以可用负梯度来近似代替残差
公式是由泰勒一阶展开得到
EM算法
expectation maximization algorithm，即期望极大算法
EM算法就是含有隐变量的概率模型参数的极大似然估计法，是一种迭代算法，每次迭代中包含E(求期望)和M(求极大值)两步
应用：高斯混合模型
高斯混合模型可逼近任意连续概率分布，就如函数中的泰勒公式逼近任意函数一样
推广：GEM算法