設(shè)計(jì)素材網(wǎng)站照片逆冬黑帽seo培訓(xùn)
分享者:唐博
編者按:?
這篇文章我想要寫已經(jīng)很久了,畢竟“端對(duì)端預(yù)測后優(yōu)化”(End-to-End Predict-then-Optimize)正是我讀博期間的主要研究方向,但我又一直遲遲沒能下筆。想說自己雜事纏身(實(shí)際是重度拖延癥晚期的緣故),更主要的原因恐怕是我對(duì)這一領(lǐng)域理解依然尚淺,尤其我希望以綜述的形式,為讀者提供詳盡的介紹。然而,這篇文章并不能稱為一篇綜述,原因有二:一方面,我雖然進(jìn)行相關(guān)的研究,但還無法自稱為專家;另一方面,"端對(duì)端預(yù)測后優(yōu)化"還處于起步階段,有很大的探索空間,尚有無窮可能。因此,此時(shí)編寫綜述可能為時(shí)尚早。因此,我選擇用這篇文章拋磚引玉,旨在引發(fā)關(guān)于這個(gè)領(lǐng)域的進(jìn)一步探討和思考。
1. 引言
運(yùn)籌學(xué)和統(tǒng)計(jì)學(xué)/數(shù)據(jù)科學(xué)/機(jī)器學(xué)習(xí)的緊密關(guān)系由來已久。機(jī)器學(xué)習(xí)通過挖掘數(shù)據(jù),預(yù)測未知或不確定的信息,一旦得到預(yù)測結(jié)果,常常需要進(jìn)一步的決策行動(dòng)來獲取收益。而運(yùn)籌學(xué)作為建模求解最優(yōu)化問題的工具,盡管可以(相對(duì))高效地找到最優(yōu)解,但一大限制是通常需要參數(shù)(無論是本身還是其分布)的確定性,無法充分利用數(shù)據(jù)。
本文就是要討論數(shù)據(jù)驅(qū)動(dòng)下,帶有不確定參數(shù)的優(yōu)化問題。這種問題通常通過“預(yù)測后優(yōu)化”的范式來解決。這一問題在現(xiàn)實(shí)生產(chǎn)生活中有著深遠(yuǎn)的意義。舉例來說,車輛路徑規(guī)劃中,由于交通狀況的不斷變化,在每段道路的行駛時(shí)間是不確定的;電網(wǎng)調(diào)度中,不同地區(qū)的電力負(fù)荷也會(huì)隨時(shí)間發(fā)生變化;投資組合中,金融資產(chǎn)的收益率會(huì)受到市場波動(dòng)的影響。以上這些情況都涉及到優(yōu)化模型參數(shù)的不確定性,但是,我們可以利用時(shí)間、天氣、金融因素等特征,預(yù)測這些不確定的參數(shù),從而進(jìn)行最優(yōu)決策。
此外,本文也會(huì)介紹一個(gè)端對(duì)端預(yù)測后優(yōu)化的開源框架PyEPO (https://github.com/khalil-research/PyEPO)。PyEPO基于PyTorch, 主要針對(duì)(但不限于)線性規(guī)劃(LP)和整數(shù)線性規(guī)劃(ILP),集成了文中提到的多種算法,并提供了Gurobi、Pyomo等優(yōu)化建模工具的API。PyEPO可以作為PyTorch的autograd模塊進(jìn)行深度學(xué)習(xí)的訓(xùn)練和測試,使用起來簡潔明了。這個(gè)框架的設(shè)計(jì)目標(biāo)是為廣大學(xué)界和業(yè)界用戶提供便捷的工具,幫助大家更好地理解和應(yīng)用端對(duì)端預(yù)測后優(yōu)化方法。
2. 問題描述和符號(hào)
首先,請(qǐng)各位讀者放心,本文并不打算深入挖掘端對(duì)端預(yù)測后優(yōu)化背后的數(shù)學(xué)推導(dǎo),而是致力于提供一些直觀的理解。
我們以一個(gè)簡單的線性優(yōu)化問題為例:
max ? w 1 , w 2 c 1 w 1 + c 2 w 2 s . t . w 1 + w 2 ≤ 1 w 1 , w 2 ≥ 0 \begin{aligned} \underset{w_1,w_2}{\max} \quad & c_1 w_1+c_2 w_2 \\ s.t. \quad & w_1 + w_2 \leq 1 \\ & w_1, w_2 \geq 0 \end{aligned} w1?,w2?max?s.t.?c1?w1?+c2?w2?w1?+w2?≤1w1?,w2?≥0?
在這里, w = ( w 1 , w 2 ) \mathbf{w} = (w_1,w_2) w=(w1?,w2?)代表的是決策變量, W = { w 1 + w 2 ≤ 1 , w 1 , w 2 ≥ 0 } \mathbf{W} = \lbrace w_1 + w_2 ≤ 1,w_1, w_2 ≥ 0 \rbrace W={w1?+w2?≤1,w1?,w2?≥0}定義了可行域,而 c = ( c 1 , c 2 ) \mathbf{c}=(c_1,c_2) c=(c1?,c2?)就是我們不確定的成本向量。
給定成本向量 c \mathbf{c} c,由于退化問題的存在,優(yōu)化問題可能得到多個(gè)最優(yōu)解,但可以假定使用某種特定的求解器(如Gurobi)時(shí),只返回唯一一個(gè)最優(yōu)解 w ? ( c ) \mathbf{w}^* (\mathbf{c}) w?(c)。
有一組數(shù)據(jù) D = { ( x 1 , c 1 ) , ( x 2 , c 2 ) , ? , ( x n , c n ) } \mathbf{D} = \lbrace(\mathbf{x}^1,\mathbf{c}^1), (\mathbf{x}^2,\mathbf{c}^2), ?, (\mathbf{x}^n,\mathbf{c}^n)\rbrace D={(x1,c1),(x2,c2),?,(xn,cn)},其中 x \mathbf{x} x為數(shù)據(jù)特征,我們可以利用機(jī)器學(xué)習(xí)模型 g ( x , θ ) \mathbf{g}(\mathbf{x},\boldsymbol{\theta}) g(x,θ)來最小化某個(gè)損失函數(shù) l ( g ( x , θ ) , c ) l(\mathbf{g}(\mathbf{x},\boldsymbol{\theta}),\mathbf{c}) l(g(x,θ),c)。其中, θ \boldsymbol{\theta} θ是模型 g ( x , θ ) \mathbf{g}(\mathbf{x},\boldsymbol{\theta}) g(x,θ)的參數(shù),會(huì)在訓(xùn)練過程中不斷更新,而 c ^ = g ( x , θ ) \hat{\mathbf{c}} = \mathbf{g}(\mathbf{x},\boldsymbol{\theta}) c^=g(x,θ)則是成本向量 c \mathbf{c} c的預(yù)測值。由此我們可以利用數(shù)據(jù)驅(qū)動(dòng)的方式來預(yù)測不確定的參數(shù),幫助實(shí)現(xiàn)優(yōu)化決策。
3. 什么是端對(duì)端預(yù)測后優(yōu)化?
在回答這個(gè)問題之前,我們首先需要理解端對(duì)端學(xué)習(xí)(End-to-End Learning)的理念。端對(duì)端的這個(gè)“端”,指的是輸入端和輸出端。相比于傳統(tǒng)的分步驟方式,它并不依賴于中間過程的手動(dòng)特征工程或者人為設(shè)計(jì)的步驟,而直接構(gòu)建從輸入到輸出的映射,以一種更直接和自動(dòng)的方式解決問題。這種簡化不僅減輕了手動(dòng)特征工程的負(fù)擔(dān),而且通過學(xué)習(xí)直接的映射,減少了對(duì)中間結(jié)果的依賴,有可能發(fā)現(xiàn)傳統(tǒng)方法難以發(fā)現(xiàn)的模式,從而提高整體的性能。端對(duì)端學(xué)習(xí)作為一個(gè)整體,使得整個(gè)系統(tǒng)變得更簡潔,有利于處理復(fù)雜和高維度的問題。
[圖片]
對(duì)于端對(duì)端預(yù)測后優(yōu)化,我們?cè)谟?xùn)練機(jī)器學(xué)習(xí)模型 g ( x , θ ) \mathbf{g}(\mathbf{x},\boldsymbol{\theta}) g(x,θ)的過程中,模型預(yù)測了成本向量 c ^ = g ( x , θ ) \hat{\mathbf{c}} = \mathbf{g}(\mathbf{x},\boldsymbol{\theta}) c^=g(x,θ),然后通過求解器得到最優(yōu)解 w ? ( c ^ ) = min ? w ∈ W c ^ ? w \mathbf{w}^* (\hat{\mathbf{c}}) = \underset{\mathbf{w} \in \mathbf{W}}{\min} \hat{\mathbf{c}}^{\top} \mathbf{w} w?(c^)=w∈Wmin?c^?w,并計(jì)算損失函數(shù) l ( c ^ , c ) l(\hat{\mathbf{c}}, \mathbf{c}) l(c^,c)來直接衡量決策損失。
借助鏈?zhǔn)椒▌t,我們能夠計(jì)算出模型參數(shù) θ \boldsymbol{\theta} θ相對(duì)于損失函數(shù) l ( c ^ , c ) l(\hat{\mathbf{c}}, \mathbf{c}) l(c^,c)的梯度,用于更新模型參數(shù):
? l ( c ^ , c ) ? θ = ? l ( c ^ , c ) ? c ^ ? c ^ ? θ = ? l ( c ^ , c ) ? w ? ( c ^ ) ? w ? ( c ^ ) ? c ^ ? c ^ ? θ \begin{aligned} \frac{\partial l(\hat{\mathbf{c}}, \mathbf{c})}{\partial \boldsymbol{\theta}} & = \frac{\partial l(\hat{\mathbf{c}}, \mathbf{c})}{\partial \hat{\mathbf{c}}} \frac{\partial \hat{\mathbf{c}}}{\partial \boldsymbol{\theta}} \\ & = \frac{\partial l(\hat{\mathbf{c}}, \mathbf{c})}{\partial \mathbf{w}^* (\hat{\mathbf{c}})} \frac{\partial \mathbf{w}^* (\hat{\mathbf{c}})}{\partial \hat{\mathbf{c}}} \frac{\partial \hat{\mathbf{c}}}{\partial \boldsymbol{\theta}} \end{aligned} ?θ?l(c^,c)??=?c^?l(c^,c)??θ?c^?=?w?(c^)?l(c^,c)??c^?w?(c^)??θ?c^??
顯然,對(duì)于依賴于鏈?zhǔn)椒▌t進(jìn)行反向傳播的模型(如神經(jīng)網(wǎng)絡(luò)),關(guān)鍵部分是計(jì)算求解過程的梯度 ? w ? ( c ^ ) ? c ^ \frac{\partial \mathbf{w}^* (\hat{\mathbf{c}})}{\partial \hat{\mathbf{c}}} ?c^?w?(c^)?。端對(duì)端預(yù)測后優(yōu)化的各類算法幾乎都是在此基礎(chǔ)上展開的。然而,在此,我們先不深入討論這些算法,因?yàn)槲覀兾覀儽仨毾然卮鹨粋€(gè)更為重要,也是更致命的問題:
4. 為什么要使用端對(duì)端預(yù)測后優(yōu)化?
4.1 關(guān)于兩階段的預(yù)測后優(yōu)化
毫無疑問,采用兩階段的預(yù)測后優(yōu)化,即將機(jī)器學(xué)習(xí)預(yù)測模型 g ( x , θ ) \mathbf{g}(\mathbf{x},\boldsymbol{\theta}) g(x,θ)和優(yōu)化求解器 w ? ( c ) \mathbf{w}^* (\mathbf{c}) w?(c)獨(dú)立使用,看似是一個(gè)更為自然、直接的做法。此方法的預(yù)測任務(wù)中,我們最小化成本向量預(yù)測值 c ^ = g ( x , θ ) \hat{\mathbf{c}} = \mathbf{g}(\mathbf{x},\boldsymbol{\theta}) c^=g(x,θ)和真實(shí)值 c \mathbf{c} c之間的預(yù)測誤差,如均方誤差 l MSE ( c ^ , c ) = ∥ c ^ ? c ∥ 2 l_{\text{MSE}} (\hat{\mathbf{c}},\mathbf{c}) = {\lVert \hat{\mathbf{c}}-\mathbf{c} \rVert}^2 lMSE?(c^,c)=∥c^?c∥2。熟悉機(jī)器學(xué)習(xí)的讀者可能會(huì)發(fā)現(xiàn),這實(shí)際上是一項(xiàng)非常經(jīng)典的回歸任務(wù),對(duì)應(yīng)的模型和算法已經(jīng)相當(dāng)成熟。而在決策任務(wù)中,一旦給定預(yù)測參數(shù) c ^ \hat{\mathbf{c}} c^,現(xiàn)代求解器可以將問題視作確定性優(yōu)化直接求解。既然預(yù)測任務(wù)和決策任務(wù)都有成熟的方案,那么為什么我們還要嘗試將它們結(jié)合在一起?
文獻(xiàn)中的解釋——“與直接考慮決策誤差相比,基于預(yù)測誤差訓(xùn)練預(yù)測模型會(huì)導(dǎo)致更糟糕的決策?!庇萌嗽拋碚f就是:像 l MSE ( c ^ , c ) l_{\text{MSE}} (\hat{\mathbf{c}},\mathbf{c}) lMSE?(c^,c)這樣的預(yù)測誤差,不能準(zhǔn)確地衡量決策的質(zhì)量。
在日常生活中,人們只關(guān)心決策的好壞,而不是各項(xiàng)指標(biāo)預(yù)測的準(zhǔn)確度。正如我們驅(qū)車趕往目的地時(shí),只關(guān)心自己是否選中捷徑,而無須精確預(yù)測每段可能經(jīng)過的路段所耗費(fèi)的時(shí)間。
讓我們回到前文提到的線性優(yōu)化問題:假設(shè)實(shí)際成本向量為 c = ( 0 , 1 ) \mathbf{c}=(0,1) c=(0,1),最優(yōu)解為 w ? ( c ) = ( 0 , 1 ) \mathbf{w}^* (\mathbf{c}) = (0,1) w?(c)=(0,1)。當(dāng)我們將成本向量預(yù)測為 c ^ = ( 1 , 0 ) \hat{\mathbf{c}} = (1,0) c^=(1,0),其最優(yōu)解為 w ? ( c ^ ) = ( 1 , 0 ) \mathbf{w}^* (\hat{\mathbf{c}}) = (1,0) w?(c^)=(1,0),預(yù)測的均方誤差 l MSE ( c ^ , c ) = 2 l_{\text{MSE}} (\hat{\mathbf{c}},\mathbf{c}) = 2 lMSE?(c^,c)=2;當(dāng)我們將成本向量預(yù)測為 c ^ = ( 0 , 3 ) \hat{\mathbf{c}} = (0,3) c^=(0,3),其最優(yōu)解為 w ? ( c ^ ) = ( 0 , 1 ) \mathbf{w}^* (\hat{\mathbf{c}}) = (0,1) w?(c^)=(0,1),預(yù)測的均方誤差 l MSE ( c ^ , c ) = 4 l_{\text{MSE}} (\hat{\mathbf{c}},\mathbf{c}) = 4 lMSE?(c^,c)=4。
這個(gè)例子揭示了一個(gè)有趣的現(xiàn)象:后者雖然在預(yù)測誤差上比前者大,但在決策上卻是最優(yōu)的。
因此,即使預(yù)測模型表現(xiàn)出了較大的誤差,但只要預(yù)測的成本向量能引導(dǎo)我們做出正確的決策,這個(gè)預(yù)測模型就是有效的。這就是為什么我們需要考慮端對(duì)端預(yù)測后優(yōu)化,我們希望訓(xùn)練出的模型能夠引導(dǎo)我們做出最優(yōu)的決策,而不必預(yù)測出精確的成本向量。
那么,如果預(yù)測模型的預(yù)測結(jié)果足夠精確,那是不是可以摒棄使用端對(duì)端方法了呢?答案是肯定的。然而,不要忘記統(tǒng)計(jì)學(xué)家George E.P. Box有句名言: “All models are wrong, but some are useful.”
4.2 關(guān)于模仿學(xué)習(xí)
既然端對(duì)端方法展現(xiàn)了足夠的優(yōu)勢,那我們?yōu)槭裁床环粮みM(jìn)一點(diǎn),采用模仿學(xué)習(xí)(Imitation Learning),把(最優(yōu))決策行為 w ? ( c ) \mathbf{w}^* (\mathbf{c}) w?(c)作為標(biāo)簽,省去了中間的求解過程,直接訓(xùn)練模型 w ^ ? = g ( x , θ ) \hat{\mathbf{w}}^* = \mathbf{g}(\mathbf{x},\boldsymbol{\theta}) w^?=g(x,θ)預(yù)測最優(yōu)解呢?
毫無疑問,模仿學(xué)習(xí)在計(jì)算效率上具有顯著優(yōu)勢,因?yàn)樗?guī)避了計(jì)算效率的主要瓶頸:優(yōu)化求解。
然而,其局限性也很明顯。盡管研究人員已經(jīng)做出了許多嘗試,比如Kervadec等人的“Constrained deep networks: Lagrangian optimization via log-barrier extensions” [8],但目前的預(yù)測模型,無論是線性回歸、決策樹、還是神經(jīng)網(wǎng)絡(luò),在處理帶有硬約束(Hard Constraints)的問題上仍存在難度。因此,模仿學(xué)習(xí)的預(yù)測結(jié)果常常面臨可行性問題,特別是對(duì)于高維度、有復(fù)雜約束的優(yōu)化問題。
5. 如何進(jìn)行端對(duì)端預(yù)測后優(yōu)化?
開篇名義,這個(gè)章節(jié)將會(huì)討論端對(duì)端預(yù)測后優(yōu)化的若干方法,這些方法適用的優(yōu)化問題有所差異,但主要集中在成本向量 c \mathbf{c} c未知、有線性目標(biāo)函數(shù)的問題上。需要明確的是,這里強(qiáng)調(diào)的是目標(biāo)函數(shù)的線性,并不意味著約束條件也必須是線性的。例如,在SPO+的相關(guān)論文中 [1],作者們探討了具有二次約束的投資組合均值-方差模型。此外,對(duì)比、排序方法和損失函數(shù)近似法甚至對(duì)優(yōu)化問題的形式幾乎沒有特定要求。
盡管也存在基于決策樹的模型SPO Tree [9],大部分方法還是依賴梯度下降更新參數(shù)。之前提到,端對(duì)端學(xué)習(xí)的關(guān)鍵是計(jì)算求解過程的梯度 ? w ? ( c ^ ) ? c ^ \frac{\partial \mathbf{w}^* (\hat{\mathbf{c}})}{\partial \hat{\mathbf{c}}} ?c^?w?(c^)?。然而,傳統(tǒng)的優(yōu)化求解器和算法往往并未提供梯度信息。
更壞的消息是:線性規(guī)劃、整數(shù)線性規(guī)劃等具有線性目標(biāo)函數(shù)的問題,其最優(yōu)解 w ? ( c ) \mathbf{w}^* (\mathbf{c}) w?(c)作為成本向量 c \mathbf{c} c的函數(shù),是一個(gè)分片常數(shù)函數(shù)(Piecewise Constant Function),它的一階導(dǎo)數(shù)要么為0,要么不存在。熟悉線性規(guī)劃敏感性分析的話,就會(huì)知道成本向量系數(shù) c \mathbf{c} c的元素發(fā)生變化時(shí),最優(yōu)解 w ? ( c ) \mathbf{w}^* (\mathbf{c}) w?(c)要么不發(fā)生改變,要么會(huì)從可行域的一個(gè)極點(diǎn)跳到另一個(gè)極點(diǎn)。我們依然以線性規(guī)劃 max ? w 1 , w 2 { c 1 w 1 + c 2 w 2 : w 1 + w 2 ≤ 1 , w 1 , w 2 ≥ 0 } \underset{w_1,w_2}{\max} \lbrace c_1 w_1 + c_2 w_2: w_1 + w_2 ≤ 1,w_1, w_2 ≥ 0 \rbrace w1?,w2?max?{c1?w1?+c2?w2?:w1?+w2?≤1,w1?,w2?≥0}為例,如圖:
既然梯度幾乎處處為0,梯度下降法似乎無法實(shí)施。然而,科研的魅力正是將不可能變?yōu)榭赡?。面?duì)這一挑戰(zhàn),研究者們提出了多種解決策略:一類是尋找替代的梯度信息,用以更新模型參數(shù);另一類索性重新設(shè)計(jì)一個(gè)(有非0梯度的)替代損失函數(shù)。這兩類思路基本囊括了基于梯度的端對(duì)端預(yù)測后優(yōu)化算法:
5.1 基于KKT條件的隱函數(shù)求導(dǎo)
Amos和Kolter提出“OptNet” [10],通過求解KKT條件的偏微分矩陣線性方程組來計(jì)算求解器反向傳播的梯度。為了克服線性規(guī)劃中無法得到非0梯度的問題,Wilder等人 [11] 在線性目標(biāo)函數(shù)中加入了一個(gè)微小的二次項(xiàng)?;谶@類方法,后續(xù)的研究者展開了多方面的探索。例如,引入割平面法(Cutting-Plane Method)以處理整數(shù)問題 [12],或使用障礙函數(shù)來替代拉格朗日罰函數(shù) [13]。
值得一提的是,這類方法不僅能計(jì)算出目標(biāo)函數(shù)成本向量的梯度,而且能夠得到約束條件中參數(shù)的梯度信息。
5.2 SPO+
不同于KKT方法,Elmachtoub和Grigas [1] 為目標(biāo)函數(shù)是線性( c ? w \mathbf{c}^{\top} \mathbf{w} c?w)的決策誤差找到了一個(gè)凸且可導(dǎo)的替代損失函數(shù)SPO+ Loss。
在這里,對(duì)于一個(gè)最小化問題 min ? w ∈ W c ? w \underset{\mathbf{w} \in \mathbf{W}}{\min} \mathbf{c}^{\top} \mathbf{w} w∈Wmin?c?w,我們先定義一個(gè)決策損失“遺憾”: l Regret ( c ^ , c ) = c ? w ? ( c ^ ) ? c ? w ? ( c ) l_{\text{Regret}} (\hat{\mathbf{c}}, \mathbf{c}) = \mathbf{c}^{{\top}} \mathbf{w}^* (\hat{\mathbf{c}}) - \mathbf{c}^{{\top}} \mathbf{w}^* (\mathbf{c}) lRegret?(c^,c)=c?w?(c^)?c?w?(c),衡量實(shí)際成本向量 c \mathbf{c} c下,實(shí)際目標(biāo)值 c ? w ? ( c ^ ) \mathbf{c}^{{\top}} \mathbf{w}^* (\hat{\mathbf{c}}) c?w?(c^)與最優(yōu)目標(biāo)值 c ? w ? ( c ) \mathbf{c}^{{\top}} \mathbf{w}^* (\mathbf{c}) c?w?(c)之間的差距,也可以理解為優(yōu)化間隙(optimality gap)。
由于 w ? ( c ) \mathbf{w}^* (\mathbf{c}) w?(c)沒有非0導(dǎo)數(shù),這個(gè)損失函數(shù)同樣也沒有非0導(dǎo)數(shù)。Elmachtoub和Grigas [1] 找到了這個(gè)函數(shù)的一個(gè)凸上界作為替代::
l SPO+ ( c ^ , c ) = ? min ? w ∈ W { ( 2 c ^ ? c ) ? w } + 2 c ^ ? w ? ( c ) ? c ? w ? ( c ) l_{\text{SPO+}} (\hat{\mathbf{c}}, \mathbf{c}) = - \underset{\mathbf{w} \in \mathbf{W}}{\min} \{(2 \hat{\mathbf{c}} - \mathbf{c})^{\top} \mathbf{w}\} + 2 \hat{\mathbf{c}}^{\top} \mathbf{w}^* (\mathbf{c}) - \mathbf{c}^{{\top}} \mathbf{w}^* (\mathbf{c}) lSPO+?(c^,c)=?w∈Wmin?{(2c^?c)?w}+2c^?w?(c)?c?w?(c)
對(duì)于損失函數(shù) l SPO+ ( c ^ , c ) l_{\text{SPO+}} (\hat{\mathbf{c}}, \mathbf{c}) lSPO+?(c^,c),有次梯度:
2 w ? ( c ) ? 2 w ? ( 2 c ^ ? c ) ∈ ? l SPO+ ( c ^ , c ) ? c ^ 2 \mathbf{w}^* (\mathbf{c}) - 2 \mathbf{w}^* (2 \hat{\mathbf{c}} - \mathbf{c}) \in \frac{\partial l_{\text{SPO+}}(\hat{\mathbf{c}}, \mathbf{c})}{\partial \hat{\mathbf{c}}} 2w?(c)?2w?(2c^?c)∈?c^?lSPO+?(c^,c)?
5.3 擾動(dòng)方法
同樣是線性目標(biāo)函數(shù),擾動(dòng)方法則是另辟蹊徑,引入隨機(jī)擾動(dòng)來處理成本向量的預(yù)測值 c ^ \hat{\mathbf{c}} c^。
Berthet等人 [4] 用在高斯隨機(jī)擾動(dòng) ξ \boldsymbol{\xi} ξ下最優(yōu)決策的期望值 E ξ [ w ? ( c ^ + σ ξ ) ] \mathbb{E}^{\boldsymbol{\xi}} [\mathbf{w}^* (\hat{\mathbf{c}} + \sigma \boldsymbol{\xi})] Eξ[w?(c^+σξ)]代替 w ? ( c ^ ) \mathbf{w}^* (\hat{\mathbf{c}}) w?(c^)。如圖所示, w ? ( c ^ + σ ξ ) \mathbf{w}^* (\hat{\mathbf{c}} + \sigma \boldsymbol{\xi}) w?(c^+σξ)是可行域極點(diǎn)(基本可行解)的離散型隨機(jī)向量,決策的期望值 E ξ [ w ? ( c ^ + σ ξ ) ] \mathbb{E}^{\boldsymbol{\xi}} [\mathbf{w}^* (\hat{\mathbf{c}} + \sigma \boldsymbol{\xi})] Eξ[w?(c^+σξ)]實(shí)際上可視為可行域極點(diǎn)???????的概率加權(quán)平均(凸組合)。與 w ? ( c ^ ) \mathbf{w}^* (\hat{\mathbf{c}}) w?(c^)不同,只要 c ^ \hat{\mathbf{c}} c^在 E ξ [ w ? ( c ^ + σ ξ ) ] \mathbb{E}^{\boldsymbol{\xi}} [\mathbf{w}^* (\hat{\mathbf{c}} + \sigma \boldsymbol{\xi})] Eξ[w?(c^+σξ)]中發(fā)生一些微小的變化,可行域極點(diǎn)權(quán)重(其發(fā)生的概率)就會(huì)相應(yīng)變化。本質(zhì)上,擾動(dòng)方法通過為離散的解向量引入概率分布實(shí)現(xiàn)平滑,這種方法與機(jī)器學(xué)習(xí)中SoftMax的思想有著異曲同工之處。
接下來,我們“只”需要通過概率密度函數(shù) f ( ξ ) f(\boldsymbol{\xi}) f(ξ)的積分求期望 E ξ [ w ? ( c ^ + σ ξ ) ] = ∫ w ? ( c ^ + σ ξ ) f ( ξ ) d ξ \mathbb{E}^{\boldsymbol{\xi}} [\mathbf{w}^* (\hat{\mathbf{c}} + \sigma \boldsymbol{\xi})] = \int \mathbf{w}^* (\hat{\mathbf{c}} + \sigma \boldsymbol{\xi}) f(\boldsymbol{\xi}) d \boldsymbol{\xi} Eξ[w?(c^+σξ)]=∫w?(c^+σξ)f(ξ)dξ,然后發(fā)現(xiàn)好像做不到。在實(shí)際操作中,我們用樣本量為 K K K的蒙特卡洛采樣來近似期望:
E ξ [ w ? ( c ^ + σ ξ ) ] ≈ 1 K ∑ κ K w ? ( c ^ + σ ξ κ ) \mathbb{E}^{\boldsymbol{\xi}} [\mathbf{w}^* (\hat{\mathbf{c}} + \sigma \boldsymbol{\xi})] \approx \frac{1}{K} \sum_{\kappa}^K {\mathbf{w}^*(\hat{\mathbf{c}} + \sigma \boldsymbol{\xi}_{\kappa})} Eξ[w?(c^+σξ)]≈K1?κ∑K?w?(c^+σξκ?)
由于 ? E ξ [ w ? ( c ^ + σ ξ ) ] ? c ^ \frac{\partial\mathbb{E}^{\boldsymbol{\xi}} [\mathbf{w}^* (\hat{\mathbf{c}} + \sigma \boldsymbol{\xi})]}{\partial \hat{\mathbf{c}}} ?c^?Eξ[w?(c^+σξ)]?存在且非0,梯度問題由此引刃而解。
除了加法擾動(dòng),Dalle等人 [14] 進(jìn)一步提出了乘法擾動(dòng),同樣引入高斯隨機(jī)擾動(dòng) ξ \boldsymbol{\xi} ξ,但讓預(yù)測成本向量 c ^ \hat{\mathbf{c}} c^與 e σ ξ ? 1 / 2 σ 2 e^{\sigma \boldsymbol{\xi} - 1/2 {\sigma}^2} eσξ?1/2σ2對(duì)應(yīng)位元素相乘。乘法擾動(dòng)消除了加法擾動(dòng)可能引起的正負(fù)號(hào)變化問題。在一些特定的應(yīng)用中,例如Dijkstra算法等,對(duì)成本向量有非負(fù)性的要求,乘法擾動(dòng)就非常有用。
基于擾動(dòng)方法,Berthet等人 [4] 利用了Fenchel-Young對(duì)偶的性質(zhì),進(jìn)一步構(gòu)造了一個(gè)新的損失函數(shù),用來降低 F ξ ( c ^ ) = E ξ [ min ? w ∈ W { ( c ^ + σ ξ ) ? w } ] F^{\boldsymbol{\xi}}(\hat{\mathbf{c}}) = \mathbb{E}^{\boldsymbol{\xi}}[\underset{\mathbf{w} \in \mathbf{W}}{\min} {\{(\hat{\mathbf{c}}+\sigma \boldsymbol{\xi})^{\top} \mathbf{w}\}}] Fξ(c^)=Eξ[w∈Wmin?{(c^+σξ)?w}]的對(duì)偶間隙。令 Ω ( w ? ( c ) ) \Omega (\mathbf{w}^* ({\mathbf{c}})) Ω(w?(c))為 F ξ ( c ) F^{\boldsymbol{\xi}}(\mathbf{c}) Fξ(c)的對(duì)偶,則有:
l PFY ( c ^ , w ? ( c ) ) = c ^ ? w ? ( c ) ? F ξ ( c ^ ) ? Ω ( w ? ( c ) ) l_{\text{PFY}}(\hat{\mathbf{c}}, \mathbf{w}^* ({\mathbf{c}})) = \hat{\mathbf{c}}^{\top} \mathbf{w}^* ({\mathbf{c}}) - F^{\boldsymbol{\xi}}(\hat{\mathbf{c}}) - \Omega (\mathbf{w}^* ({\mathbf{c}})) lPFY?(c^,w?(c))=c^?w?(c)?Fξ(c^)?Ω(w?(c))
這個(gè)損失函數(shù)可能看起來有些復(fù)雜,它甚至包含一個(gè)神秘的對(duì)偶函數(shù) Ω ( w ? ( c ) ) \Omega (\mathbf{w}^* ({\mathbf{c}})) Ω(w?(c))。但是,當(dāng)我們對(duì)其進(jìn)行求導(dǎo)操作時(shí),會(huì)發(fā)現(xiàn) Ω ( w ? ( c ) ) \Omega (\mathbf{w}^* ({\mathbf{c}})) Ω(w?(c))實(shí)際上是常數(shù),因此,梯度表達(dá)式非常簡單:
? l PFY ( c ^ , w ? ( c ) ) ? c ^ = w ? ( c ) ? E ξ [ w ? ( c ^ + σ ξ ) ] \frac{\partial l_{\text{PFY}}(\hat{\mathbf{c}}, \mathbf{w}^* ({\mathbf{c}}))}{\partial \hat{\mathbf{c}}} = \mathbf{w}^* ({\mathbf{c}}) - \mathbb{E}^{\boldsymbol{\xi}} [\mathbf{w}^* (\hat{\mathbf{c}} + \sigma \boldsymbol{\xi})] ?c^?lPFY?(c^,w?(c))?=w?(c)?Eξ[w?(c^+σξ)]
5.4 黑箱方法
面對(duì) w ? ( c ) \mathbf{w}^* (\mathbf{c}) w?(c)的不可導(dǎo)問題,有一個(gè)更加簡單粗暴的方法,即將求解器函數(shù)視為一個(gè)“黑箱”,并利用解空間的幾何形狀等性質(zhì)找到替代梯度。
如圖所示,Pogancic等人 [3] 提出了“Differentiable Black-box”方法引入一個(gè)插值超參數(shù) λ \lambda λ。對(duì)于一個(gè)成本向量預(yù)測值 c ^ \hat{\mathbf{c}} c^,在 c ^ \hat{\mathbf{c}} c^與 c ^ + λ ? l ( c ^ , c ) ? w ? ( c ^ ) \hat{\mathbf{c}} + \lambda \frac{\partial l (\hat{\mathbf{c}}, \mathbf{c})}{\partial \mathbf{w}^* (\hat{{\mathbf{c}}})} c^+λ?w?(c^)?l(c^,c)?之間對(duì)分片常數(shù)損失函數(shù) l ( c ^ , c ) l (\hat{\mathbf{c}}, \mathbf{c}) l(c^,c)進(jìn)行線性插值,從而將其轉(zhuǎn)化為分片線性函數(shù)(Piecewise Affine Function),以此可得非0梯度。
此外,Sahoo等人 [7] 提出了一種相當(dāng)簡潔的方案,即用負(fù)單位矩陣 ? I - \mathbf{I} ?I替代求解器梯度 ? w ? ( c ^ ) ? c ^ \frac{\partial \mathbf{w}^* (\hat{\mathbf{c}})}{\partial \hat{\mathbf{c}}} ?c^?w?(c^)?。我們可以將其稱為“Negative Identity”方法。從直觀角度理解,對(duì)于一個(gè)最小化問題 min ? w ∈ W c ? w \underset{\mathbf{w} \in \mathbf{W}}{\min} \mathbf{c}^{\top} \mathbf{w} w∈Wmin?c?w,我們希望通過如下方式更新成本向量的預(yù)測值 c ^ \hat{\mathbf{c}} c^:沿著 w ? ( c ^ ) \mathbf{w}^* (\hat{\mathbf{c}}) w?(c^)需要上升的方向減少,沿著 w ? ( c ^ ) \mathbf{w}^* (\hat{\mathbf{c}}) w?(c^)需要下降的方向增加,這會(huì)使 w ? ( c ^ ) \mathbf{w}^* (\hat{\mathbf{c}}) w?(c^)接近最優(yōu)決策 w ? ( c ) \mathbf{w}^* (\mathbf{c}) w?(c)。另外,該研究也證明了,這個(gè)方法可以看作是“Differentiable Black-box”方法在特定超參數(shù)λ下的特例。
5.5 對(duì)比、排序方法:
Mulamba [5] 則是曲線救國,采用了 “噪聲對(duì)比估計(jì)(Noise Contrastive Estimation)” 的技巧,巧妙地計(jì)算出替代損失函數(shù)。
首先,由于我們的可行域 w ∈ W \mathbf{w} \in \mathbf{W} w∈W是固定不變的,因此在訓(xùn)練集以及訓(xùn)練、求解過程中,我們可以自然地收集到大量的可行解,形成一個(gè)解集合 Γ \Gamma Γ。
該方法的關(guān)鍵思路是,將非最優(yōu)可行解的子集 Γ ? w ? ( c ) \Gamma \setminus \mathbf{w}^* (c) Γ?w?(c)作為負(fù)樣本,讓最優(yōu)解和“負(fù)樣本”之間的的差值盡可能大。對(duì)于一個(gè)最小化問題 min ? w ∈ W c ? w \underset{\mathbf{w} \in \mathbf{W}}{\min} \mathbf{c}^{\top} \mathbf{w} w∈Wmin?c?w,有:
l NCE ( c ^ , c ) = 1 ∣ Γ ∣ ? 1 ∑ w ∈ Γ ? w ? ( c ) ( c ^ ? w ? ( c ) ? c ^ ? w ) l_{\text{NCE}} (\hat{\mathbf{c}},\mathbf{c}) = \frac{1}{|\Gamma|-1} \sum_{\mathbf{w} \in {\Gamma \setminus {\mathbf{w}^* (\mathbf{c})}}}(\hat{\mathbf{c}}^{\top} \mathbf{w}^* (\mathbf{c})-\hat{\mathbf{c}}^{\top} \mathbf{w}) lNCE?(c^,c)=∣Γ∣?11?w∈Γ?w?(c)∑?(c^?w?(c)?c^?w)
受到這項(xiàng)工作構(gòu)造損失函數(shù)區(qū)分最優(yōu)解的啟發(fā),Mandi等人 [6] 提出了一種新思路,將端對(duì)端預(yù)測后優(yōu)化任務(wù)轉(zhuǎn)化為一個(gè)排序?qū)W習(xí)(Learning to rank) [15],學(xué)習(xí)一個(gè)目標(biāo)函數(shù)(如 c ^ ? w \hat{\mathbf{c}}^{\top} \mathbf{w} c^?w)作為排序得分,以便對(duì)可行解的子集 Γ \Gamma Γ進(jìn)行正確排序(和使用真實(shí)成本向量 c \mathbf{c} c時(shí)一致)。和之前的方法相比,這種方法的優(yōu)勢在于,它對(duì)使用的優(yōu)化方法和目標(biāo)函數(shù)的形式不加以限制。
例如,對(duì)于一個(gè)線性規(guī)劃問題, c ? w \mathbf{c}^{\top} \mathbf{w} c?w可以被視為排序得分。對(duì)于預(yù)測的成本向量 c ^ \hat{\mathbf{c}} c^,為了排序得分 c ^ ? w \hat{\mathbf{c}}^{\top} \mathbf{w} c^?w能在解集 w ∈ Γ \mathbf{w} \in \Gamma w∈Γ中有正確的排序,我們可以采用以下三種經(jīng)典的排序?qū)W習(xí)方法:單文檔方法(Pointwise Approach)、文檔對(duì)方法(Pairwise Approach)、以及文檔列表方法(Listwise Approach)。
在單文檔方法中,我們希望成本向量的預(yù)測值 c ^ \hat{\mathbf{c}} c^在可行解的子集 Γ \Gamma Γ中的得分 c ^ ? w \hat{\mathbf{c}}^{\top} \mathbf{w} c^?w盡可能接近 c ? w \mathbf{c}^{\top} \mathbf{w} c?w;在文檔對(duì)方法中,我們可以在最優(yōu)解和其他解之間創(chuàng)造排序得分的差值;而在文檔列表方法中,我們根據(jù)排序得分使用SoftMax函數(shù)計(jì)算每個(gè)可能解 w ∈ Γ \mathbf{w} \in \Gamma w∈Γ被排在最前面的概率 P ( w ∣ c ) P(\mathbf{w} | \mathbf{c}) P(w∣c),然后定義損失為概率的交叉熵 l LTR ( c ^ , c ) = 1 ∣ Γ ∣ ∑ w ∈ Γ P ( w ∣ c ) log ? P ( w ∣ c ^ ) l_{\text{LTR}} (\hat{\mathbf{c}},\mathbf{c}) = \frac{1}{|\Gamma|} \sum_{\mathbf{w} \in \Gamma} P(\mathbf{w} | \mathbf{c}) \log P(\mathbf{w} | \hat{\mathbf{c}}) lLTR?(c^,c)=∣Γ∣1?∑w∈Γ?P(w∣c)logP(w∣c^)。
5.6 損失函數(shù)近似法:
最后,我們來聊一個(gè)堪稱邪道的方法——損失函數(shù)近似法。當(dāng)我們的預(yù)測模型 g ( x , θ ) \mathbf{g}(\mathbf{x},\boldsymbol{\theta}) g(x,θ)預(yù)測出成本向量 c ^ \hat{\mathbf{c}} c^后,我們需要尋找最優(yōu)解 w ? ( c ^ ) \mathbf{w}^* (\hat{\mathbf{c}}) w?(c^),然后計(jì)算相應(yīng)的決策損失 l ( c ^ , c ) l(\hat{\mathbf{c}}, \mathbf{c}) l(c^,c)。然而,這個(gè)過程面臨著兩個(gè)主要的問題:一是優(yōu)化求解過程計(jì)算效率低下,二是損失函數(shù) l ( c ^ , c ) l(\hat{\mathbf{c}}, \mathbf{c}) l(c^,c)可能不存在有效的梯度。
針對(duì)這些問題,Shah等人 [17] 提出了一個(gè)頗為驚人的方案:局部優(yōu)化決策損失(Locally Optimized Decision Loss)。他們提出對(duì)于任意決策誤差的損失函數(shù) l ( c ^ , c ) l(\hat{\mathbf{c}}, \mathbf{c}) l(c^,c),我們都可以使用一個(gè)額外的神經(jīng)網(wǎng)絡(luò)模型 h LODL ( c ^ , c ) h_{\text{LODL}} (\hat{\mathbf{c}}, \mathbf{c}) hLODL?(c^,c)進(jìn)行擬合。具體來說,他們通過采樣預(yù)測成本向量和其對(duì)應(yīng)的真實(shí)值 ( c ^ , c ) (\hat{\mathbf{c}}, \mathbf{c}) (c^,c),訓(xùn)練近似函數(shù)模型 h LODL ( c ^ , c ) h_{\text{LODL}} (\hat{\mathbf{c}}, \mathbf{c}) hLODL?(c^,c),其損失定義為真實(shí)損失函數(shù) l ( c ^ , c ) l(\hat{\mathbf{c}}, \mathbf{c}) l(c^,c)和近似損失函數(shù) h LODL ( c ^ , c ) h_{\text{LODL}} (\hat{\mathbf{c}}, \mathbf{c}) hLODL?(c^,c)的均方誤差(MSE):
∥ l ( c ^ , c ) ? h LODL ( c ^ , c ) ∥ 2 { \lVert l(\hat{\mathbf{c}}, \mathbf{c}) - h_{\text{LODL}} (\hat{\mathbf{c}}, \mathbf{c}) \rVert}^2 ∥l(c^,c)?hLODL?(c^,c)∥2
接下來,我們固定好模型 h LODL ( c ^ , c ) h_{\text{LODL}} (\hat{\mathbf{c}}, \mathbf{c}) hLODL?(c^,c)的參數(shù),作為決策損失的近似。在這個(gè)近似的指導(dǎo)下,我們通過對(duì) h LODL ( g ( x , θ ) , c ) h_{\text{LODL}} (\mathbf{g}(\mathbf{x},\boldsymbol{\theta}), \mathbf{c}) hLODL?(g(x,θ),c)執(zhí)行梯度下降操作來更新預(yù)測模型 g ( x , θ ) \mathbf{g}(\mathbf{x},\boldsymbol{\theta}) g(x,θ)的參數(shù) θ \boldsymbol{\theta} θ。這個(gè)流程既避免了求解優(yōu)化問題的計(jì)算成本,又確保了損失函數(shù)能夠有效地計(jì)算梯度。
雖然這種方法看似天方夜譚,實(shí)則根植于深度學(xué)習(xí)的一項(xiàng)核心理論——“萬能近似定理(Universal Approximation Theorem)”,即神經(jīng)網(wǎng)絡(luò)理論上具備擬合任何函數(shù)的能力。事實(shí)上,值函數(shù)的近似是強(qiáng)化學(xué)習(xí)中的一種常見策略。因此,用類似的方法擬合端到端預(yù)測后優(yōu)化的決策誤差中也是行得通的。
這種策略優(yōu)雅地規(guī)避了求解優(yōu)化問題的計(jì)算效率瓶頸(盡管在訓(xùn)練近似函數(shù) h LODL ( c ^ , c ) h_{\text{LODL}} (\hat{\mathbf{c}}, \mathbf{c}) hLODL?(c^,c)的時(shí)候,優(yōu)化求解仍然難以避免),同時(shí)充分利用了神經(jīng)網(wǎng)絡(luò)在擬合復(fù)雜損失函數(shù)方面的強(qiáng)大能力。然而,這也帶來了額外的模型訓(xùn)練步驟,并且近似損失函數(shù)的準(zhǔn)確性將直接影響到最終模型的表現(xiàn)。盡管理論上神經(jīng)網(wǎng)絡(luò)具備表示任何函數(shù)的能力,但在實(shí)踐中,要訓(xùn)練神經(jīng)網(wǎng)絡(luò)有效地學(xué)習(xí)并近似特定函數(shù)可能并非易事。這涉及到一個(gè)復(fù)雜損失函數(shù)的優(yōu)化問題,可能存在大量的局部最優(yōu)解,而且可能受到過擬合、梯度消失、梯度爆炸等問題的影響。此外,這種方法在基準(zhǔn)數(shù)據(jù)集上的性能尚缺乏詳盡的比較,其實(shí)際效用仍待進(jìn)一步探索和證明。
6. 使用PyEPO進(jìn)行端對(duì)端預(yù)測后優(yōu)化
PyEPO(PyTorch-based End-to-End Predict-then-Optimize Tool) [16] 是我讀博期間的開發(fā)的工具,該工具的源代碼已經(jīng)發(fā)布在GitHub上,可以通過以下鏈接查找:https://github.com/khalil-research/PyEPO。它是一款基于Python的開源軟件,支持預(yù)測后優(yōu)化問題的建模和求解。PyEPO的核心功能是使用GurobiPy、Pyomo或其他求解器和算法建立優(yōu)化模型,然后將優(yōu)化模型嵌入到人工神經(jīng)網(wǎng)絡(luò)中進(jìn)行端到端訓(xùn)練。具體來說,PyEPO借助PyTorch autograd模塊,實(shí)現(xiàn)了如SPO+、黑箱方法、擾動(dòng)方法以及對(duì)比排序方法等多種策略的框架。具體使用方法可以查看文檔。
作為一款開源工具,PyEPO也歡迎社區(qū)的貢獻(xiàn)和反饋,我們也將持續(xù)更新和優(yōu)化其中的算法。
6.1 下載和安裝
要下載PyEPO,你可以從GitHub倉庫克隆:
git clone -b main --depth 1 https://github.com/khalil-research/PyEPO.git
之后進(jìn)行安裝:
pip install PyEPO/pkg/.
6.2 建立優(yōu)化模型
使用PyEPO的第一步是創(chuàng)建一個(gè)繼承于optModel類的優(yōu)化模型。由于PyEPO處理未知成本系數(shù)的預(yù)測后優(yōu)化,因此首先需要實(shí)例化一個(gè)具有固定約束和可變成本的優(yōu)化模型optModel。這樣一個(gè)優(yōu)化模型可以接受不同的成本向量,并能夠在固定的約束條件下找到相應(yīng)的最優(yōu)解。
在PyEPO中,optModel類的作用類似于一個(gè)黑箱對(duì)求解器進(jìn)行封裝,這意味著PyEPO并不一定要使用某種特定的算法或求解器。
對(duì)如下問題:
max ? x ∑ i = 0 4 c i x i s . t . 3 x 0 + 4 x 1 + 3 x 2 + 6 x 3 + 4 x 4 ≤ 12 4 x 0 + 5 x 1 + 2 x 2 + 3 x 3 + 5 x 4 ≤ 10 5 x 0 + 4 x 1 + 6 x 2 + 2 x 3 + 3 x 4 ≤ 15 ? x i ∈ { 0 , 1 } \begin{aligned} \underset{\mathbf{x}}{\max} & \sum_{i=0}^4 c_i x_i \\ s.t. \quad & 3 x_0 + 4 x_1 + 3 x_2 + 6 x_3 + 4 x_4 \leq 12 \\ & 4 x_0 + 5 x_1 + 2 x_2 + 3 x_3 + 5 x_4 \leq 10 \\ & 5 x_0 + 4 x_1 + 6 x_2 + 2 x_3 + 3 x_4 \leq 15 \\ & \forall x_i \in \{0, 1\} \end{aligned} xmax?s.t.?i=0∑4?ci?xi?3x0?+4x1?+3x2?+6x3?+4x4?≤124x0?+5x1?+2x2?+3x3?+5x4?≤105x0?+4x1?+6x2?+2x3?+3x4?≤15?xi?∈{0,1}?
PyEPO也提供了Gurobi的API,用戶能輕松地對(duì)各種優(yōu)化問題進(jìn)行建模,無需手動(dòng)編寫復(fù)雜的求解過程:
import gurobipy as gp
from gurobipy import GRB
from pyepo.model.grb import optGrbModelclass myOptModel(optGrbModel):def _getModel(self):# ceate a modelm = gp.Model()# variblesx = m.addVars(5, name="x", vtype=GRB.BINARY)# sensem.modelSense = GRB.MAXIMIZE# constraintsm.addConstr(3*x[0]+4*x[1]+3*x[2]+6*x[3]+4*x[4]<=12)m.addConstr(4*x[0]+5*x[1]+2*x[2]+3*x[3]+5*x[4]<=10)m.addConstr(5*x[0]+4*x[1]+6*x[2]+2*x[3]+3*x[4]<=15)return m, xoptmodel = myOptModel()
6.3 生成數(shù)據(jù)集
我們用隨機(jī)特征生成有高斯噪音的成本向量:
import torch
torch.manual_seed(42)num_data = 1000 # number of data
num_feat = 5 # feature dimension
num_cost = 5 # cost dimension# randomly generate data
x_true = torch.rand(num_data, num_feat) # feature
weight_true = torch.rand(num_feat, num_cost) # weight
bias_true = torch.randn(num_cost) # bias
noise = 0.5 * torch.randn(num_data, num_cost) # random noise
c_true = x_true @ weight_true + bias_true + noise # cost coef
對(duì)于端到端預(yù)測后優(yōu)化,只有成本向量 c \mathbf{c} c作為標(biāo)簽是不夠的,我們還需要最優(yōu)解 w ? ( c ) \mathbf{w}^* (\mathbf{c}) w?(c)和相應(yīng)的目標(biāo)函數(shù)值。因此,我們可以使用optDataset。optDataset是在PyTorch的Dataset類的基礎(chǔ)上進(jìn)行擴(kuò)展的一個(gè)類,它允許我們利用optModel方便地獲取求解數(shù)據(jù),并且可以被PyTorch的DataLoader直接使用。
# split train test data
from sklearn.model_selection import train_test_split
x_train, x_test, c_train, c_test = train_test_split(x_true, c_true, test_size=200, random_state=42)# build optDataset
from pyepo.data.dataset import optDataset
dataset_train = optDataset(optmodel, x_train, c_train)
dataset_test = optDataset(optmodel, x_test, c_test)# build DataLoader
from torch.utils.data import DataLoader
batch_size = 32
loader_train = DataLoader(dataset_train, batch_size=batch_size, shuffle=True)
loader_test = DataLoader(dataset_test, batch_size=batch_size, shuffle=False)
6.4 建立預(yù)測模型
由于PyEPO是基于PyTorch構(gòu)建的,所以我們可以像平常一樣使用PyTorch進(jìn)行模型的搭建,函數(shù)的使用,以及模型的訓(xùn)練等操作。這為使用各種深度學(xué)習(xí)技術(shù)的用戶提供了極大的便利。下面,我們將建立一個(gè)簡單的線性回歸模型作為預(yù)測模型:
import torch
from torch import nn# build linear model
class LinearRegression(nn.Module):def __init__(self):super(LinearRegression, self).__init__()self.linear = nn.Linear(num_feat, num_cost)def forward(self, x):out = self.linear(x)return out# init model
reg = LinearRegression()
# cuda
if torch.cuda.is_available():reg = reg.cuda()
6.5 模型的訓(xùn)練和測試
PyEPO的核心組件就是它的autograd優(yōu)化模塊,可以方便地調(diào)用前文中提到的各種方法,比如:
SPO+
import pyepo
# init SPO+ loss
spop = pyepo.func.SPOPlus(optmodel, processes=2)
擾動(dòng)方法
import pyepo
# init perturbed optimizer layer
ptb = pyepo.func.perturbedOpt(optmodel, n_samples=3, sigma=1.0, processes=2)
# init perturbed Fenchel-Younge loss
pfy = pyepo.func.perturbedFenchelYoung(optmodel, n_samples=3, sigma=1.0, processes=2)
黑箱方法
import pyepo
# init dbb optimizer layer
dbb = pyepo.func.blackboxOpt(optmodel, lambd=20, processes=2)
# init optimizer layer with identity grad
nid = pyepo.func.negativeIdentity(optmodel, processes=2)
對(duì)比、排序方法
import pyepo
# init NCE loss
nce = pyepo.func.NCE(optmodel, processes=2, solve_ratio=0.05, dataset=dataset_train)
# init constrastive MAP loss
cmap = pyepo.func.contrastiveMAP(optmodel, processes=2, solve_ratio=0.05, dataset=dataset_train)
import pyepo
# init pointwise LTR loss
ltr = pyepo.func.pointwiseLTR(optmodel, processes=2, solve_ratio=0.05, dataset=dataset_train)
# init pairwise LTR loss
ltr = pyepo.func.pairwiseLTR(optmodel, processes=2, solve_ratio=0.05, dataset=dataset_train)
# init listwise LTR loss
ltr = pyepo.func.listwiseLTR(optmodel, processes=2, solve_ratio=0.05, dataset=dataset_train)
訓(xùn)練
接下來,以SPO+為例,我們可以正常使用PyTorch進(jìn)行模型訓(xùn)練:
# set adam optimizeroptimizer = torch.optim.Adam(reg.parameters(), lr=5e-3)# train modereg.train()for epoch in range(5):# load datafor i, data in enumerate(loader_train):x, c, w, z = data # feat, cost, sol, obj# cudaif torch.cuda.is_available():x, c, w, z = x.cuda(), c.cuda(), w.cuda(), z.cuda()# forward passcp = reg(x)# spo+ lossloss = spop(cp, c, w, z)# backward passoptimizer.zero_grad()loss.backward()optimizer.step()# logregret = pyepo.metric.regret(reg, optmodel, loader_test)print("Loss: {:9.4f}, Regret: {:7.4f}%".format(loss.item(), regret*100))
由于不同的模塊可能有不同的輸入輸出,在使用這些模塊時(shí),我們需要特別關(guān)注各模塊的接口文檔,確保我們的輸入輸出數(shù)據(jù)與其兼容,避免出現(xiàn)不一致的情況。
以擾動(dòng)優(yōu)化(perturbedOpt)為例,其訓(xùn)練過程和SPO+有所不同:
# set adam optimizeroptimizer = torch.optim.Adam(reg.parameters(), lr=5e-3)# set some lossl1 = nn.L1Loss()# train modereg.train()for epoch in range(5):# load datafor i, data in enumerate(loader_train):x, c, w, z = data # feat, cost, sol, obj# cudaif torch.cuda.is_available():x, c, w, z = x.cuda(), c.cuda(), w.cuda(), z.cuda()# forward passcp = reg(x)# perturbed optimizerwe = ptb(cp)# lossloss = l1(we, w)# backward passoptimizer.zero_grad()loss.backward()optimizer.step()# logregret = pyepo.metric.regret(reg, optmodel, loader_test)print("Loss: {:9.4f}, Regret: {:7.4f}%".format(loss.item(), regret*100))
7. 結(jié)語
端到端預(yù)測后優(yōu)化是一項(xiàng)有趣的工作,也正是這項(xiàng)工作激發(fā)了我對(duì)優(yōu)化和機(jī)器學(xué)習(xí)的深入探索。我無比敬佩在這個(gè)領(lǐng)域中工作的研究者們,他們提出的各種方法都有著獨(dú)特的理論支撐和應(yīng)用價(jià)值。我們明白這只是一個(gè)開始,端對(duì)端預(yù)測后優(yōu)化這個(gè)領(lǐng)域還有有許多新的問題和理論等待我們?nèi)ヌ剿?。我期待在未來的研究?#xff0c;我們可以繼續(xù)深化對(duì)這個(gè)領(lǐng)域的理解,發(fā)現(xiàn)更多的可能性。
參考文獻(xiàn)
[1] Elmachtoub, A. N., & Grigas, P. (2021). Smart “predict, then optimize”. Management Science.
[2] Mandi, J., Stuckey, P. J., & Guns, T. (2020). Smart predict-and-optimize for hard combinatorial optimization problems. In Proceedings of the AAAI Conference on Artificial Intelligence.
[3] Pogan?i?, M. V., Paulus, A., Musil, V., Martius, G., & Rolinek, M. (2019, September). Differentiation of blackbox combinatorial solvers. In International Conference on Learning Representations.
[4] Berthet, Q., Blondel, M., Teboul, O., Cuturi, M., Vert, J. P., & Bach, F. (2020). Learning with differentiable pertubed optimizers. Advances in neural information processing systems, 33, 9508-9519.
[5] Mulamba, M., Mandi, J., Diligenti, M., Lombardi, M., Bucarey, V., & Guns, T. (2021). Contrastive losses and solution caching for predict-and-optimize. Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence.
[6] Mandi, J., Bucarey, V., Mulamba, M., & Guns, T. (2022). Decision-focused learning: through the lens of learning to rank. Proceedings of the 39th International Conference on Machine Learning.
[7] Sahoo, S. S., Paulus, A., Vlastelica, M., Musil, V., Kuleshov, V., & Martius, G. (2022). Backpropagation through combinatorial algorithms: Identity with projection works. arXiv preprint arXiv:2205.15213.
[8] Kervadec, H., Dolz, J., Yuan, J., Desrosiers, C., Granger, E., & Ayed, I. B. (2022, August). Constrained deep networks: Lagrangian optimization via log-barrier extensions. In 2022 30th European Signal Processing Conference (EUSIPCO) (pp. 962-966). IEEE.
[9] Elmachtoub, A. N., Liang, J. C. N., & McNellis, R. (2020, November). Decision trees for decision-making under the predict-then-optimize framework. In International Conference on Machine Learning (pp. 2858-2867). PMLR.
[10] Amos, B., & Kolter, J. Z. (2017, July). Optnet: Differentiable optimization as a layer in neural networks. In International Conference on Machine Learning (pp. 136-145). PMLR.
[11] Wilder, B., Dilkina, B., & Tambe, M. (2019, July). Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 33, No. 01, pp. 1658-1665).
[12] Mandi, J., & Guns, T. (2020). Interior point solving for lp-based prediction+ optimisation. Advances in Neural Information Processing Systems, 33, 7272-7282.
[13] Ferber, A., Wilder, B., Dilkina, B., & Tambe, M. (2020, April). Mipaal: Mixed integer program as a layer. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 34, No. 02, pp. 1504-1511).
[14] Dalle, G., Baty, L., Bouvier, L., & Parmentier, A. (2022). Learning with combinatorial optimization layers: a probabilistic approach. arXiv preprint arXiv:2207.13513.
[15] Liu, T. Y. (2009). Learning to rank for information retrieval. Foundations and Trends? in Information Retrieval, 3(3), 225-331.
[16] Tang, B., & Khalil, E. B. (2022). PyEPO: A PyTorch-based end-to-end predict-then-optimize library for linear and integer programming. arXiv preprint arXiv:2206.14234.
[17] Shah, S., Wilder, B., Perrault, A., & Tambe, M. (2022). Learning (local) surrogate loss functions for predict-then-optimize problems. arXiv e-prints, arXiv-2203.