ADMM算法如何应用到AutoML问题上？

LiteralliJeff · 发表于 2022-1-20 16:28

什么是基于ADMM的AutoML算法？

ADMM是最近几年非常火的一个概念，AAAI 2020上，IBM的研究者们顺应时代潮流提出了基于ADMM框架的AutoML算法。首先，需要指出的是，ADMM是一个优化框架而非具体的优化算法。简单来说，ADMM算法的想法是将AutoML问题的架构搜索子问题和超参数优化子问题进行分解，利用交替优化的方式尝试搜索得到最优解。值得一提的是，由于AutoML是一个非凸的黑盒优化问题，因此基于ADMM的AutoML算法没有理论上的收敛性证明，但是从实验结果来看，ADMM-AutoML算法可以取得非常好的效果。
AutoML问题定义

AutoML问题一般可以分为两个部分，即优化模型架构方案  和模型对应的超参数。对于模型架构中的每个模块 $z_i$ ，例如特征选择模块，AutoML算法的一个常见约束是只能选择一个处理选项，即 $\mathbf{1}^{\top} \mathbf{z}_{i}=\sum_{j=1}^{K_{i}} z_{i j}=1$ 。我们使用 $\theta_{i j}^{c}$ 代表连续超参数，  代表离散超参数，那么根据模型架构方案  和参数  ，AutoML可以描述为下面的优化问题。

换个形式，也就是下面的公式。

此外，在AutoML任务中，经常还会出现一些黑盒约束，例如模型体积、预测延时，这些约束无法使用梯度法进行优化，我们可以将这些约束条件以下面的形式加到优化约束项中。

基于ADMM的AutoML算法

问题定义
这里，作者将离散参数  使用连续参数  进行近似，那么优化目标可以化简成如下公式。其中 $\mathcal{P}_{\mathcal{D}}\left(\tilde{\boldsymbol{\theta}}^{d}\right)=\left\{\mathcal{P}_{\mathcal{D}_{i j}}\left(\tilde{\boldsymbol{\theta}}_{i j}^{d}\right), \forall i \in[N], j \in\left[K_{i}\right]\right\}$ ，代表  的整数映射。

上面的优化问题可以进一步改写成下面的优化问题，这里引入了一个整数变量 $\delta_{i j}$ ，并引入约束 $\tilde{\boldsymbol{\theta}}_{i j}^{d}=\boldsymbol{\delta}_{i j}$ 表明最终连续变量的优化结果要是一个整数值。这里将 $\tilde{\boldsymbol{\theta}}_{i j}^{d}$ 替换为 $\boldsymbol{\delta}_{i j}$ 是Trivial的，但这对于ADMM算法是至关重要的。

上面的四个约束条件中的前三个可以转化为下面的目标函数，其中如果 $x$ 是可行的参数，则 $I_{\mathcal{X}}(\mathrm{x})=0$ ，否则该值为无穷大。

随后，我们可以使用增广拉格朗日乘子法将上面的目标函数转化为下面的目标函数。值得一提的是，这里选用的是增广拉格朗日乘子法而非传统的拉格朗日乘子法，只有这样才能通过ADMM算法将优化问题进行分解。

优化求解
根据上面定义的目标函数，我们就可以基于ADMM将目标函数进行分解，分别优化 $\left\{\boldsymbol{\theta}^{c}, \widetilde{\boldsymbol{\theta}}^{d}\right\}$ ， $\boldsymbol{\delta}$ 和 $\boldsymbol{z}$ 这三项。

ADMM只是一个分解框架，并不是具体的优化算法。按照上面方法进行分解之后，在每个优化阶段，我们就可以基于领域知识选择合适的优化方法。
例如，首先我们可以优化连续变量  。即将目标函数中所有与连续变量有关的项提取出来进行优化。

此时，由于已经确定了模型架构方案  ，因此这个阶段优化的变量可以分为与模块  相关的变量和不相关的变量。对于不相关的变量，优化器只需要要求连续化后的整数变量  与  越接近越好。

而对于与模块  相关的变量，则需要同时考虑优化变量  与  越接近越好，同时优化最终AutoML目标 $\widetilde{f}\left(\mathrm{z}^{(t)},\left\{\theta^{c}, \widetilde{\theta}^{d}\right\} ; \mathcal{A}\right)$ 。

在这个阶段，我们可以使用任意的贝叶斯优化算法优化参数  。
接下来，我们优化离散变量  ，这里的目标是尽量让  和  接近。这里不需要优化算法，直接对  四舍五入即可。

在最后一个阶段，我们需要优化整数变量  ，这个变量决定了具体选择哪个机器学习或特征预处理模块，例如选择SVM或决策树作为最终的预测模型。对于这个组合优化问题，我们可以考虑采用MAB或演化算法进行求解。

黑盒约束
除了能够处理经典AutoML问题以外，ADMM-AutoML算法的一个优势是可以处理黑盒约束优化问题。这里，作者将黑盒不等式约束基于一个新引入的松弛变量  转化为等式约束。

基于上面的转化，新的AutoML目标函数可以写成下面的形式。这个目标函数与上面AutoML目标函数的区别是新增了两个约束项，即定义了松弛变量  的范围，同时将上面的等式约束加入到优化约束中。

对于加入了黑盒约束的AutoML问题，我们可以继续进行类似的ADMM分解。其实这里的逻辑和算法一的逻辑是基本一致的，唯一的区别就是因为连续变量  和模型架构方案  会影响最终的黑盒约束结果，因此在优化这两组变量和的时候额外考虑了黑盒约束项。

实现方式
经过上面的分析，很明显可以看出这篇文章提出的ADMM-AutoML算法实际上是一个框架，即使用ADMM思想对AutoML问题进行分解。至于具体的优化方式，我们可以针对每个问题自己选择最合适的策略。这里，作者选择使用贝叶斯优化算法优化连续参数  ，使用汤普森采样优化模型架构参数  。
实验结果

下面这张图展示了不同的AutoML算法的相对排序，从图中可以看出，TPOT算法在初始阶段反而比Random Search更差，从最终结果来看，混合了贝叶斯优化和汤普森采样的ADMM算法具有最好的性能。

下面这张图展示了基于约束的ADMM-AutoML算法（CST）优化公平性指标和模型预测延时相比无约束+post-hoc filter（UCST）更为高效。

此外，ADMM算法还有一个比较有趣的特性的是可以在不同阶段为每个子任务分配不同比例的资源。例如在初始阶段对于每一个机器学习系统  ，可以进行少量的连续参数优化，这样可以促进机器学习Pipeline的快速迭代。然后，我们可以逐渐增加连续参数  的迭代优化次数，以促进针对每个机器学习系统  的精细优化。这种动态调整策略被作者称称为Adaptive ADMM。从下面图中可以看出，这种自适应的策略可以同时保证在优化前期和优化后期都具有良好的效果。

此外，作者尝试了使用传统的贝叶斯优化算法将连续超参数  和模型架构  进行联合优化（JOPT）。从下面的结果来看，基于ADMM框架进行优化可以取得153倍的速度提升，从而证明了基于ADMM算法对AutoML问题进行分解的必要性。

DungDaj · 发表于 2022-1-20 16:29

什么是基于ADMM的AutoML算法？

ADMM是最近几年非常火的一个概念，AAAI 2020上，IBM的研究者们顺应时代潮流提出了基于ADMM框架的AutoML算法。首先，需要指出的是，ADMM是一个优化框架而非具体的优化算法。简单来说，ADMM算法的想法是将AutoML问题的架构搜索子问题和超参数优化子问题进行分解，利用交替优化的方式尝试搜索得到最优解。值得一提的是，由于AutoML是一个非凸的黑盒优化问题，因此基于ADMM的AutoML算法没有理论上的收敛性证明，但是从实验结果来看，ADMM-AutoML算法可以取得非常好的效果。
AutoML问题定义

AutoML问题一般可以分为两个部分，即优化模型架构方案  和模型对应的超参数。对于模型架构中的每个模块 $z_i$ ，例如特征选择模块，AutoML算法的一个常见约束是只能选择一个处理选项，即 $\mathbf{1}^{\top} \mathbf{z}_{i}=\sum_{j=1}^{K_{i}} z_{i j}=1$ 。我们使用 $\theta_{i j}^{c}$ 代表连续超参数，  代表离散超参数，那么根据模型架构方案  和参数  ，AutoML可以描述为下面的优化问题。

换个形式，也就是下面的公式。

此外，在AutoML任务中，经常还会出现一些黑盒约束，例如模型体积、预测延时，这些约束无法使用梯度法进行优化，我们可以将这些约束条件以下面的形式加到优化约束项中。

基于ADMM的AutoML算法

问题定义
这里，作者将离散参数  使用连续参数  进行近似，那么优化目标可以化简成如下公式。其中 $\mathcal{P}_{\mathcal{D}}\left(\tilde{\boldsymbol{\theta}}^{d}\right)=\left\{\mathcal{P}_{\mathcal{D}_{i j}}\left(\tilde{\boldsymbol{\theta}}_{i j}^{d}\right), \forall i \in[N], j \in\left[K_{i}\right]\right\}$ ，代表  的整数映射。

上面的优化问题可以进一步改写成下面的优化问题，这里引入了一个整数变量 $\delta_{i j}$ ，并引入约束 $\tilde{\boldsymbol{\theta}}_{i j}^{d}=\boldsymbol{\delta}_{i j}$ 表明最终连续变量的优化结果要是一个整数值。这里将 $\tilde{\boldsymbol{\theta}}_{i j}^{d}$ 替换为 $\boldsymbol{\delta}_{i j}$ 是Trivial的，但这对于ADMM算法是至关重要的。

上面的四个约束条件中的前三个可以转化为下面的目标函数，其中如果 $x$ 是可行的参数，则 $I_{\mathcal{X}}(\mathrm{x})=0$ ，否则该值为无穷大。

随后，我们可以使用增广拉格朗日乘子法将上面的目标函数转化为下面的目标函数。值得一提的是，这里选用的是增广拉格朗日乘子法而非传统的拉格朗日乘子法，只有这样才能通过ADMM算法将优化问题进行分解。

优化求解
根据上面定义的目标函数，我们就可以基于ADMM将目标函数进行分解，分别优化 $\left\{\boldsymbol{\theta}^{c}, \widetilde{\boldsymbol{\theta}}^{d}\right\}$ ， $\boldsymbol{\delta}$ 和 $\boldsymbol{z}$ 这三项。

ADMM只是一个分解框架，并不是具体的优化算法。按照上面方法进行分解之后，在每个优化阶段，我们就可以基于领域知识选择合适的优化方法。
例如，首先我们可以优化连续变量  。即将目标函数中所有与连续变量有关的项提取出来进行优化。

此时，由于已经确定了模型架构方案  ，因此这个阶段优化的变量可以分为与模块  相关的变量和不相关的变量。对于不相关的变量，优化器只需要要求连续化后的整数变量  与  越接近越好。

而对于与模块  相关的变量，则需要同时考虑优化变量  与  越接近越好，同时优化最终AutoML目标 $\widetilde{f}\left(\mathrm{z}^{(t)},\left\{\theta^{c}, \widetilde{\theta}^{d}\right\} ; \mathcal{A}\right)$ 。

在这个阶段，我们可以使用任意的贝叶斯优化算法优化参数  。
接下来，我们优化离散变量  ，这里的目标是尽量让  和  接近。这里不需要优化算法，直接对  四舍五入即可。

在最后一个阶段，我们需要优化整数变量  ，这个变量决定了具体选择哪个机器学习或特征预处理模块，例如选择SVM或决策树作为最终的预测模型。对于这个组合优化问题，我们可以考虑采用MAB或演化算法进行求解。

黑盒约束
除了能够处理经典AutoML问题以外，ADMM-AutoML算法的一个优势是可以处理黑盒约束优化问题。这里，作者将黑盒不等式约束基于一个新引入的松弛变量  转化为等式约束。

基于上面的转化，新的AutoML目标函数可以写成下面的形式。这个目标函数与上面AutoML目标函数的区别是新增了两个约束项，即定义了松弛变量  的范围，同时将上面的等式约束加入到优化约束中。

对于加入了黑盒约束的AutoML问题，我们可以继续进行类似的ADMM分解。其实这里的逻辑和算法一的逻辑是基本一致的，唯一的区别就是因为连续变量  和模型架构方案  会影响最终的黑盒约束结果，因此在优化这两组变量和的时候额外考虑了黑盒约束项。

实现方式
经过上面的分析，很明显可以看出这篇文章提出的ADMM-AutoML算法实际上是一个框架，即使用ADMM思想对AutoML问题进行分解。至于具体的优化方式，我们可以针对每个问题自己选择最合适的策略。这里，作者选择使用贝叶斯优化算法优化连续参数  ，使用汤普森采样优化模型架构参数  。
实验结果

下面这张图展示了不同的AutoML算法的相对排序，从图中可以看出，TPOT算法在初始阶段反而比Random Search更差，从最终结果来看，混合了贝叶斯优化和汤普森采样的ADMM算法具有最好的性能。

下面这张图展示了基于约束的ADMM-AutoML算法（CST）优化公平性指标和模型预测延时相比无约束+post-hoc filter（UCST）更为高效。

此外，ADMM算法还有一个比较有趣的特性的是可以在不同阶段为每个子任务分配不同比例的资源。例如在初始阶段对于每一个机器学习系统  ，可以进行少量的连续参数优化，这样可以促进机器学习Pipeline的快速迭代。然后，我们可以逐渐增加连续参数  的迭代优化次数，以促进针对每个机器学习系统  的精细优化。这种动态调整策略被作者称称为Adaptive ADMM。从下面图中可以看出，这种自适应的策略可以同时保证在优化前期和优化后期都具有良好的效果。

此外，作者尝试了使用传统的贝叶斯优化算法将连续超参数  和模型架构  进行联合优化（JOPT）。从下面的结果来看，基于ADMM框架进行优化可以取得153倍的速度提升，从而证明了基于ADMM算法对AutoML问题进行分解的必要性。

		自动登录	找回密码
密码			立即注册

ADMM算法如何应用到AutoML问题上？

本帖子中包含更多资源

本帖子中包含更多资源