Abstract

Sparse neural networks are shown to give accurate predictions competitive to denser versions, while also minimizing the number of arithmetic operations performed. However current GPU hardware can only exploit structured sparsity patterns for better efficiency. We propose a framework for generating structured multilevel block sparse neural networks by using the theory of graph products. Our Ramanujan bipartite graph product (RBGP) framework uses products of Ramanujan graphs to obtain the best connectivity for a given level of sparsity. This essentially ensures that the i.) the networks has the structured block sparsity for which runtime efficient algorithms exists, ii.) the model gives high prediction accuracy, due to the better expressive power derived from the connectivity of the graph, iii.) the graph data structure has a succinct representation that can be stored efficiently in memory. We use our framework to design a specific connectivity pattern called RBGP4 which makes efficient use of the memory hierarchy available on GPU. We benchmark our approach on image classification and machine translation tasks with an edge (Jetson Nano 2GB) as well as server (V100) GPUs. When compared with commonly used sparsity patterns like unstructured and block, we obtain significant speedups while achieving the same level of accuracy.

Abstract

Recent approaches to the tensor completion problem have often overlooked the nonnegative structure of the data. We consider the problem of learning a nonnegative lowrank tensor, and using duality theory, we propose a novel factorization of such tensors. The factorization decouples the nonnegative constraints from the low-rank constraints. The resulting problem is an optimization problem on manifolds, and we propose a variant of Riemannian conjugate gradients to solve it. We test the proposed algorithm across various tasks such as colour image inpainting, video completion, and hyperspectral image completion. Experimental results show that the proposed method outperforms many state-of-the-art tensor completion algorithms.

Abstract

The tourism industry is important for the benefits it brings and due to its role as a commercial activity that creates demand and growth for many more industries. Yet there is not much work on data science problems in tourism. Unfortunately, there is not even a standard benchmark for evaluation of tourismspecific data science tasks and models. In this paper, we propose a benchmark, TOURISMNLG, of five natural language generation (NLG) tasks for the tourism domain and release corresponding datasets with standard train, validation and test splits1 . Further, previously proposed data science solutions for tourism problems do not leverage the recent benefits of transfer learning. Hence, we also contribute the first rigorously pretrained mT5 and mBART model checkpoints for the tourism domain. The models have been pretrained on four tourism-specific datasets covering different aspects of tourism. Using these models, we present initial baseline results on the benchmark tasks. We hope that the dataset will promote active research for natural language generation for travel and tourism. Keywords: NLG for Tourism · Long QA · Blog-Title Generation · Forum-Title Generation · Paragraph Generation · Short QA

Abstract

The ILSUM shared task focuses on text summarization for two major Indian languages- Hindi and Gujarati, along with English. In this task, we experiment with various pretrained sequence-to-sequence models to find out the best model for each of the languages. We present a detailed overview of the models and our approaches in this paper. We secure the first rank across all three sub-tasks (English, Hindi and Gujarati). This paper also extensively analyzes the impact of k-fold cross-validation while experimenting with limited data size, and we also perform various experiments with a combination of the original and a filtered version of the data to determine the efficacy of the pretrained models.

Abstract

We consider the standard broadcast setup with a single server broadcasting information to a number of clients, each of which contains local storage (called cache) of some size, which can store some parts of the available files at the server. The centralized coded caching framework, consists of a caching phase and a delivery phase, both of which are carefully designed in order to use the cache and the channel together optimally. In prior literature, various combinatorial structures have been used to construct coded caching schemes. One of the chief drawbacks of many of these existing constructions is the large subpacketization level, which denotes the number of times a file should be split for the schemes to provide coding gain. In this work, using a new binary matrix model, we present several novel constructions for coded caching based on the various types of combinatorial designs and their q-analogs, which are also called subspace designs. While most of the schemes constructed in this work (based on existing designs) have a high cache requirement, they provide a rate that is either constant or decreasing, and moreover require competitively small levels of subpacketization, which is an extremely important feature in practical applications of coded caching. We also apply our constructions to the distributed computing framework of MapReduce, which consists of three phases, the Map phase, the Shuffle phase and the Reduce phase. Using our binary matrix framework, we present a new simple generic coded data shuffling scheme. Employing our designs-based constructions in conjunction with this new shuffling scheme, we obtain new coded computing schemes which have low file complexity, with marginally higher communication load compared to the optimal scheme for equivalent parameters. We show that our schemes can neatly extend to the scenario with full and partial stragglers also.

Abstract

We say that two given polynomials f, g ∈ R[x_1, ..., x_n], over a ring R, are equivalent under shifts if there exists a vector (a_1, ..., a_n) ∈ Rⁿ such that f(x_1+a_1, ..., x_n+a_n) = g(x_1, ..., x_n). This is a special variant of the polynomial projection problem in Algebraic Complexity Theory. Grigoriev and Karpinski (FOCS 1990), Lakshman and Saunders (SIAM J. Computing, 1995), and Grigoriev and Lakshman (ISSAC 1995) studied the problem of testing polynomial equivalence of a given polynomial to any t-sparse polynomial, over the rational numbers, and gave exponential time algorithms. In this paper, we provide hardness results for this problem. Formally, for a ring R, let SparseShift_R be the following decision problem - Given a polynomial P(X), is there a vector 𝐚 such that P(X+𝐚) contains fewer monomials than P(X). We show that SparseShift_R is at least as hard as checking if a given system of polynomial equations over R[x_1,..., x_n] has a solution (Hilbert’s Nullstellensatz). As a consequence of this reduction, we get the following results. 1) SparseShift_ℤ is undecidable. 2) For any ring R (which is not a field) such that HN_R is NP_R-complete over the Blum-Shub-Smale model of computation, SparseShift_ is also NP_R-complete. In particular, SparseShift_ℤ is also NP_ℤ-complete. We also study the gap version of the SparseShift_R and show the following. 1) For every function β:ℕ → ℝ_+ such that β ∈ o(1), N^β-gap-SparseShift_ℤ is also undecidable (where N is the input length). 2) For R = 𝔽_p, ℚ, ℝ or ℤ_q and for every β > 1 the β-gap-SparseShift_R problem is NP-hard. Furthermore, there exists a constant α > 1 such that for every d = O(1) in the sparse representation model, and for every d ≤ n^O(1) in the arithmetic circuit model, the α^d-gap-SparseShift_R problem is NP-hard when given polynomials of degree at most d, in O(nd) many variables, as input.

Abstract

In this paper, we study the min-max optimization problems on Riemannian manifolds. We introduce a Riemannian Hamiltonian function, minimization of which serves as a proxy for solving the original min-max problems. Under the Riemannian Polyak--Łojasiewicz (PL) condition on the Hamiltonian function, its minimizer corresponds to the desired min-max saddle point. We also provide cases where this condition is satisfied. To minimize the Hamiltonian function, we propose Riemannian Hamiltonian methods (RHM) and present their convergence analysis. We extend RHM to include a consensus regularization and to the stochastic setting. We illustrate the efficacy of the proposed RHM in applications such as subspace robust Wasserstein distance, robust training of neural networks, and generative adversarial networks.

Abstract

Writing a good job description is an important step in the online recruitment process to hire the best candidates. Most recruiters forget to include some relevant skills in the job description. These missing skills affect the performance of recruitment tasks such as job suggestions, job search, candidate recommendations, etc. Existing approaches are limited to contextual modelling, do not exploit inter-relational structures like job-job and job-skill relationships, and are not scalable. In this paper, we exploit these structural relationships using a graph-based approach. We propose a novel skill prediction framework called JobXMLC, which uses graph neural networks with skill attention to predict missing skills using job descriptions. JobXMLC enables joint learning over a job-skill graph consisting of 22.8K entities (jobs and skills) and 650K relationships. We experiment with real-world recruitment datasets to evaluate our proposed approach. We train JobXMLC on 20, 298 jobs and 2, 548 skills within 30 minutes on a single GPU machine. JobXMLC outperforms the state-of-the-art approaches by 6% on precision and 3% on recall. JobXMLC is 18X faster for training tasks and up to 634X faster in skill prediction on benchmark datasets enabling JobXMLC to scale up on larger datasets. We have made our code and dataset public at https://precog.iiit.ac.in/resources.html.

Abstract

Vital gene expressions form the basis for the detection of malaria infection levels. Quantification of infected erythrocytes and classification of their life cycle stages are done at a macroscopic level by experts, for making informed decisions for diagnosis and treatment of malaria. Of late multiple computational approaches have been proposed to circumvent the problem of dimensionality leading to accurately predicted results. In this work, a dimensionality reduction technique based on Genetic Algorithm (GA) is applied to Plasmodium falciparum single cell transcriptomics to arrive at an optimized subset of features from the larger dataset. Features are chosen based on their class variants considering increased efficiency and accuracy, to separately transform the selected elements into a lower dimension. For the classification of the life cycle of malaria parasites based on single cell transcriptome data, a three-pronged approach employing the multiclass Support Vector Machine (SVM), Logistic Regression (LR), and Random Forest (RF) technique is used. Further, we constructed protein interaction networks of the genes identified by the feature selection method and gene ontology analysis elucidated the role of the proteins in the progression of the parasite through its life cycle. Our approach presents a novel protocol to implement ML techniques on scRNA seq datasets and subsequently harness the extracted information for biomarker/drug target detection.

Abstract

Employment scams, such as scapegoat positions, clickbait and non-existing jobs, etc., are among the top five scams registered over online platforms.1 Generally, scam complaints contain heterogeneous information (money, location, employment type, organization, email, and phone number), which can provide critical insights for appropriate interventions to avoid scams. Despite substantial efforts to analyze employment scams, integrating relevant scam-related information in structured form remains unexplored. In this work, we extract this information and construct a large-scale Employment Scam Knowledge Graph consisting of 0.1M entities and 0.2M relationships. Our findings include discovering different modes of employment scams, entities, and relationships among entities to alert job seekers. We plan to extend this work by utilizing a knowledge graph to identify and avoid potential scams in the future