PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Limitations of Representing Functions on Sets

Edward Wagstaff, Fabian B. Fuchs, Martin Engelcke, Ingmar Posner, Michael Osborne

arXiv:1901.09006v2cs.LGcs.AIcs.NEcs.ROstat.ML

TL;DR

The paper examines whether fixed-dimensional sum-decomposition can universally represent functions on sets as set size grows. It shows that discontinuous countable-domain constructions have limited practical relevance, and proves that continuous implementations require latent dimension at least the maximum input-set size, with that size also sufficient.

  • Problem

    Prior analyses left open whether a fixed latent dimension could support universal representation as set cardinality increases, while countable-domain constructions may not reflect continuous implementations.

  • Method

    The paper analyzes sum-decomposition under continuity on uncountable domains and derives necessary and sufficient latent-dimension conditions for universal representation.

  • Results

    A latent dimension at least the maximum number of input elements is both necessary and sufficient for universal function representation.

  • Takeaways & Limitations

    Practical universal representation of set inputs requires latent dimensionality to scale with the maximum set size.

  • Takeaways & Limitations

    The countable-domain construction does not support multisets, and its infinite-set extension is therefore restricted when repeated elements are allowed.

Abstract

from arXiv · show

Recent work on the representation of functions on sets has considered the use of summation in a latent space to enforce permutation invariance. In particular, it has been conjectured that the dimension of this latent space may remain fixed as the cardinality of the sets under consideration increases. However, we demonstrate that the analysis leading to this conjecture requires mappings which are highly discontinuous and argue that this is only of limited practical use. Motivated by this observation, we prove that an implementation of this model via continuous mappings (as provided by e.g. neural networks or Gaussian processes) actually imposes a constraint on the dimensionality of the latent space. Practical universal function representation for set inputs can only be achieved with a latent dimension at least the size of the maximum number of input elements.

1. Introduction

Sum-decomposition uses summation in a latent space to make set-function models permutation-invariant, but practical universal representation requires continuity and a latent dimension tied to maximum set size.

  • Motivation: Attention-based models also perform weighted summation, making the mathematical properties of set models relevant to attention-based architectures.
  • Motivation: Set-based models address unordered inputs by enforcing permutation invariance, meaning reordering inputs does not change the output.Sum-decomposition achieves this because summation is permutation-invariant.
  • Continuity: Recent proofs based on countable domains can have limited practical value because their mappings may be discontinuous and cannot be implemented by neural networks.The paper argues that continuity on uncountable domains such as R is needed for practical usefulness.
  • Contributions: The paper establishes a necessary condition for universal function representation, rather than only sufficient conditions considered in prior work.
  • Contributions: A latent space dimension at least as large as the maximum number of input elements is both necessary and sufficient for universal function representation.The result applies to sum-decomposition implementations that universally approximate continuous functions, including neural networks and Gaussian processes.

2. Preliminaries

The preliminaries define permutation-invariant and sum-decomposable functions, distinguish countable from uncountable domains, and review contrasting representation results for the two cases.

  • Definitions: A function is sum-decomposable via latent space Z when its elementwise mapping has codomain Z and the resulting sum can be transformed into the function output.
  • Definitions: Continuous sum-decomposability requires both component mappings, ρ and φ, to be continuous.
  • Definitions: The sum-decomposition expression sums φ(x) over set elements, with care required when the set is not finite.
  • Countable case: For countable universes, every permutation-invariant function is sum-decomposable via R using an injective base-4 encoding of subsets.The construction works for any set size, including infinite sets, when repeated elements are excluded.
  • Uncountable case: For continuous permutation-invariant functions on [0,1]^M, the reviewed uncountable-domain result gives continuous sum-decomposition via R^(M+1).
  • Practical boundary: For finite subsets of [0,1] with maximum size M, the paper states that N ≥ M is necessary and N = M is sufficient for arbitrary continuous representation.Thus, the latent dimension cannot be reduced below the maximum input-set size under the stated continuity requirements.

3. The Importance of Continuity

Continuity is essential for practical function representation, but prior results on countable domains can rely on discontinuous constructions that do not extend to the uncountable domains required by neural-network approximation. The paper shows that these continuity issues constrain when sum-decomposition can provide universal representation.

  • Motivation: Continuity matters for practical computation because small input changes produce only small output changes.This is why finite-precision implementations generally remain meaningful.
  • Motivation: Prior work showed that every function on a countable set can be sum-decomposed via R, suggesting the result might extend to uncountable domains.The paper argues that this extension is not a mere formality because practical approximation concerns uncountable domains such as R^N.
  • Motivation: Continuity on Q is too weak for neural-network universal approximation, which requires continuity on R or compact subsets of R^N.A function can be continuous at every rational point yet fail to extend continuously to R.
  • Continuity of Sum-Decomposition: Theorem 3.1 shows that some functions on 2^Q require every sum-decomposition via R to use a φ discontinuous at every rational point.Thus, the countable-domain representation result does not generally yield a continuous implementation.
  • Continuity of Sum-Decomposition: More generally, for injective f or a fixed φ serving any f, φ can be continuous only at isolated points of the underlying set.The failure of continuous sum-decomposability therefore is not specific to the structure of Q.
  • Uncountable Domains: For uncountable X, some functions on 2^X are not sum-decomposable even when discontinuous decompositions are allowed.The uncountable-domain result also considers functions defined on arbitrarily large finite sets, but not infinite sets.

4. Practical Function Representation

The paper proves that continuous sum-decomposition requires latent dimension at least the maximum set size for universal representation, and illustrates how required capacity grows with input size in a median task.

  • A latent dimensionality of M is sufficient for representing all continuous permutation-invariant functions on sets of size ≤M.
  • A latent dimensionality of at least M is necessary to guarantee representation of all continuous permutation-invariant functions on sets of size ≤M.
  • For M > N, some continuous permutation-invariant functions on R^M are not continuously sum-decomposable via R^N.
  • Thus, arbitrary continuous functions on sets of size M require a sum-decomposition latent space with dimension at least M; analogous limitations apply to max-decomposition.
  • For fixed size M and variable sizes ≤M, continuous permutation-invariant functions are continuously sum-decomposable via R^M.
  • In median estimation, error decreases with latent dimension before reaching a critical point, and the critical dimension increases roughly linearly with set size while remaining below M.The experiment varies N and M while using expressive MLPs so latent dimension is the bottleneck; smaller N can suffice because the learned estimator exploits distribution-specific redundancy.

5. Related Work

Related work develops permutation-invariant models for sets, point clouds, attention, neural processes, and exchangeable sequences, while this paper analyzes sum-decomposition theoretically.

  • Prior work uses set-based models for point clouds, including hierarchical grouping and RGB–lidar object detection.
  • Attention-based models connect to set models through aggregation layers that perform weighted summation of set features.
  • Neural Processes and Conditional Neural Processes aggregate sets by summation to infer distributions from data points.
  • Work on exchangeable sequences studies joint likelihoods or models invariant under permutations, including bijective Student-t process constructions.

6. Conclusions

The paper derives theoretical limitations for finite latent spaces and concludes that continuous universal representation requires latent dimension at least the maximum input-set size.

  • The work derives theoretical limitations on representing arbitrary functions on sets through a finite latent space.
  • Continuity must be considered on uncountable domains because guarantees on countable domains do not ensure practical neural-network applicability.
  • For continuous sum-decomposition, latent dimension at least the maximum input-set size is both sufficient and necessary for universal function representation.
  • When summing over infinite sets, permutation invariance requires absolute convergence; otherwise the aggregate is set to infinity.
  • Sums over uncountable sets converge only when all but countably many elements are zero, reducing their interest to the countable case.

A.3. Remark on Theorem 2.8

The paper examines extensions of countable-domain constructions to multisets and shows that infinite multisets prevent a convergent, uniquely identifying sum representation.

  • This prime-based choice diverges for infinitely large sets.
  • No function φ can uniquely represent arbitrary multisets while guaranteeing convergence for infinitely large sets.If φ(x)=a≠0, a multiset containing infinitely many copies of x produces a divergent sum.

B.1. Theorem 3.1

Theorem 3.1 shows that some functions on subsets of Q cannot be represented through a sum-decomposition via R with a continuous element map: every such map is discontinuous at every rational point.

  • Theorem statement: Theorem 3.1 constructs functions f : 2Q → R whose every sum-decomposition via R has φ discontinuous at every q ∈ Q.The proof uses f(X) = sup(X).
  • Proof: For f(X) = sup(X), φ(q) cannot equal zero for any rational q.Otherwise the decomposition would assign the same latent contribution in cases where the supremum differs.
  • Proof: The latent sum Φ(X) must be finite for every upper-bounded X ⊂ Q.Allowing Φ(X) = ∞ for an upper-bounded set contradicts the required supremum representation.
  • Proof: For each n, only finitely many elements of an upper-bounded X can satisfy φ(x) > 1/n.Otherwise an infinite upper-bounded subset would force the latent sum to diverge.
  • Proof: Choosing q_n arbitrarily close to q with φ(q_n) < 1/n yields a sequence contradicting continuity of φ at q.The sequence satisfies the two conditions needed to establish discontinuity everywhere.

B.2. Theorem 3.2

Theorem 3.2 proves that every real-valued function on finite subsets of R has a sum-decomposition via R, using an injective latent sum constructed from a finite-sum-distinct set of continuum cardinality.

  • Theorem statement: Theorem 3.2 states that every f : R^F → R is sum-decomposable via R.The construction represents each finite set by an injective sum of element-wise codes.
  • Construction: A finite-sum-distinct set D lets the map Φ(X) = Σx∈Xφ(x) be injective on finite subsets.Choosing φ as a bijection from R to D preserves distinct finite subset sums.
  • Construction: Zorn’s Lemma is used to obtain a maximal finite-sum-distinct set Dmax.The finite-sum-distinct subsets of R are ordered by inclusion, and every chain has an upper bound.
  • Construction: Any infinite finite-sum-distinct set of cardinality κ < c is not maximal because its forbidden-element set has cardinality less than c.Thus Dmax must have cardinality c.
  • Representation: With Φ injective, choosing ρ = f ◦ Φ^-1 gives f(X) = ρ(Σx∈Xφ(x)).The decoder is defined on the image of the injective latent representation.

B.3. Theorem 3.3

Theorem 3.3 shows that uncountable input domains contain permutation-invariant functions that cannot be sum-decomposed, even when discontinuous decompositions are allowed. The section then states continuous decomposability results for bounded set sizes and contrasts them with max-decomposition limits.

  • Theorem 3.3: Theorem 3.3 states that for uncountable X, some functions f : 2X → R are not sum-decomposable, even with discontinuous ρ and φ.The proof considers f(X) = sup(X).
  • Proof: A sum over uncountably many elements can converge only when at most countably many element contributions are non-zero.For the supremum construction, every φ(x) is non-zero, ruling out sum-decomposition on uncountable subsets.
  • Proof: The countable-subset restriction still fails because X would become a countable union of finite sets.For every n, only finitely many x can satisfy φ(x) > 1/n, yet nonzero φ would require X = ⋃X_n.
  • Continuous decomposability: For fixed set size M, every continuous permutation-invariant f : R^M → R is continuously sum-decomposable via R^M.The result uses a continuous injective representation based on a sum-of-power mapping.
  • Continuous decomposability: For variable set sizes up to M, every continuous permutation-invariant f : R^≤M → R is continuously sum-decomposable via R^M.Smaller sets are padded with a constant k outside the input domain, then decoded continuously.
  • Max-decomposition: If M > N, some continuous permutation-invariant functions on R^M are not max-decomposable via R^N.The limitation holds for both continuous and discontinuous max-decompositions, including summation as a candidate operation.

C. A Continuous Function on Q

This section constructs a function Ψ that is continuous on Q but not on R by taking a pointwise limit of iteratively defined functions and choosing an irrational rescaling.

  • Construction: The function Ψ is defined as a pointwise limit of functions Ψ_n and is continuous on Q but not on R.The construction is illustrated through several iterations of Ψ_n.
  • Construction: The construction defines a sequence of functions eΨ_n on [0, 1] before taking the pointwise limit eΨ.The limit is continuous except at dyadic rationals.
  • Rescaling: The function Ψ on [0, A] is obtained by rescaling eΨ according to Ψ(x) = eΨ(x/A).Its possible discontinuities occur at points A · k · 2^-m.
  • Rescaling: Choosing irrational A makes all discontinuities irrational, so Ψ is continuous on Q.The figures use A = log(4).
  • Iteration: Each iteration splits the unit interval into 2^n even subintervals and horizontally reflects the function in every even-numbered subinterval.The midpoint of the unique half-open interval containing x determines the reflection structure.
  • Binary construction: The binary-digit convention uses the non-terminating expansion for dyadic rationals.This resolves the ambiguity caused by terminating and non-terminating binary representations.

D. Implementation Details for Illustrative Example

The illustrative experiments vary the latent dimension within a fixed fully connected architecture and evaluate performance using repeated smoothed RMSE measurements. Out-of-distribution tests show that the trained model can rely on the statistical properties of its training distributions when estimating medians.

  • Network setup: The network uses three fully connected layers before summation and two after, with 1000 hidden units and ReLU nonlinearities in each layer.The third hidden layer creates the latent space used for summation.
  • Network setup: The latent dimension N is varied across experiments to examine its influence on performance.
  • Training procedure: Training uses ADAM with learning rate 0.001, batch decay 0.99, batch size 32, and convergence at 500 batches.Samples are continuously drawn, so the experiments have no train/test split or epoch sizes.
  • Evaluation: Performance is summarized by the final exponentially smoothed RMSE, averaged over 500 random-seed runs.Critical points use the smallest latent dimension whose RMSE is below 10% above the global minimum for each set size.
  • Out-of-distribution evaluation: The model performs poorly on unlikely out-of-distribution inputs, indicating that median estimation uses information about the underlying training distributions.For an all-ones input, the output is 0.933 versus the true label 1.0; for an ordered input from 0.002 to 1.0, it outputs 0.5006 versus 0.5000.
Loading 1901.09006v2…