探秘武当山美景，身临其境的感受不容错过！

Qkeaikatongzaizhenggeguochengzhongdedonghuafengge，shininkeyigengzhiguandiganshoudaoQbudingderouruanliuchangdetuxiang。mianfeipingmuluzhizhuanjia。buyongdanxinlupingshijian。luzhiwanchenghou，keyidaochuhuofenxianggeihaoyou。meigeguankazhiyouboguaiwu，suipianshijianjiukeyiwandehenguoyinla。zengjialetilidejizhi，dangnichuangguanshibaideqingkuang，huiyingxiangnidepaiming。yingxiongyangcheng：zhaomushengxingqianghuadengzhunichuangtianxia圖(tu)靈(ling)機(ji)就(jiu)是(shi)深(shen)度(du)學(xue)習(xi)最(zui)熱(re)循(xun)環(huan)神(shen)經(jing)網(wang)絡(luo)RNN？1996年(nian)論(lun)文(wen)就已(yi)證(zheng)明(ming)！

新(xin)智(zhi)元(yuan)報(bao)道(dao)

編(bian)輯(ji)：Aeneas Joey

【新智元導(dao)讀(du)】這(zhe)幾(ji)位(wei)科(ke)学家(jia)在(zai)1996年對(dui)图灵机進(jin)行(xing)的(de)论证，拿(na)到(dao)今(jin)天(tian)來(lai)看(kan)也(ye)是值(zhi)得(de)深思(si)的。

1996年的8月(yue)19日(ri)至(zhi)23日，芬(fen)蘭(lan)的瓦(wa)薩(sa)舉(ju)行了(le)由(you)芬兰人(ren)工(gong)智能(neng)協(xie)會(hui)和(he)瓦萨大(da)学組(zu)織(zhi)的芬兰人工智能会議(yi)。

会议上(shang)發(fa)表(biao)的壹(yi)篇(pian)论文证明：图灵机就是一個(ge)循环神经网络。

沒(mei)錯(cuo)，这是在26年前(qian)！

讓(rang)我(wo)們(men)来看一看，这篇发表於(yu)1996年的论文。

1 前言(yan)

1.1 神经网络分(fen)類(lei)

神经网络可(ke)用(yong)于分类任(ren)務(wu)，判(pan)斷(duan)輸(shu)入(ru)模(mo)式(shi)是否(fou)屬(shu)于特(te)定(ding)的类別(bie)。

長(chang)期(qi)以(yi)来，人们都(dou)知(zhi)道單(dan)層(ceng)前饋(kui)网络只(zhi)能用于对線(xian)性(xing)可分的模式进行分类，即(ji)連(lian)續(xu)层越(yue)多(duo)，类的分布(bu)就越復(fu)雜(za)。

當(dang)在网络結(jie)構(gou)中(zhong)引(yin)入反(fan)馈時(shi)，感(gan)知器(qi)输出(chu)值被(bei)循环利(li)用，连续层的數(shu)量(liang)原(yuan)則(ze)上變(bian)為(wei)無(wu)限(xian)大。

算(suan)力(li)有(you)没有質(zhi)的提(ti)升(sheng)？答(da)案(an)是肯(ken)定的。

例(li)如(ru)，可以构造(zao)一个分类器来判断输入整(zheng)数是否为素(su)数。

事(shi)實(shi)证明，用于此(ci)目(mu)的的网络大小(xiao)可以是有限的，即使(shi)输入整数大小不(bu)受(shou)限制(zhi)，可以正(zheng)確(que)分类的素数数量也是无限的。

在本(ben)文中，「由相(xiang)同(tong)計(ji)算元素组成(cheng)的循环网络结构」可用于完(wan)成任何(he)（算法(fa)上的）可计算功(gong)能。

1.2 關(guan)于可计算性

根(gen)據(ju)可计算性理(li)论的基(ji)本公(gong)理，可以使用图灵机实現(xian)可计算函(han)数，有多種(zhong)方(fang)法可以实现图灵机。

定義(yi)程(cheng)序(xu)語(yu)言。該(gai)语言有四(si)种基本操(cao)作(zuo)：

这裏(li)， V代(dai)表任何具(ju)有正整数值的变量， j代表任何行號(hao)。

可以证明，如果(guo)一个函数是图灵可计算的，则可以使用这种簡(jian)单的语言对其(qi)进行编碼(ma)（有关詳(xiang)細(xi)信(xin)息(xi)，請(qing)參(can)見(jian)[1]） 。

2 图灵网络

2.1 遞(di)歸(gui)神经网络结构

本文研(yan)究(jiu)的神经网络由感知器组成，它(ta)们都具有相同的结构，感知器数 q的運(yun)算可以定义为

其中，当前时刻(ke)的感知器输出（用表示(shi)）是使用 n输入 计算的。

非(fei)线性函数 f现在可定义为

这樣(yang)函数就可以简单地(di)「切(qie)断」負(fu)值，感知器网络中的循环意(yi)味(wei)著(zhe)感知器可以以复杂的方式组合(he)。

图1 递归神经网络的整體(ti)框(kuang)架(jia)，结构自(zi)主(zhu)无外(wai)部(bu)输入，网络行为完全(quan)由初(chu)始(shi)狀(zhuang)態(tai)決(jue)定

在图1中，递归结构顯(xian)示在一个通(tong)用框架中：现在和 n是感知器的数量，從(cong)感知器p到感知器q的连接(jie)由（1）中的 標(biao)量權(quan)重(zhong)表示。

即給(gei)定初始状态，网络状态会叠(die)代到不再(zai)发生(sheng)变化(hua)，结果可以在该穩(wen)定状态或(huo)网络的 「固(gu)定點(dian)」下(xia)读取(qu)。

2.2 神经网络建(jian)构

接下来闡(chan)述(shu)该程序如何在感知器网络中实现。该网络由以下節(jie)点（或感知器）组成：

对于程序中的每(mei)个变量 V，都有一个变量节点 。

对于每个程序行 i，都有一个指(zhi)令(ling)节点 。

对于第(di) i行上的每个條(tiao)件(jian)分支(zhi)指令，另(ling)外還(hai)有兩(liang)个轉(zhuan)移(yi)节点 和 。

语言程序的实现包(bao)括(kuo)感知器网络的以下变化：

对于程序中的每个变 V，使用以下鏈(lian)接擴(kuo)充(chong)网络：

如果程序代码的第 i行没有操作( )，则使用以下链接扩充网络（假(jia)設(she)该节点 存(cun)在：

如果第 i行有增(zeng)量操作( )，则按(an)如下方式扩充网络：

如果第 i行有递減(jian)操作( )，则按如下方式扩充网络：

如果第 i行有条件分支( )，则按如下方式扩充网络：

2.3 等(deng)效(xiao)性证明

现在需(xu)要(yao)证明的是，「网络的內(nei)部状态或网络节点的内容(rong)」，可以用程序状态来标識(shi)，同时网络状态的连续性與(yu)程序流(liu)对應(ying)。

定义网络的「合法状态」如下：

至所(suo)有转換(huan)节点和（如2.2中所定义）的输出为零(ling)()；

至多一个指令节点有单位输出()，所有其他(ta)指令节点有零输出，並(bing)且(qie)

变量节点具有非负整数输出值。

如果所有指令节点的输出均(jun)为零，则状态 最終(zhong)状态。一个合法的网络状态可以直(zhi)接解(jie)釋(shi)为一个程序「快(kuai)照(zhao)」——如果 ，程序计数器在第 i行，相应的变量值存儲(chu)在变量节点中。

网络状态的变化是由非零节点激(ji)活(huo)的。

首(shou)先(xian)，关註(zhu)变量节点，事实证明它们表现为積(ji)分器，节点的先前内容被循环回(hui)同一节点。

从变量节点到其他节点的唯(wei)一连接具有负权重——这就是为什(shen)麽(me)包含(han)零的节点不会改(gai)变，因(yin)为非线性的原因（2）。

接下来，详细說(shuo)明指令节点。假设唯一的非零指令节点在时間(jian) k---这对应于程序计数器在程序代码中第 i行。

若(ruo)程序中第 i行是 ，则网络向(xiang)前一步(bu)的行为可表示为（只显示受影(ying)響(xiang)的节点）

事实证明，新的网络状态再次(ci)合法。与程序代码相比(bi)，这对应于程序计数器被转移到第 i+1行。

另一方面(mian)，如果程序中的第 i行是 ，则向前一步的行为是

这样，除(chu)了將(jiang)程序计数器转移到下一行之(zhi)外，变量 V的值也会递减。如果第 i行是

，网络的操作将是相同的，除了变量 V的值增加(jia)。

第 i行的条件分支操作（IF GOTO j）激活更(geng)复杂的操作序列(lie)：

最後(hou)，

事实证明，在这些(xie)步驟(zhou)之后，网络状态可以再次被解释为另一个程序快照。

变量值已更改，token已转移到新位置(zhi)，就像(xiang)執(zhi)行了相应的程序行一样。

如果token消(xiao)失(shi)，网络状态不再改变——这只有在程序计数器「超(chao)出」程序代码时才(cai)会发生，这意味着程序终止(zhi)。

网络的运行也类似(si)对应程序的运行，证明完成。

3 修(xiu)改

3.1 扩展(zhan)

定义額(e)外的流线型(xing)指令很(hen)容易(yi)，这些指令可以使编程更容易，并且生成的程序更具可读性和执行速(su)度。例如，

第 i行的无条件分支（GOTO j）可以实现为

将常(chang)量c添(tian)加到第 i行的变量（ ） 可以实现为

行 i上的另一种条件分支（IF V=0 GOTO j）可以实现为

此外，可以同时評(ping)估(gu)各(ge)种递增/递减指令。假设要执行以下操作：。只需要一个节点：

上述方式絕(jue)不是实现图灵机的唯一途(tu)徑(jing)。

这是一个简单的实现，在应用程序中不一定是最佳(jia)的。

3.2 矩(ju)陣(zhen)制定

上述构造也可以以矩阵的形(xing)式实现。

基本思想(xiang)是将变量值和「程序计数器」存储在进程状态 s中，并让状态转换矩阵 A代表节点之间的链接。

矩阵结构的运算可以定义为一个離(li)散(san)时间的動(dong)态過(guo)程

其中非线性向量值函数现在按元素定义，如（2）中所示。

状态转移矩阵 A的内容很容易从网络公式中解码出来——矩阵元素是节点之间的权重。

该矩阵公式类似于[3]中提出的「概(gai)念(nian)矩阵」框架。

4 例子(zi)

假设要实现一个简单的函数 y=x，也就是说，输入变量 x的值应该傳(chuan)递给输出变量 y。使用语言 可以将其编码为（让「入口(kou)点」现在不是第一行而(er)是第三(san)行）：

生成的感知器网络如图2所示。

实线代表正连接（权重为 1），虛(xu)线代表负连接（权重 -1）。与图1相比，重新繪(hui)制了网络结构，并通过在节点中集(ji)成延(yan)遲(chi)元件来简化网络结构。

图2 简单程序的网络实现

在矩阵形式中，上面的程序看起(qi)来像

矩阵A中的前两行/列对应于连接到代表两个变量 Y和 X的节点的链接，接下来的三行代表三个程序行（1、2和3），最后两个代表分支指令所需的附(fu)加节点（3'和3''）。

然(ran)后是初始（迭代前）和最终（迭代后，找(zhao)到固定点时）的状态

如果变量节点的值将嚴(yan)格(ge)保(bao)在0和1之间，则动态系(xi)統(tong)（3）的操作将是线性的，该函数根本没有影响。

原则上，然后可以在分析(xi)中使用线性系统理论。

例如，在图3中，示出了状态转移矩阵 A的特征(zheng)值。

即使在上面的例子中单位圓(yuan)外有特征值，非线性使得迭代總(zong)是稳定的。

事实证明，迭代总是在步骤之后收(shou)斂(lian)，其中。

图3 简单程序的「特征值」

5 討(tao)论

5.1 理论方面

结果表明，图灵机可以编码为感知器网络。

根据定义，所有可计算函数都是图灵可计算的——在可计算性理论的框架内，不存在更強(qiang)大的计算系统。

这就是为什么，可以得出结论——

循环感知器网络（如上所示）是图灵机的（又(you)一种）形式。

这种等價(jia)的好(hao)處(chu)是可计算性理论的结果很容易獲(huo)得——例如，给定一个网络和一个初始状态，就不可能判断这个过程最终是否会停(ting)止。

上述理论等价性并没有说明计算效率(lv)的任何信息。

与传统的图灵机实现（实際(ji)上是今天的计算机）相比，网络中发生的不同机制可以使一些功能在这个框架中更好地实现。

至少(shao)在某(mou)些情(qing)況(kuang)下，例如，一个算法的网络实现可以通过允(yun)許(xu)snapshot向量中的多个「程序计数器」来被并行化。

网络的运行是严格本地的，而不是全局(ju)的。

一个有趣(qu)的問(wen)題(ti)出现了，例如，是否可以在网络环境(jing)中更有效地攻(gong)擊(ji)NP完全问题！

与语言相比 ，网络实现具有以下 「扩展」：

与原始程序代码相比，矩阵公式显然是比程序代码更 「连续」的信息表示形式——可以（经常）修改参数，而迭代结果不会突(tu)然改变。

这种 「冗(rong)余(yu)」也许可以在某些应用中使用。

例如，当使用遺(yi)传算法（GA）进行结构優(you)化时，可以使遗传算法中使用的隨(sui)机搜(sou)索(suo)策(ce)略(lve)更加高(gao)效：在系统结构发生变化后，可以搜索连续成本函数的局部最小值使用一些传统技(ji)術(shu)（参见[4]）。

通过示例学习有限状态机结构，如[5]中所述，可以知道：在这种更复杂的情况下也采(cai)用迭代增强网络结构的方法。

不仅神经网络理论可能受益(yi)于上述结果——仅看动态系统公式（3），很明显，在可计算性理论領(ling)域(yu)发现的所有现象(xiang)也都以简单的形式存在——尋(xun)找非线性动态过程。

例如，停机问题的不可判定性是系统论领域的一个有趣貢(gong)獻(xian)：对于任何表示为图灵机的决策过程，都存在形式（3）的动态系统，它違(wei)背(bei)了这个过程——对于例如，无法构建通用的稳定性分析算法。

5.2 相关工作

所呈现的网络结构与递归来Hopfield神经网络範(fan)式之间存在一些相似之处（例如，参见[2]）。

在这两种情况下， 「输入」都被编码为网络中的初始状态， 「输出」在迭代后从网络的最终状态中读取。

Hopfield网络的固定点是預(yu)编程的模式模型，输入是 「噪(zao)聲(sheng)」模式——该网络可用于增强損(sun)壞(huai)的模式。

中非线性函数的展望(wang)（2）使得上述 「图灵网络」中可能的状态数量是无限的。

与单元输出始终为-1或1的Hopfield网络相比，可以看出，理论上，这些网络结构有很大不同。

例如，雖(sui)然Hopfield网络中的稳定点集是有限的，但(dan)以图灵网络为代表的程序通常具有无限数量的可能结果。

Hopfield网络的计算能力在[6]中进行了讨论。

Petri网是基于事件和并发系统建模的强大工具[7]。

Petri网由位和转移以及(ji)连接它们的弧(hu)组成。每个地方可能包含任意数量的token，token的分布稱(cheng)为Petri网的标記(ji)。

如果转换的所有输入位置都被标记占(zhan)用，则转换可能会觸(chu)发，从每个输入位置刪(shan)除一个标记，并向其每个输出位置添加一个标记。

可以证明，具有附加抑(yi)制弧的 扩展Petri网也具有图灵机的能力（参见[7]）。

上述图灵网与Petri网的主要區(qu)别在于Petri网的框架更为复杂，具有專(zhuan)門(men)定制的结构，不能用简单的一般(ban)形式（3）来表達(da)。

参考(kao)

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 oppihistoria (History and dimensions of intelligence), Finnish Artificial Intelligence 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.

参考資(zi)料(liao)：

http://users.ics.aalto.fi/tho/stes/step96/hyotyniemi1/返(fan)回搜狐(hu)，查(zha)看更多

責(ze)任编辑：