pwc-archive/papers-with-abstracts huggingface dataset:
Precise Runtime Analysis for Plateau Functions
Authors: Denis Antipov, Benjamin Doerr
Date: 2018-06-04 00:00:00
Tasks: Evolutionary Algorithms

To gain a better theoretical understanding of how evolutionary algorithms (EAs) cope with plateaus of constant fitness, we propose the $n$-dimensional Plateau$_k$ function as natural benchmark and analyze how different variants of the $(1 + 1)$ EA optimize it. The Plateau$_k$ function has a plateau of second-best fitness in a ball of radius $k$ around the optimum. As evolutionary algorithm, we regard the $(1 + 1)$ EA using an arbitrary unbiased mutation operator. Denoting by $\alpha$ the random number of bits flipped in an application of this operator and assuming that $\Pr[\alpha = 1]$ has at least some small sub-constant value, we show the surprising result that for all constant $k \ge 2$, the runtime $T$ follows a distribution close to the geometric one with success probability equal to the probability to flip between $1$ and $k$ bits divided by the size of the plateau. Consequently, the expected runtime is the inverse of this number, and thus only depends on the probability to flip between $1$ and $k$ bits, but not on other characteristics of the mutation operator. Our result also implies that the optimal mutation rate for standard bit mutation here is approximately $k/(en)$. Our main analysis tool is a combined analysis of the Markov chains on the search point space and on the Hamming level space, an approach that promises to be useful also for other plateau problems.
Closed Form Word Embedding Alignment
Authors: Sunipa Dev, Safia Hassan, Jeff M. Phillips
Date: 2018-06-04 00:00:00
Tasks: Form, Word Embeddings

We develop a family of techniques to align word embeddings which are derived from different source datasets or created using different mechanisms (e.g., GloVe or word2vec). Our methods are simple and have a closed form to optimally rotate, translate, and scale to minimize root mean squared errors or maximize the average cosine similarity between two embeddings of the same vocabulary into the same dimensional space. Our methods extend approaches known as Absolute Orientation, which are popular for aligning objects in three-dimensions, and generalize an approach by Smith etal (ICLR 2017). We prove new results for optimal scaling and for maximizing cosine similarity. Then we demonstrate how to evaluate the similarity of embeddings from different sources or mechanisms, and that certain properties like synonyms and analogies are preserved across the embeddings and can be enhanced by simply aligning and averaging ensembles of embeddings.
Past Visions of Artificial Futures: One Hundred and Fifty Years under the Spectre of Evolving Machines
Authors: Tim Taylor, Alan Dorin
Date: 2018-06-04 00:00:00
Tasks: Artificial Life

The influence of Artificial Intelligence (AI) and Artificial Life (ALife)
technologies upon society, and their potential to fundamentally shape the
future evolution of humankind, are topics very much at the forefront of current
scientific, governmental and public debate. While these might seem like very
modern concerns, they have a long history that is often disregarded in
contemporary discourse. Insofar as current debates do acknowledge the history
of these ideas, they rarely look back further than the origin of the modern
digital computer age in the 1940s-50s. In this paper we explore the earlier
history of these concepts. We focus in particular on the idea of
self-reproducing and evolving machines, and potential implications for our own
species. We show that discussion of these topics arose in the 1860s, within a
decade of the publication of Darwin's The Origin of Species, and attracted
increasing interest from scientists, novelists and the general public in the
early 1900s. After introducing the relevant work from this period, we
categorise the various visions presented by these authors of the future
implications of evolving machines for humanity. We suggest that current debates
on the co-evolution of society and technology can be enriched by a proper
appreciation of the long history of the ideas involved.
Cube Padding for Weakly-Supervised Saliency Prediction in 360° Videos
Authors: Hsien-Tzu Cheng, Chun-Hung Chao, Jin-Dong Dong, Hao-Kai Wen, Tyng-Luh Liu, Min Sun
Date: 2018-06-04 00:00:00
Proceeding: CVPR 2018
Tasks: Saliency Prediction

Automatic saliency prediction in 360{\deg} videos is critical for viewpoint
guidance applications (e.g., Facebook 360 Guide). We propose a spatial-temporal
network which is (1) weakly-supervised trained and (2) tailor-made for
360{\deg} viewing sphere. Note that most existing methods are less scalable
since they rely on annotated saliency map for training. Most importantly, they
convert 360{\deg} sphere to 2D images (e.g., a single equirectangular image or
multiple separate Normal Field-of-View (NFoV) images) which introduces
distortion and image boundaries. In contrast, we propose a simple and effective
Cube Padding (CP) technique as follows. Firstly, we render the 360{\deg} view
on six faces of a cube using perspective projection. Thus, it introduces very
little distortion. Then, we concatenate all six faces while utilizing the
connectivity between faces on the cube for image padding (i.e., Cube Padding)
in convolution, pooling, convolutional LSTM layers. In this way, CP introduces
no image boundary while being applicable to almost all Convolutional Neural
Network (CNN) structures. To evaluate our method, we propose Wild-360, a new
360{\deg} video saliency dataset, containing challenging videos with saliency
heatmap annotations. In experiments, our method outperforms baseline methods in
both speed and quality.
Data-driven Localization and Estimation of Disturbance in the Interconnected Power System
Authors: Hyang-Won Lee, Jianan Zhang, Eytan Modiano
Date: 2018-06-04 00:00:00
Tasks: regression

Identifying the location of a disturbance and its magnitude is an important
component for stable operation of power systems. We study the problem of
localizing and estimating a disturbance in the interconnected power system. We
take a model-free approach to this problem by using frequency data from
generators. Specifically, we develop a logistic regression based method for
localization and a linear regression based method for estimation of the
magnitude of disturbance. Our model-free approach does not require the
knowledge of system parameters such as inertia constants and topology, and is
shown to achieve highly accurate localization and estimation performance even
in the presence of measurement noise and missing data.
Universal Statistics of Fisher Information in Deep Neural Networks: Mean Field Approach
Authors: Ryo Karakida, Shotaro Akaho, Shun-ichi Amari
Date: 2018-06-04 00:00:00

The Fisher information matrix (FIM) is a fundamental quantity to represent the characteristics of a stochastic model, including deep neural networks (DNNs). The present study reveals novel statistics of FIM that are universal among a wide class of DNNs. To this end, we use random weights and large width limits, which enables us to utilize mean field theories. We investigate the asymptotic statistics of the FIM's eigenvalues and reveal that most of them are close to zero while the maximum eigenvalue takes a huge value. Because the landscape of the parameter space is defined by the FIM, it is locally flat in most dimensions, but strongly distorted in others. Moreover, we demonstrate the potential usage of the derived statistics in learning strategies. First, small eigenvalues that induce flatness can be connected to a norm-based capacity measure of generalization ability. Second, the maximum eigenvalue that induces the distortion enables us to quantitatively estimate an appropriately sized learning rate for gradient methods to converge.
Finite Sample Analysis of Two-Timescale Stochastic Approximation with Applications to Reinforcement Learning
Authors: Gal Dalal, Balazs Szorenyi, Gugan Thoppe, Shie Mannor
Date: 2017-03-15 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Two-timescale Stochastic Approximation (SA) algorithms are widely used in
Reinforcement Learning (RL). Their iterates have two parts that are updated
using distinct stepsizes. In this work, we develop a novel recipe for their
finite sample analysis. Using this, we provide a concentration bound, which is
the first such result for a two-timescale SA. The type of bound we obtain is
known as `lock-in probability'. We also introduce a new projection scheme, in
which the time between successive projections increases exponentially. This
scheme allows one to elegantly transform a lock-in probability into a
convergence rate result for projected two-timescale SA. From this latter
result, we then extract key insights on stepsize selection. As an application,
we finally obtain convergence rates for the projected two-timescale RL
algorithms GTD(0), GTD2, and TDC.
Y-Net: Joint Segmentation and Classification for Diagnosis of Breast Biopsy Images
Authors: Sachin Mehta, Ezgi Mercan, Jamen Bartlett, Donald Weave, Joann G. Elmore, Linda Shapiro
Date: 2018-06-04 00:00:00
Tasks: Descriptive, Diagnostic, General Classification, Medical Image Segmentation, Segmentation

In this paper, we introduce a conceptually simple network for generating
discriminative tissue-level segmentation masks for the purpose of breast cancer
diagnosis. Our method efficiently segments different types of tissues in breast
biopsy images while simultaneously predicting a discriminative map for
identifying important areas in an image. Our network, Y-Net, extends and
generalizes U-Net by adding a parallel branch for discriminative map generation
and by supporting convolutional block modularity, which allows the user to
adjust network efficiency without altering the network topology. Y-Net delivers
state-of-the-art segmentation accuracy while learning 6.6x fewer parameters
than its closest competitors. The addition of descriptive power from Y-Net's
discriminative segmentation masks improve diagnostic classification accuracy by
7% over state-of-the-art methods for diagnostic classification. Source code is
available at: https://sacmehta.github.io/YNet.
End to End Brain Fiber Orientation Estimation using Deep Learning
Authors: Nandakishore Puttashamachar, Ulas Bagci
Date: 2018-06-04 00:00:00
Tasks: Deep Learning, GPU

In this work, we explore the various Brain Neuron tracking techniques, which
is one of the most significant applications of Diffusion Tensor Imaging.
Tractography provides us with a non-invasive method to analyze underlying
tissue micro-structure. Understanding the structure and organization of the
tissues facilitates us with a diagnosis method to identify any aberrations and
provide acute information on the occurrences of brain ischemia or stroke, the
mutation of neurological diseases such as Alzheimer, multiple sclerosis and so
on. Time if of essence and accurate localization of the aberrations can help
save or change a diseased life. Following up with the limitations introduced by
the current Tractography techniques such as computational complexity,
reconstruction errors during tensor estimation and standardization, we aim to
elucidate these limitations through our research findings. We introduce an end
to end Deep Learning framework which can accurately estimate the most probable
likelihood orientation at each voxel along a neuronal pathway. We use
Probabilistic Tractography as our baseline model to obtain the training data
and which also serve as a Tractography Gold Standard for our evaluations.
Through experiments we show that our Deep Network can do a significant
improvement over current Tractography implementations by reducing the run-time
complexity to a significant new level. Our architecture also allows for
variable sized input DWI signals eliminating the need to worry about memory
issues as seen with the traditional techniques. The advantage of this
architecture is that it is perfectly desirable to be processed on a cloud setup
and utilize the existing multi GPU frameworks to perform whole brain
Tractography in minutes rather than hours. We evaluate our network with Gold
Standard and benchmark its performance across several parameters.
Infrared Safety of a Neural-Net Top Tagging Algorithm
Authors: Suyong Choi, Seung J. Lee, Maxim Perelstein
Date: 2018-06-04 00:00:00
Tasks: General Classification, Jet Tagging

Neural network-based algorithms provide a promising approach to jet
classification problems, such as boosted top jet tagging. To date, NN-based top
taggers demonstrated excellent performance in Monte Carlo studies. In this
paper, we construct a top-jet tagger based on a Convolutional Neural Network
(CNN), and apply it to parton-level boosted top samples, with and without an
additional gluon in the final state. We show that the jet observable defined by
the CNN obeys the canonical definition of infrared safety: it is unaffected by
the presence of the extra gluon, as long as it is soft or collinear with one of
the quarks. Our results indicate that the CNN tagger is robust with respect to
possible mis-modeling of soft and collinear final-state radiation by Monte
Carlo generators.
Learning a Code: Machine Learning for Approximate Non-Linear Coded Computation
Authors: Jack Kosaian, K. V. Rashmi, Shivaram Venkataraman
Date: 2018-06-04 00:00:00
Tasks: BIG-bench Machine Learning

Machine learning algorithms are typically run on large scale, distributed
compute infrastructure that routinely face a number of unavailabilities such as
failures and temporary slowdowns. Adding redundant computations using
coding-theoretic tools called "codes" is an emerging technique to alleviate the
adverse effects of such unavailabilities. A code consists of an encoding
function that proactively introduces redundant computation and a decoding
function that reconstructs unavailable outputs using the available ones. Past
work focuses on using codes to provide resilience for linear computations and
specific iterative optimization algorithms. However, computations performed for
a variety of applications including inference on state-of-the-art machine
learning algorithms, such as neural networks, typically fall outside this
realm. In this paper, we propose taking a learning-based approach to designing
codes that can handle non-linear computations. We present carefully designed
neural network architectures and a training methodology for learning encoding
and decoding functions that produce approximate reconstructions of unavailable
computation results. We present extensive experimental results demonstrating
the effectiveness of the proposed approach: we show that the our learned codes
can accurately reconstruct $64 - 98\%$ of the unavailable predictions from
neural-network based image classifiers on the MNIST, Fashion-MNIST, and
CIFAR-10 datasets. To the best of our knowledge, this work proposes the first
learning-based approach for designing codes, and also presents the first
coding-theoretic solution that can provide resilience for any non-linear
(differentiable) computation. Our results show that learning can be an
effective technique for designing codes, and that learned codes are a highly
promising approach for bringing the benefits of coding to non-linear
computations.
Agreement-based Learning
Authors: Emmanouil Antonios Platanios
Date: 2018-06-04 00:00:00
Tasks: BIG-bench Machine Learning, Model Selection

Model selection is a problem that has occupied machine learning researchers
for a long time. Recently, its importance has become evident through
applications in deep learning. We propose an agreement-based learning framework
that prevents many of the pitfalls associated with model selection. It relies
on coupling the training of multiple models by encouraging them to agree on
their predictions while training. In contrast with other model selection and
combination approaches used in machine learning, the proposed framework is
inspired by human learning. We also propose a learning algorithm defined within
this framework which manages to significantly outperform alternatives in
practice, and whose performance improves further with the availability of
unlabeled data. Finally, we describe a number of potential directions for
developing more flexible agreement-based learning algorithms.
ML-Leaks: Model and Data Independent Membership Inference Attacks and Defenses on Machine Learning Models
Authors: Ahmed Salem, Yang Zhang, Mathias Humbert, Pascal Berrang, Mario Fritz, Michael Backes
Date: 2018-06-04 00:00:00
Tasks: BIG-bench Machine Learning, Inference Attack, Membership Inference Attack

Machine learning (ML) has become a core component of many real-world
applications and training data is a key factor that drives current progress.
This huge success has led Internet companies to deploy machine learning as a
service (MLaaS). Recently, the first membership inference attack has shown that
extraction of information on the training set is possible in such MLaaS
settings, which has severe security and privacy implications.
  However, the early demonstrations of the feasibility of such attacks have
many assumptions on the adversary, such as using multiple so-called shadow
models, knowledge of the target model structure, and having a dataset from the
same distribution as the target model's training data. We relax all these key
assumptions, thereby showing that such attacks are very broadly applicable at
low cost and thereby pose a more severe risk than previously thought. We
present the most comprehensive study so far on this emerging and developing
threat using eight diverse datasets which show the viability of the proposed
attacks across domains.
  In addition, we propose the first effective defense mechanisms against such
broader class of membership inference attacks that maintain a high level of
utility of the ML model.
Marginal Singularity, and the Benefits of Labels in Covariate-Shift
Authors: Samory Kpotufe, Guillaume Martinet
Date: 2018-03-05 00:00:00
Tasks: General Classification

We present new minimax results that concisely capture the relative benefits of source and target labeled data, under covariate-shift. Namely, we show that the benefits of target labels are controlled by a transfer-exponent $\gamma$ that encodes how singular Q is locally w.r.t. P, and interestingly allows situations where transfer did not seem possible under previous insights. In fact, our new minimax analysis - in terms of $\gamma$ - reveals a continuum of regimes ranging from situations where target labels have little benefit, to regimes where target labels dramatically improve classification. We then show that a recently proposed semi-supervised procedure can be extended to adapt to unknown $\gamma$, and therefore requests labels only when beneficial, while achieving minimax transfer rates.
Graph networks as learnable physics engines for inference and control
Authors: Alvaro Sanchez-Gonzalez, Nicolas Heess, Jost Tobias Springenberg, Josh Merel, Martin Riedmiller, Raia Hadsell, Peter Battaglia
Date: 2018-06-04 00:00:00
Proceeding: ICML 2018 7
Tasks: Inductive Bias, Weather Forecasting

Understanding and interacting with everyday physical scenes requires rich
knowledge about the structure of the world, represented either implicitly in a
value or policy function, or explicitly in a transition model. Here we
introduce a new class of learnable models--based on graph networks--which
implement an inductive bias for object- and relation-centric representations of
complex, dynamical systems. Our results show that as a forward model, our
approach supports accurate predictions from real and simulated data, and
surprisingly strong and efficient generalization, across eight distinct
physical systems which we varied parametrically and structurally. We also found
that our inference model can perform system identification. Our models are also
differentiable, and support online planning via gradient-based trajectory
optimization, as well as offline policy optimization. Our framework offers new
opportunities for harnessing and exploiting rich knowledge about the world, and
takes a key step toward building machines with more human-like representations
of the world.
Diffeomorphic Learning
Authors: Laurent Younes
Date: 2018-06-04 00:00:00

We introduce in this paper a learning paradigm in which the training data is transformed by a diffeomorphic transformation before prediction. The learning algorithm minimizes a cost function evaluating the prediction error on the training set penalized by the distance between the diffeomorphism and the identity. The approach borrows ideas from shape analysis where diffeomorphisms are estimated for shape and image alignment, and brings them in a previously unexplored setting, estimating, in particular diffeomorphisms in much larger dimensions. After introducing the concept and describing a learning algorithm, we present diverse applications, mostly with synthetic examples, demonstrating the potential of the approach, as well as some insight on how it can be improved.
Deep Graphs
Authors: Emmanouil Antonios Platanios, Alex Smola
Date: 2018-06-04 00:00:00
Tasks: Ingenuity, regression

We propose an algorithm for deep learning on networks and graphs. It relies
on the notion that many graph algorithms, such as PageRank, Weisfeiler-Lehman,
or Message Passing can be expressed as iterative vertex updates. Unlike
previous methods which rely on the ingenuity of the designer, Deep Graphs are
adaptive to the estimation problem. Training and deployment are both efficient,
since the cost is $O(|E| + |V|)$, where $E$ and $V$ are the sets of edges and
vertices respectively. In short, we learn the recurrent update functions rather
than positing their specific functional form. This yields an algorithm that
achieves excellent accuracy on both graph labeling and regression tasks.
Image reconstruction through metamorphosis
Authors: Gris Barbara, Chen Chong, Öktem Ozan
Date: 2018-06-04 00:00:00
Tasks: Image Reconstruction, Image Registration

This article adapts the framework of metamorphosis to solve inverse problems
in imaging that includes joint reconstruction and image registration. The
deformations in question have two components, one that is a geometric
deformation moving intensities and the other a deformation of intensity values
itself, which, e.g., allows for appearance of a new structure. The idea
developed here is to reconstruct an image from noisy and indirect observations
by registering, via metamorphosis, a template to the observed data. Unlike a
registration with only geometrical changes, this framework gives good results
when intensities of the template are poorly chosen. We show that this method is
a well-defined regularisation method (proving existence, stability and
convergence) and present several numerical examples.
Challenges in High-dimensional Reinforcement Learning with Evolution Strategies
Authors: Nils Müller, Tobias Glasmachers
Date: 2018-06-04 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Vocal Bursts Intensity Prediction

Evolution Strategies (ESs) have recently become popular for training deep
neural networks, in particular on reinforcement learning tasks, a special form
of controller design. Compared to classic problems in continuous direct search,
deep networks pose extremely high-dimensional optimization problems, with many
thousands or even millions of variables. In addition, many control problems
give rise to a stochastic fitness function. Considering the relevance of the
application, we study the suitability of evolution strategies for
high-dimensional, stochastic problems. Our results give insights into which
algorithmic mechanisms of modern ES are of value for the class of problems at
hand, and they reveal principled limitations of the approach. They are in line
with our theoretical understanding of ESs. We show that combining ESs that
offer reduced internal algorithm cost with uncertainty handling techniques
yields promising methods for this class of problems.