IJCAI 2021 | 一文了解微軟亞洲研究院機器學習方向前沿進展（2）

CUC：云計算中基于不確定約束的預測作業(yè)調度算法

論文鏈接：

https://www.ijcai.org/proceedings/2021/0499.pdf

在云計算中，由于需求的龐大和多樣性，平臺計算資源的容量管理一直是一個極大的挑戰(zhàn)。為了更好地根據整個云計算平臺的容量進行規(guī)劃，平臺往往會提前收集一部分非即時的計算作業(yè)需求，這些計算作業(yè)可以持續(xù)運行指定長度的時間，且起止時間更加靈活。通過根據非即時計算作業(yè)的需求和平臺在未來一段時間內的容量情況來進行統(tǒng)一調度，有助于平衡整個平臺的工作負荷，提升平臺資源的利用效率。但是，由于平臺上未來可用的計算容量是不確定的，所以對這些非即時作業(yè)的調度，在不確定的計算資源約束下進行安排是一個巨大的挑戰(zhàn)。

對于具有不確定約束的優(yōu)化問題，傳統(tǒng)的優(yōu)化方法無法直接進行求解，而是需要結合對不確定約束進行預測的步驟來進行優(yōu)化。然而，單獨進行預測和優(yōu)化的兩階段方法有明顯的不足之處：兩階段方法假設預測結果是準確的，可是在實際中預測誤差卻無法避免，從而導致優(yōu)化得出的解會違反（violate） 約束。

在本篇論文中，微軟亞洲研究院的研究員們將這類問題建模成一個預測+優(yōu)化（Prediction + Optimization）框架下的問題，并針對這類問題提出了不確定約束下的作業(yè)調度算法 CUC（Controlling under Uncertain Constraints），該算法的架構如圖4所示。其架構大體上可以概括為以下三個方面：

1）在預測階段預測未來容量的大小，同時對預測的不確定性進行建模；

2）用預測的未來容量的分布來指導作業(yè)調度的優(yōu)化問題，得到相應的調度方案；

3）利用調度結果結合貝葉斯優(yōu)化來進一步提升容量預測的表現。

圖4：CUC 方法的架構

此外，研究員們還針對實際應用中難以避免的違反約束情況，提出了相應的控制方式。該方式可以根據系統(tǒng)的要求，將實際違反約束的比例控制在特定水平以下，使得調度方案更加可靠與穩(wěn)健。

為了驗證 CUC 算法的有效性，本文將 CUC 算法與包含經典預測方法以及精確優(yōu)化求解方法的兩階段法進行了對比，結果如表2和表3所示。結果表明 CUC 算法可以高效準確地得到違反約束比例很小的調度方案，同時可以盡可能使得更多的作業(yè)得到調度。而且通過改變違反約束水平的參數p，CUC 算法也可以靈活控制實際的違反約束情況出現的比例，以滿足不同系統(tǒng)對于調度方案的實際違反約束情況的要求。

表2：不同方法在公開數據集上的表現對比

表3：不同違反約束水平參數 p 下，CUC 方法的表現

04 用于學習三維隱式符號距離場的樣條位置編碼

論文鏈接：

https://www.ijcai.org/proceedings/2021/0151.pdf

近日，全連接神經網絡（MLP） 被提出作為三維形狀的隱式表達。MLP 以 3D 坐標為輸入，可以直接輸出該 3D 坐標點到三維形狀表面的距離，即帶符號的距離場（SDF），如圖5所示。距離為正的點在三維形狀外部，距離為負的點在三維形狀內部，距離為0的點則代表三維形狀本身。相對于傳統(tǒng)的離散三維形狀表達而言，MLP 的表達非常緊致，只需要極少量的存儲就能表達復雜的形狀，因而引起了科研人員的廣泛關注。

圖5：算法流程圖

Spline Positional Encodings 可以幫助 MLP 更好地擬合三維形狀的細節(jié)

在使用 MLP 從點云中重建 SDF 的任務中，微軟研究院的研究人員發(fā)現，如果直接將 3D 坐標作為 MLP 的輸入，那么輸出的形狀會被過度平滑，丟失高頻細節(jié)（見圖6-(a)）。為了解決這一問題，研究員們提出將三維坐標通過一系列正弦/余弦函數映射到高維空間，即 Fourier Positional Encodings（見圖6-(b)），然后再作為 MLP 的輸入；或者將 MLP 中常用的 ReLU 激活函數替換為正弦函數（見圖6-(c)）。這些方法雖然能夠擬合三維形狀的幾何細節(jié)，但是輸出的 SDF 非常雜亂，其低頻量無法被很好地重建。因此，微軟研究院的研究員們提出了基于樣條的位置編碼，即 Spline Positional Encodings。該方法不僅可以重建三維形狀的高頻細節(jié)，還能夠輸出高質量的 SDF（見圖6-(d)）。

圖6：各個方法的比較

Spline Positional Encodings 的結果如 (d) 所示

具體而言，研究員們將輸入的三維坐標通過一系列可以訓練的 B 樣條函數映射到高維空間。當 B 樣條基函數足夠稠密的時候，B 樣條函數就可以很好地逼近各種連續(xù)函數，包括正弦/余弦函數。B 樣條函數的權重可以隨著 MLP 一起優(yōu)化，所以本篇論文提出的方法可以被當成是 Fourier Positional Encodings 的推廣，因而該方法具有很強的表達能力，可以擬合形狀的高頻細節(jié)。另外，由于 B 樣條基函數可以不斷被細分，所以研究員們可以用多尺度的方式對網絡進行訓練，使得 MLP 能夠收斂到更好的局部極小。在訓練 MLP 的時候，可以先以低分辨率的 B 樣條基函數作為初始，讓 MLP 先擬合 SDF 的低頻成分；然后將 B 樣條基函數進行細分，增強 MLP 的擬合能力，讓 MLP 逐步地恢復三維形狀的幾何細節(jié)。

此外，研究員們還在單個形狀重建和 DFaust 數據集上的形狀空間重建任務上對本文的方法進行了驗證。相較于現有的方法，本文提出的方法能取得更好的結果。另外，研究員們還在圖片擬合任務上進行了測試。實驗表明，本文的方法能夠取得更好的性能，且具有較強的通用性。

05 User-as-Graph: 基于異構圖池化的新聞推薦用戶建模

論文鏈接：

https://www.ijcai.org/proceedings/2021/0224.pdf

用戶建模是各項個性化服務（如推薦系統(tǒng)）中的關鍵技術?；谟脩粜袨榈挠脩艚＃菍嶋H推薦系統(tǒng)中的主要建模方法。已有的基于用戶行為的用戶建模方法，通常將用戶建模為他們行為的集合或序列，亦或是用戶-物品二分圖上的節(jié)點。但是這些建模方法難以對行為之間的復雜聯系和上下文信息進行充分建模。為了解決這一問題，微軟亞洲研究院的研究員們提出了 User-as-Graph 方法。該方法將用戶建模為一個由行為組成的異構圖，這樣就可以更好地理解行為之間復雜的關系和上下文信息，進而更加準確地表示用戶，以實現“一人一圖，千圖千面”。

在 User-as-Graph 方法中，每個用戶都被表示為一個個性化異構圖。圖7展示了一個構建示例。圖中的節(jié)點是一個用戶的異構行為，邊是行為之間的關系。

圖7：個性化異構圖的構建示例

此外，用戶建模的任務可以轉化為一個異構圖池化的問題，即從個性化的異構圖中學習用戶的表示。然而，對異構圖池化方面的研究非常稀缺，并且現有的同構圖池化方法對于異構圖池化可能不是最優(yōu)的。基于此，研究員們又提出了一種名為 HG-Pool 的異構圖池化方法，如圖8所示。該方法的核心思想是經過多次迭代，將一個大的異構圖池化，并不斷壓縮為一個更小的異構圖，直到獲得最終的用戶表示。在每次迭代中，研究員們使用類型特定的 GNN 模型從整個異構圖的信息中學習每種節(jié)點的池化函數，這樣能夠充分考慮異構節(jié)點的特性。

圖8：從個性化異構圖學習用戶表示的迭代圖池化過程

HG-Pool 方法的框架如圖9所示。對于每種節(jié)點，首先使用一個不同的池化 GNN 模型來學習類型特定的節(jié)點表示。然后使用帶 softmax 激活函數的線性變換，將這些節(jié)點表示轉換為類型特定的池化矩陣。最后使用 padding 后的池化矩陣，將當前鄰接矩陣和節(jié)點特征矩陣轉換為更小的矩陣。

圖9：HG-Pool的示意圖

研究員們基于 MIND 新聞推薦數據集進行了實驗。表4的結果顯示 User-as-Graph 可以顯著提升新聞推薦中用戶建模的效果，從而取得更好的個性化新聞推薦的性能。

表4：不同方法在 MIND 數據集上的比較

圖10進一步比較了 User-as-Graph 和幾種常用的基于用戶行為的用戶建模方法。實驗結果表明，User-as-Graph 在用戶建模上有更好的效果。同時圖11比較了所提出的 HG-Pool 方法和幾種同構圖池化方法在新聞推薦上的性能。實驗結果表明，HG-Pool 在異構圖池化方面具有更好的效果。

圖10：不同用戶建模方法的比較。UaG 是 User-as-Graph 的縮寫

圖11：不同圖池化方法的比較