CWYAlpha

Just another WordPress.com site

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

leave a comment »


前阵子去参加了数学规划会议,报告很多,人也很多。或者说报告和人过多了……
有少数感兴趣的报告,这里谈一下全场最后一个报告。报告人是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

from Dora Blog: http://diaorui.net/?p=360

Written by cwyalpha

九月 5, 2012 在 9:08 上午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: