Abstract

Hindi is a morphologically rich, free word order language. Parsing morphologically rich, free word order languages (MoR-FWO) is a challenging task. In this work we present our experiments which lead to state-of-the-art dependency parser for Hindi. We do a series of experiments exploring the role of different morphological and syntactic features in Hindi dependency parsing using two data-driven parsers, Malt and MST. With just 1500 sentences training data, we are able to build a dependency parser with state-of-the-art accuracy of 74.5% Labeled Attachment Score (LAS) and 90.1% Unlabeled Attachment Score (UAS). We also do a detailed error analysis and suggest possible remedies for these problems. During the course of experiments, we realized that some of the basic linguistic constraints were violated by these data driven parsers. We built a linguistically sound parser without compromising on the accuracy. Consider a simple linguistic constraint that a verb should not have multiple karta karakas (roughly, subjects) as its children in the dependency tree. We propose two approaches to handle this constraint and evaluate them on the state-of-the-art Hindi dependency parser. After building state-of-the-art inter-chunk dependency parser for Hindi, we also present our preliminary work on sentence level parsing of Hindi. We extract 1000 sentences, which are word level annotated, from a new multi-layered and multi-representational Hindi Treebank which is being developed. We do a step by step analysis of the importance of different features like, Part-Of-Speech, morph and chunk information for sentence level parsing of Hindi. We could achieve 75.4% Labeled Attachment Score (LAS) and 85.5% Unlabeled Attachment Score (UAS), which is the state-of-the-art performance for sentence level parsing. We also propose an new error detection tool for Treebank validation. Majority of the available error detection tools don’t work for small treebanks, or for the treebanks which are under development. But our tool handles the data sparsity issues and also helps in validation of the treebanks which are being developed. Based on the nature of errors, the proposed tool uses either rule-based or hybrid or both systems to detect errors. We present our results on Hindi dependency treebank data. With our preliminary experiments, we are able to detect 75%, 62.5% and 76.63% of errors in POS, chunk and dependency annotation respectively.

Abstract

Advances in medical device technology have resulted in a plethora of devices that sense, record, transform and process digital data. Images are a key form of diagnostic data, and many devices have been designed and deployed that capture high-resolution in-vivo images in different parts of the spectrum. Computers have enabled complex forms of reconstruction of cross-sectional/ 3D structure (and temporal data) non-invasively, by combining views from multiple projections. Images thus present valuable diagnostic information that may be used to make well-informed decisions. Computer aided diagnosis is a contemporary exploration to apply computers to process digital data with the aim of assisting medical practitioners in interpreting diagnostic information. This thesis takes up a specific disease: diabetic retinopathy, which has visual characteristics manifesting in different stages. Image analysis and pattern recognition have been used to design systems with the objective of detecting and quantifying the extent. The quantitative information can be used by the practitioner to stage the disease and plan treatment, track drug efficacy, or make decisions on course of treatment or prognosis. The generic task of image understanding is known to be computationally ill-posed. However adding domain constraints and restricting the size of the problem make it possible to attempt solutions that are useful. Two basic tasks in image understanding : detection and segmentation, are used. A system is designed to detect a type of vascular lesion called microaneurysm, which appear in the retinal vasculature at the advent of diabetic retinopathy. As the disease progresses it manifests visually as exudative lesions, which are to be segmented, and a system has been developed for the same. The developed systems are tested with image datasets that are in the public domain, as well as a real dataset (from a local speciality hospital) collected during the course of the research, to compare performance indicators against the prior art and elicit better understanding of the factors and challenges involved in creating a system that is ready for clinical use.

Abstract

In Very Long Instruction Word (VLIW) processors, based on the available instruction-level parallelism in programs, compilers schedule operations onto different functional units. By assuming all the functional units of same kind and having the same latency, the conventional list-scheduling algorithm selects the first available (free) functional unit to schedule an operation. But, in advanced process technologies due to process variation, functional units of same kind may have different latencies. In such situation, conventional scheduling algorithms may not yield good performance. Process variations in components like adders, multipliers, etc., of different Integer Functional Units (IFUs) in VLIW processors may cause these units to operate at different speeds, resulting in non-uniform latency IFUs. Pessimistic/conservative techniques dealing with the non-uniform latency IFUs may incur significant performance and/or leakage energy loss. In this work, We propose three process variation-aware compile-time techniques to handle non-uniform latency IFUs. In the first technique, namely `turn-off', we turn of all the process variation affected high latency IFUs. In the second technique, namely `on-demand turn-on', we use some of the process variation affected high latency IFUs by turning them on whenever there is a requirement. Our experimental results show that with these techniques, the non-uniform latency IFU can be tackled without much performance penalty. The proposed techniques also achieve significant reduction in leakage energy consumption as some of the IFUs are turned of. In variation affected situation, conventional scheduling algorithms may not yield good performance. We propose third technique, namely `mobility-list-scheduling' algorithm to schedule operations on non-uniform latency functional units and compare our algorithm with the conventional list-scheduling algorithm.

Abstract

Search engines have become a popular medium for people to fulfill their information needs. Studies on search engines reported a high misspelling rate of queries: around 10-15% queries are erroneous. The detection and correction of spelling errors has become an integral part of computer applications since the very beginning; even before the search engines exist. Research on spelling correction has begun in early 1960s. The research focused on correcting the errors in word processors, specifically where errors occurred in well formed sentences. Search engine queries are very short in length; they have about two to three words on average. Moreover, considerable amount of search queries contain valid but Out Of Vocabulary(OOV) terms. Due to this nature of search queries, correcting search engine queries is more complex than correcting errors in word processors. Research on spelling correction for search engines queries began in early 2000s. But, most of the techniques heavily relied on query logs with the intuition that, People who can’t spell a term correctly can be helped by the people who spell it correctly. Moreover, most of the techniques explored till date depend on linguistic resources, training data or hand crafted rules. In this thesis, we explore ways of correcting spelling errors without relying on query logs or linguistic resources. We focused on correcting two types of errors: 1.Isolated-word errors and 2.Context dependent word errors. Our approach to the above two types of errors is handled using a document collection of a search engine. Our approach addresses correction of isolated-word errors in two steps. In thefirst step, candidate suggestions are generated using an Information Retrieval approach. We explain the reasons for failure of traditional tf-idf (term frequency inverse document frequency) ranking and propose to use df (document frequency) instead of idf in the ranking. In addition, we demonstrate the importance of word frequency in the collection. In step two, candidate suggestions are re-ranked using a new string similarity measure that uses the length of the longest common substrings occurring at the beginning and at the end of the words. We obtained very impressive results by re-ranking candidate suggestions using the new similarity measure. The accuracy of first suggestion is 92.3%, 90.0% and 83.5% for Dutch, Danish and Bulgarian language datasets respectively. The system developed for isolated-word errors is extended to address context dependent errors. In case of context dependent errors; we consider each term in query to be a isolated-word and retrieve candidate suggestions for each of those query terms. Candidate suggestions retrieved for all query terms are used to construct a directed acyclic graph with each suggestion as a node and an edge between suggestions of two consecutive query terms. The longest path, computed by adding the weights of its constituent edges, in the graph yields the best correction candidate to misspelt query. We explore how query expansion and pseudo relevance feedback techniques help in improving the suggestion accuracy of the system. Our approach to context dependent errors obtained a first suggestion accuracy of 75.6%, 80.5% and 85.5% for Bulgarian, English and Dutch language data sets respectively. In this thesis we show that, search queries can be corrected even without using any query logs. In order to keep track of newly evolving words we rely completely on document collection of search engine. Moreover, we demonstrate that, tf-df ranking works better than tf-idf when dealing with character n-grams. The results prove that pseudo relevance feedback techniques can be of great help while correcting the spelling errors in search queries.

Abstract

The amount of textual and multimedia information on world wide web has been increasing many folds every year. A user seeking information on the web is often overloaded with colossal amount of related documents by search engines and information retrieval systems to satisfy his information need. In this context, it has become increasingly important to develop information access systems that provide focused and precise answers to the user. Text Summarization is a popular information access solution for information overload problem. Internet allows its users to follow any popular and temporal topic on web. A temporal topic has a lot of publishing sources and the user cannot handle with the huge amount of raw information from news aggregators, blogs. In such scenario it is not sensible to wait for the topic to complete to produce a summary, nor does it make sense to produce an overall summary at every time interval. In this thesis we study a variant of text summarization, “Progressive Summarization”, focusing only on relevant and novel information, and produce an informative, non redundant summary of the topic. We provide progressive summaries at regular time intervals that helps in updating the user knowledge about the topic. In this work we focus only on extractive methods of summarization, where only the text units from document collection are used in producing a summary. Sentence is considered as a basic text unit for the summary. Extractive summarizers generally follow a sequential framework, that include Pre-processing of text for sentence boundary identification and extraction, a Feature Extraction stage where several statistical, linguistic and heuristic models are employed to estimate sentence importance, Sentence Ranking stage that estimates sentence importance through weighted linear combination of the features and finally Summary Extraction, during which a subset of ranked sentences are selected into summary. The most important factor in extracting important items for a progressive summary, is the identification of novel information. Progressive summarization requires differentiating between Relevant and Novel Vs Non-Relevant and Novel Vs Relevant and Redundant information. Since the existing features are successful in capturing only the relevance, We devise multiple new features (NF, NW, HKLID) to capture novelty of a sentence along with its relevance. We build alternative methods to incorporate novelty in conventional summarization framework. We devise a new re-ranking measure, Proximity Re-ranking (ProximRank), that computes the rank of a sentence based on the relevant novelty of its surrounding sentences. We model novelty detection in the context of progressive summarization as an information filtering task. Sentences that possibly contain prior information are filtered out from summary by creating a Novelty Pool (NP). These methods are successfully related to different stages of summarization and evaluated against each other to find the best. In this thesis we also discover the importance of prepositions in determining the salience and relevance of a sentence to the topic. Also, we use a machine learning technique (Regression) to estimate sentence importance from its feature vector. Thus we overcome the problem of determining ideal weight combination that takes ample amount of experiments and human judgment when several features are used. The techniques described in this thesis are used in building a progressive summarization system (Siel 09) that outperformed all other 43 participating systems in Text Analysis Conference (TAC 2009) in manual evaluations.

Abstract

Coloring is an abstraction for partitioning a set of objects into a few independent sets. The notion of independence and the associated coloring rules vary from context to context. In the simplest case, adjacent vertices in a graph are required to receive different colors ( proper coloring). In parallel scientific computing, a proper coloring is used to identify computational subtasks that can be performed concurrently. A proper coloring of vertices of a graph G is acyclic if every 2-colored subgraph of G is acyclic. The acyclic coloring problem arises in the context of matrix partitioning for the estimation of the Hessian matrix associated with numerical optimization problems. The smallest number of colors required to acyclically vertex color a graph G is called its achromatic number and is denoted by a(G). Finding the achromatic number, a(G), of a graph(G) is an NP-hard problem. Several approaches have been used to solve this problem. Some researchers looked at finding the achroamtic number of family of graphs such as planar graphs, planar graphs with large girth, 1- planar graphs, outerplanar graphs, and d-dimensional grids. Another direction of study is finding upper bounds on a(G) in terms of the maximum degree of G. Alon et al. used problabistic arguements and showed that it is possible to acyclically color any graph of maximum degree D , with O(D^{4/3}) colors. Fertin et al. designed a polynomial time algorithm to find upper bounds on a(G) in terms of D. This thesis is dedicated to designing deterministic algorithms to reduce upper bounds on a(G) for bounded degree graphs. By extending/generalizing ideas of Skulrattanakulchai we reduce upper bounds for a(G) for family of graphs of maximum degree five from 9 to 8 and, for the family of graphs of maximum degree 6 from 15 to 12 respectively. We show above result by extending a partial coloring by one vertex at a time. Let v be the vertex that we color during an iteration. During this process, in some scenarios it is required that we recolor some of the vertices already colored so as to make a color feasible for the vertex v, the vertex we try to color. However, note that this recoloring, if required, is limited to the neighborhood of the neighbors of v in all cases. We have presented a polynomial time algorithm to acyclically color the vertices of graphs with maximum degree D using D^2+2D+2/3 colors. The algorithm improves the state-of-the-art by a factor of 3/2 to the best known result till date. Our algorithm is greedy, and at each time we observed up to 3-neighborhood of a vertex even though recoloring is done up to 2-neighborhood of vertex.

Abstract

In recent times the discovery of several ncRNA (non coding RNA which does not code for proteins but directly performs structural and catalytic functions) genes have drawn progressively greater scientific attention to RNA studies and drawn renewed attention to the hypothesis of “RNA world” where RNA potentially has served the dual role as both the genetic material and as the principal biocatalyst. The non covalent interactions, which are responsible for folding of highly flexible and negatively charged sugar phosphate backbone of RNA molecules are far less understood, compared to those involved in protein folding. These interactions are relatively more complex than in regular DNA double helices, which are held together by canonical A:T and G:C Watson-crick base pairing, which is suited for structure and function of DNA molecules. In contrast, single stranded RNA molecules display a richer variety in base pairing patterns, which govern their folding on themselves into complex dynamic structures. Non canonical base pairs, which constitute ~ 40% of base pairing interactions in RNA (Leontis et al, 2001) have been recognized for their role in molecular recognition including proteins, ligands and metal ions and mediating numerous tertiary interactions. (Westhof et al, 2000) High concentration of charges has long since been identified as one of the major features distinguishing nucleic acids from proteins, in terms of their structure, activity and folding dynamics. Neutralization of the negatively charged backbone phosphate groups, involving metal counter ions, has e. g., been shown as one of the primary events in RNA folding in vitro.(Misra et al, 2003) However, there is now a growing acceptance of the fact that, apart from phosphates and metal cations, the nucleobases themselves can acquire charges through protonation. This development indicates a major change in paradigm, particularly with respect to the role of metal cations in nucleic acid folding and catalysis. It may be noted in this context, that the role of nucleobase protonation in nucleic acids goes much beyond general purpose neutralization – something which the metal cations ubiquitously perform. Several studies have pointed towards more specific roles, including the mediation of global conformational changes in DNA as well as in RNA structures, whereby the protonation of nucleobases in specific macromolecular contexts may be important for defining their catalytic roles and folding pathways. In general, nucleobases do not get protonated at physiological pH, since the pKa values for imino nitrogens are ~ 3.5 and 4.2 for adenine and cytosine respectively, and ~9.2 for guanine and uracil. (Saenger, 1984) It is thus important to understand the basis of context dependent pKa shift which leads to protonation of nucleobases in different cases. Based on their occurrence contexts and functional features, protonated nucleobases identified in known structures have been divided into two classes, (Bevilacqua et al, 2005) viz. Class I, for which the loaded proton is sequestered in hydrogen bonding between paired bases, and class II sites, where the proton is not directly involved in base pairing. Of these, we have investigated Class I type of interactions. For the detection of these base pair types, we have extended available methods (Das et al, 2006) of base pair detection for detecting putative protonated base pairs and understand their contexts. We have also used advanced quantum chemical methods, both to confirm their occurrence as well as to study their geometries and stabilities. We have used a non redundant dataset of selected highresolution RNA crystal structures (PDB ids given in Appendix) from Protein Data Bank (PDB) to analyze the geometries and analyze the occurrence contexts of base pairs belonging to protonated base pair. Out of twelve RNA base pair geometric families described by Leontis-Westhof classification scheme (Leontis and Westhof, 2001), we have identified eighteen possible protonated base pairs spanning eight base pair families. In addition, we also report a putative base pair on the basis of modeling. Out of nineteen distinct possibilities studied in this work, as many as six instances needed hypothesis driven manual intervention for addressing ambiguities; which arouse due to variety of factors , and which were resolved to different degrees using quantum chemical methods. Out of nineteen distinct geometries studied in this work, nine base pairing geometries are new, and not previously being detected in nucleic acid structures. These base pairs have potential to nucleate higher order structures and participate in tertiary interactions joining distant regions in RNA structures. The interaction patterns of protonated base pairs are highly diverse, with gas phase optimized interaction energies in the range from -24 to -49 Kcal/mol. The high interaction energy is generally observed for

Abstract

In the emerging web databases and e-commerce scenario, information systems have to meet intensive information requirements from a large number of users. These information systems receive both update transactions (UTs) and read-only transactions (ROTs). A UT contains both read and write operations and an ROT contains only read operations. Designing efficient protocols to process ROTs is a research issue. There are three aspects for designing a concurrency control protocol for processing ROTs: correctness, data currency and performance. The protocol should process transactions by satisfying serializability criteria. Also, the protocol should process transactions without any data currency issues. Note that “data currency” is another important aspect of the protocol. A protocol should process the ROTs without missing the effect of any preceding UTs. Finally, the protocol should give high performance. If both the UTs and ROTs are processed with the popular two-phase locking (2PL) protocol, the performance degrades with the data contention as the UTs have to wait for ROTs and vice versa in case of a conflict. On the other hand, it can be noted that, the 2PL processes ROTs without any correctness and data currency issues. So, efforts are being made to propose improved protocols by exploiting the special property of ROT that “it does not modify the data” and by compromising on correctness and data currency. There are efforts to improve the performance by processing ROTs with multi-version based approaches, at lower isola tion levels, and by compromising correctness. One of the popular protocols is snapshot isolation (SI)-based protocol, in which an ROT reads the snapshot of the database ignoring modifications done by preceding UTs. In SI-based protocols, even though performance is improved, both correctness and data currency aspects are compromised. The 2PL protocol suffers from the performance problems and SI-based protocol suffers from both correctness and data currency problems. So, the research challenge is to develop efficient concurrency control protocols to improve the performance of ROTs without correctness and data currency problems. In this thesis, we have proposed speculation- and semantics-based protocols for processing ROTs that provide high performance and process transactions without any correctness and data currency issues. Speculation-based protocols have been proposed in the literature to improve the performance of UTs. Basically, under speculation, a transaction carries out multiple executions by reading the uncommitted values of preceding conflicting transactions. A transaction retains one of the speculative executions based on the termination decisions of preceding transactions. Speculation improves the parallelism but requires extra processing resources. Also, the number of speculative executions and number of object versions explode with data contention. In this thesis, the notion of speculation is being extended to propose improved protocols for processing ROTs. In the proposed protocols, ROTs are processed with speculation and UTs are processed with 2PL. The ROTs access after-images produced by UTs and carry out speculative executions. As a result, the following advantages have been identified: (i) an ROT can carry out speculative executions and commit independently based on the status of preceding UTs, and (ii) the number of speculative executions and data versions is significantly reduced. We have proposed two speculation-based protocols for processing ROTs. In the synchronous approach, the speculative executions of an ROT can be carried out in a synchronous manner, i.e., all the speculativeexecutions of an ROT are carried out at the same pace. In the asynchronous approach, the speculative executions of an ROT are carried out at different pace. It was observed that asynchronous approach improves the performance over the synchronous approach. In the proposed speculation-based protocols for ROTs, UTs follow 2PL and are made to wait if they conflict with concurrent UTs and ROTs. To reduce the waiting time of UTs, we have proposed a semanticsbased approach by proposing the notion of “compensatability”. In this protocol, a UT need not wait for an ROT, if the computation of that ROT is compensatable. However, the compensatable ROT has to perform compensating computations before its commitment. We have proposed enhanced protocols by extending semantics to the proposed speculation-based protocols. The proposed protocols bring significant benefits. The ROTs are processed without violating correctness and compromising data currency. The performance results show that the proposed protocols significantly improve the performance over 2PL and SI-based protocols with manageable extra processing resources.

Abstract

The detailed molecular level understanding of physicochemical interactions responsible for the overall architecture and dynamics of functional RNA molecules embodies a major challenge to the scientific community. The 3D architecture of RNA is mainly influenced by various non covalent interactions such as hydrogen bonding and stacking interactions between the nuleobases, interactions involving the sugar and phosphate backbone and interactions involving the solvent molecules and metal cations. A proper description of all these non covalent interactions and their involvement in various recurrent structural motifs help us to understand the physicochemical principles which are crucial for the complex structure, folding and functional dynamics of RNA molecules. Current approaches in mining are constrained by their dependence on identification of strong hydrogen bonded canonical and noncanonical base pairs and motifs and are thus restricted by conventional stability benchmarks. Collections of several weak, 'non-base specific' interactions, found in structurally, as well as functionally, important regions such as A-minor motifs, tetraloops and in various tertiary interactions are often not detected by these algorithms. In this work, we have used a comprehensive BOTTOMUP approach towards understanding structure. This task has been achieved by studying 'weak' and 'other than stable base pairing' contacts from a reduced redundancy dataset of functional RNA molecules by applying a python based in house developed tool INCAR (Inter-Nucleotide Contact Annotator in RNA), which efficiently manages time and space to capture, categorize and suitable annotate all inter-nucleotide non-covalent interactions such as hydrogen bonding and ion mediated contacts. A new automated centroid based approach which doesn't require a priori knowledge on standard base pair geometries and atoms involving in hydrogen bonding is designed for detection of glycosidic bond orientation of various standard and nonstandard base pairing geometries ( bifurcated, single hydrogen bonded, deformed).Results are with high specificity with out compromising on sensitivity with respect to currently analyzed benchmarks. Other key features include a) Classification of bifurcated geometries, b) Classification of higher order interactions such as triplets, quartets etc. based on spatial topologies. c) Identification of various structural elements such as platforms, bulges, loops, stems etc. We have identified a new structurally important AA-Diloop and an interesting tertiary interaction in a ribozyme involving weak and 'non-base specific' contacts. In addition, INCAR has applied in several areas such as comparative analysis to investigate the structural conservancy of a class of sequence variants, investigating motifs in terms of 'non-base specific' contacts and dynamic structural analysis of RNA molecules. A repository has been developed for (http://web.iiit.ac.in/~ramsagar.bpg08/incardataset) archiving details of the analyzed RNA structures using INCAR.

Abstract

Text summarization is the process of distilling the most important information from a source to produce an abridged version for a particular user or task. That is restating of the main ideas of the text in as few words as possible in a pertinent format. Automated text summarization has drawn a lot of interest in the natural language processing and information retrieval communities in the recent years due to the rapid growth of the World Wide Web and electronic information services. Information is becoming available on-line at an incredible rate but no one has time to read everything. Hence, the technology of automatic text summarization is becoming indispensable for dealing with this problem. With the growing need for good summarization systems, summarization evaluation plays an important role in their creation. Evaluation has become one of the ongoing issue in this field of automatic text summarization. Human judgement often has wide variance on what is considered a ”good” summary, which means that making the evaluation process automatic is particularly difficult. Manual evaluation like ’Likert Scale rating’, ’Pyramid Evaluation’ can be used, but this is both time and labor intensive as it requires humans to read not only the summaries but also the source documents. Hence, there is an urgent need for developing automatic evaluation metrics to fasten the process of evaluating summarization systems which can result in better summarizing algorithms. Summaries can be evaluated based on two properties : content and form. The evaluation of content is called ’Content Evaluations’ and that of form is called ’Readability Evaluation’. There are various manual evaluation metrics for content evaluation including ’Likert Scale rating’, ’Pyramid Evaluation’ and ’Content Responsiveness’. For Readability evaluations a ’Likert scale rating’ is used by human experts to rank summaries. In the context of automated metrics for evaluation of summary quality, content evaluations have been presented through the last decade and continue to evolve. However, a careful examination of readability aspects of summary quality has not been as exhaustive. In this thesis, we dissect readability into 5 parameters and automate the evaluation of readability based on some of these parameters. Readability of a summary is usually graded manually on five aspects: grammaticality, coherence, focus, referential clarity and nonredundancy. We explore alternative evaluation metrics for grammatvviicality, focus and coherence. By defining grammaticality as a degree of acceptance, we use language models built over shallow features such as parts-of-speech (POS) and chunk tags to estimate the acceptability of a sentence to be a part of the summary. To capture the coherence in a summary, we use lexical chains and compute semantic relatedness of the sentences within the summary. We claim that the focus of a summary is a characteristic dependent on the cohesiveness of a summary, due to which, any metric for coherence should be a good indicator of focus. Our approaches to capture grammaticality, focus and coherence are able to strongly correlate with manual ratings. Overall, in context of query focused multi-document summaries, we observe that none of the five aspects of readability are independent of each other, and hence by addressing the individual criteria of evaluation, we aim to achieve automated appreciation of readability of summaries.