把Transformer當通用計算機用，還能執行in-context learning演算法，這項研究腦洞大開

Transformer 已成為各種機器學習任務的熱門選擇，並且取得了很好的效果，那它還能怎麼用？腦洞大開的研究者竟然想用它來設計可程式計算機！

這篇論文的作者來自普林斯頓大學和威斯康辛大學，標題為《Looped Transformers as Programmable Computers》，旨在探索如何用Transformer 來實作通用計算機。

具體來說，作者提出了一個將 transformer 網路用作通用電腦的框架，方法是使用特定權重對它們進行編程並將它們置於循環（loop）中。在這個框架中，輸入序列充當穿孔卡片，由指令和用於資料讀取 / 寫的記憶體組成。

作者證明了恆定數量的編碼器層可以模擬基本計算區塊。使用這些構建塊，他們模擬了一個小型指令集計算機。這使得他們能夠將迭代演算法映射到可以由循環的（looped）13 層 transformer 執行的程式。他們展示了這個 transformer 如何在其輸入的指導下模擬一個基本的計算器、一個基本的線性代數函式庫和使用反向傳播的 in-context learning 演算法。這項工作突出了注意力機制的多功能性，並證明即使是淺層 transformer 也可以執行成熟的通用程序。

論文概述

Transformer (TF) 已成為各種機器學習任務的熱門選擇，它在自然語言處理和電腦視覺等領域很多問題上取得了最先進的成果。 Transformer 成功的關鍵原因是能夠透過注意力機制捕捉 higher-order 關係和 long-range 依賴關係。這使得 TF 可以對上下文資訊進行建模，並使其在機器翻譯和語言建模等任務中更加有效，在這些任務中 Transformer 的表現一直優於其它方法。

GPT-3（175B 參數）和 PaLM（540B 參數）等具有數千億參數的語言模型在許多自然語言處理任務上都取得了最先進的效能。有趣的是，這些大型語言模型 (LLM) 中的一些還可以執行 in-context learning (ICL) ，根據簡短 prompt 和一些範例即時適應和執行特定任務。 LLM 的 ICL 能力是在沒有可以訓練的情況下就具備，並允許這些大型模型有效地執行新任務而無需更新權重。

 令人驚訝的是，透過ICL，LLM 可以執行演算法任務和推理，並且[Nye et al. [2021], Wei et al. [2022c], Lewkowycz et al . [2022], Wei et al. [2022b], Zhou et al. [2022]] 等人的工作已經證明其可行性。 [Zhou et al. [2022] ] 等的工作證明，當給出多位加法演算法和一些加法範例的 prompt 時，LLM 可以成功地對未知用例進行加法運算。這些結果表明，LLM 可以根據演算法原理並在推理時對給定輸入執行 pre-instructed 的命令，就好像將自然語言解釋為程式碼一樣。

 有證據表明，Transformer 可以模擬具有足夠深度的圖靈機或Attention 層之間的遞歸連結[Pérez et al. [2021], Pérez et al. [2019], Wei et al. [2022a]]。這證明了 Transformer 網路精確遵循輸入指定的演算法指令的潛力。然而，這些構造相對籠統，無法深入理解如何創建能夠執行特定演算法任務的 Transformer。

然而更專業的設計可以讓 TF 執行更高階的程式。如 [Weiss et al. [2021]] 設計了一種計算模型和一種程式語言，可將簡單的選擇和聚合命令對應到索引輸入 token。這種語言可用於創建多種有趣的演算法，例如 token 計數、排序、建立直方圖和識別 Dyck-k 語言。然後可以將用受限存取序列處理語言 (RASP) 編寫的程式對應到 Transformer 網路中，Transformer 網路的大小通常會隨著程式的大小而變化。

 另一項研究展示了選擇Transformer 模型權重的方法，以用作動態學習線性回歸模型的最佳化演算法，在給定訓練資料作為輸入時在推理時執行隱式訓練。這些方法通常需要與學習演算法的迭代次數成比例的層數，並且僅限於一個損失函數和模型集合。

對 Transformer 模型進行編程以模擬圖靈機的抽象計算的能力、RASP 等語言的專用命令以及 ICL 的特定演算法，突出了 Transformer 網路作為多功能可編程電腦的潛力。

本文作者的研究旨在研究探索這一充滿希望的前景，揭示 Attention 機制如何能夠模擬受指令集架構啟發的通用電腦。

將Transformer 作為可編程計算機

在本文中，作者展示了Transformer 網路可以透過使用特定權重對它們進行硬編碼並將它們置於一個循環中來模擬複雜的演算法和程式。作者透過對 Attention 進行逆向工程來模擬基本計算區塊來做到這一點，例如對輸入序列的編輯操作、非線性函數、函數呼叫、程式計數器和條件分支。作者的論文證明了使用單一循環或遞歸將 Transformer 的輸出序列連接回其輸入的重要性，從而避免對深度模型的需求。

#論文網址：https://arxiv.org/pdf/2301.13196.pdf

#作者透過設計一個Transformer 來實現這一點，該Transformer 可以執行以單一指令的通用版本編寫的程序，稱為SUBLEQ (A,B,C)，即如果小於或等於零，則相減併分支。 SUBLEQ 是一種單一指令語言，定義了單一指令集電腦（one-instruction set computer，簡寫為 OISC）。 SUBLEQ 由 3 個記憶體位址運算元組成，執行時以記憶體位址 B 的值減去記憶體位址 A 的值，結果存入 B。如果 B 的結果小於等於 0，則跳到位址 C，否則繼續下一條指令。但這條指令能夠定義通用計算機。

作者建構了實作類似SUBLEQ 程式的明確Transformer，作者稱為FLEQ 的更靈活的單一指令，其形式為

其中f_m 可以從一組函數（矩陣乘法/ 非線性函數/ 多項式等）中選擇，可以將其硬編碼到網路中。可以執行 FLEQ 程式的循環 Transformer 的深度不依賴程式的深度或程式碼的行數，而是取決於實作單一 FLEQ 指令所需的深度，這是不變的。這是透過在輸入序列上循環運行 Transformer 來實現的，類似於 CPU 的運作方式。

作者使用這個框架，展示了在推理時模擬各種函數的能力，包括一個基本的計算器、一個基本的線性代數庫（矩陣轉置、乘法、求逆、冪迭代）和在隱式完全連接網路上實現反向傳播的ICL。輸入序列或 prompt 可當成穿孔卡片，包括 Transformer 需要執行的指令，同時為儲存和處理程序中使用的變數提供空間。用於執行這些程序的 Transformer 網路的深度都小於或等於 13，並且提供了所有這些模型的權重矩陣。下面的定理總結了作者的主要發現：

定理1：存在一個少於13 層的循環Transformer，它可以模擬通用計算機（文章第5 節）、基本計算器（文章第7 節）、數值線性代數方法，如近似矩陣逆和冪迭代（文章第8 節），以及基於神經網路的ICL 演算法（如SGD）（文章第9 節）。

#圖1：循環Transformer 架構示意圖，其中輸入序列儲存指令，從中讀取/ 寫入資料的記憶體以及儲存中間結果的暫存器。輸入由網路處理，輸出用作新輸入，允許網路迭代更新隱式狀態並執行複雜計算。

作者的研究強調了 Attention 機制的靈活性和單循環的重要性，這使得設計可以模擬複雜迭代演算法和執行通用程式的模型成為可能。並進一步證明了 Transformer 模型高效執行複雜數學和演算法任務的能力。可以想像，現代 Transformer (如 GPT-3)，在執行各種任務時使用類似的內部子程式。在某種程度上，當給出上下文範例和說明時，可以啟發這些模型特定技巧或演算法的能力，類似於函數呼叫。然而，應該謹慎對待這個假設，因為作者設計結構的方式與現實世界語言模型的訓練方式沒有任何相似之處。

作者希望他們的研究能鼓勵進一步研究 Attention 機制的潛力，以及語言模型執行演算法指令的能力。作者提出的設計可以幫助確定執行特定演算法任務所需的最小 Transformer 網路規模。此外，作者還希望其發現有助於啟發開發方法，從而透過利用更小的、逆向工程的 Transformer 網路來完成特定的演算法任務，從而增強訓練語言模型的能力。

建構通用計算的 Transformer 模組

 要使用 Transformer 網路建構通用計算框架，需要專門的計算區塊。將這些區塊組裝來創建所需的最終功能。以下重點介紹 Transformer 層可以執行的各種操作。這些操作將為創建更複雜的例程和演算法提供基礎。這些操作的目的是彼此可互通，利用 Attention 執行各種任務的能力，例如產生近似置換矩陣和透過 sigmoid 函數逼近一般函數。

#圖2: 用作實作小型指令集電腦建構塊的三個Transformer 區塊的示意圖。這些區塊處理輸入序列中的編輯操作（例如從一個區塊移動或複製到另一個區塊），追蹤程式計數器，並在滿足指定條件時執行程式計數器跳轉。

位置編碼、程式計數器與資料指標

##Transformer 通常需要執行迭代演算法或執行一系列命令。為實現這一點，作者使用一個循環存取命令的程式計數器。計數器包含儲存下一個命令的位置的編碼。此外，命令可能具有指向命令需要讀取和寫入的資料位置的資料指標。程式計數器和資料指標都使用與前一段中討論的相同的位置編碼。

作者的位置編碼方案也可用於指向特定資料位置以進行讀取或寫入，這將在下一節論述。這是透過使用相同的二進位向量作為程式計數器和資料指標的位置編碼來實現的。此外，這種指向特定資料位置的技術使 Transformer 能夠在執行演算法或建置以實現的命令序列期間有效地讀取 / 寫入資料。

讀取/ 寫入：將資料、指令複製到暫存器或從暫存器取出

圖3: 讀取操作的示意圖。箭頭顯示從指派給暫存器命令的輸入部分複製的命令區塊。一條指令是一組指標。位置編碼和計數器用於追蹤什麼內容被複製到哪裡。

下面的引理說明，程式計數器指向的命令或目前命令中指定位置的資料可以複製到暫存器以供進一步計算。程式計數器的位置通常位於暫存器內容的正下方，但可以任意變更。在整個計算過程中將其保持在特定位置有助於保持結構的良好組織。

下一個引理解釋了儲存在暫存器中的向量 v 可以複製到記憶體中的指定位置，如暫存器本身所指定的。這允許將資料從暫存器傳輸到記憶體中的特定位置以供進一步使用或儲存。

圖 4: 寫入操作的示意圖。箭頭顯示資料區塊正在從暫存器複製到分配給記憶體的輸入部分中的指定位置。位置編碼用於追蹤目標位置並確保資料寫入正確的記憶體位置。

#條件分支

#在這一部分，作者實作一個條件分支指令，該指令評估條件並在條件為真時將程式計數器設定到指定位置，或在條件為假時將程式計數器遞增1。 

指令的形式如下：如果 mem [a]≤0，則前往 i，其中 mem [a] 是輸入序列的記憶體部分中某個位置的值。這個指令有兩個部分：判斷不等式和修改程式計數器。

模擬通用單一指令集電腦

SUBLEQ Transformer

Mavaddat 和Parhami 早在1988年已經證明存在一條指令，任何電腦程式都可以轉換為由這條指令的實例化所組成的程式。這種指令的變體是 SUBLEQ，能存取不同的暫存器或記憶體位置。

SUBLEQ 的運作方式很簡單。它存取記憶體中的兩個暫存器，取得它們內容的差異並將其儲存回其中一個暫存器，然後如果結果為負，則它跳到不同的預定義程式碼行，或繼續執行目前行的下一條指令。為執行 SUBLEQ 程式而建構的計算機稱為單指令集計算機，並且是通用計算機，即，如果可以訪問無限內存，它就是圖靈完備的。

下面描述了一個循環 Transformer 的構造，它可以執行用特定指令集寫的程式。 Transformer 追蹤程式碼行、記憶體位置和程式計數器，將輸入的記憶體部分用作記憶體暫存器，將指令部分用作程式碼行 / 指令。暫存器用於記錄每條指令涉及的加法和指針，讀取、寫入、條件分支操作等。

#圖 5: 實作 OISC 指令區塊的圖形表示。前兩個區塊將資料 / 指令傳送到暫存器，第二個和第三個執行減法並儲存結果，而最後一個執行完成指令的 if goto 指令。

FLEQ：更靈活的Attention 為基礎的電腦

##在這一節，作者對FLEQ進行介紹，它是對SUBLEQ 的推廣，它定義了一種更靈活的精簡指令集電腦。這一隱含的附加指令集基於 SUBLEQ 的更高級版本，允許在同一 Transformer 網路中實現多種功能。作者使用術語 FLEQ 來指稱指令、語言和它定義的基於 Attention 的電腦。

FLEQ 的設計允許透過產生比簡單減法更通用的函數來實現複雜的演算法，如矩陣乘法、平方根計算、激活函數等。

 基於 Attention 的電腦執行週期。在循環 Transformer 的每次迭代中，根據程式計數器從輸入中的指令集中提取一條指令。然後指令被複製到暫存器。根據要實現的功能，使用不同的功能塊位置在局部記錄該功能的結果。一旦計算出結果，它就會被複製回指令提供的指定記憶體位置。

執行週期類似於上一節中的單指令集計算機(OISC)，主要區別在於，對於每個指令，可以從預先選擇的函數列表中進行選擇，這些函數以任意數組的形式輸入，如矩陣、向量和標量。

輸入序列的格式。如圖 6 所示，循環 Transformer 的輸入 X，它可以執行一系列 FLEQ 指令構成的程式（X 由暫存器、記憶體、指令等三部分構成）。

基於 Transformer 的功能塊的格式。每個功能塊都位於輸入 X 的左下方部分，如圖 6 所示。

#####圖6:執行FLEQ 指令的輸入X 的結構########################### ######更多技術細節和範例請參閱原始論文。 ######

以上是把Transformer當通用計算機用，還能執行in-context learning演算法，這項研究腦洞大開的詳細內容。更多資訊請關注PHP中文網其他相關文章！