神经网络的计算能力
来源
Siegelmann 1995, On the Computational Power of Neural Networks
摘要
本文讨论由同步演化的处理器连接成的有限大小的神经网络。每个处理器通过一个 sigmoidal 函数作用到所有单元前一个状态的线性组合来更新状态。我们证明，可以通过这样的网络来模拟所有图灵机。特别是，我们可以实时模拟任何多栈图灵机，并且存在一个由 886 个处理器组成的网络能计算通用部分递归函数。高阶网络是不必要的，与之前文献的说法相反。非决定性图灵机可以通过非决定性有理网络模拟，并且也是实时的。本文的结果对递归网络的可判定性和复杂性有许多影响。
1. 引言
我们研究循环一阶神经网络的计算能力；我们管这种网络叫处理器网络。这个模型由处理器的同步网络组成，其架构由一个一般性的有向图描述。输入字符通过 M 个输入通道传输，每次传一个。输出端是一个字符流，每个字符由 p 个值表示。图的节点称为神经元。每个神经元把一个单变量函数作用到所有神经元的激活值和外部输入的仿射组合上，以此来更新自己的激活值。具体地，更新方式是 \begin{equation} x_i(t+1) = \sigma\left(\sum_{j=1}^N a_{ij} x_j(t) + \sum_{j=1}^M b_{ij} u_j(t) + c_i\right) \end{equation} 上面的 \(a_{ij}\), \(b_{ij}\), \(c_{ij}\) 都是有理数。
我们采用最简单的一种 \(\sigma\) 函数，即饱和线性函数 \begin{equation} \sigma(x) = \begin{cases} 0 \quad \text{ if } x < 0\\ x \quad \text{ if } 0\le x\le 1\\ 1 \quad \text{ if } x>1 \end{cases} \end{equation} 之所以采用这个激活函数，一是因为它让定理更容易证明，二是因为一大类 sigmoidal 类型的激活函数对应的模型的计算能力并不比这个更强。
采用 sigmoidal 函数而非硬阈值让神经网络与较早的关于有限自动机的工作区别开来。事实上，至少从 McCulloh 和 Pitts 以及 Kleene 的经典论文开始，人们已经知道如何通过这种网络模拟有限自动机。
我们假定从 \(N\) 个处理器里选出了 \(p\) 个 \(x_{i_1},\ldots,x_{i_p}\) 作为输出单元，用于把结果传递给外界环境。一般来说输出值是 \([0,1]\) 范围内的任意实数，不过我们后面会限制它们只取二进制值。
我们只处理有理数描述的状态和权重，这是为了保证可计算性。如果采用实数权重，得到的处理器网络可以计算超图灵函数。
1.1 相关的工作
许多之前关于循环神经网络的工作处理的都是无限大小的网络。由于每个网络都是一个处理器，无限大的网络效果上等价于无限自动机，因此具有无限的处理能力。因此，无限大的模型对于计算能力的研究来说不太有挑战性，至少与我们要处理的有限大小网络相比而言。
前面已经提及 McCulloh 和 Pitts 关于有限自动机的工作。另一个相关的结果来自 Pollack。Pollack 认为某类循环神经网络 (他称之为神经机器) 是通用的。他的模型由有限多个分两类的神经元组成，具有恒等和阈值响应。这个机器是高阶的；也就是说，激活值通过乘积关系组合起来，而不是线性组合。具体的就是这样 \begin{equation} x_i(t+1) = \sigma\left(\sum_{|\omega|+|\beta|\le k} a_{i,\omega,\beta} x^\omega(t) u^\beta(t)\right),\quad i=1,\ldots,N \end{equation} 这里 \(\omega\), \(\beta\) 都是多重指标，\(k\lt\infty\)，以及 \[ x^\omega = x_1^{\omega_1}\cdots x_N^{\omega_N},\ u^\beta = u_1^{\beta_1}\cdots u_M^{\beta_M}. \] Pollack 没有说明是否高阶关联是必要的，虽然他这么猜测。高阶网络有应用。使用高阶网络的一个动机是 Pollack 猜测的更高级的计算能力。我们会证明，不存在这样的更高级的计算能力，至少在多项式时间的范畴内是如此。
有些处理无限结构的工作实际上处理的是元胞自动机。Wolper 证明仅仅使用线性激活函数的机器至少跟图灵机的计算能力一样强 (并且明显具有超过图灵机的能力)。在他的模型里神经元个数的无限性 (实际上是不可数的) 是至关重要的，因为其构造依赖于不同神经元编码多栈图灵机的不同的可能的栈配置。
使用连续值神经元而不是阈值门来提高计算能力也是被研究过的，但之前的工作只考虑了前馈网络这种特殊情况，比如用来研究函数的近似和插值或者布尔电路的复杂性等。
还有人研究了由有限个元件组成的光束追逐系统的可计算性。他们讨论的一个模型跟我们的有点类似，都包含参数的线性组合，系数都是有理数，穿过光学元件，具有递归计算能力。只不过，在那个模型里，使用了三种基本单元类型，模拟的图灵机拥有单元纸带。他们还假定能够瞬间得到两个数的差值，而我们不做这个假定。
1.2 影响，以及后续工作
本文结果对递归网络的可判定性和复杂性都有影响。比如，决定一个神经元是否会取 0 值实质上是个不可判定的问题 (因为停机问题可化为这个问题)。另一方面，采用线性激活函数的话，则这个问题变得可判定，并且在纯阈值函数的情况也是可判定的。由于我们的函数相当于阈值函数和线性组合的复合，关于可判定性的这个鸿沟是值得关注的。由于线性时间限制，也可能把 NP 完备方面的结果转移到网络方面的问题。另一个结果是，关于下述动力系统 \[ x(t+1) = \sigma(A x(t) + 1) \] 是否存在平衡点的问题是不可判定的。
另一个推论是，高阶网络计算上等价于一阶网络 (在多项式时间等价的意义上)。
许多其它种类的机器可用于通用计算。比如，可以证明按照 \(x(t+1) = x(t) + \tau(A x(t) + b u(t) + c)\) 演化的系统也是通用的，这里 \(\tau\) 的作用是取出每个坐标的正负号。有意思的是，这个方程是微分方程的欧拉差分近似；这提示了图灵机的连续时间模拟的可能性，并且技术上与模拟计算很不同。
2. 模型及主要结果
我们把网络建模为一个动力系统。在每个时刻，系统状态由一个有理数组成的向量 \(x(t)\in\mathbb{Q}^N\) 表示，第 \(i\) 个坐标表示第 \(i\) 个处理器的活化值。给定初始状态和输入，由迭代方程可得到新的态。
我们需要定义通过网络来计算下面这样的函数是什么意思： \[ \phi:\ \{0,1\}^+ \mapsto \{0,1\}^+, \] 这里 \(\{0,1\}^+\) 代表二进制字符串的自由半群 (排除空字符串)。为此，我们必须先定义形式化网络，这个网络按照严格的规则来编码和解码。我们的形式化网络有两条二进制输入线。第一个是数据线，用于传输二进制输入信号，当没有信号的时候默认值为 0。第二条线是检验线，用于标记何时数据是活跃的：1 表示数据出现，0 表示没有数据。我们用 D 和 V 分别表示两条线的内容，而每个时刻的输入就是 \[ u(t) = (D(t), V(t)) \in \left\{0,1\right\}^2. \] 我们总是把初始状态 \(x(1)\) 设置为 0，并且是平衡态。我们假定有两个输出单元，也分别具有数据和检验的角色，用 G 和 H 表示。网络的输出就是 \[ y(t) = (H(t), G(t)) \in \left\{0,1\right\}^2. \] 采用两条输入线使得所有外部信号都是二进制的。其它约定当然也可以，但结果是一样的，
一般来说，我们的离散时间动力系统由下述映射描述 \[ \mathcal{F}:\ \mathbb{Q}^N\times\{0,1\}^2 \to \mathbb{Q}^N. \] 时刻 \(t\) 的状态是 \[ x(1) = x^\text{init},\ x(t+1) = \mathcal{F}(x(t), u(t)),\ t=1,2,\ldots \]
对于每个 \(N\in\mathbb{N}\)，我们把下面的映射 \[ (q_1,\ldots,q_N) \mapsto (\sigma(q_1),\ldots,\sigma(q_N)) \] 写为 \[ \sigma_N:\ \mathbb{Q}^N\to\mathbb{Q}^N. \] 有时候也会省掉下标。
定义 2.1 一个具有两个二进制输入的 \(\sigma\)-单元网络 \(\mathcal{N}\) 是具有如下形式映射的动力系统 \[ \mathcal{F}(x,u) = \sigma(Ax + b_1u_1 + b_2 u_2 + c), \] 这里 \(A\in\mathbb{Q}^{N\times N}\) 是个矩阵，\(b_1\), \(b_2\), \(c\in \mathbb{Q}^N\) 都是向量。 偏置矢量 \(c\) 并不必须，但有它会让方便些。
显然，可以用图灵机来模拟一个拥有零初始状态或有理初始状态的处理单元网络。我们想要证明的是，相反地，任何可以用图灵机计算的函数也可以被这样的处理单元网络计算。我们关心的是递归计算的映射 \[ \phi:\ \{0,1\}^+ \mapsto \{0,1\}^+. \] 换句话说，我们关心的映射是那些存在一个多栈图灵机 \(\mathcal{M}\) 使得当一个词 \(\omega\in\{0,1\}^+\) 被一开始写在输入/输出栈上时，\(\mathcal{M}\) 在 \(\omega\) 处停止当且仅当 \(\phi(\omega)\) 是有定义的，并且，在这个情况下，\(\phi(\omega)\) 是停机时栈上的内容。
对于每个词 \[ \omega = \omega_1\cdots\omega_k\in\{0,1\}^+ \] 满足条件 \[ \phi(\omega) = \beta_1\cdots\beta_l\in\{0,1\}^+\ 或未定义 \] 以及 \(r\in\mathbb{N}\) (\(l\) 是输出的长度，\(r\) 是响应时间)，我们按下述方式编码。输入编码为 \[ u_\omega(t) = (V_\omega(t), D_\omega(t)),\ t=1,\ldots, \] 这里 \[ V_\omega(t) = \begin{cases} 1, \quad \text{if}\ t=1,\ldots,k, \\ 0, \quad \text{otherwise} \end{cases} \] 以及 \[ D_\omega(t) = \begin{cases} \omega_k, \quad \text{if}\ t=1,\ldots,k, \\ 0, \quad \text{otherwise} \end{cases} \] 输出编码为 \[ y_{\omega,r}(t) = (G_{\omega,r}(t), H_{\omega,r}(t)),\ t=1,\ldots, \] 这里 \[ G_{\omega,r}(t) = \begin{cases} 1, \quad \text{if}\ t=r,\ldots,(r+l-1),\\ 0, \quad \text{otherwise} \end{cases} \] 若 \(\phi(\omega)\) 有定义的话，否则为 0。最后 \[ H_{\omega,r}(t) = \begin{cases} \beta_{t-r+1}, \quad \text{if}\ t=r,\ldots,(r+l-1),\\ 0, \quad \text{otherwise} \end{cases} \] 若 \(\phi(\omega)\) 有定义的话，否则为 0。
定理 1 若 \(\phi\) 是前面定义的递归可计算部分函数，则存在具有如下性质的处理单元网络 \(\mathcal{N}\)
- 若 \(\mathcal{N}\) 从零初态开始，并且输入序列 \(u_\omega\) 被应用上，则对某些 \(r\), \(\mathcal{N}\) 会输出 \(y_{\omega,r}\)。
- 进一步，如果一个具有 \(p\) 个栈的图灵机 \(\mathcal{M}\) 在时间 \(T(\omega)\) 内计算 \(\phi(\omega)\)，则可以让 \(r(\omega) = T(\omega) + O(|\omega|)\)。
2.1 重述：无 I/O 情形
考虑定理 1 的一个版本是有用的：没有输入，把初始数据编码进初始状态。对于图灵机来说，这相当于把输入编码进输入栈而不是作为额外的输入流。
对于没有输入的网络，可以把动力学映射 \(\mathcal{F}\) 想成 \(\mathbb{Q}^N\to\mathbb{Q}^N\)。对于状态 \(\xi\in\mathbb{Q}^N\), 令 \(\xi^j = \mathcal{F}^j(\xi)\)。现在我们断言，如果 \(\phi: \{0,1\}^+ \rightarrow \{0,1\}^+\) 是一个递归可计算部分函数，则存在处理器网络 \(\mathcal{N}\) 以及把数据编码成初始状态的方式，使得 \(\phi(\omega)\) 当且仅当第二个处理器的激活值永远是 0 的时未定义，而当这个值等于 1 时有定义，而在这种情况下第一个处理器编码了结果。
给定 \(\omega=a_1\cdots a_k \in \{0,1\}^+\)，定义编码函数为 \begin{equation} \delta[a_1\cdots a_k] = \sum_{i=1}^k \frac{2a_i+1}{4^i}. \label{eqFour} \end{equation}
定理 2 令 M 是一个 \(p\) 栈图灵机，它可在时间 \(T\) 内计算函数 \(\phi: \{0,1\}^+ \rightarrow \{0,1\}^+\)。则存在无输入处理器网络 \(\mathcal{N}\) 使得下面的性质 (a) 和 (b) 成立。在两种情况下，对每个 \(\omega\in\{0,1\}^+\)，我们考虑对应的初态
\[
\xi(\omega) = (\delta[\omega],0,\ldots,0) \in \mathbb{Q}^N.
\]
(a) 如果 \(\phi(\omega)\) 未定义，\(j\) 步后的状态的第二个坐标 \(\xi(\omega)^j_2\) 恒等于 0，对所有 \(j\)。如果 \(\phi(\omega)\) 有定义，并且在时间 \(T\) 内计算，则存在 \(\mathcal{T} = O(T)\) 使得
\[
\begin{split}
&\xi(\omega)^j_2 = 0, \quad j=0,\ldots,\mathcal{T}-1,\\
&\xi(\omega)^\mathcal{T}_2 = 1,
\end{split}
\]
并且 \(\xi(\omega)_1^\mathcal{T} = \delta[\phi(\omega)]\) (线性时间模拟).
(b) 并且，如果把方程 (\(\ref{eqFour}\)) 中的 \(\delta\) 替换为新的映射 \(\delta_p\)
\[
\delta[a_1\cdots a_k]_p = \sum_{i=1}^k \frac{10 p^2 - 1 + 4p(a_i-1)}{(10 p^2)^i},
\]
则这个构造的运行时间是 \(\mathcal{T} = T\) (实时模拟)。
后面的几节包含两个定理的证明。我们先证明定理 2，然后把定理 1 作为一个推论。定理 2 的证明细节很技术化，所以我们先会大致给出主要步骤。证明本身按几个步骤组织。我们先展示如何构造一个网络 \(\mathcal{N}\) 在时间 \(\mathcal{T}=4T\) 内模拟给定的多栈图灵机 M (\(T\) 是图灵机的运算时间)。之后我们修改网络的构造使得没有计算速度的减缓。这通过三个步骤完成，并且是通过让大的负数作为禁止器实现的。
3. 证明的概要
我们从一个 2-栈机器开始；这个模型明显等价于单纸带标准图灵机。形式上，2-栈机有有限多个控制器和两个二进制栈组成，长度无限。每个栈通过读写头存取，位于栈的顶端。在计算的开始，二进制输入序列被写到栈 1。每一步机器把栈的顶部元素读入为一个元素 \(\alpha \in\{0,1,\#\}\) (这里 \(\#\) 表示栈是空的)，检查控制器的状态 (\(s\in\{1,2,\ldots,|S|\}\))，并且执行下面的操作
- 对每个栈，做下面的处理
- 弹出顶部元素
- 把一个元素推到栈顶 (0 或 1)
- 不改变栈
- 改变控制器的状态
3.1 栈的编码
假定我们要把二进制流 \(\omega=\omega_1\cdots\omega_n\) 编码为数字 \[ \sum_{i=1}^n \frac{\omega_i}{2^i}. \] 这样一个数可以存放在神经元里，因为大小在 \([0,1]\) 内。但这个简单的编码有些问题。第一，不能区分字符串“\(\beta\)”和“\(\beta\cdot0\)”，这里 \(\cdot\) 表示字符拼接。第二，就算假定所有字符串都以 1 结尾，激活函数的连续性也让在恒定时间内获取最高位变得不可能 (比如 0.10000000000 和 0.01111111111 对于一个网络来说几乎不可分辨)。换句话说，给定二进制输入信号流，把信号转换到连续范围内是不好的，让编码之间有间隙会好些。间隙有助于通过有限精度快速解码，或者等价地，在恒定时间内读出最高位。当然，计算阶段需要保证栈的编码不变。编码方案 \[ \sum_{i=1}^n \frac{2\omega_i+1}{4^i} \] 的结果处于 \([0,1)\) 中，但不是每个值都取到。如果字符串以 1 开始，则相应的数字至少为 \(3/4\)，如果以 0 开始，则在 \([1/4, 1/2)\) 内。空字符串的编码是 0。可能的取值不连续，有孔洞。这样的集合是一个康托集。其自相似结构意味着移位操作保持了孔洞。这个编码方案的好处是，不需要通过比较两个很接近的数字来读出最高位。
3.2 栈的操作
下面我们展示我们的编码的用途：
1. 读取顶端元素。假定栈的值是 \(\omega=1011\)，也就是说，它的四进制编码是 \(q=0.3133_4\)。前面已经讨论过，\(q\) 的值至少是 \(3/4\) 若栈顶为 1，至多为 \(1/2\) 其它情况。线性操作 \(4q-2\) 把这个范围变到至少为 1 若栈顶为 1，至多为 0 其它情况。因此函数 \[ \mathrm{top}(q) = \sigma(4q-2) \] 给出了顶部元素的值。
2. Push 0 操作通过 \((q+1)/4\) 实现，push 1 操作通过 \((q+3)/4\) 实现。
3. Pop 操作通过 \(4q - (2\text{top}(q)+1)\) 实现。
4. 判断栈非空通过 \(\sigma(4q)\) 实现。
3.3 网络的一般构造
基于上面的讨论我们构造一个每个栈有三个神经元的网络。一个神经元保存栈的编码 (q)，一个保存 top(q)，一个用来指示栈是否是空的。并且，还有一些神经元用于表示有限控制单元，以及一些神经元从读栈神经元和有限控制神经元获取输入来计算下一步。
3.4 P 栈机器
已经知道 p-栈机器 (\(p\ge2\)) 多项式等价于 2-栈机器，但通过后者模拟前者会导致速度减慢超线性量级。有意思的是，在我们的神经网络里，我们能实时模拟 p-栈机器。也就是说，不存在从一个模型转到另一个模型导致的减慢。所以我们就用 p-栈机器。
3.5 实时模拟
为了达成“逐步”模拟，需要更加复杂的编码。然后使用大的负数作为禁止器，以此获得实时模拟效果。下面是正式的证明。