pwc-archive/papers-with-abstracts huggingface dataset:
How Robust are Reconstruction Thresholds for Community Detection?
Authors: Ankur Moitra, William Perry, Alexander S. Wein
Date: 2015-11-04 00:00:00
Tasks: Clustering, Community Detection, Stochastic Block Model

The stochastic block model is one of the oldest and most ubiquitous models
for studying clustering and community detection. In an exciting sequence of
developments, motivated by deep but non-rigorous ideas from statistical
physics, Decelle et al. conjectured a sharp threshold for when community
detection is possible in the sparse regime. Mossel, Neeman and Sly and
Massoulie proved the conjecture and gave matching algorithms and lower bounds.
  Here we revisit the stochastic block model from the perspective of semirandom
models where we allow an adversary to make `helpful' changes that strengthen
ties within each community and break ties between them. We show a surprising
result that these `helpful' changes can shift the information-theoretic
threshold, making the community detection problem strictly harder. We
complement this by showing that an algorithm based on semidefinite programming
(which was known to get close to the threshold) continues to work in the
semirandom model (even for partial recovery). This suggests that algorithms
based on semidefinite programming are robust in ways that any algorithm meeting
the information-theoretic threshold cannot be.
  These results point to an interesting new direction: Can we find robust,
semirandom analogues to some of the classical, average-case thresholds in
statistics? We also explore this question in the broadcast tree model, and we
show that the viewpoint of semirandom models can help explain why some
algorithms are preferred to others in practice, in spite of the gaps in their
statistical performance on random models.
The SVM Classifier Based on the Modified Particle Swarm Optimization
Authors: L. Demidova, E. Nikulchev, Yu. Sokolova
Date: 2016-03-21 00:00:00
Tasks: General Classification

The problem of development of the SVM classifier based on the modified
particle swarm optimization has been considered. This algorithm carries out the
simultaneous search of the kernel function type, values of the kernel function
parameters and value of the regularization parameter for the SVM classifier.
Such SVM classifier provides the high quality of data classification. The idea
of particles' {\guillemotleft}regeneration{\guillemotright} is put on the basis
of the modified particle swarm optimization algorithm. At the realization of
this idea, some particles change their kernel function type to the one which
corresponds to the particle with the best value of the classification accuracy.
The offered particle swarm optimization algorithm allows reducing the time
expenditures for development of the SVM classifier. The results of experimental
studies confirm the efficiency of this algorithm.
Facial Landmark Detection with Tweaked Convolutional Neural Networks
Authors: Yue Wu, Tal Hassner, KangGeon Kim, Gerard Medioni, Prem Natarajan
Date: 2015-11-12 00:00:00
Tasks: Face Verification, Facial Landmark Detection, regression

We present a novel convolutional neural network (CNN) design for facial
landmark coordinate regression. We examine the intermediate features of a
standard CNN trained for landmark detection and show that features extracted
from later, more specialized layers capture rough landmark locations. This
provides a natural means of applying differential treatment midway through the
network, tweaking processing based on facial alignment. The resulting Tweaked
CNN model (TCNN) harnesses the robustness of CNNs for landmark detection, in an
appearance-sensitive manner without training multi-part or multi-scale models.
Our results on standard face landmark detection and face verification
benchmarks show TCNN to surpasses previously published performances by wide
margins.
Action-Affect Classification and Morphing using Multi-Task Representation Learning
Authors: Timothy J. Shields, Mohamed R. Amer, Max Ehrlich, Amir Tamrakar
Date: 2016-03-21 00:00:00
Tasks: Classification, General Classification, Multi-Task Learning, Representation Learning, Time Series, Time Series Analysis

Most recent work focused on affect from facial expressions, and not as much
on body. This work focuses on body affect analysis. Affect does not occur in
isolation. Humans usually couple affect with an action in natural interactions;
for example, a person could be talking and smiling. Recognizing body affect in
sequences requires efficient algorithms to capture both the micro movements
that differentiate between happy and sad and the macro variations between
different actions. We depart from traditional approaches for time-series data
analytics by proposing a multi-task learning model that learns a shared
representation that is well-suited for action-affect classification as well as
generation. For this paper we choose Conditional Restricted Boltzmann Machines
to be our building block. We propose a new model that enhances the CRBM model
with a factored multi-task component to become Multi-Task Conditional
Restricted Boltzmann Machines (MTCRBMs). We evaluate our approach on two
publicly available datasets, the Body Affect dataset and the Tower Game
dataset, and show superior classification performance improvement over the
state-of-the-art, as well as the generative abilities of our model.
Two Timescale Stochastic Approximation with Controlled Markov noise and Off-policy temporal difference learning
Authors: Prasenjit Karmakar, Shalabh Bhatnagar
Date: 2015-03-31 00:00:00

We present for the first time an asymptotic convergence analysis of two
time-scale stochastic approximation driven by `controlled' Markov noise. In
particular, both the faster and slower recursions have non-additive controlled
Markov noise components in addition to martingale difference noise. We analyze
the asymptotic behavior of our framework by relating it to limiting
differential inclusions in both time-scales that are defined in terms of the
ergodic occupation measures associated with the controlled Markov processes.
Finally, we present a solution to the off-policy convergence problem for
temporal difference learning with linear function approximation, using our
results.
A Comparison Study of Nonlinear Kernels
Authors: Ping Li
Date: 2016-03-21 00:00:00

In this paper, we compare 5 different nonlinear kernels: min-max, RBF, fRBF
(folded RBF), acos, and acos-$\chi^2$, on a wide range of publicly available
datasets. The proposed fRBF kernel performs very similarly to the RBF kernel.
Both RBF and fRBF kernels require an important tuning parameter ($\gamma$).
Interestingly, for a significant portion of the datasets, the min-max kernel
outperforms the best-tuned RBF/fRBF kernels. The acos kernel and acos-$\chi^2$
kernel also perform well in general and in some datasets achieve the best
accuracies.
  One crucial issue with the use of nonlinear kernels is the excessive
computational and memory cost. These days, one increasingly popular strategy is
to linearize the kernels through various randomization algorithms. In our
study, the randomization method for the min-max kernel demonstrates excellent
performance compared to the randomization methods for other types of nonlinear
kernels, measured in terms of the number of nonzero terms in the transformed
dataset.
  Our study provides evidence for supporting the use of the min-max kernel and
the corresponding randomized linearization method (i.e., the so-called "0-bit
CWS"). Furthermore, the results motivate at least two directions for future
research: (i) To develop new (and linearizable) nonlinear kernels for better
accuracies; and (ii) To develop better linearization algorithms for improving
the current linearization methods for the RBF kernel, the acos kernel, and the
acos-$\chi^2$ kernel. One attempt is to combine the min-max kernel with the
acos kernel or the acos-$\chi^2$ kernel. The advantages of these two new and
tuning-free nonlinear kernels are demonstrated vias our extensive experiments.
Deep video gesture recognition using illumination invariants
Authors: Otkrist Gupta, Dan Raviv, Ramesh Raskar
Date: 2016-03-21 00:00:00
Tasks: Gesture Recognition

In this paper we present architectures based on deep neural nets for gesture
recognition in videos, which are invariant to local scaling. We amalgamate
autoencoder and predictor architectures using an adaptive weighting scheme
coping with a reduced size labeled dataset, while enriching our models from
enormous unlabeled sets. We further improve robustness to lighting conditions
by introducing a new adaptive filer based on temporal local scale
normalization. We provide superior results over known methods, including recent
reported approaches based on neural nets.
Phase transitions and sample complexity in Bayes-optimal matrix factorization
Authors: Yoshiyuki Kabashima, Florent Krzakala, Marc Mézard, Ayaka Sakata, Lenka Zdeborová
Date: 2014-02-06 00:00:00
Tasks: blind source separation, Dictionary Learning, Low-Rank Matrix Completion, Matrix Completion, Representation Learning

We analyse the matrix factorization problem. Given a noisy measurement of a
product of two matrices, the problem is to estimate back the original matrices.
It arises in many applications such as dictionary learning, blind matrix
calibration, sparse principal component analysis, blind source separation, low
rank matrix completion, robust principal component analysis or factor analysis.
It is also important in machine learning: unsupervised representation learning
can often be studied through matrix factorization. We use the tools of
statistical mechanics - the cavity and replica methods - to analyze the
achievability and computational tractability of the inference problems in the
setting of Bayes-optimal inference, which amounts to assuming that the two
matrices have random independent elements generated from some known
distribution, and this information is available to the inference algorithm. In
this setting, we compute the minimal mean-squared-error achievable in principle
in any computational time, and the error that can be achieved by an efficient
approximate message passing algorithm. The computation is based on the
asymptotic state-evolution analysis of the algorithm. The performance that our
analysis predicts, both in terms of the achieved mean-squared-error, and in
terms of sample complexity, is extremely promising and motivating for a further
development of the algorithm.
Static and Dynamic Feature Selection in Morphosyntactic Analyzers
Authors: Bernd Bohnet, Miguel Ballesteros, Ryan Mcdonald, Joakim Nivre
Date: 2016-03-21 00:00:00
Tasks: feature selection

We study the use of greedy feature selection methods for morphosyntactic
tagging under a number of different conditions. We compare a static ordering of
features to a dynamic ordering based on mutual information statistics, and we
apply the techniques to standalone taggers as well as joint systems for tagging
and parsing. Experiments on five languages show that feature selection can
result in more compact models as well as higher accuracy under all conditions,
but also that a dynamic ordering works better than a static ordering and that
joint systems benefit more than standalone taggers. We also show that the same
techniques can be used to select which morphosyntactic categories to predict in
order to maximize syntactic accuracy in a joint system. Our final results
represent a substantial improvement of the state of the art for several
languages, while at the same time reducing both the number of features and the
running time by up to 80% in some cases.
Instance Influence Estimation for Hyperspectral Target Signature Characterization using Extended Functions of Multiple Instances
Authors: Sheng Zou, Alina Zare
Date: 2016-03-21 00:00:00
Tasks: Multiple Instance Learning

The Extended Functions of Multiple Instances (eFUMI) algorithm is a
generalization of Multiple Instance Learning (MIL). In eFUMI, only bag level
(i.e. set level) labels are needed to estimate target signatures from mixed
data. The training bags in eFUMI are labeled positive if any data point in a
bag contains or represents any proportion of the target signature and are
labeled as a negative bag if all data points in the bag do not represent any
target. From these imprecise labels, eFUMI has been shown to be effective at
estimating target signatures in hyperspectral subpixel target detection
problems. One motivating scenario for the use of eFUMI is where an analyst
circles objects/regions of interest in a hyperspectral scene such that the
target signatures of these objects can be estimated and be used to determine
whether other instances of the object appear elsewhere in the image collection.
The regions highlighted by the analyst serve as the imprecise labels for eFUMI.
Often, an analyst may want to iteratively refine their imprecise labels. In
this paper, we present an approach for estimating the influence on the
estimated target signature if the label for a particular input data point is
modified. This "instance influence estimation" guides an analyst to focus on
(re-)labeling the data points that provide the largest change in the resulting
estimated target signature and, thus, reduce the amount of time an analyst
needs to spend refining the labels for a hyperspectral scene. Results are shown
on real hyperspectral sub-pixel target detection data sets.
A System for Probabilistic Linking of Thesauri and Classification Systems
Authors: Lisa Posch, Philipp Schaer, Arnim Bleier, Markus Strohmaier
Date: 2016-03-21 00:00:00
Tasks: Classification, General Classification

This paper presents a system which creates and visualizes probabilistic
semantic links between concepts in a thesaurus and classes in a classification
system. For creating the links, we build on the Polylingual Labeled Topic Model
(PLL-TM). PLL-TM identifies probable thesaurus descriptors for each class in
the classification system by using information from the natural language text
of documents, their assigned thesaurus descriptors and their designated
classes. The links are then presented to users of the system in an interactive
visualization, providing them with an automatically generated overview of the
relations between the thesaurus and the classification system.
Hard-Clustering with Gaussian Mixture Models
Authors: Johannes Blömer, Sascha Brauer, Kathrin Bujna
Date: 2016-03-21 00:00:00
Tasks: Clustering, parameter estimation

Training the parameters of statistical models to describe a given data set is
a central task in the field of data mining and machine learning. A very popular
and powerful way of parameter estimation is the method of maximum likelihood
estimation (MLE). Among the most widely used families of statistical models are
mixture models, especially, mixtures of Gaussian distributions. A popular
hard-clustering variant of the MLE problem is the so-called complete-data
maximum likelihood estimation (CMLE) method. The standard approach to solve the
CMLE problem is the Classification-Expectation-Maximization (CEM) algorithm.
Unfortunately, it is only guaranteed that the algorithm converges to some
(possibly arbitrarily poor) stationary point of the objective function.
  In this paper, we present two algorithms for a restricted version of the CMLE
problem. That is, our algorithms approximate reasonable solutions to the CMLE
problem which satisfy certain natural properties. Moreover, they compute
solutions whose cost (i.e. complete-data log-likelihood values) are at most a
factor $(1+\epsilon)$ worse than the cost of the solutions that we search for.
Note the CMLE problem in its most general, i.e. unrestricted, form is not well
defined and allows for trivial optimal solutions that can be thought of as
degenerated solutions.
Illumination-invariant image mosaic calculation based on logarithmic search
Authors: Wolfgang Konen
Date: 2016-03-21 00:00:00
Tasks: Optical Flow Estimation

This technical report describes an improved image mosaicking algorithm. It is
based on Jain's logarithmic search algorithm [Jain 1981] which is coupled to
the method of Kourogi (1999} for matching images in a video sequence.
Logarithmic search has a better invariance against illumination changes than
the original optical-flow-based method of Kourogi.
Descriptor transition tables for object retrieval using unconstrained cluttered video acquired using a consumer level handheld mobile device
Authors: Warren Rieutort-Louis, Ognjen Arandjelovic
Date: 2016-03-16 00:00:00
Tasks: Object, Retrieval

Visual recognition and vision based retrieval of objects from large databases
are tasks with a wide spectrum of potential applications. In this paper we
propose a novel recognition method from video sequences suitable for retrieval
from databases acquired in highly unconstrained conditions e.g. using a mobile
consumer-level device such as a phone. On the lowest level, we represent each
sequence as a 3D mesh of densely packed local appearance descriptors. While
image plane geometry is captured implicitly by a large overlap of neighbouring
regions from which the descriptors are extracted, 3D information is extracted
by means of a descriptor transition table, learnt from a single sequence for
each known gallery object. These allow us to connect local descriptors along
the 3rd dimension (which corresponds to viewpoint changes), thus resulting in a
set of variable length Markov chains for each video. The matching of two sets
of such chains is formulated as a statistical hypothesis test, whereby a subset
of each is chosen to maximize the likelihood that the corresponding video
sequences show the same object. The effectiveness of the proposed algorithm is
empirically evaluated on the Amsterdam Library of Object Images and a new
highly challenging video data set acquired using a mobile phone. On both data
sets our method is shown to be successful in recognition in the presence of
background clutter and large viewpoint changes.
Appearance Harmonization for Single Image Shadow Removal
Authors: Liqian Ma, Jue Wang, Eli Shechtman, Kalyan Sunkavalli, Shi-Min Hu
Date: 2016-03-21 00:00:00
Tasks: Image Generation, Image Shadow Removal, Shadow Removal

Shadows often create unwanted artifacts in photographs, and removing them can
be very challenging. Previous shadow removal methods often produce de-shadowed
regions that are visually inconsistent with the rest of the image. In this work
we propose a fully automatic shadow region harmonization approach that improves
the appearance compatibility of the de-shadowed region as typically produced by
previous methods. It is based on a shadow-guided patch-based image synthesis
approach that reconstructs the shadow region using patches sampled from
non-shadowed regions. The result is then refined based on the reconstruction
confidence to handle unique image patterns. Many shadow removal results and
comparisons are show the effectiveness of our improvement. Quantitative
evaluation on a benchmark dataset suggests that our automatic shadow
harmonization approach effectively improves upon the state-of-the-art.
Analysis of Crowdsourced Sampling Strategies for HodgeRank with Sparse Random Graphs
Authors: Braxton Osting, Jiechao Xiong, Qianqian Xu, Yuan YAO
Date: 2015-02-28 00:00:00
Tasks: Informativeness

Crowdsourcing platforms are now extensively used for conducting subjective
pairwise comparison studies. In this setting, a pairwise comparison dataset is
typically gathered via random sampling, either \emph{with} or \emph{without}
replacement. In this paper, we use tools from random graph theory to analyze
these two random sampling methods for the HodgeRank estimator. Using the
Fiedler value of the graph as a measurement for estimator stability
(informativeness), we provide a new estimate of the Fiedler value for these two
random graph models. In the asymptotic limit as the number of vertices tends to
infinity, we prove the validity of the estimate. Based on our findings, for a
small number of items to be compared, we recommend a two-stage sampling
strategy where a greedy sampling method is used initially and random sampling
\emph{without} replacement is used in the second stage. When a large number of
items is to be compared, we recommend random sampling with replacement as this
is computationally inexpensive and trivially parallelizable. Experiments on
synthetic and real-world datasets support our analysis.
Predictive Interval Models for Non-parametric Regression
Authors: Mohammad Ghasemi Hamed, Mathieu Serrurier, Nicolas Durand
Date: 2014-02-24 00:00:00
Tasks: Prediction, regression

Having a regression model, we are interested in finding two-sided intervals
that are guaranteed to contain at least a desired proportion of the conditional
distribution of the response variable given a specific combination of
predictors. We name such intervals predictive intervals. This work presents a
new method to find two-sided predictive intervals for non-parametric least
squares regression without the homoscedasticity assumption. Our predictive
intervals are built by using tolerance intervals on prediction errors in the
query point's neighborhood. We proposed a predictive interval model test and we
also used it as a constraint in our hyper-parameter tuning algorithm. This
gives an algorithm that finds the smallest reliable predictive intervals for a
given dataset. We also introduce a measure for comparing different interval
prediction methods yielding intervals having different size and coverage. These
experiments show that our methods are more reliable, effective and precise than
other interval prediction methods.
STDP as presynaptic activity times rate of change of postsynaptic activity
Authors: Yoshua Bengio, Thomas Mesnard, Asja Fischer, Saizheng Zhang, Yuhuai Wu
Date: 2015-09-19 00:00:00

We introduce a weight update formula that is expressed only in terms of
firing rates and their derivatives and that results in changes consistent with
those associated with spike-timing dependent plasticity (STDP) rules and
biological observations, even though the explicit timing of spikes is not
needed. The new rule changes a synaptic weight in proportion to the product of
the presynaptic firing rate and the temporal rate of change of activity on the
postsynaptic side. These quantities are interesting for studying theoretical
explanation for synaptic changes from a machine learning perspective. In
particular, if neural dynamics moved neural activity towards reducing some
objective function, then this STDP rule would correspond to stochastic gradient
descent on that objective function.
Analyzing coevolutionary games with dynamic fitness landscapes
Authors: Hendrik Richter
Date: 2016-03-21 00:00:00

Coevolutionary games cast players that may change their strategies as well as
their networks of interaction. In this paper a framework is introduced for
describing coevolutionary game dynamics by landscape models. It is shown that
coevolutionary games invoke dynamic landscapes. Numerical experiments are shown
for a prisoner's dilemma (PD) and a snow drift (SD) game that both use either
birth-death (BD) or death-birth (DB) strategy updating. The resulting
landscapes are analyzed with respect to modality and ruggedness