pwc-archive/papers-with-abstracts huggingface dataset:
On the Minimax Risk of Dictionary Learning
Authors: Alexander Jung, Yonina C. Eldar, Norbert Görtz
Date: 2015-07-20 00:00:00
Tasks: Dictionary Learning

We consider the problem of learning a dictionary matrix from a number of
observed signals, which are assumed to be generated via a linear model with a
common underlying dictionary. In particular, we derive lower bounds on the
minimum achievable worst case mean squared error (MSE), regardless of
computational complexity of the dictionary learning (DL) schemes. By casting DL
as a classical (or frequentist) estimation problem, the lower bounds on the
worst case MSE are derived by following an established information-theoretic
approach to minimax estimation. The main conceptual contribution of this paper
is the adaption of the information-theoretic approach to minimax estimation for
the DL problem in order to derive lower bounds on the worst case MSE of any DL
scheme. We derive three different lower bounds applying to different generative
models for the observed signals. The first bound applies to a wide range of
models, it only requires the existence of a covariance matrix of the (unknown)
underlying coefficient vector. By specializing this bound to the case of sparse
coefficient distributions, and assuming the true dictionary satisfies the
restricted isometry property, we obtain a lower bound on the worst case MSE of
DL schemes in terms of a signal to noise ratio (SNR). The third bound applies
to a more restrictive subclass of coefficient distributions by requiring the
non-zero coefficients to be Gaussian. While, compared with the previous two
bounds, the applicability of this final bound is the most limited it is the
tightest of the three bounds in the low SNR regime.
RAPS: A Recommender Algorithm Based on Pattern Structures
Authors: Dmitry I. Ignatov, Denis Kornilov
Date: 2015-07-20 00:00:00
Tasks: Recommendation Systems

We propose a new algorithm for recommender systems with numeric ratings which
is based on Pattern Structures (RAPS). As the input the algorithm takes rating
matrix, e.g., such that it contains movies rated by users. For a target user,
the algorithm returns a rated list of items (movies) based on its previous
ratings and ratings of other users. We compare the results of the proposed
algorithm in terms of precision and recall measures with Slope One, one of the
state-of-the-art item-based algorithms, on Movie Lens dataset and RAPS
demonstrates the best or comparable quality.
Efficient moving point handling for incremental 3D manifold reconstruction
Authors: Andrea Romanoni, Matteo Matteucci
Date: 2015-07-20 00:00:00
Tasks: 3D Reconstruction, Management

As incremental Structure from Motion algorithms become effective, a good
sparse point cloud representing the map of the scene becomes available
frame-by-frame. From the 3D Delaunay triangulation of these points,
state-of-the-art algorithms build a manifold rough model of the scene. These
algorithms integrate incrementally new points to the 3D reconstruction only if
their position estimate does not change. Indeed, whenever a point moves in a 3D
Delaunay triangulation, for instance because its estimation gets refined, a set
of tetrahedra have to be removed and replaced with new ones to maintain the
Delaunay property; the management of the manifold reconstruction becomes thus
complex and it entails a potentially big overhead. In this paper we investigate
different approaches and we propose an efficient policy to deal with moving
points in the manifold estimation process. We tested our approach with four
sequences of the KITTI dataset and we show the effectiveness of our proposal in
comparison with state-of-the-art approaches.
Scalable Stochastic Alternating Direction Method of Multipliers
Authors: Shen-Yi Zhao, Wu-Jun Li, Zhi-Hua Zhou
Date: 2015-02-12 00:00:00

Stochastic alternating direction method of multipliers (ADMM), which visits
only one sample or a mini-batch of samples each time, has recently been proved
to achieve better performance than batch ADMM. However, most stochastic methods
can only achieve a convergence rate $O(1/\sqrt T)$ on general convex
problems,where T is the number of iterations. Hence, these methods are not
scalable with respect to convergence rate (computation cost). There exists only
one stochastic method, called SA-ADMM, which can achieve convergence rate
$O(1/T)$ on general convex problems. However, an extra memory is needed for
SA-ADMM to store the historic gradients on all samples, and thus it is not
scalable with respect to storage cost. In this paper, we propose a novel
method, called scalable stochastic ADMM(SCAS-ADMM), for large-scale
optimization and learning problems. Without the need to store the historic
gradients, SCAS-ADMM can achieve the same convergence rate $O(1/T)$ as the best
stochastic method SA-ADMM and batch ADMM on general convex problems.
Experiments on graph-guided fused lasso show that SCAS-ADMM can achieve
state-of-the-art performance in real applications
Influence-Optimistic Local Values for Multiagent Planning --- Extended Version
Authors: Frans A. Oliehoek, Matthijs T. J. Spaan, Stefan Witwicki
Date: 2015-02-18 00:00:00
Tasks: Benchmarking, Heuristic Search

Recent years have seen the development of methods for multiagent planning
under uncertainty that scale to tens or even hundreds of agents. However, most
of these methods either make restrictive assumptions on the problem domain, or
provide approximate solutions without any guarantees on quality. Methods in the
former category typically build on heuristic search using upper bounds on the
value function. Unfortunately, no techniques exist to compute such upper bounds
for problems with non-factored value functions. To allow for meaningful
benchmarking through measurable quality guarantees on a very general class of
problems, this paper introduces a family of influence-optimistic upper bounds
for factored decentralized partially observable Markov decision processes
(Dec-POMDPs) that do not have factored value functions. Intuitively, we derive
bounds on very large multiagent planning problems by subdividing them in
sub-problems, and at each of these sub-problems making optimistic assumptions
with respect to the influence that will be exerted by the rest of the system.
We numerically compare the different upper bounds and demonstrate how we can
achieve a non-trivial guarantee that a heuristic solution for problems with
hundreds of agents is close to optimal. Furthermore, we provide evidence that
the upper bounds may improve the effectiveness of heuristic influence search,
and discuss further potential applications to multiagent planning.
Towards Effective Codebookless Model for Image Classification
Authors: Qilong Wang, Peihua Li, Lei Zhang, WangMeng Zuo
Date: 2015-07-09 00:00:00
Tasks: Classification, General Classification, image-classification, Image Classification, model, Saliency Detection

The bag-of-features (BoF) model for image classification has been thoroughly
studied over the last decade. Different from the widely used BoF methods which
modeled images with a pre-trained codebook, the alternative codebook free image
modeling method, which we call Codebookless Model (CLM), attracted little
attention. In this paper, we present an effective CLM that represents an image
with a single Gaussian for classification. By embedding Gaussian manifold into
a vector space, we show that the simple incorporation of our CLM into a linear
classifier achieves very competitive accuracy compared with state-of-the-art
BoF methods (e.g., Fisher Vector). Since our CLM lies in a high dimensional
Riemannian manifold, we further propose a joint learning method of low-rank
transformation with support vector machine (SVM) classifier on the Gaussian
manifold, in order to reduce computational and storage cost. To study and
alleviate the side effect of background clutter on our CLM, we also present a
simple yet effective partial background removal method based on saliency
detection. Experiments are extensively conducted on eight widely used databases
to demonstrate the effectiveness and efficiency of our CLM method.
Dual-normal Logic Programs - the Forgotten Class
Authors: Johannes K. Fichte, Miroslaw Truszczynski, Stefan Woltran
Date: 2015-07-20 00:00:00
Tasks: Translation

Disjunctive Answer Set Programming is a powerful declarative programming
paradigm with complexity beyond NP. Identifying classes of programs for which
the consistency problem is in NP is of interest from the theoretical standpoint
and can potentially lead to improvements in the design of answer set
programming solvers. One of such classes consists of dual-normal programs,
where the number of positive body atoms in proper rules is at most one. Unlike
other classes of programs, dual-normal programs have received little attention
so far. In this paper we study this class. We relate dual-normal programs to
propositional theories and to normal programs by presenting several
inter-translations. With the translation from dual-normal to normal programs at
hand, we introduce the novel class of body-cycle free programs, which are in
many respects dual to head-cycle free programs. We establish the expressive
power of dual-normal programs in terms of SE- and UE-models, and compare them
to normal programs. We also discuss the complexity of deciding whether
dual-normal programs are strongly and uniformly equivalent.
Linear Inverse Problems with Norm and Sparsity Constraints
Authors: Volkan Cevher, Sina Jafarpour, Anastasios Kyrillidis
Date: 2015-07-20 00:00:00
Tasks: Combinatorial Optimization, regression

We describe two nonconventional algorithms for linear regression, called GAME
and CLASH. The salient characteristics of these approaches is that they exploit
the convex $\ell_1$-ball and non-convex $\ell_0$-sparsity constraints jointly
in sparse recovery. To establish the theoretical approximation guarantees of
GAME and CLASH, we cover an interesting range of topics from game theory,
convex and combinatorial optimization. We illustrate that these approaches lead
to improved theoretical guarantees and empirical performance beyond convex and
non-convex solvers alone.
Structured Sparsity: Discrete and Convex approaches
Authors: Anastasios Kyrillidis, Luca Baldassarre, Marwa El-Halabi, Quoc Tran-Dinh, Volkan Cevher
Date: 2015-07-20 00:00:00
Tasks: Compressive Sensing

Compressive sensing (CS) exploits sparsity to recover sparse or compressible
signals from dimensionality reducing, non-adaptive sensing mechanisms. Sparsity
is also used to enhance interpretability in machine learning and statistics
applications: While the ambient dimension is vast in modern data analysis
problems, the relevant information therein typically resides in a much lower
dimensional space. However, many solutions proposed nowadays do not leverage
the true underlying structure. Recent results in CS extend the simple sparsity
idea to more sophisticated {\em structured} sparsity models, which describe the
interdependency between the nonzero components of a signal, allowing to
increase the interpretability of the results and lead to better recovery
performance. In order to better understand the impact of structured sparsity,
in this chapter we analyze the connections between the discrete models and
their convex relaxations, highlighting their relative advantages. We start with
the general group sparse model and then elaborate on two important special
cases: the dispersive and the hierarchical models. For each, we present the
models in their discrete nature, discuss how to solve the ensuing discrete
problems and then describe convex relaxations. We also consider more general
structures as defined by set functions and present their convex proxies.
Further, we discuss efficient optimization solutions for structured sparsity
problems and illustrate structured sparsity in action via three applications.
Learning Complexity-Aware Cascades for Deep Pedestrian Detection
Authors: Zhaowei Cai, Mohammad Saberian, Nuno Vasconcelos
Date: 2015-07-19 00:00:00
Proceeding: ICCV 2015 12
Tasks: Pedestrian Detection

The design of complexity-aware cascaded detectors, combining features of very
different complexities, is considered. A new cascade design procedure is
introduced, by formulating cascade learning as the Lagrangian optimization of a
risk that accounts for both accuracy and complexity. A boosting algorithm,
denoted as complexity aware cascade training (CompACT), is then derived to
solve this optimization. CompACT cascades are shown to seek an optimal
trade-off between accuracy and complexity by pushing features of higher
complexity to the later cascade stages, where only a few difficult candidate
patches remain to be classified. This enables the use of features of vastly
different complexities in a single detector. In result, the feature pool can be
expanded to features previously impractical for cascade design, such as the
responses of a deep convolutional neural network (CNN). This is demonstrated
through the design of a pedestrian detector with a pool of features whose
complexities span orders of magnitude. The resulting cascade generalizes the
combination of a CNN with an object proposal mechanism: rather than a
pre-processing stage, CompACT cascades seamlessly integrate CNNs in their
stages. This enables state of the art performance on the Caltech and KITTI
datasets, at fairly fast speeds.
Fast Adaptive Weight Noise
Authors: Justin Bayer, Maximilian Karl, Daniela Korhammer, Patrick van der Smagt
Date: 2015-07-19 00:00:00
Tasks: Gaussian Processes

Marginalising out uncertain quantities within the internal representations or
parameters of neural networks is of central importance for a wide range of
learning techniques, such as empirical, variational or full Bayesian methods.
We set out to generalise fast dropout (Wang & Manning, 2013) to cover a wider
variety of noise processes in neural networks. This leads to an efficient
calculation of the marginal likelihood and predictive distribution which evades
sampling and the consequential increase in training time due to highly variant
gradient estimates. This allows us to approximate variational Bayes for the
parameters of feed-forward neural networks. Inspired by the minimum description
length principle, we also propose and experimentally verify the direct
optimisation of the regularised predictive distribution. The methods yield
results competitive with previous neural network based approaches and Gaussian
processes on a wide range of regression tasks.
2 Notes on Classes with Vapnik-Chervonenkis Dimension 1
Authors: Shai Ben-David
Date: 2015-07-19 00:00:00
Tasks: BIG-bench Machine Learning, Learning Theory

The Vapnik-Chervonenkis dimension is a combinatorial parameter that reflects
the "complexity" of a set of sets (a.k.a. concept classes). It has been
introduced by Vapnik and Chervonenkis in their seminal 1971 paper and has since
found many applications, most notably in machine learning theory and in
computational geometry. Arguably the most influential consequence of the VC
analysis is the fundamental theorem of statistical machine learning, stating
that a concept class is learnable (in some precise sense) if and only if its
VC-dimension is finite. Furthermore, for such classes a most simple learning
rule - empirical risk minimization (ERM) - is guaranteed to succeed.
  The simplest non-trivial structures, in terms of the VC-dimension, are the
classes (i.e., sets of subsets) for which that dimension is 1.
  In this note we show a couple of curious results concerning such classes. The
first result shows that such classes share a very simple structure, and, as a
corollary, the labeling information contained in any sample labeled by such a
class can be compressed into a single instance.
  The second result shows that due to some subtle measurability issues, in
spite of the above mentioned fundamental theorem, there are classes of
dimension 1 for which an ERM learning rule fails miserably.
An Efficient Genetic Algorithm for Discovering Diverse-Frequent Patterns
Authors: Shanjida Khatun, Hasib Ul Alam, Swakkhar Shatabda
Date: 2015-07-19 00:00:00
Tasks: Diversity, Heuristic Search

Working with exhaustive search on large dataset is infeasible for several
reasons. Recently, developed techniques that made pattern set mining feasible
by a general solver with long execution time that supports heuristic search and
are limited to small datasets only. In this paper, we investigate an approach
which aims to find diverse set of patterns using genetic algorithm to mine
diverse frequent patterns. We propose a fast heuristic search algorithm that
outperforms state-of-the-art methods on a standard set of benchmarks and
capable to produce satisfactory results within a short period of time. Our
proposed algorithm uses a relative encoding scheme for the patterns and an
effective twin removal technique to ensure diversity throughout the search.
Judgment Aggregation in Multi-Agent Argumentation
Authors: Edmond Awad, Richard Booth, Fernando Tohme, Iyad Rahwan
Date: 2014-05-26 00:00:00

Given a set of conflicting arguments, there can exist multiple plausible
opinions about which arguments should be accepted, rejected, or deemed
undecided. We study the problem of how multiple such judgments can be
aggregated. We define the problem by adapting various classical
social-choice-theoretic properties for the argumentation domain. We show that
while argument-wise plurality voting satisfies many properties, it fails to
guarantee the collective rationality of the outcome, and struggles with ties.
We then present more general results, proving multiple impossibility results on
the existence of any good aggregation operator. After characterising the
sufficient and necessary conditions for satisfying collective rationality, we
study whether restricting the domain of argument-wise plurality voting to
classical semantics allows us to escape the impossibility result. We close by
listing graph-theoretic restrictions under which argument-wise plurality rule
does produce collectively rational outcomes. In addition to identifying
fundamental barriers to collective argument evaluation, our results open up the
door for a new research agenda for the argumentation and computational social
choice communities.
Optimizing Phylogenetic Supertrees Using Answer Set Programming
Authors: Laura Koponen, Emilia Oikarinen, Tomi Janhunen, Laura Säilä
Date: 2015-07-19 00:00:00

The supertree construction problem is about combining several phylogenetic
trees with possibly conflicting information into a single tree that has all the
leaves of the source trees as its leaves and the relationships between the
leaves are as consistent with the source trees as possible. This leads to an
optimization problem that is computationally challenging and typically
heuristic methods, such as matrix representation with parsimony (MRP), are
used. In this paper we consider the use of answer set programming to solve the
supertree construction problem in terms of two alternative encodings. The first
is based on an existing encoding of trees using substructures known as
quartets, while the other novel encoding captures the relationships present in
trees through direct projections. We use these encodings to compute a
genus-level supertree for the family of cats (Felidae). Furthermore, we compare
our results to recent supertrees obtained by the MRP method.
Reinforcement Learning for the Unit Commitment Problem
Authors: Gal Dalal, Shie Mannor
Date: 2015-07-19 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Scheduling

In this work we solve the day-ahead unit commitment (UC) problem, by
formulating it as a Markov decision process (MDP) and finding a low-cost policy
for generation scheduling. We present two reinforcement learning algorithms,
and devise a third one. We compare our results to previous work that uses
simulated annealing (SA), and show a 27% improvement in operation costs, with
running time of 2.5 minutes (compared to 2.5 hours of existing
state-of-the-art).
Handwriting Recognition
Authors: Jayati Ghosh Dastidar, Surabhi Sarkar, Rick Punyadyuti Sinha, Kasturi Basu
Date: 2015-07-19 00:00:00
Tasks: Handwriting Recognition, Segmentation

This paper describes the method to recognize offline handwritten characters.
A robust algorithm for handwriting segmentation is described here with the help
of which individual characters can be segmented from a selected word from a
paragraph of handwritten text image which is given as input.
Hand Gesture Recognition Library
Authors: Jonathan Fidelis Paul, Dibyabiva Seth, Cijo Paul, Jayati Ghosh Dastidar
Date: 2015-07-19 00:00:00
Tasks: Gesture Recognition, Hand Gesture Recognition, Hand-Gesture Recognition

In this paper we have presented a hand gesture recognition library. Various
functions include detecting cluster count, cluster orientation, finger pointing
direction, etc. To use these functions first the input image needs to be
processed into a logical array for which a function has been developed. The
library has been developed keeping flexibility in mind and thus provides
application developers a wide range of options to develop custom gestures.
Mapping Big Data into Knowledge Space with Cognitive Cyber-Infrastructure
Authors: Hai Zhuge
Date: 2015-07-18 00:00:00
Tasks: Management

Big data research has attracted great attention in science, technology,
industry and society. It is developing with the evolving scientific paradigm,
the fourth industrial revolution, and the transformational innovation of
technologies. However, its nature and fundamental challenge have not been
recognized, and its own methodology has not been formed. This paper explores
and answers the following questions: What is big data? What are the basic
methods for representing, managing and analyzing big data? What is the
relationship between big data and knowledge? Can we find a mapping from big
data into knowledge space? What kind of infrastructure is required to support
not only big data management and analysis but also knowledge discovery, sharing
and management? What is the relationship between big data and science paradigm?
What is the nature and fundamental challenge of big data computing? A
multi-dimensional perspective is presented toward a methodology of big data
computing.
Theory of Dual-sparse Regularized Randomized Reduction
Authors: Tianbao Yang, Lijun Zhang, Rong Jin, Shenghuo Zhu
Date: 2015-04-15 00:00:00
Tasks: General Classification

In this paper, we study randomized reduction methods, which reduce
high-dimensional features into low-dimensional space by randomized methods
(e.g., random projection, random hashing), for large-scale high-dimensional
classification. Previous theoretical results on randomized reduction methods
hinge on strong assumptions about the data, e.g., low rank of the data matrix
or a large separable margin of classification, which hinder their applications
in broad domains. To address these limitations, we propose dual-sparse
regularized randomized reduction methods that introduce a sparse regularizer
into the reduced dual problem. Under a mild condition that the original dual
solution is a (nearly) sparse vector, we show that the resulting dual solution
is close to the original dual solution and concentrates on its support set. In
numerical experiments, we present an empirical study to support the analysis
and we also present a novel application of the dual-sparse regularized
randomized reduction methods to reducing the communication cost of distributed
learning from large-scale high-dimensional data.