pwc-archive/papers-with-abstracts huggingface dataset:
Traversing News with Ant Colony Optimisation and Negative Pheromones
Authors: David M. S. Rodrigues, Vitorino Ramos
Date: 2014-05-24 00:00:00

The past decade has seen the rapid development of the online newsroom. News
published online are the main outlet of news surpassing traditional printed
newspapers. This poses challenges to the production and to the consumption of
those news. With those many sources of information available it is important to
find ways to cluster and organise the documents if one wants to understand this
new system. A novel bio inspired approach to the problem of traversing the news
is presented. It finds Hamiltonian cycles over documents published by the
newspaper The Guardian. A Second Order Swarm Intelligence algorithm based on
Ant Colony Optimisation was developed that uses a negative pheromone to mark
unrewarding paths with a "no-entry" signal. This approach follows recent
findings of negative pheromone usage in real ants.
Improvements and Experiments of a Compact Statistical Background Model
Authors: Dong Liang, Shun'ichi Kaneko
Date: 2014-05-24 00:00:00
Tasks: Change Detection

Change detection plays an important role in most video-based applications.
The first stage is to build appropriate background model, which is now becoming
increasingly complex as more sophisticated statistical approaches are
introduced to cover challenging situations and provide reliable detection. This
paper reports a simple and intuitive statistical model based on deeper learning
spatial correlation among pixels: For each observed pixel, we select a group of
supporting pixels with high correlation, and then use a single Gaussian to
model the intensity deviations between the observed pixel and the supporting
ones. In addition, a multi-channel model updating is integrated on-line and a
temporal intensity constraint for each pixel is defined. Although this method
is mainly designed for coping with sudden illumination changes, experimental
results using all the video sequences provided on changedetection.net validate
it is comparable with other recent methods under various situations.
Geometric Polynomial Constraints in Higher-Order Graph Matching
Authors: Mayank Bansal, Kostas Daniilidis
Date: 2014-05-24 00:00:00
Tasks: Graph Matching

Correspondence is a ubiquitous problem in computer vision and graph matching
has been a natural way to formalize correspondence as an optimization problem.
Recently, graph matching solvers have included higher-order terms representing
affinities beyond the unary and pairwise level. Such higher-order terms have a
particular appeal for geometric constraints that include three or more
correspondences like the PnP 2D-3D pose problems. In this paper, we address the
problem of finding correspondences in the absence of unary or pairwise
constraints as it emerges in problems where unary appearance similarity like
SIFT matches is not available. Current higher order matching approaches have
targeted problems where higher order affinity can simply be formulated as a
difference of invariances such as lengths, angles, or cross-ratios. In this
paper, we present a method of how to apply geometric constraints modeled as
polynomial equation systems. As opposed to RANSAC where such systems have to be
solved and then tested for inlier hypotheses, our constraints are derived as a
single affinity weight based on $n>2$ hypothesized correspondences without
solving the polynomial system. Since the result is directly a correspondence
without a transformation model, our approach supports correspondence matching
in the presence of multiple geometric transforms like articulated motions.
Deep Generative Stochastic Networks Trainable by Backprop
Authors: Yoshua Bengio, Éric Thibodeau-Laufer, Guillaume Alain, Jason Yosinski
Date: 2013-06-05 00:00:00

We introduce a novel training principle for probabilistic models that is an
alternative to maximum likelihood. The proposed Generative Stochastic Networks
(GSN) framework is based on learning the transition operator of a Markov chain
whose stationary distribution estimates the data distribution. The transition
distribution of the Markov chain is conditional on the previous state,
generally involving a small move, so this conditional distribution has fewer
dominant modes, being unimodal in the limit of small moves. Thus, it is easier
to learn because it is easier to approximate its partition function, more like
learning to perform supervised function approximation, with gradients that can
be obtained by backprop. We provide theorems that generalize recent work on the
probabilistic interpretation of denoising autoencoders and obtain along the way
an interesting justification for dependency networks and generalized
pseudolikelihood, along with a definition of an appropriate joint distribution
and sampling mechanism even when the conditionals are not consistent. GSNs can
be used with missing inputs and can be used to sample subsets of variables
given the rest. We validate these theoretical results with experiments on two
image datasets using an architecture that mimics the Deep Boltzmann Machine
Gibbs sampler but allows training to proceed with simple backprop, without the
need for layerwise pretraining.
Connection graph Laplacian methods can be made robust to noise
Authors: Noureddine El Karoui, Hau-Tieng Wu
Date: 2014-05-23 00:00:00

Recently, several data analytic techniques based on connection graph
laplacian (CGL) ideas have appeared in the literature. At this point, the
properties of these methods are starting to be understood in the setting where
the data is observed without noise. We study the impact of additive noise on
these methods, and show that they are remarkably robust. As a by-product of our
analysis, we propose modifications of the standard algorithms that increase
their robustness to noise. We illustrate our results in numerical simulations.
Convex Banding of the Covariance Matrix
Authors: Jacob Bien, Florentina Bunea, Luo Xiao
Date: 2014-05-23 00:00:00

We introduce a new sparse estimator of the covariance matrix for
high-dimensional models in which the variables have a known ordering. Our
estimator, which is the solution to a convex optimization problem, is
equivalently expressed as an estimator which tapers the sample covariance
matrix by a Toeplitz, sparsely-banded, data-adaptive matrix. As a result of
this adaptivity, the convex banding estimator enjoys theoretical optimality
properties not attained by previous banding or tapered estimators. In
particular, our convex banding estimator is minimax rate adaptive in Frobenius
and operator norms, up to log factors, over commonly-studied classes of
covariance matrices, and over more general classes. Furthermore, it correctly
recovers the bandwidth when the true covariance is exactly banded. Our convex
formulation admits a simple and efficient algorithm. Empirical studies
demonstrate its practical effectiveness and illustrate that our exactly-banded
estimator works well even when the true covariance matrix is only close to a
banded matrix, confirming our theoretical results. Our method compares
favorably with all existing methods, in terms of accuracy and speed. We
illustrate the practical merits of the convex banding estimator by showing that
it can be used to improve the performance of discriminant analysis for
classifying sound recordings.
Evaluating the fully automatic multi-language translation of the Swiss avalanche bulletin
Authors: Kurt Winkler, Tobias Kuhn, Martin Volk
Date: 2014-05-23 00:00:00
Tasks: Translation

The Swiss avalanche bulletin is produced twice a day in four languages. Due
to the lack of time available for manual translation, a fully automated
translation system is employed, based on a catalogue of predefined phrases and
predetermined rules of how these phrases can be combined to produce sentences.
The system is able to automatically translate such sentences from German into
the target languages French, Italian and English without subsequent
proofreading or correction. Our catalogue of phrases is limited to a small
sublanguage. The reduction of daily translation costs is expected to offset the
initial development costs within a few years. After being operational for two
winter seasons, we assess here the quality of the produced texts based on an
evaluation where participants rate real danger descriptions from both origins,
the catalogue of phrases versus the manually written and translated texts. With
a mean recognition rate of 55%, users can hardly distinguish between the two
types of texts, and give similar ratings with respect to their language
quality. Overall, the output from the catalogue system can be considered
virtually equivalent to a text written by avalanche forecasters and then
manually translated by professional translators. Furthermore, forecasters
declared that all relevant situations were captured by the system with
sufficient accuracy and within the limited time available.
Online Linear Optimization via Smoothing
Authors: Jacob Abernethy, Chansoo Lee, Abhinav Sinha, Ambuj Tewari
Date: 2014-05-23 00:00:00

We present a new optimization-theoretic approach to analyzing
Follow-the-Leader style algorithms, particularly in the setting where
perturbations are used as a tool for regularization. We show that adding a
strongly convex penalty function to the decision rule and adding stochastic
perturbations to data correspond to deterministic and stochastic smoothing
operations, respectively. We establish an equivalence between "Follow the
Regularized Leader" and "Follow the Perturbed Leader" up to the smoothness
properties. This intuition leads to a new generic analysis framework that
recovers and improves the previous known regret bounds of the class of
algorithms commonly known as Follow the Perturbed Leader.
Building of Networks of Natural Hierarchies of Terms Based on Analysis of Texts Corpora
Authors: Dmitry Lande
Date: 2014-05-23 00:00:00
Tasks: Information Retrieval, Retrieval

The technique of building of networks of hierarchies of terms based on the
analysis of chosen text corpora is offered. The technique is based on the
methodology of horizontal visibility graphs. Constructed and investigated
language network, formed on the basis of electronic preprints arXiv on topics
of information retrieval.
Robust subspace clustering
Authors: Mahdi Soltanolkotabi, Ehsan Elhamifar, Emmanuel J. Candès
Date: 2013-01-11 00:00:00
Tasks: Clustering

Subspace clustering refers to the task of finding a multi-subspace
representation that best fits a collection of points taken from a
high-dimensional space. This paper introduces an algorithm inspired by sparse
subspace clustering (SSC) [In IEEE Conference on Computer Vision and Pattern
Recognition, CVPR (2009) 2790-2797] to cluster noisy data, and develops some
novel theory demonstrating its correctness. In particular, the theory uses
ideas from geometric functional analysis to show that the algorithm can
accurately recover the underlying subspaces under minimal requirements on their
orientation, and on the number of samples per subspace. Synthetic as well as
real data experiments complement our theoretical study, illustrating our
approach and demonstrating its effectiveness.
Understanding model counting for $β$-acyclic CNF-formulas
Authors: Johann Brault-Baron, Florent Capelli, Stefan Mengel
Date: 2014-05-23 00:00:00
Tasks: model

We extend the knowledge about so-called structural restrictions of
$\mathrm{\#SAT}$ by giving a polynomial time algorithm for $\beta$-acyclic
$\mathrm{\#SAT}$. In contrast to previous algorithms in the area, our algorithm
does not proceed by dynamic programming but works along an elimination order,
solving a weighted version of constraint satisfaction. Moreover, we give
evidence that this deviation from more standard algorithm is not a coincidence,
but that there is likely no dynamic programming algorithm of the usual style
for $\beta$-acyclic $\mathrm{\#SAT}$.
Large Margin Distribution Machine
Authors: Teng Zhang, Zhi-Hua Zhou
Date: 2013-11-05 00:00:00

Support vector machine (SVM) has been one of the most popular learning
algorithms, with the central idea of maximizing the minimum margin, i.e., the
smallest distance from the instances to the classification boundary. Recent
theoretical results, however, disclosed that maximizing the minimum margin does
not necessarily lead to better generalization performances, and instead, the
margin distribution has been proven to be more crucial. In this paper, we
propose the Large margin Distribution Machine (LDM), which tries to achieve a
better generalization performance by optimizing the margin distribution. We
characterize the margin distribution by the first- and second-order statistics,
i.e., the margin mean and variance. The LDM is a general learning approach
which can be used in any place where SVM can be applied, and its superiority is
verified both theoretically and empirically in this paper.
Gemini: Graph estimation with matrix variate normal instances
Authors: Shuheng Zhou
Date: 2012-09-23 00:00:00

Undirected graphs can be used to describe matrix variate distributions. In
this paper, we develop new methods for estimating the graphical structures and
underlying parameters, namely, the row and column covariance and inverse
covariance matrices from the matrix variate data. Under sparsity conditions, we
show that one is able to recover the graphs and covariance matrices with a
single random matrix from the matrix variate normal distribution. Our method
extends, with suitable adaptation, to the general setting where replicates are
available. We establish consistency and obtain the rates of convergence in the
operator and the Frobenius norm. We show that having replicates will allow one
to estimate more complicated graphical structures and achieve faster rates of
convergence. We provide simulation evidence showing that we can recover
graphical structures as well as estimating the precision matrices, as predicted
by theory.
On the Optimal Solution of Weighted Nuclear Norm Minimization
Authors: Qi Xie, Deyu Meng, Shuhang Gu, Lei Zhang, WangMeng Zuo, Xiangchu Feng, Zongben Xu
Date: 2014-05-23 00:00:00
Tasks: Denoising, Image Denoising

In recent years, the nuclear norm minimization (NNM) problem has been
attracting much attention in computer vision and machine learning. The NNM
problem is capitalized on its convexity and it can be solved efficiently. The
standard nuclear norm regularizes all singular values equally, which is however
not flexible enough to fit real scenarios. Weighted nuclear norm minimization
(WNNM) is a natural extension and generalization of NNM. By assigning properly
different weights to different singular values, WNNM can lead to
state-of-the-art results in applications such as image denoising. Nevertheless,
so far the global optimal solution of WNNM problem is not completely solved yet
due to its non-convexity in general cases. In this article, we study the
theoretical properties of WNNM and prove that WNNM can be equivalently
transformed into a quadratic programming problem with linear constraints. This
implies that WNNM is equivalent to a convex problem and its global optimum can
be readily achieved by off-the-shelf convex optimization solvers. We further
show that when the weights are non-descending, the globally optimal solution of
WNNM can be obtained in closed-form.
LASS: a simple assignment model with Laplacian smoothing
Authors: Miguel Á. Carreira-Perpiñán, Weiran Wang
Date: 2014-05-23 00:00:00
Tasks: model

We consider the problem of learning soft assignments of $N$ items to $K$
categories given two sources of information: an item-category similarity
matrix, which encourages items to be assigned to categories they are similar to
(and to not be assigned to categories they are dissimilar to), and an item-item
similarity matrix, which encourages similar items to have similar assignments.
We propose a simple quadratic programming model that captures this intuition.
We give necessary conditions for its solution to be unique, define an
out-of-sample mapping, and derive a simple, effective training algorithm based
on the alternating direction method of multipliers. The model predicts
reasonable assignments from even a few similarity values, and can be seen as a
generalization of semisupervised learning. It is particularly useful when items
naturally belong to multiple categories, as for example when annotating
documents with keywords or pictures with tags, with partially tagged items, or
when the categories have complex interrelations (e.g. hierarchical) that are
unknown.
Distributed Representations of Sentences and Documents
Authors: Quoc V. Le, Tomas Mikolov
Date: 2014-05-16 00:00:00
Tasks: Question Answering, Sentiment Analysis, Text Classification

Many machine learning algorithms require the input to be represented as a
fixed-length feature vector. When it comes to texts, one of the most common
fixed-length features is bag-of-words. Despite their popularity, bag-of-words
features have two major weaknesses: they lose the ordering of the words and
they also ignore semantics of the words. For example, "powerful," "strong" and
"Paris" are equally distant. In this paper, we propose Paragraph Vector, an
unsupervised algorithm that learns fixed-length feature representations from
variable-length pieces of texts, such as sentences, paragraphs, and documents.
Our algorithm represents each document by a dense vector which is trained to
predict words in the document. Its construction gives our algorithm the
potential to overcome the weaknesses of bag-of-words models. Empirical results
show that Paragraph Vectors outperform bag-of-words models as well as other
techniques for text representations. Finally, we achieve new state-of-the-art
results on several text classification and sentiment analysis tasks.
Computerization of African languages-French dictionaries
Authors: Chantal Enguehard, Mathieu Mangeot
Date: 2014-05-22 00:00:00
Tasks: Management

This paper relates work done during the DiLAF project. It consists in
converting 5 bilingual African language-French dictionaries originally in Word
format into XML following the LMF model. The languages processed are Bambara,
Hausa, Kanuri, Tamajaq and Songhai-zarma, still considered as under-resourced
languages concerning Natural Language Processing tools. Once converted, the
dictionaries are available online on the Jibiki platform for lookup and
modification. The DiLAF project is first presented. A description of each
dictionary follows. Then, the conversion methodology from .doc format to XML
files is presented. A specific point on the usage of Unicode follows. Then,
each step of the conversion into XML and LMF is detailed. The last part
presents the Jibiki lexical resources management platform used for the project.
Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)
Authors: Anshumali Shrivastava, Ping Li
Date: 2014-05-22 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Collaborative Filtering

We present the first provably sublinear time algorithm for approximate
\emph{Maximum Inner Product Search} (MIPS). Our proposal is also the first
hashing algorithm for searching with (un-normalized) inner product as the
underlying similarity measure. Finding hashing schemes for MIPS was considered
hard. We formally show that the existing Locality Sensitive Hashing (LSH)
framework is insufficient for solving MIPS, and then we extend the existing LSH
framework to allow asymmetric hashing schemes. Our proposal is based on an
interesting mathematical phenomenon in which inner products, after independent
asymmetric transformations, can be converted into the problem of approximate
near neighbor search. This key observation makes efficient sublinear hashing
scheme for MIPS possible. In the extended asymmetric LSH (ALSH) framework, we
provide an explicit construction of provably fast hashing scheme for MIPS. The
proposed construction and the extended LSH framework could be of independent
theoretical interest. Our proposed algorithm is simple and easy to implement.
We evaluate the method, for retrieving inner products, in the collaborative
filtering task of item recommendations on Netflix and Movielens datasets.
Node Classification in Uncertain Graphs
Authors: Michele Dallachiesa, Charu Aggarwal, Themis Palpanas
Date: 2014-05-22 00:00:00
Tasks: Classification, General Classification, Node Classification

In many real applications that use and analyze networked data, the links in
the network graph may be erroneous, or derived from probabilistic techniques.
In such cases, the node classification problem can be challenging, since the
unreliability of the links may affect the final results of the classification
process. If the information about link reliability is not used explicitly, the
classification accuracy in the underlying network may be affected adversely. In
this paper, we focus on situations that require the analysis of the uncertainty
that is present in the graph structure. We study the novel problem of node
classification in uncertain graphs, by treating uncertainty as a first-class
citizen. We propose two techniques based on a Bayes model and automatic
parameter selection, and show that the incorporation of uncertainty in the
classification process as a first-class citizen is beneficial. We
experimentally evaluate the proposed approach using different real data sets,
and study the behavior of the algorithms under different conditions. The
results demonstrate the effectiveness and efficiency of our approach.
An Abductive Framework for Horn Knowledge Base Dynamics
Authors: Radhakrishnan Delhibabu
Date: 2014-05-12 00:00:00

The dynamics of belief and knowledge is one of the major components of any
autonomous system that should be able to incorporate new pieces of information.
We introduced the Horn knowledge base dynamics to deal with two important
points: first, to handle belief states that need not be deductively closed; and
the second point is the ability to declare certain parts of the belief as
immutable. In this paper, we address another, radically new approach to this
problem. This approach is very close to the Hansson's dyadic representation of
belief. Here, we consider the immutable part as defining a new logical system.
By a logical system, we mean that it defines its own consequence relation and
closure operator. Based on this, we provide an abductive framework for Horn
knowledge base dynamics.