pwc-archive/papers-with-abstracts huggingface dataset:
Spatial Symmetry Driven Pruning Strategies for Efficient Declarative Spatial Reasoning
Authors: Carl Schultz, Mehul Bhatt
Date: 2015-06-16 00:00:00
Tasks: Spatial Reasoning

Declarative spatial reasoning denotes the ability to (declaratively) specify
and solve real-world problems related to geometric and qualitative spatial
representation and reasoning within standard knowledge representation and
reasoning (KR) based methods (e.g., logic programming and derivatives). One
approach for encoding the semantics of spatial relations within a declarative
programming framework is by systems of polynomial constraints. However, solving
such constraints is computationally intractable in general (i.e. the theory of
real-closed fields).
  We present a new algorithm, implemented within the declarative spatial
reasoning system CLP(QS), that drastically improves the performance of deciding
the consistency of spatial constraint graphs over conventional polynomial
encodings. We develop pruning strategies founded on spatial symmetries that
form equivalence classes (based on affine transformations) at the qualitative
spatial level. Moreover, pruning strategies are themselves formalised as
knowledge about the properties of space and spatial symmetries. We evaluate our
algorithm using a range of benchmarks in the class of contact problems, and
proofs in mereology and geometry. The empirical results show that CLP(QS) with
knowledge-based spatial pruning outperforms conventional polynomial encodings
by orders of magnitude, and can thus be applied to problems that are otherwise
unsolvable in practice.
Recognize Foreign Low-Frequency Words with Similar Pairs
Authors: Xi Ma, Xiaoxi Wang, Dong Wang, Zhiyong Zhang
Date: 2015-06-16 00:00:00
Tasks: Automatic Speech Recognition, Automatic Speech Recognition (ASR), Language Modeling, Language Modelling, speech-recognition, Speech Recognition

Low-frequency words place a major challenge for automatic speech recognition
(ASR). The probabilities of these words, which are often important name
entities, are generally under-estimated by the language model (LM) due to their
limited occurrences in the training data. Recently, we proposed a word-pair
approach to deal with the problem, which borrows information of frequent words
to enhance the probabilities of low-frequency words. This paper presents an
extension to the word-pair method by involving multiple `predicting words' to
produce better estimation for low-frequency words. We also employ this approach
to deal with out-of-language words in the task of multi-lingual speech
recognition.
Post-Reconstruction Deconvolution of PET Images by Total Generalized Variation Regularization
Authors: Stéphanie Guérit, Laurent Jacques, Benoît Macq, John A. Lee
Date: 2015-06-16 00:00:00
Tasks: Image Deconvolution

Improving the quality of positron emission tomography (PET) images, affected
by low resolution and high level of noise, is a challenging task in nuclear
medicine and radiotherapy. This work proposes a restoration method, achieved
after tomographic reconstruction of the images and targeting clinical
situations where raw data are often not accessible. Based on inverse problem
methods, our contribution introduces the recently developed total generalized
variation (TGV) norm to regularize PET image deconvolution. Moreover, we
stabilize this procedure with additional image constraints such as positivity
and photometry invariance. A criterion for updating and adjusting automatically
the regularization parameter in case of Poisson noise is also presented.
Experiments are conducted on both synthetic data and real patient images.
ASPMT(QS): Non-Monotonic Spatial Reasoning with Answer Set Programming Modulo Theories
Authors: Przemysław Andrzej Wałęga, Mehul Bhatt, Carl Schultz
Date: 2015-06-16 00:00:00
Tasks: Spatial Reasoning

The systematic modelling of \emph{dynamic spatial systems} [9] is a key
requirement in a wide range of application areas such as comonsense cognitive
robotics, computer-aided architecture design, dynamic geographic information
systems. We present ASPMT(QS), a novel approach and fully-implemented prototype
for non-monotonic spatial reasoning ---a crucial requirement within dynamic
spatial systems-- based on Answer Set Programming Modulo Theories (ASPMT).
ASPMT(QS) consists of a (qualitative) spatial representation module (QS) and a
method for turning tight ASPMT instances into Sat Modulo Theories (SMT)
instances in order to compute stable models by means of SMT solvers. We
formalise and implement concepts of default spatial reasoning and spatial frame
axioms using choice formulas. Spatial reasoning is performed by encoding
spatial relations as systems of polynomial constraints, and solving via SMT
with the theory of real nonlinear arithmetic. We empirically evaluate ASPMT(QS)
in comparison with other prominent contemporary spatial reasoning systems. Our
results show that ASPMT(QS) is the only existing system that is capable of
reasoning about indirect spatial effects (i.e. addressing the ramification
problem), and integrating geometric and qualitative spatial information within
a non-monotonic spatial reasoning context.
Subsampled terahertz data reconstruction based on spatio-temporal dictionary learning
Authors: Vahid Abolghasemi, Hao Shen, Yaochun Shen, Lu Gan
Date: 2015-06-16 00:00:00
Tasks: Dictionary Learning

In this paper, the problem of terahertz pulsed imaging and reconstruction is
addressed. It is assumed that an incomplete (subsampled) three dimensional THz
data set has been acquired and the aim is to recover all missing samples. A
sparsity-inducing approach is proposed for this purpose. First, a simple
interpolation is applied to incomplete noisy data. Then, we propose a
spatio-temporal dictionary learning method to obtain an appropriate sparse
representation of data based on a joint sparse recovery algorithm. Then, using
the sparse coefficients and the learned dictionary, the 3D data is effectively
denoised by minimizing a simple cost function. We consider two types of
terahertz data to evaluate the performance of the proposed approach; THz data
acquired for a model sample with clear layered structures (e.g., a T-shape
plastic sheet buried in a polythene pellet), and pharmaceutical tablet data
(with low spatial resolution). The achieved signal-to-noise-ratio for
reconstruction of T-shape data, from only 5% observation was 19 dB. Moreover,
the accuracies of obtained thickness and depth measurements for pharmaceutical
tablet data after reconstruction from 10% observation were 98.8%, and 99.9%,
respectively. These results, along with chemical mapping analysis, presented at
the end of this paper, confirm the accuracy of the proposed method.
Parsing Natural Language Sentences by Semi-supervised Methods
Authors: Rudolf Rosa
Date: 2015-06-16 00:00:00

We present our work on semi-supervised parsing of natural language sentences,
focusing on multi-source crosslingual transfer of delexicalized dependency
parsers. We first evaluate the influence of treebank annotation styles on
parsing performance, focusing on adposition attachment style. Then, we present
KLcpos3, an empirical language similarity measure, designed and tuned for
source parser weighting in multi-source delexicalized parser transfer. And
finally, we introduce a novel resource combination method, based on
interpolation of trained parser models.
Learning Super-Resolution Jointly from External and Internal Examples
Authors: Zhangyang Wang, Yingzhen Yang, Zhaowen Wang, Shiyu Chang, Jianchao Yang, Thomas S. Huang
Date: 2015-03-03 00:00:00
Tasks: Image Super-Resolution, Super-Resolution

Single image super-resolution (SR) aims to estimate a high-resolution (HR)
image from a lowresolution (LR) input. Image priors are commonly learned to
regularize the otherwise seriously ill-posed SR problem, either using external
LR-HR pairs or internal similar patterns. We propose joint SR to adaptively
combine the advantages of both external and internal SR methods. We define two
loss functions using sparse coding based external examples, and epitomic
matching based on internal examples, as well as a corresponding adaptive weight
to automatically balance their contributions according to their reconstruction
errors. Extensive SR results demonstrate the effectiveness of the proposed
method over the existing state-of-the-art methods, and is also verified by our
subjective evaluation study.
Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates
Authors: Zeyuan Allen-Zhu, Zhenyu Liao, Lorenzo Orecchia
Date: 2015-06-16 00:00:00

In this paper, we provide a novel construction of the linear-sized spectral
sparsifiers of Batson, Spielman and Srivastava [BSS14]. While previous
constructions required $\Omega(n^4)$ running time [BSS14, Zou12], our
sparsification routine can be implemented in almost-quadratic running time
$O(n^{2+\varepsilon})$.
  The fundamental conceptual novelty of our work is the leveraging of a strong
connection between sparsification and a regret minimization problem over
density matrices. This connection was known to provide an interpretation of the
randomized sparsifiers of Spielman and Srivastava [SS11] via the application of
matrix multiplicative weight updates (MWU) [CHS11, Vis14]. In this paper, we
explain how matrix MWU naturally arises as an instance of the
Follow-the-Regularized-Leader framework and generalize this approach to yield a
larger class of updates. This new class allows us to accelerate the
construction of linear-sized spectral sparsifiers, and give novel insights on
the motivation behind Batson, Spielman and Srivastava [BSS14].
Semi-Stochastic Gradient Descent Methods
Authors: Jakub Konečný, Peter Richtárik
Date: 2013-12-05 00:00:00

In this paper we study the problem of minimizing the average of a large
number ($n$) of smooth convex loss functions. We propose a new method, S2GD
(Semi-Stochastic Gradient Descent), which runs for one or several epochs in
each of which a single full gradient and a random number of stochastic
gradients is computed, following a geometric law. The total work needed for the
method to output an $\varepsilon$-accurate solution in expectation, measured in
the number of passes over data, or equivalently, in units equivalent to the
computation of a single gradient of the loss, is
$O((\kappa/n)\log(1/\varepsilon))$, where $\kappa$ is the condition number.
This is achieved by running the method for $O(\log(1/\varepsilon))$ epochs,
with a single gradient evaluation and $O(\kappa)$ stochastic gradient
evaluations in each. The SVRG method of Johnson and Zhang arises as a special
case. If our method is limited to a single epoch only, it needs to evaluate at
most $O((\kappa/\varepsilon)\log(1/\varepsilon))$ stochastic gradients. In
contrast, SVRG requires $O(\kappa/\varepsilon^2)$ stochastic gradients. To
illustrate our theoretical results, S2GD only needs the workload equivalent to
about 2.1 full gradient evaluations to find an $10^{-6}$-accurate solution for
a problem with $n=10^9$ and $\kappa=10^3$.
Exploiting Text and Network Context for Geolocation of Social Media Users
Authors: Afshin Rahimi, Duy Vu, Trevor Cohn, Timothy Baldwin
Date: 2015-06-16 00:00:00
Proceeding: HLT 2015 5

Research on automatically geolocating social media users has conventionally
been based on the text content of posts from a given user or the social network
of the user, with very little crossover between the two, and no bench-marking
of the two approaches over compara- ble datasets. We bring the two threads of
research together in first proposing a text-based method based on adaptive
grids, followed by a hybrid network- and text-based method. Evaluating over
three Twitter datasets, we show that the empirical difference between text- and
network-based methods is not great, and that hybridisation of the two is
superior to the component methods, especially in contexts where the user graph
is not well connected. We achieve state-of-the-art results on all three
datasets.
Is Joint Training Better for Deep Auto-Encoders?
Authors: Yingbo Zhou, Devansh Arpit, Ifeoma Nwogu, Venu Govindaraju
Date: 2014-05-06 00:00:00

Traditionally, when generative models of data are developed via deep
architectures, greedy layer-wise pre-training is employed. In a well-trained
model, the lower layer of the architecture models the data distribution
conditional upon the hidden variables, while the higher layers model the hidden
distribution prior. But due to the greedy scheme of the layerwise training
technique, the parameters of lower layers are fixed when training higher
layers. This makes it extremely challenging for the model to learn the hidden
distribution prior, which in turn leads to a suboptimal model for the data
distribution. We therefore investigate joint training of deep autoencoders,
where the architecture is viewed as one stack of two or more single-layer
autoencoders. A single global reconstruction objective is jointly optimized,
such that the objective for the single autoencoders at each layer acts as a
local, layer-level regularizer. We empirically evaluate the performance of this
joint training scheme and observe that it not only learns a better data model,
but also learns better higher layer representations, which highlights its
potential for unsupervised feature learning. In addition, we find that the
usage of regularizations in the joint training scheme is crucial in achieving
good performance. In the supervised setting, joint training also shows superior
performance when training deeper models. The joint training framework can thus
provide a platform for investigating more efficient usage of different types of
regularizers, especially in light of the growing volumes of available unlabeled
data.
Incremental Knowledge Base Construction Using DeepDive
Authors: Jaeho Shin, Sen Wu, Feiran Wang, Christopher De Sa, Ce Zhang, Christopher Ré
Date: 2015-02-03 00:00:00
Tasks: Knowledge Base Construction

Populating a database with unstructured information is a long-standing
problem in industry and research that encompasses problems of extraction,
cleaning, and integration. Recent names used for this problem include dealing
with dark data and knowledge base construction (KBC). In this work, we describe
DeepDive, a system that combines database and machine learning ideas to help
develop KBC systems, and we present techniques to make the KBC process more
efficient. We observe that the KBC process is iterative, and we develop
techniques to incrementally produce inference results for KBC systems. We
propose two methods for incremental inference, based respectively on sampling
and variational techniques. We also study the tradeoff space of these methods
and develop a simple rule-based optimizer. DeepDive includes all of these
contributions, and we evaluate DeepDive on five KBC systems, showing that it
can speed up KBC inference tasks by up to two orders of magnitude with
negligible impact on quality.
Encog: Library of Interchangeable Machine Learning Models for Java and C#
Authors: Jeff Heaton
Date: 2015-06-15 00:00:00
Tasks: BIG-bench Machine Learning, Clustering, General Classification, regression

This paper introduces the Encog library for Java and C#, a scalable,
adaptable, multiplatform machine learning framework that was 1st released in
2008. Encog allows a variety of machine learning models to be applied to
datasets using regression, classification, and clustering. Various supported
machine learning models can be used interchangeably with minimal recoding.
Encog uses efficient multithreaded code to reduce training time by exploiting
modern multicore processors. The current version of Encog can be downloaded
from http://www.encog.org.
Image-based Recommendations on Styles and Substitutes
Authors: Julian McAuley, Christopher Targett, Qinfeng Shi, Anton Van Den Hengel
Date: 2015-06-15 00:00:00

Humans inevitably develop a sense of the relationships between objects, some
of which are based on their appearance. Some pairs of objects might be seen as
being alternatives to each other (such as two pairs of jeans), while others may
be seen as being complementary (such as a pair of jeans and a matching shirt).
This information guides many of the choices that people make, from buying
clothes to their interactions with each other. We seek here to model this human
sense of the relationships between objects based on their appearance. Our
approach is not based on fine-grained modeling of user annotations but rather
on capturing the largest dataset possible and developing a scalable method for
uncovering human notions of the visual relationships within. We cast this as a
network inference problem defined on graphs of related images, and provide a
large-scale dataset for the training and evaluation of the same. The system we
develop is capable of recommending which clothes and accessories will go well
together (and which will not), amongst a host of other applications.
Linguistic Harbingers of Betrayal: A Case Study on an Online Strategy Game
Authors: Vlad Niculae, Srijan Kumar, Jordan Boyd-Graber, Cristian Danescu-Niculescu-Mizil
Date: 2015-06-15 00:00:00
Proceeding: IJCNLP 2015 7
Tasks: Form

Interpersonal relations are fickle, with close friendships often dissolving
into enmity. In this work, we explore linguistic cues that presage such
transitions by studying dyadic interactions in an online strategy game where
players form alliances and break those alliances through betrayal. We
characterize friendships that are unlikely to last and examine temporal
patterns that foretell betrayal.
  We reveal that subtle signs of imminent betrayal are encoded in the
conversational patterns of the dyad, even if the victim is not aware of the
relationship's fate. In particular, we find that lasting friendships exhibit a
form of balance that manifests itself through language. In contrast, sudden
changes in the balance of certain conversational attributes---such as positive
sentiment, politeness, or focus on future planning---signal impending betrayal.
Fast Two-Sample Testing with Analytic Representations of Probability Measures
Authors: Kacper Chwialkowski, Aaditya Ramdas, Dino Sejdinovic, Arthur Gretton
Date: 2015-06-15 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Two-sample testing, Vocal Bursts Valence Prediction

We propose a class of nonparametric two-sample tests with a cost linear in
the sample size. Two tests are given, both based on an ensemble of distances
between analytic functions representing each of the distributions. The first
test uses smoothed empirical characteristic functions to represent the
distributions, the second uses distribution embeddings in a reproducing kernel
Hilbert space. Analyticity implies that differences in the distributions may be
detected almost surely at a finite number of randomly chosen
locations/frequencies. The new tests are consistent against a larger class of
alternatives than the previous linear-time tests based on the (non-smoothed)
empirical characteristic functions, while being much faster than the current
state-of-the-art quadratic-time kernel-based or energy distance-based tests.
Experiments on artificial benchmarks and on challenging real-world testing
problems demonstrate that our tests give a better power/time tradeoff than
competing approaches, and in some cases, better outright power than even the
most expensive quadratic-time tests. This performance advantage is retained
even in high dimensions, and in cases where the difference in distributions is
not observable with low order statistics.
Automatic Layer Separation using Light Field Imaging
Authors: Qiaosong Wang, Haiting Lin, Yi Ma, Sing Bing Kang, Jingyi Yu
Date: 2015-06-15 00:00:00
Tasks: 3D geometry

We propose a novel approach that jointly removes reflection or translucent
layer from a scene and estimates scene depth. The input data are captured via
light field imaging. The problem is couched as minimizing the rank of the
transmitted scene layer via Robust Principle Component Analysis (RPCA). We also
impose regularization based on piecewise smoothness, gradient sparsity, and
layer independence to simultaneously recover 3D geometry of the transmitted
layer. Experimental results on synthetic and real data show that our technique
is robust and reliable, and can handle a broad range of layer separation
problems.
Latent Regression Bayesian Network for Data Representation
Authors: Siqi Nie, Qiang Ji
Date: 2015-06-15 00:00:00
Tasks: regression

Deep directed generative models have attracted much attention recently due to
their expressive representation power and the ability of ancestral sampling.
One major difficulty of learning directed models with many latent variables is
the intractable inference. To address this problem, most existing algorithms
make assumptions to render the latent variables independent of each other,
either by designing specific priors, or by approximating the true posterior
using a factorized distribution. We believe the correlations among latent
variables are crucial for faithful data representation. Driven by this idea, we
propose an inference method based on the conditional pseudo-likelihood that
preserves the dependencies among the latent variables. For learning, we propose
to employ the hard Expectation Maximization (EM) algorithm, which avoids the
intractability of the traditional EM by max-out instead of sum-out to compute
the data likelihood. Qualitative and quantitative evaluations of our model
against state of the art deep models on benchmark datasets demonstrate the
effectiveness of the proposed algorithm in data representation and
reconstruction.
Leveraging the Power of Gabor Phase for Face Identification: A Block Matching Approach
Authors: Yang Zhong, Hai-Bo Li
Date: 2015-06-15 00:00:00
Tasks: Face Identification, Face Recognition, Face Verification

Different from face verification, face identification is much more demanding.
To reach comparable performance, an identifier needs to be roughly N times
better than a verifier. To expect a breakthrough in face identification, we
need a fresh look at the fundamental building blocks of face recognition. In
this paper we focus on the selection of a suitable signal representation and
better matching strategy for face identification. We demonstrate how Gabor
phase could be leveraged to improve the performance of face identification by
using the Block Matching method. Compared to the existing approaches, the
proposed method features much lower algorithmic complexity: face images are
only filtered by a single-scale Gabor filter pair and the matching is performed
between any pairs of face images at hand without involving any training
process. Benchmark evaluations show that the proposed approach is totally
comparable to and even better than state-of-the-art algorithms, which are
typically based on more features extracted from a large set of Gabor faces
and/or rely on heavy training processes.
Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
Authors: Zheng Qu, Peter Richtárik
Date: 2014-12-27 00:00:00

We study the problem of minimizing the sum of a smooth convex function and a
convex block-separable regularizer and propose a new randomized coordinate
descent method, which we call ALPHA. Our method at every iteration updates a
random subset of coordinates, following an arbitrary distribution. No
coordinate descent methods capable to handle an arbitrary sampling have been
studied in the literature before for this problem. ALPHA is a remarkably
flexible algorithm: in special cases, it reduces to deterministic and
randomized methods such as gradient descent, coordinate descent, parallel
coordinate descent and distributed coordinate descent -- both in nonaccelerated
and accelerated variants. The variants with arbitrary (or importance) sampling
are new. We provide a complexity analysis of ALPHA, from which we deduce as a
direct corollary complexity bounds for its many variants, all matching or
improving best known bounds.