多目标优化
- 2021 年 4 月 6 日
- AI
多目标优化问题的定义和基本术语
为了方便理解上式，我们以单目标优化的线性回归为例，F(x)表示线性回归的function，即w1x1+w2x2+。。。。wnxn=y_pred，其中，x表示的是线性回归的权重系数W（注意这里的x并不是表示样本），gj(x)表示m个对W的不等式约束，hi(x)表示对W的等式约束。
这里简单回顾一下，凸优化的基础内容：
图片来源：学弱猹：凸优化|笔记整理（1）——引入，优化实例分析，凸集举例与相关性质
可以看到，多目标优化的公式形式和凸优化问题的公式形式基本是一样的。
两个简单的定义：
{x|gj (x) ≤ 0, j = 1, 2, …, m; and hi(x)=0, i = 1, 2, …, e} 可行解，即满足不等式和等式约束的的解构成的空间；
{F(x)|x ∈ X} 可达解，即x能够取到的解构成的解空间，显然可达解包含了可行解。
多目标优化最初源于经济平衡和福利理论、博弈理论和数学。因此，许多术语和基本思想都源于这些领域，下面是一些术语的定义：
Preferences
preference，指决策者对解空间中各个解的意见，简单来说，就是我们要实现什么样的目标，例如我们的目标是提高点击率，或者是降低信贷损失，指的是人（决策者）的定性的目标。
Preferences function
有了定性的目标之后，我们要想办法对定性的目标进行量化转化为定量的目标，例如我们要降低信贷损失，则目前来说简单的思路就是提高模型的分类准确率，但是提高分类准确率是和决策者的目标间接相关但不是直接相关的，因为不同用户的信贷额度可能不同，所以严格来说要实现这一目标，需要在Preferences function 引入信贷额度的数据。
Utility Function
在经济学的背景下，用Utility Function建模的效用代表个人或群体的满足程度（Mansfield 1985）。这与有用或有价值的通常含义略有不同。相反，在这种情况下，Utility Function强调决策者的满意度。在多目标优化方面，为每个目标定义了一个单独的效用函数，并表示该目标的相对重要性。效用函数U是各个效用函数的合并，并且是一个数学表达式，试图对决策者的偏好进行建模。它用于近似偏好函数，通常无法以数学形式将其表达出来。
简单来说，Utility Function可以近似认为是多目标中决定不同目标的权重的函数，但是人的偏好函数很难量化。
Global Criterion
Global Criterion是一个标量函数，在数学上将多个目标函数组合在一起；它不一定涉及偏好。
博弈论 Game theory
Stadler（1988）写道：“（解决多目标问题）的数学，数学和经济方法最终与1921年Borel创立博弈论相结合。”根据传统博弈论的解释，博弈是至少两个玩家之间有多种可能的策略或举动发生冲突或合作的情况。博弈论代表具有多个决策者的多目标优化，每个决策者控制某些变量（Vincent 1983）。如果所有参与者都合作，则结果与单个参与者充当多目标优化问题的决策者的结果相同。
多目标方法的主要分类之一是标量化方法和矢量优化方法。 给定对象函数的向量，可以简单地组合此向量的分量以形成单个标量对象函数，因此称为标量。 尽管很少有作者对此加以区分，但术语“向量优化”宽松地暗示着对每个目标函数的独立处理。 在本研究中讨论了这两种方法。
Pareto optimality
与单目标优化不同，多目标问题的解决方案通常没有单一的解决方案，通常有必要确定一组点，这些点都符合预定的定义以获得最佳值。 定义最佳点的主要概念是帕累托最优（Pareto 1906），关于帕累托最优解的资料就很多了，这里引用一些比较好理解的定义：
从定义上讲，帕累托最优描述的是一种资源最优化配置的状态。在帕累托最优的条件下，是没有办法在不让某一参与资源分配的一方利益受损的情况下，令另一方获得更大利益的。
试着用两个最简单的例子来说明这个问题。
举例1：
假设现在有两个人，甲和乙，分10块蛋糕，并且两个人都喜欢吃蛋糕。10块蛋糕无论在两个人之间如何分配，都是帕累托最优，因为你想让某一个人拥有更大利益的唯一办法是从另一个人手里拿走蛋糕，导致的结果是那个被拿走蛋糕的人利益受损。
举例2：
假设现在有两个人，甲和乙，分10块蛋糕10个包子。甲喜欢吃蛋糕而乙喜欢吃包子，而且甲讨厌吃包子，乙讨厌吃蛋糕（甲包子吃得越多越不开心，乙蛋糕吃得越多越不开心）。这种情形下，帕累托最优应当是：把10块蛋糕全部给甲，把10个包子全部给乙。因为任何其他的分配都会使得至少一个人手里拿着一些自己讨厌的东西，比如甲拥有10块蛋糕以及2个包子，乙拥有8个包子。这个时候，如果把2个包子从甲的手里转移到乙的手里，甲和乙都变得比原来更开心了，同时这样的转移并不会使得任何一方的利益受损。
如何通俗地解释“帕累托最优”（Pareto optimum）？
Definition 1. Pareto Optimal: A point, x∗ ∈ X, is Pareto optimal i there does not exist another point, x ∈ X, such that F(x) ≤ F(x∗), and Fi (x) < Fi (x∗) for at least one function.
举一个可能不是很严谨的例子，
我们可以假设多目标优化问题中，function1=查全率，function2=查准率，优化目标组合为f1 score，
无任何偏好，定义的变量w为阈值，阈值的约束为0~1，当w处于某个区间的时候，F1达到最大，假设w在0.4~0.42之间时，F1达到最大，则我们可以认为在0，4~0.42之间的阈值对应的是帕累托最优解。
通常来说，我们的多目标优化问题中可能还存在不等式和等式约束，在这些约束的条件下我们可能无法找到帕累托最优解，例如上面的例子，假设阈值的约束为[0.5,0.6]则我们无法找到最优解，因此有：
Weakly Pareto Optimal 弱帕累托最优解的定义：
针对于存在约束条件而无法得到帕累托最优解的问题，弱帕累托最优解认为在可行域(即满足约束条件的x)内如果存在某个解x，除了这个解x之外，没有任何一个其它的可行域解能够使得总的loss func最小，则我们认为这个解叫做弱帕累托最优解，帕累托最优解必然是弱帕累托最优解，但是弱帕累托最优解不一定是帕累托最优解。
Properly Pareto Optimal 适合的帕累托最优解的定义：
首先Properly Pareto Optimal必须先是Pareto Optimal，在这些Pareto Optimal 最优解的集合中，
我们希望每个loss func，Fi(x)和至少一个其它的loss func Fj(x)之间的增量是有界的，M表示一个有限的大于0的值，可以看到，上图的公式实际上就是表示由目标函数i的递减所导致的目标函数j的增量，我们希望这个增量是有限的，这种情况下满足上述条件的帕累托最优解成为适合的帕累托最优解，否则就不是适合的（感觉一般情况下应该都是有界的吧。。。）。
对于任何给定的问题，可能有无限数量的帕累托最优点构成帕累托最优集。因此，我们必须区分提供帕累托最优集的方法或该集合的某些部分，以及实际上寻求最终的一个解。
关于多目标和单目标的比较可以看这一篇有图有例子非常好理解：
木木松：多目标优化之帕累托最优
张大快：多目标优化总结：概念、算法和应用（文末附pdf下载）
这篇的总结也非常精彩
基本概念部分看完了，下面就总结一下多目标优化的一些方法思路：
1、加权求和，当所有多目标中所有目标函数的权重为1时为简单求和，这里的权重需要人工来定义，因此需要人类的先验知识；
2、主要目标法，人工根据多个目标的重要性定性排序，然后将最重要的k个子目标作为优化目标，其它子目标作为约束条件，例如我们要同时优化 A，B，C三个目标，其中A和B比较重要，C相对不重要，则我们可以界定目标C不得小于某个具体的值，从而使C目标成为一个约束条件；
3、依次求解法：和主要目标法类似，人工根据多个目标的重要性定性排序，然后按照重要性大小从大到小依次优化，简单来说，就是每次最优化一个目标，收敛之后，该目标的最优解成为新的约束条件，然后再优化下一个。
4、逼近目标法：逼近目标法是让决策者提出一个目标值，使得每个目标函数
都尽可能的逼近对应的目标值：
张大快：多目标优化总结：概念、算法和应用（文末附pdf下载）
同样，这里的目标需要人工来进行定义。
5、指数加权法
p是一个超参数，wi是人工定义的权重；
6、另一种指数形式的加权法
7、Multi-Task Learning Using Uncertainty to Weigh Losses for Scene Geometry and Semantics ，这篇论文还没看，大概思路是对每个任务的loss定义一个可以学习的权重，避免了人工先验的问题，让模型自动学习最优的权重和loss。
yaringal/multi-task-learning-example
具体代码可见，不过用过之后感觉有bug，就是原作者对可学习的权重没有进行范围约束，我实际使用的时候发现权重出现负数的问题，解决方法也比较简单，对可学习权重使用softmax进行归一化之后即可。
8、构建所有loss的Pareto，以一次训练的超低代价得到多种超参组合对应的结果。有代表性的工作参见Intel在2018年NeurIPS（对，就是那个刚改了名字的机器学习顶会）发表的
from
这篇也暂时没看过，具体实现在：
intel-isl/MultiObjectiveOptimization
找了一下，深度学习中关于多目标优化的方法可以在这篇论文中找到详细的描述，除了上面提到的方法7，8之外还有grad norm等方式，回头先看这篇好了。
凉爽的安迪：多任务学习优化（Optimization in Multi-task learning）
有大佬已经总结好了，感动！
上述的方法（除了最后一个没看过不知道具体什么操作）的思路基本是把多目标优化问题通过一些手段转化为单目标优化问题，然后使用凸优化例如梯度下降法这类的成熟的优化方法来进行求解， 这种思路的优点是简单，缺点可见：
多目标优化的意义到底是什么？目前关于多目标优化的研究难点和热点有哪些？
1单目标权值难以确定
多个目标之间必然存在矛盾，如何权衡这些目标，如果是用单目标加权的话，我们只能是调节权值大小，这样权值的确定其实是很难的，除了一顿实验没有什么太好的方法去确定，而多目标优化因为是直接求解多目标问题，就不存在确定权值的问题了。（将权重作为可学习的参数也是一个解决上述问题的思路）2各个目标之间量纲的不统一，可能会造成单目标优化问题鲁棒性差
各个目标之间量纲往往不统一，所以为了平衡各个目标之间的量纲，往往需要较大的权值来平衡量纲。例如目标函数
的量纲相对其它目标函数就很小，所以为了平衡各个目标，就需要将
设置的很大，而如果
3单目标加权求和只能逼近凸的帕累托面
加权求和的方式只能逼近帕累托前沿面为凸集的情况，如果多目标优化问题的帕累托面为非凸，则加权求和的方式就不能和原多目标优化问题等价，此时只有直接处理原多目标优化问题才能解决。4多目标优化问题的帕累托解集包含更多有效信息
多目标优化问题的求解是会得到一个帕累托解集的，这个解集里边包含着很多的信息，例如可以产生一些对模型的可解释，可以分析多个目标之间的相关性等等。去年的机器学习顶级会议NIPS2018有一篇文章就是巧妙的将多目标优化的概念引入到多任务学习中，就是利用了多目标优化问题的这个性质。具体可参看我之前的回答 NIPS 2018 有什么值得关注的亮点？（也就是前面提到的第八点）
多目标优化的局限性
说完了优势，那现在多目标优化的局限性是什么？为啥我们之前都是用单目标的比较多呢？原因比较简单，
1 单目标毕竟是比较简单的。
2 搞成多目标之后计算量要大大增加，这对于目前非常吃计算量的优化领域来说也很致命的弱点。看看多目标领域的顶级期刊的文章，搞个几千或者上万维的决策变量就是large-scale的了，可是在实际应用中经常会遇到百万，千万级别的优化问题。3多目标优化目前在处理2-5个目标还不错，如果目标数太多，其实目前也没啥太的好方法啦。
4在业界的应用问题中，业务方需要你给一个明确的答案，而不是在一堆帕累托解集里边去选。
如果是直接处理多目标优化的问题不进行单目标的转换，则基本上是另外一个故事了：
这里实现了许多常见的优化算法。
简单来说，多目标优化的优化算法，像进化、遗传、贝叶斯优化、粒子群等等这类优化算法，可以看作是和梯度下降法这种理论有保证的凸优化算法在一个level的，一般来说很多问题都是非凸的，例如nn的loss function就是一种典型的非凸函数，比如我们常见的超参数搜索，本身甚至都难以写出具体的目标函数，那么就可以考虑使用这类优化算法进行求解。
到这里就不再深入了。。。目前应用碰到的问题还是主要在传统的多目标转单目标方面，也就是怎么去处理 深度学习中多个loss之间的关系。
