Explore
For Enterprise
Join for Free
Log In

艺术与人文
商务
计算机科学
数据科学
信息技术
健康
数学和逻辑
个人发展
物理科学与工程
社会科学
语言学习
学位
证书

浏览 Coursera 的全部课程

浏览
搜索
企业版
登录
免费加入

Lesson 5.7: Link Analysis - Part 2

Loading...

文本检索和搜索引擎

伊利诺伊大学香槟分校

4.4（476 个评分） | 29K 名学生已注册

课程 2（共 6 门，数据挖掘专项课程）

Recent years have seen a dramatic growth of natural language text data, including web pages, news articles, scientific literature, emails, enterprise documents, and social media such as blog articles, forum posts, product reviews, and tweets. Text data are unique in that they are usually generated directly by humans rather than a computer system or sensors, and are thus especially valuable for discovering knowledge about people’s opinions and preferences, in addition to many other kinds of knowledge that we encode in text. This course will cover search engine technologies, which play an important role in any data mining applications involving text data for two reasons. First, while the raw data may be large for any particular problem, it is often a relatively small subset of the data that are relevant, and a search engine is an essential tool for quickly discovering a small subset of relevant text data in a large text collection. Second, search engines are needed to help analysts interpret any patterns discovered in the data by allowing them to examine the relevant original text data to make sense of any discovered pattern. You will learn the basic concepts, principles, and the major techniques in text retrieval, which is the underlying science of search engines.

查看授课大纲

您将学习的技能

Information Retrieval (IR), Document Retrieval, Machine Learning, Recommender Systems

审阅

4.4（476 个评分）

5 stars
279 ratings
4 stars
133 ratings
3 stars
47 ratings
2 stars
9 ratings
1 star
8 ratings

GI

Aug 21, 2016

Excellent ! Well organized, presented with aptitude to detail. Definitely will recommend and take further units in this specialization.\n\nThanks Prof

HJ

Jun 26, 2016

This course is complemented with a software and text (not mandatory) and good explanation with diagrams...

从本节课中

Week 5

In this week's lessons, you will learn feedback techniques in information retrieval, including the Rocchio feedback method for the vector space model, and a mixture model for feedback with language models. You will also learn how web search engines work, including web crawling, web indexing, and how links between web pages can be leveraged to score web pages.

Lesson 5.1: Feedback in Text Retrieval6:49

Lesson 5.2: Feedback in Vector Space Model - Rocchio12:05

Lesson 5.3: Feedback in Text Retrieval - Feedback in LM19:11

Lesson 5.4: Web Search: Introduction & Web Crawler11:05

Lesson 5.5: Web Indexing17:19

Lesson 5.6: Link Analysis - Part 19:16

Lesson 5.7: Link Analysis - Part 217:30

Lesson 5.8: Link Analysis - Part 35:59

教学方

ChengXiang Zhai
Professor

脚本

[MUSIC]

So let's take a look at this in detail.

So in this random surfing model at any page would assume

random surfer would choose the next page to visit.

So this is a small graph here.

That's of course, over simplification of the complicated web.

But let's say there are four documents here, d1, d2, d3 and d4.

And let's assume that a random surfer or random walker can be any of these pages.

And then the random surfer could decide to,

just randomly jumping to any page or

follow a link and then visit the next page.

So if the random surfer is at d1,

then there is some probability that random surfer will follow the links.

Now there are two outlinks here, one is pointing to d3,

the other is pointing to d4.

So the random surfer could pick any of these two to reach d3 and d4.

But it also assumes that the random so far might get bore sometimes.

So the random surfing which decide to ignore the actual links and

simply randomly jump into any page in the web.

So if it does that, it would be able to reach any of the other pages even

though there's no link you actually, you want from that page.

So this is to assume that random surfing model.

Imagine a random surfer is really doing surfing like this,

then we can ask the question how likely on average the surfer

would actually reach a particular page like a d1, a d2, or a d3.

That's the average probability of visiting a particular page and

this probability is precisely what a page ranker computes.

So the page rank score of the document is the average

probability that the surfer visits a particular page.

Now intuitively, this would basically capture the inlink account, why?

Because if a page has a lot of inlinks,

then it would have a higher chance of being visited.

Because there will be more opportunities of having the server to

follow a link to come to this page.

And this is why the random surfing model

actually captures the ID of counting the inlinks.

Note that it also considers the interacting links, why?

Because if the page is that point then you have themselves a lot of inlinks.

That would mean the random surfer would very likely reach one of them and

therefore, it increase the chance of visiting you.

So this is just a nice way to capture both indirect and a direct links.

So mathematically, how can we compute this problem in a day in order to see that,

we need to take a look at how this problem there is a computing.

So first of all let's take a look at the transition metrics here.

And this is just metrics with values indicating how likely

the random surfer would go from one page to another.

So each rule stands for a starting page.

For example, rule one would indicate the probability of going

to any of the other four pages from d1.

And here we see there are only 2 non 0 entries which is 1/2.

So this is because if you look at the graph d1 is pointing to d3 and d4.

There is no link from d1 or d2.

So we've got 0s for the first 2

columns and 0.5 for d3 and d4.

In general, the M in this matrix,

M sub ij is the probability of going from di to dj.

And obviously for each rule, the values should sum to 1,

because the surfer would have to go to precisely one of these other pages.

So this is a transition metric.

Now how can we compute the probability of a surfer visiting a page?

Well if you look at the surf model then basically,

we can compute the probability of reaching a page as follows.

So here on the left hand side, you see it's the probability

visiting page dj at time plus 1, so it's the next time point.

On the right hand side, you can see the equation involves the probability

of at page di at time t.

So you can see the subscript in that t here, and

that indicates that's the probability that the server was at a document at time t.

So the equation basically, captures the two

possibilities of reaching at dj at the time t plus 1.

What are these two possibilities?

Well one is through random surfing and

one is through following a link, as we just explained.

So the first part captures the probability

that the random surfer would reach this page by following a link.

And you can see the random surfer chooses this strategy

with probability 1 minus alpha as we assume.

And so there is a factor of 1 minus alpha here.

But the main party is realist sum over all the possible pages

that the surfer could have been at time t.

There are n pages so it's a sum over all possible n pages.

Inside the sum is a product of two probabilities.

One is the probability that the surfer

was at di at time t, that's p sub t of di.

The other is the transition probability from di to dj.

And so in order to reach this dj page,

the surfer must first be at di at time t.

And then also, would also have to follow the link to go from di to dj.

So the probability is the probability of being at di at time t multiplied by

the probability of going from that page to the target page, dj here.

The second part is a similar sum, the only difference is that now the transition

probability is a uniform transition probability.

1 over n and this part of captures is the probability

of reaching this page through random jumping.

So the form is exactly the same and this also allows us to

see on why PageRank is essentially assumed a smoothing of the transition matrix.

If you think about this 1 over n as coming from another transition matrix

that has all the elements being 1 over n in uniform matrix.

Then you can see very clearly essentially we can merge the two parts,

because they are of the same form.

We can imagine there's a different metrics that's combination of this m and

that uniform metrics where every m is 1 over n.

And in this sense PageRank uses this idea of smoothing and

ensuring that there's no zero entry in such as transition matrix.

Now of course this is the time dependent the calculation of the probabilities.

Now we can imagine, if we'll compute the average of the probabilities,

the average of probabilities probably with the sets of file this equation

without considering the time index.

So let's drop the time index and just assume that they will be equal.

Now this would give us any equations, because for

each page we have such equation.

And if you look at the what variables we have in these equations

there are also precisely n variables.

So this basically means, we now have a system of

n equations with n variables and these are linear equations.

So basically, now the problem boils down to solve this system of equations.

And here, I also show the equations in the metric form.

It's the vector p here equals a matrix or

the transpose of the matrix here and multiplied by the vector again.

Now, if you still remember some knowledge that you've learned from linear algebra

and then you will realize, this is precisely the equation for eigenvector.

When multiply the metrics by this vector, you get the same value as this matter and

this can be solved by using iterative algorithm.

So because the equations here

on the back are basically taken from the previous slide.

So you'll see the relation between the page that ran sports on different pages.

And this iterative approach or power approach,

we simply start with s randomly initialized vector p.

And then we repeatedly just update this p by

multiplying the metrics here by this p factor.

I also show a concrete example here.

So you can see this now.

If we assume alpha is 0.2,

then with the example that we show here on the slide,

we have the original transition matrix is here.

That includes the graph, the actual links and we have this smoothing transition

metrics, uniform transition metrics representing random jumping.

And we can combine them together with a liner interpolation to form another

metric that would be like this.

So essentially,

we can imagine now the web looks like this and can be captured like that.

They're all virtual links between all the pages now.

The page we're on now would just initialize the p vector first and

then just computed the updating of this

p vector by using this metrics multiplication.

Now if you rewrite this metric multiplication in

terms of individual equations, you'll see this.

And this is basically, the updating formula for

this particular pages and page score.

So you can also see if you want to compute the value of this updated score for d1.

You basically multiply this rule by this column,

and we'll take the third product of the two.

And that will give us the value for this value.

So this is how we updated the vector we started with an initial values for

these guys for this.

And then we just revise the scores which generate a new

set of scores and the updating formula is this one.

So we just repeatedly apply this and here it converges.

And when the matrix is like this, where there's no 0 values and

it can be guaranteed to converge.

And at that point the we will just have the PageRank scores for all the pages.

We typically go to sets of initial values just to 1 over n.

So interestingly, this updating formula can be

also interpreted as propagating scores on the graph, can you see why?

Or if you look at this formula and then compare that with this graph and

can you imagine, how we might be able to interpret this as

essentially propagating scores over the graph.

I hope you will see that indeed,

we can imagine we have values initialized on each of these pages.

So we can have values here and say, that's a 1 over 4 for each.

And then we're going to use these metrics to update this the scores.

And if you look at the equation here this one, basically we're going

to combine the scores of the pages that possibly would lead to reaching this page.

So we'll look at all the pages that are pointing to this page and

then combine this score and propagate the sum of the scores to this document, d1.

To look at the scores that we present the probability that the random

surfer would be visiting the other pages before it reached d1.

And then just do the propagation to simulate

the probability of reaching this page, d1.

So there are two interpretations here.

One is just the matrix multiplication.

We repeat the multiplying that by these metrics.

The other is to just think of it as a propagating

these scores repeatedly on the web.

So in practice, the combination of PageRank score is actually efficient.

Because the matrices is fast and there are some, ways we transform the equation.

So that you avoid actually literally computing the values for

all those elements.

Sometimes you may also normalize the equation and that will give you a somewhat

different form of the equation, but then the ranking of pages will not change.

The results of this potential problem of zero-outlink problem.

In that case, if a page does not have any outlink then the probability of

these pages would not sum to 1.

Basically, the probability of reaching the next page from this page would not sum to

1, mainly because we have lost some probability to mass.

One would assume there's some probability that the surfer would try to follow

the links, but then there is no link to follow.

And one possible solution is simply to use a page that is specific damping factor,

and that could easily fix this.

Basically, that's to say alpha would be 1.0 for a page with no outlink.

In that case, the surfer would just have to

randomly jump to another page instead of trying to follow a link.

There are many extensions of PageRank, one extension is to topic-specific PageRank.

Note that PageRank doesn't merely use the query information.

So we can make PageRank specific however.

So for example, at the top of a specific page you rank,

we can simply assume when the surfer is bored.

The surfer is not randomly jumping to any page on the web.

Instead, he's going to jump to only those pages that are relevant to our query.

For example, if the query is not sports then we can assume that when it's

doing random jumping, it's going to randomly jump to a sports page.

By doing this, then we can buy a PageRank through topic and sports.

And then if you know the current theory is about sports, and

then you can use this specialized PageRank score to rank documents.

That would be better than if you use the generic PageRank score.

PageRank is also a channel that can be used in many other applications for

network analysis particularly for example, social networks.

You can imagine if you compute the PageRank scores for

social network, where a link might indicate a friendship or

a relation, you would get some meaningful scores for people

[MUSIC]

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2019 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取

Coursera
关于
管理团队
工作机会
目录
证书
MasterTrack™ 证书
学位
企业版
政府版

社区
Learners
Partners
Developers
Beta Testers
Translators

连接
博客
Facebook
领英
Twitter
Instagram
YouTube
技术博客

更多
条款
隐私
帮助
内容访问
媒体
联系我们
目录
附属公司