Bootstrap + subsample: simple, efficient, then elegant?

继续昨天。早晨一起来，看到施老师的一句简短评论，瞬间人就清醒了。然后跟做错了事的小孩子似的，惴惴不安的跑到office里面，翻墙，开始下paper。

现在的节奏基本上是白天开会写代码，晚上回家看paper，哎，不看心里总觉得好惶恐。还好中间等车等了蛮久的，顺便就借着六七点昏黄的路灯把这篇不算太长的paper看完了。有趣的是等车的时候碰到一位同事，然后我俩就开始呱唧呱唧的聊起来统计推断了...不知道当时旁边的路人是不是一道黑线，幸好当时把ebay的牌牌藏在了衣服里面...

这篇不算长的paper是：Bootstrapping Big Data，UC Berkeley 计算机系一群人鼓捣出来的。idea很简单（符合第一标准，simple），就是在大数据上（无放回的随机抽样）取一些subsamples，然后在这些subsamples上面做bootstrap，然后把结果取平均数。

这样的好处显而易见，天生的分布式算法，把数据随机分布到各个计算节点就可以了。然后bootstrap也不用占那么大的内存了，空间时间都省掉了，所以符合第二标准：efficient。

最后，就是还是比较effective的，有着良好的渐进收敛性质。和直接的bootstrap相比，它不仅保持渐进一致，而且有着更高的收敛速度，还是天生并行的...过年回济南的时候joke童鞋（高中同学）去火车站接我，然后我们就兴致昂扬的聊起来大数据和算法并行问题了...是不是有点天雷滚滚？哇咔咔，大过年的...好久没见竟然是如斯叙旧，汗。

此外，还可以结合binning的思路做一些weighted calculation，这样又进一步节省了时间。

不知道这样是不是就足够的elegant了...我看了一眼converging rate 还是比较好看的。伪代码思路也是简单得很。还可以用在各种现成的线形非线性、参数非参数模型上，真是瞬间变身并行高富帅。貌似和前段时间看到的rmr2包里面做OLS并行的思路有点像，待我细细研究一下。

唯一的concern就是这东西更适合hadoop而不适合teradata，哎。我没法在TD上控制节点的分配，这个比较讨厌。Hadoop可以直接写并行map reduce，就会方便很多了。

先看了这一篇简介，后面慢慢地研究一些理论证明什么的，有点too good to believe...还是先找点数据测试玩玩吧^_^