Deep Learning | JsingMog‘s Blog

type

status

date

slug

summary

1.图灵完备

1.1什么是图灵机？

图灵机是图灵在1936年发表的“On Computable Numbers, with an Application to the Entscheidungs problem”（《论可计算数及其在判定性问题上的应用》）中提出的数学模型。并非实体概念，而是架空的想法。论文中证明了，只要图灵机可以被实现，就可以用来解决任何可计算问题。

图灵机结构包括以下几部分：

一条无限长的纸带

一个字符表，即字符的集合

一个读写头，可以读取/擦除/写入当前格子的内容，也可以向左/右移动一个格子

一个状态寄存器，追踪每一步运算过程中，整个机器所处的状态。

一个有限的指令集，记录读写头在特定情况下应该执行的行为。

1.2图灵机可以解决什么问题？

图灵证明了假设上诉模型中所说的功能都能被以物理形式实现，那么任意可计算问题都可以被解决。

1.3什么是图灵完备

图灵完备性（Turing Completeness）是针对一套数据操作规则而言的概念。数据操作规则可以是一门编程语言，也可以是计算机中具体实现了的指令集。当这套规则可以实现图灵机模型中的全部功能时，就称它具有图灵完备性。

直观理解图灵完备——Brainfuck语言

如今主流的编程语言（C++，Java，Python等）都是图灵完备的语言，回到最底层，就会发现他们可以实现的功能其实完全一样，本质上就是一个图灵机。

1993年，Urban Mulller发明了Brainfuck语言，它一共包含8个有效字符，每个有效字符就是一条指令。语言虽然极致轻量，但它确实一门图灵完备的编程语言。

Brainfuck is fully Turing-complete.

BF的工作机制与图灵机高度一致。首先它存储数据的方式是一个不限长的一维整数数组，里面的数值全部初始化为0。此外，有一数据指针，每一时刻都指向数组的某一任意元素。指针可以向左/右移动，也可以读取/修改当前值。

8个有效字符分别为：

> ：指针向右移动一格

< ：指针向左移动一个

+ ：使指针当前格值加一

：使指针当前格值减一

. ：把当前格值按ASCII表输出到终端

, ：从终端接受一byte的数据，存储其ASCII数值到当前格

[ ：当指针当前值为0时，程序跳转至与之对应的 ] 之后，否则程序正常执行

] ：程序跳转回与之对应的 [ 处。

BF语言是图灵完备的，一门新语言的功能语法很复杂，证明其完备性很麻烦，但是只要使用这门语言实现一个BF的解释器，那么就必然证明它是图灵完备的。

2.归纳偏置

机器学习的no-free-lunch定理表明对于任何函数而言，一定的偏好（归纳偏置）是实现泛化的必要手段，也就是说，没有完全通用的学习算法，任何学习算法都只能在特定的分布上实现泛化。一般来说，给定特定的数据集和损失函数，一个学习算法存在许多可行解。然而，给定有限的训练集，要想在新数据上实现泛化就必须依赖对最优解做出的合理结社，因此，为了让人工智能达到与人类相近的性能，我们需要依据某些直觉和经验，针对不同问题探索合适的归纳偏置，使得学习算法能够更好地搜寻到具有某种特性的解。

例如CNN的归纳偏置是局部性（locality），空间不变性（spatial invariance），平移等效性（translation equivariance），即卷积核的参数共享；RNN的归纳偏置是时序性（sequential），时间不变性（time invariance），即时间步上的参数共享；GNN则是节点和关系的不变性；attention是置换不变性。

实际上，引入归纳偏置的方式有多种，例如在目标函数中引入适当的正则化，对网络结构进行限制，参数共享，选择合适的优化方法，对已知变化的不变性和等效性，或者在一个贝叶斯模型中选择合适的先验分布。例如，我们可以将矩阵相乘替换为卷积和池化，或者对输入特征做平均，或者利用具有数据样本经过变化之后的数据集训练，实现神经网络的平移不变性。

我们可以将归纳偏置或先验知识看做是“变相的训练数据”，同样的，我们也可以利用更多的数据来弥补先验归纳偏置的不足。通常来说，归纳偏置都是不完美的，并且，归纳偏置的优势在大数据集下会变得不明显。相反，归纳偏置在训练数据很少的迁移学习场景下具有很大的潜能。

3.迁移学习，持续学习和元学习

相较于针对某一固定数据分布寻找合适的归纳偏置，很多情况下，我们更希望模型能够适应一系列任务，这就要求模型能够从过去的任务和经验中提取到有用的信息来加速学习，这就是迁移学习和持续学习所考虑的问题。假设模型在任务A，B，C上训练，现在我们希望它能完成任务D。在没有任何假设的情况下，这几乎不可能完成。但是如果迁移任务D和源任务A，B，C之间存在共性，那么我们就可以实现源任务到目标任务间的知识迁移和泛化。

知识迁移的关键在于对模型所面对的数据做出合理假设，包括：

源任务和迁移任务之间具有什么共性；

源任务到迁移任务发生了什么改变

这与元学习也息息相关，元学习的过程分为对于世界平稳部分的慢学习和对于特定任务的快学习。理想情况下，我们希望能够尽可能地建立起对世界地完整理解，将学习过程大部分聚焦于对稳定部分地探索，也就是简历能够适应不同任务的归纳偏置，从而能够加速对特定任务的快速适应。

4.神经网络的高效性

单隐藏层的神经网络已经具备足够能力表达任何函数，但是我们仍然需要使用多层神经网络。例如下图展示了使用多层神经网络和单层进行对比的结果（语音辨识领域）。

可以看到，在参数相同的情况下，更深层的神经网络比单层神经网络效果好。为什么？

使用更深层的神经网络更加高效。更深层次的神经网络需要更少的参数，更少的训练数据，更加不容易过拟合。

深度神经网络相当于复合函数，而单隐藏层的网络相当于多项式函数。相比于深度神经网络，单层网络需要的参数是其指数规模倍。