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
