pwc-archive/papers-with-abstracts huggingface dataset:
Sparse Principal Component Analysis via Rotation and Truncation
Authors: Zhenfang Hu, Gang Pan, Yueming Wang, Zhaohui Wu
Date: 2014-03-06 00:00:00

Sparse principal component analysis (sparse PCA) aims at finding a sparse
basis to improve the interpretability over the dense basis of PCA, meanwhile
the sparse basis should cover the data subspace as much as possible. In
contrast to most of existing work which deal with the problem by adding some
sparsity penalties on various objectives of PCA, in this paper, we propose a
new method SPCArt, whose motivation is to find a rotation matrix and a sparse
basis such that the sparse basis approximates the basis of PCA after the
rotation. The algorithm of SPCArt consists of three alternating steps: rotate
PCA basis, truncate small entries, and update the rotation matrix. Its
performance bounds are also given. SPCArt is efficient, with each iteration
scaling linearly with the data dimension. It is easy to choose parameters in
SPCArt, due to its explicit physical explanations. Besides, we give a unified
view to several existing sparse PCA methods and discuss the connection with
SPCArt. Some ideas in SPCArt are extended to GPower, a popular sparse PCA
algorithm, to overcome its drawback. Experimental results demonstrate that
SPCArt achieves the state-of-the-art performance. It also achieves a good
tradeoff among various criteria, including sparsity, explained variance,
orthogonality, balance of sparsity among loadings, and computational speed.
Relative Facial Action Unit Detection
Authors: Mahmoud Khademi, Louis-Philippe Morency
Date: 2014-05-01 00:00:00
Tasks: Action Unit Detection, Facial Action Unit Detection, General Classification

This paper presents a subject-independent facial action unit (AU) detection
method by introducing the concept of relative AU detection, for scenarios where
the neutral face is not provided. We propose a new classification objective
function which analyzes the temporal neighborhood of the current frame to
decide if the expression recently increased, decreased or showed no change.
This approach is a significant change from the conventional absolute method
which decides about AU classification using the current frame, without an
explicit comparison with its neighboring frames. Our proposed method improves
robustness to individual differences such as face scale and shape, age-related
wrinkles, and transitions among expressions (e.g., lower intensity of
expressions). Our experiments on three publicly available datasets (Extended
Cohn-Kanade (CK+), Bosphorus, and DISFA databases) show significant improvement
of our approach over conventional absolute techniques. Keywords: facial action
coding system (FACS); relative facial action unit detection; temporal
information;
Latent Self-Exciting Point Process Model for Spatial-Temporal Networks
Authors: Yoon-Sik Cho, Aram Galstyan, P. Jeffrey Brantingham, George Tita
Date: 2013-02-12 00:00:00

We propose a latent self-exciting point process model that describes
geographically distributed interactions between pairs of entities. In contrast
to most existing approaches that assume fully observable interactions, here we
consider a scenario where certain interaction events lack information about
participants. Instead, this information needs to be inferred from the available
observations. We develop an efficient approximate algorithm based on
variational expectation-maximization to infer unknown participants in an event
given the location and the time of the event. We validate the model on
synthetic as well as real-world data, and obtain very promising results on the
identity-inference task. We also use our model to predict the timing and
participants of future events, and demonstrate that it compares favorably with
baseline approaches.
Piecewise regression mixture for simultaneous functional data clustering and optimal segmentation
Authors: Faicel Chamroukhi
Date: 2013-12-25 00:00:00
Tasks: Classification, Clustering, General Classification, regression, Segmentation

This paper introduces a novel mixture model-based approach for simultaneous
clustering and optimal segmentation of functional data which are curves
presenting regime changes. The proposed model consists in a finite mixture of
piecewise polynomial regression models. Each piecewise polynomial regression
model is associated with a cluster, and within each cluster, each piecewise
polynomial component is associated with a regime (i.e., a segment). We derive
two approaches for learning the model parameters. The former is an estimation
approach and consists in maximizing the observed-data likelihood via a
dedicated expectation-maximization (EM) algorithm. A fuzzy partition of the
curves in K clusters is then obtained at convergence by maximizing the
posterior cluster probabilities. The latter however is a classification
approach and optimizes a specific classification likelihood criterion through a
dedicated classification expectation-maximization (CEM) algorithm. The optimal
curve segmentation is performed by using dynamic programming. In the
classification approach, both the curve clustering and the optimal segmentation
are performed simultaneously as the CEM learning proceeds. We show that the
classification approach is the probabilistic version that generalizes the
deterministic K-means-like algorithm proposed in H\'ebrail et al. (2010). The
proposed approach is evaluated using simulated curves and real-world curves.
Comparisons with alternatives including regression mixture models and the
K-means like algorithm for piecewise regression demonstrate the effectiveness
of the proposed approach.
LTLf and LDLf Monitoring: A Technical Report
Authors: Giuseppe De Giacomo, Riccardo De Masellis, Marco Grasso, Fabrizio Maggi, Marco Montali
Date: 2014-04-30 00:00:00
Tasks: Translation

Runtime monitoring is one of the central tasks to provide operational
decision support to running business processes, and check on-the-fly whether
they comply with constraints and rules. We study runtime monitoring of
properties expressed in LTL on finite traces (LTLf) and in its extension LDLf.
LDLf is a powerful logic that captures all monadic second order logic on finite
traces, which is obtained by combining regular expressions and LTLf, adopting
the syntax of propositional dynamic logic (PDL). Interestingly, in spite of its
greater expressivity, LDLf has exactly the same computational complexity of
LTLf. We show that LDLf is able to capture, in the logic itself, not only the
constraints to be monitored, but also the de-facto standard RV-LTL monitors.
This makes it possible to declaratively capture monitoring metaconstraints, and
check them by relying on usual logical services instead of ad-hoc algorithms.
This, in turn, enables to flexibly monitor constraints depending on the
monitoring state of other constraints, e.g., "compensation" constraints that
are only checked when others are detected to be violated. In addition, we
devise a direct translation of LDLf formulas into nondeterministic automata,
avoiding to detour to Buechi automata or alternating automata, and we use it to
implement a monitoring plug-in for the PROM suite.
Belief Revision and Trust
Authors: Aaron Hunter
Date: 2014-04-30 00:00:00

Belief revision is the process in which an agent incorporates a new piece of
information together with a pre-existing set of beliefs. When the new
information comes in the form of a report from another agent, then it is clear
that we must first determine whether or not that agent should be trusted. In
this paper, we provide a formal approach to modeling trust as a pre-processing
step before belief revision. We emphasize that trust is not simply a relation
between agents; the trust that one agent has in another is often restricted to
a particular domain of expertise. We demonstrate that this form of trust can be
captured by associating a state-partition with each agent, then relativizing
all reports to this state partition before performing belief revision. In this
manner, we incorporate only the part of a report that falls under the perceived
domain of expertise of the reporting agent. Unfortunately, state partitions
based on expertise do not allow us to compare the relative strength of trust
held with respect to different agents. To address this problem, we introduce
pseudometrics over states to represent differing degrees of trust. This allows
us to incorporate simultaneous reports from multiple agents in a way that
ensures the most trusted reports will be believed.
Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraints
Authors: Jie Fu, Ufuk Topcu
Date: 2014-04-28 00:00:00

We consider synthesis of control policies that maximize the probability of
satisfying given temporal logic specifications in unknown, stochastic
environments. We model the interaction between the system and its environment
as a Markov decision process (MDP) with initially unknown transition
probabilities. The solution we develop builds on the so-called model-based
probably approximately correct Markov decision process (PAC-MDP) methodology.
The algorithm attains an $\varepsilon$-approximately optimal policy with
probability $1-\delta$ using samples (i.e. observations), time and space that
grow polynomially with the size of the MDP, the size of the automaton
expressing the temporal logic specification, $\frac{1}{\varepsilon}$,
$\frac{1}{\delta}$ and a finite time horizon. In this approach, the system
maintains a model of the initially unknown MDP, and constructs a product MDP
based on its learned model and the specification automaton that expresses the
temporal logic constraints. During execution, the policy is iteratively updated
using observation of the transitions taken by the system. The iteration
terminates in finitely many steps. With high probability, the resulting policy
is such that, for any state, the difference between the probability of
satisfying the specification under this policy and the optimal one is within a
predefined bound.
Phase transitions in semisupervised clustering of sparse networks
Authors: Pan Zhang, Cristopher Moore, Lenka Zdeborová
Date: 2014-04-30 00:00:00
Tasks: Clustering, Stochastic Block Model

Predicting labels of nodes in a network, such as community memberships or
demographic variables, is an important problem with applications in social and
biological networks. A recently-discovered phase transition puts fundamental
limits on the accuracy of these predictions if we have access only to the
network topology. However, if we know the correct labels of some fraction
$\alpha$ of the nodes, we can do better. We study the phase diagram of this
"semisupervised" learning problem for networks generated by the stochastic
block model. We use the cavity method and the associated belief propagation
algorithm to study what accuracy can be achieved as a function of $\alpha$. For
$k = 2$ groups, we find that the detectability transition disappears for any
$\alpha > 0$, in agreement with previous work. For larger $k$ where a hard but
detectable regime exists, we find that the easy/hard transition (the point at
which efficient algorithms can do better than chance) becomes a line of
transitions where the accuracy jumps discontinuously at a critical value of
$\alpha$. This line ends in a critical point with a second-order transition,
beyond which the accuracy is a continuous function of $\alpha$. We demonstrate
qualitatively similar transitions in two real-world networks.
Pupil: An Open Source Platform for Pervasive Eye Tracking and Mobile Gaze-based Interaction
Authors: Moritz Kassner, William Patera, Andreas Bulling
Date: 2014-04-30 00:00:00
Tasks: Gaze Estimation, Pupil Detection

Commercial head-mounted eye trackers provide useful features to customers in
industry and research but are expensive and rely on closed source hardware and
software. This limits the application areas and use of mobile eye tracking to
expert users and inhibits user-driven development, customisation, and
extension. In this paper we present Pupil -- an accessible, affordable, and
extensible open source platform for mobile eye tracking and gaze-based
interaction. Pupil comprises 1) a light-weight headset with high-resolution
cameras, 2) an open source software framework for mobile eye tracking, as well
as 3) a graphical user interface (GUI) to playback and visualize video and gaze
data. Pupil features high-resolution scene and eye cameras for monocular and
binocular gaze estimation. The software and GUI are platform-independent and
include state-of-the-art algorithms for real-time pupil detection and tracking,
calibration, and accurate gaze estimation. Results of a performance evaluation
show that Pupil can provide an average gaze estimation accuracy of 0.6 degree
of visual angle (0.08 degree precision) with a latency of the processing
pipeline of only 0.045 seconds.
A graph-based mathematical morphology reader
Authors: Laurent Najman, Jean Cousty
Date: 2014-04-30 00:00:00
Tasks: Survey

This survey paper aims at providing a "literary" anthology of mathematical
morphology on graphs. It describes in the English language many ideas stemming
from a large number of different papers, hence providing a unified view of an
active and diverse field of research.
Compact Argumentation Frameworks
Authors: Ringo Baumann, Wolfgang Dvorák, Thomas Linsbichler, Hannes Strass, Stefan Woltran
Date: 2014-04-30 00:00:00
Tasks: Abstract Argumentation, Fairness

Abstract argumentation frameworks (AFs) are one of the most studied
formalisms in AI. In this work, we introduce a certain subclass of AFs which we
call compact. Given an extension-based semantics, the corresponding compact AFs
are characterized by the feature that each argument of the AF occurs in at
least one extension. This not only guarantees a certain notion of fairness;
compact AFs are thus also minimal in the sense that no argument can be removed
without changing the outcome. We address the following questions in the paper:
(1) How are the classes of compact AFs related for different semantics? (2)
Under which circumstances can AFs be transformed into equivalent compact ones?
(3) Finally, we show that compact AFs are indeed a non-trivial subclass, since
the verification problem remains coNP-hard for certain semantics.
An argumentation system for reasoning with conflict-minimal paraconsistent ALC
Authors: Wenzhao Qiao, Nico Roos
Date: 2014-04-30 00:00:00

The semantic web is an open and distributed environment in which it is hard
to guarantee consistency of knowledge and information. Under the standard
two-valued semantics everything is entailed if knowledge and information is
inconsistent. The semantics of the paraconsistent logic LP offers a solution.
However, if the available knowledge and information is consistent, the set of
conclusions entailed under the three-valued semantics of the paraconsistent
logic LP is smaller than the set of conclusions entailed under the two-valued
semantics. Preferring conflict-minimal three-valued interpretations eliminates
this difference.
  Preferring conflict-minimal interpretations introduces non-monotonicity. To
handle the non-monotonicity, this paper proposes an assumption-based
argumentation system. Assumptions needed to close branches of a semantic
tableaux form the arguments. Stable extensions of the set of derived arguments
correspond to conflict minimal interpretations and conclusions entailed by all
conflict-minimal interpretations are supported by arguments in all stable
extensions.
Dimension Reduction via Colour Refinement
Authors: Martin Grohe, Kristian Kersting, Martin Mladenov, Erkal Selman
Date: 2013-07-22 00:00:00
Tasks: Dimensionality Reduction, Isomorphism Testing, Math

Colour refinement is a basic algorithmic routine for graph isomorphism
testing, appearing as a subroutine in almost all practical isomorphism solvers.
It partitions the vertices of a graph into "colour classes" in such a way that
all vertices in the same colour class have the same number of neighbours in
every colour class. Tinhofer (Disc. App. Math., 1991), Ramana, Scheinerman, and
Ullman (Disc. Math., 1994) and Godsil (Lin. Alg. and its App., 1997)
established a tight correspondence between colour refinement and fractional
isomorphisms of graphs, which are solutions to the LP relaxation of a natural
ILP formulation of graph isomorphism.
  We introduce a version of colour refinement for matrices and extend existing
quasilinear algorithms for computing the colour classes. Then we generalise the
correspondence between colour refinement and fractional automorphisms and
develop a theory of fractional automorphisms and isomorphisms of matrices.
  We apply our results to reduce the dimensions of systems of linear equations
and linear programs. Specifically, we show that any given LP L can efficiently
be transformed into a (potentially) smaller LP L' whose number of variables and
constraints is the number of colour classes of the colour refinement algorithm,
applied to a matrix associated with the LP. The transformation is such that we
can easily (by a linear mapping) map both feasible and optimal solutions back
and forth between the two LPs. We demonstrate empirically that colour
refinement can indeed greatly reduce the cost of solving linear programs.
LLAMA: Leveraging Learning to Automatically Manage Algorithms
Authors: Lars Kotthoff
Date: 2013-06-05 00:00:00

Algorithm portfolio and selection approaches have achieved remarkable
improvements over single solvers. However, the implementation of such systems
is often highly customised and specific to the problem domain. This makes it
difficult for researchers to explore different techniques for their specific
problems. We present LLAMA, a modular and extensible toolkit implemented as an
R package that facilitates the exploration of a range of different portfolio
techniques on any problem domain. It implements the algorithm selection
approaches most commonly used in the literature and leverages the extensive
library of machine learning algorithms and techniques in R. We describe the
current capabilities and limitations of the toolkit and illustrate its usage on
a set of example SAT problems.
Proceedings of The 38th Annual Workshop of the Austrian Association for Pattern Recognition (ÖAGM), 2014
Authors: Vladimir Kolmogorov, Christoph Lampert, Emilie Morvant, Rustem Takhanov
Date: 2014-04-14 00:00:00

The 38th Annual Workshop of the Austrian Association for Pattern Recognition
(\"OAGM) will be held at IST Austria, on May 22-23, 2014. The workshop provides
a platform for researchers and industry to discuss traditional and new areas of
computer vision. This year the main topic is: Pattern Recognition:
interdisciplinary challenges and opportunities.
Surprisingly Rational: Probability theory plus noise explains biases in judgment
Authors: Fintan Costello, Paul Watts
Date: 2012-11-01 00:00:00

The systematic biases seen in people's probability judgments are typically
taken as evidence that people do not reason about probability using the rules
of probability theory, but instead use heuristics which sometimes yield
reasonable judgments and sometimes systematic biases. This view has had a major
impact in economics, law, medicine, and other fields; indeed, the idea that
people cannot reason with probabilities has become a widespread truism. We
present a simple alternative to this view, where people reason about
probability according to probability theory but are subject to random variation
or noise in the reasoning process. In this account the effect of noise is
cancelled for some probabilistic expressions: analysing data from two
experiments we find that, for these expressions, people's probability judgments
are strikingly close to those required by probability theory. For other
expressions this account produces systematic deviations in probability
estimates. These deviations explain four reliable biases in human probabilistic
reasoning (conservatism, subadditivity, conjunction and disjunction fallacies).
These results suggest that people's probability judgments embody the rules of
probability theory, and that biases in those judgments are due to the effects
of random noise.
Gabor Filter and Rough Clustering Based Edge Detection
Authors: Chandranath Adak
Date: 2014-04-30 00:00:00
Tasks: Clustering, Edge Detection

This paper introduces an efficient edge detection method based on Gabor
filter and rough clustering. The input image is smoothed by Gabor function, and
the concept of rough clustering is used to focus on edge detection with soft
computational approach. Hysteresis thresholding is used to get the actual
output, i.e. edges of the input image. To show the effectiveness, the proposed
technique is compared with some other edge detection methods.
Selecting a Small Set of Optimal Gestures from an Extensive Lexicon
Authors: Jacob Grosek, J. Nathan Kutz
Date: 2014-04-30 00:00:00

Finding the best set of gestures to use for a given computer recognition problem is an essential part of optimizing the recognition performance while being mindful to those who may articulate the gestures. An objective function, called the ellipsoidal distance ratio metric (EDRM), for determining the best gestures from a larger lexicon library is presented, along with a numerical method for incorporating subjective preferences. In particular, we demonstrate an efficient algorithm that chooses the best $n$ gestures from a lexicon of $m$ gestures where typically $n \ll m$ using a weighting of both subjective and objective measures.
Dynamic Mode Decomposition for Real-Time Background/Foreground Separation in Video
Authors: Jacob Grosek, J. Nathan Kutz
Date: 2014-04-30 00:00:00

This paper introduces the method of dynamic mode decomposition (DMD) for
robustly separating video frames into background (low-rank) and foreground
(sparse) components in real-time. The method is a novel application of a
technique used for characterizing nonlinear dynamical systems in an
equation-free manner by decomposing the state of the system into low-rank terms
whose Fourier components in time are known. DMD terms with Fourier frequencies
near the origin (zero-modes) are interpreted as background (low-rank) portions
of the given video frames, and the terms with Fourier frequencies bounded away
from the origin are their sparse counterparts. An approximate low-rank/sparse
separation is achieved at the computational cost of just one singular value
decomposition and one linear equation solve, thus producing results orders of
magnitude faster than a leading separation method, namely robust principal
component analysis (RPCA). The DMD method that is developed here is
demonstrated to work robustly in real-time with personal laptop-class computing
power and without any parameter tuning, which is a transformative improvement
in performance that is ideal for video surveillance and recognition
applications.