HTML

机器学习笔记

评估指标

准确率

查准率

How many relevant items are selected?

accuracy=TP(TP+FN)

召回率

查全率

How many selected items are relevant?

recall=TP(TP+FN)

F1 score

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

ROC/AUC

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

Area Under Curve, 表示 ROC 曲线下的面积, 越大越好. AUC 是一个概率值, 当你随机挑选一个正样本以及一个负样本, 当前的分类算法根据计算得到的Score值将这个正样本排在负样本前面的概率就是AUC值. (Fawcett, 2006)

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

ROC

距离范数

损失函数中, 正则项一般是参数的 Lp 距离.

L1最优化问题的解是稀疏性的, 其倾向于选择很少的一些非常大的值和很多的insignificant的小值. 而L2最优化则更多的非常少的特别大的值, 却又很多相对小的值, 但其仍然对最优化解有significant的贡献. 但从最优化问题解的平滑性来看, L1范数的最优解相对于L2范数要少, 但其往往是最优解, 而L2的解很多, 但更多的倾向于某种局部最优解.

L0范数本身是特征选择的最直接最理想的方案, 但如前所述, 其不可分, 且很难优化, 因此实际应用中我们使用L1来得到L0的最优凸近似. L2相对于L1具有更为平滑的特性, 在模型预测中, 往往比L1具有更好的预测特性. 当遇到两个对预测有帮助的特征时, L1倾向于选择一个更大的特征. 而L2更倾向把两者结合起来.

lp-balls

L0-范数

向量中非零元素的个数

在 Sparse Coding 中, 通过最小化 L0 寻找最少最优的稀疏特征. 但难以优化, 一般转化成 L1 L2

L1-范数

曼哈顿距离

如计算机视觉中对比两张图片的不同像素点之和

L2-范数

欧几里得距离

Lp-范数

无限范数距离

切比雪夫距离

d=\underset {p \to \infty}{\lim}\sum_{i=1}^{n}\bigg(|x_i-y_i|^{p}\bigg)^{\frac {1}{p}} = \max(|x_1-y_1|,…,|x_n-y_n|)

损失函数

0 - 1 损失函数

gold standard

对数损失函数

对 LR 而言, 把它的条件概率分布方程

带入上式, 即可得到 LR 的对数损失函数

平方损失函数

Square Loss

其中 $$Y-f(X)$$ 表示残差, 整个式子表示残差平方和, Residual Sum of Squares

指数损失函数

Exponential Loss

如 Adaboost, 它是前向分步加法算法的特例, 是一个加和模型, 损失函数就是指数函数. 经过m此迭代之后, 可以得到

\underset {\alpha, G}{\arg\ \min}=\sum_{i=1}^{N}e^{[-y_i(f_{m-1}(x_i)+\alpha G(x_i))]}

Adaboost 每次迭代的目标是最小化指数损失函数

合页损失

Hinge Loss, 如 SVM

Huber 损失

常用于回归树。与比平方损失相比，它对 outlier 更加不敏感

对于回归问题

其中 $$|a|=y-f(x)$$

对分类问题

下图是 huber loss（绿色）与平方损失（蓝色）的对比，来自 wiki

huber loss

正则化

Regulization or Penalization

\underset{w \in \Theta}{min} \frac{1}{N}\sum_{i=l}^{N}L(y_i,f(x_i,w))+\lambda J(w)

其中第一项是经验风险, 第二项是正则化项。常见的正则项，通过 $$L_0,L_1,L_2$$ 范数衡量参数 $$w$$

\begin{align} J_0(w) &= \big|\{i:w_i \ne 0\}\big| \\ J_1(w) &= \sum_i |w_i|\\ J_2(w) &= \frac{1}{2} ||w||^2 \end{align}

其中 $$L_2$$ 正则项最常用，因为它是凸函数，可以用梯度下降法求解。

而 $$L_1$$ 正则项有特征选择功能，能够得到更加稀疏、更多 0 的解。可以用简单截断法，梯度截断法（TG, Truncated Gradient），ADMM 方法求解。

以 $$w\in \mathbb R^2$$ 为例，椭圆形是 loss 的损失等高线，灰色区域是约束区域，等高线与约束区域相交的地方，就是最优解。可以看出，L1 较 L2 有更大的概率在角处相交，得到稀疏解。

l1vsl2

泛化能力

泛化误差

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

Bias Variance Tradeoff

wiki

bias_variance

泛化误差上界

性质: 它是样本容量的函数, 当样本增加时, 趋于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$$ 的期望风险和经验风险是

经验风险最小化函数是

f_N=\underset {f \in F}{\arg\ \min} \ \hat R(f)

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

泛化误差上界

其中

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

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

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

熵

给定一个离散有限随机变量 $$X$$ 的分布为 $$P(X = x_i)=p_i$$ , $$i=1,2,…,n$$, 那么 $$X$$ 的熵定义为

熵越大, 随机变量的不确定性越大, 从定义可以验证

条件熵

条件熵 $$H(Y|X)$$ 描述了在已知第二个随机变量 $$X$$ 的值的前提下, 随机变量 $$Y$$ 的信息熵

\begin{align} H(Y|X) &=\sum_{x\in \mathcal X}p(x)H(Y|X=x) \\ &=-\sum_{x\in \mathcal X} p(x) \sum_{y\in\mathcal Y} p(y|x) \log p(y|x) \\ &=\sum_{x\in\mathcal X,y\in\mathcal Y} p(x,y) \log \frac{p(x)}{p(x,y)} \end{align}

当且仅当 $$Y$$ 的值完全有 $$X$$ 确定时, $$H(Y|X)=0$$. 相反, 当且仅当 $$Y$$ 和 $$X$$ 为独立随机变量时, $$H(Y|X)=H(Y)$$.

由数据估算 (如极大似然估计) 得到时, 称为经验条件熵.

信息增益

信息增益表示得知特征 $$X$$ 的信息而使得类 $$Y$$ 的信息的不确定性减少的程度.

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

g(D,A)=H(D)−H(D∣A)

信息增益可以用于决策树的特征选取: 对训练数据集 D, 计算每个特征的信息增益, 选择信息增益大的特征.

信息增益比

以信息增益划分, 存在偏向于选择值较多的问题. 用信息增益比可以进行校正, 归一化.

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

gR(D,A)=g(D,A)/HA(D)

其中, $$n​$$ 是特征 $$A​$$ 取值的个数.

H_A(D)=−\sum_{i=1}^n \frac{|Di|}{|D|} \log_{2}{\frac{|Di|}{|D|}}

其中, $$D_i$$ 是根据特征 $$A$$ 的值将 $$D$$ 划分为 $$n$$ 个子集.

基尼指数

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

Gini(p)=\sum_k p_k(1−p_k)=1− \sum_k p^2_k

对于二分类问题, 若样本点属于第 1 个类的概率是 p, 则概率分布的基尼指数为:

Gini(p)=2p(1−p)

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

Gini(D)=1−∑(|C_k||D|)^2

这里, $$C_k$$ 是 $$D$$ 中属于第 $$k$$ 类的样本子集, $$k$$ 是类的个数.

如果样本集合 $$D$$ 根据特征 $$A$$ 是否取到某一可能值 $$a$$ 被分割成 $$D_1$$ 和 $$D_2$$ 两部分, 则在特征 $$A$$ 的条件下, 集合 $$D$$ 的基尼指数定义为:

Gini(D,A)=∣D1∣∣D∣Gini(D1)+∣D1∣∣D∣Gini(D2)

基尼指数 $$Gini(D)$$ 表示集合 $$D$$ 的不确定性, 基尼指数越大, 样本集合的不确定性也就越大, 这一点与熵相似

IV & WOE

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

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

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

WOE_i = \ln(\frac{py_i}{pn_i}) = ...\\ IV_i = (py_i - pn_i) * WOE_i

这个变量的 $$IV$$ 是

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

IV 越大, 特征越重要

回归问题

给定一个训练集

T=(x1,y1),(x2,y2),...,(xn,yn)

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

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

分类问题

给定一个训练集

T=(x1,y1),(x2,y2),...,(xn,yn)

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

P(Y(1),Y(2),...,Y(n))∣X(1),X(2),...,X(n))P(Y^{(1)},Y^{(2)},...,Y^{(n)}) | X^{(1)},X^{(2)},...,X^{(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

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

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

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

最小岭回归

加入L2惩罚项

LASSO

加入L1惩罚项, 把参数约束在 $$L1\ ball$$ 中

更多的系数为0, 可以用来做特征选择, 具有可解释性

或优化目标形式

\underset{w}{\min} \frac{1}{2}||y-Xw||^2 \\ \text{s.t.} ||w||^1 < \theta

有解析解

Elastic Net

L1+L2

LR

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

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

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

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

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

输入: $$x$$

输出: $$0\le y \le1$$

定义事件发生几率 (Odds)

对数几率, 或 logit 函数

对逻辑斯谛回归而言

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

参数估计

为简化推导, 设

P(Y=1∣x)=π(x),P(Y=0∣x)=1−π(x)

损失函数 (似然函数) 为

对数损失函数为

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

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

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

\frac{\partial L(w)}{\partial w} = X^T (y-\pi) \\ \frac{\partial^2 L(w)}{\partial w \partial w^T} = - X^T W X \\

其中

W_{ij} = \pi(x_i; w)(1 - \pi(x_j; w))\\ \pi_i = \pi(x_i; w)

ref

用法

输入特征相互独立 (descrete)

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

最大熵模型

熵满足下列不等式

0≤H(P)≤log∣X∣

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

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

The equivalence of logistic regression and maximum entropy models

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

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

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

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

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

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

E_{\widetilde{P}}(f)=\sum\limits_{x,y} \widetilde{P}(x,y)f(x,y) E_{P}(f)=\sum\limits_{x} \widetilde{P}(x)P(y|x)f(x,y)

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

E_{\widetilde{P}}(f)=E_{P}(f)

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

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

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

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

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

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

熵最大模型的学习

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

\begin{align} \\ \underset{P\in C}{\min} \hspace{1em} & -H(P)=\sum_{x,y} \tilde P(x)P(y|x) \log P(y|x)\\ s.t. \hspace{1em} & E_p(f_i) - E_{\tilde P}(f_i) = 0, i = 1,2,...,n \\ \hspace{1em} & \sum_y P(y|x)=1 \\ \end{align} \\

Softmax

对多分类问题, 假设离散型随机变量 $$Y$$ 的取值集合是 $${1,2,…,K}$$ , 那么逻辑斯谛模型推广到 softmax 有:

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

贝叶斯分类器

贝叶斯决策论

假设样本分类空间 $$\mathcal{Y}={c_1,c_2,…,c_n}$$, 样本 $$x$$ 上的条件风险定义

其中 $$\lambda_{ij}$$ 是误分 $$j$$ 为 $$i$$ 类产生的损失

寻找一个判定准则 $$h:X \leftarrow Y$$ 以最小化风险

贝叶斯准则: 为最小化总体风险, 只需在每个样本上选择那个能使条件风险 $$R(c|x)$$ 最小化的类别标记, 即

h^*(x)= \underset{c \in \mathcal{Y}}{\arg \min} R(c|x)

其中, $$1 - R(h^*)$$ 反应了分类器所能达到的最优性能, 即通过机器学习所能产生的模型精度的最上限.

此时 $$h^{*}$$ 称为贝叶斯最优分类器

与之对应的总体风险称为 $$R(h^*)$$ 称为贝叶斯风险.

当最小化分类错误错误分类率时, $$\lambda_{i,j}$$ 定义为

λi,j=I(i==j)\lambda_{i,j}=I(i==j) λ​i,j​​=I(i==j)

此时条件风险

R(c∣x)=1−P(c∣x)R(c|x)=1-P(c|x) R(c∣x)=1−P(c∣x)

于是最小化分类错误率的贝叶斯最优分类器为

h^* (x)= \underset{x \in mathcal{Y}}{\arg \max} P(c|x)

不难看出, 要使用贝叶斯判定准则来最小化决策风险, 首先要获得后验概率 $$P(c|x)$$, 但是在现实任务中很难. 问题可以转化为贝叶斯公式

P(c∣x)=P(x,c)P(x)=P(c)P(x∣c)P(x)P(c|x)=\frac{P(x,c)}{P(x)}=\frac{P(c)P(x|c)}{P(x)} P(c∣x)=​P(x)​​P(x,c)​​=​P(x)​​P(c)P(x∣c)​​

其中, $$P©$$ 是类先验概率, $$P(x|c)$$ 是样本 x 相对于标记 c 的累条件概率, 或者成为似然, $$P(x)$$ 是用于归一化的证据因子. 对给定样本 x, 证据因子和累标记无关. 因此累估计 $$P(c|x)$$ 的问题就转化为如何基于训练数据集 $$T$$ 来估计先验 $$P©$$ 和似然 $$P(x|c)$$

其中 $$P(x|c)$$ 的 Frequentist 估计方法, 假定参数是客观存在的固定值, 通过优化似然函数等准则来确定参数值. Bayesian 学派认为, 参数是为观察到的随机变量, 它本身也可有分布, 因此可以假定参数服从一个先验分布, 然后基于观测到的数据来计算参数的后验分布.

Frequentist 的 MLE 方法: 令 $$D_c$$ 表示训练集中第 $$c$$ 类样本组成的集合, 假设这些样本是独立同分布的, 则参数 $$\theta_c$$ 对于数据集 $$D_c$$ 的似然是

P(Dc∣θc)=∏x∈DcP(x∣θc)P(D_c|\theta_c) = \prod{x \in D_c}{P(x|\theta_c)} P(D​c​​∣θ​c​​)=∏x∈D​c​​P(x∣θ​c​​)

通常用对数似然, 避免上式练乘操作的下溢

LL(θc)=logP(Dc∣θc)=∑x∈DclogP(x∣θc)LL(\theta_c)=\log P(D_c|\theta_c)=\sum_{x\in D_c} \log P(x|\theta_c) LL(θ​c​​)=logP(D​c​​∣θ​c​​)=​x∈D​c​​​∑​​logP(x∣θ​c​​)

朴素贝叶斯分类器

贝叶斯公式估计后验概率 $$P(c|x)$$ 的困难在于 $$P(x|c)$$ 是所有属性上的联合概率, 难以从有限的样本直接估计而得. 为解决这个问题, 朴素贝叶斯分类器采用了 “属性条件独立性假设”: 对已知类别, 假设所有属性相互独立. 那么有

P(c∣x)=P(c)P(x∣c)P(x)=P(c)P(x)∏i=1dP(xi∣c)P(c|x)=\frac{P(c)P(x|c)}{P(x)} = \frac{P(c)}{P(x)} \prod_{i=1}^{d} P(x_i|c) P(c∣x)=​P(x)​​P(c)P(x∣c)​​=​P(x)​​P(c)​​​i=1​∏​d​​P(x​i​​∣c)

其中 $$d$$ 为属性的数目, $$x_i$$ 为 $$x$$ 在第 $$i$$ 个属性上的取值

对所有类别 $$P(x)$$ 相同, 因此贝叶斯判定准则有

h_{nb}(x) = \underset{c\in \mathcal{Y}}{\arg \max} P(c) \prod_{i=1}^{d} P(x_i|c)

这就是朴素贝叶斯分类器的表达式, 其中

P(c)=\frac{|D_c|}{|D|} \\ P(x_i|c)=\frac{|D_{c,x_i}|}{|D_c|}

半朴素贝叶斯分类器

One-Depedent Estimator, ODE, 独依赖估计, 假设每个属性在类别之外最多仅依赖一个其他属性

P(c∣x)∝P(c)∏i=1dP(xi∣c,pai)P(c|x) \propto P(c) \prod_{i=1}^{d} P(x_i|c,pa_i) P(c∣x)∝P(c)​i=1​∏​d​​P(x​i​​∣c,pa​i​​)

TODO

贝叶斯网

也叫信念网, belief network, 借助无环图, Directed Acyclic Graph, DAG 来刻画属性之间的依赖关系, 并使用条件概率表 CPT 来描述属性的联合概率分布

TODO

EM 算法

在训练集中, 有时会有未观测到的变量, 即隐变量. 令 $$X$$ 表示已观测变量集合, $$Z$$ 表示隐变量集, $$\Theta$$ 表示模型参数. 若想对 $$\Theta$$ 做极大似然估计, 则应最大化对数似然函数

LL(Θ∣X,Z)=lnP(X,Z∣Θ)LL(\Theta|X,Z)=\ln {P(X,Z|\Theta)} LL(Θ∣X,Z)=lnP(X,Z∣Θ)

由于 $$Z$$ 是隐变量, 无法直接求解. 我们可以用梯度下降方法估计隐变量, 但是求和项数会随着隐变量的数目指数增加, 给梯度计算带来麻烦. 或者可用 EM 方法 (非梯度优化方法), 通过对 $$Z$$ 计算期望, 来最大化已观测数据的对数边际似然 marginal likelyhood

LL(Θ∣X)=ln(P(X∣Θ))=ln∑ZP(X,Z∣Θ)LL(\Theta|X)=ln(P(X|\Theta))=ln \sum_{Z} P(X,Z|\Theta) LL(Θ∣X)=ln(P(X∣Θ))=ln​Z​∑​​P(X,Z∣Θ)

Expectation Maximization 算法, 是常用的估计参数隐变量的方法, 其基本想法是: 若参数 $$\Theta$$ 已知, 则可根据训练数据推断初最优隐变量 $$Z$$ 的值 (E步); 反之, 若 $$Z$$ 的值已知, 则可方便地对参数 $$\Theta$$ 做极大似然估计 (M 步). 交替 E 步, M 步直到收敛到局部最优解.

Expetation 步: 若当前参数 $$\Theta^t$$ 推断隐变量分布 $$P(Z|X,\Theta^t)$$ 并计算对数似然 $$LL(\Theta|X,Z)$$ 关于 Z 的期望,

Q(Θ∣Θt)=EZ∣X,ΘtLL(Θ∣X,Z)Q(\Theta|\Theta^t)=\mathbb{E}_{Z|X,\Theta^t} LL(\Theta|X,Z) Q(Θ∣Θ​t​​)=E​Z∣X,Θ​t​​​​LL(Θ∣X,Z)

Maximization 步: 寻找参数最大化的期望似然

Θt+1=argmaxQ(Θ∣Θt)\Theta^{t+1}=\arg \max Q(\Theta|\Theta^t) Θ​t+1​​=argmaxQ(Θ∣Θ​t​​)

k-NN

1968 Cover & Hart

一种高效实现: KD 树

决策树

求所有可能的决策树是 NP 完全问题, 常用启发式方法, 近似求解, 得到次优解, 常用学习算法: ID3 / C4.5 / CART

特征选择的准则, 用信息增益、信息增益比来衡量: 如果用一个特征进行分类的结果与随机分类的结果没有很大差异, 则认为这个特征是没有分类能力的.

一般算法: 递归地选择最优特征, 并根据该特征对训练数据进行分割.

剪枝: 以避免过拟合, 考虑全局最优.

优点: wiki

• 易于理解和解释
• 只需很少的数据准备 其他技术往往需要数据归一化
• 即可以处理数值型数据也可以处理类别型数据
• 可以通过测试集来验证模型的性能
• 强健控制. 对噪声处理有好的强健性
• 可以很好的处理大规模数据

ID3

极大似然进行概率模型的选择, 用 信息增益 来选择特征

输入: 训练集 D, 特征集 A, 阈值 ε

输出: 决策树 T

1. 若 $$D$$ 同属一类 $$C_k$$, 则 $$T$$ 为单节点树, 将 $$C_k$$ 作为该节点的类标记, 返回 $$T$$
2. 若 $$A = {}$$ , 则 $$T$$ 为单节点树, 将 $$D$$ 中实例数最大的类 $$C_k$$ 作为该节点的类标记, 返回 $$T$$
3. 否则, 计算 $$A$$ 中特征对 $$D$$ 的信息增益, 选择信息增益最大的特征 $$A_g$$
4. 如果 $$A_g$$ 的信息增益小于阈值 $$ε$$, 则置 $$T$$ 为单节点树, 将 $$D$$ 中实例数最大的类 $$C_k$$ 作为该节点的类标记, 返回 $$T$$
5. 否则, 对 $$A_g$$ 的每一可能值 $$a_i$$, 以 $$A_g=a_i$$ (选均值、随机值或者其他) 将 $$D$$ 分割为若干非空子集 $$D_i$$, 将 $$D_i$$ 中实例最大的类作为标记, 构建子节点, 构成树 $$T$$, 返回 $$T$$
6. 对第 $$i$$ 个子节点, 以 $$D_i$$ 为训练集, $$A-{A_g}$$ 为特征集, 递归地调用步骤 1 至 5, 得到子树 $$T_i$$, 返回 $$T_i$$

C4.5

改进 ID3, 用 信息增益比 来选择特征

剪枝

一种简单的方法: 通过极小化损失函数来实现, 损失函数定义

Cα(T)=ΣtNtHt(T)+α∣T∣C_\alpha(T)=\Sigma_tN_tH_t(T)+\alpha|T| C​α​​(T)=Σ​t​​N​t​​H​t​​(T)+α∣T∣

其中 $$T$$ 是节点个数, t 是叶节点, 有 Nt 个样本点, k 类样本点有 $$N_{tk}$$ 个, $$k=1,2,…,K$$, $$\alpha\ge0$$ 为参数, $$H_t(T)$$ 是叶节点 t 的经验熵, 定义

Ht(T)=−ΣtNtHt(T)H_t(T)=-\Sigma_tN_tH_t(T) H​t​​(T)=−Σ​t​​N​t​​H​t​​(T)

模型对训练数据的误差为

Cα(T)=C(T)+α∣T∣C_\alpha(T)=C(T)+\alpha|T| C​α​​(T)=C(T)+α∣T∣

其中 $$|T|$$ 表示模型复杂度, $$\alpha$$ 越小, 模型越复杂

CART

分类与回归树, Breiman 1984 提出, 算法由特征选择、树的生成、剪枝组成, 分类、回归任务都可以用.

最小二乘法生成回归树

输入：训练集 $$T={(x_1,y_1),…,(x_N,y_N)}, x_i \in X, y_i \in Y $$, 其中 $$Y$$ 是连续变量

输出: 回归树 $$f(x)$$

假设将输入空间划分成 $$M$$ 个单元 $$R_1,…,R_M$$, 并且在每个单元 $$R_m$$ 上有固定输出值 $$c_m$$, 于是回归树模型可表示为

f(x)=∑m=1McmI(x⊆Rm)f(x)=\sum_{m=1}^{M} c_m I(x \subseteq R_m) f(x)=​m=1​∑​M​​c​m​​I(x⊆R​m​​)

当输入空间的划分确定时, 可用平方误差表示回归树的预测误差, 用平方误差最小的准则求借每个单元上的最优输出值

c^m=ave(yi∣xi⊆Rm)\hat c_m = ave(y_i|x_i \subseteq R_m) ​c​^​​​m​​=ave(y​i​​∣x​i​​⊆R​m​​)

如何对输入空间划分? 用启发式的方法, 选择第 j 个变量 $$x^{(j)}$$ 和它的取值 $$s$$, 作为切分变量和切分点, 并定义两个区域

R_1(j,s)=\{x|x^{(j)} \leq s\}\\ R_2(j,s)=\{x|x^{(j)} \gt s\}

然后寻找最优切分变量 $$j$$ 和最优切分点 $$s$$, 即求解

\underset{j,s}{\min}\bigg[\underset{c_1}{\min} \sum_{x_i\in R_1(j,s)} (y_i - c_1)^2 + \underset{c_2}{\min}\sum_{x_i\in R_2(j,s)} (y_i-c_2)^2\bigg]

对固定输入变量 $$j$$ 可以找到最优切分点 $$s$$

\hat c_1 = ave(y_i|x_i \in R_1(j,s))\\ \hat c_2 = ave(y_i|x_i \in R_2(j,s))

遍历所有输入变量,找到最优的切分变量 $$j$$, 构成一个对 $$(j,s)$$, 将输入空间划分为两个区域

接着,对每个区域重复上述划分过程, 直到满足停止条件, 得到输入空间的划分空间 $$R_1,R_2,…,R_M$$, 和一颗回归树

f(x)=∑m−1Mc^mI(x∈Rm)f(x)=\sum_{m-1}^M \hat c_m I(x\in R_m) f(x)=​m−1​∑​M​​​c​^​​​m​​I(x∈R​m​​)

随机森林

是决策树的组合, 适用于分类和回归. 较决策树, 它更容易避免过拟合, 不需要对参数进行正则化预处理, 冗余、相关的参数不会影响结果, 输入特征可以是离散和连续的.

在训练过程中引入随机性, 如特征的随机选择、训练集的随机抽样, 并行训练多颗树. 多个预测的结合, 有助于降低预测在某棵树上的相关性, 增加在测试集上的性能.

优点:

• 对于很多数据集表现良好, 精确度比较高
• 不容易过拟合
• 可以得到变量的重要性排序
• 既能处理离散型数据, 也能处理连续型数据
• 不需要进行归一化处理
• 能够很好的处理缺失数据
• 容易并行化等等

随机森林 vs GDBT

Gradient-Boosted Trees 又名 MART(Multiple Additive Regression Tree), GBRT(Gradient Boost Regression Tree), Tree Net, Treelink, 由 Friedman 发明.

GBT 迭代地训练一组决策树, 每棵树的训练残差结果, 作为下一个带训练的树的输入标签.

二者的区别有:

• GBTs 每次训练一颗树, 而 RF 是并行训练多棵树, 前者时间较长
• 增加 GBTs 的 numTrees, 会增加过拟合的可能;增加 RF 的 numTree, 会减少过拟合的可能性
• RF 较容易调参, 因为 numTree 增加会使性能单调提高, 而 GBTs 的 numTree 增加有可能会使性能降低

总体而言, 二者的选择, 取决于你数据集的特性

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. 初始化训练数据的权值分布

D1(w11,...,w1i,...,w1N),w1i=1N,i=1,2,...,ND_1(w_{11}, ..., w_{1i}, ..., w_{1N}), w_{1i}=\frac{1}{N},i=1,2,...,N D​1​​(w​11​​,...,w​1i​​,...,w​1N​​),w​1i​​=​N​​1​​,i=1,2,...,N

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

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

Gm(x):X→−1,1G_m(x):X \to {-1,1} G​m​​(x):X→−1,1

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

em=P(Gm(xi))≠yi)=∑i=1NwmiI(Gm(xi)≠yi)e_m=P(G_m(x_i)) \neq y_i) = \sum_{i=1}^{N}w_{mi}I(G_m(x_i)\neq y_i) e​m​​=P(G​m​​(x​i​​))≠y​i​​)=​i=1​∑​N​​w​mi​​I(G​m​​(x​i​​)≠y​i​​)

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

αm=12log1−emem\alpha_m=\frac{1}{2}\log{\frac{1-e_m}{e_m}} α​m​​=​2​​1​​log​e​m​​​​1−e​m​​​​

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

Dm+i=(wm+1,1...,wm+1,i,...,wm+1,N)D_{m+i}=(w_{m+1,1} ..., w_{m+1,i},..., w_{m+1,N}) D​m+i​​=(w​m+1,1​​...,w​m+1,i​​,...,w​m+1,N​​)

wm+1,i=wmiZmexp(−αmyiGm(xi))w_{m+1,i}=\frac{w_{mi}}{Z_m} \exp ({-\alpha_m y_i G_m(x_i)}) w​m+1,i​​=​Z​m​​​​w​mi​​​​exp(−α​m​​y​i​​G​m​​(x​i​​))

这里 $$Z_m$$ 是规范化因子

Zm=∑i=1Nwmiexp(−αmyiGm(xi))Z_m=\sum_{i=1}^{N}w_{mi}\exp(-\alpha_my_iG_m(x_i)) Z​m​​=​i=1​∑​N​​w​mi​​exp(−α​m​​y​i​​G​m​​(x​i​​))

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

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

f(x)=∑m=1NαmGm(x)f(x)=\sum_{m=1}^{N} \alpha_m G_m(x) f(x)=​m=1​∑​N​​α​m​​G​m​​(x)

最终得到分类器

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

算法解释

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

加法模型

f(x)=∑m−1Mβmb(x;γm)f(x)=\sum_{m-1}^{M}\beta_mb(x;\gamma_m) f(x)=​m−1​∑​M​​β​m​​b(x;γ​m​​)

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

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

\underset{\beta_m,\gamma_m}{\min}{\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)=\underset{\beta, \gamma}{\arg\ \min} \sum_{i=1}^{N} L(y_i,f_{m-1}(x_i)+\beta b(x_i;\gamma))

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

b) 更新

fm(x)=fm−1+βmb(x;γm)f_m(x)=f_{m-1}+\beta_mb(x;\gamma_m) f​m​​(x)=f​m−1​​+β​m​​b(x;γ​m​​)

1. 得到加法模型

f(x)=fM(x)=∑m=1Mβmb(x;γm)f(x)=f_M(x)=\sum_{m=1}^M \beta_m b(x;\gamma_m) f(x)=f​M​​(x)=​m=1​∑​M​​β​m​​b(x;γ​m​​)

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

Boosting Tree

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

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

fM(x)=∑m=1MT(x;Θm)f_M(x)=\sum_{m=1}^{M}T(x;\Theta_m) f​M​​(x)=​m=1​∑​M​​T(x;Θ​m​​)

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

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

1. 令初试提升树 $$f_0(x)=0$$
2. m=1,2,…,M

fm(x)=fm−1(x)+T(x;Θm)f_m(x)=f_{m-1}(x)+T(x;\Theta_m) f​m​​(x)=f​m−1​​(x)+T(x;Θ​m​​)

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

Θ^m=arg min∑i=1NL(yi,fm−1+T(xi;Θm))\hat \Theta_m = \arg\ \min \sum_{i=1}^{N}L(y_i,f_{m-1}+T(x_i;\Theta_m)) ​Θ​^​​​m​​=arg min​i=1​∑​N​​L(y​i​​,f​m−1​​+T(x​i​​;Θ​m​​))

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

\begin{align} 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{align}

这里

γ=y−fm−1(x)\gamma = y-f_{m-1}(x) γ=y−f​m−1​​(x)

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

回归问题的提升树算法

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

T(x;Θ)=∑j=1jcjI(x∈Rj)T(x;\Theta)=\sum_{j=1}^{j}c_jI(x\in \mathbb{R}_j) T(x;Θ)=​j=1​∑​j​​c​j​​I(x∈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) 计算残差

γmi=yi−fm−1(xi),i=1,2,...,N\gamma_{mi}=y_i-f_{m-1}(x_i),i=1,2,...,N γ​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)$$

1. 得到提升回归树

fM(x)=∑m=1MT(x;Θm)f_M(x)=\sum_{m=1}^{M}T(x;\Theta_m) f​M​​(x)=​m=1​∑​M​​T(x;Θ​m​​)

GBDT

提升树用加法模型和前向分步算法实现学习的优化过程. 当损失函数是平方损失和指数损失时, 每一步优化很简单;对一半损失函数而言, 有时并不容易. 针对这个问题, Freidman 提出了梯度提升 Gradient Boost 算法. 这是利用最速下降法的近似方法, 其关键是利用损失函数的负梯度在当前模型的值

−[∂L(y,f(xi))∂f(xi)]f(x)=fm−1(x)-\bigg[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}\bigg]_{f(x)=f_{m-1}(x)} −[​∂f(x​i​​)​​∂L(y,f(x​i​​))​​]​f(x)=f​m−1​​(x)​​

作为回归问题提升树算法中的残差的近似值, 拟合一个回归树

输入: 训练集 $$T={(x_1,y_1,…,(x_n,y_n)},x_i \in X \subseteq \mathbb{R}^n,y_i \in Y \subseteq \mathbb{R}$$;损失函数 $$L(y,f(x))$$

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

1. 初始化

f_0(x)=\arg \underset{c}{\min} \sum_{i=1}^{N}L(y_i,c)

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

a) 对 $$i=1,2,…,N$$ 计算

γmi=−[∂L(y,f(xi))∂f(xi)]f(x)=fm−1(x)\gamma_{mi}=-\bigg[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}\bigg]_{f(x)=f_{m-1}(x)} γ​mi​​=−[​∂f(x​i​​)​​∂L(y,f(x​i​​))​​]​f(x)=f​m−1​​(x)​​

b) 对 $$\gamma_{mi}$$ 拟合一个回归树, 得到第 $$m$$ 棵树的叶节点区域 $$R_{mj}$$, $$j=1,2,…,J$$

c) 对 $$j=1,2,…,J$$ 计算

c_{mj}=\arg \underset {c}{\min} \sum_{x_i \in \mathbb{R}_{mj}} L(y_i,f_{m-1}(x_i)+c)

d) 更新

fm(x)=fm−1(x)+∑j=1JcmjI(x∈Rmj)f_m(x)=f_{m-1}(x)+\sum_{j=1}^{J}c_{mj}I(x\in \mathbb{R}_{mj}) f​m​​(x)=f​m−1​​(x)+​j=1​∑​J​​c​mj​​I(x∈R​mj​​)

3)得到回归树

f^(x)=fM(x)=∑m=1M∑j=1JcmjI(x∈Rmj)\hat f(x)=f_M(x)=\sum_{m=1}^{M}\sum_{j=1}^{J} c_{mj}I(x\in \mathbb{R}_{mj}) ​f​^​​(x)=f​M​​(x)=​m=1​∑​M​​​j=1​∑​J​​c​mj​​I(x∈R​mj​​)

特征

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 个变量的方程组问题

如最优化问题

\max f(x,y)\\ s.t.\ g(x,y)=c

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

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

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

Hilbert Space

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

∣∣x∣∣=<x,x>||x|| = \sqrt{\big<x,x\big>} ∣∣x∣∣=√​⟨x,x⟩​​​

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

Rank

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

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

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

计算

\begin{align} \log a + \log b &= \log (a \cdot b)\\ \log a - \log b &= \log (\frac {a} {b})\\ \end{align} \frac{de^x}{dx}=e^x\\ \frac{d\log_{\alpha}{|x|}}{dx}=\frac{1}{x\ln\alpha}

方差

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

var(X)=1N−1∑i=1N(Xi−X‾)2var(X) = \frac{1}{N-1} \sum_{i=1}^{N} (X_i-\overline{X})^2 var(X)=​N−1​​1​​​i=1​∑​N​​(X​i​​−​X​​​)​2​​

协方差

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

cov(X)=1N−1∑i=1N(Xi−X‾)(Yi−Y‾)cov(X) = \frac{1}{N-1} \sum_{i=1}^{N} (X_i-\overline{X})(Y_i-\overline{Y}) cov(X)=​N−1​​1​​​i=1​∑​N​​(X​i​​−​X​​​)(Y​i​​−​Y​​​)

协方差矩阵

Cn×n,Ci,j=cov(Dimi,Dimj)C_{n \times n}, C_{i,j} = cov(Dim_i, Dim_j) C​n×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$$ 为非奇异方阵,

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)}

其中 $$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