On the Limitations of Representing Functions on Sets

Edward Wagstaff, Fabian Fuchs, Martin Engelcke, Ingmar Posner, Michael A. Osborne
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:6487-6494, 2019.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-wagstaff19a, title = {On the Limitations of Representing Functions on Sets}, author = {Wagstaff, Edward and Fuchs, Fabian and Engelcke, Martin and Posner, Ingmar and Osborne, Michael A.}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {6487--6494}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/wagstaff19a/wagstaff19a.pdf}, url = {https://proceedings.mlr.press/v97/wagstaff19a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T On the Limitations of Representing Functions on Sets %A Edward Wagstaff %A Fabian Fuchs %A Martin Engelcke %A Ingmar Posner %A Michael A. Osborne %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-wagstaff19a %I PMLR %P 6487--6494 %U https://proceedings.mlr.press/v97/wagstaff19a.html %V 97 %X 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.
APA
Wagstaff, E., Fuchs, F., Engelcke, M., Posner, I. & Osborne, M.A.. (2019). On the Limitations of Representing Functions on Sets. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:6487-6494 Available from https://proceedings.mlr.press/v97/wagstaff19a.html.

Related Material