Handout #3 — From Counting to Learning

How can a collection of weighted sums represent useful patterns? Today we connect count-based language models to parameterized functions, build feedforward networks, and explore why nonlinear hidden layers matter. We finish with the history of neural networks and perceptron learning.

1Language modeling as a learning problem

Slides 1–2 · Connection to Handout #2

A count-based language model stores statistics for discrete contexts. A neural language model instead computes a distribution with a parameterized function $p_\theta(w\mid c)$. The corpus still supplies the examples: a context $c$ is the input and its next word is the target. Self-supervision provides the labels; supervised learning machinery fits the resulting input–target pairs.

1.1  A fixed-window example

Keep the previous four words, look up a learned vector for each word, concatenate the vectors, and feed them to a network. The network produces one logit (an unrestricted score) per vocabulary item. Softmax turns the logits into a probability distribution.

The embeddings and the network weights are shared across contexts. Training on one context can therefore change predictions for another. We still have a finite context window; we have changed how the conditional distribution is estimated, not removed the Markov assumption.

1.2  Parameter sharing and generalization

If “dog” and “cat” acquire similar embeddings, the network can make similar predictions after “the dog slept” and “the cat slept.” This gives a way to transfer evidence to unseen contexts. Useful similarity has to be learned: a neural network is not guaranteed to generalize well merely because it outputs a distribution.

For vocabulary size $V$, embedding size $d$, window size $k$, and one hidden layer of width $h$, a simple untied model has $Vd+(kd)h+h+hV+V$ parameters. This grows linearly in $V$ and $k$ when $d,h$ are fixed, unlike the $V^{k+1}$ possible entries in a dense count table. Sparse tables store only observed entries, but still face the problem of estimating unseen combinations.

2What a feedforward neural network is

Slides 3–31

A feedforward network is a parameterized computation with no directed cycles: information flows from inputs through intermediate values to outputs. Here we study an MLP, built from fully connected affine layers and nonlinear activations. MLPs are one kind of feedforward network. Hidden values are learned features; they need not be probabilities or class predictions.

2.1  One unit: score, shift, activate

The weights select and combine input features. The bias shifts the threshold independently of the input. The activation changes how the score is passed onward. The map $w^\top x+b$ is affine; it is linear in $x$ only when $b=0$. We often call the module a “linear layer” even when it includes a bias.

2.2  From units to layers, from layers to an architecture

Stack $h$ weight vectors as rows of $W_1$. For a two-layer MLP with input dimension $d$ and output dimension $m$:

We count layers with trainable weights, excluding the input: this is two layers, one of them hidden. Architecture specifies the connectivity, dimensions, and activations; parameters specify the numerical weights and biases. Both are needed to determine a particular function. Width is the size of a hidden layer; depth is the number of successive layers.

2.3  Nonlinearity is essential

Sigmoid, tanh, and ReLU act elementwise in a layer. Softmax couples the coordinates. Several sigmoids need not sum to one; use softmax for a choice among mutually exclusive classes. ReLU avoids saturation on its positive side, but inactive units have zero derivative and networks using ReLU can still have vanishing or exploding gradients.

2.4  Expressivity: XOR, width, and depth

XOR labels $(0,0)$ and $(1,1)$ as 0, and $(0,1)$ and $(1,0)$ as 1. A single affine threshold cannot separate the two diagonals. Nonlinear hidden features can: for binary inputs, take $h_1=\operatorname{ReLU}(x_1-x_2)$, $h_2=\operatorname{ReLU}(x_2-x_1)$, and output $h_1+h_2$.

import torch

x = torch.tensor([[0., 0.], [0., 1.], [1., 0.], [1., 1.]])
W = torch.tensor([[1., -1.], [-1., 1.]])
h = torch.relu(x @ W.T)
y = h.sum(dim=1)
assert y.tolist() == [0., 1., 1., 0.]
print(h, y)
# Experiment: remove torch.relu. Predict the outputs before running.

The universal approximation idea in slides 24–31 is an expressivity statement: with a suitable activation and enough hidden units, a one-hidden-layer MLP can approximate any continuous function on a compact domain to arbitrary accuracy. It does not say a fixed small network represents every function, that gradient descent will find the needed weights, or that the result generalizes from finite data. Some function families admit much more compact deep representations than shallow ones; this does not mean deeper is always better.

3History: from fixed features to learned hidden layers

Slides 32–54

The biological analogy motivated simple computational units, but an MLP is not a detailed model of a biological brain. The historical thread to follow is the separation between representing a function and finding its parameters.

3.1  An update before gradients

A threshold perceptron predicts $o=\mathbf{1}[w^\top x+b>0]$. For binary target $t$, the error-driven rule in the slides is

A correct prediction causes no update. A missed positive increases the score on that example; a false positive decreases it. The classic perceptron convergence guarantee assumes linearly separable training data. This rule does not differentiate the discontinuous threshold function.

A single affine threshold cannot express XOR, whereas the hidden-layer construction in §2.4 can. Be careful with historical layer counts: the impossibility is about a linear separator, not an MLP with a nonlinear hidden layer. The next challenge is to learn those hidden features rather than supply their weights by hand.