从解决问题的角度思考一下xgboost的原理# DataSciences - 数据科学
T*x
1 楼
抛砖引玉。
假设有一个训练数据集，有两个feature分别为X和Y，目标值为Z。
假设XYZ都取[0,1]之间的实数。
训练目标是要得到一个函数Z=f(X,Y)以作预测之用。
最理想的解决当然是找出数量之间的物理联系，得到解析解。
其次是用回归的方法，比如线性回归，Z=aX+bY+c，
也就是要找到三个参数abc，使得训练误差最小。
使用回归的方法其实也要对数量之间的内在联系有所假设。
也因此参数较少，在这个例子中是三个参数，解空间为三维。
如果实在找不出数量之间联系的合理假设，那就用笨办法，
也可以说用最直接的办法，分片求平均，然后以平均值给分片赋值。
得到的函数是一个分片函数。分片函数和决策树是等价的。
因为分片函数在使用上就比如
先判断X是否小于0.5，再判断Y是否大于0.7，
再判断X是否大于0.4，再判断Y是否小于0.9，然后给一个值。
这正是一个决策树。
关键是如何分片，分多少片。
假设只考虑Cartesian Product分片，比如X维度上以
0
解空间是8维，比线性回归的解空间大多了。
如果用和线性回归同样的方法找最优解，那就难多了。
那怎么找呢？
先考虑一下这个分片函数应该是什么样子才合理。
这个分片函数应该在每一个分片上训练样本的取值尽量趋同，
也就是每一片的取值的面越平越好。
或者说每一片样本方差越小越好。
怎么才能找到样本方差小的分片呢？
这个地方是xgboost的一个核心设计：分裂法。
比如现在还没有分片，那么在X维度上找一个点X1，
把XY feature空间分两半，两半各自的方差之和小于未分片之前的总方差。
小多少呢？这和X1点的选取有关。
那么有一个点可以使得这个方差变小的数量最大。
几何意义是在某一点上分两半使两边的样本面越平越好。
Y维度上也可以找这么一个点Y1。X1和Y1之间还可以比较一下，
取一个最好的点比如是X1，这就是第一步分裂。
第二步怎么办呢？还是在X维度上找X2同时在Y维度上找Y1，
使得X2是X维度上的最优分裂点，Y1是Y维度上的最优分裂点。
然后再比较X2和Y1，取一个最优点，比如是Y1，这是第二步分裂。
以此类推。
有一些regularization方面的考虑：
分片不能分太细：这个可以用分裂最大数量来限制，也就是树高。
learning rate的意义：
一整套分裂完成之后，比如找到最优的分裂序列
(X1,Y1,Y2,X2,X3,X4,Y3,X5)
之后就得到了一个分片函数。这个分片函数从得到的过程来看已经是最优了。
但是我们并不让它一步到位。而是在这个最优方向上只前进一小步。
前进多少呢？乘以这个learning rate。就前进这么多。
那这个前进一小步的函数离训练样本的实际值还有好大差距。
以这个差距为目标函数，我们再用这个分裂法来找到下一个分片函数，
然后再以learning rate前进一小步。如此继续。
为啥不让它一步到位呢？这个地方我觉得道理挺深。
我只能形象的思考一下：比如手工捶打一口铁锅，
在最优的方向上敲一锤子，敲敲打打，最后就成型了。
假设有一个训练数据集，有两个feature分别为X和Y，目标值为Z。
假设XYZ都取[0,1]之间的实数。
训练目标是要得到一个函数Z=f(X,Y)以作预测之用。
最理想的解决当然是找出数量之间的物理联系，得到解析解。
其次是用回归的方法，比如线性回归，Z=aX+bY+c，
也就是要找到三个参数abc，使得训练误差最小。
使用回归的方法其实也要对数量之间的内在联系有所假设。
也因此参数较少，在这个例子中是三个参数，解空间为三维。
如果实在找不出数量之间联系的合理假设，那就用笨办法，
也可以说用最直接的办法，分片求平均，然后以平均值给分片赋值。
得到的函数是一个分片函数。分片函数和决策树是等价的。
因为分片函数在使用上就比如
先判断X是否小于0.5，再判断Y是否大于0.7，
再判断X是否大于0.4，再判断Y是否小于0.9，然后给一个值。
这正是一个决策树。
关键是如何分片，分多少片。
假设只考虑Cartesian Product分片，比如X维度上以
0
解空间是8维，比线性回归的解空间大多了。
如果用和线性回归同样的方法找最优解，那就难多了。
那怎么找呢？
先考虑一下这个分片函数应该是什么样子才合理。
这个分片函数应该在每一个分片上训练样本的取值尽量趋同，
也就是每一片的取值的面越平越好。
或者说每一片样本方差越小越好。
怎么才能找到样本方差小的分片呢？
这个地方是xgboost的一个核心设计：分裂法。
比如现在还没有分片，那么在X维度上找一个点X1，
把XY feature空间分两半，两半各自的方差之和小于未分片之前的总方差。
小多少呢？这和X1点的选取有关。
那么有一个点可以使得这个方差变小的数量最大。
几何意义是在某一点上分两半使两边的样本面越平越好。
Y维度上也可以找这么一个点Y1。X1和Y1之间还可以比较一下，
取一个最好的点比如是X1，这就是第一步分裂。
第二步怎么办呢？还是在X维度上找X2同时在Y维度上找Y1，
使得X2是X维度上的最优分裂点，Y1是Y维度上的最优分裂点。
然后再比较X2和Y1，取一个最优点，比如是Y1，这是第二步分裂。
以此类推。
有一些regularization方面的考虑：
分片不能分太细：这个可以用分裂最大数量来限制，也就是树高。
learning rate的意义：
一整套分裂完成之后，比如找到最优的分裂序列
(X1,Y1,Y2,X2,X3,X4,Y3,X5)
之后就得到了一个分片函数。这个分片函数从得到的过程来看已经是最优了。
但是我们并不让它一步到位。而是在这个最优方向上只前进一小步。
前进多少呢？乘以这个learning rate。就前进这么多。
那这个前进一小步的函数离训练样本的实际值还有好大差距。
以这个差距为目标函数，我们再用这个分裂法来找到下一个分片函数，
然后再以learning rate前进一小步。如此继续。
为啥不让它一步到位呢？这个地方我觉得道理挺深。
我只能形象的思考一下：比如手工捶打一口铁锅，
在最优的方向上敲一锤子，敲敲打打，最后就成型了。
