pwc-archive/papers-with-abstracts huggingface dataset:
Simple random search provides a competitive approach to reinforcement learning
Authors: Horia Mania, Aurelia Guy, Benjamin Recht
Date: 2018-03-19 00:00:00
Tasks: Computational Efficiency, continuous-control, Continuous Control, MuJoCo, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

A common belief in model-free reinforcement learning is that methods based on
random search in the parameter space of policies exhibit significantly worse
sample complexity than those that explore the space of actions. We dispel such
beliefs by introducing a random search method for training static, linear
policies for continuous control problems, matching state-of-the-art sample
efficiency on the benchmark MuJoCo locomotion tasks. Our method also finds a
nearly optimal controller for a challenging instance of the Linear Quadratic
Regulator, a classical problem in control theory, when the dynamics are not
known. Computationally, our random search algorithm is at least 15 times more
efficient than the fastest competing model-free methods on these benchmarks. We
take advantage of this computational efficiency to evaluate the performance of
our method over hundreds of random seeds and many different hyperparameter
configurations for each benchmark task. Our simulations highlight a high
variability in performance in these benchmark tasks, suggesting that commonly
used estimations of sample efficiency do not adequately evaluate the
performance of RL algorithms.
Optimal link prediction with matrix logistic regression
Authors: Nicolai Baldin, Quentin Berthet
Date: 2018-03-19 00:00:00
Tasks: Link Prediction, Prediction, regression

We consider the problem of link prediction, based on partial observation of a
large network, and on side information associated to its vertices. The
generative model is formulated as a matrix logistic regression. The performance
of the model is analysed in a high-dimensional regime under a structural
assumption. The minimax rate for the Frobenius-norm risk is established and a
combinatorial estimator based on the penalised maximum likelihood approach is
shown to achieve it. Furthermore, it is shown that this rate cannot be attained
by any (randomised) algorithm computable in polynomial time under a
computational complexity assumption.
Learning Steerable Filters for Rotation Equivariant CNNs
Authors: Maurice Weiler, Fred A. Hamprecht, Martin Storath
Date: 2017-11-20 00:00:00
Proceeding: CVPR 2018 6
Tasks: Breast Tumour Classification, Colorectal Gland Segmentation:, Multi-tissue Nucleus Segmentation, Rotated MNIST

In many machine learning tasks it is desirable that a model's prediction
transforms in an equivariant way under transformations of its input.
Convolutional neural networks (CNNs) implement translational equivariance by
construction; for other transformations, however, they are compelled to learn
the proper mapping. In this work, we develop Steerable Filter CNNs (SFCNNs)
which achieve joint equivariance under translations and rotations by design.
The proposed architecture employs steerable filters to efficiently compute
orientation dependent responses for many orientations without suffering
interpolation artifacts from filter rotation. We utilize group convolutions
which guarantee an equivariant mapping. In addition, we generalize He's weight
initialization scheme to filters which are defined as a linear combination of a
system of atomic filters. Numerical experiments show a substantial enhancement
of the sample complexity with a growing number of sampled filter orientations
and confirm that the network generalizes learned patterns over orientations.
The proposed approach achieves state-of-the-art on the rotated MNIST benchmark
and on the ISBI 2012 2D EM segmentation challenge.
Factorised spatial representation learning: application in semi-supervised myocardial segmentation
Authors: Agisilaos Chartsias, Thomas Joyce, Giorgos Papanastasiou, Scott Semple, Michelle Williams, David Newby, Rohan Dharmakumar, Sotirios A. Tsaftaris
Date: 2018-03-19 00:00:00
Tasks: Medical Image Segmentation, Myocardium Segmentation, Representation Learning

The success and generalisation of deep learning algorithms heavily depend on
learning good feature representations. In medical imaging this entails
representing anatomical information, as well as properties related to the
specific imaging setting. Anatomical information is required to perform further
analysis, whereas imaging information is key to disentangle scanner variability
and potential artefacts. The ability to factorise these would allow for
training algorithms only on the relevant information according to the task. To
date, such factorisation has not been attempted. In this paper, we propose a
methodology of latent space factorisation relying on the cycle-consistency
principle. As an example application, we consider cardiac MR segmentation,
where we separate information related to the myocardium from other features
related to imaging and surrounding substructures. We demonstrate the proposed
method's utility in a semi-supervised setting: we use very few labelled images
together with many unlabelled images to train a myocardium segmentation neural
network. Specifically, we achieve comparable performance to fully supervised
networks using a fraction of labelled images in experiments on ACDC and a
dataset from Edinburgh Imaging Facility QMRI. Code will be made available at
https://github.com/agis85/spatial_factorisation.
Recovery of Noisy Points on Band-limited Surfaces: Kernel Methods Re-explained
Authors: Sunrita Poddar, Mathews Jacob
Date: 2018-01-03 00:00:00

We introduce a continuous domain framework for the recovery of points on a
surface in high dimensional space, represented as the zero-level set of a
bandlimited function. We show that the exponential maps of the points on the
surface satisfy annihilation relations, implying that they lie in a finite
dimensional subspace. The subspace properties are used to derive sampling
conditions, which will guarantee the perfect recovery of the surface from
finite number of points. We rely on nuclear norm minimization to exploit the
low-rank structure of the maps to recover the points from noisy measurements.
Since the direct estimation of the surface is computationally prohibitive in
very high dimensions, we propose an iterative reweighted algorithm using the
"kernel trick". The iterative algorithm reveals deep links to Laplacian based
algorithms widely used in graph signal processing; the theory and the sampling
conditions can serve as a basis for discrete-continuous domain processing of
signals on a graph.
Estimating the intrinsic dimension of datasets by a minimal neighborhood information
Authors: Elena Facco, Maria d'Errico, Alex Rodriguez, Alessandro Laio
Date: 2018-03-19 00:00:00

Analyzing large volumes of high-dimensional data is an issue of fundamental
importance in data science, molecular simulations and beyond. Several
approaches work on the assumption that the important content of a dataset
belongs to a manifold whose Intrinsic Dimension (ID) is much lower than the
crude large number of coordinates. Such manifold is generally twisted and
curved, in addition points on it will be non-uniformly distributed: two factors
that make the identification of the ID and its exploitation really hard. Here
we propose a new ID estimator using only the distance of the first and the
second nearest neighbor of each point in the sample. This extreme minimality
enables us to reduce the effects of curvature, of density variation, and the
resulting computational cost. The ID estimator is theoretically exact in
uniformly distributed datasets, and provides consistent measures in general.
When used in combination with block analysis, it allows discriminating the
relevant dimensions as a function of the block size. This allows estimating the
ID even when the data lie on a manifold perturbed by a high-dimensional noise,
a situation often encountered in real world data sets. We demonstrate the
usefulness of the approach on molecular simulations and image analysis.
Numerical Integration on Graphs: where to sample and how to weigh
Authors: George C. Linderman, Stefan Steinerberger
Date: 2018-03-19 00:00:00
Tasks: Numerical Integration

Let $G=(V,E,w)$ be a finite, connected graph with weighted edges. We are
interested in the problem of finding a subset $W \subset V$ of vertices and
weights $a_w$ such that $$ \frac{1}{|V|}\sum_{v \in V}^{}{f(v)} \sim \sum_{w
\in W}{a_w f(w)}$$ for functions $f:V \rightarrow \mathbb{R}$ that are `smooth'
with respect to the geometry of the graph. The main application are problems
where $f$ is known to somehow depend on the underlying graph but is expensive
to evaluate on even a single vertex. We prove an inequality showing that the
integration problem can be rewritten as a geometric problem (`the optimal
packing of heat balls'). We discuss how one would construct approximate
solutions of the heat ball packing problem; numerical examples demonstrate the
efficiency of the method.
Pinball Loss Minimization for One-bit Compressive Sensing: Convex Models and Algorithms
Authors: Xiaolin Huang, Lei Shi, Ming Yan, Johan A. K. Suykens
Date: 2015-05-14 00:00:00
Tasks: Compressive Sensing, Quantization

The one-bit quantization is implemented by one single comparator that
operates at low power and a high rate. Hence one-bit compressive sensing
(1bit-CS) becomes attractive in signal processing. When measurements are
corrupted by noise during signal acquisition and transmission, 1bit-CS is
usually modeled as minimizing a loss function with a sparsity constraint. The
one-sided $\ell_1$ loss and the linear loss are two popular loss functions for
1bit-CS. To improve the decoding performance on noisy data, we consider the
pinball loss, which provides a bridge between the one-sided $\ell_1$ loss and
the linear loss. Using the pinball loss, two convex models, an elastic-net
pinball model and its modification with the $\ell_1$-norm constraint, are
proposed. To efficiently solve them, the corresponding dual coordinate ascent
algorithms are designed and their convergence is proved. The numerical
experiments confirm the effectiveness of the proposed algorithms and the
performance of the pinball loss minimization for 1bit-CS.
Technical Report: When Does Machine Learning FAIL? Generalized Transferability for Evasion and Poisoning Attacks
Authors: Octavian Suciu, Radu Mărginean, Yiğitcan Kaya, Hal Daumé III, Tudor Dumitraş
Date: 2018-03-19 00:00:00
Tasks: BIG-bench Machine Learning

Recent results suggest that attacks against supervised machine learning
systems are quite effective, while defenses are easily bypassed by new attacks.
However, the specifications for machine learning systems currently lack precise
adversary definitions, and the existing attacks make diverse, potentially
unrealistic assumptions about the strength of the adversary who launches them.
We propose the FAIL attacker model, which describes the adversary's knowledge
and control along four dimensions. Our model allows us to consider a wide range
of weaker adversaries who have limited control and incomplete knowledge of the
features, learning algorithms and training instances utilized. To evaluate the
utility of the FAIL model, we consider the problem of conducting targeted
poisoning attacks in a realistic setting: the crafted poison samples must have
clean labels, must be individually and collectively inconspicuous, and must
exhibit a generalized form of transferability, defined by the FAIL model. By
taking these constraints into account, we design StingRay, a targeted poisoning
attack that is practical against 4 machine learning applications, which use 3
different learning algorithms, and can bypass 2 existing defenses. Conversely,
we show that a prior evasion attack is less effective under generalized
transferability. Such attack evaluations, under the FAIL adversary model, may
also suggest promising directions for future defenses.
What Doubling Tricks Can and Can't Do for Multi-Armed Bandits
Authors: Lilian Besson, Emilie Kaufmann
Date: 2018-03-19 00:00:00
Tasks: Multi-Armed Bandits, Reinforcement Learning

An online reinforcement learning algorithm is anytime if it does not need to
know in advance the horizon T of the experiment. A well-known technique to
obtain an anytime algorithm from any non-anytime algorithm is the "Doubling
Trick". In the context of adversarial or stochastic multi-armed bandits, the
performance of an algorithm is measured by its regret, and we study two
families of sequences of growing horizons (geometric and exponential) to
generalize previously known results that certain doubling tricks can be used to
conserve certain regret bounds. In a broad setting, we prove that a geometric
doubling trick can be used to conserve (minimax) bounds in $R\_T = O(\sqrt{T})$
but cannot conserve (distribution-dependent) bounds in $R\_T = O(\log T)$. We
give insights as to why exponential doubling tricks may be better, as they
conserve bounds in $R\_T = O(\log T)$, and are close to conserving bounds in
$R\_T = O(\sqrt{T})$.
Featureless: Bypassing feature extraction in action categorization
Authors: Silvia L. Pintea, Pascal S. Mettes, Jan C. van Gemert, Arnold W. M. Smeulders
Date: 2018-03-19 00:00:00
Tasks: Action Recognition, Temporal Action Localization

This method introduces an efficient manner of learning action categories
without the need of feature estimation. The approach starts from low-level
values, in a similar style to the successful CNN methods. However, rather than
extracting general image features, we learn to predict specific video
representations from raw video data. The benefit of such an approach is that at
the same computational expense it can predict 2 D video representations as well
as 3 D ones, based on motion. The proposed model relies on discriminative
Waldboost, which we enhance to a multiclass formulation for the purpose of
learning video representations. The suitability of the proposed approach as
well as its time efficiency are tested on the UCF11 action recognition dataset.
Fast and robust curve skeletonization for real-world elongated objects
Authors: Amy Tabb, Henry Medeiros
Date: 2017-02-24 00:00:00
Tasks: Decision Making

We consider the problem of extracting curve skeletons of three-dimensional,
elongated objects given a noisy surface, which has applications in agricultural
contexts such as extracting the branching structure of plants. We describe an
efficient and robust method based on breadth-first search that can determine
curve skeletons in these contexts. Our approach is capable of automatically
detecting junction points as well as spurious segments and loops. All of that
is accomplished with only one user-adjustable parameter. The run time of our
method ranges from hundreds of milliseconds to less than four seconds on large,
challenging datasets, which makes it appropriate for situations where real-time
decision making is needed. Experiments on synthetic models as well as on data
from real world objects, some of which were collected in challenging field
conditions, show that our approach compares favorably to classical thinning
algorithms as well as to recent contributions to the field.
Asymmetric kernel in Gaussian Processes for learning target variance
Authors: Silvia L. Pintea, Jan C. van Gemert, Arnold W. M. Smeulders
Date: 2018-03-19 00:00:00
Tasks: Gaussian Processes, Metric Learning, regression

This work incorporates the multi-modality of the data distribution into a
Gaussian Process regression model. We approach the problem from a
discriminative perspective by learning, jointly over the training data, the
target space variance in the neighborhood of a certain sample through metric
learning. We start by using data centers rather than all training samples.
Subsequently, each center selects an individualized kernel metric. This enables
each center to adjust the kernel space in its vicinity in correspondence with
the topology of the targets --- a multi-modal approach. We additionally add
descriptiveness by allowing each center to learn a precision matrix. We
demonstrate empirically the reliability of the model.
Inference on Auctions with Weak Assumptions on Information
Authors: Vasilis Syrgkanis, Elie Tamer, Juba Ziani
Date: 2017-10-10 00:00:00
Tasks: counterfactual, Econometrics

Given a sample of bids from independent auctions, this paper examines the
question of inference on auction fundamentals (e.g. valuation distributions,
welfare measures) under weak assumptions on information structure. The question
is important as it allows us to learn about the valuation distribution in a
robust way, i.e., without assuming that a particular information structure
holds across observations. We leverage the recent contributions of
\cite{Bergemann2013} in the robust mechanism design literature that exploit the
link between Bayesian Correlated Equilibria and Bayesian Nash Equilibria in
incomplete information games to construct an econometrics framework for
learning about auction fundamentals using observed data on bids. We showcase
our construction of identified sets in private value and common value auctions.
Our approach for constructing these sets inherits the computational simplicity
of solving for correlated equilibria: checking whether a particular valuation
distribution belongs to the identified set is as simple as determining whether
a {\it linear} program is feasible. A similar linear program can be used to
construct the identified set on various welfare measures and counterfactual
objects. For inference and to summarize statistical uncertainty, we propose
novel finite sample methods using tail inequalities that are used to construct
confidence regions on sets. We also highlight methods based on Bayesian
bootstrap and subsampling. A set of Monte Carlo experiments show adequate
finite sample properties of our inference procedures. We illustrate our methods
using data from OCS auctions.
An attentive neural architecture for joint segmentation and parsing and its application to real estate ads
Authors: Giannis Bekoulis, Johannes Deleu, Thomas Demeester, Chris Develder
Date: 2017-09-27 00:00:00
Tasks: Dependency Parsing

In processing human produced text using natural language processing (NLP)
techniques, two fundamental subtasks that arise are (i) segmentation of the
plain text into meaningful subunits (e.g., entities), and (ii) dependency
parsing, to establish relations between subunits. In this paper, we develop a
relatively simple and effective neural joint model that performs both
segmentation and dependency parsing together, instead of one after the other as
in most state-of-the-art works. We will focus in particular on the real estate
ad setting, aiming to convert an ad to a structured description, which we name
property tree, comprising the tasks of (1) identifying important entities of a
property (e.g., rooms) from classifieds and (2) structuring them into a tree
format. In this work, we propose a new joint model that is able to tackle the
two tasks simultaneously and construct the property tree by (i) avoiding the
error propagation that would arise from the subtasks one after the other in a
pipelined fashion, and (ii) exploiting the interactions between the subtasks.
For this purpose, we perform an extensive comparative study of the pipeline
methods and the new proposed joint model, reporting an improvement of over
three percentage points in the overall edge F1 score of the property tree.
Also, we propose attention methods, to encourage our model to focus on salient
tokens during the construction of the property tree. Thus we experimentally
demonstrate the usefulness of attentive neural architectures for the proposed
joint model, showcasing a further improvement of two percentage points in edge
F1 score for our application.
Universal features of price formation in financial markets: perspectives from Deep Learning
Authors: Justin Sirignano, Rama Cont
Date: 2018-03-19 00:00:00
Tasks: Time Series Analysis

Using a large-scale Deep Learning approach applied to a high-frequency
database containing billions of electronic market quotes and transactions for
US equities, we uncover nonparametric evidence for the existence of a universal
and stationary price formation mechanism relating the dynamics of supply and
demand for a stock, as revealed through the order book, to subsequent
variations in its market price. We assess the model by testing its
out-of-sample predictions for the direction of price moves given the history of
price and order flow, across a wide range of stocks and time periods. The
universal price formation model is shown to exhibit a remarkably stable
out-of-sample prediction accuracy across time, for a wide range of stocks from
different sectors. Interestingly, these results also hold for stocks which are
not part of the training sample, showing that the relations captured by the
model are universal and not asset-specific.
  The universal model --- trained on data from all stocks --- outperforms, in
terms of out-of-sample prediction accuracy, asset-specific linear and nonlinear
models trained on time series of any given stock, showing that the universal
nature of price formation weighs in favour of pooling together financial data
from various stocks, rather than designing asset- or sector-specific models as
commonly done. Standard data normalizations based on volatility, price level or
average spread, or partitioning the training data into sectors or categories
such as large/small tick stocks, do not improve training results. On the other
hand, inclusion of price and order flow history over many past observations is
shown to improve forecasting performance, showing evidence of path-dependence
in price dynamics.
A DIRT-T Approach to Unsupervised Domain Adaptation
Authors: Rui Shu, Hung H. Bui, Hirokazu Narui, Stefano Ermon
Date: 2018-02-23 00:00:00
Proceeding: ICLR 2018 1
Tasks: Domain Adaptation, Unsupervised Domain Adaptation

Domain adaptation refers to the problem of leveraging labeled data in a
source domain to learn an accurate model in a target domain where labels are
scarce or unavailable. A recent approach for finding a common representation of
the two domains is via domain adversarial training (Ganin & Lempitsky, 2015),
which attempts to induce a feature extractor that matches the source and target
feature distributions in some feature space. However, domain adversarial
training faces two critical limitations: 1) if the feature extraction function
has high-capacity, then feature distribution matching is a weak constraint, 2)
in non-conservative domain adaptation (where no single classifier can perform
well in both the source and target domains), training the model to do well on
the source domain hurts performance on the target domain. In this paper, we
address these issues through the lens of the cluster assumption, i.e., decision
boundaries should not cross high-density data regions. We propose two novel and
related models: 1) the Virtual Adversarial Domain Adaptation (VADA) model,
which combines domain adversarial training with a penalty term that punishes
the violation the cluster assumption; 2) the Decision-boundary Iterative
Refinement Training with a Teacher (DIRT-T) model, which takes the VADA model
as initialization and employs natural gradient steps to further minimize the
cluster assumption violation. Extensive empirical results demonstrate that the
combination of these two models significantly improve the state-of-the-art
performance on the digit, traffic sign, and Wi-Fi recognition domain adaptation
benchmarks.