Abstract: We consider the classical problem of finding the minimum feedback arc set on tournaments (MFAST). The problem is NP-hard in general and we study it for important classes of tournaments that arise naturally in the problem of learning to rank from pairwise comparisons. Specifically, we consider tournaments classes that arise out of parametric preference matrices that can lead to cyclic preference relations. The parametric assumption we make is a limit on the rank of the true preference matrix under a suitable link function. We investigate the structural properties of the tournaments induced by rank 2 preference matrices via forbidden sub tournament configurations. These properties are used to prove the optimality of our proposed ranking algorithm, Rank2Rank(R2R), on the rank 2 class of tournaments. We then propose the Block-Rank 2 tournament class and demonstrate its usefulness in modelling real world data. R2R can be used as a subroutine to develop another ranking algorithm, BlockRank2Rank(BR2R), which is optimal for the Block-Rank 2 tournament class. As an application, we study the problem of learning to rank from pairwise comparisons under the proposed model. Exploiting our structural characterization, we propose PairwiseBlockRank - a pairwise ranking algorithm for this class. We provide sample complexity bounds and performance comparisons with other popular ranking algorithms to show the efficacy of the proposed algorithm.

Reference: Vishnu Veerathu and Arun Rajkumar. (2021) “On The Structure of Parametric Tournaments with Application to Ranking from Pairwise Comparisons”. To appear in Thirty-fifth Annual Conference on Neural Information Processing Systems (NeurIPS 2021).

Abstract: Deep convolutional neural networks (CNNs) for video denoising are typically trained with supervision, assuming the availability of clean videos. However, in many applications, such as microscopy, noiseless videos are not available. To address this, we propose an Unsupervised Deep Video Denoiser (UDVD), a CNN architecture designed to be trained exclusively with noisy data. The performance of UDVD is comparable to the supervised state-of-the-art, even when trained only on a single short noisy video. We demonstrate the promise of our approach in real-world imaging applications by denoising raw video, fluorescence-microscopy, and electron-microscopy data. In contrast to many current approaches to video denoising, UDVD does not require explicit motion compensation. This is advantageous because motion compensation is computationally expensive, and can be unreliable when the input data are noisy. A gradient-based analysis reveals that UDVD automatically tracks the motion of objects in the input noisy videos. Thus, the network learns to perform implicit motion compensation, even though it is only trained for denoising.

Reference: Sheth, D. Y., Mohan, S., Vincent, J. L., Manzorro, R., Crozier, P. A., Khapra, M. M., ... & Fernandez-Granda, C. (2021). Unsupervised deep video denoising. In Proceedings of the IEEE/CVF International Conference on Computer Vision (pp. 1759-1768). PDF

Abstract: Natural Language Generation (NLG) evaluation is a multifaceted task requiring the assessment of multiple desirable criteria, e.g., fluency, coherency, coverage, relevance, adequacy, overall quality, etc. However, the majority of the existing automatic evaluation metrics provide just a single overall score. In this talk, we will first discuss an overview of the techniques used for formulating automatic evaluation metrics for NLG. Across existing datasets for 6 NLG tasks, we observe that the human evaluation scores on these multiple criteria are often not correlated. For example, there is a very low correlation between human scores on fluency and data coverage for the task of structured data to text generation. This suggests that the current recipe of proposing new automatic evaluation metrics for NLG by showing that they correlate well with scores assigned by humans for a single criteria (overall quality) alone is inadequate. Indeed, we find that there is no single metric that correlates well with human scores on all desirable criteria, for most NLG tasks. Given this situation, we propose CheckLists for better design and evaluation of automatic metrics. We design templates that target specific criteria (e.g., coverage) and perturb the output such that the quality gets affected only along with these specific criteria (e.g., the coverage drops). We show that existing evaluation metrics are not robust against even such simple perturbations and disagree with scores assigned by humans to the perturbed output. The proposed templates thus allow for a fine-grained assessment of automatic evaluation metrics exposing their limitations and will facilitate better design, analysis, and evaluation of such metrics.

Reference: Ananya B. Sai, Tanay Dixit, Dev Sheth, Sreyas Mohan and Mitesh M. Khapra: Perturbation CheckLists for Evaluating NLG Evaluation Metrics. In Proceedings of Empirical Methods in Natural Language Processing (EMNLP 2021). PDF

Abstract: Multiplex networks are complex graph structures in which a set of entities are connected to each other via multiple types of relations, each relation representing a distinct layer. Such graphs are used to investigate many complex biological, social, and technological systems. In this work, we present a novel semi-supervised approach for structure-aware representation learning on multiplex networks. Our approach relies on maximizing the mutual information between local node-wise patch representations and label correlated structure-aware global graph representations to model the nodes and cluster structures jointly. Specifically, it leverages a novel cluster-aware, node-contextualized global graph summary generation strategy for effective joint-modeling of node and cluster representations across the layers of a multiplex network. Empirically, we demonstrate that the proposed architecture outperforms state-of-the-art methods in a range of tasks: classification, clustering, visualization, and similarity search on seven real-world multiplex networks for various experiment settings.

Reference: Mitra, A., Vijayan, P., Sanasam, R., Goswami, D., Parthasarathy, S., & Ravindran, B. (2021, August). Semi-Supervised Deep Learning for Multiplex Networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining (pp. 1234-1244). PDF

Abstract: Ensemble learning is a very prevalent method employed in machine learning. The relative success of ensemble methods is attributed to their ability to tackle a wide range of instances and complex problems that require different low-level approaches. However, ensemble methods are relatively less popular in reinforcement learning owing to the high sample complexity and computational expense involved in obtaining a diverse ensemble. We present a novel training and model selection framework for model-free reinforcement algorithms that use ensembles of policies obtained from a single training run. These policies are diverse in nature and are learned through directed perturbation of the model parameters at regular intervals. We show that learning and selecting an adequately diverse set of policies is required for a good ensemble while extreme diversity can prove detrimental to overall performance. The selection of an adequately diverse set of policies is done through our novel policy selection framework. We evaluate our approach to challenging discrete and continuous control tasks and also discuss various ensembling strategies. Our framework is substantially sampled efficient, computationally inexpensive, and is seen to outperform state-of-the-art (SOTA) scores in Atari 2600 and Mujoco.

Reference: Saphal, R., Ravindran, B., Mudigere, D., Avancha, S., & Kaul, B. (2021). SEERL: Sample Efficient Ensemble Reinforcement Learning. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems (pp. 1100–1108). (AAMAS 2021) PDF

Abstract: State abstraction enables sample-efficient learning and better task transfer in complex reinforcement learning environments. State abstraction is especially beneficial in relational settings, where the number and/or types of objects are not fixed apriori. Inspired by the benefits of state abstraction in hierarchical planning and learning, we recently proposed a framework that can obtain task-specific state abstractions from humans. I will first briefly present the proposed RePReL model, a hierarchical framework that integrates relational planning and reinforcement learning. Then demonstrate how we use an SRL model to obtain the prior domain knowledge from humans that provides effective task-specific state abstractions.

Reference: Kokel, H., Manoharan, A., Natarajan, S., Ravindran, B., & Tadepalli, P. (2021, May). RePReL: Integrating Relational Planning and Reinforcement Learning for Effective Abstraction. In Proceedings of the International Conference on Automated Planning and Scheduling (Vol. 31, pp. 533-541). PDF