ICML 2022 | 關注AI技術的你，快來查收這份機器學習前沿論文精選！

01

論文鏈接：

https://arxiv.org/abs/2202.07995

強化學習（Reinforcement Learning）是一個經(jīng)典的在線決策模型。在強化學習中，智能體與未知的環(huán)境進行交互，以獲得最大的累積獎勵。傳統(tǒng)強化學習是一個單路徑的序列決策模型，智能體在一個狀態(tài)下只選擇一個動作。然而，在推薦系統(tǒng)、在線廣告等許多現(xiàn)實應用中，用戶們往往會一次選擇多個選項，每個選項會觸發(fā)對應的后繼狀態(tài)，例如，在基于類別的購物推薦中，系統(tǒng)往往會先推薦一些商品的一級類別，當某個一級類別被用戶點擊時，系統(tǒng)會進一步推薦一些二級類別。在一次購物中，用戶可能會選擇（觸發(fā)）多條類別-商品路徑，如用戶可能會觸發(fā)“辦公設備-打印機-激光打印機”和“辦公設備-掃描儀-平板掃描儀”這兩條路徑。

為了處理這種允許多個動作和多個后繼狀態(tài)的現(xiàn)實場景，微軟亞洲研究院的研究員們提出了一種新穎的、樹狀的強化學習模型，名為分支強化學習（Branching  Reinforcement Learning）。在分支強化學習中，每個狀態(tài)下，智能體可以選擇多個動作，每個狀態(tài)-動作對有一個潛在的概率被觸發(fā)。如果一個狀態(tài)-動作對被成功觸發(fā)，那么它會根據(jù)其潛在的轉(zhuǎn)移分布轉(zhuǎn)移到一個常規(guī)的后繼狀態(tài)；如果這個狀態(tài)-動作對沒有被成功觸發(fā)，那它則會轉(zhuǎn)移到一個“終止狀態(tài)”（獎勵總是為零的吸收態(tài)）。由于智能體可能觸發(fā)多條狀態(tài)-動作路徑，因此它的歷史序列決策呈現(xiàn)出一個樹狀結構。

圖1：分支強化學習模型示意（當每個狀態(tài)下允許選擇的動作個數(shù)為2時）

在分支強化學習這個新的決策模型下，研究員們構建了全新的理論分析工具，包括分支貝爾曼方程（Branching Bellman Equation）、分支價值差異引理（Branching Value Difference Lemma）和分支總方差定律（Branching Law of Total Variance）。研究員們設計了兩種計算和采樣高效的算法 BranchVI 和 BranchRFE，通過嚴格的理論分析證明了算法的最優(yōu)性，并在實驗上驗證了本文的理論結果。

02

論文鏈接：

https://arxiv.org/abs/2205.14368

代碼鏈接：

https://github.com/zhongyu1998/PG-GNN

演示鏈接：

https://github.com/zhongyu1998/PG-GNN/blob/main/demo.mp4

圖與鄰接矩陣的置換不變性是圖神經(jīng)網(wǎng)絡（GNN）的首要要求，傳統(tǒng)模型通過置換不變的聚合操作來滿足這一前提條件。然而，這種高度對稱的置換不變聚合方式假定所有鄰居結點的地位均等，可能會忽略鄰居結點與鄰居結點之間的相互關系，進而阻礙 GNN 的表達能力。

與置換不變相反，置換敏感的聚合函數(shù)對于結點順序非常敏感，可以看作是一種“對稱性破缺”機制，打破了鄰居結點的均等地位。這樣一來，聚合函數(shù)可以顯式地建模鄰居結點之間的內(nèi)在關系（如二元依賴），捕獲兩個鄰居結點之間是否存在連接，從而識別并利用局部的圖子結構來提高表達能力。

盡管置換敏感的聚合函數(shù)比置換不變的聚合函數(shù)具有更加強大的表達能力，但是還需要額外考慮所有n!種置換來保證泛化能力，在計算復雜度上面臨著巨大的挑戰(zhàn)。為了解決這一問題，本文利用置換群（permutation group）設計了一種新穎的置換敏感聚合機制，通過置換采樣策略采樣少量具有代表性的置換，捕獲鄰居與鄰居之間的二元依賴，從而高效地提升 GNN 的表達能力：研究員們證明了所提出的方法嚴格地比二維 Weisfeiler-Lehman（2-WL）圖同構測試更強大，并且能夠區(qū)分一些 3-WL 測試無法區(qū)分的非同構圖對；此外，相比于傳統(tǒng)方法需要考慮所有 n! 種置換，本文所提出的方法能夠達到線性的置換采樣復雜度。

圖2：考慮中心結點 v 和5個鄰居結點的簡單模型示例

綜合而言，本文基于置換敏感的聚合機制設計了一種強大而高效的圖神經(jīng)網(wǎng)絡，它在保證表達能力的同時，先后借助近似置換不變性的思想與線性置換采樣策略，顯著降低了計算復雜度。如何利用置換敏感的圖神經(jīng)網(wǎng)絡在表達能力上的天然優(yōu)勢，在表達能力和計算復雜度之間尋找均衡，將是未來富有前景的研究方向。

03

論文鏈接：

https://arxiv.org/abs/2202.07919

知識圖譜表示學習是一種有效緩解知識圖譜不完整問題的有效方法。本文對現(xiàn)有知識圖譜表示方法的建模能力進行了分析：（1）現(xiàn)有方法中的關系旋轉(zhuǎn)固定于低維空間，這很大程度地限制了模型的建模能力；（2）現(xiàn)有方法無法全面地建模知識圖譜中重要的關系模式與映射屬性。

為解決以上兩個問題，本文引入了 Householder 反射變換作為基本數(shù)學工具，并基于此進一步設計了兩種線性變換作為知識圖譜中的關系表示：（1）由多個 Householder 反射組合而成的 Householder 旋轉(zhuǎn)，可擴展至任意高維空間，實現(xiàn)強大的建模能力；（2）由原始 Householder 反射修改得到的 Householder 投影，可賦予模型建模復雜關系映射屬性的能力，同時保持模型對重要關系模式的建模能力。

在此 Householder 框架下，本文得以提出了一個具有更強大、更全面建模能力的 KGE 模型，名為 HousE。HousE 將關系建模為實體間的兩階段變換，如圖3所示，對于給定三元組，HousE 首先通過 Householder 關系投影得到關系特定的頭尾實體表示，然后在投影后的頭尾實體之間建模 Householder 關系旋轉(zhuǎn)。

圖3：(a) 二維空間中的Householder反射；（b）二維空間中的 Householder 旋轉(zhuǎn)；（c）二維空間中不同 τ 值下對應的 Householder 投影；（d）HousE 圖示：為了建模三元組(h, r, t_1)和(h, r, t_2)，HousE 首先利用 Householder 投影（Pro-H1 和 Pro-H2）改變實體間的相對距離，然后對投影后的頭實體表示 S_(h,r) 進行 Householder 旋轉(zhuǎn)（Rot-H），使其與投影后的尾實體表示盡可能相近。

文章從理論上證明了 HousE 可以建模知識圖譜中的重要關系模式和復雜映射屬性，并且能夠自然地將旋轉(zhuǎn)變換擴展到任意高維空間，是現(xiàn)有基于旋轉(zhuǎn)的知識圖譜表示模型的推廣。實驗上，HousE 在五個公開數(shù)據(jù)集上均取得了最新的 SOTA 性能，更多實驗結果（如細粒度性能分析實驗等）也進一步驗證了 Householder 框架所帶來的強大建模能力。

04

論文鏈接：

https://arxiv.org/abs/2110.14811

-群等變性質(zhì)如置換不變、平移旋轉(zhuǎn)等變性（又稱 SE(3) 群等變），是許多 3D 多體物理系統(tǒng)（如分子動力系統(tǒng)）具有的性質(zhì)。等變圖網(wǎng)絡是一類滿足群等變性質(zhì)的機器學習模型，常用于 3D 多體物理系統(tǒng)的性質(zhì)預測、構像生成等任務。群等變模型是指模型的輸入輸出關于群作用是等變的，即 ?_NN (T_g (x))=S_g (?_NN (x))，其中 T_g 和 S_g 是群元素 g 對應的群作用。一個傳統(tǒng)設計等變模型的方式是僅作用非線性變換在節(jié)點距離上（例如 Radial Nework, Schnet, EGNN 等），并利用鄰居節(jié)點坐標為標架來表示向量信息。本文指出，這類模型雖然計算高效，但會存在方向退化、表達力不足的問題。本文從等變圖網(wǎng)絡的表達能力出發(fā)，設計了一組 3D 等變局部標架 ClofNet，解決了一類 SE(3) 等變圖網(wǎng)絡表達力不足的問題。

圖4：ClofNet 示意圖

具體地，對于給定 3D 圖，首先對位置坐標進行去中心化，將系統(tǒng)質(zhì)心移動至原點，這一操作保證了結果的平移不變性。然后給定相鄰粒子對位置坐標 (x_i,x_j)，建立局部等變標架 (a_ij, b_ij, c_ij )，其中 a_ij=(x_i-x_j)/(||x_i-x_j||), b_ij=(x_i×x_j)/(||x_i×x_j ||), c_ij=a_ij×b_ij。由于叉乘運算的性質(zhì)，(a_ij, b_ij, c_ij)構成了一組相互正交的 3D 標架。在構建局部標架后，ClofNet 將節(jié)點 i, j 對應的張量信息向標架投影，得到一組標量 s_ij=Scalarize(X_i, X_j, (a_ij, b_ij, c_ij))，例如節(jié)點 i 的坐標投影后獲得標量?x_i, a_ij?,?x_i, b_ij ?,?x_i, c_ij?。標量信息經(jīng)神經(jīng)網(wǎng)絡作用，輸出局部標架的系數(shù)，并用局部標架的線性組合表示輸出向量，此步驟稱為 Vectorization?？梢宰C明，ClofNet 在 SE(3) 群等變函數(shù)空間具有一致的表達力。

模型在多體物理系統(tǒng)軌跡預測和 3D 分子結構生成任務上進行了測試。結果表明，ClofNet 顯著降低了樣本復雜度，并提升了模型預測精度和生成效果。

圖5：不同訓練樣本量下的均方誤差結果

表1：不同算法在數(shù)據(jù)集 GEOM-QM9 和 GEOM-Drugs 上的實驗結果

05

論文鏈接：

https://arxiv.org/abs/2108.12821

在當前的自動架構搜索技術中，權重共享作為一種最為流行的核心技術被廣泛應用。權重共享通過復用之前訓練的子結構的部分權重來減少從零開始訓練不同子模型的代價。然而，由于不同子模型的共享權重梯度更新時存在干擾，如圖6和圖7所示，所以真實的子模型的準確率和最后估計的子模型的準確率之間的相關度往往比較低，嚴重影響了神經(jīng)架構搜索技術的性能和適用性。

圖6：不同架構在權重上的梯度干擾示意

圖7：不同子模型在共享權重的梯度相似度

在這個工作里，研究員們深入研究了權值共享中的干擾問題。通過采樣不同的子模型并計算這些子模型在共享的部分權值上的梯度，研究員們觀察到了兩個現(xiàn)象：1）共享權值上的梯度的干擾程度和兩個子模型之間的不同網(wǎng)絡層結構的數(shù)量是正相關的；2）兩個子架構在共享網(wǎng)絡結構上的輸入和輸出值越相似，他們之間的干擾就越小。

從以上兩個觀察出發(fā)，本文提出了 MAGIC-AT 技術來有效緩解干擾問題，它包括兩項關鍵技術：

1）MAGIC-T：與之前的隨機采樣子模型進行梯度更新的工作不同，本文提出了一個漸進子架構修改的采樣范式。在每一次臨接的梯度更新步數(shù)之間，讓其采樣的子架構僅僅存在一個網(wǎng)絡層結構的差別以最小化不同鄰接梯度更新的干擾。

2）MAGIC-A：強制讓不同子模型在共享網(wǎng)絡結構上的輸入輸出盡可能相似來進一步減少他們之間的干擾。

研究員們首先在一個復雜的 BERT 搜索空間中驗證了本文提出的兩項關鍵技術都能夠提升超網(wǎng)絡的排序性能，并且兩種技術結合能夠得到進一步的提升。接著，研究員們使用 MAGIC-AT 在 BERT 語言模型（如表1所示），SQuAD 自然語言理解任務以及大規(guī)模圖像分類問題 ImageNet 上做了神經(jīng)架構搜索，實驗證明 MAGIC-AT 搜索得到的架構一致且顯著的超過之前的工作，證明了本文方法的有效性。

表2：MAGIC-NAS 搜索的 BERT 語言模型在 GLUE 數(shù)據(jù)集上的效果

06

論文鏈接：

https://arxiv.org/abs/2107.01360

離策略評估（Off-Policy Evaluation, OPE）旨在利用由其他策略產(chǎn)生的數(shù)據(jù)評估目標策略的性能。OPE 在許多實際應用中至關重要，如交易、廣告、自動駕駛、****物試驗等等。在這些應用中，通過與真實環(huán)境交互的在線評估策略方式可能花費成本巨大。

現(xiàn)有的 OPE 方法主要基于分布糾正（distribution correction）、模型估計（model estimation）和價值函數(shù)估計（Q-estimation），關注的是精確估計策略的回報，采用的是無監(jiān)督估計方法。本文發(fā)現(xiàn)這些方法與現(xiàn)實需求和條件存在差異。首先，在許多應用中，OPE 的最終目標是從候選策略中選擇較好的策略，而非精確估計每個策略的回報。其次，人們通?？梢灾酪恍┮言谡鎸嵀h(huán)境中部署的策略的性能，但是這部分信息未被利用。因此，本文定義了兩個新問題：監(jiān)督離策略估計（Supervised Off-Policy Evaluation, SOPE）和監(jiān)督離策略排序（Supervised Off-Policy Ranking, SOPR），分別利用離策略數(shù)據(jù)集以及已知策略的回報或排序來估計目標策略的性能或性能排序。其中，SOPR 不需精確估計策略性能，更加容易并且更具實際應用價值。

本文還進一步提出了一種基于監(jiān)督學習的策略排序算法，利用策略表示和策略排序標簽訓練了一個策略打分模型，并基于策略得分對策略排序。對于策略表示，由于不同策略可能函數(shù)形式不同輸入特征不同，且不一定具有參數(shù)，因此難以采用策略參數(shù)表示策略。對此，本文提出利用狀態(tài)-動作數(shù)據(jù)和一種分層 Transformer 編碼器學習策略表示，其中狀態(tài)出自離策略數(shù)據(jù)集，動作由策略在狀態(tài)上決策產(chǎn)生；然后通過對數(shù)據(jù)進行聚類，在類內(nèi)和類間分別編碼；最后將策略表示映射為分數(shù)，利用排序損失函數(shù)優(yōu)化模型。該算法名為 SOPR-T，T 代表 Transformer。本文利用 Mujoco 環(huán)境的公開數(shù)據(jù)集對所提算法進行了驗證，并與 OPE 基線算法對比，結果表明 SOPR-T 在排序相關度（Rank correlation）和后悔值（Regret value）上的表現(xiàn)均優(yōu)于基線算法。

圖8：基于分層 Transformer 編碼器的策略打分模型

07

論文鏈接：

https://arxiv.org/abs/2205.07308

在具有異質(zhì)性（Graph heterophily）的圖中，相鄰節(jié)點間更傾向于有不同的標簽。業(yè)界稱具有相同標簽的節(jié)點記為同質(zhì)節(jié)點，不同標簽的節(jié)點記為異質(zhì)節(jié)點。當用傳統(tǒng) GNN 方法（GCN、GAT等）去學習異質(zhì)圖節(jié)點的表示時，會導致當前節(jié)點的表示被鄰域中更多的異質(zhì)節(jié)點所誤導，從而學習到錯誤的表示。現(xiàn)有的研究嘗試通過增大鄰域的范圍去捕獲更多的同質(zhì)節(jié)點來指導當前節(jié)點的學習。但這其中存在一個挑戰(zhàn)：該使用多大范圍的鄰域？微軟亞洲研究院的研究員們給出的解決方案是：使用全局鄰域，即使用整張圖。

為此，研究員們提出了一個新的 GNN 模型 GloGNN，其架構如圖10所示，輸入包括節(jié)點特征和鄰接矩陣，經(jīng)融合得到初始的節(jié)點特征矩陣。在之后的每一層中，GloGNN 基于一個系數(shù)矩陣來對節(jié)點特征矩陣進行更新。該系數(shù)矩陣刻畫了整張圖中所有節(jié)點間的相關性，由一個同時考慮節(jié)點特征和拓撲結構的優(yōu)化函數(shù)求解得到，并且引入 Woodbury    Formula 優(yōu)化求逆過程和調(diào)整矩陣乘法順序?qū)⒏逻^程的時間復雜度降低為線性復雜度。此外，研究員們還提出了升級版的 GloGNN++，其不僅考慮節(jié)點之間的相關性，也關注節(jié)點特征中每一維的重要性。最后，本文從理論和實驗兩方面證明了方法的有效性。

圖9：GloGNN 架構

理論方面，通過對更新過程中的系數(shù)矩陣和節(jié)點特征進行 Grouping Effect 分析，驗證了方法設計的合理性。實驗方面，研究員們在15個不同領域、規(guī)模、異質(zhì)性的數(shù)據(jù)集上與代表性的11種 GNN 方法進行了比較，并做了大量的效率分析和可解釋性分析，結果表明本文提出的 GloGNN 和 GloGNN++ 可以有效且高效地從整張圖中捕獲同質(zhì)節(jié)點。