pwc-archive/papers-with-abstracts huggingface dataset:
An Adaptive Amoeba Algorithm for Shortest Path Tree Computation in Dynamic Graphs
Authors: Xiaoge Zhang, Qi Liu, Yong Hu, Felix T. S. Chan, Sankaran Mahadevan, Zili Zhang, Yong Deng
Date: 2013-11-03 00:00:00

This paper presents an adaptive amoeba algorithm to address the shortest path
tree (SPT) problem in dynamic graphs. In dynamic graphs, the edge weight
updates consists of three categories: edge weight increases, edge weight
decreases, the mixture of them. Existing work on this problem solve this issue
through analyzing the nodes influenced by the edge weight updates and recompute
these affected vertices. However, when the network becomes big, the process
will become complex. The proposed method can overcome the disadvantages of the
existing approaches. The most important feature of this algorithm is its
adaptivity. When the edge weight changes, the proposed algorithm can recognize
the affected vertices and reconstruct them spontaneously. To evaluate the
proposed adaptive amoeba algorithm, we compare it with the Label Setting
algorithm and Bellman-Ford algorithm. The comparison results demonstrate the
effectiveness of the proposed method.
On multi-class learning through the minimization of the confusion matrix norm
Authors: Sokol Koço, Cécile Capponi
Date: 2013-03-16 00:00:00
Tasks: General Classification, imbalanced classification, Multi-class Classification

In imbalanced multi-class classification problems, the misclassification rate
as an error measure may not be a relevant choice. Several methods have been
developed where the performance measure retained richer information than the
mere misclassification rate: misclassification costs, ROC-based information,
etc. Following this idea of dealing with alternate measures of performance, we
propose to address imbalanced classification problems by using a new measure to
be optimized: the norm of the confusion matrix. Indeed, recent results show
that using the norm of the confusion matrix as an error measure can be quite
interesting due to the fine-grain informations contained in the matrix,
especially in the case of imbalanced classes. Our first contribution then
consists in showing that optimizing criterion based on the confusion matrix
gives rise to a common background for cost-sensitive methods aimed at dealing
with imbalanced classes learning problems. As our second contribution, we
propose an extension of a recent multi-class boosting method --- namely
AdaBoost.MM --- to the imbalanced class problem, by greedily minimizing the
empirical norm of the confusion matrix. A theoretical analysis of the
properties of the proposed method is presented, while experimental results
illustrate the behavior of the algorithm and show the relevancy of the approach
compared to other methods.
Second Croatian Computer Vision Workshop (CCVW 2013)
Authors: Sven Lončarić, Siniša Šegvić
Date: 2013-10-01 00:00:00

Proceedings of the Second Croatian Computer Vision Workshop (CCVW 2013,
http://www.fer.unizg.hr/crv/ccvw2013) held September 19, 2013, in Zagreb,
Croatia. Workshop was organized by the Center of Excellence for Computer Vision
of the University of Zagreb.
Info-computational constructivism in modelling of life as cognition
Authors: Gordana Dodig-Crnkovic
Date: 2013-11-02 00:00:00
Tasks: Open-Ended Question Answering

This paper addresses the open question formulated as: Which levels of
abstraction are appropriate in the synthetic modelling of life and cognition?
within the framework of info-computational constructivism, treating natural
phenomena as computational processes on informational structures. At present we
lack the common understanding of the processes of life and cognition in living
organisms with the details of co-construction of informational structures and
computational processes in embodied, embedded cognizing agents, both living and
artifactual ones. Starting with the definition of an agent as an entity capable
of acting on its own behalf, as an actor in Hewitt Actor model of computation,
even so simple systems as molecules can be modelled as actors exchanging
messages (information). We adopt Kauffmans view of a living agent as something
that can reproduce and undergoes at least one thermodynamic work cycle. This
definition of living agents leads to the Maturana and Varelas identification of
life with cognition. Within the info-computational constructive approach to
living beings as cognizing agents, from the simplest to the most complex living
systems, mechanisms of cognition can be studied in order to construct synthetic
model classes of artifactual cognizing agents on different levels of
organization.
Inferring clonal evolution of tumors from single nucleotide somatic mutations
Authors: Wei Jiao, Shankar Vembu, Amit G. Deshwar, Lincoln Stein, Quaid Morris
Date: 2012-10-11 00:00:00

High-throughput sequencing allows the detection and quantification of
frequencies of somatic single nucleotide variants (SNV) in heterogeneous tumor
cell populations. In some cases, the evolutionary history and population
frequency of the subclonal lineages of tumor cells present in the sample can be
reconstructed from these SNV frequency measurements. However, automated methods
to do this reconstruction are not available and the conditions under which
reconstruction is possible have not been described.
  We describe the conditions under which the evolutionary history can be
uniquely reconstructed from SNV frequencies from single or multiple samples
from the tumor population and we introduce a new statistical model, PhyloSub,
that infers the phylogeny and genotype of the major subclonal lineages
represented in the population of cancer cells. It uses a Bayesian nonparametric
prior over trees that groups SNVs into major subclonal lineages and
automatically estimates the number of lineages and their ancestry. We sample
from the joint posterior distribution over trees to identify evolutionary
histories and cell population frequencies that have the highest probability of
generating the observed SNV frequency data. When multiple phylogenies are
consistent with a given set of SNV frequencies, PhyloSub represents the
uncertainty in the tumor phylogeny using a partial order plot. Experiments on a
simulated dataset and two real datasets comprising tumor samples from acute
myeloid leukemia and chronic lymphocytic leukemia patients demonstrate that
PhyloSub can infer both linear (or chain) and branching lineages and its
inferences are in good agreement with ground truth, where it is available.
Information, Computation, Cognition. Agency-based Hierarchies of Levels
Authors: Gordana Dodig-Crnkovic
Date: 2013-11-02 00:00:00

Nature can be seen as informational structure with computational dynamics
(info-computationalism), where an (info-computational) agent is needed for the
potential information of the world to actualize. Starting from the definition
of information as the difference in one physical system that makes a difference
in another physical system, which combines Bateson and Hewitt definitions, the
argument is advanced for natural computation as a computational model of the
dynamics of the physical world where information processing is constantly going
on, on a variety of levels of organization. This setting helps elucidating the
relationships between computation, information, agency and cognition, within
the common conceptual framework, which has special relevance for biology and
robotics.
Data-based approximate policy iteration for nonlinear continuous-time optimal control design
Authors: Biao Luo, Huai-Ning Wu, Ting-Wen Huang, Derong Liu
Date: 2013-11-02 00:00:00
Tasks: Reinforcement Learning

This paper addresses the model-free nonlinear optimal problem with
generalized cost functional, and a data-based reinforcement learning technique
is developed. It is known that the nonlinear optimal control problem relies on
the solution of the Hamilton-Jacobi-Bellman (HJB) equation, which is a
nonlinear partial differential equation that is generally impossible to be
solved analytically. Even worse, most of practical systems are too complicated
to establish their accurate mathematical model. To overcome these difficulties,
we propose a data-based approximate policy iteration (API) method by using real
system data rather than system model. Firstly, a model-free policy iteration
algorithm is derived for constrained optimal control problem and its
convergence is proved, which can learn the solution of HJB equation and optimal
control policy without requiring any knowledge of system mathematical model.
The implementation of the algorithm is based on the thought of actor-critic
structure, where actor and critic neural networks (NNs) are employed to
approximate the control policy and cost function, respectively. To update the
weights of actor and critic NNs, a least-square approach is developed based on
the method of weighted residuals. The whole data-based API method includes two
parts, where the first part is implemented online to collect real system
information, and the second part is conducting offline policy iteration to
learn the solution of HJB equation and the control policy. Then, the data-based
API algorithm is simplified for solving unconstrained optimal control problem
of nonlinear and linear systems. Finally, we test the efficiency of the
data-based API control design method on a simple nonlinear system, and further
apply it to a rotational/translational actuator system. The simulation results
demonstrate the effectiveness of the proposed method.
Coherence and sufficient sampling densities for reconstruction in compressed sensing
Authors: Franz J. Király, Louis Theran
Date: 2013-02-12 00:00:00
Tasks: compressed sensing, Low-Rank Matrix Completion, Matrix Completion

We give a new, very general, formulation of the compressed sensing problem in
terms of coordinate projections of an analytic variety, and derive sufficient
sampling rates for signal reconstruction. Our bounds are linear in the
coherence of the signal space, a geometric parameter independent of the
specific signal and measurement, and logarithmic in the ambient dimension where
the signal is presented. We exemplify our approach by deriving sufficient
sampling densities for low-rank matrix completion and distance matrix
completion which are independent of the true matrix.
Multivariate Generalized Gaussian Process Models
Authors: Antoni B. Chan
Date: 2013-11-02 00:00:00
Tasks: regression

We propose a family of multivariate Gaussian process models for correlated
outputs, based on assuming that the likelihood function takes the generic form
of the multivariate exponential family distribution (EFD). We denote this model
as a multivariate generalized Gaussian process model, and derive Taylor and
Laplace algorithms for approximate inference on the generic model. By
instantiating the EFD with specific parameter functions, we obtain two novel GP
models (and corresponding inference algorithms) for correlated outputs: 1) a
Von-Mises GP for angle regression; and 2) a Dirichlet GP for regressing on the
multinomial simplex.
Spatio-temporal variation of conversational utterances on Twitter
Authors: Christian M. Alis, May T. Lim
Date: 2013-10-09 00:00:00

Conversations reflect the existing norms of a language. Previously, we found
that utterance lengths in English fictional conversations in books and movies
have shortened over a period of 200 years. In this work, we show that this
shortening occurs even for a brief period of 3 years (September 2009-December
2012) using 229 million utterances from Twitter. Furthermore, the subset of
geographically-tagged tweets from the United States show an inverse proportion
between utterance lengths and the state-level percentage of the Black
population. We argue that shortening of utterances can be explained by the
increasing usage of jargon including coined words.
Contextualizing concepts using a mathematical generalization of the quantum formalism
Authors: Liane Gabora, Diederik Aerts
Date: 2013-10-29 00:00:00

We outline the rationale and preliminary results of using the state context
property (SCOP) formalism, originally developed as a generalization of quantum
mechanics, to describe the contextual manner in which concepts are evoked, used
and combined to generate meaning. The quantum formalism was developed to cope
with problems arising in the description of (i) the measurement process, and
(ii) the generation of new states with new properties when particles become
entangled. Similar problems arising with concepts motivated the formal
treatment introduced here. Concepts are viewed not as fixed representations,
but entities existing in states of potentiality that require interaction with a
context-a stimulus or another concept-to 'collapse' to an instantiated form
(e.g. exemplar, prototype, or other possibly imaginary instance). The stimulus
situation plays the role of the measurement in physics, acting as context that
induces a change of the cognitive state from superposition state to collapsed
state. The collapsed state is more likely to consist of a conjunction of
concepts for associative than analytic thought because more stimulus or concept
properties take part in the collapse. We provide two contextual measures of
conceptual distance-one using collapse probabilities and the other weighted
properties-and show how they can be applied to conjunctions using the pet fish
problem.
Parsimonious Shifted Asymmetric Laplace Mixtures
Authors: Brian C. Franczak, Paul D. McNicholas, Ryan P. Browne, Paula M. Murray
Date: 2013-11-01 00:00:00
Tasks: Clustering, General Classification, Model Selection, parameter estimation

A family of parsimonious shifted asymmetric Laplace mixture models is
introduced. We extend the mixture of factor analyzers model to the shifted
asymmetric Laplace distribution. Imposing constraints on the constitute parts
of the resulting decomposed component scale matrices leads to a family of
parsimonious models. An explicit two-stage parameter estimation procedure is
described, and the Bayesian information criterion and the integrated completed
likelihood are compared for model selection. This novel family of models is
applied to real data, where it is compared to its Gaussian analogue within
clustering and classification paradigms.
Nearly Optimal Sample Size in Hypothesis Testing for High-Dimensional Regression
Authors: Adel Javanmard, Andrea Montanari
Date: 2013-11-01 00:00:00
Tasks: regression, Two-sample testing, Vocal Bursts Intensity Prediction

We consider the problem of fitting the parameters of a high-dimensional
linear regression model. In the regime where the number of parameters $p$ is
comparable to or exceeds the sample size $n$, a successful approach uses an
$\ell_1$-penalized least squares estimator, known as Lasso. Unfortunately,
unlike for linear estimators (e.g., ordinary least squares), no
well-established method exists to compute confidence intervals or p-values on
the basis of the Lasso estimator. Very recently, a line of work
\cite{javanmard2013hypothesis, confidenceJM, GBR-hypothesis} has addressed this
problem by constructing a debiased version of the Lasso estimator. In this
paper, we study this approach for random design model, under the assumption
that a good estimator exists for the precision matrix of the design. Our
analysis improves over the state of the art in that it establishes nearly
optimal \emph{average} testing power if the sample size $n$ asymptotically
dominates $s_0 (\log p)^2$, with $s_0$ being the sparsity level (number of
non-zero coefficients). Earlier work obtains provable guarantees only for much
larger sample size, namely it requires $n$ to asymptotically dominate $(s_0
\log p)^2$.
  In particular, for random designs with a sparse precision matrix we show that
an estimator thereof having the required properties can be computed
efficiently. Finally, we evaluate this approach on synthetic data and compare
it with earlier proposals.
Dynamic Clustering via Asymptotics of the Dependent Dirichlet Process Mixture
Authors: Trevor Campbell, Miao Liu, Brian Kulis, Jonathan P. How, Lawrence Carin
Date: 2013-05-28 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Clustering

This paper presents a novel algorithm, based upon the dependent Dirichlet
process mixture model (DDPMM), for clustering batch-sequential data containing
an unknown number of evolving clusters. The algorithm is derived via a
low-variance asymptotic analysis of the Gibbs sampling algorithm for the DDPMM,
and provides a hard clustering with convergence guarantees similar to those of
the k-means algorithm. Empirical results from a synthetic test with moving
Gaussian clusters and a test with real ADS-B aircraft trajectory data
demonstrate that the algorithm requires orders of magnitude less computational
time than contemporary probabilistic and hard clustering algorithms, while
providing higher accuracy on the examined datasets.
Dropout Training as Adaptive Regularization
Authors: Stefan Wager, Sida Wang, Percy Liang
Date: 2013-07-04 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Document Classification

Dropout and other feature noising schemes control overfitting by artificially
corrupting the training data. For generalized linear models, dropout performs a
form of adaptive regularization. Using this viewpoint, we show that the dropout
regularizer is first-order equivalent to an L2 regularizer applied after
scaling the features by an estimate of the inverse diagonal Fisher information
matrix. We also establish a connection to AdaGrad, an online learning
algorithm, and find that a close relative of AdaGrad operates by repeatedly
solving linear dropout-regularized problems. By casting dropout as
regularization, we develop a natural semi-supervised algorithm that uses
unlabeled data to create a better adaptive regularizer. We apply this idea to
document classification tasks, and show that it consistently boosts the
performance of dropout training, improving on state-of-the-art results on the
IMDB reviews dataset.
Convergence Properties of Kronecker Graphical Lasso Algorithms
Authors: Theodoros Tsiligkaridis, Alfred O. Hero III, Shuheng Zhou
Date: 2012-04-03 00:00:00
Tasks: Imputation, Model Selection

This paper studies iteration convergence of Kronecker graphical lasso
(KGLasso) algorithms for estimating the covariance of an i.i.d. Gaussian random
sample under a sparse Kronecker-product covariance model and MSE convergence
rates. The KGlasso model, originally called the transposable regularized
covariance model by Allen ["Transposable regularized covariance models with an
application to missing data imputation," Ann. Appl. Statist., vol. 4, no. 2,
pp. 764-790, 2010], implements a pair of $\ell_1$ penalties on each Kronecker
factor to enforce sparsity in the covariance estimator. The KGlasso algorithm
generalizes Glasso, introduced by Yuan and Lin ["Model selection and estimation
in the Gaussian graphical model," Biometrika, vol. 94, pp. 19-35, 2007] and
Banerjee ["Model selection through sparse maximum likelihood estimation for
multivariate Gaussian or binary data," J. Mach. Learn. Res., vol. 9, pp.
485-516, Mar. 2008], to estimate covariances having Kronecker product form. It
also generalizes the unpenalized ML flip-flop (FF) algorithm of Dutilleul ["The
MLE algorithm for the matrix normal distribution," J. Statist. Comput. Simul.,
vol. 64, pp. 105-123, 1999] and Werner ["On estimation of covariance matrices
with Kronecker product structure," IEEE Trans. Signal Process., vol. 56, no. 2,
pp. 478-491, Feb. 2008] to estimation of sparse Kronecker factors. We establish
that the KGlasso iterates converge pointwise to a local maximum of the
penalized likelihood function. We derive high dimensional rates of convergence
to the true covariance as both the number of samples and the number of
variables go to infinity. Our results establish that KGlasso has significantly
faster asymptotic convergence than Glasso and FF. Simulations are presented
that validate the results of our analysis.
Reinforcement Learning for Matrix Computations: PageRank as an Example
Authors: Vivek S. Borkar, Adwaitvedant S. Mathkar
Date: 2013-11-01 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Reinforcement learning has gained wide popularity as a technique for
simulation-driven approximate dynamic programming. A less known aspect is that
the very reasons that make it effective in dynamic programming can also be
leveraged for using it for distributed schemes for certain matrix computations
involving non-negative matrices. In this spirit, we propose a reinforcement
learning algorithm for PageRank computation that is fashioned after analogous
schemes for approximate dynamic programming. The algorithm has the advantage of
ease of distributed implementation and more importantly, of being model-free,
i.e., not dependent on any specific assumptions about the transition
probabilities in the random web-surfer model. We analyze its convergence and
finite time behavior and present some supporting numerical experiments.
Iterative Bilateral Filtering of Polarimetric SAR Data
Authors: Olivier D'Hondt, Stéphane Guillaso, Olaf Hellwich
Date: 2013-11-01 00:00:00

In this paper, we introduce an iterative speckle filtering method for
polarimetric SAR (PolSAR) images based on the bilateral filter. To locally
adapt to the spatial structure of images, this filter relies on pixel
similarities in both spatial and radiometric domains. To deal with polarimetric
data, we study the use of similarities based on a statistical distance called
Kullback-Leibler divergence as well as two geodesic distances on Riemannian
manifolds. To cope with speckle, we propose to progressively refine the result
thanks to an iterative scheme. Experiments are run over synthetic and
experimental data. First, simulations are generated to study the effects of
filtering parameters in terms of polarimetric reconstruction error, edge
preservation and smoothing of homogeneous areas. Comparison with other methods
shows that our approach compares well to other state of the art methods in the
extraction of polarimetric information and shows superior performance for edge
restoration and noise smoothing. The filter is then applied to experimental
data sets from ESAR and FSAR sensors (DLR) at L-band and S-band, respectively.
These last experiments show the ability of the filter to restore structures
such as buildings and roads and to preserve boundaries between regions while
achieving a high amount of smoothing in homogeneous areas.
Reconstruction of Complex-Valued Fractional Brownian Motion Fields Based on Compressive Sampling and Its Application to PSF Interpolation in Weak Lensing Survey
Authors: Andriyan B. Suksmono
Date: 2013-11-01 00:00:00

A new reconstruction method of complex-valued fractional Brownian motion
(CV-fBm) field based on Compressive Sampling (CS) is proposed. The decay
property of Fourier coefficients magnitude of the fBm signals/ fields indicates
that fBms are compressible. Therefore, a few numbers of samples will be
sufficient for a CS based method to reconstruct the full field. The
effectiveness of the proposed method is showed by simulating, random sampling,
and reconstructing CV-fBm fields. Performance evaluation shows advantages of
the proposed method over boxcar filtering and thin plate methods. It is also
found that the reconstruction performance depends on both of the fBm's Hurst
parameter and the number of samples, which in fact is consistent with the CS
reconstruction theory. In contrast to other fBm or fractal interpolation
methods, the proposed CS based method does not require the knowledge of fractal
parameters in the reconstruction process; the inherent sparsity is just
sufficient for the CS to do the reconstruction. Potential applicability of the
proposed method in weak gravitational lensing survey, particularly for
interpolating non-smooth PSF (Point Spread Function) distribution representing
distortion by a turbulent field is also discussed.