Abstract

Recently, a lot of the standard algorithms in machine learning and computer vision need to be redesigned for handling large scale problems. In this thesis, we explore one such fundamental algorithm, which is inherent in almost every multi-view reconstruction system pipeline in computer vision. Recently, bundle adjustment has been the key component in Structure-from-Motion (SfM) problem. Bundle adjustment (BA) jointly optimizes the camera parameters and feature points parameters according to an objective function of reprojection errors. This joint optimization of camera parameters and feature points paramters for multi-view reconstruction formulate the BA problem as a non-linear least squares problem which is solved by some variant of the traditional Levenberg-Marquardt (LM) algorithm [44]. Most of the computation in LM goes into repeatedly solving the normal equations that arise as a result of linearizing the objective function. Some widely used methods like Cholesky Decomposition and Preconditioned Conjugate Gradients [25], to solve these normal equations still face some challenges in robustness, accuracy, and efficiency. In this thesis, we propose a deflated algebraic two-grid method has been used as a preconditioner for Generalized Minimal Residual Method (GMRES) [58], for solving these normal equations arising in the Bundle Adjustment process. We show that the proposed method is several times faster than iterative schur and jacobi schur [2] which are considered as state-of-the-art methods to solve the Bundle Adjustment problem. We verify the competence of our algorithm by benchmarking it against the stateof-the-art methods on publicly available Bundle Adjustment in the Large (BAL) dataset [3].

Abstract

As demands for high volume data exchanges increase in many memory applications, significant efforts have been devoted to improving I/O interface performance to achieve high bandwidth. However, the impedance mismatch between I/O driver and a transmitting channel causes signal reflection, interfering with the incoming data in terms of overshoot, undershoot, or ringing. I/O interface requires a minimum variation of output I/O driver impedance over process, temperature, and voltage variations to ensure high-quality signal integrity. The traditional approach of using an external resistor component to generate a constant reference for impedance calibration is not an effective solution considering the constraints due to shrinking package form factor and low-cost limitations of memory applications. This thesis proposes a novel I/O driver impedance calibration architecture and its circuit design using internally generated constant current reference. Also, designed a current mode Bandgap Reference circuit, which generates a constant current across Process and Temperatures variations. A voltage detect circuit is proposed to capture Supply Voltage variations and to compensate the current reference accordingly. To minimize the error in calibration codes, a low offset comparator is designed. IO driver with a combination of MOS device and a series poly resistor is used for better linearity in impedance. This thesis proposes and implements an independent calibration of Pullup and Pulldown IO drivers. The pullup driver calibration codes are not reused for pulldown driver calibration. It reduces the mismatch in impedance of Pullup and Pulldown drivers by eliminating propagation of any quantization error in Pullup calibration codes to Pulldown driver calibration. The proposed calibration scheme and the whole circuit was designed and implemented in 28nm standard CMOS technology using 1.8V supply voltage. In spice simulations of the proposed calibration design/scheme, the impedance variation of both pullup and pulldown driver is approximately +/-7% across process, temperature, and voltage variations. This reduced IO driver impedance variation is achieved using the proposed internally generated constant current source without using any external component resistor.

Abstract

Autonomous driving has evolved with the advent of deep learning and increased computational capacity in the past two decades. While many tasks have evolved that help autonomous navigation, understanding on-road vehicle behaviour from a continuous sequence of sensor data (camera or radar) is an important and useful task. Determining state of other vehicles and their motion helps in decision making for the ego-vehicle (Self/Our Vehicle). Such systems can be a part of driver assistance systems or even path planners for vehicles to avoid obstacles. Instances of such decision making could be, deciding to apply brakes incase an external agent is moving into our lane or coming opposite to us. Another instance would be keeping distance from an aggressive driver who is changing lanes and overtaking frequently could be helpful and safer. Specifically, our proposed methods classify the behaviours of on-road vehicles into one of the following categories-{Moving Away, Moving Towards Us, Parked/stationary, Lane Change, Overtake}. Many current methods leverage 3D depth information using expensive equipment, such as Lidar and complex algorithms. In this thesis, we propose a simpler pipeline for understanding vehicle behaviour from a monocular (single camera) image sequence or video. This will help in easier installation of the equipment and helps in Driver Assistance systems. A simple video along with Camera parameters, scene semantics (Detected Objects in the images) are used to get information about the objects of interest (vehicles) and other static objects like lanes/poles in the scene. We consider detecting objects across frames as the pre-processing pipe-line and propose two main methods, 1.Spatio-temporal MRGCN (Chapter:3) and 2.Relational-Attentive GCN (Chapter:4) for behaviour detection of vehicles. We divide our process of identifying behaviours into learning positional information of vehicles first, and then observing them across time to make a prediction. The positional information is encoded by a Multi-Relational Graph Convolutional Network (MR-GCN) in both the methods. Temporal information is encoded by recurrent networks in Method 1, while it is formulated inside the graph in Method 2. We also showcase how Attention is an important aspect in both our methods through our experiments. The proposed frameworks can classify a variety of vehicle behaviours to high fidelity on datasets that are diverse and include European, Chinese and Indian on-road scenes. The framework also provides for seamless transfer of models across datasets without entailing re-annotation, retraining and even fine-tuning. We provide comparative performance gain over baselines and detail a variety of ablations to showcase the efficacy of the framework.

Abstract

Autonomous cars and fixed-wing aerial vehicles (FWV) have the so-called non-holonomic kinematics which non-linearly maps control input to states. As a result, trajectory optimization using such a motion model becomes highly non-linear and non-convex. In this work, we present two alternate methods to efficiently solve this trajectory optimization problem. The first approach is based on the path velocity decomposition paradigm. The optimization underlying this approach has a two layer structure wherein first, an appropriate path is computed for the vehicle followed by the computation of optimal forward velocity along it. A key feature of this approach is that it offloads most of the responsibility of collision avoidance to the velocity optimization layer for which computationally efficient formulations can be derived. In particular, we extend our previously developed concept of time scaled collision cone (TSCC) constraints and formulate the forward velocity optimization layer as a convex quadratic programming problem. In the second approach, we improve the computational tractability of the problem by reformulating trajectory optimization in terms of a set of bi-convex cost and constraint functions along with a non-linear penalty. The bi-convex part acts as a relaxation for the non-holonomic trajectory optimization while the residual of the penalty dictates how well its output obeys the non-holonomic behavior. We adopt an alternating minimization approach for solving the reformulated problem and show that it naturally leads to the replacement of the challenging non-linear penalty with a globally valid convex surrogate. Along with the common cost functions modeling goal-reaching, trajectory smoothness, etc., the proposed optimizer can also accommodate a class of non-linear costs for modeling goal-sets, while retaining the bi-convex structure. We perform validation of first approach on autonomous driving scenarios to compute lane change, overtaking and merging maneuvers among multiple dynamic obstacles. We later benchmark the second approach against those based on sequential quadratic programming (SQP) and interior-point methods on common examples from autonomous driving and FWV navigation and show that it produces solutions with similar cost as the former while significantly outperforming the latter. Furthermore, as compared to both SQP and interior-point optimizers, it achieves more than 20x reduction in computation time.

Abstract

In recent years there has been an increase in the generation of health care documents such as clinical trials, discharge summaries, and Electronic Health Records (EHRs). These documents contain a lot of actionable data buried in them. Actionable data includes a set of events and activities that occur in health care processes. This valuable information has led to an increased scope for research on biomedical literature. However, most of the data reside in the form of free text which makes it difficult to extract useful information. The thesis develops methods to automatically extract semantics from the health care documents in an effort to check conformance of the treatment processes with standard treatment guidelines. Discharge summary is one of the major sources of information about the treatment process. A discharge summary contains information about a patient’s one or more encounters with health care service providers, stored electronically to share across different stakeholders in the health care system. The discharge summary has summarized information that includes a wide range of information like chief complaint, physical examination, vital signs, lab test results, recommended medications, and discharge status. Text analytics over these documents has various applications and would help the caregivers to provide better health care. The main theme of the thesis is to automatically extract medical semantics from discharge summaries. We focus on semantics such as medical entities, attributes of medical entities and relationships between these entities. Further, we illustrate an application of these semantics on a Treatment Process Conformance Checking usecase. Automatically identifying medical entities from biomedical literature is referred to as Biomedical Named Entity Recognition (BMNER). BMNER is one of the important tasks in the field of biomedical text mining. BMNER involves identifying continuous named entities and discontinuous named entities. Discontinuous entities are comprised of two or more non-consecutive components. For example, in a sentence, “The aortic root is moderately dilated.”, the disjoint entity “aortic root...dilated” is composed of two components, “aortic root” and “dilated”. Most of the prior works on BMNER were based on feature-dependent machine learning techniques and focused only on continuous named entities and not discontinuous entities. Traditional BIO tagging schema is unable to tag sentences with discontinuous entities. In this thesis, we propose a novel systematic BIODT tagging schema to identify both continuous and discontinuous named entities. We explore deep learning models that require limited feature engineering for tagging the entities. Our results illustrate that our BIODT tagging schema performs better than traditional BIO and other tagging schemas and overcomes label sparsity problem in identifying both continuous and discontinuous biomedical entities. We also show that our neural network model with BIODT tagging schema has shown superior performance than state-of-the-art methods on CLEF 2013 and SemEval 2013 datasets which were based on feature-dependent machine learning techniques. Mere medical entities cannot give enough information for understanding the condition of the patient. In a given context, characteristic of a medical entity is based on different attributes like temporal information, severity and progression of the disease. In this work, we consider ten attributes that allow us to understand the main details regarding the condition of the patient. They are Negation Indicator, Subject Class, Uncertainty Indicator, Course Class, Severity Class, Conditional Class, Generic Class, Body Location, DocTime Class, and Temporal Expression. In this thesis, we present a methodology with rule-based and machine learning approaches to identify each of these attributes. We evaluate our methodology on ShARe/CLEF eHealth Evaluation Lab 2014 Challenge dataset on attribute level and system level accuracy. Mining relationships between treatment(s), test(s) and medical problem(s) is vital in the biomedical domain. This helps in various applications such as decision support system, safety surveillance, and new treatment discovery. In this thesis, we propose a deep learning approach that utilizes both word level and sentence-level representations to extract the relationships between treatment and problem. While deep learning techniques demand a large amount of data for training, we make use of a rule-based system particularly for relationship classes with fewer samples. Our final relations are derived by jointly combining the results from deep learning and rule-based models. Our system achieved a promising performance on the relationship classes of I2b2 2010 relation extraction task. Finally, we employ the above pipeline of tasks such as Biomedical Named Entity Recognition, Medical Entity Attribute extractio

Abstract

Scientific knowledge is one of the greatest assets of humankind. This knowledge is recorded and disseminated in scientific publications, and the body of scientific literature is growing at a tremendous rate. As scientific communities grow and evolve, there is a high demand for improved methods for finding relevant papers, comparing papers on similar topics and studying trends in the research community. Whenever researchers start working on a problem, they are interested to know if the problem has been solved previously, methods used to solve this problem, the importance of the problem and the applications of that problem. Automatic methods of processing and cataloging that information are necessary for assisting scientists to navigate this vast amount of information and facilitating automated reasoning, discovery, and decision-making on that data. All these tasks involve the common problem of extracting structured information from scientific articles. This leads to the requirement to find automatic ways of extracting such structured information from the vast available raw scientific literature, which can help summarize the research paper and the research community. This thesis focuses on processing scientific articles and creating structured repositories such as knowledge graphs to find new information and make scientific discoveries. In this thesis, we propose a novel, scalable, semi-supervised method for extracting relevant structured information from the vast available raw scientific literature. We extract the fundamental concepts of aim, method, and result from scientific articles and use them to construct a knowledge graph. The algorithm makes use of domainbased word embedding and the bootstrap framework. Our approach also makes use of citation context apart from title and abstract on which most of the work relied till now. We show how the extracted concepts and the available citation graph can be used to represent the research community as a knowledge graph. We demonstrate our method on a sizeable multi-domain dataset built with the help of the DBLP citation network. Our experiments show the domain independence of our algorithm and that our system achieves precision and recall compared to state of the art. The tremendous amount of research publications available online aims to solve a lot of interesting problems. Some of the fields have been studied well and research problems have been solved with time. However, there are few problematic research problems which are yet not solved entirely and interests many researchers. In this thesis, we also aim to find research fields that are saturated and research fields that need to be explored yet by performing temporal analysis on top of the knowledge graph formed.

Abstract

Distinguishing neuropsychiatric disorders is challenging due to the overlap in symptoms and genetic risk factors. People suffering from these disorders face personal and professional challenges. Understanding the dysregulation of brain metabolism under disease condition can aid in effective diagnosis and in developing treatment strategies based on the metabolism. In this study, we reconstructed the metabolic network of three major neuropsychiatric disorders, schizophrenia (SCZ), bipolar disorder (BD) and major depressive disorder (MDD) using transcriptomic data and constrained based modelling approach. We integrated brain transcriptomic data from six independent studies with a recent comprehensive genome-scale metabolic model, Recon3D. The analysis of the reconstructed network revealed flux-level alterations in the peroxisome-mitochondria-golgi axis in neuropsychiatric disorders. We also extracted reporter metabolites and pathways that distinguish these three neuropsychiatric disorders. We found differences with respect to fatty acid oxidation, aromatic and branched chain amino acid metabolism, bile acid synthesis, glycosaminoglycans synthesis and modifications, and phospholipid metabolism. Further, we predicted network perturbations that transform the disease metabolic state to a healthy metabolic state for each disorder. These analyses provide local and global views of the metabolic changes in SCZ, BD and MDD, which may have clinical implications. In light of the current pandemic of COVID-19, we also focussed on understanding the pathogenesis in SARS-CoV-2 infection. Viruses hijack the host metabolism to redirect the resources for their replication and survival. The influence of SARS-CoV-2 on the host metabolism is yet to be fully understood. We analyzed the transcriptomic data obtained from different human respiratory cell lines and patient samples (nasopharyngeal swabs, peripheral blood mononuclear cells, lung biopsy, bronchoalveolar lavage fluid) to understand the metabolic alterations in response to SARS-CoV-2 infection. We explored the expres sion pattern of metabolic genes in Recon3D and identified key metabolic genes, pathways, and reporter metabolites under each SARS-CoV-2 infected condition and compared them to identify common and unique changes in the metabolism. Our analysis revealed host-dependent dysregulation of glycolysis, mitochondrial metabolism, amino acid metabolism, glutathione metabolism, polyamine synthesis, and lipid metabolism. We observed different pro- and antiviral metabolic changes and generated hypotheses on how antiviral metabolism can be targeted/enhanced for reducing viral titers. These findings warrant further exploration with more samples and in vitro studies to test predictions. Overall, this thesis highlights that metabolic network analysis techniques help to understand the pathogenesis of complex diseases like neuropsychiatric disorders and COVID-19, and aids in developing effective treatment strategies.

Abstract

Reinforcement Learning (RL) has proved its effectiveness by providing a way of modeling the agents’ behavior based on environmental feedback. Conventional RL employs a single monolithic agent that learns to solve the entire complex task on its own. In spite of its evident success this approach has some limitations (i) the joint state space for the complete task grows exponentially and often becomes intractable for standard RL techniques and (ii) a single monolithic agent is unable to exploit the problem structure. Fortunately complex domains are often composed of simpler subproblems that might be easier to learn. Modular reinforcement learning (MRL) has been primarily useful in leveraging such inherent structure in the problem domain. In MRL a complex decision making problem is decomposed into multiple modules which solve different components of the original problem. After such decomposition, the task of recomposing their individual knowledge to construct a global policy remains one of the main challenges in MRL. Often, subproblems addressed by different modules have conflicting goals, and incompatible reward scales. A composable decision making architecture requires that even the modules authored separately with possibly misaligned reward scales can be combined coherently. An arbitrator that coordinates the learnings of individual modules should consider module’s action preferences to learn effective global action selection across all the modules. We present a novel framework called GRACIAS that assigns fine-grained importance to the different modules based on their relevance in a given state, and enables composable decision making based on modern deep RL methods such as deep deterministic policy gradient (DDPG) and deep Q-learning. We provide insights into convergence properties of GRACIAS by exploiting connections to the two timescale stochastic approximation. We show that our approach is able to overcome the major limitations of existing algorithms and also reduce previous MRL algorithms to special cases of our framework. We experimentally demonstrate on several standard MRL domains that our approach works significantly better than the previous MRL methods, and is highly robust to incompatible reward scales. Our framework extends MRL to complex Atari games such as Qbert, and has a better learning curve than the conventional RL algorithms.

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.