Loading...
Navigation
Table of Contents

机器学习总结Data

学习资料索引

经验


回归

  • 线性回归方程 (linear regression)与数学原理 (MLE on least squares)
  • 损失函数 (loss function)
  • 评价指标:MSE,R^2等等
  • 杂项:influential points,共线性 (col-linearity),方差/偏差trade-off等等
  • 正则化 (regularization):L1正则化 (ridge regression),L2正则化(Lasso),两者的区别和联系;弹性网 (Elastic Net)
  • 特征工程 (feature engineering):基本概念:连续特征 (continuous feature),离散特征 (categorical feature),非线性特征 (bucketization);one-hot编码,Hash编码,词向量;特征选择,特征交叉,特征验证

分类 (逻辑回归)

参考资料 逻辑回归和TensorFlow演示 @线性回归和逻辑斯蒂线性回归

Sigmoid函数

为什么LR要用sigmoid函数,除了这个函数表面上可以生成[0,1]之间的概率外,本质上是因为$y$服从Bernouli分布,参见指数族分布与广义线性模型知乎知乎

logit 如果$p$是一个概率值(probability),那么$p/(1-p)$叫做发生比(odds)。概率$p$的logit实际上就是发生比的对数(logarithm):$\text{logit}(p)=\log {\frac {p}{1-p}}$。在LR中,logit即指未经sigmoid变换的原始值,更多参见维基百科

在统计学中,如果想输出概率,也不一定用logit模型(sigmoid函数),也可以用probit模型,即使用Gaussian的CDF作为激活函数,其实两者差不多。参见probit模型与logit模型

对数损失

两个离散随机变量的分布的相对熵(Relative Entropy),又称KL散度(Kullback–Leibler divergence),是$D_{KL}(p||q)=\sum_{x} p(x)\ln \frac{q(x)}{p(i)}$,其可以用于衡量两个概率分布之间的差异。相对熵公式的前半部分是交叉熵(Cross Entropy),即$H(p,q)=-\sum_{x}p(x)\log q(x)$。交叉熵可以用来衡量在给定的真实分布下,使用非真实分布所指定的策略消除系统的不确定性所需要付出的努力的大小。交叉熵损失的二分类版本就是逻辑回归损失。交叉熵损失和逻辑回归损失都是对数损失(logloss)。

逻辑回归损失

对于二分类问题,设真实分布$y\in\{0,1\}$,设$p={\rm Pr}(y=1)=1/(1+e^{-WX})$,则每个样本的对数损失为:

$$L(y,p)=-y\log(p)-(1-y)\log(1-p))$$

注意这里的表达式前必须有负号! 因为$y_k\log p_k$本身是负值。所以交叉熵的值是正实数。交叉熵损失越小,说明模型拟合的越好。
数学来源:对$y_1,\dots,y_N$的似然函数$\prod p(y_i|x_i,\theta)=\prod p^{y_i}\cdot (1-p))^{(1-y_i)}$,对此式取对数便得到上述逻辑回归损失。

交叉熵损失

对于$K$分类问题。设某个样本的真实标签为$y=[ y^1\dots y^K]$(one-hot)。模型预测的分布为$p=[p^1,\dots,p^K]$(softmax函数变换后的),则每个样本交叉熵损失为$L(y,p) = - \sum\limits_{k=1}^{K}y_k\log p_k$,至于整个训练集的交叉熵损失,可以把每个样本的损失求和,也可以求平均(实验中好像求平均比较好)。损失函数带有正则项的时候需要求平均,否则求和求平均差不多。
对数损失/交叉熵损失的由来:

  • 是KL散度的马甲,KL散度用来衡量两个分布的差别
  • 本质是通过MLE来推导出来的
  • 形式比较符合"输出概率"的认知
  • 这里
L2损失比起较为稳定的Softmax损失来,其最优化过程要困难很多.直观而言,它需要网络具备一个特别的性质,即对于每个输入都要输出一个确切的正确值。而在Softmax中就不是这样,每个评分的准确值并不是那么重要:只有当它们量级适当的时候,才有意义。还有,L2损失鲁棒性不好,因为异常值可以导致很大的梯度。
所以在面对一个回归问题时,先考虑将输出变成二值化是否真的不够用。例如,如果对一个产品的星级进行预测,使用5个独立的分类器来对1-5星进行打分的效果一般比使用一个回归损失要好很多。分类还有一个额外优点,就是能给出关于回归的输出的分布,而不是一个简单的毫无把握的输出值。如果确信分类不适用,那么使用L2损失吧,但是一定要谨慎:L2非常脆弱,在网络中使用随机失活(尤其是在L2损失层的上一层)不是好主意。
  • 评价指标:准确率 (accuracy),精确率 (precision),召回率 (recall),F1-score,ROC和AUC等等

线性判别分析 | 不重要

  • 先验概率与后验概率
  • 判别函数
  • 与LR的联系

k临近法(kNN)和平衡kd树

以分类问题为例,给定训练集$(x,y)$和距离度量方法,想要求新样本$x_{new}$的$y_{new}$,只需要计算$X_{new}$最近的样本的$y$,然后进行majority voting即可。注意k选的太小会过拟合,反之欠拟合。
由于搜索空间太大,可以先用平衡kd树(注意这里的k是特征的维度,不是kNN里面的k)把训练集按照二叉树来划分开来,具体来说,现根据$x^{(1)}$的中位数为分割线将数据集化为两半,接着在两个子集里,分别按其各自的$x^{(2)}$的中位数再划分。重复进行,直至子区域里面没有样本截止。kd树有点类似于手工定制的决策树。
给定一个kd树,只需在$x_{new}$所在的叶节点找其邻近的$k'$个邻居,如果不够的话,可以去此叶结点的父节点里寻找。


降维

  • k临近学习
  • 主成分分析 (principal component analysis,PCA)

聚类

参考资料:漫谈Clustering - PlusKid

k-means

k-means适用于欧氏度量空间中的数据,目标是把数据聚成$k$类。设$x_1\dots x_n$为$d$维向量,$S_1\dots S_k$为$k$个聚好的类,质心为$\mu_i\dots \mu_k$,其最小化目标为组内平方和,即$J=\sum_{i=1}^k \sum_{x\in S_i} ||x-\mu_i||^2$。

具体流程如下,1)随便选$k$个点为质心;2)遍历所有点,将其划到最近质心所在的那个类中,然后重新计算质心(即类内所有点的均值);3)重复2,即重新划分类,直到$J$小于一定值。

Note:k-means对初值选取敏感,容易局部最优,可以多跑几次看看;$k$的选取很关键,一般可以根据业务知识或者对数据进行预分析(估计下密度啥的);k-means一定会收敛的,因为EM算法一定收敛;k-means还有一些变种,如二分k-means,k-means++。

k-medoids

对于不是欧氏空间的数据,尤其是带有离散特征的数据,我们可以采用L1距离(又称Manhattan距离)来衡量相似性,即$d(a,b)=\sum w^i|a^i-b^i|$(这里是带权版本)。k-medoids和k-mean是非常不一样的一点是,k-medoids质心点必须选在数据中出现的点,这样在更新每个类的质心的时候,需要暴力把每个点和类内其它点进行距离计算,然后找出离大家最近的点作为质心,这个复杂度是$O(n^2)$,而k-means只有$O(n)$。

Note:k-medoids的优势在于其选取数据点为质心,这样来说更不容易受outlier的影响,鲁棒性更好,但缺点是复杂度太高。

高斯混合模型GMM

除了直接将数据聚类外,我们还可以先求出数据反映的总体所服从的分布,然后分布的最高点/期望值就是所需要的类中心了。如果所有数据都是属于一个类的(iid的),这就可以用常见的极大似然来做。对于多类情况,可以用多个高斯分布的叠加作为总体,即$p(x)=\sum \pi_i p(x;\mu_i,\Sigma_i)$。之所以选取高斯分布,因为中心极限定理$\frac{\bar X -\mu}{\sigma/\sqrt{n}}\rightarrow N(0,1)$告诉我们这样比较合理。
对于这种比较复杂的似然函数,可以用EM算法来求解。

Note:GMM的一个优点是其可以返回每个点属于每个类的概率。


深度学习

参考资料:@cs231n,@神经网络与深度学习 - 吴恩达,解析卷及神经网络 @CNN_book_weixs.pdf

  • 随机初始化,反向传播,梯度下降
  • 随机失活DropOut。参考知乎cs231n。Batch Normalization

Batch Normalization

为什么有用

  • 对于每一层(或者是第一层,或者是隐藏层),我们希望不同mini-batch数据的分布是一致的(就像我们希望训练集和测试集分布一致,这里是对于第一层而言)。BN就保证了不同mini-batch分布区别不大。(其实训练之前打乱样本也是在保证mini-batch之间的一致性,不然你前10个batch全拿正样本,后10个batch全拿负样本训练试试?)
  • 即使是对于同一个mini-batch,我们希望不同feature里的数据范围(scale)区别不大。记得在做数据pre-processing时候,我们经常会归一化,但经过DNN几层后,不同神经元(即feature)很可能区别很大,所以也需要一个隐层中的归一化操作,即BN。参见quora。- 防止梯度爆炸或者消失。考虑前向传播$h_{l+1}=bn-relu(X\cdot W + b)$,如果把$W$增大$c$倍,由于BN的存在,$h_{l+1}=bn-relu(X\cdot cW + b)$的值是不变的。反向传播时,观察梯度的公式,会发现$\partial h_{l+1} / \partial h_{l}$其和$W$是没有关系的,$\partial x$TBD
  • 可以起到轻微的正则化作用。因为$\hat x = \frac{x-\mu}{\sigma^2 + \epsilon}$这里引入了噪声

在哪里用 BN应该插在每个$XW+b$层后面,激活层前面,但是最后输出层不加。
也可参考深度学习中BN为什么效果好,BN的梯度推导见Kevin Zakka's Blog这里

Dropout (随机失活)

Dropout是指,在前向传播时以$p$的概率让神经元不参与传播,即只有$1-p$的会被使用(激活),注意在预测时候需要使用全部神经元并进行缩小,即$h_l = h_l * p$。实际使用中更推荐inverted dropout,其只需修改训练部分的代码。dropout一般放在激活层之后

#inverted dropout前向传播
mask = np.random.rand(x.shape) < (1 - p) #1-p left
mask = mask / (1 - p) #放大
out = mask * x

SVM

  • 间隔和支持向量,对偶问题
  • 核函数,核方法 等等
  • 与LR的联系

函数/几何间隔 对于某个样本,函数间隔是$y(w\cdot x+b)$,几何间隔是距离,即$y(w\cdot x+b)/||w||$,其中$||w||=\sqrt{\sum w_i^2}$。
优化目标 记$(x_0,y_0)$是离超平面几何间隔最小的点,所以最大几何间隔问题就是
$$\arg\limits_{w,b} \max \frac{y_0(w\cdot x_0+b)}{||w||},~\text{s.t.}~y_i(w\cdot x_i+b) \ge y_0(w\cdot x_0+b)$$
不失一般性,设最小的函数间隔为1,同时把$||w||$移到分子上,得到原始问题
$$\arg_{w,b} \min \frac{1}{2}||w||^2,~\text{s.t.}~y_i(w\cdot x_i+b) \ge 1$$
为了解决这个原始问题,可以通过引入Lagrange乘子来求对偶问题的解
$$\max_{\alpha} \min_{w,b} L(w,b,\alpha)= \frac{1}{2}||w||^2 -\sum \alpha_iy_i(w\cdot x_i+b)+\sum \alpha_i$$
通过对$w,b$求导,并带回原式,就可以得到关于$\alpha$的对偶问题
$$\max_{\alpha}-\frac{1}{2}\sum\sum\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum\alpha,~\text{s.t.}~\sum\alpha_i y_i=0,\alpha_i\ge 0$$
从这个对偶问题中可以求得$\alpha_1\dots\alpha_N$的最优解(实际上这里面支持向量对应的$\alpha_i>0$,其余样本对应的$\alpha_i=0$),然后便可得到$w,b$。
软间隔


决策树

决策树在数学上一般可以用$T(x;\theta)=\sum c_iI(x\in R_i)$,其中$I$是Indicator,$(R_i,c_i)$代表一个叶子节点和这个节点的label输出,分类问题中一般用majority voting,回归问题里一般用均值或者中位数。

ID3/C4.5

熵/信息增益 熵用来衡量随机变量$X$的不确定度,若$P(X=x_i)=p_i$,则熵$H(X)=-\sum p_i \log p_i$,给定$X$下的$Y$的条件熵为$H(Y|X)=\sum p_iH(Y|X=x_i)$。当熵和条件熵是由数据估计出来的,他们被称为经验熵和经验条件熵。

在用决策树处理多分类问题时,数据集$D$的经验熵$H(D)$是对于label而言的,经验条件熵$H(D|A)$则是选取某个特征$A$后,划分的子数据集对于label的熵。然后根据信息增益($H(D)- H(D|A)$)来选取特征作为划分节点。

ID3和C4.5适用于离散特征。ID3算法就是每次根据信息增益来选取特征来作为划分节点,此离散特征有几种取法就划分成几个子节点(所以注意这里不一定是二叉树),C4.5做的改进是选取信息增益比(归一化的信息增益)来选取特征。更多参见统计学习方法Kack Cui的决策树笔记

CART

CART是分类与回归树,可以处理回归和分类问题,也是生成二叉树。对于回归问题($y$为连续值,此时一般$x$也是连续的,这里就当连续的,书上没说离散的怎么办),对于每个叶子节点的输出不是majority voting,而是属于叶子节点所有label的均值,即$\frac{1}{N}\sum y_i$。下面考虑划分方法,每次划分都遍历一遍连续值特征和每个特征应该选取哪个划分点,最后选取能让划分之后数据集均方误差最小的特征以及划分点。划分成两个子集后,继续对两个子集各自进行划分。

对于多分类问题,CART构造二叉决策树。定义基尼指数$Gini(p)=1-p_0^2-p_1^2-\dots$,其表示数据集的不确定性。每次划分时,选取使得基尼指数变得最小的离散特征和取值,如左子树为学历=本科,右子树为学历!=本科,然后递归对两个子树再划分。

训练集用于树的生成,验证集用于剪枝。

其它

@OneNote:gbdt学习笔记,xgboost库介绍 @Adaboost


集成学习boosting和bagging

集成学习本质都是加法模型(additive model),$f(x)=\sum \alpha_if_i(x)$,即由很多子模型的输出加起来的。一般采用前向分步算法求解,如求得第$m$个子模型$f_m(x)$,然后更新主模型,$f(x)=f_{old}(x)+f_m(x)$。这里不同的损失函数对应着不同的算法。

Adaboost

Adaboost采用的是指数损失函数,$L=\sum \exp(-y_i(f_{old}(x_i)+f_m(x_i)))$,在求第$m$个子模型$f_m(x)$时,可发现优化目标是找使得$\sum \exp(-y_i(f_{old}(x_i))\cdot I(y_i\neq f_m(x_i))$最小的$f_m(x)$,所以adaboost是把这个损失函数拆成两步,一个是给每个样本赋予权重(即$\exp(-y_i(f_{old}(x_i))$再加上归一化),然后对于每个子模型都是最小化误差率(预测错误/总样本个数)。对于$\alpha_m$,也可以通过对损失求导得到。

Adaboost适用于分类问题,原始流程如下:每个样本赋予权重$\{w_i=1/N\}$,然后训练一个以最小化带权的误差率$e_1$为目标的分类模型,再根据$e_1$更新样本权重$\{w_i\}$和模型权重$\alpha_1$,训练第二个模型。

Boosting Tree(提升树)

提升树处理分类问题时,和Adaboost是一样的;处理回归问题时,采用平方(均方)误差作为loss,即$L=\frac{1}{2}\sum (y_i-f_{old}(x_i)-f_m(x_i))^2=\frac{1}{2}(r_i-f_m(x_i))^2$,这里$r_i$正好就是label的残差。所以对于回归问题的提升树算法来说,每次只需拟合之前模型的残差就行,也不用设置什么样本权重和模型权重了。

GBDT

在以上两个例子中,指数loss和平方loss都是比较容易求导的loss,对于其它损失函数,Freidman提出将$f_{old}(x)$的损失函数,在每个样本输出的负梯度(导数),作为$f_m(x)$的目标函数的做法,即将$-\partial L(y_i,f_{old}(x_i))/\partial f_{old}(x_i)\rightarrow y_i$,以平方损失为例,即$y_i-f_{old}(x_i)$作为新的label。

Bagging(bootstrap aggregating)

bagging是对数据集进行有放回地采样,生成多个训练集,然后对于每个训练集都训练一个模型出来。在预测时,对这些模型的输出做平均或投票。Bagging + 决策树 = 随机森林。

bagging在子模型不完全相同的时候,可以减少模型的方差,因为$Var(\frac{\sum X_i}{n})=\frac{Var(X)}{n}$;对于偏差,则一般不能显著减少。和bagging相反,boosting一般可以减小偏差,但可能过拟合。更多参见知乎


贝叶斯方法

贝叶斯定理及应用


概率图模型

  • 图模型基本表示
  • 贝叶斯网络 (bayesian network),马尔科夫随机场 (markov random field)
  • 条件随机场 (conditional random field,CRF)与隐马尔科夫模型(hidden markov,model,HMM)

计算学习理论

参考资料:@OneNote:梯度下降的原理和变种

  • PAC学习,有限假设空间,VC维理论
  • 梯度下降:批量梯队下降 (batch gradient descent),随机梯度下降 (stochastic gradient descent),mini-batch SDG,Adagrad,momentum @Adam那么棒,为什么还对SGD念念不忘

最优化理论


附1:Kaggle

Last updated on Sep 15, 2019.