pwc-archive/papers-with-abstracts huggingface dataset:
Nonparametric Estimation of Renyi Divergence and Friends
Authors: Akshay Krishnamurthy, Kirthevasan Kandasamy, Barnabas Poczos, Larry Wasserman
Date: 2014-02-12 00:00:00

We consider nonparametric estimation of $L_2$, Renyi-$\alpha$ and
Tsallis-$\alpha$ divergences between continuous distributions. Our approach is
to construct estimators for particular integral functionals of two densities
and translate them into divergence estimators. For the integral functionals,
our estimators are based on corrections of a preliminary plug-in estimator. We
show that these estimators achieve the parametric convergence rate of
$n^{-1/2}$ when the densities' smoothness, $s$, are both at least $d/4$ where
$d$ is the dimension. We also derive minimax lower bounds for this problem
which confirm that $s > d/4$ is necessary to achieve the $n^{-1/2}$ rate of
convergence. We validate our theoretical guarantees with a number of
simulations.
Multilinguals and Wikipedia Editing
Authors: Scott A. Hale
Date: 2013-12-03 00:00:00
Tasks: Articles

This article analyzes one month of edits to Wikipedia in order to examine the
role of users editing multiple language editions (referred to as multilingual
users). Such multilingual users may serve an important function in diffusing
information across different language editions of the encyclopedia, and prior
work has suggested this could reduce the level of self-focus bias in each
edition. This study finds multilingual users are much more active than their
single-edition (monolingual) counterparts. They are found in all language
editions, but smaller-sized editions with fewer users have a higher percentage
of multilingual users than larger-sized editions. About a quarter of
multilingual users always edit the same articles in multiple languages, while
just over 40% of multilingual users edit different articles in different
languages. When non-English users do edit a second language edition, that
edition is most frequently English. Nonetheless, several regional and
linguistic cross-editing patterns are also present.
Policy Gradients for CVaR-Constrained MDPs
Authors: Prashanth L. A
Date: 2014-05-12 00:00:00

We study a risk-constrained version of the stochastic shortest path (SSP)
problem, where the risk measure considered is Conditional Value-at-Risk (CVaR).
We propose two algorithms that obtain a locally risk-optimal policy by
employing four tools: stochastic approximation, mini batches, policy gradients
and importance sampling. Both the algorithms incorporate a CVaR estimation
procedure, along the lines of Bardou et al. [2009], which in turn is based on
Rockafellar-Uryasev's representation for CVaR and utilize the likelihood ratio
principle for estimating the gradient of the sum of one cost function
(objective of the SSP) and the gradient of the CVaR of the sum of another cost
function (in the constraint of SSP). The algorithms differ in the manner in
which they approximate the CVaR estimates/necessary gradients - the first
algorithm uses stochastic approximation, while the second employ mini-batches
in the spirit of Monte Carlo methods. We establish asymptotic convergence of
both the algorithms. Further, since estimating CVaR is related to rare-event
simulation, we incorporate an importance sampling based variance reduction
scheme into our proposed algorithms.
CNN Features off-the-shelf: an Astounding Baseline for Recognition
Authors: Ali Sharif Razavian, Hossein Azizpour, Josephine Sullivan, Stefan Carlsson
Date: 2014-03-23 00:00:00
Tasks: Attribute, General Classification, image-classification, Image Classification, Image Retrieval, Retrieval, Scene Recognition

Recent results indicate that the generic descriptors extracted from the
convolutional neural networks are very powerful. This paper adds to the
mounting evidence that this is indeed the case. We report on a series of
experiments conducted for different recognition tasks using the publicly
available code and model of the \overfeat network which was trained to perform
object classification on ILSVRC13. We use features extracted from the \overfeat
network as a generic image representation to tackle the diverse range of
recognition tasks of object image classification, scene recognition, fine
grained recognition, attribute detection and image retrieval applied to a
diverse set of datasets. We selected these tasks and datasets as they gradually
move further away from the original task and data the \overfeat network was
trained to solve. Astonishingly, we report consistent superior results compared
to the highly tuned state-of-the-art systems in all the visual classification
tasks on various datasets. For instance retrieval it consistently outperforms
low memory footprint methods except for sculptures dataset. The results are
achieved using a linear SVM classifier (or $L2$ distance in case of retrieval)
applied to a feature representation of size 4096 extracted from a layer in the
net. The representations are further modified using simple augmentation
techniques e.g. jittering. The results strongly suggest that features obtained
from deep learning with convolutional nets should be the primary candidate in
most visual recognition tasks.
Stochastic Gradient Hamiltonian Monte Carlo
Authors: Tianqi Chen, Emily B. Fox, Carlos Guestrin
Date: 2014-02-17 00:00:00
Tasks: Efficient Exploration, Friction

Hamiltonian Monte Carlo (HMC) sampling methods provide a mechanism for
defining distant proposals with high acceptance probabilities in a
Metropolis-Hastings framework, enabling more efficient exploration of the state
space than standard random-walk proposals. The popularity of such methods has
grown significantly in recent years. However, a limitation of HMC methods is
the required gradient computation for simulation of the Hamiltonian dynamical
system-such computation is infeasible in problems involving a large sample size
or streaming data. Instead, we must rely on a noisy gradient estimate computed
from a subset of the data. In this paper, we explore the properties of such a
stochastic gradient HMC approach. Surprisingly, the natural implementation of
the stochastic approximation can be arbitrarily bad. To address this problem we
introduce a variant that uses second-order Langevin dynamics with a friction
term that counteracts the effects of the noisy gradient, maintaining the
desired target distribution as the invariant distribution. Results on simulated
data validate our theory. We also provide an application of our methods to a
classification task using neural networks and to online Bayesian matrix
factorization.
Structural Return Maximization for Reinforcement Learning
Authors: Joshua Joseph, Javier Velez, Nicholas Roy
Date: 2014-05-12 00:00:00
Tasks: Learning Theory, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Batch Reinforcement Learning (RL) algorithms attempt to choose a policy from
a designer-provided class of policies given a fixed set of training data.
Choosing the policy which maximizes an estimate of return often leads to
over-fitting when only limited data is available, due to the size of the policy
class in relation to the amount of data available. In this work, we focus on
learning policy classes that are appropriately sized to the amount of data
available. We accomplish this by using the principle of Structural Risk
Minimization, from Statistical Learning Theory, which uses Rademacher
complexity to identify a policy class that maximizes a bound on the return of
the best policy in the chosen policy class, given the available data. Unlike
similar batch RL approaches, our bound on return requires only extremely weak
assumptions on the true system.
Efficient Computation of the Well-Founded Semantics over Big Data
Authors: Ilias Tachmazidis, Grigoris Antoniou, Wolfgang Faber
Date: 2014-05-11 00:00:00

Data originating from the Web, sensor readings and social media result in
increasingly huge datasets. The so called Big Data comes with new scientific
and technological challenges while creating new opportunities, hence the
increasing interest in academia and industry. Traditionally, logic programming
has focused on complex knowledge structures/programs, so the question arises
whether and how it can work in the face of Big Data. In this paper, we examine
how the well-founded semantics can process huge amounts of data through mass
parallelization. More specifically, we propose and evaluate a parallel approach
using the MapReduce framework. Our experimental results indicate that our
approach is scalable and that well-founded semantics can be applied to billions
of facts. To the best of our knowledge, this is the first work that addresses
large scale nonmonotonic reasoning without the restriction of stratification
for predicates of arbitrary arity. To appear in Theory and Practice of Logic
Programming (TPLP).
Sentiment Analysis: A Survey
Authors: Rahul Tejwani
Date: 2014-05-11 00:00:00
Tasks: Opinion Mining, Sentiment Analysis, Survey

Sentiment analysis (also known as opinion mining) refers to the use of
natural language processing, text analysis and computational linguistics to
identify and extract subjective information in source materials. Mining
opinions expressed in the user generated content is a challenging yet
practically very useful problem. This survey would cover various approaches and
methodology used in Sentiment Analysis and Opinion Mining in general. The focus
would be on Internet text like, Product review, tweets and other social media.
Learning modular structures from network data and node variables
Authors: Elham Azizi, James E. Galagan, Edoardo M. Airoldi
Date: 2014-05-11 00:00:00

A standard technique for understanding underlying dependency structures among
a set of variables posits a shared conditional probability distribution for the
variables measured on individuals within a group. This approach is often
referred to as module networks, where individuals are represented by nodes in a
network, groups are termed modules, and the focus is on estimating the network
structure among modules. However, estimation solely from node-specific
variables can lead to spurious dependencies, and unverifiable structural
assumptions are often used for regularization. Here, we propose an extended
model that leverages direct observations about the network in addition to
node-specific variables. By integrating complementary data types, we avoid the
need for structural assumptions. We illustrate theoretical and practical
significance of the model and develop a reversible-jump MCMC learning procedure
for learning modules and model parameters. We demonstrate the method accuracy
in predicting modular structures from synthetic data and capability to learn
influence structures in twitter data and regulatory modules in the
Mycobacterium tuberculosis gene regulatory network.
A Review of Image Mosaicing Techniques
Authors: Dushyant Vaghela, Prof. Kapildev Naina
Date: 2014-05-11 00:00:00
Tasks: Image Registration

Image Mosaicing is a method of constructing multiple images of the same scene
into a larger image. The output of the image mosaic will be the union of two
input images. Image-mosaicing algorithms are used to get mosaiced image. Image
Mosaicing processed is basically divided in to 5 phases. Which includes;
Feature point extraction, Image registration, Homography computation, Warping
and Blending if Image. Various corner detection algorithm is being used for
Feature extraction. This corner produces an efficient and informative output
mosaiced image. Image mosaicing is widely used in creating 3D images, medical
imaging, computer vision, data from satellites, and military automatic target
recognition.
Fast SVM-based Feature Elimination Utilizing Data Radius, Hard-Margin, Soft-Margin
Authors: Yaman Aksu
Date: 2012-10-16 00:00:00

Margin maximization in the hard-margin sense, proposed as feature elimination
criterion by the MFE-LO method, is combined here with data radius utilization
to further aim to lower generalization error, as several published bounds and
bound-related formulations pertaining to lowering misclassification risk (or
error) pertain to radius e.g. product of squared radius and weight vector
squared norm. Additionally, we propose additional novel feature elimination
criteria that, while instead being in the soft-margin sense, too can utilize
data radius, utilizing previously published bound-related formulations for
approaching radius for the soft-margin sense, whereby e.g. a focus was on the
principle stated therein as "finding a bound whose minima are in a region with
small leave-one-out values may be more important than its tightness". These
additional criteria we propose combine radius utilization with a novel and
computationally low-cost soft-margin light classifier retraining approach we
devise named QP1; QP1 is the soft-margin alternative to the hard-margin LO. We
correct an error in the MFE-LO description, find MFE-LO achieves the highest
generalization accuracy among the previously published margin-based feature
elimination (MFE) methods, discuss some limitations of MFE-LO, and find our
novel methods herein outperform MFE-LO, attain lower test set classification
error rate. On several datasets that each both have a large number of features
and fall into the `large features few samples' dataset category, and on
datasets with lower (low-to-intermediate) number of features, our novel methods
give promising results. Especially, among our methods the tunable ones, that do
not employ (the non-tunable) LO approach, can be tuned more aggressively in the
future than herein, to aim to demonstrate for them even higher performance than
herein.
Image Restoration Using Joint Statistical Modeling in Space-Transform Domain
Authors: Jian Zhang, Debin Zhao, Ruiqin Xiong, Siwei Ma, Wen Gao
Date: 2014-05-11 00:00:00
Tasks: Deblurring, Image Deblurring, Image Inpainting, Image Restoration, Salt-And-Pepper Noise Removal

This paper presents a novel strategy for high-fidelity image restoration by
characterizing both local smoothness and nonlocal self-similarity of natural
images in a unified statistical manner. The main contributions are three-folds.
First, from the perspective of image statistics, a joint statistical modeling
(JSM) in an adaptive hybrid space-transform domain is established, which offers
a powerful mechanism of combining local smoothness and nonlocal self-similarity
simultaneously to ensure a more reliable and robust estimation. Second, a new
form of minimization functional for solving image inverse problem is formulated
using JSM under regularization-based framework. Finally, in order to make JSM
tractable and robust, a new Split-Bregman based algorithm is developed to
efficiently solve the above severely underdetermined inverse problem associated
with theoretical proof of convergence. Extensive experiments on image
inpainting, image deblurring and mixed Gaussian plus salt-and-pepper noise
removal applications verify the effectiveness of the proposed algorithm.
Off-policy reinforcement learning for $ H_\infty $ control design
Authors: Biao Luo, Huai-Ning Wu, TingWen Huang
Date: 2013-11-24 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

The $H_\infty$ control design problem is considered for nonlinear systems
with unknown internal system model. It is known that the nonlinear $ H_\infty $
control problem can be transformed into solving the so-called
Hamilton-Jacobi-Isaacs (HJI) equation, which is a nonlinear partial
differential equation that is generally impossible to be solved analytically.
Even worse, model-based approaches cannot be used for approximately solving HJI
equation, when the accurate system model is unavailable or costly to obtain in
practice. To overcome these difficulties, an off-policy reinforcement leaning
(RL) method is introduced to learn the solution of HJI equation from real
system data instead of mathematical system model, and its convergence is
proved. In the off-policy RL method, the system data can be generated with
arbitrary policies rather than the evaluating policy, which is extremely
important and promising for practical systems. For implementation purpose, a
neural network (NN) based actor-critic structure is employed and a least-square
NN weight update algorithm is derived based on the method of weighted
residuals. Finally, the developed NN-based off-policy RL method is tested on a
linear F16 aircraft plant, and further applied to a rotational/translational
actuator system.
Using Tabled Logic Programming to Solve the Petrobras Planning Problem
Authors: Roman Barták, Neng-Fa Zhou
Date: 2014-05-11 00:00:00

Tabling has been used for some time to improve efficiency of Prolog programs
by memorizing answered queries. The same idea can be naturally used to memorize
visited states during search for planning. In this paper we present a planner
developed in the Picat language to solve the Petrobras planning problem. Picat
is a novel Prolog-like language that provides pattern matching, deterministic
and non-deterministic rules, and tabling as its core modelling and solving
features. We demonstrate these capabilities using the Petrobras problem, where
the goal is to plan transport of cargo items from ports to platforms using
vessels with limited capacity. Monte Carlo Tree Search has been so far the best
technique to tackle this problem and we will show that by using tabling we can
achieve much better runtime efficiency and better plan quality.
Anomaly-Sensitive Dictionary Learning for Unsupervised Diagnostics of Solid Media
Authors: Jeffrey M. Druce, Jarvis D. Haupt, Stefano Gonella
Date: 2014-05-11 00:00:00
Tasks: Dictionary Learning

This paper proposes a strategy for the detection and triangulation of
structural anomalies in solid media. The method revolves around the
construction of sparse representations of the medium's dynamic response,
obtained by learning instructive dictionaries which form a suitable basis for
the response data. The resulting sparse coding problem is recast as a modified
dictionary learning task with additional spatial sparsity constraints enforced
on the atoms of the learned dictionaries, which provides them with a prescribed
spatial topology that is designed to unveil anomalous regions in the physical
domain. The proposed methodology is model agnostic, i.e., it forsakes the need
for a physical model and requires virtually no a priori knowledge of the
structure's material properties, as all the inferences are exclusively informed
by the data through the layers of information that are available in the
intrinsic salient structure of the material's dynamic response. This
characteristic makes the approach powerful for anomaly identification in
systems with unknown or heterogeneous property distribution, for which a model
is unsuitable or unreliable. The method is validated using both synthetically
Coordinate System Selection for Minimum Error Rate Training in Statistical Machine Translation
Authors: Chen Lijiang
Date: 2014-05-10 00:00:00
Tasks: Machine Translation, Translation

Minimum error rate training (MERT) is a widely used training procedure for
statistical machine translation. A general problem of this approach is that the
search space is easy to converge to a local optimum and the acquired weight set
is not in accord with the real distribution of feature functions. This paper
introduces coordinate system selection (RSS) into the search algorithm for
MERT. Contrary to previous approaches in which every dimension only corresponds
to one independent feature function, we create several coordinate systems by
moving one of the dimensions to a new direction. The basic idea is quite simple
but critical that the training procedure of MERT should be based on a
coordinate system formed by search directions but not directly on feature
functions. Experiments show that by selecting coordinate systems with tuning
set results, better results can be obtained without any other language
knowledge.
Functional Bandits
Authors: Long Tran-Thanh, Jia Yuan Yu
Date: 2014-05-10 00:00:00
Tasks: Decision Making, Management

We introduce the functional bandit problem, where the objective is to find an
arm that optimises a known functional of the unknown arm-reward distributions.
These problems arise in many settings such as maximum entropy methods in
natural language processing, and risk-averse decision-making, but current
best-arm identification techniques fail in these domains. We propose a new
approach, that combines functional estimation and arm elimination, to tackle
this problem. This method achieves provably efficient performance guarantees.
In addition, we illustrate this method on a number of important functionals in
risk management and information theory, and refine our generic theoretical
results in those cases.
A binary differential evolution algorithm learning from explored solutions
Authors: Yu Chen, Weicheng Xie, Xiufen Zou
Date: 2014-01-06 00:00:00
Tasks: Evolutionary Algorithms

Although real-coded differential evolution (DE) algorithms can perform well
on continuous optimization problems (CoOPs), it is still a challenging task to
design an efficient binary-coded DE algorithm. Inspired by the learning
mechanism of particle swarm optimization (PSO) algorithms, we propose a binary
learning differential evolution (BLDE) algorithm that can efficiently locate
the global optimal solutions by learning from the last population. Then, we
theoretically prove the global convergence of BLDE, and compare it with some
existing binary-coded evolutionary algorithms (EAs) via numerical experiments.
Numerical results show that BLDE is competitive to the compared EAs, and
meanwhile, further study is performed via the change curves of a renewal metric
and a refinement metric to investigate why BLDE cannot outperform some compared
EAs for several selected benchmark problems. Finally, we employ BLDE solving
the unit commitment problem (UCP) in power systems to show its applicability in
practical problems.
Optimal Learners for Multiclass Problems
Authors: Amit Daniely, Shai Shalev-Shwartz
Date: 2014-05-10 00:00:00
Tasks: Binary Classification, Open-Ended Question Answering

The fundamental theorem of statistical learning states that for binary
classification problems, any Empirical Risk Minimization (ERM) learning rule
has close to optimal sample complexity. In this paper we seek for a generic
optimal learner for multiclass prediction. We start by proving a surprising
result: a generic optimal multiclass learner must be improper, namely, it must
have the ability to output hypotheses which do not belong to the hypothesis
class, even though it knows that all the labels are generated by some
hypothesis from the class. In particular, no ERM learner is optimal. This
brings back the fundmamental question of "how to learn"? We give a complete
answer to this question by giving a new analysis of the one-inclusion
multiclass learner of Rubinstein et al (2006) showing that its sample
complexity is essentially optimal. Then, we turn to study the popular
hypothesis class of generalized linear classifiers. We derive optimal learners
that, unlike the one-inclusion algorithm, are computationally efficient.
Furthermore, we show that the sample complexity of these learners is better
than the sample complexity of the ERM rule, thus settling in negative an open
question due to Collins (2005).