pwc-archive/papers-with-abstracts huggingface dataset:
Dynamics of Belief: Abduction, Horn Knowledge Base And Database Updates
Authors: Radhakrishnan Delhibabu
Date: 2015-01-25 00:00:00
Tasks: Negation

The dynamics of belief and knowledge is one of the major components of any
autonomous system that should be able to incorporate new pieces of information.
In order to apply the rationality result of belief dynamics theory to various
practical problems, it should be generalized in two respects: first it should
allow a certain part of belief to be declared as immutable; and second, the
belief state need not be deductively closed. Such a generalization of belief
dynamics, referred to as base dynamics, is presented in this paper, along with
the concept of a generalized revision algorithm for knowledge bases (Horn or
Horn logic with stratified negation). We show that knowledge base dynamics has
an interesting connection with kernel change via hitting set and abduction. In
this paper, we show how techniques from disjunctive logic programming can be
used for efficient (deductive) database updates. The key idea is to transform
the given database together with the update request into a disjunctive
(datalog) logic program and apply disjunctive techniques (such as minimal model
reasoning) to solve the original update problem. The approach extends and
integrates standard techniques for efficient query answering and integrity
checking. The generation of a hitting set is carried out through a hyper
tableaux calculus and magic set that is focused on the goal of minimality. The
present paper provides a comparative study of view update algorithms in
rational approach. For, understand the basic concepts with abduction, we
provide an abductive framework for knowledge base dynamics. Finally, we
demonstrate how belief base dynamics can provide an axiomatic characterization
for insertion a view atom to the database. We give a quick overview of the main
operators for belief change, in particular, belief update versus database
update.
A General Preprocessing Method for Improved Performance of Epipolar Geometry Estimation Algorithms
Authors: Maria Kushnir, Ilan Shimshoni
Date: 2015-01-27 00:00:00

In this paper a deterministic preprocessing algorithm is presented, whose
output can be given as input to most state-of-the-art epipolar geometry
estimation algorithms, improving their results considerably. They are now able
to succeed on hard cases for which they failed before. The algorithm consists
of three steps, whose scope changes from local to global. In the local step it
extracts from a pair of images local features (e.g. SIFT). Similar features
from each image are clustered and the clusters are matched yielding a large
number of putative matches. In the second step pairs of spatially close
features (called 2keypoints) are matched and ranked by a classifier. The
2keypoint matches with the highest ranks are selected. In the global step, from
each two 2keypoint matches a fundamental matrix is computed. As quite a few of
the matrices are generated from correct matches they are used to rank the
putative matches found in the first step. For each match the number of
fundamental matrices, for which it approximately satisfies the epipolar
constraint, is calculated. This set of matches is combined with the putative
matches generated by standard methods and their probabilities to be correct are
estimated by a classifier. These are then given as input to state-of-the-art
epipolar geometry estimation algorithms such as BEEM, BLOGS and USAC yielding
much better results than the original algorithms. This was shown in extensive
testing performed on almost 900 image pairs from six publicly available
data-sets.
Inclusion within Continuous Belief Functions
Authors: Dorra Attiaoui, Pierre-Emmanuel Doré, Arnaud Martin, Boutheina Ben Yaghlane
Date: 2015-01-27 00:00:00
Tasks: Relation

Defining and modeling the relation of inclusion between continuous belief
function may be considered as an important operation in order to study their
behaviors. Within this paper we will propose and present two forms of
inclusion: The strict and the partial one. In order to develop this relation,
we will study the case of consonant belief function. To do so, we will simulate
normal distributions allowing us to model and analyze these relations. Based on
that, we will determine the parameters influencing and characterizing the two
forms of inclusion.
Risk Estimation Without Using Stein's Lemma -- Application to Image Denoising
Authors: Sagar Venkatesh Gubbi, Chandra Sekhar Seelamantula
Date: 2014-12-06 00:00:00
Tasks: Denoising, GPU, Image Denoising, LEMMA

We address the problem of image denoising in additive white noise without
placing restrictive assumptions on its statistical distribution. In the recent
literature, specific noise distributions have been considered and
correspondingly, optimal denoising techniques have been developed. One of the
successful approaches for denoising relies on the notion of unbiased risk
estimation, which enables one to obtain a useful substitute for the mean-square
error. For the case of additive white Gaussian noise contamination, the risk
estimation procedure relies on Stein's lemma. Sophisticated wavelet-based
denoising techniques, which are essentially nonlinear, have been developed with
the help of the lemma. We show that, for linear, shift-invariant denoisers, it
is possible to obtain unbiased risk estimates of the mean-square error without
using Stein's lemma. An interesting consequence of this development is that the
unbiased risk estimator becomes agnostic to the statistical distribution of the
noise. As a proof of principle, we show how the new methodology can be used to
optimize the parameters of a simple Gaussian smoother. By locally adapting the
parameters of the Gaussian smoother, we obtain a shift-variant smoother, which
has a denoising performance (quantified by the improvement in peak
signal-to-noise ratio (PSNR)) that is competitive to far more sophisticated
methods reported in the literature. The proposed solution exhibits considerable
parallelism, which we exploit in a Graphics Processing Unit (GPU)
implementation.
Inferring and Learning from Neuronal Correspondences
Authors: Ashish Kapoor, E. Paxon Frady, Stefanie Jegelka, William B. Kristan, Eric Horvitz
Date: 2015-01-23 00:00:00
Tasks: Decision Making

We introduce and study methods for inferring and learning from
correspondences among neurons. The approach enables alignment of data from
distinct multiunit studies of nervous systems. We show that the methods for
inferring correspondences combine data effectively from cross-animal studies to
make joint inferences about behavioral decision making that are not possible
with the data from a single animal. We focus on data collection, machine
learning, and prediction in the representative and long-studied invertebrate
nervous system of the European medicinal leech. Acknowledging the computational
intractability of the general problem of identifying correspondences among
neurons, we introduce efficient computational procedures for matching neurons
across animals. The methods include techniques that adjust for missing cells or
additional cells in the different data sets that may reflect biological or
experimental variation. The methods highlight the value harnessing inference
and learning in new kinds of computational microscopes for multiunit
neurobiological studies.
Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
Authors: Branislav Kveton, Zheng Wen, Azin Ashkan, Csaba Szepesvari
Date: 2014-10-03 00:00:00

A stochastic combinatorial semi-bandit is an online learning problem where at
each step a learning agent chooses a subset of ground items subject to
constraints, and then observes stochastic weights of these items and receives
their sum as a payoff. In this paper, we close the problem of computationally
and sample efficient learning in stochastic combinatorial semi-bandits. In
particular, we analyze a UCB-like algorithm for solving the problem, which is
known to be computationally efficient; and prove $O(K L (1 / \Delta) \log n)$
and $O(\sqrt{K L n \log n})$ upper bounds on its $n$-step regret, where $L$ is
the number of ground items, $K$ is the maximum number of chosen items, and
$\Delta$ is the gap between the expected returns of the optimal and best
suboptimal solutions. The gap-dependent bound is tight up to a constant factor
and the gap-free bound is tight up to a polylogarithmic factor.
High Dimensional Expectation-Maximization Algorithm: Statistical Optimization and Asymptotic Normality
Authors: Zhaoran Wang, Quanquan Gu, Yang Ning, Han Liu
Date: 2014-12-30 00:00:00
Tasks: parameter estimation, Vocal Bursts Intensity Prediction

We provide a general theory of the expectation-maximization (EM) algorithm
for inferring high dimensional latent variable models. In particular, we make
two contributions: (i) For parameter estimation, we propose a novel high
dimensional EM algorithm which naturally incorporates sparsity structure into
parameter estimation. With an appropriate initialization, this algorithm
converges at a geometric rate and attains an estimator with the (near-)optimal
statistical rate of convergence. (ii) Based on the obtained estimator, we
propose new inferential procedures for testing hypotheses and constructing
confidence intervals for low dimensional components of high dimensional
parameters. For a broad family of statistical models, our framework establishes
the first computationally feasible approach for optimal estimation and
asymptotic inference in high dimensions. Our theory is supported by thorough
numerical results.
Optimal computational and statistical rates of convergence for sparse nonconvex learning problems
Authors: Zhaoran Wang, Han Liu, Tong Zhang
Date: 2013-06-20 00:00:00
Tasks: regression

We provide theoretical analysis of the statistical and computational
properties of penalized $M$-estimators that can be formulated as the solution
to a possibly nonconvex optimization problem. Many important estimators fall in
this category, including least squares regression with nonconvex
regularization, generalized linear models with nonconvex regularization and
sparse elliptical random design regression. For these problems, it is
intractable to calculate the global solution due to the nonconvex formulation.
In this paper, we propose an approximate regularization path-following method
for solving a variety of learning problems with nonconvex objective functions.
Under a unified analytic framework, we simultaneously provide explicit
statistical and computational rates of convergence for any local solution
attained by the algorithm. Computationally, our algorithm attains a global
geometric rate of convergence for calculating the full regularization path,
which is optimal among all first-order algorithms. Unlike most existing methods
that only attain geometric rates of convergence for one single regularization
parameter, our algorithm calculates the full regularization path with the same
iteration complexity. In particular, we provide a refined iteration complexity
bound to sharply characterize the performance of each stage along the
regularization path. Statistically, we provide sharp sample complexity analysis
for all the approximate local solutions along the regularization path. In
particular, our analysis improves upon existing results by providing a more
refined sample complexity bound as well as an exact support recovery result for
the final estimator. These results show that the final estimator attains an
oracle statistical property due to the usage of nonconvex penalty.
Two-stage Sampled Learning Theory on Distributions
Authors: Zoltan Szabo, Arthur Gretton, Barnabas Poczos, Bharath Sriperumbudur
Date: 2014-02-07 00:00:00
Tasks: Density Estimation, Learning Theory, Open-Ended Question Answering, regression, Vocal Bursts Valence Prediction

We focus on the distribution regression problem: regressing to a real-valued
response from a probability distribution. Although there exist a large number
of similarity measures between distributions, very little is known about their
generalization performance in specific learning tasks. Learning problems
formulated on distributions have an inherent two-stage sampled difficulty: in
practice only samples from sampled distributions are observable, and one has to
build an estimate on similarities computed between sets of points. To the best
of our knowledge, the only existing method with consistency guarantees for
distribution regression requires kernel density estimation as an intermediate
step (which suffers from slow convergence issues in high dimensions), and the
domain of the distributions to be compact Euclidean. In this paper, we provide
theoretical guarantees for a remarkably simple algorithmic alternative to solve
the distribution regression problem: embed the distributions to a reproducing
kernel Hilbert space, and learn a ridge regressor from the embeddings to the
outputs. Our main contribution is to prove the consistency of this technique in
the two-stage sampled setting under mild conditions (on separable, topological
domains endowed with kernels). For a given total number of observations, we
derive convergence rates as an explicit function of the problem difficulty. As
a special case, we answer a 15-year-old open question: we establish the
consistency of the classical set kernel [Haussler, 1999; Gartner et. al, 2002]
in regression, and cover more recent kernels on distributions, including those
due to [Christmann and Steinwart, 2010].
Online Nonparametric Regression with General Loss Functions
Authors: Alexander Rakhlin, Karthik Sridharan
Date: 2015-01-26 00:00:00
Tasks: regression

This paper establishes minimax rates for online regression with arbitrary
classes of functions and general losses. We show that below a certain threshold
for the complexity of the function class, the minimax rates depend on both the
curvature of the loss function and the sequential complexities of the class.
Above this threshold, the curvature of the loss does not affect the rates.
Furthermore, for the case of square loss, our results point to the interesting
phenomenon: whenever sequential and i.i.d. empirical entropies match, the rates
for statistical and online learning are the same.
  In addition to the study of minimax regret, we derive a generic forecaster
that enjoys the established optimal rates. We also provide a recipe for
designing online prediction algorithms that can be computationally efficient
for certain problems. We illustrate the techniques by deriving existing and new
forecasters for the case of finite experts and for online linear regression.
Consensus Message Passing for Layered Graphical Models
Authors: Varun Jampani, S. M. Ali Eslami, Daniel Tarlow, Pushmeet Kohli, John Winn
Date: 2014-10-27 00:00:00

Generative models provide a powerful framework for probabilistic reasoning.
However, in many domains their use has been hampered by the practical
difficulties of inference. This is particularly the case in computer vision,
where models of the imaging process tend to be large, loopy and layered. For
this reason bottom-up conditional models have traditionally dominated in such
domains. We find that widely-used, general-purpose message passing inference
algorithms such as Expectation Propagation (EP) and Variational Message Passing
(VMP) fail on the simplest of vision models. With these models in mind, we
introduce a modification to message passing that learns to exploit their
layered structure by passing 'consensus' messages that guide inference towards
good solutions. Experiments on a variety of problems show that the proposed
technique leads to significantly more accurate inference results, not only when
compared to standard EP and VMP, but also when compared to competitive
bottom-up conditional models.
Measuring academic influence: Not all citations are equal
Authors: Xiaodan Zhu, Peter Turney, Daniel Lemire, André Vellino
Date: 2015-01-26 00:00:00
Tasks: All, feature selection

The importance of a research article is routinely measured by counting how
many times it has been cited. However, treating all citations with equal weight
ignores the wide variety of functions that citations perform. We want to
automatically identify the subset of references in a bibliography that have a
central academic influence on the citing paper. For this purpose, we examine
the effectiveness of a variety of features for determining the academic
influence of a citation. By asking authors to identify the key references in
their own work, we created a data set in which citations were labeled according
to their academic influence. Using automatic feature selection with supervised
machine learning, we found a model for predicting academic influence that
achieves good performance on this data set using only four features. The best
features, among those we evaluated, were those based on the number of times a
reference is mentioned in the body of a citing paper. The performance of these
features inspired us to design an influence-primed h-index (the hip-index).
Unlike the conventional h-index, it weights citations by how many times a
reference is mentioned. According to our experiments, the hip-index is a better
indicator of researcher performance than the conventional h-index.
Multiscale statistical testing for connectome-wide association studies in fMRI
Authors: P. Bellec, Y. Benhajali, F. Carbonell, C. Dansereau, G. Albouy, M. Pelland, C. Craddock, O. Collignon, J. Doyon, E. Stip, P. Orban
Date: 2014-09-07 00:00:00

Alterations in brain connectivity have been associated with a variety of
clinical disorders using functional magnetic resonance imaging (fMRI). We
investigated empirically how the number of brain parcels (or scale) impacted
the results of a mass univariate general linear model (GLM) on connectomes. The
brain parcels used as nodes in the connectome analysis were functionnally
defined by a group cluster analysis. We first validated that a classic
Benjamini-Hochberg procedure with parametric GLM tests did control
appropriately the false-discovery rate (FDR) at a given scale. We then observed
on realistic simulations that there was no substantial inflation of the FDR
across scales, as long as the FDR was controlled independently within each
scale, and the presence of true associations could be established using an
omnibus permutation test combining all scales. Second, we observed both on
simulations and on three real resting-state fMRI datasets (schizophrenia,
congenital blindness, motor practice) that the rate of discovery varied
markedly as a function of scales, and was relatively higher for low scales,
below 25. Despite the differences in discovery rate, the statistical maps
derived at different scales were generally very consistent in the three real
datasets. Some seeds still showed effects better observed around 50,
illustrating the potential benefits of multiscale analysis. On real data, the
statistical maps agreed well with the existing literature. Overall, our results
support that the multiscale GLM connectome analysis with FDR is statistically
valid and can capture biologically meaningful effects in a variety of
experimental conditions.
Every LWF and AMP chain graph originates from a set of causal models
Authors: Jose M. Peña
Date: 2013-12-10 00:00:00
Tasks: Selection bias

This paper aims at justifying LWF and AMP chain graphs by showing that they
do not represent arbitrary independence models. Specifically, we show that
every chain graph is inclusion optimal wrt the intersection of the independence
models represented by a set of directed and acyclic graphs under conditioning.
This implies that the independence model represented by the chain graph can be
accounted for by a set of causal models that are subject to selection bias,
which in turn can be accounted for by a system that switches between different
regimes or configurations.
A* Sampling
Authors: Chris J. Maddison, Daniel Tarlow, Tom Minka
Date: 2014-10-31 00:00:00
Proceeding: NeurIPS 2014 12

The problem of drawing samples from a discrete distribution can be converted
into a discrete optimization problem. In this work, we show how sampling from a
continuous distribution can be converted into an optimization problem over
continuous space. Central to the method is a stochastic process recently
described in mathematical statistics that we call the Gumbel process. We
present a new construction of the Gumbel process and A* sampling, a practical
generic sampling algorithm that searches for the maximum of a Gumbel process
using A* search. We analyze the correctness and convergence time of A* sampling
and demonstrate empirically that it makes more efficient use of bound and
likelihood evaluations than the most closely related adaptive rejection
sampling-based algorithms.
Parallel Graph Partitioning for Complex Networks
Authors: Henning Meyerhenke, Peter Sanders, Christian Schulz
Date: 2014-04-18 00:00:00
Tasks: Clustering, Graph Clustering, graph partitioning

Processing large complex networks like social networks or web graphs has
recently attracted considerable interest. In order to do this in parallel, we
need to partition them into pieces of about equal size. Unfortunately, previous
parallel graph partitioners originally developed for more regular mesh-like
networks do not work well for these networks. This paper addresses this problem
by parallelizing and adapting the label propagation technique originally
developed for graph clustering. By introducing size constraints, label
propagation becomes applicable for both the coarsening and the refinement phase
of multilevel graph partitioning. We obtain very high quality by applying a
highly parallel evolutionary algorithm to the coarsened graph. The resulting
system is both more scalable and achieves higher quality than state-of-the-art
systems like ParMetis or PT-Scotch. For large complex networks the performance
differences are very big. For example, our algorithm can partition a web graph
with 3.3 billion edges in less than sixteen seconds using 512 cores of a high
performance cluster while producing a high quality partition -- none of the
competing systems can handle this graph on our system.
On a Family of Decomposable Kernels on Sequences
Authors: Andrea Baisero, Florian T. Pokorny, Carl Henrik Ek
Date: 2015-01-26 00:00:00
Tasks: Dynamic Time Warping, General Classification

In many applications data is naturally presented in terms of orderings of
some basic elements or symbols. Reasoning about such data requires a notion of
similarity capable of handling sequences of different lengths. In this paper we
describe a family of Mercer kernel functions for such sequentially structured
data. The family is characterized by a decomposable structure in terms of
symbol-level and structure-level similarities, representing a specific
combination of kernels which allows for efficient computation. We provide an
experimental evaluation on sequential classification tasks comparing kernels
from our family of kernels to a state of the art sequence kernel called the
Global Alignment kernel which has been shown to outperform Dynamic Time Warping