13.2. DENSE FEEDFORWARD NETWORKS
515
! Exercise 13.1.2: Consider the general problem of identifying bit-vectors of
length n having two consecutive 1’s. Assume a single hidden layer with some
number of gates. What is the smallest number of gates you can have in the
hidden layer if (a) n = 5 (b) n = 6?
! Exercise 13.1.3: Design a neural net that functions as an exclusive-or gate,
that is, it takes two inputs and gives output 1 if exactly one of the inputs is
1 gives output 0 otherwise. Hint: remember that both weights and thresholds
can be negative.
! Exercise 13.1.4: Prove that there is no single preceptron that behaves like
an exclusive-or gate.
! Exercise 13.1.5: Design a neural net to compute the exclusive-or of three
inputs; that is, output 1 if an odd number of the three inputs is 1 and output
0 if an even number of the inputs are 1.
13.2
Dense Feedforward Networks
In the previous section, we simply exhibited a neural net that worked for the
“consecutive 1’s” problem. However, the true value of neural nets comes from
our ability to design them given training data. To design a net, there are many
choices that must be made, such as the number of layers and the number of
nodes for each layer, as was discussed in Section 13.1.4.
These choices can
be more art than science. The computational part of training, which is more
science than art, is primarily the choice of weights for the inputs to each node.
The techniques for selecting weights usually involve convergence using gra-
dient descent. But gradient descent requires a cost function, which must be a
continuous function of the weights. The nets discussed in Section 13.1.4, on the
other hand, use perceptrons whose output is either 0 or 1, so the outputs are
not normally continuous functions of the inputs. In this section, we shall dis-
cuss the various ways one can modify the behavior of the nodes in a net so the
outputs become continuous functions of the inputs, and therefore a reasonable
cost function applied to the outputs will also be continuous.
13.2.1
Linear Algebra Notation
We can succinctly describe the neural network we used for the consecutive
1’s problem using linear algebra notation.
The input nodes form a vector2
x = [x1, x2, x3, x4], while the hidden nodes form a vector h = [h1, h2]. The
4 edges connecting the input to hidden node 1 form a weight vector w1 =
[w11, w12, w13, w14], and similarly we have weight vector w2 for hidden node 2.
2We assume all vectors are column vectors by default. However, it is often more convenient
to write row vectors, and we shall do so in the text. But in formulas, we shall use the transpose
operator when we actually want to use the vector as a row rather than a column.
