ICML 2022 | 關(guān)注AI技術(shù)的你，快來(lái)查收這份機(jī)器學(xué)習(xí)前沿論文精選！

01

論文鏈接：

https://arxiv.org/abs/2202.07995

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

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

圖1：分支強(qiáng)化學(xué)習(xí)模型示意（當(dāng)每個(gè)狀態(tài)下允許選擇的動(dòng)作個(gè)數(shù)為2時(shí)）

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

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)絡(luò)（GNN）的首要要求，傳統(tǒng)模型通過(guò)置換不變的聚合操作來(lái)滿足這一前提條件。然而，這種高度對(duì)稱的置換不變聚合方式假定所有鄰居結(jié)點(diǎn)的地位均等，可能會(huì)忽略鄰居結(jié)點(diǎn)與鄰居結(jié)點(diǎn)之間的相互關(guān)系，進(jìn)而阻礙 GNN 的表達(dá)能力。

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

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

圖2：考慮中心結(jié)點(diǎn) v 和5個(gè)鄰居結(jié)點(diǎn)的簡(jiǎn)單模型示例

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

03

論文鏈接：

https://arxiv.org/abs/2202.07919

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

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

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

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

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

04

論文鏈接：

https://arxiv.org/abs/2110.14811

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

圖4：ClofNet 示意圖

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

模型在多體物理系統(tǒng)軌跡預(yù)測(cè)和 3D 分子結(jié)構(gòu)生成任務(wù)上進(jìn)行了測(cè)試。結(jié)果表明，ClofNet 顯著降低了樣本復(fù)雜度，并提升了模型預(yù)測(cè)精度和生成效果。

圖5：不同訓(xùn)練樣本量下的均方誤差結(jié)果

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

05

論文鏈接：

https://arxiv.org/abs/2108.12821

在當(dāng)前的自動(dòng)架構(gòu)搜索技術(shù)中，權(quán)重共享作為一種最為流行的核心技術(shù)被廣泛應(yīng)用。權(quán)重共享通過(guò)復(fù)用之前訓(xùn)練的子結(jié)構(gòu)的部分權(quán)重來(lái)減少?gòu)牧汩_(kāi)始訓(xùn)練不同子模型的代價(jià)。然而，由于不同子模型的共享權(quán)重梯度更新時(shí)存在干擾，如圖6和圖7所示，所以真實(shí)的子模型的準(zhǔn)確率和最后估計(jì)的子模型的準(zhǔn)確率之間的相關(guān)度往往比較低，嚴(yán)重影響了神經(jīng)架構(gòu)搜索技術(shù)的性能和適用性。

圖6：不同架構(gòu)在權(quán)重上的梯度干擾示意

圖7：不同子模型在共享權(quán)重的梯度相似度

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

從以上兩個(gè)觀察出發(fā)，本文提出了 MAGIC-AT 技術(shù)來(lái)有效緩解干擾問(wèn)題，它包括兩項(xiàng)關(guān)鍵技術(shù)：

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

2）MAGIC-A：強(qiáng)制讓不同子模型在共享網(wǎng)絡(luò)結(jié)構(gòu)上的輸入輸出盡可能相似來(lái)進(jìn)一步減少他們之間的干擾。

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

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

06

論文鏈接：

https://arxiv.org/abs/2107.01360

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

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

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

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

07

論文鏈接：

https://arxiv.org/abs/2205.07308

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

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

圖9：GloGNN 架構(gòu)

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