pwc-archive/papers-with-abstracts huggingface dataset:
Learning graphical models from the Glauber dynamics
Authors: Guy Bresler, David Gamarnik, Devavrat Shah
Date: 2014-10-28 00:00:00

In this paper we consider the problem of learning undirected graphical models
from data generated according to the Glauber dynamics. The Glauber dynamics is
a Markov chain that sequentially updates individual nodes (variables) in a
graphical model and it is frequently used to sample from the stationary
distribution (to which it converges given sufficient time). Additionally, the
Glauber dynamics is a natural dynamical model in a variety of settings. This
work deviates from the standard formulation of graphical model learning in the
literature, where one assumes access to i.i.d. samples from the distribution.
  Much of the research on graphical model learning has been directed towards
finding algorithms with low computational cost. As the main result of this
work, we establish that the problem of reconstructing binary pairwise graphical
models is computationally tractable when we observe the Glauber dynamics.
Specifically, we show that a binary pairwise graphical model on $p$ nodes with
maximum degree $d$ can be learned in time $f(d)p^2\log p$, for a function
$f(d)$, using nearly the information-theoretic minimum number of samples.
Egocentric Pose Recognition in Four Lines of Code
Authors: Gregory Rogez, James S. Supancic III, Deva Ramanan
Date: 2014-11-29 00:00:00
Tasks: Pose Estimation

We tackle the problem of estimating the 3D pose of an individual's upper
limbs (arms+hands) from a chest mounted depth-camera. Importantly, we consider
pose estimation during everyday interactions with objects. Past work shows that
strong pose+viewpoint priors and depth-based features are crucial for robust
performance. In egocentric views, hands and arms are observable within a well
defined volume in front of the camera. We call this volume an egocentric
workspace. A notable property is that hand appearance correlates with workspace
location. To exploit this correlation, we classify arm+hand configurations in a
global egocentric coordinate frame, rather than a local scanning window. This
greatly simplify the architecture and improves performance. We propose an
efficient pipeline which 1) generates synthetic workspace exemplars for
training using a virtual chest-mounted camera whose intrinsic parameters match
our physical camera, 2) computes perspective-aware depth features on this
entire volume and 3) recognizes discrete arm+hand pose classes through a sparse
multi-class SVM. Our method provides state-of-the-art hand pose recognition
performance from egocentric RGB-D images in real-time.
Online Learning and Profit Maximization from Revealed Preferences
Authors: Kareem Amin, Rachel Cummings, Lili Dworkin, Michael Kearns, Aaron Roth
Date: 2014-07-27 00:00:00
Tasks: Management

We consider the problem of learning from revealed preferences in an online
setting. In our framework, each period a consumer buys an optimal bundle of
goods from a merchant according to her (linear) utility function and current
prices, subject to a budget constraint. The merchant observes only the
purchased goods, and seeks to adapt prices to optimize his profits. We give an
efficient algorithm for the merchant's problem that consists of a learning
phase in which the consumer's utility function is (perhaps partially) inferred,
followed by a price optimization step. We also consider an alternative online
learning algorithm for the setting where prices are set exogenously, but the
merchant would still like to predict the bundle that will be bought by the
consumer for purposes of inventory or supply chain management. In contrast with
most prior work on the revealed preferences problem, we demonstrate that by
making stronger assumptions on the form of utility functions, efficient
algorithms for both learning and profit maximization are possible, even in
adaptive, online settings.
Bus Travel Time Predictions Using Additive Models
Authors: Matthias Kormaksson, Luciano Barbosa, Marcos R. Vieira, Bianca Zadrozny
Date: 2014-11-28 00:00:00
Tasks: Additive models

Many factors can affect the predictability of public bus services such as
traffic, weather and local events. Other aspects, such as day of week or hour
of day, may influence bus travel times as well, either directly or in
conjunction with other variables. However, the exact nature of such
relationships between travel times and predictor variables is, in most
situations, not known. In this paper we develop a framework that allows for
flexible modeling of bus travel times through the use of Additive Models. In
particular, we model travel times as a sum of linear as well as nonlinear terms
that are modeled as smooth functions of predictor variables. The proposed class
of models provides a principled statistical framework that is highly flexible
in terms of model building. The experimental results demonstrate uniformly
superior performance of our best model as compared to previous prediction
methods when applied to a very large GPS data set obtained from buses operating
in the city of Rio de Janeiro.
Effective Face Frontalization in Unconstrained Images
Authors: Tal Hassner, Shai Harel, Eran Paz, Roee Enbar
Date: 2014-11-28 00:00:00
Proceeding: CVPR 2015 6
Tasks: Face Recognition

"Frontalization" is the process of synthesizing frontal facing views of faces appearing in single unconstrained photos. Recent reports have suggested that this process may substantially boost the performance of face recognition systems. This, by transforming the challenging problem of recognizing faces viewed from unconstrained viewpoints to the easier problem of recognizing faces in constrained, forward facing poses. Previous frontalization methods did this by attempting to approximate 3D facial shapes for each query image. We observe that 3D face shape estimation from unconstrained photos may be a harder problem than frontalization and can potentially introduce facial misalignments. Instead, we explore the simpler approach of using a single, unmodified, 3D surface as an approximation to the shape of all input faces. We show that this leads to a straightforward, efficient and easy to implement method for frontalization. More importantly, it produces aesthetic new frontal views and is surprisingly effective when used for face recognition and gender estimation.
Adaptive Representations for Tracking Breaking News on Twitter
Authors: Igor Brigadir, Derek Greene, Pádraig Cunningham
Date: 2014-03-12 00:00:00
Tasks: Retrieval

Twitter is often the most up-to-date source for finding and tracking breaking
news stories. Therefore, there is considerable interest in developing filters
for tweet streams in order to track and summarize stories. This is a
non-trivial text analytics task as tweets are short, and standard retrieval
methods often fail as stories evolve over time. In this paper we examine the
effectiveness of adaptive mechanisms for tracking and summarizing breaking news
stories. We evaluate the effectiveness of these mechanisms on a number of
recent news events for which manually curated timelines are available.
Assessments based on ROUGE metrics indicate that an adaptive approaches are
best suited for tracking evolving stories on Twitter.
Predicting clicks in online display advertising with latent features and side-information
Authors: Bjarne Ørum Fruergaard
Date: 2014-11-28 00:00:00
Tasks: Click-Through Rate Prediction, Collaborative Filtering, Prediction

We review a method for click-through rate prediction based on the work of
Menon et al. [11], which combines collaborative filtering and matrix
factorization with a side-information model and fuses the outputs to proper
probabilities in [0,1]. In addition we provide details, both for the modeling
as well as the experimental part, that are not found elsewhere. We rigorously
test the performance on several test data sets from consecutive days in a
click-through rate prediction setup, in a manner which reflects a real-world
pipeline. Our results confirm that performance can be increased using latent
features, albeit the differences in the measures are small but significant.
Learning Face Representation from Scratch
Authors: Dong Yi, Zhen Lei, Shengcai Liao, Stan Z. Li
Date: 2014-11-28 00:00:00
Tasks: Face Recognition

Pushing by big data and deep convolutional neural network (CNN), the performance of face recognition is becoming comparable to human. Using private large scale training datasets, several groups achieve very high performance on LFW, i.e., 97% to 99%. While there are many open source implementations of CNN, none of large scale face dataset is publicly available. The current situation in the field of face recognition is that data is more important than algorithm. To solve this problem, this paper proposes a semi-automatical way to collect face images from Internet and builds a large scale dataset containing about 10,000 subjects and 500,000 images, called CASIAWebFace. Based on the database, we use a 11-layer CNN to learn discriminative representation and obtain state-of-theart accuracy on LFW and YTF. The publication of CASIAWebFace will attract more research groups entering this field and accelerate the development of face recognition in the wild.
On Rendering Synthetic Images for Training an Object Detector
Authors: Artem Rozantsev, Vincent Lepetit, Pascal Fua
Date: 2014-11-28 00:00:00
Tasks: Object

We propose a novel approach to synthesizing images that are effective for
training object detectors. Starting from a small set of real images, our
algorithm estimates the rendering parameters required to synthesize similar
images given a coarse 3D model of the target object. These parameters can then
be reused to generate an unlimited number of training images of the object of
interest in arbitrary 3D poses, which can then be used to increase
classification performances.
  A key insight of our approach is that the synthetically generated images
should be similar to real images, not in terms of image quality, but rather in
terms of features used during the detector training. We show in the context of
drone, plane, and car detection that using such synthetically generated images
yields significantly better performances than simply perturbing real images or
even synthesizing images in such way that they look very realistic, as is often
done when only limited amounts of training data are available.
A stronger null hypothesis for crossing dependencies
Authors: Ramon Ferrer-i-Cancho
Date: 2014-10-20 00:00:00
Tasks: Sentence

The syntactic structure of a sentence can be modeled as a tree where vertices
are words and edges indicate syntactic dependencies between words. It is
well-known that those edges normally do not cross when drawn over the sentence.
Here a new null hypothesis for the number of edge crossings of a sentence is
presented. That null hypothesis takes into account the length of the pair of
edges that may cross and predicts the relative number of crossings in random
trees with a small error, suggesting that a ban of crossings or a principle of
minimization of crossings are not needed in general to explain the origins of
non-crossing dependencies. Our work paves the way for more powerful null
hypotheses to investigate the origins of non-crossing dependencies in nature.
Efficient inference of overlapping communities in complex networks
Authors: Bjarne Ørum Fruergaard, Tue Herlau
Date: 2014-11-28 00:00:00
Tasks: Attribute, Link Prediction

We discuss two views on extending existing methods for complex network
modeling which we dub the communities first and the networks first view,
respectively. Inspired by the networks first view that we attribute to White,
Boorman, and Breiger (1976)[1], we formulate the multiple-networks stochastic
blockmodel (MNSBM), which seeks to separate the observed network into
subnetworks of different types and where the problem of inferring structure in
each subnetwork becomes easier. We show how this model is specified in a
generative Bayesian framework where parameters can be inferred efficiently
using Gibbs sampling. The result is an effective multiple-membership model
without the drawbacks of introducing complex definitions of "groups" and how
they interact. We demonstrate results on the recovery of planted structure in
synthetic networks and show very encouraging results on link prediction
performances using multiple-networks models on a number of real-world network
data sets.
V-variable image compression
Authors: Franklin Mendivil, Örjan Stenflo
Date: 2014-11-28 00:00:00
Tasks: Image Compression

V-variable fractals, where $V$ is a positive integer, are intuitively
fractals with at most $V$ different "forms" or "shapes" at all levels of
magnification. In this paper we describe how V-variable fractals can be used
for the purpose of image compression.
Lazier Than Lazy Greedy
Authors: Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrak, Andreas Krause
Date: 2014-09-28 00:00:00
Tasks: Clustering, Data Summarization

Is it possible to maximize a monotone submodular function faster than the
widely used lazy greedy algorithm (also known as accelerated greedy), both in
theory and practice? In this paper, we develop the first linear-time algorithm
for maximizing a general monotone submodular function subject to a cardinality
constraint. We show that our randomized algorithm, STOCHASTIC-GREEDY, can
achieve a $(1-1/e-\varepsilon)$ approximation guarantee, in expectation, to the
optimum solution in time linear in the size of the data and independent of the
cardinality constraint. We empirically demonstrate the effectiveness of our
algorithm on submodular functions arising in data summarization, including
training large-scale kernel methods, exemplar-based clustering, and sensor
placement. We observe that STOCHASTIC-GREEDY practically achieves the same
utility value as lazy greedy but runs much faster. More surprisingly, we
observe that in many practical scenarios STOCHASTIC-GREEDY does not evaluate
the whole fraction of data points even once and still achieves
indistinguishable results compared to lazy greedy.
Coarse-grained Cross-lingual Alignment of Comparable Texts with Topic Models and Encyclopedic Knowledge
Authors: Vivi Nastase, Angela Fahrni
Date: 2014-11-28 00:00:00
Tasks: Topic Models

We present a method for coarse-grained cross-lingual alignment of comparable
texts: segments consisting of contiguous paragraphs that discuss the same theme
(e.g. history, economy) are aligned based on induced multilingual topics. The
method combines three ideas: a two-level LDA model that filters out words that
do not convey themes, an HMM that models the ordering of themes in the
collection of documents, and language-independent concept annotations to serve
as a cross-language bridge and to strengthen the connection between paragraphs
in the same segment through concept relations. The method is evaluated on
English and French data previously used for monolingual alignment. The results
show state-of-the-art performance in both monolingual and cross-lingual
settings.
Learning with Algebraic Invariances, and the Invariant Kernel Trick
Authors: Franz J. Király, Andreas Ziehe, Klaus-Robert Müller
Date: 2014-11-28 00:00:00
Tasks: Clustering

When solving data analysis problems it is important to integrate prior
knowledge and/or structural invariances. This paper contributes by a novel
framework for incorporating algebraic invariance structure into kernels. In
particular, we show that algebraic properties such as sign symmetries in data,
phase independence, scaling etc. can be included easily by essentially
performing the kernel trick twice. We demonstrate the usefulness of our theory
in simulations on selected applications such as sign-invariant spectral
clustering and underdetermined ICA.
Two Gaussian Approaches to Black-Box Optomization
Authors: Lukáš Bajer, Martin Holeňa
Date: 2014-11-28 00:00:00
Tasks: Gaussian Processes, Vocal Bursts Valence Prediction

Outline of several strategies for using Gaussian processes as surrogate
models for the covariance matrix adaptation evolution strategy (CMA-ES).
Cross-Modal Learning via Pairwise Constraints
Authors: Ran He, Man Zhang, Liang Wang, Ye Ji, Qiyue Yin
Date: 2014-11-28 00:00:00
Tasks: Clustering, Retrieval

In multimedia applications, the text and image components in a web document
form a pairwise constraint that potentially indicates the same semantic
concept. This paper studies cross-modal learning via the pairwise constraint,
and aims to find the common structure hidden in different modalities. We first
propose a compound regularization framework to deal with the pairwise
constraint, which can be used as a general platform for developing cross-modal
algorithms. For unsupervised learning, we propose a cross-modal subspace
clustering method to learn a common structure for different modalities. For
supervised learning, to reduce the semantic gap and the outliers in pairwise
constraints, we propose a cross-modal matching method based on compound ?21
regularization along with an iteratively reweighted algorithm to find the
global optimum. Extensive experiments demonstrate the benefits of joint text
and image modeling with semantically induced pairwise constraints, and show
that the proposed cross-modal methods can further reduce the semantic gap
between different modalities and improve the clustering/retrieval accuracy.
Flying Objects Detection from a Single Moving Camera
Authors: Artem Rozantsev, Vincent Lepetit, Pascal Fua
Date: 2014-11-27 00:00:00
Proceeding: CVPR 2015 6
Tasks: Collision Avoidance, General Classification, regression

We propose an approach to detect flying objects such as UAVs and aircrafts
when they occupy a small portion of the field of view, possibly moving against
complex backgrounds, and are filmed by a camera that itself moves.
  Solving such a difficult problem requires combining both appearance and
motion cues. To this end we propose a regression-based approach to motion
stabilization of local image patches that allows us to achieve effective
classification on spatio-temporal image cubes and outperform state-of-the-art
techniques.
  As the problem is relatively new, we collected two challenging datasets for
UAVs and Aircrafts, which can be used as benchmarks for flying objects
detection and vision-guided collision avoidance.
Features in Concert: Discriminative Feature Selection meets Unsupervised Clustering
Authors: Marius Leordeanu, Alexandra Radu, Rahul Sukthankar
Date: 2014-11-27 00:00:00
Tasks: Clustering, feature selection

Feature selection is an essential problem in computer vision, important for
category learning and recognition. Along with the rapid development of a wide
variety of visual features and classifiers, there is a growing need for
efficient feature selection and combination methods, to construct powerful
classifiers for more complex and higher-level recognition tasks. We propose an
algorithm that efficiently discovers sparse, compact representations of input
features or classifiers, from a vast sea of candidates, with important
optimality properties, low computational cost and excellent accuracy in
practice. Different from boosting, we start with a discriminant linear
classification formulation that encourages sparse solutions. Then we obtain an
equivalent unsupervised clustering problem that jointly discovers ensembles of
diverse features. They are independently valuable but even more powerful when
united in a cluster of classifiers. We evaluate our method on the task of
large-scale recognition in video and show that it significantly outperforms
classical selection approaches, such as AdaBoost and greedy forward-backward
selection, and powerful classifiers such as SVMs, in speed of training and
performance, especially in the case of limited training data.
A Nonparametric Bayesian Approach to Uncovering Rat Hippocampal Population Codes During Spatial Navigation
Authors: Scott W. Linderman, Matthew J. Johnson, Matthew A. Wilson, Zhe Chen
Date: 2014-11-27 00:00:00
Tasks: Bayesian Inference, Model Selection

Rodent hippocampal population codes represent important spatial information
about the environment during navigation. Several computational methods have
been developed to uncover the neural representation of spatial topology
embedded in rodent hippocampal ensemble spike activity. Here we extend our
previous work and propose a nonparametric Bayesian approach to infer rat
hippocampal population codes during spatial navigation. To tackle the model
selection problem, we leverage a nonparametric Bayesian model. Specifically, to
analyze rat hippocampal ensemble spiking activity, we apply a hierarchical
Dirichlet process-hidden Markov model (HDP-HMM) using two Bayesian inference
methods, one based on Markov chain Monte Carlo (MCMC) and the other based on
variational Bayes (VB). We demonstrate the effectiveness of our Bayesian
approaches on recordings from a freely-behaving rat navigating in an open field
environment. We find that MCMC-based inference with Hamiltonian Monte Carlo
(HMC) hyperparameter sampling is flexible and efficient, and outperforms VB and
MCMC approaches with hyperparameters set by empirical Bayes.
On color image quality assessment using natural image statistics
Authors: Mounir Omari, Mohammed El Hassouni, Hocine Cherifi, Abdelkaher Ait Abdelouahad
Date: 2014-11-27 00:00:00
Tasks: Image Quality Assessment

Color distortion can introduce a significant damage in visual quality
perception, however, most of existing reduced-reference quality measures are
designed for grayscale images. In this paper, we consider a basic extension of
well-known image-statistics based quality assessment measures to color images.
In order to evaluate the impact of color information on the measures
efficiency, two color spaces are investigated: RGB and CIELAB. Results of an
extensive evaluation using TID 2013 benchmark demonstrates that significant
improvement can be achieved for a great number of distortion type when the
CIELAB color representation is used.
Complexity of Equivalence and Learning for Multiplicity Tree Automata
Authors: Ines Marusic, James Worrell
Date: 2014-05-02 00:00:00

We consider the complexity of equivalence and learning for multiplicity tree
automata, i.e., weighted tree automata over a field. We first show that the
equivalence problem is logspace equivalent to polynomial identity testing, the
complexity of which is a longstanding open problem. Secondly, we derive lower
bounds on the number of queries needed to learn multiplicity tree automata in
Angluin's exact learning model, over both arbitrary and fixed fields.
  Habrard and Oncina (2006) give an exact learning algorithm for multiplicity
tree automata, in which the number of queries is proportional to the size of
the target automaton and the size of a largest counterexample, represented as a
tree, that is returned by the Teacher. However, the smallest
tree-counterexample may be exponential in the size of the target automaton.
Thus the above algorithm does not run in time polynomial in the size of the
target automaton, and has query complexity exponential in the lower bound.
  Assuming a Teacher that returns minimal DAG representations of
counterexamples, we give a new exact learning algorithm whose query complexity
is quadratic in the target automaton size, almost matching the lower bound, and
improving the best previously-known algorithm by an exponential factor.