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.
Lesson 1.4: Overview of Text Retrieval Methods
Loading...
Do curso por University of Illinois at Urbana-Champaign
Text Retrieval and Search Engines
383 classificações
University of Illinois at Urbana-Champaign
383 classificações
Curso 2 de 6 em Specialization Data Mining
Na lição
Week 1
During this week's lessons, you will learn of natural language processing techniques, which are the foundation for all kinds of text-processing applications, the concept of a retrieval model, and the basic idea of the vector space model.
Conheça os instrutores
ChengXiang ZhaiProfessor
Department of Computer Science
[SOUND]
This lecture is a overview of text retrieval methods.
In the previous lecture, we introduced the problem of text retrieval.
We explained that the main problem
is the design of ranking function to rank documents for a query.
In this lecture,
we will give an overview of different ways of designing this ranking function.
So the problem is the following.
We have a query that has a sequence of words and
the document that's also a sequence of words.
And we hope to define a function f
that can compute a score based on the query and document.
So the main challenge you hear is with design a good ranking function that
can rank all the relevant documents on top of all the non-relevant ones.
Clearly, this means our function must be able to measure
the likelihood that a document d is relevant to a query q.
That also means we have to have some way to define relevance.
In particular, in order to implement the program to do that,
we have to have a computational definition of relevance.
And we achieve this goal by designing a retrieval model,
which gives us a formalization of relevance.
Now, over many decades,
researchers have designed many different kinds of retrieval models.
And they fall into different categories.
First, one family of the models are based on the similarity idea.
Basically, we assume that if a document is more similar to
the query than another document is,
then we will say the first document is more relevant than the second one.
So in this case, the ranking function is defined as
the similarity between the query and the document.
One well known example in this case is vector space model,
which we will cover more in detail later in the lecture.
A second kind of models are called probabilistic models.
In this family of models, we follow a very different strategy, where we assume that
queries and documents are all observations from random variables.
And we assume there is a binary random variable called R here
to indicate whether a document is relevant to a query.
We then define the score of document with respect to a query as a probability that
this random variable R is equal to 1, given a particular document query.
There are different cases of such a general idea.
One is classic probabilistic model, another is language model,
yet another is divergence from randomness model.
In a later lecture, we will talk more about one case, which is language model.
A third kind of model are based on probabilistic inference.
So here the idea is to associate uncertainty to inference rules,
and we can then quantify the probability that we can
show that the query follows from the document.
Finally, there is also a family of models
that are using axiomatic thinking.
Here, an idea is to define a set of constraints that we
hope a good retrieval function to satisfy.
So in this case, the problem is to seek a good ranking function
that can satisfy all the desired constraints.
Interestingly, although these different models are based on different thinking,
in the end, the retrieval function tends to be very similar.
And these functions tend to also involve similar variables.
So now let's take a look at the common form of a state of the art retrieval model
and to examine some of the common ideas used in all these models.
First, these models are all based on the assumption
of using bag of words to represent text, and
we explained this in the natural language processing lecture.
Bag of words representation remains the main representation used in all
the search engines.
So with this assumption, the score of a query,
like a presidential campaign news with respect to a document of d here,
would be based on scores computed based on each individual word.
And that means the score would depend on the score of each word,
such as presidential, campaign, and news.
Here, we can see there are three different components,
each corresponding to how well the document matches each of the query words.
Inside of these functions, we see a number of heuristics used.
So for example, one factor that affects the function d here
is how many times does the word presidential occur in the document?
This is called a term frequency, or TF.
We might also denote as c of presidential and d.
In general, if the word occurs more frequently in the document,
then the value of this function would be larger.
Another factor is, how long is the document?
And this is to use the document length for scoring.
In general, if a term occurs in a long
document many times, it's not as significant as
if it occurred the same number of times in a short document.
Because in a long document, any term is expected to occur more frequently.
Finally, there is this factor called document frequency.
That is, we also want to look at how often presidential occurs in the entire
collection, and we call this document frequency, or df of presidential.
And in some other models, we might also use a probability
to characterize this information.
So here, I show the probability of presidential in the collection.
So all these are trying to characterize the popularity of the term in
the collection.
In general, matching a rare term in the collection is contributing more
to the overall score than matching up common term.
So this captures some of the main ideas used in pretty much older state of
the art original models.
So now, a natural question is, which model works the best?
Now it turns out that many models work equally well.
So here are a list of the four major models
that are generally regarded as a state of the art original models,
pivoted length normalization, BM25, query likelihood, PL2.
When optimized, these models tend to perform similarly.
And this was discussed in detail in this reference at the end of this lecture.
Among all these, BM25 is probably the most popular.
It's most likely that this has been used in virtually all the search engines,
and you will also often see this method discussed in research papers.
And we'll talk more about this method later in some other lectures.
So, to summarize, the main points made in this lecture are first the design
of a good ranking function pre-requires a computational definition of relevance, and
we achieve this goal by designing appropriate retrieval model.
Second, many models are equally effective, but we don't have a single winner yet.
Researchers are still active and working on this problem,
trying to find a truly optimal retrieval model.
Finally, the state of the art ranking functions tend
to rely on the following ideas.
First, bag of words representation.
Second, TF and document frequency of words.
Such information is used in the weighting function to determine
the overall contribution of matching a word and document length.
These are often combined in interesting ways, and we'll discuss how
exactly they are combined to rank documents in the lectures later.
There are two suggested additional readings if you have time.
The first is a paper where you can find the detailed discussion and
comparison of multiple state of the art models.
The second is a book with a chapter that gives a broad
review of different retrieval models.
[MUSIC]
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
