# Learning from unordered tuples?

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.

• @charles.y.zheng, I don't think the replication idea is appropriate. Your function $f$ is a function of the "order statistics" of your input $X_i$. So, why not sort the coordinates of $X_i$ and fit your $f$ that way? (Of course you're formally fitting a different function $g$ in this case, but there is a simple mapping in terms of compositions in which to define $f$ given $g$ and $X_i$.) Mar 12, 2011 at 16:56
• @cardinal: yes, but this has the effect of favoring certain functions $f$ over others. And since in the case of complex numbers, the ordering is not unique, it seems like this might not be the most desirable solution. Mar 12, 2011 at 17:15
• Sorry, I missed the comment on complex-valued entries. In the real-valued case, my previous comment stands and should not "favor" any admissible $f$ over another. Mar 12, 2011 at 17:21
• +1 for the example of how to cross-post properly and very interesting question. When do these type of problems arise? Physics? Mar 12, 2011 at 19:22
• @mpiktas: I am a newcomer to the field so I cannot give you any references. However, it is easy to imagine where the regression might come in. Suppose you measure the social networks of $n$ schools. These networks take the form of adjacency matrices $X_n$. You also know some demographic information about the schools, like average income, ethnic composition, etc. How are those covariates related to features of the graphs? And by the way, the eigenvalues capture a lot of the important properties of the network, such as average degree, connectivity, and clustering. Mar 12, 2011 at 20:29

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!)

• Apparently I know enough that I am beginning to forget some. Thanks for the reply, in any case! Mar 12, 2011 at 17:40

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.

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.