pwc-archive/papers-with-abstracts huggingface dataset:
On the relation between Gaussian process quadratures and sigma-point methods
Authors: Simo Särkkä, Jouni Hartikainen, Lennart Svensson, Fredrik Sandblom
Date: 2015-04-22 00:00:00
Tasks: Numerical Integration, regression, Relation

This article is concerned with Gaussian process quadratures, which are
numerical integration methods based on Gaussian process regression methods, and
sigma-point methods, which are used in advanced non-linear Kalman filtering and
smoothing algorithms. We show that many sigma-point methods can be interpreted
as Gaussian quadrature based methods with suitably selected covariance
functions. We show that this interpretation also extends to more general
multivariate Gauss--Hermite integration methods and related spherical cubature
rules. Additionally, we discuss different criteria for selecting the
sigma-point locations: exactness for multivariate polynomials up to a given
order, minimum average error, and quasi-random point sets. The performance of
the different methods is tested in numerical experiments.
Learning Mixed Membership Community Models in Social Tagging Networks through Tensor Methods
Authors: Anima Anandkumar, Hanie Sedghi
Date: 2015-03-16 00:00:00
Tasks: Community Detection, TAG, Tensor Decomposition

Community detection in graphs has been extensively studied both in theory and
in applications. However, detecting communities in hypergraphs is more
challenging. In this paper, we propose a tensor decomposition approach for
guaranteed learning of communities in a special class of hypergraphs modeling
social tagging systems or folksonomies. A folksonomy is a tripartite 3-uniform
hypergraph consisting of (user, tag, resource) hyperedges. We posit a
probabilistic mixed membership community model, and prove that the tensor
method consistently learns the communities under efficient sample complexity
and separation requirements.
Allocating Indivisible Items in Categorized Domains
Authors: Erika Mackin, Lirong Xia
Date: 2015-04-22 00:00:00

We formulate a general class of allocation problems called categorized domain
allocation problems (CDAPs), where indivisible items from multiple categories
are allocated to agents without monetary transfer and each agent gets at least
one item per category.
  We focus on basic CDAPs, where the number of items in each category is equal
to the number of agents. We characterize serial dictatorships for basic CDAPs
by a minimal set of three axiomatic properties: strategy-proofness,
non-bossiness, and category-wise neutrality. Then, we propose a natural
extension of serial dictatorships called categorial sequential allocation
mechanisms (CSAMs), which allocate the items in multiple rounds: in each round,
the active agent chooses an item from a designated category. We fully
characterize the worst-case rank efficiency of CSAMs for optimistic and
pessimistic agents, and provide a bound for strategic agents. We also conduct
experiments to compare expected rank efficiency of various CSAMs w.r.t. random
generated data.
A review of "Mem-computing NP-complete problems in polynomial time using polynomial resources" (arXiv:1411.4798)
Authors: Igor L. Markov
Date: 2014-11-29 00:00:00

The reviewed paper describes an analog device that empirically solves small
instances of the NP-complete Subset Sum Problem (SSP). The authors claim that
this device can solve the SSP in polynomial time using polynomial space, in
principle, and observe no exponential scaling in resource requirements. We
point out that (a) the properties ascribed by the authors to their device are
insufficient to solve NP-complete problems in poly-time, (b) runtime analysis
offered does not cover the spectral measurement step, (c) the overall technique
requires exponentially increasing resources when scaled up because of the
spectral measurement step.
Robust Vertex Classification
Authors: Li Chen, Cencheng Shen, Joshua Vogelstein, Carey Priebe
Date: 2013-11-23 00:00:00
Tasks: Classification, General Classification, Position

For random graphs distributed according to stochastic blockmodels, a special
case of latent position graphs, adjacency spectral embedding followed by
appropriate vertex classification is asymptotically Bayes optimal; but this
approach requires knowledge of and critically depends on the model dimension.
In this paper, we propose a sparse representation vertex classifier which does
not require information about the model dimension. This classifier represents a
test vertex as a sparse combination of the vertices in the training set and
uses the recovered coefficients to classify the test vertex. We prove
consistency of our proposed classifier for stochastic blockmodels, and
demonstrate that the sparse representation classifier can predict vertex labels
with higher accuracy than adjacency spectral embedding approaches via both
simulation studies and real data experiments. Our results demonstrate the
robustness and effectiveness of our proposed vertex classifier when the model
dimension is unknown.
The Power of Randomization: Distributed Submodular Maximization on Massive Datasets
Authors: Rafael da Ponte Barbosa, Alina Ene, Huy L. Nguyen, Justin Ward
Date: 2015-02-09 00:00:00
Tasks: BIG-bench Machine Learning, Clustering, Document Summarization

A wide variety of problems in machine learning, including exemplar
clustering, document summarization, and sensor placement, can be cast as
constrained submodular maximization problems. Unfortunately, the resulting
submodular optimization problems are often too large to be solved on a single
machine. We develop a simple distributed algorithm that is embarrassingly
parallel and it achieves provable, constant factor, worst-case approximation
guarantees. In our experiments, we demonstrate its efficiency in large problems
with different kinds of constraints with objective values always close to what
is achievable in the centralized setting.
Semantic Enrichment of Mobile Phone Data Records Using Background Knowledge
Authors: Zolzaya Dashdorj, Stanislav Sobolevsky, Luciano Serafini, Fabrizio Antonelli, Carlo Ratti
Date: 2015-04-22 00:00:00

Every day, billions of mobile network events (i.e. CDRs) are generated by
cellular phone operator companies. Latent in this data are inspiring insights
about human actions and behaviors, the discovery of which is important because
context-aware applications and services hold the key to user-driven,
intelligent services, which can enhance our everyday lives such as social and
economic development, urban planning, and health prevention. The major
challenge in this area is that interpreting such a big stream of data requires
a deep understanding of mobile network events' context through available
background knowledge. This article addresses the issues in context awareness
given heterogeneous and uncertain data of mobile network events missing
reliable information on the context of this activity. The contribution of this
research is a model from a combination of logical and statistical reasoning
standpoints for enabling human activity inference in qualitative terms from
open geographical data that aimed at improving the quality of human behaviors
recognition tasks from CDRs. We use open geographical data, Openstreetmap
(OSM), as a proxy for predicting the content of human activity in the area. The
user study performed in Trento shows that predicted human activities (top
level) match the survey data with around 93% overall accuracy. The extensive
validation for predicting a more specific economic type of human activity
performed in Barcelona, by employing credit card transaction data. The analysis
identifies that appropriately normalized data on points of interest (POI) is a
good proxy for predicting human economical activities, with 84% accuracy on
average. So the model is proven to be efficient for predicting the context of
human activity, when its total level could be efficiently observed from cell
phone data records, missing contextual information however.
Convergence results for projected line-search methods on varieties of low-rank matrices via Łojasiewicz inequality
Authors: Reinhold Schneider, André Uschmajew
Date: 2014-02-21 00:00:00
Tasks: Riemannian optimization

The aim of this paper is to derive convergence results for projected
line-search methods on the real-algebraic variety $\mathcal{M}_{\le k}$ of real
$m \times n$ matrices of rank at most $k$. Such methods extend Riemannian
optimization methods, which are successfully used on the smooth manifold
$\mathcal{M}_k$ of rank-$k$ matrices, to its closure by taking steps along
gradient-related directions in the tangent cone, and afterwards projecting back
to $\mathcal{M}_{\le k}$. Considering such a method circumvents the
difficulties which arise from the nonclosedness and the unbounded curvature of
$\mathcal{M}_k$. The pointwise convergence is obtained for real-analytic
functions on the basis of a \L{}ojasiewicz inequality for the projection of the
antigradient to the tangent cone. If the derived limit point lies on the smooth
part of $\mathcal{M}_{\le k}$, i.e. in $\mathcal{M}_k$, this boils down to more
or less known results, but with the benefit that asymptotic convergence rate
estimates (for specific step-sizes) can be obtained without an a priori
curvature bound, simply from the fact that the limit lies on a smooth manifold.
At the same time, one can give a convincing justification for assuming critical
points to lie in $\mathcal{M}_k$: if $X$ is a critical point of $f$ on
$\mathcal{M}_{\le k}$, then either $X$ has rank $k$, or $\nabla f(X) = 0$.
Spectral Norm of Random Kernel Matrices with Applications to Privacy
Authors: Shiva Prasad Kasiviswanathan, Mark Rudelson
Date: 2015-04-22 00:00:00
Tasks: Attribute, regression

Kernel methods are an extremely popular set of techniques used for many
important machine learning and data analysis applications. In addition to
having good practical performances, these methods are supported by a
well-developed theory. Kernel methods use an implicit mapping of the input data
into a high dimensional feature space defined by a kernel function, i.e., a
function returning the inner product between the images of two data points in
the feature space. Central to any kernel method is the kernel matrix, which is
built by evaluating the kernel function on a given sample dataset.
  In this paper, we initiate the study of non-asymptotic spectral theory of
random kernel matrices. These are n x n random matrices whose (i,j)th entry is
obtained by evaluating the kernel function on $x_i$ and $x_j$, where
$x_1,...,x_n$ are a set of n independent random high-dimensional vectors. Our
main contribution is to obtain tight upper bounds on the spectral norm (largest
eigenvalue) of random kernel matrices constructed by commonly used kernel
functions based on polynomials and Gaussian radial basis.
  As an application of these results, we provide lower bounds on the distortion
needed for releasing the coefficients of kernel ridge regression under
attribute privacy, a general privacy notion which captures a large class of
privacy definitions. Kernel ridge regression is standard method for performing
non-parametric regression that regularly outperforms traditional regression
approaches in various domains. Our privacy distortion lower bounds are the
first for any kernel technique, and our analysis assumes realistic scenarios
for the input, unlike all previous lower bounds for other release problems
which only hold under very restrictive input settings.
Learning of Behavior Trees for Autonomous Agents
Authors: Michele Colledanchise, Ramviyas Parasuraman, Petter Ögren
Date: 2015-04-22 00:00:00
Tasks: valid

Definition of an accurate system model for Automated Planner (AP) is often
impractical, especially for real-world problems. Conversely, off-the-shelf
planners fail to scale up and are domain dependent. These drawbacks are
inherited from conventional transition systems such as Finite State Machines
(FSMs) that describes the action-plan execution generated by the AP. On the
other hand, Behavior Trees (BTs) represent a valid alternative to FSMs
presenting many advantages in terms of modularity, reactiveness, scalability
and domain-independence. In this paper, we propose a model-free AP framework
using Genetic Programming (GP) to derive an optimal BT for an autonomous agent
to achieve a given goal in unknown (but fully observable) environments. We
illustrate the proposed framework using experiments conducted with an open
source benchmark Mario AI for automated generation of BTs that can play the
game character Mario to complete a certain level at various levels of
difficulty to include enemies and obstacles.
LOAD: Local Orientation Adaptive Descriptor for Texture and Material Classification
Authors: Xianbiao Qi, Guoying Zhao, Linlin Shen, Qingquan Li, Matti Pietikainen
Date: 2015-04-22 00:00:00
Tasks: General Classification, Material Classification, Material Recognition, Texture Classification

In this paper, we propose a novel local feature, called Local Orientation
Adaptive Descriptor (LOAD), to capture regional texture in an image. In LOAD,
we proposed to define point description on an Adaptive Coordinate System (ACS),
adopt a binary sequence descriptor to capture relationships between one point
and its neighbors and use multi-scale strategy to enhance the discriminative
power of the descriptor. The proposed LOAD enjoys not only discriminative power
to capture the texture information, but also has strong robustness to
illumination variation and image rotation. Extensive experiments on benchmark
data sets of texture classification and real-world material recognition show
that the proposed LOAD yields the state-of-the-art performance. It is worth to
mention that we achieve a 65.4\% classification accuracy-- which is, to the
best of our knowledge, the highest record by far --on Flickr Material Database
by using a single feature. Moreover, by combining LOAD with the feature
extracted by Convolutional Neural Networks (CNN), we obtain significantly
better performance than both the LOAD and CNN. This result confirms that the
LOAD is complementary to the learning-based features.
Rounding Methods for Neural Networks with Low Resolution Synaptic Weights
Authors: Lorenz K. Muller, Giacomo Indiveri
Date: 2015-04-22 00:00:00

Neural network algorithms simulated on standard computing platforms typically
make use of high resolution weights, with floating-point notation. However, for
dedicated hardware implementations of such algorithms, fixed-point synaptic
weights with low resolution are preferable. The basic approach of reducing the
resolution of the weights in these algorithms by standard rounding methods
incurs drastic losses in performance. To reduce the resolution further, in the
extreme case even to binary weights, more advanced techniques are necessary. To
this end, we propose two methods for mapping neural network algorithms with
high resolution weights to corresponding algorithms that work with low
resolution weights and demonstrate that their performance is substantially
better than standard rounding. We further use these methods to investigate the
performance of three common neural network algorithms under fixed memory size
of the weight matrix with different weight resolutions. We show that dedicated
hardware systems, whose technology dictates very low weight resolutions (be
they electronic or biological) could in principle implement the algorithms we
study.
Honeybees-inspired heuristic algorithms for numerical optimisation
Authors: Muharrem Düğenci
Date: 2015-04-22 00:00:00

Swarm intelligence is all about developing collective behaviours to solve
complex, ill-structured and large-scale problems. Efficiency in collective
behaviours depends on how to harmonise the individual contributions so that a
complementary collective effort can be achieved to offer a useful solution. The
main points in organising the harmony remains as managing the diversification
and intensification actions appropriately, where the efficiency of collective
behaviours depends on blending these two actions appropriately. In this study,
two swarm intelligence algorithms inspired of natural honeybee colonies have
been overviewed with many respects and two new revisions and a hybrid version
have been studied to improve the efficiencies in solving numerical optimisation
problems, which are well-known hard benchmarks. Consequently, the revisions and
especially the hybrid algorithm proposed have outperformed the two original bee
algorithms in solving these very hard numerical optimisation benchmarks.
Learning Non-deterministic Representations with Energy-based Ensembles
Authors: Maruan Al-Shedivat, Emre Neftci, Gert Cauwenberghs
Date: 2014-12-23 00:00:00
Tasks: One-Shot Learning

The goal of a generative model is to capture the distribution underlying the
data, typically through latent variables. After training, these variables are
often used as a new representation, more effective than the original features
in a variety of learning tasks. However, the representations constructed by
contemporary generative models are usually point-wise deterministic mappings
from the original feature space. Thus, even with representations robust to
class-specific transformations, statistically driven models trained on them
would not be able to generalize when the labeled data is scarce. Inspired by
the stochasticity of the synaptic connections in the brain, we introduce
Energy-based Stochastic Ensembles. These ensembles can learn non-deterministic
representations, i.e., mappings from the feature space to a family of
distributions in the latent space. These mappings are encoded in a distribution
over a (possibly infinite) collection of models. By conditionally sampling
models from the ensemble, we obtain multiple representations for every input
example and effectively augment the data. We propose an algorithm similar to
contrastive divergence for training restricted Boltzmann stochastic ensembles.
Finally, we demonstrate the concept of the stochastic representations on a
synthetic dataset as well as test them in the one-shot learning scenario on
MNIST.
Rebuilding Factorized Information Criterion: Asymptotically Accurate Marginal Likelihood
Authors: Kohei Hayashi, Shin-ichi Maeda, Ryohei Fujimaki
Date: 2015-04-22 00:00:00
Tasks: Model Selection

Factorized information criterion (FIC) is a recently developed approximation
technique for the marginal log-likelihood, which provides an automatic model
selection framework for a few latent variable models (LVMs) with tractable
inference algorithms. This paper reconsiders FIC and fills theoretical gaps of
previous FIC studies. First, we reveal the core idea of FIC that allows
generalization for a broader class of LVMs, including continuous LVMs, in
contrast to previous FICs, which are applicable only to binary LVMs. Second, we
investigate the model selection mechanism of the generalized FIC. Our analysis
provides a formal justification of FIC as a model selection criterion for LVMs
and also a systematic procedure for pruning redundant latent variables that
have been removed heuristically in previous studies. Third, we provide an
interpretation of FIC as a variational free energy and uncover a few
previously-unknown their relationships. A demonstrative study on Bayesian
principal component analysis is provided and numerical experiments support our
theoretical results.
Distinguishing Cause from Effect Based on Exogeneity
Authors: Kun Zhang, Jiji Zhang, Bernhard Schölkopf
Date: 2015-04-22 00:00:00
Tasks: Causal Inference

Recent developments in structural equation modeling have produced several
methods that can usually distinguish cause from effect in the two-variable
case. For that purpose, however, one has to impose substantial structural
constraints or smoothness assumptions on the functional causal models. In this
paper, we consider the problem of determining the causal direction from a
related but different point of view, and propose a new framework for causal
direction determination. We show that it is possible to perform causal
inference based on the condition that the cause is "exogenous" for the
parameters involved in the generating process from the cause to the effect. In
this way, we avoid the structural constraints required by the SEM-based
approaches. In particular, we exploit nonparametric methods to estimate
marginal and conditional distributions, and propose a bootstrap-based approach
to test for the exogeneity condition; the testing results indicate the causal
direction between two variables. The proposed method is validated on both
synthetic and real data.
Self-Tuned Deep Super Resolution
Authors: Zhangyang Wang, Yingzhen Yang, Zhaowen Wang, Shiyu Chang, Wei Han, Jianchao Yang, Thomas S. Huang
Date: 2015-04-22 00:00:00
Tasks: Denoising, Image Super-Resolution, Super-Resolution

Deep learning has been successfully applied to image super resolution (SR).
In this paper, we propose a deep joint super resolution (DJSR) model to exploit
both external and self similarities for SR. A Stacked Denoising Convolutional
Auto Encoder (SDCAE) is first pre-trained on external examples with proper data
augmentations. It is then fine-tuned with multi-scale self examples from each
input, where the reliability of self examples is explicitly taken into account.
We also enhance the model performance by sub-model training and selection. The
DJSR model is extensively evaluated and compared with state-of-the-arts, and
show noticeable performance improvements both quantitatively and perceptually
on a wide range of images.
Adaptive Compressive Tracking via Online Vector Boosting Feature Selection
Authors: Qingshan Liu, Jing Yang, Kaihua Zhang, Yi Wu
Date: 2015-04-21 00:00:00
Tasks: feature selection

Recently, the compressive tracking (CT) method has attracted much attention
due to its high efficiency, but it cannot well deal with the large scale target
appearance variations due to its data-independent random projection matrix that
results in less discriminative features. To address this issue, in this paper
we propose an adaptive CT approach, which selects the most discriminative
features to design an effective appearance model. Our method significantly
improves CT in three aspects: Firstly, the most discriminative features are
selected via an online vector boosting method. Secondly, the object
representation is updated in an effective online manner, which preserves the
stable features while filtering out the noisy ones. Finally, a simple and
effective trajectory rectification approach is adopted that can make the
estimated location more accurate. Extensive experiments on the CVPR2013
tracking benchmark demonstrate the superior performance of our algorithm
compared over state-of-the-art tracking algorithms.
Median and Mode Ellipse Parameterization for Robust Contour Fitting
Authors: Michael A. Greminger
Date: 2015-04-22 00:00:00

Problems that require the parameterization of closed contours arise
frequently in computer vision applications. This article introduces a new curve
parameterization algorithm that is able to fit a closed curve to a set of
points while being robust to the presence of outliers and occlusions in the
data. This robustness property makes this algorithm applicable to computer
vision applications where misclassification of features may lead to outliers.
The algorithm starts by fitting ellipses to numerous five point subsets from
the source data. The closed curve is parameterized by determining the median
perimeter of the set of ellipses. The resulting curve is not an ellipse,
allowing arbitrary closed contours to be parameterized. The use of the modal
perimeter rather than the median perimeter is also explored. A detailed
comparison is made between the proposed curve fitting algorithm and existing
robust ellipse fitting algorithms. Finally, the utility of the algorithm for
computer vision applications is demonstrated through the parameterization of
the boundary of fuel droplets during combustion. The performance of the
proposed algorithm and the performance of existing algorithms are compared to a
ground truth segmentation of the fuel droplet images, which demonstrates
improved performance for both area quantification and edge deviation.