Abstract

Crowdsourcing effectively solves a large variety of tasks by employing a distributed human population. Information aggregation from multiple reports provided by potentially unreliable or malicious agents is a primary challenge in crowdsourcing systems. As a result, research in this area has focused on incentivising agents to exert efforts and report truthfully. In particular, Peer Based Mechanisms (PBMs) appropriately reward agents for reporting accurately and truthfully. However, we observe that with PBMs, crowdsourcing systems may not be fair. As PBMs evaluate agents’ reports based on their consistency with their peers, agents may not receive deserved rewards despite investing efforts and reporting truthfully. Unfair rewards for the agents may discourage participation. Motivated by this, we aim to build a general framework that assures fairness in PBMs. Towards this, we propose the idea of providing trustworthy agents with additional chances of pairing while evaluating their reports. Providing additional chances will help to reduce the penalty obtained by trustworthy agents from unfair pairings, improving their expected reward. To decide which agents to give additional chances we adopt a reputation model that quantifies agents’ trustworthiness in the system. Based on this approach, we build a general iterative framework, REFORM, which adopts the reward scheme of any existing PBM and uses a suitable reputation model. To quantify fairness in PBMs, we introduce two general notions of fairness for PBMs, namely γ-fairness and qualitative fairness. γ-fairness is based on the proximity of the expected rewards a PBM assures to a truthful agent with the optimal reward it can provide. Qualitative fairness prioritises agents who consistently report accurate over other agents. In this work, we also consider that the tasks in the setting are time-sensitive. The task’s requester expects agents to submit the task reports at the earliest. We refer to such a setting as temporal settings. In a temporal setting, the reputation model needs to consider both accuracy of reports and the time taken to report. However, no existing reputation models consider the time taken to report. Towards this, we introduce Temporal Reputation Model (TERM) to quantify an agent’s trustworthiness in a temporal setting. TERM assigns scores to the agents based on their reporting behaviour and the time taken to report. Later, we demonstrate REFORM’s significance by deploying the framework with RPTSC’s reward scheme and TERM. Specifically, we prove that REFORM considerably improves fairness; while incentivising truthful and early reports. Furthermore, we conduct synthetic simulations to validate our results.

Abstract

Decision-making is hard when presented with a large set of similar options that insignificantly tradeoff amongst a range of attributes. This phenomenon is encountered within the skyline set because no skyline point is strictly better than any other skyline point, and therefore, every skyline point can excel ever so slightly in some subspace of attributes. The objective of this work is to determine the set of all sets of skyline points that are hard to choose from and hence all points in a set compete for attention from the same type of consumer (such sets are called competitive skyline cliques) In this work, two skyline points are defined to be competitive if the differences between the two points across each attribute are bounded by specified thresholds. We introduce maximal competitive skyline cliques (MCSCs) – maximal sets of mutually competitive skyline points and provide algorithms that enumerate all MCSCs. While the problem of enumerating all MCSCs is structurally similar to the NP-Hard problem of enumerating all maximal cliques in a graph, because of properties exhibited by our competitiveness metric, we show that enumerating all MCSCs can be performed efficiently in polynomial time. Furthermore, in 2D space, we provide an optimal linear-time sweepline algorithm. We also provide a bounded approximation for MCSCs that are easier to enumerate. Our extensive experiments using both synthetic and real (UCars, FIFA22 and Pokemon) datasets demonstrate the ´ efficacy of MCSCs and the efficiency of our algorithms.

Abstract

For decades, process technology scaling has catered to ever increasing demands of high-speed integrated circuits. Many applications, such as image and multimedia data processing, artificial intelligence, machine learning etc., depend on these circuits to process huge swaths of data in real time. Be it in the data centers, the cloud networks or the mobile devices, the computing efficiency of the circuits has had to play catch-up with this ever-increasing demand. However, it has become abundantly clear in recent years that cranking the technology knob isn’t a feasible solution to future needs of high-speed computing. Across the spectrum, data processing applications are endowed with resilience to acceptable levels of errors in the underlying computations. These applications incorporate, what can only be called a “forgiving” nature, into their algorithms without compromising with the end-user experience. And this intrinsic robustness to errors can be leveraged even further by the design methodology of Approximate Computing. It has now become an independent field that explores methods to reduce computation costs by allowing minor degradation in intermediate computations. Several approximate arithmetic units have been extensively studied and implemented with significant impacts on the system costs in terms of power, area and speed. Image processing algorithms with intrinsic robustness to errors can be approximated for significant resource and energy savings while still meeting the end-user requirements. FPGA-based implementations can increase their suitability for real-time high-speed multimedia applications by leveraging Approximate Computing. With high volume of pixel level computations, algorithms such as the Harris Corner Detector (HCD) and Unsharp Making (USM), become targets for such approximation strategies. In this thesis, we propose hardware implementations of these algorithms that rely on approximating the intermediate multiplication operations using Dynamic Range Unbiased Multiplier (DRUM). With runtime configurable bit-width control of DRUM instances, their quality of outputs is shown to depend on the varying accuracy. We explore how the errors due to approximate operations propagate to the output. Further,the experimental results from implementations on Virtex-7 and Zynq-7000 FPGA devices are documented and an analytical approach based on quality metric comparisons with base implementation is presented.

Abstract

The task of Visual Grounding is at the intersection of computer vision and natural language processing tasks. The Visual Grounding (VG) task requires spatially localizing an entity in a visual scene based on its linguistic description. The capability to ground language in the visual domain is of significant importance for many real-world applications, especially for human-machine interaction. One such application is language-guided navigation, where the navigation of autonomous vehicles is modulated using a linguistic command. The VG task is intimately linked with the task of vision-language navigation (VLN), as both the tasks require reasoning about the linguistic command and the visual scene simultaneously. Existing approaches to VG can be divided into two categories based on the type of localization performed: (1) bounding-box/proposal-based localization and (2) pixel-level localization. This work focuses on pixel-level localization, where the segmentation mask corresponding to the entity/region referred to by the linguistic expression is predicted. The research in this thesis focuses on a novel modeling strategy for visual and linguistic modalities for the VG task, followed by the first-ever visual grounding based approach to the VLN task. We first present a novel architecture for the task of pixel-level localization, also known as Referring Image Segmentation (RIS). The architecture is based on the hypothesis that both intra-modal (wordword and pixel-pixel) and inter-modal (word-pixel) interactions are required to identify the referred entity successfully. Existing methods are limited because they either compute different forms of interactions sequentially (leading to error propagation) or ignore intra-modal interactions. We address this limitation by performing all three interactions synchronously in a single step. We validate our hypothesis empirically against existing methods and achieve State-Of-the-Art results on RIS benchmarks. Finally, we propose the novel task of Referring Navigable Regions (RNR), i.e., grounding regions of interest for navigation based on the linguistic command. RNR is different from RIS, which focuses on grounding an object referred to by the natural language expression instead of grounding a navigable region. We additionally introduce a new dataset, Talk2Car-RegSeg, which extends the existing Talk2car dataset with segmentation masks for the regions described by the linguistic commands. We present extensive ablations and show superior performance over baselines on multiple evaluation metrics. A downstream path planner generating trajectories based on RNR outputs confirms the efficacy of the proposed framework.

Abstract

Finding or tracking the location of an object with precision and accuracy is a crucial problem in defence applications, robotics and computer vision. Radars fall into the spectrum of high-end defence sensors or systems upon which the security and surveillance of the entire world depends. There has been a lot of focus on Multi Sensor Tracking (MST) in recent years, with radars as the sensors. The Indian Air Force (IAF) uses a MST system to detect flights pan India, developed and supported by Bharat Electronics Limited (BEL), a defence agency that we are working with. In this thesis, we describe the Machine Learning approaches, which are built on top of the existing system the Air force uses currently. We have used 3 Machine Learning approaches, the first on a smaller dataset and the second and third on a bigger dataset. Each subsequent approach does a better job of reducing the errors faced by the system. The final approach trained our models on about 11 million anonymized real Multi Sensor tracking data points provided by radars performing tracking activity across the Indian air space. This approach has shown an increase in tracking accuracy by 5.5% from 91.5% to 97%. The model and the corresponding code were transitioned to BEL, which have been tested in their simulation environment with a plan to take forward for ground testing. Our final approach comprises of 3 steps: (a) We train a Neural Network and a CatBoost model and ensemble them using a Logistic Regression model to predict one type of error, namely Splitting error, which can help to improve the accuracy of tracking. (b) We again train a Neural Network and a CatBoost model and ensemble them using a different Logistic Regression model to predict the second type of error, namely Merging error, which can further improve the tracking accuracy. (c) We use cosine similarity to find the nearest neighbour and correct the data points predicted to have Splitting/Merging errors by predicting the original global track of these data points.

Abstract

Deep learning models perform very well when it comes to inferencing on benchmark NLP tasks. Because they perform well on these tasks- tasks that, like the GLUE set, are designed to test the language understanding and reasoning skills of the model- we hypothesize that the models are, in fact, understanding and reasoning based on the evidence. In this dissertation, we test that hypothesis by designing a series of probes to test evidence-based reasoning in the context of the tabular NLI task. The particular models examined are BERT-based tabular NLI models representative of the state-of-the-art in tabular NLI. A problem faced in probe creation is the time and effort required to manually create probing datasets for multiple tasks. In this dissertation, we also detail the use of data augmentation techniques to create probing datasets. In total, we create datasets to probe for: (a) prioritization of evidence, (b) robustness to annotation artefacts, and (c) reliance on pre-trained world knowledge over presented evidence. We find that the class of models studied displays the following deviations from expected behaviour: it (a) ignores relevant parts of the evidence, (b) is over-sensitive to annotation artifacts, and (c) relies on the knowledge encoded in the pretrained language model rather than the evidence presented in its tabular inputs. Finally, through inoculation experiments, we show that fine-tuning the model on challenging data does not help it overcome the behavioural deficiencies.

Abstract

The ability to synthesize novel and diverse human motion at scale is indispensable not only to the umbrella field of computer vision but in multitudes of allied fields such as animation, human computer interaction, robotics and human robot interaction. Over the years, various approaches have been proposed including physics-based simulation, key-framing, database methods, etc. But ever since the renaissance of deep learning and the rapid development of computing, the generation of synthetic human motion using deep learning based methods have received significant attention. Apart from pixel-based video data, the availability of reliable motion capture systems has enabled pose-based human action synthesis. Much of it is owed to the development of frugal motion capture systems, which enabled the curation of large scale skeleton action datasets. In this thesis, we focus on skeleton-based human action generation. To begin with, we study an approach for large-scale skeleton-based action generation. In doing so, we introduce MUGL, a novel deep neural model for large-scale, diverse generation of single and multiperson pose-based action sequences with locomotion. Our controllable approach enables variable-length generations customizable by action category, across more than 100 categories. To enable intra/intercategory diversity, we model the latent generative space using a Conditional Gaussian Mixture Variational Autoencoder. To enable realistic generation of actions involving locomotion, we decouple local pose and global trajectory components of the action sequence. We incorporate duration-aware feature representations to enable variable-length sequence generation. We use a hybrid pose sequence representation with 3D pose sequences sourced from videos and 3D Kinect-based sequences of NTU-RGBD120. To enable principled comparison of generation quality, we employ suitably modified strong baselines during evaluation. Although smaller and simpler compared to baselines, MUGL provides better quality generations, paving the way for practical and controllable large-scale human action generation. Further, we study the approaches for methods that are generalizable across datasets with varying properties and we also study methods for dense skeleton action generation. In this backdrop, we introduce DSAG, a controllable deep neural framework for action-conditioned generation of full body multi-actor variable duration actions. To compensate for incompletely detailed finger joints in existing large-scale datasets, we introduce full body dataset variants with detailed finger joints. To overcome shortcomings in existing generative approaches, we introduce dedicated representations for encoding finger joints. We also introduce novel spatiotemporal transformation blocks with multi-head self attention and specialized temporal processing. The design choices enable generations for a large range in body joint counts (24 - 52), frame rates (13 - 50), global body movement (in-place, locomotion) and action categories (12 - 120), across multiple datasets (NTU-120, HumanAct12, UESTC, Human3.6M). Our experimental results demonstrate DSAG’s significant improvements over state-of-the-art, its suitability for action-conditioned generation at scale and also for the challenging task of long-term motion prediction.

Abstract

Optimization encompasses the mathematical problem of making the best use of the resources available to us, to maximize our reward, or equivalently, minimize our cost. It is a vast field, with important applications, and the importance of optimization has only increased with the rise of machine learning and artificial intelligence - most machine learning problems involve optimization in some way or another. Optimization problems come in various forms. We consider constrained, continous optimization problems with differentiable cost functions and a specific geometric structure on the constraint set. This geometric structure is that of a Riemannian manifold, which are smooth spaces that locally resemble Euclidean space. The paradigm of geometric or Riemannian optimization tackles constrained optimization problems on Euclidean spaces, by translating these problems into unconstrained optimization problems over Riemannian manifolds which may be non-Euclidean spaces. Using concepts from Riemannian geometry, we can develop optimization problems on these manifolds. Since the manifolds have a smaller dimension than the original Euclidean space, these Riemannian optimization algorithms tend to be scalable, fast, and we can prove guarantees on the convergence of these algorithms. This thesis is concerned with the application of geometric optimization techniques to tackle machine learning problems. Specifically, we consider the task of low-rank tensor completion. This problem is an extension of the low-rank matrix completion problem, an important problem with applications in recommendation systems (like the famous Netflix Prize problem). In recent years, there has been an increased interest in multi-dimensional data, which are represented as tensors, higher-dimensional analogues of matrices. Capturing this data as a matrix fundamentally alters the structure, and causes loss of information. This motivates us to study tensor problems. Tensor completion is one such problem, where we attempt to recover the original tensor given sparse observations, under the assumption that the tensor has a small rank. It has applications in visual data inpainting and recommender systems, among others. As an extension, we study the general structured tensor completion problem, where, in addition to the low rank structure, the tensor must also satisfy some structural constraints such as nonnegativity. The dual problem for the structured tensor completion problem has a constraint set that is a Riemannian manifold. We develop optimization algorithms for this problem, provide experimental results to show the method is competitive, and provide theoretical guarantees for the recovered tensor.

Abstract

It is observed that internal repeats in eukaryotic proteins are three times more likely compared to in prokaryotes suggesting possible advantages provided to the organism. Functions specific to eukaryotes such as connective tissue proteins, cytoskeletal proteins, ribonucleoproteins, muscle proteins, brain and synaptic proteins, and cell adhesion proteins are observed to have internal repeats. The other major advantage of studying protein repeats is in their ability to confer multiple binding and structural roles on proteins. With a high frequency of occurrence in humans, 30%, tandem repeat proteins have been linked to various complex diseases, e.g., the role of Leucine-rich repeats in Parkinson's disease, ANK, HEAT, and ARM repeats in cancer, etc. A large surfaceto-volume ratio, good target affinity, smaller size, and stability in the shape of repeat proteins make them important for biomedical applications. For example, designed ankyrin repeat proteins (DARPins) are being developed for targeted therapies. Due to fewer constraints at the sequence level, detection of repeats at the structure level is desirable. Here we propose a deep learning-based approach for the detection of two major classes of structural repeats, namely, Class III and Class IV repeats in Kajava’s classification, which covers over 90% of known structural repeats and their repeat region. We approached the problem by exploiting the presence of structural information in the protein distance matrix which captures the internal distances between residues in a protein chain. Performance evaluation is carried out by comparison with other state-of-the-art methods and annotations in UniProt. Lastly, we have discussed the improvement done in the development of the NAPS Portal (Network Analysis of Protein Structures) which is used by researchers to visualize and to perform analyses of different protein structures.

Abstract

The process of data mining discovers interesting knowledge from large amounts of data. Given a large amount of data, we have several data mining software systems for summarizing/characterizing, extracting frequent patterns and association rules, classification, and clustering tasks. The data mining based systems are employed to improve the performance of e-commerce systems, marketing, search systems, banking, healthcare, etc. Investigating data mining approaches to extract new knowledge from the given data is one of the active research areas. Graph model is widely employed to model the real world. For example, a chemical compound, a protein-ligand complex, and an XML document can be modeled as a graph or a graph transaction. In the literature, the topic of extracting the knowledge of frequent subgraphs from the given Graph Transactional Dataset (GTD) has been extensively studied. It has been shown that such knowledge could help in the drug discovery process. So far, in the literature, the issue of extracting coverage-related knowledge from GTD has not yet been explored. In this thesis, we propose new data mining models and approaches to extract two types of knowledge patterns from GTDs. Motivated by the issues in the process of drug discovery, as the first contribution, we propose the model and approach to extract the coverage-related knowledge of potential subgraph patterns from the given GTD. A subgraph pattern is a set of subgraphs. We consider that a subgraph covers the graph transaction if it belongs to that graph transaction. A subgraph pattern is considered as Subgraph Coverage Pattern (SCP) if the ratio of the union of the graph transactions covered by the subgraphs of the subgraph pattern to the size of GTD is not less than a user-given threshold value. We have defined three metrics to characterize an SCP. First, the relative frequency metric ensures that each subgraph of an SCP should appear in the threshold number of graph transactions. Second, the coverage support metric ensures that the union of graph transactions covered by each subgraph of SCP should satisfy the threshold percentage of GTD. Third, the overlap ratio metric ensures that the overlap ratio among the graph transactions covered by individual subgraphs of SCP satisfies overlap ratio constraint. Given a GTD and the user-given threshold values of relative frequency, coverage support and overlap ratio, the problem is to extract all SCPs from the given GTD. A straightforward approach requires the extraction of all possible subgraphs from GTD and generation of all possible subgraph patterns. In addition, for each subgraph pattern, it requires expensive graph-based computation of relative frequency, coverage support and overlap ratio to identify all SCPs of GTD. In this model, we propose the notions of the potential subgraphs, flat transactional modeling, and employ an overlap ratio-based candidate pruning heuristic for efficiently extracting SCPs from GTD. As the second contribution, with the motivation to improve the process of drug cocktail discovery, we have proposed the model and approach to extract the coverage-related knowledge of graph transactional patterns from the given GTD. A graph transactional pattern is a set of graph transactions. A drug compound can be modeled as a graph transaction, and its fragments can be modeled as subgraphs. A set of all fragments extracted from GTD is considered as a fragment set. We consider that a graph transaction covers a fragment if the fragment belongs to that graph transaction. A graph transactional pattern is considered as a Graph Transactional Coverage Pattern (GTCP) if the ratio of the union of fragments covered by each of its graph transactions to the size of the fragment set satisfies the coverage constraint. We have defined three metrics to characterize GTCP. First, the graph transactional coverage metric ensures that each graph of GTCP should cover at least threshold percentage of fragments in the fragment set. Second, the graph transactional pattern coverage metric ensures that the union of fragments covered by each graph transaction of GTCP should satisfy the coverage constraint. Third, the overlap ratio metric ensures that the overlap ratio among the fragments covered by individual graph transactions of GTCP should satisfy the overlap ratio constraint. Given a GTD and the threshold values of graph transactional coverage, graph transactional pattern coverage, and overlap ratio, the problem is to extract all GTCPs from given GTD. A straightforward approach involves extracting all of the possible fragments from GTD and generation of all possible graph transactional patterns, which increase exponentially as the size of GTD increases. In addition, for each candidate graph transactional pattern, requires expensive graph-based computation of graph transactional pattern coverage and overlap ratio for extracting all GTCPs from GTD. In this work