pwc-archive/papers-with-abstracts huggingface dataset:
Labeled Directed Acyclic Graphs: a generalization of context-specific independence in directed graphical models
Authors: Johan Pensar, Henrik Nyman, Timo Koski, Jukka Corander
Date: 2013-10-04 00:00:00

We introduce a novel class of labeled directed acyclic graph (LDAG) models
for finite sets of discrete variables. LDAGs generalize earlier proposals for
allowing local structures in the conditional probability distribution of a
node, such that unrestricted label sets determine which edges can be deleted
from the underlying directed acyclic graph (DAG) for a given context. Several
properties of these models are derived, including a generalization of the
concept of Markov equivalence classes. Efficient Bayesian learning of LDAGs is
enabled by introducing an LDAG-based factorization of the Dirichlet prior for
the model parameters, such that the marginal likelihood can be calculated
analytically. In addition, we develop a novel prior distribution for the model
structures that can appropriately penalize a model for its labeling complexity.
A non-reversible Markov chain Monte Carlo algorithm combined with a greedy hill
climbing approach is used for illustrating the useful properties of LDAG models
for both real and synthetic data sets.
Spectral Clustering with Epidemic Diffusion
Authors: Laura M. Smith, Kristina Lerman, Cristina Garcia-Cardona, Allon G. Percus, Rumi Ghosh
Date: 2013-03-11 00:00:00
Tasks: Clustering

Spectral clustering is widely used to partition graphs into distinct modules
or communities. Existing methods for spectral clustering use the eigenvalues
and eigenvectors of the graph Laplacian, an operator that is closely associated
with random walks on graphs. We propose a new spectral partitioning method that
exploits the properties of epidemic diffusion. An epidemic is a dynamic process
that, unlike the random walk, simultaneously transitions to all the neighbors
of a given node. We show that the replicator, an operator describing epidemic
diffusion, is equivalent to the symmetric normalized Laplacian of a reweighted
graph with edges reweighted by the eigenvector centralities of their incident
nodes. Thus, more weight is given to edges connecting more central nodes. We
describe a method that partitions the nodes based on the componentwise ratio of
the replicator's second eigenvector to the first, and compare its performance
to traditional spectral clustering techniques on synthetic graphs with known
community structure. We demonstrate that the replicator gives preference to
dense, clique-like structures, enabling it to more effectively discover
communities that may be obscured by dense intercommunity linking.
GOTCHA Password Hackers!
Authors: Jeremiah Blocki, Manuel Blum, Anupam Datta
Date: 2013-10-04 00:00:00

We introduce GOTCHAs (Generating panOptic Turing Tests to Tell Computers and
Humans Apart) as a way of preventing automated offline dictionary attacks
against user selected passwords. A GOTCHA is a randomized puzzle generation
protocol, which involves interaction between a computer and a human.
Informally, a GOTCHA should satisfy two key properties: (1) The puzzles are
easy for the human to solve. (2) The puzzles are hard for a computer to solve
even if it has the random bits used by the computer to generate the final
puzzle --- unlike a CAPTCHA. Our main theorem demonstrates that GOTCHAs can be
used to mitigate the threat of offline dictionary attacks against passwords by
ensuring that a password cracker must receive constant feedback from a human
being while mounting an attack. Finally, we provide a candidate construction of
GOTCHAs based on Inkblot images. Our construction relies on the usability
assumption that users can recognize the phrases that they originally used to
describe each Inkblot image --- a much weaker usability assumption than
previous password systems based on Inkblots which required users to recall
their phrase exactly. We conduct a user study to evaluate the usability of our
GOTCHA construction. We also generate a GOTCHA challenge where we encourage
artificial intelligence and security researchers to try to crack several
passwords protected with our scheme.
Spatio-temporal wavelet regularization for parallel MRI reconstruction: application to functional MRI
Authors: Lotfi Chaari, Sébastien Mériaux, Jean-Christophe Pesquet, Philippe Ciuciu
Date: 2011-12-23 00:00:00
Tasks: Image Reconstruction, MRI Reconstruction

Parallel MRI is a fast imaging technique that enables the acquisition of
highly resolved images in space or/and in time. The performance of parallel
imaging strongly depends on the reconstruction algorithm, which can proceed
either in the original k-space (GRAPPA, SMASH) or in the image domain
(SENSE-like methods). To improve the performance of the widely used SENSE
algorithm, 2D- or slice-specific regularization in the wavelet domain has been
deeply investigated. In this paper, we extend this approach using 3D-wavelet
representations in order to handle all slices together and address
reconstruction artifacts which propagate across adjacent slices. The gain
induced by such extension (3D-Unconstrained Wavelet Regularized -SENSE:
3D-UWR-SENSE) is validated on anatomical image reconstruction where no temporal
acquisition is considered. Another important extension accounts for temporal
correlations that exist between successive scans in functional MRI (fMRI). In
addition to the case of 2D+t acquisition schemes addressed by some other
methods like kt-FOCUSS, our approach allows us to deal with 3D+t acquisition
schemes which are widely used in neuroimaging. The resulting 3D-UWR-SENSE and
4D-UWR-SENSE reconstruction schemes are fully unsupervised in the sense that
all regularization parameters are estimated in the maximum likelihood sense on
a reference scan. The gain induced by such extensions is illustrated on both
anatomical and functional image reconstruction, and also measured in terms of
statistical sensitivity for the 4D-UWR-SENSE approach during a fast
event-related fMRI protocol. Our 4D-UWR-SENSE algorithm outperforms the SENSE
reconstruction at the subject and group levels (15 subjects) for different
contrasts of interest (eg, motor or computation tasks) and using different
parallel acceleration factors (R=2 and R=4) on 2x2x3mm3 EPI images.
Compressed Counting Meets Compressed Sensing
Authors: Ping Li, Cun-Hui Zhang, Tong Zhang
Date: 2013-10-03 00:00:00
Tasks: compressed sensing

Compressed sensing (sparse signal recovery) has been a popular and important
research topic in recent years. By observing that natural signals are often
nonnegative, we propose a new framework for nonnegative signal recovery using
Compressed Counting (CC). CC is a technique built on maximally-skewed p-stable
random projections originally developed for data stream computations. Our
recovery procedure is computationally very efficient in that it requires only
one linear scan of the coordinates. Our analysis demonstrates that, when
0<p<=0.5, it suffices to use M= O(C/eps^p log N) measurements so that all
coordinates will be recovered within eps additive precision, in one scan of the
coordinates. The constant C=1 when p->0 and C=pi/2 when p=0.5. In particular,
when p->0 the required number of measurements is essentially M=K\log N, where K
is the number of nonzero coordinates of the signal.
Machine Teaching for Bayesian Learners in the Exponential Family
Authors: Xiaojin Zhu
Date: 2013-06-20 00:00:00
Proceeding: NeurIPS 2013

What if there is a teacher who knows the learning goal and wants to design
good training data for a machine learner? We propose an optimal teaching
framework aimed at learners who employ Bayesian models. Our framework is
expressed as an optimization problem over teaching examples that balance the
future loss of the learner and the effort of the teacher. This optimization
problem is in general hard. In the case where the learner employs conjugate
exponential family models, we present an approximate algorithm for finding the
optimal teaching set. Our algorithm optimizes the aggregate sufficient
statistics, then unpacks them into actual teaching examples. We give several
examples to illustrate our framework.
Multivariate regression and fit function uncertainty
Authors: Peter Kovesarki, Ian C. Brock
Date: 2013-10-03 00:00:00
Tasks: regression

This article describes a multivariate polynomial regression method where the
uncertainty of the input parameters are approximated with Gaussian
distributions, derived from the central limit theorem for large weighted sums,
directly from the training sample. The estimated uncertainties can be
propagated into the optimal fit function, as an alternative to the statistical
bootstrap method. This uncertainty can be propagated further into a loss
function like quantity, with which it is possible to calculate the expected
loss function, and allows to select the optimal polynomial degree with
statistical significance. Combined with simple phase space splitting methods,
it is possible to model most features of the training data even with low degree
polynomials or constants.
Cross-Recurrence Quantification Analysis of Categorical and Continuous Time Series: an R package
Authors: Moreno I. Coco, Rick Dale
Date: 2013-10-01 00:00:00
Tasks: Computational Efficiency, Time Series, Time Series Analysis

This paper describes the R package crqa to perform cross-recurrence
quantification analysis of two time series of either a categorical or
continuous nature. Streams of behavioral information, from eye movements to
linguistic elements, unfold over time. When two people interact, such as in
conversation, they often adapt to each other, leading these behavioral levels
to exhibit recurrent states. In dialogue, for example, interlocutors adapt to
each other by exchanging interactive cues: smiles, nods, gestures, choice of
words, and so on. In order for us to capture closely the goings-on of dynamic
interaction, and uncover the extent of coupling between two individuals, we
need to quantify how much recurrence is taking place at these levels. Methods
available in crqa would allow researchers in cognitive science to pose such
questions as how much are two people recurrent at some level of analysis, what
is the characteristic lag time for one person to maximally match another, or
whether one person is leading another. First, we set the theoretical ground to
understand the difference between 'correlation' and 'co-visitation' when
comparing two time series, using an aggregative or cross-recurrence approach.
Then, we describe more formally the principles of cross-recurrence, and show
with the current package how to carry out analyses applying them. We end the
paper by comparing computational efficiency, and results' consistency, of crqa
R package, with the benchmark MATLAB toolbox crptoolbox. We show perfect
comparability between the two libraries on both levels.
Developments in the theory of randomized shortest paths with a comparison of graph node distances
Authors: Ilkka Kivimäki, Masashi Shimbo, Marco Saerens
Date: 2012-12-07 00:00:00
Tasks: Clustering, Node Clustering

There have lately been several suggestions for parametrized distances on a
graph that generalize the shortest path distance and the commute time or
resistance distance. The need for developing such distances has risen from the
observation that the above-mentioned common distances in many situations fail
to take into account the global structure of the graph. In this article, we
develop the theory of one family of graph node distances, known as the
randomized shortest path dissimilarity, which has its foundation in statistical
physics. We show that the randomized shortest path dissimilarity can be easily
computed in closed form for all pairs of nodes of a graph. Moreover, we come up
with a new definition of a distance measure that we call the free energy
distance. The free energy distance can be seen as an upgrade of the randomized
shortest path dissimilarity as it defines a metric, in addition to which it
satisfies the graph-geodetic property. The derivation and computation of the
free energy distance are also straightforward. We then make a comparison
between a set of generalized distances that interpolate between the shortest
path distance and the commute time, or resistance distance. This comparison
focuses on the applicability of the distances in graph node clustering and
classification. The comparison, in general, shows that the parametrized
distances perform well in the tasks. In particular, we see that the results
obtained with the free energy distance are among the best in all the
experiments.
Learning Chordal Markov Networks by Constraint Satisfaction
Authors: Jukka Corander, Tomi Janhunen, Jussi Rintanen, Henrik Nyman, Johan Pensar
Date: 2013-10-03 00:00:00
Proceeding: NeurIPS 2013 12

We investigate the problem of learning the structure of a Markov network from
data. It is shown that the structure of such networks can be described in terms
of constraints which enables the use of existing solver technology with
optimization capabilities to compute optimal networks starting from initial
scores computed from the data. To achieve efficient encodings, we develop a
novel characterization of Markov network structure using a balancing condition
on the separators between cliques forming the network. The resulting
translations into propositional satisfiability and its extensions such as
maximum satisfiability, satisfiability modulo theories, and answer set
programming, enable us to prove optimal certain network structures which have
been previously found by stochastic search.
Efficient pedestrian detection by directly optimize the partial area under the ROC curve
Authors: Sakrapee Paisitkriangkrai, Chunhua Shen, Anton Van Den Hengel
Date: 2013-10-03 00:00:00
Tasks: Ensemble Learning, object-detection, Object Detection, Pedestrian Detection

Many typical applications of object detection operate within a prescribed
false-positive range. In this situation the performance of a detector should be
assessed on the basis of the area under the ROC curve over that range, rather
than over the full curve, as the performance outside the range is irrelevant.
  This measure is labelled as the partial area under the ROC curve (pAUC).
Effective cascade-based classification, for example, depends on training node
classifiers that achieve the maximal detection rate at a moderate false
positive rate, e.g., around 40% to 50%. We propose a novel ensemble learning
method which achieves a maximal detection rate at a user-defined range of false
positive rates by directly optimizing the partial AUC using structured
learning. By optimizing for different ranges of false positive rates, the
proposed method can be used to train either a single strong classifier or a
node classifier forming part of a cascade classifier. Experimental results on
both synthetic and real-world data sets demonstrate the effectiveness of our
approach, and we show that it is possible to train state-of-the-art pedestrian
detectors using the proposed structured ensemble learning method.
Multiple Kernel Learning in the Primal for Multi-modal Alzheimer's Disease Classification
Authors: Fayao Liu, Luping Zhou, Chunhua Shen, Jianping Yin
Date: 2013-10-03 00:00:00
Tasks: General Classification

To achieve effective and efficient detection of Alzheimer's disease (AD),
many machine learning methods have been introduced into this realm. However,
the general case of limited training samples, as well as different feature
representations typically makes this problem challenging. In this work, we
propose a novel multiple kernel learning framework to combine multi-modal
features for AD classification, which is scalable and easy to implement.
Contrary to the usual way of solving the problem in the dual space, we look at
the optimization from a new perspective. By conducting Fourier transform on the
Gaussian kernel, we explicitly compute the mapping function, which leads to a
more straightforward solution of the problem in the primal space. Furthermore,
we impose the mixed $L_{21}$ norm constraint on the kernel weights, known as
the group lasso regularization, to enforce group sparsity among different
feature modalities. This actually acts as a role of feature modality selection,
while at the same time exploiting complementary information among different
kernels. Therefore it is able to extract the most discriminative features for
classification. Experiments on the ADNI data set demonstrate the effectiveness
of the proposed method.
Prior-free and prior-dependent regret bounds for Thompson Sampling
Authors: Sébastien Bubeck, Che-Yu Liu
Date: 2013-04-21 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Thompson Sampling

We consider the stochastic multi-armed bandit problem with a prior
distribution on the reward distributions. We are interested in studying
prior-free and prior-dependent regret bounds, very much in the same spirit as
the usual distribution-free and distribution-dependent bounds for the
non-Bayesian stochastic bandit. Building on the techniques of Audibert and
Bubeck [2009] and Russo and Roy [2013] we first show that Thompson Sampling
attains an optimal prior-free bound in the sense that for any prior
distribution its Bayesian regret is bounded from above by $14 \sqrt{n K}$. This
result is unimprovable in the sense that there exists a prior distribution such
that any algorithm has a Bayesian regret bounded from below by $\frac{1}{20}
\sqrt{n K}$. We also study the case of priors for the setting of Bubeck et al.
[2013] (where the optimal mean is known as well as a lower bound on the
smallest gap) and we show that in this case the regret of Thompson Sampling is
in fact uniformly bounded over time, thus showing that Thompson Sampling can
greatly take advantage of the nice properties of these priors.
Stemmers for Tamil Language: Performance Analysis
Authors: M. Thangarasu, R. Manavalan
Date: 2013-10-02 00:00:00
Tasks: Information Retrieval, Retrieval

Stemming is the process of extracting root word from the given inflection
word and also plays significant role in numerous application of Natural
Language Processing (NLP). Tamil Language raises several challenges to NLP,
since it has rich morphological patterns than other languages. The rule based
approach light-stemmer is proposed in this paper, to find stem word for given
inflection Tamil word. The performance of proposed approach is compared to a
rule based suffix removal stemmer based on correctly and incorrectly predicted.
The experimental result clearly show that the proposed approach light stemmer
for Tamil language perform better than suffix removal stemmer and also more
effective in Information Retrieval System (IRS).
Using the Random Sprays Retinex Algorithm for Global Illumination Estimation
Authors: Nikola Banić, Sven Lončarić
Date: 2013-10-01 00:00:00
Tasks: Color Constancy

In this paper the use of Random Sprays Retinex (RSR) algorithm for global
illumination estimation is proposed and its feasibility tested. Like other
algorithms based on the Retinex model, RSR also provides local illumination
estimation and brightness adjustment for each pixel and it is faster than other
path-wise Retinex algorithms. As the assumption of the uniform illumination
holds in many cases, it should be possible to use the mean of local
illumination estimations of RSR as a global illumination estimation for images
with (assumed) uniform illumination allowing also the accuracy to be easily
measured. Therefore we propose a method for estimating global illumination
estimation based on local RSR results. To our best knowledge this is the first
time that RSR algorithm is used to obtain global illumination estimation. For
our tests we use a publicly available color constancy image database for
testing. The results are presented and discussed and it turns out that the
proposed method outperforms many existing unsupervised color constancy
algorithms. The source code is available at
http://www.fer.unizg.hr/ipg/resources/color_constancy/.
Boundary identification of events in clinical named entity recognition
Authors: Azad Dehghan
Date: 2013-08-05 00:00:00
Tasks: General Classification, named-entity-recognition, Named Entity Recognition, Named Entity Recognition (NER)

The problem of named entity recognition in the medical/clinical domain has
gained increasing attention do to its vital role in a wide range of clinical
decision support applications. The identification of complete and correct term
span is vital for further knowledge synthesis (e.g., coding/mapping concepts
thesauruses and classification standards). This paper investigates boundary
adjustment by sequence labeling representations models and post-processing
techniques in the problem of clinical named entity recognition (recognition of
clinical events). Using current state-of-the-art sequence labeling algorithm
(conditional random fields), we show experimentally that sequence labeling
representation and post-processing can be significantly helpful in strict
boundary identification of clinical events.
Iterated Variable Neighborhood Search for the resource constrained multi-mode multi-project scheduling problem
Authors: Martin Josef Geiger
Date: 2013-10-02 00:00:00
Tasks: Combinatorial Optimization, Scheduling

The resource constrained multi-mode multi-project scheduling problem
(RCMMMPSP) is a notoriously difficult combinatorial optimization problem. For a
given set of activities, feasible execution mode assignments and execution
starting times must be found such that some optimization function, e.g. the
makespan, is optimized. When determining an optimal (or at least feasible)
assignment of decision variable values, a set of side constraints, such as
resource availabilities, precedence constraints, etc., has to be respected.
  In 2013, the MISTA 2013 Challenge stipulated research in the RCMMMPSP. It's
goal was the solution of a given set of instances under running time
restrictions. We have contributed to this challenge with the here presented
approach.
Rule Based Stemmer in Urdu
Authors: Vaishali Gupta, Nisheeth Joshi, Iti Mathur
Date: 2013-10-02 00:00:00
Tasks: Information Retrieval, Retrieval

Urdu is a combination of several languages like Arabic, Hindi, English,
Turkish, Sanskrit etc. It has a complex and rich morphology. This is the reason
why not much work has been done in Urdu language processing. Stemming is used
to convert a word into its respective root form. In stemming, we separate the
suffix and prefix from the word. It is useful in search engines, natural
language processing and word processing, spell checkers, word parsing, word
frequency and count studies. This paper presents a rule based stemmer for Urdu.
The stemmer that we have discussed here is used in information retrieval. We
have also evaluated our results by verifying it with a human expert.
Subjective and Objective Evaluation of English to Urdu Machine Translation
Authors: Vaishali Gupta, Nisheeth Joshi, Iti Mathur
Date: 2013-10-02 00:00:00
Tasks: Machine Translation, Translation

Machine translation is research based area where evaluation is very important
phenomenon for checking the quality of MT output. The work is based on the
evaluation of English to Urdu Machine translation. In this research work we
have evaluated the translation quality of Urdu language which has been
translated by using different Machine Translation systems like Google, Babylon
and Ijunoon. The evaluation process is done by using two approaches - Human
evaluation and Automatic evaluation. We have worked for both the approaches
where in human evaluation emphasis is given to scales and parameters while in
automatic evaluation emphasis is given to some automatic metric such as BLEU,
GTM, METEOR and ATEC.