Kaggle&TianChi分类问题相关纯算法理论剖析


17/12/30-update :很多朋友私密我想要代码,甚至利用金钱诱惑我,好吧,我沦陷了。因为原始代码涉及到公司的特征工程及一些利益trick,所以我构造了一个数据集后复现了部分算法流程,需要看详细代码实现朋友可以移步Ensemble_Github


更多代码内容欢迎follow我的个人Github,如果有任何算法、代码疑问都欢迎通过stw386@sina.com联系我,知无不答。


导读

上一次的文章中,我们讲了,如何快速的利用bagging、boosting、stacking、ensemble的形式实现一个分类算法,当时我们直接看了代码以及核心的理论注意点。如果需要有更加优异的结果表现,对整套算法的设计及相关的理论了解是必不可少的。本文将从数学、工程、领域经验的角度去剖析如何用好bagging、boosting、stacking、ensemble去训练一个相对完善的模型。

再次提醒,本文中的数据公式较多,抽象概念较多,需要一定的高等代数、泛函分析、机器学习基础作为前置条件。如果你只需要知道如何运行或者完成分类识别,请参考Kaggle-TianChi分类问题相关算法快速实现。如果需要更详尽的理论解析或者有哪些地方不明白的同学,建议私下联系我stw386@sina.com。如果你想skip read本文,请直接阅读最后一个小节:调参流程梳理。

那么接下来让我们开始正文,虽然本文写的很冗长,我依旧建议阅读完此文,即便是处于懵懂的状态,对后续模型调整的理解也是有一定益处的,而且我会尽可能的用通俗易懂的语言来讲,很多地方会存在解释不严谨的地方但是更易于理解。

Bias-Variance-Tradeof

在上次的文章中,我们就提到了一个好的模型应该有着非常好的拟合能力,就是说我的偏差要尽可能的小;同时,也要保证方差尽可能的小,这样我们才能在泛化能力上有很不错的表现。

设样本容量为n的训练集为随机变量的集合(X1, X2, …, Xn),那么模型是以这些随机变量为输入的随机变量函数(这边的F虽然上函数,但是也是随机变化的):F(X1, X2, …, Xn)。抽样的随机性带来了模型的随机性。那如何定义一个模型的Bias和Variance呢?这边我们采取的是基模型的加权均值E(F)=E(∑(γ*fi))移动来替代bias、基模型的加权方差Var(F)=Var(∑(γ*fi))替代Variance,更详细的数学定义如下:

这边在Variance推导过程中用到了这个性质:
Cov(X*Y) = E(X*Y) - E(X)*E(Y),同时将方差拆分成协方差的形式。我们可以看到,组合后的模型的Bias和基模型的Bias的权重γ相关,组合后的模型的Var和基模型的权重γ、基模型个数m、基模型相关性ρ相关。
请务必深刻的记得上述bias和var的数学式子,在后续无论是调参数还是模型设计,我们都是围绕着,降低bias和var的角度去做的。

Bagging Bias and Variance

很多同学在没看这篇文章之前就知道,bagging算法和stacking算法是需要基模型保持强基模型(偏差低方差高)的,但是不知道大家有没有想过为什么?阿里15年校招的时候,我有幸回答过一个题目就是这个问题,下面让我们看看为什么是这样的?

对于bagging算法而言,每次的抽样都是以尽可能使得基模型相互独立为前提的,为了维持这样的假设,我们做了三件事:

  • 样本抽样:整体模型F(X1, X2, …, Xn)中各输入随机变量(X1, X2, …, Xn)对样本的抽样
  • 子抽样:整体模型F(X1, X2, …, Xn)中随机抽取若干输入随机变量成为基模型的输入随机变量
  • 弱抽样:整体模型F(X1, X2, …, Xn)中各输入随机变量(X1, X2, …, Xn)下的feature的抽样

同时,由此我们由此也可以得到bias和var公式中的γ=1/m,基模型的权重一定程度是可以看作是相等的,
所以原来的E和Var公式就变成:

组合模型F的bias和基模型fi的bias一致,这就是我们为什么要求基模型fi的bias要低的原因,因为组合模型F的拟合能力E(F)不随着基模型个数的增加而上升。

组合模型F的var与基模型fi的var、基模型fi的个数m、基模型的相关性ρ相关,很明显可以看出,随着基模型的个数上升Var(F)第二项是在下降的,所以基模型的个数上升会降低组合模型的方差,这就是为什么基模型的方差可以高一些。

除此之外,我们还可以看出,如果基模型相关性ρ越低,整体的方差是越小的,所以我们才去做样本抽样,子抽样,弱抽样等等行为。还有,基模型的个数上升一定程度上会降低组合模型F的方差,但是不是无限递减的,公式中它只能降低第二项的方差值,第一项的方差值不随基模型的个数而增减。

从这个角度看,是不是对Bagging算法的理解又深刻了一些?接下来让我们看看Boosting。

Boosting Bias and Variance

依旧的是很多同学在没看这篇文章之前就知道,boosting算法是需要基模型保持弱基模型(偏差高方差低)的,让我们一探究竟。

熟悉boosting算法的同学都知道,boosting算法的基模型的相关性几乎≈1的,后续模型强依赖于前模型,所以我们可以认为ρ=1,得到如上的简化式子。组合模型F的bias是基模型的bias的累加,基模型的准确度都不是很高(因为其在训练集上的准确度不高),随着基模型数的增多,整体模型的期望值增加,更接近真实值。而站在方差的角度,组合模型F的方差是随着基模型的fi个数上升而平方上升的,这就要求我们的基模型的方差不能太高,否则组合模型的F就会增长爆炸。这就是为什么我们在boosting模型设计的时候,需要基模型保持弱模型(偏差高方差低)的原因。

多说一句,大家也看到了,boosting的Var(F)是依赖于基模型的权重γ的,所以在后续的gbdt、xgboost,各位数据科学家选择了类似bagging的采样模式,降低模型的γ,控制方差,所以说,了解原理再去重新或者优化还是很重要的。

Bagging、Boosting、Stacking Bias&Variance总结

纵观刚才说了的这么多,我们在Bagging、Boosting、Stacking的模型设计中所围绕的就是降低bias的同时,降低Variance。而我们所做的sklearn里面的参数调整就可以说用来:

  • a.构建基模型,变化基模型的Bias和Variance
  • b.组合模型构建,控制基模型后,如何把这个基模型很好的组合成一个优秀的ensemble模型。

GBDT 理论剖析

模型过程推导

其实random forest和gbdt、xgboost都是非常好的Bagging、Boosting、Stacking算法的优化升级版本,我个人用的gbdt稍多,所以就以gbdt为例子给大家梳理一遍,从理论,到调参数,到trick分享。

我最讨厌很多博主贴个上面的伪代码就跑了,我念书的时候,老师讲题目也是,我靠,我要是看得懂还需要你贴?所以,我们选择一步一步的来看这个伪代码。

让我们先概览一下整个流程,gbdt有递归设计如下:

如果y(i)代表着第i个基模型,第i+1个基模型其实是基于第i个基模型的结果而追加了一个New function去修正前i个基模型的误差。如果以F代替y,h代替f的话,我们可以得到下面这个递归函数:

第i个基模型是由前i-1个基模型中的h(x)累计得到的,我们最后想要得到的分类器即为:

每一轮迭代中,只要集中精力使得Fi(x)每次loss下降的最快即可:每次构建一个残差负梯度作为更新方向的New function(即hi(x)),就可以解决这个复杂的递归问题,从而得到F(x)的解析式。

接下来,我们再看看更加详细的做法:

  • 初始化部分,在这次梳理之前,我也一直认为是随机构造的,这边看完伪代码我才知道,在初始值设置的时候,考虑了直接使得损失函数极小化的常数值,它是只有一个根节点的树,即是一个c常数值。

  • 构建回归树,这边就稍许复杂,让我们拆开一步一步来看:

首先,先求整体损失函数的反向梯度。先举个mse的例子,如果现在我们考虑的是mse(着重注意,只有mse的情况下以下的梯度才是这样的)的形式,我们要做的就是在每一步的时候让我们的预测值Fi(x)与真实值y的损失函数:1/2*(y-Fi(x))^2最小(前面的1/2是为了方便求导计算加上去的),如果对梯度下降有了解的朋友就知道,此刻要求它的最小就是去求偏导:

按照这个方向去更新Fi(x),可以保证,组合模型F(x)的每次都是按照最优的方向去优化。

MSE的损失函数确实是残差形式,不代表所有的损失函数下更新的方向都满足这样的残差形式。kaggle master 在blog里面提到Although we can minimize this function directly, gradient descent will let us minimize more complicated loss functions that we can’t minimize directly,我们就需要设计出一种更快速能提升泛化能力且不失一般性的解决方案,所以有大神提出了以梯度下降的值直接代替因变量y,也就是我每次预测不去比预测值与真实值y的差异,我们比较的是预测的梯度方向与真实的梯度方向。

再基于已经预估出来的负梯度去计算最优的更新步长,使得预测值与真实值更加靠近,因为每层的负梯度的方向不固定,所以每层i的步长都是变化的。

最后通过缩减率v(这边就是类似logistics里面的∂)控制速率。

综上,假设test集合第i轮预测中,根据训练集训练出来的负梯度拟合模型不妨记为fi(x)、最优步长γi、缩减率v,可得到最终的递归公式为:

损失函数介绍

刚才上面我举了一个mse作为损失函数的例子,其实还有很多其他的,参考如下:

这边说个有意思的东西,就是如果有兴趣的朋友可以把exponential:指数损失函数计算一下,反向梯度为:

则有第i轮损失函数:

这货就是adaboost的第i轮损失函数的非归一化的结果,是不是很有趣,虽然知道了没啥用,但是起码得到了我们在用gbdt的时候,loss=’exponential’即为adaboost的结论啊,哈哈~所以说,我觉得去推推公式,还是很有意思的。

到此为止,gbdt是怎么构造得来的就讲完了,其实这个和bias&variance关系不大,但是为了铺垫后续的GBDT实战剖析,我觉得还是非常有必要梳理一遍的,但就比起Bias-Variance-Tradeof这节的内容,我觉得各位还是着重理解Bias-Variance-Tradeof,这节可以看作是’甜品’缓解下气氛。

GBDT 实战剖析

我们以python下的sklearn.ensemble中的GradientBoosting及RandomForest为例子,实战分析一下,如何能够理性的调好参数而并非玄学的gridsearch。

在Bias-Variance-Tradeof我们提到了参数设置分为两块:a.构建基模型,b.构建组合模型,我们分GradientBoosting参数如下:

构建组合模型:

1) n_estimators:
基模型的个数,对于gbdt来说,因为我们需要通过基模型的个数来提升准确率所以n_estimators一般都会大于random forest的n_estimators的个数,实际上RandomForestClassifier默认为10,GradientBoostingClassifier默认为100也证明了这点。

2)learning_rate:
步长,对于gbdt来说,步长依赖于n_estimators,100=2*50=5*20,就是这个道理。而random forest里面不存在步长这个概念。在gbdt里面,关于步长的优化一般是伴随着基模型的变化而变化的。

3)subsample:
子采样率,还记得我们上面对子采样的描述么?一般来说,降低“子采样率”(subsample),也会造成子模型间的关联度降低,整体模型的方差减小,但是当子采样率低到一定程度时,子模型的偏差增大,将引起整体模型的准确度降低。

4) init:初始化,更多见GBDT 理论剖析中,我们对初始化的描述。

5)loss:
对于分类模型,有对数似然损失函数”deviance”和指数损失函数”exponential”两者输入选择。默认是对数似然损失函数”deviance”。对于回归模型,有均方差”ls”, 绝对损失”lad”, Huber损失”huber”和分位数损失“quantile”。默认是均方差”ls”。
分类模型不说了,刚才在GBDT 理论剖析中讲了,一般用”deviance”比较多;回归模型中,”ls”我们也在GBDT 理论剖析中讲了,异常点多的情况下”huber”,训练集分段预测的话用”quantile”,但是我个人建议异常点或者分段预测还是在数据已处理中完成。

6) alpha:这个参数只有Huber损失”huber”和分位数损失”quantile”下的GradientBoostingRegressor,alpha越小对噪声处理的力度越强,alpha越小分位数的值越小。

构建基模型:

1)max_features:
每次划分最大特征数,有log2,sqrt,None等等,默认的是sqrt,该值越小,我们每次能获得信息越少,造成偏差时变大的,同时方差是变小的,所以当我们模型拟合能力不足的时候,可以考虑提升该值。

2)max_depth:
基模型最大深度,深度越大,模型的拟合能力越强,bias越小。根据Bias-Variance-Tradeof我们对bagging和boosting里面的Var和Bias的描述可知,如果在boost(gbdt)采用了过深的基模型,组合模型的var会很大,在泛化能力会降低,造成训练集效果优秀,测试集差;如果在bagging(random forest)采取了过浅的基模型,组合模型的拟合能力会不足,我们可以考虑增加深度,甚至不控制生长。

3)min_samples_split:
内部节点再划分所需最小样本数,这个值限制了子树继续划分的条件,如果某节点的样本数少于min_samples_split,则不会继续再尝试选择最优特征来进行划分。随着分裂所需的最小样本数的增加,子模型的结构变得越来越简单,极端情况下,方差减小导致整体模型的拟合能力不足。

4)min_weight_fraction_leaf:
叶节点最小权重总值,这个值限制了叶子节点所有样本权重和的最小值,如果小于这个值,则会和其他子叶节点一起被剪枝,会使得模型变得简单,降低了方差,提高了偏差,如果正负样本不一致,需要考虑调整这个值。

5)max_leaf_nodes:
最大叶子节点数,通过限制最大叶子节点数,可以防止过拟合,会使得模型变得简单,降低了方差,提高了偏差。这边需要注意如果设置了max_leaf_nodes,会忽略max_depth参数值

梳理完以上每个参数的对模型拟合的能力及对Vaild集合泛化能力的影响,我们可以根据项目训练中,实际模型的训练集拟合效果,检验集的泛化效果进行优化参数。

调参流程梳理

ok,问题来了,很多同学看了之后说,你说了这么多参数作用,你还是没告诉我改如何调参数?我就喜欢这种很关注结果的同学,以下干货来自个人及个人朋友及我从知乎等网站”剽窃”来的观点,不负任何理论责任。

我第一任老大,现在在阿里做算法专家,他根据24个数据集合上以不同的调参流程去训练相同的测试集得出的效果对比,总结出以下一个流程:

  • 先确定快速训练的n_estimators和learning_rate,之后所有的调参基于这个确定的值
  • 再确定合适的subsample
  • 再调优最大树深度(max_depth)
  • 再考虑是否有必要修改叶节点最小权重总值(min_weight_fraction_leaf),这边是不一定使用的
  • 再调优最大叶节点数(max_leaf_nodes)
  • 再组合优化分裂所需最小样本数(min_samples_split)、叶节点最小样本数(min_samples_leaf)
  • 最后,优化分裂时考虑的最大特征数(max_features)
  • 组合调整n_estimators和learning_rate

但是,我今年在逛知乎的时候偶然看到一个帖子,里面讲的就是调参数的困扰,提到了一个点,就是先确定了max_depth=3后,无论怎么优化min_samples_split和min_samples_leaf对结果都没有任何影响了。当时我想了很久,最后是一位知友解答了这疑惑,其实这样的:

假设原始数据中正负样本比是1:1000,在做max_depth=3的时候,因为样本不均衡,已经可以通过非常简单的少量feature对正负样本进行区分,所以,在之后怎么调节分裂所需要最小样本树和子节点最小样本数都不能够影响到回归树的构造,然而该区分的回归树是没有泛化能力的。

要解决这个问题要么平衡数据,要么就是先确定回归决策树每个叶子结点最小的样本数(min_samples_leaf),再确定分裂所需最小样本数(min_samples_split),才能确定最大深度,这样就能保证不会出现某棵树通过一个feature将数量较少的的正类以较过拟合的简单浅层树拟合出来,而是优先保证了每一次我构造树都尽可能的平衡满足了数据量合理,数据具有样本具有代表性,不会过拟合这样的假设。所以,可以优化为:

  • 先确定快速训练的n_estimators和learning_rate,之后所有的调参基于这个确定的值
  • 再确定合适的subsample
  • 再组合调优最大树深度(max_depth)和叶节点最小样本数(min_samples_leaf)
  • 再调优最大叶节点数(max_leaf_nodes)
  • 再考虑是否有必要修改叶节点最小权重总值(min_weight_fraction_leaf),这边是不一定使用的
  • 再组合优化分裂所需最小样本数(min_samples_split)
  • 最后,优化分裂时考虑的最大特征数(max_features)
  • 组合调整n_estimators和learning_rate

去年Aarshay Jain大神总结的调参数整理也给出了一种调优思路:

  • 优先,调整最大叶节点数和最大树深度
  • 其次,分裂所需最小样本数(min_samples_split)、叶节点最小样本数(min_samples_leaf)及叶节点最小权重总值(min_weight_fraction_leaf)
  • 然后,分裂时考虑的最大特征数(max_features)

容我多嘴一句,我们思考了这么多,其实如果能在最开始做一个正负样本平衡就会避免很多问题,所以,再次强调数据预处理的重要性。

除此在外,很多人会选择在以上模型调优结束后再以10*learning_rate进行”鞍点逃逸”,以0.1*learning_rate进行”极限探索”。至于random forest及xgboost的更多调参数的细节与gbdt类似,我就不赘述了,有问题可以问我。

终于结束了,这篇文章真的是又繁琐又冗长,希望能够给一些同学对gbdt更深刻的理解。

没啥广告要打,就这样吧。

另求一个比较好的公式编辑器,鬼知道我现在在excel里面写完公式截图过来有多扯淡,而且图片质量超差,谢谢了。

打赏的大佬可以联系我,赠送超赞的算法资料