Abstract

Underscoring the importance of storage and cache memory is a steady climb in the present generation, which is highly attributable to the presence of large number of video streaming devices, big data and the profusion of IoT devices. The placement of data across the system in a structured fashion aids in bringing down the number of transmissions within the system. Coded transmissions during the demand phase enables us to use the locally stored cache data most effectively. Coded Caching and Coded Data Rebalancing are two recent techniques to reduce the communication load in scenarios which require communication intended to multiple receivers, each of which store a fraction of the total data available in the system. Building on these two ideas, we focus on two main topics in this thesis. Our first contribution is a coded caching scheme for an interference channel which achieves subexponential subpacketization. Our second contribution consists of coded data rebalancing schemes for node addition and node removal scenarios in a decentralized distributed database. Although coded caching is an effective technique in obtaining large gains in cache-aided broadcast communication networks, its practical implementation is severely hampered by its exponential subpacketization levels. It is crucial in lowering this subpacketization level for various scenarios where coded caching is applied. We specifically choose the scenario of a cache aided interference channel with KT transmitters, KR receivers and N files stored in the system library. Each transmitter and receiver can cache upto MT and MR files from the library respectively. Initial coded caching scheme for this scenario had an exponential subpacketization with respect to the number of receivers KR for large KR and achieved a sum-DoF of L + KRMR N where L , KT MTN . Recent work on this scenario improvised on the required subpacketization to approximately its L th root and thereby boosted the achievable sum-DoF by a multiplicative factor of L. In the first contribution of this thesis, we present a projective geometry based coded caching scheme that achieves a subpacketization of F = 1 m! q m(m−1) 2 mQ−1 i=0 " k − i 1 # q , and a sum-DoF of L(m + 1) where k, m ∈ Z + with m ≤ k and q is some prime power. As the number of receivers grows large, this subpacketization is subexponential with respect to the number of receivers provided the receiver cache fraction MRN is upper bounded by a constant. We further present a comparison of this scheme with the recent work on this scenario that achieved a low subpacketization. Secondly, we focus on handling the problem of non-uniform storage across storage nodes (also known as data skew) in replication-based distributed databases. The performance of such replicationbased distributed databases is affected by data skew and reduction in the replication factor during operation, particularly due to node additions or removals. Data rebalancing refers to the communication involved between the nodes in correcting this data skew, while maintaining the replication factor. For carefully designed distributed databases, transmitting coded symbols during the rebalancing phase has been recently shown to reduce the communication load of rebalancing. In this thesis, we look at balanced distributed databases with random placement, in which each data segment is stored in a random subset of r nodes in the system, where r refers to the replication factor of the distributed database. We call these as decentralized databases. For a natural class of such decentralized databases, we propose rebalancing schemes for correcting data skew and the reduction in the replication factor arising due to a single node addition or removal. We give converse arguments which show that our proposed rebalancing schemes are optimal asymptotically in the size of the file.

Abstract

In this thesis, we propose a distributed, cooperative path planning technique for multiple drones (∼200) to explore an unknown region (∼10,000 connected units) in the presence of obstacles. The map of an unknown region is dynamically created based on the information obtained from sensors and other drones. The unknown region is considered as connected region split up into hexagonal unit regions. We use two types of communication, one long-range, and another more frequently used short-range communication. The short-range communication within drones in smaller proximity helps to avoid obstacles and re-exploration of cells already explored by companion drones located in the same sub-area as proven by the simulation results. The long range communication helps in deciding the next optimal sub-area to be targeted by individual drones based on weighted RNN (Reverse nearest neighbour). We have two types of communication in a weighted hexagonal representation of sub-areas which makes exploration more efficient and scalable. However, given the fact that drones are prone to failures due to a variety of causes, it is important that the strategies developed for these systems be failure resilient. Hence, failure resilience in multi-agent robot systems for area exploration and mapping is a critical aspect. Thus, in the thesis, we will introduce the failures in the simulation scenario and study the impact of failures on the present state of the art algorithms. Moreover, we will also study the present benchmarking metrics and show how the present metrics fail to incorporate the failures that exist in real-world scenarios

Abstract

Society has been evolving rapidly with the digital revolution. With the increase of Internet adoption in the last decade, multilingualism has proliferated as the Internet has provided unrestricted access to resources. In a multilingual society, people often mix multiple languages in an informal setting leading to Code-Mixed (CM) text. The CM text generated has been increasing with time. The analysis of this data may help us to derive potentially valuable conclusions. Since data is seen as the new oil, many public and private institutions have been moving towards digital governance, focusing on data-driven decision-making. This phenomenon is reflected in the enormous increase in the number of new and existing companies established to extract various valuable sources of information. But, analysis of low-resourced CM languages is still a long shot. While there have been significant advancements in Natural Language Processing with Machine Learning, processing low-resourced CM text presents new challenges because of its noisy nature and lack of reliable data. Thus, CM requires better data sets and robust pre-processing pipelines. This work aims to analyze a new approach towards building data sets and proposes a pre-processing pipeline for low-resourced CM text. We have chosen Telugu, a low-resourced Dravidian language spoken in the Southern part of India, as the primary matrix language and English as the secondary embedded language for this study. In this thesis, we first present the largest CM dataset for Code-Mixed Telugu-English Text (CMTET), annotated with a new, highly efficient chatbot-based annotation tool. We then propose a pre-processing pipeline to help model CM data using existing NLP models. The pre-processing pipeline starts with Language IDentification (LID) on raw text. It then presents a novel data normalization technique to normalize the spelling and transliteration errors. To analyze the performance of the proposed pipeline, we carried out Sentiment Analysis on the CM dataset with a reported 2.53% increase in accuracy with the pipeline included.

Abstract

With the growing data in terms of images and videos, it becomes imperative to derive a solution to filter out important/salient information in these data. Learning computational models for visual attention (saliency estimation) is an effort to inch machines/robots closer to human visual cognitive abilities. Developing such a solution can help reduce human effort and can be used in various applications like automatic cropping, segmentation etc. We approached this problem by investigating saliency estimation in images which is predicting the stimuli of the human visual system when exposed to an image. We start by identifying four key components of saliency models, i.e. , input features, multi-level integration, readout architecture, and loss functions. Data-driven efforts have dominated the landscape since the introduction of deep neural network architectures. In deep learning research, the choices in architecture design are often empirical and frequently lead to more complex models than necessary. The complexity, in turn, hinders the application requirements. We review other state-of-the-art models on these four components and propose two novel and simpler end-to-end architectures - SimpleNet and MDNSal. They are straightforward, neater, minimal, and more interpretable than other architectures achieving state-of-the-art performance on public saliency benchmarks. SimpleNet is an optimized encoder-decoder architecture. MDNSal is a parametric model that directly predicts parameters of a GMM distribution and aims to bring more interpretability to the prediction maps. Conclusively, we suggest that the way to move forward is not necessarily to design complex architectures but a modular analysis to optimize each component and possibly explore novel (and simpler) alternatives. After exploring these components, we shifted our focus to saliency estimation in videos where the stimuli of users are captured when exposed to a dynamic scenario. We propose ViNet architecture for the task of video saliency prediction. ViNet is a fully convolutional encoder-decoder architecture. The encoder uses visual features from a network trained for action recognition, and the decoder infers a saliency map via trilinear interpolation and 3D convolutions, combining features from multiple hierarchies. The overall architecture of ViNet is conceptually simple; it is causal and runs in real-time. ViNet does not use audio as input and still outperforms the state-of-the-art audio-visual saliency prediction models on nine different datasets (three visual-only and six audio-visual datasets). We also explore a variation of ViNet architecture by augmenting audio features into the decoder. To our surprise, upon sufficient training, the network becomes agnostic to the input audio and provides the same output irrespective of the input. Interestingly, we also observe similar behavior in the previous state-of-the-art models for audio-visual saliency prediction. Our findings contrast with earlier works on deep learningbased audio-visual saliency prediction, suggesting a clear avenue for future explorations incorporating audio more effectively

Abstract

Nowadays, we use speech-enabled smart devices either to improve human-machine or humanhuman interaction. One of the primary tasks in these speech-enabled devices is speech enhancement. Speech enhancement is the extraction of the desired speech signal from the noisy and reverberant mixture signals recorded by the microphones. The performance of the speech-enabled devices relies significantly on the performance of the speech enhancement methods. Among these enhancement methods, beamformers and Time-Frequency (TF) mask-based methods are widely used. Beamformers are linear spatial filters that aim to boost the signal coming from a specific direction by appropriate configuration of the microphone array, and in doing so attenuates interfering signals from other directions. A source TF mask identifies the TF regions where the source is dominant and can be applied on the mixture TF representation to extract the desired source. Several beamformers and a few TF mask estimators estimate the azimuth and elevation angles called the Direction of Arrival (DoA) of the sources from the microphone data. Several other speech enhancement methods estimate the source TF masks. In all these methods, it is necessary that the DoA and the masks be accurately estimated for high quality of the enhanced signals. The thesis addresses the following problems: the problem of robust DoA and TF-mask estimation from the noisy and reverberant microphone signals and the problem of enhancement of a TF mask. Specifically, this thesis proposes two robust DoA estimators and a novel TF mask interpolation technique to improve the TF masks. Further, the efficacy of eigenvalue features for robust TF mask estimation in a resource constrained, neural network-based speech enhancement task is investigated. The first DoA estimator is a Non-negative Matrix Factorization weighted Steered Response Power beamformer abbreviated as the SRP-NMF. The broadband SRP beamformers cannot perform multi-speaker DoA estimation in a single time frame, a drawback which is overcome in the SRP-NMF by NMF weighting. The weights are obtained by NMF of the mixture spectrogram and correspond to the NMF atoms of the underlying sources. On evaluations conducted on data from public challenges and data generated from recorded room impulse responses and with various microphone array configurations, the SRP-NMF method outperforms the widely used variants of narrowband and broadband DoA estimators in terms of source detection capa-bility and DoA estimation accuracy. The second DoA estimator, SFF-PHAT-env, estimates the directional information of the sources by, PHAse Transform (PHAT) weighted cross-correlation of the amplitude envelopes at several frequencies (obtained by passing the microphone signals through a narrowband filter called Single Frequency Filtering (SFF)) across the channels. The high signal-to-noise ratio regions in the envelopes, PHAT weighting, and multiple evidences at several frequencies, result in robust DoA estimates. The performance of SFF-PHAT-env is compared with the other existing SFF-based methods and the state-of-the-art Generalized Cross Correlation (GCC)-based methods. The tests are conducted on publicly available data collected in real rooms in challenging conditions From the experiments, it is observed that the best performing SFF-based methods are better or comparable to the best GCC-based estimator in detection metrics such as F-measure and accuracy metrics based on azimuth error. Irrespective of whether the TF mask is obtained as an ideal binary mask (IBM) or by any practical method, there are often regions of the target speech that are suppressed, leading to audible artefacts. The influence of these errors could be reduced by estimating such missing data points by some form of interpolation using NMF. The existing NMF-based methods of interpolation are computationally intensive and do not offer a means to control the degree of interpolation, resulting in over-estimation of the missing regions and leading to noise-vocoded output. In the proposed NMF-based interpolation method, we address the drawbacks of the existing methods by considering the improvement achievable by applying the proposed method to ideal binary mask-based gain functions. The instrumental quality metrics (PESQ and SNR)) indicate the added benefit of the missing data interpolation compared to the output of the ideal binary mask. In resource constraint devices, the learning model cannot be complex. Hence the demand to perform a task is on the input features. The more discriminative the features, the better is the performance. Eigenvalues are spectral features that can discriminate coherent sound sources from the spatially uncorrelated ones. However, the eigenvalues have not been used for neural-network-based enhancement. In this thesis, for extracting speech from noise, we explore the efficacy of the instantaneous generalized eigenvalue f

Abstract

Data mining is a process of extracting interesting information from the large volumes of data. Data mining algorithms are being widely used in several applications like customer relationship management, inventory management, recommendation systems, fraud detection, and surveillance. Pattern mining is an important task of data mining, which involves discovering interesting associations from large trans- actional databases such as market basket data, e-commerce transactions, social network transactions, etc. In the literature, efforts are being made to investigate different kinds of pattern mining models such as frequent patterns, periodic patterns, utility patterns, coverage patterns, and correlated patterns. Also, research efforts are being made to propose MapReduce based approaches to improve the scalability of pattern mining approaches. In this thesis, we investigate improved approaches to extract partial periodic patterns (3Ps) from a given spatio-temporal database. In the literature, the model of periodic patterns has been proposed to extract the interesting associations, which appear periodically in a large temporal database. Moreover, a model of 3Ps has also been proposed to extract the knowledge of interesting associations, which appear periodically in a partial manner in a large temporal database. However, the issue of extracting 3Ps from spatio-temporal databases has not addressed. In this thesis, we have proposed an improved model and algorithms to extract 3Ps from spatio-temporal databases. Moreover, we have also proposed MapReduce framework to extract 3Ps from large spatio-temporal database. A 3P in the given temporal database is defined based on the user-given minimum periodic-support and maximum inter-arrival time constraints. For extracting 3Ps from a given temporal database, Pattern- growth and ECLAT (Equivalence Class Clustering and bottom-up Lattice Traversal) based approaches have been proposed in the literature. It has been observed that the existing model of extracting 3Ps (and the algorithms) face performance issues for extracting 3Ps in a spatio-temporal database scenario. Based on the observation that the itemsets or patterns having large spatial distance between the items may not be interesting, we have identified the notion of maximum distance as the additional pruning criteria and proposed the improved model of 3Ps. Overall, the proposed model employs minimum periodic-support, maximum inter-arrival time, and maximum distance as three constraints to determine the interestingness of a pattern in a spatio-temporal database. The minimum periodic-support is equal to the minimum number of periodic occurrences of a pattern within the data. The maximum inter-arrival time is equal to the maximum duration in which a pattern must reappear to consider its occurrence as periodic within the data. The maximum distance is equal to the maximum distance between the items in a pattern. All patterns satisfying these three constraints are returned as interesting patterns. Based on the new model, we have proposed both ECLAT and pattern growth based algorithms to extract 3Ps from the given spatio-temporal databases. The efficiency of our approaches is shown by conducting experiments on large synthetic and real-world spatio-temporal databases. We also demonstrate the usefulness of the extracted patterns through a case study by applying on air pollution and congestion datasets. To improve scalability, we have also proposed a parallel MapReduce based pattern growth approach to discover 3Ps in a spatio-temporal database. The issue is to maintain the load balancing among the ma- chines and mine 3Ps in parallel by employing a large number of machines. To address the issue, we have proposed a parallel algorithm by incorporating the step of distributing transactional identifiers among the machines and mining the identical itemsets independently over the different machines. We have proposed an improved load allocation algorithm such that the machines receive the balanced load, ap- proximately. Experimental results conducted on Apache Spark’s distributed environment show that the proposed parallel approach improves performance significantly with increase in number of machines.

Abstract

The current generation of quantum computers is widely referred to as noisy intermediate-scale quantum (NISQ) computers. These devices are predecessors of fault-tolerant quantum computers, which are speculated to perform calculations that will be intractable for even the most powerful classical supercomputers. However, unlike fault-tolerant hardware, the computational capabilities of the near-term hardware are primarily affected by their limited qubit count, restrictive hardware topology, and lack of error correction. A natural question arises whether there are any practical applications for these NISQ devices in performing calculations of independent interest. This dissertation focuses on employing NISQ hardware for solving computational problems more efficiently. We begin by posing this problem into a series of key research questions that are built on understanding the noises present in these devices and designing software to tailor algorithms to be more noise resilient. Our major contributions are then based on answering each of these questions individually. In the beginning, we give a didactic introduction to quantum computation and NISQ architecture along with the self-contained theory for hybrid quantum-classical algorithms. We also provide a comprehensive review of the potential areas for applications of these hybrid algorithms and the field of quantum error mitigation. We then present Aakash, a software simulator based on IBM Qiskit, that models a noisy quantum processor based on density matrix formalism. This simulator is currently being used as a backend for the QSim: Quantum Computer Simulator Toolkit, one of India’s first initiatives under the Quantum-Enabled Science & Technology (QuEST) program to address the common challenge of advancing the quantum computing research frontiers in India. Furthermore, we showcase formulations for applications related to combinatorial optimization and quantum chemistry that can be used to solve problems using variational quantum algorithms such as quantum approximate optimization algorithm (QAOA) and variational quantum eigensolver (VQE), respectively. We also perform noise analysis for these algorithms, characterizing how different types of noise-based errors affect their performance. Our simulation of QAOA provides insightful data about the effect of errors due to amplitude decay, decoherence, thermalization, and logic gate imprecision, which will help in designing specific quantum hardware for variational quantum algorithms that will allow us to approximately solve NP problems more efficiently. We further use a VQE-based method to calculate molecular energy derivatives on a quantum computer for both ground state energy and excited state energies up to the second order. Other than minimum energy configuration search for H2 molecule, estimation of molecular response properties such as dipolemoment and polarizability, we also pursue transition state search for the reaction H2+H↔H+H2. Our variational method gives results in complete agreement with those obtained using full configuration interaction (FCI) values. We also present qLEET, an open-source library for exploring loss landscape, expressibility, entangling capability, and training trajectories of noisy parameterized quantum circuits. It supports quantum circuits and noise models built using popular quantum computing libraries such as Qiskit, Cirq and Pyquil while providing opportunities to design new hybrid algorithms by utilizing intuitive insights from the ansatz capability and structure of the loss landscape. Finally, we show how NISQ hardware can be designed and utilized in a more circuit-centric fashion by studying the dependence of the circuit size, circuit depth on the interaction and connection between different qubits present in quantum hardware. Throughout our work, we have not performed any quantum computations beyond the reach of the current capabilities of classical computers. Still, we do address many implementation challenges that must be overcome in such an endeavor, including circuit optimization, efficient compilation, and error mitigation. We conclude by providing an optimistic outlook towards the incremental utilization of quantum computers and explicitly stating how our work could help with it

Abstract

Extracting knowledge from large amounts of data has been an important research field for the past three decades. Data mining is one such area that deals with the investigation of frameworks and algorithms to extract different kinds of knowledge from large databases. Pattern mining is one of the data mining tasks, which deals with developing frameworks and algorithms for extracting interesting patterns (or itemsets) from large databases. In the literature, several pattern mining techniques have been employed to mine different kinds of patterns such as frequent patterns, coverage patterns, periodic patterns, weighted patterns, utility patterns, etc. In this thesis, we investigate improved approaches for mining weighted and high utility itemsets. As a first contribution, we have proposed an improved approach to mine Weighted Frequent Itemsets (WFIs) from spatio-temporal databases. The WFI framework allows the users to set weights to the items present in the database based on their importance and discovers all itemsets whose weighted sum in a transactional database is no less than the user-specified minimum weighted sum (minW S) value. The existing works in the literature have focused on finding WFIs in a transactional database and did not consider the spatial characteristics of the items within the data. The spatial characteristics of an item imply the geographical location of an item. We have proposed an improved WFI Mining (WFIM) approach for spatio-temporal databases by introducing the notion of neighborhood itemset, which is defined by considering the spatial characteristics of the items. An itemset is called a neighborhood itemset if the distance between each pair of items is no more than the user-specified maximum distance (maxDist) value. By adding the notion of neighborhood itemset to WFIM, we have proposed a new model, which we call Weighted Frequent Neighborhood Itemset Mining (WFNIM), to mine Weighted Frequent Neighborhood Itemsets (WFNIs) from spatiotemporal data. The generated WFNIs do not satisfy the anti-monotonic property. To extract WFNIs efficiently, we have proposed new pruning measures by exploiting the spatial nature of items to effectively reduce the search space and the computational cost of finding the desired patterns. A new pattern-growth algorithm has been presented to find all WFNIs from a given spatio-temporal database. Experimental results demonstrate that the proposed algorithm is efficient. A case study on JAPAN air pollution data is presented to demonstrate the usefulness of this model. As a second contribution, we have proposed an improved High Utility Itemset Mining (HUIM) approach. HUIM uses utility measure to mine High Utility Itemsets (HUIs) from the transactional database. In HUIM, each item is associated with internal utility (frequency of an item within the transaction) and external utility (cost of the item). The utility of an item is defined as the product of external and internal utilities. An itemset is called a high utility itemset if its utility is no less than the userspecified minimum utility (minU til) value. It can be noted that HUIM suffers from low utility item problem. To overcome this problem, we introduce a new null-invariant measure, called utility ratio, to evaluate the interestingness of an itemset in the database. We have extended HUIM to propose a new model of Relative High Utility Itemset Mining (RHUIM) to mine Relative High Utility Itemsets (RHUIs) in transactional data. An itemset is called RHUI if its utility is no less than the minU til value and its utility ratio is no less than the user-specified minimum utility ratio (minUR) value. We have proposed two new pruning measures based on utility ratio to reduce the search space. We also present a fast algorithm to find all desired itemsets in a transactional database. Experimental results demonstrate that the proposed algorithm is efficient. A case study on the real-world Yahoo! JAPAN retail data is presented to demonstrate the usefulness of this model. Overall, we have proposed improved approaches to discover weighted frequent neighborhood itemsets from spatio-temporal databases and relative high utility itemsets from transactional databases. We have demonstrated efficiency by conducting extensive experiments on real-world and synthetic databases. We have also demonstrated the application of the proposed approaches by applying the proposed approaches in real-world scenarios.

Abstract

In this thesis, we address the age old problem of dealing with scenarios in which the significance of making a mistake while taking a classification decision is very high. We also look deeper into how we can take advantage of deep learning techniques to establish state of the art results and study the representations learnt by the deep reject option classifiers. While supervised techniques have their advantage we explored unsupervised learning in real time scenario of catching malicious traders in Stock Exchanges which are establishments where significance of mistakes are very high. Firstly, we propose deep architectures for learning binary instance specific abstain (reject option) classifiers. To show the effectiveness of the proposed approach, we experiment with several real world datasets. We observe that the proposed approach not only performs comparable to the state-of-the-art approaches, it is also robust against label noise. We also provide visualizations to observe the important features learned by the network corresponding to the abstaining decision. Secondly, we look at Stock exchanges. Due to their prominence, stock exchanges are prone to a variety of attacks. Different types of proprietary fraudulent activity detectors are deployed by stock exchanges to analyze the time series data of trader’s activities or the activity of a particular stock to flag potentially malicious transactions while human analysts probe the flagged transactions further. The key issue faced here is that while the number of anomalous transactions identified can run into thousands or tens of thousands, the number of such transactions that can realistically be probed by human analysts would be a small fraction due to resource constraints. The issue therefore reduces to a dynamic resource allocation problem wherein alerts that represent the most malicious transactions need to be mapped to human analysts for further probing across different time intervals. Thirdly, we develop a multiclass deep learning solution with a rejection option. While binary so- lutions find relevance in scenarios such as cancer detection where ”yes” or ”no” could be the probable options. In scenarios such as autonomous driving, multiple options could be applicable at each instant. So, we propose a multiclass double ramp loss function. We study the properties of the loss function and establish state of the art results on real world datasets.

Abstract

Binocular vision (BV) is the result of the fusion of the input from each eye to form a coherent image. BV is essential for an individual to have a normal vision. Clinically BV anomalies (strabismus, amblyopia) are evaluated using different diagnostic tests and instruments. In recent studies, non-strabismus BV anomalies have also been reported and flagged to be included in conventional screening protocols. A traditional instrument is the Synoptophore which evaluates three grades of BV. This equipment is very efficient but has certain limitations a) ambient light in the testing room, b) bulky and hence difficult to transport to screening camps in remote areas, c) Cost of Synoptophore is another major disadvantage, making it out of reach of most eye care centers etc. The Aim of this study is to address these limitations with existing technology and provide a suitable solution for the same. Virtual Reality(VR) is one such rapidly evolving technology which provide a suitable platform to implement the principle of Synoptophore easily. Therefore, we propose VR-Phore, a VR application solely based on principle of the haploscope as in the Synoptophore. Which uses a head-mounted display device (Oculus Rift is used for this study) for diagnostics and also as possible therapeutic use. The proposed system addresses the limitations of the Synoptophore. Limitations such as requirement of suiatable light source in the room while using synoptophore, there is no such requirement for VR-Phore usage. VR-Phore is a simple VR application which can be easily set up at any places like screening camps in schools, clinics or in any remote areas etc. Operating Synoptophore requires a clinical professional with prior knowledge on the device whereas VR-Phore can be used by anyone and the stored data can be provided to doctors for diagnosis. VR-Phore also provide added advantages of a software platform to incorporate testing modules for a range of clinical conditions very easily and tele-diagnosis. A total of 41 participants are involved in this study for data collection. The data collected from this system was compared to Synoptophore. Measurements, high correlations and accuracy was observed validating the application of the proposed system in diagnostics. The added advantage is the portability of the software platform onto a smart phone attached to a low-cost VR head-mounted device, effectively making this system cost-friendly and affordable to everyone.