So in this lecture, we'll continue our discussion on how the techs rank summariser works.
This lecture will be a continuation of the previous lecture, so make sure you've watched that first.
In particular, this lecture will go through the mechanics of how PageRank works, which can then obviously
be applied to text rank as well.
Now please note that in order to go through this subject properly, it really takes half, of course,
to a full course of time.
So this lecture is really a compressed version of what I've taught in the past.
Now, this doesn't mean I've left out any details, but it does mean that I'm going to go faster than
usual.
So after this lecture, if you still have any questions or if you need more details, please email me
on my website using the contact form.
OK, so to begin our discussion, we'll note that a random walk is an example of a Markov chain.
In fact, this is very similar to the Markov models we discussed elsewhere in this course.
Generally speaking, Markov chains are made up of a set of states.
We can then go from any state at time T to any other state at time T plus one.
According to some given set of probabilities, suppose that we have states in total.
In the case of PageRank, this means that we have M Web pages.
The probability of going from state eye at time T to state at time T plus one is written like what you
see here.
Note that these transitions follow the mark of property.
Since this probability only depends on where you were at the previous state, but not any state before
that.
Furthermore, note that we can store these probabilities in a matrix since I can be any state from one
up to M and J can be any state from one up to M..
This is an m by M matrix, which we simply denote as a bi convention.
So AJ is the probability of going from state to state J.
Note that we call a the state transition matrix.
Also note that a is independent of time, which is why it does not depend on T.
The next step is to consider how we represent the probability of being in a particular state.
We call this the state distribution, so possessive tea will be a vector of improbability values, telling
us the probability of being in any particular state at time, T noted by convention.
We think of pervasive T as a rogue vector instead of a column vector like we normally do.
Importantly, we can use this along with the Matrix to compute the state distribution at the next time
step in particular, a p of S of T plus one is simply pervasive of T multiplied by the matrix.
As an exercise, you can do a simple example yourself to prove that this works.
Now, as you recall, what we would like to do is compute the state distribution after an infinitely
long random walk that is we want to know of as of T one T is infinity.
We call this the limiting distribution.
Now, in general, this would be very hard to compute since it could take an infinite amount of steps.
In fact, there's no guarantee it will actually converge such that the limiting distribution actually
exists.
But luckily, there's a trick from linear algebra, which we can use, which not only guarantees that
this distribution does exist, but also that we won't need to take an infinite number of steps to find
it.
Let's start by recognizing one fact if we take our state transition equation, poverty of two plus one
equals press of tee times a we can simply plug in T is equal to infinity.
What we get is p of us.
Infinity equals p of s infinity times.
This is because infinity plus one is still infinity.
Now you might think.
Doesn't this simply mean a is one which is a contradiction?
And the answer is no, because we are working with matrices instead.
This is what is known as the eigenvalue problem.
As you recall, the eigenvalue problem is typically stated as eight times v equals lambda times v,
where a is a matrix V is an eigen vector in lambda is an eigenvalue.
It means that eigenvectors are special vectors such that when you multiply them by the matrix a, this
is the same as simply multiplying by scalar, which is the eigenvalue lambda.
For our problem, this simply means that Pervez Inf. is the eigenvectors, while the eigenvalue is just
one.
And recall that there's no need to discuss how we actually find eigenvalues and eigenvectors, since
that's a low level operation, included a nampai.
Now, what I just showed you was kind of a sleight of hand, as you recall, what we originally wanted
to find was the limiting distribution that is the distribution we would get if we kept multiplying by
a an infinite number of times.
What we actually found is called the stationary distribution, which is not necessarily the same.
The stationary distribution is simply a distribution that doesn't change after a transition.
So here are some questions to consider.
How do we know that the stationary distribution is the same as the limiting distribution?
Furthermore, how do we know that this distribution is unique?
And finally, how do we know that the corresponding eigenvalue is one to begin with?
The answer is called the parent for a zero.
In short, the states that if the Matrix A is a mark of matrix, also known as a stochastic matrix and
we can travel from any state to any other state with positive probability, then all the previous assumptions
we made will be true.
Now, luckily, you'll never have to prove this theorem, since it's more common to simply apply it.
So to recap, there are two conditions and all we need to do is ensure that our matrix meets these conditions.
The first condition is that a is a mark of matrix.
This simply means that each row, some still one and all these values are not negative.
This makes each row a valid probability distribution.
The second condition is that all the values in a are positive.
Normally we only have to ensure they are not negative as per condition one which allows some values
to be zero.
But if we want all our nice assumptions to hold, then we also have to ensure they are positive.
OK, so these are the two conditions.
If these conditions are true, then as mentioned, all the assumptions we made are true.
As you recall, this means that the Matrix does have an eigenvalue of one.
It means that the limiting distribution and the stationary distribution are the same.
And it means that this distribution is unique.
Furthermore, this means that it's easy to find or limiting distribution, since it simply amounts to
finding the eigen vector for which the corresponding eigenvalue is one.
Since we can do this, there is no need to multiply by a an infinite number of times.
In the case of PageRank, it's very easy to ensure that these conditions are true.
So let's discuss how we build the PageRank matrix, which will make it simpler to understand the tech's
rank matrix.
Let's consider a single row of The Matrix, some arbitrary row at index.
I now suppose that there are any links on web page I, since we want to have equal probability of going
to any web page.
We'll make the probability for each of these outgoing links to be won over in I and of course, all
the rest of the values will be zero.
So hopefully this makes sense.
We'll call this matrix.
Now we can't only use G because as you recall, although this is a mark of matrix where each row comes
to one, it does not contain only positive numbers.
Currently, since this matrix contains zeros.
It's not possible to go from any webpage to any other webpage.
Therefore, we need to apply smoothing to this matrix.
In other words, we're going to artificially insert a small probability of going to any web page in
particular, what we want to do is create a new matrix called you, which contains the same value one
over m in each position.
This would be our matrix if every page on the internet links to every other page on the internet.
The final step is to take a convex combination of both G and U.
For example, zero point one five U.
Plus zero point eighty five g.
As an exercise, you should confirm to yourself that each row of this new matrix still comes to one.
OK, so now that you know how the PageRank matrix is built, let's move on to tax rank.
As you recall, we've just computed the TFI TAF.
This gives us a tier of IDF vector for each sentence in our document.
The next step is to compute the cosine similarity between every sentence and every other sentence.
Note that there are other ways to compute the similarity between sentences.
You're encouraged to check out these other methods yourself, which are described in the text rank paper,
which you can find an extra reading dot text.
Either way, this will give us an end by a matrix, just like with PageRank.
So at position, we have the similarity between sentence, eye and sentence.
However, note that it's not possible to use this as is, since each road is not sum to one.
To fix this, we simply divide every row by some to enforce this constraint.
As with PageRank, there can still be zeros in this matrix.
And so we use the same method to smooth it by adding a small uniform probability for every pair of states.