最優(yōu)傳輸距離數(shù)值求解

拉格朗日成本下的神經(jīng)最優(yōu)傳輸 一文中，筆者整理了三個(gè)要點(diǎn)：

1.最優(yōu)傳輸距離（也稱推土距離）將統(tǒng)一深度學(xué)習(xí)概率分布距離計(jì)算

2.大模型Transformer等價(jià)的重整化群流都將會(huì)沿著最優(yōu)傳輸?shù)姆较蜻M(jìn)行

3.拉格朗日成本處理神經(jīng)網(wǎng)絡(luò)最優(yōu)傳輸能更有效地建模復(fù)雜的系統(tǒng)動(dòng)力學(xué)

文章提到最優(yōu)傳輸距離目前受到數(shù)值計(jì)算效率的制約，影響了其廣泛應(yīng)用。這也是筆者一直關(guān)注的方向之一。

文中介紹的紐約大學(xué)和Meta的AI學(xué)者創(chuàng)新的拉格朗日成本處理神經(jīng)網(wǎng)絡(luò)最優(yōu)傳輸?shù)姆椒?，能更有效地解決最優(yōu)傳輸復(fù)雜成本函數(shù)問(wèn)題。

我們知道，最優(yōu)傳輸問(wèn)題大致上是尋求以最低的成本將所有質(zhì)量從源分布傳輸?shù)侥繕?biāo)分布。

眾多學(xué)者在這個(gè)領(lǐng)域做出了建設(shè)性的進(jìn)展：熵正則化近似提供了一種解決各種最優(yōu)傳輸問(wèn)題的方法，如著名的Sinkhorn算法。

核心思想是在目標(biāo)函數(shù)上加入熵正則化項(xiàng)，把復(fù)雜邊際的線性規(guī)劃問(wèn)題轉(zhuǎn)化為平滑可行域上的求解過(guò)程。  

有學(xué)者進(jìn)一步擴(kuò)展Sinkhorn 算法，證明二階Wasserstein 距離的核可以用熱核（Heat kernel）近似，從而能夠利用幾何域上的 PDE（Partial Differential Equations 偏微分方程） 求解技術(shù)進(jìn)行計(jì)算。

麻省理工學(xué)院開發(fā)了一種新算法，在幾何域上利用熱核近似，求解某個(gè)二階拋物線非線性偏微分方程，可以克服Sinkhorn算法中常見的小熵系數(shù)帶來(lái)的數(shù)值挑戰(zhàn)【文獻(xiàn)1】。

這個(gè)算法具備足夠的通用性，可以數(shù)值求解一類典型的二階拋物線偏微分方程，最優(yōu)傳輸之外，還有例如著名的熱擴(kuò)散、Hamilton-Jacobi、Fokker-Planck等方程。學(xué)者們稱之為：求解拋物線偏微分方程的框架。

求解拋物線偏微分方程的框架

最近爆火的《黑神話-悟空》等視頻游戲和電影中，創(chuàng)建模擬火焰等物理現(xiàn)象的視覺(jué)效果，以及使用 3D 打印等工具制造復(fù)雜的幾何形狀，后臺(tái)很大程度上依賴偏微分方程對(duì)這些自然過(guò)程進(jìn)行建模。

偏微分方程分析自然成為計(jì)算機(jī)圖形學(xué)、幾何處理和鄰近科技領(lǐng)域中無(wú)處不在的技術(shù)。特別是，拋物線偏微分方程描述的各種各樣的現(xiàn)象：

Hamilton-Jacobi 方程的實(shí)例模擬了前沿傳播的時(shí)間演變和經(jīng)歷非線性擴(kuò)散的函數(shù)的演變。

Fokker-Planck 方程描述了由隨機(jī)過(guò)程驅(qū)動(dòng)的密度函數(shù)的演變。而著名熱擴(kuò)散方程，則預(yù)測(cè)熱量如何隨時(shí)間沿表面或體積擴(kuò)散。

這都是歷史悠久的方程，也包括計(jì)算機(jī)圖形學(xué)中各種問(wèn)題如火焰建模G方程、隨機(jī)熱核估計(jì)、內(nèi)側(cè)軸檢測(cè)和紋理合成等等。

研究人員設(shè)計(jì)了許多算法來(lái)求解曲面上的這些問(wèn)題，但他們的方法通常因?yàn)闊o(wú)法捕獲無(wú)窮小或非線性現(xiàn)象，僅適用于線性問(wèn)題或單個(gè)PDE。

一個(gè)有趣的例子是用于重心計(jì)算的卷積 Wasserstein 距離方法【文獻(xiàn)2】：

在少量擴(kuò)散的基礎(chǔ)上，通過(guò)啟發(fā)式方法來(lái)選擇擴(kuò)散時(shí)間，步長(zhǎng)太小則數(shù)值不準(zhǔn)，步長(zhǎng)太大，則近似值出錯(cuò)。

上文提到的麻省理工學(xué)院開發(fā)的新算法則更通用，可以用于解決這一類非線性問(wèn)題，通過(guò)將復(fù)雜的偏微分方程分解為更簡(jiǎn)單的問(wèn)題來(lái)解決它們。

論文發(fā)表在 Transactions on Graphics 期刊和 SIGGRAPH 會(huì)議上。學(xué)者們稱他們的主要貢獻(xiàn)是：

一個(gè)數(shù)值框架，用于在彎曲三角形網(wǎng)格上求解線性和非線性拋物線偏微分方程，其效率與傳統(tǒng)幾何處理方法相當(dāng)。

一種對(duì)數(shù)域擴(kuò)散算法，克服了依賴于微量擴(kuò)散的幾何處理方法的已知局限性，在最佳輸運(yùn)（OT）任務(wù)中進(jìn)行了演示。

一個(gè)對(duì)該數(shù)值框架在 G 方程數(shù)值積分方面的應(yīng)用，該方程可以作為圖形管道中的組件，用于模擬火和火焰。

該算法通過(guò)將三角形網(wǎng)格上不同的非線性拋物線偏微分方程拆分為三個(gè)更簡(jiǎn)單的方程來(lái)求解，此框架可以幫助更好地分析形狀并對(duì)復(fù)雜的動(dòng)態(tài)過(guò)程進(jìn)行建模。

G 方程在計(jì)算流體動(dòng)力學(xué) （CFD） 中廣為人知，后作為“薄火焰模型”被引入計(jì)算機(jī)圖形學(xué)界，用于模擬火和火焰，以及更廣泛的燃燒現(xiàn)象。

新框架實(shí)現(xiàn)了比標(biāo)準(zhǔn)方案更好的數(shù)值穩(wěn)定性，且提供了匹配的數(shù)值結(jié)果，甚至精確解的合理近似值。 

Fokker-Planck 方程是一個(gè)線性拋物線偏微分方程，描述了由隨機(jī)微分方程 （SDE） 驅(qū)動(dòng)的過(guò)程的概率密度函數(shù)的時(shí)間演變。

新框架可用于直接在彎曲三角形網(wǎng)格上求解 Fokker-Planck 方程。表明該框架為在傳統(tǒng)幾何處理中使用隨機(jī)微分方程的新方法奠定了基礎(chǔ)。

框架的典型應(yīng)用案例

論文詳述了該框架在Wasserstein 重心、測(cè)量插值、Fire 和 Flames 的數(shù)值積分三個(gè)領(lǐng)域的應(yīng)用。以Wasserstein 重心計(jì)算為例：

“l(fā)og-sum-exp” 技巧是一種用于穩(wěn)定數(shù)值算法的標(biāo)準(zhǔn)方法，包括使用少量熵時(shí)的 Sinkhorn 算法。  

論文主張使用該數(shù)值框架直接在對(duì)數(shù)域中計(jì)算三角形網(wǎng)格上的熱擴(kuò)散結(jié)果，而不是在線性域中擴(kuò)散，然后取對(duì)數(shù)，從而獲得最優(yōu)結(jié)果：

二階拋物線 PDE 非常典型。該框架建立了一種有效的時(shí)間積分和空間離散化策略，以在三角形網(wǎng)格表面上的溫和假設(shè)下求解這類偏微分方程。

微分方程與機(jī)器學(xué)習(xí)中提到，就像統(tǒng)計(jì)學(xué)家George Box 說(shuō)的那樣: 所有的模型都是錯(cuò)誤的，但有一些是有用的。PDE對(duì)自然過(guò)程的建模無(wú)處不在。

今天初三剛開學(xué)的女兒一起散步時(shí)她說(shuō)，其實(shí)世界就是個(gè)巨大的方程。

筆者一邊在想這個(gè)認(rèn)知自己是什么時(shí)候獲得的，一邊補(bǔ)充：這個(gè)巨大的方程可以用一個(gè)巨大的神經(jīng)網(wǎng)絡(luò)近似，這就是目前人工智能的核心。

而且我們能從世界中觀測(cè)到的數(shù)據(jù)集決定了我們對(duì)世界認(rèn)知的上限。“薛定諤的佛與深度學(xué)習(xí)中的因果“中筆者總結(jié)過(guò)：

最大似然事實(shí)上決定了模型可以學(xué)習(xí)到的極限，構(gòu)成了所有學(xué)習(xí)方法的信息繭房。

【文獻(xiàn)1】A Framework for Solving Parabolic Partial Differential Equations on Discrete Domains  https://dl.acm.org/doi/10.1145/3666087

【文獻(xiàn)2】 Convolutional wasserstein distances: efficient optimal transportation on geometric domains ? https://dl.acm.org/doi/10.1145/2766963           

本文轉(zhuǎn)載自 ??清熙??，作者： 王慶法