To see mutual information in action, let's turn to Adsense which is the mechanism
which Google uses to place ads in webpages other than search results.
In such cases there are no search terms in which to match the keyword 'Bates', so
what Adsense does is it figures out which are the right keywords that best represent
webpages actual content and use these to decide which keyword 'Bates' should get ad
space on the page. For example, suppose you are reading this
review of a camera. Then the ad on the right has probably been
posted by a company in multi-brand retail who happened to bid high for the camera
keyword. On the other hand, if you turned to a
story about smartphones, you end up seeing an ad about mobiles.
What is happening, is that the Adsense code that Google asks you to put on your
site is figuring out which are the best keywords that represent the content on
your page. And matches that to the key words that are
being bid on the key word auction. In a sense this is an inverse of search.
Think about it this way. When you're searching, you give some query
keywords. And you wanna come back with the pages
that best match them. In this case, you're shown a page and the
system needs to guess what are the best possible keywords that you would have
searched with if this was the page that you really wanted as a result.
Viewing this problem in the language of information theory.
The transmitted signal is the content of the web page and what your receiving are
the keywords.The channel that enables you to do this is Ad sense, which is Google's
technique to guess keywords from content. And it rise to maximize the mutual
information between these two signals. Such on the other hand is the reverse.
You're given some key works and you want to find those pages which best match the
key words that you chose. So, the question now reduces to how to
maximize the mutual information between the words on one side and the words that
you want to receive on the other, that would define the way you design and Ad
sense channel. Of course you might know this that we
haven't yet defined what exactly is the technique to compute the mutual
information. Be patient, we're going to come to that
because mutual information is so deep a concept that it applies in many contexts.
For the moment. Bear with me and believe that there is a
formula using which one can exactly compute the mutual information between two
signals. Disregarding mutual information for the
time being, let's think about how one might construct the best possible keywords
given a web page. The converse problem of search is equally
related. Which terms in a query should one consider
while searching? Obviously, you don't need to worry about
which documents match the, and, a. We really should focus on those words in
the query which are likely to be keywords in the documents that you want to search
for. Let's figure this out intuitively.
Merely a word like, the can weighs much like less about the content of some page
describing the computer science concepts than say the word touring which really
like me to be on pages about computer science.
Clearly, rarer words, that means, words that are not that common in all documents,
like the, a, and an, make better keywords. Even other keywords like computer, might
be present in many, many documents but. They are certainly rarer than the in, or
etcetera. So, based on the principle that rarer
words make better keywords. The concept of inverse document frequency
of a word. Becomes, useful.
Now what is inverse, inverse document frequency?
Let. N is the total number of documents.
Say all the documents on the web. And out of these, N sub W contain the word
W. Then, the ratio of N over N sub W.
Obviously, N sub W will be less than N. Tells us which fraction, or rather, the
inverse of the fraction of the words which contain W, as compared to all the words.
And then we take the logorithm of this term and, obviously, we reverse the
fraction. Because, otherwise, the logorithm would
become negative. And we get what is called the inverse
document frequency of a word. Well, that's obviously not enough.
Because a document needs to contain the word itself if the word needs to be a
keyword. And if it contains many instances of the
word touring, maybe fifteen times for example its much more likely that
[inaudible] is a keyword for that document compared to say a document where the word
appears only twice. So, the second principle that we apply in
our intuition, is that more frequent words make better key words...
More frequent in the document that we are considering, not more frequent in general.
So rarer words overall, but more frequent in the document that we are considering.
So we simply multiply. The, inverse document frequency with
another term. Which is the frequency of the word in, a
given document. Cuz the word occurs five times.
N, sub w, sub t, is five, and so on. So TFIDF is nothing but the Term Frequency
multiplied by the Inverse Document Frequency.
Words having a high TFIDF are considered to be good keywords.
Apart from guessing key words think about it from the search perspective.
If you're searching with a query which has certain words with, whose idf is high, you
would like to use those in your query. At the same time, when you index a word,
you want to weight it by its tf-idf value. If a word occurs hundred times in a
document, but the word is, the, weighting that element in the Index by 100 doesn't
make sense. But if a word like queuing [inaudible]
occurs a 100 times than weighting it with a high value makes sense.
The TF idea accurately captures this intuition.