pwc-archive/papers-with-abstracts huggingface dataset:
Random feedback weights support learning in deep neural networks
Authors: Timothy P. Lillicrap, Daniel Cownden, Douglas B. Tweed, Colin J. Akerman
Date: 2014-11-02 00:00:00

The brain processes information through many layers of neurons. This deep
architecture is representationally powerful, but it complicates learning by
making it hard to identify the responsible neurons when a mistake is made. In
machine learning, the backpropagation algorithm assigns blame to a neuron by
computing exactly how it contributed to an error. To do this, it multiplies
error signals by matrices consisting of all the synaptic weights on the
neuron's axon and farther downstream. This operation requires a precisely
choreographed transport of synaptic weight information, which is thought to be
impossible in the brain. Here we present a surprisingly simple algorithm for
deep learning, which assigns blame by multiplying error signals by random
synaptic weights. We show that a network can learn to extract useful
information from signals sent through these random feedback connections. In
essence, the network learns to learn. We demonstrate that this new mechanism
performs as quickly and accurately as backpropagation on a variety of problems
and describe the principles which underlie its function. Our demonstration
provides a plausible basis for how a neuron can be adapted using error signals
generated at distal locations in the brain, and thus dispels long-held
assumptions about the algorithmic constraints on learning in neural circuits.
A Heuristic Method for Solving the Problem of Partitioning Graphs with Supply and Demand
Authors: Raka Jovanovic, Abdelkader Bousselham, Stefan Voss
Date: 2014-11-02 00:00:00

In this paper we present a greedy algorithm for solving the problem of the
maximum partitioning of graphs with supply and demand (MPGSD). The goal of the
method is to solve the MPGSD for large graphs in a reasonable time limit. This
is done by using a two stage greedy algorithm, with two corresponding types of
heuristics. The solutions acquired in this way are improved by applying a
computationally inexpensive, hill climbing like, greedy correction procedure.
In our numeric experiments we analyze different heuristic functions for each
stage of the greedy algorithm, and show that their performance is highly
dependent on the properties of the specific instance. Our tests show that by
exploring a relatively small number of solutions generated by combining
different heuristic functions, and applying the proposed correction procedure
we can find solutions within only a few percent of the optimal ones.
A Multi-Heuristic Approach for Solving the Pre-Marshalling Problem
Authors: Raka Jovanovic, Milan Tuba, Stefan Voss
Date: 2014-11-02 00:00:00

Minimizing the number of reshuffling operations at maritime container
terminals incorporates the Pre-Marshalling Problem (PMP) as an important
problem. Based on an analysis of existing solution approaches we develop new
heuristics utilizing specific properties of problem instances of the PMP. We
show that the heuristic performance is highly dependent on these properties. We
introduce a new method that exploits a greedy heuristic of four stages, where
for each of these stages several different heuristics may be applied. Instead
of using randomization to improve the performance of the heuristic, we
repetitively generate a number of solutions by using a combination of different
heuristics for each stage. In doing so, only a small number of solutions is
generated for which we intend that they do not have undesirable properties,
contrary to the case when simple randomization is used. Our experiments show
that such a deterministic algorithm significantly outperforms the original
nondeterministic method when the quality of found solutions is observed, with a
much lower number of generated solutions.
Cuckoo Search Inspired Hybridization of the Nelder-Mead Simplex Algorithm Applied to Optimization of Photovoltaic Cells
Authors: Raka Jovanovic, Sabre Kais, Fahhad H. Alharbi
Date: 2014-11-02 00:00:00

A new hybridization of the Cuckoo Search (CS) is developed and applied to
optimize multi-cell solar systems; namely multi-junction and split spectrum
cells. The new approach consists of combining the CS with the Nelder-Mead
method. More precisely, instead of using single solutions as nests for the CS,
we use the concept of a simplex which is used in the Nelder-Mead algorithm.
This makes it possible to use the flip operation introduces in the Nelder-Mead
algorithm instead of the Levy flight which is a standard part of the CS. In
this way, the hybridized algorithm becomes more robust and less sensitive to
parameter tuning which exists in CS. The goal of our work was to optimize the
performance of multi-cell solar systems. Although the underlying problem
consists of the minimization of a function of a relatively small number of
parameters, the difficulty comes from the fact that the evaluation of the
function is complex and only a small number of evaluations is possible. In our
test, we show that the new method has a better performance when compared to
similar but more compex hybridizations of Nelder-Mead algorithm using genetic
algorithms or particle swarm optimization on standard benchmark functions.
Finally, we show that the new method outperforms some standard meta-heuristics
for the problem of interest.
Extension of SBL Algorithms for the Recovery of Block Sparse Signals with Intra-Block Correlation
Authors: Zhilin Zhang, Bhaskar D. Rao
Date: 2012-01-04 00:00:00

We examine the recovery of block sparse signals and extend the framework in
two important directions; one by exploiting signals' intra-block correlation
and the other by generalizing signals' block structure. We propose two families
of algorithms based on the framework of block sparse Bayesian learning (BSBL).
One family, directly derived from the BSBL framework, requires knowledge of the
block structure. Another family, derived from an expanded BSBL framework, is
based on a weaker assumption on the block structure, and can be used when the
block structure is completely unknown. Using these algorithms we show that
exploiting intra-block correlation is very helpful in improving recovery
performance. These algorithms also shed light on how to modify existing
algorithms or design new ones to exploit such correlation and improve
performance.
Compressed Sensing of EEG for Wireless Telemonitoring with Low Energy Consumption and Inexpensive Hardware
Authors: Zhilin Zhang, Tzyy-Ping Jung, Scott Makeig, Bhaskar D. Rao
Date: 2012-06-13 00:00:00
Tasks: compressed sensing, Data Compression, EEG, Electroencephalogram (EEG)

Telemonitoring of electroencephalogram (EEG) through wireless body-area
networks is an evolving direction in personalized medicine. Among various
constraints in designing such a system, three important constraints are energy
consumption, data compression, and device cost. Conventional data compression
methodologies, although effective in data compression, consumes significant
energy and cannot reduce device cost. Compressed sensing (CS), as an emerging
data compression methodology, is promising in catering to these constraints.
However, EEG is non-sparse in the time domain and also non-sparse in
transformed domains (such as the wavelet domain). Therefore, it is extremely
difficult for current CS algorithms to recover EEG with the quality that
satisfies the requirements of clinical diagnosis and engineering applications.
Recently, Block Sparse Bayesian Learning (BSBL) was proposed as a new method to
the CS problem. This study introduces the technique to the telemonitoring of
EEG. Experimental results show that its recovery quality is better than
state-of-the-art CS algorithms, and sufficient for practical use. These results
suggest that BSBL is very promising for telemonitoring of EEG and other
non-sparse physiological signals.
Compressed Sensing for Energy-Efficient Wireless Telemonitoring of Noninvasive Fetal ECG via Block Sparse Bayesian Learning
Authors: Zhilin Zhang, Tzyy-Ping Jung, Scott Makeig, Bhaskar D. Rao
Date: 2012-05-07 00:00:00
Tasks: compressed sensing, CPU, Data Compression

Fetal ECG (FECG) telemonitoring is an important branch in telemedicine. The
design of a telemonitoring system via a wireless body-area network with low
energy consumption for ambulatory use is highly desirable. As an emerging
technique, compressed sensing (CS) shows great promise in
compressing/reconstructing data with low energy consumption. However, due to
some specific characteristics of raw FECG recordings such as non-sparsity and
strong noise contamination, current CS algorithms generally fail in this
application.
  This work proposes to use the block sparse Bayesian learning (BSBL) framework
to compress/reconstruct non-sparse raw FECG recordings. Experimental results
show that the framework can reconstruct the raw recordings with high quality.
Especially, the reconstruction does not destroy the interdependence relation
among the multichannel recordings. This ensures that the independent component
analysis decomposition of the reconstructed recordings has high fidelity.
Furthermore, the framework allows the use of a sparse binary sensing matrix
with much fewer nonzero entries to compress recordings. Particularly, each
column of the matrix can contain only two nonzero entries. This shows the
framework, compared to other algorithms such as current CS algorithms and
wavelet algorithms, can greatly reduce code execution in CPU in the data
compression stage.
Image color transfer to evoke different emotions based on color combinations
Authors: Li He, Hairong Qi, Russell Zaretzki
Date: 2013-07-12 00:00:00

In this paper, a color transfer framework to evoke different emotions for
images based on color combinations is proposed. The purpose of this color
transfer is to change the "look and feel" of images, i.e., evoking different
emotions. Colors are confirmed as the most attractive factor in images. In
addition, various studies in both art and science areas have concluded that
other than single color, color combinations are necessary to evoke specific
emotions. Therefore, we propose a novel framework to transfer color of images
based on color combinations, using a predefined color emotion model. The
contribution of this new framework is three-fold. First, users do not need to
provide reference images as used in traditional color transfer algorithms. In
most situations, users may not have enough aesthetic knowledge or path to
choose desired reference images. Second, because of the usage of color
combinations instead of single color for emotions, a new color transfer
algorithm that does not require an image library is proposed. Third, again
because of the usage of color combinations, artifacts that are normally seen in
traditional frameworks using single color are avoided. We present encouraging
results generated from this new framework and its potential in several possible
applications including color transfer of photos and paintings.
Synchronization Clustering based on a Linearized Version of Vicsek model
Authors: Xinquan Chen
Date: 2014-11-02 00:00:00
Tasks: Clustering

This paper presents a kind of effective synchronization clustering method
based on a linearized version of Vicsek model. This method can be represented
by an Effective Synchronization Clustering algorithm (ESynC), an Improved
version of ESynC algorithm (IESynC), a Shrinking Synchronization Clustering
algorithm based on another linear Vicsek model (SSynC), and an effective
Multi-level Synchronization Clustering algorithm (MSynC). After some analysis
and comparisions, we find that ESynC algorithm based on the Linearized version
of the Vicsek model has better synchronization effect than SynC algorithm based
on an extensive Kuramoto model and a similar synchronization clustering
algorithm based on the original Vicsek model. By simulated experiments of some
artificial data sets, we observe that ESynC algorithm, IESynC algorithm, and
SSynC algorithm can get better synchronization effect although it needs less
iterative times and less time than SynC algorithm. In some simulations, we also
observe that IESynC algorithm and SSynC algorithm can get some improvements in
time cost than ESynC algorithm. At last, it gives some research expectations to
popularize this algorithm.
A Novel Method to Extract Rocks from Mars Images
Authors: Shuliang Wang, Yasen Chen
Date: 2014-03-13 00:00:00

In this paper, a novel method is proposed to extract rocks from Martian
surface images by using 8 data field. It models the interaction between two
pixels of an image in the context of imagery 9 characteristics. First,
foreground rocks are differed from background information by binarizing 10
image on roughly partitioned images. Second, foreground rocks are grouped into
clusters by 11 locating the centers and edges of clusters in data field via
hierarchical grids. Third, the target 12 rocks are discovered for the Mars
Exploration Rover (MER) to keep healthy paths. The 13 experiment with images
taken by MER shows the proposed method is practical and potential.
Spectral Methods meet EM: A Provably Optimal Algorithm for Crowdsourcing
Authors: Yuchen Zhang, Xi Chen, Dengyong Zhou, Michael. I. Jordan
Date: 2014-06-15 00:00:00
Proceeding: NeurIPS 2014 12

Crowdsourcing is a popular paradigm for effectively collecting labels at low
cost. The Dawid-Skene estimator has been widely used for inferring the true
labels from the noisy labels provided by non-expert crowdsourcing workers.
However, since the estimator maximizes a non-convex log-likelihood function, it
is hard to theoretically justify its performance. In this paper, we propose a
two-stage efficient algorithm for multi-class crowd labeling problems. The
first stage uses the spectral method to obtain an initial estimate of
parameters. Then the second stage refines the estimation by optimizing the
objective function of the Dawid-Skene estimator via the EM algorithm. We show
that our algorithm achieves the optimal convergence rate up to a logarithmic
factor. We conduct extensive experiments on synthetic and real datasets.
Experimental results demonstrate that the proposed algorithm is comparable to
the most accurate empirical approach, while outperforming several other
recently proposed methods.
Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms
Authors: Siu-On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun
Date: 2014-11-01 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Density Estimation

Let $p$ be an unknown and arbitrary probability distribution over $[0,1)$. We
consider the problem of {\em density estimation}, in which a learning algorithm
is given i.i.d. draws from $p$ and must (with high probability) output a
hypothesis distribution that is close to $p$. The main contribution of this
paper is a highly efficient density estimation algorithm for learning using a
variable-width histogram, i.e., a hypothesis distribution with a piecewise
constant probability density function.
  In more detail, for any $k$ and $\epsilon$, we give an algorithm that makes
$\tilde{O}(k/\epsilon^2)$ draws from $p$, runs in $\tilde{O}(k/\epsilon^2)$
time, and outputs a hypothesis distribution $h$ that is piecewise constant with
$O(k \log^2(1/\epsilon))$ pieces. With high probability the hypothesis $h$
satisfies $d_{\mathrm{TV}}(p,h) \leq C \cdot \mathrm{opt}_k(p) + \epsilon$,
where $d_{\mathrm{TV}}$ denotes the total variation distance (statistical
distance), $C$ is a universal constant, and $\mathrm{opt}_k(p)$ is the smallest
total variation distance between $p$ and any $k$-piecewise constant
distribution. The sample size and running time of our algorithm are optimal up
to logarithmic factors. The "approximation factor" $C$ in our result is
inherent in the problem, as we prove that no algorithm with sample size bounded
in terms of $k$ and $\epsilon$ can achieve $C<2$ regardless of what kind of
hypothesis distribution it uses.
Entropy of Overcomplete Kernel Dictionaries
Authors: Paul Honeine
Date: 2014-11-01 00:00:00
Tasks: Diversity, Gaussian Processes

In signal analysis and synthesis, linear approximation theory considers a
linear decomposition of any given signal in a set of atoms, collected into a
so-called dictionary. Relevant sparse representations are obtained by relaxing
the orthogonality condition of the atoms, yielding overcomplete dictionaries
with an extended number of atoms. More generally than the linear decomposition,
overcomplete kernel dictionaries provide an elegant nonlinear extension by
defining the atoms through a mapping kernel function (e.g., the gaussian
kernel). Models based on such kernel dictionaries are used in neural networks,
gaussian processes and online learning with kernels.
  The quality of an overcomplete dictionary is evaluated with a diversity
measure the distance, the approximation, the coherence and the Babel measures.
In this paper, we develop a framework to examine overcomplete kernel
dictionaries with the entropy from information theory. Indeed, a higher value
of the entropy is associated to a further uniform spread of the atoms over the
space. For each of the aforementioned diversity measures, we derive lower
bounds on the entropy. Several definitions of the entropy are examined, with an
extensive analysis in both the input space and the mapped feature space.
Surrogate Search As a Way to Combat Harmful Effects of Ill-behaved Evaluation Functions
Authors: William Cushing, J. Benton, Patrick Eyerich, Subbarao Kambhampati
Date: 2014-11-01 00:00:00

Recently, several researchers have found that cost-based satisficing search
with A* often runs into problems. Although some "work arounds" have been
proposed to ameliorate the problem, there has been little concerted effort to
pinpoint its origin. In this paper, we argue that the origins of this problem
can be traced back to the fact that most planners that try to optimize cost
also use cost-based evaluation functions (i.e., f(n) is a cost estimate). We
show that cost-based evaluation functions become ill-behaved whenever there is
a wide variance in action costs; something that is all too common in planning
domains. The general solution to this malady is what we call a surrogatesearch,
where a surrogate evaluation function that doesn't directly track the cost
objective, and is resistant to cost-variance, is used. We will discuss some
compelling choices for surrogate evaluation functions that are based on size
rather that cost. Of particular practical interest is a cost-sensitive version
of size-based evaluation function -- where the heuristic estimates the size of
cheap paths, as it provides attractive quality vs. speed tradeoffs
A Two-phase Decision Support Framework for the Automatic Screening of Digital Fundus Images
Authors: Balint Antal, Andras Hajdu, Zsuzsanna Maros-Szabo, Zsolt Torok, Adrienne Csutak, Tunde Peto
Date: 2014-11-01 00:00:00

In this paper we give a brief review on the present status of automated
detection systems describe for the screening of diabetic retinopathy. We
further detail an enhanced detection procedure that consists of two steps.
First, a pre-screening algorithm is considered to classify the input digital
fundus images based on the severity of abnormalities. If an image is found to
be seriously abnormal, it will not be analysed further with robust lesion
detector algorithms. As a further improvement, we introduce a novel feature
extraction approach based on clinical observations. The second step of the
proposed method detects regions of interest with possible lesions on the images
that previously passed the pre-screening step. These regions will serve as
input to the specific lesion detectors for detailed analysis. This procedure
can increase the computational performance of a screening system. Experimental
results show that both two steps of the proposed approach are capable to
efficiently exclude a large amount of data from further processing, thus, to
decrease the computational burden of the automatic screening system.
Detection of texts in natural images
Authors: Gowtham Rangarajan Raman
Date: 2014-11-01 00:00:00

A framework that makes use of Connected components and supervised Support
machine to recognise texts is proposed. The image is preprocessed and and edge
graph is calculated using a probabilistic framework to compensate for
photometric noise. Connected components over the resultant image is calculated,
which is bounded and then pruned using geometric constraints. Finally a Gabor
Feature based SVM is used to classify the presence of text in the candidates.
The proposed method was tested with ICDAR 10 dataset and few other images
available on the internet. It resulted in a recall and precision metric of 0.72
and 0.88 comfortably better than the benchmark Eiphstein's algorithm. The
proposed method recorded a 0.70 and 0.74 in natural images which is
significantly better than current methods on natural images. The proposed
method also scales almost linearly for high resolution, cluttered images.
Combining pattern-based CRFs and weighted context-free grammars
Authors: Rustem Takhanov, Vladimir Kolmogorov
Date: 2014-04-22 00:00:00

We consider two models for the sequence labeling (tagging) problem. The first
one is a {\em Pattern-Based Conditional Random Field }(\PB), in which the
energy of a string (chain labeling) $x=x_1\ldots x_n\in D^n$ is a sum of terms
over intervals $[i,j]$ where each term is non-zero only if the substring
$x_i\ldots x_j$ equals a prespecified word $w\in \Lambda$. The second model is
a {\em Weighted Context-Free Grammar }(\WCFG) frequently used for natural
language processing. \PB and \WCFG encode local and non-local interactions
respectively, and thus can be viewed as complementary.
  We propose a {\em Grammatical Pattern-Based CRF model }(\GPB) that combines
the two in a natural way. We argue that it has certain advantages over existing
approaches such as the {\em Hybrid model} of Bened{\'i} and Sanchez that
combines {\em $\mbox{$N$-grams}$} and \WCFGs. The focus of this paper is to
analyze the complexity of inference tasks in a \GPB such as computing MAP. We
present a polynomial-time algorithm for general \GPBs and a faster version for
a special case that we call {\em Interaction Grammars}.
Complex Events Recognition under Uncertainty in a Sensor Network
Authors: Atul Kanaujia, Tae Eun Choe, Hongli Deng
Date: 2014-11-01 00:00:00
Tasks: Decision Making, Decision Making Under Uncertainty

Automated extraction of semantic information from a network of sensors for
cognitive analysis and human-like reasoning is a desired capability in future
ground surveillance systems. We tackle the problem of complex decision making
under uncertainty in network information environment, where lack of effective
visual processing tools, incomplete domain knowledge frequently cause
uncertainty in the visual primitives, leading to sub-optimal decisions. While
state-of-the-art vision techniques exist in detecting visual entities (humans,
vehicles and scene elements) in an image, a missing functionality is the
ability to merge the information to reveal meaningful information for high
level inference. In this work, we develop a probabilistic first order predicate
logic(FOPL) based reasoning system for recognizing complex events in
synchronized stream of videos, acquired from sensors with non-overlapping
fields of view. We adopt Markov Logic Network(MLN) as a tool to model
uncertainty in observations, and fuse information extracted from heterogeneous
data in a probabilistically consistent way. MLN overcomes strong dependence on
pure empirical learning by incorporating domain knowledge, in the form of
user-defined rules and confidences associated with them. This work demonstrates
that the MLN based decision control system can be made scalable to model
statistical relations between a variety of entities and over long video
sequences. Experiments with real-world data, under a variety of settings,
illustrate the mathematical soundness and wide-ranging applicability of our
approach.