Universal approximations of permutation invariant/equivariant functions by deep neural networks

By Akiyoshi Sannai, Yuuki Takai, Matthieu Cordonnier. 2019

76 citations recorded by the source corpus.

In this paper,we develop a theory of the relationship between permutation ($S_n$-) invariant/equivariant functions and deep neural networks. As a result, we prove an permutation invariant/equivariant version of the universal approximation theorem, i.e $S_n$-invariant/equivariant deep neural networks. The equivariant models are consist of stacking standard single-layer neural networks $Z_i:X \to Y$ for which every $Z_i$ is $S_n$-equivariant with respect to the actions of $S_n$ . The invariant models are consist of stacking equivariant models and standard single-layer neural networks $Z_i:X \to Y$ for which every $Z_i$ is $S_n$-invariant with respect to the actions of $S_n$ . These are universal approximators to $S_n$-invariant/equivariant functions. The above notation is mathematically natural generalization of the models in \cite{deepsets}. We also calculate the number of free parameters appeared in these models. As a result, the number of free parameters appeared in these models is much smaller than the one of the usual models. Hence, we conclude that although the free parameters of the invariant/equivarint models are exponentially fewer than the one of the usual models, the invariant/equivariant models can approximate the invariant/equivariant functions to arbitrary accuracy. This gives us an understanding of why the invariant/equivariant models designed in [Zaheer et al. 2018] work well.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Set2Graph: Learning Graphs From Sets (2020, background): “Several options exists (Keriven & Peyr´e, 2019; Sannai et al., 2019) although probably the simplest option is either DeepSets (Zaheer et al., 2017) or one of its variations; all were proven to be universal recently in (Segol & Lipman, 2020).”
Are Transformers universal approximators of sequence-to-sequence functions? (2019, background): “Sannai et al. (2019) consider universally approximating permutation invariant/equivariant functions using fully-connected ReLU networks.”
Universal Invariant and Equivariant Graph Neural Networks (2019, background): “Sannai et al. (2019) recently proved that equivariant NNs acting on point clouds are universal, that is, for d = 1 in our notations.”
Deep Fictitious Play for Finding Markovian Nash Equilibrium in Multi-Agent Games (2019, background): “On the hand, designing specific neural network architectures to guarantee permutation invariance/equivariance exactly has been discussed in depth in the recent literature (Zaheer et al. (2017); Zhang et al. (2018c); Sannai et al. (2019)).”
On Universal Equivariant Set Networks (2019, background): “Sannai et al. (2019) builds a universal equivariant network by taking n copies of ( n − 1) -invariant networks and combines them with a layer that is not permutation invariant in the standard (above mentioned) sense.”
Universal Equivariant Multilayer Perceptrons (2020, background): “[34] Akiyoshi Sannai, Yuuki Takai, and Matthieu Cordonnier.”