Abstract

Modelling and simulation of a robot on uneven terrain is of importance as it provides a basis to know about the robots position and its state. In this work we present a simulation framework and dynamic state space realisation for evolution on uneven terrains for a wheeled mobile robot such as a synchronous drive robot. The framework lends itself as a tool capable of solving various problems, such as forward kinematic based evolution, inverse kinematic based evolution, path planning and trajectory tracking. This framework becomes particularly useful when we understand that the evolution problem (and hence the various associated problems based on evolution) is particularly challenging on uneven terrain. Specifically it is entailed to bring in the contact constraints posed by the interaction of the wheel and the ground as well as the holonomic constraints as the problem is formulated in a DAE setting (Differential Algebraic Equation). The problem becomes all the more crucial as vehicles moving on uneven terrain are becoming the order of the day. Nonetheless there has not been much literature that deals in length the various aspects that go into the framework. This work elaborates on the various aspects of the framework, presents simulation results on uneven terrain, where the vehicle evolves without slipping and also presents substantial quantitative analysis in regard to wheel slippage. Dynamic model which ensures no slip and permanent contact on uneven terrain and which satisfies holonomic and non holonomic constraints simultaneously is also proposed. For a 3 wheeled WMR a generalised state space is derived and is used to find the dynamic equations of motion as a second order constrained Differential Algebraic Equations (DAE). Dynamic equations are represented using lagrangian formulation where all the matrices and constraints are represented in the generalised state space representation. Constraint satisfaction is achieved by using Baumgarthe stabilisation for the equivalent second order holonomic and non holonomic constraints and in calculating the Lagrangian multipliers as part of the DAE which is unique. The main contributions of the thesis is to realise a system for uneven terrain navigation and to simulate it using both kinematic and dynamic equations to get feasible paths on uneven terrains.

Abstract

Crystal structures of drug molecules complexed with their target RNAs are being widely studied today, particularly in the context of the importance of the ribosome as a potential drug target, and the notable discriminatory ability of recognition and binding of cognate ligands by RNA aptamers. However, the molecular level understanding of the role of ligand binding interactions in RNA functions, require the analysis of stabilities and interaction energies of RNA-drug interactions. The present work deals with a detailed analysis of the structural and energetic features of these drug-nucleobase pairs and pseudo pairs using quantum chemical methods.
Previous studies on RNA base pairing interactions have demonstrated that gas phase quantum chemical calculations can be used to analyze the intrinsic stabilities of non-covalent interaction in RNA. In line with these studies, here we report the results of analysis of geometries and interaction energies of base pairs and pseudo pairs observed in experimental structures of different classes of drug molecules interacting with RNA, which include aminoglycosides, oxazolidinones, tetracyclines and lincosamides. Geometry optimizations of studied nucleobase-drug pairs have been carried out at B3LYP/6-31G (d,p) level, while the interaction energies have been evaluated at the RIMP2 (using aug-cc-pVDZ and RIMP2/aug-cc-pVTZ basis sets which has been further extrapolated to CBS limit), DFT and DFT-D (using TPSS functional and aug-cc-pVDZ basis set). Further, interaction energy decomposition has been carried out using Morokuma method performed at the HF/6-31G (d,p) level. Our studies show that on full geometry optimization, these pairs tend to achieve greater stability compared to that in their respective experimental geometries. The gas phase interaction energies of RNA-drug pairs compare well with those of standard Watson Crick base pairs. Except for the Puromycin - Guanine pair involving sugar edge-sugar edge interaction, the Hartree Fock component dominates the interaction energies in all fully optimized geometries. The comparison of EDFT and EDFT-D interaction energies suggest that the interaction between the RNA-Drug pairs is further stabilised due to dispersion.
In context of RNA-drug interactions involving multiple bases forming base pairs with single drug molecule, we also report detailed studies on the discriminative ability of the theophylline RNA aptamer with respect to its cognate ligand. Unlike in the context of purine riboswitches observed earlier, cooperativity between different RNA-base pairs is found to be negligible in multiple base-ligand interactions studied in case of Theophylline interacting with its aptamer. In addition, the binding affinities of theophylline, caffeine and theobromine with the theophylline aptamer correlates well with the experimental data with high binding affinity for theophylline and least for caffeine.

Abstract

Information explosion on the internet popularly known as the web has led to a phenomenon of the user unable to find the information relevant to him or her. There is plethora of information available and thousands of pages are being added everyday. Hence more and more information is available on each and every subject. Hence, it has become increasing difficult for users to remain up to date on one’s own areas of interest. This has increased the need for indexing of documents drastically. Indexing can take place at the user end or at the search engine end. However traditionally, indexing used to take place at the middle level by authorities or librarians. With the vast amount of content available on the internet, it is practically impossible for any authority to index the data. This led to the evolution of social bookmarking systems where users are able to maintain individual collections of resources and index them using tags for retrieval purposes. This model has evolved into a collaborative model where users share their resource collection and tags with others leading to the emergence of collaborative tagging systems. These systems are also referred to as “Folksonomies”. Due to the flexibility and ease of use, the usage of these systems has increased very rapidly. Many tagging systems like Delicious, Flickr, Bibsonomy, Citeseer etc. have evolved and became very popular. This has created a new form of rich user generated content which can be exploited to good use in a wide range of applications. The data in these systems typically consists of three dimensions - resources, users and tags. In this thesis, we have focused on some of the basic metrics for extracting information from folksonomies - Tag weight and Tag similarity and the usage of them in applications like Tag Search and Web document summarization. First, we propose a model of tag weighting extending the traditional Vector Space Model for term weighting. We show how tag weighting can be used in tag similarity and also show how we compute tag similarity. We evaluate our proposed tag similarity measure by grounding them against semantic lexicon WordNet using correlation measures - Kendall’s tau and Spearman’s rho correlation coefficients. We further demonstrate the application of our tag weighting in summarization of web documents. We have proposed a summarization feature based on tag weights which can be used with some of the existing features in generating summaries. We have evaluated the generated summaries by comparing them with manually generated summaries to find how close they are to the manual summaries and hence more readable. Further, we also demonstrated the application of our tag similarity in tag search. Our experimental results proved that our proposed approaches are able to achieve good improvement over our baselines.

Abstract

A question may be either a linguistic expression used to make a request for information, or else the request itself made by such an expression. This information may be provided with an answer. Asking questions is a fundamental cognitive process that underlies higher-level cognitive abilities such as comprehension and reasoning. The ability to ask questions is the central cognitive element that distinguishes human and animal cognitive abilities. Questions are used from the most elementary stage of learning to original research. Question Generation (QG) is the task of automatically generating questions from various inputs such as raw text, database, or semantic representation. Ultimately, QG allows humans, and in many cases artificial intelligence systems, to understand their environment and each other. Research on QG has a long history in artificial intelligence, psychology, education, and natural language processing. The present work describes automatic Question Generation Systems that take natural language text as input and generate questions of various types and scope for the user. Our aim is to generate questions that assess the content knowledge that a student has acquired upon reading a text rather than vocabulary or grammar assessment or language learning. In this work, we have described two automatic question generation systems. Both these systems factor the QG process into several stages, enabling more or less independent development of particular stages. The QG system, described in chapter 2, generates questions automatically using discourse connec- tives for different question types. We described an end-to-end system that takes a document as input and outputs all the questions for selected discourse connectives. The selected discourse connectives include four subordinating conjunctions, since, when, because and although, and three adverbials, for example, for instance and as a result. Our system factors the QG process into two stages: content selec- tion (the text selected for question generation) and question formation (transformations on the content to get the question), Question formation module further has the modules of (i) finding suitable question type (wh-word), (ii) auxiliary and main verb transformations and (iii) rearranging the phrases to get the final question. The system has been evaluated for syntactic and semantic soundness of the question by two evaluators. The overall system has been rated 6.3 out of 8 for QGSTEC development dataset and 5.8 out of 8 for Wikipedia dataset. We have shown that some specific discourse relations are important, such as causal, temporal, result, etc., than others from the QG point of view. This work also shows that discourse connectives are good enough for QG and that there is no need for full fledged discourse parsing. We have generated questions using discourse connectives paving way for medium and specific scope questions. Cloze question generation (CQG) system, described in chapter 3, takes a document as input and outputs the important cloze questions. Our system factors the CQG system into three stages: (i) Sen- tence selection, (ii) Keyword selection and (iii) Distractor selection. A domain dependent approach is described for the distractor selection module of CQG system. The system is implemented for and tested on examples from the cricket sports domain. The system is evaluated using the guidelines described in this work. The accuracy of the distractors is 3.05 (Eval-1), 3.14 ((Eval-2) and 3.5 (Eval-3) out of 4. Main focus being on distractor selection, we have shown the influence of domain on the quality of distractors.

Abstract

After microprocessor clock speeds have levelled off, general purpose computing on Graphics Pro- cessing Units (GPGPUs) has shown some promise for the future High Performance Computing (HPC). This can be largely attributed to the performance per unit cost, performance per unit watt and CUDA, a programming model for GPU. For instance, for under $400, one can buy a GPU that can deliver more than a TFLOP of computing power while requiring less than 250 Wof power. It is therefore no surprise that 3 out of the top 5 supercomputers [71] use GPUs along with other computing elements. However, this comes at the expense of reinterpreting applications in a highly multithreaded manner. GPUs are good at exploiting massive data parallelism, and are well-suited for applications with regular memory access patterns and high arithmetic intensity. For several regular applications, this approach has been very successful [63, 48]. For example for dense matrix multiplication GPUs can perform upto 838GFlops/s. However, most applications in high performance computing are irregular in nature. Examples include list ranking [81], graph algorithms [53], sparse matrix computations [22], among others. Viability of using GPUs for accelerating these irregular workloads needs to be explored. In recent works, efforts are on to arrive at efficient implementations of irregular algorithms on the GPUs [81, 6], and on other recent multi-core architectures such as the Cell [4, 59, 51]. In this thesis we first accelerate Lanczos method for large sparse matrices, an algorithm for finding eigenvectors corresponding to least eigenvalues. We then use this in accelerating two important ap- plications namely spectral graph partitioning and image segmentation. For these applications our GPU imlementation shows a speedup upto 2.9 and 3.27 respectively when compared to highly optimized Intel MKL library implementation on multi-core. We then investigate sparse matrix routines from sparse blas level 2 and level 3. The investigated routines include sparse matrix multiplied with a dense vector / sparse matrix / dense matrix. Sparse Matrix Vector Multiplication (spmv) is the heart of many numerical computations and is notorious for sustaining low fractions of peak performance. This operation finds applications in solving system of linear equations, finding eigenvalues of a matrix to name a few. spmv becomes bottleneck in many of these methods. spmv performance is limited by the available memory bandwidth due to the low computation per data accessed. spmv further suffers from the memory access and thread execution constraints posed by the gpu and also from load balancing among threads. To address some of these challenges we proposed a run-time methodology to choose the right data structures to represent sparse matrices. Our methodology uses parameters that attempt to balance the load amongst threads and also identify the right kind of representation to use for storing the sparse matrix. Experimental results show that our technique improves the performance of the spmv kernel by an average of 25% when compared to the library implementation of spmv on GPU (cusp library). Sparse matrix-sparse/dense matrix multiplications, spgemm and csrmm, among other applications find usage in various matrix formulations of graph problems. GPU based supercomputers are presently experiencing severe performance issues on the Graph-500 benchmarks, a new HPC benchmark suite focusing on graph algorithms. Considering the difficulties in executing graph problems and the duality between graphs and matrices, computations such as spgemm and csrmm have recently caught the attention of HPC community. These computations pose challenges such as load balancing, irregular nature of the computation, and difficulty in predicting output size. It is even more challenging when combined with the GPU architectural constraints in memory accesses, limited shared memory, and thread execution. To address these challenges and perform the operations efficiently on a GPU, we evaluate three pos- sible variations of matrix multiplication (Row-Column, Column-Row, Row-Row) and perform suitable optimizations. Our experiments indicate that the Row-Row formulation outperforms the other formu- lations. Our row-row formulation of the spgemm operation performs up to 6x faster when compared to the highly optimized multi-core implementation in Intel MKL library. In a similar fashion, our GPU csrmm operation performs up to 5x faster when compared to corresponding implementation in the cusparse library, which outperforms the Intel MKL library implementation.

Abstract

In the last few decades there has been a tremendous increase in the infrastructure related to computing and collection of data. Tools such as sensors for moving objects, GPS (global positioning systems), satellite data and imagery, internet and web technologies are some of the many entities which have led to an exponential increase in the amount of data being collected these days. According to a recent study (http://tinyurl.com/2frbdeu), the total volume of electronic data stored worldwide reached 1.2 billion terabytes (a growth rate of 62% from 2009). At the same time there has also been an increase in the computing power of our systems. In particular, this information overload calls for new methods for querying large spatial datasets, since users are often not interested in merely retrieving a list of all data items satisfying a query, but would, instead, like a more informative “summary” of the retrieved items.
Orthogonal range searching has been a widely studied problem in the field of computational geometry and databases. In this problem, we need to preprocess a set S of n points lying in a d-dimensional space into a data structure so that given an axis-aligned orthgonal query box q (i.e. a rectangle and a cuboid in 2- and 3- dimensional space, respectively), we need to efficiently report (or count) the points of S lying inside q. For example, the set S could represent all the villages of India. A natural query would be to specify a region (which could be a district, a state etc.) on the map and to find out all the villages lying inside it. This is nothing but a range query. Traditionally, the researchers in computational geometry have been interested in building solutions for this problem which aim at coming up with worst-case efficient query time solutions, i.e., ensuring that the query time is low for all possible values of the query. Range trees are an extremely popular example. On the other hand, the researchers in database community try to come up with practical solutions which are optmized to work well for the average case queries (with the assumption that the worst-case query will occur rarely). R-trees and R*-trees are commonly used structures in the database literature.
In many applications a more general form of a range searching problem arises: Here the points in S come aggregated in disjoint groups and of interest are questions regarding the intersection of q with the groups rather than with the points itself. q intersects a group if and only if it intersects some point in the group. For convinience, each group is associated with a different color and all the points in the group are imagined to have that color. Then, in the colored reporting (resp., colored counting) problem, we want to report (resp., count) the distinct colors intersected by q. In the dynamic setting, a point of some (possibly new) color is inserted in S or a point in S is deleted. In this thesis we shall consider the query region q to be an axis-aligned orthognal query region and label the problem as orthogonal colored range searching (OCRS). Note that the colored problem reduces to the standard range searching problem when each color class has cardinality 1. This query has applications in various diverse fields, most notable being databases and GIS. For instance, in an SQL database, a GROUP-BY query is one of the most useful queries and OCRS is a geometric representation of a GROUP-BY query.
Till now most of the work on OCRS and related geometric problems has been done by the computational geometry researchers. The issue with those solutions is that the space occupied by the data structures increases exponentially in terms of dimension size. In an internal memory setting the amount of free space available is the main constraint, so these solutions might not scale up well for large datasets with high dimensionality. Therefore, the objective in this thesis is to answer OCRS query on internal memory by building a near-linear space data structure while maintaining low query time. We also handle insertion and deletion of points.
In this thesis we propose a new technique named BB K-d technique to answer OCRS query on internal memory. The space occupied by the data structure is O(n log ), where  is the number of unique colors in the dataset. We considered K-d tree and augmented with additional information to speed up the query. The performance of the proposed algorithm (query response time and space occupied) has been evaluated through extensive experiments and comparison with two base-line brute-force algorithms is presented. All the factors affecting the query time of the BB k-d technique have been thouroughly tested experimentally (such as number of colors, size of query box, data distribution). Real world and synthetic datasets have been used to perform these experiments. The query time of the BB K-d technique varies minimally irrespective

Abstract

Clustering algorithms have wide applications in Computer Vision, Data mining, Data Visualization, etc. Clustering is an important step for indexing and searching of documents, images, video, etc. Clustering large numbers of high-dimensional vectors is very computation intensive. CPUs are unable to handle such load and consume sometimes days and even weeks to cluster large data. GPUs are being used for general purpose computing of wide range of problems which require high computational power. Today’s GPUs deliver as high as 1.5 TFLOPs. The GPU has evolved over the time not only by increasing number of cores but also major architectural changes like faster access of data, more shared memory, threads per block, etc. Such changes have enabled the GPU programmers to exploit its architectural features to the fullest and achieve high performance. In this thesis, we focus on K-Means algorithm which is a widely used unsupervised clustering algorithm. We develop a GPU based K-Means implementation for large datasets; also we have used this implementation to develop a video organizing application. We present the design and implementation of theK-Means clustering algorithm on the modern GPU. All steps are performed entirely on the GPU efficiently in our approach. We also present a load balanced Multi-node, Multi-GPU implementation which can handle up to 6 million, 128-dimensional vectors. We use efficient memory layout for all steps to get high performance. The GPU accelerators are now present on high-end workstations and low-end laptops. Scalability in the number and dimensionality of the vectors, the number of clusters, as well as in the number of cores available for processing are important for usability to different users. Our implementation scales linearly or near-linearly with different problem parameters. We achieve up to 2 times increase in speed compared to the best GPU implementation for K-Means on a single GPU. We obtain a speed up of upto 170 on a single Nvidia Fermi GPU compared to a standard sequential implementation. We are able to execute single iteration of K-Means in 136 seconds on off-the-shelf GPUs to cluster 6 million vectors of 128 dimensions into 4K clusters and in 2.5 seconds to cluster 125K vectors of 128 dimensions into 2K clusters. Video data is increasing rapidly along with the capacity of storage devices owned by a lay user. Users have moderate to large personal collections of videos and would like to keep them in an organized manner based on its content. Video organizing tools for personal users are way behind even the primitive image organizing tools. We present a mechanism in this thesis to help ordinary users organize their personal collection of videos based on categories they choose. We cluster the PHOG features extracted from selected key frames usingK-Means to form a representation for each user-selected category during the learning phase. During the organization phase, labels from aK-NN classifier on these cluster centers for each key frame are aggregated to give a label to the video while categorizing. Video processing is computationally intensive. To perform the computationally intensive steps involved, we exploit the CPU as well as the GPU that is common even on personal systems. Effective use of the parallel hardware on the system is the only way to make the tool scale reasonably to large collections that will be available soon. Our tool is able to organize a set of 100 sport videos of total duration of 1375 minutes in about 9.5 minutes. The process of learning the categories from 12 annotated videos of duration 165 minutes took 75 seconds on a GTX 580 card. These were on a standard desktop with an off-the-shelf GPU. The labeling accuracy is about 96% on all videos. The ideas, approaches proposed in this thesis have been implemented and validated with experimental results. For large data-sets we developed a scalable, efficientK-Means clustering on GPU along with a Multi GPU framework and used it to develop a video organizer application providing high accuracy.

Abstract

With the advent of Web 2.0, Internet has been subdued by a group of applications which facilitate the creation and exchange of user-generated content. Such groups are collectively represented as Social Media which changed the phase of communication between individuals. Blogs, Internet forums, user reviews, chats, activities on social networking sites etc., are some of notable online forms of current social media. As the content of social interactions on these social media forms is increasing rapidly, it led to the problem of information overload. A user may find it difficult to go through millions of lines of different users to grasp the status of a topic. This problem can be dealt wisely by presenting crux of the content rather than the whole user generated text. Automatic extraction of important topics or attributes, and summarization of these topics may help in saving considerable human effort in understanding the content. Automatic summarization is always a classical solution for information overload problem. Summarization of news articles has been explored from theory to building satisfactory models, but summarization of user generated content has not been given much attention. This may be because of the amount of user content on the Internet is once not so signicant but later exponentially increased. In this thesis we study the text in user generated content focusing on its summarization using new extraction methodologies. We initially focus on deriving information extraction techniques for social interactions do-main. We identify extraction of important topics or attributes of a discussion as the first step towards successful summarization of social interactions. There have been developed many ways of extraction from structured text using natural language processing tools. But not much have been developed for information extraction in unstructured social media text. Hence we rst fo- cus on deriving extraction methodologies which can later enhance summarization. We refrained from using language processing resources in our extraction procedures to make sure their success in all domains of social interactions rather than the selected domain of experimentation. We made use of knowledge from external resources like Wikipedia and Web in harnessing the extraction quality. We used machine learning (regression) in judging the extracted output. We choose the scenario of online customer reviews for testing our extraction engine. As the online retail market is growing immense, it poses a large arena of products, their descriptions, customer and professional reviews that are pertinent to them. Reviews contain useful opinionated information about products and their attributes. Most of the product attribute extraction techniques in literature work on structured descriptions using several text analysis tools. However, attributes in these descriptions are limited compared to those in the customer reviews of a product, where users discuss more deeper and specic attributes. In this thesis, we propose a novel supervised domain independent model for product attribute extraction from user reviews. The user generated content contains unstructured and semi-structured text where conventional language grammar dependent tools like parts-of-speech tagger, named-entity recognizers, parsers do not perform to their expected levels. We used Wikipedia and Web to identify the product attributes from customer reviews. In later parts of this thesis we focus on summarization of user generated content taking help from our extraction modules. Our summarization work can be classied as extractive summarization where text units from the original content are used in summary production. The text units we choose for a summary are sentence level units. Our trained system picks sentences from the content and then rank them to produce summary. Sentence ranking is done by estimating the sentence importance through a combination of word level and sentence level features. We choose a scenario where summarization is very much needed. Sales/service chats in the present day E-commerce are crucial for customer support and growth of a company. These chats should be clearly analyzed and followed for product, service, agent and customer validation. Hence summarization of these chats can minimize considerable human eort. Here, we suggest a novel approach to eectively summarize sales/service chats by analyzing their structure and using Wikipedia. Our system outperformed classic text summarization systems when applied for social interactions.

Abstract

State estimation in power systems has carved itself a pivotal niche over the years in what is known as the Energy Management Systems (EMS). Its ability to compute the voltage magnitude and angle at every system node and thus the state of the system at a given operating point classified it as a major player in real time monitoring. However, research in the domain of state estimation is no more limited to the likes of estimating the system states alone. Nor it is limited to the network boundaries of the transmission system anymore. State estimation has really come of age today, especially with the role power engineers see it capable of playing in the modern smart grid when implemented on a larger scale. Its application is now done in a much wider perspective. It has gained significant ground in system security requirements, specifically applications like the contingency analysis which feed off the basic state estimator. The unprecedented stature it has gained over the years has understandably led to a compelling demand for its accountability. With the inevitable step-up in reliability requirements, the dependability of the power system network database which the state estimator is built on becomes a key factor. A simple or conventional state estimator however imparts very high or rather infinite confidence on the branch or line parameters of the power system network considered to be fixed. The state estimator consequently settles to a solution corresponding to the information regarding system conditions as of then and the known network parameters. This assurance makes the state estimator totally unaware of any existing network errors which actually culminate in erroneous interpretation of the state. The failure in updating the parameter database thus leads to inaccurate estimation which could bear heavily on post estimation analysis like security assessment. This led to the dawning of the concept known as network parameter estimation not very long ago. Literature on network parameter estimation is understandably not very large, but nevertheless, has thrown up quite a few techniques and algorithms. In this thesis, a particularly unique approach has been developed and implemented for a state estimator with network parameter errors. A 2 bus π equivalent model is contrived for every two buses in the power network which are connected. It claims a huge advantage of generic structure devoid of any anomaly like existence of a transformer tap or a multiple parallel line structure. The equivalent model parameters for any branch are the same and are thus much easier to estimate rather than evaluating different network components including transformer tap on different line structures. Thus the estimator implemented is independent of the type of connection between two buses as well as the type of component present on it. The correct information regarding the equivalent branch parameters is sufficient for an accurate state estimation. To provide a touch of completeness, there is a convenient provision for original parameters to be estimated from the equivalent once the correct state is estimated. The network parameter estimator requires a significant level of local measurement redundancy around the branch suspected to have the parameter error. Remote Terminal Units (RTU) on the field cannot telemeter points to the extent that power injections and power flows are available at will everywhere. In addition, the data communicated via RTU are not void of noise and communication delays. On the other hand, phasor measurement units (PMUs) have developed remarkably into a crucial link to reliable power system monitoring in EMS since their advent in early 80’s. A PMU capable of measuring the voltage phasor directly on the bus is not only more accurate compared to the conventional RTU, but also measures line currents which can be used to calculate the voltage phasors on the other end. The PMU can thus not only effectively improve estimator accuracy but double it up with measurement redundancy thus making it very applicable in the context of the problem in focus. The proposed state and parameter estimator is thus implemented in the combined presence of a pre-specified set of RTU measurements and strategically placed PMU. A comparative study is proposed to assess the improvement in the performance of the parameter-state estimator when modelled with PMU. Since PMU installations at every node of a power system is unlikely today as well as in a few years to come, optimally placing PMUs to observe the system completely would ensure uniform local redundancy for the parameter state estimator. The other significant contribution of the thesis is thus entirely dedicated to explore this angle in the form of novel techniques proposed to strategically place PMU to account for entirely different or rather contrasting scenarios. While one calls for redundancy in PMU installations at selected points, the other calls for addressing the more pra

Abstract

Natural languages are ambiguous at various levels of processing e.g. phonological, morphological, syntactical and semantically (Jurafsky and Martin, 2000). While the human brain is able to process language despite its ambiguity, computer systems face problems in dealing with ambiguity. In the context of natural language processing, machine translation, information extraction and Q&A, the study of relation is very important as it helps to understand the structure of language and find the correct relation for genitive constructions. Anchoring this research to study of relations, this study develops rules based on semantic and syntactic information to disambiguate the parsing of recursive genitive constructions. Hindi follows “Head-Last” rule (Christiansen and Devlin, 1997) where the last noun behaves as the head noun and the preceding nouns act as the modifiers of the head noun. Since in recursion, we have more than one preceding noun, there is ambiguity about which noun(s) is/are modifier(s) of the head noun. This research is set out to handle the ambiguity arising due to recursion in Hindi language. In this work, we limit ourselves to examine recursive genitive construction with maximum two modifiers occurring before the head noun. We argue that semantic and syntactic information can be used to disambiguate parsing of recursive genitive constructions. We develop six syntactic agreement rules and four semantic rules for parsing the construction under consideration. We implement the rules and achieve an overall accuracy level of 86.6%. In the process of developing semantic rules we identify some semantic relations that exist between noun and its genitive modifiers. In the present work, we postulate 35 semantic relations for noun-noun and five for noun–verbal noun. We utilize these relations to develop the semantic rules which are used to determine the correct parsing of recursive genitive constructions. The syntactic and semantic rules work in the following manner: a. First syntactic agreement rules are applied for parsing. b. If they fail, semantic constraints are checked. c. If the constraints are satisfied, semantic rules determine the parse.