pwc-archive/papers-with-abstracts huggingface dataset:
Characterizing A Database of Sequential Behaviors with Latent Dirichlet Hidden Markov Models
Authors: Yin Song, Longbing Cao, Xuhui Fan, Wei Cao, Jian Zhang
Date: 2013-05-24 00:00:00
Tasks: General Classification

This paper proposes a generative model, the latent Dirichlet hidden Markov
models (LDHMM), for characterizing a database of sequential behaviors
(sequences). LDHMMs posit that each sequence is generated by an underlying
Markov chain process, which are controlled by the corresponding parameters
(i.e., the initial state vector, transition matrix and the emission matrix).
These sequence-level latent parameters for each sequence are modeled as latent
Dirichlet random variables and parameterized by a set of deterministic
database-level hyper-parameters. Through this way, we expect to model the
sequence in two levels: the database level by deterministic hyper-parameters
and the sequence-level by latent parameters. To learn the deterministic
hyper-parameters and approximate posteriors of parameters in LDHMMs, we propose
an iterative algorithm under the variational EM framework, which consists of E
and M steps. We examine two different schemes, the fully-factorized and
partially-factorized forms, for the framework, based on different assumptions.
We present empirical results of behavior modeling and sequence classification
on three real-world data sets, and compare them to other related models. The
experimental results prove that the proposed LDHMMs produce better
generalization performance in terms of log-likelihood and deliver competitive
results on the sequence classification problem.
Edge Detection in Radar Images Using Weibull Distribution
Authors: Ali El-Zaart, Wafaa Kamel Al-Jibory
Date: 2013-05-24 00:00:00
Tasks: Crop Type Mapping, Edge Detection

Radar images can reveal information about the shape of the surface terrain as
well as its physical and biophysical properties. Radar images have long been
used in geological studies to map structural features that are revealed by the
shape of the landscape. Radar imagery also has applications in vegetation and
crop type mapping, landscape ecology, hydrology, and volcanology. Image
processing is using for detecting for objects in radar images. Edge detection;
which is a method of determining the discontinuities in gray level images; is a
very important initial step in Image processing. Many classical edge detectors
have been developed over time. Some of the well-known edge detection operators
based on the first derivative of the image are Roberts, Prewitt, Sobel which is
traditionally implemented by convolving the image with masks. Also Gaussian
distribution has been used to build masks for the first and second derivative.
However, this distribution has limit to only symmetric shape. This paper will
use to construct the masks, the Weibull distribution which was more general
than Gaussian because it has symmetric and asymmetric shape. The constructed
masks are applied to images and we obtained good results.
Density-sensitive semisupervised inference
Authors: Martin Azizyan, Aarti Singh, Larry Wasserman
Date: 2012-04-07 00:00:00

Semisupervised methods are techniques for using labeled data
$(X_1,Y_1),\ldots,(X_n,Y_n)$ together with unlabeled data $X_{n+1},\ldots,X_N$
to make predictions. These methods invoke some assumptions that link the
marginal distribution $P_X$ of X to the regression function f(x). For example,
it is common to assume that f is very smooth over high density regions of
$P_X$. Many of the methods are ad-hoc and have been shown to work in specific
examples but are lacking a theoretical foundation. We provide a minimax
framework for analyzing semisupervised methods. In particular, we study methods
based on metrics that are sensitive to the distribution $P_X$. Our model
includes a parameter $\alpha$ that controls the strength of the semisupervised
assumption. We then use the data to adapt to $\alpha$.
Validity of a clinical decision rule based alert system for drug dose adjustment in patients with renal failure intended to improve pharmacists' analysis of medication orders in hospitals
Authors: Boussadi Abdelali, Caruba Thibaut, Karras Alexandre, Berdot Sarah, Degoulet Patrice, Durieux Pierre, Sabatier Brigitte
Date: 2013-05-24 00:00:00
Tasks: Diagnostic

Objective: The main objective of this study was to assess the diagnostic
performances of an alert system integrated into the CPOE/EMR system for renally
cleared drug dosing control. The generated alerts were compared with the daily
routine practice of pharmacists as part of the analysis of medication orders.
Materials and Methods: The pharmacists performed their analysis of medication
orders as usual and were not aware of the alert system interventions that were
not displayed for the purpose of the study neither to the physician nor to the
pharmacist but kept with associate recommendations in a log file. A senior
pharmacist analyzed the results of medication order analysis with and without
the alert system. The unit of analysis was the drug prescription line. The
primary study endpoints were the detection of drug-dose prescription errors and
inter-rater reliability between the alert system and the pharmacists in the
detection of drug dose error. Results: The alert system fired alerts in 8.41%
(421/5006) of cases: 5.65% (283/5006) exceeds max daily dose alerts and 2.76%
(138/5006) under dose alerts. The alert system and the pharmacists showed a
relatively poor concordance: 0.106 (CI 95% [0.068, 0.144]). According to the
senior pharmacist review, the alert system fired more appropriate alerts than
pharmacists, and made fewer errors than pharmacists in analyzing drug dose
prescriptions: 143 for the alert system and 261 for the pharmacists. Unlike the
alert system, most diagnostic errors made by the pharmacists were false
negatives. The pharmacists were not able to analyze a significant number (2097;
25.42%) of drug prescription lines because understaffing. Conclusion: This
study strongly suggests that an alert system would be complementary to the
pharmacists activity and contribute to drug prescription safety.
The multi-armed bandit problem with covariates
Authors: Vianney Perchet, Philippe Rigollet
Date: 2011-10-27 00:00:00

We consider a multi-armed bandit problem in a setting where each arm produces
a noisy reward realization which depends on an observable random covariate. As
opposed to the traditional static multi-armed bandit problem, this setting
allows for dynamically changing rewards that better describe applications where
side information is available. We adopt a nonparametric model where the
expected rewards are smooth functions of the covariate and where the hardness
of the problem is captured by a margin parameter. To maximize the expected
cumulative reward, we introduce a policy called Adaptively Binned Successive
Elimination (abse) that adaptively decomposes the global problem into suitably
"localized" static bandit problems. This policy constructs an adaptive
partition using a variant of the Successive Elimination (se) policy. Our
results include sharper regret bounds for the se policy in a static bandit
problem and minimax optimal regret bounds for the abse policy in the dynamic
problem.
Applications of Clifford's Geometric Algebra
Authors: Eckhard Hitzer, Tohru Nitta, Yasuaki Kuroe
Date: 2013-05-24 00:00:00
Tasks: Survey

We survey the development of Clifford's geometric algebra and some of its
engineering applications during the last 15 years. Several recently developed
applications and their merits are discussed in some detail. We thus hope to
clearly demonstrate the benefit of developing problem solutions in a unified
framework for algebra and geometry with the widest possible scope: from quantum
computing and electromagnetism to satellite navigation, from neural computing
to camera geometry, image processing, robotics and beyond.
ML4PG in Computer Algebra verification
Authors: Jónathan Heras, Ekaterina Komendantskaya
Date: 2013-02-26 00:00:00
Tasks: BIG-bench Machine Learning

ML4PG is a machine-learning extension that provides statistical proof hints
during the process of Coq/SSReflect proof development. In this paper, we use
ML4PG to find proof patterns in the CoqEAL library -- a library that was
devised to verify the correctness of Computer Algebra algorithms. In
particular, we use ML4PG to help us in the formalisation of an efficient
algorithm to compute the inverse of triangular matrices.
Verifying a platform for digital imaging: a multi-tool strategy
Authors: Jónathan Heras, Gadea Mata, Ana Romero, Julio Rubio, Rubén Sáenz
Date: 2013-03-05 00:00:00

Fiji is a Java platform widely used by biologists and other experimental
scientists to process digital images. In particular, in our research - made
together with a biologists team; we use Fiji in some pre-processing steps
before undertaking a homological digital processing of images. In a previous
work, we have formalised the correctness of the programs which use homological
techniques to analyse digital images. However, the verification of Fiji's
pre-processing step was missed. In this paper, we present a multi-tool approach
filling this gap, based on the combination of Why/Krakatoa, Coq and ACL2.
Algebraic Net Class Rewriting Systems, Syntax and Semantics for Knowledge Representation and Automated Problem Solving
Authors: Seppo Ilari Tirri
Date: 2013-05-24 00:00:00

The intention of the present study is to establish general framework for
automated problem solving by approaching the task universal algebraically
introducing knowledge as realizations of generalized free algebra based nets,
graphs with gluing forms connecting in- and out-edges to nodes. Nets are caused
to undergo transformations in conceptual level by type wise differentiated
intervening net rewriting systems dispersing problems to abstract parts,
matching being determined by substitution relations. Achieved sets of
conceptual nets constitute congruent classes. New results are obtained within
construction of problem solving systems where solution algorithms are derived
parallel with other candidates applied to the same net classes. By applying
parallel transducer paths consisting of net rewriting systems to net classes
congruent quotient algebras are established and the manifested class rewriting
comprises all solution candidates whenever produced nets are in anticipated
languages liable to acceptance of net automata.
Integrating tabu search and VLSN search to develop enhanced algorithms: A case study using bipartite boolean quadratic programs
Authors: Fred Glover, Tao Ye, Abraham P. Punnen, Gary Kochenberger
Date: 2013-05-24 00:00:00

The bipartite boolean quadratic programming problem (BBQP) is a
generalization of the well studied boolean quadratic programming problem. The
model has a variety of real life applications; however, empirical studies of
the model are not available in the literature, except in a few isolated
instances. In this paper, we develop efficient heuristic algorithms based on
tabu search, very large scale neighborhood (VLSN) search, and a hybrid
algorithm that integrates the two. The computational study establishes that
effective integration of simple tabu search with VLSN search results in
superior outcomes, and suggests the value of such an integration in other
settings. Complexity analysis and implementation details are provided along
with conclusions drawn from experimental analysis. In addition, we obtain
solutions better than the best previously known for almost all medium and large
size benchmark instances.
Learning from Complex Systems: On the Roles of Entropy and Fisher Information in Pairwise Isotropic Gaussian Markov Random Fields
Authors: Alexandre L. M. Levada
Date: 2011-08-25 00:00:00

Markov Random Field models are powerful tools for the study of complex
systems. However, little is known about how the interactions between the
elements of such systems are encoded, especially from an information-theoretic
perspective. In this paper, our goal is to enlight the connection between
Fisher information, Shannon entropy, information geometry and the behavior of
complex systems modeled by isotropic pairwise Gaussian Markov random fields. We
propose analytical expressions to compute local and global versions of these
measures using Besag's pseudo-likelihood function, characterizing the system's
behavior through its \emph{Fisher curve}, a parametric trajectory accross the
information space that provides a geometric representation for the study of
complex systems. Computational experiments show how the proposed tools can be
useful in extrating relevant information from complex patterns. The obtained
results quantify and support our main conclusion, which is: in terms of
information, moving towards higher entropy states (A --> B) is different from
moving towards lower entropy states (B --> A), since the \emph{Fisher curves}
are not the same given a natural orientation (the direction of time).
Cluster Forests
Authors: Donghui Yan, Aiyou Chen, Michael. I. Jordan
Date: 2011-04-14 00:00:00
Tasks: Clustering, Clustering Ensemble

With inspiration from Random Forests (RF) in the context of classification, a
new clustering ensemble method---Cluster Forests (CF) is proposed.
Geometrically, CF randomly probes a high-dimensional data cloud to obtain "good
local clusterings" and then aggregates via spectral clustering to obtain
cluster assignments for the whole dataset. The search for good local
clusterings is guided by a cluster quality measure kappa. CF progressively
improves each local clustering in a fashion that resembles the tree growth in
RF. Empirical studies on several real-world datasets under two different
performance metrics show that CF compares favorably to its competitors.
Theoretical analysis reveals that the kappa measure makes it possible to grow
the local clustering in a desirable way---it is "noise-resistant". A
closed-form expression is obtained for the mis-clustering rate of spectral
clustering under a perturbation model, which yields new insights into some
aspects of spectral clustering.
A Primal Condition for Approachability with Partial Monitoring
Authors: Shie Mannor, Vianney Perchet, Gilles Stoltz
Date: 2013-05-23 00:00:00
Tasks: Form

In approachability with full monitoring there are two types of conditions
that are known to be equivalent for convex sets: a primal and a dual condition.
The primal one is of the form: a set C is approachable if and only all
containing half-spaces are approachable in the one-shot game; while the dual
one is of the form: a convex set C is approachable if and only if it intersects
all payoff sets of a certain form. We consider approachability in games with
partial monitoring. In previous works (Perchet 2011; Mannor et al. 2011) we
provided a dual characterization of approachable convex sets; we also exhibited
efficient strategies in the case where C is a polytope. In this paper we
provide primal conditions on a convex set to be approachable with partial
monitoring. They depend on a modified reward function and lead to
approachability strategies, based on modified payoff functions, that proceed by
projections similarly to Blackwell's (1956) strategy; this is in contrast with
previously studied strategies in this context that relied mostly on the
signaling structure and aimed at estimating well the distributions of the
signals received. Our results generalize classical results by Kohlberg 1975
(see also Mertens et al. 1994) and apply to games with arbitrary signaling
structure as well as to arbitrary convex sets.
Constant conditional entropy and related hypotheses
Authors: Ramon Ferrer-i-Cancho, Łukasz Dębowski, Fermín Moscoso del Prado Martín
Date: 2013-04-27 00:00:00

Constant entropy rate (conditional entropies must remain constant as the
sequence length increases) and uniform information density (conditional
probabilities must remain constant as the sequence length increases) are two
information theoretic principles that are argued to underlie a wide range of
linguistic phenomena. Here we revise the predictions of these principles to the
light of Hilberg's law on the scaling of conditional entropy in language and
related laws. We show that constant entropy rate (CER) and two interpretations
for uniform information density (UID), full UID and strong UID, are
inconsistent with these laws. Strong UID implies CER but the reverse is not
true. Full UID, a particular case of UID, leads to costly uncorrelated
sequences that are totally unrealistic. We conclude that CER and its particular
cases are incomplete hypotheses about the scaling of conditional entropies.
Dimension Independent Similarity Computation
Authors: Reza Bosagh Zadeh, Ashish Goel
Date: 2012-06-11 00:00:00
Tasks: All

We present a suite of algorithms for Dimension Independent Similarity
Computation (DISCO) to compute all pairwise similarities between very high
dimensional sparse vectors. All of our results are provably independent of
dimension, meaning apart from the initial cost of trivially reading in the
data, all subsequent operations are independent of the dimension, thus the
dimension can be very large. We study Cosine, Dice, Overlap, and the Jaccard
similarity measures. For Jaccard similiarity we include an improved version of
MinHash. Our results are geared toward the MapReduce framework. We empirically
validate our theorems at large scale using data from the social networking site
Twitter. At time of writing, our algorithms are live in production at
twitter.com.
A Supervised Neural Autoregressive Topic Model for Simultaneous Image Classification and Annotation
Authors: Yin Zheng, Yu-Jin Zhang, Hugo Larochelle
Date: 2013-05-23 00:00:00
Tasks: General Classification, image-classification, Image Classification, Scene Recognition, Topic Models

Topic modeling based on latent Dirichlet allocation (LDA) has been a
framework of choice to perform scene recognition and annotation. Recently, a
new type of topic model called the Document Neural Autoregressive Distribution
Estimator (DocNADE) was proposed and demonstrated state-of-the-art performance
for document modeling. In this work, we show how to successfully apply and
extend this model to the context of visual scene modeling. Specifically, we
propose SupDocNADE, a supervised extension of DocNADE, that increases the
discriminative power of the hidden topic features by incorporating label
information into the training objective of the model. We also describe how to
leverage information about the spatial position of the visual words and how to
embed additional image annotations, so as to simultaneously perform image
classification and annotation. We test our model on the Scene15, LabelMe and
UIUC-Sports datasets and show that it compares favorably to other topic models
such as the supervised variant of LDA.
A novel automatic thresholding segmentation method with local adaptive thresholds
Authors: Bo Xiao, Yuefeng Jing, Yonghong Guan
Date: 2013-05-22 00:00:00
Tasks: Object

A novel method for segmenting bright objects from dark background for
grayscale image is proposed. The concept of this method can be stated simply
as: to pick out the local-thinnest bands on the grayscale grade-map. It turns
out to be a threshold-based method with local adaptive thresholds, where each
local threshold is determined by requiring the average normal-direction
gradient on the object boundary to be local minimal. The method is highly
automatic and the segmentation mimics a man's natural expectation even the
object boundaries are fuzzy.
Sharp analysis of low-rank kernel matrix approximations
Authors: Francis Bach
Date: 2012-08-09 00:00:00
Tasks: regression

We consider supervised learning problems within the positive-definite kernel
framework, such as kernel ridge regression, kernel logistic regression or the
support vector machine. With kernels leading to infinite-dimensional feature
spaces, a common practical limiting difficulty is the necessity of computing
the kernel matrix, which most frequently leads to algorithms with running time
at least quadratic in the number of observations n, i.e., O(n^2). Low-rank
approximations of the kernel matrix are often considered as they allow the
reduction of running time complexities to O(p^2 n), where p is the rank of the
approximation. The practicality of such methods thus depends on the required
rank p. In this paper, we show that in the context of kernel ridge regression,
for approximations based on a random subset of columns of the original kernel
matrix, the rank p may be chosen to be linear in the degrees of freedom
associated with the problem, a quantity which is classically used in the
statistical analysis of such methods, and is often seen as the implicit number
of parameters of non-parametric estimators. This result enables simple
algorithms that have sub-quadratic running time complexity, but provably
exhibit the same predictive performance than existing algorithms, for any given
problem instance, and not only for worst-case situations.
A Comparison of Random Forests and Ferns on Recognition of Instruments in Jazz Recordings
Authors: Alicja A. Wieczorkowska, Miron B. Kursa
Date: 2013-05-22 00:00:00
Tasks: Classification, General Classification

In this paper, we first apply random ferns for classification of real music
recordings of a jazz band. No initial segmentation of audio data is assumed,
i.e., no onset, offset, nor pitch data are needed. The notion of random ferns
is described in the paper, to familiarize the reader with this classification
algorithm, which was introduced quite recently and applied so far in image
recognition tasks. The performance of random ferns is compared with random
forests for the same data. The results of experiments are presented in the
paper, and conclusions are drawn.
Evolution of Covariance Functions for Gaussian Process Regression using Genetic Programming
Authors: Gabriel Kronberger, Michael Kommenda
Date: 2013-05-16 00:00:00
Tasks: Gaussian Processes, regression, Time Series, Time Series Analysis

In this contribution we describe an approach to evolve composite covariance
functions for Gaussian processes using genetic programming. A critical aspect
of Gaussian processes and similar kernel-based models such as SVM is, that the
covariance function should be adapted to the modeled data. Frequently, the
squared exponential covariance function is used as a default. However, this can
lead to a misspecified model, which does not fit the data well. In the proposed
approach we use a grammar for the composition of covariance functions and
genetic programming to search over the space of sentences that can be derived
from the grammar. We tested the proposed approach on synthetic data from
two-dimensional test functions, and on the Mauna Loa CO2 time series. The
results show, that our approach is feasible, finding covariance functions that
perform much better than a default covariance function. For the CO2 data set a
composite covariance function is found, that matches the performance of a
hand-tuned covariance function.
Towards Rational Deployment of Multiple Heuristics in A*
Authors: David Tolpin, Tal Beja, Solomon Eyal Shimony, Ariel Felner, Erez Karpas
Date: 2013-05-22 00:00:00

The obvious way to use several admissible heuristics in A* is to take their
maximum. In this paper we aim to reduce the time spent on computing heuristics.
We discuss Lazy A*, a variant of A* where heuristics are evaluated lazily: only
when they are essential to a decision to be made in the A* search process. We
present a new rational meta-reasoning based scheme, rational lazy A*, which
decides whether to compute the more expensive heuristics at all, based on a
myopic value of information estimate. Both methods are examined theoretically.
Empirical evaluation on several domains supports the theoretical results, and
shows that lazy A* and rational lazy A* are state-of-the-art heuristic
combination methods.