1
00:00:00,580 --> 00:00:04,670
So we start talking about our first
extension, or fix to the page rank.

2
00:00:04,670 --> 00:00:07,030
And this is called
Topic Specific PageRank.

3
00:00:07,030 --> 00:00:10,630
Sometimes it is also known
as Personalized PageRank.

4
00:00:10,630 --> 00:00:12,760
So here is basic, basically the idea.

5
00:00:12,760 --> 00:00:15,450
Let's think of, our initial goal.

6
00:00:15,450 --> 00:00:20,971
Our initial goal was to identify
important pages on the web graph.

7
00:00:20,971 --> 00:00:25,087
Now of course we don't necessarily
want to find pages that are generic in

8
00:00:25,087 --> 00:00:28,469
popularity or
that have generically high PageRank score.

9
00:00:28,469 --> 00:00:32,713
But we would want to say what are the web
pages that are popular within our

10
00:00:32,713 --> 00:00:35,380
given topic or within a domain.

11
00:00:35,380 --> 00:00:39,630
So in order to identify this our
goal is the following, right?

12
00:00:39,630 --> 00:00:43,020
What we would like to do is we
would like to evaluate web pages,

13
00:00:43,020 --> 00:00:46,810
not just according to their
overall popularity but also how

14
00:00:46,810 --> 00:00:52,030
close they are to our particular topic or
particular set of topic web pages.

15
00:00:52,030 --> 00:00:57,440
For example, how, what is their importance
in terms of the sports topic or

16
00:00:57,440 --> 00:01:00,250
what is their importance in
terms of the history topic?

17
00:01:00,250 --> 00:01:00,780
Right?

18
00:01:00,780 --> 00:01:03,670
And what is, why,
why is this interesting is because if we

19
00:01:03,670 --> 00:01:08,330
think of the web search the way, the way
PageRank was initially thought of was that

20
00:01:08,330 --> 00:01:10,780
somebody will come ask
our web search query.

21
00:01:10,780 --> 00:01:12,350
We will go identify all the,

22
00:01:12,350 --> 00:01:16,170
all the web pages that are relevant
towards that web search query.

23
00:01:16,170 --> 00:01:18,230
And then now we need to
decide how to rank or

24
00:01:18,230 --> 00:01:20,560
how to present all these
web pages to the user.

25
00:01:20,560 --> 00:01:24,980
We, we would basically take pages, simply
sort them by their page rank score, and

26
00:01:24,980 --> 00:01:29,190
show the pages that have the highest
page rank score first to the user.

27
00:01:29,190 --> 00:01:33,440
Now, of course, if you would have the
personalized page rank or topic specific

28
00:01:33,440 --> 00:01:37,180
page rank way of measuring importance of
a page, we could say, we could basically

29
00:01:37,180 --> 00:01:42,140
show to the user a given, a given ranking
depending on what, what the user wants.

30
00:01:42,140 --> 00:01:45,630
And in particular there, there can
be many queries that are ambiguous.

31
00:01:45,630 --> 00:01:49,780
For example quee,
query Trojan could have very different

32
00:01:49,780 --> 00:01:53,890
relevant pages depending on what is,
what is the topic you are interested in.

33
00:01:53,890 --> 00:01:58,600
In a sense that trojan can mean,
Trojans could mean us, a sports team.

34
00:01:58,600 --> 00:02:01,800
It can mean something different
if you are interested in history.

35
00:02:01,800 --> 00:02:06,050
Or if can mean something very different if
you're interested in Internet security.

36
00:02:06,050 --> 00:02:11,440
So the idea would be that we could want
to compute different important scores

37
00:02:11,440 --> 00:02:15,430
of different web pages based on
their relation to a given topic.

38
00:02:16,600 --> 00:02:19,100
So the question is how do we achieve this?

39
00:02:19,100 --> 00:02:22,050
And the way we will achieve this
is actually to do a small but

40
00:02:22,050 --> 00:02:25,130
very clever trick to
the PageRank formulation.

41
00:02:25,130 --> 00:02:28,170
So let's think of what we have so far.

42
00:02:28,170 --> 00:02:31,950
So far right we talked about basically
the random walker with the very

43
00:02:31,950 --> 00:02:36,740
small probability can teleport from
one page to any other page in the way.

44
00:02:36,740 --> 00:02:39,160
And we made this assumption
that this teleportation.

45
00:02:40,350 --> 00:02:42,630
Where the random walker will land.

46
00:02:42,630 --> 00:02:45,740
They land uniformly at random
at any other web page.

47
00:02:45,740 --> 00:02:50,300
So what we can do now is change this
random, random teleportation part a bit.

48
00:02:50,300 --> 00:02:50,820
Right?

49
00:02:50,820 --> 00:02:55,110
So in the original PageRank formulation we
said that the random walker can land at

50
00:02:55,110 --> 00:02:57,360
any page with equal probability.

51
00:02:57,360 --> 00:03:04,320
What we do in the personalized PageRank
world is we say we will, the random walker

52
00:03:04,320 --> 00:03:08,920
can teleport only to a topic-specific
set of relevant pages, alright?

53
00:03:08,920 --> 00:03:13,280
So whenever a random walker decides to
jump, they don't jump to any page on

54
00:03:13,280 --> 00:03:16,570
the web, but it only,
they only jump to a small subset of pages.

55
00:03:16,570 --> 00:03:19,270
And this subset of pages
is called the teleport set.

56
00:03:20,320 --> 00:03:24,800
So the idea here is in some sense that
we are biasing the random walk, right?

57
00:03:24,800 --> 00:03:25,980
So the idea is that,

58
00:03:25,980 --> 00:03:31,400
when the walker teleports, they can
only teleport into a small set of pages.

59
00:03:31,400 --> 00:03:34,590
We call it S as the teleport set, right?

60
00:03:34,590 --> 00:03:36,070
And in our case,

61
00:03:36,070 --> 00:03:40,930
we can think that set S contains only
pages that are relevant to a given topic.

62
00:03:40,930 --> 00:03:45,580
So what this will allows us to do is
basically to measure the relevance of

63
00:03:45,580 --> 00:03:51,020
of all the other webpages on the web
with regard to this given set s.

64
00:03:51,020 --> 00:03:51,580
Okay?

65
00:03:51,580 --> 00:03:57,030
So in some sense for every set s or for
every topic s for every teleport set.

66
00:03:57,030 --> 00:04:00,330
We'll now be able to compute
a different page rank vector,

67
00:04:00,330 --> 00:04:03,880
R, that is specific to that teleport set.

68
00:04:03,880 --> 00:04:07,820
so, the way we do this is actually
everything is still the same as we do,

69
00:04:07,820 --> 00:04:11,050
all we need to do is we need
to change the formulation.

70
00:04:11,050 --> 00:04:13,220
So everything still works.

71
00:04:13,220 --> 00:04:17,790
The only thing we do is now we change
the definition of our matrix A to be

72
00:04:17,790 --> 00:04:18,710
to be the following.

73
00:04:18,710 --> 00:04:23,550
If the entry i is not in the ma,
in the teleport set s.

74
00:04:23,550 --> 00:04:25,160
Then basically nothing happens.

75
00:04:25,160 --> 00:04:27,260
Everything is, everything is okay.

76
00:04:27,260 --> 00:04:30,560
Right?
But if our entry i is in the teleport set

77
00:04:30,560 --> 00:04:34,410
now the,
now we add the teleport edges in a set.

78
00:04:34,410 --> 00:04:37,450
Right?
So we have the data times MIJ plus 1

79
00:04:37,450 --> 00:04:38,120
minus beta.

80
00:04:38,120 --> 00:04:40,530
All right,
this is the random jump probability.

81
00:04:40,530 --> 00:04:42,930
Divided by S.

82
00:04:42,930 --> 00:04:45,970
Right?
So with probability 1 minus data we jump

83
00:04:45,970 --> 00:04:47,760
into one of the S pages so to,

84
00:04:47,760 --> 00:04:52,690
the probability of jumping to one of them
is 1 over the size of the teleport set.

85
00:04:52,690 --> 00:04:53,320
Okay?

86
00:04:53,320 --> 00:04:56,425
And everything still works,
A is still stochastic.

87
00:04:56,425 --> 00:04:58,501
Power iteration still works.

88
00:04:58,501 --> 00:05:02,630
Our paging algorithm still works,
everything is good.

89
00:05:02,630 --> 00:05:05,710
Just our matrix A is now a bit different.

90
00:05:05,710 --> 00:05:07,080
Of course, here for

91
00:05:07,080 --> 00:05:12,340
example, we are assuming that when a ran,
a random walker jumps into teleport set,

92
00:05:12,340 --> 00:05:16,160
they jump uniformly at random into
any of the pages in the teleport set.

93
00:05:16,160 --> 00:05:17,930
We could make things
even more interesting and

94
00:05:17,930 --> 00:05:20,740
say that there is
a probability distribution, or

95
00:05:20,740 --> 00:05:25,630
every page has a different rate of the
random walker landing at that given page.

96
00:05:26,640 --> 00:05:29,810
The idea here is basically
that we have lots and

97
00:05:29,810 --> 00:05:33,650
lots of freedom in how do
we set the teleport set S.

98
00:05:33,650 --> 00:05:37,530
For example,
when teleport set S is just a single node,

99
00:05:37,530 --> 00:05:40,030
this is called a random
walk with restarts.

100
00:05:40,030 --> 00:05:42,112
And I will talk about
this a bit more later.

101
00:05:42,112 --> 00:05:43,768
But for now, all we need to,

102
00:05:43,768 --> 00:05:47,707
we need to unders, do to understand
the personalized PageRank, or

103
00:05:47,707 --> 00:05:52,582
topic specific PageRank, is that we have
these topic specific set of pages s.

104
00:05:52,582 --> 00:05:56,282
These topic specific pages set
of pages we somehow decide we

105
00:05:56,282 --> 00:06:01,462
now compute the new version of matrix
a where the random walks, can only jump or

106
00:06:01,462 --> 00:06:03,600
teleport to the entries of s.

107
00:06:03,600 --> 00:06:06,660
And basically the same machinery
that we have developed, developed so

108
00:06:06,660 --> 00:06:10,740
far applies in the,
in the case of Topic-Specific PageRank.

109
00:06:12,100 --> 00:06:16,640
To give you an example how this works,
here is a simple graph, and

110
00:06:16,640 --> 00:06:22,690
what we will do is here I am showing
you first the transition probabilities,

111
00:06:22,690 --> 00:06:26,080
and now let's suppose that our
teleport set is a single node s.

112
00:06:26,080 --> 00:06:27,200
And our beta is 0.8.

113
00:06:27,200 --> 00:06:28,680
Okay?

114
00:06:28,680 --> 00:06:32,000
So now given, given these values.

115
00:06:32,000 --> 00:06:34,580
I, I updated the transition probabilities.

116
00:06:34,580 --> 00:06:35,890
Right?
So be,

117
00:06:35,890 --> 00:06:40,500
because with probability 0.2 a random
walker can jump out of every node.

118
00:06:40,500 --> 00:06:43,800
And then can,
they can only jump back to the node 1.

119
00:06:43,800 --> 00:06:48,910
Right, so with probability .2,
the node will land, the random walker will

120
00:06:48,910 --> 00:06:54,900
land at node one, and, with the remaining
probabilities we see the transitions.

121
00:06:54,900 --> 00:07:01,400
And now if we were, if we were and run the
power method and see where it converges

122
00:07:01,400 --> 00:07:07,310
to, here are the page rank scores of the,
of the nodes under this case.

123
00:07:07,310 --> 00:07:09,310
What we see, for example,
is that node one.

124
00:07:09,310 --> 00:07:13,270
Because the highest PageRank
score nodes three and

125
00:07:13,270 --> 00:07:16,440
four also have a very high PageRank score.

126
00:07:16,440 --> 00:07:22,680
Actually what I, what I will also show
you now is that in this particular case

127
00:07:22,680 --> 00:07:27,840
what I'm varying here for example is I'm
keeping the parameter beta the same but

128
00:07:27,840 --> 00:07:30,330
I'm varying the teleports set S right?

129
00:07:30,330 --> 00:07:33,350
When teleport set S is all
the nodes in the graph these

130
00:07:33,350 --> 00:07:35,370
are the traditional pagering scores.

131
00:07:35,370 --> 00:07:39,750
For example, you notice that as I am,
as I'm decreasing the size and

132
00:07:39,750 --> 00:07:45,040
of the teleport set and at the end the
teleport set only contains of node one.

133
00:07:45,040 --> 00:07:48,400
Notice how the PageRank
score of node one and

134
00:07:48,400 --> 00:07:53,550
the PageRank scores of all other
nodes tend to tends to decrease.

135
00:07:53,550 --> 00:07:59,250
Similarly for example, if I keep the page,
the, the teleport set S constant but

136
00:07:59,250 --> 00:08:04,500
I'm changing the random jump probability
or the teleportation probability you see.

137
00:08:04,500 --> 00:08:08,990
As the parameter beta gets smaller,
the score of the first, the node one,

138
00:08:08,990 --> 00:08:14,110
the first node, the node where the random
walker is jumping to also starts,

139
00:08:14,110 --> 00:08:15,000
starts to increase.

140
00:08:15,000 --> 00:08:18,400
Because more and more often,
the random walker jumps to node one.

141
00:08:18,400 --> 00:08:21,170
So more and more often the random
walker is at that given node.

142
00:08:22,710 --> 00:08:25,650
So, one thing that I haven't told you yet,

143
00:08:25,650 --> 00:08:29,220
is, how do we find a topic specific,
Vector S?

144
00:08:29,220 --> 00:08:30,790
All right.
How do we find a set of

145
00:08:30,790 --> 00:08:33,660
authoritative pages on a given topic?

146
00:08:33,660 --> 00:08:34,970
Actually, what we can do is,

147
00:08:34,970 --> 00:08:38,890
we can go back to the initial efforts
of how to organize wed graph.

148
00:08:38,890 --> 00:08:45,530
So, for example, DMOZ, or open directory,
is, is human created set of web pages,

149
00:08:45,530 --> 00:08:51,240
that are, that categorized into
a 16 category top level hierarchy.

150
00:08:51,240 --> 00:08:52,680
Right?
So one idea is for

151
00:08:52,680 --> 00:08:57,110
example is that we go and
use the web pages that are,

152
00:08:57,110 --> 00:09:01,830
classified into this hierarchy as
the teleport set S for every given topic.

153
00:09:01,830 --> 00:09:05,740
So for example the idea would be,
would be now the following.

154
00:09:05,740 --> 00:09:09,705
That for every webpage on the,
on the web, we have a number of different

155
00:09:09,705 --> 00:09:15,010
PageRank scores, one,
with respect to a given, to a given topic.

156
00:09:15,010 --> 00:09:18,830
So, for every page we would know what
is its quality with respect to arts?

157
00:09:18,830 --> 00:09:20,820
What is its quality with
respect to business?

158
00:09:20,820 --> 00:09:22,160
And so on.

159
00:09:22,160 --> 00:09:26,730
So now, the question is as I
mentioned before, how do we,

160
00:09:26,730 --> 00:09:30,230
how do we use this in terms of web search,
right?

161
00:09:30,230 --> 00:09:33,320
So one way how we could use
personalized page rank for

162
00:09:33,320 --> 00:09:34,960
a web search would be the following.

163
00:09:34,960 --> 00:09:40,580
Basically a user types in a query and
picks a particular topic from the menu,

164
00:09:40,580 --> 00:09:42,930
whether, or,
whether they are interested in arts or

165
00:09:42,930 --> 00:09:45,970
whether they are interested in sports,
and then

166
00:09:45,970 --> 00:09:51,930
what we can also do is we can classify
a query into a given topic, and now.

167
00:09:51,930 --> 00:09:53,940
Based on this, we can basically show,

168
00:09:53,940 --> 00:09:59,440
pick a particular topic in a particular
ranking with respect to to a given topic.

169
00:09:59,440 --> 00:10:02,770
And this is how the whole
methodology could be used in

170
00:10:02,770 --> 00:10:03,960
earlier [INAUDIBLE] settings.