Abstract

In today’s world, Information Retrieval (IR) systems play a significant role in facilitating users to access their desired information on the web. Current IR systems have come a long way in retrieving the most relevant results by using sophisticated ranking algorithms, relevance feedback, efficient indexing techniques etc. As a substantial amount of the web content is in English, current IR systems do a fair job of fulfilling users information needs. On the other hand, Non-English web content has also seen tremendous growth in the recent years. Content from local or native languages originates mainly in the form of news portals, blogs, social networking web sites, etc. The surge in such web content can be attributed to major factors like users interests to read and express thoughts in their local languages, availability of sophisticated input methods for local language text entry, and robust technologies to handle such Non-English content. From the users perspective, IR systems that can retrieve relevant local language search results in addition to the search results in English would be more useful. This aspect of information need has given rise to the field of Cross Language Information Retrieval (CLIR). CLIR deals with retrieval of documents present in one language using user queries in another language. CLIR systems either translate the queries to the documents language during input processing or translate the documents to the language of the queries during indexing for efficient retrieval. In this thesis, we focus on exploring efficient ways to translate user queries for cross language retrieval involving Indian languages. To build an effective query translation process, we need to find answers for some interesting questions pertaining to queries like What does a general user query consist of? What are the ways to translate user queries from one language to another? A typical web query consists of three to four words with most of them as named entities. Studies have shown that more than 80% of the query terms are Out Of Vocabulary (OOV) words. Generally, these OOV words are not present in bi-lingual thesaurus. Hence they cannot be translated using bi-lingual dictionaries similar to other content words present in the query. They have to be transliterated either phonetically or orthographically or combining both based on the source and target languages. The content words in the query can be translated using several approaches including bi-lingual thesaurus, Ontologies, parallel or comparable corpora, using web and other related resources. As one could infer, some form of “external resources” is needed for translating queries across any two languages. Firstly, we try to address the problem of translating OOV words in the context of English-Indian language and Indian language-English cross language retrieval. In our analysis, we found that most of the transliteration errors are due to ambiguities in the usage of “vowels” either in the source side or in the target side word. To address this issue, we introduce a mapping based approach of transliterating named entities that generates “consonant skeleton” for the given source word and map it to the right target side word equivalent based on phonetically modified Levenshtein distance. Our method requires very minimal training data and yet achieves significant improvement in performance when compared to another statistical based technique. Initially, we evaluated the algorithm for English-Tamil transliteration. The transliteration accuracy of our algorithm is 91%, 96% and 99% for top-1, top-3 and top-8 transliteration candidates, when compared to 42%, 62% and 77% of the statistical system on a given standard test data. We have also extended the algorithm for English-Hindi and Hindi-English transliteration of named entities in the cross language retrieval scenario. Our algorithm proved to be effective in the cross language retrieval context and our systems have achieved state-of-the-art performance. Secondly, as mentioned earlier, most of the current CLIR systems use some form of external translation resources for translating queries. However if such resources are scarce or not available across any two languages, query translation becomes rarely feasible. In the second case, we address this particular issue in the context of CLIR across Indian languages. We propose an approximate, fuzzy string matching technique that exploits the presence of common origin words and similarity across the writing systems between Indian languages for query translation. We have implemented our technique for query translation on top of existing CLIR systems. Our method performs reasonably well for CLIR across all the six bi-lingual language pairs comprising of Hindi, Bengali and Marathi. We have also tested the significance of our obtained results and have shown that they are statistically valid.

Abstract

This thesis is an investigation into Indian language information access. The investigation shows that Indian language information access technologies face severe recall problem when using conventional IR techniques (used for English-like languages). During this investigation we crawled the web extensively for Indian languages, characterized the Indian language web and in the process came up with some solutions for the low recall problem. We focused our investigation on the loss of recall in monolingual and cross-lingual based IR and text summarization. The following are some of the major contributions of this thesis. We built a language focused web crawler that can optimally find and fetch pages of a given language using syllable based IR index model. We conducted a language focused crawl for a period of 6 months to analyze the characteristics and distribution of Indian language content on the web. We crawled the web for a continuous period of 2 years to collect a large corpus of Indian language web pages, which was used to build IR and summarization evaluation datasets. We showed that Indian language information access technologies that use state-of-the-art technologies used by English like languages, face low recall. We observed the recall loss to be relatively higher when the target language corpus is English. We came up with a semi-automatic method of converting proprietary encoded text into UTF-8 which otherwise was causing low-recall in document retrieval. We came up with a unied information access framework which can address the problems of Monolingual and Cross-lingual Information Retrieval and Text Summarization. We dened a single index model that can be used for many scoring functions used in our Monolingual and Cross-lingual IR and Summarization. This index model can help in identifying languages of a document, handling morphological variations, spelling variations, co-occurrence based query term expansion and weighted term dictionary translation. The score of each document or sentence (in the case of summarization) is viewed as a joint probability of multiple IR events occuring in sequence. Assuming each event to be independent of each other, we multiply the scores of each intermediate IR event, thereby weighting the query terms. For example, Monolingual IR with morphological variation handling is broken down as two sequential events. The first event is the generation of multiple morphological variations using syllable-term model, then multiplying these weights with the term score in each document. We modeled the stemming problem as an IR problem and came up with a syllable based model to retrieve and rank the morphological variations of a given word. This ordered set was used to generate a weighted query for retrieval of documents. We showed that, word spelling normalization is an essential component of Indian language information access systems. We proposed a linguistically motivated rule based approach and showed that this approach works better than the various approximate string matching algorithms. We modeled the problem of Dictionary based query translation as an IR problem. This helps us to automatically generate a weighted query when used in combination with query expansion techniques. We attempted cognate identication among Indian languages and evaluted their role in Telugu-Hindi CLIR using many approximate string matching algorithms. We found that Jaro-Winkler technique to identify cognates can provide reasonably good performance even without a dictionary for Telugu-Hindi CLIR. We also observed that using the available dictionary did not improve the performance much above the cognate based approach. Since most of the search queries are usually nouns, cognate based translation seems to work well. We modeled the problem of Text summarization as an IR problem. This helps us to overcome the sparseness problem of sentences while scoring them using the term collocation model. We showed that query independent scoring of sentences contribute a lot towards the quality of the summary. This type of scoring that we used for the first time in a query-focused summarization, helps in providing background information about a topic. This helps in improving readability and provides information to the user without losing the context. We modeled automatic transliteration of text from one language to another language as a sequence labeling problem. We used Conditional Random Fields to generate possible transliterations of text from one language to another. This model outperforms the HMM based model which is widely used. We dened and explored the problem of cross-lingual query based text summarization for Indian language queries. To the best of our knowledge this is the rst work in cross-language query based text summarization. We showed that the performance of a cross-lingual query focused summarizer does not degrade as much as a CLIR system

Abstract

With vast amount of data available electronically, there has been an ever increasing need to readily sort out and extract only the chief and pertinent sections from the data sources to present to the user. Time and space being critical constraints in this electronic era, it is indispensable to provide a mechanism to locate and browse required information quickly to avoid information overload. Automatic multi-document text summarization fulfills this need by presenting user with desired information in the form of a quick summary. Given a collection of documents related to same topic, the goal of multi document summarization system is to generate a short and concise summary that can be read in lieu of the original document collection. In multi-document summarization, sentence extraction is a critical phase in the formation of useful summaries. where the task is to pick a subset of sentences from the document cluster to form the summary giving an overall sense of the document’s content. Developing a principled sentence extraction mechanism that also performs empirically well is a big challenge in itself. This thesis presents a new sentence extractive summarization framework based on Information Loss. We treat summarization as a decision making problem. Given a set of documents, either to a human or system, the selection of few sentences as a representative to whole document set is a critical decision making problem. As per decision theory we derive a general extraction mechanism for picking sentences based on an ascending order of the expected risk of information loss. We propose to use an intrinsic loss function to compute this information loss and to make a decision on picking a sentence as a part of summary. Sentences and documents are considered as different text units and are represented by probabilistic language models to estimate their distributions. In this inferential setting we use entropy based intrinsic loss function (relative entropy) to measure the discrepancy between the sentence and document model. Relative entropy loss function measures how bad a sentence distribution is in modeling the documents distribution. By doing this we are able to capture the amount of information loss in picking a sentence to represent the whole document cluster. The selection of a sentence in summary is not by a set of features but only the measure of loss. A large document set is divided into smaller text units (sentences), each of which tries to approximate the document set variationally, yielding an overall variational approximation. Sentences which are the candidates of summary act as a surrogate for document set in a larger inference process. This decomposition strategy leads us directly to a new sentence extraction algorithm. With a simple redundancy identification and text reformulation mechanism, we come up with a lightweight summarizer to generate more informative summaries. The proposed algorithm generates the extracts on the fly without extensive computation or training which seem to be used in various state of the art algorithms. Furthermore, we consider different information theoretic divergence measures and loss functions to estimate loss between sentence and document distribution, and analyze their performance. In order to evaluate the performance of our approach, we have used DUC (Document Understanding Conference) and MSE (Multi-Lingual Summarization Evaluation) dataset that have been widely used in recent document summarization evaluations. We have applied ROUGE (Recall-Oriented Understudy for Gisting Evaluation) as the automatic summary evaluation metric which is the standard way of evaluation of summaries. It essentially calculates n-gram overlaps between automatically generated summaries and previously-written human summaries. A high level of overlap indicates a high level of shared concepts between the two summaries. Our overall results are the best reported on the DUC-2004 summarization task for all three metrics ROUGE-1 ROUGE-2 and ROUGE-SU4, and are the best, but not statistically significantly different from the best system in MSE-2005. Results on DUC-2007 dataset supports our results on DUC-2004 and MSE-2005. Our system is also substantially simpler than the previous best systems. Furthermore, we go beyond the traditional notion of generic relevance and incorporate a user factor as sentence extraction criteria. Here we treat summarization process as not only a function of the input text but also of its reader. We believe that a good summary should change in accordance to preferences of its reader. For this purpose we model the user in the proposed information loss based framework to extract user specific personalized summaries by creating web based profiles using the personal data available online. To evaluate personalized summaries, a controlled user-centered qualitative evaluation was carried out on news articles of science and technology domain. The results indi

Abstract

With the rapid spread of Indian language content on the web, user input oriented applications in Indian languages are also becoming popular. There is an increasing need for efficient and user friendly input interfaces to type in Indian languages. However, despite the obvious need and significance, text input has not been studied and researched so far, in the context of Indian languages. In this thesis, we study the problem of text input for Indian languages, by taking Telugu as the test case. Owing to the similarity among Indian languages, the results of this work can be applied with necessary changes, to other Indian languages as well. We have first classified data input systems in to four categories - keyboard layouts, input method editors, prediction systems and soft keyboards. In the first category, we have designed some keyboard layouts for Telugu, based on a set of design principles formed after a study of the relevant literature. We have then evaluated them based on the set of evaluation measures and concluded that our designs work better than the existing solutions, thereby providing efficient alternatives to the present day Telugu keyboard. In the context of input method editors, we have studied the different mappings available to convert between Indian languages and Roman script, and compared them with our new mapping, in an attempt to find out a mapping closest to human intuition. We have concluded that though there is no significant difference in performance with different mappings, Rice Transliteration Scheme has a better ease of remembrance compared to other mappings. We have studied the problem of text prediction for Indian language input and proceeded towards developing transliteration based prediction approach to text input in Telugu. We have proved that a simple approach like edit-distance based text prediction works very well as a text input method and offers a light weight and efficient system. Finally, we have worked on the design and evaluation of soft keyboards for Telugu. Our designs worked better than the existing soft keyboards for Telugu. Thus, we have successfully proposed efficient text input methods for Telugu which can be good alternatives to existing input methods.

Abstract

The present growth of digitization of books and manuscripts demands an immediate solution to access them electronically. This will enable the archived valuable materials to be searchable and usable by users in order to achieve their objectives. This requires research in the area of document image understanding, specically in the area of document image recognition as well as document image retrieval. In the last three decades signicant advancement is made in the recognition of documents written in Latin-based scripts. There are many excellent attempts in building robust document analysis systems in industry, academia and research labs. Intelligent recognition systems are commercially available for use for certain scripts. However, there is only limited research eort for the recognition of indigenous scripts of African and Indian languages. In addition, diversity of archived printed documents poses many challenges to document analysis and understanding. Hence in this work, we explore novel approaches for understanding and accessing the content of document image collections that vary in quality and printing. In Africa around 2,500 languages are spoken. Some of these languages have their own indigenous scripts in which there is a bulk of printed documents available in the various institutions. Digitization of these documents enables us to harness already available language technologies to local information needs and developments. We present an OCR for converting digitized documents in Amharic language. Amharic is the ocial language of Ethiopia. Extensive literature survey reveals that this is the rst attempt that reports the challenges toward the recognition of indigenous African scripts and a possible solution for Amharic script. Research in the recognition of Amharic script faces major challenges due to (i) the use of large number of characters in the writing and (ii) the existence of large set of visually similar characters. Here we extract a set of optimal discriminant features to train the classier. Recognition results are presented on real-life degraded documents such as books, magazines and newspapers to demonstrate the performance of the recognizer. The present OCRs are typically designed to work on a single page at a time. We argue that the recognition scheme for a collection (like a book) could be considerably dierent from that designed for isolated pages. The motivation here is therefore to exploit the entire available information (during the recognition process), which is not eectively used earlier for enhancing the performance of the recognizer. To this end, we propose self adaptable OCR framework for the recognition of document image collections. This approach enables the recognizer to learn incrementally and adapt to document image collections for performance improvement. We employ learning procedures to capture the relevant information available online, and feed it back to update the knowledge of the system. Experimental results show the eectiveness of our design for improving the performance of the recognizer on-the- y, thereby adapting to a specic collection. For indigenous scripts of African and Indian languages there is no robust OCR avail- able. Designing such a system is also a long-term process for accessing the archived document images. Hence we explore the application of word spotting approach for retrieval of printed document images without explicit recognition. To this end, we propose an eective word image matching scheme that achieves high performance in presence of script variability, printing variations, degradations and word-form varia- tions. A novel partial matching algorithm is designed for morphological matching of word form variants in a language. We employ a feature extraction scheme that ex- tracts local features by scanning vertical strips of the word image. These features are then combined based on their discriminatory potential. We present detailed experi- mental results of the proposed approach on English, Amharic and Hindi documents. Searching and retrieval from document image collections is challenging because of the scalability issues and computational time. We design an ecient indexing scheme to speed up searching for relevant document images. We identify the word set by clustering them into dierent groups based on their similarities. Each of these clusters are equivalent to a variation in printing, morphology, and quality. This is achieved by mapping IR principles (that are widely used in text processing) for relevance ranking. Once we cluster list of index terms that dene the content of the document, they are indexed using inverted data structure. This data structure also provides scope for incremental clustering in a dynamic environment. The indexing scheme enables eective search and retrieval in image-domain that is comparable with text search engines. We demonstrate the application of th

Abstract

Keywords: Personalized Search; Personalized Web Search; Web Search; Re ranking; User Modeling; Improving Web Search; User Profiling; Improving Ranking; Query Log Analysis; Simulated Feedback The main problem with web search is as follows : There is too much information available on the web; query words used by users often are confusing, ambiguous (a query “Java”can mean the Java island in Indonesia or the Java programming language), and some times are poor descriptors of information need (‘SBH” can mean “State Bank of Hyderabad” or “Syracuse Behavioral Healthcare” among others) ; users are often not patient enough to see long list of results given by search engines to find relevant information. It has been observed that users typically view top few results, usually top 5 or 10, some times 20 and much fewer times 30 and so on. In this scenario, web search can be made more useful, effective and less burdensome to users by - trying to infer what would be relevant for the current user for a given query considering individual users’ interests and provide those results on the top so that the user does not have to scroll down a long list of results. The problem of Personalized Search aims to customize search results according to each individual user for him to find the most relevant documents to him on the top by considering his idiosyncrasies. This would possibly satisfy them and help in finding relevant information easily and quickly. The major challenges for personalized search are two fold. The first is, modeling appropriate user context and learn a user model. The second is, how to utilize the user model to improve search accuracy. Another important challenge is evaluation of experiments. There are no standard and bench mark datasets available on which experiments can be performed. This makes comparison with earlier work in the litera- ture and replicating their results difficult. There are also no standard metrics available to effectively evaluate personalized search algorithms. Some commonly used metrics used to evaluate Information Retrieval systems are usually used. We propose three approaches for personalized web search. Our first approach is based on Statistical Language Modeling techniques. In spite of the progress made in language modeling and IR recently, there has not been much work applying language modeling techniques to personalized web search. In this approach, we learn a user model by capturing statistical properties of text from his past searches. We explored different contexts. The different contexts include using single word and two adjacent words (Simple N-Gram based method) and capturing relationship between query and document words (Noisy Channel model based method). Our second approach is based on Machine Learning algorithms which show an interesting and promising framework for learning user profiles. We make use of ranking SVM, a variation of the classification support vector machines for learning the user model. The above two approaches are a class of approaches that have exploited user feedback data either explicit or implicit. The third approach is another interesting approach, where, we attempt to model a particular user based on only past queries posed by corresponding user. The basic idea is to see if there is enough information available in just the previous queries without having to use teh clickthrough data made by the user. We have employed simple approaches based on language modeling to learn the user model from the previous queries of the user. We propose three approaches for personalized web search. Our first approach is based on Statistical Language Modeling techniques. In spite of the progress made in language modeling and IR recently, there has not been much work applying language modeling techniques to personalized web search. In this approach, we learn a user model by capturing statistical properties of text from his past searches. We explored different contexts. The different contexts include using single word and two adjacent words (Simple N-Gram based method) and capturing relationship between query and document words (Noisy Channel model based method). Our second approach is based on Machine Learning algorithms which show an interesting and promising framework for learning user profiles. We make use of ranking SVM, a variation of the classification support vector machines for learning the user model. The above two approaches are a class of approaches that have exploited user feedback data either explicit or implicit. The third approach is another interesting approach, where, we attempt to model a particular user based on only past queries posed by corresponding user. The basic idea is to see if there is enough information available in just the previous queries without having to use teh clickthrough data made by the user. We have employed simple approaches based on language modeling to learn the user model fr