Bagging

bagging：bootstrap aggregating，每个分类器随机从原样本 中做有放回的随机抽样，在抽样结果上训练基模型，最后根据 多个基模型的预测结果产生最终结果

• 核心为bootstrap重抽样自举

步骤

• 建模阶段：通过boostrap技术获得k个自举样本 $S_1, S_2,…, S_K$，以其为基础建立k个相同类型模型 $T_1, T_2,…, T_K$

• 预测阶段：组合K个预测模型

  • 分类问题：K个预测模型“投票”
  • 回归问题：K个预测模型平均值

模型性质

• 相较于单个基学习器，Bagging的优势
  • 分类Bagging几乎是最优的贝叶斯分类器
  • 回归Bagging可以通过降低方差（主要）降低均方误差

预测误差

总有部分观测未参与建模，预测误差估计偏乐观

• OOB预测误差：out of bag，基于袋外观测的预测误差， 对每个模型，使用没有参与建立模型的样本进行预测，计算预测 误差

• OOB观测比率：样本总量n较大时有

  $$r = (1 - \frac 1 n)^n \approx \frac 1 e = 0.367$$
  • 每次训练样本比率小于10交叉验证的90%

Random Forest

随机森林：随机建立多个有较高预测精度、弱相关（甚至不相关） 的决策树（基础学习器），多棵决策树共同对新观测做预测

• RF是Bagging的扩展变体，在以决策树为基学习器构建Bagging 集成模型的基础上，在训练过程中引入了随机特征选择

• 适合场景

  • 数据维度相对较低、同时对准确率有要求
  • 无需很多参数调整即可达到不错的效果

步骤

• 样本随机：Bootstrap自举样本

• 输入属性随机：对第i棵决策树通过随机方式选取K个输入变量 构成候选变量子集$\Theta_I$

  • Forest-Random Input：随机选择$k=log_2P+1或k=\sqrt P$ 个变量

  • Forest-Random Combination

    • 随机选择L个输入变量x
    • 生成L个服从均匀分布的随机数$\alpha$
    • 做线性组合 $vj = \sum{i=1}^L \alpha_i x_i, \alpha_i \in [-1, 1]$
    • 得到k个由新变量v组成的输入变量子集$\Theta_i$

• 在候选变量子集中选择最优变量构建决策树

  • 生成决策树时不需要剪枝

• 重复以上步骤构建k棵决策树，用一定集成策略组合多个决策树

  • 简单平均/随机森林投票

优点

• 样本抽样、属性抽样引入随机性

  • 基学习器估计误差较大，但是组合模型偏差被修正
  • 不容易发生过拟合、对随机波动稳健性较好
  • 一定程度上避免贪心算法带来的局部最优局限

• 数据兼容性

  • 能够方便处理高维数据，“不用做特征选择”
  • 能处理分类型、连续型数据

• 训练速度快、容易实现并行

• 其他

  • 可以得到变量重要性排序
  • 启发式操作
  • 优化操作

缺点

• 决策树数量过多时，训练需要资源多
• 模型解释能力差，有点黑盒模型

Gredient Boosting

GB：（利用）梯度提升，将提升问题视为优化问题，前向分步算法 利用最速下降思想实现

• 一阶展开拟合损失函数，沿负梯度方向迭代更新

  • 损失函数中，模型的样本预测值$f(x)$是因变量
  • 即$f(x)$应该沿着损失函数负梯度方向变化
  • 即下个基学习器应该以负梯度方向作为优化目标，即负梯度 作为伪残差

  • 类似复合函数求导

• 对基学习器预测值求解最优加权系数

  • 最速下降法中求解更新步长体现
  • 前向分布算法中求解基学习器权重

损失函数

基学习器拟合目标：损失函数的负梯度在当前模型的值

$$-\left [ \frac {\partial L(y, \hat y_i)} {\partial y_i} \right ]_{\hat y_i=\hat y_i^{(t-1)}}$$

平方损失

平方损失：$L(y, f(x)) = \frac 1 2 (y - f(x))^2$（回归）

• 第m-1个基学习器伪残差为

  $$r_{m,i} = y_i - f_{m-1}(x_i), i=1,2,\cdots,N$$

  • $N$：样本数量

• 第m个基学习器为

  $$\begin{align*} h_m & = \arg\min_h \sum_{i=1}^N \frac 1 2 (y_i - (f_{m-1}(x_i) + h(x)))^2 \\ & = \arg\min_h \sum_{i=1}^N \frac 1 2 (C_{m,i} - h(x))^2 \\ C_{m,i} & = y_i - f_{m-1}(x_i) \end{align*}$$

• 第m轮学习器组合为

  $$f_m = f_{m-1} + \alpha_m h_m$$

  • $\alpha_m$：学习率，留给之后基模型学习空间

  • 这里只是形式上表示模型叠加，实际上树模型等不可加， 应该是模型预测结果叠加

指数损失

指数损失：$L(y, f(x)) = e^{-y f(x)}$（分类）

• 第m-1个基学习器伪残差

  $$r_{m,i} = -y_i e^{-y_i f_{m-1}(x_i)}, i=1,2,\cdots,N$$

• 基学习器、权重为

  $$\begin{align*} h_m & = \arg\min_h \sum_{i=1}^N exp(-y_i(f_{m-1}(x_i) + \alpha f(x_i))) \\ & = \arg\min_h \sum_{i=1}^N C_{m,i} exp(-y_i \alpha f(x_i)) \\ C_{m,i} & = exp(-y_i f_{m-1}(x_i)) \end{align*}$$

• 第m轮学习器组合为

  $$f_m = f_{m-1} + \alpha_m h_m$$

步骤

• 输入：训练数据集$T={(x_1, y_1), \cdots, (x_N, y_N)}$， 损失函数$L(y, f(x))$

  • $x_i \in \mathcal{X \subset R^n}$
  • $y_i \in \mathcal{Y} = {-1, +1 }$

• 输出：回归树$\hat f(x)$

• 初始化模型

  $$\hat y_i^{(0)} = \arg\min_{\hat y} \sum_{i=1}^N L(y_i, \hat y)$$

• 对$m=1,2,\cdots,M$（即训练M个若分类器）

  • 计算伪残差

    $$r_i^{(t)} = -\left [ \frac {\partial L(y, \hat y_i)} {\partial y_i} \right ]_{\hat y_i=\hat y_i^{(t-1)}}$$

  • 基于${(x_i, r_i^{(t)})}$生成基学习器$h_t(x)$

  • 计算最优系数

    $$\gamma = \arg\min_\gamma \sum_{i=1}^N L(y_i, \hat y_i^{(t-1)} + \gamma h_t(x_i))$$

  • 更新预测值

    $$\hat y_i^{(t)} = \hat y_i^{(t-1)} + \gamma_t h_t (x)$$

• 得到最终模型

  $$\hat f(x) = f_M(x) = \sum_{t=1}^M \gamma_t h_t(x)$$

Gradient Boosted Desicion Tree

GBDT：梯度提升树，以回归树为基学习器的梯度提升方法

• GBDT会累加所有树的结果，本质上是回归模型（毕竟梯度）

  • 所以一般使用CART回归树做基学习器
  • 当然可以实现分类效果

• 损失函数为平方损失（毕竟回归），则相应伪损失/残差

  $$r_{t,i} = y_i - f_{t-1}(x_i), i=1,2,\cdots,N$$

特点

• 准确率、效率相较于RF有一定提升
• 能够灵活的处理多类型数据
• Boosting类算法固有的基学习器之间存在依赖，难以并行训练 数据，比较可行的并行方案是在每轮选取最优特征切分时，并行 处理特征

XGBoost

Extreme Gradient Boost/Newton Boosting：前向分步算法利用 Newton法思想实现

• 二阶展开拟合损失函数

  • 损失函数中，模型的样本预测值$\hat y_i$是因变量
  • 将损失函数对$\hat y_i$二阶展开拟合
  • 求解使得损失函数最小参数

• 对基学习器预测值求解最优加权系数

  • 阻尼Newton法求解更新步长体现
  • 前向分布算法中求解基学习器权重
  • 削弱单个基学习器影响，让后续基学习器有更大学习空间

损失函数

• 第t个基分类器损失函数

  $$\begin{align*} obj^{(t)} & = \sum_{i=1}^N l(y_i, \hat y_i^{(t)}) + \Omega(f_t) \\ & = \sum_i^N l(y_i, \hat y_i^{(t-1)} + f_t(x_i)) + \Omega(f_t) \\ & \approx \sum_{i=1}^N [l(y_i, \hat y^{(t-1)}) + g_i f_t(x_i) + \frac 1 2 h_i f_t^2(x_i)] + \Omega(f_t) \\ & = \sum_{i=1}^N [l(y_i, \hat y^{(t-1)}) + g_i f_t(x_i) + \frac 1 2 h_i f_t^2(x_i)] + \gamma T_t + \frac 1 2 \lambda \sum_{j=1}^T {w_j^{(t)}}^2 \\ \Omega(f_t) & = \gamma T_t + \frac 1 2 \lambda \sum_{j=1}^T {w_j^{(t)}}^2 \end{align*}$$

  • $f_t$：第t个基学习器
  • $f_t(x_i)$：第t个基学习器对样本$x_i$的取值
  • $gi = \partial{\hat y} l(y_i, \hat y^{t-1})$
  • $hi = \partial^2{\hat y} l(y_i, \hat y^{t-1})$
  • $\Omega(f_t)$：单个基学习器的复杂度罚
  • $T_t$：第t个基学习器参数数量，即$L_0$罚

    • 线性回归基学习器：回归系数数量
    • 回归树基学习器：叶子节点数目

  • $\gamma$：基学习器$L_0$罚系数，模型复杂度惩罚系数
  • $w_j = f_t$：第t个基学习器参数值，即$L_2$罚

    • 线性回归基学习器：回归系数值
    • 回归树基学习器：叶子节点

  • $\lambda$：基学习器$L_2$罚系数，模型贡献惩罚系数
  • $\approx$：由二阶泰勒展开近似

• 对损失函数进行二阶泰勒展开（类似牛顿法）拟合原损失函数， 同时利用一阶、二阶导数求解下个迭代点

• 正则项以控制模型复杂度

  • 降低模型估计误差，避免过拟合
  • $L_2$正则项也控制基学习器的学习量，给后续学习器留下 学习空间

树基学习器

XGBoost Tree：以回归树为基学习器的XGBoost模型

• 模型结构说明

  • 基学习器类型：CART
  • 叶子节点取值作惩罚：各叶子节点取值差别不应过大，否则 说明模型不稳定，稍微改变输入值即导致输出剧烈变化
  • 树复杂度惩罚：叶子结点数量

• XGBoost最终损失（结构风险）有

  $$\begin{align*} R_{srm} & = \sum_{i=1}^N l(y_i, \hat y_i) + \sum_{t=1}^M \Omega(f_t) \end{align*}$$

  • $N, M$：样本量、基学习器数量
  • $\hat y_i$：样本$i$最终预测结果

损失函数

• 以树作基学习器时，第$t$基学习器损失函数为

  $$\begin{align*} obj^{(t)} & = \sum_{i=1}^N l(y_i, \hat y_i^{(t)}) + \Omega(f_t) \\ & \approx \sum_{i=1}^N [l(y_i, \hat y^{(t-1)}) + g_i f_t(x_i) + \frac 1 2 h_i f_t^2(x_i)] + \gamma T_t + \frac 1 2 \lambda \sum_{j=1}^T {w_j^{(t)}}^2 \\ & = \sum_{j=1}^{T_t} [(\sum_{i \in I_j} g_i) w_j^{(t)} + \frac 1 2 (\sum_{i \in I_j} h_i + \lambda) {w_j^{(t)}}^2] + \gamma T_t + \sum_{i=1}^N l(y_i, \hat y^{(t)}) \\ & = \sum_{j=1}^{T_t} [G_i w_j^{(t)} + \frac 1 2 (H_j + \lambda){w_j^{(t)}}^2] + \gamma T_t + \sum_{i=1}^N l(y_i, \hat y^{(t)}) \\ & = \sum_{j=1}^{T_t} [G_i w_j^{(t)} + \frac 1 2 (H_j + \lambda)(w_j^{(t)})^2] + \gamma T_t + \sum_{i=1}^N l(y_i, \hat y^{(t)}) \\ \end{align*}$$

  • $f_t, T_t$：第t棵回归树、树叶子节点
  • $f_t(x_i)$：第t棵回归树对样本$x_i$的预测得分
  • $w_j^{(t)} = f_t(x)$：第t棵树中第j叶子节点预测得分
  • $gi = \partial{\hat y} l(y_i, \hat y^{t-1})$
  • $hi = \partial^2{\hat y} l(y_i, \hat y^{t-1})$
  • $I_j$：第j个叶结点集合
  • $Gj = \sum{i \in I_j} g_i$
  • $Hj = \sum{i \in I_j} h_i$

  • 对回归树，正则项中含有$(w_j^{(t)})^2$作为惩罚，能够 和损失函数二阶导合并，不影响计算

  • 模型复杂度惩罚项惩罚项是针对树的，定义在叶子节点上， 而平方损失是定义在样本上，合并时将其改写

• 第t棵树的整体损失等于其各叶子结点损失加和，且 各叶子结点取值之间独立

  • 则第t棵树各叶子结点使得损失最小的最优取值如下 （$G_j, H_j$是之前所有树的预测得分和的梯度取值，在 当前整棵树的构建中是定值，所以节点包含样本确定后， 最优取值即可确定）

    $$w_j^{(*)} = -\frac {\sum_{i \in I_j} g_i} {\sum_{i \in I_j} h_i + \lambda} = -\frac {G_j} {H_j + \lambda}$$

  • 整棵树结构分数（最小损失）带入即可得

    $$obj^{(t)} = -\frac 1 2 \sum_{j=i}^M \frac {G_j^2} {H_j + \lambda} + \gamma T$$

  • 则在结点分裂为新节点时，树损失变化量为

    $$l_{split} = \frac 1 2 \left [ \frac {(\sum_{i \in I_L} g_i)^2} {\sum_{i \in I_L h_i} + \lambda} + \frac {(\sum_{i \in I_R} g_i)^2} {\sum_{i \in I_R h_i} + \lambda} - \frac {(\sum_{i \in I} g_i)^2} {\sum_{i \in I h_i} + \lambda} \right ] - \gamma$$

    • $I_L, I_R$：结点分裂出的左、右结点

• 则最后应根据树损失变化量确定分裂节点、完成树的分裂，精确 贪心分裂算法如下

  !xgb_exact_greedy_algorithm_for_split_finding

  • 对于连续型特征需遍历所有可能切分点

    • 对特征排序
    • 遍历数据，计算上式给出的梯度统计量、损失变化

  • 不适合数据量非常大、或分布式场景

模型细节

• shrinkage：对新学习的树使用系数$\eta$收缩权重

  • 类似SGD中学习率，降低单棵树的影响，给后续基模型留下 学习空间

• column subsampling：列抽样

  • 效果较传统的行抽样防止过拟合效果更好 （XGB也支持行抽样）
  • 加速计算速度

XGB树分裂算法

• 线性回归作为基学习器时，XGB相当于L0、L2正则化的 Logistic回归、线性回归

近似分割算法

XGB近似分割算法：根据特征分布选取分位数作为候选集，将连续 特征映射至候选点划分桶中，统计其中梯度值、计算最优分割点

!xgb_approximate_algorithm_for_split_finding

• 全局算法：在树构建初始阶段即计算出所有候选分割点，之后 所有构建过程均使用同样候选分割点

  • 每棵树只需计算一次分割点的，步骤少
  • 需要计算更多候选节点才能保证精度

• 局部算法：每次分裂都需要重新计算候选分割点

  • 计算步骤多
  • 总的需要计算的候选节点更少
  • 适合构建较深的树

• 分位点采样算法参见 ml_model/model_enhancement/gradient_boost

Sparsity-aware Split Finding

稀疏特点分裂算法：为每个树节点指定默认分裂方向，缺失值对应 样本归为该方向

• 仅处理非缺失值，算法复杂度和随无缺失数据集大小线性增加， 减少计算量

• 按照升许、降序分别扫描样本两轮，以便将缺失值样本分别归为 两子节点，确定最优默认分裂方向

  

XGB系统设计

Column Block for Parallel Learning

• 建树过程中最耗时的部分为寻找最优切分点，而其中最耗时部分 为数据排序

XGB对每列使用block结构存储数据

• 每列block内数据为CSC压缩格式

  • 特征排序一次，之后所有树构建可以复用（忽略缺失值）
  • 存储样本索引，以便计算样本梯度
  • 方便并行访问、处理所有列，寻找分裂点

• 精确贪心算法：将所有数据（某特征）放在同一block中

  • 可同时对所有叶子分裂点进行计算
  • 一次扫描即可得到所有叶子节点的分割特征点候选者统计 数据

• 近似算法：可以使用多个block、分布式存储数据子集

  • 对local策略提升更大，因为local策略需要多次生成分位点 候选集

Cache-aware Access

• 列block结构通过索引获取数据、计算梯度，会导致非连续内存 访问，降低CPU cache命中率

• 精确贪心算法：使用cache-aware prefetching

  • 对每个线程分配连续缓冲区，读取梯度信息存储其中，再 统计梯度信息
  • 对样本数量较大时更有效

• 近似算法：合理设置block大小为block中最多的样本数

  • 过大容易导致命中率低、过小导致并行化效率不高

Blocks for Out-of-core Computation

• 数据量过大不能全部存放在主存时，将数据划分为多个block 存放在磁盘上，使用独立线程将block读入主存 （这个是指数据划分为块存储、读取，不是列block）

• 磁盘IO提升

  • block compression：将block按列压缩，读取后使用额外 线程解压
  • block sharding：将数据分配至不同磁盘，分别使用线程 读取至内存缓冲区

分位点采样算法—XGB

Quantile Sketch

样本点权重

• 根据已经建立的$t-1$棵树可以得到数据集在已有模型上误差， 采样时根据误差对样本分配权重，对误差大样本采样粒度更大

• 将树按样本点计算损失改写如下

  $$\sum_{i=1}^N \frac 1 2 h_i(f_t(x_i) - \frac {g_i} {h_i})^2 + \Omega(f_t) + constant$$

• 则对各样本，其损失为$f_t(x_i) - \frac {g_i} {h_i}$ 平方和$h_i$乘积，考虑到$f_t(x_i)$为样本点在当前树预测 得分，则可以

  • 将样本点损失视为“二次损失”
  • 将$\frac {g_i} {h_i}$视为样本点“当前标签”
  • 相应将$h_i$视为样本点权重

• 样本权重取值示例

  • 二次损失：$h_i$总为2，相当于不带权
  • 交叉熵损失：$h_i=\hat y(1-\hat y)$为二次函数， 则$\hat y$接近0.5时权重取值大，此时该样本预测值 也确实不准确，符合预期

Rank函数

• 记集合$D={(x_1, h_1), \cdots, (x_n, h_n)}$

• 定义rank函数$r_D: R \rightarrow [0, +\infty)$如下

  $$r_D(z) = \frac 1 {\sum_{(x, h) \in D} h} \sum_{(x, h) \in D, x < z} h$$
  • 即集合$D$中权重分布中给定取值分位数
  • 即取值小于给定值样本加权占比，可视为加权秩

分位点抽样序列

• 分位点抽样即为从集合$D$特征值中抽样，找到升序点序列 $S = {s_1, \cdots, s_l}$满足

  $$|r_D(s_j - r_D(s_{j+1})| < \epsilon$$

  • $\epsilon$：采样率，序列长度$l = 1/\epsilon$
  • $s1 = \min{i} x_i$：特征最小值

  • $sl = \max{i} x_i$：特征最大值

  • 各样本等权分位点抽样已有成熟方法，加权分位点抽样方法 为XGB创新，如下

Weighted Quantile Sketch

Formalization

• 记$Dk={(x{1,k}, h1), \cdots, (x{n,k}, h_n)}$为各 训练样本第$k$维特征、对应二阶导数

  • 考虑到数据点可能具有相同$x, h$取值，$D_k$为可能包含 重复值的multi-set

• 对于多重集$D$，额外定义两个rank函数

  $$\begin{align*} r_D^{-}(y) & = \sum_{(x,h) \in D, x<y} h \\ r_D^{+}(y) & = \sum_{(x,h) \in D, x \leq y} h \end{align*}$$

  定义相应权重函数为

  $$w_D(y) = r_D^{+}(y) - r_D^{-}(y) = \sum_{(x,h) \in D, x=y} h$$

• 多重集$D$上全部权重和定义为

  $$w(D) = \sum_{(x, w) \in D} w$$

Quantile Summary of Weighted Data

• 定义加权数据上的quantile summary为 $Q(D)=(S, \tilde r_D^{+}, \tilde r_D^{-}, \tilde w_D)$

  • $S$为$D$中特征取值抽样升序序列，其最小、最大值分别 为$D$中特征最小、最大值

  • $\tilde r_D^{+}, \tilde r_D^{-}, \tilde w_D$为定义在 $S$上的函数，满足

    $$\begin{align*} \tilde r_D^{-}(x_i) & \leq r_D^{-}(x_i) \\ \tilde r_D^{+}(x_i) & \leq r_D^{+}(x_i) \\ \tilde w_D(x_i) & \leq w_D(x_i) \\ \tilde r_D^{-}(x_i) + \tilde w_D(x_i) & \leq \tilde r_D^{-}(x_{i+1}) \\ \tilde r_D^{+}(x_i) + \tilde w_D(x_i) & \leq \tilde r_D^{+}(x_{i+1}) \\ \end{align*}$$

• $Q(D)$满足如下条件时，称为 $\epsilon$-approximate quantile summary

  $$\forall y \in D_X, \tilde r_D^{+}(y) - \tilde r_D(y) - \tilde w_D(y) \leq \epsilon w(D)$$
  • 即对任意$y$的秩估计误差在$\epslion$之内

• $\phi-quantile$：秩位于$\phi * N$的元素（一般向下取整）
• $\epsilon-\phi-quantile$：秩位于区间 $[(\phi-\epsilon)N, (\phi+\epsilon)N]$的元素

构建$\epsilon$-Approximate Qunatile Summary

• 初始化：在小规模数据集 $D={(x_1,h_1), \cdots, (x_n,h_n)}$上构建初始 初始quantile summary $Q(D)=(S, \tilde r_D^{+}, \tilde r_D^{-}, \tilde w_D)$ 满足

  $$\begin{align*} \tilde r_D^{-}(x_i) & \leq r_D^{-}(x_i) \\ \tilde r_D^{+}(x_i) & \leq r_D^{+}(x_i) \\ \tilde w_D(x_i) & \leq w_D(x_i) \end{align*}$$
  • 即初始化$Q(D)$为0-approximate summary

• merge operation：记 $Q(D1)=(S_1, \tilde r{D1}^{+}, \tilde r{D1}^{-}, \tilde w{D1})$、 $Q(D_2)=(S_2, \tilde r{D2}^{+}, \tilde r{D2}^{-}, \tilde w{D_2})$、 $D = D_1 \cup D_2$，则归并后的 $Q(D)=(S, \tilde r_D^{+}, \tilde r_D^{-}, \tilde w_D)$ 定义为

  $$\begin{align*} S & S_1 \cup S_2 \\ \tilde r_D^{-}(x_i) & = \tilde r_{D_1}^{-}(x_i) + \tilde r_{D_2}^{-}(x_i) \\ \tilde r_D^{+}(x_i) & = \tilde r_{D_1}^{+}(x_i) + \tilde r_{D_2}^{+}(x_i) \\ \tilde w_D(x_i) & = \tilde w_{D_1}(x_i) + \tilde w_{D_2}(x_i) \end{align*}$$

• prune operation：从给定 $Q(D)=(S, \tilde r_D^{+}, \tilde r_D^{-}, \tilde w_D)$， （其中$S = {x_1, \cdots, x_k }$），构建新的summary $\acute Q(D)=(\acute S, \tilde r_D^{+}, \tilde r_D^{-}, \tilde w_D)$

  • 仅定义域从$S$按如下操作抽取 $\acute S={\acute x1, \cdots, \acute x{b+1}}$

    $$\acute x_i = g(Q, \frac {i-1} b w(D))$$

  • $g(Q, d)$为查询函数，对给定quantile summary $Q$、 秩$d$返回秩最接近$d$的元素

    

自编码机/稀疏编码/堆栈自编码器

• 起源：编码理论可以应用于视觉皮层感受野，大脑主要视觉皮层 使用稀疏原理创建可以用于重建输入图像的最小基函数子集

• 优点

  • 简单技术：重建输入
  • 可堆栈多层
  • 直觉型，基于神经科学研究

• 缺点

  • 贪婪训练每层
  • 没有全局优化
  • 表现较监督学习差
  • 多层容易失效
  • 输入的重建可能不是学习通用表征的理想metric

总述

expectation maximization algorithm：含有隐变量的概率模型 参数的极大似然估计法、极大后验概率估计法

• 模型含有latent variable（潜在变量）、hidden variable （隐变量）似然函数将没有解析解

• 所以EM算法需要迭代求解，每次迭代由两步组成

  • E步：求期望expectation
  • M步：求极大maximization

• 模型变量都是observable variable、给定数据情况下，可以 直接使用极大似然估计、贝叶斯估计

EM算法

对含有隐变量的概率模型，目标是极大化观测数据（不完全数据） $Y$关于参数$\theta$的对数似然函数，即极大化

$$\begin{align*} L(\theta) & = log P(Y|\theta) \\ & = log \sum_Z P(Y, Z|\theta) \\ & = log \left(\sum_Z P(Y|Z,\theta) P(Z|\theta) \right) \end{align*}$$

• $Y$：观测变量数据
• $Z$：隐随机变量数据（未知）
• $Y,Z$合在一起称为完全数据
• $P(Y,Z|\theta)$：联合分布
• $P(Z|Y,\theta)$：条件分布

• 但是极大化目标函数中包括未观测数据$Z$、求和（积分）的 对数，直接求极大化非常困难
• EM算法通过迭代逐步近似极大化$L(\theta)$

推导

• 假设第i次迭代后$\theta$的估计值是$\theta^{(i)}$，希望 新估计值$\theta$能使$L(\theta)$增加，并逐步增加到极大值 ，考虑两者之差

  $$L(\theta) - L(\theta^{(i)}) = log (\sum_Z P(Y|Z,\theta) P(Z|\theta)) - log P(Y|\theta^{(i)})$$

• 利用Jensen不等式有

  $$\begin{align*} L(\theta) - L(|\theta^{(i)}) & = log(\sum_Z P(Y|Z, \theta^{(i)}) \frac {P(Y|Z,\theta) P(Z|\theta)} {P(Y|Z,\theta^{(i)})}) - log P(Y|\theta^{(i)}) \\ & \geq \sum_Z P(Z|Y,\theta^{(i)}) log \frac {P(Y|Z,\theta) P(Z|\theta)} {P(Z|Y,\theta^{(i)})} - log P(Y|\theta^{(i)}) \\ & = \sum_z P(Z|Y,\theta^{(i)}) log \frac {P(Y|Z,\theta) P(Z|\theta)} {P(Z|Y,\theta^{(i)}) P(Y|\theta^{(i)})} \end{align*}$$

• 令

  $$B(\theta, \theta^{(i)}) = L(\theta^{(i)}) + \sum_Z P(Z|Y,\theta^{(i)}) log \frac {P(Y|Z,\theta) P(Z|\theta)} {P(Z|Y,\theta^{(i)}) P(Y|\theta^{(i)})}$$

  则$B(\theta, \theta^{(i)})$是$L(\theta)$的一个下界，即

  $$\begin{align*} L(\theta) & \geq B(\theta, \theta^{(i)}) \\ \end{align*}$$

  并根据$B(\theta, \theta^{(i)})$定义有

  $$\begin{align*} L(\theta^{(i)}) = B(\theta^{(i)}, \theta^{(i)}) \end{align*}$$

• 则任意$\theta$满足 $B(\theta,\theta^{(i)}) > B(\theta^{(i)},\theta^{(i)})$ ，将满足$L(\theta) > L(\theta^{(i)})$，应选择 $\theta^{(i+1)}$使得$B(\theta,\theta^{(i)})$达到极大

  $$\begin{align*} \theta^{(i+1)} & = \arg\max_{\theta} B(\theta,\theta^{(i)}) \\ & = \arg\max_{\theta} L(\theta^{(i)}) + \sum_Z P(Z|Y,\theta^{(i)}) log \frac {P(Y|Z,\theta) P(Z|\theta)} {P(Z|Y,\theta^{(i)}) P(Y|\theta^{(i)})} \\ & = \arg\max_{\theta} (\sum_Z P(Z|Y,\theta^{(i)}) log(P(Y|Z,\theta)P(Z|\theta))) \\ & = \arg\max_{\theta} (\sum_Z P(Z|Y,\theta^{(i)}) log P(Y,Z|\theta)) \\ & = \arg\max_{\theta} Q(\theta, \theta^{(i)}) \end{align*}$$

  • 和$\theta$无关的常数项全部舍去

• $Q(\theta, \theta^{(i)})$：Q函数，完全数据的对数似然函数 $logP(Y,Z|\theta)$，关于在给定观测$Y$和当前参数 $\theta^{(i)}$下，对未观测数据Z的条件概率分布 $P(Z|Y,\theta^{(i)})$ $$Q(\theta, \theta^{(i)}) = E_z [logP(Y,Z|\theta)|Y,\theta^{(i)}]$$

算法

1. 选择参数初值$\theta^{0}$，开始迭代

2. E步：记$\theta^{(i)}$为第$i$迭代时，参数$\theta$的估计值 ，在第$i+1$步迭代的E步时，计算Q函数 $Q(\theta, \theta^{(i)})$

3. M步：求使得Q函数极大化$\theta$作为第$i+1$次估计值 $\theta^{(i+1)}$

   $$\theta^{(i+1)} = \arg\max_{\theta} Q(\theta, \theta^{(i)})$$

4. 重复E步、M步直到待估参数收敛

• 算法初值可以任意选择，但EM算法对初值敏感

• E步：参数值估计缺失值分布，计算Q函数（似然函数）

• M步：Q函数取极大得新参数估计值

• 收敛条件一般是对较小正数$\epsilon$，满足 $|\theta^{(i+1)} - \theta^{(i)}| < \epsilon$或 $|Q(\theta^{(i+1)},\theta^{(i)}) - Q(\theta^{(i)},\theta^{(i)})| < \epsilon$

EM算法特点

EM算法优点

• EM算法可以用于估计含有隐变量的模型参数
• 非常简单，稳定上升的步骤能非常可靠的找到最优估计值
• 应用广泛，能应用在多个领域中
  • 生成模型的非监督学习

EM算法缺点

• EM算法计算复杂、受外较慢，不适合高维数据、大规模数据集
• 参数估计结果依赖初值，不够稳定，不能保证找到全局最优解

算法收敛性

定理1

• 设$P(Y|\theta)$为观测数据的似然函数，$\theta^{(i)}$为 EM算法得到的参数估计序列，$P(Y|\theta^{(i)}),i=1,2,…$ 为对应的似然函数序列，则$P(Y|\theta^{(i)})$是单调递增的 $$P(Y|\theta^{(i+1)}) \geq P(Y|\theta^{(i)})$$

• 由条件概率

  $$\begin{align*} P(Y|\theta) & = \frac {P(Y,Z|\theta)} {P(Z|Y,\theta)} \\ logP(Y|\theta) & = logP(Y,Z|\theta) - logP(Z|Y,\theta) \end{align*}$$

• 则对数似然函数有

  $$logP(Y|\theta) = Q(\theta, \theta^{(i)}) - H(\theta, \theta^{(i)})$$

  • $H(\theta, \theta^{(i)}) = \sum_Z log P(Z|Y,\theta) P(Z|Y,\theta)$
  • $Q(\theta, \theta^{(i)})$：前述Q函数
  • $logP(Y|\theta)$和$Z$无关，可以直接提出

• 分别取$\theta^{(i+1)}, \theta^{(i)}$带入，做差

  $$logP(Y|\theta^{(i+1)}) - logP(Y|\theta^{(i)}) = [Q(\theta^{(i+1)}, \theta^{(i)}) - Q(\theta^{(i)}, \theta^{(i)}] - [H(\theta^{(i+1)}, \theta^{(i)}) - H(\theta^{(i)}, \theta^{(i)})]$$

  • $\theta^{(i+1)}$使得$Q(\theta, \theta^{(i)})$取极大

  • 又有

    $$\begin{align*} & H(\theta^{(i+1)}, \theta^{(i)}) - H(\theta^{(i)}, \theta^{(i)}) \\ = & \sum_Z (log \frac {P(Z|Y,\theta^{(i+1)})} {P(Z|Y,\theta^{(I)})}) P(Z|Y,\theta^{(i)}) \\ \leq & log (\sum_Z \frac {P(Z|Y,\theta^{(i+1)})} {P(Z|Y,\theta^{(I)})} P(Z|Y,\theta^{(i)})) \\ = & log \sum_Z P(Z|Y,\theta^{(i+1)}) = 0 \end{align*}$$

定理2

• 设$L(\theta)=log P(Y|\theta)$为观测数据的对数似然函数， $\theta^{(i)},i=1,2,…$为EM算法得到的参数估计序列， $L(\theta^{(i)}),i=1,2,…$为对应的对数似然函数序列

  • 若$P(Y|\theta)$有上界，则$L(\theta^{(i)})$收敛到某 定值$L^{*}$
  • Q函数$Q(\theta, \theta^{‘})$与$L(\theta)$满足一定 条件的情况下，由EM算法得到的参数估计序列 $\theta^{(i)}$的收敛值$\theta^{*}$是$L(\theta)$的 稳定点

• 结论1由序列单调、有界显然

• Q函数$Q(\theta, \theta^{‘})$与$L(\theta)$的条件在大多数 情况下是满足的
• EM算法收敛性包含对数似然序列$L(\theta^{(i)})$、参数估计 序列$\theta^{(i)}$的收敛性，前者不蕴含后者
• 此定理只能保证参数估计序列收敛到对数似然序列的稳定点， 不能保证收敛到极大点，可选取多个不同初值迭代，从多个结果 中选择最好的

Gaussion Mixture Model

• 高斯混合模型是指具有如下概率分布模型 $$P(y|\theta) = \sum_{k=1}^K \alpha_k \phi(y|\theta_k)$$

  • $\alphak \geq 0, \sum{k=1}^K \alpha_k=1$：系数
  • $\phi(y|\theta_k)$：高斯分布密度函数
  • $\theta_k=(\mu_k, \sigma_k)$：第k个分模型参数

• 用EM算法估计高斯混合模型参数 $\theta=(\alpha_1,…,\alpha_2,\theta_1,…,\theta_K)$

推导

明确隐变量

明确隐变量，写出完全数据对数似然函数

• 反映观测数据$y_j$来自第k个分模型的数据是未知的

  $$\gamma_{j,k} = \left \{ \begin{array}{l} 1, & 第j个观测来自第k个分模型 \\ 0, & 否则 \end{array} \right.$$

  • $j=1,2,\cdots,N$：观测编号
  • $k=1,2,\cdots,K$：模型编号

• 则完全数据为

  $$(y_j,\gamma_{j,1},\cdots,\gamma_{j,K}), j=1,2,...,N$$

• 完全数据似然函数为

  $$\begin{align*} P(y,\gamma|\theta) & = \prod_{j=1}^N P(y_j,\gamma_{j,1},\cdots,\gamma_{j,N}|\theta) \\ & = \prod_{k=1}^{K} \prod_{j=1}^N [\alpha_k \phi(y_j|\theta_k)]^{\gamma _{j,k}} \\ & = \prod_{k=1}^{K} \alpha_k^{n_k} \prod_{j=1}^N [\phi(y_j|\theta_k)]^{\gamma _{j,k}} \\ \end{align*}$$

  • $nk = \sum{j=1}^{N} \gamma_{j,k}$
  • $\sum_{k=1}^K n_k = N$

• 完全数据的对数似然函数为

  $$logP(y, \gamma|\theta) = \sum_{k=1}^K \left \{ n_k log \alpha_k + \sum_{j=1}^N \gamma_{j,k} [log \frac 1 {\sqrt {2\pi}} - log \sigma_k - \frac 1 {2\sigma_k}(y_j - \mu_k)^2] \right \}$$

E步：确定Q函数

$$\begin{align*} Q(\theta, \theta^{(i)}) & = E_z[logP(y,\gamma|\theta)|Y,\theta^{(i)}] \\ & = E \sum_{k=1}^K \left \{ n_k log\alpha_k + \sum_{j=1}^N \gamma_{j,k} [log \frac 1 {\sqrt {2\pi}} - log \sigma_k - \frac 1 {2\sigma_k}(y_j - \mu_k)^2] \right \} \\ & = \sum_{k=1}^K \left \{ \sum_{k=1}^K (E\gamma_{j,k}) log\alpha_k + \sum_{j=1}^N (E\gamma_{j,k}) [log \frac 1 {\sqrt {2\pi}} - log \sigma_k - \frac 1 {2\sigma_k}(y_j - \mu_k)^2] \right \} \end{align*}$$

• $E\gamma{j,k} = E(\gamma{j,k}|y,\theta)$：记为 $\hat \gamma_{j,k}$

$$\begin{align*} \hat \gamma_{j,k} & = E(\gamma_{j,k}|y,\theta) = P(\gamma_{j,k}|y,\theta) \\ & = \frac {P(\gamma_{j,k}=1, y_j|\theta)} {\sum_{k=1}^K P(\gamma_{j,k}=1,y_j|\theta)} \\ & = \frac {P(y_j|\gamma_{j,k}=1,\theta) P(\gamma_{j,k}=1|\theta)} {\sum_{k=1}^K P(y_j|\gamma_{j,k}=1,\theta) P(\gamma_{j,k}|\theta)} \\ & = \frac {\alpha_k \phi(y_j|\theta _k)} {\sum_{k=1}^K \alpha_k \phi(y_j|\theta_k)} \end{align*}$$

带入可得

$$Q(\theta, \theta^{(i)}) = \sum_{k=1}^K \left\{ n_k log\alpha_k + \sum_{k=1}^N \hat \gamma_{j,k} [log \frac 1 {\sqrt{2\pi}} - log \sigma_k - \frac 1 {2\sigma^2}(y_j - \mu_k)^2] \right \}$$

M步

求新一轮模型参数 $\theta^{(i+1)}=(\hat \alpha_1,…,\hat \alpha_2,\hat \theta_1,…,\hat \theta_K)$

$$\begin{align*} \theta^{(i+1)} & = \arg\max_{\theta} Q(\theta,\theta^{(i)}) \\ \hat \mu_k & = \frac {\sum_{j=1}^N \hat \gamma_{j,k} y_j} {\sum_{j=1}^N \hat \gamma_{j,k}} \\ \hat \sigma_k^2 & = \frac {\sum_{j=1}^N \hat \gamma_{j,k} (y_j - \mu_p)^2} {\sum_{j=1}^N \hat \gamma_{j,k}} \\ \hat \alpha_k & = \frac {n_k} N = \frac {\sum_{j=1}^N \hat \gamma_{j,k}} N \end{align*}$$

• $\hat \theta_k = (\hat \mu_k, \hat \sigma_k^2)$：直接求 偏导置0即可得
• $\hat \alphak$：在$\sum{k=1}^K \alpha_k = 1$条件下求 偏导置0求得

算法

• 输入：观测数据$y_1, y_2,\cdots, y_N$，N个高斯混合模型
• 输出：高斯混合模型参数

1. 取参数初始值开始迭代

2. E步：依据当前模型参数，计算分模型k对观测数据$y_j$响应度

   $$\hat \gamma_{j,k} = \frac {\alpha \phi(y_k|\theta_k)} {\sum_{k=1}^N \alpha_k \phi(y_j|\theta)}$$

3. M步：计算新一轮迭代的模型参数 $\hat mu_k, \hat \sigma_k^2, \hat \alpha_k$

4. 重复2、3直到收敛

• GMM模型的参数估计的EM算法非常类似K-Means算法

  • E步类似于K-Means中计算各点和各聚类中心之间距离，不过 K-Means将点归类为离其最近类，而EM算法则是算期望
  • M步根据聚类结果更新聚类中心

GEM

Maximization-Maximization Algorithm

Free Energy函数

• 假设隐变量数据Z的概率分布为$\tilde P(Z)$，定义分布 $\tilde P$与参数$\theta$的函数$F(\tilde P, \theta)$如下 $$F(\tilde P, \theta) = E_{\tilde P} [log P(Y,Z|\theta)] + H(\tilde P)$$

• $H(\tilde P)=-E_{\tilde P} log \tilde P(Z)$：分布 $\tilde P(Z)$的熵
• 通常假设$P(Y,Z|\theta)$是$\theta$的连续函数，则函数 $F(\tilde P,\theta)$是$\tilde P, \theta$的连续函数

定理1

• 对于固定$\theta$，存在唯一分布$\tilde P\theta$，极大化 $F(\tilde P, \theta)$，这时$\tilde P\theta$由下式给出 $$\tilde P_\theta(Z) = P(Z|Y,\theta)$$ 并且$\tilde P_{\theta}$随$\theta$连续变化

• 对于固定的$\theta$，求使得$F(\tilde P, \theta)$的极大， 构造Lagrange函数

  $$L(\tilde P, \lambda, \mu) = F(\tilde P, \theta) + \lambda(1 - \sum_Z \tilde P(Z)) - \mu \tilde P(Z)$$

  因为$\tilde P(Z)$是概率密度，自然包含两个约束

  $$\left \{ \begin{array}{l} \sum_Z \tilde P(Z) = 1 \\ \tilde P(Z) \geq 0 \end{array} \right.$$

  即Lagrange方程中后两项

• 对$\tilde P(Z)$求偏导，得

  $$\frac {\partial L} {\partial \tilde P(Z)} = log P(Y,Z|\theta) - log \tilde P(Z) - \lambda - \mu$$

  令偏导为0，有

  $$\begin{align*} log P(Y,Z|\theta) - log \tilde P(Z) & = \lambda + \mu \\ \frac {P(Y,Z|\theta)} {\tilde P(Z)} & = e^{\lambda + \mu} \end{align*}$$

• 则使得$F(\tilde P, \theta)$极大的$\tilde P_\theta(Z)$ 应该和$P(Y,Z|\theta)$成比例，由概率密度自然约束有

  $$\tilde P_\theta(Z) = P(Y,Z|\theta)$$

  而由假设条件，$P(Y,Z|\theta)$是$\theta$的连续函数

• 这里概率密度函数$\tilde P(Z)$是作为自变量出现

• 理论上对$\tilde P(Z)$和一般的复合函数求导没有区别， 但$E_{\tilde P}, \sum_Z$使得整体看起来非常不和谐

  $$\begin{align*} E_{\tilde P} f(Z) & = \sum_Z f(Z) \tilde P(Z) \\ & = \int f(Z) d(\tilde P(Z)) \end{align*}$$

定理2

• 若$\tilde P_\theta(Z) = P(Z|Y, \theta)$，则 $$F(\tilde P, \theta) = log P(Y|\theta)$$

定理3

• 设$L(\theta)=log P(Y|\theta)$为观测数据的对数似然函数， $\theta^{(i)}, i=1,2,\cdots$为EM算法得到的参数估计序列， 函数$F(\tilde P,\theta)$如上定义

  • 若$F(\tilde P,\theta)$在$\tilde P^{}, \theta^{}$ 上有局部极大值，则$L(\theta)$在$\theta^{*}$也有局部 最大值
  • 若$F(\tilde P,\theta)$在$\tilde P^{}, \theta^{}$ 达到全局最大，则$L(\theta)$在$\theta^{*}$也达到全局 最大

• 由定理1、定理2有

  $$L(\theta) = logP(Y|\theta) = F(\tilde P_\theta, \theta)$$

  特别的，对于使$F(\tilde P,\theta)$极大$\theta^{8}$有

  $$L(\theta^{*}) = logP(Y|\theta^{*}) = F(\tilde P_\theta^{*}, \theta{*})$$

• 由$\tilde P_\theta$关于$\theta$连续，局部点域内不存在点 $\theta^{}$使得$L(\theta^{}) > L(\theta^{})$，否则 与$F(\tilde P, \theta^{})$矛盾

定理4

• EM算法的依次迭代可由F函数的极大-极大算法实现
• 设$\theta^{(i)}$为第i次迭代参数$\theta$的估计， $\tilde P^{(i)}$为第i次迭代参数$\tilde P$的估计，在第 i+1次迭代的两步为

  • 对固定的$\theta^{(i)}$，求$\tilde P^{(i)}$使得 $F(\tilde P, \theta^{(i)})$极大
  • 对固定的$\tilde P^{(i+1)}$，求$\theta^{(i+1)}$使 $F(\tilde P^{(t+1)}, \theta)$极大化

• 固定$\theta^{(i)}$

  $$\begin{align*} F(\tilde P^{(i+1)}, \theta^{(i)} & = E_{\tilde P^{(t+1)}} [log P(Y,Z|\theta)] + H(\tilde P^{(i+1)}) \\ & = \sum_Z log P(Y,Z|\theta) P(Z|Y,\theta^{(i)}) + H(\tilde P^{(i+1)}) \\ & = Q(\theta, \theta^{(i)}) + H(\tilde P^{(i+1)}) \end{align*}$$

• 则固定$\tilde P^{(i+1)}$求极大同EM算法M步

GEM算法

• 输入：观测数据，F函数
• 输出：模型参数

1. 初始化$\theta^{(0)}$，开始迭代

2. 第i+1次迭代：记$\theta^{(i)}$为参数$\theta$的估计值， $\tilde P^{(i)}$为函数$\tilde P$的估计，求 $\tilde P^{(t+1)}$使$\tilde P$极大化$F(\tilde P,\theta)$

3. 求$\theta^{(t+1)}$使$F(\tilde P^{(t+1)l}, \theta)$极大化

4. 重复2、3直到收敛

次优解代替最优解

• 输入：观测数据，Q函数
• 输出：模型参数

1. 初始化参数$\theta^{(0)}$，开始迭代

2. 第i+1次迭代，记$\theta^{(i)}$为参数$\theta$的估计值， 计算

   $$\begin{align*} Q(\theta, \theta^{(i)}) & = E_Z [ log P(Y,Z|\theta)|Y,\theta^{(i)}] \\ & = \sum_Z P(Z|Y, \theta^{(i)}) log P(Y,Z|\theta) \end{align*}$$

3. 求$\theta^{(i+1)}$使

   $$Q(\theta^{(i+1)}, \theta^{(i)}) > Q(\theta^{(i)}, \theta^{(i)})$$

4. 重复2、3直到收敛

• 有时候极大化$Q(\theta, \theta^{(i)})$非常困难，此算法 仅寻找使目标函数值上升方向

ADMM求次优解

• 输入：观测数据，Q函数
• 输出：函数模型

1. 初始化参数 $\theta^{(0)} = (\theta_1^{(0)},…,\theta_d^{(0)})$， 开始迭代

2. 第i次迭代，记 $\theta^{(i)} = (\theta_1^{(i)},…,\theta_d^{(i)})$， 为参数$\theta = (\theta_1,…,\theta_d)$的估计值，计算

   $$\begin{align*} Q(\theta, \theta^{(i)}) & = E_Z [ log P(Y,Z|\theta)|Y,\theta^{(i)}] \\ & = \sum_Z P(Z|Y, \theta^{(i)}) log P(Y,Z|\theta) \end{align*}$$

3. 进行d次条件极大化

   1. 在$\theta1^{(i)},…,\theta{j-1}^{(i)},\theta_{j+1}^{(i)},…,\theta_d^{(i)}$ 保持不变条件下 ，求使$Q(\theta, \theta^{(i)})$达到极大的 $\theta_j^{(i+1)}$

   2. j从1到d，进行d次条件极大化的，得到 $\theta^{(i+1)} = (\theta_1^{(i+1)},…,\theta_d^{(i+1)})$ 使得

      $$Q(\theta^{(i+1)}, \theta^{(i)}) > Q(\theta^{(i)}, \theta^{(i)})$$

4. 重复2、3直到收敛

K-NN

• 输入：p维实例特征向量

  • 将样本点视为p维特征空间的中点

• 输出：实例类别，可以取多类别

• 基本思想

  • 在已有数据中找到与$X_0$相似的若干个观测 $(X_1, X_2, …, X_k)$，称为$X_0$的近邻
  • 对近邻$(X_1, X_2, …, X_k)$的输出变量 $(y_1, y_2, …, y_k)$，计算诸如算术平均值 （加权平均值、中位数、众数），作为新观测$X_0$输出 变量取值$y_0$的预测值

• 特点

  • k近邻不具有显式学习过程、简单、直观
  • 不需要假设$y=f(X)$函数体形式，实际上是利用训练数据集 对特征空间进行划分

局部方法

k-NN是一种“局部”方法，仅适合特征空间维度较低的情况

• 给定k的情况下，在高维空间中，需要到更远的区域寻找近邻， 局部性逐渐丧失，近似误差变大

• 如：n个观测均匀分布在超立方体中，确定k后即确定$X_0$需要 寻找的近邻个数占总观测的比率r，即近邻覆盖的体积

  • 考虑$X_0$在原点，则近邻分布的小立方体边期望长度为

    $$Ed_p(r) = r^{1/p} \\ Ed_3(0.1) = 0.1^{1/3} = 0.46 \\ Ed_10(0.1)d = 0.1^{1/10} = 0.79 \\ Ed_10(0.01) = 0.1^{1/10} = 0.63 \\$$

  • 可以看出：减少近邻比例（数量）没有帮助，还会使得近似 误差变大，只能通过增大样本量解决

• 特征选择有必要

特征选择

• 变量本身考察

  • low variance filter：剔除标准差小于阈值数值型变量
  • missing values ratio：剔除缺失值大于阈值的变量
  • 剔除众数比率大于阈值的分类型变量

• 变量与输出变量相关性角度考察

  • high correlation filter

• 对预测误差影响角度考察

  • Wrapper方法：逐个选择使错误率、均方误差下降最快变量 ，可使用Forward Feature Elimination

k-NN模型

K-NN是使用模型：实际上对应于特征空间的划分

• 模型包括3个基本要素，据此划分特征空间，确定特征空间中 每个点所属类
  • k值选择
  • 距离度量：参见data_science/ref/functions
  • 分类决策规则

k值选择

k值选择对k-NN方法有重大影响

• 较小k值：相当于使用较小邻域中训练实例进行预测

  • 复杂模型，容易发生过拟合
  • approximation error较小：只有于输入实例近、相似的 训练实例才会对预测结果有影响
  • estimation error较大：预测结果对近邻实例点非常敏感

• 较大k值：相当于使用较大邻域中训练实例进行预测

  • 简单模型
  • 估计误差较小
  • 近似误差较大：同输如实例远、相似程度差的训练实例也会 对预测结果有影响

k=1

只使用一个近邻做预测

• 找到距离$X_0$最近的近邻$X_i$，用其取值作为预测值

• 模型简单、效果较理想

  • 尤其适合特征空间维度较低、类别边界不规则情况
  • 只根据单个近邻预测，预测结果受近邻差异影响极大，预测 波动（方差）大，稳健性低

• 预测错误的概率不高于普通贝叶斯方法的两倍

  $$\begin{align*} P_e & = (1-p(y=1|X=X_0))P(y=1|X=X_0) + (1-p(y=0|X=X_0))P(y=0|X=X_0) \\ & = 2P(y=1|X=X_0)(1-P(y=1|X=X_0)) \\ & \leq 2(1-P(y=1|X=X_0)) \\ \end{align*}$$

  • $P(y=1|X=X_0)$：普通贝叶斯方法做分类预测，预测结果 为1的概率
  • 1-NN方法犯错的概率就是$X_0$、$X_i$二者实际值不同的 概率？？？？

k=N

使用训练样本整体做预测

• 无论输入实例，预测结果完全相同

  • 对分类预测，预测结果为“众数”
  • 对回归预测，预测结果为“平均数”

• 模型过于简单、效果不好

  • 忽略训练实例中大量信息
  • “稳健性”极好：预测值基本不受近邻影响，无波动

决策规则

分类决策规则

Majority Voting Rule

多数表决规则：等价于经验风险最小化

• 分类损失函数为0-1损失函数，分类函数为 $f: \mathcal{R^n} \rightarrow {c_1, c_2, \cdots}$

• 误分类概率$P(Y \neq f(X)) = 1 - P(Y=f(X))$

• 给定实例$x \in \mathcal{X}$的误分率为

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

  • $N_k(x)$：最近邻k个实例构成集合
  • $c_j$：涵盖$N_k(x)$区域的类别
  • $I$：指示函数

• 为使误分率（经验风险）最小，应选择众数

• 经验风险的构造中，前提是近邻被认为属于相同类别$c_j$，
• 当然这个假设是合理的，因为k-NN方法就是认为近邻类别相同， 并使用近邻信息预测
• $c_j$的选择、选择方法是模型选择的一部分，不同的$c_j$会 有不同的经验风险

数值决策规则

算法

• 实现k近邻法时，主要问题是对训练数据进行快速k近邻搜索， 尤在特征空间维数大、训练数据量大

• 考虑使用特殊的结构存储训练数据，减少计算距离次数，提高 k近邻搜索效率

linear scan

线性扫描：最简单的实现方法

• 需要计算输入实例与每个训练实例的距离，训练集较大时计算 非常耗时

kd树最近邻搜索

• 输入：已构造kd树
• 输出：x的最近邻

• 在kd树种找出包含目标点x的叶节点的

  • 从根节点出发，比较对应坐标，递归进行访问，直到叶节点 为止

  • 目标点在训练样本中不存在，必然能够访问到叶节点

• 以此叶节点为“当前最近点”

  • 目标点在此叶节点中点所在的区域内，且区域内只有该 叶节点中点

• 回溯，并在每个节点上检查

  • 如果当前节点保存实例点比当前最近点距离目标的更近， 更新该实例点为“当前最近点”

  • 检查该节点另一子区域是否可能具有更近距离的点

    • 即其是否同以目标点为圆心、当前最短距离为半径圆 相交
    • 只需要比较目标点和相应坐标轴距离和最短距离即可

  • 若二者相交，则将目标节点视为属于该子区域中点， 进行最近邻搜索，递归向下查找到相应叶节点，重新 开始回退

  • 若二者不相交，则继续回退

• 退回到根节点时，搜索结束，最后“当前最近点”即为最近邻点

• 这里涉及到回溯过程中，另一侧子域是否访问过问题，可以通过 标记、比较相应轴坐标等方式判断
• k>1的情况类似，不过检测时使用最远近邻，新近邻需要和所有 原近邻依次比较

加权k-NN

变量重要性

计算变量的加权距离，重要变量赋予较高权重

• 变量重要性：Backward Feature Elimination得到各变量 重要性排序

  $$FI_{(i)} = e_i + \frac {1} {p} \quad \\ w_{(i)} = \frac {FI_{(i)}} {\sum_{j=1}^p FI_{(j)}}$$

  • $e_i$：剔除变量i之后的均方误差（错误率）

• 加权距离：$dw(x,y)=\sqrt {\sum{i=1}^{p} w^{(i)}(x_i - y_i)^2}$

观测相似性

目标点的k个近邻对预测结果不应有“同等力度”的影响，与$X_0$越 相似的观测，预测时重要性（权重）越大

• 权重：用函数$K(d)$将距离d转换相似性，$K(d)$应该有特性

  • 非负：$K(d) \geqslant 0, d \in R^n$
  • 0处取极大：$max K(d) = K(0)$
  • 单调减函数，距离越远，相似性越小

  • 核函数符合上述特征
  • 且研究表明除均匀核外，其他核函数预测误差差异均不明显

步骤

• 依据函数距离函数$d(Z_{(i)}, Z_0)$找到$X_0$的k+1个近邻

  • 使用第k+1个近邻距离作为最大值，调整距离在0-1之间 $$D(Z_{(i)}, Z_0) = \frac {d(Z_{(i)}, Z_0)} {d(Z_{(k+1)}, Z_0)}, \quad i=1,2,...,k$$

• 依据函数$w_i=K(d)$确定k各近邻的权重

• 预测

  • 回归预测 $$\hat{y}_0 = \frac 1 k (\sum_{i=1}^k w_iy_i)$$
  • 分类预测：多数表决原则 $$\hat{y}_0 = max_r (\sum_{i=1}^k w_iI(y_i=r)) \\ P(\hat{y}_0=r|X_0)= \frac {\sum_{i=1}^k w_iI(y_i=r)} {\sum_{i=1}^k w_i}$$

Approximate Nearest Neighbor

相似最近邻

决策树概述

结构

• 决策树分析结论、展示方式类似一棵倒置的树

• 决策树由 node、directed edge 组成

  • internal node：内部节点，表示特征、属性
  • leaf node：叶子节点，表示一个类

• 对训练数据进行分类

  • 从根节点开始，对实例某特征进行测试，根据测试结果将实例分配到其子节点，对应该特征一个取值
  • 递归地对实例进行分配，直至到达叶子节点，将实例分到叶节点地类中

• 对新数据的预测

  • 从决策树的树根到树叶搜索，确定数所的叶子节点
  • 利用叶子节点中训练数据集预测
    • 分类型：众数
    • 数值型：均值

本质

决策树：本质上是从训练数据中归纳出一组分类规则

• 与训练数据不矛盾的分类规则（即能对训练数据正确分类）可能有多个、没有，需要找到矛盾较小、泛化能力较好的
• 决策树学习也是由训练数据集估计条件概率模型，需要寻找对训练数据有很好拟合、对未知数据有很好预测的模型

分类规则集合

• 决策树可以看作是 if-then 规则的集合：体现输入、输出变量逻辑关系

• 决策树根节点到叶节点每条路径构成一条规则
• 路径上内部节点的特征对应规则的条件，叶节点对应规则结论
• 决策树的路径或其对应的 if-then 规则集合 互斥且完备，即每个实例有且仅有一条路径覆盖

条件概率分布

• 决策树可以表示定义在特征空间、类空间上的条件概率分布

• 此条件概率分布定义在特征空间的一个划分（有限）上

  • 决策树中一条路径（叶节点）对应划分中一个单元
  • 每个单元定义的概率分布就构成一个条件概率分布

• 条件概率分布由 各单元的给定条件下，各类的条件概率分布组成

  • $P(Y|X)$：$X$ 为表示特征的随机变量（取值各个单元），$Y$ 表示类的随机变量
  • 各叶节点上的条件概率往往偏向于某类，决策树分类时将属于该节点实例分为该类

特点

• 优势

  • 能有效处理分类型输入变量
  • 能够实现非线性分割
  • 模型具有可读性，分类速度块

• 问题

  • 充分生长的决策有高方差，预测不稳定
  • 剪枝可以提高预测稳健性，但是预测精度可能会下降

决策树构建

• 从所有可能决策树中选取最优决策树是NP完全问题

  • 所以实际决策树算法通常采用 启发式 算法、贪心算法，近似求解最优化问题，得到 sub-optimal 决策树
  • 从包含所有数据的根节点开始，递归的选择 当前 最优特征、分割点对训练数据进行分割，使得各子数据集有当前最好分类
  • 此样本不断分组过程对应特征空间的划分、决策树的构建

• 原则：使节点/组内观测取值异质性下降最大，从而确定

  • 最佳划分特征
  • 特征的最佳分割点

异质性衡量：划分准则

• 信息增益
• 信息增益比：避免信息增益倾向于取值较多特征
  • 若样本类别严格服从分布，则信息增益和信息增益比选择应完全相同
  • 但由于偶然性、样本数量等原因，各特征取值的样本数量往往不完全符合分布
  • 由信息增益定义可看出，各特征取值样本数量较小时，数量变动影响更大，而特征取值较多更可能出现各取值对应样本数量较小
• GINI 指数

• 研究表明，不同决策树的划分准则对泛化性能影响有限，信息增益和 GINI 指数理念分析表明，其仅在 2% 情况下有所不同

特征变量处理

• 离散值处理

  • 全分类：各类别分别独立作为分支，构建节点
  • 切分二分：将类别分为的两组
  • 是否二分：某取值作为一个分支，其余作为另一分支

• 连续值处理

  • 二分法：选择阈值，按照阈值将连续值分为两部分
    • 精确阈值选取：检查所有可能阈值点，即所有不同取值点的中间点
    • 近似阈值选取
  • 近似分裂算法：选取一组阈值，将特征划分至不同桶内，类似分类值处理
    • 等频阈值：分位数
    • 等距阈值：linespace

缺失值处理

• 缺失值处理需要解决：异质性衡量指标计算、特征缺失样本划分问题

• 异质性衡量指标计算：使用特征未缺失样本权重对指标加权（以信息增益为例）

  $$\begin{align*} g(Y|X) &= \rho * g(\tilde Y | X) \\ & = \rho * (H(\tilde D) - \sum_v^V \tilde {r_v} H(\tilde {D^v})) \\ H(\tilde V) &= - \sum_k^K \tilde {p_k} log \tilde {p_k} \\ \rho &= \frac {\sum_{x \in \tilde D} w_x} {\sum_{x \in D} w_x}\\ \tilde {p_x} &= \frac {\sum_{x \in \tilde {D_k}} w_x} {\sum_{x \in \tilde D} w_x} \\ \tilde {r_v} &= \frac {\sum_{x \in \tilde {D^v}} w_x} {\sum_{x \in \tilde D} w_x} \end{align*}$$

  • $Y, X, w_x$：样本类别，特征，样本权重
  • $D, \tilde D, \tilde {D_k}, \tilde {D^v}$：样本全集，在特征 $X$ 上无缺失样本子集，属于 $k$ 类样本子集，在特征 $X$ 上取 $v$ 样本子集

• 特征缺失样本划分

  • 划分至所有节点，其权重设置为 $\tilde {r_v} * w_x$
    • $\tilde {r_v}$ 为节点 $v$ 的权重
    • 即将特征缺失样本节点权重比例划分至各节点

剪枝

树剪枝：在决策树的学习过程中，将已生成的树进行简化的过程

• 最小化 RSS、最大化置信目标下，会导致庞大的树

  • 对训练数据拟合好
  • 模型复杂度越高
  • 推广能力差
  • 比较难理解、解释

• 通过剪枝得到恰当的树，具备一定的预测精度、复杂程度恰当，代价（误差）和复杂度之间的权衡是必要的

• Pre-pruning 预剪枝：在决策树分裂过程中，不分裂不满足分裂条件的节点，限制决策树充分生长

  • 分裂条件
    • 最大深度
    • 叶节点数量
    • 样本量最小值
    • 异质性下降阈值
  • 预剪枝基于“贪心”的禁止划分，可能降低过拟合、减少时间开销，但也可能导致欠拟合

• Post-pruning 后剪枝：决策分裂完成后，根据一定规则剪去不具备普遍性的子树

  • 比预剪枝决策保留更多分支，欠拟合风险小、泛化性能好
  • 决策树生成局部模型，决策树剪枝学习整体模型

• 剪枝方法、程度对泛化性能影响显著，尤其是数据带有噪声

自底向上剪枝

• 自底向上剪去所有无法改善评价准则的非叶节点分支（转为叶节点）

  • 最简单后剪枝策略
  • 若已使用一定预剪策略，则该策略价值不大

• 特点

  • 须在生成完全决策树之后自底向上逐个考察非叶节点，时间开销大

Minimal Cost Complexity Pruning

$$\begin{align*} C_\alpha(T) & = C(T) + \alpha |T| \\ & = \sum_{t=1}^{|T|} N_t H_t(T) + \alpha |T| \\ & = -\sum_{t=1}^{|T|} \sum_{k=1}^K \frac {N_{t,k}} {N_t} log \frac {N_{t,k}} {N_t} + \alpha|T| \\ H_t(T) & = -\sum_k (\frac {N_{t,k}} {N_t} log \frac {N_{t,k}} {N_t}) \end{align*}$$

• $N_t$：树 $T$ 的第 $t$ 个叶子节点中样本点数量
• $N_{t,k}$：树 $T$ 的第 $t$ 个叶子节点第 $k$ 类样本点数量
• $H_t(T)$：树 $T$ 的第 $t$ 个叶子节点熵
• $C(T)$：模型对训练数据的预测误差
• $|T|$：用叶节点数量衡量的模型复杂度
• $\alpha \geq 0$：控制模型复杂度对模型总损失影响，每个叶节点带来的复杂度

• 极小化损失复杂度剪枝
  • 损失函数：正则化的极大似然函数
  • 此策略即在给定 $\alpha$ 的情况下，选择损失函数最小树

剪枝步骤

• 输入：生成算法产生的整个树 $T$，参数 $\alpha$
• 输出：修剪后的子数 $T_\alpha$

• 计算每个节点的经验熵
• 递归的从树的叶节点向上回缩
  • 若 $C\alpha(T{before}) \geq C\alpha(T{after})$，则剪枝
  • 不断回缩直到根节点，选取损失函数最小的子树 $T_\alpha$

• 算法只需要比较节点、节点子树之间损失函数之差即可，计算可以在局部进行
• 算法可以由动态规划算法实现

超参选择

• 对给定超参 $\alpha$，存在使损失函数 $C\alpha(T)$ 最小子树 $T\alpha$，且此最优子树唯一

  • $\alpha$ 偏大时，最优子树 $T_\alpha$ 偏小
  • $\alpha=0$ 时完整树最优，$\alpha \rightarrow \infty$ 时单节点树最优

• 对决策树种每个节点 $t$，通过以下策略生成 $g(t)$

  • $C_{\alpha}(T^t) = C(T^t) + \alpha|T^t|$：以 $t$ 为根节点的子树 $T^t$ 损失
  • $C_{\alpha}(t) = C(t) + \alpha$：对 $t$ 剪枝之后，仅包含单个节点 $t$ 的正则损失
  • 则 $\alpha=g(t) = \frac {C(t)-C(T^t)} {|T^t|-1}$ 时，单节点 $t$ 和子树 $T^t$ 损失相同

• 考虑以上 $g(t)$ 序列

  • $\alpha^t=g(t)$ 表示对 $T^{(0)}$ 中每个内部节点 $t$ 剪枝后，整体损失函数值减少程度
  • 可以证明，对以上 $\alpha > 0$ 序列排序，按 $0, \alpha^{(1)}, \cdots, \alpha^{(N)}$ 依次进行剪枝，对应最优子树序列 $T^{(0)}, T^{(1)},\cdots, T^{(N)}$ 嵌套
  • 通过交叉验证法在独立的验证数据集上对子树进行测试，选择最优决策树

完整剪枝+超参选择

• 输入：CART 算法生成决策树 $T^{(0)}$
• 输出：最优决策树 $T_\alpha$

• 自下而上地计算各内部节点 $t$ 对应 $C(T^t), |T^t|, g(t)$，对 $g(t)$ 升序排列得到 $\alpha^{(1)},\cdots,\alpha^{(N)}$

• 置：$k=1, \alpha=\alpha^{(k)}, T=T^{(0)}$

• 自上而下访问内部节点，若有 $g(t)=\alpha$，剪枝并计算新叶节点 $t$ 取值，得到对应最优树 $T^{(k)}$

  • 对于节点 $t$，其子树 $T^t$ 最大有效 $\alpha$ 也只是根节点对应 $g(t)$，更大没有价值
  • 自上而下剪枝避免无效剪枝

• 置：$k+=1, \alpha=\alpha^{(k)}, T=T^{(k)}$

• 若 $T$ 不是单节点树，则重复以上

• 采用交叉验证法在子树序列中选取最优子树 $T_\alpha$

• 也可从 $\alpha \leftarrow \infty$ 开始，逐渐减少，添枝 得到子树序列

决策树构建算法

• 以下是一些经典的决策树（算法），但实际实现中往往不会严格按其构建决策树

• 决策树算法常用递归描述、构建，完全决策树中止条件如下 （往往不会应用，而是以预剪枝条件作为中止条件）

  • 节点中样本属于同一类
  • 所有特征利用完毕
  • 无法找到满足划分阈值的特征、划分点

Iterative Dichotomiser 3

步骤

• 输入：训练数据集 $D$，特征集 $A$，阈值 $\epsilon$
• 输出：决策树 $T$

• 以下情况下 $T$ 为单节点树，以 $D$ 中实例数最大的类（众数） $C_k$ 作为该节点的类标记，返回 $T$

  • $D$ 中所有实例属于同一类 $C_k$
  • $A = \varnothing$

• 计算 $A$ 中各特征对 $D$ 的信息增益，选择信息增益最大的特征 $A_g$

  • 若 $A_g$ 的信息增益小于阈值 $\epsilon$，则置 $T$ 为单节点树，并将 $D$ 中实例数最大的类 $C_k$ 作为节点类标记，返回 $T$
  • 否则，对 $A_g$ 每个可能值 $a_m$，将 $D$ 分割为若干非空子集 $D_i$
    • 将 $D_i$ 中实例数最多的类作为标记，构建子节点
    • 对第 $i$ 个子节点，以 $D_i$ 为训练集，以 $A-{A_g}$ 为特征集，递归的构造子树 $T_i$ 并返回

特点

• 只允许分类型特征，且每个特征只会被用于划分一次

  • 每次所有取值都会被用于建立子节点
  • ID3 树是多叉树，各个节点的分叉个数取决于使用特征

• 只有树的生成，容易产生过拟合

• 以信息增益作为划分训练数据集的特征，倾向于选择取值较多的特征进行划分

  • 理论上若特征取值严格符合分布，取值数量多寡，对信息增益没有影响
  • 由于各种误差的存在，样本不可能严格符合总体分布，取值数量较多特征，各取值对应样本数量较少，误差会使得条件经验熵倾向于偏小 （假设误差随机，可以大概证明）

• 相当于用 极大似然法 进行概率模型的选择

C4.5

C4.5算法：ID3 算法继承者

• 与 ID3 差别

  • 用信息增益比代替信息增益用于选择特征，并且也被用于 前剪枝
    • 修正 ID3 倾向于使用取值较多的特征值分裂结点
  • 兼容数值型特征，使用二分法处理

• C4.5 算法还包含 C4.5Rules 将 C4.5 决策树转化为符号规则 - 各分支被重写为规则，并进行前件合并、删减

  • 最终规则集泛化性能可能优于原决策树

Classification and Regression Tree

CART 树：可用于分类和回归的二叉树

• 特点

  • 二叉树
  • 可以用于分类、回归
    • 分类：众数代表节点，GINI 指数选择特征
    • 回归：均值代表节点，MSE 选择特征
  • 能较好的处理缺失值

• CART 回归：平方误差最小化准则

  $$f(x) = \sum_{m=1} \hat c_m I(x \in R_m)$$

  • $R_m$：空间划分出的第 $m$ 单元
  • $\hat c_m=avg(y_i|x_i \in R_m)$：第 $m$ 个单元上所有实例输出变量均值，此时平方误差最小

• CART 分类：最小化基尼指数准则

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

  • $D_1 = {(x,y) \in D, X = a}$
  • $D_2 = D - D_1$
  • CART 树是二叉树，对分类变量只选择是否

CART回归步骤

• 输入：训练数据集 $D$
• 输出：回归树 $f(x)$

• 选择最优切变量 $j$、切分点 $s$，即求解

  $$\arg\min_{j,s} [\min_{c_1} \sum_{x_i \in R_1(j,s)} (y_i - c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j,s)} (y_i - c_2)^2 ]$$

  • $R_1(j,s) = {x|x^{(j)} \leq s}$
  • $R_2(j,s) = {x|x^{(j)} \geq s}$
  • $c_m = avg(y_i|x_i \in R_m)$：使得区域 $R_m$ 中平方误差最小，即其中样本点 $y_i$ 均值
  • 这里通过 遍历 得到

• 对两个子区域 $R_1(j,s), R_2(j,s)$ 继续重复以上步骤，直至满足停止条件

• 将输入空间划分为 $M$ 个区域 $R_1, R_2, \cdots, R_M$，生成决策 树

  $$f(x) = \sum_{m=1} \hat c_m I(x \in R_m)$$

CART 分类步骤

• 输入：训练数据集 $D$，停止计算条件
• 输出：CART 决策树

• 选择最优切变量 $j$、切分点 $s$

  $$Gini(D, X=a) = \frac {|D_1|} {|D|} Gini(D_1) + \frac {|D_2|} {|D|} Gini(D_2)$$
  • 对每个特征 $X$，对其所有取值 $a$ 计算条件基尼指数
  • 选择条件基尼指数最小的特征、对应的切分点，将训练数据依特征分配到两个子结点中

• 对生成两个子节点递归分裂，直至满足停止条件

• 生成 CART 决策树

Chi-squared Automatic Interaction Detector

CHAID 卡方自动交叉检验法：类似 ID3 算法，但利用卡方统计确定特征变量

• https://wenku.baidu.com/view/bdd3e60abed5b9f3f90f1cd6.html
• https://sefiks.com/2020/03/18/a-step-by-step-chaid-decision-tree-example/

特点

• 通过卡方统计量选择最显著特征变量作为划分特征

  • 分类目标变量：列联分析，卡方检验
  • 数值目标变量：回归分析，F检验

• 特征预处理

  • 分类型特征变量：根据卡方统计量显著性、组数量等考虑拆分、合并分组
  • 数值型特征变量：均分分组

• 是从相关性显著角度确定特征变量

  • 对决策树分支优化明显
  • 可用特征变量与目标相关性显著显著性作为停止分裂的标准

QUEST

Quick Unbiased Efficient Statical Tree：类似 CHAID 算法，但对选择特征、划分点依据不同，仅能处理分类目标变量

特点

• 类似 CHAID，选择最显著（p 值）的特征变量作为划分特征

  • 分类特征变量：连列分析，卡方检验
  • 数值特征变量：方差分析，F检验

• 划分点选择

  • 分类特征变量：映射为 one-hot 向量后，用判别分析求解划分向量，再映射回划分取值

• 目标变量多分类

  • 为每个类别计算特征均值，使用均值聚类将其简化为二分类
  • 只需要为节点内样本的、用待划分特征计算均值

• 运行速度快于 CART 树

• http://www.mclover.cn/blog/index.php/archives/60.html
• http://www3.stat.sinica.edu.tw/statistica/oldpdf/A7n41.pdf

Naive Bayes Classifier

朴素贝叶斯：在训练数据集上学习联合概率分布$P(X,Y)$，利用后验 分布作为结果

• 朴素：条件概率分布有条件独立性假设，即特征在类别确定 下条件独立

模型

• 输出Y的先验概率分布为

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

  • 先验概率是指输出变量，即待预测变量的先验概率分布， 反映其在无条件下的各取值可能性
  • 同理所有的条件概率中也是以输出变量取值作为条件

• 条件概率分布为

  $$P(X=x|Y=c_k) = P(X^{(1)}=x^{(1)},\cdots,X^{(D)}=x^{(D)}| Y=c_k)$$

  • $D$：用于分类特征数量

  其中有指数数量级的参数（每个参数的每个取值都需要参数）

• 因此对条件概率分布做条件独立性假设，即分类特征在类别 确定条件下是独立的

  $$\begin{align*} P(X=x|Y=c_k) & = P(X^{(1)}=x^{(1)},\cdots,X^{(D)}=x^{(D)} |Y=c_k) \\ & = \prod_{j=1}^D P(X^{(j)}=x^{(j)}|Y=c_k) \end{align*}$$
  • 条件独立性假设是比较强的假设，也是朴素的由来

  • 其使得朴素贝叶斯方法变得简单，但有时也会牺牲准确率

  • 以上即可得到联合概率分布$P(X,Y)$

  • 朴素贝叶斯学习到的联合概率分布$P(X,Y)$是数据生成的 机制，即其为生成模型

策略

策略：选择使得后验概率最大化的类$c_k$作为最终分类结果

$$P(Y=c_k|X=x) = \frac {P(Y=c_k, X=x)} {\sum_{i=1}^K P(Y=c_k, X=x)}$$

• $K$：输出类别数量

• 后验概率根计算根据贝叶斯定理计算

  $$\begin{align*} P(Y=c_k|X=x) & = \frac {P(X=x|Y=c_k)P(Y=c_k)} {\sum_{k=1}^K P(X=x|Y=c_k) P(Y=c_k)} \\ & = \frac {P(Y=c_k) \prod_{j=1}^D P(X^{(j)}|Y=c_k)} {\sum_{k=1}^K P(Y=c_k) \prod_{j=1}^D P(X^{(j)}|Y=c_k)} \end{align*}$$

• 考虑上式中分母对所有$c_k$取值均相等，则最终分类器为

  $$y = \arg\max_{c_k} P(Y=c_k) \prod_{j=1}^D P(X^{(j)} = x^{(j)}|Y=c_k)$$
  • 即分类时，对给定输入$x$，将其归类为后验概率最大的类

策略性质

后验概率最大化等价于0-1损失的经验风险最小化

• 经验风险为

  $$\begin{align*} R_{emp}(f) & = E[L(Y, f(X))] \\ & = E_x \sum_{k=1}^K L(y, c_k) P(c_k | X) \end{align*}$$

• 为使经验风险最小化，对训练集中每个$X=x$取极小化，对每个 个体$(x,y)$有

  $$\begin{align*} f(x) & = \arg\min_{c_k} \sum_{k=1}^K L(y, c_k) P(c_k|X=x) \\ & = \arg\min_{c_k} \sum_{k=1}^K P(y \neq c_k|X=x) \\ & = \arg\min_{c_k} (1-P(y=c_k|X=x)) \\ & = \arg\max_{c_k} P(y=c_k|X=x) \end{align*}$$

  即后验概率最大化

算法

极大似然估计

• 先验概率的极大似然估计为

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

• 条件概率的极大似然估计为

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

  • $a_{j,l}$；第j个特征的第l个可能取值
  • $S_j$：第j个特征的可能取值数量
  • $I$：特征函数，满足条件取1、否则取0

算法

• 输入：训练数据T
• 输出：朴素贝叶斯分类器

1. 依据以上公式计算先验概率、条件概率

2. 将先验概率、条件概率带入，得到朴素贝叶斯分类器

   $$y = \arg\max_{c_k} P(Y=c_k) \prod_{j=1}^D P(X^{(j)} = x^{(j)}|Y=c_k)$$

贝叶斯估计

• 条件概率贝叶斯估计

  $$P(X^{(j)}=a_{j,l}|Y=c_k) = \frac {\sum_{i=1}^N I(x_i^{(j)}=a_{j,l}, y_i=c_k) + \lambda} {\sum_{i=1}^N I(y_i=c_k) + S_j \lambda} \\ j=1,2,\cdots,N;l=1,2,\cdots,S_j;k=1,2,\cdots,K$$

  • $\lambda \geq 0$

  • $\lambda=0$时就是极大似然估计
  • 常取$\lambda=1$，此时称为Laplace Smoothing
  • 以上设计满足概率分布性质 $$\begin{align*} P_{\lambda}(X^{(j)}=a_{j,l}|Y=c_k) \geq 0 \\ \sum_{l=1}^{S_j} P_{\lambda}(X^{(j)}=a_{j,l}|Y=c_k) = 1 \end{align*}$$

• 先验概率贝叶斯估计

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

• 极大似然估计可能出现所需估计概率值为0，影响后验概率计算 结果，贝叶斯估计能够避免这点

Semi-Naive Bayes Classifier

半朴素贝叶斯分类器：适当考虑部分特征之间的相互依赖信息

• Semi-Naive Bayes可以视为是利用规则对变量加权，以 此来体现相关变量的协同影响

  $$y = \arg\max_{c_k} P(Y=c_k) \prod_{j=1}^D \beta_j P(X^{(j)} = x^{(j)}|Y=c_k)$$
  • 特别的：权值为0/1即为变量筛选

One-Depentdent Estimator

独依赖估计：假设特征在类别之外最多依赖一个其他特征，这是半 朴素贝叶斯分类器中最常用的一种策略

$$P(X=x|Y=c_k) = \prod_{j=1}^D P(X^{(j)}=x^{(j)} | Y=c_k, pa_j)$$

• $pa_j$：特征$X^{(j)}$依赖的父特征

• 若父特征已知，同样可以使用条件概率计算 $P(X^{(j)}=x^{(j)} | Y=c_k, pa_j)$

  $$P(X^{(j)}=x^{(j)} | Y=c_k, pa_j) = \frac {P(X^{(j)}=x^{(j)}, Y=c_k, pa_j)} {P(Y=c_k, pa_j)}$$

• ODE形式半朴素贝叶斯分类器相应的策略为

  $$y = \arg\max_{c_k} P(Y=c_k) \prod_{j=1}^D P(X^{(j)} = x^{(j)}|Y=c_k, pa_j)$$

• 根据确定各特征父特征的不同做法，可以分为不同类型的独依赖 分类器

  • Super-Parent ODE：假设所有特征都依赖同一父特征
  • Averaged ODE：类似随机森林方法，尝试将每个属性作为 超父特征构建SPODE
  • Tree Augmented Naive Bayes：基于最大带权生成树发展

SPODE

SPODE：每个特征只与其他唯一一个特征有依赖关系

$$y = \arg\max_{c_k} P(Y=c_k, pa) \prod_{j=1}^D P(X^{(j)} = x^{(j)}|Y=c_k, pa)$$

• $pa$：所有特征共有的依赖父特征

AODE

AODE：以所有特征依次作为超父特征构建SPODE，以具有足够训练 数据支撑的SPODE集群起来作为最终结果

$$y = \arg\max_{c_k} (\sum_{i=1}^D P(Y=c_k, X^{(i)}) \prod_{j=1}^D P(X^{(j)} = x^{(j)}|Y=c_k, X^{(i)}))$$

• 这里只选取训练数据足够，即取特征$X^{(i)}$某个取值的样本 数量大于某阈值的SPODE加入结果

TAN

TAN步骤

• 计算任意特征之间的互信息

  $$g(X^{(i)}, X^{(j)}| Y) = \sum P(X^{(i)}, X^{(j)} | Y=c_k) log \frac {P(X^{(i)}, X^{(j)} | Y=c_k)} {P(X^{(i)} | Y=c_k) P(X^{(j)} | Y=c_k)}$$

• 以特征为节点构建完全图，节点边权重设为相应互信息

• 构建此完全图的最大带权生成树

  • 挑选根变量
  • 将边设置为有向

• 加入预测节点$Y$，增加从$Y$到每个属性的有向边

特点

• 条件互信息$g(X^{(i)}, X^{(j)}| Y)$刻画了特征在已知类别 情况下的相关性

• 通过最大生成树算法，TAN仅保留了强相关属性之间的依赖性

子集回归

• 特征子集选择独立于回归模型拟合，属于封装器特征选择

最优子集

• 特点
  • 可以得到稀疏的模型
  • 但搜索空间离散，可变性大，稳定性差

Forward Feature Elimination

前向变量选择

步骤

• 初始变量集合$S_0 = \varnothing$
• 选择具有某种最优特性的变量进入变量集合，得到$S_1$
• 第j步时，从剩余变量中选择最优变量进入集合，得到$S_{j+1}$
• 若满足终止条件，则结束，否则重复上步添加变量
  • j达到上限
  • 添加剩余变量均无法满足要求

Backward Feature Elimination

后向变量选择

步骤

• 初始变量集合$S_0$包含全部变量
• 从变量集合中剔除具有某种最差特性变量，得到$S_1$
• 第j步时，从剩余变量中剔除最差变量，得到$S_{j+1}$
• 若满足终止条件，则结束，否则重复上步添加变量
  • j达到上限
  • 剔除剩余变量均无法满足要求

范数正则化约束

• 回归过程中自动选择特征，属于集成特征选择

Ridge Regression

$$\min_{\beta \in R^n} \left\{ ||y - X\beta||_2^2 + \lambda ||\beta||_2^2 \right\}$$

• 在L2范数约束下最小化残差平方
• 作为连续收缩方法
  • 通过bias-variance trade-off，岭回归较普通最小二乘 预测表现更好
  • 倾向于保留所有特征，无法产生疏系数模型

LASSO

$$\min_{\beta \in R^n} \left\{ ||y - X\beta||_2^2 + \lambda||\beta||_1 \right\}$$

能够选择部分特征，产生疏系数模型

• p > n时，即使所有特征都有用，LASSO也只能从中挑选n个
• 如果存在相关性非常高的特征，LASSO倾向于只从该组中选择 一个特征，而且是随便挑选的
  • 极端条件下，两个完全相同的特征函数，严格凸的罚函数 （如Ridge）可以保证最优解在两个特征的系数相等，而 LASSO的最优解甚至不唯一

Elastic Net

Naive Elastic Net

$$\begin{align*} & \min_{\beta \in R^n} \left\{ ||y - X\beta||_2^2 + \lambda_1||\beta||_1 + \lambda_2||\beta||_2^2 \right\} \\ \Rightarrow & \min_{\beta^* \in R^p} \left\{ ||y - X^*\beta^*||_2^2 + \lambda^*||\beta^*||_1 \right\} \\ where: & y^* = \begin{pmatrix} y \\ \vec 0_p \end{pmatrix} \\ & X^* = \frac 1 {\sqrt {1+\lambda^2}} \begin{pmatrix} X \\ \sqrt {\lambda_2} I_p \end{pmatrix} \\ & \beta^* = \sqrt {1+\lambda_2} \beta \\ & \lambda^* = \frac {\lambda_1} {1+\lambda_2} \\ \end{align*}$$

• 弹性网在Lasso的基础上添加系数的二阶范数

  • 能同时做变量选择和连续收缩
  • 并且可以选择一组变量

• 传统的估计方法通过二阶段估计找到参数

  • 首先设置ridge系数$\lambda_2$求出待估参数$\beta$， 然后做lasso的收缩
  • 这种方法有两次收缩，会导致估计偏差过大，估计不准

• 弹性网可以变换为LASSO，因而lasso的求解方法都可以用于 elastic net

elastic_net

Least Angle Regression

• 线性回归即找的一组系数能够用自变量的线性组合表示 因变量

Forward Selection/Forward Stepwise Regression

• 从所有给定predictors中选择和y相关系数绝对值最大的变量 $x_{j1}$，做线性回归

  • 对于标准化后的变量，相关系数即为变量之间的内积
  • 变量之间相关性越大，变量的之间的夹角越小，单个变量 能解释得效果越好
  • 此时残差同解释变量正交

• 将上一步剩余的残差作为reponse，将剩余变量投影到残差上 重复选择步骤

  • k步之后即可选出一组变量，然后用于建立普通线性模型

• 前向选择算法非常贪心，可能会漏掉一些有效的解释变量，只是 因为同之前选出向量相关

Forward Stagewise

前向选择的catious版本

• 和前向选择一样选择和y夹角最小的变量，但是每次只更新较小 步长，每次更新完确认和y夹角最小的变量，使用新变量进行 更新

  • 同一个变量可能会被多次更新，即系数会逐渐增加
  • 每次更新一小步，避免了前向选择的可能会忽略关键变量

• 输入：实例的特征向量
• 输出：实例类别+1、-1

感知机模型

感知机：线性二分类模型（判别模型）

$$f(x) = sign(wx + b)$$

• $x \in \chi \subseteq R^n$：输入空间
• $y \in \gamma \subseteq R^n$：输出空间
• $w \in R^n, b \in R$：weight vector、bias
• 也常有$\hat w = (w^T, b^T)^T, \hat x = (x^T + 1)^T$， 则有$\hat w \hat x = wx + b$

• 感知机模型的假设空间是定义在特征空间的所有 linear classification model/linear classifier，即函数 集合${f|f(x)=wx+b}$

• 线性方程$wx+b=0$：对应特征空间$R^n$中一个hyperplane

  • $w$：超平面法向量
  • $b$：超平面截距

  • 超平面将特征空间划分为两个部分，其中分别被分为正、负 两类

  • 也被称为separating hyperplane

Linearly Separable Data Set

• 对数据集$T={(x_1,y_1),\cdots,(x_N,y_N)}$，若存在超平面 $S: wx + b=0$能够将正、负实例点，完全正确划分到超平面 两侧，即 $$\begin{align*} wx_i + b > 0, & \forall y_i > 0 \\ wx_i + b < 0, & \forall y_i < 0 \end{align*}$$ 则称数据集T为线性可分数据集

感知机学习策略

感知机学习策略：定义适当损失函数，并将经验风险极小化，确定 参数$w, b$

0-1损失

经验风险：误分率（误分点总数）

• 不是参数$w, b$的连续可导函数，不易优化

绝对值损失

经验风险：误分类点到超平面距离

• 对误分类数据$(x_i, y_i)$，有$-y_i(wx_i + b) > 0$

• 则误分类点$(x_i, y_i)$到超平面S距离

  $$\begin{align*} d_i & = \frac 1 {\|w\|} |wx_i + b| \\ & =-\frac 1 {\|w\|} y_i(wx_i + b) \end{align*}$$

• 则感知机损失函数可定义为 $L(w,b) = -\sum_{x_i \in M} y_i(wx_i + b)$

  • $M$：误分类点集合
  • 损失函数是$w, b$的连续可导函数：使用$y_i$替代绝对值

• 损失函数$L(w,b)$梯度有

  $$\begin{align*} \bigtriangledown_wL(w, b) & = -\sum_{x_i \in M} y_ix_i \\ \bigtriangledown_bL(w, b) & = -\sum_{x_i \in M} y_i \end{align*}$$

学习算法

Stochastic Gradient Descent

随机梯度下降法

• 输入：数据集$T$、学习率$\eta, 0 \leq \eta \leq 1$
• 输出：$w,b$、感知模型$f(x)=sgn(wx+b)$

1. 选取初值$w_0, b_0$

2. 随机选取一个误分类点$(x_i, y_i)$，即$y_i(wx_i+b) \leq 0$ ，对$w, b$进行更新

   $$\begin{align*} w^{(n+1)} & \leftarrow w^{(n)} + \eta y_ix_i \\ b^{(n+1)} & \leftarrow b^{(n)} + \eta y_i \end{align*}$$

   • $0 < \eta \leq 1$：learning rate，学习率，步长

3. 转2，直至训练集中无误分类点

• 不同初值、随机取点顺序可能得到不同的解
• 训练数据线性可分时，算法迭代是收敛的
• 训练数据不线性可分时，学习算法不收敛，迭代结果发生震荡
• 直观解释：当实例点被误分类，应该调整$w, b$值，使得分离 超平面向误分类点方向移动，减少误分类点与超平面距离， 直至被正确分类

学习算法对偶形式

todo

算法收敛性

为方便做如下记号

• $\hat w = (w^T, b^T)^T, \hat w \in R^{n+1}$
• $\hat x = (x^T, 1)^T, \hat x \in R^{n+1}$

此时，感知模型可以表示为

$$xw + b = \hat w \hat x = 0$$

• 数据集$T={(x_1, y_1), (x_2, y_2),…}$线性可分，其中： $x_i \in \mathcal{X = R^n}$， $y_i \in \mathcal{Y = {-1, +1}}$，则

• 存在满足条件$|\hat w{opt}|=1$超平面 $\hat w{opt} \hat x = 0$将训练数据完全正确分开，且 $\exists \gamma > 0, yi(\hat w{opt} x_i) \geq \gamma$

• 令$R = \arg\max_{1\leq i \leq N} |\hat x_i|$，则 随机梯度感知机误分类次数$k \leq (\frac R \gamma)^2$

超平面存在性

• 训练集线性可分，存在超平面将训练数据集完全正确分开，可以 取超平面为$\hat w_{opt} \hat x = 0$

• 令$|\hat w_{opt}| = 1$，有

  $$\forall i, y_i(\hat w_{opt} \hat x_i) > 0$$

  可取

  $$\gamma = \min_i \{ y_i (\hat w_{opt} \hat x) \}$$

  满足条件

感知机算法收敛性

• 给定学习率$\eta$，随机梯度下降法第k步更新为 $\hat wk = \hat w{k-1} + \eta y_i \hat x_i$

• 可以证明

  • $\hat wk \hat w{opt} \geq k\eta\gamma$

    $$\begin{align*} \hat w_k \hat w_{opt} & = \hat w_{k-1} \hat w_{opt} + \eta y_i \hat w_{opt} \hat x_i \\ & \geq \hat w_{k-1} \hat w_{opt} + \eta\gamma \\ & \geq k\eta\gamma \end{align*}$$

  • $|\hat w_k|^2 \leq k \eta^2 R^2$

    $$\begin{align*} \|\hat w_k\|^2 & = \|\hat w_{k-1} + \eta y_i x_i \|^2 \\ & = \|\hat w_{k-1}\|^2 + 2\eta y_i \hat w_{k-1} \hat x_i + \eta^2 \|\hat x_i\|^2 \\ & \leq \|w_{k-1}\|^2 + \eta^2 \|\hat x_i\|^2 \\ & \leq \|w_{k-1}\|^2 + \eta^2 R^2 \\ & \leq k\eta^2 R^2 \end{align*}$$

• 则有

  $$\begin{align*} k \eta \gamma & \leq \hat w_k \hat w_{opt} \leq \|\hat w\| \|\hat w_{opt}\| = \|\hat w\| \leq \sqrt k \eta R \\ k^2 \gamma^2 & \leq k R^2 \end{align*}$$

• 直观理解就是超平面最大移动次数不大于最大移动距离 除以最小移动步长

  • $\eta \gamma^2$：超平面法向量最小增加量（移动步长）
  • $\eta R^2$：超平面法向最大增加量（移动距离）
  • 但是超平面不可能将所有点都归为同一侧

• 误分类次数有上界，经过有限次搜索可以找到将训练数据完全 正确分开的分离超平面，即训练数据集线性可分时，算法的迭代 形式是收敛的