2
$\begingroup$

In Attention, Learn to Solve Routing Problems, it was mentioned that:

but we do not use positional encoding such that the resulting node embeddings are invariant to the input order

I'm confused about this sentence. Positional encodings in the original Transformer paper are to incorporate the idea of the position of a token in the sequence. Being invariant to the input order means that there's permutation invariance - in other words, an arbitrary labeling of the nodes (you can also view this an arbitrary sequence of nodes) should not change the resulting embedding.

Does anyone know why positional encodings result in permutation invariance?

$\endgroup$

2 Answers 2

1
$\begingroup$

Positional encoding as implemented in Vaswani et al. (2017) embeds order into the inputs. Once you do that, you can permute tokens in each input while retaining a notion of order. This means the transformer is permutation invariant, but the transformer still has access to order information.

For example, a naive positional encoding of a sequence of length $n$ could be $p = [1, 2, 3, ..., n]$. If you add this positional vector to your sequence (by concatenation or summation - the paper uses summation), token $i$ will include position $p_i$, and permuting tokens will retain order information without the need for order.

$\endgroup$
1
$\begingroup$

A super late reply, but I think you probably misread the sentence. I believe they intend to say that: we do not use positional encoding because we want that the resulting node embeddings are invariant to the input order.

In other words, positional encodings impose an order on the input tokens, but the order of nodes in TSP should not matter, so they decide not to use it.

$\endgroup$

Your Answer

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

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