机器学习和计算机视觉的双层优化入门（个人简单记录，随时 ...

franciscochonge · 发表于 2022-4-22 17:17

1、简单说明

各位好，我也是新手，这个更多的是简单的概括，对各种详细知识点说的不多，可以让大家（也是让自己）对双层优化在各个方向的定位和应用有些简单的了解，可以快速入门，每个知识点的详细内容请根据本文关键词自行查找，如果我将来能够深入研究，可能会对这里的内容进行详细说明。
2、资料汇总

2.1、综述论文1

论文1英文名：Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyon
发布于2021年的TPAMI（这是视觉顶刊），中文名：从统一的角度研究机器学习和计算机视觉的双层优化：调查和超越。
这是大连理工大学的大牛写的一篇综述型论文，将机器学习和计算机视觉中的双层优化算法进行了重新定义、汇总分类、分析收敛性和时间空间复杂度，说明了超参数优化算法、多任务和元学习、网络架构搜索、生成对抗学习、深度强化学习等研究方向中使用双层优化的详细方法，创建了包含各种双层优化算法的函数库，想要对机器学习和计算机视觉中的双层优化有大概了解的可以看此论文。

论文链接
原文代码，2.2是对这个代码的readme的汉语版说明
论文作者对BLO（Bi-Level Optimization）双层优化的快速教程，也是此论文的快速说明，英文版，2.3是对这个的汉语版说明

2.2、汉语版：论文1代码readme

BOML：A Bilevel Optimization Library in Python for Meta Learning元学习的双层优化函数库python版本：

BOML是一个模块化的优化算法库，它将多个元学习算法统一成为一个通用的双层优化框架中（类似于opencv将图像处理算法汇总一样）。提供了各种流行的双层优化算法的代码接口，以便于快速构建元学习神经网络并测试其性能。
这里简要介绍了在少（小）样本分类中实现基于元初始化和基于元特征的方法。除了已经提出的算法外，还可以使用各种低层和高层策略的组合。

元学习：

元学习让机器通过学习可以自己组装一个初始化网络，这使得网络具有非常好的泛化性，并且面对新任务时表现非常好。即使提供少量的训练数据，它也具有良好的性能，这为不同的应用提供了各种解决方案，例如少样本学习问题。
我们提出了一种通用的双层优化范式，以统一不同类型的元学习方法，其数学形式可总结如下：

双层优化范式的数学形式

通用优化流程：

在这里，我们在图中说明了通用的优化过程和分层构建的策略：

通用的优化过程和分层构建的策略

可以在下面的示例中快速实现。

相关文档说明：

有关基本功能和构建网络流程的更多详细信息，请参阅我们的文档或项目主页。名为test_script的目录中的脚本设计了一些常用的网络结构，这里我们为特定的超参数提供推荐设置，以快速测试流行算法的性能，对于构建一般训练过程非常有用。

运行示例：

加载数据
import boml
from boml import utils
from test_script.script_helper import *

dataset = boml.load_data.meta_omniglot(
std_num_classes=args.classes,
examples_train=args.examples_train,
examples_test=args.examples_test,
)
# create instance of BOMLExperiment for ong single task
ex = boml.BOMLExperiment(dataset)为meta-learner和base-learner建立网络结构和定义参数
boml_ho = boml.BOMLOptimizer(
method=&#34;MetaInit&#34;, inner_method=&#34;Simple&#34;, outer_method=&#34;Simple&#34;
)
meta_learner = boml_ho.meta_learner(_input=ex.x, dataset=dataset, meta_model=&#34;V1&#34;)
ex.model = boml_ho.base_learner(_input=ex.x, meta_learner=meta_learner)定义LL（Lower-Level低层策略）的目标和计算流程
loss_inner = utils.cross_entropy(pred=ex.model.out, label=ex.y)
accuracy = utils.classification_acc(pred=ex.model.out, label=ex.y)
inner_grad = boml_ho.ll_problem(
inner_objective=loss_inner,
learning_rate=args.lr,
T=args.T,
experiment=ex,
var_list=ex.model.var_list,
)定义UL（Upper-Level高层策略）的目标和计算流程
loss_outer = utils.cross_entropy(pred=ex.model.re_forward(ex.x_).out, label=ex.y_) # loss function
boml_ho.ul_problem(
outer_objective=loss_outer,
meta_learning_rate=args.meta_lr,
inner_grad=inner_grad,
meta_param=tf.get_collection(boml.extension.GraphKeys.METAPARAMETERS),
)汇总上述定义的所有操作
# Only need to be called once after all the tasks are ready
boml_ho.aggregate_all()元训练的迭代（iteration）
#注意，元学习训练一般是先训练搜索网络架构（也就是训练架构参数），
#之后用搜索完成的网络重新训练模型参数，
#这里的训练是指第一步训练架构参数（也就是元参数或者称为与网络架构相关的超参数）
with tf.Session() as sess:
tf.global_variables_initializer().run(session=sess)
for itr in range(args.meta_train_iterations):
      # Generate the feed_dict for calling run() everytime
      train_batch = BatchQueueMock(
         dataset.train, 1, args.meta_batch_size, utils.get_rand_state(1)
      )
      tr_fd, v_fd = utils.feed_dict(train_batch.get_single_batch(), ex)
      # Meta training step
      boml_ho.run(tr_fd, v_fd)
      if itr % 100 == 0:
         print(sess.run(loss_inner, utils.merge_dicts(tr_fd, v_fd)))

包含的算法列表：

看原文吧：代码链接
2.3、汉语版：对BLO（Bi-Level Optimization）双层优化的快速教程，也是论文1的快速说明

介绍：

双层优化（BLO）起源于经济博弈论，后来被引入到优化中。双层优化能够处理具有两层结构的问题，两层结构对应两个子任务，其中一个子任务嵌套在另一个子任务中。标准的双层优化问题可以正式的写成如下形式：

双层优化问题

在机器学习和计算机视觉领域的科研方向（或者称为科研问题）中，如超参数优化、多任务和元学习、神经结构搜索、对抗性学习和深度强化学习等，虽然看起来区别很大，但是都可以用双层优化将他们统一成为一个科研方向，也就是说这些算法可以看作是双层优化算法，这正是论文Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyond的核心思想。此外，此文还创建了一个基于最佳响应的单级重构（best-response-based single-level reformulation），并创建了一个统一的算法框架，以理解和制定主流的基于梯度的双层优化方法，涵盖从基本的自动微分方案到各种加速、简化、扩展及其收敛性和复杂性等。我们总结了主流的基于梯度的双层优化算法，并在论文代码中说明了这些算法之间的内在关系。此文还说明了统一的算法框架对创建新的双层优化算法可以起到极其巨大的作用，并指出了未来研究的一些有希望的方向。

对各种基于梯度的双层优化算法的内在关系的解释图

论文说明总结了我们的相关进展和现有作品的参考资料，以便于快速了解基于梯度的双层优化的发展情况。此外，论文说明还提供了本次调查中讨论的重要论文列表、相应的代码以及有关双层优化的其他资源。论文说明将继续维护该网站，以促进双层优化领域的研究。

相关工作：
- 论文：

请参考英文原文A Quick Tutorial on Bi-level Optimization，包含代码论文链接

双层优化算法代码工具包:

论文代码：一个基于Tensorflow1.0的模块化的双层优化算法库，包含多个相关的机器学习算法。现在集成了最近提出的算法和更兼容的应用程序，并发布了Pytorch版本（这个我看了一下，截止到2022年4月13日，代码还是没有pytorch版本?_?，也就是还没有进一步更新代码库），这个代码库中有已经整合的算法的列表可以看看。
论文说明：这里列出了即将整合的新的算法列表。

在机器学习和计算机视觉中，现有的双层优化算法分类：

同一篇论文算法可以看作是很多类别，也就是不同算法类别之间是有一定联系的，所以不可能彻底分开，但是可以帮助看清楚目前相关算法的发展情况。目前超参数可以分为两类，一类是网络层数、网络宽度等，这一类超参数是双层优化算法可以优化的，一般称为元特征或者元参数，一类是目前双层优化没有优化的超参数，例如学习率lr等。
基于梯度的优化算法：论文说明
超参数优化算法：论文说明
多任务和元学习：论文说明
网络架构搜索：论文说明
生成对抗学习：论文说明
深度强化学习：论文说明
其他分类：论文说明
2.4、网络架构搜索论文发表情况分析

东北大学大牛的论文列表和分析图
2.5、其他

各种搜索查找和询问，哈哈哈哈。
3、词汇说明

w/：with的缩写
w/o：without的缩写
UL（Upper-Level）：双层优化问题的上层问题，也称为外层问题或者高层问题或者leader问题，解决问题的策略称为高层策略。
LL（Lower-Level）：双层优化问题的下层问题，也称为内层问题或者低层问题或者follower问题，解决问题的策略称为低层策略。
BP（best response）：最佳响应，其实是为了方便书写和理解双层优化，将LL问题的解写成映射的形式y(x)。
EGBR（Explicit Gradient for Best-Response）和IGBR（Implicit Gradient for Best-Response）：最佳响应的显式梯度法，显式就是自变量和因变量在等式两边，隐式就是自变量和因变量在等式同一边另一边是常数。如图。

显式和隐式

最优化问题：最优化是工程概念，与数学中的普通的优化概念是一样的。
解析法：直接利用公式将解析解求出来的算法。
启发式算法：不能直接求解，而是通过定向迭代一步一步解出来的算法。
NP难问题：学习中!_！。
变分不等式：直观理解就是将等式变成（变分）不等式。
MILP：mixed integer linear programming ，混合整数线性规划
MIQP：mixed integer quadratic programming，混合整数二次规划
基于元初始化方法（meta-initialization-based）和基于元特征方法（meta-feature-based）：有一个研究方向叫多任务和元学习，就是用模型完成多个任务，这篇论文根据训练之后模型的状态将方法分类。如图1：
- （a）基于元初始化方法（meta-initialization-based）：是网络训练结束后，针对不同任务只有最后一层或者几层网络（也就是论文中说的logistic regression layer逻辑回归层）是不一样的。
- （b）基于元特征方法（meta-feature-based）：训练之前是统一的网络，训练结束后针对不同任务的网络的每一层都不一样（注意深红色框线处箭头的理解）。

1、meta-initialization-based and meta-feature-based

feasible [fizbl]：可行的
BLO（bi-level optimization）：双层优化，与BLP（bi-level programming）双层规划对应，BLP是建立双层问题，BLO是求解BLP的策略、方法，不明白双层相关定义的可以查询关键词双层优化、双层规划模型、双层规划问题、双层优化问题等。
UL（Upper-Level）：双层优化问题的上层问题，也称为外层问题或者高层问题，解决问题的策略称为高层策略。
LL（Lower-Level）：双层优化问题的下层问题，也称为内层问题或者低层问题，解决问题的策略称为低层策略。
denote [dnt]：表示
nonconvexity：非凸性
differentiability：可微性
aggravate [ɡrvet]：加重，加剧。
Equilibrium Constraints：平衡约束
inequality [nkwɑlti]：不等式
Learning and Vision：机器学习和计算机视觉的简写方式。
reformulation [rifrmjulen]：重构，再形成
mapping：映射
元学习meta learning：平时的网络一般都是人工设计网络之后训练使用，元学习网络是让机器自己组装网络之后训练使用，元学习比普通网络算法需要多训练的超参数被称为元参数，元参数一般是网络层数、网络层的操作种类（卷积、池化等）、网络层之间的连接等。
few-shot learning少（小）样本学习：就是字面意思，训练数据很少的任务。
基础研究和应用研究：以双层优化为例，基础研究是对双层优化算法本身进行改进，应用研究是考虑如何让双层优化在GAN等不同的研究方向中性能更好。

4、双层优化正文

4.1、双层问题

双层规划问题也称为双层优化问题，直观理解就是一个问题套在另一个问题中，是最优化问题的一个特例，优化问题有两种分类方法。第一种分类方法是根据优化层数分类：单层优化、双层优化、多层优化。第二种分类方法是根据优化问题本身的性质分类：线性规划问题、非线性规划问题、混合整数规划问题、凸优化问题、混合整数线性规划问题、混合整数二次规划问题等。
目前无论是机器学习和计算机视觉还是其他工程领域，双层优化用的是最多的，因为生活中遇到的很多问题都是嵌套关系，例如中央和地方、公司和子公司等，而且多层优化问题可以理解成多个双层优化问题的复合。
双层规划问题至今仍然是个非常难解决的问题，已经有论文证明，即便是双层规划中最简单的问题都是NP难问题。
4.2、双层算法

双层优化算法分类

根据问题能否直接求解，双层优化算法可以分为两种：解析法、启发式算法。
解析法：大部分是用KKT、对偶、罚函数等方式将双层规划转化成单层，然后针对单层求解。
启发式算法（也包括类启发式算法，是指解析法和启发式算法的结合）：特点是不能直接求出结果而是有方向的迭代，但是启发式算法很有可能得到的不是最优解，一定要对结果进行论证。除搜索法外，启发式算法中，还有包括active-set，trust region等方法，更有特色，也各有前提，需要实际问题实际分析。函数和约束都可导的话可以结合sqp将原问题近似为二次问题，然后进一求解。用分段线性拟合，将原问题转化成线性问题。后两种适用性还可以但是收敛性特征却很不明显导致迭代次数较大。
如果要直接用的话可以搜索GAMES建模软件等，看看是否有满足条件的现成的solver，利用其中的solver可以直接求解。除非遇到变分不等式将双层问题转化成单层极其复杂的问题，否则一般都是转化成单层求解。

机器学习和计算机视觉的双层优化算法说明

机器学习和计算机视觉中听到较多的词就是神经网络训练，这个其实就是启发式算法，神经网络的启发式双层优化算法有很多种类，例如贝叶斯算法、强化学习方法、基于梯度的方法，其中基于梯度的BLO算法数量最多、性能最好、速度最快，所以这里以基于梯度的双层优化算法为主进行说明，并且用来对比性能好坏的应用方向超过一半都是用图像分类，其次是自然语言处理的语言模型。

图1

图2

图1和图2是论文Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyond中提到的用来概括所有基于梯度的双层优化算法的汇总图，接下来基于梯度的双层优化算法的介绍就是对这两张图片中的一些缩写进行简单说明。
UL和LL问题中的函数在神经网络中对应的其实就是损失函数。
双层优化一般是求出LL的解y，之后将y带入到UL中继续求解，但是LL的解可能是单解也可能是多解，如果LL是单解，则LL满足LLS（lower level singleton）条件，也就是w/ LLS，如果LL是多解则LL不满足LLS条件，也就是w/o LLS。w/o LLS还分为两种情况，当约束条件能够对多解进行限制，使得最符合条件的解只有一个，那么就说这个BLO是optimistic (strong) formulation（非常棒的形式）；如果无论如何都不能找出多解中唯一一个最好的解，那么就说这个BLO问题是pessimistic (weak) formulation（非常惨的形式）。
图1：3是将LL问题变成BR形式、方便书写和观察，5是将双层优化问题转换成单层优化问题的新方法，7和9分别是6和8的具体算法举例，10是计算4（UL问题）和5的梯度，6、8都是用来计算LL梯度的算法。

算法收敛性、时间空间复杂度

很多与深度学习相关的双层优化算法没有讨论收敛性，只是用实际效果对比说明自己的算法很强，论文Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyond则是对各个算法的收敛性、时间空间复杂度进行了重点说明和计算，具体还在学习中?_?
4.3、目前问题

非线性是双层规划中最难的问题，目前许多方法也颇受争议。
无法判断是否凸，以及非凸时候很难解决。
混合整数双层规划问题，0-1条件使得这一类问题无法直接利用KKT条件变成单层问题。
针对不同种类的问题，并没有统一的双层优化算法能够对所有问题直接求解。
还有哪些双层优化算法可以应用到机器学习和计算机视觉中。
双层优化算法的理论突破：有些算法是无法证明收敛的，需要突破性的证明。
计算加速技巧：现在虽然已经有些方向使用双层优化算法了，但是应用到类似于目标检测的双层优化算法的计算速度真的很感人啊！还是需要更好的加速技巧。
应用到更多的领域中：例如知识蒸馏、自监督、tranformer、移动端等。
混合优化，既有离散空间，又有连续空间。
有些双层优化算法是将两层的问题分开求解，这使得双层问题的两个解的联系不够紧密。
收敛性和稳定性的证明和约束条件。
离散双层优化算法
4.4、应用领域

生活中的问题可以分类成单层问题、双层问题和多层问题，最多的其实是双层问题，因为生活中很多问题都是嵌套的关系，也就是问题之间都是有一定的关联性的，单层问题不会考虑不同单层问题之间的联系，能考虑问题之间联系的是双层和多层问题，而多层问题可以看作是多个双层问题的组合，所以最接近生活本质的问题是双层问题。
优化算法本身的算法包含离散和连续两个内容，目前双层优化算法几乎都是连续的算法，这些算法的关键词就是梯度和可微，所以在搜索各个研究方向过程中可以尝试带上梯度关键词，可能会有惊喜，哈哈哈哈哈！
个人不太了解的：

交通OD矩阵（origin-destination matrix）
多任务和元学习
超参数优化
强化学习

个人还算比较了解的：

网络架构搜索与双层优化：网络架构搜索在训练过程包括优化模型参数和优化架构参数两个部分，两者是嵌套关系，刚好符合双层优化的定义。是最能体现双层优化的直接应用之一。能够结合双层优化的关键词是基于梯度的网络架构搜索
对抗学习：对抗学习的训练过程包括对抗攻击和对抗防御两个部分，两者同样是嵌套关系，符合双层优化定义。对抗学习的算法几乎都是基于梯度的。
GAN：生成对抗网络，训练过程包括训练生成器和训练判别器两个部分，两者是嵌套关系，刚好符合双层优化的定义。是最能体现双层优化的直接应用之一。

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

机器学习和计算机视觉的双层优化入门（个人简单记录，随时 ...

本帖子中包含更多资源