今天看nips2017的预选论文，翻到了4篇推荐相关的，其中3篇都是做cold start问题，看来这个问题最近很火热嘛，包括了RL和meta learning，看来有必要跟进一波潮流。再看其他的论文的时候，还翻到了微软的lightGBM，果断先捞出来看一下。
之前网上流传了许多关于lightGBM相关的内容，但是看到论文才是最实在的，文中提到相比于其它关于GBDT的实现，对于计算信息增益来划分节点的做法都还是太耗时间了，基本上都是\(\#feature\times\#data\) 的计算损耗，而基于柱状图（histograms-based）的方法则会相比更高效且节约内存，所以lightGBM也是从这个思路出发的。
BTW，文中的review部分包括了很多已有的其它GBM实现方法的回顾，都cite的是很经典的文章，如果想深入了解的话可以按照文中的review来看。
lightGBM主要从两方面来优化，feature数量和data数量，分别提出EFB（Exclusive Feature bundling）和GOSS（Gradient-based One-Side Sampling）进行分别的优化。
在划分时，gradient大的样本（instance）往往会对信息增益有较大的贡献，所以，我们用采样的方法，减小那些数量较多但是gradient较少对节点划分增益不大的样本的影响，首先根据绝对误差排序，选择top \(a\%\)的样本，然后从剩下的采样 \(b\%\)，同时赋予不同的权重。后面作者做了理论分析，表示这么抽样不会改变训练数据分布，blabla（当然我是没看的）
EFB则是解决特征的问题，训练数据往往会十分稀疏，如大量onehot产生的特征，而GBDT这样的算法，在面对节点划分时，不得不考虑所有特征，所以我们用bundling的方式来减少不必要的特征。因为是从histograms-based的想法出发，EFB实际上也是再用划分“桶”（如LSH）这样的方法，减少特征量。具体做法是利用图的着色问题，用特征构造图的矩阵，然后根据着色来划分，如果两个特征不是mutually exclusive，则它们之间存在边。（具体操作此处没看太明白，着色问题我也没看过，留个坑）对于一个bundling的feature，则改变feature的取值区间来merge不同的feature。
后面是文章的实验部分，效果还是很好的，看微软的论文，就给我一种哪有问题我就干掉哪的感觉，而且是工程化很强的东西，包括之前的lightLDA，现在lightGBM，都是非常厉害。