pwc-archive/papers-with-abstracts huggingface dataset:
Blending Learning and Inference in Structured Prediction
Authors: Tamir Hazan, Alexander Schwing, David Mcallester, Raquel Urtasun
Date: 2012-10-08 00:00:00
Tasks: Prediction, Scene Understanding, Semantic Segmentation, Structured Prediction

In this paper we derive an efficient algorithm to learn the parameters of
structured predictors in general graphical models. This algorithm blends the
learning and inference tasks, which results in a significant speedup over
traditional approaches, such as conditional random fields and structured
support vector machines. For this purpose we utilize the structures of the
predictors to describe a low dimensional structured prediction task which
encourages local consistencies within the different structures while learning
the parameters of the model. Convexity of the learning task provides the means
to enforce the consistencies between the different parts. The
inference-learning blending algorithm that we propose is guaranteed to converge
to the optimum of the low dimensional primal and dual programs. Unlike many of
the existing approaches, the inference-learning blending allows us to learn
efficiently high-order graphical models, over regions of any size, and very
large number of parameters. We demonstrate the effectiveness of our approach,
while presenting state-of-the-art results in stereo estimation, semantic
segmentation, shape reconstruction, and indoor scene understanding.
Separable Approximations and Decomposition Methods for the Augmented Lagrangian
Authors: Rachael Tappenden, Peter Richtarik, Burak Buke
Date: 2013-08-30 00:00:00

In this paper we study decomposition methods based on separable
approximations for minimizing the augmented Lagrangian. In particular, we study
and compare the Diagonal Quadratic Approximation Method (DQAM) of Mulvey and
Ruszczy\'{n}ski and the Parallel Coordinate Descent Method (PCDM) of
Richt\'arik and Tak\'a\v{c}. We show that the two methods are equivalent for
feasibility problems up to the selection of a single step-size parameter.
Furthermore, we prove an improved complexity bound for PCDM under strong
convexity, and show that this bound is at least $8(L'/\bar{L})(\omega-1)^2$
times better than the best known bound for DQAM, where $\omega$ is the degree
of partial separability and $L'$ and $\bar{L}$ are the maximum and average of
the block Lipschitz constants of the gradient of the quadratic penalty
appearing in the augmented Lagrangian.
Discriminative Parameter Estimation for Random Walks Segmentation
Authors: Pierre-Yves Baudin, Danny Goodman, Puneet Kumar, Noura Azzabou, Pierre G. Carlier, Nikos Paragios, M. Pawan Kumar
Date: 2013-08-30 00:00:00
Tasks: parameter estimation, Segmentation

The Random Walks (RW) algorithm is one of the most e - cient and easy-to-use
probabilistic segmentation methods. By combining contrast terms with prior
terms, it provides accurate segmentations of medical images in a fully
automated manner. However, one of the main drawbacks of using the RW algorithm
is that its parameters have to be hand-tuned. we propose a novel discriminative
learning framework that estimates the parameters using a training dataset. The
main challenge we face is that the training samples are not fully supervised.
Speci cally, they provide a hard segmentation of the images, instead of a
proba- bilistic segmentation. We overcome this challenge by treating the opti-
mal probabilistic segmentation that is compatible with the given hard
segmentation as a latent variable. This allows us to employ the latent support
vector machine formulation for parameter estimation. We show that our approach
signi cantly outperforms the baseline methods on a challenging dataset
consisting of real clinical 3D MRI volumes of skeletal muscles.
Image Set based Collaborative Representation for Face Recognition
Authors: Pengfei Zhu, WangMeng Zuo, Lei Zhang, Simon C. K. Shiu, David Zhang
Date: 2013-08-30 00:00:00
Tasks: Face Recognition, General Classification

With the rapid development of digital imaging and communication technologies, image set based face recognition (ISFR) is becoming increasingly important. One key issue of ISFR is how to effectively and efficiently represent the query face image set by using the gallery face image sets. The set-to-set distance based methods ignore the relationship between gallery sets, while representing the query set images individually over the gallery sets ignores the correlation between query set images. In this paper, we propose a novel image set based collaborative representation and classification method for ISFR. By modeling the query set as a convex or regularized hull, we represent this hull collaboratively over all the gallery sets. With the resolved representation coefficients, the distance between the query set and each gallery set can then be calculated for classification. The proposed model naturally and effectively extends the image based collaborative representation to an image set based one, and our extensive experiments on benchmark ISFR databases show the superiority of the proposed method to state-of-the-art ISFR methods under different set sizes in terms of both recognition rate and efficiency.
Guaranteed Classification via Regularized Similarity Learning
Authors: Zheng-Chu Guo, Yiming Ying
Date: 2013-06-13 00:00:00
Tasks: BIG-bench Machine Learning, Classification, General Classification, Generalization Bounds, Metric Learning

Learning an appropriate (dis)similarity function from the available data is a
central problem in machine learning, since the success of many machine learning
algorithms critically depends on the choice of a similarity function to compare
examples. Despite many approaches for similarity metric learning have been
proposed, there is little theoretical study on the links between similarity
met- ric learning and the classification performance of the result classifier.
In this paper, we propose a regularized similarity learning formulation
associated with general matrix-norms, and establish their generalization
bounds. We show that the generalization error of the resulting linear separator
can be bounded by the derived generalization bound of similarity learning. This
shows that a good gen- eralization of the learnt similarity function guarantees
a good classification of the resulting linear classifier. Our results extend
and improve those obtained by Bellet at al. [3]. Due to the techniques
dependent on the notion of uniform stability [6], the bound obtained there
holds true only for the Frobenius matrix- norm regularization. Our techniques
using the Rademacher complexity [5] and its related Khinchin-type inequality
enable us to establish bounds for regularized similarity learning formulations
associated with general matrix-norms including sparse L 1 -norm and mixed
(2,1)-norm.
The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond
Authors: Aurélien Garivier, Olivier Cappé
Date: 2011-02-12 00:00:00

This paper presents a finite-time analysis of the KL-UCB algorithm, an
online, horizon-free index policy for stochastic bandit problems. We prove two
distinct results: first, for arbitrary bounded rewards, the KL-UCB algorithm
satisfies a uniformly better regret bound than UCB or UCB2; second, in the
special case of Bernoulli rewards, it reaches the lower bound of Lai and
Robbins. Furthermore, we show that simple adaptations of the KL-UCB algorithm
are also optimal for specific classes of (possibly unbounded) rewards,
including those generated from exponential families of distributions. A
large-scale numerical study comparing KL-UCB with its main competitors (UCB,
UCB2, UCB-Tuned, UCB-V, DMED) shows that KL-UCB is remarkably efficient and
stable, including for short time horizons. KL-UCB is also the only method that
always performs better than the basic UCB policy. Our regret bounds rely on
deviations results of independent interest which are stated and proved in the
Appendix. As a by-product, we also obtain an improved regret bound for the
standard UCB algorithm.
A New Algorithm of Speckle Filtering using Stochastic Distances
Authors: Leonardo Torres, Tamer Cavalcante, Alejandro C. Frery
Date: 2013-08-29 00:00:00

This paper presents a new approach for filter design based on stochastic
distances and tests between distributions. A window is defined around each
pixel, overlapping samples are compared and only those which pass a
goodness-of-fit test are used to compute the filtered value. The technique is
applied to intensity SAR data with homogeneous regions using the Gamma model.
The proposal is compared with the Lee's filter using a protocol based on Monte
Carlo. Among the criteria used to quantify the quality of filters, we employ
the equivalent number of looks, line and edge preservation. Moreover, we also
assessed the filters by the Universal Image Quality Index and the Pearson's
correlation on edges regions.
Supervised Feature Selection in Graphs with Path Coding Penalties and Network Flows
Authors: Julien Mairal, Bin Yu
Date: 2012-04-20 00:00:00
Tasks: feature selection

We consider supervised learning problems where the features are embedded in a
graph, such as gene expressions in a gene network. In this context, it is of
much interest to automatically select a subgraph with few connected components;
by exploiting prior knowledge, one can indeed improve the prediction
performance or obtain results that are easier to interpret. Regularization or
penalty functions for selecting features in graphs have recently been proposed,
but they raise new algorithmic challenges. For example, they typically require
solving a combinatorially hard selection problem among all connected subgraphs.
In this paper, we propose computationally feasible strategies to select a
sparse and well-connected subset of features sitting on a directed acyclic
graph (DAG). We introduce structured sparsity penalties over paths on a DAG
called "path coding" penalties. Unlike existing regularization functions that
model long-range interactions between features in a graph, path coding
penalties are tractable. The penalties and their proximal operators involve
path selection problems, which we efficiently solve by leveraging network flow
optimization. We experimentally show on synthetic, image, and genomic data that
our approach is scalable and leads to more connected subgraphs than other
regularization functions for graphs.
A Synergistic Approach for Recovering Occlusion-Free Textured 3D Maps of Urban Facades from Heterogeneous Cartographic Data
Authors: Karim Hammoudi, Fadi Dornaika, Bahman Soheilian, Bruno Vallet, John McDonald, Nicolas Paparoditis
Date: 2013-08-29 00:00:00

In this paper we present a practical approach for generating an
occlusion-free textured 3D map of urban facades by the synergistic use of
terrestrial images, 3D point clouds and area-based information. Particularly in
dense urban environments, the high presence of urban objects in front of the
facades causes significant difficulties for several stages in computational
building modeling. Major challenges lie on the one hand in extracting complete
3D facade quadrilateral delimitations and on the other hand in generating
occlusion-free facade textures. For these reasons, we describe a
straightforward approach for completing and recovering facade geometry and
textures by exploiting the data complementarity of terrestrial multi-source
imagery and area-based information.
Says who? Automatic Text-Based Content Analysis of Television News
Authors: Carlos Castillo, Gianmarco De Francisci Morales, Marcelo Mendoza, Nasir Khan
Date: 2013-07-18 00:00:00

We perform an automatic analysis of television news programs, based on the
closed captions that accompany them. Specifically, we collect all the news
broadcasted in over 140 television channels in the US during a period of six
months. We start by segmenting, processing, and annotating the closed captions
automatically. Next, we focus on the analysis of their linguistic style and on
mentions of people using NLP methods. We present a series of key insights about
news providers, people in the news, and we discuss the biases that can be
uncovered by automatic means. These insights are contrasted by looking at the
data from multiple points of view, including qualitative assessment.
GNCGCP - Graduated NonConvexity and Graduated Concavity Procedure
Authors: Zhi-Yong Liu, Hong Qiao
Date: 2013-08-29 00:00:00
Tasks: Combinatorial Optimization, Graph Matching

In this paper we propose the Graduated NonConvexity and Graduated Concavity
Procedure (GNCGCP) as a general optimization framework to approximately solve
the combinatorial optimization problems on the set of partial permutation
matrices. GNCGCP comprises two sub-procedures, graduated nonconvexity (GNC)
which realizes a convex relaxation and graduated concavity (GC) which realizes
a concave relaxation. It is proved that GNCGCP realizes exactly a type of
convex-concave relaxation procedure (CCRP), but with a much simpler formulation
without needing convex or concave relaxation in an explicit way. Actually,
GNCGCP involves only the gradient of the objective function and is therefore
very easy to use in practical applications. Two typical NP-hard problems,
(sub)graph matching and quadratic assignment problem (QAP), are employed to
demonstrate its simplicity and state-of-the-art performance.
Collecting Coupons with Random Initial Stake
Authors: Benjamin Doerr, Carola Doerr
Date: 2013-08-29 00:00:00

Motivated by a problem in the theory of randomized search heuristics, we give
a very precise analysis for the coupon collector problem where the collector
starts with a random set of coupons (chosen uniformly from all sets).
  We show that the expected number of rounds until we have a coupon of each
type is $nH_{n/2} - 1/2 \pm o(1)$, where $H_{n/2}$ denotes the $(n/2)$th
harmonic number when $n$ is even, and $H_{n/2}:= (1/2) H_{\lfloor n/2 \rfloor}
+ (1/2) H_{\lceil n/2 \rceil}$ when $n$ is odd. Consequently, the coupon
collector with random initial stake is by half a round faster than the one
starting with exactly $n/2$ coupons (apart from additive $o(1)$ terms).
  This result implies that classic simple heuristic called \emph{randomized
local search} needs an expected number of $nH_{n/2} - 1/2 \pm o(1)$ iterations
to find the optimum of any monotonic function defined on bit-strings of length
$n$.
Ranking relations using analogies in biological and information networks
Authors: Ricardo Silva, Katherine Heller, Zoubin Ghahramani, Edoardo M. Airoldi
Date: 2009-12-28 00:00:00
Tasks: Information Retrieval, Relational Reasoning, Retrieval

Analogical reasoning depends fundamentally on the ability to learn and
generalize about relations between objects. We develop an approach to
relational learning which, given a set of pairs of objects
$\mathbf{S}=\{A^{(1)}:B^{(1)},A^{(2)}:B^{(2)},\ldots,A^{(N)}:B ^{(N)}\}$,
measures how well other pairs A:B fit in with the set $\mathbf{S}$. Our work
addresses the following question: is the relation between objects A and B
analogous to those relations found in $\mathbf{S}$? Such questions are
particularly relevant in information retrieval, where an investigator might
want to search for analogous pairs of objects that match the query set of
interest. There are many ways in which objects can be related, making the task
of measuring analogies very challenging. Our approach combines a similarity
measure on function spaces with Bayesian analysis to produce a ranking. It
requires data containing features of the objects of interest and a link matrix
specifying which relationships exist; no further attributes of such
relationships are necessary. We illustrate the potential of our method on text
analysis and information networks. An application on discovering functional
interactions between pairs of proteins is discussed in detail, where we show
that our approach can work in practice even if a small set of protein pairs is
provided.
A proposition of a robust system for historical document images indexation
Authors: Nizar Zaghden, Remy Mullot, Mohamed Adel Alimi
Date: 2013-08-28 00:00:00

Characterizing noisy or ancient documents is a challenging problem up to now.
Many techniques have been done in order to effectuate feature extraction and
image indexation for such documents. Global approaches are in general less
robust and exact than local approaches. That's why, we propose in this paper, a
hybrid system based on global approach(fractal dimension), and a local one
based on SIFT descriptor. The Scale Invariant Feature Transform seems to do
well with our application since it's rotation invariant and relatively robust
to changing illumination.In the first step the calculation of fractal dimension
is applied to images in order to eliminate images which have distant features
than image request characteristics. Next, the SIFT is applied to show which
images match well the request. However the average matching time using the
hybrid approach is better than "fractal dimension" and "SIFT descriptor" if
they are used alone.
Categorizing ancient documents
Authors: Nizar Zaghden, Remy Mullot, Mohamed Adel Alimi
Date: 2013-08-28 00:00:00
Tasks: Handwriting Recognition, Optical Character Recognition (OCR)

The analysis of historical documents is still a topical issue given the
importance of information that can be extracted and also the importance given
by the institutions to preserve their heritage. The main idea in order to
characterize the content of the images of ancient documents after attempting to
clean the image is segmented blocks texts from the same image and tries to find
similar blocks in either the same image or the entire image database. Most
approaches of offline handwriting recognition proceed by segmenting words into
smaller pieces (usually characters) which are recognized separately.
Recognition of a word then requires the recognition of all characters (OCR)
that compose it. Our work focuses mainly on the characterization of classes in
images of old documents. We use Som toolbox for finding classes in documents.
We applied also fractal dimensions and points of interest to categorize and
match ancient documents.
Text recognition in both ancient and cartographic documents
Authors: Nizar Zaghden, Badreddine Khelifi, Adel M. ALIMI, Remy Mullot
Date: 2013-08-28 00:00:00

This paper deals with the recognition and matching of text in both
cartographic maps and ancient documents. The purpose of this work is to find
similar text regions based on statistical and global features. A phase of
normalization is done first, in object to well categorize the same quantity of
information. A phase of wordspotting is done next by combining local and global
features. We make different experiments by combining the different techniques
of extracting features in order to obtain better results in recognition phase.
We applied fontspotting on both ancient documents and cartographic ones. We
also applied the wordspotting in which we adopted a new technique which tries
to compare the images of character and not the entire images words. We present
the precision and recall values obtained with three methods for the new method
of wordspotting applied on characters only.
Computing Lexical Contrast
Authors: Saif M. Mohammad, Bonnie J. Dorr, Graeme Hirst, Peter D. Turney
Date: 2013-08-28 00:00:00
Proceeding: CL 2013 1
Tasks: Information Retrieval, Machine Translation, Retrieval

Knowing the degree of semantic contrast between words has widespread
application in natural language processing, including machine translation,
information retrieval, and dialogue systems. Manually-created lexicons focus on
opposites, such as {\rm hot} and {\rm cold}. Opposites are of many kinds such
as antipodals, complementaries, and gradable. However, existing lexicons often
do not classify opposites into the different kinds. They also do not explicitly
list word pairs that are not opposites but yet have some degree of contrast in
meaning, such as {\rm warm} and {\rm cold} or {\rm tropical} and {\rm
freezing}. We propose an automatic method to identify contrasting word pairs
that is based on the hypothesis that if a pair of words, $A$ and $B$, are
contrasting, then there is a pair of opposites, $C$ and $D$, such that $A$ and
$C$ are strongly related and $B$ and $D$ are strongly related. (For example,
there exists the pair of opposites {\rm hot} and {\rm cold} such that {\rm
tropical} is related to {\rm hot,} and {\rm freezing} is related to {\rm
cold}.) We will call this the contrast hypothesis. We begin with a large
crowdsourcing experiment to determine the amount of human agreement on the
concept of oppositeness and its different kinds. In the process, we flesh out
key features of different kinds of opposites. We then present an automatic and
empirical measure of lexical contrast that relies on the contrast hypothesis,
corpus statistics, and the structure of a {\it Roget}-like thesaurus. We show
that the proposed measure of lexical contrast obtains high precision and large
coverage, outperforming existing methods.
Crowdsourcing a Word-Emotion Association Lexicon
Authors: Saif M. Mohammad, Peter D. Turney
Date: 2013-08-28 00:00:00
Tasks: Emotion Recognition

Even though considerable attention has been given to the polarity of words
(positive and negative) and the creation of large polarity lexicons, research
in emotion analysis has had to rely on limited and small emotion lexicons. In
this paper we show how the combined strength and wisdom of the crowds can be
used to generate a large, high-quality, word-emotion and word-polarity
association lexicon quickly and inexpensively. We enumerate the challenges in
emotion annotation in a crowdsourcing scenario and propose solutions to address
them. Most notably, in addition to questions about emotions associated with
terms, we show how the inclusion of a word choice question can discourage
malicious data entry, help identify instances where the annotator may not be
familiar with the target term (allowing us to reject such annotations), and
help obtain annotations at sense level (rather than at word level). We
conducted experiments on how to formulate the emotion-annotation questions, and
show that asking if a term is associated with an emotion leads to markedly
higher inter-annotator agreement than that obtained by asking if a term evokes
an emotion.
Verification of Semantically-Enhanced Artifact Systems (Extended Version)
Authors: Babak Bagheri Hariri, Diego Calvanese, Marco Montali, Ario Santoso, Dmitry Solomakhin
Date: 2013-08-28 00:00:00

Artifact-Centric systems have emerged in the last years as a suitable
framework to model business-relevant entities, by combining their static and
dynamic aspects. In particular, the Guard-Stage-Milestone (GSM) approach has
been recently proposed to model artifacts and their lifecycle in a declarative
way. In this paper, we enhance GSM with a Semantic Layer, constituted by a
full-fledged OWL 2 QL ontology linked to the artifact information models
through mapping specifications. The ontology provides a conceptual view of the
domain under study, and allows one to understand the evolution of the artifact
system at a higher level of abstraction. In this setting, we present a
technique to specify temporal properties expressed over the Semantic Layer, and
verify them according to the evolution in the underlying GSM model. This
technique has been implemented in a tool that exploits state-of-the-art
ontology-based data access technologies to manipulate the temporal properties
according to the ontology and the mappings, and that relies on the GSMC model
checker for verification.