⚡机器学习⚡交替方向乘数法(Alternating Direction Method of Multipliers,ADMM)

本文涉及的产品
云原生大数据计算服务 MaxCompute,5000CU*H 100GB 3个月
云原生大数据计算服务MaxCompute,500CU*H 100GB 3个月
简介: ⚡机器学习⚡交替方向乘数法(Alternating Direction Method of Multipliers,ADMM)

最近研究二次判别分析(Quadratic Discriminant Analysis,QDA),发现运用到了交替方向乘数法(ADMM),就很迷。(关键是太菜)


很多博主都是直接翻译或者搬运的,搜罗且了解了很多相关知识,那就来个大总结及其一些自己的想法吧!


(内力有限,仅供学习交流)


确实很难,理论性很强,没有虚的,阅读完内容需要有“勇气”!


image.png

image.png

ADMM

背景

咱们先来了解了解,ADMM到底是个什么东西?


交替方向乘数法(Alternating Direction Method of Multipliers),从字面意思上理解,交替方向?是不是很迷?交替计算?交替求解?。。。难道是对偶问题?对偶求解?


先不管了,再看后半句,乘数法?咦~是不是感觉有点熟悉。


la.la.la…Lagrange乘数法???


(没错,就是Lagrange,直接干起来,等等,这里只说对了一半,具体咱们下面慢慢道来~)


ADMM是一个不算是太新的算法,其实就是一种求解优化问题的计算框架, 适用于求解分布式凸优化问题,特别是统计学习问题。 ADMM 通过分解协调(Decomposition-Coordination)过程,将大的全局问题分解为多个较小、较容易求解的局部子问题,并通过协调子问题的解而得到大的全局问题的解。


简单的理解就是,整个算法只是整合许多不少经典优化思路,然后结合现代统计学习所遇到的问题,提出了一个比较一般的比较好实施的分布式计算框架。


而他的历史可以追溯到看下面:


ADMM 最早分别由 Glowinski & Marrocco 及 Gabay & Mercier 于 1975 年和 1976年提出,并被 Boyd 等人于 2011 年重新综述并证明其适用于大规模分布式优化问题。由于 ADMM的提出早于大规模分布式计算系统和大规模优化问题的出现,所以在 2011 年以前,这种方法并不广为人知。


作为搞自动化、控制、优化、诊断…的本菜来说,当然是奔着优化求解去学习的。


先来看看一个大佬对目前大数据及其优化的见解,简直是一针见血,说出来我的心声:


业界一直在谈论大数据,对于统计而言,大数据其实意味着要不是样本量增加n → ∞ n\rightarrow \inftyn→∞,要不就是维度的增加p → ∞ p \rightarrow \inftyp→∞,亦或者两者同时增加,并且维度与样本量的增长速度呈线性或者指数型增长。在稀疏性的假设条件下,再加上一些正则性方法,统计学家可以证明各种加penalty的模型所给出的参数估计具有良好的统计性质,收敛速度也有保证,同时还会给出一些比较好的迭代算法,但是,他们并没有考虑真实环境下的所消耗的计算时间。虽然统计学家也希望尽量寻求迭代数目比较少的算法(比如one-step估计),但是面对真实的Gb级别以上的数据,很多时候我们还是无法直接用这些算法,原因是一般的硬件都无法支撑直接对所有数据进行运算的要求。如果想减少抽样误差,不想抽样,又想提高估计的精度,那么还是需要寻求其他思路,结合已有的模型思想来解决这些问题。在目前条件下,并行化、分布式计算是一种比较好的解决思路,利用多核和多机器的优势,这些好算法便可以大规模应用,处理大数据优势便体现出来了。对于统计而言,数据量越大当然信息越可能充分(假设冗余成分不是特别多),因为大样本性质本身就希望样本越多越好嘛。—源自此处


还需要知道的一点,我们都知道搞优化会遇到很多问题,无非是数据量上和维度的变化,关键词大都为:降维,收敛,迭代等等,而这里的ADMM算法不同于那些梯度下降法或其他改进的SGDM、RMSProp、Adam等等更多高级算法,应用的大多为以GB级别的数据量的数据集,如果与SGDM、Adam这些算法在同样的低维数据(这里指的是较GB级别低的)进行比较,收敛速度绝壁没它们好,很慢,实际的收敛速度往往比那些算法慢得多。ADMM的主要应用,主要是在解空间规模非常大的情况下(比如X、Y 都是存储空间上GB的超大规模矩阵),这个时候很多传统的方法不好用,强制需要分块求解,而且对解的绝对精度往往要求也没那么高。所以我觉得这是,需要提前知道的一点。


确实,这个算法很难理解,公式也很难,不敢保证,我能将其解释清楚,抱着互相学习的态度写这篇Blog!(望各位大佬批评指正)


具体结构,从ADMM需要用到的背景知识、ADMM原理、具体应用这几块进行解释。


下面咱们从基本框架结构入手吧~


背景知识

《Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers》文章中提到了一些预备知识,学过最优化或最优估计等优化课程的童鞋应该能够很快能够理解,对偶问题若很陌生的小伙伴,可以补充补充相关的知识。


先来了解一些基本算法思想吧~


对偶上升

对于凸函数的优化问题,对偶上升法核心思想就是引入一个对偶变量,然后利用交替优化的思路,使得两者同时达到optimal。


读到这里,让我们想起咱们的主题,“交替方向”,是不是有点感觉了。

对于凸函数,我们只需要知道,凸优化问题有一个良好的性质即:局部最优解便是全局最优解

对凸函数有不解的地方,可看这位大佬的博客。


一个凸函数的对偶函数其实就是原凸函数的一个下界,因此可以证明一个较好的性质:在强对偶性假设下,即最小化原凸函数(primal)等价于最大化对偶函数(dual),两者会同时达到optimal。这种转化可以将原来很多的参数约束条件变得少了很多,以利于做优化。具体表述如下:

image.png

image.png

对于对偶问题有所不解的,可以简单理解成为原函数是Y关于X的函数,那么对偶的函数则为X关于Y的函数,这样理解是不是更容易一点呢。

image.png

image.png

image.png

image.png

image.png

image.png

强对偶的假设下,原问题和对偶问题的解都是一样的,同时达到最优。

什么是强对偶性?就是指原问题的解与对偶问题的解是相同的,也即是:

image.png

image.png

image.png

arg 是变元(即自变量argument)的英文缩写。

arg min 就是使后面这个式子达到最小值时的变量的取值>

arg max 就是使后面这个式子达到最大值时的变量的取值


假如g ( y ) g(y)g(y)可求其导数,那么利用梯度上升法,交替更新参数,使得同时收敛到最优。迭代如下:

image.png

image.png

对偶分解

虽然对偶上升的方法有所缺陷,导致我们在实际操作中会遇到重重困难。

但是世界万物都是存在着两面,有其弊也有其利,就如下面的太极双鱼图

image.png

那么,我们可以利用其优秀的一面,当目标函数 f 是可分的(separable)时候(参数亦或feature可分),整个问题可以拆解成多个子参数问题,分块优化后汇集起来整体更新。


这也就是快接近咱们的主题了,分布式凸优化问题。


我们可以分块,然后并行化处理。


由此,我们可分离的目标函数为:

image.png

image.png

image.png

image.png

image.png

对偶分解是非常经典的优化方法,可追溯到1960年代。这种思想对后面的分布式优化方法影响较大,比如近期的graph-structure优化问题。(具体可自行查询一下下)

增广的拉格朗日乘数法

image.png

反正,记住一点即可:增加惩罚项,扩大约束条件的容纳范围,放松假设条件。

可使其收敛的更快。

那么,增加惩罚项的拉格朗日项为:

image.png

其中,最后加了的L2正则化,二范数,也就是岭回归优化项就是惩罚项。ρ \rhoρ 则为我们的松弛因子(惩罚系数),用于更加精细的调节扩大的范围边界。


我们可以将其等价为优化的目标函数形式:

image.png

我们增加的惩罚函数的好处是为了让对偶函数

image.png

更具有可导性,更新参数的计算过程和对偶上升的一致。除最小化x xx的时候加上惩罚项:

image.png

image.png

解除严格凸函数的限制的任务已经完成了,但是同时又存在另外一个问题,当增加惩罚项后,其平方项写成矩阵形式无法是用之前那种分块形式的,因此,在更新x xx最小化时,无法做到并行优化多个x i

参数,关于新的问题的解决办法,ADMM则杀出重围了!!!


ADMM算法原理

在上述的层层递进的方法中,你是否也发现了其中的奥秘,对偶上升法解决了可分解性问题,增广乘子法解决了严格的凸函数限制条件,增强了收敛性。那么是否,我们可以将二者集合在一起,取其各自的优点呢?


答案当然是肯定的,那就是ADMM算法,同时解决了将原函数进行分解和扩展函数的约束范围问题。使得f ( x ) f(x)f(x)能够适应于更多的更广泛的约束条件求解问题。


结合两者的优点,就有了下式目标函数:

image.png

image.png

image.png

和上面的增广拉格朗日一样,只不过增加了新的变量z zz而已。


于是ADMM的优化就变成了如下序贯型迭代(这正是被称作alternating direction交替方向的缘由):

image.png

可以看出,每次迭代分为三步:


求解与 x  相关的最小化问题,更新变量 x

求解与 z  相关的最小化问题,更新变量 z

更新对偶变量 u

ADMM名称中的“乘子法”是指这是一种使用增广拉格朗日函数(带有二次惩罚项)的对偶上升(Dual Ascent)方法,而“交替方向”是指变量 x 和 z 是交替更新的。两变量的交替更新是在 f ( x )或 g ( z )可分时可以将优化问题分解的关键原因。


到此,通过以上的内容来理解“交替方向乘数法(ADMM)”是不是就豁然开朗了许多,开篇说很难,其实是不是并没有那么的难。

image.png

image.png

image.png

当然,写成这种形式有利于后面简化优化问题,也可不作任何的处理。


具体应用

大佬回答及点评

ADMM( Alternating Direction Method of Multipliers)算法是机器学习中比较广泛使用的约束问题最优化方法,它是ALM算法的一种延伸,只不过将无约束优化的部分用块坐标下降法(block coordinate descent,或叫做 alternating minimization)来分别优化。产生这种方法主要是为了弥补二次惩罚的缺点。

在一些问题当中,用二次惩罚来近似约束问题在最优点附近需要惩罚项的系数趋近于无穷,而这种要求会使得海森矩阵很大,因此近似的目标函数很不稳定。为了解决这个问题,引入了线性逼近的部分,通过线性项系数不断的接近最优解(对偶上升),使得在二次惩罚项的系数很小的情况下,也能得到满足要求精度的解。ADMM目前是比较成熟,比较受欢迎的约束问题最优化通用框架。(引用源自知乎大佬)

image.png

受约束的凸优化问题

一般的受约束的凸优化问题可以写成如下形式:

image.png

可将此类型写成ADMM形式,增加新变量,以分解原始变量:

image.png

相应的增广拉格朗日项为:

image.png

其中的 g 函数即 C  的示性函数,上述是scaled形式,那么具体算法就是:

image.png

示性函数,顾名思义,是表示自变量性态的一个函数。

统计学习中的应用

统计学习问题也是模型拟合问题(我们知道有拟合和过拟合),可表示为:

image.png

image.png

对于带L1正则化项的线性回归(Lasso),其平方损失函数为

image.png

对于逻辑回归(Logistic Regression),其极大似然损失函数为

image.png

对于线性支持向量机(Linear Support Vector Machine),其合页(Hinge)损失函数为

image.png

将训练数据在其原始样本M维度下将其划分为N块:

image.png

由此我们可得到分块的目标函数来实现分布式计算:

image.png

相应的简洁迭代更新D 、 d 、 x 的计算方式为:


image.png

个人见解

最后说两句,虽然优化算法千千万,在不同时期,随着科技的发展与进步,老的算法暂时过时,新的算法逐步崛起,但终归要落实到实际应用当中才是真正的好算法,并不是说一味的提高求解速度,提高精度,有些时候成本会很高,有些时候老的算法会被拾起成为yyds,新的算法未必就好。终究说来,希望能够有更多更实际应用范围更加广泛的优化算法逐步崛起吧~


image.png

相关实践学习
基于MaxCompute的热门话题分析
本实验围绕社交用户发布的文章做了详尽的分析,通过分析能得到用户群体年龄分布,性别分布,地理位置分布,以及热门话题的热度。
SaaS 模式云数据仓库必修课
本课程由阿里云开发者社区和阿里云大数据团队共同出品,是SaaS模式云原生数据仓库领导者MaxCompute核心课程。本课程由阿里云资深产品和技术专家们从概念到方法,从场景到实践,体系化的将阿里巴巴飞天大数据平台10多年的经过验证的方法与实践深入浅出的讲给开发者们。帮助大数据开发者快速了解并掌握SaaS模式的云原生的数据仓库,助力开发者学习了解先进的技术栈,并能在实际业务中敏捷的进行大数据分析,赋能企业业务。 通过本课程可以了解SaaS模式云原生数据仓库领导者MaxCompute核心功能及典型适用场景,可应用MaxCompute实现数仓搭建,快速进行大数据分析。适合大数据工程师、大数据分析师 大量数据需要处理、存储和管理,需要搭建数据仓库?学它! 没有足够人员和经验来运维大数据平台,不想自建IDC买机器,需要免运维的大数据平台?会SQL就等于会大数据?学它! 想知道大数据用得对不对,想用更少的钱得到持续演进的数仓能力?获得极致弹性的计算资源和更好的性能,以及持续保护数据安全的生产环境?学它! 想要获得灵活的分析能力,快速洞察数据规律特征?想要兼得数据湖的灵活性与数据仓库的成长性?学它! 出品人:阿里云大数据产品及研发团队专家 产品 MaxCompute 官网 https://www.aliyun.com/product/odps 
相关文章
|
7月前
|
机器学习/深度学习 算法 关系型数据库
PyTorch深度强化学习中蒙特卡洛策略梯度法在短走廊环境(CartPole-v0)中的实战(超详细 附源码)
PyTorch深度强化学习中蒙特卡洛策略梯度法在短走廊环境(CartPole-v0)中的实战(超详细 附源码)
83 0
|
机器学习/深度学习 算法 计算机视觉
【智能优化算法-圆圈搜索算法】基于圆圈搜索算法Circle Search Algorithm求解单目标优化问题附matlab代码
【智能优化算法-圆圈搜索算法】基于圆圈搜索算法Circle Search Algorithm求解单目标优化问题附matlab代码
【智能优化算法-圆圈搜索算法】基于圆圈搜索算法Circle Search Algorithm求解单目标优化问题附matlab代码
|
机器学习/深度学习 人工智能 编解码
用消息传递求解偏微分方程,ML大牛Max Welling等用全神经求解器做到了更强、更快
用消息传递求解偏微分方程,ML大牛Max Welling等用全神经求解器做到了更强、更快
用消息传递求解偏微分方程,ML大牛Max Welling等用全神经求解器做到了更强、更快
|
机器学习/深度学习 存储 编解码
强化学习从基础到进阶-常见问题和面试必知必答[4]::深度Q网络-DQN、double DQN、经验回放、rainbow、分布式DQN
强化学习从基础到进阶-常见问题和面试必知必答[4]::深度Q网络-DQN、double DQN、经验回放、rainbow、分布式DQN
|
机器学习/深度学习 传感器 算法
【麻雀算法】基于自适应螺旋飞行麻雀搜索算法求解单目标优化问题附matlab代码(Adaptive Spiral Flying Sparrow Search Algorithm,ASFSSA)
【麻雀算法】基于自适应螺旋飞行麻雀搜索算法求解单目标优化问题附matlab代码(Adaptive Spiral Flying Sparrow Search Algorithm,ASFSSA)
|
算法 Java
数学建模常用算法:迭代局部搜索算法求解tsp问题+att48算例测试【java实现--详细注释】
数学建模常用算法:迭代局部搜索算法求解tsp问题+att48算例测试【java实现--详细注释】
145 0
|
机器学习/深度学习 人工智能 运维
NeurIPS 2022 Oral | 基于最优子集的神经集合函数学习方法EquiVSet
NeurIPS 2022 Oral | 基于最优子集的神经集合函数学习方法EquiVSet
102 0
|
机器学习/深度学习 传感器 算法
多元宇宙算法求解多目标优化问题附matlab代码(Multi-VerseOptimizer,MVO)
多元宇宙算法求解多目标优化问题附matlab代码(Multi-VerseOptimizer,MVO)
|
决策智能
运筹优化学习03:Lingo非唯一最优解问题--油气开采构造处最优选择问题
运筹优化学习03:Lingo非唯一最优解问题--油气开采构造处最优选择问题
运筹优化学习03:Lingo非唯一最优解问题--油气开采构造处最优选择问题