Abstract

We study an important and challenging task of attacking natural language processing models in a hard label black box setting. We propose a decision-based attack strategy that crafts high quality adversarial examples on text classification and entailment tasks. Our proposed attack strategy leverages population-based optimization algorithm to craft plausible and semantically similar adversarial examples by observing only the top label predicted by the target model. At each iteration, the optimization procedure allow word replacements that maximizes the overall semantic similarity between the original and the adversarial text. Further, our approach does not rely on using substitute models or any kind of training data. We demonstrate the efficacy of our proposed approach through extensive experimentation and ablation studies on five state-of-the-art target models across seven benchmark datasets. In comparison to attacks proposed in prior literature, we are able to achieve a higher success rate with lower word perturbation percentage that too in a highly restricted setting.

Abstract

We study an important task of attacking natural language processing models in a black box setting. We propose an attack strategy that crafts semantically similar adversarial examples on text classification and entailment tasks. Our proposed attack finds candidate words by considering the information of both the original word and its surrounding context. It jointly leverages masked language modelling and next sentence prediction for context understanding. In comparison to attacks proposed in prior literature, we are able to generate high quality adversarial examples that do significantly better both in terms of success rate and word perturbation percentage.

Abstract

Team Recommendation has always been a challenging aspect in team sports. Such systems aim to recommend a player combination best suited against the opposition players, resulting in an optimal outcome. In this paper, we propose a semi-supervised statistical approach to build a team recommendation system for cricket by modelling players into embeddings. To build these embeddings, we design a qualitative and quantitative rating system which considers the strength of opposition also for evaluating player performance. The embeddings obtained, describes the strengths and weaknesses of the players based on past performances of the player. We also embark on a critical aspect of team composition, which includes the number of batsmen and bowlers in the team. The team composition changes over time, depending on different factors which are tough to predict, so we take this input from the user and use the player embeddings to decide the best possible team combination with the given team composition.

Abstract

We continue the study of the covering complexity of constraint satisfaction problems (CSPs) initiated by Guruswami, Håstad and Sudan [SIAM J. Comp. 2002] and Dinur and Kol [CCC’13]. The covering number of a CSP instance Φ is the smallest number of assignments to the variables of Φ, such that each constraint of Φ is satisfied by at least one of the assignments. We show the following results: 1. Assuming a covering variant of the Unique Games Conjecture, introduced by Dinur and Kol, we show that for every non-odd predicate P over any constant-size alphabet and every integer K, it is NP-hard to approximate the covering number within a factor of K. This yields a complete characterization of CSPs over constant-size alphabets that are hard to cover.

Abstract

Motivated by recent progress on symmetry breaking problems such as maximal independent set (MIS) and maximal matching in the low-memory Massively Parallel Computation (MPC) model (e.g., Behnezhad et al.~PODC 2019; Ghaffari-Uitto SODA 2019), we investigate the complexity of ruling set problems in this model. The MPC model has become very popular as a model for large-scale distributed computing and it comes with the constraint that the memory-per-machine is strongly sublinear in the input size. For graph problems, extremely fast MPC algorithms have been designed assuming Ω~(n) memory-per-machine, where n is the number of nodes in the graph (e.g., the O(loglogn) MIS algorithm of Ghaffari et al., PODC 2018). However, it has proven much more difficult to design fast MPC algorithms for graph problems in the low-memory MPC model, where the memory-per-machine is restricted to being strongly sublinear in the number of nodes, i.e., $O(n^eps)$ for $0 < eps < 1$. In this paper, we present an algorithm for the 2-ruling set problem, running in O~(log1/6Δ) rounds whp, in the low-memory MPC model. We then extend this result to β-ruling sets for any integer β>1. Specifically, we show that a β-ruling set can be computed in the low-memory MPC model with $O(n^eps)$ memory-per-machine in O~(β⋅log1/(2β+1−2)Δ) rounds, whp. From this it immediately follows that a β-ruling set for β=Ω(logloglogΔ)-ruling set can be computed in in just O(βloglogn) rounds whp. The above results assume a total memory of $tilde{O}(m + n^{1+eps})$. We also present algorithms for β-ruling sets in the low-memory MPC model assuming that the total memory over all machines is restricted to O~(m).

Abstract

We introduce PeeledHuman - a novel shape representation of the human body that is robust to self-occlusions. PeeledHuman encodes the human body as a set of Peeled Depth and RGB maps in 2D, obtained by performing raytracing on the 3D body model and extending each ray beyond its first intersection. This formulation allows us to handle self-occlusions efficiently compared to other representations. Given a monocular RGB image, we learn these Peeled maps in an end-to-end generative adversarial fashion using our novel framework - PeelGAN. We train PeelGAN using a 3D Chamfer loss and other 2D losses to generate multiple depth values per-pixel and a corresponding RGB field per-vertex in a dual-branch setup. In our simple non-parametric solution, the generated Peeled Depth maps are back-projected to 3D space to obtain a complete textured 3D shape. The corresponding RGB maps provide vertex …

Abstract

Product placement in retail has a significant impact on the sales revenue of retailers. Hence, research efforts are being made to improve retailer revenue using high-utility pattern mining based product placement approaches. However, none of these existing approaches has explored generalized high-utility itemset mining for determining product placement in retail. The knowledge of generalized high-utility itemsets extracted from user purchase transactional database in conjunction with a product taxonomy can provide new insights about customer purchase behaviour. This work proposes the generalized utility itemset (GUI) index for retrieving generalized high-utility (revenue) itemsets. We also present a framework, which leverages the GUI index towards retail product placement to improve revenue. Our performance study using real datasets shows the effectiveness of our proposed scheme w.r.t. two existing …

Abstract

Utility mining has been emerging as an important area in data mining. While existing works on utility mining for retail businesses have primarily focused on the problem of finding high-utility itemsets from transactional databases, they implicitly assume that each item occupies only one slot. Here, the slot size of a given item is the number of (integer) slots occupied by that item on the retail store shelves. However, in many real-world scenarios, the number of slots consumed by different items typically varies. Hence, this paper considers that a given item may physically occupy any fixed (integer) number of slots. Thus, we address the problem of efficiently determining the top-utility itemsets when a given number of slots is specified as input. The key contributions of our work are three fold. First, we present an efficient framework to determine the top-utility itemsets for different user-specified number of slots that need to be …

Abstract

Periodic-frequent pattern mining is a challenging problem of great importance in many applications. Most previous works focused on finding these patterns in binary temporal databases and did not take into account the quantities of items within the data. This paper proposes a novel model of fuzzy periodic-frequent pattern (FPFP) that may exist in a quantitative temporal database (QTD). Finding FPFPs in QTD is a non-trivial and challenging task due to its huge search space. A novel pruning technique, called improved maximum scalar cardinality, has been introduced to effectively reduce the search space and the computational cost of finding the desired itemsets. This technique facilitates the mining of FPFPs in real-world very large databases practicable. An efficient algorithm has also been presented to find all FPFPs in a QTD. Experimental results demonstrate that the proposed algorithm is efficient. We also …

Abstract

The problem of bound entanglement detection is a challenging aspect of quantum information theory for higher dimensional systems. Here, we propose an indecomposable positive map for two-qutrit systems, which is shown to generate a class of positive partial transposed (PPT) states. A corresponding witness operator is constructed and shown to be weakly optimal and locally implementable. Further, we perform a structural physical approximation of the indecomposable map to make it a completely positive one, and find a new PPT entangled state which is not detectable by certain other well-known entanglement detection criteria.