Abstract

Natural Language Interface to Database (NLIDB) systems convert a Natural Language (NL) query into a Structured Query Language (SQL) and then use the SQL query to retrieve information from a database. The main advantage with this function of an NLIDB system is that it makes information retrieval much easier and more importantly, it also allows non-technical users to query a database. In this work, we present an effective usage of tokens in an NL query to address various problems in an NLIDB system. The conversion of an NL query to SQL query is framed as a token classification problem, using which we unveil a novel method of mapping an NL query to an SQL query. Our approach reasonably addresses domain dependency which is one of the major drawbacks of NLIDB systems. Concepts Identification is a major component of NLIDB systems (Gupta et al., 2012; Srirampur et al., 2014). We improve Concepts Identification (Srirampur et al., 2014) by making use of Stanford Parser Dependencies. Our approach is more robust than previously proposed methods. In addition, we also discuss how Concepts Identification can be applied to address Ellipsis in a dialogue process. In addition to providing results to a user, it is essential to provide a relevant and a compact set of results. We propose a new problem of generating a compact set of results to a user query. At a higher level, user-system interactions are modeled based on patterns frequently observed between a user’s current query and his previous queries, while interacting with a system. Using these models, we propose a novel method of system prompting to help a user obtain a smaller and a relevant set of results. In addition to providing a compact and a relevant set of results, it is imperative that answers of an NLIDB system are comprehensible even by the people who are less familiar with a common language like English. NLIDB systems use Natural Language Generation (NLG) modules to provide answers in the form of sentences. It is important to make sure that an answer generated by an NLG module is very simple to understand. This brings in the problem of text simplification, wherein, one of the most crucial and initial sub-problems is Complex Word Identification (CWI). We address the problem of CWI by distinguishing words as simple and complex. A plethora of classifiers were explored to identify the complex words. This information helps us in improving the simplification of an NLIDB system’s final output to a user. To summarize, in addition to addressing problems within an NLIDB system, this work touches postNLIDB problems like results processing. All the proposed issues are tackled using tokens in an NL query as the basic and a driving unit of force.

Abstract

Road extraction from very high (VHR) and high resolution (HR) satellite imagery is one of the important problems in the remote sensing area. Road network database is one of the essential features for various GIS applications like traffic management, transportation management and urban planning. Generally the road map is generated using the on-field survey techniques and GPS (Global Positioning System) based tracking methods. But recently the techniques which uses the remote sensing aerial and satellite imagery for road extraction are being developed. Since road region appear as linear segment in low resolution images, earlier research on road extraction focused on extracting road center-line from low resolution images. On the other hand, very high resolution satellite images provide an opportunity to extract entire road area along with road network. However, factors like variation in road surface characteristics and changing road geometry (widths and curvatures), occlusion due to trees building shadows and vehicles, the neighbouring non-road regions which become more apparent in very high resolution satellite images, make road extraction a challenging problem. Difference in the surface characteristics of the road in an image become too obvious in VHR images. Because of this complexity of the sensor and ground characteristics it makes difficult to have an automatic road technique which may extract the road area well in some scenarios but fails in most of the cases. In those cases semi automatic techniques where user provides some intial seeds which represents the road surface characteristics can be helpful in solving the issue. In this thesis a semi automatic road extraction algorithm based on adaptive spectral and texture matching (ASTM-R) with occlusion handling, which is a variant of region growing approach is presented. The algorithm developed in this thesis is robust to variations in radiometric resolution of input images, road surface characteristics and road geometry (widths and curvatures) and is able to reduce the false detection of neighbouring non-road regions. In addition to that, the proposed algorithm here can jump over the occlusions and can proceed with road tracking, resulting in using minimum number of user given seeds by being able to handle the occluded areas. The algorithm is tested on various satellite images, which comprises of PAN-sharpened QuickBird, IKONOS, Orbview3 and WorldView-2 images. Images are chosen to include road regions with varying width, curvatures, different ground characteristics. Experiments are conducted on images with disconnected road segments, road regions occluded with trees, vehicles. The measures used to evaluate the algorithm performance are road area completeness, correctness of road area and road network completeness. The algorithm is able to consistently extract 70% to 90% of the road area completeness and correctness. Reduction in the number of seeds is the another measure used in order to evaluate the occlusion handling performance of the algorithm. The algorithm is able to handle the occlusions and has considerably reduced manual intervention in road extraction process by minimizing 60-80% of the user seeds.

Abstract

While the ability to see colours is innate, the perception itself is a guided process. Varying across languages and cultures, linguistic vocabulary is one such influence that guides our perception. People across languages name concepts and objects central to their existence. Words of universal significance, limited to the scope of the culture, are also added. In colour specifically, those found aesthetically and poetically noteworthy are named in addition to the essential ones. These names of colours act as verbal cues that help us memorise the colours of the spectrum and later, bias us as we try to recognise them back. This makes colour a cultural and local phenomenon. The documented colour vocabulary in languages, so far, is confined to basic colour terms and their corresponding hues in the limited munsell colour space. This thesis suggests a procedure to collect a comprehensive list of colours in a language, to try to identify the complete effect that language has on colour cognition. It also tries to rectify the dearth of collected data for Indian languages by gathering a list of colour names in Hindi, Telugu and Malayalam and also a detailed colour palette. A generalised digital survey platform is proposed to collect a colour palette of a language, through which, a list of colour names is mapped to one with corresponding ranges of hues. The palette procured thus, repre- senting the colour qualia of the language speakers, can be used to gain an insight into their collective colour perception and for building useful applications in various fields. This work addresses the need for a mechanism to analyse the distinctions between different colour palettes, and introduces an idea of cultural photographic filters. From the various aspects of a culture, here, language is chosen, and the colour hues that are endowed with names by the language, are used to build a filter. For the method of colour transfer, an innovative procedure is outlined and various modifications are suggested thereafter. Image segmentation and region based colour transfer is used to ensure an accurate and desired highlighting of colours. The results are compared with some existing procedures to show the improvement that the proposed method brings about. The method is used to bias a given image with colours that are perceptually closest to it in a reference language. This lets the resulting photographs reflect the changes in colour vocabularies of people from different languages and cultures. The variations are depicted visually for any observer to draw inferences from. This work also presents a possibility for various secondary filters over the basic language filter, for further biasing a photograph as needed. Plenty of criteria for secondary biases are discussed and demonstrated. Multiple approaches are also detailed for generation of the said biases and the results are presented to affirm the width that the proposed ideas bring to this field of study.

Abstract

Researchers have demonstrated that breath acetone is an effective biomarker of Type 2 diabetes which is the most common form of diabetes. Diabetes treatment requires intermittent monitoring of the blood glucose levels in the patients. Conventional way of detecting glucose levels is through invasive technique which involves pricking the finger and collecting blood sample. This is not only painful and blood consuming but also time consuming and expensive. Therefore, there has been a great demand for the non-invasive techniques of blood glucose determinations in the commercial market. Researchers have been attempting to develop a number of non-invasive techniques where the glucose can be measured by different methods outside the body, without puncturing the skin or without taking the blood sample. However, out of various non-invasive techniques developed, many of them are not suitable for real-time, point-of-care, and routine uses because they involve high cost and require time-consuming and complicated sample pretreatment, large space and infrastructure for operations. Detection of breath acetone can be a rapid, noninvasive, and patient compliant viable alternative to the conventional methods of blood glucose determination. Acetone in the breath appears due to increased lipolysis. The breath acetone levels are found to be less than 0.9 ppm in healthy people and more than 1.8 ppm in diabetes patients. This has led researchers to develop alternative acetone sensors, especially semiconducting metal oxides (SMOs)-based chemo-resistive sensors due to their several favorable attributes. However, achieving the target selectivity, sensitivity, fast response and recovery, and low detection limit have often been very challenging for the SMO-based sensors, especially for the sample like exhaled breath that consists of plethora of gases including a large quantity of water vapor and carbon dioxide. The thesis work involves designing an embedded system to measure blood glucose levels from breath acetone. First, it involves testing with the existing SMO-based acetone sensor followed by reducing the effects of other parameters by using Artificial neural network model. We observed that we still need improvements in various fronts of sensor design. Sensors for breath acetone monitoring must show high sensitivity and selectivity and very small response and recovery times, in addition to a good reversibility and stability. Exhalation is a very fast process ( ≈ 3 s) and a small quantity of acetone (≈0.1 - 10 ppm) is present in the exhaled breath. Therefore, detection of acetone below 10 ppm is of great significance in breath acetone sensing. Towards this goal, we developed highly efficient SMO-based acetone sensors made of Pd nanoparticle-loaded nanostructured SnO 2 particles (Pd@SnO 2 ). The sensors were prepared by using simple chemical reduction and sol-gel synthesis methods with no requirements for dispersingagents or complicated synthesis and fabrication steps. Our Pd@SnO 2 sensors exhibited very high sensor response with small response and recovery time at relatively low operating temperature. Further, the sensors exhibit excellent reversibility, selectivity over ethanol and noninterference from water vapor and CO 2 , two major constituents of the exhaled breath. These parameters satisfy the requirements of a real-time breath acetone sensor.

Abstract

This thesis considers Software Plug and Play as a potentially useful architectural abstraction that can solve many software architecture problems faced by vertical markets in the industry. While Plug and Play as a technology has been utilized to address many extensibility concerns in Information Technology (IT) infrastructure, there is no systematic support for similar extensibility notion at the software architecture level. To address these concerns, this thesis proposes the creation of frameworks and component models to support Plug and Play. Accordingly, this thesis considers Plug and Play as a user-defined framework, supported by a run-time component library that is embedded in the component schema, in order to support functional and structural extensibility of a running software system.

Abstract

I proudly present Kathaa, an Open Source web-based Visual Programming Framework for Natural Language Processing (NLP) Systems. Kathaa supports the design, execution and analysis of complex NLP systems by choosing and visually connecting NLP components from an already available (and easily extensible) Module library. It models NLP systems as a edgelabeled Directed Acyclic MultiGraph (of optionally parallalized information flow), and lets the user choose and use publicly co-created modules in their own NLP applications irrespective of their technical proficiency in Natural Language Processing or in handling complex software systems. Kathaa exposes an intuitive web based Interface for the users to interact with and modify complex NLP Systems; and a precise Module definition API to allow easy and dynamic integration of new state of art NLP components (along with packing their associated services as docker containers). Kathaa enables researches to publish their services in a standardized format for the easy use of everyone else who may or may not understand the intricacies of their research but still really wants to use it and play with it, right out of the box. In more simpler words, the goal is to be able to make the basic primitives of Natural Language Processing accessible to each and everyone, and for everyone to be able to easily use, play with and adapt them. Research in Natural Language Processing has applications in a whole lot of domains. But while we as NLP Researchers happily celebrate the impact our research has, we do not actively make an effort towards making the life easier for someone without any background in Natural Language Processing, especially the rather large section of users who might want to just reuse some of our ideas and efforts in their own domain, for their own custom problems. With Kathaa, we aim to bridge this gap. One particularly strong motivation behind the effort that went into this work, is also to enable other fellow researchers to easily replicate and reuse our research without having to go through the usual technical hiccups that are associated with problems of this scale, complexity and magnitude. Also, somewhere deep down, all of us secretly wish the learning curve associated with even the simplest of the ideas in NLP was much lower, and Kathaa by design and its initial motivations also solves this exact problem by making it ridiculously easy to interact and play with rather complex NLP systems. With a little bit of creativity, the user can very easily mash up these ideas in new ways to come up with creative applications of the state of art of Natural Language Processing Research. The vision of this thesis is to pave the way for a system like Kathaa, to be the Lego blocks of Natural Language Processing Research and Applications. With Kathaa, I hope to inspire people from completely different backgrounds, motivations and curiosities to be able to play with the state of art results from Natural Language Processing research without having to indirectly prove a certain level of technical proficiency before being able to do anything productive with the systems. To help facilitate this ambition, in Kathaa, we very clearly separate the design and implementation layers of Natural Language Processing systems, and efficiently divide and pack every NLP component into consistent and reusable black-boxes which can be made to interface with each other through a consistent and robust interface, irrespective of the software environment in which these components reside. We also provide a really intuitive and visual interface to manipulate the interactions between the said components, and then go on to demonstrate how NLP components ranging from very simple to very complex in their design, can easily be included in Kathaa. As a practical use case, we visually implement the Sampark Hindi-Panjabi Machine Translation Pipeline and the Sampark Hindi-Urdu Machine Translation Pipeline in Kathaa, to demonstrate the fact that Kathaa can also handle really complex NLP systems while still choosing to be intuitive and abstract for the end user. With this thesis, I personally call out to all NLP researches to publish their research through Kathaa and help create an environment where every curious kid and every curious mind can comfortably play with our ideas around Natural Language Processing and adapt them to their heart’s content without the unnecessary burden of having to work their way through silly technical hurdles.

Abstract

The study of complex networks or graphs has been extensively pursued by researchers from multiple disciplines. In history, the well-known “Seven Bridges of Koenigsberg” problem is the first real-world problem that was solved by the study of networks. Since then, there has been significant theoretical advancement in this area. Network science has been explored in diverse fields such as sociology, biology, physics and computer science and has spanned a plethora of applications like link analysis, community detection, influence analysis. Only recently, detecting outliers in such information networks has caught the attention of researchers in the data mining community. Outlier detection in information networks is the focus of this thesis. Outliers are structures in networks which have unusual patterns, which deviate significantly from the rest of the data. Outliers in graphs can appear in different forms like nodes, edges, subgraphs, communities and so on. In this thesis, we propose a novel outlier structure in networks, graph cuboid outliers. We put forward the novel problem of graph cuboid outlier detection in both static and timeevolving networks and design efficient algorithms for the same. Recently, there has been an interest in finding outliers with respect to a given query. Query-based outlier detection is more favorable over the general outliers as it allows the user a flexibility to find outliers following a particular schema and predicates encoded in the form of a query. Given a heterogeneous network and a query we detect Graph Cuboid Outliers (GCOutliers). Graph cuboids are semantically related regions in a network which helps us view the network along multiple dimensions and at multiple levels. GCOutliers are those cuboids which exhibit anomalous behavior with respect to the given subgraph query. An example of a GCOutlier would be those research areas which have unusual collaborations in a DBLP network. Further, we can obtain such regions with respect to specific requirements, such as finding those research areas where a large numbers of papers are published with at least five authors. The requirement is modeled as a subgraph query to obtain query sensitive graph cuboid outliers. In order to detect GCOutliers, there are several challenges; (i) the number of cuboids can be high, (ii) the number of matches can be large and (iii) subgraph isomorphism is an NP-hard problem. In our solution we address the issue of the large number of matches. This is done by designing a na¨ıve random sampling method followed by a more principled sampling method using regression models for nodes and edges. We next move our attention to time-evolving or temporal networks. For a series of snapshots of a heterogeneous temporal network we propose to detect Evolutionary Graph Cuboid Outliers (EGCOutliers) in temporal networks. EGCOutliers are those cuboids which have an anomalous behaviour with respect to the cuboids in its own snapshot and whose behavior over time is different from the average behavior of all the cuboids over time. The change in behavior over time is considered as the evolutionary behavior and therefore, we call our graph cuboid outliers as Evolutionary Graph Cuboid Outliers. We extend GCOutlier detection to detect EGCOutliers. We model the problem of detecting EGCOutliers into a regression problem. The experimental results on both real and synthetic datasets show the efficiency of the proposed algorithms. We posit the problem of detecting GCOutliers and EGCOutliers in heterogeneous networks and proposed efficient solutions for the same. We believe this thesis laid the foundation for graph cuboid outliers and opens up a new direction in the area of outlier detection research. As network based systems continue to grow and become ubiquitous, we believe that the proposed algorithms will receive attention in a wide variety of applications and will foster the area of outlier detection in general.

Abstract

Recent trends in natural language processing (NLP) show ever increasing popularity of dependencybased analysis of natural language texts. Dependency representations offer simplicity, compactness and transparent encoding of predicate-argument structure. In the last decade and a half, a number of dependency treebanks have been built and various parsing algorithms have been proposed for automatic dependency analysis across wide range of languages. Over the years, it has been observed that morphologically rich and free word order languages, unlike fixed word order languages, are harder to parse, regardless of the parsing technique used. On the one hand, rich morphology provides explicit cues for parsing, while on the other hand it worsens the problem of data sparsity as it leads to high lexical diversity and variation in word order. In this thesis, we aim to address this trade-off for accurate and robust parsing of morphologically rich Indian languages. We present novel strategies to effectively represent morphology in the parsing models and also to mitigate the effect of its trade-offs. We propose to represent morphosyntactic information as higher-order features under the Markovian assumption. More specifically, we use the history of a transition-based parser to extract and propagate morphological information such as case and grammatical agreement as higher-order features for parsing nominal nodes. Despite its benefits, rich morphology can also pose a multitude of challenges to statistical parsing. The most prominent issue is related to sampling bias towards canonical structures of a language. As current parsers are mostly trained on formal texts, even a slight deviation from canonical word order can severely affect their performance. To overcome this bias, we propose a sampling technique to generate training instances with diverse word orders from the available canonical structures. We show that linearly interpolated models trained on diverse views of the same data can effectively parse both canonical and non-canonical texts. Similarly, to mitigate the effect of lexical sparsity, we use supervised domain adaptation techniques for training parsers on lexically more diverse annotations from augmented Hindi and Urdu treebanks. We demonstrate that a feedforward neural network-based dependency parser trained on augmented, harmonized Hindi and Urdu data performs significantly better than the parsing models trained separately on their individual datasets. Furthermore, we explore lexical semantics as a viable alternative to more training data for parsing semantically rich but sparse dependency annotations in Indian language treebanks. We show that lexical semantics in the form of discrete and continuous features such as ontological categories, Brown clusters and word embeddings can play a major role in disambiguating highly rich dependency relations.

Abstract

Improving the thermostability of industrial enzymes is an important protein engineering challenge. Molecular level understanding of mutational effects on stability and activity of enzymes is complex particularly when several point mutations are incorporated during the directed evolution experiments, due to non-additivity involving either cooperative (positive) or antagonistic (negative) effects. Thermostability is experimentally characterized by many observables (T50, Tm, T1/2, ΔG etc.) and they often show correlation with each other. However, this is not always true because of the different stabilizing mechanisms operative in different cases. In this thesis, I have tried to understand the molecular mechanism of thermostability and activity of B. subtilis lipase mutants. I have studied the molecular dynamics of wild type B. subtilis lipase (WT) and its six progressively thermostable mutants (2M, 3M, 4M, 6M, 9M, and 12M), at different temperatures. The less thermostable mutants (LTMs), 2M to 6M, show WT-like dynamics at all simulation temperatures. However, the two more thermostable mutants 9M and 12M (MTMs) show the required flexibility at appropriate temperature ranges and maintain conformational stability even at high temperature. They show a deep and rugged free-energy landscape, confining them within a near-native conformational space by conserving non-covalent interactions, and thus protecting them from possible aggregation. In contrast, the LTMs having marginally higher thermostabilities than WT show greater probabilities of accessing non-native conformations, which, due to aggregation, have reduced possibilities of reverting to their respective native states under refolding conditions. Our analysis indicates the possibility of non-additive effects of point mutations on the conformational stability of LTMs. I suggested the lack of consistency in the effect of point mutations incorporated during the initial generations of directed evolution experiments, towards conformational stabilization of B. subtilis lipase mutants of later generations. I show that the cumulative point mutations incorporated in mutants 2M (with two point mutations) to 6M (with six point mutations) possibly do not retain their original stabilizing nature in the most thermostable 12M mutant (with 12 point mutations). I have carried out MD simulations using structures incorporating reversal of different sets of point mutations to assess their effect on the conformational stability and activity of 12M. My analysis has revealed that reversal of certain point mutations in 12M had little effect on its conformational stability, suggesting that these mutations were probably inconsequential towards the thermostability of the 12M mutant. Interestingly, these mutations involved evolutionarily conserved residues. On the other hand, some of the other point mutations incorporated in non-conserved regions, appeared to contribute significantly towards the conformational stability and/or activity of 12M. Based on the analysis of dynamics of in-silico mutants generated using the consensus sequence, I identified experimentally verifiable residue positions to further increase the conformational stability and activity of the 12M mutant. In this context, I also studied, the protein contact networks (PCNs) and its application in understanding the small conformational variations due to point mutations using both, the crystal structures as well as the MD trajectories of the different mutants. Analysis of the variation in several network centrality measures showed some important correlations with stabilities of different mutants. I have identified key residues, in 9M and 12M, which can be related to their enhanced stability and activity compared to WT and other less thermostable mutants. I have observed that the reversal of few key point mutations in 12M have significant effect on the topological features, suggesting the importance of these point mutations in the stability/activity of 12M. The study of contact networks based on non-covalent interactions effectively bring out the factors responsible for enhanced stability/activity due to point mutations in more thermostable 9M and 12M mutants. Our study highlights the importance of considering not only the geometrical criteria but also the chemistry of interacting amino acids in PCN construction. Analysis of the molecular basis of chain length selectivity in B. subtilis lipase and the role of catalytically important point mutations in the substrate binding of the 12M mutant suggest that the combined reversal of M134E and M137P point mutations cause significant decrease in binding affinity for the small chain length ester substrates compared to long chain length ester substrates, suggesting the importance of M134E and M137P point mutations in substrate binding and hence activity. The 12M mutant maintains a nearly constant volume for binding site with all the substrates and stabilizes a ready to attack co

Abstract

In Natural Language, two senses of reference are generally described. First is the symbolic relationship that expressions (words or phrases) have with the concrete or abstract real world objects and second sense is the relationship between two textual expressions in the text, in which one expression provides the necessary information to interpret or relate the other. These expressions are distributed across the text and their connections make co-referential chains (or links). For a text, coreference resolution is a task to identify and link expressions that refer to same object. These coreference expressions can be anaphors, nominal, verbal or verb-nominal expressions. Coreference links (chains) are useful in various NLP applications such as question answering, text summarization, Machine translation, etc. For English and several other European languages, the task of resolving coreference has been studied to a sufficiently great extent and various techniques have been proposed for those languages, but for Indian Languages, work has been very limited. In this thesis, we describe our work on second sense of reference by proposing co-reference representation scheme and different co-reference relation types between continuous mentions of the same coreference chain such, as identity, near-identity and weak identity relations and their sub-types. Then, we also propose and describe methods to resolve coreference for Hindi news and dialogue text. The six major points (contributions) are covered in this thesis on the topic of coreference. First, we identified Indian language specific conceptual, structural and representational issues in the existing coreference annotation schemes and tried to resolve them by proposing a unified coreference annotation framework and procedure. This framework includes various aspects of coreference like expression span, coreference chain, relation between contiguous expressions of same coreference chain, etc. Second, Based on the proposed annotation scheme, we developed a semi-automatic annotation tool (CAT - Coreference Annotation Tool) to ease the annotation process. Third, we propose a method for calculating inter annotator agreement on various aspect/level of coreference annotation. Fourth, Using proposed coreference annotation scheme and CAT, we annotated coreference information on some part of Hindi and Urdu Dependency Treebanks. Fifth, We also present a hybrid multi-classifier based approach to identify reference type for an anaphor (pronoun). We describe a hybrid (learning and rule) approach to resolve entity and event referring pronouns for Hindi dialogue and news text. In these approaches, we explore the use of dependency structures as a source of syntactic information and for entity anaphora resolution. We compare use of dependency structure based rules (features) over syntax based rules (features) for event anaphora resolution. Other than dependency based features we also explore the use of other linguistic information such as sub-topic boundary, animacy and Named Entity categories for dialogue anaphora resolution. Sixth, we present a sieve based approach for Hindi nominal reference resolution and relation type identification between continuous expressions of same coreference chains. In the this approach, we explore the use of Paninian dependency grammar, various linguistic rules based on gender, number, person, animacy, dbpedia based dictionaries, word-embeddings from word2vec - Glove as features and rules to resolve nominal co-reference. Hybrid system on these rules and features with various sieves (on predefined preference) gives considerable amount of accuracy for nominal reference resolution and relation type identification. At conclusion, we combine all the above mentioned modules (entity anaphora resolution, event anaphora resolution and nominal reference resolution) into one software-kit so the NLP community can use it and provide us feedback on the presented approaches.