第 4 章 参数化程序Chapter 4 Parameterized programs

首先，我们考虑这样一类简单程序：它对输入 ${\bm{s}}_{0}\in\mathcal{S}_{0}$ 依次施加一系列函数 $f_{1},\dots,f_{K}$。我们将这类程序称为计算链。例如，一张图像可以经历一系列变换，如裁剪、旋转、归一化等。在神经网络中，这些变换通常是参数化的，且参数是可学习的，由此得到 4.2 节介绍的前馈网络。函数序列的另一个例子是 for 循环，将在 5.8 节介绍。To begin with, we consider simple programs that apply a sequence of functions $f_{1},\dots,f_{K}$ to an input ${\bm{s}}_{0}\in\mathcal{S}_{0}$. We call such programs computation chains. For example, an image may go through a sequence of transformations such as cropping, rotation, normalization, and so on. In neural networks, the transformations are typically parameterized, and the parameters are learned, leading to feedforward networks, presented in Section 4.2. Another example of a sequence of functions is a for loop, presented in Section 5.8.

形式上，计算链可以写为Formally, a computation chain can be written as

这里，${\bm{s}}_{0}$ 是输入，${\bm{s}}_{k}\in\mathcal{S}_{k}$ 是程序的中间状态，${\bm{s}}_{K}\in\mathcal{S}_{K}$ 是最终输出。当然，$f_{k}$ 的定义域（输入空间）必须与 $f_{k-1}$ 的像（输出空间）相容。也就是说，应当有 $f_{k}\colon\mathcal{S}_{k-1}\to\mathcal{S}_{k}$。我们可以将计算链等价地写为Here, ${\bm{s}}_{0}$ is the input, ${\bm{s}}_{k}\in\mathcal{S}_{k}$ is an intermediate state of the program, and ${\bm{s}}_{K}\in\mathcal{S}_{K}$ is the final output. Of course, the domain (input space) of $f_{k}$ must be compatible with the image (output space) of $f_{k-1}$. That is, we should have $f_{k}\colon\mathcal{S}_{k-1}\to\mathcal{S}_{k}$. We can write a computation chain equivalently as

计算链可以用有向图表示，如图 4.1 所示。链中的边定义了一种全序。之所以是全序，是因为任意两个节点之间必然由一条路径相连。A computation chain can be represented by a directed graph, shown in Fig. 4.1. The edges in the chain define a total order. The order is total, since two nodes are necessarily linked to each other by a path.

在一般程序中，中间函数不仅可能依赖于前一个函数的输出，还可能依赖于若干不同函数的输出。这类依赖关系最好用图来表示。In generic programs, intermediate functions may depend, not only on the previous function output, but on the outputs of several different functions. Such dependencies are best expressed using graphs.

有向图 $\mathcal{G}=(\mathcal{V},\mathcal{E})$ 由一组顶点（或称节点）$\mathcal{V}$ 以及一组刻画顶点之间有向依赖关系的边 $\mathcal{E}$ 共同定义。一条边 $(i,j)\in\mathcal{E}$ 是一个有序的顶点对 $i\in\mathcal{V}$ 与 $j\in\mathcal{V}$。它也可记作 $i\rightarrow j$，表示 $j$ 依赖于 $i$。为便于表示输入与输出，使用入半边 $\rightarrow j$ 和出半边 $i\rightarrow$ 会更为方便。A directed graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ is defined by a set of vertices or nodes $\mathcal{V}$ and a set of edges $\mathcal{E}$ defining directed dependencies between vertices. An edge $(i,j)\in\mathcal{E}$ is an ordered pair of vertices $i\in\mathcal{V}$ and $j\in\mathcal{V}$. It is also denoted $i\rightarrow j$, to indicate that $j$ depends on $i$. For representing inputs and outputs, it will be convenient to use incoming half-edges $\rightarrow j$ and outgoing half-edges $i\rightarrow$.

在图 $\mathcal{G}=(\mathcal{V},\mathcal{E})$ 中，顶点 $j$ 的父节点是指向 $j$ 的那些节点所构成的集合，记作 ${\operatorname{pa}}(j)\coloneqq\{i:i\rightarrow j\}$。顶点 $i$ 的子节点则是 $i$ 所指向的那些节点所构成的集合，即 ${\operatorname{ch}}(i)\coloneqq\{j\colon i\rightarrow j\}$。没有父节点的顶点称为根，没有子节点的顶点称为叶。In a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, the parents of a vertex $j$ are the set of nodes pointing to $j$, denoted ${\operatorname{pa}}(j)\coloneqq\{i:i\rightarrow j\}$. The children of a vertex $i$ are the set of nodes $i$ is pointing to, that is, ${\operatorname{ch}}(i)\coloneqq\{j\colon i\rightarrow j\}$. Vertices without parents are called roots and vertices without children are called leaves.

从 $i$ 到 $j$ 的路径由一个顶点序列 $j_{1},\ldots,j_{m}$（可以为空）定义，且满足 $i\rightarrow j_{1}\rightarrow\ldots\rightarrow j_{m}\rightarrow j$。无环图是指这样的图：其中不存在顶点 $i$，使得存在从 $i$ 到 $i$ 的路径。有向无环图（DAG）则是指既是有向图、又是无环图的图。A path from $i$ to $j$ is defined by a sequence of vertices $j_{1},\ldots,j_{m}$, potentially empty, such that $i\rightarrow j_{1}\rightarrow\ldots\rightarrow j_{m}\rightarrow j$. An acyclic graph is a graph such that there exists no vertex $i$ with a path from $i$ to $i$. A directed acyclic graph (DAG) is a graph that is both directed and acyclic.

DAG 的边定义了顶点的一个偏序：若存在从 $i$ 到 $j$ 的路径，则记作 $i\preceq j$。该序是偏序，因为两个顶点不一定通过路径相互连接。尽管如此，我们可以定义一个称为拓扑序的全序：任意一种顺序，使得 $i\leq j$ 当且仅当不存在从 $j$ 到 $i$ 的路径。The edges of a DAG define a partial order of the vertices, denoted $i\preceq j$ if there exists a path from $i$ to $j$. The order is partial, since two vertices may not necessarily be linked to each other by a path. Nevertheless, we can define a total order called a topological order: any order such that $i\leq j$ if and only if there is no path from $j$ to $i$.

我们假定程序所定义的是一个数学上合法的函数（即纯函数）：对相同的参数，程序返回相同的值，且不产生任何副作用。我们还假定程序会停机，即在有限步内终止。这样的程序由有限个中间函数与中间变量构成，因此函数与变量之间的依赖关系可以用有向无环图（DAG）来表示。不失一般性，我们作出如下简化假设：We assume that a program defines a mathematically valid function (a.k.a. pure function): the program should return identical values for identical arguments and should not have any side effects. We also assume that the program halts, i.e., that it terminates in a finite number of steps. As such a program is made of a finite number of intermediate functions and intermediate variables, the dependencies between functions and variables can be expressed using a directed acyclic graph (DAG). Without loss of generality, we make the following simplifying assumptions:

1. 1.

   程序只有一个输入 ${\bm{s}}_{0}\in\mathcal{S}_{0}$。There is a single input ${\bm{s}}_{0}\in\mathcal{S}_{0}$.

2. 2.

   程序只有一个输出 ${\bm{s}}_{K}\in\mathcal{S}_{K}$。There is a single output ${\bm{s}}_{K}\in\mathcal{S}_{K}$.

3. 3.

   程序中的每个中间函数 $f_{k}$ 都只输出一个变量 ${\bm{s}}_{k}\in\mathcal{S}_{k}$。Each intermediate function $f_{k}$ in the program outputs a single variable ${\bm{s}}_{k}\in\mathcal{S}_{k}$.

我们将各节点依次编号为 $\mathcal{V}\coloneqq\{0,1,\dots,K\}$。其中，节点 $0$ 是根，对应输入 ${\bm{s}}_{0}\in\mathcal{S}_{0}$；节点 $K$ 是叶，对应最终的输出 ${\bm{s}}_{K}\in\mathcal{S}_{K}$。根据上述第三条假设，除 ${\bm{s}}_{0}$ 外，每个变量 ${\bm{s}}_{k}$ 都与一个函数 $f_{k}$ 一一对应。因此，节点 $0$ 表示输入 ${\bm{s}}_{0}$，而节点 $1,\dots,K$ 则既表示函数 $f_{k}$，又表示输出变量 ${\bm{s}}_{k}$。We number the nodes as $\mathcal{V}\coloneqq\{0,1,\dots,K\}$. Node $0$ is the root, corresponding to the input ${\bm{s}}_{0}\in\mathcal{S}_{0}$. Node $K$ is the leaf, corresponding to the final output ${\bm{s}}_{K}\in\mathcal{S}_{K}$. Because of the third assumption above, apart from ${\bm{s}}_{0}$, each variable ${\bm{s}}_{k}$ is in bijection with a function $f_{k}$. Therefore, node $0$ represents the input ${\bm{s}}_{0}$, and nodes $1,\dots,K$ represent both a function $f_{k}$ and an output variable ${\bm{s}}_{k}$.

DAG 中的边表示依赖关系。节点 $k$ 的父节点 $i_{1},\dots,i_{p_{k}}\coloneqq{\operatorname{pa}}(k)$（其中 $p_{k}\coloneqq|{\operatorname{pa}}(k)|$）所表示的，正是函数 $f_{k}$ 完成计算所需的变量 ${\bm{s}}_{{\operatorname{pa}}(k)}\coloneqq{\bm{s}}_{i_{1}},\dots,{\bm{s}}_{i_{p_{k}}}$。换言之，父节点 $i_{1},\dots,i_{p_{k}}$ 表示在求解 $f_{k}$ 之前必须先求值的函数 $f_{i_{1}},\ldots,f_{i_{p_{k}}}$。图 4.3 给出了这一形式体系下的一个计算图示例。Edges in the DAG represent dependencies. The parents $i_{1},\dots,i_{p_{k}}\coloneqq{\operatorname{pa}}(k)$ of node $k$, where $p_{k}\coloneqq|{\operatorname{pa}}(k)|$, indicate the variables ${\bm{s}}_{{\operatorname{pa}}(k)}\coloneqq{\bm{s}}_{i_{1}},\dots,{\bm{s}}_{i_{p_{k}}}$ that the function $f_{k}$ needs to perform its computation. Put differently, the parents $i_{1},\dots,i_{p_{k}}$ indicate the functions $f_{i_{1}},\ldots,f_{i_{p_{k}}}$ that need to be evaluated, prior to evaluating $f_{k}$. An example of a computation graph in our formalism is presented in Fig. 4.3.

算术电路是计算图最简单的例子之一，源出计算复杂性理论。形式上，域 $\mathbb{F}$（例如实数集 $\mathbb{R}$）上的算术电路是一个有向无环图（DAG），其根节点为 $\mathbb{F}$ 的元素，其函数 $f_{k}$ 或为 $+$，或为 $\times$。后者通常称为门。与一般计算图的情形不同，由于每个 $f_{k}$ 或为 $+$，或为 $\times$，因此必须允许图具有多个根节点。根节点既可以是变量，也可以是常数，且都应属于 $\mathbb{F}$。Arithmetic circuits are one of the simplest examples of computation graph, originating from computational complexity theory. Formally, an arithmetic circuit over a field $\mathbb{F}$, such as the reals $\mathbb{R}$, is a directed acyclic graph (DAG) whose root nodes are elements of $\mathbb{F}$ and whose functions $f_{k}$ are either $+$ or $\times$. The latter are often called gates. Contrary to the general computation graph case, because each $f_{k}$ is either $+$ or $\times$, it is important to allow the graph to have several root nodes. Root nodes can be either variables or constants, and should belong to $\mathbb{F}$.

算术电路可用于计算多项式。同一个多项式可能有多个算术电路来表示。于是便产生一个重要问题：如何为计算给定多项式找到最高效的算术电路。为比较表示同一多项式的不同算术电路，一个直观的复杂度概念是电路规模，其定义如下。Arithmetic circuits can be used to compute polynomials. There are potentially multiple arithmetic circuits for representing a given polynomial. One important question is then to find the most efficient arithmetic circuit for computing a given polynomial. To compare arithmetic circuits representing the same polynomial, an intuitive notion of complexity is the circuit size, as defined below.

关于算术电路的更多内容，读者可参阅 [44] 的专著。For more information on arithmetic circuits, we refer the reader to the monograph of [44].

上一节没有说明如何参数化前馈网络。一种典型的参数化方式称为多层感知机（MLP），它采用如下形式的全连接（又称稠密）层：In the previous section, we did not specify how to parametrize the feedforward network. A typical parametrization, called the multilayer perceptron (MLP), uses fully-connected (also called dense) layers of the form

其中我们定义了元组 ${\bm{w}}_{k}\coloneqq({\bm{W}}_{k},{\bm{b}}_{k})$，并假定 ${\bm{W}}_{k}$ 与 ${\bm{b}}_{k}$ 分别是尺寸适当的矩阵和向量。该层还可进一步分解为两个函数。函数 ${\bm{s}}\mapsto{\bm{W}}_{k}{\bm{s}}+{\bm{b}}_{k}$ 称为仿射层；函数 ${\bm{v}}\mapsto a_{k}({\bm{v}})$ 是一个无参数的非线性函数，通常称为激活函数（见 4.4 节）。值 ${\bm{\alpha}}_{k}\coloneqq{\bm{W}}_{k}{\bm{s}}_{k-1}+{\bm{b}}_{k}$ 通常称为预激活值，值 $a_{k}({\bm{\alpha}}_{k})$ 称为激活值。where we defined the tuple ${\bm{w}}_{k}\coloneqq({\bm{W}}_{k},{\bm{b}}_{k})$ and where we assumed that ${\bm{W}}_{k}$ and ${\bm{b}}_{k}$ are a matrix and a vector of appropriate size. We can further decompose the layer into two functions. The function ${\bm{s}}\mapsto{\bm{W}}_{k}{\bm{s}}+{\bm{b}}_{k}$ is called an affine layer. The function ${\bm{v}}\mapsto a_{k}({\bm{v}})$ is a parameter-free nonlinearity, often called an activation function (see Section 4.4). The value ${\bm{\alpha}}_{k}\coloneqq{\bm{W}}_{k}{\bm{s}}_{k-1}+{\bm{b}}_{k}$ is often called the pre-activation value and the value $a_{k}({\bm{\alpha}}_{k})$ is the activation value.

更一般地，我们可以用关于 ${\bm{s}}_{k-1}$ 的任意参数化线性函数替代矩阵—向量乘积 ${\bm{W}}_{k}{\bm{s}}_{k-1}$。例如，卷积层将输入 ${\bm{s}}_{k-1}$ 与若干滤波器 $W_{k}$ 的卷积视为一个线性映射。More generally, we may replace the matrix-vector product ${\bm{W}}_{k}{\bm{s}}_{k-1}$ by any parametrized linear function of ${\bm{s}}_{k-1}$. For example, convolutional layers use the convolution of an input ${\bm{s}}_{k-1}$ with some filters $W_{k}$, seen as a linear map.

当深度为 $K=1$（即只有一层）时，MLP 的输出为When the depth is $K=1$ (only one layer), the output of an MLP is

这称为广义线性模型（GLM），见 3.4 节。因此，MLP 将 GLM 作为特例包含在内。特别地，当 $a_{1}$ 取 softargmax（见 4.4 节）时，我们便得到（多分类）logistic 回归。对于一般的深度 $K$，MLP 的输出为This is called a generalized linear model (GLM); see Section 3.4. Therefore, MLPs include GLMs as a special case. In particular, when $a_{1}$ is the softargmax (see Section 4.4), we obtain (multiclass) logistic regression. For general depth $K$, the output of an MLP is

这可以看作是在输入 ${\bm{x}}$ 的学习表示 ${\bm{s}}_{K-1}$ 之上应用一个 GLM。这正是 MLP 的主要吸引力所在：它同时学习特征表示与输出模型！后文将会看到，MLP 也可以作为子组件用于其他架构。This can be seen as a GLM on top of learned representation ${\bm{s}}_{K-1}$ of the input ${\bm{x}}$. This is the main appeal of MLPs: they learn the feature representation and the output model at the same time! We will see that MLPs can also be used as subcomponents in other architectures.

许多激活函数是标量到标量的函数，但也可以按逐元素方式应用于向量。ReLU（修正线性单元）是一种常用的非线性函数，定义为输入的非负部分Many activations are scalar-to-scalar functions, but they can also be applied to vectors in an element-wise fashion. The ReLU (rectified linear unit) is a popular nonlinearity defined as the non-negative part of its input

它是分段线性函数，在 $u=0$ 处有一个折角。采用 ReLU 激活函数的多层感知机称为整流神经网络，其各层具有如下形式：It is a piecewise linear function and includes a kink at $u=0$. A multilayer perceptron with ReLU activations is called a rectifier neural network. The layers take the form

其中 ReLU 按逐元素方式应用。ReLU 可替换为一种光滑近似（即不含折角），称为 softpluswhere the ReLU is applied element-wise. The ReLU can be replaced with a smooth approximation (i.e., without kinks), called the softplus

与 ReLU 不同，它始终严格为正。ReLU 还可有其他平滑变体，见 13.4 节。Unlike the ReLU, it is always strictly positive. Other smoothed variants of the ReLU are possible, see Section 13.4.

许多激活函数是向量到标量的函数：它们把向量归约为一个标量值。该标量值可视为一种统计量，用以“概括”该向量。Many activations are vector-to-scalar functions: they reduce vectors to a scalar value. This scalar value can be seen as a statistic, “summarizing” the vector.

我们常常希望把实数值映射到 $[0,1]$ 中的某个数，用以表示某一事件的概率。为此，通常使用 S 形函数。S 形函数是曲线呈特征性“S”形的函数。这类函数是标量到标量的概率映射：用于把实数值压缩到 $[0,1]$。Oftentimes, we want to map a real value to a number in $[0,1]$, that can represent the probability of an event. For that purpose, we generally use sigmoids. A sigmoid is a function with a characteristic “S”-shaped curve. These functions are scalar-to-scalar probability mappings: they are used to squash real values to $[0,1]$.

将实向量变换为概率向量往往很有用。这是一个从 $\mathbb{R}^{M}$ 到概率单纯形的映射，定义为It is often useful to transform a real vector into a vector of probabilities. This is a mapping from $\mathbb{R}^{M}$ to the probability simplex, defined by

这类向量到向量的概率映射有两个例子：argmax 与 softargmax。Two examples of such vector-to-vector probability mappings are the argmax and the softargmax.

假设给定一批中间变量（如激活值或状态）${\bm{s}}_{1},\dots,{\bm{s}}_{B}\in\mathbb{R}^{D}$，其中 ${\bm{s}}_{i}\coloneqq(s_{i,1},\dots,s_{i,D})$，这些变量由某个函数作用于从训练集中抽取的 $B$ 个样本得到（为清晰起见，省略对层索引 $k$ 的依赖）。在批归一化 [99] 中，我们计算批内样本上的标准分数（又称 z 分数）来归一化这些值，Suppose we are given a batch of intermediate variables (such as activations or states) ${\bm{s}}_{1},\dots,{\bm{s}}_{B}\in\mathbb{R}^{D}$, where ${\bm{s}}_{i}\coloneqq(s_{i,1},\dots,s_{i,D})$, obtained by applying some function to $B$ samples drawn from the training set (we omit the dependency on the layer index $k$ for clarity). In batch normalization [99], we normalize the values by calculating the standard score (a.k.a. z-score) across batch samples,