《统计学习方法》监督学习Notes

来源：

• [《统计学习方法》书籍-第1篇 监督学习（链接缺失…）]

2024-01-16@isSeymour

第1章 统计学习及监督学习概论

1.1 统计学习

• 统计学习 statistical learning

  是关于计算机基于数据构建概率统计模型并运用模型对数据进行预测与分析的一门学科。亦称统计机器学习 statistical machine learning。

“如果一个系统能够通过执行某个过程改进它的性能，这就是学习”

——Herbert A.Simon

• 统计学习的基本假设（前提）

  同类数据具有一定的统计规律性。

1.2 统计学习的分类

基本分类

监督学习 supervised learning

指从标注数据中学习预测模型的机器学习问题。

• 本质

  学习输入到输出的映射的统计规律。

• 基本假设

  训练数据和测试数据是依联合概率分布 P(X, Y) 独立同分布的。

• 模型

  • 条件概率分布 $P(Y|X)$
  • 决策函数 $Y = f(X)$

• 预测

  输入 $x_{N+1}$

  • $y_N+1 = \arg \max P(y|x_{N+1})$
  • $y_{N+1} = f(x_{N+1})$

无监督学习 unsupervised learning

指从无标注数据中学习预测模型的机器学习问题。

• 本质

  学习数据中的统计规律或潜在结构。

• 模型

  • 函数 $z = g(x)$

  • 条件概率分布 $P(z|x)$

  • 条件概率分布 $P(x|z)$

• 预测

  • $z_{N+1} = \arg \max P(z|x_{N+1})$
  • $z_{N+1} = g(x_{N+1})$

强化学习 reinforcement learning

指智能系统在与环境的连续交互中学习最优行为策略的机器学习问题。

• 本质

  学习最优的序贯决策。

• 模型

  每一步 $t$，智能系统从环境中观测到一个状态 $S_t$ 与一个奖励 $r_t$ ，采取一个动作 $a_t$。

  环境根据智能系统选择的动作，决定下一步 $t+1$ 的状态 $s_{t+1}$ 与奖励 $r_{t+1}$ 。

  注：目标不是短期奖励的最大化，而是长期积累奖励的最大化。

• 过程

  强化学习过程中，系统不断试错 trial and error ，以达到学习最优策略的目的。

• 决策过程

  强化学习的马尔可夫决策过程是状态、奖励、动作序列上的随机过程，由四元组$<S, A, P, r>$组成。

  • $S$ 是有限状态的集合

  • $A$ 是有限动作的集合

  • $P$ 是状态转移概率函数

    $P(s'|s,a) = P(s_{t+1~}= s'|s_t = s, a_t = a)$

  • $r$ 是奖励函数

    $r(s, a) = E(r_{t+1}|s_t = s, a_t = a)$

  马尔可夫决策过程具有马尔可夫性：下一个状态只依赖于前一个状态与动作，由状态转移函数 $P(s'|s, a)$ 表示。下一个奖励依赖于前一个状态与动作，由奖励函数 $r(s, a)$ 表示。

• 策略 $\pi$

  给定状态下动作的函数 $a = f(s)$ 或者条件概率分布 $P(a|s)$。

• 价值函数（状态价值函数）

  策略 $\pi$ 从某一个状态 $s$ 开始的长期积累奖励的数学期望

  $v_\pi (s) = E_\pi \Big[r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + ... |s_t = s \Big]$

• 动作价值函数

  策略 $\pi$ 从某一个状态 $s$ 和动作 $a$ 开始的长期积累奖励的数学期望

  $q_\pi (s, a) = E_\pi \Big[r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + ... |s_t = s, a_t = a \Big]$

• 目标

  在所有可能的决策中选出价值函数最大的策略Π*

半监督学习 semi-supervised learning

指利用标注数据和未标注数据学习预测模型的机器学习问题。

• 目的

  旨在利用未标注数据中的信息，辅助标注数据，进行监督学习，以较低的成本达到较好的学习效果。

主动学习 active learning

指机器不断主动给出实例让教师进行标注，然后利用标注数据学习预测模型的机器学习问题。

• 目的

  找出对学习最有帮助的实例让教师标注，以较小的标注代价，达到较好的学习效果。

其他分类

• 概率论

  • 概率模型（存在联合概率分布）
  • 非概率模型

• 线性

  • 线性模型（函数是线性函数）
  • 非线性模型

• 参数

  • 参数化模型（参数维度固定）
  • 非参数化模型

• 算法

  • 在线学习 online learning

    每次接受一个样本，进行预测，之后学习模型，并不断重复该操作的机器学习。

  • 批量学习 batch learning

    一次接受所有数据，学习模型，之后进行预测。

按技巧分类

• 贝叶斯学习 Bayesian learning

  在概率模型的学习和推理中，利用贝叶斯定理，计算在给定数据条件下模型的条件概率，即后验概率，并应用这个原理进行模型的估计，以及对数据的预测。

  特点：使用模型的先验分布。

  

• 核方法 kernel method

  使用核函数表示和学习非线性模型的一种机器学习方法，可以用于监督学习和无监督学习。

  特点：不显式地定义这个映射，而是直接定义核函数，简化计算。

  

1.3 统计学习方法的三要素

方法 = 模型 + 策略 + 算法

模型

• 就是所要学习的条件概率分布或决策函数。

  • 模型的假设空间 hypothesis space

    包含所有可能的条件概率分布或决策函数

    $F = \{ f | Y = f(X)\}$

策略

• 从假设空间中选取最优模型。

• 损失函数 loss function

  度量模型一次预测的好坏，记作 $L( Y, f(X) )$

  • 0-1损失函数
  • 平方损失函数
  • 绝对损失函数
  • 对数损失函数

  损失函数值越小，模型越好。

• 风险函数 risk function （期望损失 expected loss）

  模型 $f(X)$ 关于联合分布 $P(X, Y)$ 的平均意义下的损失。

• 经验风险 empirical risk （经验损失 empirical loss）

  $$R_{emp} (f) = \frac{1}{N} \sum L(y_i , f(x_i ) )$$

  • 期望风险$R_{exp} (f)$ 是模型关于联合分布的期望损失；

    经验风险$R_{emp} (f)$ 是模型关于训练样本集的平均损失。

    根据大数定律，当样本容量 $N$ 趋于无穷时，经验风险 $R_{emp} (f)$ 趋于 $R_{exp} (f)$ 。

    所以，一个很自然的想法是用经验风险估计期望风险。

  • 但是，现实中训练样本数目有限，如此估计，常常不理想，

    因此，需要对经验风险进行一定的矫正。

    监督学习的两个基本策略：

    • 经验风险最小化
    • 结构风险最小化

• 经验风险最小化 empirical risk minimization, ERM

  认为，经验风险最小的模型是最优的模型。

  $$R_{erm} (f) = \min \frac{1}{N} \sum L(y_i,f(x_i))$$

• 结构风险最小化 structural risk minimization, SRM

  为了防止过拟合，结构风险最小化等价于正则化 reghularization 。

  在经验风险上加上表示模型复杂度的正则化项 regularizer 或 罚项 penalty term。

  $$R_{srm} (f) = \min \frac{1}{N} \sum L(y_i,f(x_i)) + \lambda J(f)$$

  • 例如，贝叶斯估计中的最大后验估计 maximun posterior probability estimation , MAP

    就是结构风险最小化的一个例子。

  • 当模型是条件概率分布、损失函数是对数损失函数、模型复杂度由模型的先验概率表示时，结构风险最小化就等价于最大后验概率估计。

监督学习问题就变成了经验风险或结构风险函数的最优化问题。

这时，经验或结构风险函数就是最优化的目标函数。

算法

• 指学习模型的具体计算方法。

1.4 模型评估与模型选择

训练误差与测试误差

• 训练误差 training error
• 测试误差 test error

过拟合与模型选择

• 过拟合

  如果一味追求提高对训练数据的预测能力，所选模型的复杂度则往往会比真模型更高。

  学习时选择的模型所包含的参数过多，导致这一模型对已知数据预测很好，但对未知数据预测得很差。

• 当模型的复杂度增大时，

  • 训练误差会逐渐减小并趋向于0；

  • 测试误差会先减小，达到最小值后又增大。（欠拟合 -> 完全拟合 -> 过拟合）

  选择复杂度适当的模型！

1.5 正则化与交叉验证

正则化 regularization

• 是结构风险最小化策略的实现。

  在经验风险上加一个正则化项 或 罚项。

  一般是模型复杂度的单调递增函数，模型越复杂，正则化值越大。

• 作用

  选择经验风险与模型复杂度同时最小的模型。

• 正则化符合奥卡姆剃刀 Occam’s razor 原理

  能够很好解释已知数据且十分简单才是最好的模型。

• 正则化项对应于模型的先验概率。

交叉验证 cross validation

• 重复使用数据，把给定数据切分，组合成为训练集与测试集，在此基础上反复进行训练、测试以及模型的选择。
  • 简单交叉验证
  • S折交叉验证
  • 留一交叉验证

1.6 泛化能力

泛化误差 generalization error

• 泛化能力

  指由该方法学习到的模型对未知数据的预测能力。

• 泛化误差

  所学到的模型的期望风险。

• 泛化误差上界 generalization error bound

  概率上界。

• 定理1.1 （泛化误差上界）

  $$R(f) \leq \hat{R}(f) + \varepsilon(d,N,\delta) \\ 其中 \varepsilon (d,N,\delta) = \sqrt{\frac{1}{2N}\Big( \log d + \log \frac{1}{\delta} \Big)}$$

1.7 生成模型与判别模型

生成方法

• 特点

  • 生成方法可以还原出联合概率分布$P(X, Y)$

  • 收敛速度更快

判别方法

• 特点
  • 直接学习的是条件概率 $P(Y|X)$ 或决策函数 $F(X)$ ，直接面对预测，准确率更高
  • 可以对数据进行各种程度的抽象、定义特征并使用特征，可以简化学习问题

1.8 监督学习应用

分类问题

• 分门别类

• X 连续，Y 离散

• 从数据中学习一个分类模型或分类决策函数，称为分类器 classifier。

  • 二分类问题
  • 多分类问题

• 性能指标

  $$TP——将正类预测为正类数 \\ FN——将正类预测为负类数 \\ FP——将负类预测为正类数 \\ TN——将负类预测为负类数$$

  • 精确率 precision

    $$P = \frac{TP}{TP+FP}$$

  • 召回率 recall

    $$R = \frac{TP}{TP+FN}$$

  • F1值 是P和R的调和均值

    $$\frac{2}{F_1} = \frac{1}{P} + \frac{1}{R} \\ F_1 = \frac{2TP}{2TP+FP+FN}$$

标注问题

• X 离散，Y 离散

回归问题

• X 连续，Y 连续

• 回归模型是表示从输入变量到输出变量之间映射的函数。

  回归问题等价于函数拟合：选择一条函数使其很好地拟合已知数据且很好地预测未知数据。

  • 一元回归
  • 多元回归
  • 线性回归
  • 非线性回归

• 回归问题最常用的损失函数是平方损失函数，

  在此情况下，回归问题可以用 最小二乘法 求解。

第2章 感知机

• 感知机 perceptron

  是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值。

  • 旨在求出将训练数据进行线性划分的分离超平面。

  • 导入基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求得感知机模型。

2.1 感知机模型

• 输入空间

  $X \subseteq{R^n}$

• 输出空间

  $Y \subseteq{ \{+1,-1\} }$

• 函数

  $f(x) = sign(w \cdot{x} + b)$

  • 权值向量 $w\in{R^n}$
  • 偏置 $b\in{R}$
  • $w\cdot{x}$ 表示内积，$sign$ 是符号函数

• 假设空间

  函数集合$\{f | f(x) = w\cdot{x} + b \}$

• 几何解释

  线性方程 $w \cdot{x} + b = 0$ 对应于特征空间 $R^n$ 的一个超平面 $S$，其中 $w$ 是超平面的法向量，$b$ 是超平面的截距。

  这个超平面将特征空间划分为两个部分，两部分的点分别为正、负两类，因此称为分离超平面。

  

2.2 感知机学习策略

• 线性可分数据集 linearly separable data set

  存在超平面 S 能够将数据集的所有实例点完全划分到超平面的两侧。

• 损失函数

  误分类点到超平面的 $S$ 的总距离

  $$-\frac{1}{||w||} \sum\limits_{x_i \in M}{ |w \cdot x_0 + b| }$$

  不考虑$\frac{1}{||w||}$，就得到感知机学习的损失函数

  $$L(w, b) = - \sum\limits_{x_i \in M}{ |w \cdot x_0 + b| }$$

  其中 $M$ 为误分类点的集合。

• 可知

  • 损失函数$L(w,b)$ 是非负的。
  • 没有误分类点，损失函数值为0；
  • 误分类点越少，误分类点离超平面越近，损失函数值越小。
  • 给定数据集$T$ ，损失函数$L(w,b)$ 是$w,b$ 的连续可导函数。

• 学习策略

  在假设空间中选取使损失函数式最小的模型参数$w,b$ ，即感知机模型。

2.3 感知机学习算法

感知机学习问题转化为求解损失函数式的最优化问题。

最优化的方法是随机梯度下降法。

原始形式

• 输入

  训练数据集 $T = \{ (x_1,y_1), (x_2,y_2), ..., (x_N,y_N) \}$ ，其中$x_i \in X = R^n, y_i \in Y = \{-1,+1\}, i=1,2,...,N$ ，学习率 $\eta (0 < \eta \leq 1)$

• 输出

  $w,b,感知机模型f(x) = sign(w \cdot x + b)$​

• 算法

  1. 选取初值 $w_0,b_0$

  2. 在训练集中选取数据 $(x_i,y_i)$

  3. 如果 $y_i(w \cdot x_i + b) \leq 0$ ，

     $$w \leftarrow w + \eta y_i x_i \\ b \leftarrow b + \eta y_i$$

  4. 转至（2），直至训练集中没有误分类点。

解释：

当一个实例点被误分类，即位于分离超平面的错误一侧时，即调整 $w,b$ 的值，使分离超平面向该误分类点的一侧移动，以减少该误分类点与超平面的距离，直至超平面越过该分类点使其被正确分类。

对偶形式

• 输入

  训练数据集 $T = \{ (x_1,y_1), (x_2,y_2), ..., (x_N,y_N) \}$ ，其中$x_i \in X = R^n, y_i \in Y = \{-1,+1\}, i=1,2,...,N$ ，学习率 $\eta (0 < \eta \leq 1)$

• 输出

  $a,b,感知机模型f(x) = sign(\sum\limits_{j=1}^{N}\alpha_j y_j x_j \cdot x + b)$ ，其中$\alpha = (\alpha_1,\alpha_2,...,\alpha_N)^T$

• 算法

  1. $\alpha \leftarrow 0, b \leftarrow 0$

  2. 在训练集中选取数据 $(x_i, y_i)$

  3. 如果 $y_i(\sum\limits_{j=1}^{N}{\alpha_j y_j x_j \cdot x_i + b}) \leq 0$

     $$\alpha_i \leftarrow \alpha_i + \eta \\ b \leftarrow b + \eta y_i$$

  4. 转至（2）直到没有误分类数据。

对偶形式中的训练实例仅以内积的形式出现，可以预先计算出来以矩阵形式存储——Gram矩阵。

$$G = {[ x_i \cdot x_j ]_{N \times N} }$$

收敛性

• 可以证明，误分类的次数 $k$​ 是有上界的，经过有限次搜索可以找到将训练数据完全正确分开的分离超平面。

  $$k \leq (\frac{R}{\gamma})^2$$

• 可以证明：

  样本集线性可分的充要条件是正实例点集所构成的凸壳与负实例点集所构成的凸壳互不相交。

• 当训练集线性可分时，

  感知机学习算法存在无穷多个解，其解由于不同的初值或不同的迭代顺序可能有所不同。

*2.4 示例

感知机1：原始形式

感知机2：对偶形式

第3章 $k$ 近邻法

• $k$ 近邻法 $k$ - nearest neighbor, $k$ - NN

  是一种基本的分类与回归方法。

  • 假设给定一个训练数据集，其中的实例类别已确定。分类时，对新的实例，根据其 k 个最近邻的训练实例的类别，通过多数表决等方式进行预测。

  • k 近邻法不具有显式的学习过程。

    k 近邻法实际上利用训练数据集对特征空间进行划分，并作为其分类的“模型”。

  • k近邻法是三要素：

    • k 值的选择
    • 距离度量
    • 分类决策规则

3.1 k 近邻算法

1. 根据给定的距离度量，在训练集 $T$ 中找出与 $x$ 最近邻的 k 个点，涵盖这 k 个点的 $x$ 的邻域 记作 $N_k(x)$

2. 在 $N_k(x)$ 中根据分类决策规则（如多数表决）决定 $x$ 的类别 $y$

   $$y = \arg \mathop{\max} \sum \limits_{x_i \in N_k(x)} I(y_i = c_i) \\ i=1,2,...,N\\ j=1,2,...,K \\ I为指示函数（当 y_i = c_i 时I为1，否则I为0）$$

• 特殊情况
  • 当 k=1 时：最近邻算法

3.2 k 近邻模型

距离度量

• 相似程度

  特征空间中两个实例点的距离是两个实例点相似程度的反映。

• 特征空间

  n维实数向量空间 $R^n$

• 距离度量

  $L_p$ 距离

  $$L_p(x_i,y_j) = (\sum \limits_{l=1}^{n} | x_i^{(l)} -x_j^{(l)} |^p )^{\frac{1}{p} }$$

  其中 $p \geq 1$

  • $p=2$ 为 欧式距离 Euclidean distance

    $$L_2(x_i,y_j) = (\sum \limits_{l=1}^{n} | x_i^{(l)} -x_j^{(l)} |^2 )^{\frac{1}{2} }$$

  • $p=1$ 为 曼哈顿距离 Manhattan distance

    $$L_1(x_i,y_j) = \sum \limits_{l=1}^{n} | x_i^{(l)} -x_j^{(l)} |$$

  • $p=\infty$ ，它是各个坐标距离的最大值，即

    $$L_\infty(x_i,y_j) = \mathop{max}_l | x_i^{(l)} -x_j^{(l)} |$$

k 值的选择

• k 值的选择会对 k 近邻法的结果产生重大影响。

  • 较小的 k

    较小的领域，近似误差 approximation error 减小，估计误差 estimation error 增大。

    整体模型变得复杂，容易发生过拟合。

  • 较大的 k

    较大的领域，近似误差增大，估计误差减小。

    整体模型变得简单，可能欠拟合。

  估计误差：当 k 较小，测试结果会对近邻的实例点非常敏感，若近邻的实例点恰好是噪声，预测结果就错了。

  近似误差：当 k 较大，领域较大，更多点被认为是近邻点，作为噪声的近邻点更多了。

• k 值一般会取一个比较小的数值。

  通常采用 交叉验证法 来选取最优的 k 值。

分类决策规则

• 分类决策规则

  往往采用 多数表决。

  即 由输入实例的 k 个邻近的训练实例中的多数类决定输入实例的类。

• 多数表决规则 majority voting rule

  如果分类的损失函数为 0-1损失函数，分类函数为

  $$f: R^n \rightarrow \{ c_1,c_2,...,c_k \}$$

  那么误分类率是

  $$\frac{1}{k} \sum \limits_{x_i \in N_k(x)} I(y_i \neq c_j) = 1 - \frac{1}{k} \sum \limits_{x_i \in N_k(x) } I(y_i = c_j)$$

• 因此，要使 误分类率最小 即 经验风险最小，

  就要使$ \sum \limits_{x_i \in N_k(x) } I(y_i = c_j)$ 最大，所以，多数表决规则等价于经验风险最小化。

3.3 k 近邻法的实现：kd 树

• 问题

  如何对训练数据进行快速 k 近邻搜索？

  这一点在特征空间的维数过大及训练数据容量大时尤其必要。

• 方法

  • 线性扫描 linear scan

    简单，但是非常耗时，在数据过大时不可行！

  • kd 树

    一种对 k 维空间中的实例点进行存储以便对其快速检索的树形数据结构。

    kd 树是二叉树，表示对 k 维空间的一个划分 partition。

构造平衡 kd 树

• 输入

  k 维空间数据集 $T = \{ x_1,x_2,...,x_N \}$，其中$x_i = (x_i^{(1)},x_i^{(2)},...,x_i^{(k)})^T$，$i=1,2,...,N$

• 输出

  kd 树

• 算法

  1. 开始：构造根结点（根结点对应于包含 $T$ 的 k 维空间的超矩形区域。

     • 选坐标轴，中位数切分

       选择 $x^{(1)}$ 为坐标轴，以 $T$ 中所有实例的 $x^{(1)}$ 坐标的中位数为切分点，将根结点对应的超矩形区域切分为两个子区域。

       （切分由通过切分点并与坐标轴 $x^{(1)}$ 垂直的超平面实现）

     • 划分左右子结点，中位数留在根

       由根结点生成深度为 1 的左、右子节点

       • 左子节点对应坐标 $x^{(1)}$​ 小于切分点的子区域
       • 右子节点对应坐标 $x^{(1)}$ 大于切分点的子区域
       • 根结点对应落在切分超平面上的实例点

  2. 重复：

     • 依次选取坐标轴，中位数切分

       对深度为 j 的结点，选择 $x^{(l)}$ 作为切分坐标轴，其中 $l = j\mod k + 1$ 。

     • 划分存值

  3. 直至两个子区域没有实例存在时停止。从而形成 kd 树的区域划分。

搜索 kd 树

• 输入

  已构造的 kd 树，目标点 x

• 输出

  x 的最近邻

• 算法

  1. 在 kd 树中找出包含目标点 x 的叶结点

     就是从根结点出发，向下搜索到正确的叶结点即可。

  2. 以此叶结点为“当前最近点”

  3. 递归地向上回退，在每个结点进行如下操作：

     • 若该结点保存的实例点比当前最近点距离目标更近，

       则以该实例点为“当前最近点”。

       而这个最近点一定位于该结点的一个子节点的区域中。

       其实，是检测另一子结点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交。

       • 若相交，可能在另一子区域存在更近的点，移动到另一个子结点，递归进行最近邻搜索。
       • 若不相交，向上回退。

  4. 当回退到根结点时，搜索结束。

     最后的“当前最近点”即为 x 的最近邻点。

• 时间复杂度

  $O(\log N)$

  这里N 是训练实例数。

  • kd 树适合训练实例数远大于空间维数
  • kd 树可以省去对大部分数据点的搜索，从而减少搜索的计算量。

*3.4 示例

构建平衡 kd 树

搜索最近邻

第4章 朴素贝叶斯法

• 朴素贝叶斯 naive Bayes

  基于贝叶斯定理与特征条件独立假设的分类方法。

  • 对于给定的训练数据集，
    • 基于特征条件独立假设学习输入输出的联合概率分布
    • 基于此模型，对给定的输入 x ，利用贝叶斯定理求出后验概率最大的输出 y。

• 实现简单，学习与预测效率都很高，很常用。

4.1 朴素贝叶斯法的学习与分类

条件独立性假设

• 见下方

  学习 - 条件概率分布 - 条件独立性假设。

学习

• 假设

  $P(X,Y)$ 是 $X$ 和 $Y$ 的联合概率分布，训练数据集 $T$ 由 $P(X,Y)$ 独立同分布产生。

  • 先验概率分布

    $$P(Y = c_k) , k=1,2,...,K$$

  • 条件概率分布

    $$P(X=x | Y=c_k) = P(X^{(1)}=x^{(1)},...,X^{(n)}=x^{(n)}|Y=c_k), k=1,2,...,K$$

    • 但是上述的条件概率分布有指数级数量的参数，其估计实际不可行。

      假设 $x^{(j)}$ 可能取值有 $S_j$ 个，$Y$ 可能取值有 $K$ 个，

      那么参数个数为$K \prod_{j=1}^{n} S_j$

    • 条件独立性假设

      这是一个较强的假设，朴素贝叶斯法也由此得名。假设如下：

      $$P(X=x|Y=c_k) = P(X^{(1)} = x^{(1)},...,X^{(n)}=x^{(n)}|Y=c_k)\\ = \prod \limits_{j=1}^{n} P(X^{(j)}=x^{(j)}|Y=c_k)$$

      条件独立假设等于是说，用于分类的特征在类确定的条件下都是条件独立。

      这一假设使得朴素贝叶斯法变得简单，但有时会牺牲一定的分类准确率。

  • 因此，可以得到联合概率分布$P(X,Y)$​

• 朴素贝叶斯法实际上学习到生成数据的机制，

  所以属于生成模型。

分类

• 朴素贝叶斯的分类

  对给定的输入 x ，通过学习到的模型计算后验概率分布

  $$P(Y=c_k|X=x) = \frac{P(X=x|Y=c_k)P(Y=c_k)}{\sum \limits_{k} P(X=x|Y=c_k)P(Y=c_k) }$$

  代入独立性假设，得到

  $$P(Y=c_k|X=x) = \frac{P(Y=c_k) \prod \limits_{j} P(X^{(j)}=x^{(j)}|Y=c_k)}{\sum \limits_{k} P(Y=c_k) \prod \limits_{j} P(X^{(j)}=x^{(j)}|Y=c_k) }$$

  这就是朴素贝叶斯法分类的基本公式。

• 朴素贝叶斯分类器

  $$y = f(x) = \arg \mathop{\max}_{c_k} \frac{P(Y=c_k) \prod \limits_{j} P(X^{(j)}=x^{(j)}|Y=c_k)}{\sum \limits_{k} P(Y=c_k) \prod \limits_{j} P(X^{(j)}=x^{(j)}|Y=c_k)}$$

  由于式子中对于所有 $c_k$ 的分母都是相同的，由此

  $$y = f(x) = \arg \mathop{\max}_{c_k} P(Y=c_k) \prod \limits_{j} P(X^{(j)}=x^{(j)}|Y=c_k)$$

• 后验概率最大化的含义

  • 朴素贝叶斯法将实例分到后验概率最大的类中，

    这等价于期望风险最小。

  • 可以取损失函数为 0-1损失函数，取条件期望，

    要求取期望风险极小化，只需对 X = x 逐个极小化。

    最终，由此推出了后验概率最大化。

    这就是朴素贝叶斯采用的原理。

4.2 朴素贝叶斯法的参数估计

极大似然估计

• 在朴素贝叶斯法中，学习意味着估计 $P(Y=c_k)$ 和$P(X^{(j)}=x^{(j)} |Y=c_k)$。

• 可以应用极大似然估计法估计相应的概率。

  • 先验概率

    $$P(Y=c_k) = \frac{\sum \limits_{i=1}^{N} I(y_i = c_k)}{N}, k=1,2,...,K$$

  • 条件概率

    设第 j 个特征 $x^{(j)}$ 可能取值的集合为 $\{ a_{j1},a_{j2},...,a_{jSj}\}$

    $$P(X^{(j)}=a_{jl}|Y=c_k) = \frac{\sum \limits_{i=1}^{N} I(x_i^{(j)}=a_{jl},y_i=c_k) }{\sum \limits_{i=1}^{N} I(y_i = c_k) } \\ j=1,2,...,n; \, l=1,2,...,S_j; \, k=1,2,...K$$

贝叶斯估计

• 使用极大似然估计可能出现所要估计的概率为0的情况。

  会影响后验概率的计算结果，使分类产生偏差。

• 解决方法：

  采用贝叶斯估计，在随机变量各个取值的频数上赋予一个正数 $\lambda > 0$​ 。

  $$P_{\lambda} (X^{(j)} = a_{jl} | Y=c_k) = \frac{\sum \limits_{i=1}^{N} I(x_i^{(j)}=a_{jl}, y_i=c_k)+ \lambda }{\sum \limits_{i=1}^{N} I(y_i=c_k)+S_j \lambda}$$

  • 当 $\lambda = 0$ 时，就是极大似然估计。

  • 常取 $\lambda = 1$ ，称为拉普拉斯平滑 Laplacian smoothing

  • 显然对于任何 $l=1,2,...,S_j, \, k=1,2,...,K$ 有

    $$P_{\lambda} (X^{(j)} = a_{jl} | Y=c_k) > 0 \\ \sum \limits_{l=1}^{S_j} P_{\lambda} (X^{(j)} = a_{jl}|Y=c_k) = 1$$

    可见，的确是一种概率分布。

• 先验概率的贝叶斯估计是

  $$P_\lambda (Y=c_k) = \frac{\sum \limits_{i=1}^{N} I(y_i=c_k)+\lambda }{N+K\lambda}$$

算法

• 输入

  • 训练数据 $T=\{ (x_1,y_1), (x_2,y_2),...,(x_N,y_N) \}$ ，

    其中 $x_i = (x_i^{(1)}, x_i^{(2)},...,x_i^{(n)})^T$ ，$x_i^{(j)}$ 是第 $i$ 个样本的第 $j$ 个特征， $x_i^{(j)} \in \{ a_{j1}, a_{j2},...,a_{jS_j} \}$ ，$a_{jl}$ 是第 $j$ 个特征可能取的第 $l$ 个值， $j=1,2,...,n; \, l=1,2,...,S_j; \, y_i \in \{c_1,c_2,...,c_K \}$ 。

  • 实例 $x$。

• 输出

  实例 $x$ 的分类。

• 算法

  1. 计算先验概率及条件概率

     $$P(Y=c_k) = \frac{\sum \limits_{i=1}^{N} I(y_i = c_k)}{N}, k=1,2,...,K$$

     $$P(X^{(j)}=a_{jl}|Y=c_k) = \frac{\sum \limits_{i=1}^{N} I(x_i^{(j)}=a_{jl},y_i=c_k) }{\sum \limits_{i=1}^{N} I(y_i = c_k) } \\ j=1,2,...,n; \, l=1,2,...,S_j; \, k=1,2,...K$$

  2. 对于给定的实例 $x=(x^{(1)},x^{(2)},...,x^{(n)})^T$ ，计算

     $$P(Y=c_k) \prod \limits_{j} P(X^{(j)}=x^{(j)}|Y=c_k)$$

  3. 确定实例 $x$ 的类

     $$y = \arg \mathop{\max}_{c_k} P(Y=c_k) \prod \limits_{j} P(X^{(j)}=x^{(j)}|Y=c_k)$$

这里算法采用的是极大似然估计，

若采用贝叶斯估计，则把（1）中的先验概率和条件概率替换成贝叶斯估计即可。

*4.3 示例

朴素贝叶斯1：极大似然估计

朴素贝叶斯2：贝叶斯估计

第5章 决策树

• 决策树 decision tree

  一种基本的分类与回归方法。

  • 树形结构，if-then 规则的集合。

    定义在条件特征空间与类空间上的条件概率分布。

  • 优点：可读性，分类速度快

  • 学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。

    预测时，对新的数据，利用决策树模型进行分类。

  • 决策树学习的3个步骤

    • 特征选择
    • 决策树的生成
    • 决策树的修剪

  • 算法

    • ID3
    • C4.5
    • CART

5.1 决策树模型与学习

模型

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点 node 和有向边 directed edge 组成。

结点有两种类型：

1. 内部结点 internal node
2. 叶结点 leaf node

内部结点表示一个特征或属性，叶结点表示一个类。

if-then 规则

• 由决策树的根结点到叶结点的每一条路径构建一条规则。

• 路径上内部结点的特征对应着规则的条件；

  而叶结点的类对应着规则的结论。

• if-then规则集合 互斥且完备。

条件概率分布

• 决策树表示给定特征条件下类的条件概率分布。

5.2 特征选择

• 特征选择

  决定用哪个特征来划分特征空间。

  • 在于对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。

  • 通常特征选择的准则是 信息增益 或 信息增益比。

熵 entropy

• 表示随机变量不确定性的度量。

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

  $$P(X=x_i) = p_i , \, i=1,2,...,n$$

  则随机变量 X 的熵定义为

  $$H(X) = - \sum \limits_{i=1}^{n} p_i \log p_i$$

  • 注：若 $p_i = 0$ ，则定义 $0 \log 0 = 0$ 。

  • 通常，以 $2$ 为底，或以自然对数 $e$ 为底。

    此时，熵的单位分别称作 $比特 bit$ 或 $纳特 nat$ 。

  • 由定义可知，熵只依赖于 X 的分布，而与 X 的取值无关。

    因此，也可以将 X 的熵记作 $H(p)$ 。

  • 熵越大，随机变量的不确定性就越大。

  • 可知 $0 \leq H(p) \leq \log n$ 。

条件熵 conditional entropy

• 表示已知随机变量 X 的条件下随机变量 Y 的不确定性。

• 设有随机变量 $(X,Y)$ ，其联合概率分布为

  $$P(X=x_i,Y=y_i) = p_{ij} , \, i=1,2,...,n; \, j=1,2,...,m$$

  则条件熵定义为 X 给定条件下 Y 的条件概率分布的熵对 X 的数学期望

  $$H(Y|X) = \sum \limits_{i=1}^{n} p_i H(Y|X=x_i) \\ 其中p_i = P(X=x_i), \, i=1,2,...,n$$

信息增益 information gain

• 表示得知特征 X 的信息而使得类 Y 的信息的不确定性减少的程度。

• 特征 A 对训练数据集 D 的信息增益 $g(D, A)$ ，定义为集合 D 的经验熵 $H(D)$ 与特征 A 给定条件下 D 的经验条件熵 $H(D|A)$ 之差，即

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

  • 一般地，熵 $H(D)$ 与条件熵 $H(Y|X)$ 之差称为互信息 mutual information。

  • 决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

  • 经验熵 $H(D)$

    表示对数据集 D 进行分类的不确定性。

  • 经验条件熵 $H(D|A)$

    表示在特征 A 给定的条件下对数据集 D 进行分类的不确定性。

  • 经验熵、经验条件熵

  当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别为 经验熵 empirical entropy 和 经验条件熵 empirical conditional entropy。

• 根据信息增益准则的特征选择方法

  对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。

算法

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

注：下方的对数据集取绝对值符号，表示数据集的样本个数。

• 算法

  1. 计算数据集 D 的经验熵 H(D)

     $$H(D) = - \sum \limits_{k=1}^{K} \frac{|C_k|}{|D|} \log_2 \frac{|C_k|}{|D|}$$

  2. 计算特征 A 对数据集 D 的经验条件熵 H(D|A)

     $$H(D|A) = \sum \limits_{i=1}^{n} \frac{|D_i|}{|D|} H(D_i) = - \sum \limits_{i=1}^{n} \frac{|D_i|}{|D|} \sum \limits_{k=1}^{K} \frac{|D_{ik}|}{|D_i|} \log_2 \frac{|D_{ik}|}{|D_i|}$$

  3. 计算信息增益

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

信息增益比 information gain ratio

• 校正问题

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

  使用信息增益比可以对这一问题进行校正。

• 特征 A 对训练数据集 D 的信息增益比 $g_R(D,A)$ 定义为其信息增益 $g(D,A)$ 与训练数据集 D 关于特征 A 的值的熵 $H_A(D)$ 之比，即

  $$g_R(D,A) = \frac{g(D,A)}{H_A(D)} \\ 其中，H_A(D) = - \sum \limits_{i=1}^{n} \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|}，n是特征 A 取值的个数$$

• 可以把 信息增益 改为 信息增益比 ，

  同样算法即可。

5.3 决策树的生成

ID3算法

• 输入
  • 训练数据集 D
  • 特征集 A 阈值 $\varepsilon$
• 输出
  • 决策树 $T$
• 算法
  1. 若 $D$ 中所有实例属于同一类 $C_k$ ，则 $T$ 为单结点树，并将类 $C_k$ 作为该结点的类标记，返回 $T$ ；
  2. 若 $A= \emptyset $ ，则 $T$ 为单结点树，并将 $D$ 中实例数最大的类 $C_k$ 作为该结点的类标记，返回 $T$ ；
  3. 否则，按 “信息增益”算法，计算 $A$ 中各特征对 $D$ 的信息增益，选择信息增益最大的特征 $A_g$ ；
  4. 如果 $A_g$ 的信息增益小于阈值 $\varepsilon$ ，则置 $T$ 为单结点树，并将 $D$ 中实例数最大的类 $C_k$ 作为该结点的类标记，返回 $T$ ；
  5. 否则，对 $A_g$ 的每一种可能值 $a_i$ ，依 $A_g = a_i$ 将 $D$ 分割为若干非空子集 $D_i$ ，将 $D_i$ 中实例数最大的类作为标记，构建子结点，由结点及其子节点构成构成树 $T$ ，返回 $T$ ；
  6. 对第 $i$ 个子结点，以 $D_i$ 为训练集，以 $A-\{A_g\}$ 为特征集，递归地调用步骤（1）–（5），得到子树$T_i$ ，返回 $T_i$ 。

C4.5算法

• 与 ID3算法一样，只是改进为使用信息增益比来选择特征。

5.4 决策树的剪枝

过于复杂的决策树

决策树生成算法递归地产生决策树，直到不能继续下去为止。

这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确——过拟合！

• 原因

  学习时，过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。

• 解决方法

  对已生成的决策树进行简化——剪枝。

  裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点。

• 方法

  通过极小化决策树整体的损失函数或代价函数来实现。

损失函数

• 损失函数

  $$C_\alpha (T) = \sum \limits_{t=1}^{|T|} N_t H_t (T) + \alpha |T| \\ 其中，经验熵 H_t(T) = - \sum \limits_{k} \frac{N_{tk} } {N_t} \log \frac{N_{tk} } {N_t} \\$$

  把右边第一项记作

  $$C(T) = \sum \limits_{t=1}^{|T|} N_t H_t(T) = - \sum \limits_{t=1}^{|T|} \sum \limits_{k=1}^{K} N_{tk} \log \frac{N_{tk} } {N_t}$$

  因此，简写为

  $$C_\alpha (T) = C(T) + \alpha |T|$$

  • 其中，$C(T)$ 表示模型对训练数据的预测误差，即模型与训练数据的拟合程度
  • $|T|$ 表示模型复杂度
  • 参数 $\alpha \geq 0$ 控制两者之间的影响
    • $\alpha$ 较大：选择更简单的模型
    • $\alpha$ 较小：选择更复杂的模型
    • $\alpha = 0$ ：只考虑训练数据的拟合程度，而不考虑模型的复杂度，此时模型很复杂。
  • 当 $\alpha$ 确定时，选择损失函数最小的模型（损失函数最小的子树）
    • 子树越大，往往与训练数据的拟合越好，但是模型复杂度越高；
    • 子树越小，模型复杂度越低，但往往与训练数据的拟合不好。

• 决策树的生成

  只考虑通过提高信息增益（或信息增益比）对训练数据进行更好的拟合。

  学习局部的模型。

• 决策树的剪枝

  通过优化损失函数并考虑减小模型复杂度。

  学习整体的模型。

算法

• 输入

  • 生成算法产生的整个树 $T$
  • 参数 $\alpha$

• 输出

  • 修剪后的子树 $T_\alpha$

• 算法

  1. 计算每个结点的经验熵。

  2. 递归地从树的叶结点向上回缩。

     设一组叶结点回缩到其父结点之前与之后的整体树分别为 $T_B$ 和 $T_A$ ，其对应的损失函数值分别是 $C_\alpha(T_B)$ 与 $C_\alpha(T_A)$ ，如果

     $$C_\alpha(T_A) \leq C_\alpha (T_B)$$

     则进行剪枝，即将父结点变为新的叶结点。

  3. 返回（2），直到不能继续为止，得到损失函数最小的子树 $T_\alpha$ 。

注意：

上式只需考虑两个树的损失函数的差，其计算可以在局部进行。

因此，本算法可以由一种动态规划的算法实现。

具体可参见 [文献10：Li H, Abe N. Generalizing case frames using a thesaurus and the MDL principle. Computatuional Linguistics, 1998, 24(2): 217-224.（无链接，请自查）]

5.5 CART 算法

• 分类与回归树 classification and regression tree, CART

  是应用广泛的决策树学习方法。

  • 同样由 特征选择、树的生成、树的剪枝组成。
  • 既可以用于分类，也可以用于回归，统称决策树。

• CART 简介

  CART是在给定输入随机变量 X 条件下输出随机变量 Y 的条件概率分布的学习方法。

  • CART假设决策树是二叉树，

    内部结点特征的取值为“是”（左分支）和“否”（右分支）。

  • 决策树等价于递归地二分每个特征，将输入空间（即特征空间）划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。

  • CART算法由下面两步组成：

    1. 决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大。
    2. 决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

CART 生成

• 构建二叉决策树
  • 回归树：平方误差最小化准则
  • 分类树：基尼指数 Gini index 最小化准则

回归树生成

最小二乘回归树生成算法

• 输入

  • 训练数据集 D

• 输出

  • 回归树 $f(x)$

• 算法

  在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树：

  1. 选择最优切分变量 $j$ 和切分点 $s$ ，求解

     $$\mathop{min}_{j,s} \Bigg[\mathop{min}_{c_1} \sum \limits_{x_i \in R_1(j,s)} (y_i-c_1)^2 + \mathop{min}_{c_2} \sum \limits_{x_i \in R_2(j,s) (y_i-c_2)^2} \Bigg]$$

     遍历变量 $j$ ，对固定的切分变量 $j$ 扫描切分点 $s$ ，选择使上式达到最小值的对 $(j,s)$ 。

  2. 用选定的对 $(j,s)$ 划分区域并决定相应的输出值：

     $$R_1(j,s) = \{ x|x^{(j)} \leq s \}, \, R_2(j,s) = \{ x|x^{(j)} > s \} \\ \hat{c_m} = \frac{1}{N_m} \sum \limits_{x_i \in R_m (j,s)} y_i, \, x \in R_m, \, m=1,2$$

  3. 继续对两个子区域调用步骤（1）（2）直至满足停止条件。

  4. 将输入空间划分为 $M$ 个区域 $R_1, R_2,...,R_M$ ，生成决策树：

     $$f(x) = \sum \limits_{m=1}^{M} \hat{c_m} I(x \in R_m)$$

基尼指数 Gini index

• 基尼指数 Gini index

  分类问题中，假设有 K 个类，样本点属于第 k 类的概率为 $p_k$ ，则概率分布的基尼指数定义为

  $$Gini(p) = \sum \limits_{k=1}^{K} p_k(1-p_k) = 1- \sum \limits_{k=1}^{K} p_k^2$$

  对于给定的样本集合 D，其基尼指数为

  $$Gini(D) = 1- \sum \limits_{k=1}^{K} \Big( \frac{|C_k|}{|D|} \Big)^2$$

  这里，$C_k$ 是 D 中属于第 k 类的样本子集， K 是类的个数。

  • 如果样本集合 D 根据特征 A 是否取某一值 a 被分割成 $D_1$ 和 $D_2$ 两部分，即

    $$D_1 = \{ (x,y)\in D|A(x) = a \}, \, D_2 = D -D_1$$

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

    $$Gini(D,A) = \frac{|D_1|}{|D|} Gini(D_1) + \frac{|D_2|}{|D|} Gini(D_2)$$

  • 基尼指数 $G(D)$ 表示集合 D 的不确定性。

    基尼指数 $G(D,A)$ 表示经 $A=a$ 分割后集合 D 的不确定性。

  • 基尼指数值越大，样本集合的不确定性越大，这一点与 熵 相似。

分类树生成

• CART 生成算法

• 输入

  • 训练数据集 D
  • 停止计算的条件

• 输出

  • CART 决策树

• 算法

  根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树：

  1. 设结点的训练数据集为 $D$ ，计算现有特征对该数据集的基尼指数。

     此时，对每一个特征 $A$ ，对其可能取的每个值 $a$ ，根据样本点对 $A =a$ 的测试为“是”或“否”将 $D$ 分割成 $D_1$ 和 $D_2$ 两部分，利用 $Gini(D,A)$ 式子计算 $A =a$ 时的基尼指数。

  2. 在所有可能的特征 $A$ 以及它们所有可能的切分点 $a$ 中，选择基尼指数最小的特征以及对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。

  3. 对两个子结点递归地调用（1）（2）直至满足停止条件。

  4. 生成 CART 决策树。

• 算法停止计算的条件（以下一种即可）

  • 结点中的样本个数小于预定阈值
  • 样本集的基尼指数小于预定阈值（即样本基本属于同一类）
  • 没有更多特征

CART 剪枝

• 输入

  CART 算法生成的决策树 $T_0$

• 输出

  最优决策树 $T_\alpha$

• 算法

  1. 设 $k=0,T=T_0$

  2. 设 $\alpha = + \infty$

  3. 自上而下地对各内部结点 $t$ 计算 $C(T_t)$ ，$|T_t|$ 以及

     $$g(t) = \frac{C(t)-C(T_t)}{|T_t|-1} \\ \alpha = \mathop{min} (\alpha , g(t))$$

     这里，$T_t$ 表示以 $t$ 为根结点的子树，$C(T_t)$ 是对训练数据的预测误差，$|T_t|$ 是 $T_t$ 的叶结点个数。

  4. 对 $g(t) = \alpha$ 的内部结点 $t$ 进行剪枝，并对叶结点 $t$ 以多数表决法决定其类，得到树 $T$ 。

  5. 设 $k=k+1,\alpha_k=\alpha, T_k=T$。

  6. 如果 $T_k$ 不是由根结点及两个叶结点构成的树，则回到步骤（2）；否则令 $T_k=T_n$ 。

  7. 采用交叉验证法在子树序列 $T_0,T_1,...,T_n$ 中选取最优子树 $T_\alpha$。

*5.6 示例

题目

寻找最优特征

ID3 算法

CART 算法

第6章 逻辑斯谛回归与最大熵模型

• 逻辑斯谛回归 logistic regression

  是统计学习的经典分类方法。

• 最大熵模型 maximum entropy

  最大熵原理推广到分类问题得到。

6.1 逻辑斯谛回归模型

逻辑斯谛分布

• 设 $X$ 是连续随机变量， $X$ 服从逻辑斯谛分布是指 $X$ 具有下列分布函数和密度函数：

  $$F(x) = P(X \leq x) = \frac{1}{1+e^{-(x-\mu)/\gamma} } \\ f(x) = F'(x) = \frac{e^{-(x-\mu)/\gamma} } {\gamma (1+e^{-(x-\mu)/\gamma})^2} \\ 其中，\mu为位置参数，\gamma > 0 为形状参数。$$

  • 函数图像见下。

  • 分布函数属于逻辑斯谛函数，其图形是一条 S 形曲线 sigmoid curve。

    该曲线以 $(\mu,\frac{1}{2})$ 为中心对称，即满足

    $$F(-x+\mu) - \frac{1}{2} = - F(x+\mu) + \frac{1}{2}$$

  • 曲线在中心附近i增长速度较快，在两端增长速度较慢。

  • 形状参数 $\gamma$ 的值越小，曲线在中心附近增长得越快。

二项逻辑斯谛回归模型

• 二项逻辑斯谛回归模型 binomial logistic regression model

  二项逻辑斯谛回归模型是如下的条件概率分布：

  $$P(Y=1|x) = \frac{\exp(w \cdot x + b)}{1+\exp(w \cdot x + b)} \\ P(Y=0|x) = \frac{1}{1+\exp(w \cdot x +b)} \\ 这里，x \in R^n 是输入， Y\in \{ 0,1 \}是输出，\\ w \in R^n 和 b \in R是参数,\\ w 称为权值向量， b 称为偏置， w \cdot x 为 w 和 x 的内积。$$

• 为了方便，可以改写如下：

  $$w = (w^{(1)}, w^{(2)}, ..., w^{(n)}, b)^T \\ x = (x^{(1)},x^{(2)},...,x^{(n)}, 1)^T$$

  此时，可以记为

  $$P(Y=1|x) = \frac{\exp(w \cdot x )}{1+\exp(w \cdot x )} \\ P(Y=0|x) = \frac{1}{1+\exp(w \cdot x )} \\$$

• 几率 odds

  指该事件发生的概率与该事件不发生的概率的比值。

  假设事件发生的概率是 $p$，那么该事件的几率是 $\frac{p}{1-p}$ 。

• 对数几率 log odds

  也称 logit 函数，即

  $$logit(p) = \log \frac{p}{1-p}$$

• 对于逻辑斯谛回归而言，对数几率

  $$\log \frac{P(Y=1|x)}{1-P(Y=1|x)} = w \cdot x$$

  因此，在逻辑斯谛回归模型中，输出 $Y=1$ 的对数几率是输入 x 的线性函数。

• 同样，反过来，

  通过逻辑斯谛回归模型定义式可以将线性函数 $w \cdot x$ 转换为概率：

  $$P(Y=1|x) = \frac{\exp(w\cdot x)}{1+\exp (w \cdot x)}$$

  • 线性函数的值越接近正无穷，概率值越接近1；

    线性函数的值越接近负无穷，概率值越接近0。

模型参数估计

• 可以应用极大似然估计，求出 $w$ 的估计值。

• 设

  $$P(Y=1|x) = \pi (x) , \, P(Y=0|x) = 1-\pi(x)$$

• 似然函数

  $$\prod \limits_{i=1}^{N} [\pi(x_i)]^{y_i}[1-\pi(x_i)]^{1-y_i}$$

• 对数似然函数

  $$\begin{aligned} L(w) &= \sum \limits_{i=1}^{N} [y_i \log \pi(x_i) + (1-y_i)\log (1-\pi(x_i))] \\ &= \sum \limits_{i=1}^{N} \Big[y_i \log \frac{\pi(x_i)}{1-\pi(x_i)} + \log (1-\pi(x_i))\Big] \\ &= \sum \limits_{i=1}^{N} [y_i (w \cdot x_i) - \log (1+ \exp (w \cdot x_i)] \\ \end{aligned}$$

• 对 $L(w)$ 求极大值，得到 $w$ 的估计值。

• 假设求出，则逻辑斯谛回归模型为

  $$P(Y=1|x) = \frac{\exp(\hat{w} \cdot x )}{1+\exp(\hat{w} \cdot x )} \\ P(Y=0|x) = \frac{1}{1+\exp(\hat{w} \cdot x )} \\$$

多项逻辑斯谛回归

• 上述是二项分类模型。

  可以推广为多项逻辑斯谛回归模型 multi-nominal logistic regression model，用于多项分类。

• 设离散型随机变量 $Y$ 的取值为 $\{ 1,2,...,K \}$ ，那么多项逻辑斯谛回归模型是

  $$P(Y=k|x) = \frac{\exp(w_k \cdot x )}{1+ \sum \limits_{k=1}^{K-1} \exp(w_k \cdot x )} , \, k=1,2,...,K-1\\ P(Y=K|x) = \frac{1}{1+ \sum \limits_{k=1}^{K-1} \exp(w_k \cdot x )} \\ 这里，x \in R^{n+1} ,w_k \in R^{n+1}。$$

• 而参数估计方法，仍然从二项逻辑斯谛的方法推广即可。

6.2 最大熵模型

最大熵原理

• 最大熵原理

  学习概率模型时，在所有可能的概率模型（分布）中，熵最大的模型是最好的模型。

  即，在满足约束条件的模型集合中选取熵最大的模型。

• 假设离散随机变量 $X$ 的概率分布是 $P(X)$ ，则其熵是

  $$H(P) = -\sum \limits_{x} P(x) \log P(x)$$

  熵满足不等式 $0 \leq H(P) \leq \log |X|$ ，其中绝对值表示取值个数。

  • 当且仅当 $X$ 的分布是均匀分布时，右边等号成立。

    因此，当 $X$ 服从均匀分布时，熵最大。

直观来看，最大熵原理认为，要选择的概率模型首先必须满足已有的事实，即约束条件。

在没有更多信息的情况下，那些不确定的部分都是“等可能的”。

要知道，等可能不容易操作，而最大熵原理通过熵的最大化来表示等可能性，从而成为一个可优化的数值指标。

最大熵模型

• 假设满足所有约束条件的模型集合为

  $$\mathcal{C} \equiv \{ P \in \mathcal{P} | E_P (f_i) = E_{\tilde{P} } (f_i), \, i=1,2,...,n \} \\$$

  定义在条件概率分布 $P(Y|X)$ 上的条件熵为

  $$H(P) = -\sum \limits_{x,y} \tilde{P} (x) P(y|x) \log P (y|x)$$

  则模型集合 $\mathcal{C}$ 中条件熵 $H(P)$ 最大的模型称为 最大熵模型。

  • 式子中对数为自然对数。

• 最大熵模型的学习

  求解最大熵模型的学习过程，可以转为约束最优化问题。

  就是求解：

  $$\mathop{min} \limits_{P \in \mathcal{C} } \, \, -H(P) = \sum \limits_{x,y} \tilde{P} (x) P(y|x) \log P (y|x) \\ \mathbf{s.t.} \,\,\,\, E_P(f_i) -E_{\tilde{P} } (f_i)=0 , \, i=1,2,...,n \\ \sum \limits_{y} P(y|x) = 1$$

• 具体解法可以引进拉格朗日乘子，定义拉格朗日函数，并转换为对偶问题（先证明原始问题与对偶问题的解等价），求偏导等于0，即可解出 $w^*$ 。

极大似然估计？

可以证明，对偶函数的极大似然估计等价于最大熵模型的极大似然估计。

6.3 模型学习的最优化算法

• 总结

  前面的 逻辑斯谛回归模型、最大熵模型学习归结为以似然函数为目标函数的最优化问题，通常通过迭代算法求解。

• 方法

  这时的目标函数具有很好的性质，是光滑的凸函数。

  因此多种最优化的方法都适用，保证能找到全局最优解。

  • 改进的迭代尺度法
  • 梯度下降法
  • 牛顿法
  • 拟牛顿法

  其中，牛顿法、拟牛顿法收敛速度更快。

改进的迭代尺度法 IIS

• 最大熵模型

  $$P_w(y|x) = \frac{1}{Z_w(x)} \exp \Big( \sum \limits_{i=1}^{n}w_if_i(x,y) \Big) \\ 其中，Z_w(x) = \sum \limits_{y} \exp \Big( \sum \limits_{i=1}^{n}w_if_i(x,y) \Big)$$

• 对数似然函数

  $$L(w) = \sum\limits_{x,y} \tilde{P}(x,y) \sum \limits_{i=1}^{n} w_if_i(x,y) - \sum \limits_x \tilde{P}(x)\log Z_w(x)$$

• 目标

  通过极大似然估计，求出对数似然函数的极大值 $\hat{w}$ 。

• 改进的迭代尺度法 improved iterative scaling, IIS

  一种最大熵模型学习的最优化算法。

  • IIS的想法是：假设当前参数向量是 $w=(w_1,w_2,...,w_n)^T$ ，我们希望找到一个新的参数向量 $w+\delta = (w_1+\delta_1,w_2+\delta_2,...,w_n+\delta_n)^T$ 使得对数似然函数值增大，然后更新 $w \rightarrow w +\delta$ 即可。

• 输入

  • 特征函数 $f_1, f_2,...,f_n$​
  • 经验分布 $\tilde{P} (X,Y)$
  • 模型 $P_w(y|x)$

• 输出

  • 最优参数值 $w_i^*$​
  • 最优模型 $P_{w^*}$

• 算法

  1. 对所有 $i \in \{ 1,2,...,n \}$，取初值 $w_i = 0$ 。

  2. 对每一 $i \in \{ 1,2,...,n \}$

     （a）令 $\delta_i$ 是方程

     $$\sum \limits_{x,y} \tilde{P} (x) P(y|x) f_i(x,y) \exp (\delta_i f^{ \# }(x,y)) = E_{\tilde{P} } (f_i) \\ 其中， f^\# (x,y) = \sum \limits_{i=1}^{n} f_i(x,y)$$

     的解。

     （b）更新 $w_i$ 的值： $w_i \leftarrow w_i + \delta_i$ 。

  3. 如果不是所有的 $w_i$ 都收敛，重复步骤（2）。

关键在于步骤（a），即求解 $\delta_i$ 。

拟牛顿法

• 最大熵模型

  $$P_w(y|x) = \frac{\exp \Big( \sum \limits_{i=1}^{n} w_i f_i(x,y) \Big)}{\sum \limits_y \exp \Big( \sum \limits_{i=1}^{n} w_if_i(x,y) \Big)}$$

• 目标函数

  $$\min_{w \in R^n} f(w) = \sum_x \tilde{P}(x) \log \sum_y \exp \Big( \sum \limits_{i=1}^{n} w_if_i(x,y)\Big) - \sum_{x,y} \tilde{P}(x,y) \sum \limits_{i=1}^{n} w_if_i(x,y)$$

• 梯度

  $$g(w) = \Big( \frac{\partial f(w)}{\partial w_1}, \frac{\partial f(w)}{\partial w_2},...,\frac{\partial f(w)}{\partial w_n} \Big)^T \\ 其中，\frac{\partial f(w)}{\partial w} = \sum_{x,y} \tilde{P} (x)P_w(y|x)f_i(x,y) - E_{\tilde{P} } (f_i), \, i=1,2,...,n$$

• 输入

  • 特征函数 $f_1, f_2,...,f_n$​
  • 经验分布 $\tilde{P} (X,Y)$
  • 目标函数 $f(w)$
  • 梯度 $g(w) = \nabla f(w)$
  • 精度要求 $\varepsilon$

• 输出

  • 最优参数值 $w_i^*$​
  • 最优模型 $P_{w^*}$

• 算法

  1. 选定初始点 $w^{(0)}$ ，取 $B_0$ 为正定对称矩阵，置 $k=0$ ；

  2. 计算 $g_k = g(w^{(k)})$ 。若 $||g_k|| < \varepsilon$ ，则停止计算，得 $w^* = w^{(k)}$ ；否则转（3）；

  3. 由 $B_kp_k = -g_k$ 求出 $p_k$ ；

  4. 一维搜索：求 $\lambda_k$ 使得

     $$f(w^{(k)}+\lambda_kp_k) = \min_{\lambda \geq 0} f(w^{(k)+\lambda p_k})$$

  5. 置 $w^{(k+1)}=w^{(k)}+\lambda_kp_k$ ；

  6. 计算 $g_{k+1} = g(w^{(k+1)})$ ，若 $||g_{k+1}|| < \varepsilon$ ，则停止计算，得 $w^* = w^{(k+1)}$ ；否则，按下面式子求出 $B_{k+1}$ ：

     $$B_{k+1} = B_k + \frac{y_ky_k^T}{y_k^T\delta_k}-\frac{B_k\delta_k\delta_k^TB_k}{\delta_k^TB_k\delta_k}\\ 其中，y_k=g_{k+1}-g_k, \\ \delta_k = w^{(k+1)-w^{(k)} }。$$

  7. 置 $k=k+1$ ，转（3）。

*6.4 示例

最大熵原理说明

最大熵模型

*第7章 支持向量机

注：支持向量机SVM 被认为可能已经淘汰的算法。

因此，仅阅览书籍，并没有写 Notes。

但是本章的内容是较长的，具体参见书籍[《统计学习方法》第二版 P111 - P154（无链接）]

以下只简单解释一下支持向量机，列出本章的目录，其余参见书籍。

• 支持向量机 support vector machines, SVM

  是一种二类分类模型。

  • 定义在特征空间上的间隔最大的线性分类器。
  • 间隔最大使它有别于感知机。
  • 还包括核技巧，使它成为实质上的非线性分类器。

• 支持向量机的学习策略

  间隔最大化

  • 可形式化为一个求解凸二次规划 convex quadratic programming 的问题。

    也等价于正则化的合页损失函数的最小化问题。

  • 支持向量机的学习算法是求解凸二次规划的最优化算法。

• 模型

  • 线性可分支持向量机 linear support vector machine in linearly separable case
  • 线性支持向量机 linear support vector machine
  • 非线性支持向量机 non-linear support vector machine

• 快速学习算法——序列最小最优化算法 SMO

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

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

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

7.4 序列最小最优化算法

第8章 Boosting

• Boosting

  是一种常用的统计学习方法，应用广泛且有效。

  • 在分类问题中，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类的性能。
  • 代表性的 AdaBoost 算法
  • 具体的实例 提升树 boosting tree

• 基本思想

  “三个臭皮匠顶个诸葛亮”

  对于复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断好。

• 可行性探究

  • 性能问题

    • 强可学习：一个概念（类），如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的。
    • 弱可学习：一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么就称这个概念是弱可学习的。

  • 奇妙等价

    后来证明 强可学习与弱可学习是等价的。

    一个概念是强可学习的充分必要条件就是这个概念是弱可学习的。

  • 因此，在学习中，如果已经发现了“弱学习算法”，

    那么就能将它 提升 boost 为“强学习算法”。

    • 发现“弱学习算法”就相对容易多了。
    • 具体实施提升，就是开发 Boosting 问题，最具有代表性的是 AdaBoost 算法。

• 基本步骤

  从弱学习算法出发，反复学习，得到一系列弱分类器（基本分类器），然后组合这些弱分类器，构成一个强分类器。

  • 大多数的 Boosting 都是改变训练数据的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。

  1. 每一轮如何改变训练数据的权值或概率分布？

     提高前一轮错误分类样本的权值，降低正确分类样本的权值。

  2. 如何将弱分类器组合成一个强分类器？

     AdaBoost 采用加权多数表决的方法。

     加大分类误差率小的弱分类器的权值，使其在表决中起到较大的作用；反之，减小。

8.1 AdaBoost 算法

• 输入

  • 训练数据集 $T=\{ (x_1,y_1),(x_2,y_2),...,(x_N,y_N) \}$ ，其中 $x_i\in \mathcal{X} \subseteq R^n, , y_i \in \mathcal{Y} = { -1,+1} $

  • 弱学习算法

• 输出

  最终分类器 $G(x)$

• 算法流程

  1. 初始化训练数据的权值分布

     $$D_1 = (w_{11},...,w_{1i},...,w_{1N}), \, w_{1i} = \frac{1}{N}, \, i=1,2,...,N$$

  2. 对 $m=1,2,...,M$

     （a）使用具有权值分布 $D_m$ 的训练数据集学习，得到基本分类器

     $$G_m(x) : \mathcal{X} \rightarrow \{ -1,+1 \}$$

     （b）计算 $G_m(x)$ 在训练数据集上的分类误差率

     $$e_m = \sum \limits_{i=1}^{N} P(G_m(x_i)\neq y_i) = \sum \limits_{i=1}^{N} w_{mi}I(G_m(x_i)\neq y_i)$$

     （c）计算 $G_m(x)$ 的系数

     $$\alpha_m = \frac{1}{2} \log \frac{1-e_m}{e_m} \\ 其中，对数为自然对数。$$

     （d）更新训练数据集的权值分布

     $$D_{m+1} = (w_{m+1,1}, \, ...,\, w_{m+i,i}, \, ...,\, w_{m+1,N}) \\ w_{m+1,i} = \frac{w_{mi} } {Z_m} \exp (-\alpha_my_iG_m(x_i)), \, i=1,2,...,N \\ 其中，Z_m 是规范化因子\\ Z_m = \sum \limits_{i=1}^{N} w_{mi} \exp (-\alpha_my_iG_m(x_i)) \\ 它使 D_{m+1} 成为一个概率分布。$$

  3. 构建基本分类器的线性组合

     $$f(x) = \sum \limits_{m=1}^{M} \alpha_m G_m(x)$$

     得到最终分类器

     $$\begin{aligned} G(x) &= sign(f(x)) \\ &= sign(\sum \limits_{m=1}^{M} \alpha_m G_m(x)) \end{aligned}$$

说明

• $G_m(x)$ 的系数 $\alpha_i$ 表示在$G_m(x)$ 在最终分类器中的重要性。

  当 $w_m \leq \frac{1}{2}$ 时，$\alpha_m \geq 0$ ，并且 $\alpha_m$ 随着 $e_m$ 的减小而增大，

  所以分类误差率越小的基本分类器在最终分类器中的作用越大。

• 更新后，误分类样本在下一轮学习中起更大的作用。

• 不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起到不同的作用，这是 AdaBoost 算法的一个特点。

• 线性组合 $f(x)$ 实现 $M$ 个基本分类器的加权表决。

8.2 AdaBoost 算法的训练误差分析

• AdaBoost 最基本的性质是它能在学习过程中不断减少训练误差，即在训练数据集上的分类误差率。

• AdaBoost 的训练误差界

  $$AdaBoost 算法最终分类器的训练误差界为\\ \frac{1}{N} \sum \limits_{i=1}^{N} I(G(x_i)\neq y_i) \leq \frac{1}{N} \sum \limits_{i} \exp (-y_if(x_i)) = \prod \limits_{m} Z_m \\ 其中，G(x) ,f(x)和Z_m 分别由AdaBoost算法中式子给出。$$

  • 这一定理说明

    在每一轮选取适当的 $G_m$ 使得 $Z_m$ 最小，从而使训练误差下降得最快。

• 特殊地，二类分类问题 AdaBoost 的训练误差界

  $$\begin{aligned} \prod \limits_{m=1}^{M} Z_m &= \prod \limits_{m=1}^{M} \bigg[2 \sqrt{e_m(1-e_m)} \bigg] \\ &= \prod \limits_{m=1}^{M} \sqrt{(1-4\gamma_m^2)} \\ &\leq \exp \Big( -2\sum \limits_{m=1}^{M} \gamma_m^2 \Big) \\ 其中，\gamma_m = \frac{1}{2} -e_m。 \end{aligned}$$

• 推论

  $$如果存在 \gamma >0 ，对所有 m 有 \gamma_m \geq \gamma ，则 \\ \frac{1}{N} \sum \limits_{i=1}^{N} I(G(x_i)\neq y_i) \leq \exp (-2M\gamma^2)$$

  • 这表明

    在此条件下，AdaBoost 的训练误差是以指数速率下降的。

• 注意

  AdaBoost 算法不需要知道下界 $\gamma$ 。

  与早期的 Boosting 不同， AdaBoost 具有适应性，即它能适应弱分类器各自的训练误差率。

  这就是它名字的由来 适应的提升，Adaptive Boosting。

8.3 AdaBoost 算法的解释

前向分步算法

• 输入

  • 训练数据集 $T=\{ (x_1,y_1),(x_2,y_2),...,(x_N,y_N) \}$ ；
  • 损失函数 $L(y,f(x))$ ；
  • 基函数集 $\{ b(x;\gamma) \}$

• 输出

  加法模型 $f(x)$

• 算法流程

  1. 最初化 $f_0(x)=0$ ；

  2. 对 $m=1,2,...,M$

     （a）极小化损失函数

     $$(\beta_m,\gamma_m) = \arg \min \limits_{\beta,\gamma} \sum \limits_{i=1}^{N} L(y_i,f_{m-1}(x_i)+\beta b(x_i;\gamma))$$

     得到参数 $\beta_m,\gamma_m$ 。

     （b）更新

     $$f_m(x) = f_{m-1}(x) + \beta_mb(x;\gamma)$$

  3. 得到加法模型

     $$f(x) = f_M(x) = \sum \limits_{m=1}^{M} \beta_mb(x;\gamma_m)$$

这样，前向分步算法将同时求解从 $m=1$ 到 $M$ 所有参数 $\beta_m,\gamma_m$ 的优化问题简化为

逐次求解各个 $\beta_m,\gamma_m$ 的优化问题。

联系 AdaBoost

• AdaBoost 算法是前向分步加法算法 的特例。

  这时：

  • 模型：由基本分类器组成的加法模型
  • 损失函数：指数函数

8.4 提升树

• 提升树是以分类树或回归树为基本分类器的 Boosting。

  提升树被认为是统计学习中性能最好的方法之一。

提升树模型

• Boosting 实际采用加法模型（即基函数的线性组合）与前向分步算法。

• 以决策树为基函数的 Boosting 称为提升树 boosting tree。

  • 二叉分类树
  • 二叉回归树

  $$f_M(x)= \sum \limits_{m=1}^{M} T(x;\Theta_m) \\ 其中，T(x;\Theta_m)表示决策树，\Theta_m为决策树的参数，M为树的个数。$$

分类问题的提升树算法

• 二类分类问题，提升树只需要将 前面AdaBoost 算法中的基本分类器限制为二类分类树即可。

  这时，可以说 提升树算法 是 AdaBoost 算法的特殊情况。

回归问题的提升树算法

• 输入

  训练数据集 $T=\{ (x_1,y_1),(x_2,y_2),...,(x_N,y_N) \}, \, x_i \in \mathcal{X} \subseteq R^n, \, y_i \in \mathcal{Y} \subseteq R$

• 输出

  提升树 $f_M(x)$

• 算法流程

  1. 初始化 $f_0(x) = 0$ 。

  2. 对于 $m=1,2,...,M$

     （a）按下式计算残差

     $$T(x;\Theta) = \sum \limits_{j=1}^{J} c_j I(x\in R_j) \\ 其中参数 \Theta = \{ (R_1,c_1),(R_2,c_2),...,(R_J,c_J) \} 表示树的区域划分和各区域上的常数。\\ J是回归树的复杂度，即叶结点个数。\\ r_{mi} = y_i-f_{m-1}(x_i), \, i=1,2,...,N$$

     （b）拟合残差 $r_{mi}$ 学习一个回归树，得到 $T(x;\Theta_m)$ 。

     （c）更新 $f_m(x) = f_{m-1}(x)+T(x;\Theta_m)$ 。

  3. 得到回归问题提升树

     $$f_M(x) = \sum \limits_{m=1}^{M} T(x;\Theta_m)$$

梯度提升

• 提升树当损失函数是平方损失和指数损失函数时，每一步的优化是很简单的。

• 但是对于一般损失函数而言，往往每一步优化并不那么容易。

  针对这个问题，Freidman 提出了梯度提升 gradient boosting 算法。

• 梯度提升

  利用最速下降法的近似方法，关键是利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值，拟合一个回归树。

• 输入

  • 训练数据集 $T=\{ (x_1,y_1),(x_2,y_2),...,(x_N,y_N) \}, \, x_i\in \mathcal{X} \subseteq R^n, \, y_i \in \mathcal{Y} \subseteq R$
  • 损失函数 $L(y,f(x))$

• 输出

  回归树 $\hat{f}(x)$

• 算法流程

  1. 初始化

     $$f_0(x) = \arg \min \limits_{c} \sum \limits_{i=1}^{N} L(y_i,c)$$

  2. 对 $m=1,2,..,M$

     （a）对 $i=1,2,...,N$ 计算

     $$r_{mi} = - \Big[ \frac{\partial{L(y_i,f(x_i))} } {\partial{f(x_i)} } \Big]_{f(x)=f_{m-1}(x)}$$

     （b）对 $r_{mi}$ 拟合一个回归树，得到第 $m$ 棵树的叶结点区域 $R_{mi}, \, j=1,2,...,J$ 。

     （c）对 $j=1,2,...,J$ 计算

     $$C_{mi} = \arg \min \limits_{c} \sum \limits_{x_i \in R_{mj} } L(y_i, f_{m-1}(x_i)+c)$$

     （d）更新 $f_m(x) = f_{m-1}(x)+\sum \limits_{j=1}^{J} c_{mj} I(x \in R_{mj})$

  3. 得到回归树

     $$\hat{f}(x) = f_M(x) = \sum \limits_{m=1}^{M} \sum \limits_{j=1}^{J} c_{mj} I(x \in R_{mj})$$

第2（a）步，计算损失函数的负梯度在当前模型的值，将它作为残差的估计。

• 对于平方损失函数，它就是通常所说的残差；
• 对于一般损失函数，它就是残差的近似值。

*8.5 示例

AdaBoost 算法

提升树

*第9章 EM算法及其推广

*第10章 隐马尔可夫模型

*第11章 条件随机场

本3章可以在需要使用时，再特定阅览，此处不再写 Notes。

可能另开 Notes 专门记录，关注其他 Notes。

第12章 监督学习方法总结

至此，监督学习篇章的所有内容已经结束！