Universality of Gradient Descent Neural Network Training梯度下降神经网络训练的普适性
Abstract摘要
It has been observed that design choices of neural networks are often crucial for their successful optimization. In this article, we therefore discuss the question if it is always possible to redesign a neural network so that it trains well with gradient descent. This yields the following universality result: If, for a given network, there is any algorithm that can find good network weights for a classification task, then there exists an extension of this network that reproduces these weights and the corresponding forward output by mere gradient descent training. The construction is not intended for practical computations, but it provides some orientation on the possibilities of meta-learning and related approaches.人们观察到，神经网络的设计选择往往对其优化成功与否至关重要。因此，本文探讨了是否总是可以通过重新设计神经网络，使其能够通过梯度下降进行良好训练的问题。这导出了以下普适性结果：对于给定的网络，如果存在任何算法能为分类任务找到合适的网络权重，那么就存在该网络的一个扩展版本，能够仅通过梯度下降训练来重现这些权重及其相应的正向输出。该构造并非旨在用于实际计算，但它为元学习及相关方法的可能性提供了一些指导。
Keywords: deep neural networks, global minima, Turing machines, meta-learning, biologically plausible learning关键词：深度神经网络，全局极小值，图灵机，元学习，生物学上可行的学习
AMS subject classifications: 68T07, 68Q04, 90C26AMS 主题分类：68T07, 68Q04, 90C26
1 Introduction1 引言
Training neural networks with gradient descent is remarkably effective in a multitude of applications, see e.g. [23, 19] for image classification, [32] for reinforcement learning, [34, 3] for machine translation or [15] for a general overview. This is somewhat surprising because the objective function is generally non-convex and neural network training is -hard in the worst case [6].在众多应用中，使用梯度下降训练神经网络效果显著，例如图像分类 [23, 19]、强化学习 [32]、机器翻译 [34, 3] 或通用概述 [15]。这在一定程度上令人惊讶，因为目标函数通常是非凸的，且在最坏情况下，神经网络训练是 NP-hard 的 [6]。
The current literature contains a growing number of ideas and approaches to explain this phenomenon. Some experimental studies indicate that the loss function of common learning problems is more benign than one might assume on first sight [16, 38]. Other works [7, 24, 2] provide a thorough understanding of simplified networks. For non-simplified general networks rigorous convergence results can be obtained under the assumption of over-parametrization [33, 30, 26, 1, 12]. Despite this progress, many practical networks do not satisfy all necessary assumptions and a solid understanding of the training behaviour remains a challenging question.目前的文献中，解释这一现象的观点和方法日益增多。一些实验研究表明，常见学习问题的损失函数比初看起来要温和得多 [16, 38]。其他研究 [7, 24, 2] 对简化网络提供了透彻的理解。对于未简化的通用网络，在过度参数化的假设下可以获得严格的收敛结果 [33, 30, 26, 1, 12]。尽管取得了这些进展，但许多实际网络并不满足所有必要假设，因此对训练行为的深入理解仍是一个具有挑战性的问题。
In this article, we address the problem from a different perspective. Instead of providing conditions on networks that guarantee convergence, we consider the question if we can modify a given network so that it trains well. This is loosely inspired by practical network training, where we do not consider one single fixed network either. More often, we experiment with a multitude of hyper-parameters and architectural elements such as drop-out, attention, skip connections, etc. until we obtain satisfactory results. The question is then not necessarily if every network trains well, but rather if we can find one that does.在本文中，我们从不同的角度来解决这个问题。我们没有提供保证收敛的网络条件，而是考虑是否可以修改给定的网络，使其能够良好地训练。这在一定程度上受到了实际网络训练的启发，在实际训练中，我们也不会只考虑一个固定的网络。我们通常会尝试多种超参数和架构元素（如 Dropout、注意力机制、跳跃连接等），直到获得满意的结果。因此，问题不一定在于每个网络是否都能良好训练，而在于我们是否能找到一个可以良好训练的网络。
To address this question, we provide the following universality result: For a given primary network with weights and learning task, we assume that there is a Turing machine that can compute good network weights given inputs and labels , . This could be gradient descent training, global optimization methods or any other algorithm specifically tailored to the network and problem at hand. The existence of such a Turing machine merely asserts that some good training algorithms exits. We then construct an extended network that contains the primary network as a sub-network with the following three properties:为了解决这个问题，我们提出了以下普适性结果：对于给定的具有权重 θ 的主网络 fθ 和学习任务，假设存在一台图灵机 TM，在给定输入 xi 和标签 yi（i=1,…,n）的情况下，能够计算出良好的网络权重 θ¯=TM(x,y)。这可以是梯度下降训练、全局优化方法或任何专门针对当前网络和问题的算法。此类图灵机的存在仅断言了某些良好的训练算法是存在的。然后，我们构造了一个扩展网络，将主网络作为子网络包含在内，并具有以下三个属性：
- 1.
Gradient descent training of the extended network adjusts the parameters of the primary network to the output of the Turing machine.扩展网络的梯度下降训练会将主网络 fθ 的参数 θ 调整为图灵机的输出 θ¯=TM(x,y)。
- 2.
After gradient descent training, a forward execution of the extended network with input yields the output , i.e. the output of the primary network with weights chosen by the Turing machine.梯度下降训练后，以输入 x 对扩展网络进行前向执行，将产生输出 fθ¯(x)，即权重为 θ¯=TM(x,y)（由图灵机选择）的主网络 fθ¯ 的输出。
- 3.
The number of gradient descent steps matches the number of Turing machine steps.梯度下降的步数与图灵机的步数相匹配。
In summary, if there exists an algorithm that produces good weights from the learning data, these weights can be computed by gradient descent training on a properly extended network.总之，如果存在一种能从学习数据中产生良好权重的算法，那么这些权重可以通过在适当扩展的网络上进行梯度下降训练来计算出来。
The extended network is carefully handcrafted, which, of course, is not intended as a practical algorithm, but rather an universality result to demonstrate the capabilities of gradient descent in combination with a properly chosen network. Form a practical perspective, there are multiple algorithms that aim at automatically generating good neural networks for a specific problem. Although these methods often do not optimize for gradient descent convergence directly, the extended network can be seen as a somewhat idealized potential outcome of such methods. One example is meta-learning [21], in particular methods such as MAML [13] that pre-select network weights so that they can be adapted to a specific problem by one step of gradient descent. Another example is neural architecture search [29, 40, 41, 35], which seeks to automatically generate neural networks with state of the art performance for a given learning task. In transfer learning [11, 37] neural networks contain weights that have been pre-trained on related problems.该扩展网络是精心设计的，当然，它并非旨在作为一种实用算法，而是一个旨在展示梯度下降与适当选择的网络相结合的能力的普适性结果。从实际角度来看，有多种算法旨在为特定问题自动生成良好的神经网络。尽管这些方法通常不会直接针对梯度下降收敛进行优化，但扩展网络可以被视为此类方法的一种理想化潜在结果。一个例子是元学习 [21]，特别是像 MAML [13] 这样的方法，它们预先选择网络权重，以便通过一步梯度下降将其调整到特定问题。另一个例子是神经架构搜索 [29, 40, 41, 35]，它寻求为给定的学习任务自动生成具有最先进性能的神经网络。在迁移学习 [11, 37] 中，神经网络包含已在相关问题上预训练过的权重。
Another parallel can be drawn to biologically plausible learning methods [27, 36]. They often use dedicated “feedback networks” as a replacement for the back-propagation of gradients, as e.g. [5]. Some examples include target propagation [25] and synthetic gradients [22]. Although the extended networks of this article do use back-propagation, a “switch” at the end of the network prevents gradients to be back-propagated directly to the primary network . Instead, they are propagated into a parallel network where they trace the Turing machine computation and ultimately influence the weights of . Therefore the network extension can also be understood as a “feedback network”.另一个平行点可以延伸到生物学上可行的学习方法 [27, 36]。它们通常使用专门的“反馈网络”来替代梯度的反向传播，例如 [5]。一些例子包括目标传播 [25] 和合成梯度 [22]。尽管本文的扩展网络确实使用了反向传播，但网络末端的“开关”阻止了梯度直接反向传播到主网络 fθ。相反，它们被传播到一个并行网络中，在那里它们追踪图灵机的计算，并最终影响 fθ 的权重。因此，网络扩展也可以被理解为一种“反馈网络”。
“Universality” results for neural networks usually refer to their capacity to approximate arbitrary functions, with varying restrictions on network width, depth or activation functions. See [9, 20, 4] for some early results and e.g. [39] for convolutional networks, [28, 18] for deep networks and [14] for other learning regimes as model agnostic meta learning. More quantitative results are also available e.g. in [10] and the references therein. In contrast to this body of work, the universality result in this article is concerned with a quite different question: We want to know if gradient descent training can always proceed to find desirable network weights, not if neural networks can approximate an arbitrary function.神经网络的“普适性”结果通常指其近似任意函数的能力，并对网络宽度、深度或激活函数有不同的限制。请参阅 [9, 20, 4] 获取一些早期结果，以及 [39]（卷积网络）、[28, 18]（深度网络）和 [14]（其他学习范式，如模型无关元学习）。更定量的结果也可参见 [10] 及其参考文献。与这些工作不同，本文的普适性结果关注的是一个完全不同的问题：我们想知道梯度下降训练是否总是能找到理想的网络权重，而不是神经网络是否能近似任意函数。
There are also numerous connections between Neural networks and Turing Machines. Similar to the universal function approximation, neural networks can simulate arbitrary Turing Machines [31]. Other results supplement neural networks with read and writable memory [17, 8], trainable by gradient descent. These latter neural Turing machines aim at making neural networks even more powerful in practical applications. Although they are a natural choice for the extended network of this article, for simplicity we confine ourselves to feed forward networks with sufficient width to hold the full tape during the computation of for all inputs and labels of fixed size.神经网络和图灵机之间也有许多联系。与通用函数近似类似，神经网络可以模拟任意图灵机 [31]。其他结果为神经网络补充了可读写的内存 [17, 8]，可以通过梯度下降进行训练。这些后来的神经图灵机旨在使神经网络在实际应用中更加强大。尽管它们是本文扩展网络的自然选择，但为简单起见，我们仅限于使用具有足够宽度以在计算 TM(x,y) 时容纳完整磁带的前馈网络，适用于所有固定大小的输入 x 和标签 y。
The paper is organized as follows: Section 2 contains the main result of the paper and Section 3 contains a brief overview over the construction of the extended network. In Section 4, we construct two loss functions that allow us to trace steps of Turing machines by gradient descent. Finally in Section 5, we prove the main result of the article.本文组织如下：第 2 节包含本文的主要结果，第 3 节简要概述了扩展网络的构造。在第 4 节中，我们构造了两个损失函数，允许我们通过梯度下降追踪图灵机的步骤。最后，在第 5 节中，我们证明了本文的主要结果。
2 The Main Result2 主要结果
Let us consider the following standard learning task: Given samples , and corresponding labels , we want to train the parameters of a primary network so that predicts labels for any input . In order to avoid problems with Turing computability, we use some finite precision floating point numbers instead of real numbers . The structure of the parametric function is not important for the following considerations, although we are mainly interested in neural networks with input and network weights . For notational convenience, we combine all and into two matrices and .让我们考虑以下标准学习任务：给定样本 xi∈𝔽M, i=1,…,n 和相应的标签 yi∈𝔽m，我们希望训练主网络 fθ:𝔽M→𝔽m 的参数 θ，使得 fθ(x) 能为任何输入 x∈𝔽M 预测标签。为了避免图灵可计算性方面的问题，我们使用一些有限精度的浮点数 𝔽 而不是实数 ℝ。参数化函数 fθ 的结构对于以下考虑并不重要，尽管我们主要关注输入为 x∈𝔽M 且网络权重为 θ∈𝔽W 的神经网络。为方便起见，我们将所有 xi 和 yi 合并为两个矩阵 x∈𝔽n×M 和 y∈𝔽n×m。
We assume that there is a computable function that for given inputs and labels of a learning task produces suitable weights . For example, the function could simply return the result of a standard gradient descent training, a global optimization method or any algorithm that is specialized for the problem at hand. Anyways, we do not consider the meaning of “suitable” or the choice of the algorithm any further. Instead, we show that whatever algorithm is chosen, its resulting weights can be reproduced by gradient descent training of an extended network.我们假设存在一个可计算函数 TM(x,y)→θ，对于学习任务的给定输入 x 和标签 y，它能产生合适的权重 θ。例如，函数 TM 可以简单地返回标准梯度下降训练、全局优化方法或任何专门针对当前问题的算法的结果。无论如何，我们不再进一步考虑“合适”的含义或算法的选择。相反，我们证明无论选择哪种算法，其结果权重 θ 都可以通过扩展网络的梯度下降训练来重现。
This extended network is a parametric function with the following properties:该扩展网络是一个参数化函数 F，具有以下属性：
| (1) | ||||
The stop gradient operations are used to provide a directionality for read/write operations of the Turing machine and are readily available in contemporary deep learning libraries. The quantization is never differentiated and used to transfer floating point inputs to bit sequences for the Turing machine. Of course on any computer, internally any number is already in binary format, which can be passed directly to the Turing machine. Formally, one can also use a neural network to transfer floating point numbers to a bit sequence and vice versa as discussed in Appendix B.停止梯度操作用于为图灵机的读/写操作提供方向性，在当代深度学习库中很容易实现。量化操作从不进行微分，用于将浮点数输入 𝔽 转换为图灵机的位序列。当然，在任何计算机上，内部数字已经是二进制格式，可以直接传递给图灵机。形式上，也可以使用神经网络将浮点数转换为位序列，反之亦然，如附录 B 所述。
The weights of the extended network are constrained to the Cartesian product of a simplex and a vector space. The dimensions and contents will be determined later, at this point we merely need the simplex structure to define an appropriate gradient descent method. To this end, we use the least squares loss扩展网络的权重 (s,t)∈𝒟 被限制在单纯形 S 和向量空间的笛卡尔积 𝒟=S×ℝ4τ+n×m 中。维度和内容将在稍后确定，此时我们仅需要单纯形结构来定义适当的梯度下降方法。为此，我们使用最小二乘损失
| (2) |
on the original dataset . Since the weight is constrained to a simplex, we use the conditional gradient, or Frank-Wolfe, algorithm作用于原始数据集 (x,y)。由于权重 s 被限制在一个单纯形上，我们使用条件梯度（或 Frank-Wolfe）算法
| (3) | ||||
with some fixed learning rate and component wise multiplication .其中 α∈ℝ|𝒟| 为固定的学习率，⊙ 为分量乘法。
In addition to the extended network, the construction of this article provides some explicit stopping criterion除了扩展网络之外，本文的构造还提供了一些明确的停止准则
| (4) |
for some bigger than the final training error . The following proposition is the main result of this article: We train the extended network with the given loss, gradient descent method, learning rate and stopping criterion. Afterwards, computing a forward pass of the extended network yields the same result as if we would run the primary network with weights chosen by the Turing machine.对于某些大于最终训练误差 ∥fTM(x,y)(x)-y)∥≤Bstop 的 Bstop。以下命题是本文的主要结果：我们使用给定的损失、梯度下降方法、学习率和停止准则来训练扩展网络。之后，对扩展网络进行前向传递计算，其结果与运行权重为 θ=TM(x,y)（由图灵机选择）的主网络 fθ 的结果相同。
Proposition 2.1.命题 2.1。
For any number of samples and finite precision floating point numbers , let be a computable function given by a Turing machine that halts for every input, using less than tape symbols at any step of the computation. Assume that the labels satisfy对于任意数量的样本 n 和有限精度浮点数 𝔽，设 TM:𝔽n×M×𝔽n×m→𝔽p 是一个由图灵机给出的可计算函数，该图灵机在每一步计算中使用少于 τ=τ(n) 个磁带符号，且对每个输入都能停机。假设标签满足
| (5) |
for some . Then, there is an extended network that satisfies all properties in (1), with initial values , fixed learning rate and stopping threshold , depending only on such that after gradient descent training (3) with stopping criterion (4) we have对于某些 ϵ>0。那么，存在一个满足 (1) 中所有属性的扩展网络 F，其初始值 (s0,t0)、固定学习率 α 和停止阈值 Bstop 仅取决于 TM，使得在满足停止准则 (4) 的梯度下降训练 (3) 之后，我们有
for the final parameter of the gradient descent method. The gradient descent stopping criterion is met in steps, where is the number of steps the Turing machine’s uses to compute .对于梯度下降方法的最终参数 (sK,tK)∈𝒟。梯度下降停止准则在 kt+1 步内满足，其中 kt 是图灵机计算 TM(x,y) 所需的步数。
An overview over the construction is provided in Section 3. The proof of the proposition, as well as the following two corollaries is deferred to Sections 4 and 5. Bounds on the size of the extended network depend on its construction. First, if we insist that the gradient descent loss is strictly decreasing, we obtain the following.第 3 节提供了构造的概述。命题的证明以及以下两个推论推迟到第 4 节和第 5 节。扩展网络的大小界限取决于其构造。首先，如果我们坚持梯度下降损失必须严格递减，则获得以下结果。
Corollary 2.2.推论 2.2。
Assume the Turing machine has two tape symbols, tapes and states in its finite control. Then, the extended network in Proposition 2.1 can be chosen with non-increasing gradient descent loss and less than extra layers of width smaller than in addition to .假设图灵机 TM 有两个磁带符号，d≥2 个磁带，以及 |Q| 个有限控制状态。那么，命题 2.1 中的扩展网络可以选择具有非递增梯度下降损失 ℓ(sk,tk) 且除 fθ 外，额外层数少于 12 层，宽度小于 |Q|2dττd+O(nm)。
This result is included in the paper because it contains the basic ideas to trace a Turing machine by gradient descent without adding too much technicalities for read/write operations to the tapes. However, the result itself is questionable because the extra layers are large enough to encode all possible states of the Turing machine for the given input sizes. This includes states with all possible inputs and outputs written in the tapes and therefore one could just as well store all possible input/output relations (these are finite because we work with floating point numbers ), which is obviously infeasible.本文包含此结果是因为它包含了通过梯度下降追踪图灵机的基本思想，而没有为磁带的读/写操作增加太多技术细节。然而，结果本身值得商榷，因为额外的层足够大，可以编码给定输入大小下图灵机的所有可能状态。这包括磁带中写入所有可能输入和输出的状态，因此人们同样可以存储所有可能的输入/输出关系（由于我们使用浮点数 𝔽，这些是有限的），这显然是不可行的。
The following corollary provides a similar result with a much smaller extended network, which scales linearly in the required number of tape symbols and therefore has a comparable size to the Turing machine itself. Unlike the last corollary, the loss function is no longer monotonically decreasing with regard to the gradient descent steps and does not work with a line search.以下推论提供了一个类似的结论，但扩展网络小得多，其规模与所需的磁带符号数 τ 成线性比例，因此其大小与图灵机本身相当。与上一个推论不同，损失函数不再随梯度下降步数单调递减，且不适用于线搜索。
Corollary 2.3.推论 2.3。
Assume the Turing machine has two tape symbols, tapes and states in its finite control. If the gradient descent loss is allowed to be non-monotonic, the size of the extended network in Proposition 2.1 can be constrained to less than extra layers of width smaller than , in addition to .假设图灵机 TM 有两个磁带符号，d≥2 个磁带，以及 |Q| 个有限控制状态。如果允许梯度下降损失 ℓ(sk,tk) 非单调，则命题 2.1 中扩展网络 F 的大小可以限制为除 fθ 外，额外层数少于 12 层，宽度小于 2d|Q|+2dτ+O(nm)。
This construction contains two network weights and as components of for the Turing machine’s tape and head position. In principle, we can allow these to be of infinite dimension leading to infinite tape length as for regular Turing machines.这种构造包含两个网络权重 T 和 H 作为 t 的分量，用于图灵机的磁带和磁头位置。原则上，我们可以允许这些维度无限，从而像常规图灵机一样实现无限磁带长度 τ=∞。
Remark 2.4.备注 2.4。
The extra width is required to read the full set of labels into the Turing machine . Many practical algorithms work with batches of labels, which could in principle also be implemented with a similar extended network. In this case, we would only need an extra width of .读取完整的标签集到图灵机 TM 中需要额外的宽度 O(nm)。许多实际算法使用标签批次，原则上也可以用类似的扩展网络来实现。在这种情况下，我们只需要 O([batch size]⋅m) 的额外宽度。
3 Extended Network: Overview3 扩展网络：概述
This section provides a brief overview over the construction of the extended network. A detailed construction and the proof of the main results is given in Sections 4 and 5 below.本节简要概述了扩展网络的构造。详细的构造和主要结果的证明见下文第 4 节和第 5 节。
The construction proceeds in two steps: First, we construct a loss function that allows us to trace the states of a generic Turing machine by gradient descent steps. Unlike typical loss functions, it does not compare predictions to labeled training data. Instead, it is build from standard neural network components and therefore, in the second step, used as a sub-network together with the primary network and some “switches” to build the extended network.构造分两步进行：首先，我们构造一个损失函数 ℓTM，允许我们通过梯度下降步骤追踪通用图灵机的状态。与典型的损失函数不同，它不比较预测与带标签的训练数据。相反，它由标准神经网络组件构建，因此在第二步中，它被用作与主网络和一些“开关”一起使用的子网络，以构建扩展网络。
The construction of is given in Section 4. To summarize, we associate each state of the Turing machine with a vertex of a simplex. Depending on the construction in Corollaries 2.2 or 2.3 the state includes the tape or only the finite control and the tape symbols at the head position with secondary tape and head variables. The loss function maps the simplex to the real numbers and is chosen so that gradient descent steps with unit learning rate remain on vertices if started at an initial vertex. Therefore, the gradient descent steps can be associated with states of the Turing machine, which we referred to as “tracing” the Turing machine, above.ℓTM 的构造见第 4 节。总之，我们将图灵机的每个状态与单纯形的一个顶点相关联。根据推论 2.2 或 2.3 中的构造，该状态包括磁带，或者仅包括有限控制和磁头位置处的磁带符号以及辅助磁带和磁头变量。损失函数将单纯形映射到实数，其选择使得如果从初始顶点开始，单位学习率的梯度下降步骤将保持在顶点上。因此，梯度下降步骤可以与图灵机的状态相关联，即上述提到的“追踪”图灵机。
In order to define , we subdivide the simplex into corner simplices, one for each vertex, and the remaining interior part. On each corner we can freely assign a piecewise linear loss function and then extend it continuously to the full simplex. Since the gradient descent steps remain on the vertices, this allows us to control the gradients and carve “barriers” and “slides” into that guides the gradient descent updates along the states of the Turing machine execution. If the states do not contain the full tape, some extra least squares terms are added for reading and writing to a secondary tape variable.为了定义 ℓTM，我们将单纯形细分为角单纯形（每个顶点一个）和剩余的内部部分。在每个角上，我们可以自由分配分段线性损失函数，然后将其连续扩展到整个单纯形。由于梯度下降步骤保持在顶点上，这使我们能够控制梯度，并在 ℓTM 中刻画“屏障”和“滑道”，引导梯度下降更新沿着图灵机执行的状态进行。如果状态不包含完整磁带，则会添加一些额外的最小二乘项，用于读写辅助磁带变量。
The extended network is composed of the primary network and the Turing machine network as shown in Figure 1. For the time being, we only consider a rudimentary overview and defer a more detailed description to Section 5.1 below.扩展网络由主网络 fθ 和图灵机网络 ℓTM 组成，如图 1 所示。目前，我们仅考虑一个初步概述，将更详细的描述推迟到下文第 5.1 节。
The bottom two layers and contain two switches, which select the branches of the network that are passed to the output. The first step of gradient descent training writes a copy of the labels into the weights/node . This copy is used as input for the Turing machine because the actual labels are only implicitly available through the loss function.底部的两层 snet 和 sinit 包含两个开关，用于选择传递到输出的网络分支。梯度下降训练的第一步将标签 y 的副本写入权重/节点 z。此副本用作图灵机 TM 的输入，因为实际标签 y 仅通过损失函数隐式可用。
The first training step also flips the switches so that only the branch is passed to the output and the remaining gradient descent steps trace the Turing machine as described above. is a wrapper around that matches the output dimensions from the scalar loss to the dimension of the labels .第一个训练步骤还会翻转开关，使得只有 fTM 分支被传递到输出，其余的梯度下降步骤如上所述追踪图灵机。fTM 是 ℓTM 的包装器，它将标量损失的输出维度与标签 y 的维度相匹配。
Finally, once the Turing machine reaches a halting state, the last gradient descent step flips the switches again so that only the primary network is passed to the output. The parameters are no longer network weights but read from the weights representing the Turing machine’s state and tape, containing after halting. Therefore, any further forward pass through the network computes the result of the primary network with weights computed by the Turing machine.最后，一旦图灵机达到停机状态，最后一个梯度下降步骤再次翻转开关，使得只有主网络被传递到输出。参数 θ 不再是网络权重，而是从代表图灵机状态和磁带的权重 s,T,H 中读取，在停机后包含 TM(x,y)。因此，通过网络的任何后续前向传递都会计算出主网络在图灵机计算出的权重下的结果 fTM(x,y)。
Note that during the entire training all gradients are passed only through the subnetwork , but never through the primary network . This is reminiscent of approaches in biologically plausible learning, which use separate “feedback networks” for the adjustment of network weights. Unlike other approaches in the literature, this effect is solely generated by the network architecture, not by a modification of the back-propagation algorithm.请注意，在整个训练过程中，所有梯度仅通过子网络 fTM 传递，从不通过主网络 fθ。这让人想起生物学上可行的学习方法中的途径，它们使用单独的“反馈网络”来调整网络权重。与文献中的其他方法不同，这种效应完全由网络架构产生，而不是通过修改反向传播算法。
4 Simulate Turing Machines via Gradient Descent4 通过梯度下降模拟图灵机
4.1 Turing Machines4.1 图灵机
Let us first fix the Turing machine TM. Without loss of generality, we assume that it has tapes and only two tape symbols , including the blank.首先固定图灵机 TM。不失一般性，假设它有 d 个磁带，且只有两个磁带符号 {-1,1}，包括空白符号。
- 1.
: finite and non-empty set of states.Q：有限且非空的状态集。
- 2.
: Initial state.q0∈Q：初始状态。
- 3.
: accepting states.F⊂Q：接受状态。
- 4.
Tape symbols: .磁带符号：Γ={-1,1}。
- 5.
: transition function with and denoting left and right shift of the head.δ:Q×Γd→Q×Γd×{-1,1}d：转移函数，其中 -1 和 1 分别表示磁头的左移和右移。
We denote the component functions of by so that .我们将 δ 的分量函数记为 δi(q,t)，使得 δ(q,t)=[δ1(q,t),δ2(q,t),δ3(q,t)]。
We make two more assumptions on the Turing machine. First a subset of the tapes is read-only. This will usually be the tape holding the inputs, whereas the outputs are placed on the remaining tapes. Second, for a class of well formed inputs of interest, we assume that the Turing machine halts in finite time and uses at most consecutive tape entries on each tape at any time during the computation. As for any real computer, we then assume that the tapes have finite length .我们对图灵机再做两个假设。首先，磁带的一个子集 RO⊂{1,…,d} 是只读的。这通常是保存输入的磁带，而输出放置在剩余的磁带上。其次，对于一类感兴趣的良构输入 𝒯0，我们假设图灵机在有限时间内停机，并且在计算过程中的任何时刻，每个磁带上最多使用 τ 个连续磁带条目。与任何真实计算机一样，我们假设磁带具有有限长度 τ。
Typically, the class consists of encodings of the training data and and the tape size depends on the data size. For the construction in Corollary 2.3, it is allowed to be infinite.通常，类 𝒯0 由训练数据 x 和 y 的编码组成，磁带大小 τ 取决于数据大小。对于推论 2.3 中的构造，允许其为无限。
4.2 Technical preliminaries4.2 技术准备
The loss function to trace the Turing machine with gradient descent is constructed with the help of piecewise linear functions on simplices. This sections contains some explicit formulas for their evaluation, derivatives and optimal descent directions. To this end, let be a simplex with vertices , for some index set and assume that is affine. The vertices will be standard basis vectors below, but this is not necessary for this section. Then, for with barycentric coordinates用于通过梯度下降追踪图灵机 TM 的损失函数 ℓTM 是在单纯形上借助分段线性函数构建的。本节包含一些用于其评估、导数和最优下降方向的显式公式。为此，设 S 为一个具有顶点 ev（v∈V，对于某个索引集 V）的单纯形，并假设 ℓ:S→ℝ 是仿射的。顶点 ev 在下文中将是标准基向量，但这对本节并非必要。那么，对于具有重心坐标的 x∈S
we can evaluate by我们可以通过以下方式评估 ℓ
Moreover, affinity implies that for any convex combination we have此外，仿射性意味着对于任何凸组合，我们有
Therefore, for any two points in the simplex , the one-sided directional derivative in the direction is given by因此，对于单纯形 S 中的任意两点 x,y，沿方向 y-x 的单侧方向导数由下式给出
| (6) | ||||
For gradient descent on simplices, we optimize over directions that point into the simplex. However, the loss function will not be affine on the entire simplex, but only in its corners. To this end, for , the corner at is a sub-simplex defined by对于单纯形上的梯度下降，我们在指向单纯形内部的方向上进行优化。然而，损失函数不会在整个单纯形上都是仿射的，而仅在其角上。为此，对于 0<μ≤1，顶点 v 处的角是一个由下式定义的子单纯形
with “” denoting the convex hull. In the following, we denote the vertices of a simplex by . If , we also use the abbreviations其中“conv”表示凸包。在下文中，我们将单纯形 S 的顶点记为 V(S)。如果 μ=1/2，我们还使用缩写
The next lemma provides explicit formulas for optimal descent directions with eventual extra quadratic terms.下一个引理提供了最优下降方向的显式公式，最终带有额外的二次项。
Lemma 4.1.引理 4.1。
Let be a vertex of and be a loss function that is affine on the corner for some . Then for and , we have设 ev 是 S⊂ℝN 的一个顶点，ℓ 是在某个 0<μ≤1 的角 Svμ 上仿射的损失函数。那么对于 A∈ℝM×N 和 y∈ℝM，我们有
with其中
| (7) | ||||
| (8) |
Proof.证明。
Let us abbreviate . We first rescale the directional derivatives to the corner . To this end, note that让我们缩写 f(x):=ℓ(x)+12∥Ax-y∥2。我们首先将方向导数重新缩放到角 Svμ。为此，请注意
where the point is in the corner if and only if is in . Hence, the last equation and the identity imply that其中点 a:=(1-μ)ev+μz 在角 Svμ 中，当且仅当 z 在 S 中。因此，最后一个方程和恒等式 1μ(a-ev)=z-ev 意味着
| (9) |
Since is affine in the corner , we use (6) to simplify the directional derivative to由于 ℓ 在角 Svμ 中是仿射的，我们使用 (6) 将方向导数简化为
for any with barycentric coordinates with respect to the vertices of . Likewise, we have对于任何具有相对于 Svμ 的顶点 {bu|u∈V}=V(Svμ) 的重心坐标 au 的 a∈Svμ。同样，我们有
In the last two equations the respective last terms and do not depend on and therefore the minimizer is given by在最后两个方程中，各自的最后一项 ⋯-ℓ(ev) 和 ⋯-(Aev-y)TAev 不依赖于 a，因此最小化器由下式给出
The right hand side is minimal, if puts all its weight on the smallest summand, so that如果 a 将其所有权重放在最小的加数上，则右侧最小，因此
Since are the vertices of , together with (9) this directly shows (7). In order to show (8), note that every vertex is a convex combination of vertices of . Therefore, we have由于 bu 是 Svμ 的顶点，结合 (9)，这直接显示了 (7)。为了显示 (8)，请注意每个顶点 bu∈V(Svμ) 都是 S 的顶点的凸组合 (1-μ)ev+μeu。因此，我们有
Using that the first summand of the right hand side is independent of shows (8).利用右侧的第一个加数与 u 无关，证明了 (8)。
∎
4.3 Tracing Turing Machines: No Extra Tape Variable4.3 追踪图灵机：无额外磁带变量
In this section we construct a loss function that is used in the construction of Corollary 2.2 and allows a gradient descent method to trace the steps of the Turing machine . The method is simple but also very costly, therefore we consider a related but more efficient approach in Section 4.4 below.在本节中，我们构造了一个用于推论 2.2 构造中的损失函数，它允许梯度下降方法追踪图灵机 TM 的步骤。该方法简单但代价非常高，因此我们在下文第 4.4 节中考虑一种相关但更有效的方法。
The Loss Function损失函数
By the assumption in Section 4.1, for all relevant inputs in the Turing machine halts in finite time using at most tape entries at any time during the computation. Hence, we can represent every relevant computation by a finite directed graph. Its vertices are all states of the Turing machine with the given size constraint and the edges encode the computational steps, i.e. there is an edge from vertices to if and only if the state follows after in the Turing machine execution.根据 4.1 节中的假设，对于 𝒯0 中的所有相关输入，图灵机在有限时间内停机，在计算过程中的任何时刻最多使用 τ 个磁带条目。因此，我们可以用有限有向图表示每个相关的计算。其顶点 V 是图灵机在给定大小限制下的所有状态，边 E 编码计算步骤，即当且仅当状态 w 在图灵机执行中紧随 v 之后时，存在从顶点 v 到 w 的边。
In order to construct the corresponding loss function, we first assign weights to vertices and pairs of vertices, including non-edges, so that their minimization mimics the Turing machine execution. To this end, let为了构造相应的损失函数，我们首先为顶点分配权重 ωv，并为顶点对（包括非边）分配权重 ωvw，使得它们的最小化模仿图灵机的执行。为此，设
| (10) | ||||||
where is an upper bound其中 B 是一个上界
of all vertices and computationally legitimate edge weights. Although for the time being the problem is still discrete, we consider moving between vertices along the pairs with minimal weights , or staying in place if the current vertex weight is smaller than the outgoing connections. The first inequality of (10) ensures that the correct computational step is preferred over staying in place, the second inequality ensures that we do not follow the computation backwards and the third equality ensures that we do not follow computationally non-valid steps. The last identity is used to ease the transition to a continuous optimization problem later. It is not necessarily required that whenever succeeds in the computation, although for some constructions below we enforce this property to ensure that the gradient descent method has strictly decreasing loss.涵盖所有顶点和计算上合法的边权重。尽管目前问题仍然是离散的，但我们考虑沿着具有最小权重 ωvw 的对在顶点之间移动，或者如果当前顶点权重 ωv 小于传出连接，则保持在原地。 (10) 的第一个不等式确保正确的计算步骤优先于保持原地，第二个不等式确保我们不会向后追踪计算，第三个等式确保我们不会遵循计算上无效的步骤。最后一个恒等式用于简化稍后向连续优化问题的过渡。并不一定要求每当 w 在计算中继 v 之后时，都有 ωw<ωv，尽管对于下文的某些构造，我们强制执行此属性以确保梯度下降方法具有严格递减的损失。
Next, we extend theses weighs to a continuous loss function that can be optimized with gradient descent. To this end, we associate each vertex with the standard unit basis vector and define the domain as the simplex接下来，我们将这些权重扩展为连续损失函数 ℓ:S⊂ℝ|V|→ℝ，该函数可以通过梯度下降进行优化。为此，我们将每个顶点 v∈V 与标准单位基向量 ev∈ℝV 相关联，并将域 S 定义为单纯形
spanned by the basis vectors. The values at the vertices and barycenters of each two vertices correspond to the graph weights:由基向量张成。每个两个顶点 (v,w) 的顶点和重心 evw 处的值对应于图权重：
| (11) | ||||||
The latter condition requires the symmetry of the edge weights in (10).后一个条件要求 (10) 中边权重的对称性。
Each iterate of the gradient descent method will be a vertex. In order to control the gradient direction, we need to fill in values for in their neighborhood. To this end, we assume that梯度下降方法的每个迭代 xk∈S 都将是一个顶点。为了控制梯度方向，我们需要在它们的邻域内填充 ℓ 的值。为此，我们假设
| (12) |
A loss function with all properties in (10), (11) and (12) can be easily constructed by linear finite elements on a subdivision of the simplex . Nonetheless, in this article, we use the related explicit functions from Appendix A. These have two advantages: First, we do not need all finite element basis functions and therefore can avoid the construction of subdivisions for high dimensional simplices. Second, the explicit formulas demonstrate that they can be implemented by single layer neural networks. Specifically, from Appendix A, we have the functions and , which are linear in all corners and have the interpolation properties具有 (10)、(11) 和 (12) 中所有属性的损失函数可以通过单纯形 S 的细分上的线性有限元轻松构造。尽管如此，在本文中，我们使用附录 A 中的相关显式函数。这些函数有两个优点：首先，我们不需要所有的有限元基函数，因此可以避免为高维单纯形构造细分。其次，显式公式证明了它们可以通过单层 ReLU 神经网络实现。具体而言，根据附录 A，我们有函数 ℓv 和 ℓvw，它们在所有角 Svμ 中是线性的，并具有插值属性
for all , , and . A loss function satisfying (11) and (12) is then given by对于所有 v≠w，u≠{v,w}，r∈V 以及 (s,t)∉{(v,w),(w,v)}。满足 (11) 和 (12) 的损失函数由下式给出
| (13) |
Let us next assign some numeric values to the weights and satisfying the requirements (10). By assumption, we know that for all relevant inputs in , the Turing machine halts in finite time, say with no more than steps. For each state we run the Turing machine for at most steps and record the number it took until it reaches a halting state or set if it does not reach a halting state. For arbitrary numbers we then assign接下来，让我们为满足要求 (10) 的权重 wv 和 wvw 分配一些数值。根据假设，我们知道对于 𝒯0 中的所有相关输入，图灵机在有限时间内停机，例如不超过 K-1 步。对于每个状态 v∈V，我们运行图灵机最多 K 步，并记录它达到停机状态所花费的步数 k(v)，如果它没有达到停机状态，则设置 k(v)=K。对于任意数字 W0<W1<⋯<WK=B，我们然后分配
Gradient Descent梯度下降
Since the loss function is only defined on the simplex , we use the conditional gradient method (Frank-Wolfe algorithm) for optimization. This is a modification of the gradient descent method, which only allows update directions that are compatible with the convex constraint . It is defined by由于损失函数仅定义在单纯形 S 上，我们使用条件梯度法（Frank-Wolfe 算法）进行优化。这是梯度下降法的一种修改，它只允许与凸约束 x∈S 兼容的更新方向。它定义为
| (14) | ||||
More commonly, the update direction is defined by with . This is equivalent to the one given above because and the latter term is independent of . In our case is piecewise linear and may have kinks. Nonetheless, one-sided directional derivatives are well-defined and sufficient for the method above.更常见的是，更新方向定义为 dk=yk-xk，其中 yk=argminy∈S⟨∇ℓ(xk),y⟩。这与上面给出的等价，因为 ∂y-xkℓ(xk)=⟨∇ℓ(xk),y⟩-⟨∇ℓ(xk),xk⟩，且后一项与 y 无关。在我们的例子中，ℓ 是分段线性的，可能存在拐点。尽管如此，单侧方向导数定义明确，足以满足上述方法。
The learning rate is either constant , or determined by a line search. For the latter, we need the extra condition that学习率要么是常数 αk=1，要么由线搜索确定。对于后者，我们需要额外的条件
| (15) |
to ensure that is indeed the minimizer along the gradient direction given by the edge from to . For fixed learning rate this is not required since the loss is not necessarily strictly decreasing (at least for exact computation, which we consider in this paper).以确保 ωw 确实是沿从 ev 到 ew 的边给出的梯度方向上的最小化器。对于固定学习率，这不是必需的，因为损失不一定严格递减（至少对于我们在本文中考虑的精确计算而言）。
Convergence收敛性
The loss function is defined on the simplex of a dimensional vector space. Since is the number of all possible states of the Turing machine with tape length bounded by , the dimension is very large. It must be at least with states of the finite control, possible tape contents and head positions. Practically, this is of course unrealistic and in Section 4.4 we consider a modified construction that scales linearly in the tape length.损失函数定义在 |V| 维向量空间的单纯形 S⊂ℝV 上。由于 |V| 是磁带长度受限于 τ 的图灵机所有可能状态的数量，因此维度非常大。它必须至少为 |Q|2dττd，其中有 |Q| 个有限控制状态，2dτ 个可能的磁带内容和 τd 个磁头位置。实际上，这当然是不现实的，在 4.4 节中，我们考虑了一种随磁带长度线性缩放的改进构造。
We now show that gradient descent applied to our loss function traces the steps of the Turing machine .我们现在证明应用于我们损失函数的梯度下降追踪了图灵机 TM 的步骤。
Proposition 4.2.命题 4.2。
Let be defined by the gradient descent method (14) with initial value , contained in the vertices of . Assume that the loss function satisfies the conditions (10), (11) and (12). Let the learning rate be constant or defined by line search if (15) holds in addition.设 xk 由梯度下降法 (14) 定义，初始值为 x0=ev0，v0∈𝒯0⊂V(S) 包含在 S 的顶点中。假设损失函数 ℓ 满足条件 (10)、(11) 和 (12)。设学习率为常数 αk=1，或者如果此外满足 (15)，则由线搜索定义。
For consecutive states of the Turing machine execution with initial state and halting state , we have对于具有初始状态 v0 和停机状态 vK 的图灵机执行的连续状态 v0,…,vK，我们有
| If (15) holds, we have | |||||
in addition and the loss is strictly decreasing, i.e. with for .此外，损失严格递减，即 ℓ(xk)=ωvk，且对于 k=1,…,K，ωv0>⋯>ωvK。
Proof.
By induction, assume that is a non-halting state. Since the loss is linear on the corner , Lemma 4.1 implies that the updated direction of the gradient method is given by通过归纳法，假设 xk=ev 是一个非停机状态。由于损失 ℓ 在角 Sv 上是线性的，引理 4.1 意味着梯度法的更新方向由下式给出
| (16) |
Since is a non-halting state, the interpolation property (11) and the weight properties (10) of the loss function, yield , where is the successor state of in the Turing machine execution, i.e. . Therefore, the next step of the gradient method is given by由于 v 是一个非停机状态，插值属性 (11) 和损失函数的权重属性 (10) 得出 dk=1μ(evw-ev)=ew-ev，其中 w∈V(S) 是 v 在图灵机执行中的后继状态，即 (v,w)∈E。因此，梯度法的下一步由下式给出
If the learning rate is , this directly yields . In case the learning rate is given by a line search, the extra condition (15) ensures that the loss function is piecewise linear along the line segments from to and to with values . Thus, the line search follows this direction as far as possible without leaving the simplex , resulting in the final point .如果学习率为 αk=1，这直接得出 xk+1=evk+1。如果学习率 αk 由线搜索给出，则额外条件 (15) 确保损失函数沿从 ev 到 evw 以及从 evw 到 ew 的线段分段线性，且值 ℓ(ev)>ℓ(evw)>ℓ(ew)。因此，线搜索尽可能远地沿着该方向进行而不离开单纯形 S，从而得出最终点 xk+1=ew。
If is a halting state, by the extra condition (15), the minimizer of (16) is itself. Therefore, we have , irrespective of the choice of .如果 xk=ev 是一个停机状态，根据额外条件 (15)，(16) 的最小化器本身就是 ev。因此，无论 αk 的选择如何，我们都有 xk+1=xk。
∎
4.4 Tracing Turing Machines: With Extra Tape Variable4.4 追踪图灵机：带有额外磁带变量
The construction in Section 4.3 has the disadvantage that all possible relevant computations of the Turing machine must be known beforehand and hard-coded into the loss function. This quickly leads to an excessively high dimensional domain of the loss function. In this section, we consider an alternative construction, where the states of the simplex correspond to the finite control of the Turing machine only and the tape is stored in a extra variables that scales linearly with the tape length. The drawback of this method is that we have to use a fixed step size and the gradient descent iterates are no longer strictly decreasing.第 4.3 节中的构造方法有一个缺点，即必须预先知道图灵机所有可能的相关计算，并将其硬编码到损失函数中。这很快会导致损失函数的定义域维度过高。在本节中，我们考虑一种替代构造方法，其中单纯形 SS 的状态仅对应于图灵机的有限控制器，而纸带存储在随纸带长度线性缩放的额外变量中。这种方法的缺点是我们必须使用固定的步长，且梯度下降迭代不再严格递减。
The Loss Function
The loss function is similar to the construction in Section 4.4 with the tape content split of into a new variable. We define a computational graph with vertices composed of the state of the finite control and copies of the tapes at the head positions. The directional edges correspond to legitimate computational steps, i.e. if and , with successor state of the finite control and arbitrary tape symbol read from the tape.该损失函数类似于第 4.4 节中的构造，将纸带内容拆分到了一个新变量中。我们定义了一个计算图，其顶点 V=Q×ΓdV=Q\times\Gamma^{d} 由有限控制器的状态和磁头位置处的纸带副本组成。有向边 EE 对应于合法的计算步骤，即如果 v=(q,t)v=(q,t) 且 w=(q′,t′)w=(q^{\prime},t^{\prime})，且有限控制器的后继状态 q′=δ1(q,t)q^{\prime}=\delta_{1}(q,t)，同时从纸带读取了任意纸带符号 t′t^{\prime}，则 (v,w)∈E(v,w)\in E。
As before, we associate each vertex with a standard unit basis vector in the -dimensional vector space and define the simplex as the convex hull of these basis vectors. To account for the tapes of length , we introduce two extra variables: with one component for each tape entry and with exactly one non-zero entry per tape indicating the head positions.与之前一样，我们将每个顶点 v=(q,t)∈Vv=(q,t)\in V 与 |Q|2d|Q|2^{d} 维向量空间 ℝV=ℝQ×Γd\mathbb{R}^{V}=\mathbb{R}^{Q\times\Gamma^{d}} 中的标准单位基向量 ev=eq,te_{v}=e_{q,t} 相关联，并将单纯形 SS 定义为这些基向量的凸包。为了处理长度为 τ\tau 的 dd 条纸带，我们引入了两个额外变量：T∈ℝτ×dT\in\mathbb{R}^{\tau\times d}（每个纸带条目对应一个分量）和 H∈{0,1}τ×dH\in\{0,1\}^{\tau\times d}（每条纸带恰好有一个非零条目，用于指示磁头位置）。
Note that the total number of vertices plus tape and head dimensions scale linearly in the number of control states and the tape size. This is significantly less than the construction in Section 4.3 with at least an exponential number of vertices.请注意，顶点总数 2d|Q|2^{d}|Q| 加上纸带和磁头维度 2τd2\tau d 与控制状态的数量和纸带大小呈线性比例关系。这远少于第 4.3 节中至少具有指数级顶点数 |Q|2dττd|Q|2^{d\tau}\tau^{d} 的构造。
As in Section 4.4, for vertices and halting states , we assign weights与第 4.4 节一样，对于顶点 v=(q,t)v=(q,t) 和停机状态 FF，我们分配权重
with a global scaling factor and some constant to be chosen later. The weights distinguish halting from non-halting states, but are no longer decreasing while following a computational path. This cannot be avoided because the Turing machine may pass a vertex several times during its execution, with different tape content and head position. Since the tape is no longer included in , we cannot distinguish these states with different weights.其中包含一个全局缩放因子 γ\gamma 和稍后选择的某个常数 b>0b>0。这些权重区分了停机状态和非停机状态，但在沿着计算路径移动时不再递减。这是不可避免的，因为图灵机在执行过程中可能会多次经过同一个顶点 vv，且每次的纸带内容和磁头位置都不同。由于纸带不再包含在 SS 中，我们无法用不同的权重来区分这些状态。
For two vertices and , the edge weights are given by对于两个顶点 v=(q,t)v=(q,t) 和 w=(q′,t′)w=(q^{\prime},t^{\prime})，边权重由下式给出
| (17) |
The first choice is negative and therefore favors correct computational steps. Its structure is chosen to balance some quadratic terms that we add to the loss function later, for read and write operations to the tape variables and . These quadratic terms may have zero gradients, in which case the extra sum in the definition of the edge weights ensures correct successor states. The powers of are used to balance several contributions to the gradient. For later reference, we choose it sufficiently large so that第一个选择是负数，因此有利于正确的计算步骤。其结构旨在平衡我们稍后添加到损失函数中的某些二次项，用于对纸带变量 TT 和 HH 进行读写操作。这些二次项的梯度可能为零，在这种情况下，边权重 ωvw\omega_{vw} 定义中的额外求和项确保了后继状态的正确性。bb 的幂用于平衡梯度中的多个贡献项。为了便于后续参考，我们选择足够大的 bb，使得
| (18) |
We extend these weights to a continuous loss function on with the properties我们将这些权重扩展为 SS 上的连续损失函数 ℓS\ell_{S}，并具有以下性质
| (19) | ||||||
Since , the loss is not well defined if both and are legitimate computations in , i.e. the Turing machine goes back and forth between two states in . Without loss of generality, we assume that this cannot happen, i.e. that由于 evw1/4=ewv3/4e_{vw}^{1/4}=e_{wv}^{3/4}，如果 (v,w)(v,w) 和 (w,v)(w,v) 都是 EE 中的合法计算（即图灵机在 SS 中的两个状态之间来回切换），则损失 ℓS\ell_{S} 定义不明确。在不失一般性的前提下，我们假设这种情况不会发生，即
| (20) |
This can easily be achieved by the following modification of the Turing machine : We triple the states to and extend the transition function to这可以通过对图灵机 TMTM 进行以下修改轻松实现：我们将状态三倍化为 Q¯:={[q,r]|q∈Q,r∈{0,1,2}}\bar{Q}:=\{[q,r]|\,q\in Q,\,r\in\{0,1,2\}\}，并将转移函数扩展为
Thus, the extended Turing machine performs the exact same computations as the original one, with the exception that in each step the new index of state cycles through the numbers . Therefore, if the state is followed by the latter is followed by some because . Therefore, we never have the sequence of states , which implies (20).因此，扩展后的图灵机执行与原始图灵机完全相同的计算，区别在于每一步中状态 [q,r][q,r] 的新索引 rr 会在 0,1,20,1,2 之间循环。因此，如果状态 v=([q,r],t])v=([q,r],t]) 之后紧跟 w=([q′,r+1mod3],t′)w=([q^{\prime},r+1\mod 3],t^{\prime})，则后者之后紧跟的必然是某个 [q′′,r+2mod3]≠[q,r][q^{\prime\prime},r+2\mod 3]\neq[q,r]，因为 r+2mod3≠rr+2\mod 3\neq r。因此，我们永远不会出现状态序列 v→w→vv\to w\to v，这意味着 (20) 成立。
In order to extend the loss function to the full simplex, we use the two functions and defined in Lemma A.1 and (34) in Appendix A, which can be easily constructed with single layer units. They have the properties为了将损失函数扩展到整个单纯形，我们使用附录 A 中引理 A.1 和 (34) 定义的两个函数 ℓv1/4\ell_{v}^{1/4} 和 ℓ¯vw\bar{\ell}_{vw}，它们可以很容易地用单层 ReLUReLU 单元构造。它们具有以下性质
and以及
Along the edge , the function is piecewise linear as shown in Figure 2. Therefore, a loss function satisfying all properties in (19) is given by沿着边 (v,w)(v,w)，函数 ℓ¯vw\bar{\ell}_{vw} 是分段线性的，如图 2 所示。因此，满足 (19) 中所有性质的损失函数由下式给出
The loss is used to trace the steps of the finite control via gradient descent, but in addition we need some extra terms for reading and writing to the tape variable and moving the head positions . To this end, we first define some matrices , to read out tape symbols from vertices and a bilinear map to shift head positions and then add corresponding least squares terms to the loss function.损失函数 ℓS\ell_{S} 用于通过梯度下降追踪有限控制器的步骤，此外我们还需要一些额外的项来对纸带变量 TT 进行读写以及移动磁头位置 HH。为此，我们首先定义一些矩阵 𝒯↓\mathcal{T}_{\downarrow}, 𝒯↷\mathcal{T}_{\curvearrowright} 以从顶点 v=(q,t)v=(q,t) 中读出纸带符号，并定义一个双线性映射 𝒮\mathcal{S} 以移动磁头位置，然后将相应的最小二乘项添加到损失函数中。
The matrices yield the tape symbols of each vertex at the current and next state of the Turing machine, defined by矩阵 𝒯↓,𝒯↷∈ℝτ×d\mathcal{T}_{\downarrow},\mathcal{T}_{\curvearrowright}\in\mathbb{R}^{\tau\times d} 产生图灵机在当前和下一状态下每个顶点的纸带符号，定义为
The shift of the head positions is defined by磁头位置的偏移 𝒮\mathcal{S} 定义为
for basis vectors and then expanded to be bi-linear in both of its variables. It shifts all tape head indicators by the amount determined by the current step of the Turing machine. Note that we always assume that the tapes are sufficiently large so that the head positions never reach its boundary. Hence, we may insert blank symbols if necessary.对于基向量，然后扩展为在其两个变量上是双线性的。它将所有纸带磁头指示器偏移由当前图灵机步骤确定的量 δ3(q,t)\delta_{3}(q,t)。请注意，我们始终假设纸带足够大，使得磁头位置永远不会到达边界。因此，如有必要，我们可以插入空白符号。
We can now match the tape symbols in a vertex with tape symbols in the tape . To this end, let us denote by subscripts columns of tape matrices, so that e.g. is the content of the -th tape of the Turing machine. Then, adding a term to the loss function matches the tape symbol of the -th tape at the next head position with the tape symbol in the vertex . We can do the same for all tapes by adding a term , where “” is the vector of diagonal entries of the matrix .现在，我们可以将顶点 x=ev=eq,tx=e_{v}=e_{q,t} 中的纸带符号 tt 与纸带 TT 中的纸带符号进行匹配。为此，令下标 ii 表示纸带矩阵的列，例如 Ti∈ℝτT_{i}\in\mathbb{R}^{\tau} 是图灵机第 ii 条纸带的内容。然后，将项 |TiT⋅[𝒮(x)H]i−(𝒯↓x)i|2|T^{T}_{i}\cdot[\mathcal{S}(x)H]_{i}-(\mathcal{T}_{\downarrow}x)_{i}|^{2} 添加到损失函数中，即可将第 ii 条纸带在下一个磁头位置处的纸带符号与顶点 vv 中的纸带符号进行匹配。我们可以通过添加项 ‖diag(TT𝒮(x)H)−𝒯↓x‖2\|\diag(T^{T}\mathcal{S}(x)H)-\mathcal{T}_{\downarrow}x\|^{2}$ 对所有纸带执行相同的操作，其中 “diag\diag” 是 d×dd\times d 矩阵 TT𝒮(x)HT^{T}\mathcal{S}(x)H 的对角元素向量。
However, with this expression we have no control if we read or write a symbol from the tape to the vertex. Therefore, we include extra “stop gradient” operations denoted by , which are readily available in current neural network libraries. Terms inside are considered constant when differentiated, so that e.g. as opposed to the correct . With this extra operation, we can extend our above example to . Now the first term is considered constant so that minimizing it changes so that matches , i.e. we write the tape symbols at the head positions into the component of .然而，使用该表达式，我们无法控制是从纸带读取符号还是向顶点写入符号。因此，我们引入了额外的“停止梯度”操作，记为 \⋅\\backslash\cdot\backslash，这在当前的神经网络库中很容易实现。在 \⋅\\backslash\cdot\backslash 内部的项在求导时被视为常数，因此例如 ddxf(x)\g(x)\=f′(x)g(x)\frac{d}{dx}f(x)\backslash g(x)\backslash=f^{\prime}(x)g(x)，而不是正确的 f′(x)g(x)+f(x)g′(x)f^{\prime}(x)g(x)+f(x)g^{\prime}(x)。通过此额外操作，我们可以将上述示例扩展为 ∥\diag(TT𝒮(x)H)\−𝒯↓x∥2\|\backslash\diag(T^{T}\mathcal{S}(x)H)\backslash-\mathcal{T}_{\downarrow}x\|^{2}。现在，第一项被视为常数，因此最小化它会改变 xx，使得 𝒯↓x\mathcal{T}_{\downarrow}x 与 diag(TT𝒮(x)H)\diag(T^{T}\mathcal{S}(x)H) 匹配，即我们将磁头位置 𝒮(x)H\mathcal{S}(x)H 处的纸带符号写入 xx 的分量 t=𝒯↓xt=\mathcal{T}_{\downarrow}x 中。
We add a global additive constant and several read/write operations to the loss function:我们在损失函数中添加了一个全局加性常数 cc 和几个读/写操作：
| (21) |
The first least squares term writes to the current head position, the second term reads the content of the next head position into the next state and the last term moves the current head position to the next head position.第一个最小二乘项将 t′=δ2(q,t)t^{\prime}=\delta_{2}(q,t) 写入当前磁头位置，第二个项将下一个磁头位置的内容读取到下一个状态 (q′,t′)(q^{\prime},t^{\prime}) 中，最后一项将当前磁头位置移动到下一个磁头位置。
Gradient Descent
The loss function is trained by the conditional gradient method损失函数通过条件梯度法进行训练
| (22) | ||||
We slightly abuse notation and denote by the gradient with respect to the writable tapes of only, excluding the read-only tapes. As in Section 4.3, the loss function has kinks so that the gradient with respect to is not defined everywhere. Nonetheless, the one-sided directional derivatives used in the method are well defined at all points encountered during training.我们稍微滥用了符号，用 ∇T\nabla_{T} 表示仅相对于 TT 的可写纸带的梯度，排除了只读纸带。与第 4.3 节一样，损失函数存在折点，因此相对于 xx 的梯度并非在所有地方都有定义。尽管如此，该方法中使用的单侧方向导数在训练过程中遇到的所有点上都是定义良好的。
Convergence
The following proposition shows that minimizing the loss function traces the steps of the Turing machine.以下命题表明，最小化损失函数可以追踪图灵机的步骤。
Proposition 4.3.命题 4.3。
For , let with tape variables , be consecutive states of the Turing machine with , where are non-halting states and is a halting state. Assume that the loss function is defined by (21) and satisfies (18) and (20). Then and , satisfy the gradient descent updates (22) and in addition, we have对于 k=0,…,Kk=0,\dots,K，令 vk=(qk,tk)v_{k}=(q_{k},t_{k}) 以及纸带变量 TkT_{k}, HkH_{k} 为图灵机 TMTM 的连续状态，且 tk=diag(TTH)t_{k}=\diag(T^{T}H)，其中 q1,…,qK−1∉Fq_{1},\dots,q_{K-1}\not\in F 为非停机状态，qK∈Fq_{K}\in F 为停机状态。假设损失函数 ℓ\ell 由 (21) 定义并满足 (18) 和 (20)。则 xk:=evk∈ℝVx_{k}:=e_{v_{k}}\in\mathbb{R}^{V}$ 以及 TkT_{k}, HkH_{k} 满足梯度下降更新 (22)，此外我们有
| (23) | ||||||
Note that unlike Proposition 4.2, we cannot allow a line search for the gradient descent method any longer. Indeed non-halting states are vertices of the simplex and therefore the first component of the loss function is independent of and the remaining components are not necessarily decreasing.请注意，与命题 4.2 不同，我们不能再对梯度下降法进行线搜索。事实上，非停机状态 xkx_{k} 是单纯形 SS 的顶点，因此损失函数的第一个分量 ℓS(xk)=0\ell_{S}(x_{k})=0 与 kk 无关，且其余分量不一定递减。
The loss bounds in (23) are second order in for and third order for . Therefore, for sufficiently large, the loss in a halting state is strictly smaller than the loss in any non-halting state, which can be used as a stopping criterion.在 (23) 中的损失界限对于 k<Kk<K 是 bb 的二阶项，对于 k=Kk=K 是三阶项。因此，对于足够大的 bb，停机状态下的损失严格小于任何非停机状态下的损失，这可以用作停止准则。
Proof.
Without loss of generality, we assume that the additive constant in the loss function is zero. By induction, assume that , , and are iterates of the gradient descent method and that is not an accepting state. The variable is updated by with direction在不失一般性的前提下，我们假设损失函数中的加性常数 cc 为零。通过归纳法，假设 xk=ev=eq,tx_{k}=e_{v}=e_{q,t}, Tk∈Γτ={−1,1}τT_{k}\in\Gamma^{\tau}=\{-1,1\}^{\tau}, 和 Hk∈{0,1}τH_{k}\in\{0,1\}^{\tau} 是梯度下降法的迭代，且 q∉Fq\not\in F 不是接受状态。变量 xx 通过 xk+1=xk+dkx_{k+1}=x_{k}+d_{k}$ 更新，方向为
where we have disregarded two least square terms in the loss function (21) because their -gradient is zero by the stop gradient operation. Since all are linear in all corners , , and we can disregard gradients of , by Lemma 4.1 with , we have其中我们忽略了损失函数 (21) 中的两个最小二乘项，因为通过停止梯度操作，它们的 xx-梯度为零。由于所有 ℓ¯vw\bar{\ell}_{vw}$ 在所有角 Su1/4S_{u}^{1/4}, u∈Vu\in V 上都是线性的，并且我们可以忽略 \diag(TkTℋ↷xk)\\backslash\diag(T_{k}^{T}\mathcal{H}_{\curvearrowright}x_{k})\backslash 的梯度，根据引理 4.1，当 μ=1/4\mu=1/4 时，我们有
| (24) |
We have to show that the minimizer is the next state of the Turing machine, i.e. and contains a copy of the tape at the current head location shifted by .我们必须证明最小化器 ew=eq′,t′e_{w}=e_{q^{\prime},t^{\prime}} 是图灵机的下一个状态，即 q′=δ1(q,t)q^{\prime}=\delta_{1}(q,t)，且 t′t^{\prime} 包含一个在当前磁头位置处偏移了 δ3(q,t)\delta_{3}(q,t) 的纸带副本。
Let us first prove that has the correct state by showing that the first term in (24) dominates the second. To this end, note that the numbers , and , for all tapes are tape symbols contained in so that . It follows that the second summand in (24) is contained in .让我们首先证明 ewe_{w} 具有正确的状态 q′q^{\prime}，方法是证明 (24) 中的第一项主导第二项。为此，请注意对于所有纸带 i=1,…,di=1,\dots,d，数字 (𝒯↓xk)i(\mathcal{T}_{\downarrow}x_{k})_{i}, (Tk)iT⋅(𝒮(xk)Hk)i(T_{k})_{i}^{T}\cdot(\mathcal{S}(x_{k})H_{k})_{i} 和 (𝒯↓ew)i(\mathcal{T}_{\downarrow}e_{w})_{i}$ 都是包含在 {−1,1}\{-1,1\} 中的纸带符号，因此 b2γ((𝒯↓xk)i−(Tk)iT⋅(𝒮(xk)Hk)i)(𝒯↓ew)i∈{−2b2γ,0,2b2γ}b^{2}\gamma\left((\mathcal{T}_{\downarrow}x_{k})_{i}-(T_{k})_{i}^{T}\cdot(\mathcal{S}(x_{k})H_{k}\right)_{i})(\mathcal{T}_{\downarrow}e_{w})_{i}\in\{-2b^{2}\gamma,0,2b^{2}\gamma\}$。由此可知，(24) 中的第二个求和项 b2γ(𝒯↓xk−diag(TkT𝒮(xk)Hk))𝒯↓ewb^{2}\gamma\left(\mathcal{T}_{\downarrow}x_{k}-\diag(T_{k}^{T}\mathcal{S}(x_{k})H_{k})\right)\mathcal{T}_{\downarrow}e_{w}$ 包含在 {2jb2γ|j∈{−d,…,d}}\{2jb^{2}\gamma|\,j\in\{-d,\dots,d\}\}$ 中。
Since is a non-halting state, the vertex weight is zero and therefore for we have three possibilities: It is in the interval if is a successor state of in the Turing machine execution, in if is a predecessor state of with the extra factor coming from the profile in Figure 2 and else, irrespective the tape symbols and . By assumption (18) we have so that successor states are preferred over predecessor states. By the same assumption (18), we also have , i.e. the smallest possible gap between predecessor and successor states in the first gradient component is bigger than the maximal contribution of the second term in (24). Hence, the minimizer of the directional derivative (24) with vertex , is a successor state so that .由于 qq 是非停机状态，顶点权重 ωv=0\omega_{v}=0 为零，因此对于 ℓS(evw1/4)\ell_{S}\left(e_{vw}^{1/4}\right)$，我们有三种可能性：如果 q′,t′q^{\prime},t^{\prime} 是图灵机执行中 q,tq,t 的后继状态，则它在区间 [−(b3+db)γ,−b3γ]\left[-(b^{3}+db)\gamma,-b^{3}\gamma\right] 中；如果 q′,t′q^{\prime},t^{\prime} 是 q,tq,t 的前驱状态，则它在区间 [−12(b3+db)γ,−12b3γ]\left[-\frac{1}{2}(b^{3}+db)\gamma,-\frac{1}{2}b^{3}\gamma\right] 中（额外的 1/21/2 因子来自图 2 中的轮廓）；否则为 00，无论纸带符号 tt 和 t′t^{\prime} 如何。根据假设 (18)，我们有 b3≥12(b3+db)b^{3}\geq\frac{1}{2}(b^{3}+db)$，因此后继状态优于前驱状态。根据同样的假设 (18)，我们还有 12(b3−db)γ≥2db2γ\frac{1}{2}(b^{3}-db)\gamma\geq 2db^{2}\gamma$，即第一个梯度分量 ℓ(⋅)\ell(\cdot)$ 中前驱状态和后继状态之间最小可能的间隙大于第二项 (24) 的最大贡献 2db2γ2db^{2}\gamma$。因此，方向导数 (24) 的最小化器 ewe_{w}（顶点 w=(q′,t′)w=(q^{\prime},t^{\prime})）是后继状态，即 q′=δ1(q,t)q^{\prime}=\delta_{1}(q,t)$。
Next, we show that contains the correct tape symbol. Since we already know that is a successor state, we use the definition (17) of the weights to simplify the gradient descent update (24) to with接下来，我们证明 t′t^{\prime} 包含正确的纸带符号。由于我们已经知道 q′q^{\prime} 是后继状态，我们使用权重的定义 (17) 来简化梯度下降更新 (24) 为 xk+1=eq′,t′x_{k+1}=e_{q^{\prime},t^{\prime}}$，其中
Eliminating constant summands and sorting the remaining terms with respect to components , we obtain消除常数项并根据分量 i∈{1,…,d}i\in\{1,\dots,d\} 对剩余项进行排序，我们得到
| (25) |
where is one if and zero else. Since we want to read the tape symbol of tape at the next head position into the component of the successor state , we have to show that the minimizer of the last equation satisfies . We distinguish two cases:其中 δti,ti′\delta_{t_{i},t^{\prime}_{i}}$ 如果 ti=ti′t_{i}=t^{\prime}_{i} 则为 1，否则为 0。由于我们想将下一个磁头位置处纸带 ii 的纸带符号读取到后继状态 ewe_{w} 的分量 ti′t^{\prime}_{i}$ 中，我们必须证明最后一个方程的最小化器满足 ti′=(Tk)iT⋅(𝒮(xk)Hk)it^{\prime}_{i}=(T_{k})_{i}^{T}\cdot(\mathcal{S}(x_{k})H_{k})_{i}$。我们区分两种情况：
- 1.
Case 1: Let us assume that , i.e. the tape symbol of the current vertex already matches the one of the successor state of the TM. In this case, the second term in (25) is zero and the term in (25) ensures that , as required.情况 1：假设 ti=(Tk)iT⋅(𝒮(xk)Hk)it_{i}=(T_{k})_{i}^{T}\cdot(\mathcal{S}(x_{k})H_{k})_{i}$，即当前顶点 xkx_{k}$ 的纸带符号已经与 TM 后继状态的符号匹配。在这种情况下，(25) 中的第二项为零，(25) 中的项 δti,ti′\delta_{t_{i},t^{\prime}_{i}}$ 确保了 ti′=tit_{i}^{\prime}=t_{i}$，符合要求。
- 2.
Case 2: Let us now assume that . One easily verifies that the second term of (25) is for and for . The first term of (25) is either or zero, depending on the choice of . Since by assumption (18), the second term dominates the choice and we obtain as required.情况 2：假设 ti≠(Tk)iT⋅(𝒮(xk)Hk)it_{i}\neq(T_{k})_{i}^{T}\cdot(\mathcal{S}(x_{k})H_{k})_{i}$。人们可以很容易地验证，对于 ti′=(Tk)iT⋅(𝒮(xk)Hk)it^{\prime}_{i}=(T_{k})_{i}^{T}\cdot(\mathcal{S}(x_{k})H_{k})_{i}$，(25) 的第二项为 −2b2γ-2b^{2}\gamma，而对于 ti′≠(Tk)iT⋅(𝒮(xk)Hk)it_{i}^{\prime}\neq(T_{k})_{i}^{T}\cdot(\mathcal{S}(x_{k})H_{k})_{i}$，它为 2b2γ2b^{2}\gamma$。(25) 的第一项要么是 bγb\gamma，要么是零，取决于 ti′t^{\prime}_{i}$ 的选择。由于根据假设 (18) b2γ>bγb^{2}\gamma>b\gamma$，第二项在选择中占主导地位，我们得到 ti′=(Tk)iT⋅(𝒮(xk)Hk)it_{i}^{\prime}=(T_{k})_{i}^{T}\cdot(\mathcal{S}(x_{k})H_{k})_{i}$，符合要求。
It remains to consider the gradient descent updates and . By the stop gradient operations, we have剩下的就是考虑梯度下降更新 Tk+1T_{k+1}$ 和 Hk+1H_{k+1}$。通过停止梯度操作，我们有
Recall our convention that is the gradient excludes the read-only tapes . Therefore, we confine the sums and components above to the writable tapes not in . The remaining read-only tapes are unchanged by both the Turing machine execution and the gradient descent updates. Using that is the indicator vector for the head location and , the last equation implies that回顾我们的约定，即 ∇T\nabla_{T}$ 是排除只读纸带 RORO 的梯度。因此，我们将上述求和和分量限制在不在 RORO 中的可写纸带上。剩余的只读纸带不受图灵机执行和梯度下降更新的影响。利用 (Hk)i∈{0,1}τ(H_{k})_{i}\in\{0,1\}^{\tau}$ 是磁头位置的指示向量，且 (𝒯↷xk)i=δ2(q,t)i(\mathcal{T}_{\curvearrowright}x_{k})_{i}=\delta_{2}(q,t)_{i}$，最后一个方程意味着
so that is indeed the content of the tape in the next step of the Turing machine.因此 Tk+1T_{k+1}$ 确实是图灵机下一步中纸带的内容。
The update of the head location works analogously. We have磁头位置 HkH_{k}$ 的更新以类似方式进行。我们有
and therefore因此
i.e. the new head position is shifted by as required.即新的磁头位置根据 𝒮(xk)\mathcal{S}(x_{k})$ 进行了偏移，符合要求。
In order to show the bounds (23), note that all tape symbols are contained in , and the head locations are indicator vectors with entries in . Hence, the last three summands in the loss (21) are in the intervals and , , respectively. The bound (23) then follows from the observation that on vertices is in a halting state and zero else.为了证明界限 (23)，请注意所有纸带符号都包含在 {−1,1}\{-1,1\}$ 中，磁头位置是条目为 {0,1}\{0,1\}$ 的指示向量。因此，损失 (21) 中的最后三项分别在区间 [0,2dγ][0,2d\gamma]$，[0,8b2dγ][0,8b^{2}d\gamma]$ 和 [0,dγ][0,d\gamma]$ 中。界限 (23) 随后得自以下观察结果：在顶点上，ℓS\ell_{S}$ 在停机状态下为 −b3γ-b^{3}\gamma，否则为零。
∎
5 Application to Supervised Learning5 在监督学习中的应用
In this section, we prove the main result of the paper as stated in Section 2, i.e. we construct an extended network that adjusts its weights according to the computation of a Turing machine during supervised learning. This is achieved by connecting the output of the Turing machine tracing from the last section with the weights of the primary network and to ensure that proper gradients are passed back into the tracing component by an optimization of a standard least squares loss.在本节中，我们证明了本文第 2 节所述的主要结果，即我们构建了一个扩展网络，其权重根据监督学习期间图灵机的计算进行调整。这是通过将上一节中图灵机追踪的输出与主网络的权重连接起来，并确保通过优化标准最小二乘损失，将正确的梯度传回追踪组件来实现的。
5.1 Construction of the Extended Network5.1 扩展网络的构造
The construction of the extended network is shown and briefly explained in Figure 1 in Section 3. In this section, we fill in some details that we skipped over in its initial description.扩展网络 F(x,(s,t))F(x,(s,t))$ 的构造如图 1（第 3 节）所示并进行了简要说明。在本节中，我们将补充其初步描述中跳过的一些细节。
The extended network mostly consists of two main branches connected by some extra “switches”. The first branch contains the primary network depending on the input and its parameters , which are no longer trainable but outputs of some hidden layers. The second branch consists of a network that emulates the Turing machine and is constructed similar to the Turing machine tracing in Propositions 4.2 and 4.3. The switches then pass one of these branches to the network output. The components of the extended network in Figure 1 are defined as follows:扩展网络主要由两个通过一些额外“开关”连接的主要分支组成。第一个分支包含主网络 fθ(x)f_{\theta}(x)$，它依赖于输入 xx 及其参数 θ\theta（不再是可训练的，而是某些隐藏层的输出）。第二个分支由一个模拟图灵机 TMTM 的网络组成，其构造类似于命题 4.2 和 4.3 中的图灵机追踪。然后，开关将这些分支中的一个传递给网络输出。图 1 中扩展网络的组件定义如下：
- •
: Neural network input.xx：神经网络输入。
- •
holds a copy of the labels after the first training step. Note that we cannot pass into the Turing machine directly because it is only implicitly accessible through the loss function.z∈ℝn×nz\in\mathbb{R}^{n\times n}$ 保存了第一次训练步骤后标签 yy 的副本。请注意，我们不能直接将 yy 传入图灵机，因为它只能通过损失函数隐式访问。
- •
: Trainable parameters, representing the Turing machine’s state as in Sections 4.3, 4.4. They Contain for the state state of the Turing machine and, depending on the construction, for the tape symbols and head positions.s,T,Hs,T,H：可训练参数，表示图灵机的状态（如第 4.3、4.4 节所述）。它们包含用于图灵机状态的 s∈Ss\in S，以及根据构造的不同，包含用于纸带符号和磁头位置的 T,H∈ℝdτT,H\in\mathbb{R}^{d\tau}$。
Although are mostly trainable weights, the inputs and are written on the read-only tapes of the Turing machine. All edges leading into and out of this node use quantization and de-quantization, except for the one to . No derivatives of the (de)quantization are required during training.虽然 s,T,Hs,T,H$ 大多是可训练权重，但输入 xx 和 zz 被写入图灵机的只读纸带上。除通往 fTMf_{TM}$ 的边外，所有通向和离开该节点的边都使用量化和去量化。训练期间不需要 (去) 量化的导数。
- •
: Weights of the primary network, read from the output tape of the Turing machine and not trainable.θ\theta：主网络的权重，从图灵机的输出纸带读取，不可训练。
- •
: The primary neural network, depending on input and weights .fθf_{\theta}：主神经网络，取决于输入 xx 和权重 θ\theta$。
- •
: Component of the network associated with the Turing machine . With initial and on its read-only tape, it halts with weights on the output tape and returns a vector that is fed into the downstream node as described below.fTMf_{TM}：与图灵机 TMTM 关联的网络组件。初始 xx 和 yy 在其只读纸带上，它在输出纸带上以权重 θ\theta 停机，并返回一个向量 uu，该向量被馈送到下游节点 snets_{net}$，如下所述。
- •
: Switch between the Turing machine output and the output of the primary network .snets_{net}：在图灵机输出 fTMf_{TM}$ 和主网络输出 fθf_{\theta}$ 之间切换的开关。
- •
: Switch for reading the labels into and the remaining training.sinits_{init}：用于将标签 yy 读取到 zz 中以及进行剩余训练的开关。
- •
: Output of the extended network.outout：扩展网络的输出。
- •
Red boxes: Trainable weights.红色框：可训练权重。
- •
Dotted Arcs denote “stop-gradient” operations, i.e. for a dotted arc from node to node , we artificially set the gradient , even if that does not correspond the actual gradient. This means that we consider non-trainable or constant whenever it passes through . This is a common feature implemented in most current deep learning libraries.虚线弧表示“停止梯度”操作，即对于从节点 n1n_{1}$ 到节点 n2n_{2}$ 的虚线弧，我们人为地设置梯度 ∂n2∂n1:=0\frac{\partial n_{2}}{\partial n_{1}}:=0$，即使这不对应于实际梯度。这意味着每当 n1n_{1}$ 通过 n2n_{2}$ 时，我们都将其视为不可训练或常数。这是大多数当前深度学习库中实现的一个常见功能。
- •
Function arguments are ordered left to right with respect to incoming arcs in Figure 1 so that e.g. takes arguments in the order .函数参数在图 1 中相对于传入弧从左到右排序，例如 sinits_{init}$ 按 sinit(snet,z)s_{init}(s_{net},z)$ 的顺序接收参数。
The Turing Machine contains one read-only tape for the inputs and . Unlike the other tapes, the read-only tape is not a trainable network weight but a hidden layer of width containing a quantization of the input and the weight (which will hold a copy of the labels ). Likewise, the weights of the primary network become a hidden layer containing a de-quantization of the output tape of the Turing machine. On a practical computer all variables are already stored in quantized format and can directly be written to and from the tapes. Formally, (de)quantizations can also be computed by a neural network from floating point numbers, see Appendix B for more details.图灵机 TMTM 包含一个用于输入 xx 和 yy 的只读纸带。与其他纸带不同，只读纸带不是可训练的网络权重，而是宽度为 τ\tau 的隐藏层，包含输入 xx 和权重 zz（将保存标签 yy 的副本）的量化值。同样，主网络的权重 θ\theta 成为一个隐藏层，包含图灵机输出纸带的去量化值。在实际计算机上，所有变量都已经以量化格式存储，可以直接写入纸带或从纸带读出。形式上，(去) 量化也可以由神经网络从浮点数计算得出，详见附录 B。
In the description of the main result, in particular for the loss (2), we have split up the trainable weights as into variables that are restricted to a simplex and variables that are unrestricted. Now, with the full description of the extended network, we have and . Likewise, the vector valued learning rate in (3) is split into three components , and for the three components of the trainable weights, respectively.在主要结果的描述中，特别是对于损失 (2)，我们将可训练权重 (s,t)(s,t)$ 拆分为受限于单纯形的变量 ss 和不受限制的变量 tt。现在，有了扩展网络的完整描述，我们有 s=ss=s$ 和 t=T,H,zt=T,H,z$。同样，(3) 中的向量值学习率 α\alpha$ 被拆分为三个分量 αT,αH,αz\alpha_{T}, \alpha_{H}, \alpha_{z}$，分别对应可训练权重的三个分量 H,T,zH,T,z$。
After training, both switches and are “open”, the network computes with read from the Turing machine’s tape. Nonetheless, in the following sections, we describe the training process bottom-up in the network starting from the initial state.训练完成后，开关 sinits_{init}$ 和 snets_{net}$ 均“打开”，网络计算 fθ(x)f_{\theta}(x)$，其中 θ\theta 从图灵机的纸带中读取。尽管如此，在接下来的章节中，我们将从初始状态开始，自下而上地描述网络中的训练过程。
5.2 Reading the Labels5.2 读取标签
In the first gradient descent step, we read the labels into the trainable variable and then shut off this reading process for the rest of the training. This is done with the switch , which, if fully turned on or off, lets either the first or second input pass through unchanged. The switch is triggered by the size of its second input variable . Specifically, for two matrices with the shape of the data and given by (5), the switch has the following properties:在第一次梯度下降步骤中，我们将标签读取到可训练变量 zz 中，然后在训练的其余部分关闭此读取过程。这是通过开关 sinit(u,z)s_{init}(u,z)$ 完成的，如果完全打开或关闭，它会让第一个或第二个输入原样通过。该开关由其第二个输入变量 zz 的大小触发。具体而言，对于两个矩阵 u,z∈ℝn×mu,z\in\mathbb{R}^{n\times m}$（具有数据 yy 的形状）和 (5) 给出的 ϵ\epsilon$，该开关具有以下性质：
where is the identity matrix. This can be easily realized by a cutoff function , with for and for and其中 I∈ℝ(n×m)×(n×m)I\in\mathbb{R}^{(n\times m)\times(n\times m)}$ 是单位矩阵。这可以很容易地通过截止函数 ψ:[0,∞)→[0,1]\psi:[0,\infty)\to[0,1]$ 实现，其中当 0≤t<13ϵ0\leq t<\frac{1}{3}\epsilon$ 时 ψ(t)=1\psi(t)=1，当 23ϵ<t\frac{2}{3}\epsilon<t$ 时 ψ(t)=0\psi(t)=0$，并且
The cutoff function does not need to be differentiable in the interval and can be constructed e.g. from two units. Let us now consider the first gradient descent step. With initial value , the chain rule implies截止函数不需要在区间 [ϵ/3,2ϵ/3][\epsilon/3,2\epsilon/3]$ 内可微，例如可以由两个 ReLUReLU 单元构造。现在让我们考虑第一次梯度下降步骤。对于初始值 z0=0z_{0}=0$，链式法则意味着
for . Together with for input , it follows that对于 □∈s,T,H\Box\in\{s,T,H\}$。连同输入 z0=0z_{0}=0$ 时 out=0out=0$，可以得出
and therefore, the after one gradient descent step with learning rate for , we have因此，在对 zz 使用学习率 αz:=1\alpha_{z}:=1$ 进行一次梯度下降步骤后，我们有
Since by assumption , for the next gradient descent steps we have由于根据假设 ‖y‖22>ϵ\|y\|_{2}^{2}>\epsilon$，对于后续的梯度下降步骤，我们有
where we have used that only depends of via a stop gradient operation so that the latter gradient is zero. This directly implies that其中我们利用了 snets_{net}$ 仅通过停止梯度操作依赖于 zz，因此后者的梯度为零。这直接意味着
Likewise, we have同样，我们有
| (26) | ||||
for so that the parameters对于 □∈{s,T,H}\Box\in\{s,T,H\}$，因此参数
train as if we would train the partial network with output only. Technically, as in (6) the node inside only has one-sided directional derivatives, but one easily verifies that this does not alter the chain rule.训练方式就好像我们只训练输出为 snets_{net}$ 的部分网络一样。从技术上讲，如 (6) 中所述，snets_{net}$ 内部的节点 fTMf_{TM}$ 仅具有单侧方向导数，但人们可以很容易地验证这不会改变链式法则。
5.3 Switching between Neural Network and Turing Machine5.3 在神经网络和图灵机之间切换
The second switch selects between the primary network and the Turing machine . Just as the switch , it has two inputs , with and to shorten the notation below, and the properties第二个开关 snets_{net}$ 在主网络 fθ(x)f_{\theta}(x)$ 和图灵机 fTM(s,t)f_{TM}(s,t)$ 之间进行选择。就像开关 sinits_{init}$ 一样，它有两个输入 snet(f,u)s_{net}(f,u)$（其中 f=fθf=f_{\theta}$ 且 u=fTMu=f_{TM}$ 以缩短下文的符号），并具有以下性质
| (27) | ||||||||
| if and | ||||||||
| (28) | ||||||||
if for some to be specified later. Similar to this can be realized by a smooth cutoff function with for and for for some with and如果 ‖u‖22>2B¯\|u\|_{2}^{2}>2\underline{B}$，其中 B¯<B¯\underline{B}<\overline{B}$ 稍后指定。类似于 sinits_{init}$，这可以通过平滑截止函数 ϕ:[0,∞)→[0,1]\phi:[0,\infty)\to[0,1]$ 实现，其中当 t≤2B¯+δt\leq 2\underline{B}+\delta$ 时 ϕ(t)=0\phi(t)=0，当 t≥2B¯−δt\geq 2\overline{B}-\delta$ 时 ϕ(t)=1\phi(t)=1$，对于某个 δ>0\delta>0$ 且 2B¯+δ<2B¯−δ2\underline{B}+\delta<2\overline{B}-\delta$，并且
Let be a gradient descent step after the initialization in the first step and before the iterate when training is terminated by the stopping criterion (4) and the outputs of the network node in the corresponding steps. Starting from its initial state till the st step, one step before the halting state, we will ensure below that令 k∈{1,…,K}k\in\{1,\dots,K\}$ 为初始化之后且在训练因停止准则 (4) 而终止的迭代 KK 之前的梯度下降步骤，fTMkf_{TM}^{k}$ 为相应步骤中网络节点 fTMf_{TM}$ 的输出。从其初始状态 s0=s1s_{0}=s_{1}$ 到第 (K−1)(K-1)$ 步（停机状态前一步），我们将在下面确保
| (29) | ||||||
Thus before the Turing machine has halted, we have因此，在图灵机停机之前，我们有
and
| (30) |
for , whereas after halting, we have对于 □∈{s,T,H}\Box\in\{s,T,H\}$，而停机后，我们有
Again, we have used that the chain rule for the one-sided directional derivatives in works as usual. Thus, we obtain the updates同样，我们使用了 fTMf_{TM}$ 中单侧方向导数的链式法则可以正常工作。因此，我们得到更新
| (31) | ||||
for so that while the Turing machine has not halted, the network output corresponds to the output of and all weight updates are equivalent to training alone, independent of the primary network . After the Turing machine is finished, the switch deactivates the Turing machine branch an outputs the primary network with the values of that the Turing machine has written on its output tape.对于 k=1,…,K−1k=1,\dots,K-1$，因此当图灵机尚未停机时，网络输出对应于 fTMf_{TM}$ 的输出，所有权重更新等同于仅训练 fTMf_{TM}$，与主网络 fθf_{\theta}$ 无关。图灵机完成后，开关 snets_{net}$ 停用图灵机分支 fTMf_{TM}$，并输出主网络 fθ(x)f_{\theta}(x)$，其中 θ\theta 的值为图灵机在其输出纸带上写入的值。
5.4 Training the Turing Machine5.4 训练图灵机
Finally, we have to construct the node such that the bounds (29) of its input hold and gradient descent training traces the Turing machine calculations so that the final state of the output tape contains the weights . To this end, we apply either Proposition 4.2 or Proposition 4.3, which both rely on a carefully crafted loss associated with the Turing machine , which is different from the least squares loss in our application. We reconcile these two losses as follows: After reading the labels into , we can calculate a vector that is orthogonal to and has unit length, see Appendix C. We then define the output of the node by最后，我们必须构建节点 fTMf_{TM}$，使得其输入的界限 (29) 成立，并且梯度下降训练能够追踪图灵机的计算，从而使输出纸带的最终状态包含权重 θ=TM(x,y)\theta=TM(x,y)$。为此，我们应用命题 4.2 或命题 4.3，两者都依赖于与图灵机 TMTM 关联的精心设计的损失 ℓTM\ell_{TM}$，这与我们应用中的最小二乘损失不同。我们通过以下方式协调这两个损失：将标签 yy 读取到 zk=yz_{k}=y$ 中后，我们可以计算一个与 zz 正交且具有单位长度的向量 f⟂(z)f_{\perp}(z)$，详见附录 C。然后，我们通过下式定义节点 fTMf_{TM}$ 的输出
By choosing appropriate constants, we ensure that is always non-negative below. This directly yields通过选择适当的常数，我们确保 ℓTM\ell_{TM}$ 在下文中始终是非负的。这直接得出
for so that with (31) we obtain the gradient descent updates对于 □∈{s,T,H}\Box\in\{s,T,H\}$，因此利用 (31) 我们得到梯度下降更新
| (32) | ||||
for the gradient descent steps . These updates are identical to the gradient descent methods in Proposition 4.2 and Proposition 4.3 (with appropriate choices of the learning rates and ) so that for , the variables , and have the same values if we train the loss or alternatively the loss directly. Note that we also have对于梯度下降步骤 1,…,K−11,\dots,K-1$。这些更新与命题 4.2 和命题 4.3 中的梯度下降法相同（使用适当的学习率 αT\alpha_{T}$ 和 αH\alpha_{H}$ 选择），因此对于 k=1,…,K−1k=1,\dots,K-1$，如果我们训练损失 12‖out−y‖2\frac{1}{2}\|out-y\|^{2}$ 或者直接训练损失 ℓTM\ell_{TM}$，变量 sks_{k}, TkT_{k}$ 和 HkH_{k}$ 具有相同的值。请注意，我们还有
| (33) |
which we will need for triggering the switch , later.稍后我们将需要它来触发开关 snets_{net}$。
We choose the stopping bound in (4) such that and for the loss , we use one of the following two options:我们在 (4) 中选择停止界限 BstopB_{stop}$，使得 ∥fTM(x,y)(x)−y)∥≤Bstop\|f_{TM(x,y)}(x)-y)\|\leq B_{stop}$，对于损失 ℓTM\ell_{TM}$，我们使用以下两个选项之一：
- 1.
With the loss function of Proposition 4.2 and extra condition (15), we include the full state of the Turing machine in the simplex with possible states of the finite control, possible tape contents and possible head positions. Since the tape is already included in the simplex we do not need the extra variables and set so that are trivial. The states during training will be vertices of only so that we can easily read the weights of the primary network from directly. In summary, we have使用命题 4.2 的损失函数和额外条件 (15)，我们将图灵机的完整状态包含在单纯形 SS 中，其中 |Q||Q|$ 为有限控制器的可能状态，2τ2^{\tau}$ 为可能的纸带内容，τ\tau 为可能的磁头位置。由于纸带已经包含在单纯形 SS 中，我们不需要额外的变量 T,HT,H$，并设置 τ=0\tau=0$，使得 T,H∈ℝ0T,H\in\mathbb{R}^{0}$ 是平凡的。训练期间的状态 sk∈Ss_{k}\in S$ 将仅为 SS 的顶点，因此我们可以很容易地直接从 SS 中读取主网络 fθf_{\theta}$ 的权重 θ\theta$。总之，我们有
In order to choose the constants , from the definition (27), (28) of and and from the loss in (10), let and be the smallest and second but smallest weights. Then, we choose all weights and , so that为了从 snets_{net}$ 的定义 (27), (28) 和 ωv\omega_{v}$ 以及损失 ℓTM\ell_{TM}$ 在 (10) 中的 BB 中选择常数 B¯\underline{B}, B¯\overline{B}$，令 ω0=minv∈V(S)ωv\omega_{0}=\min_{v\in V(S)}\omega_{v}$ 和 ω1∈min{ωv|v∈V(S),ωv≠ω0}\omega_{1}\in\min\{\omega_{v}|\,v\in V(S),\,\omega_{v}\neq\omega_{0}}$ 分别为最小和第二小的权重。然后，我们选择所有权重 ωv\omega_{v}$ 和 B¯\underline{B}, B¯\overline{B}$，使得
With this choice, by Proposition 4.2 and (32) the minimization of traces the steps of the Turing machine until we reach a halting state. Then by (33), we have and by definition, the switch is flipped so that it lets the primary network pass to the output with weights read from the final tape of .通过此选择，根据命题 4.2 和 (32)，最小化 12‖out−y‖2\frac{1}{2}\|out-y\|^{2}$ 会追踪图灵机 TMTM 的步骤，直到达到停机状态。然后根据 (33)，我们有 ‖fTM‖2=2ℓTM<2B¯\|f_{TM}\|^{2}=2\ell_{TM}<2\underline{B}$，根据定义，开关 snets_{net}$ 被翻转，使其将主网络 fθf_{\theta}$ 传递到输出，权重 θ=TM(x,y)\theta=TM(x,y)$ 从 fTMf_{TM}$ 的最终纸带读取。
- 2.
With the loss function of Proposition 4.3, the finite control and tape symbols at the head positions are contained in the states of the simplex and the full tape and head positions in the variables , so that使用命题 4.3 的损失函数 ℓTM\ell_{TM}$，有限控制器和磁头位置处的纸带符号包含在单纯形 SS 的状态中，完整的纸带和磁头位置包含在变量 TT, HH 中，因此
where without loss of generality we assume that the Turing machine has two tapes: One for input and on for output. In order to select the constants and from definition (27), (28) and , and of the loss function (17) and (21), we first choose sufficiently large so that the condition (18) holds and , which by (23) ensures that the loss for the halting states is strictly smaller than the loss for the non-halting states. Next, we select the positive global scaling factor , the global additive constant and the bounds , from (29) such that the loss is positive and其中在不失一般性的前提下，我们假设图灵机有两条纸带：一条用于输入，一条用于输出。为了从定义 (27), (28) 以及损失函数 (17) 和 (21) 的 bb, cc 和 γ\gamma$ 中选择常数 B¯\underline{B}, B¯\overline{B}$，我们首先选择足够大的 bb，使得条件 (18) 成立，并且 8b2dγ+3dγ−b3γ<08b^{2}d\gamma+3d\gamma-b^{3}\gamma<0$，根据 (23)，这确保了停机状态的损失严格小于非停机状态的损失。接下来，我们选择正全局缩放因子 γ\gamma$、全局加性常数 cc 和 (29) 中的界限 B¯\underline{B}, B¯\overline{B}$，使得损失 ℓTM(x,T,H)\ell_{TM}(x,T,H)$ 为正且
By (23) the left hand side is an upper bound for at halting states and the right and side a lower bound for non-halting states. Note that the left hand side is smaller than the right hand side by our choice of . As for the alternative construction, this ensures that once a halting state is reached, the switch passes the primary network to the output.根据 (23)，左侧是停机状态下 ℓTM(x,T,H)\ell_{TM}(x,T,H)$ 的上界，右侧是非停机状态的下界。请注意，根据我们对 bb 的选择，左侧小于右侧。对于替代构造，这确保了一旦达到停机状态，开关 snets_{net}$ 就会将主网络 fθf_{\theta}$ 传递到输出。
Once the switch is flipped, the primary network is passed to the output with weights read from the final state of ’s tape. Since we have chose such that , the stopping criterion of the gradient descent method applies and no further training steps are executed.一旦开关 snets_{net}$ 被翻转，主网络 fθf_{\theta}$ 就会被传递到输出，权重 θ=TM(x,y)\theta=TM(x,y)$ 从 fTMf_{TM}$ 纸带的最终状态读取。由于我们选择了 BstopB_{stop}$，使得 ∥fTM(x,y)(x)−y)∥≤Bstop\|f_{TM(x,y)}(x)-y)\|\leq B_{stop}$，梯度下降法的停止准则适用，不再执行进一步的训练步骤。
5.5 Number of Layers5.5 层数
Finally, let us count the number of layers in the extended network. The switches and can be implemented with layers each: E.g. for最后，让我们计算扩展网络中的层数。开关 sinits_{init}$ 和 snets_{net}$ 每个都可以用 33 层实现：例如对于
we have one layer for the norm , one for the cutoff function and one for the outer products of the scalar weights with the vectors and .我们有一层用于范数 ‖z‖22\|z\|_{2}^{2}$，一层用于截止函数 ψ\psi$，一层用于标量权重与向量 uu 和 zz 的外积。
Next, is defined by接下来，fTMf_{TM}$ 定义为
We need one layer for the product of the square root with and can implement the latter two terms on parallel layers. The function can be implemented with layers as in Appendix C. The square root is one layer and can be implemented in one layer for the outer sum in (13) or (21) and two layers for all involved functions from Section (A). The least squares terms in (21) can be computed in one extra layer that is parallel to the others.我们需要一层用于平方根与 f⟂f_{\perp}$ 的乘积，并且可以在并行层上实现后两项。函数 f⟂f_{\perp}$ 可以像附录 C 中那样用 55 层实现。平方根是一层，ℓTM\ell_{TM}$ 可以用一层实现（用于 (13) 或 (21) 中的外求和），并用两层实现来自 (A) 节的所有相关函数。 (21) 中的最小二乘项可以在与其它层并行的额外一层中计算。
In summary, the extend network requires at most 12 layers plus the layers form the primary network and eventually some layers for quantization and de-quantization of the Turing machine tapes variables .总之，扩展网络最多需要 12 层，加上主网络 ff 的层，以及最终用于图灵机纸带变量 TT 量化和去量化的一些层。
Appendix A Lagrange Basis附录 A 拉格朗日基
Let with indices in some index set be an orthonormal basis of with dimension and be the standard simplex spanned by the vertices , . Define the sub-simplex by cutting out a corner of the standard simplex with vertices and for .设 ${e_{v}}$ 为 $\mathbb{R}^{V}$ 的一组正交基，其中 $v$ 属于某个指标集 $V$，其维度为 $m=|V|$，并设 $S$ 为以顶点 ${e_{v}}$ ($v \in V$) 为顶点的标准单纯形。通过切除标准单纯形 $S$ 的一个顶点 $e_{v}$ 和顶点 $e_{vw}^{\mu}=(1-\mu)e_{v}+\mu e_{w}$（对于 $v \neq w \in V$）所构成的角，定义子单纯形 $S_{v}^{\mu}$。
We need a Lagrange basis function or equivalently a finite element hat function associated with this corner. Although the construction is standard, the following lemma provides an explicit formula, which entails that it can be easily constructed from a network.我们需要一个与该角相关的拉格朗日基函数 $\ell_{v}^{\mu}$，或者等价地，一个有限元帽函数。虽然这种构造是标准的，但以下引理提供了一个显式公式，这意味着它可以很容易地由 ReLU 网络构造出来。
Lemma A.1.引理 A.1。
For and , define对于 $v \in V$ 和 $0 < \mu \leq 1$，定义
Then is linear on and则 $\ell_{v}^{\mu}$ 在 $S_{v}^{\mu}$ 上是线性的，且
Geometrically, the scaled normal vector points from the barycenter of the face opposite of to .几何上，缩放后的法向量 $\frac{\mu m}{m-1}n_{v}^{\mu}=e_{v}-\frac{1}{m-1}\sum_{w \neq v}e_{w}$ 从 $e_{v}$ 对面的面的重心指向 $e_{v}$。
Proof.
Since is fixed throughout the proof, we abbreviate , and . For any , we have由于 $\mu$ 在整个证明过程中是固定的，我们将 $n_{v}=n_{v}^{\mu}$、$d=d_{\mu}$ 和 $\ell_{v}=\ell_{v}^{\mu}$ 简写。对于任何 $w \neq v$，我们有
This directly yields这直接得出
and therefore
Note that is zero on the face spanned by the vertices , and therefore is linear on and its complement . In fact is identically zero on the latter because it is a convex set with vertices and with and is zero on all of these.注意 $n_{v}^{T}x-d=0$ 在由顶点 $e_{vw}^{\mu}$ ($v \neq w$) 构成的面上为零，因此 $\ell_{v}^{\mu}$ 在 $S_{v}^{\mu}$ 及其补集 $S \setminus S_{v}^{\mu}$ 上是线性的。事实上，$\ell_{v}^{\mu}$ 在后者上恒为零，因为它是一个以 $e_{w}$ 和 $e_{vw}^{\mu}$ ($w \neq v$) 为顶点的凸集，且 $\ell_{v}^{\mu}$ 在所有这些点上均为零。
∎
In the following Lemma, we only consider and use the abbreviations and . Recall that denotes the vertices of a simplex.在随后的引理中，我们仅考虑 $\mu=1/2$，并使用缩写 $S_{v}=S_{v}^{1/2}$ 和 $e_{vw}=e_{vw}^{1/2}=\frac{1}{2}(e_{v}+e_{w})$。回想一下，$V(\cdot)$ 表示单纯形的顶点。
Lemma A.2.引理 A.2。
For with , and barycenter of , define对于 $v, w \in V$ ($v \neq w$) 以及 $S$ 的重心 $b=\frac{1}{m}\sum_{u \in V}e_{u}$，定义
with and defined in Lemma A.1. Then is linear on each corner and其中 $\ell_{v}^{1/2}$ 和 $\ell_{w}^{1/2}$ 在引理 A.1 中定义。那么 $\ell_{vw}$ 在每个角 $S_{v}$ 上是线性的，且
Geometrically, defines a plane that contains all vertices of and except , and , even though these are more vertices than needed to span a plane. In addition, the plane cuts the simplex into two pieces, one that contains and and another that contains all other corners , .几何上，$n_{vw}x-c=0$ 定义了一个平面，该平面包含了 $S_{v}$ 和 $S_{w}$ 的所有 $(2|V|-3)$ 个顶点，除了 $e_{v}$、$e_{w}$ 和 $e_{vw}$，尽管这些顶点比跨越一个平面所需的要多。此外，该平面将单纯形 $S$ 切割成两部分，其中一部分包含 $S_{v}$ 和 $S_{w}$，另一部分包含所有其他角 $S_{u}$ ($u \neq v, w$)。
Proof.
First note that for any two indices , we have首先注意，对于任意两个指标 $s, t \in V$，我们有
Furthermore, one directly verifies that此外，直接验证可得
for . This yields对于 $t, u \notin \{v, w\}$。这得出
and therefore, using Lemma A.1, we conclude that因此，利用引理 A.1，我们得出
for all . From the value of on the vertices of the simplices , and their convexity, we conclude that the kinks from the units are not contained in the interior of any of the corners , and hence is linear in each of them. This directly implies the lemma.对于所有 $u \notin \{v, w\}$。根据 $n_{vw}x-c$ 在单纯形 $S_{t}$ ($t \in V$) 顶点上的值及其凸性，我们得出 ReLU 单元产生的折点不包含在任何角 $S_{t}$ ($t \in V$) 的内部，因此 $\ell_{vw}$ 在其中每一个角上都是线性的。这直接意味着该引理成立。
∎
Lemma A.3.引理 A.3。
For , and , let be the “unsymmetric corner” or simplex with vertices and and for . Then there is a and such that the function satisfies对于 $v, w \in V$ ($v \neq w$) 和 $0 < \mu \leq 1$，设 $S_{vw}^{\mu}$ 为“非对称角”或单纯形，其顶点为 $e_{v}$、$(1-\mu)e_{v}+\mu e_{w}$ 以及 $\frac{1}{2}(e_{v}+e_{u})$（对于 $u \neq v, w$）。那么存在一个 $n \in \mathbb{R}^{V}$ 和 $d \in \mathbb{R}$，使得函数 $\ell_{vw,\mu}^{s}(x)=\operatorname{ReLU}(n^{T}x-d)$ 满足
for all .对于所有 $u \neq v, w$。
Proof.
One easily verifies that the vertices and for of , or equivalently , are in general position so that they define a unique hyperplane given by with normal and scalar .人们可以很容易地验证 $S_{vw}^{\mu}$ 的顶点 $(1-\mu)e_{v}+\mu e_{w}$ 和 $\frac{1}{2}(e_{v}+e_{u})$（对于 $u \neq v, w$），或者等价地 $V(S_{vw}^{\mu}) \setminus \{e_{v}\}$，处于一般位置，因此它们定义了一个唯一的超平面，由 $\{x \in \mathbb{R}^{N}: \bar{n}^{T}x+\bar{d}=0\}$ 给出，其中法向量 $\bar{n} \in \mathbb{R}^{N}$ 和标量 $\bar{d}$。
Geometrically, the hyperplane cuts the simplex from the larger simplex . Therefore its corner vertex is not contained in the plane, which can easily be checked algebraically. Thus, we have and upon rescaling we obtain a new vector and scalar so that defines the same hyperplane and we have .几何上，该超平面将单纯形 $S_{vw}^{\mu}$ 从更大的单纯形 $S$ 中切出。因此其角顶点 $e_{v}$ 不包含在该平面内，这一点可以很容易地通过代数方法验证。因此，我们有 $\bar{n}^{T}e_{v}+\bar{d} \neq 0$，通过重新缩放，我们得到一个新的向量 $n$ 和标量 $d$，使得 $n^{T}x+d=0$ 定义了相同的超平面，且我们有 $n^{T}e_{v}+d=1$。
By construction, a point is contained in the convex set if and only if . Together with the construction above, this shows all statements of the lemma.根据构造，点 $x$ 包含在凸集 $S \setminus S_{vw}^{\mu}$ 中当且仅当 $n^{T}x+d < 0$。结合上述构造，这证明了引理的所有陈述。
∎
We need one more function with the properties我们需要另一个函数 $\bar{\ell}_{vw}$，具有以下属性
It can be easily constructed from the functions in this section by它可以很容易地通过本节中的函数构造出来，即
| (34) |
Since the corner is contained in the unsymmetric corner the function is linear on the corner , as well as all other corners , . In addition, all three functions , and are lines on the line segments from to the barycenter and from the barycenter to for all . On these three points one directly verifies that is zero and therefore, it is zero on the entire line segment from to , . For all remaining and , one can easily verify that their value is zero, as well. Finally, on the edge connecting to , the function is piecewise linear as shown in Figure 2.由于角 $S_{w}^{1/4}$ 包含在非对称角 $S_{wv}^{1/4}$ 中，函数 $\bar{\ell}_{vw}$ 在角 $S_{w}^{1/4}$ 以及所有其他角 $S_{u}^{1/4}$ ($u \in V$) 上是线性的。此外，所有三个函数 $\ell_{vw}$、$\ell_{v}^{1/2}$ 和 $\ell_{vw}^{1/4}$ 在从 $e_{v}$ 到重心 $\frac{1}{2}(e_{v}+e_{u})$ 以及从重心到 $e_{u}$ 的线段上都是线性的（对于所有 $u \neq v, w$）。在这三个点上，可以直接验证 $\bar{\ell}_{vw}$ 为零，因此它在从 $e_{v}$ 到 $e_{u}$ ($u \neq w$) 的整条线段上均为零。对于所有剩余的 $\bar{\ell}_{vw}(e_{tu}^{1/4})$ 和 $\bar{\ell}_{vw}(e_{tu}^{3/4})$，也可以很容易地验证它们的值也为零。最后，在连接 $e_{v}$ 和 $e_{w}$ 的边上，函数 $\bar{\ell}_{vw}$ 是分段线性的，如图 2 所示。
Appendix B Quantization附录 B 量化
In order to input data and labels into the Turing machine and later read the resulting weights from the output tape, we need to quantize and de-quantize floating point numbers to bit streams. From a practical perspective nothing needs to be done because on every computing device, data and weights are already represented by zeros and ones, which can be passed directly to and from the Turing machine.为了将数据和标签输入图灵机，并在稍后从输出带读取所得权重 $\theta$，我们需要将浮点数量化为位流，以及进行反量化。从实际角度来看，什么都不需要做，因为在任何计算设备上，数据和权重都已经由零和一表示，可以直接传递给图灵机或从图灵机传出。
Nonetheless, for the sake of completeness, we show by a rudimentary construction that this quantization/de-quantization can also be achieved purely by neural networks. To this end, given a number , we compute a floating point approximation尽管如此，为了完整起见，我们通过一个简单的构造证明这种量化/反量化也可以完全由神经网络实现。为此，给定一个数 $x \in \mathbb{R}$，我们计算一个浮点近似值
with fixed sizes , of the mantissa and exponent. Thus, we need two neural networks for mapping to the binary and its inversion. The latter can easily be implemented as a neural network with one exponential function as activation, or alternatively with a product of the terms .其中尾数和指数的大小 $m, n$ 是固定的。因此，我们需要两个神经网络来分别实现将 $x$ 映射到二进制 $\sigma \times (a_{0}, \dots, a_{m}) \times (b_{1}, \dots, b_{n})$ 及其逆映射。后者可以很容易地实现为一个以一个指数函数作为激活函数的神经网络，或者可选地，使用项 $b_{j}2^{j}$ 的乘积。
Since the operation is never differentiated for training the extended network in Figure 1, we can use any standard algorithm for that purpose, as e.g. the following:由于操作 $x \to \sigma, a, b$ 在训练图 1 中的扩展网络时从未进行过微分，我们可以为此使用任何标准算法，例如以下算法：
With precomputed weights with and , , we only need additions and if statements, which can be easily realized with Heaviside activation functions. The loops are finite and can be unrolled. If we want the network to be continuous, we can replace the Heaviside function with a piecewise linear approximation利用预先计算的权重 $2^{i}e$（其中 $i=0, \dots, m$ 且 $e=2^{\sum_{j=0}^{n}\hat{b}_{j}2^{j}}$，$\hat{b} \in \{0, 1\}^{n}$），我们只需要加法和 if 语句，这些可以很容易地通过 Heaviside 激活函数实现。循环是有限的，可以展开。如果我们希望网络是连续的，可以用分段线性近似来代替 Heaviside 函数
By choosing smaller than the machine accuracy, we can ensure that even with this approximation we obtain unchanged results for all floating point inputs .通过选择小于机器精度的 $\epsilon$，我们可以确保即使使用这种近似，对于所有浮点输入 $x$，我们也能获得不变的结果。
Appendix C Orthogonal Vector附录 C 正交向量
This appendix provides an algorithm for the function used in Section 5.4. This function returns a vector that has unit length and is orthogonal to the input . Of course it is easy to find an orthogonal vector, we just have to select one of them. To this end, we use two orthonormal vectors and . Our first choice is本附录提供了 5.4 节中使用的函数 $f_{\perp}(z)$ 的算法。该函数返回一个长度为单位且与输入 $z$ 正交的向量 $y$。当然，找到一个正交向量很容易，我们只需要选择其中一个即可。为此，我们使用两个正交向量 $v$ 和 $w$。我们的第一个选择是
given by and then upon normalization . This procedure produces a non-zero if and only if is not parallel to . In the latter case (or better with a small safety margin if and are almost parallel) we repeat the same calculation with , instead of .由 $\bar{y}=v-\frac{x^{T}v}{x^{T}x}x$ 给出，然后通过归一化得到 $y=\bar{y}/\|\bar{y}\|$。当且仅当 $v$ 不平行于 $x$ 时，此过程产生非零的 $\bar{y}$。在后一种情况下（或者更好的是，如果 $x$ 和 $v$ 几乎平行，则留出小的安全余量），我们用 $w$ 代替 $v$ 重复相同的计算。
This can be implemented with neural network layers: one switch between and , one for the squared norm , one for the division and likewise two more layers for the normalization of .这可以用 5 层神经网络实现：一层用于在 $v$ 和 $w$ 之间切换，一层用于平方范数 $x^{T}x$，一层用于除法 $x^{T}v/x^{T}x$，同样还有两层用于 $\bar{y}$ 的归一化。
References参考文献
- [1] Z. Allen-Zhu, Y. Li, and Z. Song. A convergence theory for deep learning via over-parameterization. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 242–252, Long Beach, California, USA, 09–15 Jun 2019. PMLR. Full version available at https://arxiv.org/abs/1811.03962. [1] Z. Allen-Zhu, Y. Li, and Z. Song. A convergence theory for deep learning via over-parameterization. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 242–252, Long Beach, California, USA, 09–15 Jun 2019. PMLR. Full version available at https://arxiv.org/abs/1811.03962.
- [2] S. Arora, N. Cohen, N. Golowich, and W. Hu. A convergence analysis of gradient descent for deep linear neural networks. In International Conference on Learning Representations, 2019. [2] S. Arora, N. Cohen, N. Golowich, and W. Hu. A convergence analysis of gradient descent for deep linear neural networks. In International Conference on Learning Representations, 2019.
- [3] D. Bahdanau, K. Cho, and Y. Bengio. Neural machine translation by jointly learning to align and translate. In Y. Bengio and Y. LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. [3] D. Bahdanau, K. Cho, and Y. Bengio. Neural machine translation by jointly learning to align and translate. In Y. Bengio and Y. LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
- [4] A. R. Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information Theory, 39(3):930–945, 1993. [4] A. R. Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information Theory, 39(3):930–945, 1993.
- [5] G. Bellec, F. Scherr, E. Hajek, D. Salaj, R. A. Legenstein, and W. Maass. Biologically inspired alternatives to backpropagation through time for learning in recurrent neural nets. 2019. [5] G. Bellec, F. Scherr, E. Hajek, D. Salaj, R. A. Legenstein, and W. Maass. Biologically inspired alternatives to backpropagation through time for learning in recurrent neural nets. 2019.
- [6] A. Blum and R. L. Rivest. Training a 3-node neural network is np-complete. In D. S. Touretzky, editor, Advances in Neural Information Processing Systems 1, pages 494–501. Morgan-Kaufmann, 1989. [6] A. Blum and R. L. Rivest. Training a 3-node neural network is np-complete. In D. S. Touretzky, editor, Advances in Neural Information Processing Systems 1, pages 494–501. Morgan-Kaufmann, 1989.
- [7] A. Choromanska, M. Henaff, M. Mathieu, G. B. Arous, and Y. LeCun. The loss surfaces of multilayer networks. In G. Lebanon and S. V. N. Vishwanathan, editors, Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, volume 38 of Proceedings of Machine Learning Research, pages 192–204, San Diego, California, USA, 09–12 May 2015. PMLR. [7] A. Choromanska, M. Henaff, M. Mathieu, G. B. Arous, and Y. LeCun. The loss surfaces of multilayer networks. In G. Lebanon and S. V. N. Vishwanathan, editors, Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, volume 38 of Proceedings of Machine Learning Research, pages 192–204, San Diego, California, USA, 09–12 May 2015. PMLR.
- [8] M. Collier and J. Beel. Implementing neural turing machines. In V. Kůrková, Y. Manolopoulos, B. Hammer, L. Iliadis, and I. Maglogiannis, editors, Artificial Neural Networks and Machine Learning – ICANN 2018, pages 94–104, Cham, 2018. Springer International Publishing. [8] M. Collier and J. Beel. Implementing neural turing machines. In V. Kůrková, Y. Manolopoulos, B. Hammer, L. Iliadis, and I. Maglogiannis, editors, Artificial Neural Networks and Machine Learning – ICANN 2018, pages 94–104, Cham, 2018. Springer International Publishing.
- [9] G. Cybenko. Approximation by superpositions of a sigmoidal function. Math. Control Signal Systems, 2:303–314, 1989. [9] G. Cybenko. Approximation by superpositions of a sigmoidal function. Math. Control Signal Systems, 2:303–314, 1989.
- [10] I. Daubechies, R. DeVore, S. Foucart, B. Hanin, and G. Petrova. Nonlinear approximation and (deep) relu networks. 2019. [10] I. Daubechies, R. DeVore, S. Foucart, B. Hanin, and G. Petrova. Nonlinear approximation and (deep) relu networks. 2019.
- [11] J. Donahue, Y. Jia, O. Vinyals, J. Hoffman, N. Zhang, E. Tzeng, and T. Darrell. Decaf: A deep convolutional activation feature for generic visual recognition. In E. P. Xing and T. Jebara, editors, Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 647–655, Bejing, China, 22–24 Jun 2014. PMLR. [11] J. Donahue, Y. Jia, O. Vinyals, J. Hoffman, N. Zhang, E. Tzeng, and T. Darrell. Decaf: A deep convolutional activation feature for generic visual recognition. In E. P. Xing and T. Jebara, editors, Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 647–655, Bejing, China, 22–24 Jun 2014. PMLR.
- [12] S. Du, J. Lee, H. Li, L. Wang, and X. Zhai. Gradient descent finds global minima of deep neural networks. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1675–1685, Long Beach, California, USA, 09–15 Jun 2019. PMLR. [12] S. Du, J. Lee, H. Li, L. Wang, and X. Zhai. Gradient descent finds global minima of deep neural networks. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1675–1685, Long Beach, California, USA, 09–15 Jun 2019. PMLR.
- [13] C. Finn, P. Abbeel, and S. Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In D. Precup and Y. W. Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1126–1135, International Convention Centre, Sydney, Australia, 06–11 Aug 2017. PMLR. [13] C. Finn, P. Abbeel, and S. Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In D. Precup and Y. W. Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1126–1135, International Convention Centre, Sydney, Australia, 06–11 Aug 2017. PMLR.
- [14] C. Finn and S. Levine. Meta-learning and universality: Deep representations and gradient descent can approximate any learning algorithm. 2017. [14] C. Finn and S. Levine. Meta-learning and universality: Deep representations and gradient descent can approximate any learning algorithm. 2017.
- [15] I. Goodfellow, Y. Bengio, and A. Courville. Deep Learning. MIT Press, 2016. http://www.deeplearningbook.org. [15] I. Goodfellow, Y. Bengio, and A. Courville. Deep Learning. MIT Press, 2016. http://www.deeplearningbook.org.
- [16] I. J. Goodfellow and O. Vinyals. Qualitatively characterizing neural network optimization problems. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. [16] I. J. Goodfellow and O. Vinyals. Qualitatively characterizing neural network optimization problems. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
- [17] A. Graves, G. Wayne, and I. Danihelka. Neural turing machines, 2014. [17] A. Graves, G. Wayne, and I. Danihelka. Neural turing machines, 2014.
- [18] B. Hanin and M. Sellke. Approximating continuous functions by relu nets of minimal width. 2017. [18] B. Hanin and M. Sellke. Approximating continuous functions by relu nets of minimal width. 2017.
- [19] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770–778, June 2016. [19] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770–778, June 2016.
- [20] K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):359 – 366, 1989. [20] K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):359 – 366, 1989.
- [21] T. Hospedales, A. Antoniou, P. Micaelli, and A. Storkey. Meta-learning in neural networks: A survey, 2020. [21] T. Hospedales, A. Antoniou, P. Micaelli, and A. Storkey. Meta-learning in neural networks: A survey, 2020.
- [22] M. Jaderberg, W. M. Czarnecki, S. Osindero, O. Vinyals, A. Graves, D. Silver, and K. Kavukcuoglu. Decoupled neural interfaces using synthetic gradients. In D. Precup and Y. W. Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1627–1635, International Convention Centre, Sydney, Australia, 06–11 Aug 2017. PMLR. [22] M. Jaderberg, W. M. Czarnecki, S. Osindero, O. Vinyals, A. Graves, D. Silver, and K. Kavukcuoglu. Decoupled neural interfaces using synthetic gradients. In D. Precup and Y. W. Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1627–1635, International Convention Centre, Sydney, Australia, 06–11 Aug 2017. PMLR.
- [23] A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 25, pages 1097–1105. Curran Associates, Inc., 2012. [23] A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 25, pages 1097–1105. Curran Associates, Inc., 2012.
- [24] T. Laurent and J. von Brecht. Deep linear networks with arbitrary loss: All local minima are global. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2902–2907, Stockholmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR. [24] T. Laurent and J. von Brecht. Deep linear networks with arbitrary loss: All local minima are global. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2902–2907, Stockholmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR.
- [25] D.-H. Lee, S. Zhang, A. Fischer, and Y. Bengio. Difference target propagation. In A. Appice, P. P. Rodrigues, V. Santos Costa, C. Soares, J. Gama, and A. Jorge, editors, Machine Learning and Knowledge Discovery in Databases, pages 498–515, Cham, 2015. Springer International Publishing. [25] D.-H. Lee, S. Zhang, A. Fischer, and Y. Bengio. Difference target propagation. In A. Appice, P. P. Rodrigues, V. Santos Costa, C. Soares, J. Gama, and A. Jorge, editors, Machine Learning and Knowledge Discovery in Databases, pages 498–515, Cham, 2015. Springer International Publishing.
- [26] Y. Li and Y. Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 8157–8166. Curran Associates, Inc., 2018. [26] Y. Li and Y. Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 8157–8166. Curran Associates, Inc., 2018.
- [27] T. P. Lillicrap, D. Cownden, and C. J. Tweed, Douglas B. Akerman. Random synaptic feedback weights support error backpropagation for deep learning. Nat Commun, 7(13276), 2016. [27] T. P. Lillicrap, D. Cownden, and C. J. Tweed, Douglas B. Akerman. Random synaptic feedback weights support error backpropagation for deep learning. Nat Commun, 7(13276), 2016.
- [28] Z. Lu, H. Pu, F. Wang, Z. Hu, and L. Wang. The expressive power of neural networks: A view from the width. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 6231–6239. Curran Associates, Inc., 2017. [28] Z. Lu, H. Pu, F. Wang, Z. Hu, and L. Wang. The expressive power of neural networks: A view from the width. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 6231–6239. Curran Associates, Inc., 2017.
- [29] E. Real, S. Moore, A. Selle, S. Saxena, Y. L. Suematsu, J. Tan, Q. V. Le, and A. Kurakin. Large-scale evolution of image classifiers. In D. Precup and Y. W. Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2902–2911, International Convention Centre, Sydney, Australia, 06–11 Aug 2017. PMLR. [29] E. Real, S. Moore, A. Selle, S. Saxena, Y. L. Suematsu, J. Tan, Q. V. Le, and A. Kurakin. Large-scale evolution of image classifiers. In D. Precup and Y. W. Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2902–2911, International Convention Centre, Sydney, Australia, 06–11 Aug 2017. PMLR.
- [30] I. Safran and O. Shamir. Spurious local minima are common in two-layer ReLU neural networks. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 4433–4441, Stockholmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR. [30] I. Safran and O. Shamir. Spurious local minima are common in two-layer ReLU neural networks. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 4433–4441, Stockholmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR.
- [31] H. Siegelmann and E. Sontag. On the computational power of neural nets. Journal of Computer and System Sciences, 50(1):132 – 150, 1995. [31] H. Siegelmann and E. Sontag. On the computational power of neural nets. Journal of Computer and System Sciences, 50(1):132 – 150, 1995.
- [32] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484–489, 2016. [32] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484–489, 2016.
- [33] D. Soudry and Y. Carmon. No bad local minima: Data independent training error guarantees for multilayer neural networks. 2016. [33] D. Soudry and Y. Carmon. No bad local minima: Data independent training error guarantees for multilayer neural networks. 2016.
- [34] I. Sutskever, O. Vinyals, and Q. V. Le. Sequence to sequence learning with neural networks. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 27, pages 3104–3112. Curran Associates, Inc., 2014. [34] I. Sutskever, O. Vinyals, and Q. V. Le. Sequence to sequence learning with neural networks. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 27, pages 3104–3112. Curran Associates, Inc., 2014.
- [35] B. Wu, X. Dai, P. Zhang, Y. Wang, F. Sun, Y. Wu, Y. Tian, P. Vajda, Y. Jia, and K. Keutzer. Fbnet: Hardware-aware efficient convnet design via differentiable neural architecture search. In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 10726–10734, 2019. [35] B. Wu, X. Dai, P. Zhang, Y. Wang, F. Sun, Y. Wu, Y. Tian, P. Vajda, Y. Jia, and K. Keutzer. Fbnet: Hardware-aware efficient convnet design via differentiable neural architecture search. In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 10726–10734, 2019.
- [36] W. Xiao, H. Chen, Q. Liao, and T. Poggio. Biologically-plausible learning algorithms can scale to large datasets. In International Conference on Learning Representations, 2019. [36] W. Xiao, H. Chen, Q. Liao, and T. Poggio. Biologically-plausible learning algorithms can scale to large datasets. In International Conference on Learning Representations, 2019.
- [37] J. Yosinski, J. Clune, Y. Bengio, and H. Lipson. How transferable are features in deep neural networks? In Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2, NIPS’14, page 3320–3328, Cambridge, MA, USA, 2014. MIT Press. [37] J. Yosinski, J. Clune, Y. Bengio, and H. Lipson. How transferable are features in deep neural networks? In Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2, NIPS’14, page 3320–3328, Cambridge, MA, USA, 2014. MIT Press.
- [38] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017. [38] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017.
- [39] D.-X. Zhou. Universality of deep convolutional neural networks. Applied and Computational Harmonic Analysis, 48(2):787 – 794, 2020. [39] D.-X. Zhou. Universality of deep convolutional neural networks. Applied and Computational Harmonic Analysis, 48(2):787 – 794, 2020.
- [40] B. Zoph and Q. V. Le. Neural architecture search with reinforcement learning. In ICLR (2017), 2017. [40] B. Zoph and Q. V. Le. Neural architecture search with reinforcement learning. In ICLR (2017), 2017.
- [41] B. Zoph, V. Vasudevan, J. Shlens, and Q. V. Le. Learning transferable architectures for scalable image recognition. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8697–8710, 2018. [41] B. Zoph, V. Vasudevan, J. Shlens, and Q. V. Le. Learning transferable architectures for scalable image recognition. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8697–8710, 2018.