PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Sets

Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, Alexander Smola

arXiv:1703.06114v3cs.LGstat.ML

TL;DR

Machine learning models for permutation-invariant sets are not straightforward with conventional fixed-dimensional architectures. DeepSets characterizes invariant set functions and uses that structure to build a set-processing network, which performs competitively across diverse tasks and domains.

  • Problem

    Models for variable-sized, permutation-invariant set inputs and outputs require a generic framework beyond conventional fixed-dimensional machine learning algorithms.

  • Method

    DeepSets characterizes permutation-invariant functions and processes sets by transforming each element, summing representations, and applying a shared output network.

  • Results

    DeepSets is competitive across diverse tasks and domains, including outperforming other methods comprehensively on COCO-Tag image tagging.

  • Takeaways & Limitations

    A single theoretically grounded model can operate on sets across supervised, semi-supervised, and unsupervised applications.

  • Takeaways & Limitations

    For uncountable input spaces, the exact decomposition is proved only for fixed-size sets and remains conjectural in general.

Abstract

from arXiv · show

We study the problem of designing models for machine learning tasks defined on \emph{sets}. In contrast to traditional approach of operating on fixed dimensional vectors, we consider objective functions defined on sets that are invariant to permutations. Such problems are widespread, ranging from estimation of population statistics \cite{poczos13aistats}, to anomaly detection in piezometer data of embankment dams \cite{Jung15Exploration}, to cosmology \cite{Ntampaka16Dynamical,Ravanbakhsh16ICML1}. Our main theorem characterizes the permutation invariant functions and provides a family of functions to which any permutation invariant objective function must belong. This family of functions has a special structure which enables us to design a deep network architecture that can operate on sets and which can be deployed on a variety of scenarios including both unsupervised and supervised learning tasks. We also derive the necessary and sufficient conditions for permutation equivariance in deep models. We demonstrate the applicability of our method on population statistic estimation, point cloud classification, set expansion, and outlier detection.

1 Introduction

Deep Sets addresses the challenge of learning from permutation-invariant sets rather than fixed-dimensional vectors by introducing a generic framework and the DeepSets architecture. The paper covers supervised and unsupervised set-based tasks, including population-statistic estimation and set expansion.

  • Problem: Machine-learning methods for fixed-dimensional instances do not straightforwardly extend to permutation-invariant input or output sets.The paper presents a generic framework for machine-learning tasks whose inputs and possibly outputs are sets.
  • Supervised learning: Supervised set learning predicts labels that are invariant or equivariant to permutations of set elements.Applications include population-statistic estimation in cosmology and quantum chemistry.
  • Unsupervised learning: Unsupervised set learning can infer set structure from homophily or heterophily, as in set expansion from similar query objects.The example expands {lion, tiger, leopard} with similar candidates such as jaguar or cheetah.
  • Main contributions: The paper proposes DeepSets, whose properties are shown to be necessary and sufficient for handling sets as inputs.It also extends the architecture to condition on arbitrary objects and develops a deep network for sets with possibly different sizes.

2 Permutation Invariance and Equivariance

This section formalizes permutation invariance for set-valued inputs and permutation equivariance for instance-wise outputs. It characterizes invariant set functions and gives necessary and sufficient conditions for equivariant neural-network layers, with limitations for uncountable sets.

  • Permutation invariance: Set functions must be permutation invariant, producing the same response regardless of the ordering of their input elements.This applies to supervised classification or regression with a variable number of predictors.
  • Permutation equivariance: Permutation-equivariant functions reorder their outputs in the same way that input instances are permuted.In the transductive setting, each input instance has an associated label, so the learned function maps X^M to Y^M equivariantly.
  • Invariant set-function structure: For countable input universes and real-valued outputs, a set function is permutation invariant iff it has the decomposition specified by Theorem 2.The theorem characterizes the structure of valid set functions through a mapping involving ρ.
  • Invariant set-function structure: For uncountable domains such as R, the decomposition is proved only for fixed-size sets, although exact equality is conjectured more generally.The proofs and difficulties for the uncountable case are deferred to Appendix A.
  • Permutation equivariance: A neural-network layer f_Θ(x) = σ(Θx) is permutation equivariant iff its weight matrix has the form Θ = λI + γ(11^T), with λ, γ ∈ R.The result extends to higher-dimensional inputs when λ and γ are matrices.

3 Deep Sets

Deep Sets models permutation-invariant objectives by transforming each set element, aggregating the representations, and applying learned universal approximators. The paper also characterizes permutation-equivariant layers through tied parameters and uses these layers to construct equivariant architectures.

  • Invariant model: DeepSets transforms each instance with φ, aggregates the resulting representations, and applies ρ, with universal approximators replacing both functions.Because φ and ρ can approximate arbitrary polynomials, learning these approximators preserves the intended invariant-function structure.
  • Equivariant model: A neural layer is permutation equivariant if and only if its parameters have tied off-diagonal elements and equal diagonal elements, Θ = λI + γ (11T).This is the necessary and sufficient parameter-sharing form identified from Lemma 3.
  • Equivariant model: A practical equivariant variation uses maxpooling: f(x) .= σ (λIx + γ maxpool(x)1).Maxpooling over set elements is commutative, and when λ = γ the nonlinearity input is max-normalized.
  • Equivariant model: Stacking permutation-equivariant layers yields DeepSets because composition preserves permutation equivariance.The maxpooling variation performs better in some applications.
  • Contributions: The paper highlights three contributions: universal permutation-invariance characterization, necessary-and-sufficient equivariant parameter sharing, and novel application settings.These contributions are presented as the central advances relative to related work.

4 Applications and Empirical Results

DeepSets is evaluated across supervised, unsupervised, and permutation-equivariant tasks, including statistics estimation, digit summation, point-cloud classification, galaxy red-shift regression, outlier detection, set expansion, and image tagging. The experiments show strong generalization and competitive retrieval or tagging performance, while permutation equivariance is important for one image-based baseline.

  • Applications: DeepSets covers supervised statistics estimation, digit summation, point-cloud classification, and clustered regression, plus equivariant outlier detection and unsupervised set expansion and image tagging.These applications span population statistics, sum prediction, object recognition, cosmological regression, anomaly detection, concept retrieval, and image tagging.
  • Population statistics: DeepSets learns Gaussian entropy and mutual information without being given information about Gaussianity.The experiment uses rotated and correlated Gaussian sample sets with varying set sizes.
  • Digit summation: DeepSets generalize much better than LSTM and GRU when models trained on sets of length 10 are tested on examples of length up to 100.For image inputs, the best single-digit classification error is around p = 0.01, while the evaluation measures exact equality after rounding.
  • Point-cloud classification: DeepSets directly classifies ModelNet40 point clouds containing 100, 1000, or 5000 sampled 3D particles across 40 object classes.The dataset includes 9,843 training and 2,468 test instances.
  • Set expansion: DeepSets performs set expansion by inferring a coherent concept from query terms and retrieving suitable completions without restricting data to a particular exponential family.The method generalizes the Bayesian Set algorithm’s set-completion setting.
  • Image tagging: DeepSets’ image-tagging recall beats the best approach by 2% on ESPgame, while its performance is comparable to the best approaches on all metrics except precision.The model retrieves relevant tags omitted from ground-truth lists because annotations are limited to five tags.

5 Summary … A.1 Countable Case

DeepSets combines theory of permutation-invariant and equivariant set functions with experiments across several domains. For countable domains, permutation invariance is characterized exactly by a decomposition through functions ρ and φ.

  • 5 Summary: DeepSets demonstrates generalization across several domains using extensive qualitative and quantitative experiments.The paper also reports that DeepSets outperforms intuitive deep networks lacking theoretical backing.
  • Appendix: Deep Sets: DeepSets outperforms other intuitive deep networks that are not backed by theory.The comparison is reported for Sec. 4.2.1 and Sec. 4.1.2.
  • A Proofs and Discussion Related to Theorem 2: Set functions must be permutation invariant, so their outputs cannot depend on the ordering of set elements.For any permutation π, f({x1, ..., xM}) = f({xπ(1), ..., xπ(M)}).
  • A Proofs and Discussion Related to Theorem 2: The paper claims that permutation-invariant functions have a structure of the form f(X) = ρ(...), for suitable functions ρ and φ.The following sections formally prove this structural characterization.
  • A.1 Countable Case: For countable element domains, a set function is permutation invariant if and only if it admits the stated decomposition through ρ and φ.This is Theorem 2’s necessary-and-sufficient characterization.
  • A.1 Countable Case: Sufficiency follows because the decomposed function ρ satisfies the permutation-invariance condition.The proof begins from the fact that sets have no particular order.
  • A.1 Countable Case: Necessity uses countability to map elements to natural numbers and define φ(x) = 4−c(x), yielding a unique representation for every set.A function ρ can then be constructed so that f(X) = ρ(...).

A.2 Uncountable Case

For uncountable domains with fixed set size M, continuous permutation-invariant functions admit a sum-of-power representation with a function-independent inner map, and this form is a universal approximator. The proof establishes injectivity and continuous invertibility of the embedding using Newton–Girard identities and polynomial-root continuity.

  • Scope and limitation: The uncountable extension is nontrivial because the result is proved for fixed-size domains such as [0,1]^M, rather than arbitrary-size sets over [0,1].The section represents permutation ambiguity by restricting to ordered tuples x1 ≤ x2 ≤ · · · ≤ xM.
  • Proof strategy: The proof uses φ(x) = [1, x, x^2, ..., x^M] so the sum-of-power embedding is injective after ordering inputs and has a continuous inverse.Injectivity follows through Newton–Girard identities and equality of polynomial roots; inverse continuity follows from continuous dependence of roots on coefficients.
  • Main result: On [0,1]^M, a function is continuous and permutation invariant iff it has a representation with continuous ρ: R^(M+1)→R and φ: R→R^(M+1), where φ is independent of f.The inner map is the moment feature φ(x) = [1, x, x^2, ..., x^M].
  • Main result: For fixed set size M, every continuous permutation-invariant function on a compact subset of R^d can be approximated arbitrarily closely by the ρ-sum representation.The uncountable-domain result assumes the elements lie in a compact subset of R^d and the set size is fixed.
  • Open direction: Further progress requires studying alternative topologies, with preliminary findings suggesting MMD may support a proof when representations are allowed in ℓ2 rather than finite-dimensional spaces.The section identifies this direction as requiring further exploration.

B Proof of Lemma 3

The section proves that a layer is permutation-equivariant exactly when its weight matrix commutes with every permutation matrix. This occurs precisely when all diagonal entries match and all off-diagonal entries match.

  • Equivariance condition: Permutation equivariance requires fΘ(πx) = πfΘ(x) for every permutation of the M input elements.The symmetric group SM contains all permutations of indices 1, . . . , M.
  • Lemma 3: The necessary and sufficient matrix structure ties all off-diagonal elements together and makes every diagonal element equal.Equivalently, Θ = λI + γ(11T), with λ, γ ∈ R.
  • Proof reduction: Assuming the nonlinearity is bijective, equivariance is equivalent to the matrix condition Θπ = πΘ for every permutation matrix π.The proof derives this by applying the definition of the layer and equivariance.
  • Proof of Lemma 3: Sufficiency follows because both the identity matrix and the constant matrix 11T commute with every permutation, and commutativity is preserved under linear combinations.Necessity follows by using transpositions to equate diagonal entries and products of transpositions to equate off-diagonal entries.

C More Details on the architecture … D.3 Gauss Inverse Wishart Model

The paper develops Deep Sets by summing instance representations before nonlinear processing, derives permutation-equivariant layer constraints, and relates these operations to Bayesian set models and conjugate sufficient statistics.

  • C.1 Invariant model: Deep Sets transform each instance with φ, sum the representations, and process the aggregate with ρ, yielding permutation-invariant models.The networks may be universal approximators, and conditioning on additional meta-information z is optional.
  • C.1 Invariant model: Parameter tying is theoretically necessary for deep networks whose inputs have irrelevant ordering.The result strengthens the practice of tying parameters by proving it is the only way to preserve the stated invariance.
  • C.2 Equivariant model: A pointwise nonlinear layer is permutation equivariant exactly when all off-diagonal weights are tied and all diagonal weights are equal.Its matrix has the form Θ = λI + γ11T.
  • C.2 Equivariant model: Equivariant layers combine each input with a commutative aggregate such as summation or max-pooling, and stacking them preserves equivariance before pooling yields invariance.The construction extends to multiple input-output channels and can factor parameters to improve generalization.
  • D Bayes Set [36]: Bayesian Sets scores candidate additions using exchangeable set models, seeking completions that make the aggregate set coherent regardless of element order.The score s(x|X) is the pointwise mutual information between x and X.
  • D.1 Exponential Family: Conjugate exponential-family models compute set scores in closed form using sufficient statistics φ(X) formed by summing constituent statistics.Precomputing φ(X) simplifies evaluating and maximizing over additional elements.
  • D.2 Beta-Binomial Model: The Beta-Binomial model represents binary objects through counts, then sums candidate statistics, adds β, applies a coordinatewise logarithm, and aggregates scores.Its efficiency comes from maintaining minimal statistics of X.
  • D.3 Gauss Inverse Wishart Model: The Gauss Inverse Wishart model uses φ(x) = (x, xx⊤), determinant-based conjugate computations, and a nontrivial convex function over matrix-vector aggregates.This structure motivates the general Deep Sets template, where φ performs a nonlinear, dimension-altering transformation.

E Text Concept Set Retrieval

This section studies text concept set retrieval: inferring the concept connecting a few input words and retrieving other words relevant to that concept. Examples use semantically similar latent topics from LDA datasets.

  • Task: Text concept set retrieval retrieves words from a concept or cluster given a few words from that concept.For example, {tiger, lion, cheetah} should retrieve related big-cat words such as jaguar and puma.
  • Task: The model must implicitly infer the concept connecting the input set before ranking and retrieving relevant words.The retrieval objective depends on reasoning about the shared concept represented by the given words.
  • Examples: LDA-1k examples contain latent topics whose words are semantically similar.Examples include topics involving planning, political office, folklore, and news publishing.

F Image Tagging

The image-tagging experiment conditions DeepSets on image features to predict missing tags and enrich image information. Across ESPgame, IAPRTC-12.5, and COCO-Tag, DeepSets performs comparably to leading approaches while improving recall on ESPgame.

  • Setup: DeepSets predicts a partial tag set from an image and remaining tags, then retrieves relevant tags to enrich downstream information.The model conditions DeepSets on the image and learns from partial and remaining tag sets.
  • Datasets: Experiments cover ESPgame, IAPRTC-12.5, and COCO-Tag image-tagging datasets.ESPgame and IAPRTC-12.5 each contain around 20k images; ESPgame has 268 unique tags and averages 4.6 tags per image.
  • Representations: The model uses ResNet features for images and learned word embeddings, except COCO-Tag, which bootstraps from 300-dimensional word2vec embeddings.The image features come from a publicly available 152-layer pretrained ResNet model.
  • Methods: DeepSets conditions pooled word representations on concatenated image features, using 300-dimensional word embeddings followed by two 300-unit ReLU layers.The concatenation combines image features with the set feature obtained by pooling individual element representations.
  • Results and Observations: DeepSets is comparable to the best other approaches on all ESPgame and IAPRTC-12.5 metrics except precision, and its recall beats the best approach by 2% on ESPgame.The reported metrics are mean per-tag precision, recall, F1 score, and number of tags with non-zero recall.
  • Results and Observations: Qualitative examples show relevant retrieved tags absent from ground truth alongside failures involving semantic confusion and hallucinated tags.Examples include snowboarding-versus-skiing confusion, laptop-versus-refrigerator confusion, and airplane hallucination.

G Improved Red-shift Estimation Using Clustering Information

The section treats each galaxy cluster as a set and uses permutation-equivariant layers to improve photometric red-shift estimates with clustering information. On test galaxies, the model achieves lower average scatter than both the catalogue estimates and a fully connected baseline.

  • G Improved Red-shift Estimation Using Clustering Information: Galaxy clusters are modeled as sets because each galaxy’s prediction is invariant to permutations of the cluster members.Permutation-equivariant layers estimate individual galaxy red-shifts while respecting this structure.
  • G Improved Red-shift Estimation Using Clustering Information: The task uses 17 photometric features per galaxy from a catalog of 26,111 red galaxy clusters, with cluster sizes of approximately 20–300 galaxies.Clusters therefore have varying cardinalities, represented as x ∈ R^N(c)×17.
  • G Improved Red-shift Estimation Using Clustering Information: The permutation-equivariant model reaches an average scatter of .023, compared with .025 for the original photometric estimates.The model uses four permutation-equivariant layers with output channels 128, 128, 128, and 1, trained using available spectroscopic red-shifts.
  • G Improved Red-shift Estimation Using Clustering Information: The fully connected multi-layer Perceptron reaches an average scatter of .026, showing that clustering information improves photometric red-shift estimates.This comparison uses fully connected layers with the same number of parameters and trains only on individual galaxies with spectroscopic estimates.

H Point Cloud Classification

For ModelNet40 point-cloud classification, DeepSets uses permutation-equivariant layers followed by set max-pooling and achieves strong performance with a compact representation. The model remains effective with fewer particles, while learned features progress from localized patterns to more complex surfaces.

  • Architecture: DeepSets stacks three 256-channel permutation-equivariant layers, applies set max-pooling, and classifies the resulting representation with a 256-unit dense layer and 40-way softmax.All layers use Tanh; two post-pooling dropout operations use a 50% dropout rate.
  • Classification results: The method achieves its best accuracy using a 5000 × 3 dimensional object representation, smaller than most competing methods based on voxelization or multiple views.View/angle-pooling methods can be interpreted as set-pooling because the class label is invariant to view permutations.
  • Classification results: Using only 100 particles still produces comparatively good results, whereas graph convolution is computationally more challenging and inferior in this setting.Graph convolution was also significantly slower than the set layer, limiting hyper-parameter search.
  • Classification results: With 5000 particles, the results are invariant to small changes in scale and rotation around the z-axis.This setting increases all layer widths to 512 and applies random z-axis rotations and scaling during training.
  • Learned features: The first permutation-equivariant layer learns simple localized, often cubic point-clouds at different coordinates, while the second learns more complex surface features.Features were visualized by locating 1000 particle coordinates that maximize each unit’s activation.

I Set Anomaly Detection

The set anomaly detection model uses a deep convolutional architecture that processes a fixed-size set representation before permutation-aware prediction. On CelebA, it identifies anomalous members in sets whose other members share attributes, without accessing those attributes.

  • Model architecture: The model uses nine 3 × 3 convolutional layers, max-pooling, and a final pooling step that produces an M = 16 set representation with 256 features per member.The representation is forwarded to three permutation-related layers.
  • CelebA anomaly detection: On CelebA, each set contains one outlier while all other members share at least two attributes, and the network assigns probabilities to identify the anomalous member.Training uses sets with labeled anomalous members but no access to the underlying attributes.
  • CelebA anomaly detection: The assigned member probabilities are visualized as red bars and sum to one across each set.The outlier is marked with a red frame in the CelebA examples.
Loading 1703.06114v3…