pwc-archive/papers-with-abstracts huggingface dataset:
Adaptive Stochastic Resource Control: A Machine Learning Approach
Authors: Balázs Csanád Csáji, László Monostori
Date: 2014-01-15 00:00:00
Tasks: BIG-bench Machine Learning, Clustering, Management, Q-Learning, Scheduling

The paper investigates stochastic resource allocation problems with scarce,
reusable resources and non-preemtive, time-dependent, interconnected tasks.
This approach is a natural generalization of several standard resource
management problems, such as scheduling and transportation problems. First,
reactive solutions are considered and defined as control policies of suitably
reformulated Markov decision processes (MDPs). We argue that this reformulation
has several favorable properties, such as it has finite state and action
spaces, it is aperiodic, hence all policies are proper and the space of control
policies can be safely restricted. Next, approximate dynamic programming (ADP)
methods, such as fitted Q-learning, are suggested for computing an efficient
control policy. In order to compactly maintain the cost-to-go function, two
representations are studied: hash tables and support vector regression (SVR),
particularly, nu-SVRs. Several additional improvements, such as the application
of limited-lookahead rollout algorithms in the initial phases, action space
decomposition, task clustering and distributed sampling are investigated, too.
Finally, experimental results on both benchmark and industry-related data are
presented.
A Rigorously Bayesian Beam Model and an Adaptive Full Scan Model for Range Finders in Dynamic Environments
Authors: Tinne De Laet, Joris De Schutter, Herman Bruyninckx
Date: 2014-01-15 00:00:00
Tasks: model

This paper proposes and experimentally validates a Bayesian network model of
a range finder adapted to dynamic environments. All modeling assumptions are
rigorously explained, and all model parameters have a physical interpretation.
This approach results in a transparent and intuitive model. With respect to the
state of the art beam model this paper: (i) proposes a different functional
form for the probability of range measurements caused by unmodeled objects,
(ii) intuitively explains the discontinuity encountered in te state of the art
beam model, and (iii) reduces the number of model parameters, while maintaining
the same representational power for experimental data. The proposed beam model
is called RBBM, short for Rigorously Bayesian Beam Model. A maximum likelihood
and a variational Bayesian estimator (both based on expectation-maximization)
are proposed to learn the model parameters.
  Furthermore, the RBBM is extended to a full scan model in two steps: first,
to a full scan model for static environments and next, to a full scan model for
general, dynamic environments. The full scan model accounts for the dependency
between beams and adapts to the local sample density when using a particle
filter. In contrast to Gaussian-based state of the art models, the proposed
full scan model uses a sample-based approximation. This sample-based
approximation enables handling dynamic environments and capturing
multi-modality, which occurs even in simple static environments.
Compositional Belief Update
Authors: James Delgrande, Yi Jin, Francis Jeffry Pelletier
Date: 2014-01-15 00:00:00
Tasks: Sentence

In this paper we explore a class of belief update operators, in which the
definition of the operator is compositional with respect to the sentence to be
added. The goal is to provide an update operator that is intuitive, in that its
definition is based on a recursive decomposition of the update sentences
structure, and that may be reasonably implemented. In addressing update, we
first provide a definition phrased in terms of the models of a knowledge base.
While this operator satisfies a core group of the benchmark Katsuno-Mendelzon
update postulates, not all of the postulates are satisfied. Other
Katsuno-Mendelzon postulates can be obtained by suitably restricting the
syntactic form of the sentence for update, as we show. In restricting the
syntactic form of the sentence for update, we also obtain a hierarchy of update
operators with Winsletts standard semantics as the most basic interesting
approach captured. We subsequently give an algorithm which captures this
approach; in the general case the algorithm is exponential, but with some
not-unreasonable assumptions we obtain an algorithm that is linear in the size
of the knowledge base. Hence the resulting approach has much better complexity
characteristics than other operators in some situations. We also explore other
compositional belief change operators: erasure is developed as a dual operator
to update; we show that a forget operator is definable in terms of update; and
we give a definition of the compositional revision operator. We obtain that
compositional revision, under the most natural definition, yields the Satoh
revision operator.
A Unifying Framework for Structural Properties of CSPs: Definitions, Complexity, Tractability
Authors: Lucas Bordeaux, Marco Cadoli, Toni Mancini
Date: 2014-01-15 00:00:00

Literature on Constraint Satisfaction exhibits the definition of several
structural properties that can be possessed by CSPs, like (in)consistency,
substitutability or interchangeability. Current tools for constraint solving
typically detect such properties efficiently by means of incomplete yet
effective algorithms, and use them to reduce the search space and boost search.
  In this paper, we provide a unifying framework encompassing most of the
properties known so far, both in CSP and other fields literature, and shed
light on the semantical relationships among them. This gives a unified and
comprehensive view of the topic, allows new, unknown, properties to emerge, and
clarifies the computational complexity of the various detection problems.
  In particular, among the others, two new concepts, fixability and
removability emerge, that come out to be the ideal characterisations of values
that may be safely assigned or removed from a variables domain, while
preserving problem satisfiability. These two notions subsume a large number of
known properties, including inconsistency, substitutability and others.
  Because of the computational intractability of all the property-detection
problems, by following the CSP approach we then determine a number of
relaxations which provide sufficient conditions for their tractability. In
particular, we exploit forms of language restrictions and local reasoning.
Latent Tree Models and Approximate Inference in Bayesian Networks
Authors: Yi Wang, Nevin L. Zhang, Tao Chen
Date: 2014-01-15 00:00:00

We propose a novel method for approximate inference in Bayesian networks
(BNs). The idea is to sample data from a BN, learn a latent tree model (LTM)
from the data offline, and when online, make inference with the LTM instead of
the original BN. Because LTMs are tree-structured, inference takes linear time.
In the meantime, they can represent complex relationship among leaf nodes and
hence the approximation accuracy is often good. Empirical evidence shows that
our method can achieve good approximation accuracy at low online computational
cost.
A Heuristic Search Approach to Planning with Continuous Resources in Stochastic Domains
Authors: Nicolas Meuleau, Emmanuel Benazera, Ronen I. Brafman, Eric A. Hansen, Mausam
Date: 2014-01-15 00:00:00
Tasks: Heuristic Search

We consider the problem of optimal planning in stochastic domains with
resource constraints, where the resources are continuous and the choice of
action at each step depends on resource availability. We introduce the HAO*
algorithm, a generalization of the AO* algorithm that performs search in a
hybrid state space that is modeled using both discrete and continuous state
variables, where the continuous variables represent monotonic resources. Like
other heuristic search algorithms, HAO* leverages knowledge of the start state
and an admissible heuristic to focus computational effort on those parts of the
state space that could be reached from the start state by following an optimal
policy. We show that this approach is especially effective when resource
constraints limit how much of the state space is reachable. Experimental
results demonstrate its effectiveness in the domain that motivates our
research: automated planning for planetary exploration rovers.
Analogical Dissimilarity: Definition, Algorithms and Two Experiments in Machine Learning
Authors: Laurent Miclet, Sabri Bayoudh, Arnaud Delhay
Date: 2014-01-15 00:00:00
Tasks: BIG-bench Machine Learning, Vocal Bursts Valence Prediction

This paper defines the notion of analogical dissimilarity between four
objects, with a special focus on objects structured as sequences. Firstly, it
studies the case where the four objects have a null analogical dissimilarity,
i.e. are in analogical proportion. Secondly, when one of these objects is
unknown, it gives algorithms to compute it. Thirdly, it tackles the problem of
defining analogical dissimilarity, which is a measure of how far four objects
are from being in analogical proportion. In particular, when objects are
sequences, it gives a definition and an algorithm based on an optimal alignment
of the four sequences. It gives also learning algorithms, i.e. methods to find
the triple of objects in a learning sample which has the least analogical
dissimilarity with a given object. Two practical experiments are described: the
first is a classification problem on benchmarks of binary and nominal data, the
second shows how the generation of sequences by solving analogical equations
enables a handwritten character recognition system to rapidly be adapted to a
new writer.
Networks of Influence Diagrams: A Formalism for Representing Agents' Beliefs and Decision-Making Processes
Authors: Yaakov Gal, Avi Pfeffer
Date: 2014-01-15 00:00:00
Tasks: Decision Making

This paper presents Networks of Influence Diagrams (NID), a compact, natural
and highly expressive language for reasoning about agents beliefs and
decision-making processes. NIDs are graphical structures in which agents mental
models are represented as nodes in a network; a mental model for an agent may
itself use descriptions of the mental models of other agents. NIDs are
demonstrated by examples, showing how they can be used to describe conflicting
and cyclic belief structures, and certain forms of bounded rationality. In an
opponent modeling domain, NIDs were able to outperform other computational
agents whose strategies were not known in advance. NIDs are equivalent in
representation to Bayesian games but they are more compact and structured than
this formalism. In particular, the equilibrium definition for NIDs makes an
explicit distinction between agents optimal strategies, and how they actually
behave in reality.
Infinite Mixed Membership Matrix Factorization
Authors: Avneesh Saluja, Mahdi Pakdaman, Dongzhen Piao, Ankur P. Parikh
Date: 2014-01-15 00:00:00
Tasks: Recommendation Systems

Rating and recommendation systems have become a popular application area for
applying a suite of machine learning techniques. Current approaches rely
primarily on probabilistic interpretations and extensions of matrix
factorization, which factorizes a user-item ratings matrix into latent user and
item vectors. Most of these methods fail to model significant variations in
item ratings from otherwise similar users, a phenomenon known as the "Napoleon
Dynamite" effect. Recent efforts have addressed this problem by adding a
contextual bias term to the rating, which captures the mood under which a user
rates an item or the context in which an item is rated by a user. In this work,
we extend this model in a nonparametric sense by learning the optimal number of
moods or contexts from the data, and derive Gibbs sampling inference procedures
for our model. We evaluate our approach on the MovieLens 1M dataset, and show
significant improvements over the optimal parametric baseline, more than twice
the improvements previously encountered for this task. We also extract and
evaluate a DBLP dataset, wherein we predict the number of papers co-authored by
two authors, and present improvements over the parametric baseline on this
alternative domain as well.
MRFalign: Protein Homology Detection through Alignment of Markov Random Fields
Authors: Jianzhu Ma, Sheng Wang, Zhiyong Wang, Jinbo Xu
Date: 2014-01-12 00:00:00
Tasks: Multiple Sequence Alignment

Sequence-based protein homology detection has been extensively studied and so
far the most sensitive method is based upon comparison of protein sequence
profiles, which are derived from multiple sequence alignment (MSA) of sequence
homologs in a protein family. A sequence profile is usually represented as a
position-specific scoring matrix (PSSM) or an HMM (Hidden Markov Model) and
accordingly PSSM-PSSM or HMM-HMM comparison is used for homolog detection. This
paper presents a new homology detection method MRFalign, consisting of three
key components: 1) a Markov Random Fields (MRF) representation of a protein
family; 2) a scoring function measuring similarity of two MRFs; and 3) an
efficient ADMM (Alternating Direction Method of Multipliers) algorithm aligning
two MRFs. Compared to HMM that can only model very short-range residue
correlation, MRFs can model long-range residue interaction pattern and thus,
encode information for the global 3D structure of a protein family.
Consequently, MRF-MRF comparison for remote homology detection shall be much
more sensitive than HMM-HMM or PSSM-PSSM comparison. Experiments confirm that
MRFalign outperforms several popular HMM or PSSM-based methods in terms of both
alignment accuracy and remote homology detection and that MRFalign works
particularly well for mainly beta proteins. For example, tested on the
benchmark SCOP40 (8353 proteins) for homology detection, PSSM-PSSM and HMM-HMM
succeed on 48% and 52% of proteins, respectively, at superfamily level, and on
15% and 27% of proteins, respectively, at fold level. In contrast, MRFalign
succeeds on 57.3% and 42.5% of proteins at superfamily and fold level,
respectively. This study implies that long-range residue interaction patterns
are very helpful for sequence-based homology detection. The software is
available for download at http://raptorx.uchicago.edu/download/.
Binary Classifier Calibration: Non-parametric approach
Authors: Mahdi Pakdaman Naeini, Gregory F. Cooper, Milos Hauskrecht
Date: 2014-01-14 00:00:00
Tasks: Classifier calibration, Decision Making, Density Estimation

Accurate calibration of probabilistic predictive models learned is critical
for many practical prediction and decision-making tasks. There are two main
categories of methods for building calibrated classifiers. One approach is to
develop methods for learning probabilistic models that are well-calibrated, ab
initio. The other approach is to use some post-processing methods for
transforming the output of a classifier to be well calibrated, as for example
histogram binning, Platt scaling, and isotonic regression. One advantage of the
post-processing approach is that it can be applied to any existing
probabilistic classification model that was constructed using any
machine-learning method.
  In this paper, we first introduce two measures for evaluating how well a
classifier is calibrated. We prove three theorems showing that using a simple
histogram binning post-processing method, it is possible to make a classifier
be well calibrated while retaining its discrimination capability. Also, by
casting the histogram binning method as a density-based non-parametric binary
classifier, we can extend it using two simple non-parametric density estimation
methods. We demonstrate the performance of the proposed calibration methods on
synthetic and real datasets. Experimental results show that the proposed
methods either outperform or are comparable to existing calibration methods.
A programme to determine the exact interior of any connected digital picture
Authors: Antonio Elias Fabris, Valério Ramos Batista
Date: 2014-01-14 00:00:00

Region filling is one of the most important and fundamental operations in
computer graphics and image processing. Many filling algorithms and their
implementations are based on the Euclidean geometry, which are then translated
into computational models moving carelessly from the continuous to the finite
discrete space of the computer. The consequences of this approach is that most
implementations fail when tested for challenging degenerate and nearly
degenerate regions. We present a correct integer-only procedure that works for
all connected digital pictures. It finds all possible interior points, which
are then displayed and stored in a locating matrix. Namely, we present a
filling and locating procedure that can be used in computer graphics and image
processing applications.
An adaptive Simulated Annealing-based satellite observation scheduling method combined with a dynamic task clustering strategy
Authors: Guohua Wu, Huilin Wang, Haifeng Li, Witold Pedrycz, Dishan Qiu, Manhao Ma, Jin Liu
Date: 2014-01-14 00:00:00
Tasks: Clustering, Scheduling

Efficient scheduling is of great significance to rationally make use of
scarce satellite resources. Task clustering has been demonstrated to realize an
effective strategy to improve the efficiency of satellite scheduling. However,
the previous task clustering strategy is static. That is, it is integrated into
the scheduling in a two-phase manner rather than in a dynamic fashion, without
expressing its full potential in improving the satellite scheduling
performance. In this study, we present an adaptive Simulated Annealing based
scheduling algorithm aggregated with a dynamic task clustering strategy (or
ASA-DTC for short) for satellite observation scheduling problems (SOSPs).
First, we develop a formal model for the scheduling of Earth observing
satellites. Second, we analyze the related constraints involved in the
observation task clustering process. Thirdly, we detail an implementation of
the dynamic task clustering strategy and the adaptive Simulated Annealing
algorithm. The adaptive Simulated Annealing algorithm is efficient, with the
endowment of some sophisticated mechanisms, i.e. adaptive temperature control,
tabu-list based revisiting avoidance mechanism, and intelligent combination of
neighborhood structures. Finally, we report on experimental simulation studies
to demonstrate the competitive performance of ASA-DTC. Moreover, we show that
ASA-DTC is especially effective when SOSPs contain a large number of targets or
these targets are densely distributed in a certain area.
Learning Language from a Large (Unannotated) Corpus
Authors: Linas Vepstas, Ben Goertzel
Date: 2014-01-14 00:00:00

A novel approach to the fully automated, unsupervised extraction of
dependency grammars and associated syntax-to-semantic-relationship mappings
from large text corpora is described. The suggested approach builds on the
authors' prior work with the Link Grammar, RelEx and OpenCog systems, as well
as on a number of prior papers and approaches from the statistical language
learning literature. If successful, this approach would enable the mining of
all the information needed to power a natural language comprehension and
generation system, directly from a large, unannotated corpus.
Survey On The Estimation Of Mutual Information Methods as a Measure of Dependency Versus Correlation Analysis
Authors: D. Gencaga, N. K. Malakar, D. J. Lary
Date: 2014-01-14 00:00:00

In this survey, we present and compare different approaches to estimate
Mutual Information (MI) from data to analyse general dependencies between
variables of interest in a system. We demonstrate the performance difference of
MI versus correlation analysis, which is only optimal in case of linear
dependencies. First, we use a piece-wise constant Bayesian methodology using a
general Dirichlet prior. In this estimation method, we use a two-stage approach
where we approximate the probability distribution first and then calculate the
marginal and joint entropies. Here, we demonstrate the performance of this
Bayesian approach versus the others for computing the dependency between
different variables. We also compare these with linear correlation analysis.
Finally, we apply MI and correlation analysis to the identification of the bias
in the determination of the aerosol optical depth (AOD) by the satellite based
Moderate Resolution Imaging Spectroradiometer (MODIS) and the ground based
AErosol RObotic NETwork (AERONET). Here, we observe that the AOD measurements
by these two instruments might be different for the same location. The reason
of this bias is explored by quantifying the dependencies between the bias and
15 other variables including cloud cover, surface reflectivity and others.
A Boosting Approach to Learning Graph Representations
Authors: Rajmonda Caceres, Kevin Carter, Jeremy Kun
Date: 2014-01-14 00:00:00
Tasks: Community Detection, Relational Reasoning

Learning the right graph representation from noisy, multisource 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. We explore the extent to which different
quality measurements yield graph representations that are suitable for
community detection. We then present empirical results on both synthetic and
real datasets demonstrating the utility of this framework. Our framework leads
to suitable global graph representations from quality measurements local to
each edge. Finally, we discuss future extensions and theoretical considerations
of learning useful graph representations from weak feedback in general
application settings.
Online Markov decision processes with Kullback-Leibler control cost
Authors: Peng Guan, Maxim Raginsky, Rebecca Willett
Date: 2014-01-14 00:00:00

This paper considers an online (real-time) control problem that involves an
agent performing a discrete-time random walk over a finite state space. The
agent's action at each time step is to specify the probability distribution for
the next state given the current state. Following the set-up of Todorov, the
state-action cost at each time step is a sum of a state cost and a control cost
given by the Kullback-Leibler (KL) divergence between the agent's next-state
distribution and that determined by some fixed passive dynamics. The online
aspect of the problem is due to the fact that the state cost functions are
generated by a dynamic environment, and the agent learns the current state cost
only after selecting an action. An explicit construction of a computationally
efficient strategy with small regret (i.e., expected difference between its
actual total cost and the smallest cost attainable using noncausal knowledge of
the state costs) under mild regularity conditions is presented, along with a
demonstration of the performance of the proposed strategy on a simulated target
tracking problem. A number of new results on Markov decision processes with KL
control cost are also obtained.
Dynamic Topology Adaptation and Distributed Estimation for Smart Grids
Authors: S. Xu, R. C. de Lamare, H. V. Poor
Date: 2014-01-14 00:00:00

This paper presents new dynamic topology adaptation strategies for
distributed estimation in smart grids systems. We propose a dynamic exhaustive
search--based topology adaptation algorithm and a dynamic sparsity--inspired
topology adaptation algorithm, which can exploit the topology of smart grids
with poor--quality links and obtain performance gains. We incorporate an
optimized combining rule, named Hastings rule into our proposed dynamic
topology adaptation algorithms. Compared with the existing works in the
literature on distributed estimation, the proposed algorithms have a better
convergence rate and significantly improve the system performance. The
performance of the proposed algorithms is compared with that of existing
algorithms in the IEEE 14--bus system.