Abstract

Traditional air pollution monitoring systems are bulky and expensive resulting in a very sparse deployment. In addition, the data from these monitoring stations may not be easily accessible. With the advent of internet of things (IoT) technology, millions of smart devices will be connected to each other as well as to the internet enabling easier air pollution monitoring. Low-cost portable sensors along with IoT can overcome the above two issues of traditional monitoring systems. This thesis focuses mainly on three aspects. Firstly, research, development and deployment of IoTbased dense air pollution monitoring using network low-cost sensor nodes in an Indian urban setting which is first of kind in India in terms of dense deployment and spatial coverage. Second, it deals with improving the energy consumption of the sensor nodes developed and finally, reducing the redundancy of the nodes. More specifically, a new adaptive sensing algorithm and hierarchical clustering based spatial sampling paradigm have been introduced. The results of the proposed implementations have been evaluated upon real-time deployment of the nodes. In total, ten low-cost IoT nodes monitoring particulate matter (PM), which is one of the most dominant pollutants, are developed and deployed in a small educational campus in Indian city of Hyderabad. New datasets were created in the process which are thoroughly investigated by applying various preprocessing, signal processing and clustering techniques. Different analyses such as correlation and spatial interpolation are done on the data to understand efficacy of dense deployment in better understanding the spatial variability and time-dependent changes to the local pollution indicators. For reducing energy consumption, an adaptive, non-parametric method to change the sensing rate using the maximum frequency estimate based on recent historical data. The proposed algorithm has been tested on the data collected over one year from an IoT network consisting of multiple PM sensor nodes. A performance comparison of the proposed scheme with the existing approach shows the effectiveness and performance improvement in terms of Reduction Factor (RF) and Mean Absolute Error (MAE). For removing the redundant nodes, a framework based on Hierarchical Agglomerative Clustering for deciding an optimal number of nodes and which nodes in an IoT network of sensor nodes has been proposed. The approach proposed is an end to end framework to obtain the required number of nodes and their location based on an error threshold in a deployed IoT network. The framework’s performance has been compared with the brute force approach, which entirely relies on comparing all the possible combinations. Finally the trade-off between the sensor nodes’ spatial density and the error in the spatial reconstruction for an optimal spatial understanding of PM values has been presented.

Abstract

Modern Computers were first conceptualised by Charles Babbage in the 19th century. This first concept envisioned a machine in which a program (set of instructions to be performed by computer) were provided using punched cards. Over the past century, the idea of a programmable computer became a reality. As computers became more sophisticated and powerful, it became hard to program computers using punched cards. To solve this problem, programming languages were conceptualized and implemented. In last 50 years, computer programming has evolved from being a method of instructing computers into a necessary skill. Nowadays, It is even taught in primary schools. Programming Word Problems (PWP) are used to teach Introductory Programming in schools and colleges. A PWP consists of a problem in natural language giving a background story and input/output format. The solver is expected to come up with a computer program which processes the input into expected output. As PWPs are much harder to solve, there has not been much work in automatically solving them. As a preliminary step towards solving these problems, we introduce the problem of Programming Word Problem Classification. The problem is about predicting the algorithm class to which a PWP belongs. We create two datasets of a total of 4000 problems and pose this as a single and multi label classification task. We provide a deep learning based approach which gives an accuracy of 62.7 percent. Along with the task of classifying Programming Word Problems, we introduce the problem of generation of Programming Word Problems. This problem is about automatically generating a Programming Word Problem. We propose a graph based representation for a PWP. Using the graph based representation and template based methods, we propose a method for generating programming word problems. We generate a set of Programming Word Problems and carry out human evaluation to evaluate correctness and relevance of the generated problems. The evaluations show that the generated problems are sufficiently realistic

Abstract

Text summarization is a natural language processing problem which has been investigated by the NLP community for half a century. In the era of information explosion, the community has intensified research for more sophisticated methods for automated text summarization. Attempts were made in the past to frame extractive and abstractive techniques for multidocument summarization. Extractive techniques select a subset of sentences which can approximate the summary of the input corpus of documents, while abstractive summarization techniques construct a semantic representation and are expected to generate the summary in its own learnt writing style. Extractive techniques create an intermediate representation for the target text, capturing the key textual features. Possible approaches for intermediate representation are Topic Signatures, Word frequency count, Latent Space Approaches using Matrix Factorizations, or Bayesian approaches. These intermediate representations are then used to assign scores for individual linguistic units within the text and select a subset of linguistic units which maximizes the total score as the summary of the target text. The mathematical scoring function for the summary is generally composed of components to quantify topical coverage and topical diversity. They report the accuracy in terms of a measure called the ROUGE score. Relatively less work is available on abstractive multi-document summarization in the past. Most of them utilise sub- syntactical structures which are directly extracted from input documents to generate summary sentences. Sub syntactical structures such as phrases are reorganized to create summary sentences using a method which can ensure relevant topical coverage, topical diversity and gramaticality. They also incorporate means to ensure factual accuracy so that sentences generated by the abstract summarization system are factually correct with respect to original corpus. Despite all the attempts to improve summarization in easily quantifiable dimensions such as topical coverage and diversity, a summary needs to be improved in other qualitative dimensions such as comprehensibility and coherence to match with a well-crafted human summary. Coherence represents the presence of inter-sentence structural relationships and topical continuity. Comprehensibility denotes how much a sentence is comprehensible without its context in the source document during an extractive summarization process.

Abstract

Empathy, a complex social skill, allows for the ability to understand the emotional and cognitive states of another. In general, empathy is crucial in the social world and for survival. Several studies have demonstrated that the default mode network (DMN) is involved in the process of internal mental simulations (also known as mind wandering) - an aspect significant for empathetic response. Researchers have found an overlap in brain regions between the social networks and the DMN. Since the DMN is activated during the mind wandering process, most of empathy literature has examined the DMN during resting state. Therefore in this thesis, we investigate the functional connectivity differences in resting state DMN and empathy-task DMN. In this study, we apply a novel time-frequency filter method on the BOLD signal to investigate the FC of the DMN. The aim of this thesis is to demonstrate the role of the DMN in empathetic processes and to further identify the time-frequency characteristics of the DMN activations during free-viewing emotional movie clips. Specifically, we use movie clips because research has shown more intense emotions being evoked in participants during dynamic stimuli vs static stimuli. And since we want to capture the complex psychological process of empathy, we decided to use emotional movie clips to portray the naturalistic complexity of human interactions. It must be noted that the time-frequency technique used in this thesis (the single frequency filter bank) provides a better resolution compared to traditional approaches such as sliding window. Using this novel technique, analysis on two sets of fMRI data were conducted to examine the time-frequency dynamics. To the best of our knowledge, this is the first study to explore the time-frequency characteristics of the DMN in empathy tasks. In the first experiment, fMRI response signals from the three short diverse movie clips (Disney, Green, and Taare) were analyzed. Before the stimuli was presented, resting state data of 3 minutes was also recorded for the 8 participants. Specific scans which consisted of the most emotional scenes were chosen to conduct the comparative analysis. The results from this preliminary investigation demonstrated differences in the activations between empathetic task vs resting state. This preliminary study corroborates findings from previous studies. For example, we found highly skewed power distributions where most power was at the lowest frequencies. This has been shown in previous research as well

Abstract

Machine Translation is a sub-field of Computational Linguistics that deals with systems that automatically translate text or an utterance from one language into another. The field has made huge strides, from rule-based translators to the now state-of-the-art neural machine translators. However, translators in the general domain are far from achieving human parity. At this stage, even for state-of-the-art translators, a human needs to check the output and post-edit it. The aim therefore, is to continuously improve the machine translator so that the post-editing effort reduces. Guided by this aim and a will to make translators more complete, I identify one area where even state-of-the-art machine translators perform poorly – translating idiomatic and non-compositional constructions. I establish that these constructions are infrequent in the data translators are trained and tested on, which could be the primary reason for the inadequacy of their translations. To improve the translation adequacy of non-compositional constructions, I propose a rule-based pre-processor that detects these constructions in the input sentence and simplifies them into more compositional constructions – which are far more likely to translate adequately. I start by compiling a list of constructions, which range from fully lexical and rigid constructions to constructions with slots constrained by parts of speech, all the way to fully syntactic constructions. Using examples of sentences that have these constructions, I evaluate five English–Hindi NMT systems and report that their performance is thoroughly inadequate when translating non-compositional constructions. To understand the capabilities that a pre-processor would need to solve this issue, I conduct an analysis of these constructions, and come up with features that a rule-based pre-processor needs to detect and simplify the constructions. This theoretical analysis of rules is followed by a description of the actual pre-processor I created as part of this project and its rule formalism. The pre-processor is then systematically evaluated for English – Hindi translation. I report a high accuracy of construction detection in English based on manually written rules, as well as a significant improvement in the quality of translation in Hindi after the non-compositional constructions in the English input text are preprocessed into more compositional constructions. I conclude by discussing the results of this evaluation and the errors made by the pre-processor, some limitations of this solution, as well as possible future work to extend this system and improve it. The pre-processor is open-source and its code is available at https://github.com/khannatanmai/rule-based-preprocessing-mt.

Abstract

Gold Nanoparticles (AuNPs) are significantly important in the field of biomedical applications and are being used to diagnose and treat various important diseases such as cancer. The properties of AuNPs strongly depend on the size, structure, and morphology. Experimental conditions or mechanism which lead to specific morphology have not been clearly understood; therefore, it is of utmost importance to understand the influence of experimental parameters, geometrical properties on the growth of AuNPs and mechanism which lead to different morphology of AuNP. Modeling the atomistic behavior of nanoparticles with the timescale that approach actual experiments and represents the true atomistic behavior is a challenging task in the field of computational chemistry. In the literature survey, methods like Molecular Dynamics (MD), phase-field method, level-set method, adaptive mesh techniques, random walks with adaptive step sizes have been used to model the atomistic behavior of nanoparticle. This thesis uses the Kinetic Monte Carlo (KMC) scheme along with greedy nearest neighbor approaches to make the computation less expensive for modeling the true atomistic behavior of AuNP in the solution of gold ions with the timescale that approaches the actual experiments. Three processes namely adsorption, desorption, and surface diffusion have been considered. This model is further used to study the effects of different experimental parameters that influence shape and size and also to find out geometrical trends of different initial seed shape over time. AuNP of different morphology like the truncated octahedron, cuboctahedron, truncated cube, cube, rhombic dodecahedron, and the sphere was synthesized by the model at the certain specific experimental condition. This study will help scientists, nanotechnologists, and experimentalists to understand the mechanism and conditions to synthesize specific morphology

Abstract

Language identification (LID) refers to the task of figuring out the language in a given speech utterance. The task of Language Identification is very important in development of spoken dialogue system especially for multilingual society like India. In this work, an implicit approach has been used for the task of language identification. Combination of MFCC feature vector and RCC feature vector has been explored for Indian Language identification (LID) task. MFCC represents the vocal tract information and RCC represent the excitation source information which are complementary to each other. To combine these two complementary features different fusion based approaches has been used. Decision level fusion based approach and feature level fusion based approach has been explored for this task. Deep neural network (DNN) framework has been used as a classifier. DNN models are very popular for the task of speaker identification and other speech signal processing related task. In decision level fusion different fusion techniques such as Min, Max, Average, and Min-Max has been used. In feature level fusion approach canonical correlation analysis(CCA) has been performed to combine MFCC feature vector and RCC feature vector. In this algorithm only one DNN classifier is trained which has improved computation time and accuracy. Several experiments has been performed on 13 Indian languages data set. This data set consists of 120 hours of training data and 30 hours of testing data. Here, EER is equal error rate which is used as the performance metric. Lower the value of EER, higher the accuracy of LID performance. Results are compared with state of art I-vector based approach. Decision level fusion based approach gives an equal error rate of 9.64% as compared to an equal error rate of 10.18% of I-vector based approach. CCA based feature level fusion gives an equal error rate of 9.19% as compared to average EER of 9.64% of decision level fusion approach. From the results it is proved that Fusion based approaches performed better as compared to the individual feature vector based approaches.

Abstract

Presburger arithmetic provides the mathematical core for the polyhedral compilation techniques that drive analytical cache models, loop optimization for ML and HPC, formal verification, and even hardware design. Polyhedral compilation is widely regarded as being slow due to the potentially high computational cost of the underlying Presburger libraries. Researchers typically use these libraries as powerful black-box tools, but a lack of internal documentation and decade-old C implementations hold back broader performanceoptimization efforts. With FPL, we introduce a new library for Presburger arithmetic built from the ground up in modern C++. We carefully document its internal algorithmic foundations, use lightweight C++ data structures to minimize memory management costs, and deploy transprecision computing across the entire library to effectively exploit machine integers and vector instructions. Major parts of our library have already been upstreamed into the LLVM/MLIR open source project, and this functionality is being used by MLIR to perform loop fusion. On a newly-developed comprehensive benchmark suite for Presburger arithmetic, we show a 5.25x speedup in total runtime over the state-of-the-art library isl in its default configuration and 3.14x when over a variant of isl optimized with elementwise transprecision computing. We expect that the availability of a well-documented and fast Presburger library will accelerate the adoption of polyhedral compilation techniques in production compilers.

Abstract

Multi-robot systems have many applications where a group of robots carry out a certain task more efficiently than a single robot. One of the most practical implementations of such a system is to transport large payloads using multiple small robots. Such a payload transportation system can be used in large warehouses, rescue operations during natural disasters and patient transportation in hospitals. Food and package delivery systems are also possible to design by extending these concepts to multiple drones. In the case of rigid payloads, the robots must group in a static formation as per the shape of the payload so that it can be transported. However, when it comes to deformable payloads, the process becomes complicated due to the flexible nature of the payload. In addition to that for efficient transportation of the deformable payload the robots must be able to reshape the formation to squeeze through the narrow gaps among the obstacles. In this thesis, we present a methodology for transportation of deformable payloads using a formation of non-holonomic mobile robots, while avoiding static and dynamic obstacles. This work is an endto-end solution which includes creating initial formation of the robots, path planning to avoid static obstacles, dynamic obstacle avoidance, control signal generation for individual robots and building a local positioning system for localization of individual robots as well as the formation. We assume the center of the formation to be a virtual robot which also plays the role of the leader of the formation. Rapidly exploring Random Tree star (RRT*) algorithm is used to determine static obstacle free trajectory for the virtual leader while a custom path planning algorithm is incorporated for the follower robots. Individual trajectories are planned for each of the robots. A decentralized leaderfollower formation control is applied for the robots to traverse on their respective trajectories without breaking the formation while following the constraints of the deformable payload. The virtual leader moves forward or backward on the initially generated path with variable velocity depending on the proximity of dynamic obstacles. All the other robots follow it so that the formation can avoid dynamic obstacles while remaining on the path leading towards the destination. In order to carry out the process smoothly we created a local position system using Ultra Wide Band (UWB) modules which can localize each of the robots in the formation in real time.

Abstract

Focus, defocus and depth-of-field are integral aspects of a photograph captured using a wide-aperture camera. Focus and defocus blur provide critical cues for estimation of scene depth and structure which helps in scene understanding or post-capture image manipulation. Focus and defocus blur are also used creatively by photographers to produce remarkable compositional effects such as emphasis on the foreground subject with aesthetic bokeh in the background. Epsilon Focus Photography is a branch of computational photography that deals with the capture and processing of multi-focus imagery - where multiple wide-aperture images are captured with a small change in focus position. In this thesis, we provide a comprehensive study of various problems in epsilon focus photography along with a detailed analysis of the related work in the area. We provide useful constructs for the understanding and manip- ulation of focus, defocus blur and the depth-of-field of an image. The work in this thesis can be divided into four broad categories of measurement, representation, manipulation and applications of focus. Measuring focus is a long studied and challenging problem in computer vision. We study various methods to measure focus and propose a composite measure of focus that combines the strengths of well-known focus measures. We the study the task of post-capture focus manipulation at each pixel in an image and formulate a novel representation of focus that can find much use in image editing toolkits. Our representation can faithfully encode the fine characteristics of a wide-aperture image even at complex interaction locations such as depth-edges and over-saturated background regions, while optimizing the memory footprint of multi-focus imagery. Apart from precise geometric constructs for scene refocusing, we also propose an data-driven approach for post-capture scene refocusing using deep adversarial learning. We show how the tasks of deblurring an image, magnification of the defocused content and overall comprehensive focus manipulation can be efficiently modeled using conditional adversarial networks. We study several applications of focus in computer vision such as view interpolation and depth-from-focus. We provide a tool that can interpolate different views of a scene based on focus texture segmentation and propose a novel solution for depth-from-focus using the proposed composite focus measure. In summary, this thesis consists of a comprehensive study of epsilon focus photography and its applications in the context of computer vision and computational photography.