pwc-archive/papers-with-abstracts huggingface dataset:
Deep Transductive Semi-supervised Maximum Margin Clustering
Authors: Gang Chen
Date: 2015-01-26 00:00:00
Tasks: Clustering, Transductive Learning

Semi-supervised clustering is an very important topic in machine learning and
computer vision. The key challenge of this problem is how to learn a metric,
such that the instances sharing the same label are more likely close to each
other on the embedded space. However, little attention has been paid to learn
better representations when the data lie on non-linear manifold. Fortunately,
deep learning has led to great success on feature learning recently. Inspired
by the advances of deep learning, we propose a deep transductive
semi-supervised maximum margin clustering approach. More specifically, given
pairwise constraints, we exploit both labeled and unlabeled data to learn a
non-linear mapping under maximum margin framework for clustering analysis.
Thus, our model unifies transductive learning, feature learning and maximum
margin techniques in the semi-supervised clustering framework. We pretrain the
deep network structure with restricted Boltzmann machines (RBMs) layer by layer
greedily, and optimize our objective function with gradient descent. By
checking the most violated constraints, our approach updates the model
parameters through error backpropagation, in which deep features are learned
automatically. The experimental results shows that our model is significantly
better than the state of the art on semi-supervised clustering.
Online Optimization : Competing with Dynamic Comparators
Authors: Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, Karthik Sridharan
Date: 2015-01-26 00:00:00

Recent literature on online learning has focused on developing adaptive
algorithms that take advantage of a regularity of the sequence of observations,
yet retain worst-case performance guarantees. A complementary direction is to
develop prediction methods that perform well against complex benchmarks. In
this paper, we address these two directions together. We present a fully
adaptive method that competes with dynamic benchmarks in which regret guarantee
scales with regularity of the sequence of cost functions and comparators.
Notably, the regret bound adapts to the smaller complexity measure in the
problem environment. Finally, we apply our results to drifting zero-sum,
two-player games where both players achieve no regret guarantees against best
sequences of actions in hindsight.
A Topic Modeling Approach to Ranking
Authors: Weicong Ding, Prakash Ishwar, Venkatesh Saligrama
Date: 2014-12-11 00:00:00

We propose a topic modeling approach to the prediction of preferences in
pairwise comparisons. We develop a new generative model for pairwise
comparisons that accounts for multiple shared latent rankings that are
prevalent in a population of users. This new model also captures inconsistent
user behavior in a natural way. We show how the estimation of latent rankings
in the new generative model can be formally reduced to the estimation of topics
in a statistically equivalent topic modeling problem. We leverage recent
advances in the topic modeling literature to develop an algorithm that can
learn shared latent rankings with provable consistency as well as sample and
computational complexity guarantees. We demonstrate that the new approach is
empirically competitive with the current state-of-the-art approaches in
predicting preferences on some semi-synthetic and real world datasets.
Randomized sketches for kernels: Fast and optimal non-parametric regression
Authors: Yun Yang, Mert Pilanci, Martin J. Wainwright
Date: 2015-01-25 00:00:00
Tasks: regression

Kernel ridge regression (KRR) is a standard method for performing
non-parametric regression over reproducing kernel Hilbert spaces. Given $n$
samples, the time and space complexity of computing the KRR estimate scale as
$\mathcal{O}(n^3)$ and $\mathcal{O}(n^2)$ respectively, and so is prohibitive
in many cases. We propose approximations of KRR based on $m$-dimensional
randomized sketches of the kernel matrix, and study how small the projection
dimension $m$ can be chosen while still preserving minimax optimality of the
approximate KRR estimate. For various classes of randomized sketches, including
those based on Gaussian and randomized Hadamard matrices, we prove that it
suffices to choose the sketch dimension $m$ proportional to the statistical
dimension (modulo logarithmic factors). Thus, we obtain fast and minimax
optimal approximations to the KRR estimate for non-parametric regression.
Exploring Human Vision Driven Features for Pedestrian Detection
Authors: Shanshan Zhang, Christian Bauckhage, Dominik A. Klein, Armin B. Cremers
Date: 2015-01-25 00:00:00
Tasks: Pedestrian Detection

Motivated by the center-surround mechanism in the human visual attention
system, we propose to use average contrast maps for the challenge of pedestrian
detection in street scenes due to the observation that pedestrians indeed
exhibit discriminative contrast texture. Our main contributions are first to
design a local, statistical multi-channel descriptorin order to incorporate
both color and gradient information. Second, we introduce a multi-direction and
multi-scale contrast scheme based on grid-cells in order to integrate
expressive local variations. Contributing to the issue of selecting most
discriminative features for assessing and classification, we perform extensive
comparisons w.r.t. statistical descriptors, contrast measurements, and scale
structures. This way, we obtain reasonable results under various
configurations. Empirical findings from applying our optimized detector on the
INRIA and Caltech pedestrian datasets show that our features yield
state-of-the-art performance in pedestrian detection.
Discrete and fuzzy dynamical genetic programming in the XCSF learning classifier system
Authors: Richard J. Preen, Larry Bull
Date: 2012-01-26 00:00:00

A number of representation schemes have been presented for use within
learning classifier systems, ranging from binary encodings to neural networks.
This paper presents results from an investigation into using discrete and fuzzy
dynamical system representations within the XCSF learning classifier system. In
particular, asynchronous random Boolean networks are used to represent the
traditional condition-action production system rules in the discrete case and
asynchronous fuzzy logic networks in the continuous-valued case. It is shown
possible to use self-adaptive, open-ended evolution to design an ensemble of
such dynamical systems within XCSF to solve a number of well-known test
problems.
Thou Shalt is not You Will
Authors: Guido Governatori
Date: 2014-04-07 00:00:00

In this paper we discuss some reasons why temporal logic might not be
suitable to model real life norms. To show this, we present a novel deontic
logic contrary-to-duty/derived permission paradox based on the interaction of
obligations, permissions and contrary-to-duty obligations. The paradox is
inspired by real life norms.
An Occlusion Reasoning Scheme for Monocular Pedestrian Tracking in Dynamic Scenes
Authors: Sourav Garg, Swagat Kumar, Rajesh Ratnakaram, Prithwijit Guha
Date: 2015-01-25 00:00:00

This paper looks into the problem of pedestrian tracking using a monocular,
potentially moving, uncalibrated camera. The pedestrians are located in each
frame using a standard human detector, which are then tracked in subsequent
frames. This is a challenging problem as one has to deal with complex
situations like changing background, partial or full occlusion and camera
motion. In order to carry out successful tracking, it is necessary to resolve
associations between the detected windows in the current frame with those
obtained from the previous frame. Compared to methods that use temporal windows
incorporating past as well as future information, we attempt to make decision
on a frame-by-frame basis. An occlusion reasoning scheme is proposed to resolve
the association problem between a pair of consecutive frames by using an
affinity matrix that defines the closeness between a pair of windows and then,
uses a binary integer programming to obtain unique association between them. A
second stage of verification based on SURF matching is used to deal with those
cases where the above optimization scheme might yield wrong associations. The
efficacy of the approach is demonstrated through experiments on several
standard pedestrian datasets.
Prediction Error Reduction Function as a Variable Importance Score
Authors: Ernest Fokoué
Date: 2015-01-25 00:00:00
Tasks: Ensemble Learning

This paper introduces and develops a novel variable importance score function
in the context of ensemble learning and demonstrates its appeal both
theoretically and empirically. Our proposed score function is simple and more
straightforward than its counterpart proposed in the context of random forest,
and by avoiding permutations, it is by design computationally more efficient
than the random forest variable importance function. Just like the random
forest variable importance function, our score handles both regression and
classification seamlessly. One of the distinct advantage of our proposed score
is the fact that it offers a natural cut off at zero, with all the positive
scores indicating importance and significance, while the negative scores are
deemed indications of insignificance. An extra advantage of our proposed score
lies in the fact it works very well beyond ensemble of trees and can seamlessly
be used with any base learners in the random subspace learning context. Our
examples, both simulated and real, demonstrate that our proposed score does
compete mostly favorably with the random forest score.
Semi-blind Source Separation via Sparse Representations and Online Dictionary Learning
Authors: Sirisha Rambhatla, Jarvis D. Haupt
Date: 2012-12-03 00:00:00
Tasks: Audio Source Separation, blind source separation, Dictionary Learning

This work examines a semi-blind single-channel source separation problem. Our
specific aim is to separate one source whose local structure is approximately
known, from another a priori unspecified background source, given only a single
linear combination of the two sources. We propose a separation technique based
on local sparse approximations along the lines of recent efforts in sparse
representations and dictionary learning. A key feature of our procedure is the
online learning of dictionaries (using only the data itself) to sparsely model
the background source, which facilitates its separation from the
partially-known source. Our approach is applicable to source separation
problems in various application domains; here, we demonstrate the performance
of our proposed approach via simulation on a stylized audio source separation
task.
A simpler condition for consistency of a kernel independence test
Authors: Arthur Gretton
Date: 2015-01-25 00:00:00

A statistical test of independence may be constructed using the
Hilbert-Schmidt Independence Criterion (HSIC) as a test statistic. The HSIC is
defined as the distance between the embedding of the joint distribution, and
the embedding of the product of the marginals, in a Reproducing Kernel Hilbert
Space (RKHS). It has previously been shown that when the kernel used in
defining the joint embedding is characteristic (that is, the embedding of the
joint distribution to the feature space is injective), then the HSIC-based test
is consistent. In particular, it is sufficient for the product of kernels on
the individual domains to be characteristic on the joint domain. In this note,
it is established via a result of Lyons (2013) that HSIC-based independence
tests are consistent when kernels on the marginals are characteristic on their
respective domains, even when the product of kernels is not characteristic on
the joint domain.
Between Pure and Approximate Differential Privacy
Authors: Thomas Steinke, Jonathan Ullman
Date: 2015-01-24 00:00:00

We show a new lower bound on the sample complexity of $(\varepsilon,
\delta)$-differentially private algorithms that accurately answer statistical
queries on high-dimensional databases. The novelty of our bound is that it
depends optimally on the parameter $\delta$, which loosely corresponds to the
probability that the algorithm fails to be private, and is the first to
smoothly interpolate between approximate differential privacy ($\delta > 0$)
and pure differential privacy ($\delta = 0$).
  Specifically, we consider a database $D \in \{\pm1\}^{n \times d}$ and its
\emph{one-way marginals}, which are the $d$ queries of the form "What fraction
of individual records have the $i$-th bit set to $+1$?" We show that in order
to answer all of these queries to within error $\pm \alpha$ (on average) while
satisfying $(\varepsilon, \delta)$-differential privacy, it is necessary that
$$ n \geq \Omega\left( \frac{\sqrt{d \log(1/\delta)}}{\alpha \varepsilon}
\right), $$ which is optimal up to constant factors. To prove our lower bound,
we build on the connection between \emph{fingerprinting codes} and lower bounds
in differential privacy (Bun, Ullman, and Vadhan, STOC'14).
  In addition to our lower bound, we give new purely and approximately
differentially private algorithms for answering arbitrary statistical queries
that improve on the sample complexity of the standard Laplace and Gaussian
mechanisms for achieving worst-case accuracy guarantees by a logarithmic
factor.
Fisher Vectors Derived from Hybrid Gaussian-Laplacian Mixture Models for Image Annotation
Authors: Benjamin Klein, Guy Lev, Gil Sadeh, Lior Wolf
Date: 2014-11-26 00:00:00
Tasks: Image Retrieval, Object Recognition, Sentence

In the traditional object recognition pipeline, descriptors are densely
sampled over an image, pooled into a high dimensional non-linear representation
and then passed to a classifier. In recent years, Fisher Vectors have proven
empirically to be the leading representation for a large variety of
applications. The Fisher Vector is typically taken as the gradients of the
log-likelihood of descriptors, with respect to the parameters of a Gaussian
Mixture Model (GMM). Motivated by the assumption that different distributions
should be applied for different datasets, we present two other Mixture Models
and derive their Expectation-Maximization and Fisher Vector expressions. The
first is a Laplacian Mixture Model (LMM), which is based on the Laplacian
distribution. The second Mixture Model presented is a Hybrid Gaussian-Laplacian
Mixture Model (HGLMM) which is based on a weighted geometric mean of the
Gaussian and Laplacian distribution. An interesting property of the
Expectation-Maximization algorithm for the latter is that in the maximization
step, each dimension in each component is chosen to be either a Gaussian or a
Laplacian. Finally, by using the new Fisher Vectors derived from HGLMMs, we
achieve state-of-the-art results for both the image annotation and the image
search by a sentence tasks.
Sparse Distance Weighted Discrimination
Authors: Boxiang Wang, Hui Zou
Date: 2015-01-24 00:00:00
Tasks: Computational Efficiency, General Classification

Distance weighted discrimination (DWD) was originally proposed to handle the
data piling issue in the support vector machine. In this paper, we consider the
sparse penalized DWD for high-dimensional classification. The state-of-the-art
algorithm for solving the standard DWD is based on second-order cone
programming, however such an algorithm does not work well for the sparse
penalized DWD with high-dimensional data. In order to overcome the challenging
computation difficulty, we develop a very efficient algorithm to compute the
solution path of the sparse DWD at a given fine grid of regularization
parameters. We implement the algorithm in a publicly available R package sdwd.
We conduct extensive numerical experiments to demonstrate the computational
efficiency and classification performance of our method.
Consistency Analysis of Nearest Subspace Classifier
Authors: Yi Wang
Date: 2015-01-24 00:00:00
Tasks: General Classification

The Nearest subspace classifier (NSS) finds an estimation of the underlying
subspace within each class and assigns data points to the class that
corresponds to its nearest subspace. This paper mainly studies how well NSS can
be generalized to new samples. It is proved that NSS is strongly consistent
under certain assumptions. For completeness, NSS is evaluated through
experiments on various simulated and real data sets, in comparison with some
other linear model based classifiers. It is also shown that NSS can obtain
effective classification results and is very efficient, especially for large
scale data sets.
Learning From Non-iid Data: Fast Rates for the One-vs-All Multiclass Plug-in Classifiers
Authors: Vu Dinh, Lam Si Tung Ho, Nguyen Viet Cuong, Duy Nguyen, Binh T. Nguyen
Date: 2014-08-12 00:00:00
Tasks: All

We prove new fast learning rates for the one-vs-all multiclass plug-in
classifiers trained either from exponentially strongly mixing data or from data
generated by a converging drifting distribution. These are two typical
scenarios where training data are not iid. The learning rates are obtained
under a multiclass version of Tsybakov's margin assumption, a type of low-noise
assumption, and do not depend on the number of classes. Our results are general
and include a previous result for binary-class plug-in classifiers with iid
data as a special case. In contrast to previous works for least squares SVMs
under the binary-class setting, our results retain the optimal learning rate in
the iid case.
Canonical Logic Programs are Succinctly Incomparable with Propositional Formulas
Authors: Yuping Shen, Xishun Zhao
Date: 2014-12-01 00:00:00

\emph{Canonical (logic) programs} (CP) refer to normal logic programs
augmented with connective $not\ not$. In this paper we address the question of
whether CP are \emph{succinctly incomparable} with \emph{propositional
formulas} (PF). Our main result shows that the PARITY problem, which can be
polynomially represented in PF but \emph{only} has exponential representations
in CP. In other words, PARITY \emph{separates} PF from CP. Simply speaking,
this means that exponential size blowup is generally inevitable when
translating a set of formulas in PF into an equivalent program in CP (without
introducing new variables). Furthermore, since it has been shown by Lifschitz
and Razborov that there is also a problem that separates CP from PF (assuming
$\mathsf{P}\nsubseteq \mathsf{NC^1/poly}$), it follows that CP and PF are
indeed succinctly incomparable. From the view of the theory of computation, the
above result may also be considered as the separation of two \emph{models of
computation}, i.e., we identify a language in $\mathsf{NC^1/poly}$ which is not
in the set of languages computable by polynomial size CP programs.
Random Variables Recorded under Mutually Exclusive Conditions: Contextuality-by-Default
Authors: Ehtibar N. Dzhafarov, Janne V. Kujala
Date: 2013-09-04 00:00:00

We present general principles underlying analysis of the dependence of random
variables (outputs) on deterministic conditions (inputs). Random outputs
recorded under mutually exclusive input values are labeled by these values and
considered stochastically unrelated, possessing no joint distribution. An input
that does not directly influence an output creates a context for the latter.
Any constraint imposed on the dependence of random outputs on inputs can be
characterized by considering all possible couplings (joint distributions)
imposed on stochastically unrelated outputs. The target application of these
principles is a quantum mechanical system of entangled particles, with
directions of spin measurements chosen for each particle being inputs and the
spins recorded outputs. The sphere of applicability, however, spans systems
across physical, biological, and behavioral sciences.
Automatic Objects Removal for Scene Completion
Authors: Jianjun Yang, Yin Wang, Honggang Wang, Kun Hua, Wei Wang, Ju Shen
Date: 2015-01-23 00:00:00
Tasks: 3D Scene Reconstruction, Texture Synthesis

With the explosive growth of web-based cameras and mobile devices, billions
of photographs are uploaded to the internet. We can trivially collect a huge
number of photo streams for various goals, such as 3D scene reconstruction and
other big data applications. However, this is not an easy task due to the fact
the retrieved photos are neither aligned nor calibrated. Furthermore, with the
occlusion of unexpected foreground objects like people, vehicles, it is even
more challenging to find feature correspondences and reconstruct realistic
scenes. In this paper, we propose a structure based image completion algorithm
for object removal that produces visually plausible content with consistent
structure and scene texture. We use an edge matching technique to infer the
potential structure of the unknown region. Driven by the estimated structure,
texture synthesis is performed automatically along the estimated curves. We
evaluate the proposed method on different types of images: from highly
structured indoor environment to the natural scenes. Our experimental results
demonstrate satisfactory performance that can be potentially used for
subsequent big data processing: 3D scene reconstruction and location
recognition.
Advances in Human Action Recognition: A Survey
Authors: Guangchun Cheng, Yiwen Wan, Abdullah N. Saudagar, Kamesh Namuduri, Bill P. Buckles
Date: 2015-01-23 00:00:00
Tasks: Action Recognition, Retrieval, Survey, Temporal Action Localization, Video Retrieval

Human action recognition has been an important topic in computer vision due
to its many applications such as video surveillance, human machine interaction
and video retrieval. One core problem behind these applications is
automatically recognizing low-level actions and high-level activities of
interest. The former is usually the basis for the latter. This survey gives an
overview of the most recent advances in human action recognition during the
past several years, following a well-formed taxonomy proposed by a previous
survey. From this state-of-the-art survey, researchers can view a panorama of
progress in this area for future research.
Auto-encoders: reconstruction versus compression
Authors: Yann Ollivier
Date: 2014-03-30 00:00:00
Tasks: Denoising

We discuss the similarities and differences between training an auto-encoder
to minimize the reconstruction error, and training the same auto-encoder to
compress the data via a generative model. Minimizing a codelength for the data
using an auto-encoder is equivalent to minimizing the reconstruction error plus
some correcting terms which have an interpretation as either a denoising or
contractive property of the decoding function. These terms are related but not
identical to those used in denoising or contractive auto-encoders [Vincent et
al. 2010, Rifai et al. 2011]. In particular, the codelength viewpoint fully
determines an optimal noise level for the denoising criterion.