Modelling functions of sets, or equivalently, permutation-invariant
functions, is a long-standing challenge in machine learning. Deep Sets is a
popular method which is known to be a universal approximator for continuous set
functions. We provide a theoretical analysis of Deep Sets which shows that this
universal approximation property is only guaranteed if the model's latent space
is sufficiently high-dimensional. If the latent space is even one dimension
lower than necessary, there exist piecewise-affine functions for which Deep
Sets performs no better than a na\"ive constant baseline, as judged by
worst-case error. Deep Sets may be viewed as the most efficient incarnation of
the Janossy pooling paradigm. We identify this paradigm as encompassing most
currently popular set-learning methods. Based on this connection, we discuss
the implications of our results for set learning more broadly, and identify
some open questions on the universality of Janossy pooling in general.

研究介绍了深度集模型的理论分析，发现只有当模型的潜空间具备足够高维度时，其可以作为连续集函数的通用逼近器。同时指出深度集模型可以被看作是 Janossy 池化范例的最有效体现，阐述了其在集合学习中的广泛应用以及问题。

集合上函数的普适逼近

Universal Approximation of Functions on Sets

We consider a simple and overarching representation for permutation-invariant
functions of sequences (or multiset functions). Our approach, which we call
Janossy pooling, expresses a permutation-invariant function as the average of a
permutation-sensitive function applied to all reorderings of the input
sequence. This allows us to leverage the rich and mature literature on
permutation-sensitive functions to construct novel and flexible
permutation-invariant functions. If carried out naively, Janossy pooling can be
computationally prohibitive. To allow computational tractability, we consider
three kinds of approximations: canonical orderings of sequences, functions with
$k$-order interactions, and stochastic optimization algorithms with random
permutations. Our framework unifies a variety of existing work in the
literature, and suggests possible modeling and algorithmic extensions. We
explore a few in our experiments, which demonstrate improved performance over
current state-of-the-art methods.

本文提出了 Janossy pooling 方法，可以将置换不变函数表示为输入序列的所有重新排序应用置换敏感函数的平均值，并且通过三种近似方法实现了可计算性可控，实验结果表明该方法在置换不变函数的构建上表现出了比当前最先进的方法更好的性能。