Emsemble Learning

• 集成学习：训练多个基模型，并将其组合起来，以达到更好的 预测能力、泛化能力、稳健性
• base learner：基模型，基于独立样本建立的、一组 具有相同形式的模型中的一个
• 组合预测模型：由基模型组合，即集成学习最终习得模型

• 源于样本均值抽样分布思路

  • $var(\bar{X}) = \sigma^2 / n$
  • 基于独立样本，建立一组具有相同形式的基模型
  • 预测由这组模型共同参与
  • 组合预测模型稳健性更高，类似于样本均值抽样分布方差 更小

• 关键在于

  • 获得多个独立样本的方法
  • 组合多个模型的方法

分类

• homogenous ensemble：同源集成，基学习器属于同一类型

  • bagging
  • boosting

• heterogenous ensemble：异源集成，基学习器不一定属于同 一类型

  • [genralization] stacking

• 以上都是指原始版本、主要用途

Boosting

提升方法：将弱可学习算法提升为强可学习算法的组合元算法

• 属于加法模型：即基函数的线性组合
• 各模型之间存在依赖关系

分类Boosting

• 依次学习多个基分类器
• 每个基分类器依之前分类结果调整权重
• 堆叠多个分类器提高分类准确率

• boosting通过组合多个误分率略好于随机猜测的分类器得到 误分率较小的分类器，因此boosting适合这两类问题

  • 个体之间难度有很大不同，boosting能够更加关注较难的 个体
  • 学习器对训练集敏感，boosting驱使学习器在趋同的、 “较难”的分布上学习，此时boosting就和bagging一样能够 使得模型更加稳健（但原理不同）

• boosting能减小预测方差、偏差、过拟合

  • 直觉上，使用在不同的样本上训练的基学习器加权组合， 本身就能减小学习器的随机变动

  • 基于同样的理由，boosting同时也能减小偏差

  • 过拟合对集成学习有些时候有正面效果，其带来多样性， 使模型泛化能力更好，前提是样本两足够大，否则小样本 仍然无法提供多样性

回归Boosting

• 依次训练多个基学习器
• 每个基学习器以之前学习器拟合残差为目标
• 堆叠多个学习器减少整体损失

• boosting组合模型整体损失（结构化风险）

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

  • $l$：损失函数
  • $f_t$：基学习器
  • $\Omega(f_t)$：单个基学习器的复杂度罚
  • $N, M$：样本数目、学习器数目

• 基学习器损失

  $$obj^{(t)} = \sum_{i=1}^N l(y_i, \hat y_i^{(t)}) + \Omega(f_t)$$

最速下降法

使用线性函数拟合$l(y_i, \hat y_i^{(t)})$

$$\begin{align*} obj^{(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)] + \Omega(f_t) \end{align*}$$

• $gi = \partial{\hat y} l(y_i, \hat y^{t-1})$

• 一次函数没有极值
• 将所有样本损失视为向量（学习器权重整体施加），则负梯度 方向损失下降最快，考虑使用负梯度作为伪残差

Newton法

使用二次函数拟合$l(y_i, \hat y_i^{(t)}$

$$\begin{align*} obj^{(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) \\ \end{align*}$$

• $hi = \partial^2{\hat y} l(y_i, \hat y^{t-1})$

• 二次函数本身有极值
• 可以结合复杂度罚综合考虑，使得每个基学习器损失达到最小

Boosting&Bagging

• 基分类器足够简单时，boosting表现均显著好于bagging

  • 仅靠单次决策（单个属性、属性组合）分类

• 使用C4.5树作为基分类器时，boosting仍然具有优势，但是不够 有说服力

• 结论来自于Experiments with a New Boosting Algorithm

Boosting&Bagging

• 基分类器足够简单时，boosting表现均显著好于bagging

  • 仅靠单次决策（单个属性、属性组合）分类

• 使用C4.5树作为基分类器时，boosting仍然具有优势，但是不够 有说服力

• 结论来自于Experiments with a New Boosting Algorithm

原理

probably approximately correct：概率近似正确，在概率近似 正确学习的框架中

• strongly learnable：强可学习，一个概念（类），如果存在 一个多项式的学习算法能够学习它，并且正确率很高，那么 就称为这个概念是强可学习的

• weakly learnable：弱可学习，一个概念（类），如果存在 一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测 略好，称此概念为弱可学习的

• Schapire证明：在PAC框架下强可学习和弱可学习是等价的

具体措施

• 弱学习算法要比强学习算法更容易寻找，所以具体实施提升就是 需要解决的问题

• 改变训练数据权值、概率分布的方法

  • 提高分类错误样本权值、降低分类正确样本权值

• 将弱学习器组合成强学习器的方法

  • competeing
  • simple majority voting
  • weighted majority voting
  • confidence-based weighting

学习器组合方式

• 很多模型无法直接组合，只能组合预测结果

• simple majority voting/simple average：简单平均

  $$h = \frac 1 K \sum_{k=1}_K h_k$$

  • $h_k$：第k个预测

• weighted majority voting/weighted average：加权平均

  $$h = \frac {\sum_{k=1}^K w_k h_k} {\sum_{k=1}^K w_k}$$

  • $w_k$：第k个预测权重，对分类器可以是准确率

• competing voting/largest：使用效果最优者

• confidence based weighted：基于置信度加权

  $$\begin{align*} h = \arg\max_{y \in Y} \sum_{k=1}^K ln(\frac {1 - e_k} {e_k}) h_k \end{align*}$$

  • $e_k$：第k个模型损失

Meta Learning

元学习：自动学习关于关于机器学习的元数据的机器学习子领域

• 元学习主要目标：使用学习到元数据解释，自动学习如何 flexible的解决学习问题，借此提升现有学习算法性能、 学习新的学习算法，即学习学习

• 学习算法灵活性即可迁移性，非常重要

  • 学习算法往往基于某个具体、假象的数据集，有偏
  • 学习问题、学习算法有效性之间的关系没有完全明白，对 学习算法的应用有极大限制

要素

• 元学习系统必须包含子学习系统
• 学习经验通过提取元知识获得经验，元知识可以在先前单个 数据集，或不同的领域中获得
• 学习bias（影响用于模型选择的前提）必须动态选择
  • declarative bias：声明性偏见，确定假设空间的形式 ，影响搜索空间的大小
    • 如：只允许线性模型
  • procedural bias：过程性偏见，确定模型的优先级
    • 如：简单模型更好

Recurrent Neural networks

RNN：self-referential RNN理论上可以通过反向传播学习到， 和反向传播完全不同的权值调整算法

Meta Reinforcement Learning

MetaRL：RL智能体目标是最大化奖励，其通过不断提升自己的学习 算法来加速获取奖励，这也涉及到自我指涉

Additional Model

加法模型：将模型视为多个基模型加和而来

$$f(x) = \sum_{m=1}^M \beta_m b(x;\theta_m)$$

• $b(x;\theta_m)$：基函数
• $\theta_m$：基函数的参数
• $\beta_m$：基函数的系数

• 则相应风险极小化策略

  $$\arg\min_{\beta_m, \theta_m} \sum_{i=1}^N L(y_i, \sum_{m=1}^M \beta_m b(x_i;\theta_m))$$

  • $L(y, f(x))$：损失函数

Forward Stagewise Algorithm

前向分步算法：从前往后，每步只学习加法模型中一个基函数 及其系数，逐步逼近优化目标函数，简化优化复杂度

• 即每步只求解优化

  $$\arg\min_{\beta, \theta} \sum_{i=1}^N L(y_i, \hat f_m(x_i) + \beta b(x_i;\theta))$$

  • $\hat f_m$：前m轮基函数预测值加和

步骤

• 输入：训练数据集$T={(x_1,y_1), \cdots, (x_N,y_N)}$，损失 函数$L(y,f(x))$，基函数集${b(x;\theta)}$
• 输出：加法模型$f(x)$

• 初始化$f_0(x)=0$

• 对$m=1,2,\cdots,M$，加法模型中M个基函数

  • 极小化损失函数得到参数$\beta_m, \theta_m$

    $$(\beta_m, \theta_m) = \arg\min_{\beta, \theta} \sum_{i=1}^N L(y_i, f_{m-1}(x_1) + \beta b(x_i; \theta))$$

  • 更新

    $$f_m(x) = f_{m-1}(x) + \beta_m b(x;y_M)$$

• 得到加法模型

  $$f(x) = f_M(x) = \sum_{i=1}^M \beta_m b(x;\theta_m)$$

AdaBoost&前向分步算法

AdaBoost（基分类器loss使用分类误差率）是前向分步算法的特例， 是由基本分类器组成的加法模型，损失函数是指数函数

• 基函数为基本分类器时加法模型等价于AdaBoost的最终分类器 $f(x) = \sum_{m=1}^M \alpha_m G_m(x)$

• 前向分步算法的损失函数为指数函数$L(y,f(x))=exp(-yf(x))$ 时，学习的具体操作等价于AdaBoost算法具体操作

  • 假设经过m-1轮迭代，前向分步算法已经得到

    $$\begin{align*} f_{m-1}(x) & = f_{m-2}(x) + \alpha_{m-1}G_{m-1}(x) \\ & = \alpha_1G_1(x) + \cdots + \alpha_{m-1}G_{m-1}(x) \end{align*}$$

  • 经过第m迭代得到$\alpha_m, G_m(x), f_m(x)$，其中

    $$\begin{align*} (\alpha_m, G_m(x)) & = \arg\min_{\alpha, G} \sum_{i=1}^N exp(-y_i(f_{m-1}(x_i) + \alpha G(x_i))) \\ & = \arg\min_{\alpha, G} \sum_{i=1}^N \bar w_{m,i} exp(-y_i \alpha G(x_i)) \end{align*}$$

    • $\bar w{m,i}=exp(-y_i f{m-1}(x_i))$：不依赖 $\alpha, G$

  • $\forall \alpha > 0$，使得损失最小应该有 （提出$\alpha$）

    $$\begin{align*} G_m^{*}(x) & = \arg\min_G \sum_{i=1}^N \bar w_{m,i} exp(-y_i f_{m-1}(x_i)) \\ & = \arg\min_G \sum_{i=1}^N \bar w_{m,i} I(y_i \neq G(x_i)) \end{align*}$$

    此分类器$G_m^{*}$即为使得第m轮加权训练误差最小分类器 ，即AdaBoost算法的基本分类器

  • 又根据

    $$\begin{align*} \sum_{i=1}^N \bar w_{m,i} exp(-y_i \alpha G(x_i)) & = \sum_{y_i = G_m(x_i)} \bar w_{m,i} e^{-\alpha} + \sum_{y_i \neq G_m(x_i)} \bar w_{m,i} e^\alpha \\ & = (e^\alpha - e^{-\alpha}) \sum_{i=1}^N (\bar w_{m,i} I(y_i \neq G(x_i))) + e^{-\alpha} \sum_{i=1}^N \bar w_{m,i} \end{align*}$$

    带入$G_m^{*}$，对$\alpha$求导置0，求得极小值为

    $$\begin{align*} \alpha_m^{*} & = \frac 1 2 log \frac {1-e_m} {e_m} \\ e_m & = \frac {\sum_{i=1}^N (\bar w_{m,i} I(y_i \neq G_m(x_i)))} {\sum_{i=1}^N \bar w_{m,i}} \\ & = \frac {\sum_{i=1}^N (\bar w_{m,i} I(y_i \neq G_m(x_i)))} {Z_m} \\ & = \sum_{i=1}^N w_{m,i} I(y_i \neq G_m(x_i)) \end{align*}$$

    • $w_{m,i}, Z_M$同AdaBoost中

    即为AdaBoost中$\alpha_m$

  • 对权值更新有

    $$\bar w_{m+1,i} = \bar w_{m,i} exp(-y_i \alpha_m G_m(x))$$

    与AdaBoost权值更新只相差规范化因子$Z_M$

AdaBoost

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

• 对离群点、奇异点敏感
• 对过拟合不敏感

Boosting实现

• 改变训练数据权值或概率分布：提高分类错误样本权值、降低 分类正确样本权值

• 弱分类器组合：加权多数表决，即加大分类误差率小的弱分类器 权值，使其在表决中起更大作用；减小分类误差率大的弱分类器 权值，使其在表决中起更小作用

步骤

• 输入：训练数据集$T={(x_1, y_1), \cdots, (x_N, y_N)}$， 弱分类器算法$G(x)$

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

• 输出：最终分类器$G(x)$

• 初始化训练数据权值分布： $D1=(w{11}, \cdots, w{1N}), w{1i}=\frac 1 N$

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

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

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

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

    $$\begin{align*} e_m & = P(G_m(x_i)) \neq y_i) \\ & = \sum_{i=1}^N w_{mi}I(G_m(x_i) \neq y_i) \\ & = \sum_{G_m(x_i) \neq y_i} w_{mi} \end{align*}$$

  • 计算$G_m(x)$组合为最终分类器时权重

    $$\alpha = \frac 1 2 log \frac {1-e_m} {e_m}$$

    • $\alpha_m$表示就简单分类器$G_m(x)$在最终分类器中 的重要性，随$e_m$减小而增加 （弱分类器保证$e_m \leq 1/2$）

  • 更新训练集权值分布

    $$\begin{align*} D_{m+1} & = (w_{m+1,1}, \cdots, w_{m+1,N}) \\ w_{m+1,i} & = \frac {w_{mi}} {Z_m} exp(-\alpha y_i G_m(x_i)) = \left \{ \begin{array}{l} \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{array} \right. \\ Z_m & = \sum_{i=1}^N w_{mi} exp(-\alpha_m y_i G_m(x_i)) \end{align*}$$

    • $Zm$：规范化因子，是第m轮调整后的权值之和，其 使得$D{m+1}$成为概率分布
    • 误分类样本权值相当于被放大 $e^{2\alpha_m} = \frac {e_m} {1 - e_m}$倍

• 构建基本分类器线性组合

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

  得到最终分类器

  $$G(x) = sign(f(x)) = sign(\sum_{m=1}^M \alpha_m G_m(x))$$

  • 这里$\alpha_m$没有规范化，和不为1，规范化没有必要
  • $f(x)$符号决定分类预测结果，绝对值大小表示分类确信度

• AdaBoost中分类器学习和之后的分类误差率“无关”，基分类器 学习算法中的loss不是分类误差率，可以是其他loss，只是需要 考虑训练数据的权值分布

  • 好像基学习器的loss就要是和集成部分调权的loss一致

    todo

  • 按权值分布有放回的抽样，在抽样集上进行训练
  • 各样本loss按权重加权，类似分类误差率中加权

训练误差边界

AdaBoost算法最终分类器的训练误差边界为

$$\frac 1 N \sum_{i=1}^N I(G(x_i) \neq y_i) \leq \frac 1 N \sum_i exp(-y_if(x_i)) = \prod_m Z_m$$

• $G(x_i) \neq y_i$时，$y_if(x_i)<0$，所以 $exp(-y_i f(x_i)) \geq 1$，则不等式部分可证

• $$\begin{align*} \frac 1 N \sum_i exp(-y_i f(x_i)) & = \frac 1 N \sum_i exp(-\sum_{m=1}^M \alpha_m y_i G_m(x_i)) \\ & = \sum_i (w_{1,i} \prod_{m=1}^M exp(-\alpha_m y_i G_m(x_i))) \\ & = \sum_i (Z_1 w_{2,i} \prod_{m=2}^M exp(-\alpha_m y_i G_m(x_i))) \\ & = \prod_{m=1}^M Z_i \sum_i w_{M+1,i} \\ & = \prod_{m=1}^M Z_i \end{align*}$$

• AdaBoost训练误差边界性质的关键：权重调整与基本分类器权重 调整共系数（形式不完全一样）
• 这也是AdaBoost权重调整设计的依据，方便给出误差上界

二分类训练误差边界

$$\prod_{m=1}^M Z_m = \prod_{m=1}^M (2\sqrt{e_m(1-e_m)}) = \prod_{m=1}^M \sqrt{(1-4\gamma_m^2)} \leq exp(-2\sum_{m=1}^M \gamma_m^2)$$

• $\gamma_m = \frac 1 2 - e_m$

• $$\begin{align*} Z_m & = \sum_{i=1}^N w_{m,i} exp(-\alpha y_i G_m(x_i)) \\ & = \sum_{y_i = G_m(x_i)} w_{m,i}e^{-\alpha_m} + \sum_{y_i \neq G_m(x_i)} w_{m,i}e^{\alpha_m} \\ & = (1-e_m)e^{-\alpha_m} + e_m e^{\alpha_m} \\ & = 2\sqrt{e_m(1-e_m)} \\ & = \sqrt{1-4\gamma^2} \end{align*}$$

• 由$\forall x \in [0, 0.5], e^{-x} > \sqrt{1-2x}$可得， $\sqrt{1-4\gamma_m^2} \leq exp(-2\gamma_m^2)$

• 二分类AdaBoost误差边界性质的关键：$\alpha$的取值，也是 前向分步算法（损失函数）要求
• 若存$\gamma > 0$，对所有m有$\gamma_m \geq \gamma$，则 $$\frac 1 N \sum_{i=1}^N I(G(x_i) \neq y_i) \neq exp(-2M\gamma^2)$$ 即AdaBoost的训练误差是指数下降的
• 分类器下界$\gamma$可以未知，AdaBoost能适应弱分类器各自 训练误差率，所以称为adptive

Adaboost.M1

Adaboost.M1是原版AdaBoost的多分类升级版，基本思想同Adaboost

Boosting实现

• 基分类器组合方式

  • 仍然是加权投票，且投票权重同Adaboost
  • 出于多分类考虑，没有使用sign符号函数

• 改变训练数据权值或概率分布：和Adaboost形式稍有不同，但 相对的错误分类样本提升比率完全相同

  • 被上个分类器错误分类样本，权值保持不变
  • 被上个分类器正确分类样本，权值缩小比例是Adaboost平方

步骤

• 输入

  • 训练集：$T={x_i, y_i}, i=1,\cdots,N; y_i \in C, C={c_1, \cdots, c_m}$
  • 训练轮数：T
  • 弱学习器：I

• 输出：提升分类器

  $$H(x) = \arg\max_{y \in C} \sum_{m=1}^M ln(\frac 1 {\beta_m}) [h_m(x) = y]$$

  • $h_t, h_t(x) \in C$：分类器
  • $\beta_t$：分类器权重

误分率上界

• 对弱学习算法产生的伪损失$\epsilon1,\cdots,\epsilon_t$， 记$\gamma_t = 1/2 \epsilon_t$，最终分类器$h{fin}$误分率 上界有 $$\frac 1 N |\{i: h_{fin}(x_i) \neq y_i \}| \leq \prod_{t-1}^T \sqrt {1-4\gamma^2} \leq exp(-2 \sum_{t-1}^T \gamma^2)$$

特点

Adaboost.M1和Adaboost基本上没有区别

• 类别数目为2的Adaboost.M1就是Adaboost
• 同样无法处理对误分率高于0.5的情况，甚至在多分类场合， 误分率小于0.5更加难以满足
• 理论误分率上界和Adaboost相同

Adaboost.M2

AdaboostM2是AdaboostM1的进阶版，更多的利用了基分类器信息

• 要求基学习器能够输出更多信息：输出对样本分别属于各类别 的置信度向量，而不仅仅是最终标签
• 要求基分类器更加精细衡量错误：使用伪损失代替误分率 作为损失函数

Psuedo-Loss

$$\begin{align*} L & = \frac 1 2 \sum_{(i,y) \in B} D_{i,y} (1 - h(x_i, y_i) + h(x_i, y)) \\ & = \frac 1 2 \sum_{i=1}^N D_i (1 - h(x_i, y_i) + \sum_{y \neq y_i} (w_{i,y} h(x_i, y))) \end{align*}$$

• $D$：权重分布（行和为1，但不满足列和为1）

  • $D_{i,y}$：个体$x_i$中错误标签$y$的权重，代表从个体 $x_i$中识别出错误标签$y$的重要性

• $B = {(i, y)|y \neq y_i, i=1,2,\cdots,N }$
• $w$：个体各错误标签权重边际分布
• $h(x, y)$：模型$h$预测样本$x$为$y$的置信度

  • $h(x_i,y_i)$：预测正确的置信度
  • $h(x_i,y), y \neq y_i$：预测$x_i$为错误分类$y$置信度

• 伪损失函数同时考虑了样本和标签的权重分布
• 通过改变此分布，能够更明确的关注难以预测的个体标签， 而不仅仅个体

Boosting实现

• 改变数据权值或者概率分布

  • 使用psuedo-loss替代误分率，以此为导向改变权值
  • 对多分类每个错误分类概率分别计算错误占比，在此基础上 分别计算

• 基分类器组合方式：同Adaboost.M1

步骤

训练误差上界

• 对弱学习算法产生的伪损失$\epsilon1,\cdots,\epsilon_t$， 记$\gamma_t = 1/2 \epsilon_t$，最终分类器$h{fin}$误分率 上界有

$$\frac 1 N |\{i: h_{fn}(x_i) \neq y_i \}| \leq (M-1) \prod_{t-1}^T \sqrt {1-4\gamma^2} \leq (M-1) exp(-2 \sum_{t-1}^T \gamma^2)$$

特点

• 基于伪损失的Adaboost.M2能够提升稍微好于随机预测的分类器

• Adaboosting.M2能够较好的解决基分类器对噪声的敏感性，但是 仍然距离理论最优Bayes Error有较大差距，额外误差主要 来自于

  • 训练数据
  • 过拟合
  • 泛化能力

• 控制权值可以有效的提升算法，减小最小训练误差、过拟合 、泛化能力

  • 如对权值使用原始样本比例作为先验加权

• 其分类结果不差于AdaBoost.M1（在某些基分类器、数据集下）

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棵决策树，用一定集成策略组合多个决策树

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

优点

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

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

• 数据兼容性

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

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

• 其他

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

缺点

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

推荐系统架构

Matching

召回算法Match：包含多个渠道的召回模型，希望从资源库中选取 多样性偏好内容，缩小排序目标

• 协同过滤
• 主题模型
• 内容召回
• 热点召回

Ranking

排序：对多个召回渠道内容打分、排序、选出最优的少量结果

• 若召回结果仍包含大量数据，可以考虑分为两个阶段
  • 粗排：进一步剔除召回结果
  • 精排：对粗排结果再次打分、排序，得到最终推荐结果

Collaborative Filtering-Based Recommendation

基于协同过滤推荐算法：推荐算法中主流

• 模型一般为n个物品、m个用户的表

  • 只有部分用户、物品之间有评分数据
  • 要用已有部分稀疏数据预测空白物品、数据之间评分关系， 推荐高评分物品

• 无需太多特定领域的知识，可通过基于统计的机器学习算法得到 较好推荐效果，可以分为

  • 基于用户
  • 基于物品
  • 基于模型

• 现在指推荐算法一般指协同过滤，其他基于内容、规则、人口 统计信息等都被包含/忽略

User-based

基于用户协同过滤：主要考虑用户之间相似度，找出相似用户、相似 用户喜欢的物品，预测目标用户对对应物品的评分，推荐高评分物品

• 特点：（相较于Item-Based）推荐更社会化

  • 反映用户所在小型兴趣群体中物品热门程度
  • 可帮助用户找到新类别、惊喜物品

• 适合场景

  • 用户数量较少、变化慢场合，否则更新、计算用户相似度矩阵 代价大
  • 时效性强、用户个性化兴趣不明显领域
  • 无需给出推荐解释
  • 示例
    • 新闻推荐：注重热门、时效、item更新快
    • 热点视频推荐

• 方法

  • 基于规则：大众型推荐方法，如：最多用户点击、浏览
  • 基于人口统计信息：简单根据用户基本信息发现用户相关 程度、推荐
  • 混合推荐
    • 结合多个推荐算法，集成算法推荐结果
    • 复杂度高

Item-Based Collaborative Filtering

基于项目协同过滤：考虑物品和物品之间的相似度，找到目标用户 对某些物品的评分，预测用户对相似度高的类似物品评分，推荐高 评分相似物品

• 特点：（相较于User-Based）推荐更个性化

  • 反映用户自身的兴趣传承
  • 可帮助用户深入挖掘自身兴趣
  • 准确度一般
  • 推荐多样性弱，难以带来惊喜

• 适合场景

  • 物品数量较少、变化慢场合，否则更新、计算物品相似度 矩阵代价大
  • 长尾物品丰富、个性化需求不明显
  • 需要向用户给出推荐理由
  • 示例
    • 电商
    • 电影：兴趣持久、更个性化

Model-Based Collaborative Filtering

基于模型：目前最主流的协同过滤类型

• 关联算法：找出用户-物品数据里频繁出现的项集，作频繁集 挖掘，推荐频繁集、序列中其他物品

  • Apriori
  • FPTree
  • PrefixSpan

• 聚类算法：按照用户、物品基于一定距离度量聚类，推荐高评分 同类物品、同类人群 （类似于基于用户、物品协同过滤）

  • K-means
  • BIRCH
  • DBSCAN
  • Spectral Clustering

• 分类算法：使用分类模型划分物品

  • 逻辑回归
  • 朴素贝叶斯

• 回归算法：使用回归模型给物品预测打分，较分类更平滑

  • 线性回归
  • 决策树
  • SVM

• 矩阵分解：对用户-物品评分矩阵进行分解

  • FunkSVD
  • BiasSVD
  • SVD++

• 还有基于图模型、神经网络等新模型
• 还有依赖于自然语言处理NLP，通过挖掘文本内容特征，得到 用户的偏好，进而做推荐，同样可以找到用户独特的小众喜好

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$的元素

    

文本预处理

• 去除噪声文档、文档中垃圾数据
• 停用词去除
• 词根还原（英文）
• 分词（中文）
• 词性标注
• 短语识别
• 词频统计

汉语分词

分词：添加合适的显性词语边界标志，使所形成的词串反映句子本意

• 分词是正确处理中文信息的基础

  • 文本基于单字
  • 书面表达方式以汉字作为最小单位
  • 词之间没有显性界限标志

• 用单个汉字作特征，不考虑词语含义，直接利用汉字在文本中 出现的统计特性对文本进行划分

  • 直观明了
  • 操作简单
  • 对西语文本划分非常容易（使用空格划分）

• 使用词作为特征

  • 词是中文语义的最小信息单位，可以更好的反映句子中信息
  • 分析难度更高，中文文本中词之间没有分隔标记，正确分词 是关键

分词方法

• 基于词典

  • FMM：正向最大匹配分词
  • BMM：逆向最大匹配分词
  • BM法：双向扫描法
  • 逐词遍历

• 基于统计模型

  • N-最短路径
  • HMM
  • N元语法
  • 由字构词的汉语分词方法

分词难点

歧义切分

• 分词规范

  • 分词单位
    • 二字、三字以及结合紧密、使用稳定的
    • 四字成语
    • 四字词或结合紧密、使用稳定的四字词组
  • 五字、五字以上谚语、格言等，分开后如不违背原有组合 意义，应切分

• 歧义切分

  • 交集型切分歧义
  • 组合型切分歧义

未登录词识别

• 词表词：记录在词表中的词
• 未登录词：词表中没有的词、或已有训练语料中未曾出现词 （此时也称为out of vocabulary）

• 真实文本切分中，未登录词总数大约9成是专有名词，其余为 新词

• 未登录词对分词精度影响是歧义词的10倍

• 命名实体识别：实体名词、专业名词

  • 界定规则不存在太大分歧、构成形式有一定规律
  • 在文本中只占8.7%，引起分词错误率59.2%

词性标注

词性标注：在给定句子中判定每个词的语法范畴，确定词性并加以 标注的过程

• POS作为特征可以更好的识别词语之间关系

  • 词性标注计数为phrase chunking词组组块的界定、 entities and relationship实体与关系的识别打下良好 基础，有利于深入探索文本语义信息

  • 词组的形式提高了特征向量的语义含量，使得向量更稀疏

• 难点

  • 汉语缺乏词形态变化
  • 常用词兼类现象严重：占11%
  • 研究者主观原因：不同语料库有不同规定、划分方法

• part of speech：POS，词性

Forward Maximum Matching Method

FMM：正向最大匹配分词

• 步骤

  • 记词典中最长此表包含汉字数量为M
  • 从材料中选取前$m = M$个汉字去作为匹配字段，查找分词 词典
    • 若存在匹配词，则将其切分出
    • 否则$m = m - 1$，重复
  • 重复直至材料分词完毕

• 特点

  • 对交叉歧义、组合歧义没有解决办法
  • 错误切分率为$\frac 1 {169}$

Backward Maximum Matching Method

BMM：逆向最大匹配分词

• 步骤：类似FMM，仅从材料/句子末尾开始处理

• 特点

  • 错误切分率$\frac 1 {245}$，较FMM更有效

Bi-direction Matching Method

BM法：双向扫描法

• 步骤：比较FMM、BMM法切分结果，决定正确切分

• 特点

  • 可以识别分词中交叉语义

N-最短路径

• 思想

  • 考虑待切分字串$S=c_1 c_2 \cdots c_n$，其中$c_i$为 单个字、$n$为串长

  • 建立节点数为$n+1$的切分有向无环图，各节点编号为 $V_0, V_1, \cdots, V_n$

    • 相邻节点间存在边
    • 若$w=ci c{i+1} \cdots cj$是一个词，则节点 $v{i-1}, v_j$直接存在边
    • 所有边距离均为1

  • 求有图无环图中最短路径

特点

• 算法时间复杂度为$O(nNK)$

  • $n$：字串长度
  • $N$：最短路径数目
  • $k$：某个字作为词末端字的平均次数

改进—考虑噪声

基于统计信息的粗分模型

• 考虑词串$W$经过信道传输，由于噪声干扰丢失词界切分标志， 到输出端为字串$C$

• N-最短路径词语粗分模型可以改进为：求N个候选切分$W$，使得 概率$P(W|C)$为前N个最大值

  $$P(W|C) = \frac {P(W) P(C|W)} {P(C)}$$

  • $P(C)$：字串概率，常数
  • $P(C|W)$：仅有

• 采用一元统计模型，设$W=w_1w_2\cdots W_m$是字串 $S=c_1c_2\cdots c_n$的切分结果，则其切分概率为

  $$\begin{align*} P(W) & = \prod_{i=1}^m P(w_i) \\ P^{*}(W) = -ln P(w) = \sum_{i=1}^m (-ln P(W_i)) \end{align*}$$

  • $P(w_i)$：词$w_i$出现概率，在大规模预料训练的基础上 通过极大似然方法得到

• 则$-lnP(w_i)$可看作是词$w_i$在切分有向无环图中对应距离， 改进N-最短路径方法

由字构词

假设、背景

• 思想：将分词过程看作字分类问题，认为每个字在构造特定词语 时，占据确定的位置

• 中文词一般不超过4个字，字位数量很小
  • 首部B
  • 词中M
  • 词尾E
  • 单独成词S
• 部分汉字按一定方式分布，有规律
• 利用相对固定的字推断相对不定的字的位置问题
• 虽然无法将所有词列入词典，但字基本稳定

步骤

• 对所有字根据预定义的特征进行词位特征学习，获得概率 模型
• 在带待分字串上根据字与字之间的结合紧密程度得到词位的分类 结果
• 根据词位定义直接获得最终分词结果

Productivity

能产度：词$c_i$在词位$t_j$的能产度定义为

$$P_{c_i}(t_j) = \frac {count(c_i, t_j)} \sum_{t_j \in T} count(c_i, t_j)$$

• $T = {B, B_2, B_3, M, E, S}$

• 主词位：给定字在其上能产度高于0.5的词位

  |标记|B|B2|B3|M|E|S|总字量| |——-|——-|——-|——-|——-|——-|——-|——-| |字量|1634|156|27|33|1438|632|3920| |百分比|31.74|3.03|0.52|0.64|27.94|12.28|76.16|

  • MSRA2005语料库中有主词位的字量分布

• 自由字：没有主词位的字

  • 自由字是基于词位分类的分词操作得以有效进行的的基础 之一

• 字：不仅限于汉字，包括标点、外文字母、注音符号、数字等 任何可能文字符号

优势

• 能平衡词表词、未登录词
• 简化分词系统设计
  • 无需强调词表词信息
  • 无需设置特定未登录词识别模块

分词评价指标

• 正确率
• 召回率
• F-测度值

Vector Space Model

向量空间模型：自然语言处理常用模型

• document：文档，句子、段落、整篇文章
• term/feature：词根、词、短语、其他
• weight：项的权重，每个特征项在文档中重要程度

相似度比较

• 内积

  $$sim(D_1, D_2) = \sum_{k=1}^n w_{1,k} w_{2,k}$$

• Cosine相似度

  $$cos(D_1, D_2) = cos \theta = \frac {\sum_{k=1}^n w_{1,k} w_{2,k}} {\sqrt{\sum_{k=1}^n w_{1,k}^2 \sum_{k=1}^n w_{2,k}^2}}$$

权重

• 布尔权重：$bw_{t,d} = {0, 1}$
• TF：绝对词频，$TF{t,d} = \frac {n{t,d}} {n_d}$
• IDF：倒排文档频度，$IDF_{t,d} = log \frac M {m_t}$
• TF-IDF：$TF-IDF{t,d} = TF{t,d} * IDF_{t,d}$
• TF-IWF：$TFIWF{t,d}= TF{t,d} log \frac {\sum{t=1}^T \sum{d=1}^N n{t,d}} {\sum{t=1} n{t,d}}$

• $t_{t,d}$：文档$d$中出现特征$t$的次数
• $t_d$：文档$d$中出现总词数
• $m_t$：训练集中出现特征$t$文档数
• $M$：训练集中文档总数
• $K$：特征总数量

特征加权

• 特征加权主要包括三个部分（层次）

  • 局部加权：使用词语在文档中的统计量
  • 全局加权：词语在整个数据集中的统计量
  • 标准化

• 一般化特征加权表达式

  $$L_d(w) G(w) N_d$$

  • $L_d(w)$：词$w$在文档$d$中的局部权重
  • $G(w)$：词$w$在文档集合中的全局权重
  • $N_d$：文档d的标准化因子

Document Frequency

DF：文档频率，文本数据中包含某词条的文档数目

• 通过文档频率进行特征选择：按文档频率大小对词条进行排序

  • 将DF小于某阈值的词删除

    • 稀有词项全局影响力不大
    • 文档若有稀有词向，通常也会有常见词项

    • 和通常信息获取观念抵触：稀有更有代表性

  • 将DF大于某阈值的词删除

    • 太频繁词词项没有区分度

• 容易实现、可扩展性好

其他指标

• 信息增益/互信息

• 卡方统计量

Latent Semantic Analysis

LSA：潜在语义分析

• 文本分析中常用的降维技术

  • 特征重构方法
  • 很好解决了同义词、一词多义等现象给文本分析造成的困难

• 理论依据、假设

  • 认为有潜在语义结构隐含在文档中词语的上下文使用模式中
  • 而文档词频共现矩阵在一定程度可以反映词和不同主题之间 关系

• 以文档词频矩阵为基础进行分析

  • 得到向量空间模型中文档、词的高维表示
  • 并通过投影形成文档、词在潜在语义空间中的相对稠密的 低维表示，缩小问题规模
  • 通过这种低维表示解释出“文档-语义-词语”之间的联系

• 数学描述

  • LSA将每个文本视为以词语/特征为维度的空间的点，包含 语义的文本出现在空间中分布服从某种语义结构
  • LSA将每个词视为以文档为维度的空间中点
  • 文档由词语构成，词语需要放在文档中理解，体现词语和 文档之间的双重概率关系

应用SVD分解

• 词频共现矩阵$X=(x_{d,t})$：文档、词语的共现频率矩阵

  • 其中每行代表文档向量
  • 每列代表词语向量
  • 元素$x_{d,t}$表示文档$d$中词$t$出现的频率

• 对词频共现矩阵$X$进行SVD分解得到$X=U \Sigma V^T$

• 仅保留$\Sigma$中满足阈值要求的较大的前$r$特征值， 其余置为0，得到 $\tilde X = \tilde U \tilde \Sigma \tilde V^T$，达到信息 过滤、去除噪声的目的

  • $A = \tilde X$：矩阵特征分解后的文档词频矩阵近似
  • $T = \tilde U$：文档和潜在语义的关系矩阵近似
  • $S = \tilde V$：词语和潜在语义的关系矩阵近似
  • $D = \tilde \Sigma$：各潜在语义的重要程度

说明

• 从数据压缩角度：近似矩阵是秩为$K$的前提下，矩阵$X$的最小 二乘意义下最佳近似

• r值过大会增加运算量，一般选择K使得贡献率满足

  $$\sum_{i=1}^r d_i / \sum_{i=1}^K d_i \geq \theta$$

  • $\theta$：阈值
  • $K$：原始词频共现矩阵秩

• LSA缺点

  • SVD的向量元素有正、有负，性质难以解释
  • SVD的实际意义不够明确，难以控制词义据类的效果
  • 涉及高维矩阵运算

相似关系计算

• 潜在语义空间中存在：词-词、文本-文本、词-文本3种关系， 可以通过近似矩阵$T, S, D$计算

• 比较词汇两两相似度：“正向乘法”

  $$A A^T = T S D^T D S^T T^T = T S^2 T^T$$

• 比较文本两两相似度：“逆向乘法”

  $$A^T A = T^T S^T D D^T S T = T^T S^2 T$$

• 词汇、文本两两相似度：就是原始矩阵$X$的近似矩阵本身$A$

  $$A = T * S * D^T$$

名词

Statistic - Frequentist and Bayesian

统计：数学分支，概率论和优化的交集，是数据科学其他分支的理论基础

• 分析方法：验证式分析

  • 统计建模：基于数据构建统计模型，并验证假设
  • 模型预测：运用模型对数据进行预测、分析

• 理论依据：模型驱动，严格的数理支撑

  • 理论体系
    • 概率论、信息论、计算理论、最优化理论、计算机学科等多个领域的交叉学科
    • 并在发展中形成独自的理论体系、方法论
  • 基本假设：同类数据具有一定的统计规律性，可以用概率统计方法加以处理，推断总体特征，如
    • 随机变量描述数据特征
    • 概率分布描述数据统计规律

• 分析对象：以样本为分析对象

  • 从数据出发，提取数据特征、抽象数据模型、发现数据知识，再回到对数据的分析与预测
  • 数据多种多样，包括数字、文字、图像、音视频及其组合
  • 假设数据独立同分布产生
  • 训练数据集往往是人工给出的

Data Mining

• 从现有的信息中提取数据的 pattern、model，即精选最重要、可理解的、有价值的信息

  • 核心目的在于找到 数据变量之间的关系
  • 不是证明假说的方法，而是构建假说的方法
  • 大数据 的发展，传统的数据分析方式无法处理大量“不相关”数据

• 常用技术

  • cluster analysis：聚类分析，揭示数据内在结构
  • classification：判别分析，数据预测
  • regression/decision trees：决策树，模型图形化展示
  • neural networks：神经网络

• 联系

  • 本质上看起来像是 ML、AI 的基础
  • 会使用大量机器学习算法，但是特定的环境、目的和ML不同

• 建模一般策略：类似机器学习

  • 将数据视为高维空间中的点，在高维空间中找到分类面、回归面

Artificial Intelligence

• 研究如何创造智能 agent，并不一定涉及学习、归纳
• 但是大部分情况下，智能 需要从过去的经验中进行归纳，所以 AI 中很大一部分是 ML

Machine Learning

机器学习：从有限观测数据中学习一般性规律，并将规律应用到未观测样本中进行预测（最基本的就是在不确定中得出结论）

• 分析方法：归纳式、探索式分析
• 理论依据：数据驱动，从数据中中学习知识，
• 分析对象：对样本要求低，样本往往不具有随机样本的特征
• 机器学习建模：不假设，通过对高维空间的搜索，找到数据隐藏规律的恰当概括

Shallow Learning

浅层学习：不涉及特征学习，特征抽取依靠人工经验、特征转换方法

• 传统机器学习可以视为浅层学习

• 步骤

  • 数据预处理
  • 特征提取
  • 特征转换
  • 预测

Deep Learning

深度学习：将原始数据特征通过多步特征转换得到更高层次、抽象的特征表示，进一步输入到预测函数得到最终结果

• 主要目的是从数据中自动学习到有效的特征表示

  • 替代人工设计的特征，避免“特征”工程
  • 模型深度不断增加，特征表示能力越强，后续预测更容易

• 相较于浅层学习：需要解决的关键问题是贡献度分配问题

  • 从某种意义上说，深度学习也可以视为强化学习
  • 内部组件不能直接得到监督信息，需要通过整个模型的最终监督信息得到，有延时

• 目前深度学习模型主要是神经网络模型

  • 神经网络可以使用反向传播算法，较好的解决贡献度分配问题

• credit assignment problem：贡献度分配问题，系统中不同组件、参数对最终系统输出结果的贡献、影响

• 深度：原始数据进行非线性特征转换的次数，将深度学习系统看作有向图结构，深度可以看作是从输入节点到输出节点经过最长路径长度

Representing Learning

表示学习：自动学习有效特征、提高最终机器学习模型性能的学习

• 好的学习标准

  • 较强的表示能力：同样大小向量可以表示更多信息
  • 简化后续学习任务：需要包含更高层次语义信息
  • 具有一般性，是任务、领域独立的：期望学到的表示可以容易迁移到其他任务

• 要学习好的高层语义（分布式表示），需要从底层特征开始，经过多步非线程转换得到

  • 深层结构的优点式可以增加特征重用性，指数级增加表示能力
  • 所以表示学习的关键是构建具有一定深度、多层次特征表示

• 传统机器学习中也有关于特征学习的算法，如：主成分分析、线性判别分析、独立成分分析

  • 通过认为设计准则，用于选取有效特征
  • 特征学习、最终预测模型的学习是分开进行的，学习到的特征不一定可以用于提升最终模型分类性能

• Semantic Gap：语义鸿沟，输入数据底层特征和高层语义信息之间不一致性、差异性

表示

• Local Representation：局部表示，离散表示/符号表示

  • 通常可以表示为 one-hot 向量形式
    • 每个特征作为高维局部表示空间中轴上点
  • 不足
    • one-hot 维数很高、不方便扩展
    • 不同特征取值相似度无法衡量

• Distributed Representation：分布式表示

  • 通常可以表示为 低维、稠密 向量
    • 分散在整个低维嵌入空间中中
  • 表示能力强于局部表示
    • 维数低
    • 容易计算相似度

• 神经网络可以用于将高维局部空间 $R^{|V|}$ 映射到非常低维分布式表示空间 $R^d$

End-to-End Learning

端到端学习/训练：学习过程中不进行分模块、分阶段训练，直接优化任务的总体目标

• 不需要给出不同模块、阶段功能，中间过程不需要认为干预
• 训练数据为“输入-输出”对形式，无需提供其他额外信息
• 和深度学习一样，都是要解决“贡献度分配”问题
  • 大部分神经网络模型的深度学习可以看作是端到端学习

Learning Components

Model/Hypothesis/Opimizee/Learner/Learning Algorithm

模型/假说/优化对象/学习器/学习算法：待学习的条件概率分布 $P(Y|X)$、决策函数 $Y=f(X)$

• 概率模型：适合用条件概率分布 $P(Y|X)$ 表示的模型
• 非概率模型：用决策函数 $Y=f(x)$ 表示的模型

• learner：某类模型的总称
• hypothesis：训练好的模型实例，有时也被强调作为学习器应用在某个样本集（如训练集）上得到的结果
• learning algorithm：模型、策略、算法三者的模型总体

Hypothesis Space

假设空间：特征空间（输入空间）到输出空间的映射集合

• 假设空间可以定义为决策函数/条件概率的集合，通常是由参数向量 $\theta$ 决定的函数/条件分布族

  • 假设空间包含所有可能的条件概率分布或决策函数
  • 假设空间的确定意味着学习范围的确定

• 概率模型假设空间可表示为：$F={P|P_{\theta}(Y|X), \theta \in R^n}$

• 非概率模型假设空间可表示为：$F={f|Y=f(x),\Theta \in R^n }$

• 以下大部分情况使用决策函数，同时也可以代表概率分布

Strategy/Goal

策略/目标：从假设空间中，根据 evaluation criterion 选择最优模型，使得其对已知训练数据、未知训练数据在给定评价准则下有最优预测

• 选择合适策略，监督学习问题变为经验风险、结构风险函数 最优化问题

• 在某些学习方法中，最优化问题目标函数也有可能不是风险函数，如：SVM，是和模型紧密相关的损失函数，但逻辑是一样的

Empirical Risk Minimiation

ERM：经验风险最小化策略认为，经验风险最小模型就是最优模型

• 按经验风险最小化求最优模型，等价于求最优化问题

  $$\min_{f \in F} \frac 1 N \sum_{i=1}^N L(y_i, f(x_i))$$

• 样本容量足够大时，经验风险最小化能保证有较好的学习效果，现实中也被广泛采用

Structural Risk Minimization

SRM：结构风险最小化，为防止过拟合提出的策略

• 结构化风险最小化策略认为结构风险最小的模型是最优模型，则求解最优模型等价于求解最优化问题

  $$arg \min_{f \in F} \frac 1 N \sum_{i=1}^N L(y_i, f(x_i)) + \lambda J(f)$$

• 结构风险小需要经验风险与模型复杂度同时小，此时模型往往对训练数据、未知的测试数据都有较好的预测

• 结构化风险最小策略符合 Occam’s Razor 原理

• Occam’s Razor：奥卡姆剃刀原理，在所有可能选择的模型中，能够很好的解释已知数据并且十分简单才是最好的模型

Algorithm/Optimizer

算法/优化器：学习模型（选择、求解最优模型）的具体计算方法 （求解最优化问题）

• 如果最优化问题有显式解析解，比较简单

• 但通常解析解不存在，需要用数值计算方法求解

  • 保证找到全局最优解
  • 高效求解

Supervised Learning

监督学习：学习一个模型，使得模型能够对任意给定输入、输出，做出好的预测

• 从给定的、有限的、用于学习的 train data $T={(x_1,y_1), (x_2,y_2), \cdots, (x_N, y_N)}$ 中学习

• 预测 “未知” test data $T={(x_1,y_1), (x_2,y_2), \cdots, (x_N^{‘}, y_N^{‘})}$

数据

• input space：输入空间 $\chi$，所有输入 $X$ 可能取值的集合
• output space：输出空间 $\gamma$，所有输出 $Y$ 可能取值集合
• feature space：特征空间，表示输入实例 feature vector 存在的空间
  • 特征空间每维对应一个特征
  • 模型实际上是定义在特征空间上的
  • 特征空间是输入空间的象集，有时等于输入空间

学习方法分类

Generative Approach

生成方法：由数据学习联合概率分布 $P(X, Y)$，然后求出条件概率分布 $P(Y|X)$ 作为 generative model

• 方法学习给定输入X产生输出Y的生成关系（联合概率分布）

• generative model：生成模型，由生成方法学习到的模型 $P(Y|X) = \frac {P(X, Y)} {P(X}$

  • 朴素贝叶斯法
  • 隐马尔可夫模型

• 特点

  • 可以还原联合概率分布 $P(X, Y)$
  • 生成方法学习收敛速度快，样本容量增加时，学习到的模型可以快速收敛到真实模型
  • 存在隐变量时，仍可以使用生成方法学习

Discriminative Approach

判别方法：由数据直接学习决策函数 $f(x)$、条件概率分布 $P(Y|X)$ 作为 discriminative model

• 判别方法关心的是对给定输入 $X$，预测输出$Y$

• discriminative model：判别模型

  • KNN
  • 感知机
  • 决策树
  • 逻辑回归
  • 最大熵模型
  • 支持向量机
  • 提升方法
  • 条件随机场

• 特点

  • 直接学习条件概率、决策函数
  • 直面预测，学习准确率更高
  • 可以对数据进行各种程度抽象、定义特征、使用特征，简化学习问题

问题分类

• well-posed problem：好解问题，指问题解应该满足以下条件

  • 解存在
  • 解唯一
  • 解行为随着初值连续变化

• ill-posed problem：病态问题，解不满足以上三个条件

Classification

分类问题：输出变量$Y$为有限个离散变量

• 学习过程：根据已知训练数据集，利用有效学习方法学习分类器 $P(Y|X))$、$Y=F(X)$
• 分类过程：利用学习的分类器对新输入实例进行分类

• 可用学习方法

  • KNN
  • 感知机
  • 朴素贝叶斯
  • 决策树
  • 决策列表
  • 逻辑回归
  • 支持向量机
  • 提升方法
  • 贝叶斯网络
  • 神经网络

• 不存在分类能力弱于随机预测的分类器（结论取反）

Tagging

标注问题：输入、输出 均为变量序列

• 可认为是分类问题的一个推广、更复杂 structure prediction 简单形式
• 学习过程：利用已知训练数据集构建条件概率分布模型 $P(Y^{(1)}, Y^{(2)}, \cdots, Y^{(n)}|X^{(1)}, X^{(2)}, \cdots, X^{(n)})$

  • $X^{(1)}, X^{(2)}, \cdots, X^{(n)}$：每个输入序列
  • $Y^{(1)}, Y^{(2)}, \cdots, Y^{(n)}$：所有可能标记

• 标注过程：按照学习到的条件概率分布，标记新的输入观测序列
• 可用模型
  • 隐马尔可夫模型
  • 条件随机场

Regression

回归问题：输入（自变量）、输出（因变量）均为连续变量

• 回归模型的拟合等价于函数拟合：选择函数曲线很好的拟合已知数据，且很好的预测未知数据
• 学习过程：基于训练数据构架模型（函数）$Y=f(X)$
  • 最常用损失函数是平方损失函数，此时可以使用最小二乘求解
• 预测过程：根据学习到函数模型确定相应输出

Unsupervised Learning

无监督学习：没有给定实现标记过的训练示例，自动对输入的数据进行分类

• 主要目标：预训练一般模型（称识别、编码）网络，供其他任务使用
• 目前为止，有监督模型一般比无监督的预训练模型表现得好
  • 主要原因：有监督模型对数据的 特性编码 更好

问题分类

Clustering 聚类

• Hierarchy Clustering
• K-means
• Mixture Models
• DBSCAN
• OPTICS Algorithm

Anomaly Detection 异常检测

• Local Outlier Factor

Neural Networks 神经网络

• Auto-encoders
• Deep Belief Nets
• Hebbian Learning
• Generative Adversarial Networks
• Self-organizing Map

隐变量学习

• Expectation-maximization Algorithm
• Methods of Moments
• bind signal separation techniques
  • Principal Component analysis
  • Independent Component analysis
  • Non-negative matrix factorization
  • Singular Value Decomposition

Semi-Supervised Learning

半监督学习：利用少量标注数据和大量无标注数据进行学习的方式

• 可以利用大量无标注数据提高监督学习的效果

Reinforcement Learning

强化学习：从与环境交互中不断学习的问题、以及解决这类问题的方法

• 强化学习问题可以描述为：智能体从与环境的交互中不断学习以完成特定目标

• 强化学习的关键问题：贡献度分配问题

  • 每个动作不能直接得到监督信息，需要通过整个模型的最终 监督信息得到，且具有时延性
  • 给出的监督信息也非“正确”策略，而是策略的延迟回报，并通过调整策略以取得最大化期望回报

网络结构

• node/vertex：人
• link/edge：人与人之间的relation，可以有标签、权重、 方向
• graph/network：社交网络，表示个体之间的相互关系

• 图、网络参见cs_algorithm/data_structure/graph

基本统计指标、特性

• subnetwork/subgraph

  • singleton：单点集，没有边的子图
  • clique：派系，任意两个节点间均有连边的子图

• degree：

  • 对有向图可以分为out-degree、in-degree
  • average degree：网络平均度，所有节点度的算术平均
  • degree distribution：网络度分布，概率分布函数 $P(k)$

Path

• path length：路径长度
• shortest path：节点间最短路径
• distance：节点距离，节点间最短路径长度

• diameter：网络直径，任意两个节点间距离最大值

• 对规模（节点数量）为$N$大多数现实网络（尤其是社交网络）

  • 小直径：与六度分离实验相符
  • 存在巨大连通分支
  • 高聚类特性：具有较大点聚类系数
  • 明显的模块结构

• giant connected component：巨大连通分支，即规模达到 $O(N)$的连通分支

• node clustering coefficient：点聚类系数

  $$\begin{align*} NC_i & = \frac {triange_i} {triple_i} \\ NC & = \frac {\sum_i NC_i} N \end{align*}$$

  • $triangle_i$：包含节点$i$三角形数量
  • $triple_i$：与节点$i$相连三元组：包含节点$i$的三个 节点，且至少存在节点$i$ 到其他两个节点的两条边
  • $NC_i$：节点$i$聚类系数
  • $NC$：整个网络聚类系数

• edge clustering coefficient：边聚类系数

  $$EC_{ij} = \frac {|包含边<i,j>三角形|} {min\{(d_i-1), (d_j-1)\}}$$

  • $d_i$：节点$i$度，即分母为边$$最大可能存在于 的三角形数量

• edge betweenness：边介数，从源节点$v$出发、通过该边 的最短路径数目

边介数的计算

• 从源节点$i$出发，为每个节点$j$维护距离源节点最短路径 $d_j$、从源节点出发经过其到达其他节点最短路径数目$w_j$

  • 定义源节点$i$距离$d_i=0$、权值$w_i=1$

  • 对源节点$i$的邻接节点$j$，定义其距离$d_j=d_i+1$、 权值$w_j=w_i=1$

  • 对节点$j$的任意邻接节点$k$

    • 若$k$未被指定距离，则指定其距离$d_k=d_j+1$、 权值$w_k=w_j$
    • 若$k$被指定距离且$d_k=d_j+1$，则原权值增加1， 即$w_k=w_k+1$
    • 若$k$被指定距离且$d_k<d_j+1$，则跳过

  • 重复以上直至网络中包含节点的连通子图中节点均被指定 距离、权重

• 从节点$k$经过节点$j$到达源节点$i$的最短路径数目、与节点 $k$到达源节点$i$的最短路径数目之比为$w_i/w_j$

  • 从叶子节点$l$开始，若叶子节点$l$节点$i$相邻，则将 权值$w_i/w_l$赋给边$(i,l)$

  • 从底至上，边$(i,j)$赋值为该边之下的邻边权值之和加1 乘以$w_i/w_j$

  • 重复直至遍历图中所有节点

• 叶子节点：广度优先搜索叶子节点，即不被任何从源节点出发到 其他节点的最短路径经过
• 此边介数计算方式与节点介数中心性计算，都是寻找通过边、 节点的最短路径数目，但是具体计算方式不同

最短路径唯一

• 考虑从任何节点间最短路径只有一条，则某节点到其他节点 的最短路径构成一棵最短路径树

• 找到最短路径树的叶子节点，为每条与叶子节点相连的边赋值 为1
• 自下而上为树中其他边赋值：边之下所有临边值之和加1
• 处理所有节点直至树根源节点时，各边相对于树根源节点的介数 即为其权重

• 对各节点分别重复以上即可得到各边对各节点介数，相总即可得 各边总边介数

Node Centrality

节点中心性：采用某种定量方法对每个节点处于网络中心地位的程度 进行刻画

• 描述整个网络是否存在核心、核心的状态

基于度

• Degree Centrality：度中心性

  $$DC_i = \frac {d_i} {N-1}$$

  • $d_i$：节点$i$的度

  • 衡量节点对促进网络传播过程发挥的作用

• eigenvector centrality：特征向量中心性

  $$ EC_i = $

• subgraph centrality：子图中心性

  $$ SC_i = $

基于路径数

• Betweenness Centrality：介数中心性

  $$BC_i = \frac 2 {(N-1)(N-2)} \sum_{j<k, j,k \neq i} \frac {p_{j,k}(i)} {p_{j,k}}$$

  • $p_{j,k}$：节点$j,k$间路径数量
  • $p_{j,k}(i)$：节点$j,k$间路径经过节点$i$路径数量

  • 衡量节点对其他节点间信息传输的潜在控制能力

• Closeness Centrality

  $$CC_i =$$

Community Structure

社团/模块/社区结构：内部联系紧密、外部联系稀疏（通过边数量 体现）的子图

基于连接频数的定义

$$\begin{align*} \sigma_{in}(S) & = \frac {|E(S)|} {|V(S)|(|V(S)|-1)/2} \\ \sigma_{out}(S) & = \frac {|E| - |E(S)|} {(N - |V(S)|)(N - |V_S| - 1) / 2} \\ \sigma(G) & = \frac {|E|} {|V|(|V|-1) / 2} \end{align*}$$

• $G, S$：全图、子图
• $\simga_{in}(S)$：子图$S$的内部连接率/频数
• $S_{in}$：子图$S$内部的实际边数
• $E, E(S)$：全图、子图$S$内部边
• $V, V(S)$：全图、子图$S$内部节点

• 若子图$S \subset G$满足如下，则称为网络$G$的社区

  $$\sigma_{in}(S) > \sigma(G) > \sigma_{out}(S)$$

强弱社区

• 强社区结构

  $$|E_{in}(S, i)| > |E_{out}(S, i)|, \forall i \in S$$

  • $E_{in}(S, i)$：节点$i$和子图$S$内节点连边
  • $E_{out}(S, i)$：节点$i$和子图$S$内节点连边

• 弱社区结构

  $$\sum_{i \in S} |E_{in}(S, i)| > \sum_{i \in S} |E_{out}(S, i)|, \forall i \in S$$

• 最弱社区结构

  $$\forall i \in S_j, |E_{in}(S_j, i)| > |E(S_j, i, S_k)|, j \neq k, k=1,2,\cdots,M$$

  • 社区$S_1,S_2,\cdots,S_M$是网络$G$中社区
  • $E(S_j, i, S_k)$：子图$S_j$中节点$i$与子图$S_k$之间 连边数

• 改进的弱社区结构：同时满足弱社区结构、最弱社区结构

LS集

LS集：任何真子集与集合内部连边数都多于与集合外部连边数 的节点集合

Clique

• 派系：节点数大于等于3的全连通子图

• n派系：任意两个顶点最多可以通过n-1个中介点连接

  • 对派系定义的弱化
  • 允许两社团的重叠

• 全连通子图：任意两个节点间均有连边

模块度函数Q

$$\begina{align*} Q & = \sum_{i} (e_{i,i} - \hat e_{i,i}) \\ & = \sum_{i} (e_{i,i} - a_i^2) \\ & = \sum_{i} (e_{i,i} - \sum_j e_{i,j}^2) & = Tre - \sum_{i,j} e_{i,j}^2 \end{align*}$$

• $\hat e_{i,i}$：随机网络中社区$i$内连边数占比期望
• $e_{i,j}$：社区$i,j$中节点间连边数在所有边中所占比例
• $ai = \sum_j e{i,j}$：与社区$i$中节点连边数比例

• 思想：随机网络不会具有明显社团结构

  • 不考虑节点所属社区在节点对间直接连边，则应有 $\hat e{i,j} = a_i a_j$，特别的 $\hat e{i,i} = a_i^2$

  • 比较社区实际覆盖度、随机连接覆盖度差异评估对社区结构 的划分

• 划分对应Q值越大，划分效果越好

  • $0< Q <1$：一般以$Q=0.3$作为网络具有明显社团结构的 下限
  • 实际网络中$Q{max} \in [0.3, 0.7]$，$Q{max}$越大 网络分裂（聚类）性质越强，社区结构越明显

• 缺点

  • 采用完全随机形式，无法避免重边、自环的存在，而现实 网络研究常采用简单图，所以Q值存在局限
  • Q值分辨能力有限，网络中规模较大社区会掩盖小社区， 即使其内部连接紧密

• 覆盖度：社区内部连接数占总连接数比例

模块密度D

$$\begin{align*} D & = \sum_{i=1}^M d(S_i) \\ & = \sum_{i=1}^K \frac {|E_{in}(S_i)| - |E_{out}(S_i)|} {|V_{in}(S_i)} \begin{align*}$$

• 模块密度D表示社区内部连边、社区间连边之差与社区节点总数 之比
  • 值越大表示划分结果越好
  • 考虑社区总节点数，克服模块度Q无法探测小社区的缺陷

社区度C

$$C = \frac 1 M \sum_{i=1}^M [\frac {|E_{in}(S_i)|} {|V(S_i)|(|V(S_i)| - 1) / 2} - \frac {|E_{out}(S_i)|} {|V(S_i)| (|V| - V(S_i)|}]$$

• $\frac {|E_{in}(S_i)} {|V(S_i)||(|V(S_i)-1)/2}$：社区 $S_i$的簇内密度
• $\frac {|E_{out}(S_i)} {|V(S_i)||(|V|-|V(S_i))}$：社区 $S_i$的簇内密度

Fitness函数

$$\begin{align*} f_i & = \frac {d_{in}(S_i)} {d_{in}(S_i) + d_{out}(S_i)} \\ & = \frac {2 * E_{in}(S_i)} {2 * E_{in}(S_i) + E_{out}(S_i)} \\ \bar f = \frac 1 M \sum_{i=1}^M f_i \end{align*}$$

• $f_i$：社区$S_i$的fitness函数
• $d{in}(S_i) = 2 * E{in}(S_i)$：社区$S_i$内部度
• $d{out}(S_i) = E{out}(S_i)$：社区$S_i$外部度
• $\bar f$：整个网络社区划分的fitness函数

• fitness函数使用直接的方式避开了模块度Q函数的弊端
  • 应用结果显示其为网络社区结构的有效度量标准

Modularity

$$Q = \frac 1 {2|E|} \sum_{i,j}$$

社区发现算法

网络测试集

• Girvan、Newman人工构造网络

  • 网络包含128个节点、平均分为4组
  • 每组内部连边、组间连边概率分别记为$p{in}, p{out}$
  • 要求每个节点度期望为16

• Lancichinet ti人工构造网络

  • 测试集中节点度、社区大小服从幂律分布
  • 混淆参数$\mu$控制社区结构显著程度

• 小规模、社区结构已知真实网络

  • Zachary空手道俱乐部
  • 海豚社会关系网络
  • 美国大学生足球俱乐部网络

社区发现算法

• Agglomerative Method：凝聚算法

  • NF算法
  • Walk Trap

Division Method：分裂算法

• Girvan-Newman算法
• 边聚类探测算法

• 凝聚算法流程

  • 最初每个节点各自成为独立社区
  • 按某种方法计算各社区之间相似性，选择相似性最高的社区 合并
    • 相关系数
    • 路径长度
    • 矩阵方法
  • 不断重复直至整个网络成为一个社区

• 算法流程可以的用世系图表示

  • 可以在任意合并步骤后停止，此时节点聚合情况即为网络中 社区结构
  • 但应该在度量标准值最大时停止

• 分裂算法流程同凝聚算法相反

Girvan-Newman算法

GN算法

• 流程

  • 计算网络中各边相对于可能源节点的边介数
  • 删除网络中边介数较大的边，每当分裂出新社区 （即产生新连通分支）
    • 计算网络的社区结构评价指标
    • 记录对应网络结构
  • 重复直到网络中边都被删除，每个节点为单独社区，选择 最优评价指标的网络结构作为网络最终分裂状态

• 缺点：计算速度满，边介数计算开销大，只适合处理中小规模 网络

Newman Fast Algorithm

NF快速算法：

• 流程

  • 初始化网络中各个节点为独立社区、矩阵$E={e_{i,j}}$

    $$\begin{align*} e_{i,j} & = \left \{ \begin{array}{l} \frac 1 {2M}, & 边(i,j)存在 \\ 0, & 节点间不存在边 \end{array} \right. \\ a_i & = \frac {d_i} {2M} \end{align*}$$

    • $M$：网络中边总数
    • $e_{i,j}$：网络中社区$i,j$节点边在所有边中占比
    • $a_i$：与社区$i$中节点相连边在所有边中占比

  • 依次合并有边相连的社区对，计算合并后模块度增量

    $$\Delta Q = e_{i,j} + e_{j,i} = 2(e_{i,j}-a_i a_j)$$
    • 根据贪婪思想，每次沿使得$Q$增加最多、减少最小 方向进行
    • 每次合并后更新元素$e_{i,j}$，将合并社区相关行、 列相加
    • 计算网络社区结构评价指标、网络结构

  • 重复直至整个网络合并成为一个社区，选择最优评价指标 对应网络社区结构

• 基于贪婪思想的凝聚算法

• GN算法、NF算法大多使用无权网络，一个可行的方案是计算无权 情况下各边介数，加权网络中各边介数为无权情况下个边介数 除以边权重

  • 此时，边权重越大介数越小，被移除概率越小，符合社区 结构划分定义

Edge-Clustering Detection Algorithm

边聚类探测算法：

• 流程：
  • 计算网络中尚存的边聚类系数值
  • 移除边聚类系数值最小者$(i,j)$，每当分裂出新社区 （即产生新连通分支）
    • 计算网络社区评价指标fitness、modularity
    • 记录对应网络结构
  • 重复直到网络中边都被删除，每个节点为单独社区，选择 最优评价指标的网络结构作为网络最终分裂状态

Walk Trap

随机游走算法：

Label Propagation

标签扩散算法：

Self-Similar

（网络结构）自相似性：局部在某种意义上与整体相似

• fractal分形的重要性质

Random Walk

（网络）随机游走：

游走形式

• unbiased random walks：无偏随机游走，等概率游走
• biased random walks：有偏随机游走，正比于节点度
• self-avoid walks：自规避随机游走
• quantum walks：量子游走

研究内容

• first-passage time：平均首达时间

  $$F(s,t)$$

• mean commute time：平均转移时间

  $$C(t,s) = F(s,t) + F(t,s)$$

• mean return time：平均返回时间

  $$T(s,s)$$

用途

• community detection：社区探测
• recommendation systems：推荐系统
• electrical networks：电力系统
• spanning trees：生成树
• infomation retrieval：信息检索
• natural language proessing：自然语言处理
• graph partitioning：图像分割
• random walk hypothesis：随机游走假设（经济学）
• pagerank algorithm：PageRank算法

网络可视化

Graph Layout

图布局：无实际意义但是影响网络直观效果

• random layout：随机布局，节点、边随机放置
• circular layout：节点放在圆环上
• grid layout：网格布局
• force-directed layout：力导向布局
  • 最常用
  • 动态、由节点相互连接决定布局
  • 点距离较近节点在放置在较近位置
• YiFan Hu layout
• Harel-Koren Fast Multiscale Layout
• NodeXL：节点以box形式被展示，边放置在box内、间

Visualizing Network Features

网络特征可视化：边权、节点特性、标签、团结构

• 标签：只显示感兴趣标签
• 度、中心性、权重等量化特征：借助大小、形状、颜色体现
• 节点分类信息：节点节点颜色、形状体现

Scale Issue

网络可视化：是否对所有网络均有可视化必要

• 网络密度太小、太大，无可视化必要

现实网络

• 网络科学：现实世界的任何问题都可以用复杂关系网络近似模拟

  • 节点：研究问题中主体
  • 边：模拟主体间的某种相互关系

• 现实网络大多为无标度网络，且幂指数$\gamma \in [2, 3]$

  • 网络中大部分节点度很小，小部分hub节点有很大的度
  • 对随机攻击稳健，但对目的攻击脆弱
  • triangle power law：网络中三角形数量服从幂律分布
  • eigenvalue power law：网络邻接矩阵的特征值服从 幂律分布

• 绝大多数现实网络、网络结构模型虽然不能只管看出自相性， 但是在某种length-scale下确实具有自相似性

  • 万维网
  • 社会网络
  • 蛋白质交互作用网络
  • 细胞网络

• 个体社会影响力：社交网络中节点中心性

• power-law distribution：幂律分布
• scale-free network：无标度网络，度分布服从幂律分布的 复杂网络，具有无标度特性
• heavy-tailed distribution：厚尾分布

社交网络

• 人、人与人之间的关系确定，则网络结构固定

• 有人类行为存在的任何领域都可以转化为社交网络形式

  • offline social networks：线下社交网络，现实面对面 接触中的人类行为产生，人类起源时即出现
  • online social networks/social webs：在线社交网络
  • social media websites：多媒体网社交网

• 由于社交网络中人类主观因素的存在，定性特征可以用于社交 网络分析

  • 关系强弱
  • 信任值

• 对网络结构的分析的数量化指标可以分析社交网络的基本特征

  • 度、度分布
  • 聚类系数
  • 路径长度
  • 网络直径

• 数据分析类型

  • Content Data：内容数据分析，文本、图像、其他多媒体 数据
  • Linkage Data：链接数据分析，网络的动力学行为：网络 结构、个体之间沟通交流

社交网络中社区发现

• 现实世界网络普遍具有模块/社区结构特性

  • 内部联系紧密、外部连接稀疏
  • 提取社区/模块结构，研究其特性有助于在网络动态演化 过程中理解、预测其自然出现的、关键的、具有因果关系的 本质特性

• 挑战

  • 现实问题对应的关系网络
    • 拓扑结构类型未知
    • 大部分为随时间变化网络
    • 规模庞大
  • 现有技术方法应用受到限制
    • 多数方法适用静态无向图，研究有向网络、随时间动态 演化网络形式技术方法较少
    • 传统算法可能不适用超大规模网络

• 社区发现/探测重要性

  • 社区结构刻画了网络中连边关系的局部聚集特性，体现了 连边的分布不均匀性
  • 社区通常由功能相近、性质相似的网络节点组成
    • 有助于揭示网络结构和功能之间的关系
    • 有助于更加有效的理解、开发网络