Abstract

The field of data mining has evolved to help organizations find interesting knowledge from databases. Under data mining, different knowledge extraction approaches like association rules, classification and clustering have been proposed. Association rules are generated by analyzing the transactional databases using the support and confidence interestingness measures to identify the most important relationships among the items. Discovering frequent patterns is a key step in association rule mining. A pattern is called a frequent pattern if it satisfies the user-defined threshold on minimum support. Periodic-frequent patterns come under the class of frequent patterns which capture the temporal dimension of a pattern. In this thesis, we made efforts to improve the performance of mining periodic-frequent patterns. Periodic-frequent patterns are an important class of regularities that exist in a transactional database. A pattern is called periodic-frequent if it satisfies the thresholds of minimum support and maximum periodicity. Here, support is the frequency and periodicity is the maximum inter-arrival time of the pattern. In the literature, an algorithm called periodic-frequent pattern growth (PF-growth) was proposed which extracts the complete set of periodic-frequent patterns from transactional databases. Here, the transactional database is initially compressed into a prefix-tree like structure called periodic-frequent pattern tree (PF-tree), which is recursively mined to extract the patterns. The PF-tree explicitly maintains the transaction identifier information of each transaction. This enables the calculation of periodicity, but nevertheless the PF-tree size increases. In recent times, the amount of data generated from e-Commerce and social-networking sites are very huge. Mining periodic-frequent patterns from these datasets require large amounts of main memory and faster processing power. We propose the following two approaches to overcome these issues: (i) mining periodic-frequent patterns using the notion of period summary and (ii) a Map-Reduce based approach to extract periodic-frequent patterns. In the first approach, a novel compression technique called period summary is introduced to reduce the amount of memory consumed to extract periodic-frequent patterns. It is based on the observation that the periodic-frequent patterns can also be extracted by storing period summaries instead of transaction identifiers in the tree structure. The performance is improved as the memory required to store the period summaries is significantly less than the memory required to store the list of transaction identifiers. The process of merging period summaries is also introduced to find the support and periodicity values of a candidate pattern. Apart from memory optimization, the time consumed has also been lowered. This is because, the linear time-complexity for finding a candidate pattern’s periodicity using a list of transaction identifiers has been reduced to a constant time operation using period summaries. Experimental results on three real-world datasets show that the proposed approach using period summary performs better than the existing approach both in terms of memory and time. Further in the second approach, a Map-Reduce based approach to extract periodic-frequent patterns is proposed. As the real-world datasets are very huge, extraction of periodic-frequent patterns on a single machine takes a lot of time and in some cases it becomes difficult because of the memory constraints. The proposed approach is scalable and utilizes multiple machines by considering Map-Reduce framework. It consists of two Map-Reduce phases. In the first phase, all one-sized periodic-frequent patterns are derived and in the second phase, independent trees are constructed on different machines. These independent trees are mined parallely on different machines to find the complete set of periodic-frequent patterns. Further, we proposed the notion of partition summary to reduce the amount of data shuffled among the machines, which improves the performance. Experiments on Apache Spark’s distributed environment show that the proposed approach speeds up with increase in the number of machines. Also, the notion of partition summary significantly reduces the amount of data shuffled among the machines. Overall, the process of mining periodic-frequent patterns from transactional databases has been made efficient, both in terms of memory and time. This paves a way for various e-Commerce and social-networking sites to use the knowledge of periodic-frequent patterns in the areas of customer relation management, inventory management, recommendation systems and so on.

Abstract

Recently, the interest in Micro Aerial Vehicles (MAVs) and their autonomous flights has increased tremendously and significant advances have been made. The monocular camera has turned out to be most popular sensing modality for MAVs as it is light-weight, does not consume more power, and encodes rich information about the environment around. In this work, we present DeepFly, our framework for autonomous navigation of a quadcopter equipped with monocular camera. The navigable space detection and waypoint selection are fundamental components of autonomous navigation system. They have broader meaning than just detecting and avoiding immediate obstacles. Finding the navigable space emphasizes equally on avoiding obstacles and detecting ideal regions to move next to. The ideal region can be defined by two properties: 1) All the points in the region have approximately same high depth value and 2) The area covered by the points of the region in the disparity map is considerably large. The waypoints selected from these navigable spaces assure collision-free path which is safer than path obtained from other waypoint selection methods which do not consider neighboring information. In our approach, we obtain a dense disparity map by performing a translation maneuver. This disparity map is input to a deep neural network which predicts bounding boxes for multiple navigable regions. Our deep convolutional neural network with shortcut connections regresses variable number of outputs without any complex architectural add on. Our autonomous navigation approach has been successfully tested in both indoors and outdoors environment and in range of lighting conditions. We also propose a novel pipeline for detecting, localizing, and recognizing trees with a quadcoptor equipped with monocular camera. The quadcoptor flies in an area of semi-dense plantation filled with many trees of more than 5 meter in height. Trees are detected on a per frame basis using state of the art Convolutional Neural Networks inspired by recent rapid advancements showcased in Deep Learning literature. Once detected, the trees are tagged with a GPS coordinate through our global localizing and positioning framework. Further the localized trees are segmented, characterized by feature descriptors, and stored in a database by their GPS coordinates. In a subsequent run in the same area, the trees that get detected are queried to the database and get associated with the trees in the database. The association problem is posed as a dynamic programming problem and the optimal association is inferred. The algorithm has been verified in various zones in our campus infested with trees with varying density on the Bebop 2 drone equipped with fisheye wide angle vision. High percentage of successful recognition and association of the trees between two or more runs is the cornerstone of this effort. The proposed method is also able to identify if trees are missing from their expected GPS tagged locations thereby making it possible to immediately alert concerned authorities about possible unlawful felling of trees. We also propose a novel way of obtaining dense disparity map for quadcopter with monocular camera.

Abstract

In this thesis, we investigate spectral graph theoretic techniques especially heat-kernel embedding as a route to graph representation, in order to solve commonly known Pose-Graph applications in Robotics such as Simultaneous Localization and Mapping problem and mining Multi-Trajectory Pose Correspondences. The Simultaneous Localization and Mapping problem (SLAM) in robotics is typically modeled as a dyadic graph of relative pose measurements taken by the robot. The graph nodes store the values representing the absolute pose of the robot at a given point of time. An edge connecting two nodes represents robot movement and it stores the measurements taken by the robot sensor while moving between two nodes. The objective of the SLAM problem is to find the optimal global measurements best satisfying the noisy relative measurements [29]. This problem of optimal estimation on a graph given relative measurements is a well-studied problem , for which several results and algorithms are known [6, 7]. In this thesis, we explore the applications of spectral graph theory in assisting the problem of single and multi-robot SLAM. SLAM is generally solved as a least squares problem. Robust kernels which are less sensitive to outliers are used to deal with noise and outlier measurements. However, robust kernels tend to be dependent on initialization and can fail as the number of outliers increase. Therefore, it’s important to identify and prune the outlier (noisy) measurements represented by incorrect loop closure edges for an accurate pose estimate. Therefore, we propose a multi-scale Heat-Kernel analysis based loop closure edge pruning algorithm for the SLAM graph. We show that compared to other pruning algorithms, our algorithm has a substantially higher precision and recall when compared and is able to handle a large amount of outlier measurements. We have corroborated results on several publicly available datasets and several types of noise. Our algorithm is not restricted to SLAM graphs only, but has a much wider applicability to other types of geometric graphs. Furthermore, in the case of multi-robot SLAM problem, we consider the problem of finding pose matches between trajectories of multiple robots in their respective coordinate frames or equivalent matches between trajectories obtained during different sessions. Pose correspondences between trajectories are mediated by common landmarks represented in a topological map lacking distinct metric coordinates. Despite such lack of explicit metric level associations, we mine preliminary pose level correspondences between trajectories through a novel multi-scale heat-kernel descriptor and correspondence graph framework. These serve as an improved initialization for ICP (Iterative Closest Point) to yield dense pose correspondences. The set of models and framework proposed in this thesis could act as the basic building blocks in the future works attempting to advance the science of building smarter SLAM systems.

Abstract

A decade or so ago, setting up online businesses called for upfront investments in hardware and software. It also required regular expenses in, maintenance, upgrades etc. However, with the advent of cloud computing, this infrastructure was now able to be “rented” from a shared pool of resources which was present remotely. This was much cheaper than investing in one’s own hardware/software and provided many other advantages such as scalability, reliability, maintenance etc. Today, any new online business can launch its application with minimal costs, just by renting servers on a cloud. Load balancing means optimizing the distribution of workloads across multiple computing resources, to maximize the efficiency of each resource. Load balancing can be done at different layers of the stack, like application, network, CPU, disk etc. but in this thesis, we focus on improving it at the application layer and the network layer. We first look at an example of load balancing at the application layer. Most applications on the cloud are made to be horizontally scalable, i.e. addition of more number of servers would enable the application to handle more load. However, this also causes an increase in the costs to the business, for renting more number of servers. Therefore, it is important to distribute the load among servers smartly, so that a smaller number of servers are able to handle a given load. This requires good data distribution strategies and load balancing algorithms which adapt to the requests and the kind of data being accessed. Today, most of the companies which work with BigData use NoSQL databases to store huge volumes of data. They prefer NoSQL over relational databases because NoSQL databases are horizontally scalable, and have much better read-write performance due to the lack of a schema. Distributed Key-value stores are a type of NoSQL database which is used heavily in most applications, for storing billions of key-value pairs. Key-value stores are required to have a very high throughput as the applications using them need to perform millions of queries/updates per second. Having good load balancing algorithms helps in achieving a better throughput using the same number of servers. We analyze, compare and look at trade-offs in different load distribution schemes for consistent hashing in distributed key-value stores. Different traffic patterns, including an adversarial pattern, were constructed to test the load distribution. A simulator was made for each load distribution scheme and the load on each node was recorded. It was shown that increasing the number of consistent hash rings doesn’t change the load distribution characteristics in simple traffic scenarios, but in the case of adversarial traffic, increasing the number of hash rings leads to an improvement of around 15% in the load distribution statistics. Secondly, we look at an example of load balancing at the network layer. Nowadays, large datacenters are moving from a traditional network to a software-defined network. Software Defined Networking( SDN) lets the network administrator create his own software for defining rules to create flow routes. Since the network administrator knows about the topology and other specifications of the network, it is possible to make packets take different routes based on the various requirements, by just programming the OpenFlow controller. There are different kinds of applications with different requirements in a datacenter. Some require low latency and are not sensitive to bandwidth, others require low packet loss etc. Thus, each application has its own requirements profile. For example, a gaming server hosted on the cloud would require extremely low latency, but would not care about bandwidth. Video streaming services, on the other hand, are sensitive to bandwidth and packet loss. In the existing networks, it is very hard to control the routes that the packets take. We create an OpenFlow controller, which uses the requirements profile of each application using the network and tries to route traffic to optimize the network parameters that the application is most sensitive to. The controller is able to adapt to changing network conditions, and intelligently updates existing routes to accommodate for the network disruptions. We test it in different scenarios with different application requirements and study the improvements that the new controller gives over the existing one. We simulate and show that file transfer of 10MB on an unstable network took 168 seconds using a simple controller, and was optimized to 88 seconds using our controller. We also simulate video streaming on an unstable network and show that our controller adapts to these fluctuations in the network and pro-actively re-routes traffic, to make the stream non-lossy. We also looked at how we can optimize migration of virtual machines for load balancing by leveraging the knowledge of migration, on t

Abstract

Indian languages have a rich literature that is not available in digitized form. Attempts have been made to preserve this repository of art and information by maintaining a digital library of scanned books. However, this does not fulfill the purpose as indexing and searching the documents is difficult in images. An OCR system can be used to convert the scanned documents to editable form. However, the OCR systems are error prone. These errors are largely unavoidable and occur due to issues like poor-quality images, complex font, unknown glyphs etc. A post-processing system can help in improving the accuracy by using the information about the patterns and constraints in the word and sentence formation to identify the errors and correct them. OCR is considered to be a problem attempted with marked success in Latin scripts, especially English. This is not the case with Indic scripts as the error rates of various OCR systems available are comparatively high. The OCR pipeline includes three main stages, namely segmentation, text recognition and post-processing. We observe that Indic scripts have complex scripts and glyph segmentation itself is a challenge. The existence of visually similar glyphs also makes the recognition process difficult. The challenges faced in the post-processing stage are largely due to the properties of Indian languages. The inflectional properties of some languages like Telugu and Malayalam and agglutination of words creates issues due to the enormous and growing vocabulary in these languages. Unlike alphabet system in English, Indic scripts follow alphasyllabary writing system. Hence the choice of unicodes as the basic unit of a word is questionable. Aksharas which are a more meaningful unit is considered as a better alternative to unicodes. In this thesis, we analyze the challenges in building an efficient post-processor for Indic language OCR s and propose two novel error detection techniques. The post-processing module deals with the detection of errors in the recognized text and correction of those detected errors. To understand the issues in post-processing in Indian languages, we first perform a statistical analysis of the textual data. The unavailability of huge corpus prompted us to crawl various newspaper sites and Wikipedia dump to obtain the required text data. We compare the unique word distribution and word cover of popular Indian languages with English. We observe that languages like Telugu, Tamil, Kannada and Malayalam tend to have huge number of unique words compared to English. We also observe how many words get converted to other valid words in the language, using the Hamming distance between the words as a measure. We empirically analyze the effectiveness of statistical language models for error detection and correction. First we use an ngram model for detection of errors in the OCR output. We use akshara splitwords to create a bigram and trigram language model which gives the probability of a word. A word is declared as an error word if it has lower probability than a pre-computed threshold value. For error correction, we replace the lowest probability ngram with a higher probability one from the ngram list. We observe that akshara level ngrams perform better than unicode level ngram models in both error detection and correction. We also discuss why the dictionary based method, a popular method used in English, is not a reliable solution for error detection and correction in case of Indic OCR s. We use a simple binary dictionary method for error detection, wherein if the word is present in the dictionary, it is tagged as a correct word and error otherwise. The major bottleneck in using a lexicon is the enormous words in the languages like Telugu and Malayalam. In error correction, we use Levenshtein and Gestalt scores to select the candidate words from the dictionary for replacement of error word. Inflection of words causes issues in selecting the correct words as the candidate list consists of many words which are close to the error word. We propose two novel methods for detecting errors in the OCR output. Both the methods are language independent and does not require knowledge of language grammar. For detecting the errors in the OCR output, the first method proposed uses a recurrent neural network to learn the patterns of errors and correct words in the OCR output. The second method is using a Gaussian mixture model based clustering technique. Both methods use a language model of unicode as well as akshara split words in creating the features. We argue that aksharas are a better choice as the basic unit of a word than unicode. An akshara is formed by the combination of one or more unicode characters. We tested our method on four popular Indian languages and report an average error detection performance above 80% on a dataset of 5 K pages recognized using two state of the art OCR systems.

Abstract

This thesis investigates different approaches proposed in literature to identify the semantic relations in nominal compounds. Nominal compounds have received a great deal of attention in the last decade,owing to two main reasons - the increasing frequency with which nominal compounds occur in language, and the challenges they pose in most natural language processing applications like information extraction and retrieval, document summarization, machine translation and the like. Interpreting the semantics of nominal compounds in particular has been a popular research topic in recent times for reasons beyond just the impactful presence of compounds, like the challenges in explicating the semantic relation between constituents of the compound which is not-so-obvious to a machine as it is to a native speaker of the language. Most of the approaches proposed prior to this work are predominantly statistical techniques or treat compound interpretation as a classification task using a standard set of semantic relations as the prediction labels. The drawbacks of purely statistical and computational approaches is that they often a require large training dataset or corpus with a good distribution across all types of semantic relations, and often have no underlying lexical knowledgebases to support any data sparsity issues that may arise. Some of these approaches even involve preprocessing of large and unstructured databases like dictionaries and corpora which is inefficient and time-consuming. I motivate the need for exploring a new school of thought, quite opposite to the approaches that use computations backed up by knowledgebases . I explore in this thesis, the creation of hybrid systems that mine information from lexical and semantic knowledge resources like ConceptNet and WordNet, and are sufficiently backed by computational measures as necessary, to handle compounds outside the scope of these resources. Such systems overcome the obvious drawbacks of purely statistical and supervised learning tasks. I discuss two popular generic-domain ontologies called WordNet and ConceptNet in terms of the representational schema adopted in these ontologies to capture nominal compounds, and from the perspective of using these ontologies for labeling compounds with semantic relations. Most frequent issues encountered with these ontologies were identified as the lack of sufficient semantic information for certain nominal compounds, and the incompleteness of these ontologies in terms of capturing all the different categories of nominal compounds using a generic representational schema. I propose a new representation schema that identifies uniqueness of compounds and build a well structured purpose-centric ontology called PurposeNet centered around this representational schema. The ontology-search approach proposed in this thesis uses simple lookup techniques on indexed and preprocessed PurposeNet to derive the semantic relation between head and modifier in a nominal compound. The same ontology-search was then tailored to suit the representation used in WordNet and ConceptNet too. Comparison of results of the ontology search on all the three ontologies indicates that the best performance was on PurposeNet. While the results are definitely motivating, the ontology-search approach is not robust enough to handle different types of nominal compound constructions in the generic domain. I show that combining this ontology-search approach with semantic relatedness measures based on WordNet makes our compound interpretation system robust due to collation of semantic information from multiple resources. This hybrid system achieves state-of-the-art results on our standard test set of compounds. Lastly, I also study the feasibility of using the same approach based on PurposeNet and English WordNet as is, to label nominal compounds in other languages which have meager knowledge resources. I choose to extend this approach for nominal compounds in Hindi, by translating compounds from Hindi to English using different lexical resources like the Hindi WordNet 1 and IITB Hindi-Universal Word dictionary 2 and then running them through our hybrid compound interpretation system. While the results are not very encouraging due to various issues like change in the structure of compound after translation or lack of coverage for borrowed words in the lexical resources used, they nevertheless indicate that this approach is re-usable for interpreting compounds from other languages, with the help of context-based translation systems that take into consideration the context and structure of the nominal compound in its source language.

Abstract

Short texts play a major role in our day-to-day communication in many forms such as emails, chat, tweets, news headlines, image captions and many more. Many techniques have been developed in the field of natural language processing to automatically process such text at scale and apply it in areas apart from other NLP applications like education, law, healthcare, social platforms and security. This thesis presents automatic identification of semantic similarity between two short texts. There is a large usage of short texts and messaging in our real life. We explore and study dialogues and propose techniques for the automatic identification of subtopic boundary in Hindi dialogue using semantic similarity as a measure. We observe that there is a need for a semantic textual similarity system for Indian languages. One of the direct applications of a semantic textual similarity system is in dialogue based intelligent tutoring systems, where the answer of the user is assessed by comparing its similarity with the answer given by experts. Identification of short text similarity is an important research problem with application in a multitude of areas. Machine translation evaluation is another example, where the textual similarity between the system output and the gold standard output is used to evaluate the accuracy of the system. The direct application of STS is also in answer sentence identification in question answering applications. In natural languages, similar ideas can be linguistically expressed in very different ways, thereby making the task of semantic similarity challenging. For European languages, the task of semantic textual similarity has been studied to a great extent and various techniques have been proposed for those languages, but for Indian languages work has been very limited. This research describes our work on semantic textual similarity by proposing an annotation scheme for grading semantic similarity between two sentences. We also propose and describe methods for automatic identification of semantic similarity between short texts for Hindi language. The proposed STS algorithms are applied to tasks such as machine translation evaluation and subtopic boundary identification.

Abstract

Penn Treebank has proved the importance of treebanks as a linguistic resource for NLP. The current research presents an effort to develop a pilot treebank for Hindi, which could be used for creating a large scale treebank for Hindi. Building a treebank requires a computational grammar framework, an annotation scheme based on a chosen grammar, guidelines for annotating various types of constructions in the concerned language, and other related resources such as verb frames, etc. Since Hindi has a relatively free word order, dependency grammar formalism is well suited for it. So we chose Computational Paninian Grammar framework [36]. Panini’s grammar is a dependency grammar [99, 162]. Hence, the scheme for annotating treebanks for Indian languages was developed based on this framework. As part of this study, a pilot treebank for Hindi (HyDT – Hyderabad Dependency Treebank for Hindi) [21] was developed which was released for ICON-2009 (International Conference on Natural Language Processing-2009) [86]. The scheme [21] and guidelines for treebank annotation for Hindi developed during this study were modified and are being used for a multi-layered and multi-representational treebank for Hindi and Urdu [39, 42, 188] which is a collaborative project between various Universities. As part of this study, I annotated about 2230 sentences of Hindi from CIIL (Central Institute of Indian Languages, Mysore) corpus. Some part of data annotation was done by another annotator whose annotation was later validated by me. Various issues encountered during the annotation were studied and resolved to strengthen the scheme. I discuss some of the Hindi constructions which were intensely analyzed such as Causatives, Relative clauses, Conjunct verbs, Perception verbs, Conditionals, etc. We also looked in detail at how to treat ellipsis in a dependency Treebank (HyDT). I then present the detail study of Causative verbs [20] and Conjunct verbs [19] in which I show the classification of Hindi causative verbs and the diagnostics used to identify the conjunct verbs, respectively. The study of these Hindi constructions helped us in updating the existing guidelines for further annotation. Along with the creation of Hindi Treebank (HyDT), I also created a supplementary resource of verb frames for 687 Hindi verbs. I present the work on verb frames [22] for Hindi verbs and show the methodology used in preparing these frames and the criteria followed for classifying Hindi verbs. Verb frames were developed following Paninian Grammatical framework. Verb frames provide us the arguments that a particular verb can take in a particular sense, i.e., they show mandatory dependency relations for a verb. The main goal of this work is to create a linguistic resource which will prove to be indispensable for various NLP applications. It is also helpful in preparing demand chart for Hindi parser [84, 25]. It is also helpful for the annotators in deciding various dependency relations for a given verb in the corpus. I have also worked on the mapping between Propbank annotation and dependency annotation, based on Paninian Grammatical Framework [21, 36]. I have also discussed the use of HyDT data (Hyderabad Dependency Treebank for Hindi) [21] in various experiments.

Abstract

With the increasing computational complexity, hardware accelerators are finding lot of usage in improvising holistic system performance. The scalable multi-core processor architecture together with hardware accelerators is able to significantly boost up the system performance in high-speed computing. Such hardware accelerators require a connectivity between the processor system and the accelerating hardware for communicating data and control signals. Depending on the system level requirement, a se- rial or a parallel interface can be defined between the processor system and hardware accelerator block. The light weight serial communication protocol described here can be used to establish high speed serial connectivity between the System-on-Chip (SoC) and the hardware accelerator platform. Using the pro- tocol described in this work can transfer data up to 400 Gbps which makes the protocol suitable for high bandwidth applications. With the new protocol, the author has observed 3X reduction in area and 1.4X gain in latency over the other serial communication protocols. Parallel communication requires greater infrastructure cost due the connectors and board space used for communication. Using serial commu- nication channel, it is possible to reduce the overall system cost while maintaining data integrity. High Speed serial IOs with embedded transceiver blocks are used for serial communication. Communication using high speed serial IOs requires an initialization procedure to ensure integrated data transfer across the serial links. A physical layer initialization protocol defines the link establishment steps required before the actual data transfer. The overhead associated with the serial link initialization depends on variety of factors including the type of encoding used for transferring data across the link, initialization steps which confirm that the link partners are ready to exchange data, channel bonding procedure to in- tegrate multiple serial links to achieve higher bandwidth etc. In this work, I have discussed about a novel approach for initializing serial communication channel using 64B/66B encoding technique and a light weight channel bonding methodology to minimize the overall initialization latency while minimizing the logic area and static and dynamic power consumption.

Abstract

Machine Translation among Indian languages is a challenging problem, owing to multiple factors like their morphological complexity and diversity, in addition to lack of sufficient parallel data for most language pairs. Recent advances in the past have employed rule-based and statistical techniques to approach the problem of Indian language MT. Neural Machine Translation is an emerging technique depicting impressive performance, better than traditional MT methods in multiple aspects. This thesis demonstrates the application of Neural Machine Translation (NMT) techniques for Indian languages, with an emphasis in two important directions:- 1. Usage of specific linguistic features belonging to Indian languages to improve translation quality. 2. Building a robust NMT model which delivers efficient performance across different domains with a limited parallel corpus. We create NMT systems for 110 Indian language pairs utilizing various morphological and syntactic features to improve translation quality. We observe that although NMT models have a strong efficacy to learn language constructs, the usage of specific features further help in improving the performance. We also propose a three-phase integrated approach which helps in improving robustness across domains as well as translation quality in the absence of large parallel corpora. The three-phase training shows a significant improvement in accuracy as well as coverage over a baseline NMT model. This is the first effort towards developing Neural Machine Translation for Indian languages to the best of our knowledge.