pwc-archive/papers-with-abstracts huggingface dataset:
Bound Founded Answer Set Programming
Authors: Rehan Abdul Aziz
Date: 2014-05-14 00:00:00

Answer Set Programming (ASP) is a powerful modelling formalism that is very
efficient in solving combinatorial problems. ASP solvers implement the stable
model semantics that eliminates circular derivations between Boolean variables
from the solutions of a logic program. Due to this, ASP solvers are better
suited than propositional satisfiability (SAT) and Constraint Programming (CP)
solvers to solve a certain class of problems whose specification includes
inductive definitions such as reachability in a graph. On the other hand, ASP
solvers suffer from the grounding bottleneck that occurs due to their inability
to model finite domain variables. Furthermore, the existing stable model
semantics are not sufficient to disallow circular reasoning on the bounds of
numeric variables. An example where this is required is in modelling shortest
paths between nodes in a graph. Just as reachability can be encoded as an
inductive definition with one or more base cases and recursive rules, shortest
paths between nodes can also be modelled with similar base cases and recursive
rules for their upper bounds. This deficiency of stable model semantics
introduces another type of grounding bottleneck in ASP systems that cannot be
removed by naively merging ASP with CP solvers, but requires a theoretical
extension of the semantics from Booleans and normal rules to bounds over
numeric variables and more general rules. In this work, we propose Bound
Founded Answer Set Programming (BFASP) that resolves this issue and
consequently, removes all types of grounding bottleneck inherent in ASP
systems.
Grounding Bound Founded Answer Set Programs
Authors: Rehan Abdul Aziz, Geoffrey Chu, Peter James Stuckey
Date: 2014-05-14 00:00:00

To appear in Theory and Practice of Logic Programming (TPLP)
  Bound Founded Answer Set Programming (BFASP) is an extension of Answer Set
Programming (ASP) that extends stable model semantics to numeric variables.
While the theory of BFASP is defined on ground rules, in practice BFASP
programs are written as complex non-ground expressions. Flattening of BFASP is
a technique used to simplify arbitrary expressions of the language to a small
and well defined set of primitive expressions. In this paper, we first show how
we can flatten arbitrary BFASP rule expressions, to give equivalent BFASP
programs. Next, we extend the bottom-up grounding technique and magic set
transformation used by ASP to BFASP programs. Our implementation shows that for
BFASP problems, these techniques can significantly reduce the ground program
size, and improve subsequent solving.
A General Homogeneous Matrix Formulation to 3D Rotation Geometric Transformations
Authors: Feng Lu, Ziqiang Chen
Date: 2014-04-24 00:00:00
Tasks: Form

We present algebraic projective geometry definitions of 3D rotations so as to bridge a small gap between the applications and the definitions of 3D rotations in homogeneous matrix form. A general homogeneous matrix formulation to 3D rotation geometric transformations is proposed which suits for the cases when the rotation axis is unnecessarily through the coordinate system origin given their rotation axes and rotation angles. General three-dimensional rotation formula~\eqref{eqn:3D homogeneous roation} and~\eqref{eqn:3D rotation matrix vector Euclidean} similar to the Euler-Rodrigues formula were presented. The matrix-vector form of 3D rotation in Euclidean space is especially suited for numerical applications where gimbal lock is a concern.}
Group-based Sparse Representation for Image Restoration
Authors: Jian Zhang, Debin Zhao, Wen Gao
Date: 2014-05-14 00:00:00
Tasks: Compressive Sensing, Deblurring, Dictionary Learning, Image Deblurring, Image Inpainting, Image Restoration

Traditional patch-based sparse representation modeling of natural images
usually suffer from two problems. First, it has to solve a large-scale
optimization problem with high computational complexity in dictionary learning.
Second, each patch is considered independently in dictionary learning and
sparse coding, which ignores the relationship among patches, resulting in
inaccurate sparse coding coefficients. In this paper, instead of using patch as
the basic unit of sparse representation, we exploit the concept of group as the
basic unit of sparse representation, which is composed of nonlocal patches with
similar structures, and establish a novel sparse representation modeling of
natural images, called group-based sparse representation (GSR). The proposed
GSR is able to sparsely represent natural images in the domain of group, which
enforces the intrinsic local sparsity and nonlocal self-similarity of images
simultaneously in a unified framework. Moreover, an effective self-adaptive
dictionary learning method for each group with low complexity is designed,
rather than dictionary learning from natural images. To make GSR tractable and
robust, a split Bregman based technique is developed to solve the proposed
GSR-driven minimization problem for image restoration efficiently. Extensive
experiments on image inpainting, image deblurring and image compressive sensing
recovery manifest that the proposed GSR modeling outperforms many current
state-of-the-art schemes in both PSNR and visual perception.
An Agent-based Modeling Framework for Sociotechnical Simulation of Water Distribution Contamination Events
Authors: M. Ehsan Shafiee, Emily M. Zechman
Date: 2014-05-14 00:00:00

In the event that a bacteriological or chemical toxin is intro- duced to a
water distribution network, a large population of consumers may become exposed
to the contaminant. A contamination event may be poorly predictable dynamic
process due to the interactions of consumers and utility managers during an
event. Consumers that become aware of a threat may select protective actions
that change their water demands from typical demand patterns, and new hydraulic
conditions can arise that differ from conditions that are predicted when
demands are considered as exogenous inputs. Consequently, the movement of the
contaminant plume in the pipe network may shift from its expected trajectory. A
sociotechnical model is developed here to integrate agent-based models of
consumers with an engineering water distribution system model and capture the
dynamics between consumer behaviors and the water distribution system for
predicting contaminant transport and public exposure. Consumers are simulated
as agents with behaviors defined for water use activities, mobility,
word-of-mouth communication, and demand reduction, based on a set of rules
representing an agents autonomy and reaction to health impacts, the
environment, and the actions of other agents. As consumers decrease their water
use, the demand exerted on the water distribution system is updated; as the
flow directions and volumes shift in response, the location of the contaminant
plume is updated and the amount of contaminant consumed by each agent is
calculated. The framework is tested through simulating realistic contamination
scenarios for a virtual city and water distribution system.
Thresholding Classifiers to Maximize F1 Score
Authors: Zachary Chase Lipton, Charles Elkan, Balakrishnan Narayanaswamy
Date: 2014-02-08 00:00:00
Tasks: Binary Classification, Classification, Decision Making, General Classification

This paper provides new insight into maximizing F1 scores in the context of
binary classification and also in the context of multilabel classification. The
harmonic mean of precision and recall, F1 score is widely used to measure the
success of a binary classifier when one class is rare. Micro average, macro
average, and per instance average F1 scores are used in multilabel
classification. For any classifier that produces a real-valued output, we
derive the relationship between the best achievable F1 score and the
decision-making threshold that achieves this optimum. As a special case, if the
classifier outputs are well-calibrated conditional probabilities, then the
optimal threshold is half the optimal F1 score. As another special case, if the
classifier is completely uninformative, then the optimal behavior is to
classify all examples as positive. Since the actual prevalence of positive
examples typically is low, this behavior can be considered undesirable. As a
case study, we discuss the results, which can be surprising, of applying this
procedure when predicting 26,853 labels for Medline documents.
Querying Geometric Figures Using a Controlled Language, Ontological Graphs and Dependency Lattices
Authors: Yannis Haralambous, Pedro Quaresma
Date: 2014-03-10 00:00:00

Dynamic geometry systems (DGS) have become basic tools in many areas of
geometry as, for example, in education. Geometry Automated Theorem Provers
(GATP) are an active area of research and are considered as being basic tools
in future enhanced educational software as well as in a next generation of
mechanized mathematics assistants. Recently emerged Web repositories of
geometric knowledge, like TGTP and Intergeo, are an attempt to make the already
vast data set of geometric knowledge widely available. Considering the large
amount of geometric information already available, we face the need of a query
mechanism for descriptions of geometric constructions.
  In this paper we discuss two approaches for describing geometric figures
(declarative and procedural), and present algorithms for querying geometric
figures in declaratively and procedurally described corpora, by using a DGS or
a dedicated controlled natural language for queries.
Adaptive Monte Carlo via Bandit Allocation
Authors: James Neufeld, András György, Dale Schuurmans, Csaba Szepesvári
Date: 2014-05-13 00:00:00

We consider the problem of sequentially choosing between a set of unbiased
Monte Carlo estimators to minimize the mean-squared-error (MSE) of a final
combined estimate. By reducing this task to a stochastic multi-armed bandit
problem, we show that well developed allocation strategies can be used to
achieve an MSE that approaches that of the best estimator chosen in retrospect.
We then extend these developments to a scenario where alternative estimators
have different, possibly stochastic costs. The outcome is a new set of adaptive
Monte Carlo strategies that provide stronger guarantees than previous
approaches while offering practical advantages.
Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards
Authors: Omar Besbes, Yonatan Gur, Assaf Zeevi
Date: 2014-05-13 00:00:00

In a multi-armed bandit (MAB) problem a gambler needs to choose at each round of play one of K arms, each characterized by an unknown reward distribution. Reward realizations are only observed when an arm is selected, and the gambler's objective is to maximize his cumulative expected earnings over some given horizon of play T. To do this, the gambler needs to acquire information about arms (exploration) while simultaneously optimizing immediate rewards (exploitation); the price paid due to this trade off is often referred to as the regret, and the main question is how small can this price be as a function of the horizon length T. This problem has been studied extensively when the reward distributions do not change over time; an assumption that supports a sharp characterization of the regret, yet is often violated in practical settings. In this paper, we focus on a MAB formulation which allows for a broad range of temporal uncertainties in the rewards, while still maintaining mathematical tractability. We fully characterize the (regret) complexity of this class of MAB problems by establishing a direct link between the extent of allowable reward "variation" and the minimal achievable regret. Our analysis draws some connections between two rather disparate strands of literature: the adversarial and the stochastic MAB frameworks.
Communication Efficient Distributed Optimization using an Approximate Newton-type Method
Authors: Ohad Shamir, Nathan Srebro, Tong Zhang
Date: 2013-12-30 00:00:00
Tasks: Distributed Optimization, Stochastic Optimization, Vocal Bursts Type Prediction

We present a novel Newton-type method for distributed optimization, which is
particularly well suited for stochastic optimization and learning problems. For
quadratic objectives, the method enjoys a linear rate of convergence which
provably \emph{improves} with the data size, requiring an essentially constant
number of iterations under reasonable assumptions. We provide theoretical and
empirical evidence of the advantages of our method compared to other
approaches, such as one-shot parameter averaging and ADMM.
Effects of Sampling Methods on Prediction Quality. The Case of Classifying Land Cover Using Decision Trees
Authors: Ronald Hochreiter, Christoph Waldhauser
Date: 2014-05-13 00:00:00
Tasks: Classification, General Classification

Clever sampling methods can be used to improve the handling of big data and
increase its usefulness. The subject of this study is remote sensing,
specifically airborne laser scanning point clouds representing different
classes of ground cover. The aim is to derive a supervised learning model for
the classification using CARTs. In order to measure the effect of different
sampling methods on the classification accuracy, various experiments with
varying types of sampling methods, sample sizes, and accuracy metrics have been
designed. Numerical results for a subset of a large surveying project covering
the lower Rhine area in Germany are shown. General conclusions regarding
sampling design are drawn and presented.
Learning with many experts: model selection and sparsity
Authors: Rafael Izbicki, Rafael Bassi Stern
Date: 2014-05-13 00:00:00
Tasks: model, Model Selection

Experts classifying data are often imprecise. Recently, several models have
been proposed to train classifiers using the noisy labels generated by these
experts. How to choose between these models? In such situations, the true
labels are unavailable. Thus, one cannot perform model selection using the
standard versions of methods such as empirical risk minimization and cross
validation. In order to allow model selection, we present a surrogate loss and
provide theoretical guarantees that assure its consistency. Next, we discuss
how this loss can be used to tune a penalization which introduces sparsity in
the parameters of a traditional class of models. Sparsity provides more
parsimonious models and can avoid overfitting. Nevertheless, it has seldom been
discussed in the context of noisy labels due to the difficulty in model
selection and, therefore, in choosing tuning parameters. We apply these
techniques to several sets of simulated and real data.
How to Ask for a Favor: A Case Study on the Success of Altruistic Requests
Authors: Tim Althoff, Cristian Danescu-Niculescu-Mizil, Dan Jurafsky
Date: 2014-05-13 00:00:00

Requests are at the core of many social media systems such as question &
answer sites and online philanthropy communities. While the success of such
requests is critical to the success of the community, the factors that lead
community members to satisfy a request are largely unknown. Success of a
request depends on factors like who is asking, how they are asking, when are
they asking, and most critically what is being requested, ranging from small
favors to substantial monetary donations. We present a case study of altruistic
requests in an online community where all requests ask for the very same
contribution and do not offer anything tangible in return, allowing us to
disentangle what is requested from textual and social factors. Drawing from
social psychology literature, we extract high-level social features from text
that operationalize social relations between recipient and donor and
demonstrate that these extracted relations are predictive of success. More
specifically, we find that clearly communicating need through the narrative is
essential and that that linguistic indications of gratitude, evidentiality, and
generalized reciprocity, as well as high status of the asker further increase
the likelihood of success. Building on this understanding, we develop a model
that can predict the success of unseen requests, significantly improving over
several baselines. We link these findings to research in psychology on helping
behavior, providing a basis for further analysis of success in social media
systems.
Scalable sparse covariance estimation via self-concordance
Authors: Anastasios Kyrillidis, Rabeeh Karimi Mahabadi, Quoc Tran-Dinh, Volkan Cevher
Date: 2014-05-13 00:00:00

We consider the class of convex minimization problems, composed of a
self-concordant function, such as the $\log\det$ metric, a convex data fidelity
term $h(\cdot)$ and, a regularizing -- possibly non-smooth -- function
$g(\cdot)$. This type of problems have recently attracted a great deal of
interest, mainly due to their omnipresence in top-notch applications. Under
this \emph{locally} Lipschitz continuous gradient setting, we analyze the
convergence behavior of proximal Newton schemes with the added twist of a
probable presence of inexact evaluations. We prove attractive convergence rate
guarantees and enhance state-of-the-art optimization schemes to accommodate
such developments. Experimental results on sparse covariance estimation show
the merits of our algorithm, both in terms of recovery efficiency and
complexity.
SUNNY: a Lazy Portfolio Approach for Constraint Solving
Authors: Roberto Amadini, Maurizio Gabbrielli, Jacopo Mauro
Date: 2013-11-14 00:00:00

*** To appear in Theory and Practice of Logic Programming (TPLP) ***
  Within the context of constraint solving, a portfolio approach allows one to
exploit the synergy between different solvers in order to create a globally
better solver. In this paper we present SUNNY: a simple and flexible algorithm
that takes advantage of a portfolio of constraint solvers in order to compute
--- without learning an explicit model --- a schedule of them for solving a
given Constraint Satisfaction Problem (CSP). Motivated by the performance
reached by SUNNY vs. different simulations of other state of the art
approaches, we developed sunny-csp, an effective portfolio solver that exploits
the underlying SUNNY algorithm in order to solve a given CSP. Empirical tests
conducted on exhaustive benchmarks of MiniZinc models show that the actual
performance of SUNNY conforms to the predictions. This is encouraging both for
improving the power of CSP portfolio solvers and for trying to export them to
fields such as Answer Set Programming and Constraint Logic Programming.
Rate of Convergence and Error Bounds for LSTD($λ$)
Authors: Manel Tagorti, Bruno Scherrer
Date: 2014-05-13 00:00:00

We consider LSTD($\lambda$), the least-squares temporal-difference algorithm
with eligibility traces algorithm proposed by Boyan (2002). It computes a
linear approximation of the value function of a fixed policy in a large Markov
Decision Process. Under a $\beta$-mixing assumption, we derive, for any value
of $\lambda \in (0,1)$, a high-probability estimate of the rate of convergence
of this algorithm to its limit. We deduce a high-probability bound on the error
of this algorithm, that extends (and slightly improves) that derived by Lazaric
et al. (2012) in the specific case where $\lambda=0$. In particular, our
analysis sheds some light on the choice of $\lambda$ with respect to the
quality of the chosen linear space and the number of samples, that complies
with simulations.
Randomized Nonlinear Component Analysis
Authors: David Lopez-Paz, Suvrit Sra, Alex Smola, Zoubin Ghahramani, Bernhard Schölkopf
Date: 2014-02-01 00:00:00
Tasks: Clustering

Classical methods such as Principal Component Analysis (PCA) and Canonical
Correlation Analysis (CCA) are ubiquitous in statistics. However, these
techniques are only able to reveal linear relationships in data. Although
nonlinear variants of PCA and CCA have been proposed, these are computationally
prohibitive in the large scale.
  In a separate strand of recent research, randomized methods have been
proposed to construct features that help reveal nonlinear patterns in data. For
basic tasks such as regression or classification, random features exhibit
little or no loss in performance, while achieving drastic savings in
computational requirements.
  In this paper we leverage randomness to design scalable new variants of
nonlinear PCA and CCA; our ideas extend to key multivariate analysis tools such
as spectral clustering or LDA. We demonstrate our algorithms through
experiments on real-world data, on which we compare against the
state-of-the-art. A simple R implementation of the presented algorithms is
provided.
Locally Boosted Graph Aggregation for Community Detection
Authors: Jeremy Kun, Rajmonda Caceres, Kevin Carter
Date: 2014-05-13 00:00:00
Tasks: Community Detection, Relational Reasoning

Learning the right graph representation from noisy, multi-source data has
garnered significant interest in recent years. A central tenet of this problem
is relational learning. Here the objective is to incorporate the partial
information each data source gives us in a way that captures the true
underlying relationships. To address this challenge, we present a general,
boosting-inspired framework for combining weak evidence of entity associations
into a robust similarity metric. Building on previous work, we explore the
extent to which different local quality measurements yield graph
representations that are suitable for community detection. We present empirical
results on a variety of datasets demonstrating the utility of this framework,
especially with respect to real datasets where noise and scale present serious
challenges. Finally, we prove a convergence theorem in an ideal setting and
outline future research into other application domains.
An Intelligent Pixel Replication Technique by Binary Decomposition for Digital Image Zooming
Authors: Kaeser M Sabrin, M Haider Ali
Date: 2014-05-13 00:00:00

Image zooming is the process of enlarging the spatial resolution of a given
digital image. We present a novel technique that intelligently modifies the
classical pixel replication method for zooming. Our method decomposes a given
image into layer of binary images, interpolates them by magnifying the binary
patterns preserving their geometric shape and finally aggregates them all to
obtain the zoomed image. Although the quality of our zoomed images is much
higher than that of nearest neighbor and bilinear interpolation and comparable
with bicubic interpolation, the running time of our technique is extremely fast
like nearest neighbor interpolation and much faster than bilinear and bicubic
interpolation.
D numbers theory: a generalization of Dempster-Shafer evidence theory
Authors: Yong Deng
Date: 2014-05-13 00:00:00
Tasks: Decision Making

Efficient modeling of uncertain information in real world is still an open
issue. Dempster-Shafer evidence theory is one of the most commonly used
methods. However, the Dempster-Shafer evidence theory has the assumption that
the hypothesis in the framework of discernment is exclusive of each other. This
condition can be violated in real applications, especially in linguistic
decision making since the linguistic variables are not exclusive of each others
essentially. In this paper, a new theory, called as D numbers theory (DNT), is
systematically developed to address this issue. The combination rule of two D
numbers is presented. An coefficient is defined to measure the exclusive degree
among the hypotheses in the framework of discernment. The combination rule of
two D numbers is presented. If the exclusive coefficient is one which means
that the hypothesis in the framework of discernment is exclusive of each other
totally, the D combination is degenerated as the classical Dempster combination
rule. Finally, a linguistic variables transformation of D numbers is presented
to make a decision. A numerical example on linguistic evidential decision
making is used to illustrate the efficiency of the proposed D numbers theory.