机器学习笔记
查准率
How many relevant items are selected?
accuracy=TP(TP+FN)
查全率
How many selected items are relevant?
recall=TP(TP+FN)
准确率和召回率的调和平均值
Receiver Operating Characteristic, 考虑二分类问题, 调整阈值, 绘制 TP 和 FP 坐标曲线如下图. 其中左上角是完美的分类结果, 右下角是最差的分类结果, 曲线越接近左上角越好.
Area Under Curve, 表示 ROC 曲线下的面积, 越大越好. AUC 是一个概率值, 当你随机挑选一个正样本以及一个负样本, 当前的分类算法根据计算得到的Score值将这个正样本排在负样本前面的概率就是AUC值. (Fawcett, 2006)
ROC 曲线的一个特性: 当测试集中的正负样本的分布变化的时候, ROC曲线能够保持不变;而 Precision-Recall 曲线会随之变化
损失函数中, 正则项一般是参数的 Lp 距离.
L1最优化问题的解是稀疏性的, 其倾向于选择很少的一些非常大的值和很多的insignificant的小值. 而L2最优化则更多的非常少的特别大的值, 却又很多相对小的值, 但其仍然对最优化解有significant的贡献. 但从最优化问题解的平滑性来看, L1范数的最优解相对于L2范数要少, 但其往往是最优解, 而L2的解很多, 但更多的倾向于某种局部最优解.
L0范数本身是特征选择的最直接最理想的方案, 但如前所述, 其不可分, 且很难优化, 因此实际应用中我们使用L1来得到L0的最优凸近似. L2相对于L1具有更为平滑的特性, 在模型预测中, 往往比L1具有更好的预测特性. 当遇到两个对预测有帮助的特征时, L1倾向于选择一个更大的特征. 而L2更倾向把两者结合起来.
向量中非零元素的个数
在 Sparse Coding 中, 通过最小化 L0 寻找最少最优的稀疏特征. 但难以优化, 一般转化成 L1 L2
曼哈顿距离
如计算机视觉中对比两张图片的不同像素点之和
欧几里得距离
切比雪夫距离
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|)
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
常用于回归树。与比平方损失相比,它对 outlier 更加不敏感
对于回归问题
其中 $$|a|=y-f(x)$$
对分类问题
下图是 huber loss(绿色)与平方损失(蓝色)的对比,来自 wiki
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 有更大的概率在角处相交,得到稀疏解。
用学到的模型 $$\hat f$$ 对未知数据预测的误差, 是所学习到模型的期望风险
性质: 它是样本容量的函数, 当样本增加时, 趋于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详解](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$$
又称最小二乘法, 通过最小化平方和误差得到参数估计
当 $$X$$ 是满秩的, 即 $$rank(X) = dim(x)$$, 行/列互不线性相关, 有解析解
但实际问题中 X 往往不是满秩的, 上式的协方差矩阵 $$X^T X$$ 不可逆, 目标函数最小化导数为零时方程有无穷解,没办法求出最优解, 同时存在 overfitting 问题, 这时需要对参数进行限制
加入L2惩罚项
加入L1惩罚项, 把参数约束在 $$L1\ ball$$ 中
更多的系数为0, 可以用来做特征选择, 具有可解释性
或优化目标形式
\underset{w}{\min} \frac{1}{2}||y-Xw||^2 \\ \text{s.t.} ||w||^1 < \theta
有解析解
L1+L2
源自 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)
输入特征相互独立 (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} \\
对多分类问题, 假设离散型随机变量 $$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(Dc∣θc)=∏x∈DcP(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(Dc∣θc)=x∈Dc∑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∏dP(xi∣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∏dP(xi∣c,pai)
TODO
也叫信念网, belief network, 借助无环图, Directed Acyclic Graph, DAG 来刻画属性之间的依赖关系, 并使用条件概率表 CPT 来描述属性的联合概率分布
TODO
在训练集中, 有时会有未观测到的变量, 即隐变量. 令 $$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∣Θ))=lnZ∑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)=EZ∣X,ΘtLL(Θ∣X,Z)
Maximization 步: 寻找参数最大化的期望似然
Θt+1=argmaxQ(Θ∣Θt)\Theta^{t+1}=\arg \max Q(\Theta|\Theta^t) Θt+1=argmaxQ(Θ∣Θt)
1968 Cover & Hart
一种高效实现: KD 树
求所有可能的决策树是 NP 完全问题, 常用启发式方法, 近似求解, 得到次优解, 常用学习算法: ID3
/ C4.5
/ CART
特征选择的准则, 用信息增益
、信息增益
比来衡量: 如果用一个特征进行分类的结果与随机分类的结果没有很大差异, 则认为这个特征是没有分类能力的.
一般算法: 递归地选择最优特征, 并根据该特征对训练数据进行分割.
剪枝: 以避免过拟合, 考虑全局最优.
优点: wiki
极大似然进行概率模型的选择, 用 信息增益 来选择特征
输入: 训练集 D, 特征集 A, 阈值 ε
输出: 决策树 T
改进 ID3, 用 信息增益比 来选择特征
一种简单的方法: 通过极小化损失函数来实现, 损失函数定义
Cα(T)=ΣtNtHt(T)+α∣T∣C_\alpha(T)=\Sigma_tN_tH_t(T)+\alpha|T| Cα(T)=ΣtNtHt(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) Ht(T)=−ΣtNtHt(T)
模型对训练数据的误差为
Cα(T)=C(T)+α∣T∣C_\alpha(T)=C(T)+\alpha|T| Cα(T)=C(T)+α∣T∣
其中 $$|T|$$ 表示模型复杂度, $$\alpha$$ 越小, 模型越复杂
分类与回归树, 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∑McmI(x⊆Rm)
当输入空间的划分确定时, 可用平方误差表示回归树的预测误差, 用平方误差最小的准则求借每个单元上的最优输出值
c^m=ave(yi∣xi⊆Rm)\hat c_m = ave(y_i|x_i \subseteq R_m) c^m=ave(yi∣xi⊆Rm)
如何对输入空间划分? 用启发式的方法, 选择第 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∑Mc^mI(x∈Rm)
是决策树的组合, 适用于分类和回归. 较决策树, 它更容易避免过拟合, 不需要对参数进行正则化预处理, 冗余、相关的参数不会影响结果, 输入特征可以是离散和连续的.
在训练过程中引入随机性, 如特征的随机选择、训练集的随机抽样, 并行训练多颗树. 多个预测的结合, 有助于降低预测在某棵树上的相关性, 增加在测试集上的性能.
优点:
Gradient-Boosted Trees 又名 MART(Multiple Additive Regression Tree), GBRT(Gradient Boost Regression Tree), Tree Net, Treelink, 由 Friedman 发明.
GBT 迭代地训练一组决策树, 每棵树的训练残差结果, 作为下一个带训练的树的输入标签.
二者的区别有:
总体而言, 二者的选择, 取决于你数据集的特性
在概率近似正确 (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)$$
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 D1(w11,...,w1i,...,w1N),w1i=N1,i=1,2,...,N
a) 使具有权值分布 $$D_m$$ 的训练数据集学习, 得到基本分类器
Gm(x):X→−1,1G_m(x):X \to {-1,1} Gm(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) em=P(Gm(xi))≠yi)=i=1∑NwmiI(Gm(xi)≠yi)
c) 计算 $$G_m(x)$$ 的系数
αm=12log1−emem\alpha_m=\frac{1}{2}\log{\frac{1-e_m}{e_m}} αm=21logem1−em
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}) Dm+i=(wm+1,1...,wm+1,i,...,wm+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)}) wm+1,i=Zmwmiexp(−αmyiGm(xi))
这里 $$Z_m$$ 是规范化因子
Zm=∑i=1Nwmiexp(−αmyiGm(xi))Z_m=\sum_{i=1}^{N}w_{mi}\exp(-\alpha_my_iG_m(x_i)) Zm=i=1∑Nwmiexp(−αmyiGm(xi))
它使 $$D_m$$ 成为一个概率分布
f(x)=∑m=1NαmGm(x)f(x)=\sum_{m=1}^{N} \alpha_m G_m(x) f(x)=m=1∑NαmGm(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βmb(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)$$
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) fm(x)=fm−1+βmb(x;γm)
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)=fM(x)=m=1∑Mβmb(x;γm)
这样, 算法将同时求解从 $$m=1$$ 到 $$M$$ 所有参数 $$\beta_m,\gamma_m$$ 的优化问题简化为逐渐求解各个 $$\beta_m,\gamma_m$$ 的优化问题
提升树, 是以分类树或回归树为基本分类器的提升方法. 它采用加法模型与前向分步算法, 以决策树为基函数的提升方法. 对[分类|回归]问题的决策树是二叉[分类|回归]树.
提升树可以表示为决策树的加法模型
fM(x)=∑m=1MT(x;Θm)f_M(x)=\sum_{m=1}^{M}T(x;\Theta_m) fM(x)=m=1∑MT(x;Θm)
其中 $$T$$ 表示决策树, $$\Theta_m$$ 表示决策树的参数, $$M$$ 表示树的个数
提升树用前向分步算法训练
fm(x)=fm−1(x)+T(x;Θm)f_m(x)=f_{m-1}(x)+T(x;\Theta_m) fm(x)=fm−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 mini=1∑NL(yi,fm−1+T(xi;Θ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−fm−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∑jcjI(x∈Rj)
其中 $$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)$$
a) 计算残差
γmi=yi−fm−1(xi),i=1,2,...,N\gamma_{mi}=y_i-f_{m-1}(x_i),i=1,2,...,N γmi=yi−fm−1(xi),i=1,2,...,N
b) 拟合残差 $$\gamma_{mi}$$ 学习一个回归树, 得到 $$T(x;\Theta_m)$$
c) 更新 $$f_m(x)=f_{m-1}+T(x;\Theta_m)$$
fM(x)=∑m=1MT(x;Θm)f_M(x)=\sum_{m=1}^{M}T(x;\Theta_m) fM(x)=m=1∑MT(x;Θm)
提升树用加法模型和前向分步算法实现学习的优化过程. 当损失函数是平方损失和指数损失时, 每一步优化很简单;对一半损失函数而言, 有时并不容易. 针对这个问题, 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(xi)∂L(y,f(xi))]f(x)=fm−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)$$
f_0(x)=\arg \underset{c}{\min} \sum_{i=1}^{N}L(y_i,c)
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(xi)∂L(y,f(xi))]f(x)=fm−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}) fm(x)=fm−1(x)+j=1∑JcmjI(x∈Rmj)
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)=fM(x)=m=1∑Mj=1∑JcmjI(x∈Rmj)
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
在使用线性模型如 LR, 特征构造十分重要. 构造过程为
借助外部数据集训练模型, 如 WordNet, Reddit评论数据集
基于字母而非单词的NLP特征
衡量文本在视觉上的相似度, 如逐字符的序列比较 (difflib.SequenceMatcher)
标注单词的词性, 找出中心词, 计算基于中心词的各种匹配度和距离
将产品标题/介绍中 TF-IDF 最高的一些 Trigram 拿出来, 计算搜索词中出现在这些 Trigram 中的比例;反过来以搜索词为基底也做一遍. 这相当于是从另一个角度抽取了一些 Latent 标识
一些新颖的距离尺度, 比如 Word Movers Distance
除了 SVD 以外还可以用上 NMF
预处理, 二值化、灰度、卷积、sobel边缘
衡量美观、明暗、相似度的指标
KM 世界杯排名预测第一名, 开发了几个特征, 衡量球队的综合能力
Random Forest 的 Imoprtance Feature (原理TODO) , 根据每个特征对信息增益贡献的大小, 来筛选特征.
表现
避免方法
将多个不同的 base model 组合成一个 Ensemble Model, 可以同时降低模型的 bias 和 variance, 提高分数、降低 overfitting 风险 1. 常见方法有
组装要点:
最优化问题中, 寻找多元函数在其变量受到一个或多个条件约束时的极值的方法
这种方法可以将一个有 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$$ 是拉格朗日乘数
在一个复数向量空间 $$H$$ 上的给定的内积 $$<.,.>$$ 可以按照如下的方式导出一个范数 $$||.||$$
∣∣x∣∣=<x,x>||x|| = \sqrt{\big<x,x\big>} ∣∣x∣∣=√⟨x,x⟩
此空间称为是一个希尔伯特空间,如果其对于这个范数来说是完备的。这里的完备性是指,任何一个柯西列都收敛到此空间中的某个元素,即它们与某个元素的范数差的极限为 0。任何一个希尔伯特空间都是巴拿赫空间,但是反之未必。
一个矩阵 $$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−11i=1∑N(Xi−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−11i=1∑N(Xi−X)(Yi−Y)
协方差矩阵
Cn×n,Ci,j=cov(Dimi,Dimj)C_{n \times n}, C_{i,j} = cov(Dim_i, Dim_j) Cn×n,Ci,j=cov(Dimi,Dimj)
如果 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