Distributed Representation · Exponential Gains from Depth

§15.4 Distributed representation

A distributed representation — composed of many elements that can be set separately from each other — is representation learning’s most important tool: $n$ features with $k$ values describe $k^n$ concepts. Networks with many hidden units and probabilistic models with many latent variables both use this strategy, and it is the natural match for §15.3’s program: each direction in representation space can correspond to a different underlying configuration variable.

Contrast the symbolic case: one symbol per input, expressible as a one-hot vector — $n$ mutually exclusive bits. That is the simplest non-distributed representation , and it has plenty of company:

The non-distributed family — one parameter set per region. Click a row for the fine print.
	How it partitions input space	Why not distributed
Clustering / k-means	each input belongs to exactly one cluster	one active symbol; no separately-controllable attributes
k-nearest neighbors	one (or a few) templates answer for each input	with k > 1 there are multiple values, but they cannot be controlled separately
Decision trees	one root-to-leaf path activates per input	one region per leaf
Gaussian mixtures / mixtures of experts	templates with degrees of activation	activations exist but are not separately controllable
Kernel machine (Gaussian kernel)	continuous activation per support vector	same issue — local templates, not composable attributes
n-gram language models	a suffix-tree partition of contexts	separate parameters per leaf

Dotted-underlined cells have explanations — click one.

The geometric argument. Take the simplest distributed learner: $n$ binary features, each thresholding a linear function of the input. Each feature splits $\mathbb{R}^d$ into two half-spaces, and their intersections carve the space into regions — each with its own unique code $\boldsymbol{h}$ . Carve for yourself, then spend the same budget on prototypes:

Figs 15.7–15.8 (interactive) — the same parameter budget, two philosophies. Distributed: n linear-threshold features carve the plane into up to 1 + n + C(n,2) uniquely-coded regions (arrows point to each feature's positive side). Non-distributed: n prototypes carve exactly n nearest-neighbor cells. Slide n and watch the gap grow quadratically — O(n^d) in d dimensions.

n = 4

regions distinguished (counted)

eq 15.4 bound: 1 + n + C(n,2)

Each of the n linear-threshold features answers one question ("which side of my line?"), and every REGION gets a unique binary code h — the intersections multiply, giving O(n²) regions in 2-D and O(n^d) in d dimensions from only O(n·d) parameters. (The counted number can fall below the bound when an intersection lands outside the visible box.) Note also: not every code is feasible — with parallel-ish lines some sign patterns never occur.

How many regions can n hyperplanes make? (eq 15.4)

\sum_{j=0}^{d} \binom{n}{j} = O(n^d)

$n$	the number of hyperplanes — one per binary feature; a general result on hyperplane arrangements (Zaslavsky 1975; applied by Pascanu et al. 2014)	features
$d$	the input dimension: growth is EXPONENTIAL in d and polynomial in n	dimension
$O(n^d)\ \text{regions}$	with only O(n·d) parameters — versus a non-distributed learner needing O(n^d) EXAMPLES to carve (and label) as many regions, since each region demands its own parameters	the punchline
$k \ll r$	the general form: if a k-parameter transformation captures r regions with k ≪ r (and those features suit the task), generalization beats the O(r)-examples non-distributed route	beyond linear

Worked example — six features vs six templates

In $d = 2$ with $n = 6$ : the distributed learner distinguishes up to $\binom{6}{0} + \binom{6}{1} + \binom{6}{2} = 1 + 6 + 15 = 22$ regions; six prototypes distinguish exactly $6$ . At $n = 100$ in $d = 10$ , the bound is astronomically larger than $100$ — while the smoothness-only learner needs roughly one example per region it must distinguish (§5.11.2’s curse, revisited).

Generalization = shared attributes

As pure symbols, “cat” and “dog” are as distant as any two symbols. As distributed codes sharing entries like has_fur and number_of_legs, much of what is learned about cats transfers to dogs. Distributed representations induce a similarity space — semantically close concepts are close in distance — a property purely symbolic representations simply lack. (Non-distributed learners generalize only via the smoothness prior : enough for nearby points, hopeless for a target function with more ups and downs than you have examples.)

Why capacity stays sane. Distinguishing $O(n^d)$ regions sounds like an overfitting machine — but the VC dimension of a linear-threshold network is only $O(w \log w)$ in the number of weights (Sontag 1998). We can code exponentially many regions, yet cannot learn arbitrary functions from code space to labels with a linear classifier. That combination — powerful representation, weak classifier — expresses a prior: the classes are linearly separable as functions of the underlying factors $\boldsymbol{h}$ . “All images of green objects” qualifies; XOR-style classes (“red cars and green trucks” vs “green cars and red trucks”) deliberately do not. A classifier learning person need not treat “woman with glasses” differently from “man without glasses” — which pushes $\boldsymbol{h}$ to represent classes linearly-separably in the first place.

And it shows up in practice. Hidden units of deep vision networks are often interpretable, matching labels humans would assign (Zhou et al. 2015) — and a generative model of faces learns separate directions for separate factors, discovered with no attribute labels at all (Radford et al. 2015):

Fig 15.9 (schematic) — vector arithmetic in a learned face-representation space. The “wearing glasses” offset (amber) and the “gender” offset (purple) are separate, roughly parallel directions wherever they apply: start from man-with-glasses, subtract man, add woman — the result decodes to woman-with-glasses, a configuration never needed during training. Disentangled directions are what make the arithmetic land.

§15.5 Exponential gains from depth

§6.4.1 showed that some functions need exponentially smaller deep networks than shallow ones. The same style of result extends beyond deterministic functions. One-hidden-layer models — RBMs, deep belief networks — are universal approximators of probability distributions (Le Roux & Bengio 2008, 2010; Montúfar 2014)… but universality is silent about size. The sum-product network supplies the probabilistic depth theorem: SPNs compute distributions with polynomial circuits, and there exist distributions requiring a minimum SPN depth — insufficient depth (2, or even $k-1$ instead of $k$ ) forces exponentially large models (Delalleau & Bengio 2011), with significant differences between every two finite depths and tractability constraints that themselves limit representational power (Martens & Medabalimi 2014). For convolution-related deep circuits, the exponential advantage holds even when the shallow circuit only needs to approximate the deep one’s function (Cohen et al. 2015) — earlier results required exact replication.

The face-arithmetic example closes the loop: it took a deep generative model to relate abstract factors (gender, glasses) to pixels — factors that can be chosen nearly independently of one another yet remain meaningful are typically high-level and highly nonlinear functions of the input. That demands deep distributed representations: higher-level features and causes obtained by composing many nonlinearities.

Next: the chapter’s closing synthesis — a catalog of the generic priors by which learners are pointed at underlying causes — providing clues to discover underlying causes.

Check yourself — distributed representations & depth

1.What is the raw combinatorial power of a distributed representation?

2.Predict the outcome — in the RegionCarveLab at n = 6, roughly what region counts do the two modes give (2-D input)?

3.Why do distributed representations generalize where symbolic ones cannot?

4.Despite carving O(n^d) regions, a linear-threshold network's VC dimension is only O(w log w). What prior does distributed-h + linear-classifier express?

5.What does fig 15.9's vector arithmetic (man-with-glasses − man + woman) demonstrate?

6.What do sum-product networks contribute to the depth story (§15.5)?

6 questions