pwc-archive/papers-with-abstracts huggingface dataset:
Large-scale randomized-coordinate descent methods with non-separable linear constraints
Authors: Sashank Reddi, Ahmed Hefny, Carlton Downey, Avinava Dubey, Suvrit Sra
Date: 2014-09-09 00:00:00

We develop randomized (block) coordinate descent (CD) methods for linearly
constrained convex optimization. Unlike most CD methods, we do not assume the
constraints to be separable, but let them be coupled linearly. To our
knowledge, ours is the first CD method that allows linear coupling constraints,
without making the global iteration complexity have an exponential dependence
on the number of constraints. We present algorithms and analysis for four key
problem scenarios: (i) smooth; (ii) smooth + nonsmooth separable; (iii)
asynchronous parallel; and (iv) stochastic. We illustrate empirical behavior of
our algorithms by simulation experiments.
Robust Subgraph Generation Improves Abstract Meaning Representation Parsing
Authors: Keenon Werling, Gabor Angeli, Christopher Manning
Date: 2015-06-10 00:00:00
Proceeding: IJCNLP 2015 7
Tasks: Abstract Meaning Representation, AMR Parsing, Event Extraction, Machine Translation, Translation

The Abstract Meaning Representation (AMR) is a representation for open-domain
rich semantics, with potential use in fields like event extraction and machine
translation. Node generation, typically done using a simple dictionary lookup,
is currently an important limiting factor in AMR parsing. We propose a small
set of actions that derive AMR subgraphs by transformations on spans of text,
which allows for more robust learning of this stage. Our set of construction
actions generalize better than the previous approach, and can be learned with a
simple classifier. We improve on the previous state-of-the-art result for AMR
parsing, boosting end-to-end performance by 3 F$_1$ on both the LDC2013E117 and
LDC2014T12 datasets.
Multiscale edge detection and parametric shape modeling for boundary delineation in optoacoustic images
Authors: Subhamoy Mandal, Viswanath Pamulakanty Sudarshan, Yeshaswini Nagaraj, Xose Luis Dean Ben, Daniel Razansky
Date: 2015-06-09 00:00:00
Tasks: Edge Detection

In this article, we present a novel scheme for segmenting the image boundary
(with the background) in optoacoustic small animal in vivo imaging systems. The
method utilizes a multiscale edge detection algorithm to generate a binary edge
map. A scale dependent morphological operation is employed to clean spurious
edges. Thereafter, an ellipse is fitted to the edge map through constrained
parametric transformations and iterative goodness of fit calculations. The
method delimits the tissue edges through the curve fitting model, which has
shown high levels of accuracy. Thus, this method enables segmentation of
optoacoutic images with minimal human intervention, by eliminating need of
scale selection for multiscale processing and seed point determination for
contour mapping.
Grammar as a Foreign Language
Authors: Oriol Vinyals, Lukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, Geoffrey Hinton
Date: 2014-12-23 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Constituency Parsing, CPU

Syntactic constituency parsing is a fundamental problem in natural language
processing and has been the subject of intensive research and engineering for
decades. As a result, the most accurate parsers are domain specific, complex,
and inefficient. In this paper we show that the domain agnostic
attention-enhanced sequence-to-sequence model achieves state-of-the-art results
on the most widely used syntactic constituency parsing dataset, when trained on
a large synthetic corpus that was annotated using existing parsers. It also
matches the performance of standard parsers when trained only on a small
human-annotated dataset, which shows that this model is highly data-efficient,
in contrast to sequence-to-sequence models without the attention mechanism. Our
parser is also fast, processing over a hundred sentences per second with an
unoptimized CPU implementation.
Variational consensus Monte Carlo
Authors: Maxim Rabinovich, Elaine Angelino, Michael. I. Jordan
Date: 2015-06-09 00:00:00
Proceeding: NeurIPS 2015 12

Practitioners of Bayesian statistics have long depended on Markov chain Monte
Carlo (MCMC) to obtain samples from intractable posterior distributions.
Unfortunately, MCMC algorithms are typically serial, and do not scale to the
large datasets typical of modern machine learning. The recently proposed
consensus Monte Carlo algorithm removes this limitation by partitioning the
data and drawing samples conditional on each partition in parallel (Scott et
al, 2013). A fixed aggregation function then combines these samples, yielding
approximate posterior samples. We introduce variational consensus Monte Carlo
(VCMC), a variational Bayes algorithm that optimizes over aggregation functions
to obtain samples from a distribution that better approximates the target. The
resulting objective contains an intractable entropy term; we therefore derive a
relaxation of the objective and show that the relaxed problem is blockwise
concave under mild conditions. We illustrate the advantages of our algorithm on
three inference tasks from the literature, demonstrating both the superior
quality of the posterior approximation and the moderate overhead of the
optimization step. Our algorithm achieves a relative error reduction (measured
against serial MCMC) of up to 39% compared to consensus Monte Carlo on the task
of estimating 300-dimensional probit regression parameter expectations;
similarly, it achieves an error reduction of 92% on the task of estimating
cluster comembership probabilities in a Gaussian mixture model with 8
components in 8 dimensions. Furthermore, these gains come at moderate cost
compared to the runtime of serial MCMC, achieving near-ideal speedup in some
instances.
Clustering by transitive propagation
Authors: Vijay Kumar, Dan Levy
Date: 2015-06-09 00:00:00
Tasks: Clustering, global-optimization

We present a global optimization algorithm for clustering data given the
ratio of likelihoods that each pair of data points is in the same cluster or in
different clusters. To define a clustering solution in terms of pairwise
relationships, a necessary and sufficient condition is that belonging to the
same cluster satisfies transitivity. We define a global objective function
based on pairwise likelihood ratios and a transitivity constraint over all
triples, assigning an equal prior probability to all clustering solutions. We
maximize the objective function by implementing max-sum message passing on the
corresponding factor graph to arrive at an O(N^3) algorithm. Lastly, we
demonstrate an application inspired by mutational sequencing for decoding
random binary words transmitted through a noisy channel.
A Variance Reduced Stochastic Newton Method
Authors: Aurelien Lucchi, Brian McWilliams, Thomas Hofmann
Date: 2015-03-28 00:00:00

Quasi-Newton methods are widely used in practise for convex loss minimization
problems. These methods exhibit good empirical performance on a wide variety of
tasks and enjoy super-linear convergence to the optimal solution. For
large-scale learning problems, stochastic Quasi-Newton methods have been
recently proposed. However, these typically only achieve sub-linear convergence
rates and have not been shown to consistently perform well in practice since
noisy Hessian approximations can exacerbate the effect of high-variance
stochastic gradient estimates. In this work we propose Vite, a novel stochastic
Quasi-Newton algorithm that uses an existing first-order technique to reduce
this variance. Without exploiting the specific form of the approximate Hessian,
we show that Vite reaches the optimum at a geometric rate with a constant
step-size when dealing with smooth strongly convex functions. Empirically, we
demonstrate improvements over existing stochastic Quasi-Newton and variance
reduced stochastic gradient methods.
The Wreath Process: A totally generative model of geometric shape based on nested symmetries
Authors: Diana Borsa, Thore Graepel, Andrew Gordon
Date: 2015-06-09 00:00:00

We consider the problem of modelling noisy but highly symmetric shapes that
can be viewed as hierarchies of whole-part relationships in which higher level
objects are composed of transformed collections of lower level objects. To this
end, we propose the stochastic wreath process, a fully generative probabilistic
model of drawings. Following Leyton's "Generative Theory of Shape", we
represent shapes as sequences of transformation groups composed through a
wreath product.
  This representation emphasizes the maximization of transfer --- the idea that
the most compact and meaningful representation of a given shape is achieved by
maximizing the re-use of existing building blocks or parts.
  The proposed stochastic wreath process extends Leyton's theory by defining a
probability distribution over geometric shapes in terms of noise processes that
are aligned with the generative group structure of the shape. We propose an
inference scheme for recovering the generative history of given images in terms
of the wreath process using reversible jump Markov chain Monte Carlo methods
and Approximate Bayesian Computation. In the context of sketching we
demonstrate the feasibility and limitations of this approach on model-generated
and real data.
A Linear-Time Particle Gibbs Sampler for Infinite Hidden Markov Models
Authors: Nilesh Tripuraneni, Shane Gu, Hong Ge, Zoubin Ghahramani
Date: 2015-05-03 00:00:00

Infinite Hidden Markov Models (iHMM's) are an attractive, nonparametric
generalization of the classical Hidden Markov Model which can automatically
infer the number of hidden states in the system. However, due to the
infinite-dimensional nature of transition dynamics performing inference in the
iHMM is difficult. In this paper, we present an infinite-state Particle Gibbs
(PG) algorithm to resample state trajectories for the iHMM. The proposed
algorithm uses an efficient proposal optimized for iHMMs and leverages ancestor
sampling to suppress degeneracy of the standard PG algorithm. Our algorithm
demonstrates significant convergence improvements on synthetic and real world
data sets. Additionally, the infinite-state PG algorithm has linear-time
complexity in the number of states in the sampler, while competing methods
scale quadratically.
Compact Shape Trees: A Contribution to the Forest of Shape Correspondences and Matching Methods
Authors: Abdulrahman Oladipupo Ibraheem
Date: 2015-06-09 00:00:00

We propose a novel technique, termed compact shape trees, for computing
correspondences of single-boundary 2-D shapes in O(n2) time. Together with zero
or more features defined at each of n sample points on the shape's boundary,
the compact shape tree of a shape comprises the O(n) collection of vectors
emanating from any of the sample points on the shape's boundary to the rest of
the sample points on the boundary. As it turns out, compact shape trees have a
number of elegant properties both in the spatial and frequency domains. In
particular, via a simple vector-algebraic argument, we show that the O(n)
collection of vectors in a compact shape tree possesses at least the same
discriminatory power as the O(n2) collection of lines emanating from each
sample point to every other sample point on a shape's boundary. In addition, we
describe neat approaches for achieving scale and rotation invariance with
compact shape trees in the spatial domain; by viewing compact shape trees as
aperiodic discrete signals, we also prove scale and rotation invariance
properties for them in the Fourier domain. Towards these, along the way, using
concepts from differential geometry and the Calculus, we propose a novel theory
for sampling 2-D shape boundaries in a scale and rotation invariant manner.
Finally, we propose a number of shape recognition experiments to test the
efficacy of our concept.
An Ensemble method for Content Selection for Data-to-text Systems
Authors: Dimitra Gkatzia, Helen Hastie
Date: 2015-06-09 00:00:00
Tasks: General Classification, Multi-Label Classification, MUlTI-LABEL-ClASSIFICATION, Time Series, Time Series Analysis

We present a novel approach for automatic report generation from time-series
data, in the context of student feedback generation. Our proposed methodology
treats content selection as a multi-label classification (MLC) problem, which
takes as input time-series data (students' learning data) and outputs a summary
of these data (feedback). Unlike previous work, this method considers all data
simultaneously using ensembles of classifiers, and therefore, it achieves
higher accuracy and F- score compared to meaningful baselines.
Efficient Object Localization Using Convolutional Networks
Authors: Jonathan Tompson, Ross Goroshin, Arjun Jain, Yann Lecun, Christopher Bregler
Date: 2014-11-16 00:00:00
Proceeding: CVPR 2015 6
Tasks: Object, Object Localization, Pose Estimation, Position

Recent state-of-the-art performance on human-body pose estimation has been
achieved with Deep Convolutional Networks (ConvNets). Traditional ConvNet
architectures include pooling and sub-sampling layers which reduce
computational requirements, introduce invariance and prevent over-training.
These benefits of pooling come at the cost of reduced localization accuracy. We
introduce a novel architecture which includes an efficient `position
refinement' model that is trained to estimate the joint offset location within
a small region of the image. This refinement model is jointly trained in
cascade with a state-of-the-art ConvNet model to achieve improved accuracy in
human joint location estimation. We show that the variance of our detector
approaches the variance of human annotations on the FLIC dataset and
outperforms all existing approaches on the MPII-human-pose dataset.
Times series averaging from a probabilistic interpretation of time-elastic kernel
Authors: Pierre-François Marteau
Date: 2015-05-26 00:00:00
Tasks: Clustering, Dynamic Time Warping, General Classification, Time Series, Time Series Analysis, Time Series Averaging, Time Series Clustering

At the light of regularized dynamic time warping kernels, this paper
reconsider the concept of time elastic centroid (TEC) for a set of time series.
From this perspective, we show first how TEC can easily be addressed as a
preimage problem. Unfortunately this preimage problem is ill-posed, may suffer
from over-fitting especially for long time series and getting a sub-optimal
solution involves heavy computational costs. We then derive two new algorithms
based on a probabilistic interpretation of kernel alignment matrices that
expresses in terms of probabilistic distributions over sets of alignment paths.
The first algorithm is an iterative agglomerative heuristics inspired from the
state of the art DTW barycenter averaging (DBA) algorithm proposed specifically
for the Dynamic Time Warping measure. The second proposed algorithm achieves a
classical averaging of the aligned samples but also implements an averaging of
the time of occurrences of the aligned samples. It exploits a straightforward
progressive agglomerative heuristics. An experimentation that compares for 45
time series datasets classification error rates obtained by first near
neighbors classifiers exploiting a single medoid or centroid estimate to
represent each categories show that: i) centroids based approaches
significantly outperform medoids based approaches, ii) on the considered
experience, the two proposed algorithms outperform the state of the art DBA
algorithm, and iii) the second proposed algorithm that implements an averaging
jointly in the sample space and along the time axes emerges as the most
significantly robust time elastic averaging heuristic with an interesting noise
reduction capability. Index Terms-Time series averaging Time elastic kernel
Dynamic Time Warping Time series clustering and classification.
Generalized Gradient Learning on Time Series under Elastic Transformations
Authors: Brijnesh Jain
Date: 2015-02-17 00:00:00
Tasks: Dynamic Time Warping, Time Series, Time Series Analysis

The majority of machine learning algorithms assumes that objects are
represented as vectors. But often the objects we want to learn on are more
naturally represented by other data structures such as sequences and time
series. For these representations many standard learning algorithms are
unavailable. We generalize gradient-based learning algorithms to time series
under dynamic time warping. To this end, we introduce elastic functions, which
extend functions on time series to matrix spaces. Necessary conditions are
presented under which generalized gradient learning on time series is
consistent. We indicate how results carry over to arbitrary elastic distance
functions and to sequences consisting of symbolic elements. Specifically, four
linear classifiers are extended to time series under dynamic time warping and
applied to benchmark datasets. Results indicate that generalized gradient
learning via elastic functions have the potential to complement the
state-of-the-art in statistical pattern recognition on time series.
Adversarial patrolling with spatially uncertain alarm signals
Authors: Nicola Basilico, Giuseppe De Nittis, Nicola Gatti
Date: 2015-06-09 00:00:00

When securing complex infrastructures or large environments, constant
surveillance of every area is not affordable. To cope with this issue, a common
countermeasure is the usage of cheap but wide-ranged sensors, able to detect
suspicious events that occur in large areas, supporting patrollers to improve
the effectiveness of their strategies. However, such sensors are commonly
affected by uncertainty. In the present paper, we focus on spatially uncertain
alarm signals. That is, the alarm system is able to detect an attack but it is
uncertain on the exact position where the attack is taking place. This is
common when the area to be secured is wide such as in border patrolling and
fair site surveillance. We propose, to the best of our knowledge, the first
Patrolling Security Game model where a Defender is supported by a spatially
uncertain alarm system which non-deterministically generates signals once a
target is under attack. We show that finding the optimal strategy in arbitrary
graphs is APX-hard even in zero-sum games and we provide two (exponential time)
exact algorithms and two (polynomial time) approximation algorithms.
Furthermore, we analyse what happens in environments with special topologies,
showing that in linear and cycle graphs the optimal patrolling strategy can be
found in polynomial time, de facto allowing our algorithms to be used in
real-life scenarios, while in trees the problem is NP-hard. Finally, we show
that without false positives and missed detections, the best patrolling
strategy reduces to stay in a place, wait for a signal, and respond to it at
best. This strategy is optimal even with non-negligible missed detection rates,
which, unfortunately, affect every commercial alarm system. We evaluate our
methods in simulation, assessing both quantitative and qualitative aspects.
Kernel-Based Just-In-Time Learning for Passing Expectation Propagation Messages
Authors: Wittawat Jitkrittum, Arthur Gretton, Nicolas Heess, S. M. Ali Eslami, Balaji Lakshminarayanan, Dino Sejdinovic, Zoltán Szabó
Date: 2015-03-09 00:00:00
Tasks: regression

We propose an efficient nonparametric strategy for learning a message
operator in expectation propagation (EP), which takes as input the set of
incoming messages to a factor node, and produces an outgoing message as output.
This learned operator replaces the multivariate integral required in classical
EP, which may not have an analytic expression. We use kernel-based regression,
which is trained on a set of probability distributions representing the
incoming messages, and the associated outgoing messages. The kernel approach
has two main advantages: first, it is fast, as it is implemented using a novel
two-layer random feature representation of the input message distributions;
second, it has principled uncertainty estimates, and can be cheaply updated
online, meaning it can request and incorporate new training data when it
encounters inputs on which it is uncertain. In experiments, our approach is
able to solve learning problems where a single message operator is required for
multiple, substantially different data sets (logistic regression for a variety
of classification problems), where it is essential to accurately assess
uncertainty and to efficiently and robustly update the message operator.
Distributed Stochastic Optimization of the Regularized Risk
Authors: Shin Matsushima, Hyokun Yun, Xinhua Zhang, S. V. N. Vishwanathan
Date: 2014-06-17 00:00:00
Tasks: Stochastic Optimization

Many machine learning algorithms minimize a regularized risk, and stochastic
optimization is widely used for this task. When working with massive data, it
is desirable to perform stochastic optimization in parallel. Unfortunately,
many existing stochastic optimization algorithms cannot be parallelized
efficiently. In this paper we show that one can rewrite the regularized risk
minimization problem as an equivalent saddle-point problem, and propose an
efficient distributed stochastic optimization (DSO) algorithm. We prove the
algorithm's rate of convergence; remarkably, our analysis shows that the
algorithm scales almost linearly with the number of processors. We also verify
with empirical evaluations that the proposed algorithm is competitive with
other parallel, general purpose stochastic and batch optimization algorithms
for regularized risk minimization.
On the Error of Random Fourier Features
Authors: Dougal J. Sutherland, Jeff Schneider
Date: 2015-06-09 00:00:00
Tasks: BIG-bench Machine Learning

Kernel methods give powerful, flexible, and theoretically grounded approaches
to solving many problems in machine learning. The standard approach, however,
requires pairwise evaluations of a kernel function, which can lead to
scalability issues for very large datasets. Rahimi and Recht (2007) suggested a
popular approach to handling this problem, known as random Fourier features.
The quality of this approximation, however, is not well understood. We improve
the uniform error bound of that paper, as well as giving novel understandings
of the embedding's variance, approximation error, and use in some machine
learning methods. We also point out that surprisingly, of the two main variants
of those features, the more widely used is strictly higher-variance for the
Gaussian kernel and has worse bounds.
Fast Geometric Fit Algorithm for Sphere Using Exact Solution
Authors: Sumith YD
Date: 2015-06-09 00:00:00

Sphere fitting is a common problem in almost all science and engineering
disciplines. Most of methods available are iterative in behavior. This involves
fitting of the parameters in a least square sense or in a geometric sense. Here
we extend the methods of Thomas Chan and Landau who fitted the 2D data using
circle. This work closely resemble their work in redefining the error estimate
and solving the sphere fitting problem exactly. The solutions for center and
radius of the sphere can be found exactly and the equations can be hard coded
for high performance. We have also shown some comparison with other popular
methods and how this method behaves.