图灵机就是深度学习最热循环神经网络RNN?1996年论文就已证明(1)

简介: 图灵机就是深度学习最热循环神经网络RNN?1996年论文就已证明

【新智元导读】这几位科学家在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月前
|
机器学习/深度学习 数据可视化 算法
PyTorch生态系统中的连续深度学习:使用Torchdyn实现连续时间神经网络
神经常微分方程(Neural ODEs)是深度学习领域的创新模型,将神经网络的离散变换扩展为连续时间动力系统。本文基于Torchdyn库介绍Neural ODE的实现与训练方法,涵盖数据集构建、模型构建、基于PyTorch Lightning的训练及实验结果可视化等内容。Torchdyn支持多种数值求解算法和高级特性,适用于生成模型、时间序列分析等领域。
229 77
PyTorch生态系统中的连续深度学习:使用Torchdyn实现连续时间神经网络
|
2月前
|
机器学习/深度学习 人工智能 算法
基于Python深度学习的【害虫识别】系统~卷积神经网络+TensorFlow+图像识别+人工智能
害虫识别系统,本系统使用Python作为主要开发语言,基于TensorFlow搭建卷积神经网络算法,并收集了12种常见的害虫种类数据集【"蚂蚁(ants)", "蜜蜂(bees)", "甲虫(beetle)", "毛虫(catterpillar)", "蚯蚓(earthworms)", "蜚蠊(earwig)", "蚱蜢(grasshopper)", "飞蛾(moth)", "鼻涕虫(slug)", "蜗牛(snail)", "黄蜂(wasp)", "象鼻虫(weevil)"】 再使用通过搭建的算法模型对数据集进行训练得到一个识别精度较高的模型,然后保存为为本地h5格式文件。最后使用Djan
147 1
基于Python深度学习的【害虫识别】系统~卷积神经网络+TensorFlow+图像识别+人工智能
|
3月前
|
机器学习/深度学习 人工智能 算法
基于Python深度学习的【蘑菇识别】系统~卷积神经网络+TensorFlow+图像识别+人工智能
蘑菇识别系统,本系统使用Python作为主要开发语言,基于TensorFlow搭建卷积神经网络算法,并收集了9种常见的蘑菇种类数据集【"香菇(Agaricus)", "毒鹅膏菌(Amanita)", "牛肝菌(Boletus)", "网状菌(Cortinarius)", "毒镰孢(Entoloma)", "湿孢菌(Hygrocybe)", "乳菇(Lactarius)", "红菇(Russula)", "松茸(Suillus)"】 再使用通过搭建的算法模型对数据集进行训练得到一个识别精度较高的模型,然后保存为为本地h5格式文件。最后使用Django框架搭建了一个Web网页平台可视化操作界面,
181 11
基于Python深度学习的【蘑菇识别】系统~卷积神经网络+TensorFlow+图像识别+人工智能
|
5月前
|
机器学习/深度学习 人工智能 算法
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
宠物识别系统,本系统使用Python作为主要开发语言,基于TensorFlow搭建卷积神经网络算法,并收集了37种常见的猫狗宠物种类数据集【'阿比西尼亚猫(Abyssinian)', '孟加拉猫(Bengal)', '暹罗猫(Birman)', '孟买猫(Bombay)', '英国短毛猫(British Shorthair)', '埃及猫(Egyptian Mau)', '缅因猫(Maine Coon)', '波斯猫(Persian)', '布偶猫(Ragdoll)', '俄罗斯蓝猫(Russian Blue)', '暹罗猫(Siamese)', '斯芬克斯猫(Sphynx)', '美国斗牛犬
297 29
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
|
6月前
|
机器学习/深度学习 人工智能 自然语言处理
深入理解深度学习中的卷积神经网络(CNN)
深入理解深度学习中的卷积神经网络(CNN)
261 10
|
5月前
|
机器学习/深度学习 人工智能 自然语言处理
深入理解深度学习中的卷积神经网络(CNN)##
在当今的人工智能领域,深度学习已成为推动技术革新的核心力量之一。其中,卷积神经网络(CNN)作为深度学习的一个重要分支,因其在图像和视频处理方面的卓越性能而备受关注。本文旨在深入探讨CNN的基本原理、结构及其在实际应用中的表现,为读者提供一个全面了解CNN的窗口。 ##
|
5月前
|
机器学习/深度学习 人工智能 算法
深度学习入门:用Python构建你的第一个神经网络
在人工智能的海洋中,深度学习是那艘能够带你远航的船。本文将作为你的航标,引导你搭建第一个神经网络模型,让你领略深度学习的魅力。通过简单直观的语言和实例,我们将一起探索隐藏在数据背后的模式,体验从零开始创造智能系统的快感。准备好了吗?让我们启航吧!
153 3
|
6月前
|
机器学习/深度学习 自然语言处理 语音技术
Python在深度学习领域的应用,重点讲解了神经网络的基础概念、基本结构、训练过程及优化技巧
本文介绍了Python在深度学习领域的应用,重点讲解了神经网络的基础概念、基本结构、训练过程及优化技巧,并通过TensorFlow和PyTorch等库展示了实现神经网络的具体示例,涵盖图像识别、语音识别等多个应用场景。
182 8
|
6月前
|
机器学习/深度学习 人工智能 自然语言处理
深度学习中的卷积神经网络(CNN): 从理论到实践
本文将深入浅出地介绍卷积神经网络(CNN)的工作原理,并带领读者通过一个简单的图像分类项目,实现从理论到代码的转变。我们将探索CNN如何识别和处理图像数据,并通过实例展示如何训练一个有效的CNN模型。无论你是深度学习领域的新手还是希望扩展你的技术栈,这篇文章都将为你提供宝贵的知识和技能。
640 7
|
6月前
|
机器学习/深度学习 人工智能 自然语言处理
探索深度学习中的卷积神经网络(CNN)及其在现代应用中的革新
探索深度学习中的卷积神经网络(CNN)及其在现代应用中的革新

新智元

+ 订阅

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等