A set has no order, so a model for sets must give the same answer in every order. Deep Sets proves that adding up a code for each item, then reading the total, can compute any such function.
Press Shuffle a few times with each model. One of them answers differently every time. Then we build, piece by piece, the proof, the network and every experiment.
You need what a neural network layer does (a weighted sum, then a bend) and a little Python. We build the rest from zero.
A paper reading for MIT MMAI: Multimodal AI (Spring 2026), part of Lecture 4: Data and Heterogeneity. Paper: Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov and Alexander Smola, Deep Sets, NIPS 2017 (arXiv 1703.06114).
Toy numbers (2, 7, 1, 8, 3), illustrative. Both models try to output the mean, 4.20. The order reader is untrained: h = 0.5 h + 0.5 x, read left to right. Deep Sets uses the paper’s own mean example (Appendix A): phi(x) = (1, x), add, rho(u, v) = v / u.
Chapter 0
See why a model that reads its input in order cannot be trusted on a bag of things, and what the paper promises instead
A cashier scans your basket: milk, eggs, bread. The total is the same if she scans the bread first. Now picture a program that reads the same basket as a list. It gives a different total when the order changes. You would not trust it with your money.
That is the problem of this paper. Many inputs are sets: collections of items where position carries no meaning. A scanner returns thousands of points in 3D, and the sensor chose their order by chance. A galaxy cluster is a crowd of galaxies. A photo album is a pile of faces. The authors list more: estimating the statistics of a population from samples, spotting an odd reading in the water sensors of a dam, and measuring the mass of the universe in cosmology.
The task must not care how you list the items. The paper calls this permutation invariance. A permutation is just a reshuffling of the positions. Invariance means the answer does not change under any reshuffling. Chapter 1 makes this exact.
Most models are built for a fixed-length vector: a list of numbers with a set length where each slot has its own meaning. Slot 1 might be age and slot 2 might be height. A set breaks this in two ways. Sets come in different sizes. And no item belongs in any particular slot.
You could force the set into a vector anyway. Flatten the items in the order they arrived. The network then learns separate weights for slot 1, slot 2 and slot 3. It treats “the galaxy in slot 1” as a different thing from “the same galaxy in slot 2”. It must learn the same lesson once for every slot.
You could use a recurrent network (an LSTM or GRU: a model that reads items one at a time and carries a memory forward). This gives order a meaning by design. The memory after item 3 depends on items 1 and 2. The paper tests exactly this on a sum of digits, and the recurrent models generalize worse (Chapter 6).
You could sort the items first, or search for a good order. The paper cites a method that does the latter. But any sort rule is a choice the task never asked for. Two nearly equal sets can sort very differently, and the model sees them as far apart.
You could augment: show the model every order during training. This is the idea to test with numbers. A set of M items can be written in M! orders, read “M factorial”: M × (M−1) × … × 1. For 5 items that is 120. For 10 items it is 3,628,800. Try the device below.
The bar shows how many digits the count of orders has. Drag the number of items and watch it grow faster than the set does.
The count is M factorial, computed exactly in logarithms. Nothing here is from the paper’s tables; it is the arithmetic behind the paper’s motivation.
At 20 items the count is about 2.4 × 1018. At 100 items it is about 9.3 × 10157. No dataset covers that. A model that must learn each order separately never sees most of them. A model that is built to ignore order sees them all as one input.
The authors, Manzil Zaheer and five co-authors at Carnegie Mellon and Amazon, state four contributions. First, an architecture called DeepSets, with a proof that its shape is both necessary and sufficient for order-free functions. Second, a way to condition it on extra information. Third, a network that handles sets of different sizes. Fourth, experiments on very different problems.
The headline idea fits in one line. Give each item a code. Add the codes. Read the total. We build it step by step, and then we test it on seven experiments.
Where this paper sits. This paper is a reading for Lecture 4, Data and Heterogeneity. Our own framing, not the slides’: image patches, audio frames and sensor readings are often a bag, and a model for a bag must respect that symmetry.
Here is the map of what follows.
Chapter 1
Learn the two symmetries a set model can have, and test any function against them with a worked example
Take a class photo with a caption: “Class of 2017, 24 students.” Ask everyone to swap seats. The caption stays true. Now put a name tag on every student. When two students swap seats, their tags swap too. The tags changed, but in a predictable way: each tag followed its student.
These two behaviours have names. The caption is permutation invariant: reshuffle the input and the output does not change. The name tags are permutation equivariant: reshuffle the input and the output reshuffles in the same way. Invariant means “one answer for the whole set”. Equivariant means “one answer for each item, and the answers keep their owners”.
Let X = {x1, …, xM} be a set of M items. The paper’s Property 1 says a function f on sets must satisfy this for every permutation π.
The second property, equation (1) in the paper, is for functions that return one output per item.
Let x = (2, 5, 1). Take f = the sum. The sum of 2, 5, 1 is 8. Reorder to (5, 1, 2): the sum is 8. Try all 3! = 6 orders. Every one gives 8. So the sum is invariant.
Now take g = “square each item”. On (2, 5, 1) it gives (4, 25, 1). On the reordered input (5, 1, 2) it gives (25, 1, 4). That is exactly the first output with its entries moved the same way. So squaring each item is equivariant.
Finally take h = “first item minus last item”. On (2, 5, 1) it gives 1. On (5, 1, 2) it gives 3. The answer changed with the order, so h is not invariant. It is not a function of the set at all.
sum: 8, 8, 8, 8, 8, 8 → invariant · square each: follows the items → equivariant · first minus last: 1 or 3 → neither
Each row feeds the same four numbers in a different order. Pick a function and see whether its output stays put, follows the items, or does neither.
Toy input (2, 5, 1, 3), illustrative. The verdict tests all 24 orders of the four numbers; the six rows are a sample. “Same” means the output equals the original row’s; “follows” means each output moved with its item.
The symptom: the same photo album gets two different labels on two runs. Nothing is random in the model. Only the file order changed. The measurement is the device above, run on your own model: feed every order of a small set, or a few hundred random ones, and count how many distinct outputs you see. One output means invariant. Many means the model is reading position.
The fix is not to sort the input or to average the outputs over orders. It is to build the model from parts that cannot see position: a shared per-item function, then a commutative pool. The next three chapters build exactly that.
The authors use the two properties in three settings. In supervised learning the whole set has one label. Estimating a population statistic is an example. The function must be invariant.
In the unsupervised setting there is no label. The model scores sets, giving a high score to a sensible set and a low one to an odd set. The score is invariant again. The paper uses it for set expansion: given {lion, tiger, leopard}, find words like jaguar.
In the transductive setting every item has its own label. Finding the odd face in a group is an example. The function must be equivariant, because the label for a face must follow that face when the faces are shuffled.
Chapter 2
Follow the paper’s main theorem and run its proof: add one code per item, and no set can be mixed up with another
You run a small zoo and keep a tally of which animals are in a pen. You do not care in which order the keepers listed them. Here is a trick. Give every animal its own colour of ink. Each time an animal is in the pen, add one drop of its ink to a jar. The jar ends up one exact shade. Two different pens give two different shades, because the colours never blur into each other.
The jar is a sum: adding is order-free, since 2 + 5 is 5 + 2. And the jar still tells the pens apart. If this trick works for every possible set, then sums lose nothing. That is the paper’s main claim, and it is a theorem.
Say the items come from a countable universe: a list you could number 1, 2, 3 and so on, such as all English words. The paper’s Theorem 2 says a function f on sets is a valid set function (invariant) if and only if it can be written in this form.
“If” is the easy half. Any function of that shape is order-free, because the sum is. “Only if” is the hard half: every order-free function can be written this way. That is the claim that justifies a whole architecture.
The proof in Appendix A.1 builds φ by hand. Number the items in the universe: c(x) = 1, 2, 3, … Then set φ(x) = 4−c(x). Item 1 gets 0.25. Item 2 gets 0.0625. Item 3 gets 0.015625. Each item owns one “digit” of a number written in base 4.
Take a zoo of three animals numbered cat = 1, dog = 2, fox = 3. The pen {cat, fox} sums to 0.25 + 0.015625 = 0.265625. The pen {dog, fox} sums to 0.0625 + 0.015625 = 0.078125. The pen {cat, dog} sums to 0.3125. Three different pens give three different totals.
Why can two sets never collide? Look at the sum in base 4. Each item adds a 1 to its own digit. A set has no repeats, so every digit is 0 or 1, and nothing ever carries into a neighbour. The digits spell out exactly which items are present. Read them back and you recover the set. (The paper picks base 4. In our reading, base 2 would also keep the digits apart for repeat-free sets, but 4 leaves room for an item to appear up to three times.)
The last step is ρ. Each set has its own unique number, so we can define ρ as a lookup table: take the number, find the set, and return f of that set. Then ρ(∑ φ(x)) = f(X) by construction. Done.
Each animal owns a slot worth 4 to the power minus its number. Tap animals to put them in the pen. The marker shows where the sum falls among all 64 possible pens.
The six animals are an illustration, not from the paper. The encoding phi(x) = 4^(-c(x)) is the paper’s (Appendix A.1). The check of all 64 sums runs in your browser.
Be careful here. The lookup-table ρ is wild: it jumps between neighbouring numbers and cannot be learned from a few examples. The theorem does not say to build φ this way. It says that sum-then-read loses no power. That is a licence to design the network around the sum, and to hope that a smooth, learnable φ and ρ exist.
The appendix gives gentler examples where φ and ρ are simple. The mean of M items: φ(x) = (1, x), so the sum is (M, total), and ρ(u, v) = v / u. For {2, 4, 9} the codes are (1, 2), (1, 4), (1, 9), the sum is (3, 15), and ρ gives 15 / 3 = 5.
A product-like function: x1x2(x1 + x2 + 3). Use φ(x) = (x, x2, x3) and ρ(u, v, w) = uv − w + 3(u2 − v)/2. For (1, 2) the codes are (1, 1, 1) and (2, 4, 8). The sum is (3, 5, 9). Then ρ = 15 − 9 + 3(9 − 5)/2 = 6 + 6 = 12. Direct: 1 × 2 × 6 = 12. It matches.
Even the maximum fits, in the limit. Use φ(x) = (eαx, x eαx) and ρ(u, v) = v / u. For {1, 2, 3} and α = 2 the answer is 2.85. At α = 5 it is 2.99. As α grows it reaches 3. So “sum” is not the same as “sum only”: a sum with a clever φ can imitate a mean or a max.
The paper links Theorem 2 to older work. De Finetti’s theorem says an exchangeable model (one that ignores the order of its samples) can be written as an average over a hidden variable of a product of per-sample terms. For the common exponential families, this collapses to a form with exactly a sum of per-item terms inside. Kernel methods on sets and spectral methods also fit the same shape. DeepSets is the learnable version.
Chapter 3
Build the phi, sum, rho network with real tensor shapes, trace three items through it by hand, and write the code
Picture a meeting of M people. Each person writes a short note about themselves, using the same form. The notes go into a box, and a clerk adds them up, field by field. A chair then reads only the total and makes a decision. The chair never sees who wrote what, and the clerk never cares who came first. That is the whole network.
Theorem 2 says f(X) = ρ(∑ φ(x)) is enough. The paper’s recipe is to replace φ and ρ with neural networks (stacked layers of weighted sums and bends that can learn a function from examples) and to train them together. Three steps.
Let the set have M items and let each item be a vector of d numbers. Stack them as a matrix X of shape M × d. A point cloud has d = 3 (x, y, z). A word has d = 50 if we use a 50-dimensional embedding.
The network φ maps d to h, where h is the width the designer picks. It is applied to every row with the same weights. The result Z has shape M × h. The words on a page look the same, but shared weights are the whole point: if φ differed by row, swapping two rows would change the answer.
The pooling step sums Z over the M axis. The result is a single vector s of shape h. Notice that M has vanished. The next step does not know how many items there were, except through the size of the numbers in s.
The network ρ maps h to the answer, say 1 for a score or 40 for 40 class logits. A logit is a raw score before it becomes a probability.
Take three items with d = 2: x1 = (1, 0), x2 = (0, 2), x3 = (3, 1). Let φ(x) = ReLU(Wx) with W = [[1, 1], [1, −1]], so h = 2. ReLU means “replace negatives with 0”.
For x1: Wx = (1, 1), ReLU keeps it, so φ = (1, 1). For x2: Wx = (2, −2), ReLU gives (2, 0). For x3: Wx = (4, 2), so φ = (4, 2). Sum: (1 + 2 + 4, 1 + 0 + 2) = (7, 3). Let ρ(s) = 1·s1 + 2·s2 = 7 + 6 = 13. Reorder the items any way you like: the sum is still (7, 3) and the answer is 13.
Press Next step to reveal phi, the sum and rho in turn. Then press Shuffle items and watch the rows move while the pooled vector stays fixed.
Toy weights chosen for hand arithmetic, illustrative: phi(x) = ReLU(Wx) with W = [[1, 1], [1, -1]], and rho(s) = s1 + 2 s2. A real network learns both from data.
In the population-statistics experiments, both φ and ρ are three fully connected layers with ReLU. In text concept retrieval (Appendix E), φ first turns each word into a learned 50-dimensional embedding, then applies two layers of width 150. After pooling, ρ has three layers of widths 150, 75 and 1, and its single output is a score. In point-cloud classification the network is a stack of equivariant layers (Chapter 5) with a max pool at the end.
The paper also allows conditioning: extra information z, such as an image, joins in. One way is to write φ(x | z) by concatenating z to every item before φ. In image tagging, the image features are concatenated with the pooled tag representation.
Backpropagation through a sum is simple. The derivative of s with respect to each φ(xm) is the identity. So every item receives the same upstream gradient, the gradient of the loss with respect to s. The shared network φ collects a small update from every item in the set. The sum accepts any M. The red-shift experiment shows this: its galaxy clusters hold from 20 to 300 galaxies.
pythonimport torch, torch.nn as nn class DeepSets(nn.Module): def __init__(self, d, h, out): super().__init__() self.phi = nn.Sequential(nn.Linear(d, h), nn.ReLU(), nn.Linear(h, h), nn.ReLU()) self.rho = nn.Sequential(nn.Linear(h, h), nn.ReLU(), nn.Linear(h, out)) def forward(self, x, mask=None): # x: (B, M, d) mask: (B, M) of 0/1 z = self.phi(x) # (B, M, h) same weights on every item if mask is not None: z = z * mask[..., None] # padded items add nothing s = z.sum(dim=1) # (B, h) the order-free pool return self.rho(s) # (B, out)
Read the code once. Where is the order thrown away? On the line with sum(dim=1). Where could order sneak back in? Only if you added something that depends on the position of an item, such as a positional code or a layer that mixes items by index. Do not. The mask handles sets of different sizes: a padded slot is zeroed before the sum, so it adds nothing.
The symptom: a network trained on small sets gives wild outputs on large ones. The measurement: the pooled vector grows roughly in step with M, so at M = 100 its size is ten times what ρ saw in training. The fix, in our own words and not the paper’s: train on a range of sizes, or divide the sum by M and feed M separately. The digit-sum experiment in Chapter 6 shows the other side, where the sum helps because the answer itself grows with M.
Chapter 4
See how sums of powers still pin down a set of real numbers, and what the paper can and cannot prove about it
The zoo trick of Chapter 2 needs a number for every possible item. Sensor readings are real numbers, and there are too many of them to list: between 0.1 and 0.2 there are infinitely many more. You cannot give each one its own digit. Does a sum still work?
The paper answers yes, with one condition. The set must have a fixed size M, and the items must lie in a bounded range, say between 0 and 1. The answer comes from a classical piece of algebra. A set of M numbers is fully described by the polynomial whose roots are those numbers. Roots are the inputs that make the polynomial zero. And the coefficients of that polynomial can be built from sums of powers.
The power sums of a set are pq = ∑ xq, for q = 1, 2, 3 and so on. The paper writes them Eq, and includes q = 0, which just counts the items. Notice the shape. Each power sum is a sum of a function of one item at a time. That is exactly ∑ φ(x) with φ(x) = (x, x2, …, xM).
The proof (Appendix A.2) has four steps.
Here is the arithmetic for the set {1, 2, 3}. The power sums are p1 = 1 + 2 + 3 = 6, p2 = 1 + 4 + 9 = 14, p3 = 1 + 8 + 27 = 36. Newton-Girard gives e1 = p1 = 6. Next e2 = (e1p1 − p2) / 2 = (36 − 14) / 2 = 11. Last e3 = (e2p1 − e1p2 + p3) / 3 = (66 − 84 + 36) / 3 = 6.
P(x) = x3 − 6x2 + 11x − 6 = (x − 1)(x − 2)(x − 3)
Three numbers in, three power sums, one polynomial, and the original three numbers come back as its roots. Try your own set in the device. It finds the roots from the power sums alone, with a numerical root finder.
Move the three sliders. The curve is the polynomial built only from the three power sums. Its zeros are the numbers you chose.
Illustrative numbers. The device uses the paper’s steps (Newton-Girard, then the roots of the polynomial); the roots come from a numerical solver run on the power sums, never from your sliders. The proof itself uses numbers in [0, 1]; the algebra is the same on any range.
Theorem 9 goes further. For sets of fixed size M from a bounded region of Rd, any continuous permutation-invariant function can be approximated as closely as you like by ρ(∑ φ(x)). The proof uses two classical facts. Polynomials can approximate any continuous function (the Stone-Weierstrass theorem). And every symmetric polynomial can be written using sums over single items (the fundamental theorem of symmetric functions).
The paper compares this to the Kolmogorov-Arnold theorem, which writes any continuous function of M inputs as ρ(∑ λm φ(xm)). The coefficients λm tie each input to its position. Demanding invariance removes them. The authors call it reassuring that the same shape appears.
Now the limits, stated plainly. The proofs cover a fixed M. For sets of all sizes in an uncountable universe, the authors only conjecture the same form holds, because the space of such sets has no natural notion of “continuous”. They suggest a distance called MMD as a way forward. Also, the proof uses M + 1 channels, which hints that the pooled vector must be wide enough (our reading: this is why the width h matters).
The symptom: the pooled vector contains huge values and learning stalls. The measurement: for ten items near 10, the tenth power sum is about 1011, against about 100 for the first. The fix: scale the items into a small range first. The paper does this in its point-cloud network, which normalizes each set to zero mean and unit variance in its first layer.
Chapter 5
Derive the only weight matrix that lets every item keep its own output, and stack it into the paper’s set networks
A teacher marks a set of tests and wants to give each student a curved grade. The curve for student i uses student i’s own mark and the class total. If two students swap desks, their grades must swap too. The rule must not care about desks, only about who scored what.
The invariant network of Chapter 3 returns one answer for the whole set. Some tasks need one answer per item: which face is the odd one, or what is the red-shift of each galaxy in a cluster (a number that says how far away, and how old, a galaxy looks). For these the paper builds equivariant layers. You met the definition in Chapter 1. Here we derive the layer.
Take the simplest case: M items, each a single number, so the input is a vector x of length M. A standard layer computes f(x) = σ(Θx). Here Θ is an M × M matrix of weights, and σ is a nonlinearity, such as ReLU, applied to each entry. We ask: which Θ make f equivariant?
Equivariance means f(πx) = πf(x) for every permutation π. A permutation can be written as a permutation matrix. So the condition is that Θ commutes with every permutation matrix: Θπ = πΘ.
Use the simplest permutations: swaps of two positions k and l. Swapping rows k and l of Θ and then columns k and l must give back the same Θ. Look at what that forces.
That is Lemma 3, proved in the paper’s Appendix B. In matrix form:
Read it as a sentence. Output i is σ(λ xi + γ ∑j xj): a bend of “my own value” plus a fixed fraction of “the sum of everyone”. The sum is a pooled signal, just like Chapter 3, and every item gets a copy.
Let M = 3, λ = 1, γ = 0.5 and x = (2, 5, 1). The sum is 8, and γ times it is 4. Output i = xi + 4, so Θx = (6, 9, 5), and ReLU keeps all three. Now reorder the input to (5, 1, 2). The sum is still 8. The output is (9, 5, 6). That is the first output with its entries moved the same way. The layer is equivariant.
Count the parameters. A free 3 × 3 matrix has 9. The tied layer has 2. For M = 100 the free matrix has 10,000 parameters and the tied layer still has 2. The tie also makes the layer work for any M.
Pick tied or free weights, then press Shuffle items. The bottom rows compare “reshuffle the outputs” with “output of the reshuffled inputs”. They must match.
Toy input (2, 5, 1, 3), ReLU, illustrative. The free matrix is a fixed random matrix with entries between 0 and 1.2. The tied form is Lemma 3 of the paper.
Real items are vectors, not single numbers. Let the input be a matrix x of shape M × D, with D channels per item, and let the output have D′ channels. The paper’s equation (22) is f(x) = σ(xΛ − 11TxΓ), where Λ and Γ are D × D′ matrices. The first term maps each item alone. The second maps the column sums, which are the same for every row. The minus sign is the paper’s convention; it can be absorbed into Γ.
The paper also gives a max version, f(x) = σ(xΛ − 1 maxpool(x) Γ), where maxpool takes the largest value of each channel over the items. It adds that this “performs better in some applications”, perhaps because the input to the nonlinearity is max-normalized. A compact form with fewer parameters is f(x) = σ(β + (x − 1 maxpool(x))Γ).
A stack of equivariant layers is still equivariant, because composing two functions that obey the rule obeys the rule. Finish with any commutative pool, such as sum or max, and the whole network becomes invariant. The paper uses exactly these two shapes.
The symptom: the outlier model scores 6.3% on training and test sets. The measurement: with 16 faces, picking at random is right 1 time in 16, which is 6.25%. The cause: the baseline pooled the convolution features and then used fully connected layers ending in a 16-way softmax. That head is not equivariant, so each output slot learns about a slot, not about a face. The fix: replace the head with equivariant layers. Accuracy rose to 75%.
Chapter 6
Follow the data, the losses and the metrics of the paper’s experiments, and compute the error ceiling of the digit-sum task
Imagine teaching a child to add by showing a handful of handwritten digit cards and saying only the total. You never say which card is a 3 or a 7. The child must work out what each card is worth and then add. Now give the child 50 cards, when it only ever saw 10. A good adder just keeps adding. That is the digit-sum task, and it is the paper’s cleanest test of why a sum belongs in the architecture.
There are two versions. In the text version a set holds up to M = 10 digits and the label is their sum. In the image version each digit is a 28 × 28 grey picture from MNIST8m (8 million handwritten digits), and the label is the sum of the pictured digits. The model never gets the label of a single picture. The authors build 100k training sets and 100k test sets. Training uses sets of at most 10. Testing goes up to 100 for text and 50 for images.
The competitors are recurrent networks, an LSTM and a GRU, built with a similar number of layers and parameters. The score is exact accuracy: the rounded prediction must equal the true sum. In the paper’s Figure 2, DeepSets “generalizes much better” to sets longer than any it trained on. Our reading of why: φ only needs to learn the value of one digit, and the sum handles any count for free. The recurrent models must learn a routine that depends on length.
Even a perfect adder fails sometimes, because the picture classifier is not perfect. The paper notes the best single-digit error on MNIST8m is about p = 0.01. A sum of N pictures is right only if all N are read right. So the chance that at least one is wrong is 1 − (1 − p)N.
Work it. For N = 10: 0.9910 = 0.904, so 1 − 0.904 = 9.6% of sets contain an error. For N = 50: 0.9950 = 0.605, so 39.5% do. The paper says this “matches closely” the 40% it sees in Figure 2(b). The limit comes from reading single images, not from the sum.
The curve is (1 − p) to the power N: the chance that every image in the set is read right. Drag the set size and the single-image error.
The formula and the 1% error (MNIST8m, best single-digit error) are the paper’s argument in Section 4.1.2. The curve is computed, not read from Figure 2. The shaded zone marks set sizes above the training limit of 10.
Here the set is a bag of samples from a distribution, and the label is a property of the distribution. In one setup the sets hold 300 to 500 samples from a 2D Gaussian that was rotated by a random angle, and the target is the entropy of the first coordinate (one number for how spread out and unpredictable the values are). Other setups ask for the mutual information (how much two groups of variables tell you about each other) with varying correlation, a rank-1 strength, or a random 32 × 32 covariance. The network is told nothing about Gaussians. Both φ and ρ are three fully connected layers with ReLU, trained with squared error. The baseline is Support Distribution Machines (SDM), a kernel method.
Given a few words that belong to a theme, such as {tiger, lion, cheetah}, score every other word by how well it fits. The score follows de Finetti’s theorem. For an item x and a set X, it is the pointwise mutual information.
DeepSets learns this score directly, with a large-margin objective. The loss for a good word x and a bad word x′ is l(x, x′ | X) = max(0, s(x′ | X) − s(x | X) + Δ(x, x′)), where Δ is the margin the good word should win by. Worked example with Δ = 1. If s(x) = 2.0 and s(x′) = 1.5, the loss is max(0, 1.5 − 2.0 + 1) = 0.5: the good word wins, but by less than the margin. If s(x) = 3.0 and s(x′) = 1.0, the loss is max(0, 1 − 3 + 1) = 0: the margin is met, so no gradient.
The data (Appendix E): run latent Dirichlet allocation, a topic model, on Wikipedia, and take each topic’s top 50 words as one set. With 1k, 3k and 5k topics the vocabularies hold 17k, 38k and 61k words. The split is 80% train, 10% validation, 10% test. Three metrics measure retrieval. Recall@K is the share of true words found in the top K. Mean reciprocal rank averages 1 / rank of the true word: rank 3 gives 0.33. Median rank is the middle rank, where lower is better.
For image tagging, the pooled tag representation is concatenated with the image features. The model trains to predict the missing tags from the image and the remaining tags. At test time it predicts tags from the image alone. For anomaly detection, each CelebA set has 16 faces: 15 share two chosen attributes, and one has neither of them. The paper builds 18,000 such sets, and the model never sees the attributes. For red-shift, each galaxy cluster of 20 to 300 galaxies, with 17 features each, is a set. Only some galaxies have a measured (spectroscopic) red-shift, so the loss covers only those.
The symptom: exact-sum accuracy falls steadily with N, even though the sum works. The measurement: compare against (1 − p)N. If the observed curve sits on it, the sum is fine. The fix: improve the per-item reader φ, not the pooling.
Chapter 7
Walk through every figure and table of the paper, learn what each column measures, and judge how strong each win is
A paper that claims one model works everywhere owes you seven separate checks. Here they are in the paper’s order. For each one we say what was measured, against what, and how big the gap is. The authors’ own summary is modest: the state of the art is a specialised method for each task, while DeepSets is “competitive across the board”.
The four panels estimate entropy and mutual information of Gaussian sets. The top row plots predictions against truth for 210 = 1,024 training sets; the bottom row plots error as the number of sets grows. The honest reading from the caption: SDM, the kernel baseline, has lower error with few sets, and DeepSets needs more data to catch up. But SDM must invert an N × N matrix, which becomes too costly above N = 214 = 16,384. For the high-dimensional problems DeepSets scales to many sets and reaches much lower error.
Accuracy against set size, trained on at most 10 and tested up to 100 (text) or 50 (images). DeepSets stays ahead of the LSTM and GRU as sets grow. Chapter 6 computed why the image curve must fall: at 50 images about 40% of sets contain a misread digit.
ModelNet40 holds 9,843 training and 2,468 test 3D objects in 40 classes. The authors sample 100, 1,000 or 5,000 points per object. Their numbers: 90 ± 0.3% with 5,000 points, 87 ± 1% with 1,000, and 82 ± 2% with 100. The rivals use voxels (a 3D grid of cubes) or many 2D views: 3DShapeNets 77%, VoxNet 83.10%, a multi-view CNN 90.1%, a voxel ensemble 95.54%, a 3D GAN 83.3%. So DeepSets ties the multi-view CNN with a far smaller input, but the voxel ensemble is ahead by more than five points. A graph-convolution network on 1,000 points reaches only 58 ± 2%.
The metric is the average scatter, |zspec − z| / (1 + zspec), where lower is better. A plain MLP scores 0.026, the catalogue’s own estimate (redMaPPer) 0.025, and DeepSets 0.023. A small win, from giving the model the galaxy’s whole cluster.
Columns: recall at 10, 100 and 1,000 in percent (higher is better), mean reciprocal rank (higher is better) and median rank (lower is better). Here are the 3k-topic results.
| Method (LDA-3k) | Recall@10 | Recall@100 | Recall@1k | MRR | Median rank |
|---|---|---|---|---|---|
| Random | 0.02 | 0.2 | 2.6 | 0.000 | 28,635 |
| Bayes Set | 2.01 | 14.5 | 36.5 | 0.008 | 3,234 |
| w2v Near | 4.80 | 21.2 | 43.2 | 0.016 | 2,054 |
| NN-max (max pool) | 5.30 | 24.9 | 54.8 | 0.025 | 672 |
| NN-sum-con | 5.81 | 27.2 | 60.0 | 0.027 | 453 |
| NN-max-con | 5.61 | 25.7 | 57.5 | 0.026 | 570 |
| DeepSets | 6.04 | 28.5 | 60.7 | 0.027 | 426 |
DeepSets wins or ties every column on the 3k and 5k data (on 3k the mean reciprocal rank ties at 0.027). On the 1k data, the smallest, it loses to w2v Near (recall@10: 5.53 against 6.00). The authors blame the small dataset for a big network, since w2v was trained on a billion words.
On ESPgame and IAPRTC-12.5, the metrics are precision (P), recall (R), F1 and the number of tags found at all (N+). DeepSets scores P 39, R 34, F1 36, N+ 246 on ESPgame, against 44, 32, 37, 229 for the strongest rival. It beats recall by 2 points and loses on precision. The authors argue it finds relevant tags that the five-tag annotation did not list. On COCO-Tag the gap is large: recall@10 is 31.4% against 5.6% for the word2vec baseline and 9.0% for DeepSets without the image.
On 16-face CelebA sets, the equivariant network finds the odd face in 75% of test sets. A baseline with the same convolutions but no equivariant head scores 6.3%, which is random.
Pick an experiment. The purple bars are DeepSets. Read the axis note: for red-shift, a shorter bar is better.
All numbers are from the paper: Table 1 (and Table 6), Table 2, Table 3 (LDA-3k, recall at 10), Table 5 (recall at 10) and Section 4.3. The random-guess line for the odd face is 1 in 16.
Not all wins are equal. Count the size of the gap against the noise the authors report. Point clouds show a spread of 0.3 to 2 points across runs, so 90% against 90.1% is a tie. Red-shift gains 0.003 in scatter, which is small but comes from only adding the cluster as context. Set expansion on 3k topics gains only 0.23 points of recall@10 over the best rival (6.04 against 5.81), though every other column also favours it. The COCO and odd-face gaps are far larger than any spread the paper reports, though the paper gives no error bars for them.
Also check the direction of each column. Recall and accuracy go up when the model is better. Scatter, median rank and error go down. The device marks this on every axis, because a bar that looks short is a win in some tables and a loss in others.
Chapter 8
Separate the paper’s controlled comparisons from its loose ends, and test which pooling keeps which answer
A result means little until you know what was held fixed. A good ablation changes one part and leaves the rest alone. This paper has several, scattered through its tables. Let us collect them, and then be honest about what the paper does not show.
Why does sum beat max on some tasks and not others? Because each pool throws different things away. Sum keeps totals and counts. Max keeps only the biggest value in each channel. Mean keeps the average but forgets the count. A task is solvable from the pooled vector only if the pooled vector still holds the answer.
The device tests this on 1,500 random sets of up to 6 digits, with no learning at all. For each pooling and each task, it asks: do two sets ever share a pooled vector but have different answers? If yes, no ρ can recover the answer. Try both choices of φ.
Rows are tasks and columns are poolings. A green cell means the pooled vector always determines the answer. Red shows how many sets collide with a set that has a different answer.
A toy test, illustrative and not from the paper: 1,500 random sets, 1 to 6 digits (0 to 9), pooled by sum, mean or max per channel. Answers are count, total, average and biggest. It checks whether the pooled vector could determine the answer; it trains nothing.
With a bare φ(x) = x, every pooling answers exactly one question: sum gives the total, mean gives the average, max gives the biggest. Add a constant channel, φ(x) = (1, x), and the sum now carries the count too, so it answers three of the four. That is the same trick the paper uses for the mean in Chapter 2. Sum is the pooling with the most room, which is why the theorem is stated for it.
Outside the paper, and our own framing: self-attention (see Understanding attention) treats its inputs as a set of tokens unless you add position codes. It is permutation equivariant, and a final pool makes it invariant, which is the same recipe as Chapter 5 with richer interaction between items. Point-cloud networks, graph networks (graph neural networks) and multimodal models that pool over patches or frames all lean on the same symmetry. Geometric deep learning places permutation next to the other symmetries.
Chapter 9
Keep the numbers, the terms, a build checklist and the core code, and find where to go next
Deep Sets studies functions on sets. It proves that every order-free function of a countable set has the form ρ(∑ φ(x)), shows the same form can approximate any continuous order-free function of fixed-size real sets, and derives the only weight tying that keeps each item’s output with its item. One model then handles population statistics, digit sums, point clouds, red-shift, set expansion, image tagging and odd-one-out detection.
| Item | Value | Where |
|---|---|---|
| Orders of a set | 10 items: 3,628,800. 100 items: about 9.3 × 10157 | Chapter 0, M factorial |
| Proof encoding | phi(x) = 4−c(x), then rho is a lookup | Appendix A.1, Theorem 2 |
| Fixed-size sets | power sums Zq, q = 0 to M, identify the set | Appendix A.2, Lemmas 4 and 6 |
| Tied layer | Theta = lambda I + gamma 11T, 2 numbers for any M | Lemma 3 |
| Text retrieval net | 50-d embeddings, phi two layers of 150, rho 150, 75, 1 | Appendix E |
| Digit sum | train up to 10, test up to 100 (text) or 50 (images); 100k sets; error ceiling 39.5% at 50 images | Section 4.1.2 |
| ModelNet40 | 90 ± 0.3% at 5000 points, 87 ± 1% at 1000, 82 ± 2% at 100 | Tables 1 and 6 |
| Red-shift | 26,111 clusters, 20 to 300 galaxies, 17 features; scatter 0.023 against MLP 0.026 | Table 2 |
| LDA-3k recall@10 | DeepSets 6.04, NN-max 5.30, w2v Near 4.80 | Table 3 |
| COCO-Tag recall@10 | DeepSets 31.4, word2vec baseline 5.6 | Table 5 |
| Odd face | sets of 16 from 18,000; equivariant 75%, plain head 6.3% | Section 4.3 |
pythonimport numpy as np rng = np.random.default_rng(0) def equivariant_layer(x, G, b): # x: (M, D) G: (D, D') b: (D') -> (M, D') pooled = x.max(axis=0, keepdims=True) # (1, D) paper eq. (23), max version return np.maximum(0, b + (x - pooled) @ G) # each item keeps its own row def invariant_net(x, layers, W, c): for G, b in layers: x = equivariant_layer(x, G, b) return x.sum(axis=0) @ W + c # pool once at the end -> (out,) D, H = 3, 8 layers = [(rng.normal(size=(D, H)), rng.normal(size=H)), (rng.normal(size=(H, H)), rng.normal(size=H))] W, c = rng.normal(size=(H, 1)), rng.normal(size=1) x = rng.normal(size=(5, D)); p = rng.permutation(5) assert np.allclose(equivariant_layer(x[p], *layers[0]), equivariant_layer(x, *layers[0])[p]) # follows the items assert np.allclose(invariant_net(x[p], layers, W, c), invariant_net(x, layers, W, c)) # same answer
Read it line by line. The pooled row is subtracted from every item, so each output row depends on its own input and on the set as a whole. Nothing depends on the position of a row, so the first assert holds. The last line adds up the rows, which is why the second assert holds. This is the paper’s point-cloud and outlier recipe in a dozen lines, without the training loop.
This paper is a reading for Lecture 4, Data and Heterogeneity of MIT’s Multimodal AI course. It is the cleanest statement of one symmetry: the order of a bag does not matter. Other symmetries, such as rotation and shift, are treated by geometric deep learning and equivariance at scale.
Credit. Deep Sets was written by Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov and Alexander Smola, at Carnegie Mellon University and Amazon Web Services. It appeared at NIPS 2017, the 31st Conference on Neural Information Processing Systems, in Long Beach. This lesson re-teaches it for learning; every number is the authors’ or is marked as a toy. arXiv 1703.06114.
Now press Present or Teach and explain from memory why a sum loses nothing, how the tied layer keeps each item’s output, and what the odd-face result shows. Then go back to the shuffle at the top, press Shuffle ten times with each model, and say which part of Chapter 3 makes the difference.