Archive: 九月, 2012

第一次玩Hackathon

前几天去腾讯玩了一回Hackathon,确实很好玩,某种程度上比acmicpc还好玩。
之前根本没有打算进决赛的,所以复赛也没好好做。最近很忙,如果腾讯把时间推迟一周,我就肯定放弃了。
我们项目选题是分析微博/人人用户的特征,随便指定个人就能分析点有意思的东西出来。这个思路是yangzhe1991友情提供的。
爬数据、整理数据、分词、画图、前端展示。个人认为至少从代码量上看,可能是里面最累的项目(我可不愿意只做出半成品……)。这也是为什么第一天一直没有可展示的东西做出来的原因。队里BearForest也有做网站经验,所以配合起来比较容易,而javaman搞C++,主要负责后台数据处理。我们最不擅长美工,由于腾讯配了设计师,也容易很多(专业的人真NB啊……画图又快又好看)。前端其实是最容易做的,只有画柱状图和tag云略麻烦,但前者我以前做网站用过很好的插件,比较熟悉。所以前端放到最后再做,反正没有难度,结果就导致中间裁判们来“骚扰”的时候,实在没东西可以给他们看。
============据说中间插播广告效果最好============
ACM/ICPC信息站 http://acmicpc.info
ACMer博客瀑布流 http://blog.acmicpc.info
晒代码 http://shaidaima.com
acmicpc微博 http://weibo.com/acmicpc
acmicpc人人 http://renren.com/acmicpc
====================广告结束==================
三个人一夜没睡觉,期间BearForest喝了4罐红牛,javaman写了一首诗……
早上裁判们再来看的时候,都觉得我们突然就做出东西了……汗……其实因为整后台最花时间而已。
答辩一切顺利,程序没什么大bug,裁判们测试的几个人都算的还不错。其实除了微博,我们把人人网也做好了,只是正常人都不会记得自己或者其他人的人人主页地址的(因为一般都没有个性域名……),所以没特意找人玩了。早考虑到这点就暂时先不做了,多分析一个网站还是花了不少精力的。
晚上吃饭的时候,BearForest问我觉得能有第几名。我说估计在第三第四之间吧。结果就真的被我说中了……莫非是因为我抽中iPad导致RP用光,居然真的是第四名。略桑心。但是发现,前三好像都是app吧……诺基亚用户表示无法跟上app的潮流,所以只好一直搞web玩。
结论:Hackathon很好玩。
比起ACM来,Hackathon不会因为出题不好、数据出错而影响效果,也不会因为只考算法而不够全面。做出东西可以展示,时间也不是太长。确实很好玩。只是评价有一定难度。大家选题差距较大,评分标准没有ACM容易统一。个人认为Hackathon比AI大赛也好玩一些。如果存在一种结合了ACM和Hackathon的比赛形式也许会更好玩吧,不知道存在吗?
但可惜这不能经常玩,身体受不了。要是之前想过的每个点子都这种强度去搞,早就搞完了。而现在还有很多想法都搁置着。我和licstar都没什么空,有一些好玩的点子还都没有动手。并且平时维护已有的几个网站就已经比较累了。
收获公仔、抱枕、iPad、Kindle,还是很赚的啊。。。明年这时候也还没毕业,如果有空再去玩一下吧。
截至本文发布时,报道比赛结果的ACMICPC人人公共主页状态被转发145次,ACMICPC微博被转发80次。应该给我们无盈利的acmicpc.info团队一个宣传奖什么的 @_@

随机样本选择——快速求解机器学习中的优化问题

前阵子去参加了数学规划会议,报告很多,人也很多。或者说报告和人过多了……
有少数感兴趣的报告,这里谈一下全场最后一个报告。报告人是Jorge Nocedal,就是著名的LBFGS的作者。
他关注的问题是一类机器学习中非常常见的优化模型:
$J(w) = \frac{1}{N} \sum_{i=1}^N l(f(w; x_i); y_i)$
他谈到了机器学习里面常用的随机梯度下降法(stochastic gradient descent, SGD)。在实际大数据的情况下,他比经典优化方法效果要好。因为经典优化方法算一次下降方向就已经需要很大计算量了。
SGD需要的一次迭代计算量非常小,但是代价是他非常可能不是下降方向,而且需要一个有经验的人选择很好的步长(学习速率)。并且,在理论上,SGD的性质少,所以在优化这个方向里没什么人提到。即使是在计算上,Nocedal也提到SGD有个很大的缺点是不容易并行。
以上这些现象我在学习推荐系统SVD模型的时候也有一些感触。
所以他采用了另外一个思路,思想简单,效果却很好。而且能很好的利用上经典优化算法。经典算法都需要计算梯度。他的思想就是:只选取一部分样本来计算梯度。
这样有一个近似的梯度计算方法,用
$J_S(w)=\frac{1}{|S|} \sum_{i \in S} l(f(w; x_i); y_i)$
代替原来目标函数,求它的梯度。
其中S是样本集,样本集的大小相对于N来说很小。但是他也不能太小。只要有了梯度,很多算法都能用上了,比如说他文章中提到梯度方法,Newton-CG方法。S中的元素可以在每次迭代的时候随机选取。
但是需要面临的一个问题就是如何确定S的大小。他给出了一个公式用来确定S的大小是否合适。
$\| \nabla J_S(w) – \nabla J(w) \|_2 \le \theta \| \nabla J(w) \|_2 $
这个式子的含义就是样本集上的近似梯度和真实梯度足够接近。当然这个又回到了老问题,就是真实梯度计算量太大。于是他又做了一些近似变换,使得只需要计算在样本集S上的方差即可近似估计上式是否满足。
$ \frac{ \| Var^2_S( l(w; i) ) \|_1 }{ \| S \| } \le \theta ^2 \| \nabla J(w) \|_2 ^2 $
这样就可以每次迭代验证一下S是否足够大,如果不够大就扩大一下。
这个技巧部分解决了我对大规模优化计算的一些困惑,他可以利用上很多经典优化算法,并且又能让每次迭代的运算量不会太大。这个技巧也使得并行计算容易用上去了。
后面考虑去使用一下,算算某个实际例子测试一下效果。
Nocedal这篇论文的链接:http://users.eecs.northwestern.edu/~nocedal/PDFfiles/dss.pdf