pwc-archive/papers-with-abstracts huggingface dataset:
Independent Vector Analysis: Identification Conditions and Performance Bounds
Authors: Matthew Anderson, Geng-Shen Fu, Ronald Phlypo, Tülay Adalı
Date: 2013-03-29 00:00:00

Recently, an extension of independent component analysis (ICA) from one to
multiple datasets, termed independent vector analysis (IVA), has been the
subject of significant research interest. IVA has also been shown to be a
generalization of Hotelling's canonical correlation analysis. In this paper, we
provide the identification conditions for a general IVA formulation, which
accounts for linear, nonlinear, and sample-to-sample dependencies. The
identification conditions are a generalization of previous results for ICA and
for IVA when samples are independently and identically distributed.
Furthermore, a principal aim of IVA is the identification of dependent sources
between datasets. Thus, we provide the additional conditions for when the
arbitrary ordering of the sources within each dataset is common. Performance
bounds in terms of the Cramer-Rao lower bound are also provided for the
demixing matrices and interference to source ratio. The performance of two IVA
algorithms are compared to the theoretical bounds.
Agent-based modeling of a price information trading business
Authors: Saad Ahmad Khan, Ladislau Boloni
Date: 2013-03-29 00:00:00

We describe an agent-based simulation of a fictional (but feasible)
information trading business. The Gas Price Information Trader (GPIT) buys
information about real-time gas prices in a metropolitan area from drivers and
resells the information to drivers who need to refuel their vehicles.
  Our simulation uses real world geographic data, lifestyle-dependent driving
patterns and vehicle models to create an agent-based model of the drivers. We
use real world statistics of gas price fluctuation to create scenarios of
temporal and spatial distribution of gas prices. The price of the information
is determined on a case-by-case basis through a simple negotiation model. The
trader and the customers are adapting their negotiation strategies based on
their historical profits.
  We are interested in the general properties of the emerging information
market: the amount of realizable profit and its distribution between the trader
and customers, the business strategies necessary to keep the market operational
(such as promotional deals), the price elasticity of demand and the impact of
pricing strategies on the profit.
Normalized Compression Distance of Multisets with Applications
Authors: Andrew R. Cohen, Paul M. B. Vitanyi
Date: 2012-12-22 00:00:00
Tasks: Classification, General Classification, Handwritten Digit Recognition

Normalized compression distance (NCD) is a parameter-free, feature-free,
alignment-free, similarity measure between a pair of finite objects based on
compression. However, it is not sufficient for all applications. We propose an
NCD of finite multisets (a.k.a. multiples) of finite objects that is also a
metric. Previously, attempts to obtain such an NCD failed. We cover the entire
trajectory from theoretical underpinning to feasible practice. The new NCD for
multisets is applied to retinal progenitor cell classification questions and to
related synthetically generated data that were earlier treated with the
pairwise NCD. With the new method we achieved significantly better results.
Similarly for questions about axonal organelle transport. We also applied the
new NCD to handwritten digit recognition and improved classification accuracy
significantly over that of pairwise NCD by incorporating both the pairwise and
NCD for multisets. In the analysis we use the incomputable Kolmogorov
complexity that for practical purposes is approximated from above by the length
of the compressed version of the file involved, using a real-world compression
program.
  Index Terms--- Normalized compression distance, multisets or multiples,
pattern recognition, data mining, similarity, classification, Kolmogorov
complexity, retinal progenitor cells, synthetic data, organelle transport,
handwritten character recognition
Formalizing the Confluence of Orthogonal Rewriting Systems
Authors: Ana Cristina Rocha Oliveira, Mauricio Ayala-Rincón
Date: 2013-03-29 00:00:00

Orthogonality is a discipline of programming that in a syntactic manner
guarantees determinism of functional specifications. Essentially, orthogonality
avoids, on the one side, the inherent ambiguity of non determinism, prohibiting
the existence of different rules that specify the same function and that may
apply simultaneously (non-ambiguity), and, on the other side, it eliminates the
possibility of occurrence of repetitions of variables in the left-hand side of
these rules (left linearity). In the theory of term rewriting systems (TRSs)
determinism is captured by the well-known property of confluence, that
basically states that whenever different computations or simplifications from a
term are possible, the computed answers should coincide. Although the proofs
are technically elaborated, confluence is well-known to be a consequence of
orthogonality. Thus, orthogonality is an important mathematical discipline
intrinsic to the specification of recursive functions that is naturally applied
in functional programming and specification. Starting from a formalization of
the theory of TRSs in the proof assistant PVS, this work describes how
confluence of orthogonal TRSs has been formalized, based on axiomatizations of
properties of rules, positions and substitutions involved in parallel steps of
reduction, in this proof assistant. Proofs for some similar but restricted
properties such as the property of confluence of non-ambiguous and (left and
right) linear TRSs have been fully formalized.
Symmetries in Modal Logics
Authors: Carlos Areces, Guillaume Hoffmann, Ezequiel Orbe
Date: 2013-03-29 00:00:00

We generalize the notion of symmetries of propositional formulas in
conjunctive normal form to modal formulas. Our framework uses the coinductive
models and, hence, the results apply to a wide class of modal logics including,
for example, hybrid logics. Our main result shows that the symmetries of a
modal formula preserve entailment.
Exploring the Role of Logically Related Non-Question Phrases for Answering Why-Questions
Authors: Niraj Kumar, Rashmi Gangadharaiah, Kannan Srinathan, Vasudeva Varma
Date: 2013-03-29 00:00:00

In this paper, we show that certain phrases although not present in a given
question/query, play a very important role in answering the question. Exploring
the role of such phrases in answering questions not only reduces the dependency
on matching question phrases for extracting answers, but also improves the
quality of the extracted answers. Here matching question phrases means phrases
which co-occur in given question and candidate answers. To achieve the above
discussed goal, we introduce a bigram-based word graph model populated with
semantic and topical relatedness of terms in the given document. Next, we apply
an improved version of ranking with a prior-based approach, which ranks all
words in the candidate document with respect to a set of root words (i.e.
non-stopwords present in the question and in the candidate document). As a
result, terms logically related to the root words are scored higher than terms
that are not related to the root words. Experimental results show that our
devised system performs better than state-of-the-art for the task of answering
Why-questions.
A problem dependent analysis of SOCP algorithms in noisy compressed sensing
Authors: Mihailo Stojnic
Date: 2013-03-29 00:00:00
Tasks: compressed sensing

Under-determined systems of linear equations with sparse solutions have been
the subject of an extensive research in last several years above all due to
results of \cite{CRT,CanRomTao06,DonohoPol}. In this paper we will consider
\emph{noisy} under-determined linear systems. In a breakthrough
\cite{CanRomTao06} it was established that in \emph{noisy} systems for any
linear level of under-determinedness there is a linear sparsity that can be
\emph{approximately} recovered through an SOCP (second order cone programming)
optimization algorithm so that the approximate solution vector is (in an
$\ell_2$-norm sense) guaranteed to be no further from the sparse unknown vector
than a constant times the noise. In our recent work \cite{StojnicGenSocp10} we
established an alternative framework that can be used for statistical
performance analysis of the SOCP algorithms. To demonstrate how the framework
works we then showed in \cite{StojnicGenSocp10} how one can use it to precisely
characterize the \emph{generic} (worst-case) performance of the SOCP. In this
paper we present a different set of results that can be obtained through the
framework of \cite{StojnicGenSocp10}. The results will relate to \emph{problem
dependent} performance analysis of SOCP's. We will consider specific types of
unknown sparse vectors and characterize the SOCP performance when used for
recovery of such vectors. We will also show that our theoretical predictions
are in a solid agreement with the results one can get through numerical
simulations.
Blinking Molecule Tracking
Authors: Andreas Karrenbauer, Dominik Wöll
Date: 2012-12-24 00:00:00

We discuss a method for tracking individual molecules which globally
optimizes the likelihood of the connections between molecule positions fast and
with high reliability even for high spot densities and blinking molecules. Our
method works with cost functions which can be freely chosen to combine costs
for distances between spots in space and time and which can account for the
reliability of positioning a molecule. To this end, we describe a top-down
polyhedral approach to the problem of tracking many individual molecules. This
immediately yields an effective implementation using standard linear
programming solvers. Our method can be applied to 2D and 3D tracking.
Scalable Text and Link Analysis with Mixed-Topic Link Models
Authors: Yaojia Zhu, Xiaoran Yan, Lise Getoor, Cristopher Moore
Date: 2013-03-28 00:00:00
Tasks: Link Prediction, Topic Classification

Many data sets contain rich information about objects, as well as pairwise
relations between them. For instance, in networks of websites, scientific
papers, and other documents, each node has content consisting of a collection
of words, as well as hyperlinks or citations to other nodes. In order to
perform inference on such data sets, and make predictions and recommendations,
it is useful to have models that are able to capture the processes which
generate the text at each node and the links between them. In this paper, we
combine classic ideas in topic modeling with a variant of the mixed-membership
block model recently developed in the statistical physics community. The
resulting model has the advantage that its parameters, including the mixture of
topics of each document and the resulting overlapping communities, can be
inferred with a simple and scalable expectation-maximization algorithm. We test
our model on three data sets, performing unsupervised topic classification and
link prediction. For both tasks, our model outperforms several existing
state-of-the-art methods, achieving higher accuracy with significantly less
computation, analyzing a data set with 1.3 million words and 44 thousand links
in a few minutes.
Advantages and a Limitation of Using LEG Nets in a Real-TIme Problem
Authors: Thomas Slack
Date: 2013-03-28 00:00:00
Tasks: Diagnostic, Form, Medical Diagnosis

After experimenting with a number of non-probabilistic methods for dealing
with uncertainty many researchers reaffirm a preference for probability methods
[1] [2], although this remains controversial. The importance of being able to
form decisions from incomplete data in diagnostic problems has highlighted
probabilistic methods [5] which compute posterior probabilities from prior
distributions in a way similar to Bayes Rule, and thus are called Bayesian
methods. This paper documents the use of a Bayesian method in a real time
problem which is similar to medical diagnosis in that there is a need to form
decisions and take some action without complete knowledge of conditions in the
problem domain. This particular method has a limitation which is discussed.
Detecting Overlapping Temporal Community Structure in Time-Evolving Networks
Authors: Yudong Chen, Vikas Kawadia, Rahul Urgaonkar
Date: 2013-03-28 00:00:00
Tasks: Combinatorial Optimization

We present a principled approach for detecting overlapping temporal community
structure in dynamic networks. Our method is based on the following framework:
find the overlapping temporal community structure that maximizes a quality
function associated with each snapshot of the network subject to a temporal
smoothness constraint. A novel quality function and a smoothness constraint are
proposed to handle overlaps, and a new convex relaxation is used to solve the
resulting combinatorial optimization problem. We provide theoretical guarantees
as well as experimental results that reveal community structure in real and
synthetic networks. Our main insight is that certain structures can be
identified only when temporal correlation is considered and when communities
are allowed to overlap. In general, discovering such overlapping temporal
community structure can enhance our understanding of real-world complex
networks by revealing the underlying stability behind their seemingly chaotic
evolution.
Sparse Projections of Medical Images onto Manifolds
Authors: George H. Chen, Christian Wachinger, Polina Golland
Date: 2013-03-22 00:00:00
Tasks: regression

Manifold learning has been successfully applied to a variety of medical
imaging problems. Its use in real-time applications requires fast projection
onto the low-dimensional space. To this end, out-of-sample extensions are
applied by constructing an interpolation function that maps from the input
space to the low-dimensional manifold. Commonly used approaches such as the
Nystr\"{o}m extension and kernel ridge regression require using all training
points. We propose an interpolation function that only depends on a small
subset of the input training data. Consequently, in the testing phase each new
point only needs to be compared against a small number of input training data
in order to project the point onto the low-dimensional space. We interpret our
method as an out-of-sample extension that approximates kernel ridge regression.
Our method involves solving a simple convex optimization problem and has the
attractive property of guaranteeing an upper bound on the approximation error,
which is crucial for medical applications. Tuning this error bound controls the
sparsity of the resulting interpolation function. We illustrate our method in
two clinical applications that require fast mapping of input images onto a
low-dimensional space.
Design for a Darwinian Brain: Part 2. Cognitive Architecture
Authors: Chrisantha Fernando, Vera Vasas
Date: 2013-03-28 00:00:00
Tasks: Reinforcement Learning, Reinforcement Learning (RL)

The accumulation of adaptations in an open-ended manner during lifetime
learning is a holy grail in reinforcement learning, intrinsic motivation,
artificial curiosity, and developmental robotics. We present a specification
for a cognitive architecture that is capable of specifying an unlimited range
of behaviors. We then give examples of how it can stochastically explore an
interesting space of adjacent possible behaviors. There are two main novelties;
the first is a proper definition of the fitness of self-generated games such
that interesting games are expected to evolve. The second is a modular and
evolvable behavior language that has systematicity, productivity, and
compositionality, i.e. it is a physical symbol system. A part of the
architecture has already been implemented on a humanoid robot.
Design for a Darwinian Brain: Part 1. Philosophy and Neuroscience
Authors: Chrisantha Fernando
Date: 2013-03-28 00:00:00
Tasks: Philosophy

Physical symbol systems are needed for open-ended cognition. A good way to
understand physical symbol systems is by comparison of thought to chemistry.
Both have systematicity, productivity and compositionality. The state of the
art in cognitive architectures for open-ended cognition is critically assessed.
I conclude that a cognitive architecture that evolves symbol structures in the
brain is a promising candidate to explain open-ended cognition. Part 2 of the
paper presents such a cognitive architecture.
Large-Scale Automatic Reconstruction of Neuronal Processes from Electron Microscopy Images
Authors: Verena Kaynig, Amelio Vazquez-Reina, Seymour Knowles-Barley, Mike Roberts, Thouis R. Jones, Narayanan Kasthuri, Eric Miller, Jeff Lichtman, Hanspeter Pfister
Date: 2013-03-28 00:00:00
Tasks: Brain Segmentation, Segmentation

Automated sample preparation and electron microscopy enables acquisition of
very large image data sets. These technical advances are of special importance
to the field of neuroanatomy, as 3D reconstructions of neuronal processes at
the nm scale can provide new insight into the fine grained structure of the
brain. Segmentation of large-scale electron microscopy data is the main
bottleneck in the analysis of these data sets. In this paper we present a
pipeline that provides state-of-the art reconstruction performance while
scaling to data sets in the GB-TB range. First, we train a random forest
classifier on interactive sparse user annotations. The classifier output is
combined with an anisotropic smoothing prior in a Conditional Random Field
framework to generate multiple segmentation hypotheses per image. These
segmentations are then combined into geometrically consistent 3D objects by
segmentation fusion. We provide qualitative and quantitative evaluation of the
automatic segmentation and demonstrate large-scale 3D reconstructions of
neuronal processes from a $\mathbf{27,000}$ $\mathbf{\mu m^3}$ volume of brain
tissue over a cube of $\mathbf{30 \; \mu m}$ in each dimension corresponding to
1000 consecutive image sections. We also introduce Mojo, a proofreading tool
including semi-automated correction of merge errors based on sparse user
scribbles.
Conditional Gradient Algorithms for Norm-Regularized Smooth Convex Optimization
Authors: Zaid Harchaoui, Anatoli Juditsky, Arkadi Nemirovski
Date: 2013-02-10 00:00:00

Motivated by some applications in signal processing and machine learning, we
consider two convex optimization problems where, given a cone $K$, a norm
$\|\cdot\|$ and a smooth convex function $f$, we want either 1) to minimize the
norm over the intersection of the cone and a level set of $f$, or 2) to
minimize over the cone the sum of $f$ and a multiple of the norm. We focus on
the case where (a) the dimension of the problem is too large to allow for
interior point algorithms, (b) $\|\cdot\|$ is "too complicated" to allow for
computationally cheap Bregman projections required in the first-order proximal
gradient algorithms. On the other hand, we assume that {it is relatively easy
to minimize linear forms over the intersection of $K$ and the unit
$\|\cdot\|$-ball}. Motivating examples are given by the nuclear norm with $K$
being the entire space of matrices, or the positive semidefinite cone in the
space of symmetric matrices, and the Total Variation norm on the space of 2D
images. We discuss versions of the Conditional Gradient algorithm capable to
handle our problems of interest, provide the related theoretical efficiency
estimates and outline some applications.
pROST : A Smoothed Lp-norm Robust Online Subspace Tracking Method for Realtime Background Subtraction in Video
Authors: Florian Seidel, Clemens Hage, Martin Kleinsteuber
Date: 2013-02-08 00:00:00

An increasing number of methods for background subtraction use Robust PCA to
identify sparse foreground objects. While many algorithms use the L1-norm as a
convex relaxation of the ideal sparsifying function, we approach the problem
with a smoothed Lp-norm and present pROST, a method for robust online subspace
tracking. The algorithm is based on alternating minimization on manifolds.
Implemented on a graphics processing unit it achieves realtime performance.
Experimental results on a state-of-the-art benchmark for background subtraction
on real-world video data indicate that the method succeeds at a broad variety
of background subtraction scenarios, and it outperforms competing approaches
when video quality is deteriorated by camera jitter.
Discrete Optimization of Statistical Sample Sizes in Simulation by Using the Hierarchical Bootstrap Method
Authors: A. Andronov, M. Fioshin
Date: 2013-03-28 00:00:00

The Bootstrap method application in simulation supposes that value of random
variables are not generated during the simulation process but extracted from
available sample populations. In the case of Hierarchical Bootstrap the
function of interest is calculated recurrently using the calculation tree. In
the present paper we consider the optimization of sample sizes in each vertex
of the calculation tree. The dynamic programming method is used for this aim.
Proposed method allows to decrease a variance of system characteristic
estimators.
Relation-algebraic and Tool-supported Control of Condorcet Voting
Authors: Rudolf Berghammer, Henning Schnoor
Date: 2013-03-28 00:00:00
Tasks: Relation

We present a relation-algebraic model of Condorcet voting and, based on it,
relation-algebraic solutions of the constructive control problem via the
removal of voters.
  We consider two winning conditions, viz. to be a Condorcet winner and to be
in the (Gilles resp. upward) uncovered set. For the first condition the control
problem is known to be NP-hard; for the second condition the NP-hardness of the
control problem is shown in the paper. All relation-algebraic specifications we
will develop in the paper immediately can be translated into the programming
language of the BDD-based computer system RelView. Our approach is very
flexible and especially appropriate for prototyping and experimentation, and as
such very instructive for educational purposes. It can easily be applied to
other voting rules and control problems.
Semantic Matching of Security Policies to Support Security Experts
Authors: Othman Benammar, Hicham Elasri, Abderrahim Sekkaki
Date: 2013-03-28 00:00:00
Tasks: Cloud Computing, Management

Management of security policies has become increasingly difficult given the
number of domains to manage, taken into consideration their extent and their
complexity. Security experts has to deal with a variety of frameworks and
specification languages used in different domains that may belong to any Cloud
Computing or Distributed Systems. This wealth of frameworks and languages make
the management task and the interpretation of the security policies so
difficult. Each approach provides its own conflict management method or tool,
the security expert will be forced to manage all these tools, which makes the
field maintenance and time consuming expensive. In order to hide this
complexity and to facilitate some security experts tasks and automate the
others, we propose a security policies aligning based on ontologies process;
this process enables to detect and resolve security policies conflicts and to
support security experts in managing tasks.