# What's the difference between a Permutation and a Perturbation?

I frequently come across the terms Permutation and Perturbation within the field of explainable AI.

I understand that both terms refer to methods that make changes to a sample's features. However, I'm not certain of the difference between the two.

From mathematics, a permutation is a rearrangement of elements in a set. This makes me think permutation methods draw their changes from other samples in the dataset.

From physics, a perturbation is a minor change to a model that disturbs its usual output. This makes me think perturbation methods can make any change to the sample regardless of what values are held in other samples.

If that's true then permutation methods would be special cases of perturbation methods. Have I got this right, or is there more to the distinction?

Example situation

To avoid confusion, consider the example of a single sample, which is part of a highly localised dataset.

The high locality of the dataset implies there are many other samples nearby. Permutation will therefore produce samples close to the single sample. Similarly, perturbing the single sample will produce multiple samples close to the dataset. In this situation it's possible the two methods would produce overlapping samples, the only difference being the permutation samples are more restricted than the perturbation samples.

In the above example, wouldn't that make permutation a special case of perturbation?

Related

• Conceptually, these are apples and oranges? When I think of a perturbation, I think of adding some small $\epsilon$, a tiny push. Perturbations are often used to avoid unstable, balancing on a knife edge equilibria. A permutation on the other hand is quite different: it's generally a sequence constructed from some set. A permutation uses the same components but orders them in a completely different way while a perturbation moves you some small amount? Feb 23 at 16:33
• @MatthewGunn I've updated the question to include an example of what I mean. Please let me know if the purpose of the question is more clear to you now/ if it means something different to you now. Feb 23 at 17:22

There may be a deeper connection between the two, I'll speak from a perspective of graduate level applied math/physics.

If that's true then permutation methods would be special cases of perturbation methods. Have I got this right, or is there more to the distinction?

No, I don't think so. Permutations are mappings from a finite set onto itself. In that way, a permutation can be like a function.

In english, to perturb something is "to an influence tending to alter its normal or regular state or path" or maybe "to unsettle something". This aligns fairly closely to applications in physics/applied math where we take a dynamical system and perturb the solution to understand the dynamics near fixed points. At least in physics, perturbations can be conceived as functions I suppose, but its more to understand how some other function or system behaves near some point of interest.

• In mathematics, permutations are merely bijections between a set and itself. The set needn't be finite (although that's where almost all the interest lies, because this is fundamentally a combinatorial concept). In physics perturbations usually are represented as modifications to functions, often as terms in a power series expansion or spherical harmonics expansion. That's what Feynman diagrams represent, for instance. What do permutations and perturbations have in common? The initial "p" and lots of letters is about it ;-).
– whuber
Feb 23 at 15:07
• I agree with your outside-of-machine-learning definitions, I gave similar ones myself. But I'm talking about what they mean in statistics and more specifically machine learning. With a sufficiently dense set of samples, it seems to me that a permutation of a feature in a sample is indistinguishable from a perturbation of the same feature. The only difference is the permutation's limited selections. Feb 23 at 15:09
• @Connor a permuted variable will maintain the same marginal distribution as the original one, while joint distributions get altered as well. For a perturbed one that's not the case Feb 23 at 15:58
• @Firebug Okay, thank you, that is a big difference statistically. From the perspective of how they choose samples, is it fair to say that, because the samples within the permutation's distribution are contained within the perturbation's distribution, the permutation method is a special case of the perturbation method that preserves the marginal distribution? Or does locality come into play? For example, would we say that perturbation is a distribution centred around the sample, whereas the permutation's distribution is unchanged. Feb 23 at 16:16