pwc-archive/papers-with-abstracts huggingface dataset:
Second-order Shape Optimization for Geometric Inverse Problems in Vision
Authors: J. Balzer, S. Soatto
Date: 2013-11-11 00:00:00
Proceeding: CVPR 2014

We develop a method for optimization in shape spaces, i.e., sets of surfaces
modulo re-parametrization. Unlike previously proposed gradient flows, we
achieve superlinear convergence rates through a subtle approximation of the
shape Hessian, which is generally hard to compute and suffers from a series of
degeneracies. Our analysis highlights the role of mean curvature motion in
comparison with first-order schemes: instead of surface area, our approach
penalizes deformation, either by its Dirichlet energy or total variation.
Latter regularizer sparks the development of an alternating direction method of
multipliers on triangular meshes. Therein, a conjugate-gradients solver enables
us to bypass formation of the Gaussian normal equations appearing in the course
of the overall optimization. We combine all of the aforementioned ideas in a
versatile geometric variation-regularized Levenberg-Marquardt-type method
applicable to a variety of shape functionals, depending on intrinsic properties
of the surface such as normal field and curvature as well as its embedding into
space. Promising experimental results are reported.
A Generalized Language Model as the Combination of Skipped n-grams and Modified Kneser-Ney Smoothing
Authors: Rene Pickhardt, Thomas Gottron, Martin Körner, Paul Georg Wagner, Till Speicher, Steffen Staab
Date: 2014-04-13 00:00:00
Tasks: Language Modeling, Language Modelling

We introduce a novel approach for building language models based on a
systematic, recursive exploration of skip n-gram models which are interpolated
using modified Kneser-Ney smoothing. Our approach generalizes language models
as it contains the classical interpolation with lower order models as a special
case. In this paper we motivate, formalize and present our approach. In an
extensive empirical experiment over English text corpora we demonstrate that
our generalized language models lead to a substantial reduction of perplexity
between 3.1% and 12.7% in comparison to traditional language models using
modified Kneser-Ney smoothing. Furthermore, we investigate the behaviour over
three other languages and a domain specific corpus where we observed consistent
improvements. Finally, we also show that the strength of our approach lies in
its ability to cope in particular with sparse training data. Using a very small
training data set of only 736 KB text we yield improvements of even 25.7%
reduction of perplexity.
Distance function of D numbers
Authors: Meizhu Li, Qi Zhang, Xinyang Deng, Yong Deng
Date: 2014-04-13 00:00:00

Dempster-Shafer theory is widely applied in uncertainty modelling and
knowledge reasoning due to its ability of expressing uncertain information. A
distance between two basic probability assignments(BPAs) presents a measure of
performance for identification algorithms based on the evidential theory of
Dempster-Shafer. However, some conditions lead to limitations in practical
application for Dempster-Shafer theory, such as exclusiveness hypothesis and
completeness constraint. To overcome these shortcomings, a novel theory called
D numbers theory is proposed. A distance function of D numbers is proposed to
measure the distance between two D numbers. The distance function of D numbers
is an generalization of distance between two BPAs, which inherits the advantage
of Dempster-Shafer theory and strengthens the capability of uncertainty
modeling. An illustrative case is provided to demonstrate the effectiveness of
the proposed function.
Bayes Merging of Multiple Vocabularies for Scalable Image Retrieval
Authors: Liang Zheng, Shengjin Wang, Wengang Zhou, Qi Tian
Date: 2014-03-03 00:00:00
Proceeding: CVPR 2014 6
Tasks: Image Retrieval, Quantization, Retrieval

The Bag-of-Words (BoW) representation is well applied to recent
state-of-the-art image retrieval works. Typically, multiple vocabularies are
generated to correct quantization artifacts and improve recall. However, this
routine is corrupted by vocabulary correlation, i.e., overlapping among
different vocabularies. Vocabulary correlation leads to an over-counting of the
indexed features in the overlapped area, or the intersection set, thus
compromising the retrieval accuracy. In order to address the correlation
problem while preserve the benefit of high recall, this paper proposes a Bayes
merging approach to down-weight the indexed features in the intersection set.
Through explicitly modeling the correlation problem in a probabilistic view, a
joint similarity on both image- and feature-level is estimated for the indexed
features in the intersection set.
  We evaluate our method through extensive experiments on three benchmark
datasets. Albeit simple, Bayes merging can be well applied in various merging
tasks, and consistently improves the baselines on multi-vocabulary merging.
Moreover, Bayes merging is efficient in terms of both time and memory cost, and
yields competitive performance compared with the state-of-the-art methods.
Packing and Padding: Coupled Multi-index for Accurate Image Retrieval
Authors: Liang Zheng, Shengjin Wang, Ziqiong Liu, Qi Tian
Date: 2014-02-11 00:00:00
Proceeding: CVPR 2014 6
Tasks: Image Retrieval, Quantization, Retrieval

In Bag-of-Words (BoW) based image retrieval, the SIFT visual word has a low
discriminative power, so false positive matches occur prevalently. Apart from
the information loss during quantization, another cause is that the SIFT
feature only describes the local gradient distribution. To address this
problem, this paper proposes a coupled Multi-Index (c-MI) framework to perform
feature fusion at indexing level. Basically, complementary features are coupled
into a multi-dimensional inverted index. Each dimension of c-MI corresponds to
one kind of feature, and the retrieval process votes for images similar in both
SIFT and other feature spaces. Specifically, we exploit the fusion of local
color feature into c-MI. While the precision of visual match is greatly
enhanced, we adopt Multiple Assignment to improve recall. The joint cooperation
of SIFT and color features significantly reduces the impact of false positive
matches.
  Extensive experiments on several benchmark datasets demonstrate that c-MI
improves the retrieval accuracy significantly, while consuming only half of the
query time compared to the baseline. Importantly, we show that c-MI is well
complementary to many prior techniques. Assembling these methods, we have
obtained an mAP of 85.8% and N-S score of 3.85 on Holidays and Ukbench
datasets, respectively, which compare favorably with the state-of-the-arts.
Estimating Time-varying Brain Connectivity Networks from Functional MRI Time Series
Authors: Ricardo Pio Monti, Peter Hellyer, David Sharp, Robert Leech, Christoforos Anagnostopoulos, Giovanni Montana
Date: 2013-10-14 00:00:00
Tasks: Time Series, Time Series Analysis

Understanding the functional architecture of the brain in terms of networks
is becoming increasingly common. In most fMRI applications functional networks
are assumed to be stationary, resulting in a single network estimated for the
entire time course. However recent results suggest that the connectivity
between brain regions is highly non-stationary even at rest. As a result, there
is a need for new brain imaging methodologies that comprehensively account for
the dynamic (i.e., non-stationary) nature of the fMRI data. In this work we
propose the Smooth Incremental Graphical Lasso Estimation (SINGLE) algorithm
which estimates dynamic brain networks from fMRI data. We apply the SINGLE
algorithm to functional MRI data from 24 healthy patients performing a
choice-response task to demonstrate the dynamic changes in network structure
that accompany a simple but attentionally demanding cognitive task. Using graph
theoretic measures we show that the Right Inferior Frontal Gyrus, frequently
reported as playing an important role in cognitive control, dynamically changes
with the task. Our results suggest that the Right Inferior Frontal Gyrus plays
a fundamental role in the attention and executive function during cognitively
demanding tasks and may play a key role in regulating the balance between other
brain regions.
Shrinkage Optimized Directed Information using Pictorial Structures for Action Recognition
Authors: Xu Chen, Alfred Hero, Silvio Savarese
Date: 2014-04-12 00:00:00
Tasks: Action Recognition, Temporal Action Localization

In this paper, we propose a novel action recognition framework. The method
uses pictorial structures and shrinkage optimized directed information
assessment (SODA) coupled with Markov Random Fields called SODA+MRF to model
the directional temporal dependency and bidirectional spatial dependency. As a
variant of mutual information, directional information captures the directional
information flow and temporal structure of video sequences across frames.
Meanwhile, within each frame, Markov random fields are utilized to model the
spatial relations among different parts of a human body and the body parts of
different people. The proposed SODA+MRF model is robust to view point
transformations and detect complex interactions accurately. We compare the
proposed method against several baseline methods to highlight the effectiveness
of the SODA+MRF model. We demonstrate that our algorithm has superior action
recognition performance on the UCF action recognition dataset, the Olympic
sports dataset and the collective activity dataset over several
state-of-the-art methods.
Efficient Inference and Learning in a Large Knowledge Base: Reasoning with Extracted Information using a Locally Groundable First-Order Probabilistic Logic
Authors: William Yang Wang, Kathryn Mazaitis, Ni Lao, Tom Mitchell, William W. Cohen
Date: 2014-04-12 00:00:00
Tasks: Relational Reasoning

One important challenge for probabilistic logics is reasoning with very large
knowledge bases (KBs) of imperfect information, such as those produced by
modern web-scale information extraction systems. One scalability problem shared
by many probabilistic logics is that answering queries involves "grounding" the
query---i.e., mapping it to a propositional representation---and the size of a
"grounding" grows with database size. To address this bottleneck, we present a
first-order probabilistic language called ProPPR in which that approximate
"local groundings" can be constructed in time independent of database size.
Technically, ProPPR is an extension to stochastic logic programs (SLPs) that is
biased towards short derivations; it is also closely related to an earlier
relational learning algorithm called the path ranking algorithm (PRA). We show
that the problem of constructing proofs for this logic is related to
computation of personalized PageRank (PPR) on a linearized version of the proof
space, and using on this connection, we develop a proveably-correct approximate
grounding scheme, based on the PageRank-Nibble algorithm. Building on this, we
develop a fast and easily-parallelized weight-learning algorithm for ProPPR. In
experiments, we show that learning for ProPPR is orders magnitude faster than
learning for Markov logic networks; that allowing mutual recursion (joint
learning) in KB inference leads to improvements in performance; and that ProPPR
can learn weights for a mutually recursive program with hundreds of clauses,
which define scores of interrelated predicates, over a KB containing one
million entities.
Cost-Effective HITs for Relative Similarity Comparisons
Authors: Michael J. Wilber, Iljung S. Kwak, Serge J. Belongie
Date: 2014-04-12 00:00:00
Tasks: Triplet

Similarity comparisons of the form "Is object a more similar to b than to c?"
are useful for computer vision and machine learning applications.
Unfortunately, an embedding of $n$ points is specified by $n^3$ triplets,
making collecting every triplet an expensive task. In noticing this difficulty,
other researchers have investigated more intelligent triplet sampling
techniques, but they do not study their effectiveness or their potential
drawbacks. Although it is important to reduce the number of collected triplets,
it is also important to understand how best to display a triplet collection
task to a user. In this work we explore an alternative display for collecting
triplets and analyze the monetary cost and speed of the display. We propose
best practices for creating cost effective human intelligence tasks for
collecting triplets. We show that rather than changing the sampling algorithm,
simple changes to the crowdsourcing UI can lead to much higher quality
embeddings. We also provide a dataset as well as the labels collected from
crowd workers.
Motion-Compensated Coding and Frame-Rate Up-Conversion: Models and Analysis
Authors: Yehuda Dar, Alfred M. Bruckstein
Date: 2014-04-12 00:00:00
Tasks: Motion Estimation, Prediction

Block-based motion estimation (ME) and compensation (MC) techniques are
widely used in modern video processing algorithms and compression systems. The
great variety of video applications and devices results in numerous compression
specifications. Specifically, there is a diversity of frame-rates and
bit-rates. In this paper, we study the effect of frame-rate and compression
bit-rate on block-based ME and MC as commonly utilized in inter-frame coding
and frame-rate up conversion (FRUC). This joint examination yields a
comprehensive foundation for comparing MC procedures in coding and FRUC. First,
the video signal is modeled as a noisy translational motion of an image. Then,
we theoretically model the motion-compensated prediction of an available and
absent frames as in coding and FRUC applications, respectively. The theoretic
MC-prediction error is further analyzed and its autocorrelation function is
calculated for coding and FRUC applications. We show a linear relation between
the variance of the MC-prediction error and temporal-distance. While the
affecting distance in MC-coding is between the predicted and reference frames,
MC-FRUC is affected by the distance between the available frames used for the
interpolation. Moreover, the dependency in temporal-distance implies an inverse
effect of the frame-rate. FRUC performance analysis considers the prediction
error variance, since it equals to the mean-squared-error of the interpolation.
However, MC-coding analysis requires the entire autocorrelation function of the
error; hence, analytic simplicity is beneficial. Therefore, we propose two
constructions of a separable autocorrelation function for prediction error in
MC-coding. We conclude by comparing our estimations with experimental results.
An Integer Programming Model for the Dynamic Location and Relocation of Emergency Vehicles: A Case Study
Authors: Mahdi Moeini, Zied Jemai, Evren Sahin
Date: 2014-04-12 00:00:00

In this paper, we address the dynamic Emergency Medical Service (EMS)
systems. A dynamic location model is presented that tries to locate and
relocate the ambulances. The proposed model controls the movements and
locations of ambulances in order to provide a better coverage of the demand
points under different fluctuation patterns that may happen during a given
period of time. Some numerical experiments have been carried out by using some
real-world data sets that have been collected through the French EMS system.
Pagination: It's what you say, not how long it takes to say it
Authors: Joshua Hailpern, Niranjan Damera Venkata, Marina Danilevsky
Date: 2014-04-11 00:00:00
Tasks: Articles, Language Modeling, Language Modelling

Pagination - the process of determining where to break an article across
pages in a multi-article layout is a common layout challenge for most
commercially printed newspapers and magazines. To date, no one has created an
algorithm that determines a minimal pagination break point based on the content
of the article. Existing approaches for automatic multi-article layout focus
exclusively on maximizing content (number of articles) and optimizing aesthetic
presentation (e.g., spacing between articles). However, disregarding the
semantic information within the article can lead to overly aggressive cutting,
thereby eliminating key content and potentially confusing the reader, or
setting too generous of a break point, thereby leaving in superfluous content
and making automatic layout more difficult. This is one of the remaining
challenges on the path from manual layouts to fully automated processes that
still ensure article content quality. In this work, we present a new approach
to calculating a document minimal break point for the task of pagination. Our
approach uses a statistical language model to predict minimal break points
based on the semantic content of an article. We then compare 4 novel candidate
approaches, and 4 baselines (currently in use by layout algorithms). Results
from this experiment show that one of our approaches strongly outperforms the
baselines and alternatives. Results from a second study suggest that humans are
not able to agree on a single "best" break point. Therefore, this work shows
that a semantic-based lower bound break point prediction is necessary for ideal
automated document synthesis within a real-world context.
Estimating nonlinear regression errors without doing regression
Authors: Hong Pi, Carsten Peterson
Date: 2014-04-11 00:00:00
Tasks: regression

A method for estimating nonlinear regression errors and their distributions
without performing regression is presented. Assuming continuity of the modeling
function the variance is given in terms of conditional probabilities extracted
from the data. For N data points the computational demand is N2. Comparing the
predicted residual errors with those derived from a linear model assumption
provides a signal for nonlinearity. The method is successfully illustrated with
data generated by the Ikeda and Lorenz maps augmented with noise. As a
by-product the embedding dimensions of these maps are also extracted.
Compressive classification and the rare eclipse problem
Authors: Afonso S. Bandeira, Dustin G. Mixon, Benjamin Recht
Date: 2014-04-11 00:00:00
Tasks: Classification, General Classification

This paper addresses the fundamental question of when convex sets remain
disjoint after random projection. We provide an analysis using ideas from
high-dimensional convex geometry. For ellipsoids, we provide a bound in terms
of the distance between these ellipsoids and simple functions of their
polynomial coefficients. As an application, this theorem provides bounds for
compressive classification of convex sets. Rather than assuming that the data
to be classified is sparse, our results show that the data can be acquired via
very few measurements yet will remain linearly separable. We demonstrate the
feasibility of this approach in the context of hyperspectral imaging.
Pareto-Path Multi-Task Multiple Kernel Learning
Authors: Cong Li, Michael Georgiopoulos, Georgios C. Anagnostopoulos
Date: 2014-04-11 00:00:00
Tasks: Multi-Task Learning

A traditional and intuitively appealing Multi-Task Multiple Kernel Learning
(MT-MKL) method is to optimize the sum (thus, the average) of objective
functions with (partially) shared kernel function, which allows information
sharing amongst tasks. We point out that the obtained solution corresponds to a
single point on the Pareto Front (PF) of a Multi-Objective Optimization (MOO)
problem, which considers the concurrent optimization of all task objectives
involved in the Multi-Task Learning (MTL) problem. Motivated by this last
observation and arguing that the former approach is heuristic, we propose a
novel Support Vector Machine (SVM) MT-MKL framework, that considers an
implicitly-defined set of conic combinations of task objectives. We show that
solving our framework produces solutions along a path on the aforementioned PF
and that it subsumes the optimization of the average of objective functions as
a special case. Using algorithms we derived, we demonstrate through a series of
experimental results that the framework is capable of achieving better
classification performance, when compared to other similar MTL approaches.
Decreasing Weighted Sorted $\ell_1$ Regularization
Authors: Xiangrong Zeng, Mário A. T. Figueiredo
Date: 2014-04-11 00:00:00
Tasks: Clustering, regression

We consider a new family of regularizers, termed {\it weighted sorted
$\ell_1$ norms} (WSL1), which generalizes the recently introduced {\it
octagonal shrinkage and clustering algorithm for regression} (OSCAR) and also
contains the $\ell_1$ and $\ell_{\infty}$ norms as particular instances. We
focus on a special case of the WSL1, the {\sl decreasing WSL1} (DWSL1), where
the elements of the argument vector are sorted in non-increasing order and the
weights are also non-increasing. In this paper, after showing that the DWSL1 is
indeed a norm, we derive two key tools for its use as a regularizer: the dual
norm and the Moreau proximity operator.
Datalog Rewritability of Disjunctive Datalog Programs and its Applications to Ontology Reasoning
Authors: Mark Kaminski, Yavor Nenov, Bernardo Cuenca Grau
Date: 2014-04-11 00:00:00

We study the problem of rewriting a disjunctive datalog program into plain
datalog. We show that a disjunctive program is rewritable if and only if it is
equivalent to a linear disjunctive program, thus providing a novel
characterisation of datalog rewritability. Motivated by this result, we propose
weakly linear disjunctive datalog---a novel rule-based KR language that extends
both datalog and linear disjunctive datalog and for which reasoning is
tractable in data complexity. We then explore applications of weakly linear
programs to ontology reasoning and propose a tractable extension of OWL 2 RL
with disjunctive axioms. Our empirical results suggest that many non-Horn
ontologies can be reduced to weakly linear programs and that query answering
over such ontologies using a datalog engine is feasible in practice.
The Sampling-and-Learning Framework: A Statistical View of Evolutionary Algorithms
Authors: Yang Yu, Hong Qian
Date: 2014-01-24 00:00:00
Tasks: Binary Classification, Evolutionary Algorithms, General Classification, Learning Theory

Evolutionary algorithms (EAs), a large class of general purpose optimization
algorithms inspired from the natural phenomena, are widely used in various
industrial optimizations and often show excellent performance. This paper
presents an attempt towards revealing their general power from a statistical
view of EAs. By summarizing a large range of EAs into the sampling-and-learning
framework, we show that the framework directly admits a general analysis on the
probable-absolute-approximate (PAA) query complexity. We particularly focus on
the framework with the learning subroutine being restricted as a binary
classification, which results in the sampling-and-classification (SAC)
algorithms. With the help of the learning theory, we obtain a general upper
bound on the PAA query complexity of SAC algorithms. We further compare SAC
algorithms with the uniform search in different situations. Under the
error-target independence condition, we show that SAC algorithms can achieve
polynomial speedup to the uniform search, but not super-polynomial speedup.
Under the one-side-error condition, we show that super-polynomial speedup can
be achieved. This work only touches the surface of the framework. Its power
under other conditions is still open.