![](https://csdnimg.cn/release/download_crawler_static/10027543/bg10.jpg)
CHAPTER 2. BACKGROUND 8
1: distribute the input v across the input nodes Rz
i
for i ∈ I
2: for i from 1 to N if i 6∈ I do
3: Rx
i
← concat
j∈A
i
Rz
j
4: Rz
i
← f
0
i
(x
i
) · Rx
i
5: end for
6: output Rz
N
, which is equal to F
0
(θ) · v
The correctness of this algorithm can likewise be proven by structural induction over the graph, proving
that Rz
i
= ∂z
i
/∂θ · v for each i, starting from i ∈ I and reaching node z
N
. Unlike backward differen-
tiation, forward differentiation does not need to store the state variables z
i
, since they can be computed
together with Rz
i
and be discarded once used.
Thus automatic differentiation can compute the Jacobian-vector products of any function expressible
as a computational graph at the cost of roughly two function evaluations. The Theano compiler (Bergstra
et al., 2010) computes derivatives in precisely this manner automatically and efficiently.
2.4 Feedforward Neural Networks
The Feedforward Neural Network (FNN) is the most basic and widely used artificial neural network. It
consists of a number of layers of artificial neurons (termed units) that are arranged into a layered con-
figuration (fig. 2.2). Of particular interest are deep neural networks, which are believed to be capable of
representing the highly complex functions that achieve high performance on difficult perceptual prob-
lems such as vision and speech (Bengio, 2009). FNNs have achieved success in a number of domains
(e.g., Salakhutdinov and Hinton, 2009; Glorot et al., 2011; Krizhevsky and Hinton, 2011; Krizhevsky,
2010), most notably in large vocabulary continuous speech recognition (Mohamed et al., 2012), where
they were directly responsible for considerable improvements over previous highly-tuned, state-of-the-
art systems.
Formally, a feedforward neural network with ` hidden layers is parameterized by ` + 1 weight
matrices (W
0
, . . . , W
`
) and ` + 1 vectors of biases (b
1
, . . . , b
`+1
). The concatenation of the weight
matrices and the biases forms the parameter vector θ that fully specifies the function computed by
the network. Given an input x, the feedforward neural network computes an output z as follows:
1: set z
0
← x
2: for i from 1 to ` + 1 do
3: x
i
← W
i−1
z
i−1
+ b
i
4: z
i
← e(x
i
)
5: end for
6: Output z ← z
`
Here e(·) is some nonlinear function such as the element-wise sigmoid sigmoid(x
j
) = 1/(1+exp(−x
j
)).
When e(·) is a sigmoid function, it can be used to implement Boolean logic, which allows deep and
wide feedforward neural networks to implement arbitrary Boolean circuits and hence arbitrary compu-
tation subject to some time and space constraints. But while we cannot hope to always train feedforward
neural networks so deep from labelled cases alone (provably so, under certain cryptographic assump-
tions (Kearns and Vazirani, 1994)
5
), wide and slightly deep networks (3-5 layers) are often easy to train
in practice with SGD while being moderately expressive.
5
Intuitively, given a public key, it is easy to generate a large number of (encryption, message) pairs. If circuits were
learnable, we could learn a circuit that could map an encryption to its secret message with high accuracy (since such a circuit
exists).