pwc-archive/papers-with-abstracts huggingface dataset:
Deep MR Fingerprinting with total-variation and low-rank subspace priors
Authors: Mohammad Golbabaee, Carolin M. Pirkl, Marion I. Menzel, Guido Buonincontri, Pedro A. Gómez
Date: 2019-02-26 00:00:00
Tasks: Magnetic Resonance Fingerprinting, parameter estimation, Time Series, Time Series Analysis

Deep learning (DL) has recently emerged to address the heavy storage and
computation requirements of the baseline dictionary-matching (DM) for Magnetic
Resonance Fingerprinting (MRF) reconstruction. Fed with non-iterated
back-projected images, the network is unable to fully resolve
spatially-correlated corruptions caused from the undersampling artefacts. We
propose an accelerated iterative reconstruction to minimize these artefacts
before feeding into the network. This is done through a convex regularization
that jointly promotes spatio-temporal regularities of the MRF time-series.
Except for training, the rest of the parameter estimation pipeline is
dictionary-free. We validate the proposed approach on synthetic and in-vivo
datasets.
Differentiable Scene Graphs
Authors: Moshiko Raboh, Roei Herzig, Gal Chechik, Jonathan Berant, Amir Globerson
Date: 2019-02-26 00:00:00
Tasks: Visual Reasoning

Reasoning about complex visual scenes involves perception of entities and their relations. Scene graphs provide a natural representation for reasoning tasks, by assigning labels to both entities (nodes) and relations (edges). Unfortunately, reasoning systems based on SGs are typically trained in a two-step procedure: First, training a model to predict SGs from images; Then, a separate model is created to reason based on predicted SGs. In many domains, it is preferable to train systems jointly in an end-to-end manner, but SGs are not commonly used as intermediate components in visual reasoning systems because being discrete and sparse, scene-graph representations are non-differentiable and difficult to optimize. Here we propose Differentiable Scene Graphs (DSGs), an image representation that is amenable to differentiable end-to-end optimization, and requires supervision only from the downstream tasks. DSGs provide a dense representation for all regions and pairs of regions, and do not spend modelling capacity on areas of the images that do not contain objects or relations of interest. We evaluate our model on the challenging task of identifying referring relationships (RR) in three benchmark datasets, Visual Genome, VRD and CLEVR. We describe a multi-task objective, and train in an end-to-end manner supervised by the downstream RR task. Using DSGs as an intermediate representation leads to new state-of-the-art performance.
RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space
Authors: Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, Jian Tang
Date: 2019-02-26 00:00:00
Proceeding: ICLR 2019 5
Tasks: Graph Embedding, Knowledge Graph Embedding, Knowledge Graphs, Link Prediction, Relation

We study the problem of learning representations of entities and relations in
knowledge graphs for predicting missing links. The success of such a task
heavily relies on the ability of modeling and inferring the patterns of (or
between) the relations. In this paper, we present a new approach for knowledge
graph embedding called RotatE, which is able to model and infer various
relation patterns including: symmetry/antisymmetry, inversion, and composition.
Specifically, the RotatE model defines each relation as a rotation from the
source entity to the target entity in the complex vector space. In addition, we
propose a novel self-adversarial negative sampling technique for efficiently
and effectively training the RotatE model. Experimental results on multiple
benchmark knowledge graphs show that the proposed RotatE model is not only
scalable, but also able to infer and model various relation patterns and
significantly outperform existing state-of-the-art models for link prediction.
Learning to See the Wood for the Trees: Deep Laser Localization in Urban and Natural Environments on a CPU
Authors: Georgi Tinchev, Adrian Penate-Sanchez, Maurice Fallon
Date: 2019-02-26 00:00:00
Tasks: CPU, Loop Closure Detection

Localization in challenging, natural environments such as forests or
woodlands is an important capability for many applications from guiding a robot
navigating along a forest trail to monitoring vegetation growth with handheld
sensors. In this work we explore laser-based localization in both urban and
natural environments, which is suitable for online applications. We propose a
deep learning approach capable of learning meaningful descriptors directly from
3D point clouds by comparing triplets (anchor, positive and negative examples).
The approach learns a feature space representation for a set of segmented point
clouds that are matched between a current and previous observations. Our
learning method is tailored towards loop closure detection resulting in a small
model which can be deployed using only a CPU. The proposed learning method
would allow the full pipeline to run on robots with limited computational
payload such as drones, quadrupeds or UGVs.
On the Idiosyncrasies of the Mandarin Chinese Classifier System
Authors: Shijia Liu, Hongyuan Mei, Adina Williams, Ryan Cotterell
Date: 2019-02-26 00:00:00
Proceeding: NAACL 2019 6

While idiosyncrasies of the Chinese classifier system have been a richly studied topic among linguists (Adams and Conklin, 1973; Erbaugh, 1986; Lakoff, 1986), not much work has been done to quantify them with statistical methods. In this paper, we introduce an information-theoretic approach to measuring idiosyncrasy; we examine how much the uncertainty in Mandarin Chinese classifiers can be reduced by knowing semantic information about the nouns that the classifiers modify. Using the empirical distribution of classifiers from the parsed Chinese Gigaword corpus (Graff et al., 2005), we compute the mutual information (in bits) between the distribution over classifiers and distributions over other linguistic quantities. We investigate whether semantic classes of nouns and adjectives differ in how much they reduce uncertainty in classifier choice, and find that it is not fully idiosyncratic; while there are no obvious trends for the majority of semantic classes, shape nouns reduce uncertainty in classifier choice the most.
EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs
Authors: Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao B. Schardl, Charles E. Leiserson
Date: 2019-02-26 00:00:00
Tasks: Dynamic Link Prediction, Edge Classification, General Classification, Graph Representation Learning, Link Prediction, Node Classification, Representation Learning

Graph representation learning resurges as a trending research subject owing to the widespread use of deep learning for Euclidean data, which inspire various creative designs of neural networks in the non-Euclidean domain, particularly graphs. With the success of these graph neural networks (GNN) in the static setting, we approach further practical scenarios where the graph dynamically evolves. Existing approaches typically resort to node embeddings and use a recurrent neural network (RNN, broadly speaking) to regulate the embeddings and learn the temporal dynamics. These methods require the knowledge of a node in the full time span (including both training and testing) and are less applicable to the frequent change of the node set. In some extreme scenarios, the node sets at different time steps may completely differ. To resolve this challenge, we propose EvolveGCN, which adapts the graph convolutional network (GCN) model along the temporal dimension without resorting to node embeddings. The proposed approach captures the dynamism of the graph sequence through using an RNN to evolve the GCN parameters. Two architectures are considered for the parameter evolution. We evaluate the proposed approach on tasks including link prediction, edge classification, and node classification. The experimental results indicate a generally higher performance of EvolveGCN compared with related approaches. The code is available at \url{https://github.com/IBM/EvolveGCN}.
Variational Inference to Measure Model Uncertainty in Deep Neural Networks
Authors: Konstantin Posch, Jan Steinbrener, Jürgen Pilz
Date: 2019-02-26 00:00:00
Tasks: Deep Learning, Variational Inference

We present a novel approach for training deep neural networks in a Bayesian
way. Classical, i.e. non-Bayesian, deep learning has two major drawbacks both
originating from the fact that network parameters are considered to be
deterministic. First, model uncertainty cannot be measured thus limiting the
use of deep learning in many fields of application and second, training of deep
neural networks is often hampered by overfitting. The proposed approach uses
variational inference to approximate the intractable a posteriori distribution
on basis of a normal prior. The variational density is designed in such a way
that the a posteriori uncertainty of the network parameters is represented per
network layer and depending on the estimated parameter expectation values. This
way, only a few additional parameters need to be optimized compared to a
non-Bayesian network. We apply this Bayesian approach to train and test the
LeNet architecture on the MNIST dataset. Compared to classical deep learning,
the test error is reduced by 15%. In addition, the trained model contains
information about the parameter uncertainty in each layer. We show that this
information can be used to calculate credible intervals for the prediction and
to optimize the network architecture for a given training data set.
Attention is not Explanation
Authors: Sarthak Jain, Byron C. Wallace
Date: 2019-02-26 00:00:00
Proceeding: NAACL 2019 6
Tasks: Feature Importance

Attention mechanisms have seen wide adoption in neural NLP models. In addition to improving predictive performance, these are often touted as affording transparency: models equipped with attention provide a distribution over attended-to input units, and this is often presented (at least implicitly) as communicating the relative importance of inputs. However, it is unclear what relationship exists between attention weights and model outputs. In this work, we perform extensive experiments across a variety of NLP tasks that aim to assess the degree to which attention weights provide meaningful `explanations' for predictions. We find that they largely do not. For example, learned attention weights are frequently uncorrelated with gradient-based measures of feature importance, and one can identify very different attention distributions that nonetheless yield equivalent predictions. Our findings show that standard attention modules do not provide meaningful explanations and should not be treated as though they do. Code for all experiments is available at https://github.com/successar/AttentionExplanation.
Unmasking Clever Hans Predictors and Assessing What Machines Really Learn
Authors: Sebastian Lapuschkin, Stephan Wäldchen, Alexander Binder, Grégoire Montavon, Wojciech Samek, Klaus-Robert Müller
Date: 2019-02-26 00:00:00

Current learning machines have successfully solved hard application problems,
reaching high accuracy and displaying seemingly "intelligent" behavior. Here we
apply recent techniques for explaining decisions of state-of-the-art learning
machines and analyze various tasks from computer vision and arcade games. This
showcases a spectrum of problem-solving behaviors ranging from naive and
short-sighted, to well-informed and strategic. We observe that standard
performance evaluation metrics can be oblivious to distinguishing these diverse
problem solving behaviors. Furthermore, we propose our semi-automated Spectral
Relevance Analysis that provides a practically effective way of characterizing
and validating the behavior of nonlinear learning machines. This helps to
assess whether a learned model indeed delivers reliably for the problem that it
was conceived for. Furthermore, our work intends to add a voice of caution to
the ongoing excitement about machine intelligence and pledges to evaluate and
judge some of these recent successes in a more nuanced manner.
A Memoization Framework for Scaling Submodular Optimization to Large Scale Problems
Authors: Rishabh Iyer, Jeff Bilmes
Date: 2019-02-26 00:00:00

We are motivated by large scale submodular optimization problems, where
standard algorithms that treat the submodular functions in the \emph{value
oracle model} do not scale. In this paper, we present a model called the
\emph{precomputational complexity model}, along with a unifying memoization
based framework, which looks at the specific form of the given submodular
function. A key ingredient in this framework is the notion of a
\emph{precomputed statistic}, which is maintained in the course of the
algorithms. We show that we can easily integrate this idea into a large class
of submodular optimization problems including constrained and unconstrained
submodular maximization, minimization, difference of submodular optimization,
optimization with submodular constraints and several other related optimization
problems. Moreover, memoization can be integrated in both discrete and
continuous relaxation flavors of algorithms for these problems. We demonstrate
this idea for several commonly occurring submodular functions, and show how the
precomputational model provides significant speedups compared to the value
oracle model. Finally, we empirically demonstrate this for large scale machine
learning problems of data subset selection and summarization.
Online Learning with Continuous Ranked Probability Score
Authors: Vladimir V'yugin, Vladimir Trunov
Date: 2019-02-26 00:00:00
Tasks: Form, scoring rule

Probabilistic forecasts in the form of probability distributions over future events have become popular in several fields of statistical science. The dissimilarity between a probability forecast and an outcome is measured by a loss function (scoring rule). Popular example of scoring rule for continuous outcomes is the continuous ranked probability score (CRPS). We consider the case where several competing methods produce online predictions in the form of probability distribution functions. In this paper, the problem of combining probabilistic forecasts is considered in the prediction with expert advice framework. We show that CRPS is a mixable loss function and then the time independent upper bound for the regret of the Vovk's aggregating algorithm using CRPS as a loss function can be obtained. We present the results of numerical experiments illustrating the proposed methods.
Near Optimal Algorithms for Hard Submodular Programs with Discounted Cooperative Costs
Authors: Rishabh Iyer, Jeff Bilmes
Date: 2019-02-26 00:00:00

In this paper, we investigate a class of submodular problems which in general
are very hard. These include minimizing a submodular cost function under
combinatorial constraints, which include cuts, matchings, paths, etc.,
optimizing a submodular function under submodular cover and submodular knapsack
constraints, and minimizing a ratio of submodular functions. All these problems
appear in several real world problems but have hardness factors of
$\Omega(\sqrt{n})$ for general submodular cost functions. We show how we can
achieve constant approximation factors when we restrict the cost functions to
low rank sums of concave over modular functions. A wide variety of machine
learning applications are very naturally modeled via this subclass of
submodular functions. Our work therefore provides a tighter connection between
theory and practice by enabling theoretically satisfying guarantees for a rich
class of expressible, natural, and useful submodular cost models. We
empirically demonstrate the utility of our models on real world problems of
cooperative image matching and sensor placement with cooperative costs.
Nonlinear Approximation via Compositions
Authors: Zuowei Shen, Haizhao Yang, Shijun Zhang
Date: 2019-02-26 00:00:00
Tasks: Computational Efficiency

Given a function dictionary $\cal D$ and an approximation budget $N\in\mathbb{N}^+$, nonlinear approximation seeks the linear combination of the best $N$ terms $\{T_n\}_{1\le n\le N}\subseteq{\cal D}$ to approximate a given function $f$ with the minimum approximation error\[\varepsilon_{L,f}:=\min_{\{g_n\}\subseteq{\mathbb{R}},\{T_n\}\subseteq{\cal D}}\|f(x)-\sum_{n=1}^N g_n T_n(x)\|.\]Motivated by recent success of deep learning, we propose dictionaries with functions in a form of compositions, i.e.,\[T(x)=T^{(L)}\circ T^{(L-1)}\circ\cdots\circ T^{(1)}(x)\]for all $T\in\cal D$, and implement $T$ using ReLU feed-forward neural networks (FNNs) with $L$ hidden layers. We further quantify the improvement of the best $N$-term approximation rate in terms of $N$ when $L$ is increased from $1$ to $2$ or $3$ to show the power of compositions. In the case when $L>3$, our analysis shows that increasing $L$ cannot improve the approximation rate in terms of $N$. In particular, for any function $f$ on $[0,1]$, regardless of its smoothness and even the continuity, if $f$ can be approximated using a dictionary when $L=1$ with the best $N$-term approximation rate $\varepsilon_{L,f}={\cal O}(N^{-\eta})$, we show that dictionaries with $L=2$ can improve the best $N$-term approximation rate to $\varepsilon_{L,f}={\cal O}(N^{-2\eta})$. We also show that for H\"older continuous functions of order $\alpha$ on $[0,1]^d$, the application of a dictionary with $L=3$ in nonlinear approximation can achieve an essentially tight best $N$-term approximation rate $\varepsilon_{L,f}={\cal O}(N^{-2\alpha/d})$. Finally, we show that dictionaries consisting of wide FNNs with a few hidden layers are more attractive in terms of computational efficiency than dictionaries with narrow and very deep FNNs for approximating H\"older continuous functions if the number of computer cores is larger than $N$ in parallel computing.
Coloring Big Graphs with AlphaGoZero
Authors: Jiayi Huang, Mostofa Patwary, Gregory Diamos
Date: 2019-02-26 00:00:00
Tasks: Deep Reinforcement Learning, Reinforcement Learning

We show that recent innovations in deep reinforcement learning can effectively color very large graphs -- a well-known NP-hard problem with clear commercial applications. Because the Monte Carlo Tree Search with Upper Confidence Bound algorithm used in AlphaGoZero can improve the performance of a given heuristic, our approach allows deep neural networks trained using high performance computing (HPC) technologies to transform computation into improved heuristics with zero prior knowledge. Key to our approach is the introduction of a novel deep neural network architecture (FastColorNet) that has access to the full graph context and requires $O(V)$ time and space to color a graph with $V$ vertices, which enables scaling to very large graphs that arise in real applications like parallel computing, compilers, numerical solvers, and design automation, among others. As a result, we are able to learn new state of the art heuristics for graph coloring.
A Family of Exact Goodness-of-Fit Tests for High-Dimensional Discrete Distributions
Authors: Feras A. Saad, Cameron E. Freer, Nathanael L. Ackerman, Vikash K. Mansinghka
Date: 2019-02-26 00:00:00

The objective of goodness-of-fit testing is to assess whether a dataset of
observations is likely to have been drawn from a candidate probability
distribution. This paper presents a rank-based family of goodness-of-fit tests
that is specialized to discrete distributions on high-dimensional domains. The
test is readily implemented using a simulation-based, linear-time procedure.
The testing procedure can be customized by the practitioner using knowledge of
the underlying data domain. Unlike most existing test statistics, the proposed
test statistic is distribution-free and its exact (non-asymptotic) sampling
distribution is known in closed form. We establish consistency of the test
against all alternatives by showing that the test statistic is distributed as a
discrete uniform if and only if the samples were drawn from the candidate
distribution. We illustrate its efficacy for assessing the sample quality of
approximate sampling algorithms over combinatorially large spaces with
intractable probabilities, including random partitions in Dirichlet process
mixture models and random lattices in Ising models.
Planning in Hierarchical Reinforcement Learning: Guarantees for Using Local Policies
Authors: Tom Zahavy, Avinatan Hasidim, Haim Kaplan, Yishay Mansour
Date: 2019-02-26 00:00:00
Tasks: Hierarchical Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Traveling Salesman Problem

We consider a settings of hierarchical reinforcement learning, in which the reward is a sum of components. For each component we are given a policy that maximizes it and our goal is to assemble a policy from the individual policies that maximizes the sum of the components. We provide theoretical guarantees for assembling such policies in deterministic MDPs with collectible rewards. Our approach builds on formulating this problem as a traveling salesman problem with discounted reward. We focus on local solutions, i.e., policies that only use information from the current state; thus, they are easy to implement and do not require substantial computational resources. We propose three local stochastic policies and prove that they guarantee better performance than any deterministic local policy in the worst case; experimental results suggest that they also perform better on average.
Quadratic Decomposable Submodular Function Minimization: Theory and Practice (Computation and Analysis of PageRank over Hypergraphs)
Authors: Pan Li, Niao He, Olgica Milenkovic
Date: 2019-02-26 00:00:00
Tasks: hypergraph partitioning

We introduce a new convex optimization problem, termed quadratic decomposable submodular function minimization (QDSFM), which allows to model a number of learning tasks on graphs and hypergraphs. The problem exhibits close ties to decomposable submodular function minimization (DSFM), yet is much more challenging to solve. We approach the problem via a new dual strategy and formulate an objective that can be optimized through a number of double-loop algorithms. The outer-loop uses either random coordinate descent (RCD) or alternative projection (AP) methods, for both of which we prove linear convergence rates. The inner-loop computes projections onto cones generated by base polytopes of the submodular functions, via the modified min-norm-point or Frank-Wolfe algorithm. We also describe two new applications of QDSFM: hypergraph-adapted PageRank and semi-supervised learning. The proposed hypergraph-based PageRank algorithm can be used for local hypergraph partitioning, and comes with provable performance guarantees. For hypergraph-adapted semi-supervised learning, we provide numerical experiments demonstrating the efficiency of our QDSFM solvers and their significant improvements on prediction accuracy when compared to state-of-the-art methods.