pwc-archive/papers-with-abstracts huggingface dataset:
Decentralized Data Fusion and Active Sensing with Mobile Sensors for Modeling and Predicting Spatiotemporal Traffic Phenomena
Authors: Jie Chen, Kian Hsiang Low, Colin Keng-Yan Tan, Ali Oran, Patrick Jaillet, John Dolan, Gaurav Sukhatme
Date: 2014-08-09 00:00:00

The problem of modeling and predicting spatiotemporal traffic phenomena over
an urban road network is important to many traffic applications such as
detecting and forecasting congestion hotspots. This paper presents a
decentralized data fusion and active sensing (D2FAS) algorithm for mobile
sensors to actively explore the road network to gather and assimilate the most
informative data for predicting the traffic phenomenon. We analyze the time and
communication complexity of D2FAS and demonstrate that it can scale well with a
large number of observations and sensors. We provide a theoretical guarantee on
its predictive performance to be equivalent to that of a sophisticated
centralized sparse approximation for the Gaussian process (GP) model: The
computation of such a sparse approximate GP model can thus be parallelized and
distributed among the mobile sensors (in a Google-like MapReduce paradigm),
thereby achieving efficient and scalable prediction. We also theoretically
guarantee its active sensing performance that improves under various practical
environmental conditions. Empirical evaluation on real-world urban road network
data shows that our D2FAS algorithm is significantly more time-efficient and
scalable than state-oftheart centralized algorithms while achieving comparable
predictive performance.
Video In Sentences Out
Authors: Andrei Barbu, Alexander Bridge, Zachary Burchill, Dan Coroian, Sven Dickinson, Sanja Fidler, Aaron Michaux, Sam Mussman, Siddharth Narayanaswamy, Dhaval Salvi, Lara Schmidt, Jiangnan Shangguan, Jeffrey Mark Siskind, Jarrell Waggoner, Song Wang, Jinlian Wei, Yifan Yin, Zhiqi Zhang
Date: 2014-08-09 00:00:00

We present a system that produces sentential descriptions of video: who did
what to whom, and where and how they did it. Action class is rendered as a
verb, participant objects as noun phrases, properties of those objects as
adjectival modifiers in those noun phrases, spatial relations between those
participants as prepositional phrases, and characteristics of the event as
prepositional-phrase adjuncts and adverbial modifiers. Extracting the
information needed to render these linguistic entities requires an approach to
event recognition that recovers object tracks, the trackto-role assignments,
and changing body posture.
Efficient Clustering with Limited Distance Information
Authors: Konstantin Voevodski, Maria-Florina Balcan, Heiko Roglin, Shang-Hua Teng, Yu Xia
Date: 2014-08-09 00:00:00
Tasks: Clustering

Given a point set S and an unknown metric d on S, we study the problem of
efficiently partitioning S into k clusters while querying few distances between
the points. In our model we assume that we have access to one versus all
queries that given a point s 2 S return the distances between s and all other
points. We show that given a natural assumption about the structure of the
instance, we can efficiently find an accurate clustering using only O(k)
distance queries. We use our algorithm to cluster proteins by sequence
similarity. This setting nicely fits our model because we can use a fast
sequence database search program to query a sequence against an entire dataset.
We conduct an empirical study that shows that even though we query a small
fraction of the distances between the points, we produce clusterings that are
close to a desired clustering given by manual classification.
Matrix Coherence and the Nystrom Method
Authors: Ameet Talwalkar, Afshin Rostamizadeh
Date: 2014-08-09 00:00:00
Tasks: compressed sensing, Matrix Completion

The Nystrom method is an efficient technique used to speed up large-scale
learning applications by generating low-rank approximations. Crucial to the
performance of this technique is the assumption that a matrix can be well
approximated by working exclusively with a subset of its columns. In this work
we relate this assumption to the concept of matrix coherence, connecting
coherence to the performance of the Nystrom method. Making use of related work
in the compressed sensing and the matrix completion literature, we derive novel
coherence-based bounds for the Nystrom method in the low-rank setting. We then
present empirical results that corroborate these theoretical bounds. Finally,
we present more general empirical results for the full-rank setting that
convincingly demonstrate the ability of matrix coherence to measure the degree
to which information can be extracted from a subset of columns.
Gaussian Process Structural Equation Models with Latent Variables
Authors: Ricardo Silva, Robert B. Gramacy
Date: 2014-08-09 00:00:00

In a variety of disciplines such as social sciences, psychology, medicine and
economics, the recorded data are considered to be noisy measurements of latent
variables connected by some causal structure. This corresponds to a family of
graphical models known as the structural equation model with latent variables.
While linear non-Gaussian variants have been well-studied, inference in
nonparametric structural equation models is still underdeveloped. We introduce
a sparse Gaussian process parameterization that defines a non-linear structure
connecting latent variables, unlike common formulations of Gaussian process
latent variable models. The sparse parameterization is given a full Bayesian
treatment without compromising Markov chain Monte Carlo efficiency. We compare
the stability of the sampling procedure and the predictive ability of the model
against the current practice.
GraphLab: A New Framework For Parallel Machine Learning
Authors: Yucheng Low, Joseph E. Gonzalez, Aapo Kyrola, Danny Bickson, Carlos E. Guestrin, Joseph Hellerstein
Date: 2014-08-09 00:00:00
Tasks: BIG-bench Machine Learning, compressed sensing

Designing and implementing efficient, provably correct parallel machine
learning (ML) algorithms is challenging. Existing high-level parallel
abstractions like MapReduce are insufficiently expressive while low-level tools
like MPI and Pthreads leave ML experts repeatedly solving the same design
challenges. By targeting common patterns in ML, we developed GraphLab, which
improves upon abstractions like MapReduce by compactly expressing asynchronous
iterative algorithms with sparse computational dependencies while ensuring data
consistency and achieving a high degree of parallel performance. We demonstrate
the expressiveness of the GraphLab framework by designing and implementing
parallel versions of belief propagation, Gibbs sampling, Co-EM, Lasso and
Compressed Sensing. We show that using GraphLab we can achieve excellent
parallel performance on large scale real-world problems.
Prediction with Advice of Unknown Number of Experts
Authors: Alexey Chernov, Vladimir Vovk
Date: 2014-08-09 00:00:00
Tasks: Prediction

In the framework of prediction with expert advice, we consider a recently
introduced kind of regret bounds: the bounds that depend on the effective
instead of nominal number of experts. In contrast to the Normal- Hedge bound,
which mainly depends on the effective number of experts but also weakly depends
on the nominal one, we obtain a bound that does not contain the nominal number
of experts at all. We use the defensive forecasting method and introduce an
application of defensive forecasting to multivalued supermartingales.
Incorporating Side Information in Probabilistic Matrix Factorization with Gaussian Processes
Authors: Ryan Prescott Adams, George E. Dahl, Iain Murray
Date: 2014-08-09 00:00:00
Tasks: Collaborative Filtering, Gaussian Processes

Probabilistic matrix factorization (PMF) is a powerful method for modeling
data associ- ated with pairwise relationships, Finding use in collaborative
Filtering, computational bi- ology, and document analysis, among other areas.
In many domains, there are additional covariates that can assist in prediction.
For example, when modeling movie ratings, we might know when the rating
occurred, where the user lives, or what actors appear in the movie. It is
difficult, however, to incorporate this side information into the PMF model. We
propose a framework for incorporating side information by coupling together
multi- ple PMF problems via Gaussian process priors. We replace scalar latent
features with func- tions that vary over the covariate space. The GP priors on
these functions require them to vary smoothly and share information. We apply
this new method to predict the scores of professional basketball games, where
side information about the venue and date of the game are relevant for the
outcome.
A direct method for estimating a causal ordering in a linear non-Gaussian acyclic model
Authors: Shohei Shimizu, Aapo Hyvarinen, Yoshinobu Kawahara
Date: 2014-08-09 00:00:00

Structural equation models and Bayesian networks have been widely used to
analyze causal relations between continuous variables. In such frameworks,
linear acyclic models are typically used to model the datagenerating process of
variables. Recently, it was shown that use of non-Gaussianity identifies a
causal ordering of variables in a linear acyclic model without using any prior
knowledge on the network structure, which is not the case with conventional
methods. However, existing estimation methods are based on iterative search
algorithms and may not converge to a correct solution in a finite number of
steps. In this paper, we propose a new direct method to estimate a causal
ordering based on non-Gaussianity. In contrast to the previous methods, our
algorithm requires no algorithmic parameters and is guaranteed to converge to
the right solution within a small fixed number of steps if the data strictly
follows the model.
Quantum Annealing for Variational Bayes Inference
Authors: Issei Sato, Kenichi Kurihara, Shu Tanaka, Hiroshi Nakagawa, Seiji Miyashita
Date: 2014-08-09 00:00:00

This paper presents studies on a deterministic annealing algorithm based on
quantum annealing for variational Bayes (QAVB) inference, which can be seen as
an extension of the simulated annealing for variational Bayes (SAVB) inference.
QAVB is as easy as SAVB to implement. Experiments revealed QAVB finds a better
local optimum than SAVB in terms of the variational free energy in latent
Dirichlet allocation (LDA).
Quantum Annealing for Clustering
Authors: Kenichi Kurihara, Shu Tanaka, Seiji Miyashita
Date: 2014-08-09 00:00:00
Tasks: Clustering

This paper studies quantum annealing (QA) for clustering, which can be seen
as an extension of simulated annealing (SA). We derive a QA algorithm for
clustering and propose an annealing schedule, which is crucial in practice.
Experiments show the proposed QA algorithm finds better clustering assignments
than SA. Furthermore, QA is as easy as SA to implement.
Approximate inference on planar graphs using Loop Calculus and Belief Propagation
Authors: Vicenc Gomez, Hilbert Kappen, Michael Chertkov
Date: 2014-08-09 00:00:00

We introduce novel results for approximate inference on planar graphical
models using the loop calculus framework. The loop calculus (Chertkov and
Chernyak, 2006b) allows to express the exact partition function Z of a
graphical model as a finite sum of terms that can be evaluated once the belief
propagation (BP) solution is known. In general, full summation over all
correction terms is intractable. We develop an algorithm for the approach
presented in Chertkov et al. (2008) which represents an efficient truncation
scheme on planar graphs and a new representation of the series in terms of
Pfaffians of matrices. We analyze in detail both the loop series and the
Pfaffian series for models with binary variables and pairwise interactions, and
show that the first term of the Pfaffian series can provide very accurate
approximations. The algorithm outperforms previous truncation schemes of the
loop series and is competitive with other state-of-the-art methods for
approximate inference.
Robust Graphical Modeling with t-Distributions
Authors: Michael A. Finegold, Mathias Drton
Date: 2014-08-09 00:00:00
Tasks: Model Selection

Graphical Gaussian models have proven to be useful tools for exploring
network structures based on multivariate data. Applications to studies of gene
expression have generated substantial interest in these models, and resulting
recent progress includes the development of fitting methodology involving
penalization of the likelihood function. In this paper we advocate the use of
the multivariate t and related distributions for more robust inference of
graphs. In particular, we demonstrate that penalized likelihood inference
combined with an application of the EM algorithm provides a simple and
computationally efficient approach to model selection in the t-distribution
case.
Bayesian Multitask Learning with Latent Hierarchies
Authors: Hal Daume III
Date: 2014-08-09 00:00:00
Tasks: Domain Adaptation

We learn multiple hypotheses for related tasks under a latent hierarchical
relationship between tasks. We exploit the intuition that for domain
adaptation, we wish to share classifier structure, but for multitask learning,
we wish to share covariance structure. Our hierarchical model is seen to
subsume several previously proposed multitask learning models and performs well
on three distinct real-world data sets.
Conditional Probability Tree Estimation Analysis and Algorithms
Authors: Alina Beygelzimer, John Langford, Yuri Lifshits, Gregory Sorkin, Alexander L. Strehl
Date: 2014-08-09 00:00:00
Tasks: regression

We consider the problem of estimating the conditional probability of a label
in time O(log n), where n is the number of possible labels. We analyze a
natural reduction of this problem to a set of binary regression problems
organized in a tree structure, proving a regret bound that scales with the
depth of the tree. Motivated by this analysis, we propose the first online
algorithm which provably constructs a logarithmic depth tree on the set of
labels to solve this problem. We test the algorithm empirically, showing that
it works succesfully on a dataset with roughly 106 labels.
On the Conditional Independence Implication Problem: A Lattice-Theoretic Approach
Authors: Mathias Niepert, Dirk Van Gucht, Marc Gyssens
Date: 2014-08-09 00:00:00

A lattice-theoretic framework is introduced that permits the study of the
conditional independence (CI) implication problem relative to the class of
discrete probability measures. Semi-lattices are associated with CI statements
and a finite, sound and complete inference system relative to semi-lattice
inclusions is presented. This system is shown to be (1) sound and complete for
saturated CI statements, (2) complete for general CI statements, and (3) sound
and complete for stable CI statements. These results yield a criterion that can
be used to falsify instances of the implication problem and several heuristics
are derived that approximate this "lattice-exclusion" criterion in polynomial
time. Finally, we provide experimental results that relate our work to results
obtained from other existing inference algorithms.
Sensitivity analysis for finite Markov chains in discrete time
Authors: Gert de Cooman, Filip Hermans, Erik Quaeghebeur
Date: 2014-08-09 00:00:00
Tasks: Sensitivity

When the initial and transition probabilities of a finite Markov chain in
discrete time are not well known, we should perform a sensitivity analysis.
This is done by considering as basic uncertainty models the so-called credal
sets that these probabilities are known or believed to belong to, and by
allowing the probabilities to vary over such sets. This leads to the definition
of an imprecise Markov chain. We show that the time evolution of such a system
can be studied very efficiently using so-called lower and upper expectations.
We also study how the inferred credal set about the state at time n evolves as
n->infinity: under quite unrestrictive conditions, it converges to a uniquely
invariant credal set, regardless of the credal set given for the initial state.
This leads to a non-trivial generalisation of the classical Perron-Frobenius
Theorem to imprecise Markov chains.
Bandit Algorithms for Tree Search
Authors: Pierre-Arnuad Coquelin, Remi Munos
Date: 2014-08-09 00:00:00
Tasks: Efficient Exploration, Game of Go, global-optimization

Bandit based methods for tree search have recently gained popularity when
applied to huge trees, e.g. in the game of go [6]. Their efficient exploration
of the tree enables to re- turn rapidly a good value, and improve preci- sion
if more time is provided. The UCT algo- rithm [8], a tree search method based
on Up- per Confidence Bounds (UCB) [2], is believed to adapt locally to the
effective smoothness of the tree. However, we show that UCT is
"over-optimistic" in some sense, leading to a worst-case regret that may be
very poor. We propose alternative bandit algorithms for tree search. First, a
modification of UCT us- ing a confidence sequence that scales expo- nentially
in the horizon depth is analyzed. We then consider Flat-UCB performed on the
leaves and provide a finite regret bound with high probability. Then, we
introduce and analyze a Bandit Algorithm for Smooth Trees (BAST) which takes
into account ac- tual smoothness of the rewards for perform- ing efficient
"cuts" of sub-optimal branches with high confidence. Finally, we present an
incremental tree expansion which applies when the full tree is too big
(possibly in- finite) to be entirely represented and show that with high
probability, only the optimal branches are indefinitely developed. We illus-
trate these methods on a global optimization problem of a continuous function,
given noisy values.
A Bayesian Probability Calculus for Density Matrices
Authors: Manfred K. Warmuth, Dima Kuzmin
Date: 2014-08-09 00:00:00

One of the main concepts in quantum physics is a density matrix, which is a
symmetric positive definite matrix of trace one. Finite probability
distributions are a special case where the density matrix is restricted to be
diagonal. Density matrices are mixtures of dyads, where a dyad has the form uu'
for any any unit column vector u. These unit vectors are the elementary events
of the generalized probability space. Perhaps the simplest case to see that
something unusual is going on is the case of uniform density matrix, i.e. 1/n
times identity. This matrix assigns probability 1/n to every unit vector, but
of course there are infinitely many of them. The new normalization rule thus
says that sum of probabilities over any orthonormal basis of directions is one.
We develop a probability calculus based on these more general distributions
that includes definitions of joints, conditionals and formulas that relate
these, i.e. analogs of the theorem of total probability, various Bayes rules
for the calculation of posterior density matrices, etc. The resulting calculus
parallels the familiar 'classical' probability calculus and always retains the
latter as a special case when all matrices are diagonal.
  Whereas the classical Bayesian methods maintain uncertainty about which model
is 'best', the generalization maintains uncertainty about which unit direction
has the largest variance. Surprisingly the bounds also generalize: as in the
classical setting we bound the negative log likelihood of the data by the
negative log likelihood of the MAP estimator.
A Heuristic Search Algorithm for Solving First-Order MDPs
Authors: Eldar Karabaev, Olga Skvortsova
Date: 2014-08-09 00:00:00
Tasks: Heuristic Search

We present a heuristic search algorithm for solving first-order MDPs
(FOMDPs). Our approach combines first-order state abstraction that avoids
evaluating states individually, and heuristic search that avoids evaluating all
states. Firstly, we apply state abstraction directly on the FOMDP avoiding
propositionalization. Such kind of abstraction is referred to as firstorder
state abstraction. Secondly, guided by an admissible heuristic, the search is
restricted only to those states that are reachable from the initial state. We
demonstrate the usefullness of the above techniques for solving FOMDPs on a
system, referred to as FCPlanner, that entered the probabilistic track of the
International Planning Competition (IPC'2004).
Blind Construction of Optimal Nonlinear Recursive Predictors for Discrete Sequences
Authors: Cosma Shalizi, Kristina Lisa Klinkner
Date: 2014-08-09 00:00:00

We present a new method for nonlinear prediction of discrete random sequences
under minimal structural assumptions. We give a mathematical construction for
optimal predictors of such processes, in the form of hidden Markov models. We
then describe an algorithm, CSSR (Causal-State Splitting Reconstruction), which
approximates the ideal predictor from data. We discuss the reliability of CSSR,
its data requirements, and its performance in simulations. Finally, we compare
our approach to existing methods using variablelength Markov models and
cross-validated hidden Markov models, and show theoretically and experimentally
that our method delivers results superior to the former and at least comparable
to the latter.
Automatic Removal of Marginal Annotations in Printed Text Document
Authors: Abdessamad Elboushaki, Rachida Hannane, P. Nagabhushan, Mohammed Javed
Date: 2014-08-09 00:00:00
Tasks: Boundary Detection

Recovering the original printed texts from a document with added handwritten
annotations in the marginal area is one of the challenging problems, especially
when the original document is not available. Therefore, this paper aims at
salvaging automatically the original document from the annotated document by
detecting and removing any handwritten annotations that appear in the marginal
area of the document without any loss of information. Here a two stage
algorithm is proposed, where in the first stage due to approximate marginal
boundary detection with horizontal and vertical projection profiles, all of the
marginal annotations along with some part of the original printed text that may
appear very close to the marginal boundary are removed. Therefore as a second
stage, using the connected components, a strategy is applied to bring back the
printed text components cropped during the first stage. The proposed method is
validated using a dataset of 50 documents having complex handwritten
annotations, which gives an overall accuracy of 89.01% in removing the marginal
annotations and 97.74% in case of retrieving the original printed text
document.
An Evasion and Counter-Evasion Study in Malicious Websites Detection
Authors: Li Xu, Zhenxin Zhan, Shouhuai Xu, Keyin Ye
Date: 2014-08-08 00:00:00

Malicious websites are a major cyber attack vector, and effective detection
of them is an important cyber defense task. The main defense paradigm in this
regard is that the defender uses some kind of machine learning algorithms to
train a detection model, which is then used to classify websites in question.
Unlike other settings, the following issue is inherent to the problem of
malicious websites detection: the attacker essentially has access to the same
data that the defender uses to train its detection models. This 'symmetry' can
be exploited by the attacker, at least in principle, to evade the defender's
detection models. In this paper, we present a framework for characterizing the
evasion and counter-evasion interactions between the attacker and the defender,
where the attacker attempts to evade the defender's detection models by taking
advantage of this symmetry. Within this framework, we show that an adaptive
attacker can make malicious websites evade powerful detection models, but
proactive training can be an effective counter-evasion defense mechanism. The
framework is geared toward the popular detection model of decision tree, but
can be adapted to accommodate other classifiers.