pwc-archive/papers-with-abstracts huggingface dataset:
Multiclass Data Segmentation using Diffuse Interface Methods on Graphs
Authors: Cristina Garcia-Cardona, Ekaterina Merkurjev, Andrea L. Bertozzi, Arjuna Flenner, Allon Percus
Date: 2013-02-15 00:00:00
Tasks: compressed sensing, Segmentation

We present two graph-based algorithms for multiclass segmentation of
high-dimensional data. The algorithms use a diffuse interface model based on
the Ginzburg-Landau functional, related to total variation compressed sensing
and image processing. A multiclass extension is introduced using the Gibbs
simplex, with the functional's double-well potential modified to handle the
multiclass case. The first algorithm minimizes the functional using a convex
splitting numerical scheme. The second algorithm is a uses a graph adaptation
of the classical numerical Merriman-Bence-Osher (MBO) scheme, which alternates
between diffusion and thresholding. We demonstrate the performance of both
algorithms experimentally on synthetic data, grayscale and color images, and
several benchmark data sets such as MNIST, COIL and WebKB. We also make use of
fast numerical solvers for finding the eigenvectors and eigenvalues of the
graph Laplacian, and take advantage of the sparsity of the matrix. Experiments
indicate that the results are competitive with or better than the current
state-of-the-art multiclass segmentation algorithms.
Distortion-driven Turbulence Effect Removal using Variational Model
Authors: Yuan Xie, Wensheng Zhang, DaCheng Tao, Wenrui Hu, Yanyun Qu, Hanzi Wang
Date: 2014-01-17 00:00:00
Tasks: model, regression

It remains a challenge to simultaneously remove geometric distortion and
space-time-varying blur in frames captured through a turbulent atmospheric
medium. To solve, or at least reduce these effects, we propose a new scheme to
recover a latent image from observed frames by integrating a new variational
model and distortion-driven spatial-temporal kernel regression. The proposed
scheme first constructs a high-quality reference image from the observed frames
using low-rank decomposition. Then, to generate an improved registered
sequence, the reference image is iteratively optimized using a variational
model containing a new spatial-temporal regularization. The proposed fast
algorithm efficiently solves this model without the use of partial differential
equations (PDEs). Next, to reduce blur variation, distortion-driven
spatial-temporal kernel regression is carried out to fuse the registered
sequence into one image by introducing the concept of the near-stationary
patch. Applying a blind deconvolution algorithm to the fused image produces the
final output. Extensive experimental testing shows, both qualitatively and
quantitatively, that the proposed method can effectively alleviate distortion
and blur and recover details of the original scene compared to state-of-the-art
methods.
Entropy analysis of word-length series of natural language texts: Effects of text language and genre
Authors: Maria Kalimeri, Vassilios Constantoudis, Constantinos Papadimitriou, Kostantinos Karamanos, Fotis K. Diakonos, Haris Papageorgiou
Date: 2014-01-17 00:00:00
Tasks: Attribute, Sensitivity

We estimate the $n$-gram entropies of natural language texts in word-length
representation and find that these are sensitive to text language and genre. We
attribute this sensitivity to changes in the probability distribution of the
lengths of single words and emphasize the crucial role of the uniformity of
probabilities of having words with length between five and ten. Furthermore,
comparison with the entropies of shuffled data reveals the impact of word
length correlations on the estimated $n$-gram entropies.
Arguments using ontological and causal knowledge
Authors: Philippe Besnard, Marie-Odile Cordier, Yves Moinard
Date: 2014-01-16 00:00:00

We investigate an approach to reasoning about causes through argumentation.
We consider a causal model for a physical system, and look for arguments about
facts. Some arguments are meant to provide explanations of facts whereas some
challenge these explanations and so on. At the root of argumentation here, are
causal links ({A_1, ... ,A_n} causes B) and ontological links (o_1 is_a o_2).
We present a system that provides a candidate explanation ({A_1, ... ,A_n}
explains {B_1, ... ,B_m}) by resorting to an underlying causal link
substantiated with appropriate ontological links. Argumentation is then at work
from these various explaining links. A case study is developed: a severe storm
Xynthia that devastated part of France in 2010, with an unaccountably high
number of casualties.
Convex Optimization for Binary Classifier Aggregation in Multiclass Problems
Authors: Sunho Park, TaeHyun Hwang, Seungjin Choi
Date: 2014-01-16 00:00:00

Multiclass problems are often decomposed into multiple binary problems that
are solved by individual binary classifiers whose results are integrated into a
final answer. Various methods, including all-pairs (APs), one-versus-all (OVA),
and error correcting output code (ECOC), have been studied, to decompose
multiclass problems into binary problems. However, little study has been made
to optimally aggregate binary problems to determine a final answer to the
multiclass problem. In this paper we present a convex optimization method for
an optimal aggregation of binary classifiers to estimate class membership
probabilities in multiclass problems. We model the class membership probability
as a softmax function which takes a conic combination of discrepancies induced
by individual binary classifiers, as an input. With this model, we formulate
the regularized maximum likelihood estimation as a convex optimization problem,
which is solved by the primal-dual interior point method. Connections of our
method to large margin classifiers are presented, showing that the large margin
formulation can be considered as a limiting case of our convex formulation.
Numerical experiments on synthetic and real-world data sets demonstrate that
our method outperforms existing aggregation methods as well as direct methods,
in terms of the classification accuracy and the quality of class membership
probability estimates.
Detection of Anomalous Crowd Behavior Using Spatio-Temporal Multiresolution Model and Kronecker Sum Decompositions
Authors: Kristjan Greenewald, Alfred Hero
Date: 2014-01-14 00:00:00

In this work we consider the problem of detecting anomalous spatio-temporal
behavior in videos. Our approach is to learn the normative multiframe pixel
joint distribution and detect deviations from it using a likelihood based
approach. Due to the extreme lack of available training samples relative to the
dimension of the distribution, we use a mean and covariance approach and
consider methods of learning the spatio-temporal covariance in the low-sample
regime. Our approach is to estimate the covariance using parameter reduction
and sparse models. The first method considered is the representation of the
covariance as a sum of Kronecker products as in (Greenewald et al 2013), which
is found to be an accurate approximation in this setting. We propose learning
algorithms relevant to our problem. We then consider the sparse multiresolution
model of (Choi et al 2010) and apply the Kronecker product methods to it for
further parameter reduction, as well as introducing modifications for enhanced
efficiency and greater applicability to spatio-temporal covariance matrices. We
apply our methods to the detection of crowd behavior anomalies in the
University of Minnesota crowd anomaly dataset, and achieve competitive results.
Towards the selection of patients requiring ICD implantation by automatic classification from Holter monitoring indices
Authors: Charles-Henri Cappelaere, R. Dubois, P. Roussel, G. Dreyfus
Date: 2014-01-16 00:00:00
Tasks: General Classification, Specificity

The purpose of this study is to optimize the selection of prophylactic
cardioverter defibrillator implantation candidates. Currently, the main
criterion for implantation is a low Left Ventricular Ejection Fraction (LVEF)
whose specificity is relatively poor. We designed two classifiers aimed to
predict, from long term ECG recordings (Holter), whether a low-LVEF patient is
likely or not to undergo ventricular arrhythmia in the next six months. One
classifier is a single hidden layer neural network whose variables are the most
relevant features extracted from Holter recordings, and the other classifier
has a structure that capitalizes on the physiological decomposition of the
arrhythmogenic factors into three disjoint groups: the myocardial substrate,
the triggers and the autonomic nervous system (ANS). In this ad hoc network,
the features were assigned to each group; one neural network classifier per
group was designed and its complexity was optimized. The outputs of the
classifiers were fed to a single neuron that provided the required probability
estimate. The latter was thresholded for final discrimination A dataset
composed of 186 pre-implantation 30-mn Holter recordings of patients equipped
with an implantable cardioverter defibrillator (ICD) in primary prevention was
used in order to design and test this classifier. 44 out of 186 patients
underwent at least one treated ventricular arrhythmia during the six-month
follow-up period. Performances of the designed classifier were evaluated using
a cross-test strategy that consists in splitting the database into several
combinations of a training set and a test set. The average arrhythmia
prediction performances of the ad-hoc classifier are NPV = 77% $\pm$ 13% and
PPV = 31% $\pm$ 19% (Negative Predictive Value $\pm$ std, Positive Predictive
Value $\pm$ std). According to our study, improving prophylactic
ICD-implantation candidate selection by automatic classification from ECG
features may be possible, but the availability of a sizable dataset appears to
be essential to decrease the number of False Negatives.
Revisiting loss-specific training of filter-based MRFs for image restoration
Authors: Yunjin Chen, Thomas Pock, René Ranftl, Horst Bischof
Date: 2014-01-16 00:00:00
Tasks: Denoising, GPU, Image Denoising, Image Restoration

It is now well known that Markov random fields (MRFs) are particularly
effective for modeling image priors in low-level vision. Recent years have seen
the emergence of two main approaches for learning the parameters in MRFs: (1)
probabilistic learning using sampling-based algorithms and (2) loss-specific
training based on MAP estimate. After investigating existing training
approaches, it turns out that the performance of the loss-specific training has
been significantly underestimated in existing work. In this paper, we revisit
this approach and use techniques from bi-level optimization to solve it. We
show that we can get a substantial gain in the final performance by solving the
lower-level problem in the bi-level framework with high accuracy using our
newly proposed algorithm. As a result, our trained model is on par with highly
specialized image denoising algorithms and clearly outperforms
probabilistically trained MRF models. Our findings suggest that for the
loss-specific training scheme, solving the lower-level problem with higher
accuracy is beneficial. Our trained model comes along with the additional
advantage, that inference is extremely efficient. Our GPU-based implementation
takes less than 1s to produce state-of-the-art performance.
Learning $\ell_1$-based analysis and synthesis sparsity priors using bi-level optimization
Authors: Yunjin Chen, Thomas Pock, Horst Bischof
Date: 2014-01-16 00:00:00
Tasks: Denoising, Dictionary Learning, Image Denoising

We consider the analysis operator and synthesis dictionary learning problems
based on the the $\ell_1$ regularized sparse representation model. We reveal
the internal relations between the $\ell_1$-based analysis model and synthesis
model. We then introduce an approach to learn both analysis operator and
synthesis dictionary simultaneously by using a unified framework of bi-level
optimization. Our aim is to learn a meaningful operator (dictionary) such that
the minimum energy solution of the analysis (synthesis)-prior based model is as
close as possible to the ground-truth. We solve the bi-level optimization
problem using the implicit differentiation technique. Moreover, we demonstrate
the effectiveness of our leaning approach by applying the learned analysis
operator (dictionary) to the image denoising task and comparing its performance
with state-of-the-art methods. Under this unified framework, we can compare the
performance of the two types of priors.
Co-clustering separately exchangeable network data
Authors: David Choi, Patrick J. Wolfe
Date: 2012-12-17 00:00:00
Tasks: Clustering

This article establishes the performance of stochastic blockmodels in
addressing the co-clustering problem of partitioning a binary array into
subsets, assuming only that the data are generated by a nonparametric process
satisfying the condition of separate exchangeability. We provide oracle
inequalities with rate of convergence $\mathcal{O}_P(n^{-1/4})$ corresponding
to profile likelihood maximization and mean-square error minimization, and show
that the blockmodel can be interpreted in this setting as an optimal
piecewise-constant approximation to the generative nonparametric model. We also
show for large sample sizes that the detection of co-clusters in such data
indicates with high probability the existence of co-clusters of equal size and
asymptotically equivalent connectivity in the underlying generative process.
An Empirical Evaluation of Similarity Measures for Time Series Classification
Authors: Joan Serrà, Josep Lluis Arcos
Date: 2014-01-16 00:00:00
Tasks: Classification, Clustering, General Classification, Time Series, Time Series Analysis, Time Series Classification, Time Series Clustering

Time series are ubiquitous, and a measure to assess their similarity is a
core part of many computational systems. In particular, the similarity measure
is the most essential ingredient of time series clustering and classification
systems. Because of this importance, countless approaches to estimate time
series similarity have been proposed. However, there is a lack of comparative
studies using empirical, rigorous, quantitative, and large-scale assessment
strategies. In this article, we provide an extensive evaluation of similarity
measures for time series classification following the aforementioned
principles. We consider 7 different measures coming from alternative measure
`families', and 45 publicly-available time series data sets coming from a wide
variety of scientific domains. We focus on out-of-sample classification
accuracy, but in-sample accuracies and parameter choices are also discussed.
Our work is based on rigorous evaluation methodologies and includes the use of
powerful statistical significance tests to derive meaningful conclusions. The
obtained results show the equivalence, in terms of accuracy, of a number of
measures, but with one single candidate outperforming the rest. Such findings,
together with the followed methodology, invite researchers on the field to
adopt a more consistent evaluation criteria and a more informed decision
regarding the baseline measures to which new developments should be compared.
Nonparametric Latent Tree Graphical Models: Inference, Estimation, and Structure Learning
Authors: Le Song, Han Liu, Ankur Parikh, Eric Xing
Date: 2014-01-16 00:00:00
Tasks: parameter estimation

Tree structured graphical models are powerful at expressing long range or
hierarchical dependency among many variables, and have been widely applied in
different areas of computer science and statistics. However, existing methods
for parameter estimation, inference, and structure learning mainly rely on the
Gaussian or discrete assumptions, which are restrictive under many
applications. In this paper, we propose new nonparametric methods based on
reproducing kernel Hilbert space embeddings of distributions that can recover
the latent tree structures, estimate the parameters, and perform inference for
high dimensional continuous and non-Gaussian variables. The usefulness of the
proposed methods are illustrated by thorough numerical results.
Frequency Recognition in SSVEP-based BCI using Multiset Canonical Correlation Analysis
Authors: Yu Zhang, Guoxu Zhou, Jing Jin, Xingyu Wang, Andrzej Cichocki
Date: 2013-08-26 00:00:00
Tasks: EEG, Electroencephalogram (EEG), SSVEP

Canonical correlation analysis (CCA) has been one of the most popular methods
for frequency recognition in steady-state visual evoked potential (SSVEP)-based
brain-computer interfaces (BCIs). Despite its efficiency, a potential problem
is that using pre-constructed sine-cosine waves as the required reference
signals in the CCA method often does not result in the optimal recognition
accuracy due to their lack of features from the real EEG data. To address this
problem, this study proposes a novel method based on multiset canonical
correlation analysis (MsetCCA) to optimize the reference signals used in the
CCA method for SSVEP frequency recognition. The MsetCCA method learns multiple
linear transforms that implement joint spatial filtering to maximize the
overall correlation among canonical variates, and hence extracts SSVEP common
features from multiple sets of EEG data recorded at the same stimulus
frequency. The optimized reference signals are formed by combination of the
common features and completely based on training data. Experimental study with
EEG data from ten healthy subjects demonstrates that the MsetCCA method
improves the recognition accuracy of SSVEP frequency in comparison with the CCA
method and other two competing methods (multiway CCA (MwayCCA) and phase
constrained CCA (PCCA)), especially for a small number of channels and a short
time window length. The superiority indicates that the proposed MsetCCA method
is a new promising candidate for frequency recognition in SSVEP-based BCIs.
Topological Value Iteration Algorithms
Authors: Peng Dai, Mausam, Daniel Sabby Weld, Judy Goldsmith
Date: 2014-01-16 00:00:00
Tasks: Heuristic Search

Value iteration is a powerful yet inefficient algorithm for Markov decision
processes (MDPs) because it puts the majority of its effort into backing up the
entire state space, which turns out to be unnecessary in many cases. In order
to overcome this problem, many approaches have been proposed. Among them, ILAO*
and variants of RTDP are state-of-the-art ones. These methods use reachability
analysis and heuristic search to avoid some unnecessary backups. However, none
of these approaches build the graphical structure of the state transitions in a
pre-processing step or use the structural information to systematically
decompose a problem, whereby generating an intelligent backup sequence of the
state space. In this paper, we present two optimal MDP algorithms. The first
algorithm, topological value iteration (TVI), detects the structure of MDPs and
backs up states based on topological sequences. It (1) divides an MDP into
strongly-connected components (SCCs), and (2) solves these components
sequentially. TVI outperforms VI and other state-of-the-art algorithms vastly
when an MDP has multiple, close-to-equal-sized SCCs. The second algorithm,
focused topological value iteration (FTVI), is an extension of TVI. FTVI
restricts its attention to connected components that are relevant for solving
the MDP. Specifically, it uses a small amount of heuristic search to eliminate
provably sub-optimal actions; this pruning allows FTVI to find smaller
connected components, thus running faster. We demonstrate that FTVI outperforms
TVI by an order of magnitude, averaged across several domains. Surprisingly,
FTVI also significantly outperforms popular heuristically-informed MDP
algorithms such as ILAO*, LRTDP, BRTDP and Bayesian-RTDP in many domains,
sometimes by as much as two orders of magnitude. Finally, we characterize the
type of domains where FTVI excels --- suggesting a way to an informed choice of
solver.
Scheduling Bipartite Tournaments to Minimize Total Travel Distance
Authors: Richard Hoshino, Ken-ichi Kawarabayashi
Date: 2014-01-16 00:00:00
Tasks: Scheduling

In many professional sports leagues, teams from opposing leagues/conferences
compete against one another, playing inter-league games. This is an example of
a bipartite tournament. In this paper, we consider the problem of reducing the
total travel distance of bipartite tournaments, by analyzing inter-league
scheduling from the perspective of discrete optimization. This research has
natural applications to sports scheduling, especially for leagues such as the
National Basketball Association (NBA) where teams must travel long distances
across North America to play all their games, thus consuming much time, money,
and greenhouse gas emissions. We introduce the Bipartite Traveling Tournament
Problem (BTTP), the inter-league variant of the well-studied Traveling
Tournament Problem. We prove that the 2n-team BTTP is NP-complete, but for
small values of n, a distance-optimal inter-league schedule can be generated
from an algorithm based on minimum-weight 4-cycle-covers. We apply our
theoretical results to the 12-team Nippon Professional Baseball (NPB) league in
Japan, producing a provably-optimal schedule requiring 42950 kilometres of
total team travel, a 16% reduction compared to the actual distance traveled by
these teams during the 2010 NPB season. We also develop a nearly-optimal
inter-league tournament for the 30-team NBA league, just 3.8% higher than the
trivial theoretical lower bound.
Centrality-as-Relevance: Support Sets and Similarity as Geometric Proximity
Authors: Ricardo Ribeiro, David Martins de Matos
Date: 2014-01-16 00:00:00

In automatic summarization, centrality-as-relevance means that the most
important content of an information source, or a collection of information
sources, corresponds to the most central passages, considering a representation
where such notion makes sense (graph, spatial, etc.). We assess the main
paradigms, and introduce a new centrality-based relevance model for automatic
summarization that relies on the use of support sets to better estimate the
relevant content. Geometric proximity is used to compute semantic relatedness.
Centrality (relevance) is determined by considering the whole input source (and
not only local information), and by taking into account the existence of minor
topics or lateral subjects in the information sources to be summarized. The
method consists in creating, for each passage of the input source, a support
set consisting only of the most semantically related passages. Then, the
determination of the most relevant content is achieved by selecting the
passages that occur in the largest number of support sets. This model produces
extractive summaries that are generic, and language- and domain-independent.
Thorough automatic evaluation shows that the method achieves state-of-the-art
performance, both in written text, and automatically transcribed speech
summarization, including when compared to considerably more complex approaches.
Policy Invariance under Reward Transformations for General-Sum Stochastic Games
Authors: Xiaosong Lu, Howard M. Schwartz, Sidney N. Givigi Jr
Date: 2014-01-16 00:00:00

We extend the potential-based shaping method from Markov decision processes
to multi-player general-sum stochastic games. We prove that the Nash equilibria
in a stochastic game remains unchanged after potential-based shaping is applied
to the environment. The property of policy invariance provides a possible way
of speeding convergence when learning to play a stochastic game.