pwc-archive/papers-with-abstracts huggingface dataset:
A Theoretical Analysis of NDCG Type Ranking Measures
Authors: Yining Wang, Li-Wei Wang, Yuanzhi Li, Di He, Tie-Yan Liu, Wei Chen
Date: 2013-04-24 00:00:00
Tasks: Vocal Bursts Type Prediction

A central problem in ranking is to design a ranking measure for evaluation of
ranking functions. In this paper we study, from a theoretical perspective, the
widely used Normalized Discounted Cumulative Gain (NDCG)-type ranking measures.
Although there are extensive empirical studies of NDCG, little is known about
its theoretical properties. We first show that, whatever the ranking function
is, the standard NDCG which adopts a logarithmic discount, converges to 1 as
the number of items to rank goes to infinity. On the first sight, this result
is very surprising. It seems to imply that NDCG cannot differentiate good and
bad ranking functions, contradicting to the empirical success of NDCG in many
applications. In order to have a deeper understanding of ranking measures in
general, we propose a notion referred to as consistent distinguishability. This
notion captures the intuition that a ranking measure should have such a
property: For every pair of substantially different ranking functions, the
ranking measure can decide which one is better in a consistent manner on almost
all datasets. We show that NDCG with logarithmic discount has consistent
distinguishability although it converges to the same limit for all ranking
functions. We next characterize the set of all feasible discount functions for
NDCG according to the concept of consistent distinguishability. Specifically we
show that whether NDCG has consistent distinguishability depends on how fast
the discount decays, and 1/r is a critical point. We then turn to the cut-off
version of NDCG, i.e., NDCG@k. We analyze the distinguishability of NDCG@k for
various choices of k and the discount functions. Experimental results on real
Web search datasets agree well with the theory.
The K-modes algorithm for clustering
Authors: Miguel Á. Carreira-Perpiñán, Weiran Wang
Date: 2013-04-24 00:00:00
Tasks: Clustering, valid

Many clustering algorithms exist that estimate a cluster centroid, such as
K-means, K-medoids or mean-shift, but no algorithm seems to exist that clusters
data by returning exactly K meaningful modes. We propose a natural definition
of a K-modes objective function by combining the notions of density and cluster
assignment. The algorithm becomes K-means and K-medoids in the limit of very
large and very small scales. Computationally, it is slightly slower than
K-means but much faster than mean-shift or K-medoids. Unlike K-means, it is
able to find centroids that are valid patterns, truly representative of a
cluster, even with nonconvex clusters, and appears robust to outliers and
misspecification of the scale and number of clusters.
Solving Support Vector Machines in Reproducing Kernel Banach Spaces with Positive Definite Functions
Authors: Gregory E. Fasshauer, Fred J. Hickernell, Qi Ye
Date: 2012-09-06 00:00:00

In this paper we solve support vector machines in reproducing kernel Banach
spaces with reproducing kernels defined on nonsymmetric domains instead of the
traditional methods in reproducing kernel Hilbert spaces. Using the
orthogonality of semi-inner-products, we can obtain the explicit
representations of the dual (normalized-duality-mapping) elements of support
vector machine solutions. In addition, we can introduce the reproduction
property in a generalized native space by Fourier transform techniques such
that it becomes a reproducing kernel Banach space, which can be even embedded
into Sobolev spaces, and its reproducing kernel is set up by the related
positive definite function. The representations of the optimal solutions of
support vector machines (regularized empirical risks) in these reproducing
kernel Banach spaces are formulated explicitly in terms of positive definite
functions, and their finite numbers of coefficients can be computed by fixed
point iteration. We also give some typical examples of reproducing kernel
Banach spaces induced by Mat\'ern functions (Sobolev splines) so that their
support vector machine solutions are well computable as the classical
algorithms. Moreover, each of their reproducing bases includes information from
multiple training data points. The concept of reproducing kernel Banach spaces
offers us a new numerical tool for solving support vector machines.
Verification of Inconsistency-Aware Knowledge and Action Bases (Extended Version)
Authors: Diego Calvanese, Evgeny Kharlamov, Marco Montali, Ario Santoso, Dmitriy Zheleznyakov
Date: 2013-04-23 00:00:00

Description Logic Knowledge and Action Bases (KABs) have been recently
introduced as a mechanism that provides a semantically rich representation of
the information on the domain of interest in terms of a DL KB and a set of
actions to change such information over time, possibly introducing new objects.
In this setting, decidability of verification of sophisticated temporal
properties over KABs, expressed in a variant of first-order mu-calculus, has
been shown. However, the established framework treats inconsistency in a
simplistic way, by rejecting inconsistent states produced through action
execution. We address this problem by showing how inconsistency handling based
on the notion of repairs can be integrated into KABs, resorting to
inconsistency-tolerant semantics. In this setting, we establish decidability
and complexity of verification.
On Semantic Word Cloud Representation
Authors: Lukas Barth, Stephen Kobourov, Sergey Pupyrev, Torsten Ueckerdt
Date: 2013-04-23 00:00:00

We study the problem of computing semantic-preserving word clouds in which
semantically related words are close to each other. While several heuristic
approaches have been described in the literature, we formalize the underlying
geometric algorithm problem: Word Rectangle Adjacency Contact (WRAC). In this
model each word is associated with rectangle with fixed dimensions, and the
goal is to represent semantically related words by ensuring that the two
corresponding rectangles touch. We design and analyze efficient polynomial-time
algorithms for some variants of the WRAC problem, show that several general
variants are NP-hard, and describe a number of approximation algorithms.
Finally, we experimentally demonstrate that our theoretically-sound algorithms
outperform the early heuristics.
Semi-Optimal Edge Detector based on Simple Standard Deviation with Adjusted Thresholding
Authors: Firas A. Jassim
Date: 2013-04-23 00:00:00
Tasks: Denoising

This paper proposes a novel method which combines both median filter and
simple standard deviation to accomplish an excellent edge detector for image
processing. First of all, a denoising process must be applied on the grey scale
image using median filter to identify pixels which are likely to be
contaminated by noise. The benefit of this step is to smooth the image and get
rid of the noisy pixels. After that, the simple statistical standard deviation
could be computed for each 2X2 window size. If the value of the standard
deviation inside the 2X2 window size is greater than a predefined threshold,
then the upper left pixel in the 2?2 window represents an edge. The visual
differences between the proposed edge detector and the standard known edge
detectors have been shown to support the contribution in this paper.
Structured Reachability Analysis for Markov Decision Processes
Authors: Craig Boutilier, Ronen I. Brafman, Christopher W. Geib
Date: 2013-01-30 00:00:00

Recent research in decision theoretic planning has focussed on making the
solution of Markov decision processes (MDPs) more feasible. We develop a family
of algorithms for structured reachability analysis of MDPs that are suitable
when an initial state (or set of states) is known. Using compact, structured
representations of MDPs (e.g., Bayesian networks), our methods, which vary in
the tradeoff between complexity and accuracy, produce structured descriptions
of (estimated) reachable states that can be used to eliminate variables or
variable values from the problem description, reducing the size of the MDP and
making it easier to solve. One contribution of our work is the extension of
ideas from GRAPHPLAN to deal with the distributed nature of action
representations typically embodied within Bayes nets and the problem of
correlated action effects. We also demonstrate that our algorithm can be made
more complete by using k-ary constraints instead of binary constraints. Another
contribution is the illustration of how the compact representation of
reachability constraints can be exploited by several existing (exact and
approximate) abstraction algorithms for MDPs.
Similarity of Polygonal Curves in the Presence of Outliers
Authors: Jean-Lou De Carufel, Amin Gheibi, Anil Maheshwari, Jörg-Rüdiger Sack, Christian Scheffer
Date: 2012-12-07 00:00:00

The Fr\'{e}chet distance is a well studied and commonly used measure to
capture the similarity of polygonal curves. Unfortunately, it exhibits a high
sensitivity to the presence of outliers. Since the presence of outliers is a
frequently occurring phenomenon in practice, a robust variant of Fr\'{e}chet
distance is required which absorbs outliers. We study such a variant here. In
this modified variant, our objective is to minimize the length of subcurves of
two polygonal curves that need to be ignored (MinEx problem), or alternately,
maximize the length of subcurves that are preserved (MaxIn problem), to achieve
a given Fr\'{e}chet distance. An exact solution to one problem would imply an
exact solution to the other problem. However, we show that these problems are
not solvable by radicals over $\mathbb{Q}$ and that the degree of the
polynomial equations involved is unbounded in general. This motivates the
search for approximate solutions. We present an algorithm, which approximates,
for a given input parameter $\delta$, optimal solutions for the \MinEx\ and
\MaxIn\ problems up to an additive approximation error $\delta$ times the
length of the input curves. The resulting running time is upper bounded by
$\mathcal{O} \left(\frac{n^3}{\delta} \log \left(\frac{n}{\delta}
\right)\right)$, where $n$ is the complexity of the input polygonal curves.
Learning Visual Symbols for Parsing Human Poses in Images
Authors: Fang Wang, Yi Li
Date: 2013-04-23 00:00:00

Parsing human poses in images is fundamental in extracting critical visual
information for artificial intelligent agents. Our goal is to learn
self-contained body part representations from images, which we call visual
symbols, and their symbol-wise geometric contexts in this parsing process. Each
symbol is individually learned by categorizing visual features leveraged by
geometric information. In the categorization, we use Latent Support Vector
Machine followed by an efficient cross validation procedure to learn visual
symbols. Then, these symbols naturally define geometric contexts of body parts
in a fine granularity. When the structure of the compositional parts is a tree,
we derive an efficient approach to estimating human poses in images.
Experiments on two large datasets suggest our approach outperforms state of the
art methods.
On Identifying Significant Edges in Graphical Models of Molecular Networks
Authors: Marco Scutari, Radhakrishnan Nagarajan
Date: 2011-04-05 00:00:00
Tasks: Sensitivity, Specificity

Objective: Modelling the associations from high-throughput experimental
molecular data has provided unprecedented insights into biological pathways and
signalling mechanisms. Graphical models and networks have especially proven to
be useful abstractions in this regard. Ad-hoc thresholds are often used in
conjunction with structure learning algorithms to determine significant
associations. The present study overcomes this limitation by proposing a
statistically-motivated approach for identifying significant associations in a
network.
  Methods and Materials: A new method that identifies significant associations
in graphical models by estimating the threshold minimising the $L_{\mathrm{1}}$
norm between the cumulative distribution function (CDF) of the observed edge
confidences and those of its asymptotic counterpart is proposed. The
effectiveness of the proposed method is demonstrated on popular synthetic data
sets as well as publicly available experimental molecular data corresponding to
gene and protein expression profiles.
  Results: The improved performance of the proposed approach is demonstrated
across the synthetic data sets using sensitivity, specificity and accuracy as
performance metrics. The results are also demonstrated across varying sample
sizes and three different structure learning algorithms with widely varying
assumptions. In all cases, the proposed approach has specificity and accuracy
close to 1, while sensitivity increases linearly in the logarithm of the sample
size. The estimated threshold systematically outperforms common ad-hoc ones in
terms of sensitivity while maintaining comparable levels of specificity and
accuracy. Networks from experimental data sets are reconstructed accurately
with respect to the results from the original papers.
Counting people from above: Airborne video based crowd analysis
Authors: Roland Perko, Thomas Schnabel, Gerald Fritz, Alexander Almer, Lucas Paletta
Date: 2013-04-23 00:00:00
Tasks: object-detection, Object Detection, Optical Flow Estimation

Crowd monitoring and analysis in mass events are highly important
technologies to support the security of attending persons. Proposed methods
based on terrestrial or airborne image/video data often fail in achieving
sufficiently accurate results to guarantee a robust service. We present a novel
framework for estimating human count, density and motion from video data based
on custom tailored object detection techniques, a regression based density
estimate and a total variation based optical flow extraction. From the gathered
features we present a detailed accuracy analysis versus ground truth
measurements. In addition, all information is projected into world coordinates
to enable a direct integration with existing geo-information systems. The
resulting human counts demonstrate a mean error of 4% to 9% and thus represent
a most efficient measure that can be robustly applied in security critical
services.
Dew Point modelling using GEP based multi objective optimization
Authors: Siddharth Shroff, Vipul Dabhi
Date: 2013-04-20 00:00:00

Different techniques are used to model the relationship between temperatures,
dew point and relative humidity. Gene expression programming is capable of
modelling complex realities with great accuracy, allowing at the same time, the
extraction of knowledge from the evolved models compared to other learning
algorithms. We aim to use Gene Expression Programming for modelling of dew
point. Generally, accuracy of the model is the only objective used by selection
mechanism of GEP. This will evolve large size models with low training error.
To avoid this situation, use of multiple objectives, like accuracy and size of
the model are preferred by Genetic Programming practitioners. Solution to a
multi-objective problem is a set of solutions which satisfies the objectives
given by decision maker. Multi objective based GEP will be used to evolve
simple models. Various algorithms widely used for multi objective optimization,
like NSGA II and SPEA 2, are tested on different test problems. The results
obtained thereafter gives idea that SPEA 2 is better than NSGA II based on the
features like execution time, number of solutions obtained and convergence
rate. We selected SPEA 2 for dew point prediction. The multi-objective base GEP
produces accurate and simpler (smaller) solutions compared to solutions
produced by plain GEP for dew point predictions. Thus multi objective base GEP
produces better solutions by considering the dual objectives of fitness and
size of the solution. These simple models can be used to predict future values
of dew point.
Bayesian crack detection in ultra high resolution multimodal images of paintings
Authors: Bruno Cornelis, Yun Yang, Joshua T. Vogelstein, Ann Dooms, Ingrid Daubechies, David Dunson
Date: 2013-04-22 00:00:00
Tasks: Vocal Bursts Intensity Prediction

The preservation of our cultural heritage is of paramount importance. Thanks
to recent developments in digital acquisition techniques, powerful image
analysis algorithms are developed which can be useful non-invasive tools to
assist in the restoration and preservation of art. In this paper we propose a
semi-supervised crack detection method that can be used for high-dimensional
acquisitions of paintings coming from different modalities. Our dataset
consists of a recently acquired collection of images of the Ghent Altarpiece
(1432), one of Northern Europe's most important art masterpieces. Our goal is
to build a classifier that is able to discern crack pixels from the background
consisting of non-crack pixels, making optimal use of the information that is
provided by each modality. To accomplish this we employ a recently developed
non-parametric Bayesian classifier, that uses tensor factorizations to
characterize any conditional probability. A prior is placed on the parameters
of the factorization such that every possible interaction between predictors is
allowed while still identifying a sparse subset among these predictors. The
proposed Bayesian classifier, which we will refer to as conditional Bayesian
tensor factorization or CBTF, is assessed by visually comparing classification
results with the Random Forest (RF) algorithm.
Factorized Topic Models
Authors: Cheng Zhang, Carl Henrik Ek, Andreas Damianou, Hedvig Kjellstrom
Date: 2013-01-15 00:00:00
Tasks: General Classification, Topic Models, Video Classification

In this paper we present a modification to a latent topic model, which makes
the model exploit supervision to produce a factorized representation of the
observed data. The structured parameterization separately encodes variance that
is shared between classes from variance that is private to each class by the
introduction of a new prior over the topic space. The approach allows for a
more eff{}icient inference and provides an intuitive interpretation of the data
in terms of an informative signal together with structured noise. The
factorized representation is shown to enhance inference performance for image,
text, and video classification.
A Bag of Visual Words Approach for Symbols-Based Coarse-Grained Ancient Coin Classification
Authors: Hafeez Anwar, Sebastian Zambanini, Martin Kampel
Date: 2013-04-23 00:00:00
Tasks: General Classification, Scene Recognition

The field of Numismatics provides the names and descriptions of the symbols
minted on the ancient coins. Classification of the ancient coins aims at
assigning a given coin to its issuer. Various issuers used various symbols for
their coins. We propose to use these symbols for a framework that will coarsely
classify the ancient coins. Bag of visual words (BoVWs) is a well established
visual recognition technique applied to various problems in computer vision
like object and scene recognition. Improvements have been made by incorporating
the spatial information to this technique. We apply the BoVWs technique to our
problem and use three symbols for coarse-grained classification. We use
rectangular tiling, log-polar tiling and circular tiling to incorporate spatial
information to BoVWs. Experimental results show that the circular tiling proves
superior to the rest of the methods for our problem.
A Social Welfare Optimal Sequential Allocation Procedure
Authors: Thomas Kalinowski, Nina Nardoytska, Toby Walsh
Date: 2013-04-22 00:00:00

We consider a simple sequential allocation procedure for sharing indivisible
items between agents in which agents take turns to pick items. Supposing
additive utilities and independence between the agents, we show that the
expected utility of each agent is computable in polynomial time. Using this
result, we prove that the expected utilitarian social welfare is maximized when
agents take alternate turns. We also argue that this mechanism remains optimal
when agents behave strategically
The varifold representation of non-oriented shapes for diffeomorphic registration
Authors: Nicolas Charon, Alain Trouvé
Date: 2013-04-22 00:00:00
Tasks: Anatomy

In this paper, we address the problem of orientation that naturally arises
when representing shapes like curves or surfaces as currents. In the field of
computational anatomy, the framework of currents has indeed proved very
efficient to model a wide variety of shapes. However, in such approaches,
orientation of shapes is a fundamental issue that can lead to several drawbacks
in treating certain kind of datasets. More specifically, problems occur with
structures like acute pikes because of canceling effects of currents or with
data that consists in many disconnected pieces like fiber bundles for which
currents require a consistent orientation of all pieces. As a promising
alternative to currents, varifolds, introduced in the context of geometric
measure theory by F. Almgren, allow the representation of any non-oriented
manifold (more generally any non-oriented rectifiable set). In particular, we
explain how varifolds can encode numerically non-oriented objects both from the
discrete and continuous point of view. We show various ways to build a Hilbert
space structure on the set of varifolds based on the theory of reproducing
kernels. We show that, unlike the currents' setting, these metrics are
consistent with shape volume (theorem 4.1) and we derive a formula for the
variation of metric with respect to the shape (theorem 4.2). Finally, we
propose a generalization to non-oriented shapes of registration algorithms in
the context of Large Deformations Metric Mapping (LDDMM), which we detail with
a few examples in the last part of the paper.
Stochastic Variational Inference
Authors: Matt Hoffman, David M. Blei, Chong Wang, John Paisley
Date: 2012-06-29 00:00:00
Tasks: Articles, Topic Models, Variational Inference

We develop stochastic variational inference, a scalable algorithm for
approximating posterior distributions. We develop this technique for a large
class of probabilistic models and we demonstrate it with two probabilistic
topic models, latent Dirichlet allocation and the hierarchical Dirichlet
process topic model. Using stochastic variational inference, we analyze several
large collections of documents: 300K articles from Nature, 1.8M articles from
The New York Times, and 3.8M articles from Wikipedia. Stochastic inference can
easily handle data sets of this size and outperforms traditional variational
inference, which can only handle a smaller subset. (We also show that the
Bayesian nonparametric topic model outperforms its parametric counterpart.)
Stochastic variational inference lets us apply complex Bayesian models to
massive data sets.
Cost-Sensitive Tree of Classifiers
Authors: Zhixiang Xu, Matt J. Kusner, Kilian Q. Weinberger, Minmin Chen
Date: 2012-10-09 00:00:00
Tasks: CPU

Recently, machine learning algorithms have successfully entered large-scale
real-world industrial applications (e.g. search engines and email spam
filters). Here, the CPU cost during test time must be budgeted and accounted
for. In this paper, we address the challenge of balancing the test-time cost
and the classifier accuracy in a principled fashion. The test-time cost of a
classifier is often dominated by the computation required for feature
extraction-which can vary drastically across eatures. We decrease this
extraction time by constructing a tree of classifiers, through which test
inputs traverse along individual paths. Each path extracts different features
and is optimized for a specific sub-partition of the input space. By only
computing features for inputs that benefit from them the most, our cost
sensitive tree of classifiers can match the high accuracies of the current
state-of-the-art at a small fraction of the computational cost.