Universal approximation of functions on sets
Modelling functions of sets, or equivalently, permutation-invariant functions, is a longstanding 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 th...
| Main Authors: | , , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Journal of Machine Learning Research
2022
|
| _version_ | 1826309509196283904 |
|---|---|
| author | Wagstaff, E Fuchs, FB Engelcke, M Osborne, MA Posner, I |
| author_facet | Wagstaff, E Fuchs, FB Engelcke, M Osborne, MA Posner, I |
| author_sort | Wagstaff, E |
| collection | OXFORD |
| description | Modelling functions of sets, or equivalently, permutation-invariant functions, is a longstanding 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-afine functions for which Deep Sets performs no better than a nafive 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. |
| first_indexed | 2024-03-07T07:36:48Z |
| format | Journal article |
| id | oxford-uuid:aad96d93-d8a9-4ac4-92a3-cd7bc3e3da96 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:36:48Z |
| publishDate | 2022 |
| publisher | Journal of Machine Learning Research |
| record_format | dspace |
| spelling | oxford-uuid:aad96d93-d8a9-4ac4-92a3-cd7bc3e3da962023-03-10T14:15:48ZUniversal approximation of functions on setsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:aad96d93-d8a9-4ac4-92a3-cd7bc3e3da96EnglishSymplectic ElementsJournal of Machine Learning Research2022Wagstaff, EFuchs, FBEngelcke, MOsborne, MAPosner, IModelling functions of sets, or equivalently, permutation-invariant functions, is a longstanding 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-afine functions for which Deep Sets performs no better than a nafive 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. |
| spellingShingle | Wagstaff, E Fuchs, FB Engelcke, M Osborne, MA Posner, I Universal approximation of functions on sets |
| title | Universal approximation of functions on sets |
| title_full | Universal approximation of functions on sets |
| title_fullStr | Universal approximation of functions on sets |
| title_full_unstemmed | Universal approximation of functions on sets |
| title_short | Universal approximation of functions on sets |
| title_sort | universal approximation of functions on sets |
| work_keys_str_mv | AT wagstaffe universalapproximationoffunctionsonsets AT fuchsfb universalapproximationoffunctionsonsets AT engelckem universalapproximationoffunctionsonsets AT osbornema universalapproximationoffunctionsonsets AT posneri universalapproximationoffunctionsonsets |