Source-linked AI summary
Deep Set Prediction Networks
Yan Zhang, Jonathon Hare, Adam Prügel-Bennett
TL;DR
Set-prediction methods that ignore unordered structure can face discontinuity issues. This paper predicts sets from feature vectors by optimizing a candidate set through a set encoder. It reports better results than baselines across experiments and demonstrates point-set auto-encoding and image-object prediction.
Problem
Models that ignore the unordered structure of sets can face discontinuities because set elements may be freely permuted.
Source: §1 · p. 1Method
The model predicts a set from a feature vector by decoding through a set encoder, with gradient-based optimization of the candidate set.
Source: §1 · p. 1, §3.1 · p. 4Results
Takeaways & Limitations
On CLEVR, the approach predicts object bounding boxes and attributes from a single feature vector without complicated post-processing such as non-maximum suppression.
Source: §1 · p. 1Training takes about 75% longer on CLEVR with T = 10 because each network evaluation requires O(T) passes through the set encoder.
Source: §6 · p. 9
Abstract
from arXiv · showhide
Current approaches for predicting sets from feature vectors ignore the unordered nature of sets and suffer from discontinuity issues as a result. We propose a general model for predicting sets that properly respects the structure of sets and avoids this problem. With a single feature vector as input, we show that our model is able to auto-encode point sets, predict the set of bounding boxes of objects in an image, and predict the set of attributes of these objects.
1 Introduction
Set prediction is difficult because the elements can be freely permuted, while models that ignore this structure can encounter discontinuities. The paper proposes a model for predicting sets from feature vectors and evaluates it on point sets and image objects.
1 Introduction
- Free permutation of set elements creates n! equally good solutions, and models that ignore this structure can suffer discontinuities even on simple set-prediction tasks [30].The introduction illustrates the issue with predicting the four corners of a rotated square.Source: §1 · p. 1
- The proposed model predicts a set from a feature vector while respecting set structure, supports variable-size sets, and uses backpropagation through a set encoder.It requires only a feature vector as input, making it applicable to a wide variety of set-prediction tasks.Source: §1 · p. 1
- Experiments demonstrate set auto-encoding on MNIST and prediction of image-object bounding boxes and attributes from a single feature vector on CLEVR.The approach poses object detection as set prediction and does not require complicated post-processing such as non-maximum suppression.Source: §1 · p. 1
2 Background
Set operations and losses must account for arbitrary element ordering, but direct vector-to-set prediction with an MLP imposes an order and can produce discontinuities. The background contrasts permutation-aware set processing with ordered-output approaches.
2 Background
- Set encoders compose permutation-equivariant elementwise operations with a permutation-invariant reduction, such as summation, so the resulting feature vector is independent of element order.Applying a function to each element preserves the set's equivariant structure; summing the results is order-independent.Source: §2 · p. 2
- Because target and predicted sets have arbitrary ordering, their loss needs an assignment mechanism rather than a pointwise comparison.Such matching yields a loss that is permutation-invariant in both arguments.Source: §2 · p. 2
- Chamfer loss matches each element to its nearest neighbor, but gives distance 0 to the multisets [a, a, b] and [a, b, b].Linear assignment with pairwise losses is a more sophisticated alternative that associates each element with exactly one element in the other set.Source: §2 · p. 2
- An MLP that directly emits set elements produces an ordered representation, forcing arbitrary assignments that can become discontinuous as the target set changes.The responsibility problem arises when outputs must switch which element they predict; this is one reason MLPs struggle with set prediction [30].Source: §2 · pp. 2–3
3 Deep Set Prediction Networks
The model decodes a feature vector into a set by optimizing the set itself through a set encoder, using permutation-equivariant gradient updates to avoid the responsibility problem. The paper develops this approach from fixed-size auto-encoding to variable-size sets and general vector-to-set prediction.
3 Deep Set Prediction Networks
- The core model uses gradient descent through a set encoder to find a set that represents the input feature vector, with permutation-equivariant updates that avoid the responsibility problem.Training nests an inner loop that changes the set and an outer loop that updates encoder weights.Source: §3 · p. 3
3.1 Auto-encoding fixed-size sets
- For fixed-size auto-encoding, the decoder searches for a set whose permutation-invariant latent representation matches the encoded input, thereby reconstructing the set up to permutation.Because the neural encoder makes this optimization non-convex, the method approximates a solution with a fixed number of gradient-descent steps from an initial set.Source: §3.1 · pp. 3–4
- Variable-size sets are padded to a fixed maximum size and given mask features that are optimized with the set elements and clamped to the range 0 to 1.The passage reports that clamping performed better than a sigmoid in initial experiments, possibly because exact 0s and 1s can be recovered.Source: §3.1 · p. 4
3.2 Predicting sets from a feature vector
- For general vector-to-set prediction, where the target feature vector may come from a separate model, the outer objective adds a representation-loss term for the target set.This encourages the target set itself to have low representation loss, addressing the absence of a shared set encoder between input and decoding.Source: §3.2 · p. 4
- The outer optimization can average set losses across all inner-loop iterates to encourage fast convergence and reduce divergence with more steps.The authors also report that Huber loss made training less sensitive to hyperparameter choices when outer learning rates were inappropriate.Source: §3.2 · pp. 4–5
- Momentum slightly improved results by reducing oscillation around a solution, while explicitly including the sum of masks as a feature improved MNIST results; neither modification was used in experiments.Both changes were omitted to keep the method simple.Source: §3.2 · p. 5
4 Related work
Prior set-prediction approaches use ordered lists, domain-specific assumptions, or set-to-set mappings, while this work addresses vector-to-set prediction without requiring a set input. Related methods also differ in their use of iterative optimization, auto-encoding, and nested differentiation.
4 Related work
- MLP decoders predict ordered lists as if they were unordered sets, while some point-cloud methods assume point independence or grid-like structure [14] or.Yang et al. instead compare graphs in latent space using a permutation-invariant loss in an adversarial setting.Source: §4 · p. 5
- RNN decoders [15; 23; 25] can make set generation a sequence task by imposing a domain-informed canonical order, such as breadth-first traversal for graph nodes.Source: §4 · p. 5
- Mordatch [17] also differentiates through iterative optimization, but its demonstrations modify small 2D sets, leaving its scalability to object detection unclear.The paper contrasts its interpretable representation loss, which makes predicted sets more similar to targets, with Mordatch's learned energy function.Source: §4 · p. 5
- Zhang et al. [30] use encoder-decoder information sharing for permutation-equivariant auto-encoding, but require an encoder at inference and thus cannot directly do set prediction.Greff et al. [9] learn image representations with set-structured latent variables under task-specific assumptions; this paper targets general supervised learning tasks.Source: §4 · p. 5
- Nested optimization lets the outer training objective differentiate through the inner prediction optimization, extending ideas from introspective neural networks and structured-output optimization.Bojanowski et al. differentiate through a decoder to learn a representation rather than a prediction.Source: §4 · p. 5
- Object detection has no set input, so set-to-set methods alone cannot produce its output; vector-to-set prediction instead produces a set from a feature vector.Set-to-set methods typically preserve the input ordering and therefore do not face the responsibility problem described for set prediction.Source: §4 · pp. 5–6
5 Experiments
The experiments test set prediction on MNIST point sets and CLEVR object boxes and scene states, with predictions made from a single feature vector. Across these tasks, the model improves on baselines, including at strict box-localization thresholds.
5.1 MNIST
- MNIST sets contain 32–342 pixel coordinates, and the model’s inner optimization progressively reshapes its initial set toward the target digit.The experiment uses Chamfer loss; the model has about 140,000 parameters versus roughly 530,000 for the MLP and 470,000 for the LSTM baselines.Source: §5.1 · pp. 6–7
5 Experiments
- The model improves over two MNIST baselines, achieves much better AP95 and AP98 than bounding-box baselines, and clearly outperforms baselines on scene-state prediction.The state-prediction evaluation requires exact object properties and 3D coordinates within a distance threshold.Source: §5.2 · p. 7, §5.1 · p. 7, §5.3 · p. 9
5.2 Bounding box prediction
- The model predicts bounding boxes from one 512-dimensional image feature vector and localizes objects with high AP at strict IoU thresholds; with 10 iterations, it achieves much better AP95 and AP98 than baselines.The shown baseline has decent performance at low IoU thresholds but bad performance at high IoU thresholds.Source: §5.2 · pp. 7–8
- More inner-optimization steps improve many bounding-box results, but the strictest AP98 and AP99 metrics worsen when running beyond the 10 steps used in training.The authors describe this as overshooting linked to training with exactly 10 steps; changing the step count allows a prediction-quality versus inference-time trade-off.Source: §5.2 · p. 8
5.3 State prediction
- Scene-state prediction targets object position, shape, color, size, and material without bounding-box information, and the model outputs 18-dimensional set elements.The authors report that more steps improve lenient metrics up to 30 iterations, while at 30 iterations state-only results improve and 3D-position accuracy worsens.Source: §5.3 · pp. 8–9
6 Discussion
The model consistently outperforms baselines across experiments, spanning sets of 10 to 342 elements and element dimensions of 2d to 18d. These results come at higher computational cost, while the paper identifies rotation-invariant prediction and graph tasks as possible extensions.
6 Discussion
- The model is consistently better than baselines across experiments, covering sets of size 10 to 342 and elements from 2d to 18d.The paper attributes the results to predicting sets as sets rather than predicting a list and treating it as a set.Source: §6 · p. 9
- Each network evaluation requires O(T) set-encoder passes; on CLEVR with T = 10, training takes about 75% longer.This cost concerns the set encoder, not the input encoder; the authors suggest more efficient encoders, better initialization, or an adaptive stopping criterion for further study.Source: §6 · p. 9
- The decoding algorithm could be paired with a rotation-invariant image encoder to predict images without fixing their orientation.The authors describe this as a potentially useful inductive bias, for example for aerial images.Source: §6 · p. 9
- The authors propose extending the main idea to graph prediction, including molecular graph generation and end-to-end scene graph prediction from images.They present these as prospective applications that could inspire further work.Source: §6 · p. 9
A Proof of permutation-equivariance
The appendix defines permutation-invariant and permutation-equivariant functions, then states that the gradient of a permutation-invariant function is permutation-equivariant. Its proof uses the chain rule and the orthogonality of permutation matrices.
A Proof of permutation-equivariance
- A permutation-invariant function f and a permutation-equivariant function g are defined by conditions over permutation matrices.The excerpts identify their respective function types as f: R^(n×c) → R^d and g: R^(n×c) → R^(n×d).Source: A Proof of permutation-equivariance · p. 12
- Theorem 1 states that the gradient of a permutation-invariant function with respect to its input is permutation-equivariant.The proof is introduced as using Definition 1, the chain rule, and the orthogonality of P.Source: A Proof of permutation-equivariance · p. 12
- The definitions quantify over all permutation matrices P.The proof excerpt also identifies P's orthogonality as a property used in the argument.Source: A Proof of permutation-equivariance · p. 12
B Details
The appendix reports choices for inner optimization and training, alongside baseline decoder configurations. It notes a training instability related to λ and the effect of reducing it.
B Details
- The inner-loop length T = 10 was selected after appearing sufficient for good MNIST solutions, then retained for supervised CLEVR experiments.The authors chose η in initial experiments by increasing it until the output set visibly changed between inner-optimization steps with a randomly initialized set encoder.Source: B Details · p. 12
- The supervised experiments often diverged with large training spikes at λ = 1; reducing λ eliminated most of the issue, while values much below 0.1 converged worse.The authors suggest the degradation at very small λ may reflect the issue associated with omitting the Lrepr(Y, z) term from the outer loss.Source: B Details · p. 12
- Experiments used Adam with default momentum values, batch size 32 for outer optimization, and one 1080 Ti GPU per experiment.The only tuned hyperparameter was the outer-optimization learning rate.Source: B Details · p. 12
- The MLP decoder baseline uses three layers, with 256 neurons for MNIST or 512 for CLEVR in its first two layers and task-specific output channels in the third.The LSTM baseline projects the latent vector to 256 or 512 dimensions for its initial cell state, runs for the maximum set size, and linearly transforms each step's output.Source: B Details · p. 12
B.1 MNIST
The MNIST appendix specifies the training schedule and network size, the chosen FSPool learning rate, and a mask adjustment used for baseline training.
B.1 MNIST
- The model and baseline were trained for 100 epochs with three-layer MLPs of 256, 256, and 64 neurons.The passage begins to describe fixed-size padding but does not specify the complete procedure.Source: §B.1 · p. 12
- FSPool used 20 pieces and learning rate 0.01; none of the other tried baseline learning rates performed significantly better than the selected one.The tested rates ranged from 1.0 to 0.00001.Source: §B.1 · p. 13
- Baselines were trained to predict x, y, and mask values, and adding 1 to the predicted mask was crucial for good results.Without the adjustment, many baseline outputs became stuck predicting the (0, 0, 0) point and were too sparse.Source: §B.1 · p. 13
B.2 CLEVR
CLEVR experiments predict bounding boxes and scene states from images using a single image feature vector, with a shared training setup for both tasks.
B.2 CLEVR
- The model and baselines are trained for 100 epochs on CLEVR and evaluated on the validation set because test-set scene ground truth is unavailable.Images are resized to 128×128, and the image encoder is a non-pretrained ResNet34.Source: §B.2 · p. 13
- For both tasks, the image encoder feeds a two-layer Relation Network with FSPool as the set encoder, using 512 neurons per layer.The learning rate is 0.0003 for bounding-box and state prediction; other hyperparameters match MNIST.Source: §B.2 · p. 13
- The CLEVR experiments use Hungarian loss, and include the mask target for both the baseline and proposed model for consistency.Source: §B.2 · p. 13
C Fixed results
After correcting the reported CLEVR issues, the model still beats the baselines; fixing intermediate-set loss has different effects on bounding-box and state prediction.
C Fixed results
- 66.8 versus 57.0 for the best result on AP0.5: fixing the set-loss bug improves almost all state-prediction results.Running more iterations then yields strict improvements without worsening any metric.Source: C Fixed results · p. 13
- With the set-loss bug fixed, bounding-box results tend to be worse than when loss is computed only on the last prediction.The corrected evaluation and intermediate-set-loss variants are reported in Tables 4 and 5; their AP is measured across IoU thresholds, with higher values better.Source: C Fixed results · p. 13, Table 4 · p. 14, Table 5 · p. 14
- Table 6 reports state-prediction AP across distance thresholds, including AP∞, which evaluates attribute correctness regardless of 3D position.The corrected CLEVR results also address the omitted intermediate-set loss computation.Source: C Fixed results · p. 13, Table 6 · p. 14
D Additional outputs
Additional outputs illustrate prediction progressions on MNIST and CLEVR, including scene-state predictions at successive iterations.
D Additional outputs
- Figures 3 and 4 show the set-prediction algorithm's progression on MNIST and CLEVR bounding boxes, respectively.Source: Figure 3 · p. 15, Figure 4 · p. 16
- In Table 7, objects are sorted by x coordinate, and red text marks incorrect attributes; this sorting can misalign the red entries.Source: Table 7 · p. 17
- The scene-state examples compare predictions at iterations 5, 10, and 20 with the true set and a baseline.Source: D Additional outputs · p. 17