How are the intuitions and mathematics of attention mechanisms related to those of PageRank?

Question

Excuse me if you find this question too vague and not fitting to this forum and feel free to close it. The overall goal of my question is to get a better intuition of the attention concept and mechanism.

There is a high-level analogy between attention mechanisms (to be specific: in the transformer) and Google's PageRank algorithm: both claim and strive to calculate "relative importances" – of parts of a sentence or of web pages – without a thorough definition of what "importance" actually is. The meaning of "relative importance" as calculated by PageRank is intuitively clear even though it's recursive: the relative importance of a web page is the sum of the relative importances of the pages linking to it. (Graph-theoretically speaking, the relative importances are given by the eigenvector corresponding to the largest eigenvalue of the adjacency matrix.) The idea is, that when looking for web pages on a specific topic one should pay attention to the most "important" web pages (which PageRank helps to find).

I wonder if the high-level analogy can be put a bit deeper: How are – for example – the mathematics of attention mechanisms related to the mathematics of PageRank – if they are? Or is the analogy too superficial and misleading and should be forgotten?

Until now I could not develop an intuitive understanding what the relative importance of a token in a sentence is (on which attention then is focussed): important with respect to what? To other tokens or the sentence or even the "full model" as claimed here? Or isn't the goal of attention mechanisms better explained in terms of "what kinds of relations are there between the tokens in a sentence and between the tokens and the sentence as a whole, and how strong are they?" That's the background of my question.

Once again: excuse the vagueness and possibly confusion of this question, I'm aware of it.

Answer 1

Peter,

A very interesting observation indeed.

Let's narrow down from top to bottom into the cone of understanding (the depth of your understanding represents the narrower cross-section).

When you are at the highest (biggest cross-section) it's easy to confuse (or understand) the concept of the transformer as a practically infinite-edged multigraph (a graph with multiple edges b/w two nodes), unlike Page Rank which is a simple graph (graph with only one--at max bi-directional--edge b/w any two nodes). However, in thinking so, you might not be completely wrong (unless you move into the cone of understanding). Each edge b/w two nodes i and j, in our case, represents a certain probability of occurrence of j after i in a given sequence, given the condition that i is preceded by a certain specific and finite sequence of words. Change a word, and you get a new edge with a newer probability.

Let me paint a picture.

Given two sentences, "I am the King" and "I shall be the King" and analyzing the words "the" and "king" as the ith and jth nodes. One edge b/w the two will represent the probability of occurrence if "king" given the previous sequence is "I am the", whereas another might represent the probability given the previous preceding sequence is "I shall be the". But wait, it's not as easy as that, as every two adjacent words in the preceding sequence will have a practically infinite number of edges in between them and so and so. Where PageRank can work with 100s of Billions but still finite nodes with singular edges in between any two nodes, it fails due to capturing that information for an infinitely large multigraph.

Even if you were to implement a statistical method to delete unnecessary (more like need to be removed) edges (like stopwords, lower idf rated words, etc) it will still be a practically infinitely big multigraph.

Now as you start moving down the cone of understanding, you start thinking what can be better? You start thinking about latent information capturing for the need to not create a monstrous multigraph. You start thinking about Neural Networks. Now, as we did with our multigraph we can use RNNs, use LSTMs for longer sequences, and feel pretty good about it. But, at the end of the day, you know something unnecessary is happening. You are trying to force understanding of the language by the model by using Windows, which is not really how humans understand. Not just that, as is the case with our multigraph, there are unnecessary words (stop words, lower idf rated words) that are being included in our already very time complex operations. So you want to find a way to focus on important words and also keep the memory longer.

Attention was born (or basically came into grasp) given all the foundational work already matured.

Now you have reached the nadir (the bottom of the cone) or the pinnacle (the top of the cone) depending on your pessimistic or optimistic tendency respectively. Here, you understand that PageRank is actually beautiful, but very limited in its applicability, algorithm, which was developed 26 years ago.

You understand how a deep neural network understands latent space and is capable to recreate that individual edge b/w ith and jth node based on a preceding concept case-by-case, without any need to maintain a pre-trained multigraph. Here, based on 10s-100s of Billions of trained parameters (instead of 100s of billions of nodes), we capture the language understanding rather than independent connections themselves and based on a given sequence can predict the next word by essentially calculating the probabilities of all the connected words in the space.

Hopefully, this helps.