Abstract

Trivia is any fact about an entity which is interesting due to its unusualness, uniqueness or unexpectedness. Trivia could be successfully employed to promote user engagement in various product experiences featuring the given entity. A Knowledge Graph (KG) is a semantic network which encodes various facts about entities and their relationships. We propose a novel approach called DBpedia Trivia Miner (DTM) to automatically mine trivia for entities of a given domain in KGs. The essence of DTM lies in learning an Interestingness Model (IM), for a given domain, from human annotated training data provided in the form of interesting facts from the KG. The IM thus learnt is applied to extract trivia for other entities of the same domain in the KG. We propose two different approaches for learning the IM - a) A Convolutional Neural Network (CNN) based approach and b) Fusion Based CNN (F-CNN) approach which combines both hand-crafted and CNN features. Experiments across two different domains - Bollywood Actors and Music Artists reveal that CNN automatically learns features which are relevant to the task and shows competitive performance relative to hand-crafted feature based baselines whereas F-CNN significantly improves the performance over the baseline approaches which use hand-crafted features alone. We also study the problem of relevance scoring of triples. We use the triples with “type-like” relations in which we employed a dataset with relevance scores ranging from 0 to 7, with 7 being the “most relevant” and 0 being the “least relevant”. The task focuses on two such relations: profession and nationality. We built a system which could automatically predict the relevance scores for unseen/new triples. Our model is primarily a supervised machine learning based one in which we use well-designed features which are used to a build a Logistic Ordinal Regression based classification model.

Abstract

Slow moving traffic in heavily populated cities, can many times result in loss of lives due to emergency vehicles not being able to reach their destination hospitals on time. Recent advances in the field of Intelligent Transportation Systems (ITS) makes it increasingly likely that vehicles in the near future will be equipped with advanced systems that allow inter vehicular communication. In this thesis, we assume the usage of such a system to optimize the lane level dynamics for an emergency vehicle (EV), traversing a multi lane stretch of road under a variety of traffic settings. In particular, we present the Fixed Lane Strategy (FLS) and the Best Lane Strategy (BLS) for EV traversal and perform an extensive agent based analysis to study their strengths and weaknesses. Through a series of experiments performed using the well-known traffic simulator SUMO, we could show that: (a) BLS performs better than SUMO strategy on all traffic settings we tested. (b) BLS performs better than FLS in settings that capture real-world traffic conditions involving congestion and uncertainties while FLS performs better in well-behaved conditions and (c) BLS was found to be the best strategy for the setting calibrated using real world data (obtained from NYCDOT).

Abstract

The behavior of discourse in a morphologically rich language such as Tamil has not been studied from a Computational Linguistics standpoint. A study of discourse in Tamil using a systematic framework such as PDTB would help identify the manner in which discourse features are realized in Tamil morphology. Added benefits of such a study include establishing the role of discourse in its relationship with other linguistic aspects, and facilitating cross-linguistic discourse analyses between language groups of differing morphological richness.

Abstract

Dynamic Programming(DP) is a powerful technique used for efficiently solving a vast set of complex optimization problems. It is widely used in areas of scheduling, string editing, packaging, bioinformatics, and inventory management [17]. Because of its impact and applicability across a wide range of domains, it is believed that DP will retain its importance in the future for science and engineering. This importance makes it one of the Berkeley 13 dwarfs [6]. It is thus not surprising that a lot of research attention is devoted in parallelizing DP problems. There are many classes of dynamic programming problems [11]. One of the important class is LDDP (Local Dependency Dynamic Programming). LDDP problems are ones in which update to an entry in the DP table is determined by the contents of neighboring cells [11]. Many non DP problems also mimic local dependency nature of LDDP problems. We collectively classify these local dependency problems (DP and non DP) as LDDP-Plus Problems. One more class of dynamic programming problems which is based on locality is HLDP (Horizontally Local Dynamic programming). HLDP class represents problems in which the contents of the cells from the immediately previous row/column decide the update to an entry in the DP table. Examples of both these classes of problems are common in many domains like speech processing (Dynamic Time Warping Algorithm [5], Non-Segmental Dynamic Time Warping [29]), bioinformatics (longest common subsequence, pairwise sequence alignment with affine gap cost [11]), image (Floyd-Steinberg dithering [15]) and the like. Many classical problems like 0/1 knapsack problem and checkerboard problem are also examples of these classes. Many other DP problems can also be modeled as LDDP / HLDP problems. Therefore, efficient parallel solutions to these two classes of problems is of immense research interest. While problem specific solutions are best way to achieve performance, generic solutions/frameworks enable the programmers and domain experts to extract reasonably good performance with little effort. This also enables them to take advantage of high performance computing platforms such as multi-core CPUs and GPGPUs with lesser effort. So it is meaningful to create generic parallel frameworks for solving a class of problems. The current architectural trend in parallel computing is towards a heterogeneous collection of devices involving CPUs and accelerators such as GPUs and Intel Xeon-Phi. Hence, the design and development of heterogeneous algorithms aimed at commodity heterogeneous computing platforms are of immense research interest. Heterogeneous algorithms for a variety of problems from domains such as sorting [7], graph algorithms [8] [16], sparse matrix computations [21], are reported in recent literature. In this thesis, we categorize LDDP and HLDP problems into various categories. We design and implement pure/heterogeneous algorithms for each of these categories of problems as a complete framework. Our framework can act as a software tool that can enhance the productivity of programming modern heterogeneous systems. Using our framework, users can readily create solutions for problems that follow LDDP or HLDP approach by just providing the function that dictates the dependency pattern.

Abstract

Proposition Bank or PropBank is a corpus in which the arguments of each verb predicate (simple or complex) are marked with their semantic roles [Kingsbury and Palmer, 2003]. PropBank establishes a layer of semantic representation in a Treebank already annotated with phrase structure or dependency structure. Adding the semantic layer through predicate-argument structure is quite challenging and these challenges can be comprehended from the fact that the syntactic structures in which a predicate’s arguments and its adjuncts are realized can vary based on the senses present in the sentence. Our effort of building a Proposition Bank for an Indian language, Urdu, [Anwar et al., 2016] spoken in major parts of India and Pakistan, describes the annotation process of labelling the predicate-argument structure on top of a Urdu Dependency Treebank [Bhat and Sharma, 2012]. The need for such a language resource arises from the fact that while Urdu Treebank does provide syntactico-semantic information, exploiting complete semantic information present in the form of predicate-argument structure in sentences will help in dependency parsing. Adding a semantic layer to the Dependency Treebank will help in addressing this requirement. The Urdu Proposition Bank is annotated by two annotators. With inter-annotator agreement statistics, we showed that there is almost perfect agreement between the two annotators which implies their analogous understanding of the annotation guidelines and of the linguistic phenomenon present in the Urdu language. We also introduce a statistical Semantic Role Labeler for Hindi and Urdu, two major Indian languages [Anwar and Sharma, 2016]. A Semantic Role Labeler automatically marks the arguments/valency of a predicate in a predicate argument structure of a sentence. The proposed system is based on supervised machine learning approach on Hindi and Urdu PropBanks which are being built for these languages [Vaidya et al., 2011] [Anwar et al., 2016]. Our approach is a 2-stage architecture in which, first the arguments pertaining to a predicate in a sentence of PropBank are identified by the system and finally those identified arguments are classified into one of the semantic labels of PropBank. Our system uses Logistic Regression machine learning algorithm and Support Vector Machines [Pedregosa et al., 2011] to predict and classify the arguments of a predicate respectively into one or more classes which happens to be the PropBank labels or semantic labels used to build the PropBanks. We show that our system has substantial precision of around 75% while identifying the arguments for Urdupredicates and 86% while doing so for Hindi. While classifying these identified arguments in semantic roles for Urdu and Hindi PropBank, our system reached a precision of around 83% and 58% respectively. We also experimented with automatic dependency parses extracted from dependency parsers and used them as features for our semantic role labeler. We wanted to observe how our semantic role labeler will perform when exposed to automatic dependency parses. As expected, there was a drop in the accuracy of the labeler when automatic parses were used as compared to when gold parses were used. To the best of our knowledge, this is the first such attempt of building a semantic role labeler for any Indian language. Past researches related to dependency parsing of Indian languages have shown that semantic information present in the sentences do provide important cues in parsing [Bharati et al., 2008] [Ambati et al., 2009] [Jain et al., 2013] [Bhat and Sharma, 2013]. After semantic role labeler for Hindi and Urdu was available, we wanted to study and observe the impact of semantic labels given by semantic role labeler in parsing. Therefore, we built an automatic pipeline using dependency parser and semantic role labeler. The semantic role labeler using automatic dependency labels gives semantic labels which subsequently are used as features for the dependency parser. The intuition behind building such a pipeline is that we wanted to exploit the accuracy and performance of parser when exposed to automatic semantic labels. We also worked on Inter-chunk Parsing and Intra-chunk Parsing. We performed several experiments to analyze the involvement of post-positions or case-markers in parsing. One such experiment included splitting the data-set available into 10 folds and analyzing the results of parser in each and every fold to get a better sight of performance of the parser.

Abstract

Annotated corpus is a linguistic resource which explicitly encodes the information at syntactic and semantic levels for each sentence. Annotated corpora play a crucial role in many applications of natural language processing (NLP). Error free and consistent annotated corpora is vital for these applications. Creating annotated corpora is an expensive and time consuming process. Errors or anomalies creep in due to human errors and sometimes because of multiple interpretations of the annotation guidelines. Maintaining the quality of the annotations is a challenging problem. This is because validating the annotated corpora and correcting these errors manually is an expensive and time consuming process. In particular, the validation process needs an expert’s time to detect and correct these errors, which is expensive. Hence, they need intelligent tools to automatically detect possible instances of errors in annotated corpora which they can validate quickly. Treebank annotation involves encoding information at POS, morph, chunk and dependency levels. Annotation requires a domain specific understanding of the language and dependency guidelines. Further, to validate the annotated corpora, we need experts of language and annotation guidelines. In this work, we address the problem of treebank validation and proposed novel approaches to detect errors automatically. To be specific, we address the issues at dependency level in the annotation process which is more vulnerable to errors due to complex rules in the dependency annotation schema. In our solution, we used ensembling methods on the parsers outputs. We hypothesize that the annotation and validation process should go in parallel rather than waiting for the entire corpus to be created. Our tool provides annotators error instances or inconsistent cases, so that they can clear the ambiguities in their understanding by reflecting on these small numbers of error instances. This process helps in early understanding of the errors committed in the annotation process. We also address the problem of skewed data sets, which is common in Indian languages by utilizing word embedding. Later, we attempt to build tools to correct the dependency errors automatically. Our work majorly investigated the error detection using dependency parsers and able to detect errors with an F-score values 71.18% and 42.19% respectively for Hindi and Telugu treebanks available. Our work includes some preliminary attempts to correct the errors automatically and we have increased the baseline precision of corpus from 88.59% to 92.29% for Hindi treebank.

Abstract

The statistics of professional sports, including players and teams, provide numerous opportunities for research. Cricket is one of the most popular team sports, with billions of fans all over the world. In this thesis, we address two problems related to the One Day International (ODI) format of the game. First, we propose a novel method to predict the winner of ODI cricket matches using a team-composition based approach at the start of the match. Second, we present a method to quantitatively assess the performances of individual players in a match of ODI cricket which incorporates the game situations under which the players performed. The player performances are further used to predict the player of the match award. Players are the fundamental unit of a team. Players of one team work against the players of the opponent team in order to win a match. The strengths and abilities of the players of a team play a key role in deciding the outcome of a match. However, a team changes its composition depending on the match conditions, venue, and opponent team, etc. Therefore, we propose a novel dynamic approach which takes into account the varying strengths of the individual players and reflects the changes in player combinations over time. Our work suggests that the relative team strength between the competing teams forms a distinctive feature for predicting the winner. Modeling the team strength boils down to modeling individual players’ batting and bowling performances, forming the basis of our approach. We use career statistics as well as the recent performances of a player to model him. Using the relative strength of one team versus the other, along with two player-independent features, namely, the toss outcome and the venue of the match, we evaluate multiple supervised machine learning algorithms to predict the winner of the match. We show that, for our approach, the k-Nearest Neighbor (kNN) algorithm yields better results as compared to other classifiers. Players have multiple roles in a game of cricket, predominantly as batsmen and bowlers. Over the generations, statistics such as batting and bowling averages, and strike and economy rates have been used to judge the performance of individual players. These measures, however, do not take into consideration the context of the game in which a player performed across the course of a match. Further, these types of statistics are incapable of comparing the performance of players across different roles. Therefore, we present an approach to quantitatively assess the performances of individual players in a single match of ODI cricket. We have developed a new measure, called the Work Index, which represents the amount of work that is yet to be done by a team to achieve its target. Our approach incorporates game situations and the team strengths to measure the player contributions. This not only helps us in evaluating the individual performances, but also enables us to compare players within and across various roles on a common scale. Using the player performances in a match, we predict the player of the match award for the ODI matches played between 2006 and 2016. We have achieved an accuracy of 86.80% for the top-3 positions in predicting the player of the match award, which is superior to previous works and other baseline models. This further proved the validity of our approach.

Abstract

Uneven terrain navigation and Urban Search and Rescue (USAR) Robots have been in demand in the past decade. Though tracks and legs have better traversing ability on an uneven terrain, they are still slower than wheeled robots with the same actuator system. Hence there is an added advantage for articulated wheeled robots for stair climbing. Stair Climbing is also a key functionality desired for robots deployed in USAR scenarios. Additionally, for USAR operations, a design that is capable of navigating rough terrain as well as crammed spaces is very beneficial. Keeping all these points in mind, a prototype is proposed consisting of three modules connected with each other through passive joints. It is propelled using an active pair of wheels per module. Since there are no actuators at the joints, the joints are not susceptible to losing operability while traversing on rugged terrain. However with the absence of actuators, we face the issue of the robot toppling over when an abnormally large obstacle is encountered. This shortcoming is overcome with the use of compliant joints. The compliant joints are designed by employing springs of optimal stiffness, which is calculated through an optimization formulation aided with the constraints presented by the static analysis of the robot. With this overall design considerations, variants of the design capable of carrying out various tasks is presented. This work presents the design process of the compliant modular robot (CMR) that is suitable for steep step descent, stair climbing and finally a reconfigurable multi agent system. An additional spring pair to help in the steep step descent was initially proposed and the analysis needed for its design was carried out. Experimental validation corroborated the prototype's performance. In the stair climbing conception of the CMR, necessary quasi static analyses were carried out and appropriate compliance was deployed at the joints of the CMR. The main contribution here was to use the Locus method to enumerate the phases through which the robot goes while climbing stairs. Following this, quasi static analysis was performed on each phase to determine the optimal stiffness of the compliant springs deployed at the joints. Numerical Simulations were carried out and experimental results were shown with an in-house fabricated prototype. Trials were run on various types of staircases to validate robustness of the prototype. Post this, the stair climbing compliant modular robot was improved to tackle overhang on stairs. A Multi Objective Optimization formulation was solved using Taguchi Grey Analysis and a multi-parameter based design was determined as a result that could climb stairs with overhang. Each module pushing the preceding module as the robot climbs its way across uneven terrain was one of the novelties of this project. Leveraging this modularity further, the Detachable Compliant Modular Robot (DCMR) was conceived. This is special in the sense of combining the two fields of Multi Agent Systems and Uneven Terrain Navigation. The idea is to be able to have multiple modules (capable of individual actions and exploration) collaborate to climb stairs and other uneven terrain. A spring is designed and used in the modular robot taking the worst-case-scenario of stairs encountered in an urban setting. In addition to the actuators at the wheels, an additional set of actuators per module are introduced to enable the detachment and re-attachment. The design additions and their trade-offs are discussed. Potential applications are presented with special focus on improving coverage of a map with obstacles/slabs large enough to merit exploration by climbing them. The problem of turning in crammed spaces is solved using the ability to detach of DCMR. The detaching & re-attaching capability, and stair climbing of the composite modular robot are demonstrated through experimentation using the prototype.

Abstract

The ability to convey information quickly, accurately, and efficiently is one of the primary aims of human innovation. With the invention of the electronic numerical integrator and computer, an interaction between informatics and telecommunication began which added faster data processing to distant communication. The conventional circuit switching was soon replaced by packet switching, and the TCP/IP protocol suite, facilitating communication between computers/heterogeneous machines, ultimately leading to the birth of the Internet. The advent of the Internet has resulted in the redefining of traditional modes of communication like radio, television and paper mail giving rise to services such as email, digital newspapers, Internet telephony and video streaming. With networks growing exponentially, modern communication methods have become the driving force of social evolution. The ever increasing amount of information being generated presents new challenges in terms of storage, transfer and security. Since computers can range from stand-alone to networked devices, various avenues of attacks are available to compromise information security. Ensuring confidentiality of information being transmitted and stored is therefore essential. Also known as access control, this can be achieved through authentication. Authentication is the process of verifying a claimed identity. The validation method can involve multiple factors with the level of security being proportional to the number and type of factors involved. Mutual authentication is where the involved parties simultaneously authenticate each other to establish a connection. It is most often implemented machine-to-machine through digital certificates where there is a chance of the user not realizing when the remote authentication fails. Challenge-response based mechanisms help mitigate this problem by detecting false end-points. In this thesis, we study the importance of authentication and key agreement in two different network applications – Internet of Things (IoT) and Session Initiation Protocol (SIP). The first study presents a new Elliptic Curve Cryptography (ECC) signaturebased authenticated key establishment scheme for applications in IoT environment. The proposed scheme accommodates password and biometric update as well as stolen/lost smartcard revocation phases. The proposed scheme has been proved to be secure using the widely-used Burrows-Abadi-Needham logic (BAN logic), informal security analysis, and also a formal security verification using the broadly-accepted Automated Validation of Internet Security Protocols and Applications (AVISPA) tool. The practical demonstration of the scheme is evaluated using the widely-accepted NS2 simulator for various network performance parameters. Finally, it is shown that the scheme provides more functionality features, and its computational and communication costs are also comparable with other existing approaches. In the next study, we focus on authentication in Session Initiation Protocol for Voice over IP environments. In this work, we present an efficient ECC based three-factor authentication and session key agreement scheme for SIP, which uses the identity, pass- word and personal biometrics of a user as three factors. The proposed scheme resolves the shortcomings in existing SIP authentication protocols. The proposed scheme also supports password and biometric update phase without involving the server and the user mobile device revocation phase in case the mobile device is lost/stolen. Formal security analysis under the Real-Or-Random (ROR) model and the broadly-accepted BAN logic ensures that the proposed scheme can withstand several known security attacks. The proposed scheme has also been analyzed informally to show that it can also withstand other known attacks. Simulation for formal security verification using the widely-known AVISPA tool shows that the scheme is secure against replay and man-in-the-middle attacks. Finally, high security, and low communication and computation costs make the proposed scheme more suitable for practical application as compared to other existing related ECC-based schemes for SIP authentication. Keywords:

Abstract

Active learning also known as query learning is a sub-field of machine learning. It relies on the assumption that if the learning algorithm is allowed to choose the data from which it learns, it will perform better with less training. Active Learning is predominantly used in areas where getting a large amount of annotated data for training is not feasible or extremely expensive. Active learning models aims to overcome the annotation bottleneck by asking queries in the form of unlabelled instances to be labelled by a human. In this way, the framework aims to achieve high accuracy using very less labelled instances resulting in minimization of annotation cost. In the first part of our work, we propose an Active Learning based Image Annotation model. Automatic image annotation is the computer vision task of assigning a set of appropriate textual tags to a novel image. The aim is to eventually bridge the semantic gap of visual and textual representations with the help of these tags. The advantages of the proposed model includes: (a). It is able to output the variable number of tags for images which improves the accuracy. (b). It is effectively able to choose the difficult samples that needs to be manually annotated and thereby reducing the human annotation efforts. Studies on Corel and IAPR TC-12 datasets validate the effectiveness of this model. In the second part of the thesis, we propose an active learning based solution for efficient, scalable and accurate annotations of objects in video sequences. We focus on reducing the human annotation efforts with simultaneous increase in tracking accuracy to get precise, tight bounding boxes around an object of interest. We use a novel combination of two different tracking algorithms to track an object in the whole video sequence. We propose a sampling strategy to sample the most informative frame which is given for human annotation. This newly annotated frame is used to update the previous annotations. Thus, by collaborative efforts of both human and the system we obtain accurate annotations with minimal effort. We have quantitatively and qualitatively validated the results on eight different datasets. Active Learning is efficient in Natural Language documents as well. Multilingual processing tasks like statistical machine translation and cross language information retrieval rely mainly on availability of accurate parallel corpora. In the third section we propose a simple yet efficient method to generate huge amount of reasonably accurate parallel corpus using OCR with minimal user efforts. We show the performance of our proposed method on a manually aligned dataset of 300 Hindi-English sentences and 100 English-Malayalam sentences. In the last section we utilised Active Learning for model updation in c QA system. Community Question Answering(c QA ) platforms like Yahoo! Answers, Baidu Zhidao, Quora, StackOverflow etc. provides experts to give precise and targeted answers to any question posted by a user. These sites form huge repositories of information in the form of questions and answers. Retrieval of semantically relevant questions and answers from c QA forums have been an important research area for the past few years. Considering the ever growing nature of the data in c QA forums, these models cannot be kept stagnant. They need to be continuously updated so that they can adapt to the changing patterns of Questions-Answers with time. Such updation procedures are expensive and time consuming. We propose a novel Topic model based active sampler named Picky. It intelligently selects a smaller subset of the newly added Question-Answer pairs to be fed to the existing model for updating it. Evaluations on real life c QA datasets show that our approach converges at a faster rate, giving comparable performance to other baseline sampling strategies updated with data of ten times the size.