pwc-archive/papers-with-abstracts huggingface dataset:
Neural GPUs Learn Algorithms
Authors: Łukasz Kaiser, Ilya Sutskever
Date: 2015-11-25 00:00:00
Tasks: GPU

Learning an algorithm from examples is a fundamental problem that has been
widely studied. Recently it has been addressed using neural networks, in
particular by Neural Turing Machines (NTMs). These are fully differentiable
computers that use backpropagation to learn their own programming. Despite
their appeal NTMs have a weakness that is caused by their sequential nature:
they are not parallel and are are hard to train due to their large depth when
unfolded.
  We present a neural network architecture to address this problem: the Neural
GPU. It is based on a type of convolutional gated recurrent unit and, like the
NTM, is computationally universal. Unlike the NTM, the Neural GPU is highly
parallel which makes it easier to train and efficient to run.
  An essential property of algorithms is their ability to handle inputs of
arbitrary size. We show that the Neural GPU can be trained on short instances
of an algorithmic task and successfully generalize to long instances. We
verified it on a number of tasks including long addition and long
multiplication of numbers represented in binary. We train the Neural GPU on
numbers with upto 20 bits and observe no errors whatsoever while testing it,
even on much longer numbers.
  To achieve these results we introduce a technique for training deep recurrent
networks: parameter sharing relaxation. We also found a small amount of dropout
and gradient noise to have a large positive effect on learning and
generalization.
Conformal Predictors for Compound Activity Prediction
Authors: Paolo Toccacheli, Ilia Nouretdinov, Alexander Gammerman
Date: 2016-03-14 00:00:00
Tasks: Activity Prediction, Conformal Prediction, Prediction

The paper presents an application of Conformal Predictors to a
chemoinformatics problem of identifying activities of chemical compounds. The
paper addresses some specific challenges of this domain: a large number of
compounds (training examples), high-dimensionality of feature space, sparseness
and a strong class imbalance. A variant of conformal predictors called
Inductive Mondrian Conformal Predictor is applied to deal with these
challenges. Results are presented for several non-conformity measures (NCM)
extracted from underlying algorithms and different kernels. A number of
performance measures are used in order to demonstrate the flexibility of
Inductive Mondrian Conformal Predictors in dealing with such a complex set of
data.
  Keywords: Conformal Prediction, Confidence Estimation, Chemoinformatics,
Non-Conformity Measure.
End-to-End Attention-based Large Vocabulary Speech Recognition
Authors: Dzmitry Bahdanau, Jan Chorowski, Dmitriy Serdyuk, Philemon Brakel, Yoshua Bengio
Date: 2015-08-18 00:00:00
Tasks: Acoustic Modelling, Language Modeling, Language Modelling, speech-recognition, Speech Recognition

Many of the current state-of-the-art Large Vocabulary Continuous Speech
Recognition Systems (LVCSR) are hybrids of neural networks and Hidden Markov
Models (HMMs). Most of these systems contain separate components that deal with
the acoustic modelling, language modelling and sequence decoding. We
investigate a more direct approach in which the HMM is replaced with a
Recurrent Neural Network (RNN) that performs sequence prediction directly at
the character level. Alignment between the input features and the desired
character sequence is learned automatically by an attention mechanism built
into the RNN. For each predicted character, the attention mechanism scans the
input sequence and chooses relevant frames. We propose two methods to speed up
this operation: limiting the scan to a subset of most promising frames and
pooling over time the information contained in neighboring frames, thereby
reducing source sequence length. Integrating an n-gram language model into the
decoding process yields recognition accuracies similar to other HMM-free
RNN-based approaches.
A Survey of Word Reordering in Statistical Machine Translation: Computational Models and Language Phenomena
Authors: Arianna Bisazza, Marcello Federico
Date: 2015-02-17 00:00:00
Tasks: Machine Translation, Translation

Word reordering is one of the most difficult aspects of statistical machine
translation (SMT), and an important factor of its quality and efficiency.
Despite the vast amount of research published to date, the interest of the
community in this problem has not decreased, and no single method appears to be
strongly dominant across language pairs. Instead, the choice of the optimal
approach for a new translation task still seems to be mostly driven by
empirical trials. To orientate the reader in this vast and complex research
area, we present a comprehensive survey of word reordering viewed as a
statistical modeling challenge and as a natural language phenomenon. The survey
describes in detail how word reordering is modeled within different
string-based and tree-based SMT frameworks and as a stand-alone task, including
systematic overviews of the literature in advanced reordering modeling. We then
question why some approaches are more successful than others in different
language pairs. We argue that, besides measuring the amount of reordering, it
is important to understand which kinds of reordering occur in a given language
pair. To this end, we conduct a qualitative analysis of word reordering
phenomena in a diverse sample of language pairs, based on a large collection of
linguistic knowledge. Empirical results in the SMT literature are shown to
support the hypothesis that a few linguistic facts can be very useful to
anticipate the reordering characteristics of a language pair and to select the
SMT framework that best suits them.
Sequential Voting Promotes Collective Discovery in Social Recommendation Systems
Authors: L. Elisa Celis, Peter M. Krafft, Nathan Kobe
Date: 2016-03-14 00:00:00
Tasks: Recommendation Systems

One goal of online social recommendation systems is to harness the wisdom of
crowds in order to identify high quality content. Yet the sequential voting
mechanisms that are commonly used by these systems are at odds with existing
theoretical and empirical literature on optimal aggregation. This literature
suggests that sequential voting will promote herding---the tendency for
individuals to copy the decisions of others around them---and hence lead to
suboptimal content recommendation. Is there a problem with our practice, or a
problem with our theory? Previous attempts at answering this question have been
limited by a lack of objective measurements of content quality. Quality is
typically defined endogenously as the popularity of content in absence of
social influence. The flaw of this metric is its presupposition that the
preferences of the crowd are aligned with underlying quality. Domains in which
content quality can be defined exogenously and measured objectively are thus
needed in order to better assess the design choices of social recommendation
systems. In this work, we look to the domain of education, where content
quality can be measured via how well students are able to learn from the
material presented to them. Through a behavioral experiment involving a
simulated massive open online course (MOOC) run on Amazon Mechanical Turk, we
show that sequential voting systems can surface better content than systems
that elicit independent votes.
Sparsity in Multivariate Extremes with Applications to Anomaly Detection
Authors: Nicolas Goix, Anne Sabourin, Stéphan Clémençon
Date: 2015-07-21 00:00:00
Tasks: Anomaly Detection, Dimensionality Reduction, Management

Capturing the dependence structure of multivariate extreme events is a major
concern in many fields involving the management of risks stemming from multiple
sources, e.g. portfolio monitoring, insurance, environmental risk management
and anomaly detection. One convenient (non-parametric) characterization of
extremal dependence in the framework of multivariate Extreme Value Theory (EVT)
is the angular measure, which provides direct information about the probable
'directions' of extremes, that is, the relative contribution of each
feature/coordinate of the 'largest' observations. Modeling the angular measure
in high dimensional problems is a major challenge for the multivariate analysis
of rare events. The present paper proposes a novel methodology aiming at
exhibiting a sparsity pattern within the dependence structure of extremes. This
is done by estimating the amount of mass spread by the angular measure on
representative sets of directions, corresponding to specific sub-cones of
$R^d\_+$. This dimension reduction technique paves the way towards scaling up
existing multivariate EVT methods. Beyond a non-asymptotic study providing a
theoretical validity framework for our method, we propose as a direct
application a --first-- anomaly detection algorithm based on multivariate EVT.
This algorithm builds a sparse 'normal profile' of extreme behaviours, to be
confronted with new (possibly abnormal) extreme observations. Illustrative
experimental results provide strong empirical evidence of the relevance of our
approach.
Controlling Search in Very large Commonsense Knowledge Bases: A Machine Learning Approach
Authors: Abhishek Sharma, Michael Witbrock, Keith Goolsbey
Date: 2016-03-14 00:00:00
Tasks: BIG-bench Machine Learning

Very large commonsense knowledge bases (KBs) often have thousands to millions
of axioms, of which relatively few are relevant for answering any given query.
A large number of irrelevant axioms can easily overwhelm resolution-based
theorem provers. Therefore, methods that help the reasoner identify useful
inference paths form an essential part of large-scale reasoning systems. In
this paper, we describe two ordering heuristics for optimization of reasoning
in such systems. First, we discuss how decision trees can be used to select
inference steps that are more likely to succeed. Second, we identify a small
set of problem instance features that suffice to guide searches away from
intractable regions of the search space. We show the efficacy of these
techniques via experiments on thousands of queries from the Cyc KB. Results
show that these methods lead to an order of magnitude reduction in inference
time.
Deep Neural Networks with Random Gaussian Weights: A Universal Classification Strategy?
Authors: Raja Giryes, Guillermo Sapiro, Alex M. Bronstein
Date: 2015-04-30 00:00:00
Tasks: compressed sensing, Dictionary Learning, General Classification, Metric Learning

Three important properties of a classification machinery are: (i) the system
preserves the core information of the input data; (ii) the training examples
convey information about unseen data; and (iii) the system is able to treat
differently points from different classes. In this work we show that these
fundamental properties are satisfied by the architecture of deep neural
networks. We formally prove that these networks with random Gaussian weights
perform a distance-preserving embedding of the data, with a special treatment
for in-class and out-of-class data. Similar points at the input of the network
are likely to have a similar output. The theoretical analysis of deep networks
here presented exploits tools used in the compressed sensing and dictionary
learning literature, thereby making a formal connection between these important
topics. The derived results allow drawing conclusions on the metric learning
properties of the network and their relation to its structure, as well as
providing bounds on the required size of the training set such that the
training examples would represent faithfully the unseen data. The results are
validated with state-of-the-art trained networks.
Rapid building detection using machine learning
Authors: Joseph Paul Cohen, Wei Ding, Caitlin Kuhlman, Aijun Chen, Liping Di
Date: 2016-03-14 00:00:00
Tasks: BIG-bench Machine Learning, Classification, General Classification, object-detection, Object Detection

This work describes algorithms for performing discrete object detection,
specifically in the case of buildings, where usually only low quality RGB-only
geospatial reflective imagery is available. We utilize new candidate search and
feature extraction techniques to reduce the problem to a machine learning (ML)
classification task. Here we can harness the complex patterns of contrast
features contained in training data to establish a model of buildings. We avoid
costly sliding windows to generate candidates; instead we innovatively stitch
together well known image processing techniques to produce candidates for
building detection that cover 80-85% of buildings. Reducing the number of
possible candidates is important due to the scale of the problem. Each
candidate is subjected to classification which, although linear, costs time and
prohibits large scale evaluation. We propose a candidate alignment algorithm to
boost classification performance to 80-90% precision with a linear time
algorithm and show it has negligible cost. Also, we propose a new concept
called a Permutable Haar Mesh (PHM) which we use to form and traverse a search
space to recover candidate buildings which were lost in the initial
preprocessing phase.
Sparse Coding with Earth Mover's Distance for Multi-Instance Histogram Representation
Authors: Mohua Zhang, Jianhua Peng, Xuejie Liu, Jim Jing-Yan Wang
Date: 2015-02-09 00:00:00
Tasks: Retrieval

Sparse coding (Sc) has been studied very well as a powerful data
representation method. It attempts to represent the feature vector of a data
sample by reconstructing it as the sparse linear combination of some basic
elements, and a $L_2$ norm distance function is usually used as the loss
function for the reconstruction error. In this paper, we investigate using Sc
as the representation method within multi-instance learning framework, where a
sample is given as a bag of instances, and further represented as a histogram
of the quantized instances. We argue that for the data type of histogram, using
$L_2$ norm distance is not suitable, and propose to use the earth mover's
distance (EMD) instead of $L_2$ norm distance as a measure of the
reconstruction error. By minimizing the EMD between the histogram of a sample
and the its reconstruction from some basic histograms, a novel sparse coding
method is developed, which is refereed as SC-EMD. We evaluate its performances
as a histogram representation method in tow multi-instance learning problems
--- abnormal image detection in wireless capsule endoscopy videos, and protein
binding site retrieval. The encouraging results demonstrate the advantages of
the new method over the traditional method using $L_2$ norm distance.
Neuroprosthetic decoder training as imitation learning
Authors: Josh Merel, David Carlson, Liam Paninski, John P. Cunningham
Date: 2015-11-13 00:00:00
Tasks: Brain Computer Interface, Decoder, Imitation Learning

Neuroprosthetic brain-computer interfaces function via an algorithm which
decodes neural activity of the user into movements of an end effector, such as
a cursor or robotic arm. In practice, the decoder is often learned by updating
its parameters while the user performs a task. When the user's intention is not
directly observable, recent methods have demonstrated value in training the
decoder against a surrogate for the user's intended movement. We describe how
training a decoder in this way is a novel variant of an imitation learning
problem, where an oracle or expert is employed for supervised training in lieu
of direct observations, which are not available. Specifically, we describe how
a generic imitation learning meta-algorithm, dataset aggregation (DAgger, [1]),
can be adapted to train a generic brain-computer interface. By deriving
existing learning algorithms for brain-computer interfaces in this framework,
we provide a novel analysis of regret (an important metric of learning
efficacy) for brain-computer interfaces. This analysis allows us to
characterize the space of algorithmic variants and bounds on their regret
rates. Existing approaches for decoder learning have been performed in the
cursor control setting, but the available design principles for these decoders
are such that it has been impossible to scale them to naturalistic settings.
Leveraging our findings, we then offer an algorithm that combines imitation
learning with optimal control, which should allow for training of arbitrary
effectors for which optimal control can generate goal-oriented control. We
demonstrate this novel and general BCI algorithm with simulated neuroprosthetic
control of a 26 degree-of-freedom model of an arm, a sophisticated and
realistic end effector.
Automatic Discrimination of Color Retinal Images using the Bag of Words Approach
Authors: Ibrahim Sadek
Date: 2016-03-14 00:00:00

Diabetic retinopathy (DR) and age related macular degeneration (ARMD) are
among the major causes of visual impairment worldwide. DR is mainly
characterized by red spots, namely microaneurysms and bright lesions,
specifically exudates whereas ARMD is mainly identified by tiny yellow or white
deposits called drusen. Since exudates might be the only manifestation of the
early diabetic retinopathy, there is an increase demand for automatic
retinopathy diagnosis. Exudates and drusen may share similar appearances, thus
discriminating between them is of interest to enhance screening performance. In
this research, we investigative the role of bag of words approach in the
automatic diagnosis of retinopathy diabetes. We proposed to use a single based
and multiple based methods for the construction of the visual dictionary by
combining the histogram of word occurrences from each dictionary and building a
single histogram. The introduced approach is evaluated for automatic diagnosis
of normal and abnormal color fundus images with bright lesions. This approach
has been implemented on 430 fundus images, including six publicly available
datasets, in addition to one local dataset. The mean accuracies reported are
97.2% and 99.77% for single based and multiple based dictionaries respectively.
Learning Network of Multivariate Hawkes Processes: A Time Series Approach
Authors: Jalal Etesami, Negar Kiyavash, Kun Zhang, Kushagra Singhal
Date: 2016-03-14 00:00:00
Tasks: Time Series, Time Series Analysis

Learning the influence structure of multiple time series data is of great
interest to many disciplines. This paper studies the problem of recovering the
causal structure in network of multivariate linear Hawkes processes. In such
processes, the occurrence of an event in one process affects the probability of
occurrence of new events in some other processes. Thus, a natural notion of
causality exists between such processes captured by the support of the
excitation matrix. We show that the resulting causal influence network is
equivalent to the Directed Information graph (DIG) of the processes, which
encodes the causal factorization of the joint distribution of the processes.
Furthermore, we present an algorithm for learning the support of excitation
matrix (or equivalently the DIG). The performance of the algorithm is evaluated
on synthesized multivariate Hawkes networks as well as a stock market and
MemeTracker real-world dataset.
An interacting replica approach applied to the traveling salesman problem
Authors: Bo Sun, Blake Leonard, Peter Ronhovde, Zohar Nussinov
Date: 2014-06-27 00:00:00
Tasks: Combinatorial Optimization, Traveling Salesman Problem

We present a physics inspired heuristic method for solving combinatorial
optimization problems. Our approach is specifically motivated by the desire to
avoid trapping in metastable local minima- a common occurrence in hard problems
with multiple extrema. Our method involves (i) coupling otherwise independent
simulations of a system ("replicas") via geometrical distances as well as (ii)
probabilistic inference applied to the solutions found by individual replicas.
The {\it ensemble} of replicas evolves as to maximize the inter-replica
correlation while simultaneously minimize the local intra-replica cost function
(e.g., the total path length in the Traveling Salesman Problem within each
replica). We demonstrate how our method improves the performance of rudimentary
local optimization schemes long applied to the NP hard Traveling Salesman
Problem. In particular, we apply our method to the well-known "$k$-opt"
algorithm and examine two particular cases- $k=2$ and $k=3$. With the aid of
geometrical coupling alone, we are able to determine for the optimum tour
length on systems up to $280$ cities (an order of magnitude larger than the
largest systems typically solved by the bare $k=3$ opt). The probabilistic
replica-based inference approach improves $k-opt$ even further and determines
the optimal solution of a problem with $318$ cities and find tours whose total
length is close to that of the optimal solutions for other systems with a
larger number of cities.
Diversity in Object Proposals
Authors: Anton Winschel, Rainer Lienhart, Christian Eggert
Date: 2016-03-14 00:00:00
Tasks: Diversity, Object, Object Recognition

Current top performing object recognition systems build on object proposals
as a preprocessing step. Object proposal algorithms are designed to generate
candidate regions for generic objects, yet current approaches are limited in
capturing the vast variety of object characteristics. In this paper we analyze
the error modes of the state-of-the-art Selective Search object proposal
algorithm and suggest extensions to broaden its feature diversity in order to
mitigate its error modes. We devise an edge grouping algorithm for handling
objects without clear boundaries. To further enhance diversity, we incorporate
the Edge Boxes proposal algorithm, which is based on fundamentally different
principles than Selective Search. The combination of segmentations and edges
provides rich image information and feature diversity which is essential for
obtaining high quality object proposals for generic objects. For a preset
amount of object proposals we achieve considerably better results by using our
combination of different strategies than using any single strategy alone.
Dynamic Scene Deblurring using a Locally Adaptive Linear Blur Model
Authors: Tae Hyun Kim, Seungjun Nah, Kyoung Mu Lee
Date: 2016-03-14 00:00:00
Tasks: Deblurring, Optical Flow Estimation, Video Deblurring

State-of-the-art video deblurring methods cannot handle blurry videos
recorded in dynamic scenes, since they are built under a strong assumption that
the captured scenes are static. Contrary to the existing methods, we propose a
video deblurring algorithm that can deal with general blurs inherent in dynamic
scenes. To handle general and locally varying blurs caused by various sources,
such as moving objects, camera shake, depth variation, and defocus, we estimate
pixel-wise non-uniform blur kernels. We infer bidirectional optical flows to
handle motion blurs, and also estimate Gaussian blur maps to remove optical
blur from defocus in our new blur model. Therefore, we propose a single energy
model that jointly estimates optical flows, defocus blur maps and latent
frames. We also provide a framework and efficient solvers to minimize the
proposed energy model. By optimizing the energy model, we achieve significant
improvements in removing general blurs, estimating optical flows, and extending
depth-of-field in blurry frames. Moreover, in this work, to evaluate the
performance of non-uniform deblurring methods objectively, we have constructed
a new realistic dataset with ground truths. In addition, extensive experimental
on publicly available challenging video data demonstrate that the proposed
method produces qualitatively superior performance than the state-of-the-art
methods which often fail in either deblurring or optical flow estimation.