January 31, 2020

2968 words 14 mins read

Paper Group ANR 135

Approximation Ratios of Graph Neural Networks for Combinatorial Problems. Ranking variables and interactions using predictive uncertainty measures. Toward a Standard Interface for User-Defined Scheduling in OpenMP. BCMA-ES: A Bayesian approach to CMA-ES. Knowledge Distillation in Document Retrieval. Learning-based Model Predictive Control for Safe …

Approximation Ratios of Graph Neural Networks for Combinatorial Problems


Title	Approximation Ratios of Graph Neural Networks for Combinatorial Problems
Authors	Ryoma Sato, Makoto Yamada, Hisashi Kashima
Abstract	In this paper, from a theoretical perspective, we study how powerful graph neural networks (GNNs) can be for learning approximation algorithms for combinatorial problems. To this end, we first establish a new class of GNNs that can solve a strictly wider variety of problems than existing GNNs. Then, we bridge the gap between GNN theory and the theory of distributed local algorithms. We theoretically demonstrate that the most powerful GNN can learn approximation algorithms for the minimum dominating set problem and the minimum vertex cover problem with some approximation ratios with the aid of the theory of distributed local algorithms. We also show that most of the existing GNNs such as GIN, GAT, GCN, and GraphSAGE cannot perform better than with these ratios. This paper is the first to elucidate approximation ratios of GNNs for combinatorial problems. Furthermore, we prove that adding coloring or weak-coloring to each node feature improves these approximation ratios. This indicates that preprocessing and feature engineering theoretically strengthen model capabilities.
Tasks	Feature Engineering
Published	2019-05-24
URL	https://arxiv.org/abs/1905.10261v2
PDF	https://arxiv.org/pdf/1905.10261v2.pdf
PWC	https://paperswithcode.com/paper/approximation-ratios-of-graph-neural-networks
Repo
Framework

Ranking variables and interactions using predictive uncertainty measures


Title	Ranking variables and interactions using predictive uncertainty measures
Authors	Topi Paananen, Michael Riis Andersen, Aki Vehtari
Abstract	For complex nonlinear supervised learning models, assessing the relevance of input variables or their interactions is not straightforward due to the lack of a direct measure of relevance, such as the regression coefficients in generalized linear models. One can assess the relevance of input variables locally by using the mean prediction or its derivative, but this disregards the predictive uncertainty. In this work, we present a Bayesian method for identifying relevant input variables with main effects and interactions by differentiating the Kullback-Leibler divergence of predictive distributions. The method averages over local measures of relevance and has a conservative property that takes into account the uncertainty in the predictive distribution. Our empirical results on simulated and real data sets with nonlinearities demonstrate accurate and efficient identification of relevant main effects and interactions compared to alternative methods.
Tasks
Published	2019-10-17
URL	https://arxiv.org/abs/1910.07942v1
PDF	https://arxiv.org/pdf/1910.07942v1.pdf
PWC	https://paperswithcode.com/paper/ranking-variables-and-interactions-using
Repo
Framework

Toward a Standard Interface for User-Defined Scheduling in OpenMP


Title	Toward a Standard Interface for User-Defined Scheduling in OpenMP
Authors	Vivek Kale, Christian Iwainsky, Michael Klemm, Jonas H. Muller Korndorfer, Florina M. Ciorba
Abstract	Parallel loops are an important part of OpenMP programs. Efficient scheduling of parallel loops can improve performance of the programs. The current OpenMP specification only offers three options for loop scheduling, which are insufficient in certain instances. Given the large number of other possible scheduling strategies, it is infeasible to standardize each one. A more viable approach is to extend the OpenMP standard to allow for users to define loop scheduling strategies. The approach will enable standard-compliant application-specific scheduling. This work analyzes the principal components required by user-defined scheduling and proposes two competing interfaces as candidates for the OpenMP standard. We conceptually compare the two proposed interfaces with respect to the three host languages of OpenMP, i.e., C, C++, and Fortran. These interfaces serve the OpenMP community as a basis for discussion and prototype implementation for user-defined scheduling.
Tasks
Published	2019-06-21
URL	https://arxiv.org/abs/1906.08911v2
PDF	https://arxiv.org/pdf/1906.08911v2.pdf
PWC	https://paperswithcode.com/paper/toward-a-standard-interface-for-user-defined
Repo
Framework

BCMA-ES: A Bayesian approach to CMA-ES


Title	BCMA-ES: A Bayesian approach to CMA-ES
Authors	Eric Benhamou, David Saltiel, Sebastien Verel, Fabien Teytaud
Abstract	This paper introduces a novel theoretically sound approach for the celebrated CMA-ES algorithm. Assuming the parameters of the multi variate normal distribution for the minimum follow a conjugate prior distribution, we derive their optimal update at each iteration step. Not only provides this Bayesian framework a justification for the update of the CMA-ES algorithm but it also gives two new versions of CMA-ES either assuming normal-Wishart or normal-Inverse Wishart priors, depending whether we parametrize the likelihood by its covariance or precision matrix. We support our theoretical findings by numerical experiments that show fast convergence of these modified versions of CMA-ES.
Tasks
Published	2019-04-02
URL	http://arxiv.org/abs/1904.01401v1
PDF	http://arxiv.org/pdf/1904.01401v1.pdf
PWC	https://paperswithcode.com/paper/bcma-es-a-bayesian-approach-to-cma-es
Repo
Framework

Knowledge Distillation in Document Retrieval


Title	Knowledge Distillation in Document Retrieval
Authors	Siamak Shakeri, Abhinav Sethy, Cheng Cheng
Abstract	Complex deep learning models now achieve state of the art performance for many document retrieval tasks. The best models process the query or claim jointly with the document. However for fast scalable search it is desirable to have document embeddings which are independent of the claim. In this paper we show that knowledge distillation can be used to encourage a model that generates claim independent document encodings to mimic the behavior of a more complex model which generates claim dependent encodings. We explore this approach in document retrieval for a fact extraction and verification task. We show that by using the soft labels from a complex cross attention teacher model, the performance of claim independent student LSTM or CNN models is improved across all the ranking metrics. The student models we use are 12x faster in runtime and 20x smaller in number of parameters than the teacher
Tasks
Published	2019-11-11
URL	https://arxiv.org/abs/1911.11065v1
PDF	https://arxiv.org/pdf/1911.11065v1.pdf
PWC	https://paperswithcode.com/paper/knowledge-distillation-in-document-retrieval
Repo
Framework

Learning-based Model Predictive Control for Safe Exploration and Reinforcement Learning


Title	Learning-based Model Predictive Control for Safe Exploration and Reinforcement Learning
Authors	Torsten Koller, Felix Berkenkamp, Matteo Turchetta, Joschka Boedecker, Andreas Krause
Abstract	Reinforcement learning has been successfully used to solve difficult tasks in complex unknown environments. However, these methods typically do not provide any safety guarantees during the learning process. This is particularly problematic, since reinforcement learning agent actively explore their environment. This prevents their use in safety-critical, real-world applications. In this paper, we present a learning-based model predictive control scheme that provides high-probability safety guarantees throughout the learning process. Based on a reliable statistical model, we construct provably accurate confidence intervals on predicted trajectories. Unlike previous approaches, we allow for input-dependent uncertainties. Based on these reliable predictions, we guarantee that trajectories satisfy safety constraints. Moreover, we use a terminal set constraint to recursively guarantee the existence of safe control actions at every iteration. We evaluate the resulting algorithm to safely explore the dynamics of an inverted pendulum and to solve a reinforcement learning task on a cart-pole system with safety constraints.
Tasks	Safe Exploration
Published	2019-06-27
URL	https://arxiv.org/abs/1906.12189v1
PDF	https://arxiv.org/pdf/1906.12189v1.pdf
PWC	https://paperswithcode.com/paper/learning-based-model-predictive-control-for-1
Repo
Framework

A Bayesian Approach to Robust Reinforcement Learning


Title	A Bayesian Approach to Robust Reinforcement Learning
Authors	Esther Derman, Daniel Mankowitz, Timothy Mann, Shie Mannor
Abstract	Robust Markov Decision Processes (RMDPs) intend to ensure robustness with respect to changing or adversarial system behavior. In this framework, transitions are modeled as arbitrary elements of a known and properly structured uncertainty set and a robust optimal policy can be derived under the worst-case scenario. In this study, we address the issue of learning in RMDPs using a Bayesian approach. We introduce the Uncertainty Robust Bellman Equation (URBE) which encourages safe exploration for adapting the uncertainty set to new observations while preserving robustness. We propose a URBE-based algorithm, DQN-URBE, that scales this method to higher dimensional domains. Our experiments show that the derived URBE-based strategy leads to a better trade-off between less conservative solutions and robustness in the presence of model misspecification. In addition, we show that the DQN-URBE algorithm can adapt significantly faster to changing dynamics online compared to existing robust techniques with fixed uncertainty sets.
Tasks	Safe Exploration
Published	2019-05-20
URL	https://arxiv.org/abs/1905.08188v2
PDF	https://arxiv.org/pdf/1905.08188v2.pdf
PWC	https://paperswithcode.com/paper/a-bayesian-approach-to-robust-reinforcement
Repo
Framework

Learning to Control Highly Accelerated Ballistic Movements on Muscular Robots


Title	Learning to Control Highly Accelerated Ballistic Movements on Muscular Robots
Authors	Dieter Büchler, Roberto Calandra, Jan Peters
Abstract	High-speed and high-acceleration movements are inherently hard to control. Applying learning to the control of such motions on anthropomorphic robot arms can improve the accuracy of the control but might damage the system. The inherent exploration of learning approaches can lead to instabilities and the robot reaching joint limits at high speeds. Having hardware that enables safe exploration of high-speed and high-acceleration movements is therefore desirable. To address this issue, we propose to use robots actuated by Pneumatic Artificial Muscles (PAMs). In this paper, we present a four degrees of freedom (DoFs) robot arm that reaches high joint angle accelerations of up to 28000 deg/s^2 while avoiding dangerous joint limits thanks to the antagonistic actuation and limits on the air pressure ranges. With this robot arm, we are able to tune control parameters using Bayesian optimization directly on the hardware without additional safety considerations. The achieved tracking performance on a fast trajectory exceeds previous results on comparable PAM-driven robots. We also show that our system can be controlled well on slow trajectories with PID controllers due to careful construction considerations such as minimal bending of cables, lightweight kinematics and minimal contact between PAMs and PAMs with the links. Finally, we propose a novel technique to control the the co-contraction of antagonistic muscle pairs. Experimental results illustrate that choosing the optimal co-contraction level is vital to reach better tracking performance. Through the use of PAM-driven robots and learning, we do a small step towards the future development of robots capable of more human-like motions.
Tasks	Safe Exploration
Published	2019-04-07
URL	http://arxiv.org/abs/1904.03665v1
PDF	http://arxiv.org/pdf/1904.03665v1.pdf
PWC	https://paperswithcode.com/paper/learning-to-control-highly-accelerated
Repo
Framework

Efficient and Safe Exploration in Deterministic Markov Decision Processes with Unknown Transition Models


Title	Efficient and Safe Exploration in Deterministic Markov Decision Processes with Unknown Transition Models
Authors	Erdem Bıyık, Jonathan Margoliash, Shahrouz Ryan Alimo, Dorsa Sadigh
Abstract	We propose a safe exploration algorithm for deterministic Markov Decision Processes with unknown transition models. Our algorithm guarantees safety by leveraging Lipschitz-continuity to ensure that no unsafe states are visited during exploration. Unlike many other existing techniques, the provided safety guarantee is deterministic. Our algorithm is optimized to reduce the number of actions needed for exploring the safe space. We demonstrate the performance of our algorithm in comparison with baseline methods in simulation on navigation tasks.
Tasks	Safe Exploration
Published	2019-04-01
URL	http://arxiv.org/abs/1904.01068v1
PDF	http://arxiv.org/pdf/1904.01068v1.pdf
PWC	https://paperswithcode.com/paper/efficient-and-safe-exploration-in
Repo
Framework

Temporal Logic Guided Safe Reinforcement Learning Using Control Barrier Functions


Title	Temporal Logic Guided Safe Reinforcement Learning Using Control Barrier Functions
Authors	Xiao Li, Calin Belta
Abstract	Using reinforcement learning to learn control policies is a challenge when the task is complex with potentially long horizons. Ensuring adequate but safe exploration is also crucial for controlling physical systems. In this paper, we use temporal logic to facilitate specification and learning of complex tasks. We combine temporal logic with control Lyapunov functions to improve exploration. We incorporate control barrier functions to safeguard the exploration and deployment process. We develop a flexible and learnable system that allows users to specify task objectives and constraints in different forms and at various levels. The framework is also able to take advantage of known system dynamics and handle unknown environmental dynamics by integrating model-free learning with model-based planning.
Tasks	Safe Exploration
Published	2019-03-23
URL	http://arxiv.org/abs/1903.09885v1
PDF	http://arxiv.org/pdf/1903.09885v1.pdf
PWC	https://paperswithcode.com/paper/temporal-logic-guided-safe-reinforcement
Repo
Framework

Kvasir-SEG: A Segmented Polyp Dataset


Title	Kvasir-SEG: A Segmented Polyp Dataset
Authors	Debesh Jha, Pia H. Smedsrud, Michael A. Riegler, Pål Halvorsen, Thomas de Lange, Dag Johansen, Håvard D. Johansen
Abstract	Pixel-wise image segmentation is a highly demanding task in medical-image analysis. In practice, it is difficult to find annotated medical images with corresponding segmentation masks. In this paper, we present Kvasir-SEG: an open-access dataset of gastrointestinal polyp images and corresponding segmentation masks, manually annotated by a medical doctor and then verified by an experienced gastroenterologist. Moreover, we also generated the bounding boxes of the polyp regions with the help of segmentation masks. We demonstrate the use of our dataset with a traditional segmentation approach and a modern deep-learning based Convolutional Neural Network (CNN) approach. The dataset will be of value for researchers to reproduce results and compare methods. By adding segmentation masks to the Kvasir dataset, which only provide frame-wise annotations, we enable multimedia and computer vision researchers to contribute in the field of polyp segmentation and automatic analysis of colonoscopy images.
Tasks	Semantic Segmentation
Published	2019-11-16
URL	https://arxiv.org/abs/1911.07069v1
PDF	https://arxiv.org/pdf/1911.07069v1.pdf
PWC	https://paperswithcode.com/paper/kvasir-seg-a-segmented-polyp-dataset
Repo
Framework

Diagnosis of Alzheimer’s Disease via Multi-modality 3D Convolutional Neural Network


Title	Diagnosis of Alzheimer’s Disease via Multi-modality 3D Convolutional Neural Network
Authors	Yechong Huang, Jiahang Xu, Yuncheng Zhou, Tong Tong, Xiahai Zhuang, the Alzheimer’s Disease Neuroimaging Initiative
Abstract	Alzheimer’s Disease (AD) is one of the most concerned neurodegenerative diseases. In the last decade, studies on AD diagnosis attached great significance to artificial intelligence (AI)-based diagnostic algorithms. Among the diverse modality imaging data, T1-weighted MRI and 18F-FDGPET are widely researched for this task. In this paper, we propose a novel convolutional neural network (CNN) to fuse the multi-modality information including T1-MRI and FDG-PDT images around the hippocampal area for the diagnosis of AD. Different from the traditional machine learning algorithms, this method does not require manually extracted features, and utilizes the stateof-art 3D image-processing CNNs to learn features for the diagnosis and prognosis of AD. To validate the performance of the proposed network, we trained the classifier with paired T1-MRI and FDG-PET images using the ADNI datasets, including 731 Normal (NL) subjects, 647 AD subjects, 441 stable MCI (sMCI) subjects and 326 progressive MCI (pMCI) subjects. We obtained the maximal accuracies of 90.10% for NL/AD task, 87.46% for NL/pMCI task, and 76.90% for sMCI/pMCI task. The proposed framework yields comparative results against state-of-the-art approaches. Moreover, the experimental results have demonstrated that (1) segmentation is not a prerequisite by using CNN, (2) the hippocampal area provides enough information to give a reference to AD diagnosis. Keywords: Alzheimer’s Disease, Multi-modality, Image Classification, CNN, Deep Learning, Hippocampal
Tasks	Image Classification
Published	2019-02-26
URL	http://arxiv.org/abs/1902.09904v1
PDF	http://arxiv.org/pdf/1902.09904v1.pdf
PWC	https://paperswithcode.com/paper/diagnosis-of-alzheimers-disease-via-multi
Repo
Framework

Understanding Beauty via Deep Facial Features


Title	Understanding Beauty via Deep Facial Features
Authors	Xudong Liu, Tao Li, Hao Peng, Iris Chuoying Ouyang, Taehwan Kim, Ruizhe Wang
Abstract	The concept of beauty has been debated by philosophers and psychologists for centuries, but most definitions are subjective and metaphysical, and deficit in accuracy, generality, and scalability. In this paper, we present a novel study on mining beauty semantics of facial attributes based on big data, with an attempt to objectively construct descriptions of beauty in a quantitative manner. We first deploy a deep convolutional neural network (CNN) to extract facial attributes, and then investigate correlations between these features and attractiveness on two large-scale datasets labelled with beauty scores. Not only do we discover the secrets of beauty verified by statistical significance tests, our findings also align perfectly with existing psychological studies that, e.g., small nose, high cheekbones, and femininity contribute to attractiveness. We further leverage these high-level representations to original images by a generative adversarial network (GAN). Beauty enhancements after synthesis are visually compelling and statistically convincing verified by a user survey of 10,000 data points.
Tasks
Published	2019-01-30
URL	http://arxiv.org/abs/1902.05380v2
PDF	http://arxiv.org/pdf/1902.05380v2.pdf
PWC	https://paperswithcode.com/paper/understanding-beauty-via-deep-facial-features
Repo
Framework

Data Cleaning for Accurate, Fair, and Robust Models: A Big Data - AI Integration Approach


Title	Data Cleaning for Accurate, Fair, and Robust Models: A Big Data - AI Integration Approach
Authors	Ki Hyun Tae, Yuji Roh, Young Hun Oh, Hyunsu Kim, Steven Euijong Whang
Abstract	The wide use of machine learning is fundamentally changing the software development paradigm (a.k.a. Software 2.0) where data becomes a first-class citizen, on par with code. As machine learning is used in sensitive applications, it becomes imperative that the trained model is accurate, fair, and robust to attacks. While many techniques have been proposed to improve the model training process (in-processing approach) or the trained model itself (post-processing), we argue that the most effective method is to clean the root cause of error: the data the model is trained on (pre-processing). Historically, there are at least three research communities that have been separately studying this problem: data management, machine learning (model fairness), and security. Although a significant amount of research has been done by each community, ultimately the same datasets must be preprocessed, and there is little understanding how the techniques relate to each other and can possibly be integrated. We contend that it is time to extend the notion of data cleaning for modern machine learning needs. We identify dependencies among the data preprocessing techniques and propose MLClean, a unified data cleaning framework that integrates the techniques and helps train accurate and fair models. This work is part of a broader trend of Big data – Artificial Intelligence (AI) integration.
Tasks
Published	2019-04-22
URL	http://arxiv.org/abs/1904.10761v1
PDF	http://arxiv.org/pdf/1904.10761v1.pdf
PWC	https://paperswithcode.com/paper/data-cleaning-for-accurate-fair-and-robust
Repo
Framework

Crowdsourcing a High-Quality Gold Standard for QA-SRL


Title	Crowdsourcing a High-Quality Gold Standard for QA-SRL
Authors	Paul Roit, Ayal Klein, Daniela Stepanov, Jonathan Mamou, Julian Michael, Gabriel Stanovsky, Luke Zettlemoyer, Ido Dagan
Abstract	Question-answer driven Semantic Role Labeling (QA-SRL) has been proposed as an attractive open and natural form of SRL, easily crowdsourceable for new corpora. Recently, a large-scale QA-SRL corpus and a trained parser were released, accompanied by a densely annotated dataset for evaluation. Trying to replicate the QA-SRL annotation and evaluation scheme for new texts, we observed that the resulting annotations were lacking in quality and coverage, particularly insufficient for creating gold standards for evaluation. In this paper, we present an improved QA-SRL annotation protocol, involving crowd-worker selection and training, followed by data consolidation. Applying this process, we release a new gold evaluation dataset for QA-SRL, yielding more consistent annotations and greater coverage. We believe that our new annotation protocol and gold standard will facilitate future replicable research of natural semantic annotations.
Tasks	Semantic Role Labeling
Published	2019-11-08
URL	https://arxiv.org/abs/1911.03243v1
PDF	https://arxiv.org/pdf/1911.03243v1.pdf
PWC	https://paperswithcode.com/paper/crowdsourcing-a-high-quality-gold-standard
Repo
Framework