原創(chuàng) Ian Gemp等 集智俱樂部 收錄于話題#復(fù)雜科學(xué)前沿202165個

導(dǎo)語

來自Deepmind 的論文“EigenGame: PCA as a Nash Equilibrium”獲得了ICLR2021年的杰出論文獎，該文通過多主體建模，用一個全新的視角，審視了數(shù)據(jù)降維中常用用的主成分分析法（PCA）。

Brian McWilliams、Ian Gemp、Claire Vernade | 作者

郭瑞東 | 譯者

趙雨亭 | 審校

鄧一雪 | 編輯

1. 從單主體智能到多主體建模

現(xiàn)代人工智能系統(tǒng)處理諸如識別圖像中的物體、預(yù)測蛋白質(zhì)的3D結(jié)構(gòu)這樣的任務(wù)，就像一個勤奮的學(xué)生準(zhǔn)備考試一樣——通過對許多次的訓(xùn)練，它們可以逐漸減少自己的錯誤率，直到取得成功。這是一項孤獨的努力，也是機(jī)器學(xué)習(xí)中通用的學(xué)習(xí)方式。

人類的學(xué)習(xí)是通過與他人互動與玩耍來進(jìn)行的。一個人獨自解決極其復(fù)雜的問題是很少見的。通過讓求解問題具備類似游戲的互動性， DeepMind 已經(jīng)成功訓(xùn)練了人工智能進(jìn)行 Capture the Flag 游戲，并在星際爭霸中達(dá)到人類大師的水平。這使研究人員想知道，以博弈論的視角看待模型，可否幫助解決其他基本的機(jī)器學(xué)習(xí)問題。

主成分分析（Principal Component Analysis，PCA）于20世紀(jì)初期被提出，是高維數(shù)據(jù)處理流程中的第一步：通過數(shù)據(jù)聚類，讓數(shù)據(jù)降維和可視化變得容易；同時也使得在分類及回歸任務(wù)中，學(xué)到數(shù)據(jù)的低維表征成為可能。在 Deepmind 的論文中，研究人員將主成分分析重新表述為一個競爭性的多主體博弈，將其稱為特征值游戲（EigenGame）。

主成分分析通常被表述為一個最優(yōu)化問題（或單主體問題）。然而，該文提出，多主題建模帶來了新的洞察力和算法：利用最新的計算資源。這使主成分分析能夠擴(kuò)展到以前需要太多計算資源的大規(guī)模數(shù)據(jù)集，并為未來的探索提供了一種替代方法。

最初的主成分分析，是由紙和筆完成的，之后轉(zhuǎn)移到數(shù)據(jù)倉庫的計算中心。但隨著數(shù)據(jù)集的增大，這種常見的計算方法已成為計算瓶頸。研究人員已探索使用諸如引入隨機(jī)化等方式，來改進(jìn)大數(shù)據(jù)集上 PCA算法的性能。然而，這些方法，研究者發(fā)現(xiàn)其無法利用為深度學(xué)習(xí)準(zhǔn)備的硬件資源，例如大規(guī)模并行的GPU和TPU。

PCA 與許多重要的機(jī)器學(xué)習(xí)和工程問題，都需要共同的解決方案，即奇異值分解（singular value decomposition）。通過以正確的方式解決 PCA 問題，該文提出的算法可以更廣泛地應(yīng)用于機(jī)器學(xué)習(xí)樹的各個分支。

圖1. 一系列的機(jī)器學(xué)習(xí)任務(wù)，例如 PCA、最小二乘法、 譜聚類（Spectral Clustering）、潛在語義索引（Latent Semantic Indexing LSI）和排序都需要 SVD為其基礎(chǔ)。

例如，通過提取特征值，可以在社交網(wǎng)絡(luò)上進(jìn)行譜聚類，如下圖所示，圖像展示了根據(jù)多主體建模找到的特征向量，經(jīng)過 K-means算法得出的對臉書界面的聚類可視化，其中不同顏色代表真實的分類標(biāo)簽，不同的花瓣代表聚類得出的結(jié)果。結(jié)果顯示聚類結(jié)果中7/8的標(biāo)簽都能對應(yīng)到真實標(biāo)簽。

圖2. 臉書頁面通過特征值游戲聚類的可視化，來源：EigenGame Unloaded When playing games is better than optimizing Fig 7

2. 特征值游戲 EigenGame 的規(guī)則

和任何棋類游戲一樣，為了將 PCA 重新定義為一種游戲，研究人員需要一系列的規(guī)則和目標(biāo)供玩家遵循。有許多可能的方法來設(shè)計這樣一個博弈；然而，關(guān)鍵的思路來自主成分分析本身：最佳解決方案由特征向量組成，這些特征向量捕捉數(shù)據(jù)中，方差最大并且彼此正交的維度。

圖3. 該游戲中，每個玩家都希望對齊方向的差異最大（即更大的數(shù)據(jù)傳播），但也需要保持與相對其編號較低的玩家呈正交垂直。

在特征值游戲中，每個玩家控制一個特征向量。玩家通過解釋數(shù)據(jù)中的差異來提高他們的得分，但是如果他們與其他玩家太接近，就會受到處罰。該游戲還建立了一個層次結(jié)構(gòu)：玩家1只關(guān)心方差的最大化，而其他玩家則不得不同時擔(dān)心最大化他們可解釋的方差，并最小化與編號比自己低的玩家的相似度。這種獎勵和懲罰的組合決定了每個玩家獲得的收益函數(shù)。

圖4. 玩家參與特征值游戲的收益計算法示意圖

通過經(jīng)過適當(dāng)設(shè)計的方差（var）和對齊（align）項，該論文證明了：

1）如果所有的玩家都表現(xiàn)最優(yōu)，他們等價于一起實現(xiàn)了游戲的納什均衡點，而這就是 PCA 算法的解決方案。

2）如果每個玩家獨立地使用梯度上升法，最大化他們的效用，那最優(yōu)點是有可能實現(xiàn)的。

圖5. 特征值游戲引導(dǎo)每個玩家沿著單位球面從空的圓圈走向平行的箭頭（代表找到的特征向量）。藍(lán)色代表玩家1。紅色代表玩家2。綠色代表玩家3。圖6. 每個玩家 i 的效用函數(shù)取決于編號比TA小的玩家，這里用有向無環(huán)圖來表示。每個編號更低的玩家必須以固定的順序比對其它玩家傳播它的當(dāng)前向量。（來源：EigenGame: PCA as a Nash Equilibrium）

算法中，玩家能夠同時獨立地進(jìn)行梯度上升，這一特性尤其重要，因為它允許讓計算分布在幾十個谷歌云的TPU上，從而實現(xiàn)了數(shù)據(jù)和模型的并行計算。這使得該文提出的算法能夠適應(yīng)真正的海量數(shù)據(jù)。特征值游戲能在數(shù)小時內(nèi)為包含數(shù)百萬特性或數(shù)十億行的數(shù)據(jù)集找到主成分。

圖7. 特征值游戲并行運算示意圖：每個有色方塊都是一個獨立的主體。首先，每個主體在一個設(shè)備上計算更新；之后每個主體被復(fù)制到多個設(shè)備，并使用獨立的批次數(shù)據(jù)計算更新；然后對被復(fù)制后的不同主體進(jìn)行平均，以形成一個更健壯的更新方向。

3. 多智能主體，從優(yōu)化到赫布法則

通過從多智能主體的角度審視 PCA，該文對可擴(kuò)展到大數(shù)據(jù)集的算法進(jìn)行了新穎的分析。該文還發(fā)現(xiàn)了一個與赫布法則（Hebbian Learning ，神經(jīng)元在學(xué)習(xí)時如何調(diào)整其連接權(quán)重）的令人驚訝的聯(lián)系。在特征值游戲中，每個玩家最大化他們的效用過程中，如何更新其特征，類似于赫布法則中，大腦具有可塑性的神經(jīng)元的突觸，如何從周圍的環(huán)境習(xí)得規(guī)則。按照赫布法則，更新得出的連接會收斂到已知的 PCA 解決方案，但其中不會派生出任何效用函數(shù)及其梯度。博弈論為研究人員提供了一個新的視角來看待赫布法則，同時也為一系列機(jī)器學(xué)習(xí)問題提出了解法。

圖8. 多主體建模的視角，為基于優(yōu)化和基于連接主義這兩種機(jī)器學(xué)習(xí)的模式搭建了溝通的橋梁

如何看待機(jī)器學(xué)習(xí)，存在一個連續(xù)的曲線，其一端是提出一個可優(yōu)化的目標(biāo)函數(shù)：利用凸和非凸優(yōu)化理論來解決問題，該方向可以找出解決方案的整體性質(zhì)。而在另一端上，是由神經(jīng)科學(xué)引發(fā)的純聯(lián)結(jié)主義方法——例如赫布式的連接更新法則。但該方法會使得對整個系統(tǒng)的分析更加困難，常常需要對系統(tǒng)的復(fù)雜動力學(xué)進(jìn)行研究。

像特征游戲這樣的基于博弈論的方法介于兩者之間。玩家的更新不受限于某個特定函數(shù)的梯度，只是對其他玩家當(dāng)前策略的最佳反應(yīng)。每個人可以自由地設(shè)計效用函數(shù)程序，以及更新中所需的特定屬性（例如，指定特定方向上的進(jìn)行無偏的更新，或某方向的更新需要加速）；同時， 多主體游戲符合納什均衡這一特性，仍然允許玩家對系統(tǒng)進(jìn)行整體的分析。

特征值游戲代表了一個通過設(shè)計多主體游戲，來解決機(jī)器學(xué)習(xí)問題的具體例子，其解決方案，是一個大型多智能體系統(tǒng)的輸出。一般來說，將機(jī)器學(xué)習(xí)問題設(shè)計為多智能體博弈是一個具有挑戰(zhàn)性的機(jī)制設(shè)計問題，然而，研究人員已經(jīng)利用兩人間的零和博弈，來解決機(jī)器學(xué)習(xí)問題。最值得注意成果就是生成性對抗性網(wǎng)絡(luò)（GANs）這一建模方法的成功。這推動了人們對博弈論與機(jī)器學(xué)習(xí)之間關(guān)系的興趣。

特征值游戲超越了兩人間的零和游戲，其采用了更復(fù)雜的多玩家，正和博弈的設(shè)置。這使得算法具有了更好的并行性，從而可實現(xiàn)在更大數(shù)據(jù)集上的可擴(kuò)展性和速度優(yōu)勢。它還為機(jī)器學(xué)習(xí)研究者提供了一個可量化的基線，以測試新的多主體建模在更豐富的領(lǐng)域——如外交和足球上的應(yīng)用。

該文作者希望能經(jīng)由特征值游戲，鼓勵其他人探索設(shè)計算法、智能主體和智能系統(tǒng)的新方向。期待未來能找出還有什么其他問題，可以被定義為游戲。同時希望該研究能進(jìn)一步提高人們對多智能體的智能本質(zhì)的理解。

來源：

https://deepmind.com/blog/article/EigenGame

復(fù)雜科學(xué)最新論文

集智斑圖頂刊論文速遞欄目上線以來，持續(xù)收錄來自Nature、Science等頂刊的最新論文，追蹤復(fù)雜系統(tǒng)、網(wǎng)絡(luò)科學(xué)、計算社會科學(xué)等領(lǐng)域的前沿進(jìn)展。現(xiàn)在正式推出訂閱功能，每周通過微信服務(wù)號「集智斑圖」推送論文信息。掃描下方二維碼即可一鍵訂閱：

原標(biāo)題：《Deepmind最新成果：博弈論視角下的主成分分析》

閱讀原文