【哥德尔不完全】终极算法无法超越哥德尔不完全性定理

2019-04-04
字体:
浏览:
文章简介:哥德尔不完全性定理被誉为"逻辑和数学史上的一座里程碑".由它产生的对"可证明"与"真"的讨论,直到图灵所产生的"可计算"与"不可计算"的讨论,再到如今"计算"与"超计算"."可计算"与"可学习"的讨论,构成了对心灵.智能研究的一条线索.佩德罗·多明戈斯<终极算法>一书提出的"终极算法"理想,对于解

哥德尔不完全性定理被誉为“逻辑和数学史上的一座里程碑”。由它产生的对“可证明”与“真”的讨论,直到图灵所产生的“可计算”与“不可计算”的讨论,再到如今“计算”与“超计算”、“可计算”与“可学习”的讨论,构成了对心灵、智能研究的一条线索。佩德罗·多明戈斯《终极算法》一书提出的“终极算法”理想,对于解决上述主题的问题提供了一定的思路。

【哥德尔不完全】终极算法无法超越哥德尔不完全性定理

哥德尔不完全性定理视域下早期人工智能的局限性

基于哥德尔不完全性定理的推论,可以得出形式算数本身的不可判定,即给定在形式算数中任意的公式,不存在统一的递归方法来确定它是不是其中的定理或者它是否恒真。在这里,形式算数指初等数论的递归形式化,包括此形式化的形式系统都存在不完全性。

【哥德尔不完全】终极算法无法超越哥德尔不完全性定理

早期的人工智能基于物理符号系统假设,一是任意合理的物理符号系统可以充分地获取智能,二是表现一般智能的主体都必须是物理符号系统的一个实例。也就是说物理系统表现一般智能行为的充分必要条件是一个物理符号系统,这也是人工智能符号学派建立的基础。

【哥德尔不完全】终极算法无法超越哥德尔不完全性定理

由此看出,无论对于机器的计算还是人工智能的构建来说,如果包含了初等数论,由于形式化方法原则,它们都要受到哥德尔不完全性定理的制约。也就是说,从符号学派的观点,哥德尔不完全性定理所引发的人工智能的局限性在于人工智能的不完全性。

当前机器学习对人工智能局限性的解答

不可计算问题类的存在,同样也表明人对于此类问题的不可计算。一方面,人类对于不可计算问题的真的确认,可能可以不通过计算的方式到达;另一方面,以上所讲的计算都属于递归计算问题,可能可以找到超越递归计算的计算方法。而对于人工智能而言,物理符号系统假定所展示的智能可计算观点及其局限,或许可以从以上两个方面突破。

机器学习作为当前人工智能研究的热门内容,已经在某些方面突破了固有的局限。连接学派通过模拟生物神经网络来构建人工智能的神经网络系统,通过正向传播算法来获取神经网络每一个神经元的激励节点的值,通过反向传播算法来获取每个激励节点的值的平均误差的下降梯度,通过梯度下降算法来获取每个节点的最优参数(使平均误差最小),最后这一切在最终输出神经元的带领下以获得输出函数的值。

输出函数在输入数据作为训练用例的基础上,通过以上方法成为一个能正确预测未知数据的函数,它并不完全依赖于对明确推理和描述世界的符号的预解释。

人工智能中的知识不在特定符号中而在整个神经网络的参数中,物理符号系统所假设的知识到符号的必要性映射,在这里就行不通了,因为知识到神经网络参数的映射有可能一对多,也就是说对网络中的参数可以有不同的解释。

神经网络超越物理符号系统假设是可能的,但是它没有在实质意义上超越图灵计算的局限。智能等同于计算,而计算已经不仅仅是图灵计算而是超计算的问题。但是在现实物理世界中,在超计算的指导下制造出来的计算机没有一个能超越通用图灵机。

而在超越图灵计算的意义上,自然计算指导下的进化学派从进化论的观点获得启示,主要利用的是遗传算法的涌现模型。遗传算法把问题的候选解决方案之间的关系看作竞争关系,而不是简单组合陈列;通过适应函数评估决定是否对下一代方案的形成作出贡献;最后通过类似染色体基因转换的方法,产生下一代候选解。

这是一种对于多个主体间的交互机制的最简单的表达。而涌现模型也探讨单个主体内的达尔文自然选择机制。最简单的表达是细胞自动机,即细胞的下一状态是前一状态和输入数据的函数。

显然,已有的状态会产生新的状态,新的状态会产生另一个新的状态,直到无尽。但是如果我们加入适应函数来评估它,单个主体也会受到进化的限制。

以上两者加一块便是我们想要的基于遗传与涌现的社会智能模型,在模型中主体自身进化、主体间的交互都受到自然选择机制约束。自然选择机制,不是说它们都按照全局优化的目标去做,而是说在不同的各自目标下,以类似社会的方式涌现智能。

当前机器学习对于上述局限的回答还不尽如人意,却已经产生了新的问题。PAC(probably approximately correct)学习理论表明,对机器可学习的定义不像图灵可计算那样是由算法定义的,而指由从合理数量的训练数据中通过合理的计算量可靠地学习到知识。

PAC更是指出机器学习存在训练数据不是非典型的概率和算法找到符合要求的知识的概率,它们之间在机器学习得以成功的概率关系就被称之为“可能近似正确”(PAC)学习理论。

这表明,一方面,机器学习如果要达到超越图灵计算的效果可能只是近似的结果;另一方面,对先验知识与正确度期望值的设定将一直影响你的机器学习,从语义上讲,你得到的超越性结果可能也只是你已经为机器设立的目标,而机器自己往上靠的结果。这一结果已经在人的心中存在,而机器并没有证明它,只是承认它。

“终极算法”超越局限的可能性

在多明戈斯的书中,“终极算法”是指通用学习算法,这也是“终极算法”的中心假设:所有知识,无论是过去的、现在的还是未来的,都有可能通过单个通用学习算法来从数据中获得。

多明戈斯结合不同机器学习学派的优点构建出理想的“终极算法”结构:进化学派进化出问题求解的先天数据结构,以智能的模块化的方式呈现;连接学派在这个结构的基础上通过连接计算,连接离散的节点并产生学习参数;符号学派在上述定量的基础上加入人类已经掌握的知识,完善已有的知识结构,完成定性任务;贝叶斯学派在非典型训练数据面前重新权衡训练数据,对于其他的可能的证据错误也进行重新权衡,这样就完成了对噪声的处理;类推学派在上述完整的学习结构下根据相似性类比到上述结构无法学习到的领域。

“终极算法”通过五大学派的融合,试图从已有数据的输入输出关系中找到一种综合的方法。

如果把“终极算法”看作黑箱,我们要输出图灵不可计算的结果,需要什么条件?根据“终极算法”的中心假设,这个结果会被称为知识。那么,什么才能称作知识?它不仅是通过形式化证明的东西,而且应该是我们信以为真的东西。

这就又回到了归纳偏置的问题,也就是说预设先天答案的问题。“终极算法”的哪些输入导致了图灵不可计算的结果?是否有其他的非形式化的证明方法利用输入能达到?还是说“终极算法”本身就是一种非图灵可计算的新的机器计算方法?如果它可以做到真正的无监督学习,这个图灵不可计算的结果会不会就是“机器的世界我不懂”那样而耸人听闻?

多明戈斯相信,人类自身也有一套“终极算法”存在,对人类“终极算法”的研究也存在可能性。多明戈斯还指出,“终极算法”下计算机与机器人在定义上无法拥有某样东西,即人类经历。尽管用计算机模拟人类经历是可能的,但是通过“终极算法”以准确达到对人类的整个预测几乎不可能,因为这里也存在着类似“机器的世界我不懂”这样的前述问题。

综上所述, “终极算法”并不能解决基于哥德尔不完全性定理所提出的人工智能的局限,反而产生了更多问题。不过,人工智能延展人类身体与认知的人机交互新时代可能即将到来。新时代下,人机交互、机器之间的交互和延展后人与人之间的交互之间的本体论、认识论、伦理问题,将关系着人类未来的命运。

(本文系国家社科基金后期资助项目“逻辑全能问题研究”(16FZX033)阶段性成果)