pwc-archive/papers-with-abstracts huggingface dataset:
Stochastic Privacy
Authors: Adish Singla, Eric Horvitz, Ece Kamar, Ryen White
Date: 2014-04-22 00:00:00

Online services such as web search and e-commerce applications typically rely
on the collection of data about users, including details of their activities on
the web. Such personal data is used to enhance the quality of service via
personalization of content and to maximize revenues via better targeting of
advertisements and deeper engagement of users on sites. To date, service
providers have largely followed the approach of either requiring or requesting
consent for opting-in to share their data. Users may be willing to share
private information in return for better quality of service or for incentives,
or in return for assurances about the nature and extend of the logging of data.
We introduce \emph{stochastic privacy}, a new approach to privacy centering on
a simple concept: A guarantee is provided to users about the upper-bound on the
probability that their personal data will be used. Such a probability, which we
refer to as \emph{privacy risk}, can be assessed by users as a preference or
communicated as a policy by a service provider. Service providers can work to
personalize and to optimize revenues in accordance with preferences about
privacy risk. We present procedures, proofs, and an overall system for
maximizing the quality of services, while respecting bounds on allowable or
communicated privacy risk. We demonstrate the methodology with a case study and
evaluation of the procedures applied to web search personalization. We show how
we can achieve near-optimal utility of accessing information with provable
guarantees on the probability of sharing data.
Approximate Inference for Nonstationary Heteroscedastic Gaussian process Regression
Authors: Ville Tolvanen, Pasi Jylänki, Aki Vehtari
Date: 2014-04-22 00:00:00
Tasks: regression

This paper presents a novel approach for approximate integration over the
uncertainty of noise and signal variances in Gaussian process (GP) regression.
Our efficient and straightforward approach can also be applied to integration
over input dependent noise variance (heteroscedasticity) and input dependent
signal variance (nonstationarity) by setting independent GP priors for the
noise and signal variances. We use expectation propagation (EP) for inference
and compare results to Markov chain Monte Carlo in two simulated data sets and
three empirical examples. The results show that EP produces comparable results
with less computational burden.
Mixed Strategy May Outperform Pure Strategy: An Initial Study
Authors: Jun He, Wei Hou, Hongbin Dong, Feidun He
Date: 2013-03-13 00:00:00
Tasks: Evolutionary Algorithms

In pure strategy meta-heuristics, only one search strategy is applied for all
time. In mixed strategy meta-heuristics, each time one search strategy is
chosen from a strategy pool with a probability and then is applied. An example
is classical genetic algorithms, where either a mutation or crossover operator
is chosen with a probability each time. The aim of this paper is to compare the
performance between mixed strategy and pure strategy meta-heuristic algorithms.
First an experimental study is implemented and results demonstrate that mixed
strategy evolutionary algorithms may outperform pure strategy evolutionary
algorithms on the 0-1 knapsack problem in up to 77.8% instances. Then
Complementary Strategy Theorem is rigorously proven for applying mixed strategy
at the population level. The theorem asserts that given two meta-heuristic
algorithms where one uses pure strategy 1 and another uses pure strategy 2, the
condition of pure strategy 2 being complementary to pure strategy 1 is
sufficient and necessary if there exists a mixed strategy meta-heuristics
derived from these two pure strategies and its expected number of generations
to find an optimal solution is no more than that of using pure strategy 1 for
any initial population, and less than that of using pure strategy 1 for some
initial population.
A Polynomial Time Approximation Scheme for a Single Machine Scheduling Problem Using a Hybrid Evolutionary Algorithm
Authors: Boris Mitavskiy, Jun He
Date: 2012-02-08 00:00:00
Tasks: Articles, Combinatorial Optimization, Evolutionary Algorithms, Heuristic Search, Scheduling

Nowadays hybrid evolutionary algorithms, i.e, heuristic search algorithms
combining several mutation operators some of which are meant to implement
stochastically a well known technique designed for the specific problem in
question while some others playing the role of random search, have become
rather popular for tackling various NP-hard optimization problems. While
empirical studies demonstrate that hybrid evolutionary algorithms are
frequently successful at finding solutions having fitness sufficiently close to
the optimal, many fewer articles address the computational complexity in a
mathematically rigorous fashion. This paper is devoted to a mathematically
motivated design and analysis of a parameterized family of evolutionary
algorithms which provides a polynomial time approximation scheme for one of the
well-known NP-hard combinatorial optimization problems, namely the "single
machine scheduling problem without precedence constraints". The authors hope
that the techniques and ideas developed in this article may be applied in many
other situations.
Timed Soft Concurrent Constraint Programs: An Interleaved and a Parallel Approach
Authors: Stefano Bistarelli, Maurizio Gabbrielli, Maria Chiara Meo, Francesco Santini
Date: 2014-02-24 00:00:00

We propose a timed and soft extension of Concurrent Constraint Programming.
The time extension is based on the hypothesis of bounded asynchrony: the
computation takes a bounded period of time and is measured by a discrete global
clock. Action prefixing is then considered as the syntactic marker which
distinguishes a time instant from the next one. Supported by soft constraints
instead of crisp ones, tell and ask agents are now equipped with a preference
(or consistency) threshold which is used to determine their success or
suspension. In the paper we provide a language to describe the agents behavior,
together with its operational and denotational semantics, for which we also
prove the compositionality and correctness properties. After presenting a
semantics using maximal parallelism of actions, we also describe a version for
their interleaving on a single processor (with maximal parallelism for time
elapsing). Coordinating agents that need to take decisions both on preference
values and time events may benefit from this language. To appear in Theory and
Practice of Logic Programming (TPLP).
Concurrent bandits and cognitive radio networks
Authors: Orly Avner, Shie Mannor
Date: 2014-04-22 00:00:00
Tasks: Collision Avoidance

We consider the problem of multiple users targeting the arms of a single
multi-armed stochastic bandit. The motivation for this problem comes from
cognitive radio networks, where selfish users need to coexist without any side
communication between them, implicit cooperation or common control. Even the
number of users may be unknown and can vary as users join or leave the network.
We propose an algorithm that combines an $\epsilon$-greedy learning rule with a
collision avoidance mechanism. We analyze its regret with respect to the
system-wide optimum and show that sub-linear regret can be obtained in this
setting. Experiments show dramatic improvement compared to other algorithms for
this setting.
Attractor Metadynamics in Adapting Neural Networks
Authors: Claudius Gros, Mathias Linkerhand, Valentin Walther
Date: 2014-04-22 00:00:00

Slow adaption processes, like synaptic and intrinsic plasticity, abound in
the brain and shape the landscape for the neural dynamics occurring on
substantially faster timescales. At any given time the network is characterized
by a set of internal parameters, which are adapting continuously, albeit
slowly. This set of parameters defines the number and the location of the
respective adiabatic attractors. The slow evolution of network parameters hence
induces an evolving attractor landscape, a process which we term attractor
metadynamics. We study the nature of the metadynamics of the attractor
landscape for several continuous-time autonomous model networks. We find both
first- and second-order changes in the location of adiabatic attractors and
argue that the study of the continuously evolving attractor landscape
constitutes a powerful tool for understanding the overall development of the
neural dynamics.
GP-Localize: Persistent Mobile Robot Localization using Online Sparse Gaussian Process Observation Model
Authors: Nuo Xu, Kian Hsiang Low, Jie Chen, Keng Kiat Lim, Etkin Baris Ozgul
Date: 2014-04-21 00:00:00

Central to robot exploration and mapping is the task of persistent
localization in environmental fields characterized by spatially correlated
measurements. This paper presents a Gaussian process localization (GP-Localize)
algorithm that, in contrast to existing works, can exploit the spatially
correlated field measurements taken during a robot's exploration (instead of
relying on prior training data) for efficiently and scalably learning the GP
observation model online through our proposed novel online sparse GP. As a
result, GP-Localize is capable of achieving constant time and memory (i.e.,
independent of the size of the data) per filtering step, which demonstrates the
practical feasibility of using GPs for persistent robot localization and
autonomy. Empirical evaluation via simulated experiments with real-world
datasets and a real robot experiment shows that GP-Localize outperforms
existing GP localization algorithms.
A Comparison of Clustering and Missing Data Methods for Health Sciences
Authors: Ran Zhao, Deanna Needell, Christopher Johansen, Jerry L. Grenard
Date: 2014-04-22 00:00:00
Tasks: Clustering, Compressive Sensing, Matrix Completion

In this paper, we compare and analyze clustering methods with missing data in
health behavior research. In particular, we propose and analyze the use of
compressive sensing's matrix completion along with spectral clustering to
cluster health related data. The empirical tests and real data results show
that these methods can outperform standard methods like LPA and FIML, in terms
of lower misclassification rates in clustering and better matrix completion
performance in missing data problems. According to our examination, a possible
explanation of these improvements is that spectral clustering takes advantage
of high data dimension and compressive sensing methods utilize the
near-to-low-rank property of health data.
Linking Geographic Vocabularies through WordNet
Authors: Andrea Ballatore, Michela Bertolotto, David C. Wilson
Date: 2014-04-22 00:00:00

The linked open data (LOD) paradigm has emerged as a promising approach to
structuring and sharing geospatial information. One of the major obstacles to
this vision lies in the difficulties found in the automatic integration between
heterogeneous vocabularies and ontologies that provides the semantic backbone
of the growing constellation of open geo-knowledge bases. In this article, we
show how to utilize WordNet as a semantic hub to increase the integration of
LOD. With this purpose in mind, we devise Voc2WordNet, an unsupervised mapping
technique between a given vocabulary and WordNet, combining intensional and
extensional aspects of the geographic terms. Voc2WordNet is evaluated against a
sample of human-generated alignments with the OpenStreetMap (OSM) Semantic
Network, a crowdsourced geospatial resource, and the GeoNames ontology, the
vocabulary of a large digital gazetteer. These empirical results indicate that
the approach can obtain high precision and recall.
Real-time Decolorization using Dominant Colors
Authors: Wei Hu, Wei Li, Fan Zhang, Qian Du
Date: 2014-04-10 00:00:00
Tasks: CPU

Decolorization is the process to convert a color image or video to its
grayscale version, and it has received great attention in recent years. An
ideal decolorization algorithm should preserve the original color contrast as
much as possible. Meanwhile, it should provide the final decolorized result as
fast as possible. However, most of the current methods are suffering from
either unsatisfied color information preservation or high computational cost,
limiting their application value. In this paper, a simple but effective
technique is proposed for real-time decolorization. Based on the typical
rgb2gray() color conversion model, which produces a grayscale image by linearly
combining R, G, and B channels, we propose a dominant color hypothesis and a
corresponding distance measurement metric to evaluate the quality of grayscale
conversion. The local optimum scheme provides several "good" candidates in a
confidence interval, from which the "best" result can be extracted.
Experimental results demonstrate that remarkable simplicity of the proposed
method facilitates the process of high resolution images and videos in
real-time using a common CPU.
Lexicon Infused Phrase Embeddings for Named Entity Resolution
Authors: Alexandre Passos, Vineet Kumar, Andrew McCallum
Date: 2014-04-22 00:00:00
Proceeding: WS 2014 6
Tasks: Entity Resolution, Form, Learning Word Embeddings, named-entity-recognition, Named Entity Recognition, Named Entity Recognition (NER), NER, Word Embeddings

Most state-of-the-art approaches for named-entity recognition (NER) use semi
supervised information in the form of word clusters and lexicons. Recently
neural network-based language models have been explored, as they as a byproduct
generate highly informative vector representations for words, known as word
embeddings. In this paper we present two contributions: a new form of learning
word embeddings that can leverage information from relevant lexicons to improve
the representations, and the first system to use neural word embeddings to
achieve state-of-the-art results on named-entity recognition in both CoNLL and
Ontonotes NER. Our system achieves an F1 score of 90.90 on the test set for
CoNLL 2003---significantly better than any previous system trained on public
data, and matching a system employing massive private industrial query-log
data.
Morphological Analysis of the Bishnupriya Manipuri Language using Finite State Transducers
Authors: Nayan Jyoti Kalita, Navanath Saharia, Smriti Kumar Sinha
Date: 2014-04-22 00:00:00
Tasks: Morphological Analysis

In this work we present a morphological analysis of Bishnupriya Manipuri
language, an Indo-Aryan language spoken in the north eastern India. As of now,
there is no computational work available for the language. Finite state
morphology is one of the successful approaches applied in a wide variety of
languages over the year. Therefore we adapted the finite state approach to
analyse morphology of the Bishnupriya Manipuri language.
Fast Approximate Matching of Cell-Phone Videos for Robust Background Subtraction
Authors: Raffay Hamid, Atish Das Sarma, Dennis Decoste, Neel Sundaresan
Date: 2014-04-22 00:00:00
Tasks: Object

We identify a novel instance of the background subtraction problem that
focuses on extracting near-field foreground objects captured using handheld
cameras. Given two user-generated videos of a scene, one with and the other
without the foreground object(s), our goal is to efficiently generate an output
video with only the foreground object(s) present in it. We cast this challenge
as a spatio-temporal frame matching problem, and propose an efficient solution
for it that exploits the temporal smoothness of the video sequences. We present
theoretical analyses for the error bounds of our approach, and validate our
findings using a detailed set of simulation experiments. Finally, we present
the results of our approach tested on multiple real videos captured using
handheld cameras, and compare them to several alternate foreground extraction
approaches.
The Frobenius anatomy of word meanings I: subject and object relative pronouns
Authors: Mehrnoosh Sadrzadeh, Stephen Clark, Bob Coecke
Date: 2014-04-21 00:00:00
Tasks: Anatomy

This paper develops a compositional vector-based semantics of subject and
object relative pronouns within a categorical framework. Frobenius algebras are
used to formalise the operations required to model the semantics of relative
pronouns, including passing information between the relative clause and the
modified noun phrase, as well as copying, combining, and discarding parts of
the relative clause. We develop two instantiations of the abstract semantics,
one based on a truth-theoretic approach and one based on corpus statistics.
Graph Kernels via Functional Embedding
Authors: Anshumali Shrivastava, Ping Li
Date: 2014-04-21 00:00:00
Tasks: General Classification, Graph Classification

We propose a representation of graph as a functional object derived from the
power iteration of the underlying adjacency matrix. The proposed functional
representation is a graph invariant, i.e., the functional remains unchanged
under any reordering of the vertices. This property eliminates the difficulty
of handling exponentially many isomorphic forms. Bhattacharyya kernel
constructed between these functionals significantly outperforms the
state-of-the-art graph kernels on 3 out of the 4 standard benchmark graph
classification datasets, demonstrating the superiority of our approach. The
proposed methodology is simple and runs in time linear in the number of edges,
which makes our kernel more efficient and scalable compared to many widely
adopted graph kernels with running time cubic in the number of vertices.
Constraint Reduction using Marginal Polytope Diagrams for MAP LP Relaxations
Authors: Zhen Zhang, Qinfeng Shi, Yanning Zhang, Chunhua Shen, Anton Van Den Hengel
Date: 2013-12-17 00:00:00

LP relaxation-based message passing algorithms provide an effective tool for
MAP inference over Probabilistic Graphical Models. However, different LP
relaxations often have different objective functions and variables of differing
dimensions, which presents a barrier to effective comparison and analysis. In
addition, the computational complexity of LP relaxation-based methods grows
quickly with the number of constraints. Reducing the number of constraints
without sacrificing the quality of the solutions is thus desirable.
  We propose a unified formulation under which existing MAP LP relaxations may
be compared and analysed. Furthermore, we propose a new tool called Marginal
Polytope Diagrams. Some properties of Marginal Polytope Diagrams are exploited
such as node redundancy and edge equivalence. We show that using Marginal
Polytope Diagrams allows the number of constraints to be reduced without
loosening the LP relaxations. Then, using Marginal Polytope Diagrams and
constraint reduction, we develop three novel message passing algorithms, and
demonstrate that two of these show a significant improvement in speed over
state-of-art algorithms while delivering a competitive, and sometimes higher,
quality of solution.
Influence of the learning method in the performance of feedforward neural networks when the activity of neurons is modified
Authors: M. Konomi, G. M. Sacha
Date: 2014-04-21 00:00:00

A method that allows us to give a different treatment to any neuron inside
feedforward neural networks is presented. The algorithm has been implemented
with two very different learning methods: a standard Back-propagation (BP)
procedure and an evolutionary algorithm. First, we have demonstrated that the
EA training method converges faster and gives more accurate results than BP.
Then we have made a full analysis of the effects of turning off different
combinations of neurons after the training phase. We demonstrate that EA is
much more robust than BP for all the cases under study. Even in the case when
two hidden neurons are lost, EA training is still able to give good average
results. This difference implies that we must be very careful when pruning or
redundancy effects are being studied since the network performance when losing
neurons strongly depends on the training method. Moreover, the influence of the
individual inputs will also depend on the training algorithm. Since EA keeps a
good classification performance when units are lost, this method could be a
good way to simulate biological learning systems since they must be robust
against deficient neuron performance. Although biological systems are much more
complex than the simulations shown in this article, we propose that a smart
training strategy such as the one shown here could be considered as a first
protection against the losing of a certain number of neurons.
A Computationally Efficient Limited Memory CMA-ES for Large Scale Optimization
Authors: Ilya Loshchilov
Date: 2014-04-21 00:00:00

We propose a computationally efficient limited memory Covariance Matrix
Adaptation Evolution Strategy for large scale optimization, which we call the
LM-CMA-ES. The LM-CMA-ES is a stochastic, derivative-free algorithm for
numerical optimization of non-linear, non-convex optimization problems in
continuous domain. Inspired by the limited memory BFGS method of Liu and
Nocedal (1989), the LM-CMA-ES samples candidate solutions according to a
covariance matrix reproduced from $m$ direction vectors selected during the
optimization process. The decomposition of the covariance matrix into Cholesky
factors allows to reduce the time and memory complexity of the sampling to
$O(mn)$, where $n$ is the number of decision variables. When $n$ is large
(e.g., $n$ > 1000), even relatively small values of $m$ (e.g., $m=20,30$) are
sufficient to efficiently solve fully non-separable problems and to reduce the
overall run-time.
Compressed Sensing for Energy-Efficient Wireless Telemonitoring: Challenges and Opportunities
Authors: Zhilin Zhang, Bhaskar D. Rao, Tzyy-Ping Jung
Date: 2013-11-15 00:00:00
Tasks: compressed sensing, EEG, Electroencephalogram (EEG)

As a lossy compression framework, compressed sensing has drawn much attention
in wireless telemonitoring of biosignals due to its ability to reduce energy
consumption and make possible the design of low-power devices. However, the
non-sparseness of biosignals presents a major challenge to compressed sensing.
This study proposes and evaluates a spatio-temporal sparse Bayesian learning
algorithm, which has the desired ability to recover such non-sparse biosignals.
It exploits both temporal correlation in each individual biosignal and
inter-channel correlation among biosignals from different channels. The
proposed algorithm was used for compressed sensing of multichannel
electroencephalographic (EEG) signals for estimating vehicle drivers'
drowsiness. Results showed that the drowsiness estimation was almost unaffected
even if raw EEG signals (containing various artifacts) were compressed by 90%.