圖靈機就是深度學習最熱循環神經網路RNN？ 1996年論文證明！

1996年的8月19日至23日，芬蘭的瓦薩舉行了由芬蘭人工智慧協會和瓦薩大學組織的芬蘭人工智慧會議。

會議上發表的一篇論文證明：圖靈機就是一個循環神經網路。

沒錯，這是在26年前！

讓我們來看看，這篇發表在1996年的論文。

1 前言

1.1 神經網路分類

神經網路可用來分類任務，判斷輸入模式是否屬於特定的類別。

長期以來，人們都知道單層前饋網路只能用於對線性可分的模式進行分類，即連續層越多，類別的分佈就越複雜。

當在網路結構中引入回饋時，感知器輸出值會循環利用，連續層的數量原則上變成無限大。

算力有沒有質的提升？答案是肯定的。

例如，可以建構一個分類器來判斷輸入整數是否為質數。

事實證明，用於此目的的網路大小可以是有限的，即使輸入整數大小不受限制，可以正確分類的素數數量也是無限的。

在本文中，「由相同計算元素組成的循環網路結構」可用於完成任何（演算法上的）可計算功能。

1.2 關於可計算性

根據可計算性理論的基本公理，可以使用圖靈機實現可計算函數，有多種方法可以實現圖靈機。

定義程式語言。語言有四個基本運算：

這裡，V代表任何具有正整數值的變量， j代表任何行號。

可以證明，如果一個函數是圖靈可計算的，則可以使用這種簡單的語言對其進行編碼（有關詳細信息，請參見[1]）。

2 圖靈網路

2.1 遞歸神經網路結構

本文研究的神經網路由感知器組成，它們都具有相同的結構，感知器數q的運算可以定義為

#其中，當下時刻的感知器輸出（用表示）是使用n輸入計算的。

非線性函數f現在可定義為

這樣函數就可以簡單地「切斷」負值，感知器網路中的循環意味著感知器可以以複雜的方式組合。

#

圖1 遞歸神經網路的整體框架，結構自主無外部輸入，網路行為完全由初始狀態決定

在圖1中，遞歸結構顯示在一個通用框架中：現在和n是感知器的數量，從感知器p到感知器q的連接由（1）中的標量權重表示。

即給定初始狀態，網路狀態會迭代到不再發生變化，結果可以在該穩定狀態或網路的「固定點」下讀取。

2.2 神經網路建構

接下來闡述該程式##如何在感知器網路中實現。這個網路由以下節點（或感知器）組成：

• 對於程式中的每個變數V，都有一個變數節點 。
• 對於每個程式行i，都有一個指令節點。
• 對於第i行上的每個條件分支指令，另外還有兩個轉移節點和。

語言程式的實作包括感知器網路的以下變化：

• 對於程式中的每個變V，使用以下連結擴充網路：

• 如果程式碼的第i行沒有操作()，則使用下列連結擴充網路（假設該節點存在：

• 如果第i行有增量操作()，則如下擴充網路：

• 如果第i行有遞減運算()，則如下擴充網路：

• 如果第i行有條件分支(#)，則如下擴充網路：

2.3 等效性證明

現在需要證明的是，「網路的內部狀態或網路節點的內容」，可以用程式狀態來標識，同時網絡狀態的連續性與程序流對應。

定義網路的「合法狀態」如下：

• #至所有轉換節點和（如2.2所定義）的輸出為零(#);
• 至多一個指令節點有單位輸出()，所有其他指令節點都有零輸出，且
• ##變數節點具有非負整數輸出值。

如果所有指令節點的輸出都為零，則狀態最終狀態。一個合法的網路狀態可以直接解釋為一個程式「快照」－如果，程式計數器在第i行，對應的變數值儲存在變數節點中。

網路狀態的變化是由非零節點啟動的。

首先，專注於變數節點，事實證明它們表現為積分器，節點的先前內容被循環回同一節點。

從變數節點到其他節點的唯一連接具有負權重——這就是為什麼包含零的節點不會改變，因為非線性的原因（2）。

接下來，詳細說明指令節點。假設唯一的非零指令節點在時間k---這對應於程式計數器在程式碼中第i行。

若程式中第i行是#，則網路向前一步的行為可表示為（只顯示受影響的節點）

事實證明，新的網路狀態再次合法。與程式碼相比，這對應於程式計數器被轉移到第i 1行。

另一方面，如果程式中的第i行是#，則向前一步的行為是

##這樣，除了將程式計數器轉移到下一行之外，變數V的值也會遞減。如果第i行是

，網路的運算將是相同的，除了變數V的值增加。

第i行的條件分支操作（IF  GOTO j）啟動更複雜的操作序列：

最後，

事實證明，在這些步驟之後，網路狀態可以再次被解釋為另一個程式快照。

變數值已更改，token已轉移到新位置，就像執行了相應的程式行一樣。

如果token消失，網路狀態不再改變－這只有在程式計數器「超出」程式碼時才會發生，這表示程式終止。

網路的運行也類似對應程式的運行，證明完成。

3 修改

3.1 擴充功能

定義額外的串流指令很容易，這些指令可以讓程式設計更容易，並且產生的程式更具可讀性和執行速度。例如，

• 第i行的無條件分支（GOTO j）可以實作為
  
• 將常數c加入第i行的變數（#）可以實作為
  
• #行i上的另一個條件分支（IF V=0 GOTO j ）可以實現為
  
• 此外，可以同時評估各種遞增/遞減指令。假設要執行以下操作：。只需要一個節點：
  

上述方式絕對不是實作圖靈機的唯一途徑。

這是一個簡單的實現，在應用程式中不一定是最佳的。

3.2 矩陣制定

上述構造也可以以矩陣的形式實現。

基本概念是將變數值和「程式計數器」儲存在進程狀態s中，並讓狀態轉換矩陣A代表節點之間的連結。

矩陣結構的運算可以定義為離散時間的動態過程#

其中非線性向量值函數現在按元素定義，如（2）所示。

狀態轉移矩陣A的內容很容易從網路公式解碼出來－矩陣元素是節點之間的權重。

此矩陣公式類似於[3]中所提出的「概念矩陣」框架。

4 範例

假設要實作一個簡單的函數y=x，也就是說，輸入變數x的值應該傳遞給輸出變數y。使用語言可以將其編碼為（讓「入口點」現在不是第一行而是第三行）：

產生的感知器網路如圖2所示。

實線代表正連結（權重為1），虛線代表負連結（權重-1）。與圖1相比，重新繪製了網路結構，並透過在節點中整合延遲元件來簡化網路結構。

#圖2 簡單程式的網路實作

在矩陣形式中，上面的程式看起來像

#矩陣A中的前兩行/列對應於連接到代表兩個變數Y和X的節點的鏈接，接下來的三行代表三個程式行（1、2和3），最後兩個代表分支指令所需的附加節點（3 '和3''）。

然後是初始（迭代前）和最終（迭代後，找到固定點時）的狀態

#如果變數節點的值將嚴格保在0和1之間，則動態系統（3）的操作將是線性的，該函數根本沒有影響。

原則上，然後可以在分析中使用線性系統理論。

例如，在圖3中，顯示了狀態轉移矩陣A的特徵值。

即使在上面的例子中單位圓外有特徵值，非線性使得迭代總是穩定的。

事實證明，迭代總是在步驟之後收斂，其中。

#圖3 簡單程式的「特徵值」

5 討論

5.1 理論方面

#結果表明，圖靈機可以編碼為感知器網路。

根據定義，所有可計算函數都是圖靈可計算的－在可計算性理論的框架內，不存在更強大的計算系統。

這就是為什麼，可以得出結論－

#循環感知器網路（如上圖）是圖靈機的（又一種）形式。

這種等價的好處是可計算性理論的結果很容易取得－例如，給定一個網路和一個初始狀態，就不可能判斷這個過程最終是否會停止。

上述理論等價性並沒有說明計算效率的任何資訊。

與傳統的圖靈機實作（實際上是今天的電腦）相比，網路中發生的不同機制可以使一些功能在這個框架中更好地實現。

 至少在某些情況下，例如，一個演算法的網路實作可以透過允許snapshot向量中的多個「程式計數器」來被並行化。

網路的運作是嚴格本地的，而不是全域的。

一個有趣的問題出現了，例如，是否可以在網路環境中更有效地攻擊NP完全問題！

與語言相比，網路實作有以下「擴充」：

• ##變數可以是連續的，而不僅僅是整數值。實際上，呈現現實數的（理論）能力使網路實現比語言更強大，所有以語言呈現的數字都是有理數。
• 可以同時存在各種「程式計數器」，並且控制的轉移可能是「模糊的」，這意味著指令節點提供的程式計數器值可能是非整數。
• 一個較小的擴充功能是可自由定義的程式入口點。這可能有助於簡化程序——例如，變數的複製在上面的三個程式行中完成，而名義解決方案（參見[1]）需要七行和一個額外的局部變數。

與原始程式碼相比，矩陣公式顯然是比程式碼更「連續」的資訊表示形式－可以（經常）修改參數，而迭代結果不會突然改變。

這種「冗餘」也許可以在某些應用中使用。

例如，當使用遺傳演算法（GA）進行結構最佳化時，可以使遺傳演算法中使用的隨機搜尋策略更有效率：在系統結構發生變化後，可以搜尋連續成本函數的局部最小值使用一些傳統技術（參見[4]）。

透過範例學習有限狀態機結構，如[5]所述，可以知道：在這種更複雜的情況下也採用迭代增強網路結構的方法。

不僅神經網路理論可能受益於上述結果——僅看動態系統公式（3），很明顯，在可計算性理論領域發現的所有現像也都以簡單的形式存在－尋找非線性動態過程。

例如，停機問題的不可判定性是系統論領域的一個有趣貢獻：對於任何表示為圖靈機的決策過程，都存在形式（3）的動態系統，它違背了這個過程——對於例如，無法建立通用的穩定性分析演算法。

5.2 相關工作

所呈現的網路結構與遞歸來Hopfield神經網路範式之間存在一些相似之處（例如，參見[2]）。

在這兩種情況下，「輸入」都被編碼為網路中的初始狀態，「輸出」在迭代後從網路的最終狀態中讀取。

Hopfield網路的固定點是預先編程的模式模型，輸入是「雜訊」模式－此網路可用於增強損壞的模式。

中非線性函數的展望（2）使得上述「圖靈網路」中可能的狀態數是無限的。

與單元輸出始終為-1或1的Hopfield網路相比，可以看出，理論上，這些網路結構有很大不同。

例如，雖然Hopfield網路中的穩定點集是有限的，但以圖靈網路為代表的程式通常具有無限數量的可能結果。

Hopfield網路的運算能力在[6]中進行了討論。

Petri網是基於事件和並發系統建模的強大工具[7]。

Petri網由位元和轉移以及連接它們的弧組成。每個地方可能包含任意數量的token，token的分佈稱為Petri網的標記。

如果轉換的所有輸入位置都被標記佔用，則轉換可能會觸發，從每個輸入位置刪除一個標記，並向其每個輸出位置新增一個標記。

可以證明，具有附加抑制弧的擴展Petri網也具有圖靈機的能力（參見[7]）。

上述圖靈網與Petri網的主要區別在於Petri網的框架更為複雜，具有專門定制的結構，不能用簡單的一般形式（3）來表達。

參考

#1 Davis, M. and Weyuker, E.: Computability, Complexity, and Languages---Fundamentals of Theoretical Computer Science. Academic Press, New York, 1983.

2 Haykin, S.: Neural Networks. A Comprehensive Foundation. Macmillan College Publishing, New York, 1994.

3 Hyötyniemi, H.: Correlations---Building Blocks of Intelligence? In Älyn ulottuvuudet ja oppliistoria (History and dimensions of intelligence), Finnudet ja oppliistoria (History and dimensions of intelligence), Finnish Artificial, Intelgence Society 1995, pp. 199--226.

4 Hyötyniemi, H. and Koivo, H.: Genes, Codes, and Dynamic Systems. In Proceedings of the Second Nordic Workshop on Genetic Algorithms (NWGA'96), Vaasa, Finland, August 19--23, 1996.

##5 Manolios, P. and Fanelli, R.: First-Order Recurrent Neural Networks and Deterministic Finite State Automata. Neural Computation 6, 1994, pp. 1155--1173.

##6 Orponen, P.: The Computational Power of Discrete Hopfield Nets with Hidden Units. Neural Computation 8, 1996 , pp. 403--415.

7 Peterson, J.L.: Petri Net Theory and the Modeling of Systems. Prentice--Hall, Englewood Cliffs, New Jersey, 1981.

參考資料：

#https://www.php.cn/link/ 0465a1824942fac19824528343613213##

以上是圖靈機就是深度學習最熱循環神經網路RNN？ 1996年論文證明！的詳細內容。更多資訊請關注PHP中文網其他相關文章！