李航《统计学习方法》笔记

概论

统计学习的特点

以计算机及网络为平台，建立在计算机及网络之上
以数据为研究对象，是数据驱动的学科
目的是对数据进行预测与分析
以方法为中心，统计学习方法构建模型并应用模型进行预测与分析
是概率论、统计学、信息论、计算理论、最优化理论及计算机科学等多个领域的交叉学科

统计学习的方法

统计学习由监督学习(supervised learning)、非监督学习(unsupervised learning)、半监督学习(semi-supervised learning)和强化学习(reinforcement learning)等组成，在讨论监督学习的情况下，统计学习方法的三要素为模型(model)、策略(strategy)和算法(algorithm)。

实现统计学习方法的步骤：

得到一个有限的训练数据集合
1. 去饿顶包含所有可能的模型的假设空间，即学习模型的集合
2. 确定模型选择的准则，即学习的策略
3. 实现求解最优模型的算法，即学习的算法
4. 通过学习方法选择最优模型
5. 利用学习的最优模型对新数据进行预测或分析

监督学习的基本概念

输入空间、特征空间和输出空间

在监督学习中，将输入和输出所有可能取值的集合分别称为输入空间和输出空间，每一个具体的输入是一个实例，通常由特征向量表示，所有特征向量存在的空间称为特征空间。根据输入变量X和输出变量Y的不同类型，对预测任务进行分类：
- X和Y均为连续变量的预测问题称为回归问题
- Y为有限个离散变量的预测问题称为分类问题
- X和Y均为变量序列的预测问题称为标注问题

统计学习三要素

模型

在监督学习过程中，模型就是要学习的条件概率分布或决策函数
策略

策略就是按照什么样的准则学习或者选择最优模型,损失函数度量模型一次预测的好坏,风险函数度量平均意义下模型预测的好坏.
- 损失函数(loss function，或代价函数(cost function))，度量模型一次预测的好坏，损失函数的值越小，模型就越好
  - 0-1损失函数
    - 平方损失函数
      $L(Y,f(X))=(Y-f(X))^2$
    - 绝对损失函数
      $L(Y,f(X))=|Y-f(X)|$
    - 对数损失函数
      $L(Y,P(Y|X))=-\log P(Y|X)$
- 风险函数，度量平均意义下模型预测的好坏,由于模型输入、输出(X,Y)是随机变量，遵循联合分布P(X,Y)，所以损失函数的期望是
  $R_{exp}(f)=E_P[L(Y,f(X))]=\int_{x*y}L(y,f(x))P(x,y)dxdy$
  这是理论模型f(X)关于联合分布P(X,Y)的平均意义下的损失，称为风险函数(risk function，或期望损失(expected loss))
  
  给定训练数据集
  $T=\{(x1,y1),(x2,y2),\cdots,(x_N,y_N)\}$
  模型f(X)关于训练数据集的平均损失称为经验风险(empirical risk)或经验损失(empirical loss)，记作
  $R_{emp}(f)=\frac{1}{N}\sum_{i=1}^{N}L(y_i,f(x_i))$
  根据大数定律，当样本容量N趋于无穷大时，经验风险趋于期望风险，由于现实原因，用经验风险估计期望风险并不理想，所以要对经验风险进行一定的矫正，即经验风险最小化和结构风险最小化两个基本策略，极大似然估计是经验风险最小化的一个例子；贝叶斯估计种的最大后验概率估计是结构风险最小化的一个例子.
  
  按照经验风险最小化求最优模型就是求解最优化问题:
  $\min _{f \in \mathcal{F}} \frac{1}{N} \sum_{i=1}^{N} L\left(y_{i}, f\left(x_{i}\right)\right)$
  当样本容量足够大时,经验风险最小化能保证很好的学习效果,但是当样本容量小,经验风险最小化学习容易产生”过拟合”现象.结构风险最小化是为了防止过拟合而提出的策略.结构风险最小化等价于正则化.结构风险在经验风险基础上加上表示模型复杂度的正则化项或罚项,其定义为:
  $R_{\mathrm{srm}}(f)=\frac{1}{N} \sum_{i=1}^{N} L\left(y_{i}, f\left(x_{i}\right)\right)+\lambda J(f)$
  其中$J(f)$为模型的复杂度,模型越复杂,复杂度就越大.结构风险最小化策略认为结构风险最小的模型是最优的模型.所以求解最优模型就是求解最优化问题:
  $\min _{f \in \mathcal{F}} \frac{1}{N} \sum_{i=1}^{N} L\left(y_{i}, f\left(x_{i}\right)\right)+\lambda J(f)$
  最终,监督学习问题就变成经验风险或结构风险函数的最优化问题.

正则化

正则化的一般形式:

$\min _{f \in \mathcal{F}} \frac{1}{N} \sum_{i=1}^{N} L\left(y_{i}, f\left(x_{i}\right)\right)+\lambda J(f)$

正则化项有不同的形式.例如回归问题中,损失函数是平方损失

正则化项是参数向量的$L_{2}$范数:
$L(w)=\frac{1}{N} \sum_{i=1}^{N}\left(f\left(x_{i} ; w\right)-y_{i}\right)^{2}+\frac{\lambda}{2}\|w\|^{2}$
正则化项时参数向量的$L_{1}$范数:
$L(w)=\frac{1}{N} \sum_{i=1}^{N}\left(f\left(x_{i} ; w\right)-y_{i}\right)^{2}+\lambda\|w\|_{1}$

感知机

K近邻法

$k$近邻法是基本且简单的分类与回归方法。其基本做法是：对给定的训练实例点和输入实例点，首先确定输入实例点的k个最近邻训练实例点，然后利用这$k$个训练实例点的类的多数来预测输入实例点的类。
$k$近邻法三要素：距离度量、$k$值的选择和分类决策规则。常用的距离度量是欧氏距离及更一般的$L_{p}$距离。$k$值小时，$k$近邻模型更复杂；$k$值大时，$k$近邻模型更简单。常用的分类决策规则是多数表决，对应于经验风险最小化。
$k$近邻法的实现需要考虑如何快速搜索$k$个最近邻点。$kd$树是一种便于对$k$维空间中的数据进行快速检索的数据结构。

朴素贝叶斯法

最终需要实现

$y=\arg \max _{c_{k}} P\left(Y=c_{k}\right) \prod_{j=1}^{n} P\left(X^{(j)}=x^{(j)} \mid Y=c_{k}\right)$

概率为0时会使用拉普拉斯平滑
朴素贝叶斯法的基本假设是添加独立性：
$\begin{aligned} P\left(X=x \mid Y=c_{k}\right) &=P\left(X^{(1)}=x^{(1)}, \cdots, X^{(n)}=x^{(n)} \mid Y=c_{k}\right) \\ &=\prod_{j=1}^{n} P\left(X^{(j)}=x^{(j)} \mid Y=c_{k}\right) \end{aligned}$

决策树

信息增益

若$X$是一个有限取值的离散随机变量，其概率分布为：

$P\left(X=x_{i}\right)=p_{i}, \quad i=1,2, \cdots, n$

则随机变量$X$的熵定义为：

$H(X)=-\sum_{i=1}^{n} p_{i} \log p_{i}$

信息增益：

$g(D,A) = H(D) - H(D|A)$

算法步骤：

输入：训练数据集D和特征A

输出：特征A对数据集D的信息增益$g(D,A)$

计算数据集D的经验熵$H(D)$
$H(D)=-\sum_{k=1}^{K} \frac{\left|C_{k}\right|}{|D|} \log _{2} \frac{\left|C_{k}\right|}{|D|}$
计算特征A对数据集D的经验条件熵$H(D|A)$
$H(D \mid A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} H\left(D_{i}\right)=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \sum_{k=1}^{K} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|} \log _{2} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|}$
计算信息增益
$g(D,A) = H(D) - H(D|A)$

信息增益比

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题，可以使用信息增益比进行校正。

$g_{R}(D, A)=\frac{g(D, A)}{H_{A}(D)}$

其中，

$H_{A}(D)=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \log _{2} \frac{\left|D_{i}\right|}{|D|}$

基尼指数

对于给定的数据集D，其基尼指数为：

$\operatorname{Gini}(D)=1-\sum_{k=1}^{K}\left(\frac{\left|C_{k}\right|}{|D|}\right)^{2}$

在特征A的条件下，集合D的基尼指数为：

$\operatorname{Gini}(D, A)=\frac{\left|D_{1}\right|}{|D|} \operatorname{Gini}\left(D_{1}\right)+\frac{\left|D_{2}\right|}{|D|} \operatorname{Gini}\left(D_{2}\right)$

ID3算法，信息增益
C4.5算法，信息增益比
CART算法，基尼指数

统计学习方法