多目標優化
- 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之間的關係。
