Learning from unordered tuples?

Question

EDIT: I reduced my problem to a more specific question: https://math.stackexchange.com/questions/26573/ But I am still interested in other ideas.

Let's say our data is generated by

$$Y_i = f(X_i) + \epsilon_i$$

where $X_i$ are observed vectors, and $f$ is an unknown function. We know that $f$ is invariant with respect to permutation of the elements of $X$. For example, if $X_i=[x_{i1},x_{i2},x_{i3}]$, then we have

$$ f([x_{i1},x_{i2},x_{i3}]) = f([x_{i1},x_{i3},x_{i2}]) = f([x_{i2},x_{i1},x_{i3}])=\cdots $$

Are there modified versions of linear regression, support vector machines, forests, etc. which can be used to estimate $f$? I'm specifically interested in the case when $X_i$ are eigenvalues of matrices (so they have complex-valued entries).

EDIT: A desperation move would be to make replicates of each data point with all permutations of each $X_i$ vectors and then apply standard methods, but this is clearly computationally impractical.

Answer 1

For regression models, one way would be to generate derived variables that are invariant to permutation of the labelling of the $x_i$s.

E.g. in your three-variable example, considering only polynomials of total order up to 3, such combinations would be:

• $w_1 = x_1 + x_2 + x_3$
• $w_2 = x_1x_2 + x_1x_3 + x_2x_3$
• $w_3 = x_1^2 + x_2^2 + x_3^2$
• $w_4 = x_1x_2x_3$
• $w_5 = x_1^2x_2 + x_1^2x_3 + x_2^2x_1 + x_2^2x_3 + x_3^2x_1 + x_3^2x_2$
• $w_6 = x_1^3 + x_2^3 + x_3^3$

You could then use any any form of regression that includes some function $f(a_1w_1 + a_2w_2 + \cdots + a_8w_8)$ and find values for the $a_i$s by non-linear least squares, generalized linear modelling or other methods. The combination $a_1w_1 + a_2w_2 + \cdots + a_8w_8$ fits a response surface that's a polynomial of order 3 that is symmetric in permutation of $x_1, x_2, x_3$.

Clearly there would be many more possibilities if you wished to allow functions other than polynomials such as logs, fractional powers...

(EDIT I finished this post before I saw your edit to the answer with the link to the more specific question on mathoverflow. I was started to think there must be some mathematical framework for listing all such polynomials of a given total order, but it sounds you already know more than me about the relevant area of maths!)

Answer 2

To add to onestop's response, it was confirmed on math.SE that the polynomials

$$w_1 = x_1 + \cdots + x_n$$ $$w_2 = x_1^2 + \cdots + x_n^2$$ $$\cdots$$ $$w_n = x_1^n + \cdots + x_n ^n$$

give you all the information needed to determine the original $X=(x_1, \cdots, x_n)$.

This is a neat result because it also applies to moments of a discrete distribution with uniform probabilities.

Answer 3

Deep Sets and PointNet provide two (fairly recent) examples of permutation-invariant deep learning architectures. Both these methods provided state-of-the-art results at their time of introduction and are continuous (in senses described in their papers) with respect to perturbations of the underlying sets.

The permutation-invariant Deep Sets neural architecture can be written as:

$$ F_{DS}(A) = \rho\left( \sum_{a\in A} \phi(a) \right) $$

and a (simplified) PointNet architecture can be written as:

$$ F_{PN}(A) = \rho\left( \max_{a\in A} \phi(a) \right) $$

where $\phi:\mathbb{R}^n\to\mathbb{R}^m$ creates features for each point in the set $A$ and $\rho:\mathbb{R}^m\to\mathbb{R}$ combines these features into a single real-valued output (here the $\max$ of a vector is taken to be the component-wise maximum and $\rho$ and $\phi$ are continuous). Since taking sums and max are permutation-invariant, so is the whole network.

Ideally we would choose $\rho$ and $\phi$ to be the functions that together minimize the error among all such continuous functions, but that is monstrously intractable. Instead we model $\rho$ and $\phi$ as neural networks whose joint set of parameters $\Theta$ are chosen to minimize the regression error.

---

With respect to your context and notation for $|X_i|=3$, these models look like:

$$ F_{DS}(X_i) = \rho\Big(\phi(x_{i1}) + \phi(x_{i2}) + \phi(x_{i3})\Big) $$

$$ F_{PN}(X_i) = \rho\Big( \max\big\{\phi(x_{i1}),\phi(x_{i2}),\phi(x_{i3})\big\} \Big) $$

---

Bonus: Deep Sets actually also describes a permutation-equivariant architecture as well.