pwc-archive/papers-with-abstracts huggingface dataset:
Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection
Authors: Julie Nutini, Mark Schmidt, Issam H. Laradji, Michael Friedlander, Hoyt Koepke
Date: 2015-06-01 00:00:00

There has been significant recent work on the theory and application of
randomized coordinate descent algorithms, beginning with the work of Nesterov
[SIAM J. Optim., 22(2), 2012], who showed that a random-coordinate selection
rule achieves the same convergence rate as the Gauss-Southwell selection rule.
This result suggests that we should never use the Gauss-Southwell rule, as it
is typically much more expensive than random selection. However, the empirical
behaviours of these algorithms contradict this theoretical result: in
applications where the computational costs of the selection rules are
comparable, the Gauss-Southwell selection rule tends to perform substantially
better than random coordinate selection. We give a simple analysis of the
Gauss-Southwell rule showing that---except in extreme cases---its convergence
rate is faster than choosing random coordinates. Further, in this work we (i)
show that exact coordinate optimization improves the convergence rate for
certain sparse problems, (ii) propose a Gauss-Southwell-Lipschitz rule that
gives an even faster convergence rate given knowledge of the Lipschitz
constants of the partial derivatives, (iii) analyze the effect of approximate
Gauss-Southwell rules, and (iv) analyze proximal-gradient variants of the
Gauss-Southwell rule.
Desirability and the birth of incomplete preferences
Authors: Marco Zaffalon, Enrique Miranda
Date: 2015-06-01 00:00:00

We establish an equivalence between two seemingly different theories: one is
the traditional axiomatisation of incomplete preferences on horse lotteries
based on the mixture independence axiom; the other is the theory of desirable
gambles developed in the context of imprecise probability. The equivalence
allows us to revisit incomplete preferences from the viewpoint of desirability
and through the derived notion of coherent lower previsions. On this basis, we
obtain new results and insights: in particular, we show that the theory of
incomplete preferences can be developed assuming only the existence of a worst
act---no best act is needed---, and that a weakened Archimedean axiom suffices
too; this axiom allows us also to address some controversy about the regularity
assumption (that probabilities should be positive---they need not), which
enables us also to deal with uncountable possibility spaces; we show that it is
always possible to extend in a minimal way a preference relation to one with a
worst act, and yet the resulting relation is never Archimedean, except in a
trivial case; we show that the traditional notion of state independence
coincides with the notion called strong independence in imprecise
probability---this leads us to give much a weaker definition of state
independence than the traditional one; we rework and uniform the notions of
complete preferences, beliefs, values; we argue that Archimedeanity does not
capture all the problems that can be modelled with sets of expected utilities
and we provide a new notion that does precisely that. Perhaps most importantly,
we argue throughout that desirability is a powerful and natural setting to
model, and work with, incomplete preferences, even in case of non-Archimedean
problems. This leads us to suggest that desirability, rather than preference,
should be the primitive notion at the basis of decision-theoretic
axiomatisations.
Medical Synonym Extraction with Concept Space Models
Authors: Chang Wang, Liangliang Cao, Bo-Wen Zhou
Date: 2015-06-01 00:00:00

In this paper, we present a novel approach for medical synonym extraction. We
aim to integrate the term embedding with the medical domain knowledge for
healthcare applications. One advantage of our method is that it is very
scalable. Experiments on a dataset with more than 1M term pairs show that the
proposed approach outperforms the baseline approaches by a large margin.
User Preferences Modeling and Learning for Pleasing Photo Collage Generation
Authors: Simone Bianco, Gianluigi Ciocca
Date: 2015-06-01 00:00:00

In this paper we consider how to automatically create pleasing photo collages
created by placing a set of images on a limited canvas area. The task is
formulated as an optimization problem. Differently from existing
state-of-the-art approaches, we here exploit subjective experiments to model
and learn pleasantness from user preferences. To this end, we design an
experimental framework for the identification of the criteria that need to be
taken into account to generate a pleasing photo collage. Five different
thematic photo datasets are used to create collages using state-of-the-art
criteria. A first subjective experiment where several subjects evaluated the
collages, emphasizes that different criteria are involved in the subjective
definition of pleasantness. We then identify new global and local criteria and
design algorithms to quantify them. The relative importance of these criteria
are automatically learned by exploiting the user preferences, and new collages
are generated. To validate our framework, we performed several psycho-visual
experiments involving different users. The results shows that the proposed
framework allows to learn a novel computational model which effectively encodes
an inter-user definition of pleasantness. The learned definition of
pleasantness generalizes well to new photo datasets of different themes and
sizes not used in the learning. Moreover, compared with two state of the art
approaches, the collages created using our framework are preferred by the
majority of the users.
Symmetric Weighted First-Order Model Counting
Authors: Paul Beame, Guy Van Den Broeck, Eric Gribkoff, Dan Suciu
Date: 2014-12-03 00:00:00
Tasks: model, Sentence

The FO Model Counting problem (FOMC) is the following: given a sentence
$\Phi$ in FO and a number $n$, compute the number of models of $\Phi$ over a
domain of size $n$; the Weighted variant (WFOMC) generalizes the problem by
associating a weight to each tuple and defining the weight of a model to be the
product of weights of its tuples. In this paper we study the complexity of the
symmetric WFOMC, where all tuples of a given relation have the same weight. Our
motivation comes from an important application, inference in Knowledge Bases
with soft constraints, like Markov Logic Networks, but the problem is also of
independent theoretical interest. We study both the data complexity, and the
combined complexity of FOMC and WFOMC. For the data complexity we prove the
existence of an FO$^{3}$ formula for which FOMC is #P$_1$-complete, and the
existence of a Conjunctive Query for which WFOMC is #P$_1$-complete. We also
prove that all $\gamma$-acyclic queries have polynomial time data complexity.
For the combined complexity, we prove that, for every fragment FO$^{k}$, $k\geq
2$, the combined complexity of FOMC (or WFOMC) is #P-complete.
Robust Face Recognition with Structural Binary Gradient Patterns
Authors: Weilin Huang, Hujun Yin
Date: 2015-06-01 00:00:00
Tasks: Face Recognition, Robust Face Recognition

This paper presents a computationally efficient yet powerful binary framework
for robust facial representation based on image gradients. It is termed as
structural binary gradient patterns (SBGP). To discover underlying local
structures in the gradient domain, we compute image gradients from multiple
directions and simplify them into a set of binary strings. The SBGP is derived
from certain types of these binary strings that have meaningful local
structures and are capable of resembling fundamental textural information. They
detect micro orientational edges and possess strong orientation and locality
capabilities, thus enabling great discrimination. The SBGP also benefits from
the advantages of the gradient domain and exhibits profound robustness against
illumination variations. The binary strategy realized by pixel correlations in
a small neighborhood substantially simplifies the computational complexity and
achieves extremely efficient processing with only 0.0032s in Matlab for a
typical face image. Furthermore, the discrimination power of the SBGP can be
enhanced on a set of defined orientational image gradient magnitudes, further
enforcing locality and orientation. Results of extensive experiments on various
benchmark databases illustrate significant improvements of the SBGP based
representations over the existing state-of-the-art local descriptors in the
terms of discrimination, robustness and complexity. Codes for the SBGP methods
will be available at
http://www.eee.manchester.ac.uk/research/groups/sisp/software/.
Texture Retrieval via the Scattering Transform
Authors: Alexander Sagel, Dominik Meyer, Hao Shen
Date: 2015-01-12 00:00:00
Tasks: Content-Based Image Retrieval, Image Retrieval, Retrieval, Texture Classification

This work studies the problem of content-based image retrieval, specifically,
texture retrieval. It focuses on feature extraction and similarity measure for
texture images. Our approach employs a recently developed method, the so-called
Scattering transform, for the process of feature extraction in texture
retrieval. It shares a distinctive property of providing a robust
representation, which is stable with respect to spatial deformations. Recent
work has demonstrated its capability for texture classification, and hence as a
promising candidate for the problem of texture retrieval.
  Moreover, we adopt a common approach of measuring the similarity of textures
by comparing the subband histograms of a filterbank transform. To this end we
derive a similarity measure based on the popular Bhattacharyya Kernel. Despite
the popularity of describing histograms using parametrized probability density
functions, such as the Generalized Gaussian Distribution, it is unfortunately
not applicable for describing most of the Scattering transform subbands, due to
the complex modulus performed on each one of them. In this work, we propose to
use the Weibull distribution to model the Scattering subbands of descendant
layers.
  Our numerical experiments demonstrated the effectiveness of the proposed
approach, in comparison with several state of the arts.
Bayesian Network Constraint-Based Structure Learning Algorithms: Parallel and Optimised Implementations in the bnlearn R Package
Authors: Marco Scutari
Date: 2014-06-30 00:00:00

It is well known in the literature that the problem of learning the structure
of Bayesian networks is very hard to tackle: its computational complexity is
super-exponential in the number of nodes in the worst case and polynomial in
most real-world scenarios.
  Efficient implementations of score-based structure learning benefit from past
and current research in optimisation theory, which can be adapted to the task
by using the network score as the objective function to maximise. This is not
true for approaches based on conditional independence tests, called
constraint-based learning algorithms. The only optimisation in widespread use,
backtracking, leverages the symmetries implied by the definitions of
neighbourhood and Markov blanket.
  In this paper we illustrate how backtracking is implemented in recent
versions of the bnlearn R package, and how it degrades the stability of
Bayesian network structure learning for little gain in terms of speed. As an
alternative, we describe a software architecture and framework that can be used
to parallelise constraint-based structure learning algorithms (also implemented
in bnlearn) and we demonstrate its performance using four reference networks
and two real-world data sets from genetics and systems biology. We show that on
modern multi-core or multiprocessor hardware parallel implementations are
preferable over backtracking, which was developed when single-processor
machines were the norm.
Hierarchical structure-and-motion recovery from uncalibrated images
Authors: Roberto Toldo, Riccardo Gherardi, Michela Farenzena, Andrea Fusiello
Date: 2015-06-01 00:00:00
Tasks: Computational Efficiency

This paper addresses the structure-and-motion problem, that requires to find
camera motion and 3D struc- ture from point matches. A new pipeline, dubbed
Samantha, is presented, that departs from the prevailing sequential paradigm
and embraces instead a hierarchical approach. This method has several
advantages, like a provably lower computational complexity, which is necessary
to achieve true scalability, and better error containment, leading to more
stability and less drift. Moreover, a practical autocalibration procedure
allows to process images without ancillary information. Experiments with real
data assess the accuracy and the computational efficiency of the method.
RBIR using Interest Regions and Binary Signatures
Authors: Thanh The Van, Thanh Manh Le
Date: 2015-06-01 00:00:00
Tasks: Content-Based Image Retrieval, Image Retrieval, Retrieval

In this paper, we introduce an approach to overcome the low accuracy of the
Content-Based Image Retrieval (CBIR) (when using the global features). To
increase the accuracy, we use Harris-Laplace detector to identify the interest
regions of image. Then, we build the Region-Based Image Retrieval (RBIR). For
the efficient image storage and retrieval, we encode images into binary
signatures. The binary signature of a image is created from its interest
regions. Furthermore, this paper also provides an algorithm for image retrieval
on S-tree by comparing the images' signatures on a metric similarly to EMD
(earth mover's distance). Finally, we evaluate the created models on COREL's
images.
Formal Concept Analysis for Knowledge Discovery from Biological Data
Authors: Khalid Raza
Date: 2015-06-01 00:00:00
Tasks: Clustering

Due to rapid advancement in high-throughput techniques, such as microarrays
and next generation sequencing technologies, biological data are increasing
exponentially. The current challenge in computational biology and
bioinformatics research is how to analyze these huge raw biological data to
extract biologically meaningful knowledge. This review paper presents the
applications of formal concept analysis for the analysis and knowledge
discovery from biological data, including gene expression discretization, gene
co-expression mining, gene expression clustering, finding genes in gene
regulatory networks, enzyme/protein classifications, binding site
classifications, and so on. It also presents a list of FCA-based software tools
applied in biological domain and covers the challenges faced so far.
Generalized Twin Gaussian Processes using Sharma-Mittal Divergence
Authors: Mohamed Elhoseiny, Ahmed Elgammal
Date: 2014-09-26 00:00:00
Tasks: BIG-bench Machine Learning, Gaussian Processes

There has been a growing interest in mutual information measures due to their
wide range of applications in Machine Learning and Computer Vision. In this
paper, we present a generalized structured regression framework based on
Shama-Mittal divergence, a relative entropy measure, which is introduced to the
Machine Learning community in this work. Sharma-Mittal (SM) divergence is a
generalized mutual information measure for the widely used R\'enyi, Tsallis,
Bhattacharyya, and Kullback-Leibler (KL) relative entropies. Specifically, we
study Sharma-Mittal divergence as a cost function in the context of the Twin
Gaussian Processes (TGP)~\citep{Bo:2010}, which generalizes over the
KL-divergence without computational penalty. We show interesting properties of
Sharma-Mittal TGP (SMTGP) through a theoretical analysis, which covers missing
insights in the traditional TGP formulation. However, we generalize this theory
based on SM-divergence instead of KL-divergence which is a special case.
Experimentally, we evaluated the proposed SMTGP framework on several datasets.
The results show that SMTGP reaches better predictions than KL-based TGP, since
it offers a bigger class of models through its parameters that we learn from
the data.
A Fast and Flexible Algorithm for the Graph-Fused Lasso
Authors: Wesley Tansey, James G. Scott
Date: 2015-05-24 00:00:00
Tasks: parameter estimation

We propose a new algorithm for solving the graph-fused lasso (GFL), a method
for parameter estimation that operates under the assumption that the signal
tends to be locally constant over a predefined graph structure. Our key insight
is to decompose the graph into a set of trails which can then each be solved
efficiently using techniques for the ordinary (1D) fused lasso. We leverage
these trails in a proximal algorithm that alternates between closed form primal
updates and fast dual trail updates. The resulting techinque is both faster
than previous GFL methods and more flexible in the choice of loss function and
graph structure. Furthermore, we present two algorithms for constructing trail
sets and show empirically that they offer a tradeoff between preprocessing time
and convergence rate.
On Distributive Subalgebras of Qualitative Spatial and Temporal Calculi
Authors: Zhiguo Long, Sanjiang Li
Date: 2015-06-01 00:00:00

Qualitative calculi play a central role in representing and reasoning about
qualitative spatial and temporal knowledge. This paper studies distributive
subalgebras of qualitative calculi, which are subalgebras in which (weak)
composition distributives over nonempty intersections. It has been proven for
RCC5 and RCC8 that path consistent constraint network over a distributive
subalgebra is always minimal and globally consistent (in the sense of strong
$n$-consistency) in a qualitative sense. The well-known subclass of convex
interval relations provides one such an example of distributive subalgebras.
This paper first gives a characterisation of distributive subalgebras, which
states that the intersection of a set of $n\geq 3$ relations in the subalgebra
is nonempty if and only if the intersection of every two of these relations is
nonempty. We further compute and generate all maximal distributive subalgebras
for Point Algebra, Interval Algebra, RCC5 and RCC8, Cardinal Relation Algebra,
and Rectangle Algebra. Lastly, we establish two nice properties which will play
an important role in efficient reasoning with constraint networks involving a
large number of variables.
Imaging Time-Series to Improve Classification and Imputation
Authors: Zhiguang Wang, Tim Oates
Date: 2015-06-01 00:00:00
Tasks: Classification, General Classification, Imputation, Time Series, Time Series Analysis, Time Series Classification

Inspired by recent successes of deep learning in computer vision, we propose
a novel framework for encoding time series as different types of images,
namely, Gramian Angular Summation/Difference Fields (GASF/GADF) and Markov
Transition Fields (MTF). This enables the use of techniques from computer
vision for time series classification and imputation. We used Tiled
Convolutional Neural Networks (tiled CNNs) on 20 standard datasets to learn
high-level features from the individual and compound GASF-GADF-MTF images. Our
approaches achieve highly competitive results when compared to nine of the
current best time series classification approaches. Inspired by the bijection
property of GASF on 0/1 rescaled data, we train Denoised Auto-encoders (DA) on
the GASF images of four standard and one synthesized compound dataset. The
imputation MSE on test data is reduced by 12.18%-48.02% when compared to using
the raw data. An analysis of the features and weights learned via tiled CNNs
and DAs explains why the approaches work.
Robust PCA: Optimization of the Robust Reconstruction Error over the Stiefel Manifold
Authors: Anastasia Podosinnikova, Simon Setzer, Matthias Hein
Date: 2015-06-01 00:00:00

It is well known that Principal Component Analysis (PCA) is strongly affected
by outliers and a lot of effort has been put into robustification of PCA. In
this paper we present a new algorithm for robust PCA minimizing the trimmed
reconstruction error. By directly minimizing over the Stiefel manifold, we
avoid deflation as often used by projection pursuit methods. In distinction to
other methods for robust PCA, our method has no free parameter and is
computationally very efficient. We illustrate the performance on various
datasets including an application to background modeling and subtraction. Our
method performs better or similar to current state-of-the-art methods while
being faster.
Copeland Dueling Bandits
Authors: Masrour Zoghi, Zohar Karnin, Shimon Whiteson, Maarten de Rijke
Date: 2015-06-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Form

A version of the dueling bandit problem is addressed in which a Condorcet
winner may not exist. Two algorithms are proposed that instead seek to minimize
regret with respect to the Copeland winner, which, unlike the Condorcet winner,
is guaranteed to exist. The first, Copeland Confidence Bound (CCB), is designed
for small numbers of arms, while the second, Scalable Copeland Bandits (SCB),
works better for large-scale problems. We provide theoretical results bounding
the regret accumulated by CCB and SCB, both substantially improving existing
results. Such existing results either offer bounds of the form $O(K \log T)$
but require restrictive assumptions, or offer bounds of the form $O(K^2 \log
T)$ without requiring such assumptions. Our results offer the best of both
worlds: $O(K \log T)$ bounds without restrictive assumptions.
Automatic Inference for Inverting Software Simulators via Probabilistic Programming
Authors: Ardavan Saeedi, Vlad Firoiu, Vikash Mansinghka
Date: 2015-05-31 00:00:00
Tasks: Probabilistic Programming

Models of complex systems are often formalized as sequential software
simulators: computationally intensive programs that iteratively build up
probable system configurations given parameters and initial conditions. These
simulators enable modelers to capture effects that are difficult to
characterize analytically or summarize statistically. However, in many
real-world applications, these simulations need to be inverted to match the
observed data. This typically requires the custom design, derivation and
implementation of sophisticated inversion algorithms. Here we give a framework
for inverting a broad class of complex software simulators via probabilistic
programming and automatic inference, using under 20 lines of probabilistic
code. Our approach is based on a formulation of inversion as approximate
inference in a simple sequential probabilistic model. We implement four
inference strategies, including Metropolis-Hastings, a sequentialized
Metropolis-Hastings scheme, and a particle Markov chain Monte Carlo scheme,
requiring 4 or fewer lines of probabilistic code each. We demonstrate our
framework by applying it to invert a real geological software simulator from
the oil and gas industry.
Interactive Knowledge Base Population
Authors: Travis Wolfe, Mark Dredze, James Mayfield, Paul McNamee, Craig Harman, Tim Finin, Benjamin Van Durme
Date: 2015-05-31 00:00:00
Tasks: Knowledge Base Population

Most work on building knowledge bases has focused on collecting entities and
facts from as large a collection of documents as possible. We argue for and
describe a new paradigm where the focus is on a high-recall extraction over a
small collection of documents under the supervision of a human expert, that we
call Interactive Knowledge Base Population (IKBP).