HTML

机器学习笔记

评估指标

Precision 准确率

查准率, PPV

How many selected items are relevant?

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

Recall 召回率 TPR

查全率, sensitivity, recall, hit rate, TPR

How many relevant items are selected?

$recall = \frac{TP} {P} = \frac{TP} {TP + FN}$

TNR

specificity, selectivity, TNR, 1 - FPR

$TNR = \frac{TN}{P}$

FPR

false alarm ratio

$FPR = \frac{FP}{N} = \frac{FP} {TN + FP}$

Accuracy

$accuracy = \frac{TP + TN}{TP + TN +FP + FN}$

F1 score

准确率和召回率的调和平均值

$\begin{aligned} \frac{2} {F_1} = \frac{1} {accuracy} + \frac{1} {recall} \\ F_1 = \frac{1} {2 * (\frac{1}{accuracy} + \frac{1}{recall})} = \frac{accuracy + recall}{2 * accuracy * recall} \end{aligned}$

ROC / AUC

Receiver Operating Characteristic, 考虑二分类问题, 调整阈值, 绘制 TPR 和 FPR 坐标曲线如下图. 其中左上角是完美的分类结果, 右下角是最差的分类结果, 曲线越接近左上角越好。

$\begin{aligned} \text{TPR} &= \text{ recall } = \text{ sensitivity } = \frac{\text{TP}}{\text{TP} + \text{FN}}\\ \text{FPR} &= 1 - \text{specificy} = \frac{\text{FP}}{\text{FP}+\text{TN}}\\ \text{specificy} &= \frac{\text{TN}}{\text{TN} + \text{FP}} \end{aligned}$

$\begin{aligned} y(t) &= \text{TPR}(t)= \frac{N_+(t)}{N_+}\\ x(t) &= \text{FPR}(t)= \frac{N_-(t)}{N_-}\\ \text{AUC} &= \int_t y(t)dx(t) \end{aligned}$

Area Under Curve, 表示 ROC 曲线下的面积, 越大越好. 物理意义：任取一对正、负样本，正样本的score大于负样本的概率 (Fawcett, 2006)

证明: 考虑随机取得正负样本对中, 负样本分布在 $[t, t+ \Delta t]$ 的概率为

$\begin{aligned} P(t \le s_- \le t + \Delta t) &= P(s_- > t) - P(s_- > t + \Delta t)\\ &= \frac{N_-(t) - N_-(t+\Delta t)}{N_-}\\ &= x(t) - x(t+\Delta t) \\ &= -\Delta x(t) \end{aligned}$

如果 $\Delta t$ 很小, 那么该证样本大于负样本对概率为

$\begin{aligned} P(s_+ > s_- | t \le s_- \le t+\Delta t) &\approx P(s_+ > t) \\ &= \frac{N_+(t)} {N_+}\\ &= y(t) \end{aligned}$

则有

$\begin{aligned} P(s_+ > s_-) &= - \sum y(t) \Delta x(t) \\ &= \int_{-t} y(t)dx(t) \end{aligned}$

ROC 曲线的一个特性: 当测试集中的正负样本的分布变化的时候, ROC曲线能够保持不变;而 Precision-Recall 曲线会随之变化.

其中 sensitivity 是灵敏度, specificy 是 特异度. 敏感度高则漏诊率低, 特异度高则误诊率低.

AUC 优化: 采用极大似然估计对应损失函数是 logloss, 而不是 AUC. 但在一些排序场景下, 对 AUC 的优化更接近目标, 比如 pairwise 的目标函数（排序损失, 如 rank-SVM / rank-net / 指数损失 / top损失）可以看作是 AUC优化的近似.

ROC

Demo

mAP（信息检索）

AP，average precision，每一类别 precision 值的平均值

mAP，对所有类别的 AP 取均值

例如：假设有两个查询，查询1有4个相关文档，查询2有5个相关文档。某系统对查询1检索出4个相关文档，其rank分别为1,2,4,7；对于查询2检索出3个相关文档，其rank分别为1,3,5。
对于查询1：
P1=1/1，P2=2/2，P3=3/4，P4=4/7
AP1=(1/1+2/2+3/4+4/7)/4=0.83
对于查询2：
P=1/1，P2=2/3, P3=3/5
AP2 = (1/1+2/3+3/5)/5=0.45
最后，mAP =（AP1+AP2）/2 = (0.83+0.45)/ 2=0.6

mAP（图像分类）

TODO

泛化能力

泛化误差

用学到的模型 $\hat f$ 对未知数据预测的误差, 是所学习到模型的期望风险

$R_{exp} (\hat f) = E_p [L(Y,\hat f (X))] = \int_{x \times y} L(y,\hat f(x)) P(x,y) dxdy$

偏差方差权衡：以均方误差为例

偏差 bias 是通过学习拟合出来的结果之期望，与真实结果之间的差距

方差 variance 是通过学习拟合出来的结果自身的不稳定性

模型容量大，过拟合，方差小，偏差大；

模型容量小，欠拟合，方差大，偏差小。

最优模型是在 bias 和 variance 取得平衡，使得误差最小。

过拟合、欠拟合解决思路：数据；特征；迭代次数；正则；模型容量、结构

wiki

均方误差 = bias ^ 2 + variance + random error

$\begin{aligned} E\Big[ \big(y-\hat f(x) \big)^2 \Big] &= Bias \big[\hat f(x)\big] ^2 + Variance\big[\hat f(x)\big] + \sigma ^ 2 \\ Bias\big[\hat f(x)\big] &= E\big[\hat f(x) - f(x)\big]\\ Var\big[\hat f(x)\big] &= E\big[\hat f(x)^2\big] - E\big[\hat f(x)\big]^2 \end{aligned}$

泛化误差上界

性质：它是样本容量的函数，当样本增加时，趋于0；他是假设空间容量的函数，假设空间 (一组函数的集合) 容量越大，模型学习越困难， 泛化误差上界越大。

下面考虑二分类问题, 已知训练集 $T=\{x_i,y_i\}$ , 它是从联合概率分布 $P(X,Y)$ 的独立同分布产生的, $X\in \mathbb{R}^n, Y \in \{-1,+1\}$ , 假设空间函数的有限集合 $F=\{f_1,f_2,...,f_d\}$ , d 是函数个数. 设 $f$ 是从 $F$ 中选取的函数, 损失函数是 0-1 损失, 关于 $f$ 的期望风险和经验风险是

$\begin{aligned} R(f)=E[L(Y,f(X))] \\ \hat R(f)=\frac{1}{n} \sum_{i=1}^{N}L(y_i,f(x_i)) \end{aligned}$

经验风险最小化函数是

$f_N=\arg\ \min_{f \in F} \ \hat R(f)$

我们关心 $f_N$ 的泛化能力

$R(f_N)=E[L(Y,f_N(x))]$

泛化误差上界

$R(f) \leq \hat R(f)+\epsilon(d,N,\delta)$

其中

$\epsilon(d,N,\delta)=\sqrt{\frac{1}{N} (\log d + \log \frac{1}{\delta})}$

其中 $R(f)$ 是泛化误差, 右端 $\epsilon(d,N,\delta)$ 既为泛化误差上界

可以看出, 样本越多, 泛化误差趋于0;空间 $F$ 包含的函数越多, 泛化误差越大. 证明见《统计学习方法》 P16.

以上讨论的只是假设空间包含有限个函数情况下的泛化误差上界, 对一般的假设空间要找到泛化误差上界较复杂.

没有免费午餐定理

Wolpert 96’, The Lack of A Priori Distinctions Between Learning Algorithms

假设：数据是一个有限集，而且训练和测试是独立的、各自对应不同分布的数据。

表明：在所有可能的数据生成分布上平均之后，每一个分类算法在未事先观测的点上有相同的错误率。

比如在所有可能的任务上，最先进的二分类算法 f(x) 和弱智算法 g(x)=1有着相同的平均性能。

我们应该根据真实世界的数据分布，寻找更优的算法。

IV & WOE

[数据挖掘模型中的IV和WOE详解](http://blog.csdn.net/kevin7658/article/details/50780391)

IV 和 WOE 常见于风险评估模型, 可以用 IV 来衡量变量的预测能力.

对变量进行分组处理 (离散化), 分成 i 组, 有

$\begin{aligned} WOE_i = \ln(\frac{py_i}{pn_i}) = ... \\ IV_i = (py_i - pn_i) * WOE_i \end{aligned}$

这个变量的 $IV$ 是

$IV = \sum_{i=1}^n IV_i$

其中 $py_i$ 是这个组中的响应客户 (违约客户) 占样本中所有响应客户的比例, $pn_i$ 是这个组中未响应用户占样本中所有未响应客户的比例.

IV 越大, 特征越重要

回归问题

给定一个训练集

$T={(x_1,y_1), (x_2,y_2),...,(x_n,y_n)}$

构造一个函数 $Y=f(X)$ .

对新的输入 $x_{n+1}$ , 根据学习到的函数 $Y=f(X)$ 计算 $y_{n+1}$ .

分类问题

给定一个训练集

$T={(x_1,y_1), (x_2,y_2),...,(x_n,y_n)}$

构造一个条件概率分布模型

$P(Y^{(1)},Y^{(2)},...,Y^{(n)}) | X^{(1)},X^{(2)},...,X^{(n)})$

其中, 每个$X^{(i)}$取值取值为所有可能的观测, 每个$Y^{(i)}$取值为所有可能的分类结果.

对新的预测序列 $x_{n+1}$ , 找到条件概率$P(y_{n+1}|x_{n+1})$最大的标记序列 $y_{n+1}$ , 得到预测结果.

线性回归

对样本 $T=\{(x_0,y_0),...,(x_N,y_N)\}, x_i \in X \subseteq \mathbb{R}^{m+1}, y_i \in Y \subseteq \mathbb{R}^{1}$ , 其中 $m$ 是特征, $x$ 的第 $m+1$ 是常数 $1$

Least Square

又称最小二乘法, 通过最小化平方和误差得到参数估计

$L(w) = \frac{1}{N} ||Y-X w||^2$

当 $X$ 是满秩的, 即 $rank(X) = dim(x)$ , 行/列互不线性相关, 有解析解

$\hat w = (X^T X)^{-1} X^T Y$

但实际问题中 X 往往不是满秩的, 上式的协方差矩阵 $X^T X$ 不可逆, 目标函数最小化导数为零时方程有无穷解，没办法求出最优解, 同时存在 overfitting 问题, 这时需要对参数进行限制

L2 最小岭回归

对参数分布的先验假设：高斯分布，即 $f(x|u=0,\sigma)=\frac{1}{\sigma \sqrt{2\pi}}\exp \big(-\frac{(x-\mu)^2}{2\sigma^2}\big)$

损失函数加入L2惩罚项：

$L(w) = \frac{1}{N} ||Y-X\omega||^2 + \frac{\lambda}{2} ||w||^2$

优点：连续可导，容易求解

L1 LASSO

对参数分布的先验假设：拉普拉斯分布，即 $f(x|u=0,b)=\frac{1}{2b}\exp\big(-\frac{|x-\mu|}{b}\big)$

加入L1惩罚项, 把参数约束在 $L1\ ball$ 中，使更多的系数为 0, 可以用来做特征选择, 具有可解释性

$L(w) = \frac{1}{N} ||Y-X\omega||^2 + \frac{\lambda}{2} ||w||^1$

或优化目标形式

$\begin{aligned} \min_w \frac{1}{2}||y-Xw||^2 \\ \text{s.t.} ||w||^1 < \theta \end{aligned}$

有解析解

$\hat w_R = (X^T X + \lambda I)^{-1} X^T y$

缺点：求最小值在零点计算麻烦，可能存在多个最优解

优点：稀疏解，鲁棒性更强，对异常值不敏感

Elastic Net

融合 L1+L2，其中的L1正则项产生稀疏模型，L2正则项产生以下几个作用：

1. 消除L1正则项中选择变量个数的限制（即稀疏性）
2. 产生 grouping effect（对于一组相关性较强的原子，L1会在相关的变量间随机的选择一个来实现稀疏）
3. 稳定L1正则项的路径

其结构有如下两个特点：

1. 在顶点具有奇异性（稀疏性的必要条件）
2. 严格的凸边缘（凸效应的强度随着α而变化（产生grouping效应））

总结：

1. 弹性网络同时进行正则化与变量选择
2. 能够进行grouped selection
3. 当 $p>>n$，特征多于样本时，或者严重的多重共线性情况时，效果明显
4. 当α接近0时，elastic net表现接近lasso，但去掉了由极端相关引起的退化或者奇怪的表现
5. 当 α 从1变化到0时，目标函数的稀疏解（系数为0的情况）从0增加到lasso的稀疏解

LR

源自 Logistic 分布, 是由输入对线性函数表示的输出的对数几率模型

对一个二分类问题，假设样本随机变量 $X$ 服从伯努利分布 (0-1分布) , 即概率质量函数为

$f_X(x)=p^x(1-p)^{1-x},x \in \{0,1\}$

期望值 $E[X]=p$ , 方差 $var[X]=p(1-p)$

二项逻辑斯谛回归模型是一种分类模型, 由条件概率分布 $P(Y|X)$ 表示

$P(Y=0|x)=\frac {1} {1 + e^{-w x}}$

$P(Y=1|x)=\frac {e^{-w x}} {1 + e^{-w x}}$

训练集: 训练集 $D$ 特征集 $A$

输入: 样本 $x$

输出: $0\le y \le1$

定义事件发生几率 (Odds)

$\frac {p} {1-p}$

对数几率, 或 logit 函数为

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

对逻辑斯谛回归而言

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

有时 $w x + b$ 简记为 $w x$ .

物理意义：输出 $Y=1$ 的对数几率是输入 $x$ 的线性函数, 或者说, 输出 $Y=1$ 的对数几率是由输入 $x$ 的线性函数表示的模型, 即逻辑斯谛回归模型.

参数估计

为简化推导, 设

$P(Y=1|x;w)=\sigma(wx), P(Y=0|x;w)=1-\sigma(wx)$

其中 $\sigma$ 是 sigmoid 函数

$\sigma(x) = \frac{1}{1 + e^{-x}}$

似然函数为

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

加上对数后的最大似然估计, 即损失函数为

$\begin{aligned} L(w) &= \sum_{i=1}^{N}[y_i \ln \sigma (w x_i) + (1 - y_i) \ln (1-\sigma(w x_i))]\\ & =\sum_{i=1}^{N}[y_i \ln \frac {\sigma (w x_i)} {1-\sigma (w x_i)} + \ln (1-\sigma(w x_i))]\\ & =\sum_{i=1}^{N}[y_i(w x_i) + \ln (1-\sigma(w x_i))]\\ \end{aligned}$

对 $L(w)$ 求极大值, 常用 迭代尺度法(IIS) / 梯度下降法 / 拟牛顿法, 得到 $w$ 的估计值.

损失函数的一阶、二阶导数为

$\begin{aligned} \frac{\partial L(w)}{\partial w} = X^T (y-\sigma) \\ \frac{\partial^2 L(w)}{\partial w \partial w^T} = - X^T W X \end{aligned}$

其中

$\begin{aligned} W_{ij} &= \sigma(x_i; w)(1 - \sigma(x_j; w))\\ \sigma_i &= \sigma(x_i; w)\\ \sigma'(w) &= \sigma(w)(1-\sigma(w))\\ \end{aligned}$

ref

用法

输入特征相互独立 (descrete)

算法把输入问题通过对数转换

最大熵模型

熵满足下列不等式

$0\leq H(P) \leq \log |X|$

其中, $|X|$ 是 $X$ 的取值个数, 当且仅当 $X$ 的分布是均匀时, 等式 $H(P) = \log|X|$ 成立. 即当 X 服从均匀分布时, 熵最大

熵最大模型认为, 学习概率模型时, 在所有可能的概率分布模型中, 熵最大的模型, 即等可能分布的模型是最好的模型.

The equivalence of logistic regression and maximum entropy models

LR 模型在建模时建模预测 $P(Y|X)$ , 并认为 $P(Y|X)$ 服从伯努利分布, 所以我们只需要知道 $P(Y|X)$ ;其次我们需要一个线性模型, 所以 $P(Y|X) = f(wx)$ . 接下来我们就只需要知道 $f$ 是什么就行了. 而我们可以通过最大熵原则推出的这个 $f$ , 即 $sigmoid$ 函数

给定训练集 $T=\{(x_1,y_1), ..., (x_N, y_N)\}$ , 可以确定联合分布 $\hat{P}(X,Y)$ 的经验分布

$\hat{P}(X=x,Y=y)=\frac{v(X=x,Y=y)}{N}$

和边缘分布 $P(X=x)$的经验分布

$\hat{P}(X=x)=\frac{v(X=x)}{N}$

那么, 特征函数 $f(x,y)$ 关于经验分布 $\hat{P}(X,Y)$ 的期望值, 用 $E_{\hat{P}}(f)$ 表示

$\begin{aligned} E_{\hat{P}}(f)=\sum\limits_{x,y} \hat{P}(x,y)f(x,y)\\ E_{P}(f)=\sum\limits_{x} \hat{P}(x)P(y|x)f(x,y) \end{aligned}$

如果模型可以获得训练数据中的信息, 那么可以假设这两个值相等

$E_{\hat{P}}(f)=E_{P}(f)$

将上式子作为约束条件. 如果有 $n$ 个特征函数, 那么就有 $n$ 个约束条件

最大熵模型: 假设满足所有约束条件的模型集合为

C\equiv\{P \in P_{all} | E_P(f_i)= E_\hat{P}(f_i), i=1,2,...,n\}

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

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

则模型集合 $C$ 中条件熵 $H(P)$ 最大的模型, 称为最大熵模型

熵最大模型的学习

对给定训练集 $T=\{(x_1,y_1),...,(x_N,y_N)\}$ 以及特征函数 $f_i(x,y)$，求解最优化问题

$\begin{aligned} \min_{P\in C} \text{ } & -H(P)=\sum_{x,y} \tilde P(x)P(y|x) \log P(y|x)\\ s.t. \text{ } & E_p(f_i) - E_{\tilde P}(f_i) = 0, i = 1,2,...,n \\ \text{ } & \sum_y P(y|x)=1 \end{aligned}$

Softmax

对多分类问题, 假设离散型随机变量 $Y \in \{1,2,...,K\}$, 那么逻辑斯谛模型推广到 softmax 有:

$\begin{aligned} P(Y=k|x)=\frac {\exp(w_k \cdot x )} {1+\sum_{k=1}^{K-1} \exp (w_k \cdot x)}, k=1,2,...,K-1 \\ P(Y=K|x)=\frac{1}{1+\sum_{k=1}^{K-1}\exp(w_k \cdot x)} \end{aligned}$

这里, $x \in \mathbb{R}^{n+1},w_k \in \mathbb{R}^{n+1}$

KL 散度

在信息系统中称相对熵，在连续时间序列中成为随机性，在统计推断模型中成为信息增益，也称信息散度。

KL散度是两个概率分布P和Q差别的非对称性的度量。 KL散度是用来度量使用基于Q的分布来编码服从P的分布的样本所需的额外的平均比特数。典型情况下，P表示数据的真实分布，Q表示数据的理论分布、估计的模型分布、或P的近似分布。

对于离散随机变量，其概率分布 P 和 Q 的 KL 散度定义

$KL(P||Q)=-\sum_{i}P(i) \ln \frac{Q(i)}{P(i)}=\sum_{i}P(i) \ln \frac{P(i)}{Q(i)}$

对于连续随机变量，其概率分布 P 和 Q 的 KL 散度定义

$KL(P||Q)=\int p(x)\ln \frac{p(x)}{q(x)} dx$

交叉熵

在信息论中，基于相同事件测度的两个概率分布 p 和 q 的交叉熵是指，当基于一个“非自然”（相对于“真实”分布 p 而言）的概率分布 q 进行编码时，在事件集合中唯一标识一个事件所需要的平均比特数（bit）。

给定两个概率分布 p 和 q， p 相对于 q 的交叉熵定义为：

$H(p,q) = \mathbb E_p [-\log q] = H(p) + KL(p||q)$

对于离散分布 p 和 q，交叉熵定义为：

$H(p,q)=-\sum_x p(x) \log q(x)$

$Cross Entropy = - \sum_i y_i \ln P(Y=y_i|x_i)$

在逻辑回归模型 $P(Y=1|X;w)=\sigma(wx)$ 中，损失函数 $L$ 是交叉熵

$L(w) = - \sum_{(x_i,y_i)\in D} y_i ln P(Y=1|x_i;w) + (1-y_i) P(Y=0|x_i;w)$

对损失函数 $L$ 求关于 $w_i$ 偏导，由链式法则得到

\begin{align} \frac{\delta L}{\delta w_i} &= \frac{\delta L}{\delta p} \frac{\delta p}{\delta s} \frac{\delta s}{\delta w_i} \\ &=[\sigma(s) - y] x_i \end{align}

其中 $s=wx,p=\sigma(s)$

可以看到，交叉熵的求导计算复杂度很低。

k-NN

1968 Cover & Hart

一种高效实现: KD 树

Adaboost

在概率近似正确 (PAC) 学习的框架中, 一个类如果存在一个多项式的学习算法能够学习它且正确率 [高|仅比随机猜测略好] , 称这个类是 [强|弱] 可学习的

Schapire 证明: 在 PAC 学习框架中, 强可学习 $\leftrightarrows$ 弱可学习

Adaboost 从一个弱分类学习算法出发, 反复学习, 得到一组若分类器, 然后构成一个强分类器. 在每一轮改变训练数据的权值或概率分布, [提高|降低]前一轮被[错误|正确]分类样本的权值;采取加权多数表决的方法, [加大|减少]分类误差率[小|大]的弱分类器的权值,

以二分类问题为例, 给定样本 $T= \{ (x_1,y_1),...,(x_N,y_N) \} ,x\in X, y\in Y = \{ -1,+1 \}$ , 其中 $X$ 是样本空间, $Y$ 是标签集合.

输入: 训练集 $T$ ;弱学习算法

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

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

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

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

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

$G_m(x):X \to {-1,1}$

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

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

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

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

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

$\begin{aligned} D_{m+i}=(w_{m+1,1} ..., w_{m+1,i},..., w_{m+1,N}) \\ w_{m+1,i}=\frac{w_{mi}}{Z_m} \exp ({-\alpha_m y_i G_m(x_i)}) \end{aligned}$

这里 $Z_m$ 是规范化因子

$Z_m=\sum_{i=1}^{N}w_{mi}\exp(-\alpha_my_iG_m(x_i))$

它使 $D_m$ 成为一个概率分布

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

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

最终得到分类器

$G(x)=sign(f(x))$

算法解释

有一种解释, 可以认为 AdaBoost 是模型为加法模型、损失函数为指数函数, 学习算法为前向分步算法时的二分类学习方法.

加法模型

$f(x)=\sum_{m-1}^{M}\beta_mb(x;\gamma_m)$

其中 $b(x;\gamma_m)$ 是基函数, $\gamma_m$ 是基函数的参数, $\beta_m$ 是基函数的系数

给定训练集 $T$ 和损失函数 $L(y,f(x))$ , 学习加法模型 $f(x)$ 即损失函数的最小化问题

$\min_{\beta_m,\gamma_m} {\sum_{i=1}^{N} L\bigg(y_i,\sum_{m-1}{M}\beta_mb(x;\gamma_m)\bigg)}$

前向分步算法

学习加法模型时, 从前向后, 每一步只学习一个基函数及其系数, 逐步逼近优化目标, 达到简化计算复杂度

输入: 训练集 $T=\{(x_i,y_i\}$;损失函数 $L(y,f(x))$;基函数集 $\{b(x,\gamma\}$

输出: 加法模型 $f(x)$

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

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

   a. 极小化损失函数

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

   得到参数 $\beta_m,\gamma_m$

   b. 更新

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

3. 得到加法模型

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

这样, 算法将同时求解从 $m=1$ 到 $M$ 所有参数 $\beta_m,\gamma_m$ 的优化问题简化为逐渐求解各个 $\beta_m,\gamma_m$ 的优化问题

Boosting Tree

提升树, 是以分类树或回归树为基本分类器的提升方法. 它采用加法模型与前向分步算法, 以决策树为基函数的提升方法. 对 [分类|回归] 问题的决策树是二叉 [分类|回归] 树.

提升树可以表示为决策树的加法模型

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

其中 $T$ 表示决策树, $\Theta_m$ 表示决策树的参数, $M$ 表示树的个数

提升树用前向分步算法训练

1. 令初试提升树 $f_0(x)=0$

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

$f_m(x)=f_{m-1}(x)+T(x;\Theta_m)$

其中 $f_{m-1}$ 是当前模型, 通过经验风险极小化确定下一棵树的参数 $\Theta_m$

$\hat \Theta_m = \arg\ \min \sum_{i=1}^{N}L(y_i,f_{m-1}+T(x_i;\Theta_m))$

当采用平方误差损失函数时

$\begin{aligned} L(y,f(x)) &= (y-f(x))^2\\ & =[y-f_{m-1}(x)-T(x;\Theta_m)]^2\\ & =[\gamma-T(x;\Theta_m)]^2 \end{aligned}$

这里

$\gamma = y-f_{m-1}(x)$

由于树的线性组合可以很好地你和训练数据, 即使数据中的输入与输出关系很复杂, 所以提升树是一个高功能的学习算法

回归问题的提升树算法

如果输入空间 $X$ 划分为 $J$ 个互不相交的区域 $R_1,R_2,...,R_n$ , 并且在每个区域上输出固定的常量 $c_j$ , 那么树可表示为

$T(x;\Theta)=\sum_{j=1}^{j}c_jI(x\in \mathbb{R}_j)$

其中 $I(x)=1\ if\ x\ is\ true\ else\ 0$

输入: 训练集 $T=\{(x_1,y_1,...,(x_n,y_n)\},x_i \in X \subseteq \mathbb{R}^n,y_i \in Y \subseteq \mathbb{R}$

输出: 提升树 $f_M(x)$

1. 初始化 $f_0(x)$

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

   a. 计算残差

   $\gamma_{mi}=y_i-f_{m-1}(x_i),i=1,2,...,N$

   b. 拟合残差 $\gamma_{mi}$ 学习一个回归树, 得到 $T(x;\Theta_m)$

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

3. 得到提升回归树

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

特征

Feature Engineering is the process of transforming raw data into features that better represent the underlying problem to the predictive models, resulting in improved model accuracy on unseen data. —— Jason Brownlee

特征工程

大帝: 特征工程简介

美团: 机器学习中的数据清洗与特征处理综述

使用sklearn做单机特征工程

在使用线性模型如 LR, 特征构造十分重要. 构造过程为

1. 任务的确定
2. 数据的选择: 获取难易程度, 覆盖率, 准确率
3. 预处理数据
4. 特征构造:
   1. 标准化(统一单位)
   2. 归一化
      • 线性（linearization）最大最小归一化
      • 对数（logarithm）归一化 $f(x)=\log (1+x)$
      • 双曲线归一化 $f(x)=x/(x+1)$
      • z-score 的归一化 $(x-u)/\sigma$
      • 排序归一化
   3. 离散化, 比方说通过等频率分割（Equal-Frequency）得到的特征比等区间分割（Equal-Interval）得到的特征具有更好的区分性. 一般流程是对特征做排序－> 选择合适的分割点－> 作出对整体的分割 －> 查看分割是否合理，是否能够达到停止条件
   4. 二值化
   5. 特征交叉, 比如特征 (女性, 八卦新闻点击率) $\in (0,1)$
   6. 缺省值处理, 如单独表示, 众数, 平均值
5. 特征降维, PCA, LDA
6. 特征选择 (按选择方法)
   1. 过滤 (filter): 可以通过相关系数 (correlation coefficient) 来评估特征 X 和 Y 是否线性相关 $\rho_{X,Y} = cov(X,Y)/(\sigma_X \sigma_Y) \in [-1,1]$ , 如果 $\rho_{XY} > 0$ 说明线性相关, 如果 $\rho_{XY} < 0$ 则是线性反相关, 如果 $\rho_{XY} = 0$ 也只是说明两个变量是线性无关的, 并不能推出它们之间是独立的.
   2. 包装 (wrapper), 先选定一种评估模型的指标如 Area Under Curve / Mean Absolute Error/ Mean Square Error, 通过[前|后]项特征选择或者, 有[空|满]特征集开始, 每次[增加|剔除]一个能让模型提升最[快|慢]的特征. 或者用增 L 去 R 算法（Plus-L Minus-R Selection ($L < R$)
   3. 嵌入 (embedding), 如 RF, Logistic Regression 的一些算法，可以参考 TG（Truncated Gradient Algorithm），FOBOS（Forward and Backward Splitting），RDA（Regularized Dual Averaging Algorithm）， FTRL（Follow-the-Regularized-Leader Algorithm） 算法 Ad Click Prediction: a View from the Trenches
7. 特征选择 (按搜索方法)
   1. 完全搜索(Complete)
      • 广度优先搜索( Breadth First Search ) 广度优先遍历特征子空间。枚举所有组合，穷举搜索，实用性不高。
      • 分支限界搜索( Branch and Bound ) 穷举基础上加入分支限界。例如：剪掉某些不可能搜索出比当前最优解更优的分支。
      • 其他，如定向搜索 (Beam Search )，最优优先搜索 ( Best First Search )等
   2. 启发式搜索(Heuristic)
      • 序列前向选择( SFS ， Sequential Forward Selection ) 从空集开始，每次加入一个选最优。
      • 序列后向选择( SBS ， Sequential Backward Selection ) 从全集开始，每次减少一个选最优。
      • 增L去R选择算法 ( LRS ， Plus-L Minus-R Selection ) 从空集开始，每次加入L个，减去R个，选最优（L>R)或者从全集开始，每次减去R个，增加L个，选最优(L<R)。
      • 其他如双向搜索( BDS ， Bidirectional Search )，序列浮动选择( Sequential Floating Selection )等
   3. 随机搜索(Random)
      • 随机产生序列选择算法(RGSS， Random Generation plus Sequential Selection) 随机产生一个特征子集，然后在该子集上执行SFS与SBS算法
      • 模拟退火算法( SA，Simulated Annealing ) 以一定的概率来接受一个比当前解要差的解，而且这个概率随着时间推移逐渐降低
      • 遗传算法( GA，Genetic Algorithms ) 通过交叉、突变等操作繁殖出下一代特征子集，并且评分越高的特征子集被选中参加繁殖的概率越高

自然语言

借助外部数据集训练模型, 如 WordNet, Reddit评论数据集

基于字母而非单词的NLP特征

衡量文本在视觉上的相似度, 如逐字符的序列比较 (difflib.SequenceMatcher)

标注单词的词性, 找出中心词, 计算基于中心词的各种匹配度和距离

将产品标题/介绍中 TF-IDF 最高的一些 Trigram 拿出来, 计算搜索词中出现在这些 Trigram 中的比例;反过来以搜索词为基底也做一遍. 这相当于是从另一个角度抽取了一些 Latent 标识

一些新颖的距离尺度, 比如 Word Movers Distance

除了 SVD 以外还可以用上 NMF

视觉

预处理, 二值化、灰度、卷积、sobel边缘

衡量美观、明暗、相似度的指标

组合特征

KM 世界杯排名预测第一名, 开发了几个特征, 衡量球队的综合能力

筛选

Random Forest 的 Imoprtance Feature (原理TODO) , 根据每个特征对信息增益贡献的大小, 来筛选特征.

调参

Overfitting

表现

• 准确率在训练集高、测试集低、验证集低
• 泛化误差, 泛化误差上界

避免方法

• 调整训练集、测试集比例

• 调整模型复杂度参数, 如 RandomForest、Gradient Boosting Tree 的深度, CNN 深度

• 正则项, NN 的 dropout maxpool 层, ReLU 单元.

• 验证集合连续n个迭代分数没有提高, 停止训练

• 5-Fold Cross Validation

• 利用随机性跳出局部最优解: 遗传算法, 何时重启计算问题Science: An Economics Approach to Hard Computational Problems

Ensemble Generation

将多个不同的 base model 组合成一个 Ensemble Model, 可以同时降低模型的偏差 bias 和方差 variance, 提高分数、降低 overfitting 风险 1. 常见方法有

• Bagging, 使用训练数据的不同随机子集来训练每个 Base Model, 最后进行每个 Base Model 权重相同的 Vote. 也即 Random Forest 的原理

• Boosting, 迭代地训练 Base Model, 每次根据上一个迭代中预测错误的情况修改训练样本的权重. 也即 Gradient Boosting 的原理. 比 Bagging 效果好, 但更容易 Overfit

• Blending, 用不相交的数据训练不同的 Base Model, 将它们的输出取 (加权) 平均. 实现简单, 但对训练数据利用少

• Stacking

5-fold-stacking

组装要点:

• Base Model 的相关性尽可能小. Diversity 越大, Bias 越低
• Base Model 的性能表现不能差距太大

附录

拉格朗日乘数法

最优化问题中, 寻找多元函数在其变量受到一个或多个条件约束时的极值的方法

这种方法可以将一个有 n 个变量与 k 个约束条件的最优化问题, 转换为一个解有 n + k 个变量的方程组问题

如最优化问题

$\begin{aligned} \max f(x,y)\\ s.t.\ g(x,y)=c \end{aligned}$

转化为求拉格朗日函数的极值

$L(x,y,\lambda)=f(x,y)+\lambda \cdot \bigg(g(x,y)-c\bigg)$

其中 $\lambda$ 是拉格朗日乘数

Hilbert Space

在一个复数向量空间 $H$ 上的给定的内积 $<.,.>$ 可以按照如下的方式导出一个范数 $||.||$

$||x|| = \sqrt{\big<x,x\big>}$

此空间称为是一个希尔伯特空间，如果其对于这个范数来说是完备的。这里的完备性是指，任何一个柯西列都收敛到此空间中的某个元素，即它们与某个元素的范数差的极限为
0。任何一个希尔伯特空间都是巴拿赫空间，但是反之未必。

Rank

一个矩阵 $A$ 的[列|行]秩是 $A$ 的线性独立的纵[列|行]的极大数目。

行秩 == 列秩，统称矩阵的秩

$A_{m\cdot n}$ 的秩最大为 $min(m,n)$

计算

$\begin{aligned} \log a + \log b &= \log (a \cdot b)\\ \log a - \log b &= \log (\frac {a} {b}) \end{aligned}$

$\begin{aligned} \frac{de^x}{dx}=e^x\\ \frac{d\log_{\alpha}{|x|}}{dx}=\frac{1}{x\ln\alpha} \end{aligned}$

方差

variance, 表示一个特征偏离均值的程度

$var(X) = \frac{1}{N-1} \sum_{i=1}^{N} (X_i-\overline{X})^2$

协方差

表示两个特征正相关/负相关的程度

$cov(X,Y) = \frac{1}{N-1} \sum_{i=1}^{N} (X_i-\overline{X})(Y_i-\overline{Y})$

协方差矩阵

$C_{n \times n}, C_{i,j} = cov(Dim_i, Dim_j)$

逆矩阵

如果 n 阶方形矩阵 $A$ 存在 $B$ 且 $A \cdot B = B \cdot A =I_n$ , 那么称 $A$ 是可逆的, $B$ 是 $A$ 的逆矩阵, 计作 $A^{-1}$ . 若 $A$ 的逆矩阵存在, 称 $A$ 为非奇异方阵,

$\begin{aligned} rank(A)=rank(B)=n \\ (A^{-1})^{-1}=A \\ (\lambda A)^{-1} = \frac{1}{\lambda} \times A^{-1} \\ (AB)^{-1} = B^{-1} A^{-1} \\ (A^T)^{-1}=(A^{-1})^T \\ det(A^{-1}) = \frac{1}{det(A)} \end{aligned}$

其中 $det$ 为行列式

正定矩阵

一个 n×n 的实对称矩阵 $M$ 是正定的，当且仅当对于所有的非零实系数向量 $z$，都有 $z^T M z > 0$ .

一个 n×n 的复数对称矩阵 $M$ 是正定的，当且仅当对于所有的非零实系数向量 $z$，都有 $z^* M z > 0$ . 其中 $*$ 表示共轭转置

引用

《统计学习方法》李航

Spark MLIB GBDT

从梯度下降到拟牛顿法: 详解训练神经网络的五大学习算法

Kaggle入门

机器学习面试的那些事儿

浅谈L0,L1,L2范数及其应用

机器学习中的范数规则化之 (一) L0、L1与L2范数

ROC和AUC介绍以及如何计算AUC

机器学习方法：回归（二）：稀疏与正则约束ridge regression，Lasso

理解L-BFGS算法

An overview of gradient descent optimization algorithms

TODO