CUC：云計(jì)算中基于不確定約束的預(yù)測(cè)作業(yè)調(diào)度算法

論文鏈接：

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

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

對(duì)于具有不確定約束的優(yōu)化問(wèn)題，傳統(tǒng)的優(yōu)化方法無(wú)法直接進(jìn)行求解，而是需要結(jié)合對(duì)不確定約束進(jìn)行預(yù)測(cè)的步驟來(lái)進(jìn)行優(yōu)化。然而，單獨(dú)進(jìn)行預(yù)測(cè)和優(yōu)化的兩階段方法有明顯的不足之處：兩階段方法假設(shè)預(yù)測(cè)結(jié)果是準(zhǔn)確的，可是在實(shí)際中預(yù)測(cè)誤差卻無(wú)法避免，從而導(dǎo)致優(yōu)化得出的解會(huì)違反（violate） 約束。

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

1）在預(yù)測(cè)階段預(yù)測(cè)未來(lái)容量的大小，同時(shí)對(duì)預(yù)測(cè)的不確定性進(jìn)行建模；

2）用預(yù)測(cè)的未來(lái)容量的分布來(lái)指導(dǎo)作業(yè)調(diào)度的優(yōu)化問(wèn)題，得到相應(yīng)的調(diào)度方案；

3）利用調(diào)度結(jié)果結(jié)合貝葉斯優(yōu)化來(lái)進(jìn)一步提升容量預(yù)測(cè)的表現(xiàn)。

圖4：CUC 方法的架構(gòu)

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

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

表2：不同方法在公開(kāi)數(shù)據(jù)集上的表現(xiàn)對(duì)比

表3：不同違反約束水平參數(shù) p 下，CUC 方法的表現(xiàn)

04 用于學(xué)習(xí)三維隱式符號(hào)距離場(chǎng)的樣條位置編碼

論文鏈接：

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

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

圖5：算法流程圖

Spline Positional Encodings 可以幫助 MLP 更好地?cái)M合三維形狀的細(xì)節(jié)

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

圖6：各個(gè)方法的比較

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

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

此外，研究員們還在單個(gè)形狀重建和 DFaust 數(shù)據(jù)集上的形狀空間重建任務(wù)上對(duì)本文的方法進(jìn)行了驗(yàn)證。相較于現(xiàn)有的方法，本文提出的方法能取得更好的結(jié)果。另外，研究員們還在圖片擬合任務(wù)上進(jìn)行了測(cè)試。實(shí)驗(yàn)表明，本文的方法能夠取得更好的性能，且具有較強(qiáng)的通用性。

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

論文鏈接：

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

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

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

圖7：個(gè)性化異構(gòu)圖的構(gòu)建示例

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

圖8：從個(gè)性化異構(gòu)圖學(xué)習(xí)用戶表示的迭代圖池化過(guò)程

HG-Pool 方法的框架如圖9所示。對(duì)于每種節(jié)點(diǎn)，首先使用一個(gè)不同的池化 GNN 模型來(lái)學(xué)習(xí)類型特定的節(jié)點(diǎn)表示。然后使用帶 softmax 激活函數(shù)的線性變換，將這些節(jié)點(diǎn)表示轉(zhuǎn)換為類型特定的池化矩陣。最后使用 padding 后的池化矩陣，將當(dāng)前鄰接矩陣和節(jié)點(diǎn)特征矩陣轉(zhuǎn)換為更小的矩陣。

圖9：HG-Pool的示意圖

研究員們基于 MIND 新聞推薦數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)。表4的結(jié)果顯示 User-as-Graph 可以顯著提升新聞推薦中用戶建模的效果，從而取得更好的個(gè)性化新聞推薦的性能。

表4：不同方法在 MIND 數(shù)據(jù)集上的比較

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

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

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