Abstract

In a large distributed network of interconnected nodes, the goal of any Secure Message Transmission (SMT) protocol is to securely deliver the sender’s message at the receiver’s end in the presence of a computationally unbounded adversary, that can partially control the network by corrupting some of its nodes (except the sender and the receiver). In the literature, different variants of SMT problem have been studied depending on the type of network model and/or the types of node corruptions. Undirected graph model and directed graph model are two of the most well-studied network models. Different types of node corruptions studied are passive, fail-stop, omission and Byzantine. In passive corruption, the adversary is only allowed to read/eavesdrop the corrupted node. In fail-stop corruption, the adversary can crash the corrupted node at its will. In omission corruption, the adversary can eavesdrop and/or crash the corrupted node. In Byzantine corruption, the adversary fully controls the actions of the corrupted nodes. In an undirected graph setting, for most variants of SMT problem whether the corresponding SMT protocols exist or not is known in the literature. Moreover, whenever a protocol exists, communication efficient protocols have been designed too. Whereas, in directed graph setting very little is known about the existence of protocols (for dif- ferent variants of SMT problem) as well as the design of efficient protocols. This thesis primarily focuses on bridging this gap between undirected and directed graph settings. It is usually difficult to design efficient protocols in arbitrary directed graphs due to the plethora of different cases/possibilities that usually need to be dealt with. However, in the literature due to the simplicity and ease of protocol design, wires model is considered which is a special case of directed graph setting. In wires model, paths (known as wires) from the sender to the receiver and vice-versa are considered whereas the weak paths are discarded. On the other hand, if the intermediate nodes can generate random-coins and/or perform computations, it is known that the directed wires-based abstraction is inadequate to capture arbitrary directed graphs. In this thesis, we design efficient protocols for different variants of SMT problem in both wires model as well as arbitrary directed graph model. Moreover, we introduce a new model namely routing model to answer the following fundamental question. If each intermediate node is a mere router (can not do computations but can route message to its neighbours) then under what condition(s) is given variant of SMT (im)possible? Furthermore, in arbitrary directed graph setting, we design a protocol which is both communication as well as round/hop optimum when the adversary is passive.

Abstract

Indian classical music is monophonic in nature. Melody is key to any performance. The entire performance is based on a single raga (melodic mode). Some performances are based on a coalescence of two or more ragas. Only a small duration in any musical performance in Indian art music is the precomposed portion. The rest involves a gradual systematic exploration of the raga using various forms ¯ of improvisation. The performer has great freedom in exploring his own improvisational patterns in order to delve into the intricacies of the given raga. However the performer is bound by the frame- ¯ work of the raga, t ¯ ala and other factors such as ghar ¯ an¯ a (the musical school which he belongs to), laya ¯ (tempo). There is a great variation in quality and nature of improvisation among different practitioners based on their cognitive and imaginative abilities. There are two important tools used in improvisation: alankar/alank ¯ aran (musical ornamentation) and t ¯ anas. In this thesis we restrict our study to the present ¯ day usage of alankaran ¯ 1 . Ornamentation is an indispensable part of improvisation. The performer tries to evoke the mood of the raga (melodic-mode) with the delicate exploration of flourishes and ornamentation. Indian classical ¯ music is cognitively associated with these decorations instead of the actual underlying notes. We are interested in discovering the hidden musical patterns and structures in Indian music which are fundamental in unfolding of a raga. Recognizing these patterns can further help in music search, retrieval, recommendation and pedagogy. This thesis makes an attempt to study these ornaments computationally. We begin the study with the objective to computationally detect these ornaments in Dhrupad performances on rudra veen ¯ . a. Dhrupad is the oldest surviving form of Hindustani classical music, is monophonic ¯ in nature and has a wealth of ornamentation. We have crowd-sourced multimedia annotations of primary alankara-s, namely, meen ¯ . da (glides between notes), andolana (vacillations in the note region) and ¯ gamaka (two notes alternation). These were used as the ground truth. Two signals in the time domain, a query signal, which consists of fundamental ornament templates, and a reference signal were compared. Using a variant of dynamic time warping, we then detect the matching subsequences in the reference signal with high accuracy. This method of iterative template matching is naive and has drawbacks, some of which are: 1.) Restrictiveness of the experiment to a set of non-exhaustive list of ornament templates, 2.) Computational overheads of comparing huge pitch vectors using dynamic time warping. While DTW matching was an effective method of detecting these ornaments, we didnt use any domain specific knowledge to detect/identify these ornaments computationally. Cognitively ragas are ¯ 1Most of these definitions are either explained in the introduction section or in the glossary at the end vi vii associated with ornamentation.These along with the ways in which notes are approached,sustained and quitted constitute flows. We call them flows due to the constant change in the frequency and amplitude domains. The rate of change in frequency and amplitude domains together constitute the fundamental nature of ornamentation. We thus model ornamentation as first and second derivative of frequency and amplitude information to see whether the property of rate of change is fundamental to the idea of flows. We were able to achieve very high clustering accuracy by using this representation and our custom defined distance measure. We achieved an accuracy of 81% in distinguishing between Murki vs Kan and 84.5% in Andolana vs Ghaseet. This again shows that transition is at the heart of the definition ¯ of flows and ornaments. However this doesnt account for hidden musical patterns which might not be captured by the manually engineered representation and custom distance. It is important to note that ornaments and flows are intricate Indian music decorations which only experienced musicians can recognize and comprehend. In all of our previous experiments we have used small annotated datasets which do not exhaustively capture patterns underlying ornaments. The biggest challenge in learning and making sense of flows or ornaments is the unavailability of annotated music data. Thus, to have a big data driven exhaustive exploration of these melodic structures implies having either 1.) a multi performer crowdsourced effort to create a large exhaustive dataset, or 2.) an unsupervised/semi-supervised method of learning. To avoid the shortcomings of non-exhaustive small datasets and hand engineered representations, we also develop a robust unsupervised method to learn fixed length representations of ornaments. In the domain of speech processing, neural networks have recently successfully been used for encoding acoustic inf

Abstract

Although tremendous progress has been achieved towards understanding the biochemical versatility and biological functions of RNA, there is a need to deepen our understanding of the principles governing the structural and functional diversity of these fascinating biomacromolecules. One possible factor that contributes to the structural diversity of RNA is the presence of a variety of post-transcriptional modifications of the canonical nucleobases. Detailed analysis of the role of noncovalent interactions involving modified nucleobases in RNA is thus, expected to contribute to our understanding of the factors governing the structure and dynamics of RNA. In an attempt to contribute towards this theme, the present work employs a combination of sequence and structural bioinformatics techniques, along with quantum chemical calculations to understand the structure and strength of hydrogen bonded pairs and higher order structures involving post-transcriptionally modified nucleobases that are present in RNA macromolecular crystal structures. In addition to highlighting the important structural roles some of these hydrogen bonded entities in RNA molecules, our studies highlight the need for, and providing a comprehensive approach towards further investigations on such interactions in the context of many biological processes involving RNA. In addition to understanding the role of posttranscriptional modifications in RNA, we explored the structural and functional diversity exhibited by riboswitches, non-coding RNA, a class of RNA molecules that are a part of RNA regulatory networks, which specifically binds to small cognate ligands and regulate their turnover. Using QM and MD simulations, we explored the molecular features responsible for ligand recognition, and the associated role of noncovalent interactions in gene regulation by riboswitches. Overall, the thesis contributes towards understanding the structure-functional relationships in RNA macromolecules.

Abstract

This thesis discusses a mixed-initiative, domain independent dialog system based on a hierarchically structured knowledge base. The system is rule-based and uses dependency relations and part-of-speech tags obtained from the Stanford Parser coupled with the hierarchical structure of the knowledge base to identify the user’s goal. Primarily, the system is able to accept multi-sentence inputs, that is, multiple sentences forming a query in a single user turn. The system was tested for its accuracy over answering questions, and also subjective testing was done to evaluate the dialog flow; mainly over the books domain. We show examples of the system developed over the domains of books, movies and restaurants to demonstrate the domain independence. We also discuss in detail the simple, rule-based system of extracting relevant information from a user’s query that contributes to the domain independent dialog system. Relevant information is extracted from a user query by using only dependency relations and POS tags, obtained from the Stanford Dependency Parser. Using the universal dependency tags provided by the parser, we tried to understand the semantic structure of a query. This is done by looking for semantically important dependents of the verb, such as the subject, direct object, prepositions and their objects, and so on. Using information obtained from a combination of the dependency relations and the inherent semantic implications of words (such as ‘who’ or ‘where’), we tried to extract the main objective or keyword of the query, and the constraints pertaining to it. This implementation itself is domain independent, however, a mapping to a knowledge base would require some domain knowledge; this issue is resolved using the hierarchically structured knowledge base. This keyword and constraint identification system is tested on the course management domain and the library domain. In order to further improve the domain independent keyword identification for natural language queries, we used statistical methods. We took queries supplemented by only their dependency tags (Stanford Parser) and part-of-speech tags (Stanford POS tagger) and labeled the keywords. We then delexicalised the training data, and used the Conditional Random Fields algorithm to learn these labels. We used the queries created by [45] in the course management domain for training, and tested our model on the queries of three domains: course management, library and the G EO Q UERIES 250 dataset and report fairly high accuracies of 90.65%, 83.19% and 97.13% respectively, making our model a truly domain independent and highly accurate keyword identifier. There is no agreed upon standard for the evaluation of conversational dialog systems, which are well-known to be hard to evaluate. The difficulty lies in pinning down metrics that will correspond to human judgments and the subjective nature of human judgment itself. We explored the possibility of using Grice’s Maxims to evaluate effective communication in conversation. We collected a few system generated dialogs from popular conversational chatbots across the spectrum and conducted a survey to see how the human judgements based on Gricean maxims correlate, and if such human judgments can be used as an effective evaluation metric for dialogs.

Abstract

Past decade witnessed an explosive growth in the amount of unstructured data, especially in the public domain, mainly due to Web 2.0 and social media. This has created a need for applications that extract structured information from such noisy data. Automatic extraction of structured information from unstructured data is called information extraction. Structured information thus extracted is stored in a Knowledge Base. The knowledge base stores facts about entities like name, type and other attributes. On the one hand, the information extraction task utilizes the facts of the entity stored in knowledge base to refine the extraction process, while on the other, the facts extracted refines the knowledge base facts further. Thus knowledge base provides structure and guidance to the extraction task, and gets enhanced by the results of the extraction task. Here we see that the tasks of entity extraction and knowledge base enhancement are mutually dependent and mutually beneficial. Hence this thesis proposes methods to enhance both the tasks, in an effort to build a strong and sound named entity extraction system. Documents typically talk about multiple named entities. All the named entities mentioned in the document are not equally important to the content of the document. Named entities that are important to the document are called salient named entities. In this thesis we propose a method to identify salient named entity of the document. Importance of a named entity can also be judged by understanding how the named entity is semantically related to other named entities mentioned in the document. We propose a method to identify the presence of such semantic relations within named entities. For example, semantic relation like attribute or category in a product title. Understanding the salience of a named entity and its semantic relations help the Named Entity Extraction task in extracting the important information from text, while filtering out unimportant information. Performance of Named Entity Extraction methods depend on the size and structure of the context of the named entity mention in the text. While bigger size and better structure of context results in improved performance of the Named Entity Extraction, lower size and poor structure of context results in reduced performance. We propose three different Named Entity Extraction approaches tailored to the varying size and structure of the context in this thesis. The proposed methods perform on par with state-of-the-art methods with improved latency. Named Entity Extraction approaches that work on lesser context and poorer structure, increasingly depend on non-textual signal like global coherence of entities in the knowledge base. Conventional EL performs well for popular entities but performs poorly for less popular (a.k.a tail) entities, because conventionally EL methods depend on richness of entity neighborhood in the Knowledge Graph (KG). In this context ‘KB’ refers to Knowledge Base like Wikipedia and ‘KG’ refers to Knowledge Graph like Wikipedia Hyperlink Graph. Tail entities have sparse entity neighborhood and hence EL methods perform poorly on them. In this thesis we propose ELDEN, an EL system that overcomes the degree sparsity problem of tail entities. ELDEN enriches entity’s neighborhood in a KG by extracting high quality mentions of entity from a web corpus using Pointwise Mutual Information (PMI) measure. ELDEN outperforms state-of-the-art EL systems while achieving significant improvement in linking tail entities, achieving best results on CoNLL and TAC datasets. We follow up the discussion on ELDEN with a discussion on information retrieval task that is improved by use of KB entities. We propose a novel method for enhancing classification performance of research papers into ACM computer science categories using KB entities, both Wikipedia and Freebase entities. All through this thesis we present five methods of improving Named Entity Extraction using Knowledgebases. We conclude the thesis by looking at how Knowledgebases can be improved with Named Entity Extraction. We review and analyze the main approaches of New Entity Identification (NEI) in Named Entity Extraction systems. We analyze the features and share insights from reproducing state-of-the-art results, suggesting future improvements.

Abstract

The Cooperative Target Observation (CTO) problem has been of great interest in the multi-agents and robotics literature due to the problem being at the core of a number of applications for example surveillance, inspection and search-and-rescue. In CTO problem, the observer agents attempt to maximize the collective time during which each moving target agent is being observed by at least one observer agent in the area of interest. The area of interest can include airport, border patrolling or public events. Micro-drones are typically used for such operations as with large gatherings and protests, or even when monitoring individuals, it is often difficult to maintain an overview. They can be pretty useful for surveillance allowing for a (top) view of the happenings on ground. The CTO problem in most of the prior works is solved by finding the best suited strategy for observer agents, considering the target agent’s movement to be Randomized. Given our focus on surveillance domain, we modify this assumption to make the targets strategic and present two target strategies namely Straight-line strategy and Controlled Randomization strategy. We then modify the observer strategy proposed in the literature based on the K-means algorithm to introduce five variants over the K-means algorithm and provide experimental validation across the strategies. In surveillance domain, it is often reasonable to assume that the observers may themselves be a subject of observation for a variety of purposes by unknown adversaries whose model may not be known. Randomizing the observer’s action can help to make their target observation strategy less predictable, so that the unknown adversary cannot harm the observer agent. As the fifth variant, we therefore introduce Adjustable Randomization into the best performing observer strategy among the four variants over K-means algorithm, where the observer can adjust the expected loss in reward due to randomization depending on the situation.

Abstract

Understanding the precise 3D structure of an environment is one of the fundamental goals of computer vision and is challenging due to a variety of factors such as appearance variation, illumination, pose, noise, occlusion and scene clutter. A generic solution to the problem is ill-posed due to the loss of depth information during imaging. In this paper, we consider a specific but common situation, where the scene contains known objects. Given 3D models of a set of known objects and a cluttered scene image, we try to detect these objects in the image, and align 3D models to their images to find their exact pose. We develop an approach that poses this as a 3D-to-2D alignment problem. We also deal with pose estimation of 3D articulated objects in images. We evaluate our proposed method on BigBird dataset and our own tabletop dataset, and present experimental comparisons with state-of-the-art methods. In order to find the pose of an object, we come up with a hierarchical approach whereby we first an initial estimate of the pose and thereby refine it using a robust algorithm. Obtaining the initial estimate is crucial as the refinement is entirely dependant on it. Estimating the object proposals or region proposals from an image is a well-known but difficult task, as the complexity of the problem intensifies due to the presence of object-object interaction and background clutter. We tackle the problem by coming up with a robust Convolutional Neural Network based method which learns object proposals in a supervised manner. As we need region proposals at object level, we solve the problem of instance-level semantic segmentation, where each pixel in the image is classified into one of the known classes. Moreover, two pixels are labelled differently if they belong to two different instances of the same class. We show quantitative and qualitative comparison of our proposed network models with previous approaches, and show our results on the challenging PASCAL VOC dataset.

Abstract

A given piece of textual information produced by any user or agent is said to be inappropriate if the expressed intent may cause anger, annoyance to certain users or exhibits lack of respect, rudeness, discourteousness towards certain individuals/communities or may be capable of inflicting harm to oneself or others. A search engine should regulate its query completion suggestions by detecting and filtering suchqueries as it may hurt the user sentiments or may lead to legal issues thereby tarnishing the brand image. Hence, automatic detection and pruning of such inappropriate queries from completions and related search suggestions is an important problem for most commercial search engines. The problem is rendered difficult due to unique challenges posed by search queries such as lack of sufficient context, natural language ambiguity and presence of spelling mistakes and variations. In this Thesis, we propose a novel deep learning based technique for automatically identifying inap- propriate query suggestions. We propose a novel deep learning architecture called “Convolutional Bi-Directional LSTM (C-BiLSTM)” which combines the strengths of both Convolution Neural Networks (CNN) and Bi-directional LSTMs (BLSTM). Given a query, C-BiLSTM uses a convolutional layer for extracting feature representations for each query word which is then fed as input to the BLSTM layer which captures the various sequential patterns in the entire query and outputs a richer representation encoding them. The query representation thus learnt passes through a deep fully connected network which predicts the target class. C-BiLSTM doesn’t rely on hand-crafted features, is trained end-end as a single model, and effectively captures both local features as well as their global semantics. Evaluating C-BiLSTM on real-world search queries from a commercial search engine reveals that it significantly outperforms both pattern based and other hand-crafted feature based baselines. Moreover, C-BiLSTM also performs better than individual CNN, LSTM and BLSTM models trained for the same task. Rapid growth of chatbots and Interactive Gaming Systems expect large, real time, clean (non-inappropriate) human conversation data to train their models. High demand of social networking sites provide a platform for users to interact and share opinions publicly. Inappropriate conversations and posts in these platforms may also lead to loss of business and damaging company’s image. So we extended our idea to identify inappropriate conversations in chat data. We have applied various techniques to solve this problem and observed that BLSTM performs better than LSTM and Boosted Decision Tree approaches.

Abstract

Understanding the meaning of words is essential for most natural language processing tasks. Word representations are means to mathematically represent the meaning of a word in a way that computers can understand. These representations are often in the form of vectors in which words are represented in a continuous vector-space of fixed dimensionality also referred to as word embeddings. In this thesis, we focus on generating better and reliable word representations for low resource languages. Many languages, though widely spoken, are largely under-represented in this area of research. One of the main reasons for this is the lack of reliable evaluation metrics to compare between different approaches of building these embeddings. Word similarity task is a widely used, computationally efficient method to directly evaluate the quality of word vectors. It relies on finding correlation between human assigned similarities between words, and those between corresponding word vectors. We release word similarity datasets for six low resource languages – Urdu, Telugu, Marathi, Punjabi, Tamil and Gujarati. For the construction of these datasets, our approach relies on translation and re-annotation of word similarity datasets of English. We also present baseline scores for word representation models using state-of-the-art techniques for Urdu, Telugu and Marathi by evaluating them on newly created word similarity datasets. For linguistically similar languages, we show that it is possible to use the better trained word representations of the more resourceful language for the other language in the pair, using a projection learning approach which relies on a mapping between words having similar meaning from the two languages. This cross-lingual vector space transformation results in state of the art results on word similarity test sets of French and German - an increase of 13% in case of French and 19% for German, using English as the source language. We also go on to demonstrate that this approach is better suited for linguistically similar language pairs like Hindi-Urdu (where 60% words are simply transliterations of each other) than English-German or English-French. We go on to see how we modelled prefix-suffix based morphoology using a similar technique.

Abstract

The field of data mining has emerged to extract knowledge hidden in large databases for better decision making. The process of frequent pattern (a set of items represents a pattern (or an itemset)) mining finds interesting information about the association among the items in a transactional database. The notion of support is employed to extract the frequent patterns. A pattern is called a frequent pattern if it satisfies the user-defined threshold on minimum support. An important criterion to assess the interestingness of a frequent pattern is its temporal occurrences in a database. That is, whether a frequent pattern is occurring periodically, irregularly, or mostly at specific time intervals in a database. The class of frequent patterns that are occurring periodically within a database are known as periodic-frequent patterns. Finding these patterns is a significant task with many real-world applications like improving the performance of recommender systems, intrusion detection in computer networks, discovering events in Twitter. Current periodic-frequent pattern models cannot handle datasets in which multiple transactions share a common timestamp or when transactions occur at irregular time intervals. This issue limits the applicability of the model as in many real-world databases like e-Commerce, Twitter, etc., transactions share a common timestamp and uneven time gaps exist in between the consecutive transactions. Most previous models on periodic-frequent pattern mining have focused on finding all patterns in a transactional database that satisfy the user-specified minimum support (minSup) and maximum periodicity (maxP er) constraints. The minSup constraint controls the minimum number of transactions that a pattern must cover in a database. The maxP er constraint controls the maximum duration between the two transactions below which a pattern should reoccur in a database. The usage of a single minSup and maxP er for an entire database leads to the rare item problem, because real-world databases have a non-uniform item distribution, which considers that items have different support and periodicity values. Also, current periodic-frequent pattern models have focused on discovering full periodic-frequent patterns, i.e., finding all patterns that have exhibited complete cyclic repetitions throughout the entire database. These models evaluate the periodic interestingness of a frequent pattern by determining whether all of its inter-arrival times are within the user-specified maxP er threshold. Therefore, the model cannot assess the partial periodic behavior of a frequent pattern in a database. However, partial periodic-frequent patterns are more common due to the imperfect nature of real-world databases. So, to address the above issues, in this thesis, we are proposing two improved approaches that discover periodic-correlated patterns and partial periodic-frequent patterns in non-uniform temporal databases, respectively. In the first approach, we tackle rare item problem by proposing a improved model that discovers periodic-correlated patterns in a non-uniform temporal database. In this thesis, we consider temporal database as a collection of transactions, ordered by their timestamps. Further, a temporal database facilitates multiple transactions to share a common timestamp and allows time-gaps in between consecutive transactions. A temporal database is said to be non-uniform if it contains items with dissimilar support and periodicity. To tackle rare item problem in non-uniform temporal databases, the proposed model considers a pattern as interesting if its support and periodicity are close to that of its individual items. The existing all-confidence measure is used to determine how close is the support of a pattern with respect to the support of its individual items. A new interestingness measure, called periodic-all-confidence, is being proposed to determine how close is the periodicty of a pattern with respect to the periodicity of its individual items. A pattern-growth algorithm has also been discussed to find periodic-correlated patterns. Experimental results show that the proposed model is efficient and tackles rare item problem. We discuss the usefulness of periodic-correlated patterns with a real-world case study on FAA-Accidents database and show that the proposed model may be utilized to discover interesting periodic-correlated patterns involving both frequent and rare items effectively. In the second approach, we have introduced a improved model to discover partial periodic-frequent patterns in non-uniform temporal databases. The proposed model lets the user specify a different maximum inter-arrival time (M IAT ) for each item. An inter-arrival time of a pattern is considered periodic (or cyclic) if it is no more than period. Thus, different patterns may satisfy different period depending on their items’ M IAT values. This solves the rare item problem in partial periodic-frequent pat