Deep Sets

Permutation invariant functions

Permutation invariant functions of sets need to be of the form f(sum(map(g, set))), for suitable transformations f and g. The proof for this is interesting – I am yet to understand the proof for uncountable sets, but for countable, the outline of the proof is as follows:

The functional form is obviously sufficient (it is permutation invariant).

Necessity is not as trivial: we can map each element of a coutable set to a unique natural number. We can use this to encode the whole set to a unique number (using some form of binary encoding, the paper uses f' = sum(pow(4, -c(x)) for x in set X), where c(.) is the unique natural number function). We can then use a suitable f(.) to represent any function.

For uncountable sets, the paper shows that this is a special case of the Kolmogorov-Arnold representation theorem (hello!) where we only consider perm-invar functions. The (very general) outline here is to first embed the set into a higher dimensional object for which we can prove that there is a continuous map that is of the needed form.

My understanding, which is incomplete and probably horribly wrong, is that the embedding is an M+1 degree polynomial for a set with elements from a domain of size M. The set representation, E(X), is the sum of the polynomials for each element. This mapping is a homeomorphism. Then the second half of the proof is equivalent to showing that there exists a continuous map from Z (where E(X) lives) to R. The paper then gives an example of such a map: f(E inv (z)) (this feels circular to me, might have to revisit later).

Permutation equivariant functions

Permutation equivariant functions of sets need to be of the form (a*I + b*(11 T )). It is sufficient trivially: both I and 11 T both commute with permutation matrices, and hence so does their linear combination. It is necessary because (proofs are in the paper, IIRC there are proofs in the GDL book too):

  1. All diagonal elements have to be identical
  2. All off-diagonal elements have to be identical