pwc-archive/papers-with-abstracts huggingface dataset:
Fast Supervised Hashing with Decision Trees for High-Dimensional Data
Authors: Guosheng Lin, Chunhua Shen, Qinfeng Shi, Anton Van Den Hengel, David Suter
Date: 2014-04-06 00:00:00
Proceeding: CVPR 2014 6
Tasks: Retrieval, Vocal Bursts Intensity Prediction

Supervised hashing aims to map the original features to compact binary codes
that are able to preserve label based similarity in the Hamming space.
Non-linear hash functions have demonstrated the advantage over linear ones due
to their powerful generalization capability. In the literature, kernel
functions are typically used to achieve non-linearity in hashing, which achieve
encouraging retrieval performance at the price of slow evaluation and training
time. Here we propose to use boosted decision trees for achieving non-linearity
in hashing, which are fast to train and evaluate, hence more suitable for
hashing with high dimensional data. In our approach, we first propose
sub-modular formulations for the hashing binary code inference problem and an
efficient GraphCut based block search method for solving large-scale inference.
Then we learn hash functions by training boosted decision trees to fit the
binary codes. Experiments demonstrate that our proposed method significantly
outperforms most state-of-the-art methods in retrieval precision and training
time. Especially for high-dimensional data, our method is orders of magnitude
faster than many methods in terms of training time.
An FPGA-based Parallel Architecture for Face Detection using Mixed Color Models
Authors: Luo Tao, Shi zaifeng
Date: 2014-05-27 00:00:00
Tasks: Face Detection

In this paper, a reliable method for detecting human faces in color images is proposed. This system firstly detects skin color in YCgCr and YIQ color space, then filters binary texture and the result is morphological processed, finally converts skin tone to the preferred skin color configured by users in YIQ color space. The real-time adjusting circuit is implemented and some of simulation results are given out. Experimental results demonstrate that the method has achieved high rates and low false positives, another advantage is its simplicity and minor computational costs.
Sum-of-squares proofs and the quest toward optimal algorithms
Authors: Boaz Barak, David Steurer
Date: 2014-04-21 00:00:00

In order to obtain the best-known guarantees, algorithms are traditionally
tailored to the particular problem we want to solve. Two recent developments,
the Unique Games Conjecture (UGC) and the Sum-of-Squares (SOS) method,
surprisingly suggest that this tailoring is not necessary and that a single
efficient algorithm could achieve best possible guarantees for a wide range of
different problems.
  The Unique Games Conjecture (UGC) is a tantalizing conjecture in
computational complexity, which, if true, will shed light on the complexity of
a great many problems. In particular this conjecture predicts that a single
concrete algorithm provides optimal guarantees among all efficient algorithms
for a large class of computational problems.
  The Sum-of-Squares (SOS) method is a general approach for solving systems of
polynomial constraints. This approach is studied in several scientific
disciplines, including real algebraic geometry, proof complexity, control
theory, and mathematical programming, and has found applications in fields as
diverse as quantum information theory, formal verification, game theory and
many others.
  We survey some connections that were recently uncovered between the Unique
Games Conjecture and the Sum-of-Squares method. In particular, we discuss new
tools to rigorously bound the running time of the SOS method for obtaining
approximate solutions to hard optimization problems, and how these tools give
the potential for the sum-of-squares method to provide new guarantees for many
problems of interest, and possibly to even refute the UGC.
Futility Analysis in the Cross-Validation of Machine Learning Models
Authors: Max Kuhn
Date: 2014-05-27 00:00:00
Tasks: BIG-bench Machine Learning

Many machine learning models have important structural tuning parameters that
cannot be directly estimated from the data. The common tactic for setting these
parameters is to use resampling methods, such as cross--validation or the
bootstrap, to evaluate a candidate set of values and choose the best based on
some pre--defined criterion. Unfortunately, this process can be time consuming.
However, the model tuning process can be streamlined by adaptively resampling
candidate values so that settings that are clearly sub-optimal can be
discarded. The notion of futility analysis is introduced in this context. An
example is shown that illustrates how adaptive resampling can be used to reduce
training time. Simulation studies are used to understand how the potential
speed--up is affected by parallel processing techniques.
Large Scale, Large Margin Classification using Indefinite Similarity Measures
Authors: Omid Aghazadeh, Stefan Carlsson
Date: 2014-05-27 00:00:00
Tasks: Classification, General Classification

Despite the success of the popular kernelized support vector machines, they
have two major limitations: they are restricted to Positive Semi-Definite (PSD)
kernels, and their training complexity scales at least quadratically with the
size of the data. Many natural measures of similarity between pairs of samples
are not PSD e.g. invariant kernels, and those that are implicitly or explicitly
defined by latent variable models. In this paper, we investigate scalable
approaches for using indefinite similarity measures in large margin frameworks.
In particular we show that a normalization of similarity to a subset of the
data points constitutes a representation suitable for linear classifiers. The
result is a classifier which is competitive to kernelized SVM in terms of
accuracy, despite having better training and test time complexities.
Experimental results demonstrate that on CIFAR-10 dataset, the model equipped
with similarity measures invariant to rigid and non-rigid deformations, can be
made more than 5 times sparser while being more accurate than kernelized SVM
using RBF kernels.
Supervised Dictionary Learning by a Variational Bayesian Group Sparse Nonnegative Matrix Factorization
Authors: Ivan Ivek
Date: 2014-05-27 00:00:00
Tasks: Classification, Dictionary Learning, Face Recognition, Facial Expression Recognition, Facial Expression Recognition (FER), General Classification

Nonnegative matrix factorization (NMF) with group sparsity constraints is
formulated as a probabilistic graphical model and, assuming some observed data
have been generated by the model, a feasible variational Bayesian algorithm is
derived for learning model parameters. When used in a supervised learning
scenario, NMF is most often utilized as an unsupervised feature extractor
followed by classification in the obtained feature subspace. Having mapped the
class labels to a more general concept of groups which underlie sparsity of the
coefficients, what the proposed group sparse NMF model allows is incorporating
class label information to find low dimensional label-driven dictionaries which
not only aim to represent the data faithfully, but are also suitable for class
discrimination. Experiments performed in face recognition and facial expression
recognition domains point to advantages of classification in such label-driven
feature subspaces over classification in feature subspaces obtained in an
unsupervised manner.
A Topic Model Approach to Multi-Modal Similarity
Authors: Rasmus Troelsgård, Bjørn Sand Jensen, Lars Kai Hansen
Date: 2014-05-27 00:00:00
Tasks: model

Calculating similarities between objects defined by many heterogeneous data
modalities is an important challenge in many multimedia applications. We use a
multi-modal topic model as a basis for defining such a similarity between
objects. We propose to compare the resulting similarities from different model
realizations using the non-parametric Mantel test. The approach is evaluated on
a music dataset.
Human Pose Estimation from RGB Input Using Synthetic Training Data
Authors: Oscar Danielsson, Omid Aghazadeh
Date: 2014-05-06 00:00:00
Tasks: Pose Estimation

We address the problem of estimating the pose of humans using RGB image
input. More specifically, we are using a random forest classifier to classify
pixels into joint-based body part categories, much similar to the famous Kinect
pose estimator [11], [12]. However, we are using pure RGB input, i.e. no depth.
Since the random forest requires a large number of training examples, we are
using computer graphics generated, synthetic training data. In addition, we
assume that we have access to a large number of real images with bounding box
labels, extracted for example by a pedestrian detector or a tracking system. We
propose a new objective function for random forest training that uses the
weakly labeled data from the target domain to encourage the learner to select
features that generalize from the synthetic source domain to the real target
domain. We demonstrate on a publicly available dataset [6] that the proposed
objective function yields a classifier that significantly outperforms a
baseline classifier trained using the standard entropy objective [10].
Lectures on Jacques Herbrand as a Logician
Authors: Claus-Peter Wirth, Joerg Siekmann, Christoph Benzmueller, Serge Autexier
Date: 2009-02-26 00:00:00
Tasks: Automated Theorem Proving, Formal Logic, LEMMA, Translation

We give some lectures on the work on formal logic of Jacques Herbrand, and
sketch his life and his influence on automated theorem proving. The intended
audience ranges from students interested in logic over historians to logicians.
Besides the well-known correction of Herbrand's False Lemma by Goedel and
Dreben, we also present the hardly known unpublished correction of Heijenoort
and its consequences on Herbrand's Modus Ponens Elimination. Besides Herbrand's
Fundamental Theorem and its relation to the Loewenheim-Skolem-Theorem, we
carefully investigate Herbrand's notion of intuitionism in connection with his
notion of falsehood in an infinite domain. We sketch Herbrand's two proofs of
the consistency of arithmetic and his notion of a recursive function, and last
but not least, present the correct original text of his unification algorithm
with a new translation.
Understanding Machine-learned Density Functionals
Authors: Li Li, John C. Snyder, Isabelle M. Pelaschier, Jessica Huang, Uma-Naresh Niranjan, Paul Duncan, Matthias Rupp, Klaus-Robert Müller, Kieron Burke
Date: 2014-04-04 00:00:00
Tasks: regression

Kernel ridge regression is used to approximate the kinetic energy of
non-interacting fermions in a one-dimensional box as a functional of their
density. The properties of different kernels and methods of cross-validation
are explored, and highly accurate energies are achieved. Accurate {\em
constrained optimal densities} are found via a modified Euler-Lagrange
constrained minimization of the total energy. A projected gradient descent
algorithm is derived using local principal component analysis. Additionally, a
sparse grid representation of the density can be used without degrading the
performance of the methods. The implications for machine-learned density
functional approximations are discussed.
Proximal Reinforcement Learning: A New Theory of Sequential Decision Making in Primal-Dual Spaces
Authors: Sridhar Mahadevan, Bo Liu, Philip Thomas, Will Dabney, Steve Giguere, Nicholas Jacek, Ian Gemp, Ji Liu
Date: 2014-05-26 00:00:00
Tasks: Decision Making, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Sequential Decision Making, Stochastic Optimization

In this paper, we set forth a new vision of reinforcement learning developed
by us over the past few years, one that yields mathematically rigorous
solutions to longstanding important questions that have remained unresolved:
(i) how to design reliable, convergent, and robust reinforcement learning
algorithms (ii) how to guarantee that reinforcement learning satisfies
pre-specified "safety" guarantees, and remains in a stable region of the
parameter space (iii) how to design "off-policy" temporal difference learning
algorithms in a reliable and stable manner, and finally (iv) how to integrate
the study of reinforcement learning into the rich theory of stochastic
optimization. In this paper, we provide detailed answers to all these questions
using the powerful framework of proximal operators.
  The key idea that emerges is the use of primal dual spaces connected through
the use of a Legendre transform. This allows temporal difference updates to
occur in dual spaces, allowing a variety of important technical advantages. The
Legendre transform elegantly generalizes past algorithms for solving
reinforcement learning problems, such as natural gradient methods, which we
show relate closely to the previously unconnected framework of mirror descent
methods. Equally importantly, proximal operator theory enables the systematic
development of operator splitting methods that show how to safely and reliably
decompose complex products of gradients that occur in recent variants of
gradient-based temporal difference learning. This key technical innovation
makes it possible to finally design "true" stochastic gradient methods for
reinforcement learning. Finally, Legendre transforms enable a variety of other
benefits, including modeling sparsity and domain geometry. Our work builds
extensively on recent work on the convergence of saddle-point algorithms, and
on the theory of monotone operators.
Visualizing Random Forest with Self-Organising Map
Authors: Piotr Płoński, Krzysztof Zaremba
Date: 2014-05-26 00:00:00
Tasks: Classification, General Classification

Random Forest (RF) is a powerful ensemble method for classification and
regression tasks. It consists of decision trees set. Although, a single tree is
well interpretable for human, the ensemble of trees is a black-box model. The
popular technique to look inside the RF model is to visualize a RF proximity
matrix obtained on data samples with Multidimensional Scaling (MDS) method.
Herein, we present a novel method based on Self-Organising Maps (SOM) for
revealing intrinsic relationships in data that lay inside the RF used for
classification tasks. We propose an algorithm to learn the SOM with the
proximity matrix obtained from the RF. The visualization of RF proximity matrix
with MDS and SOM is compared. What is more, the SOM learned with the RF
proximity matrix has better classification accuracy in comparison to SOM
learned with Euclidean distance. Presented approach enables better
understanding of the RF and additionally improves accuracy of the SOM.
Optimality Theory as a Framework for Lexical Acquisition
Authors: Thierry Poibeau
Date: 2014-05-26 00:00:00

This paper re-investigates a lexical acquisition system initially developed
for French.We show that, interestingly, the architecture of the system
reproduces and implements the main components of Optimality Theory. However, we
formulate the hypothesis that some of its limitations are mainly due to a poor
representation of the constraints used. Finally, we show how a better
representation of the constraints used would yield better results.
Hybrid Type-Logical Grammars, First-Order Linear Logic and the Descriptive Inadequacy of Lambda Grammars
Authors: Richard Moot
Date: 2014-05-26 00:00:00
Tasks: Descriptive, Translation, Vocal Bursts Type Prediction

In this article we show that hybrid type-logical grammars are a fragment of
first-order linear logic. This embedding result has several important
consequences: it not only provides a simple new proof theory for the calculus,
thereby clarifying the proof-theoretic foundations of hybrid type-logical
grammars, but, since the translation is simple and direct, it also provides
several new parsing strategies for hybrid type-logical grammars. Second,
NP-completeness of hybrid type-logical grammars follows immediately. The main
embedding result also sheds new light on problems with lambda grammars/abstract
categorial grammars and shows lambda grammars/abstract categorial grammars
suffer from problems of over-generation and from problems at the
syntax-semantics interface unlike any other categorial grammar.
Self-tuned Visual Subclass Learning with Shared Samples An Incremental Approach
Authors: Hossein Azizpour, Stefan Carlsson
Date: 2014-05-22 00:00:00
Tasks: Clustering, General Classification, Mixture-of-Experts, object-detection, Object Detection

Computer vision tasks are traditionally defined and evaluated using semantic
categories. However, it is known to the field that semantic classes do not
necessarily correspond to a unique visual class (e.g. inside and outside of a
car). Furthermore, many of the feasible learning techniques at hand cannot
model a visual class which appears consistent to the human eye. These problems
have motivated the use of 1) Unsupervised or supervised clustering as a
preprocessing step to identify the visual subclasses to be used in a
mixture-of-experts learning regime. 2) Felzenszwalb et al. part model and other
works model mixture assignment with latent variables which is optimized during
learning 3) Highly non-linear classifiers which are inherently capable of
modelling multi-modal input space but are inefficient at the test time. In this
work, we promote an incremental view over the recognition of semantic classes
with varied appearances. We propose an optimization technique which
incrementally finds maximal visual subclasses in a regularized risk
minimization framework. Our proposed approach unifies the clustering and
classification steps in a single algorithm. The importance of this approach is
its compliance with the classification via the fact that it does not need to
know about the number of clusters, the representation and similarity measures
used in pre-processing clustering methods a priori. Following this approach we
show both qualitatively and quantitatively significant results. We show that
the visual subclasses demonstrate a long tail distribution. Finally, we show
that state of the art object detection methods (e.g. DPM) are unable to use the
tails of this distribution comprising 50\% of the training samples. In fact we
show that DPM performance slightly increases on average by the removal of this
half of the data.
Inferring gender of a Twitter user using celebrities it follows
Authors: Puneet Singh Ludu
Date: 2014-05-26 00:00:00
Tasks: Classification, Gender Classification, Gender Prediction, General Classification

This paper addresses the task of user gender classification in social media,
with an application to Twitter. The approach automatically predicts gender by
leveraging observable information such as the tweet behavior, linguistic
content of the user's Twitter feed and the celebrities followed by the user.
This paper first evaluates linguistic content based features using LIWC
dictionary and popular neighborhood features using Wikipedia and Freebase. Then
augments both features which yielded a significant increase in the accuracy for
gender prediction. Results show that rich linguistic features combined with
popular neighborhood prove valuables and promising for additional user
classification needs.
New Algorithms for Learning Incoherent and Overcomplete Dictionaries
Authors: Sanjeev Arora, Rong Ge, Ankur Moitra
Date: 2013-08-28 00:00:00
Tasks: Dictionary Learning, Edge Detection, Super-Resolution

In sparse recovery we are given a matrix $A$ (the dictionary) and a vector of
the form $A X$ where $X$ is sparse, and the goal is to recover $X$. This is a
central notion in signal processing, statistics and machine learning. But in
applications such as sparse coding, edge detection, compression and super
resolution, the dictionary $A$ is unknown and has to be learned from random
examples of the form $Y = AX$ where $X$ is drawn from an appropriate
distribution --- this is the dictionary learning problem. In most settings, $A$
is overcomplete: it has more columns than rows. This paper presents a
polynomial-time algorithm for learning overcomplete dictionaries; the only
previously known algorithm with provable guarantees is the recent work of
Spielman, Wang and Wright who gave an algorithm for the full-rank case, which
is rarely the case in applications. Our algorithm applies to incoherent
dictionaries which have been a central object of study since they were
introduced in seminal work of Donoho and Huo. In particular, a dictionary is
$\mu$-incoherent if each pair of columns has inner product at most $\mu /
\sqrt{n}$.
  The algorithm makes natural stochastic assumptions about the unknown sparse
vector $X$, which can contain $k \leq c \min(\sqrt{n}/\mu \log n, m^{1/2
-\eta})$ non-zero entries (for any $\eta > 0$). This is close to the best $k$
allowable by the best sparse recovery algorithms even if one knows the
dictionary $A$ exactly. Moreover, both the running time and sample complexity
depend on $\log 1/\epsilon$, where $\epsilon$ is the target accuracy, and so
our algorithms converge very quickly to the true dictionary. Our algorithm can
also tolerate substantial amounts of noise provided it is incoherent with
respect to the dictionary (e.g., Gaussian). In the noisy setting, our running
time and sample complexity depend polynomially on $1/\epsilon$, and this is
necessary.
Bayesian Inference for Gaussian Process Classifiers with Annealing and Pseudo-Marginal MCMC
Authors: Maurizio Filippone
Date: 2013-11-28 00:00:00
Tasks: Bayesian Inference

Kernel methods have revolutionized the fields of pattern recognition and
machine learning. Their success, however, critically depends on the choice of
kernel parameters. Using Gaussian process (GP) classification as a working
example, this paper focuses on Bayesian inference of covariance (kernel)
parameters using Markov chain Monte Carlo (MCMC) methods. The motivation is
that, compared to standard optimization of kernel parameters, they have been
systematically demonstrated to be superior in quantifying uncertainty in
predictions. Recently, the Pseudo-Marginal MCMC approach has been proposed as a
practical inference tool for GP models. In particular, it amounts in replacing
the analytically intractable marginal likelihood by an unbiased estimate
obtainable by approximate methods and importance sampling. After discussing the
potential drawbacks in employing importance sampling, this paper proposes the
application of annealed importance sampling. The results empirically
demonstrate that compared to importance sampling, annealed importance sampling
can reduce the variance of the estimate of the marginal likelihood
exponentially in the number of data at a computational cost that scales only
polynomially. The results on real data demonstrate that employing annealed
importance sampling in the Pseudo-Marginal MCMC approach represents a step
forward in the development of fully automated exact inference engines for GP
models.