1:06

Now, this is an important topic in information retrieval, in database

Â management, we just won't have time to talk about it.

Â But we know that for any reasonably popular search terms, there will be many

Â relevant webpages. And then, what matters in deciding which

Â webpage will show up on page one of the search result often boils down to the

Â difference in the importance score of this eventually composite of two scores.

Â So, it is the important score determined by the connectivity pattern of the web

Â page graph that will often determine the final ranking of the top, say, ten or 50

Â or so web pages. And before we can go further, we also need

Â to talk a little bit about a notation and operation of linear algebra objects.

Â Now, I know that some of you may not have taken linear algebra, some of you may have

Â forgotten about it. In 2013, May, we will have a summer

Â course, a version for this very course where we will have no need for any linear

Â algebra terminology. It is possible to talk about everything we

Â are going to talk about without using the language of linear algebra.

Â However, that discussion will take a much longer time because without this shorthand

Â notations, we call vector and matrices, it will be very hard to explain every step.

Â And a lot of the existing results from linear algebra concerning matrices we

Â won't be able to use. So, in interest of time, we will have to

Â then shrink the discussion to a much smaller subset of what we will be talking

Â about in this course. So, I just want to highlight that it is

Â possible to talk about these things without the machinery of linear algebra

Â which we will indeed be doing in May 2013. But, in this version of the course, we

Â will be using linear algebra. It is a very useful shorthand notation

Â plus a powerful set of machinery that will allow us to accelerate the discussion.

Â Now, I'll try to make this as non linear algebraic as possible, but at some point,

Â we will have to do a little bit of that kind of math, okay?

Â So, if you need to tune out feel free. But, you may still be able to get some of

Â the interesting ideas even though some mathematical operations may be beyond your

Â understanding at this point. So, we've been using vector quad-quad law,

Â right? This vector, pi is a vector.

Â And by convention, a vector is a stacked-up column, okay?

Â Pi one, pi two, dot, dot, dot, pi n, say, pi 100.

Â What's a matrix? A matrix is really, in general, an object

Â with say, n rows and m columns. So, we can think of that as many vectors

Â arranged in parallel, or we can think of that as many rows stacked up, okay?

Â Either way. Let's say, we've got a matrix A that we

Â can denote this matrix A's ij-th at entry as A sub ij, okay?

Â In all of the material that we will be talking about this is just a real number.

Â It could be positive, it could be negative, in today's lecture it is never

Â negative. And, sometimes we use a little arrow on

Â top of a big letter to represent that it is a matrix.

Â A matrix multiplying a vector is a funny operation.

Â Say, say if matrix A, okay? Multiplies a vector x.

Â Say, matrix A is two by two. Say, it is one, three, four, two, okay?

Â And, vector x is just x1, x2. What you get is the following, okay?

Â First of all, the matrix is two by two. The vector is two by one.

Â So, what you get is a two by one, two by one vector.

Â The first entry is the inner product of the first row vector of the matrix and

Â this vector x. So, that is x1 plus three times x2.

Â One times x1, three times x2. The second entry of the vector is the

Â second row of matrix eight times the same vector x.

Â So, we have four times x1 plus two times x2, okay?

Â So, this is the basics of matrix multiplication.

Â Now, somehow in this lecture only, because of the research communities convention of

Â writing these quantities, they actually, instead of writing a matrix multiplying a

Â vector, they write it as a vector multiplied by a matrix.

Â Now, you may say, this doesn't even make sense cuz the vector is, let's say, you

Â know, two by one. The matrix is two by two.

Â You can't multiply two by one on the right by two by two.

Â Indeed, that's true. So, what we need to do is to flip this

Â vector into a row vector. For example, in this case will be x1, x2.

Â This is one by two row vector times the matrix which is one, three, four two,

Â that's matrix A. Then, it's okay cuz x transpose with this

Â big T on top is flipping the column vector into a row vector.

Â And now, you have one by two object timea two by two object and that makes sense

Â because this is two and this is two, the dimensionalities actually match.

Â So, in today's lecture, we'll be multiplying the vector pi on the right.

Â So, we have to write as pi transpose multiplied by different matrices on the

Â right. This is just an, perhaps unfortunate

Â convention of the notation in this specific research community.

Â So, we talked about matrix multiplication, right?

Â And, now, think about the following. Suppose I've got a vector pi here and

Â making it transpose, so it is a row vector, and multiplied on the right by

Â some matrix A. Suppose after being multiplied by this

Â matrix A, what you get is actually some constant, say half, times the same row

Â vector, pi transpose. Then, in that case we'll say, this vector

Â pi transpose is an Eigen vector. Means that, it maps back to itself

Â corresponding to this matrix A, okay? It might be a scaled version of itself,

Â every entry in the vector is scaled by some number.

Â And this scaling factor is called the Corresponding Eigenvalue.

Â In today's lecture, we'll be constructing three different matrices.

Â Start from the simplest one based on our current intuition and then point out why

Â that doesn't suffice, and then suggest an enhancement, that's why we're going to go

Â through a sequence of three matrices. And the final product is a matrix, what we

Â call the Google matrix G, that captures the connectivity pattern of these webpages

Â on the web. And what we'll see that this matrix G is

Â the so-called non- negative matrix. Meaning that, each entry in G, G sub ij,

Â the i-th row and j-th column entry of this matrix G.

Â For all the i's and all the i's, meaning, every entry in this matrix G must be a

Â non-negative number. It could be zero, but can't be negative.

Â And it turns out that there's a whole branch of mathematics in linear algebra

Â that studies non-negative matrices, with many properties, okay?

Â And that's often called Perron?Frobenius Theory of non-negative matrices.

Â One of these results says that there will be largest eigenvalue which is exactly

Â what? In other words, we can find an eigenvector

Â associated with this eigenvalue for a given matrix, say A, such that pi

Â transpose multiplied on the right by A returns nothing but the same vector pi

Â transpose. Why you can also write down this one in

Â front of it. It's okay.

Â That is the eigenvalue, okay? Now, you may say why are we even going

Â through all these matrix multiplication, and eigenvector, and eigenvalues for

Â non-negative matrices? What has this got to do with Google's

Â webpage ranking? As we will see in the next 30 minute or

Â so, that the ranking is determined by the important score vector pi.

Â And pi really is nothing but the eigenvector associated with eigenvalue of

Â one of a matrix, this Google matrix. Okay, instead of writing a generic in

Â matrix A let's write the Google matrix G. In other words, will we go through a

Â sequence of steps to properly define matrix G such that the ranking, important

Â score, pi vector, can be computed as the dominant eigenvector.

Â The eigenvector associated with the largest eigenvalue, which happens to be

Â one, of this matrix G. And from this pi, we can then compute, we

Â can then order that web pages to be displayed.

Â So, that's the game plan for the rest of the lecture.

Â And I would start with nothing but our same small example.

Â Nodes one, two, three, four with six directed lengths.

Â Now, we already know the answer, but we're going to now derive that answer using a

Â matrix notation. And in the rest of this course, we will

Â see quite a few other matrices, especially around Lecture eight.

Â All right, so the very first matrix we'll construct to represent this graph is a

Â matrix we denote by H, okay? Before we define the ij-th entry of a

Â generic matrix H for any general hyperlink to webpage graph, let's just look at this

Â specific example. I'm going to define the corresponding

Â matrix H which is four by four cuz there are four nodes as the following.

Â Look at node number one, that will give me the first row of this matrix.

Â Number one is pointing to number three and no one else.

Â So, I want to capture that information. So, one doesn't point to, back to self,

Â one does not point to node number two. Let me just label these columns and the

Â rows. But, it does point to node number three.

Â It does not point to node number four. See, just by writing down zeros and ones

Â in this row, I am encoding, representing the graph, at least part of the graph,

Â okay? What happens with node one's outgoing

Â links? Now, you may remember, we also need one to

Â normalize by the number of outgoing links was already captured here.

Â There's only one nonzero entry here so the number of outgoing links is one.

Â Now, we could write one divided by one, which is one, okay?

Â That's fine. What about node number two?

Â By, by symmetry it's actually the same as load number one so, zero, zero, one over

Â one, zero. This one is an indicator to indicate that,

Â hey, there is a link from node two to node three.

Â This one is a counting variable. It says, I count there is only one link

Â coming out of node two pointing to some other node.

Â So, actually, the function of this one is not the same as the one in the

Â denominator. What about node number three?

Â Y only points to four so you know the answer is zero, zero, zero, and a one,

Â divide by one. What about node number four?

Â Now, this gets more interesting. Four points to the other three nodes,

Â except itself, so this is zero. And so, you can see the diagonal of this

Â matrix zero, because no node points back to itself, but points to everyone else for

Â node four, so we'll have to write out one, one, one.

Â Now, we can't just write it as such but to make the computation easier to carry out,

Â we're going to incorporate this normalisation right within the definition

Â of this matrix H. We'll say, since there are three outgoing

Â links, let's represent the normalization by dividing each entry with three.

Â So, we've got one over three, one over three, one over three.

Â Now, you can see immediately that every row of this matrix H sum up one, okay?

Â Well, this is by definition by design of this matrix H, we constructed it such that

Â it sum up to one, unless this node points to no other webpages.

Â We'll come back to that in the next module of the lecture video, okay?

Â For this graph, we are fine, okay? So, you may have a lot of zeros, which is

Â actually the real case because the real web is [unknown].

Â And then, you have non-zero entries, which are actually identical.

Â They are basically all just one divided by the number of outgoing links.

Â And then, of course, obviously they will sum up to one per row.

Â This is how we construct this matrix H. You say, what's the point?

Â I mean, I can see you're capturing the connectivity pattern of the graph

Â algebraically in a bunch of numbers in a matrix.

Â But, why? Why would you want to do that?

Â Well, because, this will facilitate, accelerate our discussion.

Â For example, now when I say, I want to write down the relationship of these nodes

Â important scores, for example, okay? Pi three equals pi one plus pi two plus pi

Â four, okay? Over three, because pi four is split

Â across three ways. I can write this down by staring at the

Â graph. But, of course, when the graph becomes

Â big, for a computer to stare at it is actually staring at an algebraic

Â representation of the graph, okay? That gives you everything you need to know

Â about the graph. And as you can see, what's happening is

Â the following. Just look at this column, not the row.

Â I know we constructed the graph row by row, but now look at each column.

Â It says that pi three really is pi one plus pi two plus pi four times one over

Â three. In other words, if I give you a row

Â vector, pi one, pi two, pi three, pi four and I ask you to multiply with the third

Â column, column of this matrix, which is one, one, zero, one over three.

Â This is what you get, right? Pi one plus pi two plus pi four over

Â three. Aha.

Â If that's the case, then actually, in order to compute these pis, all I need to

Â do is to multiply this row vector on the right by the corresponding column of this

Â matrix H. So, in general, what we can do is to say,

Â