What does "permutation invariant" mean in the context of neural networks doing image recognition?

I have seen a term "permutation invariant" version of the MNIST digit recognition task. What does it mean?

In this context this refers to the fact that the model does not assume any spatial relationships between the features. E.g. for multilayer perceptron, you can permute the pixels and the performance would be the same. This is not the case for convolutional networks, which assume neighbourhood relations.

• yes, that's the confusing part. Isn't it there should be spatial relationship in classifying digits? Oct 15 '14 at 22:41
• MNIST is widely used as a benchmark (or sanity check) in neural networks. If your model can get < 1% error on permutation invariant MNIST, you are on to something. Oct 16 '14 at 6:08
• Yes, I mean isn't there spatial relationship in digits as well? If you permute the digit pixels, it will change the pixels order, which essentially affects the performance!? Oct 16 '14 at 6:45
• Only if the model assumes so. mlps don't, convnets do. That's why comparing a convnet to an mlp on mnist is somewhat unfair. Oct 16 '14 at 7:41
• I see! So, on mnist dataset, does mlps perform better or convnet? Oct 16 '14 at 17:24

A function $f$ of a vector argument $x=(x_1, \dots,x_n)$ is permutation invariant if the value of $f$ do not change if we permute the components of $x$, that is, for instance, when $n=3$: $$f((x_1, x_2, x_3))=f((x_2, x_1,x_3))=f((x_3,x_1,x_2))$$ and so on.

• This answer is a little misleading, because the in machine learning the learning algorithm is often permutation invariant, while the function it returns is not. Sep 11 '18 at 19:48
• @bayerj: That's an interesting piece of information, but I cannot see that it makes the definition I have given misleading, it is a correct definition, but maybe not a complete answer in this context. Sep 11 '18 at 20:06
• You are right, the definition is correct. But it is not applicable in the way you write it down. In the context of permutation invariant MNIST, which the OP was asking about, functions of the form you write down do not occur. Sep 15 '18 at 20:37
• @bayerj Would you please explain more about your confusion? From my part, this explanation clear my confusion. But I would like to discuss about yours. Nov 29 '21 at 6:40