ST456 Deep Learning
Assessment 1 background material
Set functions
Milan Vojnovic
https://github.com/lse-st456/lectures2022
Permutation invariant functions
• A function : !×# → is said to be permutation invariant if for every =, … , & ∈ !×# and ' = (! , … , (" & where is an arbitrary
permutation of 1,… ,, it holds ' =
• In other words, the output of the function does not change (is invariant) by
changing the order of values (permuting) of different coordinates of the input
• Examples of permutation invariant functions for = 1:
• Statistics queries, e.g. count, max, min, mean, median, any quantile value
• p-norm: = ) = * ) +⋯+ ! ) */)
• A nonlinear transformation of sum: = (* +⋯+ !)
2
Set functions
• A function is said to be a set function if it maps every set ⊆ , for some
ground set of values , to a real number ()
• Set functions are permutation invariant
• Examples of set functions
• Note that each element of a set may be a vector 3
Range queries Valuation functions

value of ?
Sum decomposable functions
• Set functions can be represented by the class of sum-decomposable functions
• A set function is said to be sum-decomposable via if = ∑∈() for all ⊆
where : → and : → are some functions
• Function is said to be continuously sum-decomposable via if it is sum-
decomposable with and being some continuous functions
• We will refer to as a latent space and dimension of as latent dimension
4
Set and sum-decomposable functions
• Thm 1: Any set function defined on subsets of a countable set is permutation
invariant if, and only if, it is sum-decomposable via
• Thm 2: Any continuous function : ! → is permutation invariant if, and only
if, it is continuously sum-decomposable via !
• Thm 3: Any continuous function : 0! → is permutation invariant if, and only
if, it is continuously decomposable via !
Note: 0! denotes the set of real vectors of dimension ≤
5
Learning set functions
• Functions and are neural networks
• For example, we may take
• to be a feedforward neural network
• to be a feedforward neural network
• We refer to the entire network as a , -sum-decomposition network
6
! "


({!, … , "})
+
⋯


Permutation equivariant functions
• Let : !×# → !×#', and for every = *, … , ! & ∈ !×#, we write = * ,… , ! & ∈ !×#'
• Function is said to be permutation-equivariant if for every = *, … , ! &
and ' = (! , … , (" & where is an arbitrary permutation of 1,… ,, it holds ' = (! ,… , ("() &
• In other words, changing the order of inputs *, … , ! to function according to
an arbitrary permutation, changes the output of only in changing the order of
the outputs according to the same permutation
7
Illustration
8

* < =
* < =

= * <
= * <
Examples
• Feature selection: input is a feature vector, the output is a vector with 0 or 1
valued coordinates, with > = 1 if feature is selected, and > = 0 otherwise
• Choice functions: input is a set of items, the output is a vector with 0 or 1 valued
coordinates, with > = 1 if item is chosen, and > = 0 otherwise
• For example, exactly one item is chosen
• Ranking functions: input is set of feature vectors *, … , ! representing some
items, and the output is a ranking of items with > denoting the rank of item
9
Affine equivariant transformations
• Let : ! → ! be an affine transformation, i.e. = + for some ∈ !×! and ∈ !
• Then, is a permutation equivariant if, and only if, = + #!∑$%#! $ +
for some real scalar parameters , , and (Exercise: show this)
• In general, an affine transformation : !×& → !×&' is permutation equivariant if, and
only if, = + 1( + (
where ∈ &×&', ∈ &×&', and ∈ &' are parameters
10
Permutation equivariant neural networks
• An equivariant neural network is a network with equivariant layers, i.e.
= ) ∘ ∘ ⋯ ∘ ∘ #
where is some activation function, and #, … , ) are equivariant affine
transformations * = * + 1(* + *(
where * ∈ &#$%×&#, * ∈ &#$%×&#, and * ∈ &# are parameters
• Note: ∘ *() means applying to each element of the matrix *()
11
!
&'!
&
()

⋮
References
• N. Sego and Y. Lipman. On universal equivariant set networks. In ICLR 2020
• E. Wagstaff, F. Fuchs, M. Engelcke, I. Posner, and M. A. Osborne, On the
limitations of representing functions on sets, ICML 2019
• M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Poczos, R. Salakhutdinov, and A. J. Smola,
Deep sets, NeurIPS 2017
12
Solution for the exercise
• We have = + , where ∈ !×! and ∈ ! are parameters
• Let and ′ be equal except for swapping the values of elements and , for some
arbitrarily fixed , ∈ {1, … ,} such that ≠
• Let = () and ' = (')
• The following three facts follow from permutation equivariance:
• For every ∈ 1,… , ∖ {, }, it holds * = ′* which is equivalent to *,$$ +*,,, = *,$, +*,,$, from which it follows that all non-diagonal elements of
must be identical, say of value
• It holds $ = ′,, i.e. $,$$ +$,,, = ,,,$ +,,$,, from which it follows that all diagonal elements of must be identical, say of value
• All the elements of are identical, say of value
• It follows that = − + ∑$%#! $ +
which corresponds to the claim by using the reparametrization = − and =
13