《统计学习方法》阅读笔记
主要以监督学习为主，包括分类、标注和回归问题；讨论离散变量为主

1. 统计学习方法概论

1.1. 统计学习

目的：对数据进行预测和分析
实现方式：
- 训练数据集合
- 确定所有可能的模型假设空间（学习模型）
- 确定学习策略
- 实现求解最优模型的算法
- 通过学习选择模型
- 利用模型对数据进行预测

1.2. 监督学习

输入空间，特征空间，输出空间
特征空间每一维对应一个特征
模型定义在特征空间中
对具体输入进行预测：$P(y|x)$或$y=f(x)$

1.3. 统计学习三要素

模型，策略（评价模型的标准），算法
损失函数和风险函数（期望损失）
- 0-1损失函数 $L(Y,f(X))=1,Y\neq f(X)$
- 平方损失函数 $L(Y,f(X))=(Y-f(X))^2$
- 绝对损失函数 $L(Y,f(X))=|Y-f(X)|$
- 对数损失函数或对数似然损失函数 $L(Y,P(Y|X))=-logP(Y|X)$
  - 损失函数越小，模型越好
经验风险最小化和结构风险最小化
- 经验风险为模型关于训练集的平均损失
- 结构风险在经验风险上加上表示模型复杂度的惩罚项——防止过拟合
  1.4. 模型评估和选择
训练误差和测试误差
过拟合
正则化
- 结构风险最小化：在经验风险上加一个正则化项
  $$min_{f\in F}\frac{1}{N}\sum_{i=1}^N L(y_i,f(x_i))+\lambda J(f)$$
- $\lambda$不小于零，调整二者关系的系数
- 正则化项：可以使参数向量的$L_1$或$L_2$范数
交叉验证
- 简单交叉验证
- $S$折交叉验证
- 留一交叉验证
  1.5. 生成模型和判别模型
生成模型：
- 由数据学习联合概率分布$P(X,Y)$
- 求出条件概率分布$P(Y|X)$作为预测模型
- 朴素贝叶斯，隐马尔可夫模型
- 可还原联合概率分布，收敛速度快
- 存在隐变量时只能用生成方法学习
判别模型：
- 由数据直接学习决策函数$f(X)$或$P(Y|X)$
- 对给定的输入X，应该预测什么样的输出Y
- $k$近邻法，感知机，决策树，逻辑斯蒂回归模型，最大熵模型，支持向量机，提升方法，条件随机场

1.6. 分类问题

监督学习
从数据中学习分类模型或分类决策函数
精确率，召回率，$F_1$值（精确率和召回率的调和平均）

1.7. 标注问题

监督学习，是分类问题的推广
输入为一个观测序列，输出一个标记序列或状态序列——可能的标记个数是有限的
隐马尔可夫模型，条件随机场
评价指标同上

1.8. 回归问题

监督学习
预测输入变量和输出变量的关系——等价于函数拟合——一元回归与多元回归，线性回归和非线性回归
常用损失函数为平方损失函数

2. 感知机

二分分类的线性分类模型（判别模型），输出为 -1 和 +1
即，将特征空间中的实例划分为正负两类的超平面
梯度下降法

2.1. 感知机模型

$f(x)=sign(\pmb{w}\cdot\pmb{x}+b)$，$sign(x)=+1，x\geq0$
$\pmb{w}\in R^n$ 称权值向量，作内积运算，$b\in R$称偏置
$\pmb{w}$是超平面的法向量，$b$是超平面的截距

2.2. 感知机学习策略

损失函数：$M$为错误分类点的集和
$$L(\pmb{w},b)=-\sum_{x_i\in M}y_i(\pmb{w}\cdot\pmb{x_i}+b)$$
损失函数非负，选取使损失函数最小的模型参数——即模型

2.3. 感知机学习算法

误分类驱动的随机梯度下降
首先随意选择一个超平面，之后用梯度下降法极小化损失函数——一次随机选取一个误分类点使其梯度下降:
- 分别计算损失函数两个参数的梯度
- 随机选择一个误分类点$(x_i,y_i)$（或训练集中选取一个点带入模型进行计算，取小于等于0的点）
- 更新参数
  $$w \leftarrow w+\eta y_ix_i$$
  $$b \leftarrow b+\eta y_i$$
- 重复步骤直到训练集中没有误分类的点
当训练集线性可分时，此算法的迭代时收敛的
当训练集不线性可分时，不收敛，结果震荡
存在很多解，这些解依赖于初值的选择和过程中误分类点的选择顺序——需要对分类超平面增加约束条件，以得到唯一的超平面（此即线性支持向量机）
对偶形式：
- 将参数表示为实例$x_i$和标记$y_i$的线性组合形式，通过求解系数得到参数
- $f(x)=sign(\sum_{j=1}^N\alpha_jy_jx_j\cdot\pmb{x}+b)$
- 模型参数为$\pmb{\alpha}=(\alpha_1,…,\alpha_n)^T$和$b$，迭代前赋初值为0
- 选取数据集中的点，如果$y_i{sign(\sum_{j=1}^N\alpha_jy_jx_j\cdot\pmb{x}+b) \leq0}$：
  $$\alpha_i \leftarrow \alpha_i+\eta $$
  $$b \leftarrow b+\eta y_i$$
- 迭代更新直到没有误分类数据

3. k近邻法

不具有显式的学习过程
利用训练集对特征向量空间进行划分
三要素：k值的选择、距离度量、分类决策规则
不同的距离度量确定的最近邻点不同

3.1. k近邻算法

输入训练数据集：$T={(x_1,y_1),(x_2,y_2),…,(x_n,y_n)}$，$x_i$为实例的特征向量，$y_i$为实例的类别。输出实例$x$所属的类别$y$
根据给定的距离度量，在训练集中找到与$x$最近的$k$个点，覆盖这些点的$x$的邻域为$N_k(x)$
根据分类决策规则（如多数表决）决定类别：
$$y={arg,\underset {c_j}{\operatorname {max}},\sum_{x_i\in N_k(x)}I(y_i=c_j)}$$

其中$I$为指示函数，相等时$I$为1，否则为0
多数表决等价于经验风险最小化

3.2. 更快寻找近邻点：kd树

最简单的方法是线性扫描。计算输入实例与每个训练实例的距离
$kd$树为二叉树，不断用垂直于坐标轴的超平面将$k$维空间切分，使得树的每一个节点对应于一个$k$维超矩形区域
构造平衡$kd$树：
- 输入$k$维空间数据集$T$，输出$kd$树
- 构造根节点，根节点对应于包含$T$的$k$维空间的超矩形区域。选择第一维为坐标轴，以数据集所有实例的第一维坐标的中位数作为切分点，将根节点对应的区域切分为两个区域，切分的超平面与坐标轴垂直。从而生成深度为 1 的左右子节点，将落在中位数上的实例保存在根节点
- 重复：对深度为$j$的结点，选择第$l$维为切分的坐标轴，其中$l=(jmodk)+1$，重复下去。生成深度为$j+1$的左右子结点。
- 直到两个子区域没有实例存在时停止
搜索算法：
- 输入已构造的$kd$树，目标点$x$ ，输出$x$的最近邻
- 在 kd 树中找出包含目标点$x$的叶结点：从根出发，递归向下访问$kd$树，若$x$当前维坐标小于切分点坐标则移动到左结点，反之右结点，直到叶子节点
- 以此叶节点为当前最近点
- 递归向上回退，对每个结点：
  - 若当前节点保存的实例点距离更近，则以当前节点的实例点为当前最近点
  - 对当前最近点检查该节点的兄弟节点，是否有更近的点：兄弟结点对应的区域，是否与以目标点为球心、以目标点和当前最近点间距离为半径的超球体相交
    - 若相交则移动到另一个子结点进行最近邻搜索
    - 不相交则向上回退
- 回到根节点时搜索结束，最后的当前最近点为$x$的最近邻点
适用于训练实例数远大于空间维数时

4. 朴素贝叶斯

4.1. 学习与分类

通过训练集学习联合概率分布$P(X,Y)$
后验概率最大化，即期望风险最小化
作条件独立性假设
对给定的输入$x$，通过学习到的模型计算后验概率分布$P(Y=c_k|X=x)$，取后验概率最大的类作为输出
$$y=f(x)=arg,\underset {c_k}{\operatorname{max}},\frac{P(Y=c_k)\prod_j P(X^{(j)}=x^{(j)}|Y=c_k)}{\sum_kP(Y=c_k)\prod_j P(X^{(j)}=x^{(j)}|Y=c_k)} ，即arg,\underset {c_k}{\operatorname{max}},P(Y=c_k)\prod_j P(X^{(j)}=x^{(j)}|Y=c_k)$$

4.2. 参数估计

$a_{jl}$为第$j$个特征可能取的第$l$个值，$j=1,…,n$，$l=1,…,S_j$；$x_i^{(j)}$是第$i$个样本的第$j$个特征
计算先验概率及条件概率
$$P(Y=c_k)=\frac{\sum_{i=1}^NI(y_i=c_k)}{N}$$
$$P(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum_{i=1}^NI(x^{(j)}=a_{jl},y_i=c_k)}{\sum_{i=1}^NI(y_i=c_k)}$$
对于给定的实例，计算各个类的后验概率
取后验概率最大的作为实例$x$的类
拉普拉斯平滑：
$$P_\lambda(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum_{i=1}^NI(x^{(j)}=a_{jl},y_i=c_k)+\lambda}{\sum_{i=1}^NI(y_i=c_k)+S_j\lambda}$$

5. 决策树

5.1. 决策树模型与学习

内部节点表示一个特征，叶节点表示一个类
损失函数通常为正则化的极大似然函数，学习策略为最小化损失函数
训练集放在根节点，选择最优特征将训练集划分为子集，使子集有一个在当前条件下的最好分类。继续选择新的最优特征进行分类，直至训练子集都被正确分类
剪枝
生成考虑局部最优，剪枝考虑全局最优

5.2. 特征选择

特征选择准则：信息增益和信息增益比
信息增益：
- 熵与条件熵
- 信息增益：训练集中，类与特征的互信息（$A$为一个特征）
  $$g(D,A)=H(D)-H(D|A)$$
- 信息增益比：信息增益/训练集类的熵

5.3. 决策树生成

5.3.1. ID3

输入：训练集$D$，特征集$A$，阈值$\varepsilon$
输出：决策树$T$
若所有实例属于同一类，则为单结点树
若$A$为空，则$T$为单节点树，取实例数最多的类作为该结点的类标记
计算$A$中各特征对$D$的信息增益，选择信息增益最大的特征$A_g$。信息增益：
- 小于$\varepsilon$，则为$T$为单结点树，取实例数最多的类作为该结点的类标记
- 不小于阈值：根据$A_g$每一可能值$a_i$，划分数据集$D_i$
对第$i$个子节点，以$D_i$为训练集，$A-A_g$为特征集，重复以上步骤

5.3.2. C4.5

基本同上，用信息增益比选择特征

5.4. 剪枝

极小化决策树整体的损失函数
- $t$为叶结点，包含$N_t$个样本点，其中$k$类样本有$N_{tk}$个，$\alpha \geq0$控制拟合程度和模型复杂度之间的影响
$$经验熵：H_t{(T)}=-\sum_k\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}$$

$$损失函数：C_\alpha(T)=\sum_{t=1}^{|T|}N_tH_t{(T)}+\alpha|T|=C(T)+\alpha|T|$$
算法：
- 计算每个结点的经验熵
- 设一组叶结点回缩到父节点之前与之后的损失函数值分别是$C_\alpha(T_A)$与$C_\alpha(T_B)$，若前者更小，则父节点变为新的叶结点
- 重复到不能继续

5.5. Cart

假设决策树是二叉树，内部节点特征取值为是和否
回归树：平方误差最小化
分类树：基尼指数最小化

6. 逻辑斯蒂回归与最大熵模型

均为对数线性回归模型

6.1. 逻辑斯蒂(logistic)回归模型

逻辑斯蒂分布
- $X$为连续随机变量，$\mu$为位置参数，$\gamma >0$ 为形状参数
- 分布函数：
  $$F(X)=P(X\leq x)=\frac{1}{1+e^{-(x-\mu)/\gamma}}$$
  - 关于点$(\mu,\frac{1}{2})$对称
  - 形状参数越小，在中心附近增长越快
- 密度函数：
  
  $$f(X)=P(X\leq x)=\frac{e^{-(x-\mu)/\gamma}}{\gamma(1+e^{-(x-\mu)/\gamma})^2}$$
  - 关于y轴对称
二项逻辑斯蒂回归模型
- 分类模型
  $$P(Y=1|x)=\frac{exp(w\cdot x+b)}{1+w\cdot x+b}$$
  $$P(Y=0|x)=\frac{1}{1+w\cdot x+b}$$
- $x$是输入，$Y\in {0,1}$是输出，$w$称权值向量，$b$称偏置
- 将实例分到概率值较大的一类
参数估计：
- 对数似然函数（训练数据有N组）
$$L(w)=\sum_{i=1}^N[y_i(w\cdot x_i)-log(1+exp(w\cdot x_i))]$$
- 对上式求极大值，得$w$的估计值
多项逻辑斯蒂回归：
- 离散随机变量$Y$有$K$个取值
  $$P(Y=k|x)=\frac{exp(w_k\cdot x+b)}{1+\sum_{k=1}^{K-1}w\cdot x+b}$$
  $$P(Y=K|x)=\frac{1}{1+\sum_{k=1}^{K-1}w_k\cdot x+b}$$

6.2. 最大熵原理

学习概率模型时，在所有可能的概率模型中，熵最大模型是最好的模型
引入拉格朗日乘子$w_0,…,w_n$，定义拉格朗日函数，得：
- $w_i$为特征的权值，$f_i(x,y)$为特征函数：当$x$和$y$满足某一事实时取值为1，否则为0
  $$P(y|x)=\frac{1}{Z_w(x)}exp(\sum_{i=1}^nw_if_i(x,y))$$
  $$Z_w(x)=\sum_yexp(\sum_{i=1}^nw_if_i(x,y))，规范化因子$$

6.3. 最优化算法

改进的迭代尺度法
- 最大熵模型的对数似然函数：$L(w)=\sum_{x,y}\widetilde{P}(x,y)\sum_{i=1}^nw_if_i(x,y)-\sum_x\widetilde{P}(x)logZ_w(x)$
- $\widetilde{P}(x,y)$为训练数据的经验概率分布
- 希望找到新的参数向量$\pmb{w}=(w_1,…,w_n)^T$，使得模型的对数似然函数值增大
- 算法：
  - 输入：特征函数$f_1,…,f_n$；经验分布$\widetilde{P}(x,y)$；模型$P_w(y|x)$
  - 输出：最优参数值${w_i}^*$，最优模型$P_{w^*}$
  - 取初值$w_i=0$
  - $\delta_i$是方程$\sum_{x,y}\widetilde{P}(x)P(y|x)f_i(x,y)exp(\delta_i\sum_{i=1}^nf_i(x,y))=\sum_{x,y}\widetilde{P}(x,y)f_i(x,y)$的解
  - 更新$w_i\leftarrow w_i+\delta_i$
拟牛顿法
梯度下降法

7. 支持向量机

训练数据线性可分：硬间隔最大化，学习线性分类器
训练数据近似线性可分：软间隔最大化，学习线性分类器
训练数据线性不可分：核技巧和软间隔最大化，学习非线性支持向量机
核函数：输入空间为欧氏空间或离散集合，特征空间为希尔伯特空间，将输入映射成的特征向量之间的内积

7.1. 线性可分支持向量机与硬间隔最大化

7.1.1. 线性可分支持向量机

二类分类问题
假设输入空间和特征空间的元素一一对应，支持向量机将输入映射为特征向量——在特征空间进行学习，希望找到一个超平面
训练数据集：$T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$，$x_i$为第$i$个特征向量，$y_i$为类标记
数据集线性可分：存在某个超平面将数据集的正实例点和负实例点完全正确地划分到超平面两侧
线性可分支持向量机：
- 分类超平面 $w^* \cdot x + b^*=0$
- 分类决策函数$f(x)=sign(w^\cdot x+b^)$
- 将两类数据正确划分且间隔最大

7.1.2. 函数间隔与几何间隔

函数间隔：给定训练集和超平面，定义函数间隔为$\hat{y_i}=y_i(w\cdot x_i+b)$，超平面关于训练集的函数间隔为所有关于样本点的函数间隔最小值
几何间隔：给定训练集和超平面，
- 超平面关于样本点的几何间隔为：$\gamma_i=y_i(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||})$，$||w||$为$w$的$L_2$范数
- 超平面关于训练集的几何间隔为所有关于样本点几何间隔的最小值

7.2. 间隔最大化

输入：线性可分数据集
输出：最大间隔分离超平面和分类决策函数
求解约束最优化问题：
$$\underset{w,b}{min} \frac{1}{2}||w||^2，s.t.y_i(w\cdot x_i+b)-1\geq 0$$
得最优解$w^*$、$b^*$
支持向量：线性可分时，样本点与超平面距离最近的样本点实例（使等号成立的点）
利用拉格朗日乘子法，构造并求解约束最优化问题：
$$\underset{\alpha}{min} \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i，s.t.\sum_{i=1}^N\alpha_iy_i=0，\alpha_i\geq 0$$

求得最优解$\alpha^*=(\alpha_1^*,…,\alpha_N^*)^T$
- $w^* = \sum_{i=1}^N\alpha_i^* y_ix_i$，并选择一个$\alpha^*$的一个正分量$\alpha_j^* $计算$b^*=y_j-\sum_{i=1}^N\alpha_i^* y_i(x_i \cdot x_j)$

7.3. 线性支持向量机与软间隔最大化

7.3.1. 线性支持向量机

将数据中的一些特异点取出，剩余的样本点线性可分

由对样本点引入松弛变量 $\xi_i\geq0$，约束条件：
$$y_i(w\cdot x_i+b\geq1-\xi_i)$$
同样的，对每个松弛变量支付一个代价，目标函数变为
$$\frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i$$
$C$为惩罚参数，较大时对误分类的惩罚增加
即：$\underset{w,b,\xi}{min} \frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i，s.t.y_i(w\cdot x_i+b\geq1-\xi_i)$

7.3.2. 学习算法

选择惩罚参数$C$，构造二次规划问题：

$$\underset{\alpha}{min} \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i，s.t.\sum_{i=1}^N\alpha_iy_i=0，C\geq \alpha_i\geq 0$$

求得最优解$\alpha^*=(\alpha_1^*,…,\alpha_N^*)^T$
$w^* = \sum_{i=1}^N\alpha_i^* y_ix_i$，选择一个$\alpha^*$的一个分量$0<\alpha_j^* <C$计算$b^* = y_j-\sum_{i=1}^N\alpha_i^* y_i(x_i\cdot x_j)$

7.4. 非线性支持向量机与核函数

7.4.1. 核技巧

通过非线性变换将输入空间对应于一个特征空间，超曲面模型对应于超平面模型，通过在特征空间中求解线性支持向量机
核函数：存在一个从欧氏空间$X$到希尔伯特空间$H$的映射函数$\phi(x)$，函数$K(x,z)=\phi(x)\cdot \phi(z)$，所有$x,z\in X$，则$K(x,z)$为核函数

7.4.2. 正定核

设$K$是对称函数，$K(x,z)$为正定核函数$<=>$对应的 Gram 矩阵$K=[K(x_i,x_j)]_{m\times n}$为半正定矩阵

7.4.3. 常用核函数

多项式核函数
高斯核函数
字符串核函数
将线性支持向量机对偶形式中的内积换成核函数

7.5. 序列最小最优化算法

解此问题：

$$\underset{\alpha}{min} \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^N\alpha_i，s.t.\sum_{i=1}^N\alpha_iy_i=0，C\geq \alpha_i\geq 0$$
变量是拉格朗日乘子，一个变量对应一个样本点
SMO算法：
- 输入：训练集，精度$\varepsilon$
- 输出：近似解$\hat{\alpha}$
1. 取初值$\alpha^{(0)}=0$，令$k=0$
2. 取优化变量 $\alpha_1^{(k)},\alpha_2^{(k)}$，解析求解两个变量的最优化问题，得到最优解$\alpha_1^{(k+1)},\alpha_2^{(k+1)}$，更新$\alpha$为$\alpha^{(k+1)}$
3. 若在精度范围内满足：
  $$\sum_{i=1}^N\alpha_iy_i=0 \ y_i\cdot g(x_i)\geq 1,{x_i|\alpha_i=0} =1, \ {x_i|0<\alpha_i<C}\leq1, \ {x_i|\alpha_i=C} \ g(x_i)=\sum_{j=1}^N\alpha_jy_jK(x_j,x_i)+b$$
  则取$\hat{\alpha} =\alpha^{(k+1)}$

8. 提升方法

改变训练样本的权重，学习多个分类器并进行线性组合，提高分类性能

8.1. AdaBoost算法

二分类的训练数据集，从训练数据中学习一系列弱分类器或基本分类器，并将其线性组合成一个强分类器
算法：
- 输入：二分类训练集，弱学习算法
- 输出：最终分类器$G(x)$
1. 初始化训练数据的权值分布$D_1=(w_{11},…,w_{1N}),w_{1i}=\frac{1}{N}$
2. 对$m=1,…,M$:
  1. 使用具有权值分布$D_m$的训练集学习，得基本分类器$G_m(x)$
  2. 计算$G_m(x)$在训练集上的分类误差率$e_m=P(G_m(x_i)\neq y_i)$
  3. $G_m(x)$系数$\alpha_m=\frac{1}{2}log\frac{1-e_m}{e_m}$，底数为自然对数
  4. 更新权值分布$D_{m+1}=(w_{m+1,1},…w_{m+1,N})$，$w_{m+1,i}=\frac{w_{mi}}{Z_m}exp(-\alpha_my_iG_m(x_i))$，其中$Z_m=\sum_{i=1}^Nw_{mi}exp(-\alpha_my_iG_m(x_i))$为规范化因子
3. 得到最终分类器$G(x)=sign(\sum_{m=1}^M\alpha_mG_m(x))$
- $w_{m+1,i}=\begin{Bmatrix} \frac{w_{mi}}{Z_m}e^{-\alpha_m},G_m(x_i)=y_i \ \frac{w_{mi}}{Z_m}e^{\alpha_m},G_m(x_i)\neq y_i\ \end{Bmatrix}\quad$

8.2. 提升树

以分类树或回归树为基本分类器
表示为$M$个决策树的加法模型$f_M(x)=\sum_{m=1}^MT(x;\theta_m)$，其中$T(x;\theta_m)$为决策树，$\theta_m$为决策树参数

8.2.1. 提升树算法

采用前向分步算法。初始提升树$f_0(x)=0$
第$m$步模型为$f_m(x)=f_{m-1}(x)+T(x;\theta_m)$
通过经验风险最小化确定下一棵决策树的参数$\hat{\theta_m}=arg\underset{\theta_m}{min} \sum_{i=1}^NL(y_i,f_{m-1}(x_i)+T(x_i;\theta_m))$
回归问题的提升树算法
- 输入：训练数据
- 输出：提升树$f_M(x)$
1. 计算残差$r_{mi}=y_i-f_{m-1}(x_i),i=1,…,N$
2. 拟合残差得回归树$T(x;\theta_m)$
3. 更新$f_m(x)=f_{m-1}(x)+T(x;\theta_m)$

8.2.2. 梯度提升

对一般的损失函数进行优化
算法：
- 输入：训练集($N$个数据)，损失函数$L(y,f(x))$
- 输出：回归树$f(x)$
1. 初始化
  $$f_0(x)=arg\underset{c}{min} \sum_{i=1}^NL(y_i,c)$$
2. 对$m=1,…,M$
  1. 对$i=1,…,N$
    
    $$r_{mi}=-[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]{f(x)=f{m-1}(x)}$$
  2. 对$r_{mi}$拟合一个回归树，得第$m$棵树的叶结点区域$R_{mj},j=1,…,J$
  3. 对$j$
    $c_{mj}=arg\underset{c}{min} \sum_{x_i\in R_{mj}}L(y_i,f_{m-1}(x_i)+c)$
  4. 更新$f_m(x)=f_{m-1}(x)+\sum_{j=1}^Jc_{mj}I(x\in R_{mj})$
  5. 得回归树$\hat{f(x)}=\sum_{m=1}^M\sum_{j=1}^Jc_{mj}I(x\in R_{mj})$
初始化，估计使损失函数极小化的常数值；计算损失函数的负梯度在当前模型的值，作为残差得估计；估计回归树叶结点区域，以拟合残差近似值；利用线性搜索估计叶结点区域的值，最小化损失函数；更新回归树

9. EM算法及其推广

用于含有隐变量的概率模型参数的极大似然估计
求期望，求极大

9.1. EM算法

三硬币模型：先抛硬币A，由A决定抛B或C，记录抛B或C的结果，如何估计三硬币正面出现的概率？
$Y$代表观测随机变量的数据（也称不完全数据），$Z$代表隐随机变量的数据（不可观测），$\theta$为需要估计的模型参数，则对数似然函数为$L(\theta)=logP(Y|\theta)$，联合概率分布$P(Y,Z|\theta)$，完全数据对数似然函数$logP(Y,Z|\theta)$
EM算法
- 迭代求$L(\theta)=logP(Y|\theta)$
- 输入：观测变量数据$Y$，隐变量数据$Z$，联合分布$P(Y,Z|\theta)$，条件分布$P(Z|Y,\theta)$
- 输出：模型参数$\theta$
1. 选择参数初值$\theta^{(0)}$
2. E步：记$\theta_{(i)}$为第$i$次迭代参数$\theta$的估计值，在第$i+1$步迭代时：
  $$Q(\theta,\theta^{(i)})=E_Z[logP(Y,Z|\theta)|Y,\theta^{(i)}]=\sum_ZlogP(Y,Z|\theta)P(Z|Y,\theta^{(i)})$$这里$P(Z|Y,\theta^{(i)})$为给定观测数据$Y$和当前参数估计$\theta_{(i)}$下隐变量数据的条件概率分布
3. M步：$\theta_{(i+1)}=arg\underset{\theta}{max} Q(\theta,\theta^{(i)})$
4. 重复直到收敛
$Q$函数：$Q(\theta,\theta^{(i)})$是核心
EM算法对初值敏感
一般停止迭代的条件为$||\theta_{(i+1)}-\theta_{(i)}||<\varepsilon_1$

9.2. 学习高斯混合模型

高斯混合模型指如下形式的概率分布模型：$P(y|\theta)=\sum_{k=1}^K\alpha_k\phi(y|\theta_k)$其中$\alpha_k\geq0$是系数，$\sum_{(k=1)}^K\alpha_k=1$,$\phi(y|\theta_k)$为高斯分布密度，称为第$k$个分模型，$\theta_k=(\mu_k,\sigma_k^2)$
一般的混合模型可以用任意的概率分布密度代替高斯分布密度
高斯混合模型参数估计的EM算法
- 明确隐变量
- 确定$Q$函数
- 确定 M 步
- 算法：
  - 输入：观测数据$y_1,…,y_N$，高斯混合模型
  - 输出：高斯混合模型的参数
1. 取参数初始值迭代
2. E步：依据当前模型参数，得分模型$k$对观测数据$y_j$的响应度$\hat{\gamma}_{jk} =\frac{\alpha_k\phi(y_j|\theta_k)}{\sum_{k=1}^K\alpha_k\phi (y_j|\theta_k)},j=1,…,N;k=1,…,K$
3. M步：新一轮迭代的模型参数
  $$\hat{\mu}k = \frac{\sum{j=1}^N\hat{\gamma}{jk}y_j}{\sum_{j=1}^N\hat{\gamma}{jk}},k=1,…,K$$
  
  $$\hat{\sigma}k^2=\frac{\sum{j=1}^N\hat{\gamma}{jk}(y_j-\mu_k)^2}{\sum{j=1}^N\hat{\gamma}_{jk}},k=1,…,K$$
  
  $$\hat{\alpha}k=\frac{\sum{j=1}^N\hat{\gamma}_{jk}}{N}$$
4. 重复，直到收敛

9.3. EM算法的推广

$F$函数：$F(\widetilde{P},\theta)=E_{\widetilde{P}}[logP(Y,Z|\theta)]+H(\widetilde{P})$
- 隐变量数据$Z$的概率分布为$\widetilde{P}(Z)$，参数为$\theta$
- $H(\widetilde{P})$是分布$\widetilde{P}(Z)$的熵

9.3.1. GEM算法

$GEM$算法1
- 输入：观测数据，$F$函数
- 输出：模型参数
1. 初始化参数$\theta^{(0)}$
2. 第$i+1$次迭代
  1. 记$\theta^{(i)}$为参数的估计值，$\hat{P}^{(i)}$为$\hat{P}$的估计，求$\hat{P}^{(i+1)}$使$\hat{P}$极大化$F(\hat{P},\theta^{(i)})$
  2. 求$\theta^{(i+1)}$使$F(\hat{P}^{(i+1)},\theta)$极大化
3. 重复，直到收敛
$GEM$算法2
- 不直接求极大化$Q(\theta,\theta^{(i)})$的$\theta$，而是逐步逼近
- 输入：观测数据，$Q$函数
- 输出：模型参数
1. 初始化参数$\theta^{(0)}$
2. 第$i+1$次迭代
  1. 记$\theta^{(i)}$为参数的估计值，$Q(\theta,\theta^{(i)})=\sum_ZP(Z|Y,\theta^{(i)})logP(Y,Z|\theta)$
  2. 求$\theta^{(i+1)}$使$Q(\theta^{(i+1)},\theta^{(i)})>Q(\theta^{(i)},\theta^{(i)})$
3. 重复，直到收敛
$GEM$算法3
- 当参数维度$d\geq2$时，采用新的算法，将EM算法的M步分解为$d$次条件极大化，每次其他分量不变，只改变一个分量
- 输入：观测数据，$Q$函数
- 输出：模型参数
1. 初始化参数$\theta^{(0)}=(\theta_1^{(0)},…,\theta_d^{(0)})$
2. 第$i+1$次迭代
  1.记$\theta^{(i)}=(\theta^{(i)}_1,…,\theta^{(i)}_d)$为参数的估计值，$Q(\theta,\theta^{(i)})=\sum_ZP(Z|Y,\theta^{(i)})logP(Y,Z|\theta)$
  1. 进行$d$次条件极大化：求使$Q(\theta,\theta^{(i)})$极大的$\theta^{(i+1)}_1$，之后固定$\theta^{(i+1)}_1$，求使$Q(\theta,\theta^{(i)})$极大的$\theta^{(i+1)}_2$，…，得到$\theta^{(i+1)}$使$Q(\theta^{(i+1)},\theta^{(i)})>Q(\theta^{(i)},\theta^{(i)})$
3. 重复，直到收敛

10. 隐马尔可夫模型

10.1. 隐马尔可夫模型的基本概念

隐马尔可夫模型：
- 关于时序的概率模型，描述由一个马尔科夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测得到观测随机序列
- 序列每一个位置可看作一个时刻
- 模型由初始概率分布、状态转移概率分布、观测概率分布确定
- 设$Q={q_1,…,q_N}$是所有可能的状态集合，$V={v_1,…,v_M}$是所有可能的观测的集合,$I=(i_1,…,i_T)$是长度为$T$的状态序列，$O=(o_1,…,o_T)$是对应的观测序列
- 状态转移矩阵$A=[a_{ij}]{N\times N},a{ij}=P(i_{t+1}=q_j|i_t=q_i)$为时刻$t$处于状态$q_i$条件下在时刻$t+1$转移到状态$q_j$的概率，观测矩阵$B=[b_j(k)]_{N\times M},b_j(k)=P(o_{t}=v_k|i_t=q_i)$为时刻$t$处于状态$q_j$条件下生成观测$v_k$的概率，$\pi=(\pi_i),\pi_i=P(i_i=q_i)$为时刻$t=1$处于状态$q_i$的概率
- 模型$\lambda=(A,B,\pi)$
- $A$与$\pi$确定隐藏的马尔可夫链，$B$确定了如何从状态生成观测
观测序列生成过程
- 输入：模型$\lambda=(A,B,\pi)$，观测序列长度$T$
- 输出：观测序列$O$
1. 按照初始状态分布$\pi$生成状态$i_1$
2. $t=1$
3. 按照状态$i_t$的观测概率分布$b_{i_t}(k)$生成$o_t$
4. 按照状态$i_t$的状态转移概率分布${a_{i_ti_{t+1}}}$产生状态$i_{t+1}$
5. $t=t+1$，重复
三个问题：
- 计算观测序列概率：给定模型$\lambda$和观测序列$O$，计算模型下观测序列出现的概率$P(O|\lambda)$
- 已知观测序列$O$，估计模型$\lambda$参数，使$P(O|\lambda)$最大
- 已知模型$\lambda$和观测序列$O$，求对给定观测序列条件概率$P(I|O)$最大的状态序列$I=(i_1,…,i_T)$，即给定观测序列求最有可能的对应状态序列

10.2. 概率计算算法

10.2.1. 前向算法

前向概率：给定模型$\lambda$，定义到时刻$t$部分观测序列为$(o_1,…,o_t)$且状态为$q_t$的概率为前向概率：$\alpha_t(i)=P(o_1,o_2,…,i_t=q_t|\lambda)$
前向算法
- 输入：模型$\lambda$，观测序列$O$
- 输出：观测序列概率$P(O|\lambda)$
1. 初值：初始化前向概率，为初始时刻$i_1=q_i$和观测$o_1$的联合概率，$\alpha_1(i)=\pi_ib_i(o_i),i=1,…,N$
2. 递推：$\alpha_{i+1}(i)=[\sum_{j=1}^N\alpha_t(j)a_{ji}]b_i(o_{t+1}),i=1,…,N$
3. 终止：$P(O|\lambda)=\sum_{i=1}^N\alpha_T(i)$
- 举例：

10.2.2. 后向算法

后向概率：定义时刻$t$状态为$q_t$的条件下，从$t+1$到$T$的部分观测序列为$(o_{t+1},…,o_T)$的概率，即$\beta_t(i)=P(o_{t+1},…,o_T|i_t=q_i,\lambda)$
后向算法
- 输入：模型$\lambda$，观测序列$O$
- 输出：观测序列概率$P(O|\lambda)$
1. $\beta_T(i)=1,i=1,…,N$
2. 对$t=T-1,T-2,…,1$，$\beta_t(i)=\sum_{j=1}^Na_{ij}b_j(o_{t+1})\beta_{t+1}(j),i=1,…,N$
3. $P(O|\lambda)=\sum_{i=1}^N\pi_ib_i(o_1)\beta_1(i)$

10.3. 学习算法

10.3.1. 监督学习方法

训练集包含$S$个长度相同的观测序列和对应状态序列${(O_1,I_1),…,(O_s,I_s)}$，利用极大似然估计发估计马尔可夫模型参数
转移概率$a_{ij}$估计：$\hat{a}{ij}=\frac{A_ij}{\sum_{j=1}^NA{ij}}$，其中$A_{ij}$为样本中时刻$t$处于状态$i$且时刻$t+1$转移到状态$j$的频数
观测概率$b_j(k)$的估计：设样本中状态$j$观测为$k$的频数为$B_{jk}$，则$\hat{b}j(k)=\frac{B{jk}}{\sum_{k=1}^MB_{jk}}$,j=1,…,N;k=1,…,M$
初始状态概率$\pi_i$估计为$S$个样本中初始状态为$q_i$的频率
人工标注训练数据代价较高

10.3.2. Baum-Welch算法

给定训练集只有$S$个长度为$T$的观测序列${O_1,…,O_S}$没有状态序列
将状态序列数据看作不可观测的隐数据$I$
$P(O|\lambda)=\sum_IP(O|I,\lambda)P(I|\lambda)$
参数估计：
- $\pi=\frac{P(O,i_1=i|\bar{\lambda})}{P(O|\lambda)}$
- $a_{ij}=\frac{\sum_{t=1}^{T-1}P(O,i_t=i,i_{t+1}=j|\bar{\lambda})}{\sum_{t=1}^{T-1}P(O,i_t=1|\bar{\lambda})}$
- $b_j(k)=\frac{\sum_{t=1}^TP(O,i_t=j|\bar{\lambda})I(o_t=v_k)}{\sum_{t=1}^TP(O,i_t=j|\bar{\lambda})}$

10.4. 预测算法

维特比算法
- 动态规划求概率最大路径，一个路径对应一个状态序列

1. 统计学习方法概论

1.1. 统计学习

1.2. 监督学习

1.3. 统计学习三要素

1.4. 模型评估和选择

1.5. 生成模型和判别模型

1.6. 分类问题

1.7. 标注问题

1.8. 回归问题

2. 感知机

2.1. 感知机模型

2.2. 感知机学习策略

2.3. 感知机学习算法

3. k近邻法

3.1. k近邻算法

3.2. 更快寻找近邻点：kd树

4. 朴素贝叶斯

4.1. 学习与分类

4.2. 参数估计

5. 决策树

5.1. 决策树模型与学习

5.2. 特征选择

5.3. 决策树生成

5.3.1. ID3

5.3.2. C4.5

5.4. 剪枝

5.5. Cart

6. 逻辑斯蒂回归与最大熵模型

6.1. 逻辑斯蒂(logistic)回归模型

6.2. 最大熵原理

6.3. 最优化算法

7. 支持向量机

7.1. 线性可分支持向量机与硬间隔最大化

7.1.1. 线性可分支持向量机

7.1.2. 函数间隔与几何间隔

7.2. 间隔最大化

7.3. 线性支持向量机与软间隔最大化

7.3.1. 线性支持向量机

7.3.2. 学习算法

7.4. 非线性支持向量机与核函数

7.4.1. 核技巧

7.4.2. 正定核

7.4.3. 常用核函数

7.5. 序列最小最优化算法

8. 提升方法

8.1. AdaBoost算法

8.2. 提升树

8.2.1. 提升树算法

8.2.2. 梯度提升

9. EM算法及其推广

9.1. EM算法

9.2. 学习高斯混合模型

9.3. EM算法的推广

9.3.1. GEM算法

10. 隐马尔可夫模型

10.1. 隐马尔可夫模型的基本概念

10.2. 概率计算算法

10.2.1. 前向算法

10.2.2. 后向算法

10.3. 学习算法

10.3.1. 监督学习方法

10.3.2. Baum-Welch算法

10.4. 预测算法