Approximation of relation functions and attention mechanisms
Awni Altabaa John Lafferty
Inner products of neural network feature maps arises in a wide variety of
machine learning frameworks as a method of modeling relations between inputs.
This work studies the approximation properties of inner products of neural
networks. It is shown that the inner product of a multi-layer perceptron with
itself is a universal approximator for symmetric positive-definite relation
functions. In the case of asymmetric relation functions, it is shown that the
inner product of two different multi-layer perceptrons is a universal
approximator. In both cases, a bound is obtained on the number of neurons
required to achieve a given accuracy of approximation. In the symmetric case,
the function class can be identified with kernels of reproducing kernel Hilbert
spaces, whereas in the asymmetric case the function class can be identified
with kernels of reproducing kernel Banach spaces. Finally, these approximation
results are applied to analyzing the attention mechanism underlying
Transformers, showing that any retrieval mechanism defined by an abstract
preorder can be approximated by attention through its inner product relations.
This result uses the Debreu representation theorem in economics to represent
preference relations in terms of utility functions.