pwc-archive/papers-with-abstracts huggingface dataset:
Measuring Atmospheric Scattering from Digital Images of Urban Scenery using Temporal Polarization-Based Vision
Authors: Tarek El-Gaaly, Joshua Gluckman
Date: 2014-07-14 00:00:00

Particulate Matter (PM) is a form of air pollution that visually degrades
urban scenery and is hazardous to human health and the environment. Current
monitoring devices are limited in measuring average PM over large areas.
Quantifying the visual effects of haze in digital images of urban scenery and
correlating these effects to PM levels is a vital step in more practically
monitoring our environment. Current image haze extraction algorithms remove
haze from the scene for the sole purpose of enhancing vision. We present two
algorithms which bridge the gap between image haze extraction and environmental
monitoring. We provide a means of measuring atmospheric scattering from images
of urban scenery by incorporating temporal knowledge. In doing so, we also
present a method of recovering an accurate depthmap of the scene and recovering
the scene without the visual effects of haze. We compare our algorithm to three
known haze removal methods. The algorithms are composed of an optimization over
a model of haze formation in images and an optimization using a constraint of
constant depth over a sequence of images taken over time. These algorithms not
only measure atmospheric scattering, but also recover a more accurate depthmap
and dehazed image. The measurements of atmospheric scattering this research
produces, can be directly correlated to PM levels and therefore pave the way to
monitoring the health of the environment by visual means. Accurate atmospheric
sensing from digital images is a challenging and under-researched problem. This
work provides an important step towards a more practical and accurate visual
means of measuring PM from digital images.
Modeling the Complex Dynamics and Changing Correlations of Epileptic Events
Authors: Drausin F. Wulsin, Emily B. Fox, Brian Litt
Date: 2014-02-27 00:00:00
Tasks: EEG, Electroencephalogram (EEG)

Patients with epilepsy can manifest short, sub-clinical epileptic "bursts" in
addition to full-blown clinical seizures. We believe the relationship between
these two classes of events---something not previously studied
quantitatively---could yield important insights into the nature and intrinsic
dynamics of seizures. A goal of our work is to parse these complex epileptic
events into distinct dynamic regimes. A challenge posed by the intracranial EEG
(iEEG) data we study is the fact that the number and placement of electrodes
can vary between patients. We develop a Bayesian nonparametric Markov switching
process that allows for (i) shared dynamic regimes between a variable number of
channels, (ii) asynchronous regime-switching, and (iii) an unknown dictionary
of dynamic regimes. We encode a sparse and changing set of dependencies between
the channels using a Markov-switching Gaussian graphical model for the
innovations process driving the channel dynamics and demonstrate the importance
of this model in parsing and out-of-sample predictions of iEEG data. We show
that our model produces intuitive state assignments that can help automate
clinical analysis of seizures and enable the comparison of sub-clinical bursts
and full clinical seizures.
A Generalized Online Mirror Descent with Applications to Classification and Regression
Authors: Francesco Orabona, Koby Crammer, Nicolò Cesa-Bianchi
Date: 2013-04-10 00:00:00
Tasks: General Classification, regression

Online learning algorithms are fast, memory-efficient, easy to implement, and
applicable to many prediction problems, including classification, regression,
and ranking. Several online algorithms were proposed in the past few decades,
some based on additive updates, like the Perceptron, and some on multiplicative
updates, like Winnow. A unifying perspective on the design and the analysis of
online algorithms is provided by online mirror descent, a general prediction
strategy from which most first-order algorithms can be obtained as special
cases. We generalize online mirror descent to time-varying regularizers with
generic updates. Unlike standard mirror descent, our more general formulation
also captures second order algorithms, algorithms for composite losses and
algorithms for adaptive filtering. Moreover, we recover, and sometimes improve,
known regret bounds as special cases of our analysis using specific
regularizers. Finally, we show the power of our approach by deriving a new
second order algorithm with a regret bound invariant with respect to arbitrary
rescalings of individual features.
A New Optimal Stepsize For Approximate Dynamic Programming
Authors: Ilya O. Ryzhov, Peter I. Frazier, Warren B. Powell
Date: 2014-07-10 00:00:00
Tasks: Management

Approximate dynamic programming (ADP) has proven itself in a wide range of
applications spanning large-scale transportation problems, health care, revenue
management, and energy systems. The design of effective ADP algorithms has many
dimensions, but one crucial factor is the stepsize rule used to update a value
function approximation. Many operations research applications are
computationally intensive, and it is important to obtain good results quickly.
Furthermore, the most popular stepsize formulas use tunable parameters and can
produce very poor results if tuned improperly. We derive a new stepsize rule
that optimizes the prediction error in order to improve the short-term
performance of an ADP algorithm. With only one, relatively insensitive tunable
parameter, the new rule adapts to the level of noise in the problem and
produces faster convergence in numerical experiments.
Brain-like associative learning using a nanoscale non-volatile phase change synaptic device array
Authors: Sukru Burc Eryilmaz, Duygu Kuzum, Rakesh Jeyasingh, Sang-Bum Kim, Matthew BrightSky, Chung Lam, H. -S. Philip Wong
Date: 2014-06-19 00:00:00

Recent advances in neuroscience together with nanoscale electronic device
technology have resulted in huge interests in realizing brain-like computing
hardwares using emerging nanoscale memory devices as synaptic elements.
Although there has been experimental work that demonstrated the operation of
nanoscale synaptic element at the single device level, network level studies
have been limited to simulations. In this work, we demonstrate, using
experiments, array level associative learning using phase change synaptic
devices connected in a grid like configuration similar to the organization of
the biological brain. Implementing Hebbian learning with phase change memory
cells, the synaptic grid was able to store presented patterns and recall
missing patterns in an associative brain-like fashion. We found that the system
is robust to device variations, and large variations in cell resistance states
can be accommodated by increasing the number of training epochs. We illustrated
the tradeoff between variation tolerance of the network and the overall energy
consumption, and found that energy consumption is decreased significantly for
lower variation tolerance.
Monte Carlo Simulation for Lasso-Type Problems by Estimator Augmentation
Authors: Qing Zhou
Date: 2014-01-17 00:00:00
Tasks: regression, Variable Selection, Vocal Bursts Type Prediction

Regularized linear regression under the $\ell_1$ penalty, such as the Lasso,
has been shown to be effective in variable selection and sparse modeling. The
sampling distribution of an $\ell_1$-penalized estimator $\hat{\beta}$ is hard
to determine as the estimator is defined by an optimization problem that in
general can only be solved numerically and many of its components may be
exactly zero. Let $S$ be the subgradient of the $\ell_1$ norm of the
coefficient vector $\beta$ evaluated at $\hat{\beta}$. We find that the joint
sampling distribution of $\hat{\beta}$ and $S$, together called an augmented
estimator, is much more tractable and has a closed-form density under a normal
error distribution in both low-dimensional ($p\leq n$) and high-dimensional
($p>n$) settings. Given $\beta$ and the error variance $\sigma^2$, one may
employ standard Monte Carlo methods, such as Markov chain Monte Carlo and
importance sampling, to draw samples from the distribution of the augmented
estimator and calculate expectations with respect to the sampling distribution
of $\hat{\beta}$. We develop a few concrete Monte Carlo algorithms and
demonstrate with numerical examples that our approach may offer huge advantages
and great flexibility in studying sampling distributions in $\ell_1$-penalized
linear regression. We also establish nonasymptotic bounds on the difference
between the true sampling distribution of $\hat{\beta}$ and its estimator
obtained by plugging in estimated parameters, which justifies the validity of
Monte Carlo simulation from an estimated sampling distribution even when $p\gg
n\to \infty$.
A New Rational Algorithm for View Updating in Relational Databases
Authors: Radhakrishnan Delhibabu, Andreas Behrend
Date: 2014-07-13 00:00:00
Tasks: Negation

The dynamics of belief and knowledge is one of the major components of any
autonomous system that should be able to incorporate new pieces of information.
In order to apply the rationality result of belief dynamics theory to various
practical problems, it should be generalized in two respects: first it should
allow a certain part of belief to be declared as immutable; and second, the
belief state need not be deductively closed. Such a generalization of belief
dynamics, referred to as base dynamics, is presented in this paper, along with
the concept of a generalized revision algorithm for knowledge bases (Horn or
Horn logic with stratified negation). We show that knowledge base dynamics has
an interesting connection with kernel change via hitting set and abduction. In
this paper, we show how techniques from disjunctive logic programming can be
used for efficient (deductive) database updates. The key idea is to transform
the given database together with the update request into a disjunctive
(datalog) logic program and apply disjunctive techniques (such as minimal model
reasoning) to solve the original update problem. The approach extends and
integrates standard techniques for efficient query answering and integrity
checking. The generation of a hitting set is carried out through a hyper
tableaux calculus and magic set that is focused on the goal of minimality.
A Superposition Calculus for Abductive Reasoning
Authors: Mnacho Echenim, Nicolas Peltier
Date: 2014-06-02 00:00:00

We present a modification of the superposition calculus that is meant to
generate consequences of sets of first-order axioms. This approach is proven to
be sound and deductive-complete in the presence of redundancy elimination
rules, provided the considered consequences are built on a given finite set of
ground terms, represented by constant symbols. In contrast to other approaches,
most existing results about the termination of the superposition calculus can
be carried over to our procedure. This ensures in particular that the calculus
is terminating for many theories of interest to the SMT community.
Regression Trees for Longitudinal Data
Authors: Madan Gopal Kundu, Jaroslaw Harezlak
Date: 2013-09-30 00:00:00
Tasks: regression

While studying response trajectory, often the population of interest may be
diverse enough to exist distinct subgroups within it and the longitudinal
change in response may not be uniform in these subgroups. That is, the
timeslope and/or influence of covariates in longitudinal profile may vary among
these different subgroups. For example, Raudenbush (2001) used depression as an
example to argue that it is incorrect to assume that all the people in a given
population would be experiencing either increasing or decreasing levels of
depression. In such cases, traditional linear mixed effects model (assuming
common parametric form for covariates and time) is not directly applicable for
the entire population as a group-averaged trajectory can mask important
subgroup differences. Our aim is to identify and characterize longitudinally
homogeneous subgroups based on the combination of baseline covariates in the
most parsimonious way. This goal can be achieved via constructing regression
tree for longitudinal data using baseline covariates as partitioning variables.
We have proposed LongCART algorithm to construct regression tree for the
longitudinal data. In each node, the proposed LongCART algorithm determines the
need for further splitting (i.e. whether parameter(s) of longitudinal profile
is influenced by any baseline attributes) via parameter instability tests and
thus the decision of further splitting is type-I error controlled. We have
obtained the asymptotic results for the proposed instability test and examined
finite sample behavior of the whole algorithm through simulation studies.
Finally, we have applied the LongCART algorithm to study the longitudinal
changes in choline level among HIV patients.
Learning Two-input Linear and Nonlinear Analog Functions with a Simple Chemical System
Authors: Peter Banda, Christof Teuscher
Date: 2014-04-02 00:00:00

The current biochemical information processing systems behave in a
predetermined manner because all features are defined during the design phase.
To make such unconventional computing systems reusable and programmable for
biomedical applications, adaptation, learning, and self-modification based on
external stimuli would be highly desirable. However, so far, it has been too
challenging to implement these in wet chemistries. In this paper we extend the
chemical perceptron, a model previously proposed by the authors, to function as
an analog instead of a binary system. The new analog asymmetric signal
perceptron learns through feedback and supports Michaelis-Menten kinetics. The
results show that our perceptron is able to learn linear and nonlinear
(quadratic) functions of two inputs. To the best of our knowledge, it is the
first simulated chemical system capable of doing so. The small number of
species and reactions and their simplicity allows for a mapping to an actual
wet implementation using DNA-strand displacement or deoxyribozymes. Our results
are an important step toward actual biochemical systems that can learn and
adapt.
Robust Hierarchical Clustering
Authors: Maria-Florina Balcan, YIngyu Liang, Pramod Gupta
Date: 2014-01-01 00:00:00
Tasks: Clustering

One of the most widely used techniques for data clustering is agglomerative
clustering. Such algorithms have been long used across many different fields
ranging from computational biology to social sciences to computer vision in
part because their output is easy to interpret. Unfortunately, it is well
known, however, that many of the classic agglomerative clustering algorithms
are not robust to noise. In this paper we propose and analyze a new robust
algorithm for bottom-up agglomerative clustering. We show that our algorithm
can be used to cluster accurately in cases where the data satisfies a number of
natural properties and where the traditional agglomerative algorithms fail. We
also show how to adapt our algorithm to the inductive setting where our given
data is only a small random sample of the entire data set. Experimental
evaluations on synthetic and real world data sets show that our algorithm
achieves better performance than other hierarchical algorithms in the presence
of noise.
Protecting Privacy through Distributed Computation in Multi-agent Decision Making
Authors: Thomas Leaute, Boi Faltings
Date: 2014-02-04 00:00:00
Tasks: Decision Making, Scheduling

As large-scale theft of data from corporate servers is becoming increasingly
common, it becomes interesting to examine alternatives to the paradigm of
centralizing sensitive data into large databases. Instead, one could use
cryptography and distributed computation so that sensitive data can be supplied
and processed in encrypted form, and only the final result is made known. In
this paper, we examine how such a paradigm can be used to implement constraint
satisfaction, a technique that can solve a broad class of AI problems such as
resource allocation, planning, scheduling, and diagnosis. Most previous work on
privacy in constraint satisfaction only attempted to protect specific types of
information, in particular the feasibility of particular combinations of
decisions. We formalize and extend these restricted notions of privacy by
introducing four types of private information, including the feasibility of
decisions and the final decisions made, but also the identities of the
participants and the topology of the problem. We present distributed algorithms
that allow computing solutions to constraint satisfaction problems while
maintaining these four types of privacy. We formally prove the privacy
properties of these algorithms, and show experiments that compare their
respective performance on benchmark problems.
Analysis of Amoeba Active Contours
Authors: Martin Welk
Date: 2013-09-30 00:00:00

Subject of this paper is the theoretical analysis of structure-adaptive
median filter algorithms that approximate curvature-based PDEs for image
filtering and segmentation. These so-called morphological amoeba filters are
based on a concept introduced by Lerallut et al. They achieve similar results
as the well-known geodesic active contour and self-snakes PDEs. In the present
work, the PDE approximated by amoeba active contours is derived for a general
geometric situation and general amoeba metric. This PDE is structurally similar
but not identical to the geodesic active contour equation. It reproduces the
previous PDE approximation results for amoeba median filters as special cases.
Furthermore, modifications of the basic amoeba active contour algorithm are
analysed that are related to the morphological force terms frequently used with
geodesic active contours. Experiments demonstrate the basic behaviour of amoeba
active contours and its similarity to geodesic active contours.
Counting Markov Blanket Structures
Authors: Shyam Visweswaran, Gregory F. Cooper
Date: 2014-07-09 00:00:00
Tasks: feature selection

Learning Markov blanket (MB) structures has proven useful in performing
feature selection, learning Bayesian networks (BNs), and discovering causal
relationships. We present a formula for efficiently determining the number of
MB structures given a target variable and a set of other variables. As
expected, the number of MB structures grows exponentially. However, we show
quantitatively that there are many fewer MB structures that contain the target
variable than there are BN structures that contain it. In particular, the ratio
of BN structures to MB structures appears to increase exponentially in the
number of variables.
Extreme State Aggregation Beyond MDPs
Authors: Marcus Hutter
Date: 2014-07-12 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We consider a Reinforcement Learning setup where an agent interacts with an
environment in observation-reward-action cycles without any (esp.\ MDP)
assumptions on the environment. State aggregation and more generally feature
reinforcement learning is concerned with mapping histories/raw-states to
reduced/aggregated states. The idea behind both is that the resulting reduced
process (approximately) forms a small stationary finite-state MDP, which can
then be efficiently solved or learnt. We considerably generalize existing
aggregation results by showing that even if the reduced process is not an MDP,
the (q-)value functions and (optimal) policies of an associated MDP with same
state-space size solve the original problem, as long as the solution can
approximately be represented as a function of the reduced states. This implies
an upper bound on the required state space size that holds uniformly for all RL
problems. It may also explain why RL algorithms designed for MDPs sometimes
perform well beyond MDPs.
Offline to Online Conversion
Authors: Marcus Hutter
Date: 2014-07-12 00:00:00

We consider the problem of converting offline estimators into an online
predictor or estimator with small extra regret. Formally this is the problem of
merging a collection of probability measures over strings of length 1,2,3,...
into a single probability measure over infinite sequences. We describe various
approaches and their pros and cons on various examples. As a side-result we
give an elementary non-heuristic purely combinatoric derivation of Turing's
famous estimator. Our main technical contribution is to determine the
computational complexity of online estimators with good guarantees in general.
Beyond Disagreement-based Agnostic Active Learning
Authors: Chicheng Zhang, Kamalika Chaudhuri
Date: 2014-07-10 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Active Learning, General Classification

We study agnostic active learning, where the goal is to learn a classifier in
a pre-specified hypothesis class interactively with as few label queries as
possible, while making no assumptions on the true function generating the
labels. The main algorithms for this problem are {\em{disagreement-based active
learning}}, which has a high label requirement, and {\em{margin-based active
learning}}, which only applies to fairly restricted settings. A major challenge
is to find an algorithm which achieves better label complexity, is consistent
in an agnostic setting, and applies to general classification problems.
  In this paper, we provide such an algorithm. Our solution is based on two
novel contributions -- a reduction from consistent active learning to
confidence-rated prediction with guaranteed error, and a novel confidence-rated
predictor.
Computational Aspects of Multi-Winner Approval Voting
Authors: Haris Aziz, Serge Gaspers, Joachim Gudmundsson, Simon Mackenzie, Nicholas Mattei, Toby Walsh
Date: 2014-07-11 00:00:00

We study computational aspects of three prominent voting rules that use
approval ballots to elect multiple winners. These rules are satisfaction
approval voting, proportional approval voting, and reweighted approval voting.
We first show that computing the winner for proportional approval voting is
NP-hard, closing a long standing open problem. As none of the rules are
strategyproof, even for dichotomous preferences, we study various strategic
aspects of the rules. In particular, we examine the computational complexity of
computing a best response for both a single agent and a group of agents. In
many settings, we show that it is NP-hard for an agent or agents to compute how
best to vote given a fixed set of approval ballots from the other agents.
Density Adaptive Parallel Clustering
Authors: Marcello La Rocca
Date: 2014-07-11 00:00:00
Tasks: Clustering

In this paper we are going to introduce a new nearest neighbours based
approach to clustering, and compare it with previous solutions; the resulting
algorithm, which takes inspiration from both DBscan and minimum spanning tree
approaches, is deterministic but proves simpler, faster and doesnt require to
set in advance a value for k, the number of clusters.