pwc-archive/papers-with-abstracts huggingface dataset:
Performance Measurement Under Increasing Environmental Uncertainty In The Context of Interval Type-2 Fuzzy Logic Based Robotic Sailing
Authors: Naisan Benatar, Uwe Aickelin, Jonathan M. Garibald
Date: 2013-08-23 00:00:00

Performance measurement of robotic controllers based on fuzzy logic,
operating under uncertainty, is a subject area which has been somewhat ignored
in the current literature. In this paper standard measures such as RMSE are
shown to be inappropriate for use under conditions where the environmental
uncertainty changes significantly between experiments. An overview of current
methods which have been applied by other authors is presented, followed by a
design of a more sophisticated method of comparison. This method is then
applied to a robotic control problem to observe its outcome compared with a
single measure. Results show that the technique described provides a more
robust method of performance comparison than less complex methods allowing
better comparisons to be drawn.
Complexity of evolutionary equilibria in static fitness landscapes
Authors: Artem Kaznatcheev
Date: 2013-08-23 00:00:00

A fitness landscape is a genetic space -- with two genotypes adjacent if they
differ in a single locus -- and a fitness function. Evolutionary dynamics
produce a flow on this landscape from lower fitness to higher; reaching
equilibrium only if a local fitness peak is found. I use computational
complexity to question the common assumption that evolution on static fitness
landscapes can quickly reach a local fitness peak. I do this by showing that
the popular NK model of rugged fitness landscapes is PLS-complete for K >= 2;
the reduction from Weighted 2SAT is a bijection on adaptive walks, so there are
NK fitness landscapes where every adaptive path from some vertices is of
exponential length. Alternatively -- under the standard complexity theoretic
assumption that there are problems in PLS not solvable in polynomial time --
this means that there are no evolutionary dynamics (known, or to be discovered,
and not necessarily following adaptive paths) that can converge to a local
fitness peak on all NK landscapes with K = 2. Applying results from the
analysis of simplex algorithms, I show that there exist single-peaked
landscapes with no reciprocal sign epistasis where the expected length of an
adaptive path following strong selection weak mutation dynamics is
$e^{O(n^{1/3})}$ even though an adaptive path to the optimum of length less
than n is available from every vertex. The technical results are written to be
accessible to mathematical biologists without a computer science background,
and the biological literature is summarized for the convenience of
non-biologists with the aim to open a constructive dialogue between the two
disciplines.
Suspicious Object Recognition Method in Video Stream Based on Visual Attention
Authors: Panqu Wang, Yan Zhang
Date: 2013-08-23 00:00:00
Tasks: Object, Object Recognition

We propose a state of the art method for intelligent object recognition and
video surveillance based on human visual attention. Bottom up and top down
attention are applied respectively in the process of acquiring interested
object(saliency map) and object recognition. The revision of 4 channel PFT
method is proposed for bottom up attention and enhances the speed and accuracy.
Inhibit of return (IOR) is applied in judging the sequence of saliency object
pop out. Euclidean distance of color distribution, object center coordinates
and speed are considered in judging whether the target is match and suspicious.
The extensive tests on videos and images show that our method in video analysis
has high accuracy and fast speed compared with traditional method. The method
can be applied into many fields such as video surveillance and security.
The Fractal Dimension of SAT Formulas
Authors: C. Ansótegui, M. L. Bonet, J. Giráldez-Cru, J. Levy
Date: 2013-08-23 00:00:00

Modern SAT solvers have experienced a remarkable progress on solving
industrial instances. Most of the techniques have been developed after an
intensive experimental testing process. Recently, there have been some attempts
to analyze the structure of these formulas in terms of complex networks, with
the long-term aim of explaining the success of these SAT solving techniques,
and possibly improving them.
  We study the fractal dimension of SAT formulas, and show that most industrial
families of formulas are self-similar, with a small fractal dimension. We also
show that this dimension is not affected by the addition of learnt clauses. We
explore how the dimension of a formula, together with other graph properties
can be used to characterize SAT instances. Finally, we give empirical evidence
that these graph properties can be used in state-of-the-art portfolios.
Likelihood Adaptively Modified Penalties
Authors: Yang Feng, Tengfei Li, Zhiliang Ying
Date: 2013-08-23 00:00:00
Tasks: Model Selection, parameter estimation, regression

A new family of penalty functions, adaptive to likelihood, is introduced for
model selection in general regression models. It arises naturally through
assuming certain types of prior distribution on the regression parameters. To
study stability properties of the penalized maximum likelihood estimator, two
types of asymptotic stability are defined. Theoretical properties, including
the parameter estimation consistency, model selection consistency, and
asymptotic stability, are established under suitable regularity conditions. An
efficient coordinate-descent algorithm is proposed. Simulation results and real
data analysis show that the proposed method has competitive performance in
comparison with existing ones.
A hybrid evolutionary algorithm with importance sampling for multi-dimensional optimization
Authors: Guanghui Huang, Zhifeng Pan
Date: 2013-08-23 00:00:00

A hybrid evolutionary algorithm with importance sampling method is proposed
for multi-dimensional optimization problems in this paper. In order to make use
of the information provided in the search process, a set of visited solutions
is selected to give scores for intervals in each dimension, and they are
updated as algorithm proceeds. Those intervals with higher scores are regarded
as good intervals, which are used to estimate the joint distribution of optimal
solutions through an interaction between the pool of good genetics, which are
the individuals with smaller fitness values. And the sampling probabilities for
good genetics are determined through an interaction between those estimated
good intervals. It is a cross validation mechanism which determines the
sampling probabilities for good intervals and genetics, and the resulted
probabilities are used to design crossover, mutation and other stochastic
operators with importance sampling method. As the selection of genetics and
intervals is not directly dependent on the values of fitness, the resulted
offsprings may avoid the trap of local optima. And a purely random EA is also
combined into the proposed algorithm to maintain the diversity of population.
30 benchmark test functions are used to evaluate the performance of the
proposed algorithm, and it is found that the proposed hybrid algorithm is an
efficient algorithm for multi-dimensional optimization problems considered in
this paper.
How Did Humans Become So Creative? A Computational Approach
Authors: Liane Gabora, Steve DiPaola
Date: 2013-08-23 00:00:00
Tasks: Diversity

This paper summarizes efforts to computationally model two transitions in the evolution of human creativity: its origins about two million years ago, and the 'big bang' of creativity about 50,000 years ago. Using a computational model of cultural evolution in which neural network based agents evolve ideas for actions through invention and imitation, we tested the hypothesis that human creativity began with onset of the capacity for recursive recall. We compared runs in which agents were limited to single-step actions to runs in which they used recursive recall to chain simple actions into complex ones. Chaining resulted in higher diversity, open-ended novelty, no ceiling on the mean fitness of actions, and greater ability to make use of learning. Using a computational model of portrait painting, we tested the hypothesis that the explosion of creativity in the Middle/Upper Paleolithic was due to onset of con-textual focus: the capacity to shift between associative and analytic thought. This resulted in faster convergence on portraits that resembled the sitter, employed painterly techniques, and were rated as preferable. We conclude that recursive recall and contextual focus provide a computationally plausible explanation of how humans evolved the means to transform this planet.
Top-down particle filtering for Bayesian decision trees
Authors: Balaji Lakshminarayanan, Daniel M. Roy, Yee Whye Teh
Date: 2013-03-03 00:00:00

Decision tree learning is a popular approach for classification and
regression in machine learning and statistics, and Bayesian
formulations---which introduce a prior distribution over decision trees, and
formulate learning as posterior inference given data---have been shown to
produce competitive performance. Unlike classic decision tree learning
algorithms like ID3, C4.5 and CART, which work in a top-down manner, existing
Bayesian algorithms produce an approximation to the posterior distribution by
evolving a complete tree (or collection thereof) iteratively via local Monte
Carlo modifications to the structure of the tree, e.g., using Markov chain
Monte Carlo (MCMC). We present a sequential Monte Carlo (SMC) algorithm that
instead works in a top-down manner, mimicking the behavior and speed of classic
algorithms. We demonstrate empirically that our approach delivers accuracy
comparable to the most popular MCMC method, but operates more than an order of
magnitude faster, and thus represents a better computation-accuracy tradeoff.
Comparison between the two definitions of AI
Authors: Dimiter Dobrev
Date: 2013-01-31 00:00:00
Tasks: Vocal Bursts Valence Prediction

Two different definitions of the Artificial Intelligence concept have been
proposed in papers [1] and [2]. The first definition is informal. It says that
any program that is cleverer than a human being, is acknowledged as Artificial
Intelligence. The second definition is formal because it avoids reference to
the concept of human being. The readers of papers [1] and [2] might be left
with the impression that both definitions are equivalent and the definition in
[2] is simply a formal version of that in [1]. This paper will compare both
definitions of Artificial Intelligence and, hopefully, will bring a better
understanding of the concept.
Sentiment in New York City: A High Resolution Spatial and Temporal View
Authors: Karla Z. Bertrand, Maya Bialik, Kawandeep Virdee, Andreas Gros, Yaneer Bar-Yam
Date: 2013-08-22 00:00:00

Measuring public sentiment is a key task for researchers and policymakers
alike. The explosion of available social media data allows for a more
time-sensitive and geographically specific analysis than ever before. In this
paper we analyze data from the micro-blogging site Twitter and generate a
sentiment map of New York City. We develop a classifier specifically tuned for
140-character Twitter messages, or tweets, using key words, phrases and
emoticons to determine the mood of each tweet. This method, combined with
geotagging provided by users, enables us to gauge public sentiment on extremely
fine-grained spatial and temporal scales. We find that public mood is generally
highest in public parks and lowest at transportation hubs, and locate other
areas of strong sentiment such as cemeteries, medical centers, a jail, and a
sewage facility. Sentiment progressively improves with proximity to Times
Square. Periodic patterns of sentiment fluctuate on both a daily and a weekly
scale: more positive tweets are posted on weekends than on weekdays, with a
daily peak in sentiment around midnight and a nadir between 9:00 a.m. and noon.
Deciding Monotone Duality and Identifying Frequent Itemsets in Quadratic Logspace
Authors: Georg Gottlob
Date: 2012-12-09 00:00:00
Tasks: Problem Decomposition

The monotone duality problem is defined as follows: Given two monotone
formulas f and g in iredundant DNF, decide whether f and g are dual. This
problem is the same as duality testing for hypergraphs, that is, checking
whether a hypergraph H consists of precisely all minimal transversals of a
simple hypergraph G. By exploiting a recent problem-decomposition method by
Boros and Makino (ICALP 2009), we show that duality testing for hypergraphs,
and thus for monotone DNFs, is feasible in DSPACE[log^2 n], i.e., in quadratic
logspace. As the monotone duality problem is equivalent to a number of problems
in the areas of databases, data mining, and knowledge discovery, the results
presented here yield new complexity results for those problems, too. For
example, it follows from our results that whenever for a Boolean-valued
relation (whose attributes represent items), a number of maximal frequent
itemsets and a number of minimal infrequent itemsets are known, then it can be
decided in quadratic logspace whether there exist additional frequent or
infrequent itemsets.
Reinforcement learning for port-Hamiltonian systems
Authors: Olivier Sprangers, Gabriel A. D. Lopes, Robert Babuska
Date: 2012-12-21 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Passivity-based control (PBC) for port-Hamiltonian systems provides an
intuitive way of achieving stabilization by rendering a system passive with
respect to a desired storage function. However, in most instances the control
law is obtained without any performance considerations and it has to be
calculated by solving a complex partial differential equation (PDE). In order
to address these issues we introduce a reinforcement learning approach into the
energy-balancing passivity-based control (EB-PBC) method, which is a form of
PBC in which the closed-loop energy is equal to the difference between the
stored and supplied energies. We propose a technique to parameterize EB-PBC
that preserves the systems's PDE matching conditions, does not require the
specification of a global desired Hamiltonian, includes performance criteria,
and is robust to extra non-linearities such as control input saturation. The
parameters of the control law are found using actor-critic reinforcement
learning, enabling learning near-optimal control policies satisfying a desired
closed-loop energy landscape. The advantages are that near-optimal controllers
can be generated using standard energy shaping techniques and that the
solutions learned can be interpreted in terms of energy shaping and damping
injection, which makes it possible to numerically assess stability using
passivity theory. From the reinforcement learning perspective, our proposal
allows for the class of port-Hamiltonian systems to be incorporated in the
actor-critic framework, speeding up the learning thanks to the resulting
parameterization of the policy. The method has been successfully applied to the
pendulum swing-up problem in simulations and real-life experiments.
A Unified Framework for Multi-Sensor HDR Video Reconstruction
Authors: Joel Kronander, Stefan Gustavson, Gerhard Bonnet, Anders Ynnerman, Jonas Unger
Date: 2013-08-22 00:00:00
Tasks: Denoising, HDR Reconstruction, Video Reconstruction

One of the most successful approaches to modern high quality HDR-video
capture is to use camera setups with multiple sensors imaging the scene through
a common optical system. However, such systems pose several challenges for HDR
reconstruction algorithms. Previous reconstruction techniques have considered
debayering, denoising, resampling (align- ment) and exposure fusion as separate
problems. In contrast, in this paper we present a unifying approach, performing
HDR assembly directly from raw sensor data. Our framework includes a camera
noise model adapted to HDR video and an algorithm for spatially adaptive HDR
reconstruction based on fitting of local polynomial approximations to observed
sensor data. The method is easy to implement and allows reconstruction to an
arbitrary resolution and output mapping. We present an implementation in CUDA
and show real-time performance for an experimental 4 Mpixel multi-sensor HDR
video system. We further show that our algorithm has clear advantages over
existing methods, both in terms of flexibility and reconstruction quality.
Validation of Soft Classification Models using Partial Class Memberships: An Extended Concept of Sensitivity & Co. applied to the Grading of Astrocytoma Tissues
Authors: Claudia Beleites, Reiner Salzer, Valter Sergo
Date: 2013-01-02 00:00:00
Tasks: Classification, General Classification, Specificity

We use partial class memberships in soft classification to model uncertain
labelling and mixtures of classes. Partial class memberships are not restricted
to predictions, but may also occur in reference labels (ground truth, gold
standard diagnosis) for training and validation data.
  Classifier performance is usually expressed as fractions of the confusion
matrix, such as sensitivity, specificity, negative and positive predictive
values. We extend this concept to soft classification and discuss the bias and
variance properties of the extended performance measures. Ambiguity in
reference labels translates to differences between best-case, expected and
worst-case performance. We show a second set of measures comparing expected and
ideal performance which is closely related to regression performance, namely
the root mean squared error RMSE and the mean absolute error MAE.
  All calculations apply to classical crisp classification as well as to soft
classification (partial class memberships and/or one-class classifiers). The
proposed performance measures allow to test classifiers with actual borderline
cases. In addition, hardening of e.g. posterior probabilities into class labels
is not necessary, avoiding the corresponding information loss and increase in
variance.
  We implement the proposed performance measures in the R package
"softclassval", which is available from CRAN and at
http://softclassval.r-forge.r-project.org.
  Our reasoning as well as the importance of partial memberships for
chemometric classification is illustrated by a real-word application:
astrocytoma brain tumor tissue grading (80 patients, 37000 spectra) for finding
surgical excision borders. As borderline cases are the actual target of the
analytical technique, samples which are diagnosed to be borderline cases must
be included in the validation.
A review on handwritten character and numeral recognition for Roman, Arabic, Chinese and Indian scripts
Authors: Aini Najwa Azmi, Dewi Nasien, Siti Mariyam Shamsuddin
Date: 2013-08-22 00:00:00

There are a lot of intensive researches on handwritten character recognition
(HCR) for almost past four decades. The research has been done on some of
popular scripts such as Roman, Arabic, Chinese and Indian. In this paper we
present a review on HCR work on the four popular scripts. We have summarized
most of the published paper from 2005 to recent and also analyzed the various
methods in creating a robust HCR system. We also added some future direction of
research on HCR.
POMDPs under Probabilistic Semantics
Authors: Krishnendu Chatterjee, Martin Chmelík
Date: 2013-08-22 00:00:00

We consider partially observable Markov decision processes (POMDPs) with
limit-average payoff, where a reward value in the interval [0,1] is associated
to every transition, and the payoff of an infinite path is the long-run average
of the rewards. We consider two types of path constraints: (i) quantitative
constraint defines the set of paths where the payoff is at least a given
threshold {\lambda} in (0, 1]; and (ii) qualitative constraint which is a
special case of quantitative constraint with {\lambda} = 1. We consider the
computation of the almost-sure winning set, where the controller needs to
ensure that the path constraint is satisfied with probability 1. Our main
results for qualitative path constraint are as follows: (i) the problem of
deciding the existence of a finite-memory controller is EXPTIME-complete; and
(ii) the problem of deciding the existence of an infinite-memory controller is
undecidable. For quantitative path constraint we show that the problem of
deciding the existence of a finite-memory controller is undecidable.
Learning Sequence Neighbourhood Metrics
Authors: Justin Bayer, Christian Osendorfer, Patrick van der Smagt
Date: 2011-09-09 00:00:00
Tasks: General Classification, Metric Learning

Recurrent neural networks (RNNs) in combination with a pooling operator and
the neighbourhood components analysis (NCA) objective function are able to
detect the characterizing dynamics of sequences and embed them into a
fixed-length vector space of arbitrary dimensionality. Subsequently, the
resulting features are meaningful and can be used for visualization or nearest
neighbour classification in linear time. This kind of metric learning for
sequential data enables the use of algorithms tailored towards fixed length
vector spaces such as R^n.
The Sample-Complexity of General Reinforcement Learning
Authors: Tor Lattimore, Marcus Hutter, Peter Sunehag
Date: 2013-08-22 00:00:00
Tasks: General Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We present a new algorithm for general reinforcement learning where the true
environment is known to belong to a finite class of N arbitrary models. The
algorithm is shown to be near-optimal for all but O(N log^2 N) time-steps with
high probability. Infinite classes are also considered where we show that
compactness is a key criterion for determining the existence of uniform
sample-complexity bounds. A matching lower bound is given for the finite case.
Matching Demand with Supply in the Smart Grid using Agent-Based Multiunit Auction
Authors: Tri Kurniawan Wijaya, Kate Larson, Karl Aberer
Date: 2013-08-22 00:00:00

Recent work has suggested reducing electricity generation cost by cutting the
peak to average ratio (PAR) without reducing the total amount of the loads.
However, most of these proposals rely on consumer's willingness to act. In this
paper, we propose an approach to cut PAR explicitly from the supply side. The
resulting cut loads are then distributed among consumers by the means of a
multiunit auction which is done by an intelligent agent on behalf of the
consumer. This approach is also in line with the future vision of the smart
grid to have the demand side matched with the supply side. Experiments suggest
that our approach reduces overall system cost and gives benefit to both
consumers and the energy provider.
Convex and Scalable Weakly Labeled SVMs
Authors: Yu-Feng Li, Ivor W. Tsang, James T. Kwok, Zhi-Hua Zhou
Date: 2013-03-06 00:00:00
Tasks: Clustering, Information Retrieval, Retrieval

In this paper, we study the problem of learning from weakly labeled data,
where labels of the training examples are incomplete. This includes, for
example, (i) semi-supervised learning where labels are partially known; (ii)
multi-instance learning where labels are implicitly known; and (iii) clustering
where labels are completely unknown. Unlike supervised learning, learning with
weak labels involves a difficult Mixed-Integer Programming (MIP) problem.
Therefore, it can suffer from poor scalability and may also get stuck in local
minimum. In this paper, we focus on SVMs and propose the WellSVM via a novel
label generation strategy. This leads to a convex relaxation of the original
MIP, which is at least as tight as existing convex Semi-Definite Programming
(SDP) relaxations. Moreover, the WellSVM can be solved via a sequence of SVM
subproblems that are much more scalable than previous convex SDP relaxations.
Experiments on three weakly labeled learning tasks, namely, (i) semi-supervised
learning; (ii) multi-instance learning for locating regions of interest in
content-based information retrieval; and (iii) clustering, clearly demonstrate
improved performance, and WellSVM is also readily applicable on large data
sets.