Peter Norvig; "we don't think it's a big advance to be able to type something as a question as opposed to keywords."

Sometime ago I found myself in a healthy argument with a friend of mine about the future of search. Both of us are crazy about information retrieval and naturally our discussion more than normally diverts towards search. While usually we agree with each other's views, today I was shocked to find a major difference in our opinions.

I sincerely believe that any breakthrough in search will have something to do with Natural Language Processing. However my friend thinks that that will not be the case. This was not at all a big deal. But what shocked me was the evidence he used... Peter Norvig.

Now I am a big fan of Peter Norvig but while i am crazy about all things Peter Norvig, I was disappointed to read what he said in his interverview with Technology Review:

"TR: Companies such as Ask and Powerset are betting that the future is in natural-­language search, which lets people use real, useful sentences instead of potentially ambiguous keywords. What is Google doing with natural language?

PN: We think what's important about natural language is the mapping of words onto the concepts that users are looking for. But we don't think it's a big advance to be able to type something as a question as opposed to keywords. Typing "What is the capital of France?" won't get you better results than typing "capital of France." But understanding how words go together is important. To give some examples, "New York" is different from "York," but "Vegas" is the same as "Las Vegas," and "Jersey" may or may not be the same as "New Jersey." That's a natural-language aspect that we're focusing on. Most of what we do is at the word and phrase level; we're not concentrating on the sentence. We think it's important to get the right results rather than change the interface."

Apparently, Peter Norvig thinks that typing complete questions will just be a change in interface. I seriously doubt it. These days, I hardly use single keyword searches. I like Powerset and really wish that I could google something much more intelligent than a few keywords. But if the director of research at Google doesn't think that this will bring any big advancement to search, then maybe it is just me. I am sure Peter has substantial data to back his comments but I for one would like to type in a question ( and not something as simple as "Who is the 44th president of USA") and expect a relevant answer.

But thats just me... The interview was conducted in 2008, here is hoping that during this time Peter has given a second thought to some serious NLP usage for search.

Information Retrieval - A word about Word Distribution

Word distributions
Words are not distributed evenly in documents. Same goes for letters of the alphabet, city sizes, wealth, etc. Usually, the 80/20 rule applies (80% of the wealth goes to 20% of the people or it takes 80% of the effort to build the easier 20% of the system). For example, the Shakespeare's famous play Romeo and Juliet we can find the following word frequencies:

Romeo and Juliet:
And, 667; The, 661; I, 570; To, 515; A, 447; Of, 382; My, 356; Is, 343; That, 343; In, 314; ........ Night, 68; Are, 67; More, 67; We, 66; At, 65; Man, 65; Or, 65; There, 64; Hath, 63;…..................
A-bed, 1; A-bleeding, 1; A-weary, 1; Abate, 1; Abbey, 1; Abhorred, 1; Abhors, 1; Aboard, 1; ...

Stop words
There are 250-300 most common words in English that account for 50% or more of a given text.
Example: “the” and “of” represent 10% of tokens. “and”, “to”, “a”, and “in” - another 10%. Next 12 words - another 10%.

For example, Moby Dick Ch.1 has 859 unique words (types), 2256 word occurrences (tokens). The Top 65 types cover 1132 tokens (> 50%).
Therefore, the token/type ratio: 2256/859 = 2.63

Zipf’s law

Rank x Frequency = Constant

Zipf's law is fairly general. It states that, if t1 is the most common term in the collection, t2 the next most common etc, then the collection frequency (cf) of the ith most common term is proportional to 1/i:

cf(i) prop. 1/i

Heap’s law
A better way of getting a handle on vocabulary size, M is Heaps’ law, which estimates vocabulary size as a function of collection size:

M = k(T pow(b))

where, T is the number of tokens in the collection. Typical values for the parameters k and b are: 30 ≤ k ≤ 100 and b ≈ 0.5.
Regardless of the values of theparameters for a particular collection, Heaps’ law suggests that: (i) the dictionary size will continue to increase with more documents in the collection, rather than a maximum vocabulary size being reached, and (ii) the size of the dictionary will be quite large for large collections.

In English, k is between 10 and 100, b is between 0.4 and 0.6.


IDF: Inverse document frequency
TF * IDF is used for automated indexing and for topic discrimination:

idf(k) = log2(N/d(k)) + 1 = log2N - log2d(k) + 1

N: number of documents
dk: number of documents containing term k
fik: absolute frequency of term k in document i
wik: weight of term k in document i


Vector-based matching

A popular measure of similarity for text (which normalizes the features by the covariance matrix) clustering is the cosine of the angle between two vectors. The cosine measure is given by

(4.2)

and captures a scale invariant understanding of similarity. An even stronger property is that the cosine similarity does not depend on the length:
for 0$" width="51" align="middle" border="0" height="33">. This allows documents with the same composition, but different totals to be treated identically which makes this the most popular measure for text documents. Also, due to this property, samples can be normalized to the unit sphere for more efficient processing.

References
Introduction to Inforamtion Retreival, Ch. 5 Index Compression

Information Retrieval - Document Preprocessing

In this post I will touch briefly on document preprocessing and indexing concepts related to IR.

Document Preprocessing
The content of a webpage read by the crawler has to be converted into tokens before an index can be created for the keywords. This is challenging because at this step we have to deal with various formatting and encoding issues. For example, what delimiter will we use to separate different words. Tokenizing using white space as a delimiter seems to work best for "Paul's", "555-1212" or "can't". But what about: "Willow Dr.", "Dr. Willow", "New York", "ad hoc". A white space delimiter will create separate tokens for each of them which is not desirable.

Tokenization becomes even more challenging when you consider tokenizing a string like “The New York-Los Angeles flight”. Other languages such as German or Korean have eve more complex tokenization issues.

Normalization
We need a systematic way of ensuring that the index structure is suitable for general-purpose querying. For instance, "new york" or "New York" or "NEW YORK" shouldn't be treated differently. There are various ways to achieve this normalcy:

• Casing (cat vs. CAT)
• Stemming (computer, computation)
• Soundex
• Spell Checker or synonyms (Labeled/labelled, extraterrestrial/extra-terrestrial/extra terrestrial, Qaddafi/Kadhafi/Ghadaffi)
• Index reduction
• Dropping stop words (“and”, “of”, “to”), it is problematic for “to be or not to be” kind of sentences

Porter’s algorithm
Porter's algorithm can be used for Stemming - the process for reducing inflected (or sometimes derived) words to their stem, base or root form – generally a written word form (Wikipedia).
The rules in the Porter algorithm are separated into five distinct phases numbered from 1 to 5. They are applied to the words in the text starting from phase 1 and moving on to phase 5. Further, they are applied sequentially one after the other as commands in a program.

The complete description of Porter's algorithm can be found here.

Example: the word “duplicatable” will be changed to "duplic" using the Proter's algorithm.

The Soundex algorithm (Odell and Russell)
This algorithm uses spelling correction and hash function and is non-recoverable.

The algorithm is as follows:

1. Retain the first letter of the name, and drop all occurrences of a,e,h,I,o,u,w,y in other positions
2. Assign the following numbers to the remaining letters after the first:
b,f,p,v : 1
c,g,j,k,q,s,x,z : 2
d,t : 3
l : 4
m n : 5
r : 6

3. if two or more letters with the same code were adjacent in the original name, omit all but the first
4. Convert to the form “LDDD” by adding terminal zeros or by dropping rightmost digits
Examples:
Euler: E460, Gauss: G200, H416: Hilbert, K530: Knuth, Lloyd: L300
same as Ellery, Ghosh, Heilbronn, Kant, and Ladd
Some problems: Rogers and Rodgers, Sinclair and StClair

Storage issues
As mentioned in the last post that a medium-sized collection with n=3,000,000 (terms) and m=50,000 (documents) will result in a large term-document matrix. We have to find a way to come up with a better data structure. Inverted Index is the basic structure that resolves the issue.

Inverted index
Instead of an incidence vector, use a posting table. We can use a Dictionary object and represent the term-documents as the term-value pairs in the dictionary. The term represents a unique ID and the document (where the term is present) IDs are the values in each term-value pair of the dictionary. For example,

CLEVELAND: D1, D2, D6
OHIO: D1, D5, D6, D7

We use linked lists to be able to insert new document postings in order and to remove existing postings. We need to keep everything sorted! This gives us a logarithmic improvement in access.

Basic operations on inverted indexes
Conjunction (AND) – iterative merge of the two postings: O(x+y)
Disjunction (OR) – very similar
Negation (NOT)

Example: MICHIGAN AND NOT OHIO
Example: MICHIGAN OR NOT OHIO

For recursive operations we should start with the smallest sets for better optimization.

That sums up the second post on Information Retrieval. In the next post, I will discuss word distribution issues in the IR.

Information Retrieval - Introduction

This is the first in the series of blog posts related to Information Retrieval.

Information Retreival
So what is Information Retrieval (IR)? IR can be defined as the indexing and retrieval of textual documents. It can be more thoroughly defined as follows:

"Information retrieval (IR) is finding material (usually documents) of an unstructured nature (usually text) that satisfies an information need from within large collections (usually stored on computers)." [1]

What does it take to build a search engine?
The task of search engines looks trivial. All search engines (Google, Yahoo, Live.com) had to do is crawl the web, index the web pages, read the text and make the links to the web pages available to upon user's request.

But if you ponder over it the simple task converts into complex sub tasks, which are as follows:

• Decide what to index
• Collect it
• Index it (efficiently)
• Keep the index up to date
• Provide user-friendly query facilities

A lot of research is done on each of these sub tasks. But that is not enough. There are other things which need to be dealt with to create an 'efficient' search engine. Some of them are:

• Understand the structure of the web for efficient crawling
• Understand user information needs
• Preprocess text and other unstructured data
• Cluster data
• Classify data
• Evaluate performance

Document representations
Search engines display relevant links to webpages (documents) based on the keywords typed by the user. The documents retrieved consist of those keywords (not necessarily). In order to carry out the task of finding keywords in the documents, there must be some sort of data structure that holds the word-document relationship. One way to achieve this is to have a Term-document matrix (m x n).

Another important datastructure that comes handy is a Document-document matrix (n x n). However, space limitations and time complexity have to be taken into consideration before implementing these matrices.

However, these matrices don't scale very well. Typical example in a medium-sized collection is something like 3,000,000 documents (n) with 50,000 terms (m). So you can imagine how big a (m x n) matrix can be. In case of web documents you will typically have: n=30,000,000,000, m=1,000,000. Creating a (m x n) matrix and then using it could shoot up the time complexity sky high.

Boolean vs. integer-valued matrices
There is also the question whether you should use boolean (True or False) or inter-valued (0s and 1s) to represent the document-word relationship in the matrix.

Major IR models
Assuming that term-document relationship has been efficiently implemented. The next task is to come up with retrieval models that will be used to query the matrices and retrieve the most relevant documents. These models are know as IR Models. Some of the most common models are as follows:

• Boolean
• Vector
• Probabilistic
• Language modeling
• Fuzzy retrieval
• Latent semantic indexing

Boolean queries
Boolean IR Model is perhaps one of the simplest to implement. It uses boolean operators: AND, OR, NOT, parentheses, etc. For example, typical search queries will be something like:
CLEVELAND AND NOT OHIO
(MICHIGAN AND INDIANA) OR (TEXAS AND OKLAHOMA)

Vector queries
Each document is represented as a vector. Non-binary weights provide consideration for partial matches. These term weights are used to compute a degree of similarity between a query and each document. Ranked set of documents provides for better matching.

Probabilistic Model
Captures the IR problem using a probabilistic framework. Improve by iteration

The matching process
Matching is done between a document and a query (or between two documents). Distance or similarity measures are used to determined which set of documents satisfied a given query. The common methods used are: Euclidean distance, Manhattan distance, Word overlap, Jaccard coefficient, etc.

Well this sums up the introductory post on IR. In the next post we will look into more details of some of the components of IR mentioned in this post, especially indexing. So stay tuned.

References
[1] http://nlp.stanford.edu/IR-book/html/htmledition/boolean-retrieval-1.html

Information Retrieval and Web Mining

Last semester I had to select a research topic for my Computer Seminar course. The topic I selected was "Personalized Search". I have always been interested in Information Retrieval and hence thought that it was a perfect opportunity to learn more about this field.

Even before I could starting doing research on personalization, I had to do a lot of reading and research related to information retrieval and web mining. In the process, I learned a lot about IR. However, I hardly get the chance to practice what I learned. Hence, I have decided to blog about what I learned related to IR every week....well, almost every week.

So why blog about this? Well, this will help me revise what I learned and maybe learn something new.

I hope that other people will find it helpful as well.

Simple IsNum() function in C#

I disparately needed a C#'s equivalent for "IsNum". I was surprised that there isn't one, so I decided to write my own. There are many ways that can be used to write this functions. However, my task required that I should be able to verify any type of number (int, double, etc.) and get either True/False return values. Below is the code that I am using to solve this problem.

public static bool IsNumeric(object Expression)
{

// Variable to collect the Return value of the TryParse method.

bool isNum;


// Define variable to collect out parameter of the TryParse method. If the conversion fails, the out parameter is zero.

double retNum;


// The TryParse method converts a string in a specified style and culture-specific format to its double-precision floating point number equivalent.

// The TryParse method does not generate an exception if the conversion fails. If the conversion passes, True is returned. If it does not, False is returned. Hence no need for try..catch block

isNum = Double.TryParse(Convert.ToString(Expression), System.Globalization.NumberStyles.Any, System.Globalization.NumberFormatInfo.InvariantInfo, out retNum);

return isNum;

}

Sorting Dictionary object in .Net

A few days ago I came across a sorting-dictionary problem at work. The easiest way to have a sorted dictionary in .Net is to use the SortedDictionary(TKey, TValue) item. Every time you enter a keyvaluepair in the SortedDictionary item, it will be sorted automatically.

But I had to sort an existing Dictionary(TKey, TValue) item, that was provided by some other program. Initially, I was hoping that there is some Dictionary.Sort() function available that I could use but there isn't.

After some research I found that you could use the List.Sort() function to sort the dictionary by keys. But that is not all. You also need to add a delegate in the List.Sort() function to carry out the sorting process.

Here is the code.

//Code takes a Dictionary<double,int> item, sorts it and return the new Dictionary<double,int> item

private static Dictionary<double,int> Sort(Dictionary<double,int> Dict)
{
//Create a List object from the Dictionary item
List<keyvaluepair<double,int>> result = new List<keyvaluepair<double,int>>(Dict);


//Use the delegate in the List.Sort function to compare the keys for sorting
result.Sort(
delegate(
KeyValuePair<double, int> first,
KeyValuePair<double, int> second)
{
return first.Key.CompareTo(second.Key);
}
);

//Add the List items into a new dictionary item
Dictionary<double,int> sortedDict = new Dictionary<double,int>();

foreach (KeyValuePair<double, int> kvp in result)
{

double key = kvp.Key;
int value = kvp.Value;

sortedDict.Add(key, value);
}

return sortedDict;
}


If there is a better way to achieve this, please let me know.