22
$\begingroup$

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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
32
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • 3
    $\begingroup$ yes, that's the confusing part. Isn't it there should be spatial relationship in classifying digits? $\endgroup$
    – RockTheStar
    Oct 15, 2014 at 22:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – bayerj
    Oct 16, 2014 at 6:08
  • 2
    $\begingroup$ 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!? $\endgroup$
    – RockTheStar
    Oct 16, 2014 at 6:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – bayerj
    Oct 16, 2014 at 7:41
  • 2
    $\begingroup$ I think in this context the idea is that a random permutation is generated once (and applied to all pixels) and then remains constant throughout training and evaluation. So with the permutation being constant, with enough data the model can learn the spatial relationships between the pixels even though they are permuted. The performance of a plain MLP won't be affected by the permutation, since its fully-connected layers are symmetric under any permutation anyway; but a convolutional network will suffer since the permutation will destroy the spatial structure that it assumes. $\endgroup$
    – Brent Kerby
    Jan 5, 2021 at 3:18
15
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – bayerj
    Sep 11, 2018 at 19:48
  • 1
    $\begingroup$ @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. $\endgroup$
    – kjetil b halvorsen ♦
    Sep 11, 2018 at 20:06
  • $\begingroup$ 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. $\endgroup$
    – bayerj
    Sep 15, 2018 at 20:37
  • $\begingroup$ @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. $\endgroup$
    – 4t8dds
    Nov 29, 2021 at 6:40
  • $\begingroup$ @bayerj Maybe you refer to equivariance? $\endgroup$
    – Anton
    May 30, 2022 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.