pwc-archive/papers-with-abstracts huggingface dataset:
Exponentially Fast Parameter Estimation in Networks Using Distributed Dual Averaging
Authors: Shahin Shahrampour, Ali Jadbabaie
Date: 2013-09-10 00:00:00
Tasks: parameter estimation

In this paper we present an optimization-based view of distributed parameter
estimation and observational social learning in networks. Agents receive a
sequence of random, independent and identically distributed (i.i.d.) signals,
each of which individually may not be informative about the underlying true
state, but the signals together are globally informative enough to make the
true state identifiable. Using an optimization-based characterization of
Bayesian learning as proximal stochastic gradient descent (with
Kullback-Leibler divergence from a prior as a proximal function), we show how
to efficiently use a distributed, online variant of Nesterov's dual averaging
method to solve the estimation with purely local information. When the true
state is globally identifiable, and the network is connected, we prove that
agents eventually learn the true parameter using a randomized gossip scheme. We
demonstrate that with high probability the convergence is exponentially fast
with a rate dependent on the KL divergence of observations under the true state
from observations under the second likeliest state. Furthermore, our work also
highlights the possibility of learning under continuous adaptation of network
which is a consequence of employing constant, unit stepsize for the algorithm.
A solution concept for games with altruism and cooperation
Authors: Valerio Capraro
Date: 2013-02-16 00:00:00

Over the years, numerous experiments have been accumulated to show that
cooperation is not casual and depends on the payoffs of the game. These
findings suggest that humans have attitude to cooperation by nature and the
same person may act more or less cooperatively depending on the particular
payoffs. In other words, people do not act a priori as single agents, but they
forecast how the game would be played if they formed coalitions and then they
play according to their best forecast. In this paper we formalize this idea and
we define a new solution concept for one-shot normal form games. We prove that
this \emph{cooperative equilibrium} exists for all finite games and it explains
a number of different experimental findings, such as (1) the rate of
cooperation in the Prisoner's dilemma depends on the cost-benefit ratio; (2)
the rate of cooperation in the Traveler's dilemma depends on the bonus/penalty;
(3) the rate of cooperation in the Publig Goods game depends on the pro-capite
marginal return and on the numbers of players; (4) the rate of cooperation in
the Bertrand competition depends on the number of players; (5) players tend to
be fair in the bargaining problem; (6) players tend to be fair in the Ultimatum
game; (7) players tend to be altruist in the Dictator game; (8) offers in the
Ultimatum game are larger than offers in the Dictator game.
Spectral Clustering with Imbalanced Data
Authors: Jing Qian, Venkatesh Saligrama
Date: 2013-09-09 00:00:00
Tasks: Clustering, graph partitioning

Spectral clustering is sensitive to how graphs are constructed from data
particularly when proximal and imbalanced clusters are present. We show that
Ratio-Cut (RCut) or normalized cut (NCut) objectives are not tailored to
imbalanced data since they tend to emphasize cut sizes over cut values. We
propose a graph partitioning problem that seeks minimum cut partitions under
minimum size constraints on partitions to deal with imbalanced data. Our
approach parameterizes a family of graphs, by adaptively modulating node
degrees on a fixed node set, to yield a set of parameter dependent cuts
reflecting varying levels of imbalance. The solution to our problem is then
obtained by optimizing over these parameters. We present rigorous limit cut
analysis results to justify our approach. We demonstrate the superiority of our
method through unsupervised and semi-supervised experiments on synthetic and
real data sets.
Technical Report: Distribution Temporal Logic: Combining Correctness with Quality of Estimation
Authors: Austin Jones, Mac Schwager, Calin Belta
Date: 2013-09-09 00:00:00

We present a new temporal logic called Distribution Temporal Logic (DTL)
defined over predicates of belief states and hidden states of partially
observable systems. DTL can express properties involving uncertainty and
likelihood that cannot be described by existing logics. A co-safe formulation
of DTL is defined and algorithmic procedures are given for monitoring
executions of a partially observable Markov decision process with respect to
such formulae. A simulation case study of a rescue robotics application
outlines our approach.
Contour Manifolds and Optimal Transport
Authors: Bernhard Schmitzer, Christoph Schnörr
Date: 2013-09-09 00:00:00
Tasks: Segmentation, Semantic Segmentation

Describing shapes by suitable measures in object segmentation, as proposed in
[24], allows to combine the advantages of the representations as parametrized
contours and indicator functions. The pseudo-Riemannian structure of optimal
transport can be used to model shapes in ways similar as with contours, while
the Kantorovich functional enables the application of convex optimization
methods for global optimality of the segmentation functional.
  In this paper we provide a mathematical study of the shape measure
representation and its relation to the contour description. In particular we
show that the pseudo-Riemannian structure of optimal transport, when restricted
to the set of shape measures, yields a manifold which is diffeomorphic to the
manifold of closed contours. A discussion of the metric induced by optimal
transport and the corresponding geodesic equation is given.
Application of Artificial Neural Networks in Estimating Participation in Elections
Authors: Seyyed Reza Khaze, Mohammad Masdari, Sohrab Hojjatkhah
Date: 2013-09-09 00:00:00

It is approved that artificial neural networks can be considerable effective
in anticipating and analyzing flows in which traditional methods and statics
are not able to solve. in this article, by using two-layer feedforward network
with tan-sigmoid transmission function in input and output layers, we can
anticipate participation rate of public in kohgiloye and boyerahmad province in
future presidential election of islamic republic of iran with 91% accuracy. the
assessment standards of participation such as confusion matrix and roc diagrams
have been approved our claims.
Task-Driven Dictionary Learning
Authors: Julien Mairal, Francis Bach, Jean Ponce
Date: 2010-09-27 00:00:00
Tasks: Classification, compressed sensing, Dictionary Learning, General Classification, image-classification, Image Classification

Modeling data with linear combinations of a few elements from a learned
dictionary has been the focus of much recent research in machine learning,
neuroscience and signal processing. For signals such as natural images that
admit such sparse representations, it is now well established that these models
are well suited to restoration tasks. In this context, learning the dictionary
amounts to solving a large-scale matrix factorization problem, which can be
done efficiently with classical optimization tools. The same approach has also
been used for learning features from data for other purposes, e.g., image
classification, but tuning the dictionary in a supervised way for these tasks
has proven to be more difficult. In this paper, we present a general
formulation for supervised dictionary learning adapted to a wide variety of
tasks, and present an efficient algorithm for solving the corresponding
optimization problem. Experiments on handwritten digit classification, digital
art identification, nonlinear inverse image problems, and compressed sensing
demonstrate that our approach is effective in large-scale settings, and is well
suited to supervised and semi-supervised classification, as well as regression
tasks for data that admit sparse representations.
Real-Time and Continuous Hand Gesture Spotting: an Approach Based on Artificial Neural Networks
Authors: Pedro Neto, Dário Pereira, Norberto Pires, Paulo Moreira
Date: 2013-09-09 00:00:00
Tasks: Gesture Recognition

New and more natural human-robot interfaces are of crucial interest to the
evolution of robotics. This paper addresses continuous and real-time hand
gesture spotting, i.e., gesture segmentation plus gesture recognition. Gesture
patterns are recognized by using artificial neural networks (ANNs) specifically
adapted to the process of controlling an industrial robot. Since in continuous
gesture recognition the communicative gestures appear intermittently with the
noncommunicative, we are proposing a new architecture with two ANNs in series
to recognize both kinds of gesture. A data glove is used as interface
technology. Experimental results demonstrated that the proposed solution
presents high recognition rates (over 99% for a library of ten gestures and
over 96% for a library of thirty gestures), low training and learning time and
a good capacity to generalize from particular situations.
Structure Learning of Probabilistic Logic Programs by Searching the Clause Space
Authors: Elena Bellodi, Fabrizio Riguzzi
Date: 2013-09-09 00:00:00

Learning probabilistic logic programming languages is receiving an increasing
attention and systems are available for learning the parameters (PRISM,
LeProbLog, LFI-ProbLog and EMBLEM) or both the structure and the parameters
(SEM-CP-logic and SLIPCASE) of these languages. In this paper we present the
algorithm SLIPCOVER for "Structure LearnIng of Probabilistic logic programs by
searChing OVER the clause space". It performs a beam search in the space of
probabilistic clauses and a greedy search in the space of theories, using the
log likelihood of the data as the guiding heuristics. To estimate the log
likelihood SLIPCOVER performs Expectation Maximization with EMBLEM. The
algorithm has been tested on five real world datasets and compared with
SLIPCASE, SEM-CP-logic, Aleph and two algorithms for learning Markov Logic
Networks (Learning using Structural Motifs (LSM) and ALEPH++ExactL1). SLIPCOVER
achieves higher areas under the precision-recall and ROC curves in most cases.
Single image super resolution in spatial and wavelet domain
Authors: Sapan Naik, Nikunj Patel
Date: 2013-09-09 00:00:00
Tasks: Denoising, Image Super-Resolution, Super-Resolution

Recently single image super resolution is very important research area to
generate high resolution image from given low resolution image. Algorithms of
single image resolution are mainly based on wavelet domain and spatial domain.
Filters support to model the regularity of natural images is exploited in
wavelet domain while edges of images get sharp during up sampling in spatial
domain. Here single image super resolution algorithm is presented which based
on both spatial and wavelet domain and take the advantage of both. Algorithm is
iterative and use back projection to minimize reconstruction error. Wavelet
based denoising method is also introduced to remove noise.
Regret-Based Multi-Agent Coordination with Uncertain Task Rewards
Authors: Feng Wu, Nicholas R. Jennings
Date: 2013-09-08 00:00:00
Tasks: Disaster Response

Many multi-agent coordination problems can be represented as DCOPs. Motivated
by task allocation in disaster response, we extend standard DCOP models to
consider uncertain task rewards where the outcome of completing a task depends
on its current state, which is randomly drawn from unknown distributions. The
goal of solving this problem is to find a solution for all agents that
minimizes the overall worst-case loss. This is a challenging problem for
centralized algorithms because the search space grows exponentially with the
number of agents and is nontrivial for standard DCOP algorithms we have. To
address this, we propose a novel decentralized algorithm that incorporates
Max-Sum with iterative constraint generation to solve the problem by passing
messages among agents. By so doing, our approach scales well and can solve
instances of the task allocation problem with hundreds of agents and tasks.
Variational Bayes Approximations for Clustering via Mixtures of Normal Inverse Gaussian Distributions
Authors: Sanjeena Subedi, Paul D. McNicholas
Date: 2013-09-07 00:00:00
Tasks: Clustering, parameter estimation

Parameter estimation for model-based clustering using a finite mixture of
normal inverse Gaussian (NIG) distributions is achieved through variational
Bayes approximations. Univariate NIG mixtures and multivariate NIG mixtures are
considered. The use of variational Bayes approximations here is a substantial
departure from the traditional EM approach and alleviates some of the
associated computational complexities and uncertainties. Our variational
algorithm is applied to simulated and real data. The paper concludes with
discussion and suggestions for future work.
Finding a most biased coin with fewest flips
Authors: Karthekeyan Chandrasekaran, Richard Karp
Date: 2012-02-16 00:00:00

We study the problem of learning a most biased coin among a set of coins by
tossing the coins adaptively. The goal is to minimize the number of tosses
until we identify a coin i* whose posterior probability of being most biased is
at least 1-delta for a given delta. Under a particular probabilistic model, we
give an optimal algorithm, i.e., an algorithm that minimizes the expected
number of future tosses. The problem is closely related to finding the best arm
in the multi-armed bandit problem using adaptive strategies. Our algorithm
employs an optimal adaptive strategy -- a strategy that performs the best
possible action at each step after observing the outcomes of all previous coin
tosses. Consequently, our algorithm is also optimal for any starting history of
outcomes. To our knowledge, this is the first algorithm that employs an optimal
adaptive strategy under a Bayesian setting for this problem. Our proof of
optimality employs tools from the field of Markov games.
Efficient Monte Carlo Methods for Multi-Dimensional Learning with Classifier Chains
Authors: Jesse Read, Luca Martino, David Luengo
Date: 2012-11-09 00:00:00
Tasks: Classification, General Classification, Multi-Label Classification, MUlTI-LABEL-ClASSIFICATION

Multi-dimensional classification (MDC) is the supervised learning problem
where an instance is associated with multiple classes, rather than with a
single class, as in traditional classification problems. Since these classes
are often strongly correlated, modeling the dependencies between them allows
MDC methods to improve their performance - at the expense of an increased
computational cost. In this paper we focus on the classifier chains (CC)
approach for modeling dependencies, one of the most popular and highest-
performing methods for multi-label classification (MLC), a particular case of
MDC which involves only binary classes (i.e., labels). The original CC
algorithm makes a greedy approximation, and is fast but tends to propagate
errors along the chain. Here we present novel Monte Carlo schemes, both for
finding a good chain sequence and performing efficient inference. Our
algorithms remain tractable for high-dimensional data sets and obtain the best
predictive performance across several real data sets.
A General Two-Step Approach to Learning-Based Hashing
Authors: Guosheng Lin, Chunhua Shen, David Suter, Anton Van Den Hengel
Date: 2013-09-07 00:00:00
Tasks: Vocal Bursts Valence Prediction

Most existing approaches to hashing apply a single form of hash function, and
an optimization process which is typically deeply coupled to this specific
form. This tight coupling restricts the flexibility of the method to respond to
the data, and can result in complex optimization problems that are difficult to
solve. Here we propose a flexible yet simple framework that is able to
accommodate different types of loss functions and hash functions. This
framework allows a number of existing approaches to hashing to be placed in
context, and simplifies the development of new problem-specific hashing
methods. Our framework decomposes hashing learning problem into two steps: hash
bit learning and hash function learning based on the learned bits. The first
step can typically be formulated as binary quadratic problems, and the second
step can be accomplished by training standard binary classifiers. Both problems
have been extensively studied in the literature. Our extensive experiments
demonstrate that the proposed framework is effective, flexible and outperforms
the state-of-the-art.
Radar shadow detection in SAR images using DEM and projections
Authors: V. B. S. Prasath, O. Haddad
Date: 2013-09-07 00:00:00
Tasks: Detecting Shadows, Shadow Detection

Synthetic aperture radar (SAR) images are widely used in target recognition
tasks nowadays. In this letter, we propose an automatic approach for radar
shadow detection and extraction from SAR images utilizing geometric projections
along with the digital elevation model (DEM) which corresponds to the given
geo-referenced SAR image. First, the DEM is rotated into the radar geometry so
that each row would match that of a radar line of sight. Next, we extract the
shadow regions by processing row by row until the image is covered fully. We
test the proposed shadow detection approach on different DEMs and a simulated
1D signals and 2D hills and volleys modeled by various variance based Gaussian
functions. Experimental results indicate the proposed algorithm produces good
results in detecting shadows in SAR images with high resolution.
Efficient Estimation of Word Representations in Vector Space
Authors: Tomas Mikolov, Kai Chen, Greg Corrado, Jeffrey Dean
Date: 2013-01-16 00:00:00
Tasks: Word Similarity

We propose two novel model architectures for computing continuous vector
representations of words from very large data sets. The quality of these
representations is measured in a word similarity task, and the results are
compared to the previously best performing techniques based on different types
of neural networks. We observe large improvements in accuracy at much lower
computational cost, i.e. it takes less than a day to learn high quality word
vectors from a 1.6 billion words data set. Furthermore, we show that these
vectors provide state-of-the-art performance on our test set for measuring
syntactic and semantic word similarities.
Convergence of Nearest Neighbor Pattern Classification with Selective Sampling
Authors: Shaun N. Joseph, Seif Omar Abu Bakr, Gabriel Lugo
Date: 2013-09-06 00:00:00
Tasks: Classification, General Classification

In the panoply of pattern classification techniques, few enjoy the intuitive
appeal and simplicity of the nearest neighbor rule: given a set of samples in
some metric domain space whose value under some function is known, we estimate
the function anywhere in the domain by giving the value of the nearest sample
per the metric. More generally, one may use the modal value of the m nearest
samples, where m is a fixed positive integer (although m=1 is known to be
admissible in the sense that no larger value is asymptotically superior in
terms of prediction error). The nearest neighbor rule is nonparametric and
extremely general, requiring in principle only that the domain be a metric
space. The classic paper on the technique, proving convergence under
independent, identically-distributed (iid) sampling, is due to Cover and Hart
(1967). Because taking samples is costly, there has been much research in
recent years on selective sampling, in which each sample is selected from a
pool of candidates ranked by a heuristic; the heuristic tries to guess which
candidate would be the most "informative" sample. Lindenbaum et al. (2004)
apply selective sampling to the nearest neighbor rule, but their approach
sacrifices the austere generality of Cover and Hart; furthermore, their
heuristic algorithm is complex and computationally expensive. Here we report
recent results that enable selective sampling in the original Cover-Hart
setting. Our results pose three selection heuristics and prove that their
nearest neighbor rule predictions converge to the true pattern. Two of the
algorithms are computationally cheap, with complexity growing linearly in the
number of samples. We believe that these results constitute an important
advance in the art.
A Comparism of the Performance of Supervised and Unsupervised Machine Learning Techniques in evolving Awale/Mancala/Ayo Game Player
Authors: O. A. Randle, O. O. Ogunduyile, T. Zuva, N. A. Fashola
Date: 2013-09-06 00:00:00
Tasks: BIG-bench Machine Learning

Awale games have become widely recognized across the world, for their
innovative strategies and techniques which were used in evolving the agents
(player) and have produced interesting results under various conditions. This
paper will compare the results of the two major machine learning techniques by
reviewing their performance when using minimax, endgame database, a combination
of both techniques or other techniques, and will determine which are the best
techniques.
Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application
Authors: Weiran Wang, Miguel Á. Carreira-Perpiñán
Date: 2013-09-06 00:00:00
Tasks: Clustering

We provide an elementary proof of a simple, efficient algorithm for computing
the Euclidean projection of a point onto the probability simplex. We also show
an application in Laplacian K-modes clustering.
Guided Self-Organization of Input-Driven Recurrent Neural Networks
Authors: Oliver Obst, Joschka Boedecker
Date: 2013-09-06 00:00:00

We review attempts that have been made towards understanding the
computational properties and mechanisms of input-driven dynamical systems like
RNNs, and reservoir computing networks in particular. We provide details on
methods that have been developed to give quantitative answers to the questions
above. Following this, we show how self-organization may be used to improve
reservoirs for better performance, in some cases guided by the measures
presented before. We also present a possible way to quantify task performance
using an information-theoretic approach, and finally discuss promising future
directions aimed at a better understanding of how these systems perform their
computations and how to best guide self-organized processes for their
optimization.
Nested Nonnegative Cone Analysis
Authors: Lingsong Zhang, J. S. Marron, Shu Lu
Date: 2013-08-20 00:00:00

Motivated by the analysis of nonnegative data objects, a novel Nested
Nonnegative Cone Analysis (NNCA) approach is proposed to overcome some
drawbacks of existing methods. The application of traditional PCA/SVD method to
nonnegative data often cause the approximation matrix leave the nonnegative
cone, which leads to non-interpretable and sometimes nonsensical results. The
nonnegative matrix factorization (NMF) approach overcomes this issue, however
the NMF approximation matrices suffer several drawbacks: 1) the factorization
may not be unique, 2) the resulting approximation matrix at a specific rank may
not be unique, and 3) the subspaces spanned by the approximation matrices at
different ranks may not be nested. These drawbacks will cause troubles in
determining the number of components and in multi-scale (in ranks)
interpretability. The NNCA approach proposed in this paper naturally generates
a nested structure, and is shown to be unique at each rank. Simulations are
used in this paper to illustrate the drawbacks of the traditional methods, and
the usefulness of the NNCA method.