最優傳輸距離數值求解

拉格朗日成本下的神經最優傳輸 一文中，筆者整理了三個要點：

1.最優傳輸距離（也稱推土距離）將統一深度學習概率分布距離計算

2.大模型Transformer等價的重整化群流都將會沿著最優傳輸的方向進行

3.拉格朗日成本處理神經網絡最優傳輸能更有效地建模復雜的系統動力學

文章提到最優傳輸距離目前受到數值計算效率的制約，影響了其廣泛應用。這也是筆者一直關注的方向之一。

文中介紹的紐約大學和Meta的AI學者創新的拉格朗日成本處理神經網絡最優傳輸的方法，能更有效地解決最優傳輸復雜成本函數問題。

我們知道，最優傳輸問題大致上是尋求以最低的成本將所有質量從源分布傳輸到目標分布。

眾多學者在這個領域做出了建設性的進展：熵正則化近似提供了一種解決各種最優傳輸問題的方法，如著名的Sinkhorn算法。

核心思想是在目標函數上加入熵正則化項，把復雜邊際的線性規劃問題轉化為平滑可行域上的求解過程。  

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

麻省理工學院開發了一種新算法，在幾何域上利用熱核近似，求解某個二階拋物線非線性偏微分方程，可以克服Sinkhorn算法中常見的小熵系數帶來的數值挑戰【文獻1】。

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

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

最近爆火的《黑神話-悟空》等視頻游戲和電影中，創建模擬火焰等物理現象的視覺效果，以及使用 3D 打印等工具制造復雜的幾何形狀，后臺很大程度上依賴偏微分方程對這些自然過程進行建模。

偏微分方程分析自然成為計算機圖形學、幾何處理和鄰近科技領域中無處不在的技術。特別是，拋物線偏微分方程描述的各種各樣的現象：

Hamilton-Jacobi 方程的實例模擬了前沿傳播的時間演變和經歷非線性擴散的函數的演變。

Fokker-Planck 方程描述了由隨機過程驅動的密度函數的演變。而著名熱擴散方程，則預測熱量如何隨時間沿表面或體積擴散。

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

研究人員設計了許多算法來求解曲面上的這些問題，但他們的方法通常因為無法捕獲無窮小或非線性現象，僅適用于線性問題或單個PDE。

一個有趣的例子是用于重心計算的卷積 Wasserstein 距離方法【文獻2】：

在少量擴散的基礎上，通過啟發式方法來選擇擴散時間，步長太小則數值不準，步長太大，則近似值出錯。

上文提到的麻省理工學院開發的新算法則更通用，可以用于解決這一類非線性問題，通過將復雜的偏微分方程分解為更簡單的問題來解決它們。

論文發表在 Transactions on Graphics 期刊和 SIGGRAPH 會議上。學者們稱他們的主要貢獻是：

一個數值框架，用于在彎曲三角形網格上求解線性和非線性拋物線偏微分方程，其效率與傳統幾何處理方法相當。

一種對數域擴散算法，克服了依賴于微量擴散的幾何處理方法的已知局限性，在最佳輸運（OT）任務中進行了演示。

一個對該數值框架在 G 方程數值積分方面的應用，該方程可以作為圖形管道中的組件，用于模擬火和火焰。

該算法通過將三角形網格上不同的非線性拋物線偏微分方程拆分為三個更簡單的方程來求解，此框架可以幫助更好地分析形狀并對復雜的動態過程進行建模。

G 方程在計算流體動力學 （CFD） 中廣為人知，后作為“薄火焰模型”被引入計算機圖形學界，用于模擬火和火焰，以及更廣泛的燃燒現象。

新框架實現了比標準方案更好的數值穩定性，且提供了匹配的數值結果，甚至精確解的合理近似值。 

Fokker-Planck 方程是一個線性拋物線偏微分方程，描述了由隨機微分方程 （SDE） 驅動的過程的概率密度函數的時間演變。

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

框架的典型應用案例

論文詳述了該框架在Wasserstein 重心、測量插值、Fire 和 Flames 的數值積分三個領域的應用。以Wasserstein 重心計算為例：

“log-sum-exp” 技巧是一種用于穩定數值算法的標準方法，包括使用少量熵時的 Sinkhorn 算法。  

論文主張使用該數值框架直接在對數域中計算三角形網格上的熱擴散結果，而不是在線性域中擴散，然后取對數，從而獲得最優結果：

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

微分方程與機器學習中提到，就像統計學家George Box 說的那樣: 所有的模型都是錯誤的，但有一些是有用的。PDE對自然過程的建模無處不在。

今天初三剛開學的女兒一起散步時她說，其實世界就是個巨大的方程。

筆者一邊在想這個認知自己是什么時候獲得的，一邊補充：這個巨大的方程可以用一個巨大的神經網絡近似，這就是目前人工智能的核心。

而且我們能從世界中觀測到的數據集決定了我們對世界認知的上限。“薛定諤的佛與深度學習中的因果“中筆者總結過：

最大似然事實上決定了模型可以學習到的極限，構成了所有學習方法的信息繭房。

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

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

本文轉載自 ??清熙??，作者： 王慶法