pwc-archive/papers-with-abstracts huggingface dataset:
When do Numbers Really Matter?
Authors: Hei Chan, Adnan Darwiche
Date: 2014-08-07 00:00:00

Common wisdom has it that small distinctions in the probabilities quantifying
a Bayesian network do not matter much for the resultsof probabilistic queries.
However, one can easily develop realistic scenarios under which small
variations in network probabilities can lead to significant changes in computed
queries. A pending theoretical question is then to analytically characterize
parameter changes that do or do not matter. In this paper, we study the
sensitivity of probabilistic queries to changes in network parameters and prove
some tight bounds on the impact that such parameters can have on queries. Our
analytical results pinpoint some interesting situations under which parameter
changes do or do not matter. These results are important for knowledge
engineers as they help them identify influential network parameters. They are
also important for approximate inference algorithms that preprocessnetwork CPTs
to eliminate small distinctions in probabilities.
Learning to Cooperate via Policy Search
Authors: Leonid Peshkin, Kee-Eung Kim, Nicolas Meuleau, Leslie Pack Kaelbling
Date: 2014-08-07 00:00:00
Tasks: Q-Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Cooperative games are those in which both agents share the same payoff
structure. Value-based reinforcement-learning algorithms, such as variants of
Q-learning, have been applied to learning cooperative games, but they only
apply when the game state is completely observable to both agents. Policy
search methods are a reasonable alternative to value-based methods for
partially observable environments. In this paper, we provide a gradient-based
distributed policy-search method for cooperative games and compare the notion
of local optimum to that of Nash equilibrium. We demonstrate the effectiveness
of this method experimentally in a small, partially observable simulated soccer
domain.
Random Algorithms for the Loop Cutset Problem
Authors: Ann Becker, Reuven Bar-Yehuada, Dan Geiger
Date: 2014-08-07 00:00:00

We show how to find a minimum loop cutset in a Bayesian network with high
probability. Finding such a loop cutset is the first step in Pearl's method of
conditioning for inference. Our random algorithm for finding a loop cutset,
called "Repeated WGuessI", outputs a minimum loop cutset, after O(c 6^k k n)
steps, with probability at least 1-(1 over{6^k})^{c 6^k}), where c>1 is a
constant specified by the user, k is the size of a minimum weight loop cutset,
and n is the number of vertices. We also show empirically that a variant of
this algorithm, called WRA, often finds a loop cutset that is closer to the
minimum loop cutset than the ones found by the best deterministic algorithms
known.
Axiomatizing Causal Reasoning
Authors: Joseph Y. Halpern
Date: 2014-08-07 00:00:00

Causal models defined in terms of a collection of equations, as defined by
Pearl, are axiomatized here. Axiomatizations are provided for three
successively more general classes of causal models: (1) the class of recursive
theories (those without feedback), (2) the class of theories where the
solutions to the equations are unique, (3) arbitrary theories (where the
equations may not have solutions and, if they do, they are not necessarily
unique). It is shown that to reason about causality in the most general third
class, we must extend the language used by Galles and Pearl. In addition, the
complexity of the decision procedures is examined for all the languages and
classes of models considered.
Generalized Qualitative Probability: Savage Revisited
Authors: Daniel Lehmann
Date: 2014-08-07 00:00:00

Preferences among acts are analyzed in the style of L. Savage, but as
partially ordered. The rationality postulates considered are weaker than
Savage's on three counts. The Sure Thing Principle is derived in this setting.
The postulates are shown to lead to a characterization of generalized
qualitative probability that includes and blends both traditional qualitative
probability and the ranked structures used in logical approaches.
Query DAGs: A Practical Paradigm for Implementing Belief Network Inference
Authors: Adnan Darwiche, Gregory M. Provan
Date: 2014-08-07 00:00:00
Tasks: Clustering

We describe a new paradigm for implementing inference in belief networks,
which relies on compiling a belief network into an arithmetic expression called
a Query DAG (Q-DAG). Each non-leaf node of a Q-DAG represents a numeric
operation, a number, or a symbol for evidence. Each leaf node of a Q-DAG
represents the answer to a network query, that is, the probability of some
event of interest. It appears that Q-DAGs can be generated using any of the
algorithms for exact inference in belief networks --- we show how they can be
generated using clustering and conditioning algorithms. The time and space
complexity of a Q-DAG generation algorithm is no worse than the time complexity
of the inference algorithm on which it is based; that of a Q-DAG on-line
evaluation algorithm is linear in the size of the Q-DAG, and such inference
amounts to a standard evaluation of the arithmetic expression it represents.
The main value of Q-DAGs is in reducing the software and hardware resources
required to utilize belief networks in on-line, real-world applications. The
proposed framework also facilitates the development of on-line inference on
different software and hardware platforms, given the simplicity of the Q-DAG
evaluation algorithm. This paper describes this new paradigm for probabilistic
inference, explaining how it works, its uses, and outlines some of the research
directions that it leads to.
Logarithmic-Time Updates and Queries in Probabilistic Networks
Authors: Arthur L. Delcher, Adam J. Grove, Simon Kasif, Judea Pearl
Date: 2014-08-07 00:00:00

In this paper we propose a dynamic data structure that supports efficient
algorithms for updating and querying singly connected Bayesian networks (causal
trees and polytrees). In the conventional algorithms, new evidence in absorbed
in time O(1) and queries are processed in time O(N), where N is the size of the
network. We propose a practical algorithm which, after a preprocessing phase,
allows us to answer queries in time O(log N) at the expense of O(logn N) time
per evidence absorption. The usefulness of sub-linear processing time manifests
itself in applications requiring (near) real-time response over large
probabilistic databases.
WebAL-1: Workshop on Artificial Life and the Web 2014 Proceedings
Authors: Tim Taylor
Date: 2014-06-10 00:00:00
Tasks: Artificial Life

Proceedings of WebAL-1: Workshop on Artificial Life and the Web 2014, held at
the 14th International Conference on the Synthesis and Simulation of Living
Systems (ALIFE 14), New York, NY, 31 July 2014.
Sparse and Low-Rank Covariance Matrices Estimation
Authors: Shenglong Zhou, Naihua Xiu, Ziyan Luo, Lingchen Kong
Date: 2014-07-17 00:00:00

This paper aims at achieving a simultaneously sparse and low-rank estimator
from the semidefinite population covariance matrices. We first benefit from a
convex optimization which develops $l_1$-norm penalty to encourage the sparsity
and nuclear norm to favor the low-rank property. For the proposed estimator, we
then prove that with large probability, the Frobenious norm of the estimation
rate can be of order $O(\sqrt{s(\log{r})/n})$ under a mild case, where $s$ and
$r$ denote the number of sparse entries and the rank of the population
covariance respectively, $n$ notes the sample capacity. Finally an efficient
alternating direction method of multipliers with global convergence is proposed
to tackle this problem, and meantime merits of the approach are also
illustrated by practicing numerical simulations.
The Mathematical Abstraction Theory, The Fundamentals for Knowledge Representation and Self-Evolving Autonomous Problem Solving Systems
Authors: Seppo Ilari Tirri
Date: 2014-08-06 00:00:00

The intention of the present study is to establish the mathematical
fundamentals for automated problem solving essentially targeted for robotics by
approaching the task universal algebraically introducing knowledge as
realizations of generalized free algebra based nets, graphs with gluing forms
connecting in- and out-edges to nodes. Nets are caused to undergo
transformations in conceptual level by type wise differentiated intervening net
rewriting systems dispersing problems to abstract parts, matching being
determined by substitution relations. Achieved sets of conceptual nets
constitute congruent classes. New results are obtained within construction of
problem solving systems where solution algorithms are derived parallel with
other candidates applied to the same net classes. By applying parallel
transducer paths consisting of net rewriting systems to net classes congruent
quotient algebras are established and the manifested class rewriting comprises
all solution candidates whenever produced nets are in anticipated languages
liable to acceptance of net automata. Furthermore new solutions will be added
to the set of already known ones thus expanding the solving power in the
forthcoming. Moreover special attention is set on universal abstraction,
thereof generation by net block homomorphism, consequently multiple order
solving systems and the overall decidability of the set of the solutions. By
overlapping presentation of nets new abstraction relation among nets is
formulated alongside with consequent alphabetical net block renetting system
proportional to normal forms of renetting systems regarding the operational
power. A new structure in self-evolving problem solving is established via
saturation by groups of equivalence relations and iterative closures of
generated quotient transducer algebras over the whole evolution.
Preventing False Discovery in Interactive Data Analysis is Hard
Authors: Moritz Hardt, Jonathan Ullman
Date: 2014-08-06 00:00:00
Tasks: valid

We show that, under a standard hardness assumption, there is no
computationally efficient algorithm that given $n$ samples from an unknown
distribution can give valid answers to $n^{3+o(1)}$ adaptively chosen
statistical queries. A statistical query asks for the expectation of a
predicate over the underlying distribution, and an answer to a statistical
query is valid if it is "close" to the correct expectation over the
distribution.
  Our result stands in stark contrast to the well known fact that exponentially
many statistical queries can be answered validly and efficiently if the queries
are chosen non-adaptively (no query may depend on the answers to previous
queries). Moreover, a recent work by Dwork et al. shows how to accurately
answer exponentially many adaptively chosen statistical queries via a
computationally inefficient algorithm; and how to answer a quadratic number of
adaptive queries via a computationally efficient algorithm. The latter result
implies that our result is tight up to a linear factor in $n.$
  Conceptually, our result demonstrates that achieving statistical validity
alone can be a source of computational intractability in adaptive settings. For
example, in the modern large collaborative research environment, data analysts
typically choose a particular approach based on previous findings. False
discovery occurs if a research finding is supported by the data but not by the
underlying distribution. While the study of preventing false discovery in
Statistics is decades old, to the best of our knowledge our result is the first
to demonstrate a computational barrier. In particular, our result suggests that
the perceived difficulty of preventing false discovery in today's collaborative
research environment may be inherent.
When does Active Learning Work?
Authors: Lewis Evans, Niall M. Adams, Christoforos Anagnostopoulos
Date: 2014-08-06 00:00:00
Tasks: Active Learning

Active Learning (AL) methods seek to improve classifier performance when
labels are expensive or scarce. We consider two central questions: Where does
AL work? How much does it help? To address these questions, a comprehensive
experimental simulation study of Active Learning is presented. We consider a
variety of tasks, classifiers and other AL factors, to present a broad
exploration of AL performance in various settings. A precise way to quantify
performance is needed in order to know when AL works. Thus we also present a
detailed methodology for tackling the complexities of assessing AL performance
in the context of this experimental study.
New crossover operators for multiple subset selection tasks
Authors: Arnab Roy, J. David Schaffer, Craig B. Laramee
Date: 2014-08-06 00:00:00
Tasks: EEG, Electroencephalogram (EEG), feature selection

We have introduced two crossover operators, MMX-BLXexploit and
MMX-BLXexplore, for simultaneously solving multiple feature/subset selection
problems where the features may have numeric attributes and the subset sizes
are not predefined. These operators differ on the level of exploration and
exploitation they perform; one is designed to produce convergence controlled
mutation and the other exhibits a quasi-constant mutation rate. We illustrate
the characteristic of these operators by evolving pattern detectors to
distinguish alcoholics from controls using their visually evoked response
potentials (VERPs). This task encapsulates two groups of subset selection
problems; choosing a subset of EEG leads along with the lead-weights (features
with attributes) and the other that defines the temporal pattern that
characterizes the alcoholic VERPs. We observed better generalization
performance from MMX-BLXexplore. Perhaps, MMX-BLXexploit was handicapped by not
having a restart mechanism. These operators are novel and appears to hold
promise for solving simultaneous feature selection problems.
Pseudo-Zernike Based Multi-Pass Automatic Target Recognition From Multi-Channel SAR
Authors: Carmine Clemente, Luca Pallotta, Ian Proudler, Antonio De Maio, John J. Soraghan, Alfonso Farina
Date: 2014-04-07 00:00:00
Tasks: Diversity

The capability to exploit multiple sources of information is of fundamental
importance in a battlefield scenario. Information obtained from different
sources, and separated in space and time, provide the opportunity to exploit
diversities in order to mitigate uncertainty. For the specific challenge of
Automatic Target Recognition (ATR) from radar platforms, both channel (e.g.
polarization) and spatial diversity can provide useful information for such a
specific and critical task. In this paper the use of pseudo-Zernike moments
applied to multi-channel multi-pass data is presented exploiting diversities
and invariant properties leading to high confidence ATR, small computational
complexity and data transfer requirements. The effectiveness of the proposed
approach, in different configurations and data source availability is
demonstrated using real data.
The functional mean-shift algorithm for mode hunting and clustering in infinite dimensions
Authors: Mattia Ciollaro, Christopher Genovese, Jing Lei, Larry Wasserman
Date: 2014-08-06 00:00:00
Tasks: Clustering, Spike Sorting

We introduce the functional mean-shift algorithm, an iterative algorithm for
estimating the local modes of a surrogate density from functional data. We show
that the algorithm can be used for cluster analysis of functional data. We
propose a test based on the bootstrap for the significance of the estimated
local modes of the surrogate density. We present two applications of our
methodology. In the first application, we demonstrate how the functional
mean-shift algorithm can be used to perform spike sorting, i.e. cluster neural
activity curves. In the second application, we use the functional mean-shift
algorithm to distinguish between original and fake signatures.
Computing With Contextual Numbers
Authors: Vahid Moosavi
Date: 2014-08-05 00:00:00
Tasks: Clustering

Self Organizing Map (SOM) has been applied into several classical modeling
tasks including clustering, classification, function approximation and
visualization of high dimensional spaces. The final products of a trained SOM
are a set of ordered (low dimensional) indices and their associated high
dimensional weight vectors. While in the above-mentioned applications, the
final high dimensional weight vectors play the primary role in the
computational steps, from a certain perspective, one can interpret SOM as a
nonparametric encoder, in which the final low dimensional indices of the
trained SOM are pointer to the high dimensional space. We showed how using a
one-dimensional SOM, which is not common in usual applications of SOM, one can
develop a nonparametric mapping from a high dimensional space to a continuous
one-dimensional numerical field. These numerical values, called contextual
numbers, are ordered in a way that in a given context, similar numbers refer to
similar high dimensional states. Further, as these numbers can be treated
similarly to usual continuous numbers, they can be replaced with their
corresponding high dimensional states within any data driven modeling problem.
As a potential application, we showed how using contextual numbers could be
used for the problem of high dimensional spatiotemporal dynamics.
Boosted Markov Networks for Activity Recognition
Authors: Truyen Tran, Hung Bui, Svetha Venkatesh
Date: 2014-08-06 00:00:00
Tasks: Activity Recognition, feature selection, General Classification

We explore a framework called boosted Markov networks to combine the learning
capacity of boosting and the rich modeling semantics of Markov networks and
applying the framework for video-based activity recognition. Importantly, we
extend the framework to incorporate hidden variables. We show how the framework
can be applied for both model learning and feature selection. We demonstrate
that boosted Markov networks with hidden variables perform comparably with the
standard maximum likelihood estimation. However, our framework is able to learn
sparse models, and therefore can provide computational savings when the learned
models are used for classification.
Human Activity Learning and Segmentation using Partially Hidden Discriminative Models
Authors: Truyen Tran, Hung Bui, Svetha Venkatesh
Date: 2014-08-06 00:00:00

Learning and understanding the typical patterns in the daily activities and
routines of people from low-level sensory data is an important problem in many
application domains such as building smart environments, or providing
intelligent assistance. Traditional approaches to this problem typically rely
on supervised learning and generative models such as the hidden Markov models
and its extensions. While activity data can be readily acquired from pervasive
sensors, e.g. in smart environments, providing manual labels to support
supervised training is often extremely expensive. In this paper, we propose a
new approach based on semi-supervised training of partially hidden
discriminative models such as the conditional random field (CRF) and the
maximum entropy Markov model (MEMM). We show that these models allow us to
incorporate both labeled and unlabeled data for learning, and at the same time,
provide us with the flexibility and accuracy of the discriminative framework.
Our experimental results in the video surveillance domain illustrate that these
models can perform better than their generative counterpart, the partially
hidden Markov model, even when a substantial amount of labels are unavailable.
MCMC for Hierarchical Semi-Markov Conditional Random Fields
Authors: Truyen Tran, Dinh Phung, Svetha Venkatesh, Hung H. Bui
Date: 2014-08-06 00:00:00

Deep architecture such as hierarchical semi-Markov models is an important
class of models for nested sequential data. Current exact inference schemes
either cost cubic time in sequence length, or exponential time in model depth.
These costs are prohibitive for large-scale problems with arbitrary length and
depth. In this contribution, we propose a new approximation technique that may
have the potential to achieve sub-cubic time complexity in length and linear
time depth, at the cost of some loss of quality. The idea is based on two
well-known methods: Gibbs sampling and Rao-Blackwellisation. We provide some
simulation-based evaluation of the quality of the RGBS with respect to run time
and sequence length.
Mixed-Variate Restricted Boltzmann Machines
Authors: Truyen Tran, Dinh Phung, Svetha Venkatesh
Date: 2014-08-06 00:00:00
Tasks: Dimensionality Reduction

Modern datasets are becoming heterogeneous. To this end, we present in this
paper Mixed-Variate Restricted Boltzmann Machines for simultaneously modelling
variables of multiple types and modalities, including binary and continuous
responses, categorical options, multicategorical choices, ordinal assessment
and category-ranked preferences. Dependency among variables is modeled using
latent binary variables, each of which can be interpreted as a particular
hidden aspect of the data. The proposed model, similar to the standard RBMs,
allows fast evaluation of the posterior for the latent variables. Hence, it is
naturally suitable for many common tasks including, but not limited to, (a) as
a pre-processing step to convert complex input data into a more convenient
vectorial representation through the latent posteriors, thereby offering a
dimensionality reduction capacity, (b) as a classifier supporting binary,
multiclass, multilabel, and label-ranking outputs, or a regression tool for
continuous outputs and (c) as a data completion tool for multimodal and
heterogeneous data. We evaluate the proposed model on a large-scale dataset
using the world opinion survey results on three tasks: feature extraction and
visualization, data completion and prediction.
It is hard to see a needle in a haystack: Modeling contrast masking effect in a numerical observer
Authors: Ali R. N. Avanaki, Kathryn S. Espig, Albert Xthona, Tom R. L. Kimpe, Predrag R. Bakic, Andrew D. A. Maidment
Date: 2014-08-05 00:00:00

Within the framework of a virtual clinical trial for breast imaging, we aim
to develop numerical observers that follow the same detection performance
trends as those of a typical human observer. In our prior work, we showed that
by including spatiotemporal contrast sensitivity function (stCSF) of human
visual system (HVS) in a multi-slice channelized Hotelling observer (msCHO), we
can correctly predict trends of a typical human observer performance with the
viewing parameters of browsing speed, viewing distance and contrast. In this
work we further improve our numerical observer by modeling contrast masking.
After stCSF, contrast masking is the second most prominent property of HVS and
it refers to the fact that the presence of one signal affects the visibility
threshold for another signal. Our results indicate that the improved numerical
observer better predicts changes in detection performance with background
complexity.
The Case for a Mixed-Initiative Collaborative Neuroevolution Approach
Authors: Sebastian Risi, Jinhong Zhang, Rasmus Taarnby, Peter Greve, Jan Piskur, Antonios Liapis, Julian Togelius
Date: 2014-08-05 00:00:00
Tasks: Common Sense Reasoning, Game Design, Ingenuity

It is clear that the current attempts at using algorithms to create
artificial neural networks have had mixed success at best when it comes to
creating large networks and/or complex behavior. This should not be unexpected,
as creating an artificial brain is essentially a design problem. Human design
ingenuity still surpasses computational design for most tasks in most domains,
including architecture, game design, and authoring literary fiction. This leads
us to ask which the best way is to combine human and machine design capacities
when it comes to designing artificial brains. Both of them have their strengths
and weaknesses; for example, humans are much too slow to manually specify
thousands of neurons, let alone the billions of neurons that go into a human
brain, but on the other hand they can rely on a vast repository of common-sense
understanding and design heuristics that can help them perform a much better
guided search in design space than an algorithm. Therefore, in this paper we
argue for a mixed-initiative approach for collaborative online brain building
and present first results towards this goal.