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 5.3: Feedback in Text Retrieval - Feedback in LM
Loading...
来自 University of Illinois at Urbana-Champaign 的课程
Text Retrieval and Search Engines
356 个评分
从本节课中
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.
与讲师见面
ChengXiang ZhaiProfessor
Department of Computer Science
[SOUND] This
lecture is about the feedback in the language modeling approach.
In this lecture, we will continue the discussion of feedback in text retrieval.
In particular,
we're going to talk about the feedback in language modeling approaches.
So we derive the query likelihood ranking function by making various assumptions.
As a basic retrieval function, all those formulas worked well.
But if we think about the feedback information, it's a little bit awkward to
use query likelihood to perform feedback, because
a lot of times the feedback information is additional information about the query.
But we assume the query has generated it by assembling words
from a language model in the query likelihood method.
It's kind of unnatural to sample words that form feedback documents.
As a result, researchers proposed a way to generalize query likelihood function,
and it's called Kullback-Leibler divergence retrieval model.
And this model is actually going to make the query likelihood
retrieval function much closer to vector space model.
Yet this form of the language model can be regarded as a generalization of
query likelihood, in the sense that it can cover query likelihood as a special case.
And in this case,
then feedback can be achieved through simply query model estimation or updating.
This is very similar to Rocchio, which updates the query vector.
So let's see what is this KL-divergence retrieval model.
So on the top, what you see is a query likelihood retrieval function, this one.
And then KL-divergence, or also called cross entropy,
retrieval model is basically to generalize
the frequency part here into a language model.
So basically it's the difference given
by the probabilistic model here to characterize what the user is looking for,
versus the count of query words there.
And this difference allows us to plug in various different ways to estimate this.
So this can be estimated in many different ways,
including using feedback information.
But this is called a KL-divergence, because
this can be interpreted as matching the KL-divergence of two distributions.
One is the query model, denoted by this distribution.
One is the document language model here and
smooth them with a collection language model, of course.
And we are not going to talk about the detail of that, and
you'll find it in some references.
It's also called cross entropy because, in fact,
we ignore some terms in the KL-divergence function and
we will end up having actually cross entropy.
And both are terms of information theory.
But anyway, for our purposes here,
you can just see the two formulas look almost identical,
except that here we have a probability of a word given by a query language model.
And here the sum is over all the words that are in the document and
also with the nonzero probability for the query model.
So it's kind of, again, a generalization of sum over all the matching query words.
Now you can also easily see we can recover the query likelihood retrieval function
by simply setting this query model to the relative frequency of a word in the query.
This is very easy to see once you plug this
into here you can eliminate this query length as a constant.
And then you will get exactly like that.
So you can see the equivalence.
And that's also why this KL-divergence model can be regarded as a generalization
of query likelihood, because we can cover query likelihood as a special case.
But it would also allow us to do much more than that.
So this is how we can use the KL-divergence model to then do feedback.
The picture shows that we first estimate a document language model,
then we estimate a query language model, and we compute the KL-divergence.
This is often denoted by a D here.
But this basically means this is exactly like the vector space model,
because we compute a vector for the document, then compute another vector for
the query, and then we compute the distance.
Only that these vectors are of special forms, they are probability distributions.
And then we get the results and we can find some feedback documents.
Let's assume they are mostly positive documents,
although we could also consider both kinds of documents.
So what we could do is, like in Rocchio, we're going to compute another language
model called the feedback language model here.
Again, this is going to be another vector just like the computing centroid of vector
in Rocchio.
And then this model can be combined with the original query model using
a linear interpolation, and this would then give us an update model,
just like, again, in Rocchio.
So here we can see the parameter alpha can control the amount of feedback.
If it's set to zero, then essentially there is no feedback.
If it's set to one, we get full feedback and we ignore the original query.
And this is generally not desirable, right?
So unless you are absolutely sure you have seen a lot of relevant documents,
then the query terms are not important.
So of course, the main question here is, how do you compute this theta F?
This is the big question here, and once you can do that, the rest is easy.
So here we will talk about one of the approaches, and
there are many approaches, of course.
This approach is based on generative model, and
I'm going to show you how it works.
This will use a generative mixture model.
So this picture shows that we have this model here,
the feedback model that we want to estimate.
And the basis is the feedback documents.
Let's say we are observing the positive documents.
These are the clicked documents by users or random documents judged by users,
or are simply top ranked documents that we assume to be relevant.
Now imagine how we can compute a centroid for
these documents by using language model.
One approach is simply to assume
these documents are generated from this language model.
As we did before, what we could do is just normalize the word frequency
here to here and then we will get this word distribution.
Now the question is whether this distribution is good for feedback.
Well, you can imagine the top ranked word would be what?
What do you think?
Well, those words would be common words.
As we always see in a language model,
the top ranked words are actually common words like the, a, etc.
So it's not very good for feedback, because we would be adding a lot of such
words to our query when we interpolate this with the original query model.
So this was not good, so we need to do something.
In particular, we are trying to get rid of those common words.
And we have seen actually one way to do that by using background
language model in the case of learning the associations of words,
the words that are related to the word computer.
We could do that and that would be another way to do this, but here we
are going to talk about another approach which is a more principled approach.
In this case, we're going to say well, you said that there are common words here
in these documents that should not belong to this topic model, right?
So now what we can do is to assume that, well,
those words are generated from background language model, so
they will generate those words like the, for example.
And if we use maximum likelihood estimate,
note that if all the words here must be generated from this model,
then this model is forced to assign high probabilities to a word like the,
because it occurs so frequently here.
Note that in order to reduce its probability in this model, we have to have
another model, which is this one, to help explain the word the here.
And in this case,
it's not appropriate to use the background language model to achieve this
goal because this model would assign high probabilities to these common words.
So in this approach, then,
we assume this machine that was generating these words would work as follows.
We have a source control up here.
Imagine we flip a coin here to decide what distribution to use.
With probability of lambda, the coin shows up as head and
we're going to use the background language model.
And we're going to do that in sample word from that model.
With probability of 1 minus lambda, we're going to decide
to use a known topic model, here, that we would like to estimate.
And we're going to then generate a word here.
If we make this assumption and this whole thing will be just one model, and we call
this a mixture model because there are two distributions that are mixed together.
And we actually don't know when each distribution is used.
So again, think of this whole thing as one model,
and we can still ask for words and it will still give us a word in a random manner.
And of course, which word will show up will depend on both this distribution and
that distribution.
In addition, it would also depend on this lambda,
because if you say lambda is very high and it's going to
always use the background distribution, you will get different words.
Then if you say, well, lambda is very small, we're going to use this.
So all of these are parameters in this model.
And then if you're thinking this way,
basically we can do exactly the same as what we did before.
We're going to use maximum likelihood estimator to adjust this model,
to estimate the parameters.
Basically we're going to adjust this parameter so
that we can best explain all the data.
The difference now is that we are not asking this model a known to explain this.
But rather we are going to ask this whole model, mixture model, to explain the data.
Because it has got some help from the background model,
it doesn't have to assign high probabilities to words like the.
As a result, it will then assign higher probabilities to other words that
are common here but not having high probability here.
So those would be common here.
And if they're common, they would have to have high probabilities,
according to a maximum likelihood estimate method.
And if they are rare here, then you don't get
much help from this background model.
As a result, this topic model must assign high probabilities.
So the high probability words, according to the topic model,
would be those that are common here but rare in the background.
So this is basically a little bit like an idea of weighting here.
But this would allow us to achieve the effect of removing these topic words that
are meaningless in the feedback.
So mathematically, what we have is to compute the likelihood, again,
local likelihood, of the feedback documents.
And note that we also have another parameter, lambda here, but
we assume that the lambda denotes the noise in the feedback document.
So we are going to, let's say set this to a parameter.
Let's say 50% of the words are noise or 90% are noise.
And this can then be assumed it will be fixed.
If we assume this is fixed, then we only have these probabilities as parameters,
just like in the simple unigram language model.
We have n parameters, n is the number of words.
And then the likelihood function would look like this.
It's very similar to the global likelihood function we see before,
except that inside the logarithm there's a sum here.
And this sum is because we consider two distributions.
And which one is used would depend on lambda, and that's why we have this form.
But mathematically, this is the function with theta as unknown variables.
So this is just a function.
All the other values are known except for this guy.
So we can then choose this probability distribution to maximize
this log likelihood,
the same idea as the maximum likelihood estimate as a mathematical problem.
We just have to solve this optimization problem.
We essentially would try all the theta values until we find one
that gives this whole thing the maximum probability.
So it's a well-defined math problem.
Once we have done that, we obtain this theta F that can then be interpolated with
original query model to the feedback.
So here are some examples of the feedback model learned from a web
document collection.
And we do pseudo-feedback we just use the top ten documents and
we use this mixture model.
So the query is airport security.
What we do is we first retrieve ten documents from the web database and
this is of course pseudo-feedback.
And then we're going to feed that mixture model to this ten document set.
And these are the words learned using this approach.
This is the probability of a word given by the feedback model in both cases.
So in both cases you can see the highest
probability words include the very relevant words to the query.
So airport security, for example,
these query words still show up as high probabilities in each case naturally,
because they occur frequently in the top ranked documents.
But we also see beverage, alcohol, bomb, terrorist, etc.
So these are relevant to this topic, and they,
if combined with original query, can help us much more accurately on documents.
And also they can help us bring up documents that only mention some of
these other words, maybe, for example, just airport and then bomb, for example.
So this is how pseudo-feedback works.
It shows that this model really works and picks up some related words to the query.
What's also interesting is that if you look at the two tables here and
you compare them, then you'll see, in this case,
when lambda is set to a small value, then we'll see some common words here.
And that means, well, we don't use the background model often.
Remember, lambda confuses the probability of using background model
to generate the text.
If we don't rely much on background model,
we still have to use this topic model to account for the common words.
Whereas if we set lambda to a very high value,
we will use the background model very often to explain these words.
Then there's no burden on expanding those common words
in the feedback documents by the topic model.
So as a result, the topic model here is very discriminative.
It contains all the relevant words without common words.
So this can be added to the original query to achieve feedback.
So to summarize,
in this lecture we have talked about the feedback in language model approach.
In general, feedback is to learn from examples.
These examples can be assumed examples, can be pseudo-examples,
like assume the top ten documents that are assumed to be relevant.
They could be based on user interactions,
like feedback based on clickthroughs or implicit feedback.
We talked about the three major feedback scenarios, relevance feedback,
pseudo feedback, and implicit feedback.
We talked about how to use Rocchio to do feedback in vector space model and
how to use query model estimation for feedback in language model.
And we briefly talked about the mixture model and the basic idea.
There are many other methods.
For example,
the relevance model is a very effective model for estimating query model.
So you can read more about these methods in the references that
are listed at the end of this lecture.
So there are two additional readings here.
The first one is a book that has a systematic review and
discussion of language models for information retrieval.
And the second one is a important research
paper that's about relevance based language models,
and it's a very effective way of computing query model.
[MUSIC]
