用ADMM求解大型机器学习问题

忘是亡心i 2023-06-04 02:48 33阅读 0赞

[用ADMM求解大型机器学习问题][ADMM]

\[本文链接：[http://www.cnblogs.com/breezedeus/p/3496819.html][http_www.cnblogs.com_breezedeus_p_3496819.html]，转载请注明出处\]

从等式约束的最小化问题说起：                                    
                                                     [![image][]][image 1]   
上面问题的拉格朗日表达式为：  
                                             [![image][image 2]][image_image 2]   
也就是前面的最小化问题可以写为：  
                                              minxmaxyL(x,y)minxmaxyL(x,y) 。  
它对应的对偶问题为：  
                                             maxyminxL(x,y)maxyminxL(x,y) 。  
下面是用来求解此对偶问题的**对偶上升迭代方法**：  
                                   [![image][image 3]][image_image 3]   
这个方法在满足一些比较强的假设下可以证明收敛。

为了弱化对偶上升方法的强假设性，一些研究者在上世纪60年代提出使用扩展拉格朗日表达式（augmented Lagrangian）代替原来的拉格朗日表达式：  
                                 [![image][image 4]][image_image 4]   
其中ρ>0ρ>0。对应上面的对偶上升方法，得到下面的**乘子法（method of multipliers）**：  
                                                    [![image][image 5]][image_image 5]

注意，乘子法里把第二个式子里的αkαk改成了扩展拉格朗日表达式中引入的ρρ。这不是一个随意行为，而是有理论依据的。利用L(x,y)L(x,y)可以导出上面最小化问题对应的原始和对偶可行性条件分别为（∂L∂y=0∂L∂y=0，∂L∂x=0∂L∂x=0）：  
                                              [![image][image 6]][image_image 6]   
既然xk\+1xk+1 最小化 Lρ(x,yk)Lρ(x,yk)，有：  
                                      [![image][image 7]][image_image 7]    
上面最后一个等式就是利用了yk\+1=yk\+ρ(Axk\+1−b)yk+1=yk+ρ(Axk+1−b)。从上面可知，这种yk\+1yk+1的取法使得(xk\+1,yk\+1)(xk+1,yk+1)满足对偶可行条件∂L∂x=0∂L∂x=0。而原始可行条件在迭代过程中逐渐成立。

乘子法弱化了对偶上升法的收敛条件，但由于在x-minimization步引入了二次项而导致无法把x分开进行求解（详见\[1\])。而接下来要讲的**Alternating Direction Method of Multipliers (ADMM)**就是期望结合乘子法的弱条件的收敛性以及对偶上升法的可分解求解性。ADMM求解以下形式的最小化问题：  
                                             [![image][image 8]][image_image 8]   
其对应的扩展拉格朗日表达式为：   
                   [![image][image 9]][image_image 9]   
ADMM包括以下迭代步骤：  
                                       [![image][image 10]][image_image 10]   
ADMM其实和乘子法很像，只是乘子法里把xx和zz放一块求解，而ADMM是分开求解，类似迭代一步的Gauss-Seidel方法。其中(3.4)中的推导类似于乘子法，只是使用了zk\+1zk+1最小化Lρ(xk\+1,z,yk)Lρ(xk+1,z,yk)：  
                                    [![image][image 11]][image_image 11]     
其中用到了zz对应的对偶可行性式子：  
                                                   ∂L∂z=∇g(z)\+BTy=0∂L∂z=∇g(z)+BTy=0

定义新变量u=1ρyu=1ρy，那么(3.2-3.4)中的迭代可以变为以下形式：  
                          [![image][image 12]][image_image 12]   
在真正求解时通常会使用所谓的over-relaxation方法，也即在zz和uu中使用下面的表达式代替其中的Axk\+1Axk+1：  
                                         αkAxk\+1−(1−αk)(Bzk−c)αkAxk+1−(1−αk)(Bzk−c)，  
其中αkαk为relaxation因子。有实验表明αk∈\[1.5,1.8\]αk∈\[1.5,1.8\]可以改进收敛性(\[2\])。

下面让我们看看ADMM怎么被用来求解大型的机器学习模型。所谓的大型，要不就是样本数太多，或者样本的维数太高。下面我们只考虑第一种情况，关于第二种情况感兴趣的读者可以参见最后的参考文献\[1, 2\]。样本数太多无法一次全部导入内存，常见的处理方式是使用分布式系统，把样本分块，使得每块样本能导入到一台机器的内存中。当然，我们要的是一个最终模型，它的训练过程利用了所有的样本数据。常见的机器学习模型如下：  
                                    minimize x∑Jj=1fj(x)\+g(x)minimize x∑j=1Jfj(x)+g(x)，  
其中xx为模型参数，fj(x)fj(x)对应第jj个样本的损失函数，而g(x)g(x)为惩罚系数，如g(x)=||x||1g(x)=||x||1。

假设把JJ个样本分成NN份，每份可以导入内存。此时我们把上面的问题重写为下面的形式：   
                                           [![image][image 13]][image_image 13]   
除了把目标函数分成NN块，还额外加了NN个等式约束，使得利用每块样本计算出来的模型参数xixi都相等。那么，ADMM中的求解步骤(3.2)-(3.4)变为：   
                            [![image][image 14]][image_image 14]   
例如求解L1惩罚的LR模型，其迭代步骤如下（u=1ρyu=1ρy，g(z)=λ||z||1g(z)=λ||z||1）：   
                                   [![image][image 15]][image_image 15]   
其中x¯≐1N∑Nixix¯≐1N∑iNxi，y¯y¯的定义类似。

在分布式情况下，为了计算方便通常会把uu的更新步骤挪在最前面，这样uu和xx的更新可以放在一块：   
                                     [![image][image 16]][image_image 16]

ADMM的框架确实很牛逼，把一个大问题分成可分布式同时求解的多个小问题。理论上，ADMM的框架可以解决大部分实际中的大尺度问题。我自己全部实现了一遍这个框架，主要用于求解LR问题，下面说说我碰到的一些问题：  
1. **收敛不够快**，往往需要迭代几十步。整体速度主要依赖于xixi更新时所使用的优化方法，个人建议使用liblinear里算法，但是不能直接拿来就用，需要做一些调整。  
2. **停止准则和ρρ的选取**：停止准则主要考量的是xixi和zz之间的差异和它们本身的变动情况，但这些值又受ρρ的取值的影响。它们之间如何权衡并无定法。个人建议使用模型在测试集上的效果来确定是否停止迭代。  
3. **不适合MapReduce框架实现**：需要保证对数据的分割自始至终都一致；用MPI实现的话相对于其他算法又未必有什么优势（如L-BFGS、OwLQN等）。  
4.** relaxation步骤要谨慎**：αα的取值依赖于具体的问题，很多时候的确可以加快收敛速度，但对有些问题甚至可能带来不收敛的后果。用的时候不论是用x -> z -> u的更新步骤，还是用u -> x -> z的更新步骤，在u步使用的x\_hat要和在z步使用的相同（使用旧的z），而不是使用z步刚更新的z重算。  
5.** warm start 和子问题**求解逐渐精确的策略可以降低xixi更新时的耗时，但也使得算法更加复杂，需要设定的参数也增加了。

**\[References\]**  
\[1\] S. Boyd.  [Alternating Direction Method of Multipliers][] (Slides).  
\[2\] S. Boyd et al.  [Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers][], 2010.

https://www.cnblogs.com/breezedeus/p/3496819.html

转载于:https://www.cnblogs.com/think90/p/11492351.html

[ADMM]: https://www.cnblogs.com/breezedeus/p/3496819.html
[http_www.cnblogs.com_breezedeus_p_3496819.html]: http://www.cnblogs.com/breezedeus/p/3496819.html
[image]: /images/20230601/7bf9cb4ca894418b97b74ae22143062a.png
[image 1]: https://images0.cnblogs.com/blog/280937/201312/29213239-cbd3da9c2d9a41d3a936b11242801725.png
[image 2]: https://images0.cnblogs.com/blog/280937/201312/29213826-74c3a630c59744f381de54b87caed752.png
[image_image 2]: /images/20230601/38bf43c830e048ea84e3481e9c74d055.png
[image 3]: https://images0.cnblogs.com/blog/280937/201312/29213828-ade100d83f7c436b9f02e8c8b97388ee.png
[image_image 3]: /images/20230601/07d1c31ba5a94f11ba088c32691590fe.png
[image 4]: https://images0.cnblogs.com/blog/280937/201312/29213829-336cd50d01ba455487415ec523c9c9d6.png
[image_image 4]: /images/20230601/c331e5e28de647d3a967a55e015635d1.png
[image 5]: https://images0.cnblogs.com/blog/280937/201312/29213831-6a93cf1e763c405bb84ec2fc757f2d48.png
[image_image 5]: /images/20230601/1c3138ebc1a846dd8a7d148f104bbf1d.png
[image 6]: https://images0.cnblogs.com/blog/280937/201312/29213832-4da492f809b74cfcacf106e4250f1684.png
[image_image 6]: /images/20230601/ac52417307cf496bb9ad3cf6ff465fc3.png
[image 7]: https://images0.cnblogs.com/blog/280937/201312/29213835-91bbf65732564a7b96acf44ad287fe9e.png
[image_image 7]: /images/20230601/b57659866e0e481ea7cd18cf3e41b074.png
[image 8]: https://images0.cnblogs.com/blog/280937/201312/29213839-9c57c94615564639a4fb14eb49878ca4.png
[image_image 8]: /images/20230601/5a415a3e54924bdc804efdc2a8a9de40.png
[image 9]: https://images0.cnblogs.com/blog/280937/201312/29213841-37717b53eb754902b5f81215023b8ffb.png
[image_image 9]: /images/20230601/af6cab67573647b187bad66ce47337a2.png
[image 10]: https://images0.cnblogs.com/blog/280937/201312/29213843-e3a89c3a5b9b40e9974d7ba9ae03b515.png
[image_image 10]: /images/20230601/a419d9a758724221b82317004766bcad.png
[image 11]: https://images0.cnblogs.com/blog/280937/201312/29213844-0c3900fd3472457c973904834c60b9d7.png
[image_image 11]: /images/20230601/24264c77626141c582c07f631b2be000.png
[image 12]: https://images0.cnblogs.com/blog/280937/201312/29213847-c4633f12e3404954abf63ca3e31773c1.png
[image_image 12]: /images/20230601/0034ef35f6c441adae79895fdec459ab.png
[image 13]: https://images0.cnblogs.com/blog/280937/201312/29213850-cc6de085c4e642a0a8d474f2b58aa6b7.png
[image_image 13]: /images/20230601/76efaf6ec5f84e57b2df1d2a9ecf1102.png
[image 14]: https://images0.cnblogs.com/blog/280937/201312/29213857-67e42c62afce4a1b8892516043d08d96.png
[image_image 14]: /images/20230601/56a7e50d6598428da068ccf19ebc275b.png
[image 15]: https://images0.cnblogs.com/blog/280937/201312/29213901-afca6c9820ab4abcb5f9362775b2cde7.png
[image_image 15]: /images/20230601/e14fa792faae4d179c2c0f0bf6b4f23b.png
[image 16]: https://images0.cnblogs.com/blog/280937/201312/29213905-2b1e80b2d10d4c2e885c7dedab117a91.png
[image_image 16]: /images/20230601/5f68b4d9018143528380f7874023444b.png
[Alternating Direction Method of Multipliers]: http://www.stanford.edu/~boyd/papers/pdf/admm_slides.pdf
[Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers]: http://www.stanford.edu/~boyd/papers/pdf/admm_distr_stats.pdf