Harman Singh, Poorva Garg, Mohit Gupta, Kevin Shah, Ashish Goswami, Satyam Modi, Arnab Mondal, Dinesh Khandelwal, Dinesh Garg, Parag Singla. Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing. 2023.

Knowledge Graph Question Answering (KGQA) has become a prominent area in natural language processing due to the emergence of large scale Knowledge Graphs (KGs). Semantic parsing based approach is the predominant direction to solve the KGQA task where natural language question is translated into a logic form such as SPARQL query. Recently Neural Machine Translation (NMT) based approaches are gaining momentum in order to translate natural language query to structured query languages thereby solving the KGQA task. However, most of these methods struggle with out-of-vocabulary words where test entities and relations are not seen during training time. In this work, we propose a modular two stage neural architecture to solve the KGQA task. Stage-I of our approach comprises a NMT-based seq2seq module that translates a question into a sketch of the desired SPARQL query called a SPARQL silhouette. Stage-II of our approach comprises a Neural Graph Search (NGS) module which aims to improve the quality of the SPARQL silhouette by detecting the right relations in the underlying knowledge graph. Experimental results show that we achieve substantial improvements and obtain state-of-the-art performance or comparable results to the best performing systems on two benchmark datasets. We believe, our proposed approach is novel and will lead to dynamic KGQA solutions that are well-suited for practical applications.

Shopping experience on any e-commerce website is largely driven by the content customers interact with. The large volume of diverse content on e-commerce platforms, and the advances in machine learning, pose unique opportunities for gathering insights through content understanding and applying these insights to generate content better shopper experience. The purpose of the first edition of this workshop was to bring together researchers from industry and academia on questions surrounding e-commerce content understanding and generation.

Shourya Aggarwal, Divyanshu Mandowara, Vishwajeet Agrawal, Dinesh Khandelwal, Parag Singla, Dinesh Garg. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). 2021.

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.

Vittorio Castelli, Rishav Chakravarti, Saswati Dana, Anthony Ferritto, Radu Florian, Martin Franz, Dinesh Garg, Dinesh Khandelwal, Scott McCarley, Michael McCawley, Mohamed Nasr, Lin Pan, Cezar Pendus, John Pitrelli, Saurabh Pujar, Salim Roukos, Andrzej Sakrajda, Avi Sil, Rosario Uceda-Sosa, Todd Ward, Rong Zhang. Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics. 2020.

Michael Glass, Alfio Gliozzo, Rishav Chakravarti, Anthony Ferritto, Lin Pan, G P Shrivatsa Bhargav, Dinesh Garg, Avi Sil. Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics. 2020.

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.

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.

Community-driven Question Answering (CQA) systems such as Yahoo!Answers have become valuable sources of reusable information.CQA retrieval enables usage of historical CQA archives to solve new questions posed by users.This task has received much recent attention, with methods building upon literature from translation models, topic models, and deep learning.In this paper, we devise a CQA retrieval technique, LASER-QA, that embeds question-answer pairs within a unified latent space preserving the local neighborhood structure of question and answer spaces.The idea is that such a space mirrors semantic similarity among questions as well as answers, thereby enabling high quality retrieval.Through an empirical analysis on various real-world QA datasets, we illustrate the improved effectiveness of LASER-QA over state-of-theart methods.

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.​

AUC (Area under the ROC curve) is an important performance measure for applications where the data is highly imbalanced. Efficient AUC optimization is a challenging research problem as the objective function is non-decomposable and non-continuous. Using a max-margin based surrogate loss function, AUC optimization problem can be approximated as a pairwise RankSVM learning problem. Batch learning algorithms for solving the kernelized version of this problem suffer from scalability issues. Therefore, recent years have witnessed an increased interest in the development of online or single-pass algorithms that design a nonlinear classifier by maximizing the AUC performance. However, on many real-world datasets, the AUC performance of these classifiers was observed to be inferior to that of the classifiers designed using batch learning algorithms. Further, many practical imbalanced data classification problems demand fast inference, which underlines the need for designing sparse nonlinear classifiers. Motivated by these observations, we design a scalable algorithm for maximizing the AUC performance by greedily adding the required number of basis functions into the classifier model. The resulting sparse classifier performs faster inference and its AUC performance is comparable with that of the classifier designed using batch mode. Our experimental results show that the level of sparsity achievable can be an order of magnitude larger than that achieved by the Kernel RankSVM model without significantly affecting the AUC performance.

We study the problem of training an accurate linear regression model by procuring labels from multiple noisy crowd annotators, under a budget constraint. We propose a Bayesian model for linear regression in crowdsourcing and use variational inference for parameter estimation. To minimize the number of labels crowdsourced from the annotators, we adopt an active learning approach. In this specific context, we prove the equivalence of well-studied criteria of active learning like entropy minimization and expected error reduction. Interestingly, we observe that we can decouple the problems of identifying an optimal unlabeled instance and identifying an annotator to label it. We observe a useful connection between the multi-armed bandit framework and the annotator selection in active learning. Due to the nature of the distribution of the rewards on the arms, we use the Robust Upper Confidence Bound (UCB) scheme with truncated empirical mean estimator to solve the annotator selection problem. This yields provable guarantees on the regret. We further apply our model to the scenario where annotators are strategic and design suitable incentives to induce them to put in their best efforts.

Label propagation is a well-explored family of methods for training a semi-supervised classifier where input data points (both labeled and unlabeled) are connected in the form of a weighted graph. For binary classification, the performance of these methods starts degrading considerably whenever input dataset exhibits following characteristics - (i) one of the class label is rare label or equivalently, class imbalance (CI) is very high, and (ii) degree of supervision (DoS) is very low -- defined as fraction of labeled points. These characteristics are common in many real-world datasets relating to network fraud detection. Moreover, in such applications, the amount of class imbalance is not known a priori. In this paper, we have proposed and justified the use of an alternative formulation for graph label propagation under such extreme behavior of the datasets. In our formulation, objective function is the difference of two convex quadratic functions and the constraints are box constraints. We solve this program using Concave-Convex Procedure (CCCP). Whenever the problem size becomes too large, we suggest to work with a k-NN subgraph of the given graph which can be sampled by using Locality Sensitive Hashing (LSH) technique. We have also discussed various issues that one typically faces while sampling such a k-NN subgraph in practice. Further, we have proposed a novel label flipping method on top of the CCCP solution, which improves the result of CCCP further whenever class imbalance information is made available a priori. Our method can be easily adopted for a MapReduce platform, such as Hadoop. We have conducted experiments on 11 datasets comprising a graph size of up to 20K nodes, CI as high as 99:6%, and DoS as low as 0:5%. Our method has resulted up to 19:5-times improvement in F-measure and up to 17:5-times improvement in AUC-PR measure against baseline methods.

We consider the team formation problem where the goal is to find a team of experts for a specific project. In the past, several attempts have been made to formulate this problem and each formulation focuses only on a subset of design criteria such as skill coverage, social compatibility, economy, skill redundancy, etc. In this paper, for the first time, we show that most of the important design criteria for this problem can be fully modeled within one single formulation as an unconstrained submodular function maximization problem. In our formulation, the submodular function turns out to be non-negative and non-monotone. The maximization of this class of submodular function is much less explored than its monotone constrained counterpart. A few recent works [7] [4] have come up with a simulated annealing based randomized approximation scheme for this problem with an approximation ratio of 0.41. In this paper, we customize this algorithm to our formulation and conduct an extensive set of experiments to show its efficacy. Our proposed formulation offers several advantageous features over the existing formulations including skill cover softening, better team communication, and connectivity relaxation. Unlike previous formulations, the skill cover softening feature allows a designer to specify Must Have and Should Have skills. Similarly, through better team communication, we avoid the restriction that all the communication among team members should pass through only the team members and not the outsiders. Finally, connectivity relaxation feature alleviates the constraint of whole team being connected and thereby, lowering the cost.

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.

Stochastic knapsack problems deal with selecting items with potentially random sizes and rewards so as to maximize the total reward while satisfying certain capacity constraints. A novel variant of this problem, where items are worthless unless collected in bundles, is introduced here. This setup is similar to the Groupon model, where a deal is off unless a minimum number of users sign up for it. Since the optimal algorithm to solve this problem is not practical, several adaptive greedy approaches with reasonable time and memory requirements are studied in detail - theoretically, as well as, experimentally. Worst case performance guarantees are provided for some of these greedy algorithms, while results of experimental evaluation demonstrate that they are much closer to optimal than what the theoretical bounds suggest. Applications include optimizing for online advertising pricing models where advertisers pay only when certain goals, in terms of clicks or conversions, are met. We perform extensive experiments for the situation where there are between two and five ads. For typical ad conversion rates, the greedy policy of selecting items having the highest individual expected reward obtains a value within 5% of optimal over 95% of the time for a wide selection of parameters.

Mobile-enabled social networks applications are becoming increasingly popular. Most of the current social network applications have been designed for high-end mobile devices, and they rely upon features such as GPS, capabilities of the world wide web, and rich media support. However, a significant fraction of mobile user base, especially in the developing world, own low-end devices that are only capable of voice and short text messages (SMS). In this context, a natural question is whether one can design meaningful social network-based applications that can work well with these simple devices, and if so, what the real challenges are. Towards answering these questions, this paper presents a social network-based recommender system that has been explicitly designed to work even with devices that just support phone calls and SMS. Our design of the social network based recommender system incorporates three features that complement each other to derive highly targeted ads. First, we analyze information such as customer's address books to estimate the level of social affinity among various users. This social affinity information is used to identify the recommendations to be sent to an individual user. Second, we combine the social affinity information with the spatio-temporal context of users and historical responses of the user to further refine the set of recommendations and to decide when a recommendation would be sent. Third, social affinity computation and spatio-temporal contextual association are continuously tuned through user feedback. We outline the challenges in building such a system, and outline approaches to deal with such challenges.

In this paper, we first describe a framework to model the sponsored search auction on the Web as a mechanism design problem. Using this framework, we describe two well-known mechanisms for sponsored search auction - generalized second price (GSP) and Vickrey-Clarke-Groves (VCG). We then derive a new mechanism for sponsored search auction which we call optimal (OPT) mechanism. The OPT mechanism maximizes the search engine's expected revenue, while achieving Bayesian incentive compatibility and individual rationality of the advertisers. We then undertake a detailed comparative study of the mechanisms GSP, VCG, and OPT. We compute and compare the expected revenue earned by the search engine under the three mechanisms when the advertisers are symmetric and some special conditions are satisfied. We also compare the three mechanisms in terms of incentive compatibility, individual rationality, and computational complexity.

In this paper, we focus on mechanism design for single leader Stackelberg problems, which are a special case of hierarchical decision making problems in which a distinguished agent, known as theleader, makes the first move and this action is followed by the actions of the remaining agents, which are known as thefollowers. These problems are also known assingleleaderrestfollower(SLRF) problems. There are many examples of such problems in the areas of electronic commerce, supply chain management, manufacturing systems, distributed computing, transportation networks, and multiagent systems. The game induced among the agents for these problems is a Bayesian Stackelberg game, which is more general than a Bayesian game. For this reason, classical mechanism design, which is based on Bayesian games, cannot be applied as is for solving SLRF mechanism design problems. In this paper, we extend classical mechanism design theory to the specific setting of SLRF problems. As a significant application of the theory developed, we explore two examples from the domain of electronic commerce-first-priceandsecond-priceelectronicprocurementauctionswithreserveprices. Using an SLRF model for these auctions, we derive certain key results using the SLRF mechanism design framework developed in this paper. The theory developed has many promising applications in modeling and solving emerging game theoretic problems in engineering.

Variability reduction and business-process synchronization are acknowledged as keys 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. The approach developed in this paper is founded on an intriguing connection between mechanical design tolerancing and supply-chain lead-time compression. We show that the 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 the inventory optimization (IOPT) problem. Given a multistage supply-chain network, the IOPT problem seeks to find optimal allocation of lead time variabilities and inventories to individual stages, so as to achieve required levels of delivery performance in a cost-effective way. 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.Note to Practitioners-This paper builds a bridge between mechanical design tolerancing and supply-chain management. In particular, the paper explores the use of statistical tolerancing techniques in achieving outstanding delivery performance through variability reduction. Informally, a six sigma supply chain is that which delivers products within a customer specified delivery window, with at most 3.4 missed deliveries per million. The innovations in this paper are the following: 1) to define two performance metrics delivery probability and delivery sharpness to describe the precision and accuracy of deliveries, in terms of process capability indexes C/sub p/,C/sub pk/, and C/sub pm/; 2) to formulate the supply-chain design optimization problem using the process capability indices; 3) to suggest an efficient solution procedure for the design optimization problem. The paper presents the case study of a two-echelon distribution network and using the framework developed in the paper shows the role of inventory in controlling lead time variability and achieving six sigma levels of delivery performance.

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.

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.

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.