pwc-archive/papers-with-abstracts huggingface dataset:
Best-First and Depth-First Minimax Search in Practice
Authors: Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin
Date: 2015-05-07 00:00:00

Most practitioners use a variant of the Alpha-Beta algorithm, a simple
depth-first pro- cedure, for searching minimax trees. SSS*, with its best-first
search strategy, reportedly offers the potential for more efficient search.
However, the complex formulation of the al- gorithm and its alleged excessive
memory requirements preclude its use in practice. For two decades, the search
efficiency of "smart" best-first SSS* has cast doubt on the effectiveness of
"dumb" depth-first Alpha-Beta. This paper presents a simple framework for
calling Alpha-Beta that allows us to create a variety of algorithms, including
SSS* and DUAL*. In effect, we formulate a best-first algorithm using
depth-first search. Expressed in this framework SSS* is just a special case of
Alpha-Beta, solving all of the perceived drawbacks of the algorithm. In
practice, Alpha-Beta variants typically evaluate less nodes than SSS*. A new
instance of this framework, MTD(f), out-performs SSS* and NegaScout, the
Alpha-Beta variant of choice by practitioners.
Fast Differentially Private Matrix Factorization
Authors: Ziqi Liu, Yu-Xiang Wang, Alexander J. Smola
Date: 2015-05-06 00:00:00
Tasks: Collaborative Filtering, CPU

Differentially private collaborative filtering is a challenging task, both in
terms of accuracy and speed. We present a simple algorithm that is provably
differentially private, while offering good performance, using a novel
connection of differential privacy to Bayesian posterior sampling via
Stochastic Gradient Langevin Dynamics. Due to its simplicity the algorithm
lends itself to efficient implementation. By careful systems design and by
exploiting the power law behavior of the data to maximize CPU cache bandwidth
we are able to generate 1024 dimensional models at a rate of 8.5 million
recommendations per second on a single PC.
Filter characteristics in image decomposition with singular spectrum analysis
Authors: Kenji Kume, Naoko Nose-Togawa
Date: 2015-05-07 00:00:00
Tasks: Denoising, Image Denoising, Time Series, Time Series Analysis

Singular spectrum analysis is developed as a nonparametric spectral
decomposition of a time series. It can be easily extended to the decomposition
of multidimensional lattice-like data through the filtering interpretation. In
this viewpoint, the singular spectrum analysis can be understood as the
adaptive and optimal generation of the filters and their two-step
point-symmetric operation to the original data. In this paper, we point out
that, when applied to the multidimensional data, the adaptively generated
filters exhibit symmetry properties resulting from the bisymmetric nature of
the lag-covariance matrices. The eigenvectors of the lag-covariance matrix are
either symmetric or antisymmetric, and for the 2D image data, these lead to the
differential-type filters with even- or odd-order derivatives. The dominant
filter is a smoothing filter, reflecting the dominance of low-frequency
components of the photo images. The others are the edge-enhancement or the
noise filters corresponding to the band-pass or the high-pass filters. The
implication of the decomposition to the image denoising is briefly discussed.
Learning and Optimization with Submodular Functions
Authors: Bharath Sankaran, Marjan Ghazvininejad, Xinran He, David Kale, Liron Cohen
Date: 2015-05-07 00:00:00

In many naturally occurring optimization problems one needs to ensure that
the definition of the optimization problem lends itself to solutions that are
tractable to compute. In cases where exact solutions cannot be computed
tractably, it is beneficial to have strong guarantees on the tractable
approximate solutions. In order operate under these criterion most optimization
problems are cast under the umbrella of convexity or submodularity. In this
report we will study design and optimization over a common class of functions
called submodular functions. Set functions, and specifically submodular set
functions, characterize a wide variety of naturally occurring optimization
problems, and the property of submodularity of set functions has deep
theoretical consequences with wide ranging applications. Informally, the
property of submodularity of set functions concerns the intuitive "principle of
diminishing returns. This property states that adding an element to a smaller
set has more value than adding it to a larger set. Common examples of
submodular monotone functions are entropies, concave functions of cardinality,
and matroid rank functions; non-monotone examples include graph cuts, network
flows, and mutual information.
  In this paper we will review the formal definition of submodularity; the
optimization of submodular functions, both maximization and minimization; and
finally discuss some applications in relation to learning and reasoning using
submodular functions.
Adaptive Nonparametric Image Parsing
Authors: Tam V. Nguyen, Can-Yi Lu, Jose Sepulveda, Shuicheng Yan
Date: 2015-05-07 00:00:00
Tasks: Retrieval

In this paper, we present an adaptive nonparametric solution to the image
parsing task, namely annotating each image pixel with its corresponding
category label. For a given test image, first, a locality-aware retrieval set
is extracted from the training data based on super-pixel matching similarities,
which are augmented with feature extraction for better differentiation of local
super-pixels. Then, the category of each super-pixel is initialized by the
majority vote of the $k$-nearest-neighbor super-pixels in the retrieval set.
Instead of fixing $k$ as in traditional non-parametric approaches, here we
propose a novel adaptive nonparametric approach which determines the
sample-specific k for each test image. In particular, $k$ is adaptively set to
be the number of the fewest nearest super-pixels which the images in the
retrieval set can use to get the best category prediction. Finally, the initial
super-pixel labels are further refined by contextual smoothing. Extensive
experiments on challenging datasets demonstrate the superiority of the new
solution over other state-of-the-art nonparametric solutions.
Semi-Orthogonal Multilinear PCA with Relaxed Start
Authors: Qiquan Shi, Haiping Lu
Date: 2015-04-30 00:00:00

Principal component analysis (PCA) is an unsupervised method for learning
low-dimensional features with orthogonal projections. Multilinear PCA methods
extend PCA to deal with multidimensional data (tensors) directly via
tensor-to-tensor projection or tensor-to-vector projection (TVP). However,
under the TVP setting, it is difficult to develop an effective multilinear PCA
method with the orthogonality constraint. This paper tackles this problem by
proposing a novel Semi-Orthogonal Multilinear PCA (SO-MPCA) approach. SO-MPCA
learns low-dimensional features directly from tensors via TVP by imposing the
orthogonality constraint in only one mode. This formulation results in more
captured variance and more learned features than full orthogonality. For better
generalization, we further introduce a relaxed start (RS) strategy to get
SO-MPCA-RS by fixing the starting projection vectors, which increases the bias
and reduces the variance of the learning model. Experiments on both face (2D)
and gait (3D) data demonstrate that SO-MPCA-RS outperforms other competing
algorithms on the whole, and the relaxed start strategy is also effective for
other TVP-based PCA methods.
Graphical Potential Games
Authors: Luis E. Ortiz
Date: 2015-05-06 00:00:00
Tasks: Image Segmentation, Semantic Segmentation

Potential games, originally introduced in the early 1990's by Lloyd Shapley,
the 2012 Nobel Laureate in Economics, and his colleague Dov Monderer, are a
very important class of models in game theory. They have special properties
such as the existence of Nash equilibria in pure strategies. This note
introduces graphical versions of potential games. Special cases of graphical
potential games have already found applicability in many areas of science and
engineering beyond economics, including artificial intelligence, computer
vision, and machine learning. They have been effectively applied to the study
and solution of important real-world problems such as routing and congestion in
networks, distributed resource allocation (e.g., public goods), and
relaxation-labeling for image segmentation. Implicit use of graphical potential
games goes back at least 40 years. Several classes of games considered standard
in the literature, including coordination games, local interaction games,
lattice games, congestion games, and party-affiliation games, are instances of
graphical potential games. This note provides several characterizations of
graphical potential games by leveraging well-known results from the literature
on probabilistic graphical models. A major contribution of the work presented
here that particularly distinguishes it from previous work is establishing that
the convergence of certain type of game-playing rules implies that the
agents/players must be embedded in some graphical potential game.
Category-Specific Object Reconstruction from a Single Image
Authors: Abhishek Kar, Shubham Tulsiani, João Carreira, Jitendra Malik
Date: 2014-11-22 00:00:00
Proceeding: CVPR 2015 6
Tasks: Object, object-detection, Object Detection, Object Reconstruction

Object reconstruction from a single image -- in the wild -- is a problem
where we can make progress and get meaningful results today. This is the main
message of this paper, which introduces an automated pipeline with pixels as
inputs and 3D surfaces of various rigid categories as outputs in images of
realistic scenes. At the core of our approach are deformable 3D models that can
be learned from 2D annotations available in existing object detection datasets,
that can be driven by noisy automatic object segmentations and which we
complement with a bottom-up module for recovering high-frequency shape details.
We perform a comprehensive quantitative analysis and ablation study of our
approach using the recently introduced PASCAL 3D+ dataset and show very
encouraging automatic reconstructions on PASCAL VOC.
Depth-based hand pose estimation: methods, data, and challenges
Authors: James Steven Supancic III, Gregory Rogez, Yi Yang, Jamie Shotton, Deva Ramanan
Date: 2015-04-24 00:00:00
Tasks: Hand Pose Estimation, Pose Estimation

Hand pose estimation has matured rapidly in recent years. The introduction of
commodity depth sensors and a multitude of practical applications have spurred
new advances. We provide an extensive analysis of the state-of-the-art,
focusing on hand pose estimation from a single depth frame. To do so, we have
implemented a considerable number of systems, and will release all software and
evaluation code. We summarize important conclusions here: (1) Pose estimation
appears roughly solved for scenes with isolated hands. However, methods still
struggle to analyze cluttered scenes where hands may be interacting with nearby
objects and surfaces. To spur further progress we introduce a challenging new
dataset with diverse, cluttered scenes. (2) Many methods evaluate themselves
with disparate criteria, making comparisons difficult. We define a consistent
evaluation criteria, rigorously motivated by human experiments. (3) We
introduce a simple nearest-neighbor baseline that outperforms most existing
systems. This implies that most systems do not generalize beyond their training
sets. This also reinforces the under-appreciated point that training data is as
important as the model itself. We conclude with directions for future progress.
Retaining Experience and Growing Solutions
Authors: Robyn Ffrancon
Date: 2015-05-06 00:00:00

Generally, when genetic programming (GP) is used for function synthesis any
valuable experience gained by the system is lost from one problem to the next,
even when the problems are closely related. With the aim of developing a system
which retains beneficial experience from problem to problem, this paper
introduces the novel Node-by-Node Growth Solver (NNGS) algorithm which features
a component, called the controller, which can be adapted and improved for use
across a set of related problems. NNGS grows a single solution tree from root
to leaves. Using semantic backpropagation and acting locally on each node in
turn, the algorithm employs the controller to assign subsequent child nodes
until a fully formed solution is generated.
  The aim of this paper is to pave a path towards the use of a neural network
as the controller component and also, separately, towards the use of meta-GP as
a mechanism for improving the controller component. A proof-of-concept
controller is discussed which demonstrates the success and potential of the
NNGS algorithm. In this case, the controller constitutes a set of hand written
rules which can be used to deterministically and greedily solve standard
Boolean function synthesis benchmarks. Even before employing machine learning
to improve the controller, the algorithm vastly outperforms other well known
recent algorithms on run times, maintains comparable solution sizes, and has a
100% success rate on all Boolean function synthesis benchmarks tested so far.
Deviation Based Pooling Strategies For Full Reference Image Quality Assessment
Authors: Hossein Ziaei Nafchi, Rachid Hedjam, Atena Shahkolaei, Mohamed Cheriet
Date: 2015-04-26 00:00:00
Tasks: Full reference image quality assessment, Full-Reference Image Quality Assessment, Image Quality Assessment

The state-of-the-art pooling strategies for perceptual image quality
assessment (IQA) are based on the mean and the weighted mean. They are robust
pooling strategies which usually provide a moderate to high performance for
different IQAs. Recently, standard deviation (SD) pooling was also proposed.
Although, this deviation pooling provides a very high performance for a few
IQAs, its performance is lower than mean poolings for many other IQAs. In this
paper, we propose to use the mean absolute deviation (MAD) and show that it is
a more robust and accurate pooling strategy for a wider range of IQAs. In fact,
MAD pooling has the advantages of both mean pooling and SD pooling. The joint
computation and use of the MAD and SD pooling strategies is also considered in
this paper. Experimental results provide useful information on the choice of
the proper deviation pooling strategy for different IQA models.
Pooled Motion Features for First-Person Videos
Authors: M. S. Ryoo, Brandon Rothrock, Larry Matthies
Date: 2014-12-19 00:00:00
Proceeding: CVPR 2015 6
Tasks: Activity Recognition, Activity Recognition In Videos, Time Series, Time Series Analysis, Video Understanding

In this paper, we present a new feature representation for first-person
videos. In first-person video understanding (e.g., activity recognition), it is
very important to capture both entire scene dynamics (i.e., egomotion) and
salient local motion observed in videos. We describe a representation framework
based on time series pooling, which is designed to abstract
short-term/long-term changes in feature descriptor elements. The idea is to
keep track of how descriptor values are changing over time and summarize them
to represent motion in the activity video. The framework is general, handling
any types of per-frame feature descriptors including conventional motion
descriptors like histogram of optical flows (HOF) as well as appearance
descriptors from more recent convolutional neural networks (CNN). We
experimentally confirm that our approach clearly outperforms previous feature
representations including bag-of-visual-words and improved Fisher vector (IFV)
when using identical underlying feature descriptors. We also confirm that our
feature representation has superior performance to existing state-of-the-art
features like local spatio-temporal features and Improved Trajectory Features
(originally developed for 3rd-person videos) when handling first-person videos.
Multiple first-person activity datasets were tested under various settings to
confirm these findings.
Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence
Authors: Nihar B. Shah, Sivaraman Balakrishnan, Joseph Bradley, Abhay Parekh, Kannan Ramchandran, Martin J. Wainwright
Date: 2015-05-06 00:00:00

Data in the form of pairwise comparisons arises in many domains, including
preference elicitation, sporting competitions, and peer grading among others.
We consider parametric ordinal models for such pairwise comparison data
involving a latent vector $w^* \in \mathbb{R}^d$ that represents the
"qualities" of the $d$ items being compared; this class of models includes the
two most widely used parametric models--the Bradley-Terry-Luce (BTL) and the
Thurstone models. Working within a standard minimax framework, we provide tight
upper and lower bounds on the optimal error in estimating the quality score
vector $w^*$ under this class of models. The bounds depend on the topology of
the comparison graph induced by the subset of pairs being compared via its
Laplacian spectrum. Thus, in settings where the subset of pairs may be chosen,
our results provide principled guidelines for making this choice. Finally, we
compare these error rates to those under cardinal measurement models and show
that the error rates in the ordinal and cardinal settings have identical
scalings apart from constant pre-factors.
Efficient Image-Space Extraction and Representation of 3D Surface Topography
Authors: Matthias Zeppelzauer, Markus Seidl
Date: 2015-04-30 00:00:00
Tasks: 3D Reconstruction, Classification, General Classification

Surface topography refers to the geometric micro-structure of a surface and
defines its tactile characteristics (typically in the sub-millimeter range).
High-resolution 3D scanning techniques developed recently enable the 3D
reconstruction of surfaces including their surface topography. In his paper, we
present an efficient image-space technique for the extraction of surface
topography from high-resolution 3D reconstructions. Additionally, we filter
noise and enhance topographic attributes to obtain an improved representation
for subsequent topography classification. Comprehensive experiments show that
the our representation captures well topographic attributes and significantly
improves classification performance compared to alternative 2D and 3D
representations.
Information Gathering in Networks via Active Exploration
Authors: Adish Singla, Eric Horvitz, Pushmeet Kohli, Ryen White, Andreas Krause
Date: 2015-04-24 00:00:00
Tasks: Experimental Design, Informativeness, Question Answering

How should we gather information in a network, where each node's visibility
is limited to its local neighborhood? This problem arises in numerous
real-world applications, such as surveying and task routing in social networks,
team formation in collaborative networks and experimental design with
dependency constraints. Often the informativeness of a set of nodes can be
quantified via a submodular utility function. Existing approaches for
submodular optimization, however, require that the set of all nodes that can be
selected is known ahead of time, which is often unrealistic. In contrast, we
propose a novel model where we start our exploration from an initial node, and
new nodes become visible and available for selection only once one of their
neighbors has been chosen. We then present a general algorithm NetExp for this
problem, and provide theoretical bounds on its performance dependent on
structural properties of the underlying network. We evaluate our methodology on
various simulated problem instances as well as on data collected from social
question answering system deployed within a large enterprise.
Mining Scientific Papers for Bibliometrics: a (very) Brief Survey of Methods and Tools
Authors: Iana Atanassova, Marc Bertin, Philipp Mayr
Date: 2015-05-06 00:00:00
Tasks: Articles

The Open Access movement in scientific publishing and search engines like
Google Scholar have made scientific articles more broadly accessible. During
the last decade, the availability of scientific papers in full text has become
more and more widespread thanks to the growing number of publications on online
platforms such as ArXiv and CiteSeer. The efforts to provide articles in
machine-readable formats and the rise of Open Access publishing have resulted
in a number of standardized formats for scientific papers (such as NLM-JATS,
TEI, DocBook). Our aim is to stimulate research at the intersection of
Bibliometrics and Computational Linguistics in order to study the ways
Bibliometrics can benefit from large-scale text analytics and sense mining of
scientific papers, thus exploring the interdisciplinarity of Bibliometrics and
Natural Language Processing.
Re-scale boosting for regression and classification
Authors: Shaobo Lin, Yao Wang, Lin Xu
Date: 2015-05-06 00:00:00
Tasks: Classification, General Classification, regression

Boosting is a learning scheme that combines weak prediction rules to produce
a strong composite estimator, with the underlying intuition that one can obtain
accurate prediction rules by combining "rough" ones. Although boosting is
proved to be consistent and overfitting-resistant, its numerical convergence
rate is relatively slow. The aim of this paper is to develop a new boosting
strategy, called the re-scale boosting (RBoosting), to accelerate the numerical
convergence rate and, consequently, improve the learning performance of
boosting. Our studies show that RBoosting possesses the almost optimal
numerical convergence rate in the sense that, up to a logarithmic factor, it
can reach the minimax nonlinear approximation rate. We then use RBoosting to
tackle both the classification and regression problems, and deduce a tight
generalization error estimate. The theoretical and experimental results show
that RBoosting outperforms boosting in terms of generalization.
Person Re-identification by Local Maximal Occurrence Representation and Metric Learning
Authors: Shengcai Liao, Yang Hu, Xiangyu Zhu, Stan Z. Li
Date: 2014-06-17 00:00:00
Proceeding: CVPR 2015 6
Tasks: Metric Learning, Person Re-Identification

Person re-identification is an important technique towards automatic search
of a person's presence in a surveillance video. Two fundamental problems are
critical for person re-identification, feature representation and metric
learning. An effective feature representation should be robust to illumination
and viewpoint changes, and a discriminant metric should be learned to match
various person images. In this paper, we propose an effective feature
representation called Local Maximal Occurrence (LOMO), and a subspace and
metric learning method called Cross-view Quadratic Discriminant Analysis
(XQDA). The LOMO feature analyzes the horizontal occurrence of local features,
and maximizes the occurrence to make a stable representation against viewpoint
changes. Besides, to handle illumination variations, we apply the Retinex
transform and a scale invariant texture operator. To learn a discriminant
metric, we propose to learn a discriminant low dimensional subspace by
cross-view quadratic discriminant analysis, and simultaneously, a QDA metric is
learned on the derived subspace. We also present a practical computation method
for XQDA, as well as its regularization. Experiments on four challenging person
re-identification databases, VIPeR, QMUL GRID, CUHK Campus, and CUHK03, show
that the proposed method improves the state-of-the-art rank-1 identification
rates by 2.2%, 4.88%, 28.91%, and 31.55% on the four databases, respectively.