pwc-archive/papers-with-abstracts huggingface dataset:
An Integrated Semantic Web Service Discovery and Composition Framework
Authors: Pablo Rodriguez-Mier, Carlos Pedrinaci, Manuel Lama, Manuel Mucientes
Date: 2015-02-10 00:00:00
Tasks: Service Composition

In this paper we present a theoretical analysis of graph-based service
composition in terms of its dependency with service discovery. Driven by this
analysis we define a composition framework by means of integration with
fine-grained I/O service discovery that enables the generation of a graph-based
composition which contains the set of services that are semantically relevant
for an input-output request. The proposed framework also includes an optimal
composition search algorithm to extract the best composition from the graph
minimising the length and the number of services, and different graph
optimisations to improve the scalability of the system. A practical
implementation used for the empirical analysis is also provided. This analysis
proves the scalability and flexibility of our proposal and provides insights on
how integrated composition systems can be designed in order to achieve good
performance in real scenarios for the Web.
A Global Approach for Solving Edge-Matching Puzzles
Authors: Shahar Z. Kovalsky, Daniel Glasner, Ronen Basri
Date: 2014-09-21 00:00:00

We consider apictorial edge-matching puzzles, in which the goal is to arrange
a collection of puzzle pieces with colored edges so that the colors match along
the edges of adjacent pieces. We devise an algebraic representation for this
problem and provide conditions under which it exactly characterizes a puzzle.
Using the new representation, we recast the combinatorial, discrete problem of
solving puzzles as a global, polynomial system of equations with continuous
variables. We further propose new algorithms for generating approximate
solutions to the continuous problem by solving a sequence of convex
relaxations.
Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering
Authors: Simon Lacoste-Julien, Fredrik Lindsten, Francis Bach
Date: 2015-01-09 00:00:00
Tasks: Position

Recently, the Frank-Wolfe optimization algorithm was suggested as a procedure
to obtain adaptive quadrature rules for integrals of functions in a reproducing
kernel Hilbert space (RKHS) with a potentially faster rate of convergence than
Monte Carlo integration (and "kernel herding" was shown to be a special case of
this procedure). In this paper, we propose to replace the random sampling step
in a particle filter by Frank-Wolfe optimization. By optimizing the position of
the particles, we can obtain better accuracy than random or quasi-Monte Carlo
sampling. In applications where the evaluation of the emission probabilities is
expensive (such as in robot localization), the additional computational cost to
generate the particles through optimization can be justified. Experiments on
standard synthetic examples as well as on a robot localization task indicate
indeed an improvement of accuracy over random and quasi-Monte Carlo sampling.
On Forgetting in Tractable Propositional Fragments
Authors: Yisong Wang
Date: 2015-02-10 00:00:00

Distilling from a knowledge base only the part that is relevant to a subset
of alphabet, which is recognized as forgetting, has attracted extensive
interests in AI community. In standard propositional logic, a general algorithm
of forgetting and its computation-oriented investigation in various fragments
whose satisfiability are tractable are still lacking. The paper aims at filling
the gap. After exploring some basic properties of forgetting in propositional
logic, we present a resolution-based algorithm of forgetting for CNF fragment,
and some complexity results about forgetting in Horn, renamable Horn, q-Horn,
Krom, DNF and CNF fragments of propositional logic.
The Benefit of Sex in Noisy Evolutionary Search
Authors: Tobias Friedrich, Timo Kötzing, Martin Krejca, Andrew M. Sutton
Date: 2015-02-10 00:00:00

The benefit of sexual recombination is one of the most fundamental questions
both in population genetics and evolutionary computation. It is widely believed
that recombination helps solving difficult optimization problems. We present
the first result, which rigorously proves that it is beneficial to use sexual
recombination in an uncertain environment with a noisy fitness function. For
this, we model sexual recombination with a simple estimation of distribution
algorithm called the Compact Genetic Algorithm (cGA), which we compare with the
classical $\mu+1$ EA. For a simple noisy fitness function with additive
Gaussian posterior noise $\mathcal{N}(0,\sigma^2)$, we prove that the
mutation-only $\mu+1$ EA typically cannot handle noise in polynomial time for
$\sigma^2$ large enough while the cGA runs in polynomial time as long as the
population size is not too small. This shows that in this uncertain environment
sexual recombination is provably beneficial. We observe the same behavior in a
small empirical study.
Generative Moment Matching Networks
Authors: Yujia Li, Kevin Swersky, Richard Zemel
Date: 2015-02-10 00:00:00
Tasks: Generative Adversarial Network, Two-sample testing

We consider the problem of learning deep generative models from data. We
formulate a method that generates an independent sample via a single
feedforward pass through a multilayer perceptron, as in the recently proposed
generative adversarial networks (Goodfellow et al., 2014). Training a
generative adversarial network, however, requires careful optimization of a
difficult minimax program. Instead, we utilize a technique from statistical
hypothesis testing known as maximum mean discrepancy (MMD), which leads to a
simple objective that can be interpreted as matching all orders of statistics
between a dataset and samples from the model, and can be trained by
backpropagation. We further boost the performance of this approach by combining
our generative network with an auto-encoder network, using MMD to learn to
generate codes that can then be decoded to produce samples. We show that the
combination of these techniques yields excellent generative models compared to
baseline approaches as measured on MNIST and the Toronto Face Database.
Particle Gibbs with Ancestor Sampling for Probabilistic Programs
Authors: Jan-Willem van de Meent, Hongseok Yang, Vikash Mansinghka, Frank Wood
Date: 2015-01-27 00:00:00
Tasks: Probabilistic Programming

Particle Markov chain Monte Carlo techniques rank among current
state-of-the-art methods for probabilistic program inference. A drawback of
these techniques is that they rely on importance resampling, which results in
degenerate particle trajectories and a low effective sample size for variables
sampled early in a program. We here develop a formalism to adapt ancestor
resampling, a technique that mitigates particle degeneracy, to the
probabilistic programming setting. We present empirical results that
demonstrate nontrivial performance gains.
Learning Reductions that Really Work
Authors: Alina Beygelzimer, Hal Daumé III, John Langford, Paul Mineiro
Date: 2015-02-09 00:00:00
Tasks: BIG-bench Machine Learning

We provide a summary of the mathematical and computational techniques that
have enabled learning reductions to effectively address a wide class of
problems, and show that this approach to solving machine learning problems can
be broadly useful.
Optimal and Adaptive Algorithms for Online Boosting
Authors: Alina Beygelzimer, Satyen Kale, Haipeng Luo
Date: 2015-02-09 00:00:00

We study online boosting, the task of converting any weak online learner into
a strong online learner. Based on a novel and natural definition of weak online
learnability, we develop two online boosting algorithms. The first algorithm is
an online version of boost-by-majority. By proving a matching lower bound, we
show that this algorithm is essentially optimal in terms of the number of weak
learners and the sample complexity needed to achieve a specified accuracy. This
optimal algorithm is not adaptive however. Using tools from online loss
minimization, we derive an adaptive online boosting algorithm that is also
parameter-free, but not optimal. Both algorithms work with base learners that
can handle example importance weights directly, as well as by rejection
sampling examples with probability defined by the booster. Results are
complemented with an extensive experimental study.
Random Coordinate Descent Methods for Minimizing Decomposable Submodular Functions
Authors: Alina Ene, Huy L. Nguyen
Date: 2015-02-09 00:00:00
Tasks: BIG-bench Machine Learning

Submodular function minimization is a fundamental optimization problem that
arises in several applications in machine learning and computer vision. The
problem is known to be solvable in polynomial time, but general purpose
algorithms have high running times and are unsuitable for large-scale problems.
Recent work have used convex optimization techniques to obtain very practical
algorithms for minimizing functions that are sums of ``simple" functions. In
this paper, we use random coordinate descent methods to obtain algorithms with
faster linear convergence rates and cheaper iteration costs. Compared to
alternating projection methods, our algorithms do not rely on full-dimensional
vector operations and they converge in significantly fewer iterations.
From Predictive to Prescriptive Analytics
Authors: Dimitris Bertsimas, Nathan Kallus
Date: 2014-02-22 00:00:00
Tasks: Management, Stochastic Optimization

In this paper, we combine ideas from machine learning (ML) and operations
research and management science (OR/MS) in developing a framework, along with
specific methods, for using data to prescribe optimal decisions in OR/MS
problems. In a departure from other work on data-driven optimization and
reflecting our practical experience with the data available in applications of
OR/MS, we consider data consisting, not only of observations of quantities with
direct effect on costs/revenues, such as demand or returns, but predominantly
of observations of associated auxiliary quantities. The main problem of
interest is a conditional stochastic optimization problem, given imperfect
observations, where the joint probability distributions that specify the
problem are unknown. We demonstrate that our proposed solution methods, which
are inspired by ML methods such as local regression, CART, and random forests,
are generally applicable to a wide range of decision problems. We prove that
they are tractable and asymptotically optimal even when data is not iid and may
be censored. We extend this to the case where decision variables may directly
affect uncertainty in unknown ways, such as pricing's effect on demand. As an
analogue to R^2, we develop a metric P termed the coefficient of
prescriptiveness to measure the prescriptive content of data and the efficacy
of a policy from an operations perspective. To demonstrate the power of our
approach in a real-world setting we study an inventory management problem faced
by the distribution arm of an international media conglomerate, which ships an
average of 1bil units per year. We leverage internal data and public online
data harvested from IMDb, Rotten Tomatoes, and Google to prescribe operational
decisions that outperform baseline measures. Specifically, the data we collect,
leveraged by our methods, accounts for an 88\% improvement as measured by our
P.
Complex-Valued Hough Transforms for Circles
Authors: Marcelo Cicconet, Davi Geiger, Michael Werman
Date: 2015-02-02 00:00:00

This paper advocates the use of complex variables to represent votes in the
Hough transform for circle detection. Replacing the positive numbers
classically used in the parameter space of the Hough transforms by complex
numbers allows cancellation effects when adding up the votes. Cancellation and
the computation of shape likelihood via a complex number's magnitude square
lead to more robust solutions than the "classic" algorithms, as shown by
computational experiments on synthetic and real datasets.
Quantum Pairwise Symmetry: Applications in 2D Shape Analysis
Authors: Marcelo Cicconet, Davi Geiger, Michael Werman
Date: 2015-02-02 00:00:00

A pair of rooted tangents -- defining a quantum triangle -- with an
associated quantum wave of spin 1/2 is proposed as the primitive to represent
and compute symmetry. Measures of the spin characterize how "isosceles" or how
"degenerate" these triangles are -- which corresponds to their mirror or
parallel symmetry. We also introduce a complex-valued kernel to model
probability errors in the parameter space, which is more robust to noise and
clutter than the classical model.
Efficient model-based reinforcement learning for approximate online optimal
Authors: Rushikesh Kamalapurkar, Joel A. Rosenfeld, Warren E. Dixon
Date: 2015-02-09 00:00:00
Tasks: Model-based Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

In this paper the infinite horizon optimal regulation problem is solved
online for a deterministic control-affine nonlinear dynamical system using the
state following (StaF) kernel method to approximate the value function. Unlike
traditional methods that aim to approximate a function over a large compact
set, the StaF kernel method aims to approximate a function in a small
neighborhood of a state that travels within a compact set. Simulation results
demonstrate that stability and approximate optimality of the control system can
be achieved with significantly fewer basis functions than may be required for
global approximation methods.
Adaptive Random SubSpace Learning (RSSL) Algorithm for Prediction
Authors: Mohamed Elshrif, Ernest Fokoue
Date: 2015-02-09 00:00:00
Tasks: Prediction

We present a novel adaptive random subspace learning algorithm (RSSL) for
prediction purpose. This new framework is flexible where it can be adapted with
any learning technique. In this paper, we tested the algorithm for regression
and classification problems. In addition, we provide a variety of weighting
schemes to increase the robustness of the developed algorithm. These different
wighting flavors were evaluated on simulated as well as on real-world data sets
considering the cases where the ratio between features (attributes) and
instances (samples) is large and vice versa. The framework of the new algorithm
consists of many stages: first, calculate the weights of all features on the
data set using the correlation coefficient and F-statistic statistical
measurements. Second, randomly draw n samples with replacement from the data
set. Third, perform regular bootstrap sampling (bagging). Fourth, draw without
replacement the indices of the chosen variables. The decision was taken based
on the heuristic subspacing scheme. Fifth, call base learners and build the
model. Sixth, use the model for prediction purpose on test set of the data. The
results show the advancement of the adaptive RSSL algorithm in most of the
cases compared with the synonym (conventional) machine learning algorithms.
Domain-Adversarial Neural Networks
Authors: Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand
Date: 2014-12-15 00:00:00
Tasks: Denoising, Domain Adaptation, General Classification, Representation Learning, Sentiment Analysis

We introduce a new representation learning algorithm suited to the context of
domain adaptation, in which data at training and test time come from similar
but different distributions. Our algorithm is directly inspired by theory on
domain adaptation suggesting that, for effective domain transfer to be
achieved, predictions must be made based on a data representation that cannot
discriminate between the training (source) and test (target) domains. We
propose a training objective that implements this idea in the context of a
neural network, whose hidden layer is trained to be predictive of the
classification task, but uninformative as to the domain of the input. Our
experiments on a sentiment analysis classification benchmark, where the target
domain data available at training time is unlabeled, show that our neural
network for domain adaption algorithm has better performance than either a
standard neural network or an SVM, even if trained on input features extracted
with the state-of-the-art marginalized stacked denoising autoencoders of Chen
et al. (2012).
Deep Learning with Limited Numerical Precision
Authors: Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, Pritish Narayanan
Date: 2015-02-09 00:00:00
Tasks: Deep Learning, General Classification

Training of large-scale deep neural networks is often constrained by the
available computational resources. We study the effect of limited precision
data representation and computation on neural network training. Within the
context of low-precision fixed-point computations, we observe the rounding
scheme to play a crucial role in determining the network's behavior during
training. Our results show that deep networks can be trained using only 16-bit
wide fixed-point number representation when using stochastic rounding, and
incur little to no degradation in the classification accuracy. We also
demonstrate an energy-efficient hardware accelerator that implements
low-precision fixed-point arithmetic with stochastic rounding.
Unbiased Bayes for Big Data: Paths of Partial Posteriors
Authors: Heiko Strathmann, Dino Sejdinovic, Mark Girolami
Date: 2015-01-14 00:00:00
Tasks: Bayesian Inference

A key quantity of interest in Bayesian inference are expectations of
functions with respect to a posterior distribution. Markov Chain Monte Carlo is
a fundamental tool to consistently compute these expectations via averaging
samples drawn from an approximate posterior. However, its feasibility is being
challenged in the era of so called Big Data as all data needs to be processed
in every iteration. Realising that such simulation is an unnecessarily hard
problem if the goal is estimation, we construct a computationally scalable
methodology that allows unbiased estimation of the required expectations --
without explicit simulation from the full posterior. The scheme's variance is
finite by construction and straightforward to control, leading to algorithms
that are provably unbiased and naturally arrive at a desired error tolerance.
This is achieved at an average computational complexity that is sub-linear in
the size of the dataset and its free parameters are easy to tune. We
demonstrate the utility and generality of the methodology on a range of common
statistical models applied to large-scale benchmark and real-world datasets.
Evaluation of modelling approaches for predicting the spatial distribution of soil organic carbon stocks at the national scale
Authors: M. P. Martin, T. G. Orton, E. Lacarce, J. Meersmans, N. P. A. Saby, J. B. Paroissien, C. Jolivet, L. Boulonne, D. Arrouays
Date: 2015-02-09 00:00:00
Tasks: regression

Soil organic carbon (SOC) plays a major role in the global carbon budget. It
can act as a source or a sink of atmospheric carbon, thereby possibly
influencing the course of climate change. Improving the tools that model the
spatial distributions of SOC stocks at national scales is a priority, both for
monitoring changes in SOC and as an input for global carbon cycles studies. In
this paper, we compare and evaluate two recent and promising modelling
approaches. First, we considered several increasingly complex boosted
regression trees (BRT), a convenient and efficient multiple regression model
from the statistical learning field. Further, we considered a robust
geostatistical approach coupled to the BRT models. Testing the different
approaches was performed on the dataset from the French Soil Monitoring
Network, with a consistent cross-validation procedure. We showed that when a
limited number of predictors were included in the BRT model, the standalone BRT
predictions were significantly improved by robust geostatistical modelling of
the residuals. However, when data for several SOC drivers were included, the
standalone BRT model predictions were not significantly improved by
geostatistical modelling. Therefore, in this latter situation, the BRT
predictions might be considered adequate without the need for geostatistical
modelling, provided that i) care is exercised in model fitting and validating,
and ii) the dataset does not allow for modelling of local spatial
autocorrelations, as is the case for many national systematic sampling schemes.
The Adaptive Mean-Linkage Algorithm: A Bottom-Up Hierarchical Cluster Technique
Authors: H. M. de Oliveira
Date: 2015-02-09 00:00:00
Tasks: Clustering

In this paper a variant of the classical hierarchical cluster analysis is
reported. This agglomerative (bottom-up) cluster technique is referred to as
the Adaptive Mean-Linkage Algorithm. It can be interpreted as a linkage
algorithm where the value of the threshold is conveniently up-dated at each
interaction. The superiority of the adaptive clustering with respect to the
average-linkage algorithm follows because it achieves a good compromise on
threshold values: Thresholds based on the cut-off distance are sufficiently
small to assure the homogeneity and also large enough to guarantee at least a
pair of merging sets. This approach is applied to a set of possible
substituents in a chemical series.
Predicting Alzheimer's disease: a neuroimaging study with 3D convolutional neural networks
Authors: Adrien Payan, Giovanni Montana
Date: 2015-02-09 00:00:00

Pattern recognition methods using neuroimaging data for the diagnosis of
Alzheimer's disease have been the subject of extensive research in recent
years. In this paper, we use deep learning methods, and in particular sparse
autoencoders and 3D convolutional neural networks, to build an algorithm that
can predict the disease status of a patient, based on an MRI scan of the brain.
We report on experiments using the ADNI data set involving 2,265 historical
scans. We demonstrate that 3D convolutional neural networks outperform several
other classifiers reported in the literature and produce state-of-art results.
Efficient batchwise dropout training using submatrices
Authors: Ben Graham, Jeremy Reizenstein, Leigh Robinson
Date: 2015-02-09 00:00:00

Dropout is a popular technique for regularizing artificial neural networks.
Dropout networks are generally trained by minibatch gradient descent with a
dropout mask turning off some of the units---a different pattern of dropout is
applied to every sample in the minibatch. We explore a very simple alternative
to the dropout mask. Instead of masking dropped out units by setting them to
zero, we perform matrix multiplication using a submatrix of the weight
matrix---unneeded hidden units are never calculated. Performing dropout
batchwise, so that one pattern of dropout is used for each sample in a
minibatch, we can substantially reduce training times. Batchwise dropout can be
used with fully-connected and convolutional neural networks.