Neural Networks

A network in which computation proceeds from one layer of units to the next, with no cycles. “Deep” because modern networks often have many layers.

They are more powerful: even a network with a single hidden layer can in principle learn any function.

Logistic regression relies on rich hand-designed feature templates. Neural networks usually take raw tokens as input and learn to induce features themselves (representation learning), so they suit tasks with enough data to learn features automatically.

A weighted sum of its inputs plus a bias, \(z = w \cdot x + b\), then a non-linear activation function: \(a = f(z)\).

The output \(a = f(z)\) of its non-linear function. For a single-unit network it is also the network output \(y\).

\(z = 0.1 + 0.18 + 0.09 + 0.5 = 0.87\), so \(y = \sigma(0.87) = \frac{1}{1 + e^{-0.87}} \approx 0.70\).

\(\tanh(z) = \frac{e^z - e^{-z}}{e^z + e^{-z}}\), a variant of the sigmoid ranging from −1 to +1. It is almost always better than the sigmoid; it is smoothly differentiable and maps outliers toward the mean.

The rectified linear unit, \(\text{ReLU}(z) = \max(z, 0)\): equal to \(z\) when positive, 0 otherwise. The simplest and perhaps most commonly used activation.

For large |z| its output is extremely close to its limit and its derivative is close to 0. Since training multiplies gradients across layers, near-zero gradients shrink the error signal until it is too small to learn from: the vanishing gradient problem.

They are close to linear: for positive \(z\) the derivative is 1, not close to 0.

That a single unit (perceptron) cannot compute some very simple functions of its input, notably XOR.

A simple neural unit with a binary output and a step-function activation: \(y = 1\) if \(w \cdot x + b > 0\), else 0.

AND: \(w_1 = w_2 = 1\), \(b = -1\). OR: \(w_1 = w_2 = 1\), \(b = 0\). (Many other settings work.)

A perceptron is a linear classifier: its decision boundary \(w_1x_1 + w_2x_2 + b = 0\) is a line. No line separates XOR’s positive cases (01, 10) from its negative cases (00, 11); XOR is not linearly separable.

A hyperplane separating the input space into the two output classes.

With a layered network: e.g. two hidden ReLU units and one output unit (Goodfellow et al., 2016). The hidden layer maps inputs [0, 1] and [1, 0] to the same point, after which positive and negative cases are linearly separable.

The hidden layer forms a new representation of the input in which the problem becomes easy. With backpropagation, networks learn such useful representations automatically.

Modern multilayer networks don’t use perceptrons (step functions) but units with non-linearities like ReLU or sigmoid; the name just stuck.

Input units, hidden units, and output units.

Each unit takes input from all units of the previous layer: there is a link between every pair of units in adjacent layers.

The weight of the connection from input unit \(x_i\) to hidden unit \(h_j\).

\(h = \sigma(Wx + b)\), with the activation applied element-wise. For input \(x \in \mathbb{R}^{n_0}\) and \(n_1\) hidden units: \(W\) is \([n_1 \times n_0]\), \(b, h \in \mathbb{R}^{n_1}\).

It multiplies the hidden representation by a weight matrix, \(z = Uh\) (\(U\) of shape \([n_2 \times n_1]\)), then normalizes with softmax: \(y = \text{softmax}(z)\).

It builds a hidden representation \(h\) of the input and runs multinomial logistic regression on it. But the features in \(h\) are induced by the network rather than designed by hand, layers can be stacked, and various activations are used.

\(h = \sigma(Wx + b)\), \(z = Uh\), \(y = \text{softmax}(z)\).

The input layer is not counted, the output layer is. So a network with one hidden layer is a 2-layer network, and logistic regression is a 1-layer network.

With \(a^{[0]} = x\): for \(i = 1 \ldots n\), \(z^{[i]} = W^{[i]}a^{[i-1]} + b^{[i]}\) and \(a^{[i]} = g^{[i]}(z^{[i]})\); output \(\hat{y} = a^{[n]}\). Intermediate \(g\) is usually ReLU or tanh, the last is softmax.

The unnormalized scores \(z^{[n]}\) in the final layer, right before the softmax.

Without them, stacked layers collapse into one: \(W^{[2]}(W^{[1]}x + b^{[1]}) + b^{[2]} = W'x + b'\). A multilayer linear network is just a single-layer network with different weights.

Add a dummy input \(x_0 = 1\) to each layer; its weight \(W_{j0}\) plays the role of the bias \(b_j\): \(h = \sigma(Wx)\).

Add a hidden layer between the features and the softmax output: \(h = \sigma(Wx + b)\), \(z = Uh\), \(\hat{y} = \text{softmax}(z)\). The hidden layer can represent non-linear interactions between features.

Vectorize: stack inputs as rows of \(X\) \([m \times d]\), then \(H = \sigma(XW^\top + b)\), \(Z = HU^\top\), \(\hat{Y} = \text{softmax}(Z)\), with output \([m \times d_o]\). Always keep track of matrix shapes, since orderings like \(WX\) vs \(XW\) vary.

A static embedding is a fixed vector per token, trained once and looked up in a dictionary. A contextual embedding differs for each occurrence and is learned by the network as part of the task (e.g. language modeling).

The dictionary of embeddings: one row per vocabulary token, shape \([|V| \times d]\). Inputs are converted to token indices, and the corresponding rows are selected.

Represent the token as a one-hot vector of shape \([1 \times |V|]\); multiplying it by \(E\) selects that token’s row. A whole sequence is an \([N \times |V|]\) one-hot matrix times \(E\), giving \([N \times d]\).

Concatenation into one long \([1 \times Nd]\) vector (keeps order and all information, but needs a big network), or pooling into a single \(d\)-dimensional vector (smaller and efficient, loses order).

For sentiment, the identity of words (e.g. great) matters more than their exact position.

Mean-pooling averages the embeddings: \(x_{mean} = \frac{1}{N}\sum_i e(w_i)\). Max-pooling takes, for each dimension, the element-wise maximum over all the inputs.

Advantages: much longer histories, better generalization over contexts of similar words, far more accurate prediction. Disadvantages: slower, more complex, vast energy to train, less interpretable; n-grams may still suit small tasks.

Like an n-gram model, \(P(w_t \mid w_{1:t-1}) \approx P(w_t \mid w_{t-N+1:t-1})\), but representing the previous words by embeddings rather than by their identities.

Cat and dog have similar embeddings, so the network generalizes from the cat context. An n-gram model, which only knows word identities, cannot.

To predict the next token it helps to know each previous token and their order, which pooling would lose.

\(e = [Ex_{t-3}; Ex_{t-2}; Ex_{t-1}]\) (concatenation), \(h = \sigma(We + b)\), \(z = Uh\), \(\hat{y} = \text{softmax}(z)\): a distribution over all \(|V|\) possible next tokens.

A loss function (cross-entropy), an optimization algorithm (gradient descent), and a way to compute the gradient of the loss with respect to every parameter (error backpropagation).

Cross-entropy: binary \(-[y\log\hat{y} + (1-y)\log(1-\hat{y})]\) with a sigmoid output; for \(K\) classes, \(-\log\hat{y}_c\) for the correct class \(c\), i.e. the negative log likelihood.

It only gives correct updates for the last weight layer; the loss is computed at the end, but we need derivatives with respect to weights deep in early layers.

The algorithm (Rumelhart et al., 1986) for computing gradients in deep networks; it is an instance of backward differentiation on computation graphs.

A representation of a mathematical computation broken down into separate operations, each a node, with edges carrying outputs to the next operations.

\(d = 2b = 2\), \(e = a + d = 5\), \(L = c \cdot e = -10\).

Pass gradients back from the final node: each node multiplies the upstream gradient it receives by its local gradient (of its output with respect to each input) to get the downstream gradient for earlier nodes (chain rule).

\(\partial L/\partial c = e = 5\). \(\partial L/\partial e = c = -2\), so \(\partial L/\partial a = \frac{\partial L}{\partial e}\frac{\partial e}{\partial a} = -2 \cdot 1 = -2\) and \(\partial L/\partial b = \frac{\partial L}{\partial e}\frac{\partial e}{\partial d}\frac{\partial d}{\partial b} = -2 \cdot 1 \cdot 2 = -4\).

It computes the intermediate values (like \(d\) and \(e\)) that the local derivatives depend on.

\(\sigma'(z) = \sigma(z)(1 - \sigma(z))\); \(\tanh'(z) = 1 - \tanh^2(z)\); ReLU’(z) = 0 for \(z < 0\), 1 for \(z \ge 0\) (undefined at 0, by convention 1).

\(a^{[2]} - y\): \(\frac{\partial L}{\partial a}\frac{\partial a}{\partial z} = \big(-\frac{y}{a} + \frac{1-y}{1-a}\big)a(1-a) = a - y\).

Network training is non-convex. Weights must be initialized with small random numbers (not 0, as in logistic regression), and inputs are normalized to zero mean and unit variance.

A regularization method: during training, at each update, each unit’s output is set to zero with probability \(p\) (and the rest renormalized), randomly dropping units and their connections.

Learning rate, mini-batch size, architecture (number of layers, hidden units per layer, activation functions), regularization (e.g. dropout rate), optimizer variant (e.g. Adam). They are tuned on a devset, not learned by gradient descent.

They build networks as computation graphs, making gradient computation and parallelization on GPUs easy.

McCulloch–Pitts neuron (1943); perceptron research in the late 1950s–60s (Rosenblatt at Cornell, Widrow at Stanford, who turned the threshold into a bias); then decline after Minsky & Papert (1969) showed a perceptron can’t model XOR.

Practical tools for deeper networks, especially backpropagation (Rumelhart et al., 1986). The connectionist / parallel distributed processing movement contributed distributed representations, recurrent networks and tensors for compositionality.

In the early 2000s, when better hardware and optimization techniques made it possible to train much larger and deeper networks (Hinton et al., 2006; Bengio et al., 2007).