大规模问题快速算法的困惑





最近所里请了南京大学何炳生老师来做系列报告,他主要研究一阶算法,所谓一阶算法,只利用一阶最优性条件,通常借助一阶信息(梯度,Jacobi矩阵),不用二阶信息(Hession)。对于大规模问题来讲,这样做会节约很多计算量。当然他主要做理论,演示了如何利用他的方法简单和巧妙的证明一些算法的全局收敛性,感觉很有收获。
解决大规模问题的迭代算法通常有两个要点:1,每次迭代计算量不能太大,通常需要利用矩阵稀疏性质等;2,迭代次数不能太多,收敛速度快,在局部最好有超线性收敛甚至二次收敛。
看一个简单的例子,比如非线性目标函数,无约束优化问题的拟牛顿算法,在局部具有超线性收敛性,但是缺点是拟牛顿矩阵一般容易很稠密,这样会很慢。而有限内存的拟牛顿算法则只有线性收敛性(从理论上看,线性收敛相当于拟牛顿不起作用一样),但是每次迭代却只需要计算若干个向量内积!而在实际计算上,也常常能观察到差不多超线性收敛的性质。
去年做KDD-CUP,矩阵因子分解模型在他们搞推荐系统的文章里面,主要用随机梯度下降方法,这在数学上看来很不好。除非你选择的参数非常好,否则都不能收敛。实际上也确实是这样的。当然对于一个老手来讲是无所谓拉,基本搞两三次就找到几乎最好的参数了。但是不得不承认,如果在参数上没有经验,那么很可能这方法就什么也算不出来。实际上最近几年搞计算数学的很多做一阶方法了,矩阵分解模型也有了非常好的一阶方法(交替方向法)和相应Matlab程序。不过就我的计算经验看,交替方向法虽然能保证收敛,而且速度不错,但是他基本上不太可能比一个老手选取参数后的随机梯度下降法计算量小。因为随机梯度下降每次迭代几乎不比扫描一遍所有打分慢多少,而交替方向法每次还要求个QR分解(虽然也很快吧)。当然了,交替方向法的优点,就是不需要特别有经验的选取参数,收敛效果就还不错,毕竟有数学理论保证,而且也能用来去算KDD-CUP这种大规模问题。感觉现在数据挖掘的方法凭借经验的很多,不知道这些有理论保证的方法在什么时候才能大规模的用到数据挖掘呢……

本文来自Dora Blog,题目为大规模问题快速算法的困惑,转载请注明出处。
如果你喜欢我的博客,请订阅本博客的RSS以更方便的阅读
欢迎关注我的新浪微博:http://weibo.com/diaorui1987