Abstract

The major contribution of this work is the construction of binary matrices from combinatorial designs. These binary matrices with certain properties are used to construct different coded caching and distributed computing schemes. The coded caching scenario consists of a broadcast setup with a single server broadcasting information to a number of clients, each of which contains local storage (called cache) of some size, which can store some parts of the available files at the server. The centralized coded caching framework, consists of a caching phase and a delivery phase, both of which are carefully designed in order to use the cache and the channel together optimally. In prior literature, various combinatorial structures have been used to construct coded caching schemes. The binary matrix model proposed in this work, is used to construct the coded caching scheme. The ones in such a caching matrix indicate uncached subfiles at the users. Identity submatrices of the caching matrix represent transmissions in the delivery phase. Using this model, we then propose several novel constructions for coded caching based on the various types of combinatorial designs. While most of the schemes constructed in this work (based on existing designs) have a high cache requirement (uncached fraction being Θ( √ 1K) or Θ( 1K), K being the number of users), they provide a rate that is either constant or decreasing (O( 1K)) with increasing K, and moreover require competitively small levels of subpacketization (being O(Ki ), 1 ≤ i ≤ 3), which is an extremely important parameter in practical applications of coded caching. We also consider the distributed computing framework of MapReduce, which consists of three phases, the Map phase, the Shuffle phase and the Reduce phase. For this framework, we propose the use of binary matrices (with 0, 1 entries) called computing matrices to describe the map phase and the shuffle phase. Similar binary matrices were recently proposed for the coded caching framework. The structure of ones and zeroes in the binary computing matrix captures the map phase of the MapReduce framework. We present a new simple coded data shuffling scheme for this binary matrix model, based on a identity submatrix cover of the computing matrix. This new coded shuffling scheme has in general a larger communication load than existing schemes, but has the advantage of less complexity overhead than the well-known earlier schemes in literature in terms of the file-splitting and associated indexing and coordination required. We also show that there exists a binary matrix based distributed computing scheme with our new data-shuffling scheme which has strictly less than twice than the communication load of the known optimal scheme in literature. The structure of this new scheme enables it to be applied to the framework of MapReduce with stragglers also, in a straightforward manner, borrowing its advantages and disadvantages from the no-straggler situation. Finally, using binary matrices derived from combinatorial designs, we show specific classes of computing schemes with very low file complexity (number of subfiles in the file), with marginally higher communication load compared to the optimal scheme for equivalent parameters. We mark this work an another attempt to exploit the well-developed theory of combinatorial designs for the problem of constructing caching schemes and distributed computing schemes, utilizing the binary caching model we develop.

Abstract

Computers do not genuinely understand the natural language or have the ability to converse with humans on any arbitrary topic, resulting in a huge barrier separating us from computers. The researchers in natural language processing and understanding are driven by the impetus to break this barrier. Consequently, natural language processing techniques moved from methodologies involving complex sets of hand-written rules to machine learning and neural network-based methods. Recent works have extensively used methodologies of sequence-to-sequence models, back-translation based method, contextualized word representations, transformer-based models to enhance the ability of machines to understand natural languages. While sequence-to-sequence models enabled the computer to generate arbitrary output sequences after seeing the entire input, transformers helped in scaling up this ability to learn from an immensely large amount of text. Contextualized word representations enable machines to use pretraining and finetuning to give better representations more efficiently. On the other hand, back-translation methodologies allow machines to train text generation models without using a parallel dataset, exploiting the natural alignment of the representations already present in both domains of the generation space. Yet, none of the machines has reached the level of understanding and conversational fluency needed to pass the Turing test. This phenomenon necessitates the need for enhancing the contemporary methodologies revolving around natural language representations to improve the ability of machines to understand natural languages. Hence, in this thesis, we attempt to address some of the commonly faced challenges in natural language processing through enhanced language representations. Firstly, we investigate the task of subjective bias detection in Wikipedia text through the adaption of optimized contextualized word representation based methodologies exploiting pretraining and finetuning. We outperform the state-of-the-art by a margin of 5.6 in F1 score. Secondly, we explore the text classification task of predicting Disclosure and Supportiveness labels based on Twitter and Reddit datasets. Our contextualized word representation based ensemble methodology outperformed all other methods, being adjudged as the Best System in the CL-Aff Shared Task held at AAAI 2019. Thirdly, we explore the new task of fine-grained text classification of tobacco-related tweets. We release the SmokEng dataset, along with comprehensive data annotation schema. We show that our contextualized word representation based model outperforms the previous state-of-the-art by a margin of 1.8 in F1 score.Finally, we successfully accommodate attribute-control in the task of semi-supervised sentiment transfer through a sentiment-based loss. We release SentiInc, a simple framework for encoding sentimentspecific information in the target sentence while preserving the content information already present in the text. Experiments performed on the widely-used Yelp dataset show that SentiInc outperforms previous state-of-the-art methods by a margin of 11% in terms of G-Score.

Abstract

In recent years, Natural Language Processing (NLP) has gained widespread attention in many commercial and academic applications. Neoteric advances in Machine Learning and Deep Learning, aided by the rise of large annotated datasets, is the cornerstone of many state-of-the-art NLP systems and architectures. The one caveat of these advances is the availability of large annotated datasets for a particular NLP task. Since the conception of the Internet and the Digital Age, more and more information is stored digitally. Given the global nature of the current information sharing infrastructure, most of the data generated belongs to one of three languages : English, Mandarin or Spanish. This abundance of raw data, aids and motivates the creation of annotated NLP resources in these languages. On the other hand, the paucity of annotated data in most other languages makes it a challenging task to develop Deep Learning/Machine Learning based solutions for them. Hence there is a pressing need to pay special attention to develop novel solutions capable of performing NLP tasks in a low-resource setting. In this thesis, we attempt to tackle this data scarcity problem by introducing a novel approach for language invariant NLP which is capable of leveraging multiple monolingual datasets for training without any form of cross-lingual supervision. The proposed approach attempts to learn language agnostic features via adversarial training on multiple resource-rich languages, which can then be leveraged for inference on a low-resource language. The robustness of the proposed approach was tested on two well-defined NLP tasks: 1. Sentiment Analysis : For classifying the sentiment of a given document in a low-resource language we introduce the Language Invariant Sentiment Analyzer (LISA) architecture which learns language invariant sentiment features that outperforms the previous state-of-the-art methods on the Multilingual Amazon Review Text Classification dataset and achieves significant performance gains over prior work on the low-resource Sentiraama corpus. 2. Open Domain Event Detection : In the case of Open Domain Event Detection, which is a sequence labeling task, we introduce the Multi-Lingual Sequence Tagger (M-LiST) architecture which attained state-of-the-art performance in three languages of the TempEval2 corpus. A detailed analysis of our research highlights the ability of our architectures to achieve state-of-theart performance in the presence of minimal amounts of training data for low-resource languages.

Abstract

The exponential rise of Online Social Media (OSM) has enabled creation, distribution, and consumption of information at an unprecedented rate. However, it has also led to the burgeoning of various forms of online abuse like hate speech, offensive language, sexist and racist opinions, etc. Detection and curtailment of such abusive content is critical for avoiding its psychological impact on victim communities and thereby preventing hate crimes. Additionally, there are concerns over the rise of other forms of hate which have not been studied traditionally by the hate speech community such as antisemitism. Increasing cases of online antisemitism have become one of the major concerns because of its socio-political consequences such as the Holocaust and Israeli–Palestinian conflict. Though every web community has a guideline against online abuse, often these guidelines are vague and subjective. Moreover, due to the myriad of content on OSMs, it is nearly impossible to manually segregate instances of different forms of abuse, thereby calling for the automation of this moderation process using machine learning techniques. While previous work has addressed the problem of classifying user posts into various forms of abusive behavior, there has been less focus on estimating the severity of abuse and the target of abuse. Prioritization of particular abuse cases can be done if severity of abuse can be automatically assessed. Further, identifying if the abuse target is a person or a large group is critical to predict potential impact set and thereby predict if it could lead to real world crimes along with its scale. In our first work, we take a holistic approach towards analysing the different forms of abusive behaviours found in the web communities. We introduce three abuse detection tasks – 1) presence of abuse, 2) severity of abuse, 3) target of abuse. Due to the absence of a rich abuse-based dataset of considerable size, labeled across all aspects – presence, severity, and target, we provide a corpus with 7,601 posts collected from a popular alt-right social media platform Gab1 , each of which is manually labeled comprehensively across all such aspects. We also propose a Transformer based text classifier which outperforms the existing baselines on each of the three proposed tasks on the presented corpus. Our proposed classifier obtains an accuracy of ∼80% for abuse presence, ∼82% for abuse target detection, and ∼64% for abuse severity detection. Recently, there has been a sharp rise in the cases of antisemitism both in online spaces and in the real world. According to the Anti-Defamation League’s 2019 report, there has been a jump of 12% in the total cases of antisemitism, and a disturbing rise of 56% in antisemitic assaults.2 Hence, in the second work, we shift our focus to the problem of antisemitism found on online social media platforms. Antisemitism has been studied extensively from the perspective of social science but it has not been explored much by the hate speech community. We start by creating an extensively annotated multi-modal corpus on Gab posts consisting of text and images to study this problem. The task poses multiple challenges that include extracting signals across multiple modalities, contextual references, and handling multiple aspects of antisemitism. We present a multimodal deep learning system that detects the presence of antisemitic content and its specific sub-category using text and images from posts. In the absence of any publicly available benchmark corpus, we labeled a dataset with 3,509 posts from Gab. The presented multimodal system gives an accuracy of ∼91% and ∼69% on the binary and 4-class classification tasks, respectively, demonstrating the practical usability of the proposed system. To the best of our knowledge, both of the presented works are first in the respective directions. Through our studies we aim to lay foundation for future research works to explore the area of hate speech and online abuse in a more holistic and complete manner.

Abstract

The growing scope of virtual reality (VR) applications demonstrates the potential to address burgeoning problems in today’s and future world. The power of VR comes through the sense of embodiment, allowing people to experience the virtual environment from a first-person perspective [71]. It empowers the experiencer to perceive a real-world inside the simulated world, breaking the limits of the physical dimension, further enabling the capturing of natural psychological, behavioural and physiological responses as one would manifest in real-life situations. These measures act as a magnifying glass to understand the underlying perception and cognition processes of every interaction made with the environment. This thesis studies the affective-state (psychological), psycho-motor (behavioural) and skin conductance (physiological) response to the affective stimuli projected through VR. The stimuli consist of pleasant and unpleasant videos varied across valence and arousal dimensions, selectively chosen from the VR Stanford affective database [76]. In this research, emotional affective state was studied by asking participants to rate their feeling after exploring each video by using the self-assessment manikin (SAM) scale. We chose Skin-Conductance Response (SCR) to measure physiological response corresponding to the affective state while exploring the affective videos and used head-tracking data to measure the psycho-motor scanning behaviour in correspondence with the affective state. We conducted two studies, in which we used HMD to display the 360° affective videos to the participants. Participants were asked to explore the video, as they would do in real world, by making their head movement in all the three directions, i.e. yaw (left-right headmovement), pitch (up-down head-movement) and roll (shoulder-tilt head-movement). The first study focuses on the physiological and psychological relationship with VR emotional stimuli with an objective to find differences in SCR data in response to varying emotional stimuli. This was a pilot study carried out with 10 volunteers, and all were shown 10 videos (5 pleasant and 5 unpleasant). We observed no significant difference in physiological activity while exploring pleasant as compared to unpleasant emotional videos. The second study focuses on the behavioural and psychological relationship with VR emotional stimuli to analyse the differences in head-orientation in all the three directions while exploring pleasant and unpleasant videos. Here, 30 volunteers participated, and all were shown 4 videos (2 pleasant and 2 unpleasant), pseudo-randomly selected from 10 videos (5 pleasant and 5 unpleasant). We observed a significant positive correlation between the standard deviation of head-movement and valence and a significant positive correlation between scanning speed and valence. Participants showed natural exploring behaviour in the region-wise analysis, where they primarily explored the front view and rarely explored the rear-view. In the second study, we also assessed the individual predispositional emotional state by using Beck Depression Inventory-II (BDI) which groups the participants into minimal, mild, moderate and severe categories. The assessment was performed, keeping in view the increasing worldwide prevalence of depression and the current state of the art, demanding the need for the alternative assessment measures and diagnostic solutions where one-to-one supervision is not required. This is because the doctor-patient ratio is too low [118, 90] leading to huge gap, and the traditional methods involve subjective measures and interviews, making the whole process gradual and inaccessible. VR has the potential to bridge this gap by providing objective assessment measures and remotely accessible solutions. For this, the current research also compares the affective state and scanning behaviour across different depression groups. The relation between virtual affective experience and 360° exploration behaviour is discussed in light of the BDI categories.

Abstract

Upon nitrogen starvation, Schizosaccharomyces pombe exits the mitotic cell cycle and becomes irreversibly committed to the completion of the meiosis program. In meiosis, DNA replication (S-phase) is followed by two successive rounds of cell divisions (Meiosis I and Meiosis II) without intermediate interphase. Meiotic cell divisions are coordinated with sporulation events to produce haploid spores. In the last few decades, experiments on fission yeast have revealed different molecular players involved in two meiotic cell divisions, MI and MII. How the MI entry, MI to MII transition, and MII exit occur because of the dynamics of the regulatory network is not well understood. In this thesis, a comprehensive mathematical model of meiotic regulatory network was developed. This network was assembled from several experimental observations in the literature for meiotic cell divisions and exit. The core of the regulatory network is the regulation of cyclin-dependent kinase (Cdk) 1 and anaphase-promoting complex or cyclosome (APC/C) by meiosis-specific factors. The network was translated into a set of ordinary differential equations to simulate the dynamics of meiotic progression. We also performed one and two-parameter bifurcations to study the role of different feedback loops in meiosis. The model accounts for the phenotypes of several experimental data including single and multiple mutations and demonstrate the control strategy involving multiple feedback loops to yield two successive division cycles. The G2 to MI transition (MI entry) involves activation of meiosis-specific transcription factor Mei4, which controls the bistable activation of Cdk1. The logic of meiotic progression involves a transition from an oscillatory regime during MI-to-MII transition to a low Cdk1 state at the MII exit with an increase in meiosis-specific APC/C coactivators. The differential regulation of APC/C coactivators and its inhibitors is crucial for the dynamics of both MI-to-MII transition and MII exit. Further, we developed an integrated model of entire meiotic cell cycle by connecting the regulation of G1 to S phase transition and irreversible commitment with the meiotic progression. S-phase entry and commitment depends on the feedback regulation of an RNA-binding protein Mei2, which regulates inhibitor of meiotic mRNAs including Mei4. This integrated model captures the dynamics of wild type and 60 different mutations. The model serves as a key tool for experimentalist to perform in silico mutations and test the hypothesis. Overall, this thesis work provides systems-level interpretation of experimental data, deduces the molecular logic of meiosis and provides insights that help in further experiments and modeling.

Abstract

Motion planning deals with the computation of a sequence of robot states and control actions to navigate between a start and a goal robot state. As part of this planning, a robot must detect environmental objects, monitor their changes, reason about them, and finally compute kinodynamically feasible realtime trajectories for task-specific navigation. The work in this thesis is motivated by real-time cooperative motion planning applications. Such applications require multiple robots to work together and complete a common task through communication and negotiation. Furthermore, robots must leverage cooperation to improve sensing, thereby, allowing them to develop a shared understanding of the environment and plan their motion effectively. In our work, we primarily focus on the cooperative task of target following and its applications. The algorithms developed aim to be applicable towards aerial outdoor motion capture, search and rescue (SAR) applications for victim and rescuer tracking, and human target guided cooperative load transport applications. For the tasks mentioned above, computing real-time coordinated plans is challenging because of the associated high-dimensional multi-agent configuration space, non-linear inter-agent dependencies like collision-avoidance, limited communication bandwidth and range, non-convex and discontinuous perceptual constraints of common target perception and tracking, and, kinodynamically constrained common payload manipulation and transportation. The key contributions of this thesis that overcome the challenges mentioned above are as follows. We first develop a decentralized robot motion planning pipeline for target following, which mitigates the large planning configuration space problem. Additionally, we embed non-convex collision avoidance and inter-robot constraints into locally convex approximations, promoting the use of convex optimization methodologies for real-time planning. Model-predictive control facilitates high-frequency replanning, which handles imperfect system models, noisy observations, and communication limitations. Model-based optimal control algorithms and model-free sequential decision-making algorithms are leveraged to plan motion in perceptually driven tasks. Finally, a hierarchical decomposition of the complex kinodynamically constrained planning problem is proposed to compute feasible and safe trajectories in real-time. In the first part of the thesis, we introduce a novel decentralized multi-agent algorithm for real-time target following and collision avoidance using model-predictive control (MPC). The algorithm is the first of its kind convex-optimization-MPC approach and is a comprehensive solution to multi-agent collision avoidance for cooperative target following scenarios. The method is validated extensively in synthetic environments. In the second part, we empirically develop stochastic target perception models and embed it into the previously designed decentralized MPC to compute formation motion plans for cooperative target following. The controller actively computes robot control actions that minimize the fused uncertainty in target perception, thereby, binding perception and planning into a single MPC. Subsequently, we leverage model-free deep reinforcement learning algorithms to determine robot motion plans, which are optimized for target pose and shape estimation. Furthermore, we experimentally compare the performance of model-free and model-based approaches for the target following task. Both the approaches are evaluated and validated extensively in simulation and using real-robot experiments for the task of outdoor motion capture. In the third part, we analyze the challenges in kinematic planning for multirobot spatial payload manipulation and target following, and introduce a hierarchical motion planning solution that builds on the previously designed decentralized MPC. The performance is corroborated in challenging simulation environments. In the last part, we present a hierarchical energy-conscious control allocation algorithm which is constrained kinodynamically by multiple agents and electrically constrained by the actuators and battery limitations. The approach is the first of its kind control allocation algorithm, which models a multi-robot system as an over-actuated multi-agent system to plan its motion. The controller is verified in simulation, and a preliminary experimental testbed design is showcased for physical validation. We conclude this thesis by summarizing our novel model-predictive control formulation for the perceptually driven task of outdoor motion capture. Subsequently, we outline the key observations from the model-free approach for designing controllers for the same perceptually driven task. We then discuss the extension of the model-based target following controller towards planning motion of a high degree of freedom cooperative payload manipulation systems. Finally, we detai

Abstract

Majority of speech and natural language processing applications rely on word and document representations (or embeddings). The document embeddings encode semantic information which makes them suitable for tasks such as topic identification (document classification), topic discovery (document clustering), language model adaptation, and query-based document retrieval. These embeddings are usually learned from widely available un-labelled data; hence generative or probabilistic topic models which aim to capture the distribution of data are suitable. Although there exist several probabilistic and neural network-based topic models to learn these embeddings, they often ignore to capture the uncertainty in the estimated embeddings. Thus, any error in the estimation of these embeddings affects the performance in downstream tasks. The uncertainty in the embeddings is usually due to shorter, ambiguous or noisy sentences/documents. This thesis presents model(s) for learning to represent document embeddings in the form of Gaussian distributions, thereby encoding the uncertainty in their covariances. Further, these learned uncertainties in embeddings are exploited by the proposed generative Gaussian linear classifier for topic identification. This thesis proposes to use subspace multinomial model (SMM), a simple log-linear model for learning document embeddings. Experiments on 20Newsgroups text corpus show that the embeddings extracted from SMM are superior when compared to popular topic models such as latent Dirichlet allocation, sparse topical coding in topic identification and document clustering tasks. Using the variational Bayes framework on SMM, the model is able to infer the uncertainty in document embeddings, represented by (posterior) Gaussian distributions. Additionally, the common problem of intractability which appears while performing variational inference in mixed-logit models is addressed using Monte Carlo sampling via the re-parametrization trick. The resulting Bayesian SMM achieves state-of-the-art perplexity results on 20Newsgroups text and Fisher speech corpora. The proposed generative classifier exploits the learned uncertainty in the document embeddings; and achieves state-of-the-art classification results on the aforementioned corpora as compared to other unsupervised topic and document models. Furthermore, this thesis presents a multilingual extension of the Bayesian SMM for zero-shot cross-lingual topic identification. The proposed model achieves superior classification results when compared to the systems based on multilingual word embeddings and neural machine translation inspired sequence-to-sequence bidirectional long-short term memory models.

Abstract

With the increase in number and size of the problems in the computer vision domain, a lot of research has focused on speeding up the algorithms in these domains. Most of these algorithms require the solution of a linear system at some point. This thesis explores the application of numerical linear algebra(NLA) techniques for increasing the efficiently of algorithms related to the bundle adjustment[62] problem. Since, the dimensions of the linear systems associated with these problems is large, iterative methods such as conjugate gradients(CG) and generalized minimal residual(GMRES), are used. However, the efficiency of these methods depends on the condition number(defined as the ratio of the largest eigenvalue to the smallest eigenvalue) of the coefficient matrix. In general, the matrices associated with these problems are very badly conditioned. This motivates the use of preconditioning matrices, or preconditioners, which are close to the original matrix in some sense, and simplifies the solution of the linear systems. In this thesis, some novel preconditioners are developed and their effects on the efficiency of the algorithms are presented.Two NLA techniques, namely the domain decomposition method and the multigrid method, are used to develop preconditioners for the bundle adjustment problem. This is the first time these techniques have been applied to this problem. Another method is explored in this thesis that is based on deflation of unfavourable eigenvectors. These preconditioners are integrated with popular solvers like SSBA1 and Ceres[2] and their improvements are demonstrated experimentally

Abstract

The internet has caused a revolutionary information explosion and we have more resources available than ever before. The size of just the English language Wikipedia articles is about 159.69 GB. As the resources we consume keep getting bigger and more complex, we need systems to query these datasets. Initially, to query large databases, simple Information Retrieval techniques like fetching keywords and combining them with Boolean logic results were used. But now, we have search engines that can take queries in the form of multiple keywords and even questions. The retrieval side of these search engines also started with simple Document Retrieval methods like document frequencies and inverse document frequencies and has evolved to complex ranking methods based on neural networks that can fetch entire questions. Question Answering is a major field in NLP. It combines query formulation and document retrieval and in some cases, summarization of the retrieved documents. We now have complete end-to-end based systems that can fetch a suitable answer from a corpus. These systems can be trained on large datasets - both closed domain or open domain. However, these systems rely heavily on curated datasets which require a lot of manual labour and resources. For Indian languages where reliable and substantial datasets are scarce, neural networks that rely purely on data cannot be used. Hence, providing more data and introducing data-independent techniques becomes important. We shall explore both these aspects. First, we present a Reading Comprehension Task in Hindi - HindiRC. The dataset has been divided into different grades based on reading proficiency and we perform the baseline experiment on each grade separately which shows the increasing level of difficulty. Using various linguistic cues and metrics we further prove that the grades are reflective of linguistic complexity. In addition to addressing the data scarcity, we propose a Hindi Question Generation methodology. The rule-based method is based on Computational Paninian Grammar Framework relations. No additional resources are required and it can be used to increase the number of questions for Hindi datasets. We also prove that the generation method tends to overgenerate questions; further inflating the number. Along with the dataset and question generation method, we aim to provide more resources for Question Answering in Hindi.