Md. Asif Uddin

    Chapter 5 I.5

    The Multilayer Perceptron

    An MLP is a composition of affine maps and nonlinearities, and depth can buy exponentially in width.

    Alternating affine maps and nonlinearities, each layer re-describing the data for the next.

    How this chapter is built

    M3Load-bearing

    The content is mathematics. Understanding is demonstrated by computation, not recall.

    basics11/11what the words mean
    concept2/2what to picture
    theory4/4why it works, and when it does not
    mathematics15/15derive it, then compute it
    practice9/9build it, break it, read the papers

    Five strands, not one. Mathematics is the spine; the other four are the body. A chapter cannot pay its way out of teaching with problems, nor out of problems with teaching.

    Before you start

    The problem

    The reader leaves I.2 with a perceptron that cannot compute XOR and I.3 with a nonlinearity applied to nothing in particular. Neither is usable alone, and the smallest repair that removes both failures at once is to compose them. That composition is the first architecture worth accounting for — the first with a shape to audit, a parameter count to pay, and a real design decision inside it: given a budget, how much of it should go to width and how much to depth.

    Composition with and without a non-linearityOn the left, two linear layers composed produce a single straight line: the stack collapses to one layer. On the right, the same two layers with a rectifier between them produce a piecewise-linear curve with three segments.linear ∘ linearlinear ∘ relu ∘ linearone line, whatever the depthkinkkinkeach unit contributes a fold
    Fig. 5 — Two linear layers composed give one line whatever the depth. The same two layers with a rectifier between them give a piecewise curve, one fold per unit.

    What this chapter covers

    • The affine layer
    • Composition, depth and width
    • Hidden representations
    • Parameter and shape accounting
    • Activation patterns and linear regions
    • Counting regions: width adds, depth multiplies
    • The depth–width trade-off
    • Minimal width and the rank bottleneck
    • Permutation symmetry of hidden units

    Apparatus

    The mathematics this chapter leans on, held in Book 0 so it can be assumed here without being taught here. Not a gate — follow a link when a step stops making sense.

    Vectors, matrices and the row-major convention 0.LA.01 · Rank, eigenvalues and the singular value decomposition 0.LA.04 · The derivative of a linear map 0.MC.04 · Convexity 0.OP.01

    Notation

    • WA weight matrix
    • bA bias vector
    • xAn input vector
    • dModel width
    • LNumber of layers
    • NParameter count
    • θAll parameters of a model, taken together

    Definitions

    Definition 1Affine layer

    A layer with parameters W ∈ ℝ^{d_in×d_out} and b ∈ ℝ^{1×d_out} sends a row x ∈ ℝ^{1×d_in} to xW + b. It is affine and not linear because of b: without the bias the origin is pinned, since 0·W = 0 for every W, and no layer could place a boundary anywhere except through zero.

    • WA weight matrix
    • bA bias vector

    Definition 2Multilayer perceptron

    The composition a⁽ˡ⁾ = φ(a⁽ˡ⁻¹⁾W⁽ˡ⁾ + b⁽ˡ⁾) for ℓ = 1 … L−1, with a⁽⁰⁾ = x, closed by an affine head a⁽ᴸ⁻¹⁾W⁽ᴸ⁾ + b⁽ᴸ⁾. Every matrix is dense: each coordinate entering a layer reaches every coordinate leaving it. The head carries no φ, which is why the output is unbounded until a loss or a link function bounds it.

    Definition 3Depth

    The number L of affine layers; the network then has L−1 hidden layers. Affine layers are the right thing to count because they are the matrices a linear network would collapse into one — the count of nonlinearities is L−1, and it is that gap between the two counts that makes depth mean anything.

    • LNumber of layers

    Definition 4Width

    The width of layer ℓ is d_ℓ, the number of columns of W⁽ˡ⁾, equivalently its number of units. The tuple (d₀, d₁, …, d_L) fixes every shape and every parameter count in the network, and nothing else does: an MLP is completely specified by its widths and its φ.

    • dModel width

    Definition 5Hidden representation

    The vector a⁽ˡ⁾ for 0 < ℓ < L. It is not a summary of the input and it is not designed: it is whatever coordinate system reduces the loss, and it has meaning only relative to the layers that consume it. Two networks with the same behaviour need have no relation between their hidden representations at all.

    Definition 6Parameter count

    N = Σ_{ℓ=1..L} (d_{ℓ−1}·d_ℓ + d_ℓ), the number of entries in θ. Quadratic in the widths and linear in the depth: doubling one width quadruples one matrix, while adding one layer of the same width adds a single matrix to the sum.

    • NParameter count
    • θAll parameters of a model, taken together

    Definition 7Activation pattern

    For a ReLU network, the binary vector at each layer recording which units have strictly positive pre-activation at a given input. It is a property of the input, not of the parameters alone, and it is what selects the arithmetic the network will perform on that input.

    Definition 8Linear region

    A maximal connected set of inputs sharing one activation pattern at every layer. On it the network is exactly affine — not approximately — so an MLP with piecewise-linear φ is a piecewise affine function whose pieces are its regions.

    Definition 9Depth–width trade-off

    The question of how a fixed parameter budget should be spent: on more units per layer or on more layers. It is not a matter of taste; the two directions buy regions at different rates, one polynomially and one exponentially, and the rates are what the theorems in this chapter compare.

    Definition 10Permutation symmetry

    For any permutation matrix P of size d_ℓ, replacing (W⁽ˡ⁾, b⁽ˡ⁾, W⁽ˡ⁺¹⁾) with (W⁽ˡ⁾P, b⁽ˡ⁾P, PᵀW⁽ˡ⁺¹⁾) leaves the network's function unchanged on every input. The map from parameters to functions is therefore many-to-one, before any question of optimisation arises.

    Formal results

    I.5.T1

    Region count of one hidden layer (Zaslavsky 1975)

    A single hidden layer of n ReLU units on input dimension d cuts the input space along n hyperplanes, so the network is affine on at most Σ_{i=0..d} C(n, i) regions. For fixed d that is Θ(n^d): width buys regions polynomially. In the plane, ten units buy 56 regions and a hundred units buy 5051.

    What this does not promise

    It is an upper bound, reached only when the hyperplanes are in general position — three parallel units in the plane give four regions, not seven. It counts pieces and not accuracy: a target needing few pieces can still be approximated badly, and a network with many regions may spend nearly all of them where no data lies. It says nothing about which of those piecewise affine functions gradient descent reaches, and nothing about generalisation.

    I.5.T2

    Regions multiply with depth (Montúfar, Pascanu, Cho and Bengio 2014)

    A ReLU network with L hidden layers of width n on input dimension d, with n ≥ d, realises at least (⌊n/d⌋)^{d(L−1)} · Σ_{j=0..d} C(n, j) linear regions. Depth sits in the exponent and width in the base, which is the whole asymmetry: thirty units in the plane arranged as three layers of ten reach 35 000 regions, against 466 for one layer of thirty.

    What this does not promise

    It is a lower bound on what a network of that shape *can* realise, exhibited by a construction — not a statement about a trained network, which typically uses far fewer. Region count is not usefulness: the function attaining the bound is a sawtooth nobody wants to fit. And the bound assumes n ≥ d; a layer narrower than the input is governed by rank instead, where no amount of depth recovers what the first matrix discarded.

    I.5.T3

    Depth separation (Telgarsky 2016)

    For every positive integer k there is a network with Θ(k³) layers, Θ(1) nodes per layer and Θ(1) distinct parameters whose function no network of O(k) layers approximates unless it has Ω(2^k) nodes. Some functions are exponentially cheaper deep than shallow, and the gap is a theorem rather than an observation.

    What this does not promise

    It is an existence result about one family of highly oscillatory functions, and gives no reason to expect the functions in any application to resemble them. It is one-directional: some functions are cheaper deep, which is not the claim that deeper is better. It says nothing about optimisation — the deep network realising the sawtooth is not one gradient descent finds from a random start — and nothing about the conditioning and initialisation problems that arrive with depth and that Chapters I.7 and I.8 exist to answer.

    I.5.T4

    Minimal width (Hanin and Sellke 2017; Lu, Pu, Wang, Hu and Wang 2017)

    For input dimension d, the minimal width at which ReLU networks of arbitrary depth can approximate every continuous function on a compact set is exactly d + 1. Hidden layers all bounded by d express a very limited class however deep the network is, so the failure of a narrow network is a statement about the architecture and not about training.

    What this does not promise

    It gives a threshold, not a recommendation: width d + 1 is enough in the limit of unbounded depth, and says nothing about how deep, how well conditioned, or how trainable that network is. It concerns uniform approximation on a compact set, so it makes no claim off that set. Lu et al. prove the companion statement for L¹ approximation at width d + 4, and the two constants differ because the two notions of approximation differ — quoting one bound for the other misstates both.

    I.5.T5

    Permutation symmetry of a hidden layer

    For any layer ℓ and any permutation matrix P ∈ {0,1}^{d_ℓ×d_ℓ}, the substitution (W⁽ˡ⁾P, b⁽ˡ⁾P, PᵀW⁽ˡ⁺¹⁾) leaves the network's output identical at every input. A hidden layer of width n therefore admits at least n! parameter vectors realising the same function; at n = 512 that is more than 10¹¹⁶⁶.

    What this does not promise

    It does not enumerate all the symmetries — ReLU is positively homogeneous, so scaling W⁽ˡ⁾ by c > 0 and W⁽ˡ⁺¹⁾ by 1/c is another, and there are more. It does not say the loss surface has n! minima that training visits; it constrains what a comparison between two networks' weights can mean, not what optimisation does. And it does not make weight averaging useless — only meaningless until the permutation is undone, which is the problem Git Re-Basin sets out to solve.

    Assumptions

    Each is paired with the problem that shows what its removal costs. An assumption nobody tests is a disclaimer.

    • Every unit reads every coordinate of the previous layer. The MLP assumes no structure in the input, so permuting the input coordinates with a fixed permutation leaves the function class unchanged — the architecture cannot tell a photograph from the same pixels shuffled. I.5.X07
    • The hyperplanes a layer draws are in general position, which is what makes the region bound attainable rather than merely an upper limit. I.5.X05
    • Width is fixed before the data is seen and is the same for every example, so capacity is a design decision rather than something the network adapts per input. I.5.X10

    Propositions

    1. Prop. 1A linear layer performs an affine transformation, and nothing more.A dense layer multiplies by a matrix and adds a vector. Every property of it — what it can express, how it composes, why it needs help — follows from that one sentence.
    2. Prop. 2Depth multiplies what width adds.A hidden layer of n ReLU units cuts input space with n hyperplanes, and the pieces grow polynomially in n. A second layer cuts the space the first has already folded, and the pieces multiply. Width and depth are not two ways of buying the same thing.
    3. Prop. 3A hidden layer is a learned coordinate system, not a summary.The hidden vector is not a compressed description of the input. It is whatever set of coordinates makes the next layer's job easy, and it has meaning only relative to the layer that consumes it.
    4. Prop. 4Permuting hidden units changes nothing, and that costs more than it sounds.A hidden layer of width n has at least n! parameter settings computing the identical function. Weights are therefore not comparable between runs, and averaging two trained networks is meaningless until the permutation is undone.

    Numbered equations

    1. a⁽ˡ⁾ = φ(a⁽ˡ⁻¹⁾W⁽ˡ⁾ + b⁽ˡ⁾), a⁽⁰⁾ = x, ŷ = a⁽ᴸ⁻¹⁾W⁽ᴸ⁾ + b⁽ᴸ⁾

      The entire architecture in one line: re-describe, bend, repeat, then read off.

      (I.5.1)

    2. N = Σ_{ℓ=1..L} (d_{ℓ−1}·d_ℓ + d_ℓ)

      Parameters are quadratic in width and only linear in depth.

      (I.5.2)

    3. ŷ = x(W⁽¹⁾D W⁽²⁾) + (b⁽¹⁾D W⁽²⁾ + b⁽²⁾), D = diag(1[z⁽¹⁾ > 0])

      Inside one region the network is a single affine map, and D names which one.

      (I.5.3)

    4. R₁(n, d) ≤ Σ_{i=0..d} C(n, i)

      One hidden layer buys regions polynomially in its width.

      (I.5.4)

    5. R_L(n, d) ≥ (⌊n/d⌋)^{d(L−1)} · Σ_{j=0..d} C(n, j)

      Depth sits in the exponent, which is where the separation comes from.

      (I.5.5)

    6. f(W⁽ˡ⁾, b⁽ˡ⁾, W⁽ˡ⁺¹⁾) = f(W⁽ˡ⁾P, b⁽ˡ⁾P, PᵀW⁽ˡ⁺¹⁾)

      n! parameter vectors, one function: weights are not a coordinate system.

      (I.5.6)

    Worked problems

    7/5 problems7/4 variants10/10 exercisesquota met, and enforced

    1. I.5.B01 — Three inputs, two regions, one networknumeric▲△△
    2. I.5.B02 — Every region is one matrix, and its rank is the count of live unitssymbolic▲▲△
    3. I.5.B03 — A shape and parameter audit of a four-layer MLPshape▲△△
    4. I.5.B04 — Width costs a square, depth costs a linecomplexity▲▲△
    5. I.5.B05 — Twenty units deep against a thousand widecounterexample▲▲▲
    6. I.5.B06 — Relabelling the hidden units, and what that forbidsproof▲▲△
    7. I.5.B07 — How many pieces a budget buys, and where you put themlimit▲▲△

    The whole problem set, with the exercises →

    Practice

    • The dense assumption costs a square, and the bill lands on the first matrix. An MLP taking a 224×224×3 image as 150 528 numbers into one hidden layer of 4096 units and then 1000 classes holds 620 663 784 parameters — 2.48 GB in fp32 — of which 616 566 784 sit in the input-facing matrix alone. A 3×3 convolution producing 64 channels from the same image holds 1792. Nothing about the task changed; only the assumption that every input touches every unit.
    • A hidden layer narrower than the input destroys information that no later layer recovers. With d₀ = 10 and d₁ = 3, W⁽¹⁾ has rank at most 3, so its null space has dimension at least 7: there are non-zero directions v with vW⁽¹⁾ = 0, and x and x + v produce byte-identical pre-activations. Every subsequent layer sees one vector, so no depth, no width later on, and no amount of training separates them. This is a rank fact, not an optimisation difficulty — and I.5.T4 is its general form.
    • Averaging the weights of two independently trained MLPs usually produces a network worse than either. Two solutions that compute nearly the same function can differ by any of the at least 512! ≈ 10¹¹⁶⁶ permutations of a width-512 hidden layer, so unit j of one network has no relation to unit j of the other, and their mean is a network neither trained. Weight-space comparison across runs — averaging, interpolation, per-unit correlation — is meaningless until the permutation is aligned.