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

導(dǎo)語(yǔ)

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

Brian McWilliams、Ian Gemp、Claire Vernade | 作者

郭瑞東 | 譯者

趙雨亭 | 審校

鄧一雪 | 編輯

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

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

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

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

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

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

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

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

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

圖2. 臉書(shū)頁(yè)面通過(guò)特征值游戲聚類(lèi)的可視化，來(lái)源：EigenGame Unloaded When playing games is better than optimizing Fig 7

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

來(lái)源：

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

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

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

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

閱讀原文