Deep Sets
This work addresses a foundational problem in machine learning for tasks involving sets, with broad implications across domains like statistics, anomaly detection, and cosmology, by providing a theoretical framework and practical architecture.
The paper tackles the problem of designing machine learning models for tasks defined on sets, where objective functions are invariant to permutations, by characterizing permutation invariant functions and proposing a deep network architecture that operates on sets. The method is demonstrated on tasks such as population statistic estimation, point cloud classification, set expansion, and outlier detection, showing applicability across various scenarios.
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.