Dinesh Garg

NeurIPS Conference 2020 Conference Paper

Inductive Quantum Embedding

• Santosh Kumar Srivastava
• Dinesh Khandelwal
• Dhiraj Madan
• Dinesh Garg
• Hima Karanam
• L Venkata Subramaniam

Quantum logic inspired embedding (aka Quantum Embedding (QE)) of a Knowledge-Base (KB) was proposed recently by Garg: 2019. It is claimed that the QE preserves the logical structure of the input KB given in the form of unary and binary predicates hierarchy. Such structure preservation allows one to perform Boolean logic style deductive reasoning directly over these embedding vectors. The original QE idea, however, is limited to the transductive (not inductive) setting. Moreover, the original QE scheme runs quite slow on real applications involving millions of entities. This paper alleviates both of these key limitations. We start by reformulating the original QE problem to allow for the induction. On the way, we also underscore some interesting analytic and geometric properties of the solution and leverage them to design a faster training scheme. As an application, we show that one can achieve state-of-the-art performance on the well-known NLP task of fine-grained entity type classification by using the inductive QE approach. Our training runs 9-times faster than the original QE scheme on this task.

AAAI Conference 2020 Conference Paper

Translucent Answer Predictions in Multi-Hop Reading Comprehension

• G P Shrivatsa Bhargav
• Michael Glass
• Dinesh Garg
• Shirish Shevade
• Saswati Dana
• Dinesh Khandelwal
• L Venkata Subramaniam
• Alfio Gliozzo

Research on the task of Reading Comprehension style Question Answering (RCQA) has gained momentum in recent years due to the emergence of human annotated datasets and associated leaderboards, for example CoQA, HotpotQA, SQuAD, TriviaQA, etc. While state-of-the-art has advanced considerably, there is still ample opportunity to advance it further on some important variants of the RCQA task. In this paper, we propose a novel deep neural architecture, called TAP (Translucent Answer Prediction), to identify answers and evidence (in the form of supporting facts) in an RCQA task requiring multi-hop reasoning. TAP comprises two loosely coupled networks – Local and Global Interaction eXtractor (LoGIX) and Answer Predictor (AP). LoGIX predicts supporting facts, whereas AP consumes these predicted supporting facts to predict the answer span. The novel design of LoGIX is inspired by two key design desiderata – local context and global interaction– that we identified by analyzing examples of multi-hop RCQA task. The loose coupling between LoGIX and the AP reveals the set of sentences used by the AP in predicting an answer. Therefore, answer predictions of TAP can be interpreted in a translucent manner. TAP offers state-of-the-art performance on the HotpotQA (Yang et al. 2018) dataset – an apt dataset for multi-hop RCQA task – as it occupies Rank-1 on its leaderboard (https: //hotpotqa. github. io/) at the time of submission.

NeurIPS Conference 2019 Conference Paper

Quantum Embedding of Knowledge for Reasoning

• Dinesh Garg
• Shajith Ikbal
• Santosh Srivastava
• Harit Vishwakarma
• Hima Karanam
• L Venkata Subramaniam

Statistical Relational Learning (SRL) methods are the most widely used techniques to generate distributional representations of the symbolic Knowledge Bases (KBs). These methods embed any given KB into a vector space by exploiting statistical similarities among its entities and predicates but without any guarantee of preserving the underlying logical structure of the KB. This, in turn, results in poor performance of logical reasoning tasks that are solved using such distributional representations. We present a novel approach called Embed2Reason (E2R) that embeds a symbolic KB into a vector space in a logical structure preserving manner. This approach is inspired by the theory of Quantum Logic. Such an embedding allows answering membership based complex logical reasoning queries with impressive accuracy improvements over popular SRL baselines.

IJCAI Conference 2017 Conference Paper

Manipulating Gale-Shapley Algorithm: Preserving Stability and Remaining Inconspicuous

• Rohit Vaish
• Dinesh Garg

We study the problem of manipulation of the men-proposing Gale-Shapley algorithm by a single woman via permutation of her true preference list. Our contribution is threefold: First, we show that the matching induced by an optimal manipulation is stable with respect to the true preferences. Second, we identify a class of optimal manipulations called inconspicuous manipulations which, in addition to preserving stability, are also nearly identical to the true preference list of the manipulator (making the manipulation hard to be detected). Third, for optimal inconspicuous manipulations, we strengthen the stability result by showing that the entire stable lattice of the manipulated instance is contained inside the original lattice. ​

UAI Conference 2012 Conference Paper

Mechanism Design for Cost Optimal PAC Learning in the Presence of Strategic Noisy Annotators

• Dinesh Garg
• Sourangshu Bhattacharya
• S. Sundararajan
• Shirish K. Shevade

We consider the problem of Probably Approximate Correct (PAC) learning of a binary classifier from noisy labeled examples acquired from multiple annotators (each characterized by a respective classification noise rate). First, we consider the complete information scenario, where the learner knows the noise rates of all the annotators. For this scenario, we derive sample complexity bound for the Minimum Disagreement Algorithm (MDA) on the number of labeled examples to be obtained from each annotator. Next, we consider the incomplete information scenario, where each annotator is strategic and holds the respective noise rate as a private information. For this scenario, we design a cost optimal procurement auction mechanism along the lines of Myerson’s optimal auction design framework in a non-trivial manner. This mechanism satisfies incentive compatibility property, thereby facilitating the learner to elicit true noise rates of all the annotators.

AAAI Conference 2012 Conference Paper

Threats and Trade-Offs in Resource Critical Crowdsourcing Tasks Over Networks

• Swaprava Nath
• Pankaj Dayama
• Dinesh Garg
• Y. Narahari
• James Zou

In recent times, crowdsourcing over social networks has emerged as an active tool for complex task execution. In this paper, we address the problem faced by a planner to incentivize agents in the network to execute a task and also help in recruiting other agents for this purpose. We study this mechanism design problem under two natural resource optimization settings: (1) cost critical tasks, where the planner’s goal is to minimize the total cost, and (2) time critical tasks, where the goal is to minimize the total time elapsed before the task is executed. We define a set of fairness properties that should be ideally satisfied by a crowdsourcing mechanism. We prove that no mechanism can satisfy all these properties simultaneously. We relax some of these properties and define their approximate counterparts. Under appropriate approximate fairness criteria, we obtain a non-trivial family of payment mechanisms. Moreover, we provide precise characterizations of cost critical and time critical mechanisms.

TCS Journal 2007 Journal Article

A primal-dual algorithm for computing Fisher equilibrium in the absence of gross substitutability property

• Dinesh Garg
• Kamal Jain
• Kunal Talwar
• Vijay V. Vazirani

IROS Conference 2003 Conference Paper

A new approach to achieving sharp and timely deliveries in supply chain networks

• Dinesh Garg
• Yadati Narahari
• Nukala Viswanadham

In this paper, we come up with an innovative approach through which variability reduction and synchronization can be realized in supply chains. The approach developed is founded on a connection between mechanical design tolerancing and supply chain lead time compression. We use two metrics for delivery performance, delivery sharpness and delivery probability, which measure the accuracy as well as the precision with which products are delivered to the customers. Then we solve the following specific problem: given the delivery sharpness and delivery probability to be achieved, how can variability be allocated across individual stages of the supply chain in a cost-effective way. We call this the variance pool allocation (VPA) problem and we suggest a systematic approach for solving the VPA problem. We show that a variety of important supply chain design problems, such as supply chain partner selection, can be posed as instances of the VPA problem. We formulate and solve the VPA problem for a plastics industry supply chain and demonstrate how the solution can be used to choose the best mix of supply chain partners.

ICRA Conference 2003 Conference Paper

Design of six sigma supply chains

• Dinesh Garg
• Yadati Narahari
• Nukala Viswanadham

Variability reduction and business process synchronization are acknowledged as key to achieving sharp and timely deliveries in supply chain networks. In this paper, we introduce a new notion, which we call six sigma supply chains to describe and quantify supply chains with sharp and timely deliveries, and develop an innovative approach for designing such networks. We show that design of six sigma supply chains can be formulated as a mathematical programming problem, opening up a rich, new framework for studying supply chain design optimization problems. To show the efficacy of the notion and the design methodology, we focus on a design optimization problem, which we call as the Inventory Optimization (IOPT) problem. We formulate and solve the IOPT problem for a four stage, make-to-order liquid petroleum gas supply chain. The solution of the problem offers rich insights into inventory-service level tradeoffs in supply chain networks and proves the potential of the new approach presented in this paper.

ICRA Conference 2002 Conference Paper

Achieving Sharp Deliveries in Supply Chains through Variance Pool Allocation

• Dinesh Garg
• Yadati Narahari
• Nukala Viswanadham

In this paper, our objective is to come up with a sound methodology to design supply chains with outstanding delivery performance. As the first step towards this objective, we consider supply chains with a linear workflow, which we call pipelined supply chains. We define a new index of delivery performance called delivery sharpness which measures the precision as well as the accuracy with which products are delivered to the customers. The specific problem we solve is: given the delivery sharpness to be achieved, how can we allocate variability across individual stages of the supply chain in a cost-effective way. We call this the variance pool allocation (VPA) problem. In formulating and solving the VPA problem, we explore interesting relationships among process capability indices C/sub p/, C/sub Pk/, and C/sub Pm/, and generalize the notion of Motorola six sigma performance. The VPA problem leads to a four step design methodology and the resulting optimization problem is solved using the method of Lagrange multipliers. We present an interesting example of a supply chain in the plastics industry and illustrate the different steps of our methodology.