Showing posts with label Information Retrieval. Show all posts
Showing posts with label Information Retrieval. Show all posts

Sunday, June 17, 2007

Part 4 - Creating a Simple Search Engine

I would like to mention how words and vocabularly are distributed inside a document. In order to decide the distribution nature of words and vocabularly in a document, we can apply below theories:

(1) Zipf Law
(2) Skewed
(3) Heap's Law

Zipf Law mentions that the frequency of any word is roughly inversely proportional to its rank in the frequency table. So, the most frequent word will occur approximately twice as often as the second most frequent word, which occurs twice as often as the fourth most frequent word, etc. That is, i-th frequent word appears 1/i to the power theta times of most frequent word. The formula for a corpus with n words and v vocabulary is as follow.



For example, in the Brown Corpus "the" is the most frequently-occurring word, and all by itself accounts for nearly 7% of all word occurrences (69971 out of slightly over 1 million). True to Zipf's Law, the second-place word "of" accounts for slightly over 3.5% of words (36411 occurrences), followed by "and" (28852). Only 135 vocabulary items are needed to account for half the Brown Corpus.

Check below image for distribution nature of words in a document. You will see that words like a,an,the,etc are at the highest point where the word "Zaw" which is considered informative is nearly at the zero point.



Example Zipf's law calculation where vocabularly=1000, Theta=2.0 and words=500.




Below is a song for you



Stayed Tuned,
- Zaw Win Htike

Thursday, June 7, 2007

Part 3 - Creating a Simple Search Engine

In part 2, I have discussed about the pre-processing tasks needed to perform on documents so that lexicon size can be reduced. Now, I want to discuss the informativeness of a document.

In reading an article in newspaper, magazine or journal, you may not sure how much level of informativeness the article you read carries. Depending on your judgement about the content of an article, you may want to skip to another article.

Same concept applies in creating a search engine. A search engine needs to decide the informativeness of a document depending on the contents contained in it so that a search engine can provide you with the most relevant and useful documents in ranking order. Then, how does a search engine determine a document carries much information compare to another document? It uses Information Theory (Entropy). Entropy is the amount of information related to symbol distribution in documents. Its formula is as follow:

Symbols may mean a character or a word in a document. Suppose that your document contains 001001011011 where it has six zeros and six 1s and we can derive its entropy value as:

E=− 6/12*log2 * 6/12− 6/12*log2 *6/12=1

(Where 12 is total no of characters in our document and the two 6: one for total no of zero and another for total no of 1.)

Getting 1 in entropy means that your document contain maximun informativeness and the symbols are randomly distributed in your document.

Or if your document contains 111111111111 where there is no variation except 1 and we can get its entropy value as:

E=− 0/12*log2*0/12−12/12*log2*12/12=0

If we have no different characters/words in our document, then we need to include zero case in our formula(eg. 0/12*log2*0/12). Resulting zero means that your document does not contain much information.

Note: if you don't understand mathematical symbols, you can check them at http://en.wikipedia.org/wiki/Table_of_mathematical_symbols.

Below is a present song from me for you.

Stay Tuned,
- Zaw Win Htike

Friday, May 25, 2007

Part 2 - Creating a Simple Search Engine

In part 2, I would like to address pre-processing tasks that we need to perform on the documents before the users come and do a search using our search engine.

Do you think all words have equal level of importance and weightage? Of course not. For example, the word "you" carries way less information than that of "nepotism". And important words will serve as index terms. Then you may ask why not index everything (full-text). The reasons are:

(1)Increase the level of noise(stopwords, eg - a, an, the, etc)
(2)Reduce the overall importance of a document
(3)Reduce indexing and retrieval performance

It is now clear that some kind of preprocessing task is needed on the documents to alleviate the above issues. Below represents a list of steps required to preprocess on the documents.

(1) Lexical Analysis

It means converting stream of characters into stream of words. In another term, it is identifying words. Four types of scenarios are needed to consider in doing lexical analysis: whether to consider numbers, hyphen, punctuation, case-sensitivity in indexing. For example, if you index all numbers up to 10 digits, then it may add 1 billion terms to your lexicon. So these four scenarios are really important in determing the size of your lexicon. By the way, Google knows every number. Have you ever tried typing your phone no in Google?

(2) Stopword Removal

Examples of stopwords are a, an, the, about, of, to, be, not etc. Considering stopwords removal, it will reduce your lexicon size by 40% or more. But doing so may not be able to find specialized words like "to be or not not be".

(3) Stemming

It is a kind of morphology. By doing so, it will reduce the no of words and improve performance. For example, whenever the indexer finds "hope, hoped, hop", it will reduce all to "hop" and store it in the lexicon - meaning there will be only one word "hop" in the lexicon. The most frequently used stemmer is "Porter Stemmer". It uses a 5-phase pattern matching rules to determine which affixes to strip in which order and when to apply repair strategies.

(4) Selection of Index Terms

A sentence contains nouns, pronouns, articles, verbs, adjectives, adverbs, connectives. We need to decide which one to index among them. Noun carries most semantics but sometimes you may want to cluster co-occuring nouns into phrases(n-grams, typically n=3, eg. Information Retrieval) and concepts (noun groups of distance n, typically n=3-5, eg. gates microsoft richest)

(5) Grouping Similar Terms Together

We can use Thesaurus and WordNet to group similar terms together. Eg. stupid, moronic, idiotic, retarded, spastic. Thesaurus is precompiled list of important words w for a given domain. WordNet is English Semantics Lexicon. It is a BSD lincensed open source software. WordNet groups nouns, verbs, adverbs, adjectives into synsets and create semantic relationship between synsets. Eg.

(3) Antonyms (NOT): stupid is not smart
(2) Hyponyms (ISA): chihuahua is a kind of dog
(1) Meronyms (HASA): dog has a mouth

The following diagram represents logical view of a document through out the various phases of text processing.






Below is a present song from me for you.


Stayed Tuned,

- Zaw Win Htike

Tuesday, May 22, 2007

Part 1 - Creating a Simple Search Engine

Before delving down into the technical parts, let me enlighten all of the happenings around the search engines and induce you what you can do and what you can benefit by knowing about them.

Starting from 1945 to Google 2007, the realm of search engines have bypassed 1st generation and 2nd generation till its current wobbly state in 3rd generation. In 3rd generation, researchers are trying to widen and make search engines more intelligent by including such features as semantic analysis, focusing on user needs rather than on query and context determination.

You may probably notice some of those features by chance when you do a search - for example -from your GMail and you will notice "New!View and manage your web history" at the top right corner of the resulting web page. It means that this feature is trying to focus on your needs and try to provide you with more relevant results overtime. (User Needs)

Or if you query Google with the word "Iraq", Google will aware that you are looking for news related to Iraq and make best recommendation to you with today top-stories in Iraq at the uppermost result pane. (Context Determination)

Or if you question Google with the phrase starting with "What is..", Google recognizes that you are looking for a definition about something. (Semantic Analysis)

By learning about information retrieval system, you can design next generation search engine, be next Google and be a billionaire. Who knows...?

In 1994 Yahoo rocked the cybersphere,
In 2004 Google reigned the web,
But in 200x, 200x [Put You or Your Company Name here] will take the crown from Google.

Researchers have anticipated 3rd generation search engine to be available by year 2020.

I hope you all enjoy my article.

By the way, I have it in mind to jot down this article into quite a long series. With a bit of luck, you all won't worn-out about my upcoming series.

Below is a present song from me for you.


Stay Tuned,

- Zaw Win Htike