pwc-archive/papers-with-abstracts huggingface dataset:
Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity
Authors: Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir Podolskii, Michael Zakharyaschev
Date: 2016-05-04 00:00:00

We give solutions to two fundamental computational problems in ontology-based
data access with the W3C standard ontology language OWL 2 QL: the succinctness
problem for first-order rewritings of ontology-mediated queries (OMQs), and the
complexity problem for OMQ answering. We classify OMQs according to the shape
of their conjunctive queries (treewidth, the number of leaves) and the
existential depth of their ontologies. For each of these classes, we determine
the combined complexity of OMQ answering, and whether all OMQs in the class
have polynomial-size first-order, positive existential, and nonrecursive
datalog rewritings. We obtain the succinctness results using hypergraph
programs, a new computational model for Boolean functions, which makes it
possible to connect the size of OMQ rewritings and circuit complexity.
IISCNLP at SemEval-2016 Task 2: Interpretable STS with ILP based Multiple Chunk Aligner
Authors: Lavanya Sita Tekumalla, Sharmistha
Date: 2016-05-04 00:00:00
Tasks: Semantic Textual Similarity, Sentence, Sentence Similarity, STS, Task 2

Interpretable semantic textual similarity (iSTS) task adds a crucial
explanatory layer to pairwise sentence similarity. We address various
components of this task: chunk level semantic alignment along with assignment
of similarity type and score for aligned chunks with a novel system presented
in this paper. We propose an algorithm, iMATCH, for the alignment of multiple
non-contiguous chunks based on Integer Linear Programming (ILP). Similarity
type and score assignment for pairs of chunks is done using a supervised
multiclass classification technique based on Random Forrest Classifier. Results
show that our algorithm iMATCH has low execution time and outperforms most
other participating systems in terms of alignment score. Of the three datasets,
we are top ranked for answer- students dataset in terms of overall score and
have top alignment score for headlines dataset in the gold chunks track.
A Generic Method for Automatic Ground Truth Generation of Camera-captured Documents
Authors: Sheraz Ahmed, Muhammad Imran Malik, Muhammad Zeshan Afzal, Koichi Kise, Masakazu Iwamura, Andreas Dengel, Marcus Liwicki
Date: 2016-05-04 00:00:00
Tasks: Articles, Optical Character Recognition (OCR)

The contribution of this paper is fourfold. The first contribution is a
novel, generic method for automatic ground truth generation of camera-captured
document images (books, magazines, articles, invoices, etc.). It enables us to
build large-scale (i.e., millions of images) labeled camera-captured/scanned
documents datasets, without any human intervention. The method is generic,
language independent and can be used for generation of labeled documents
datasets (both scanned and cameracaptured) in any cursive and non-cursive
language, e.g., English, Russian, Arabic, Urdu, etc. To assess the
effectiveness of the presented method, two different datasets in English and
Russian are generated using the presented method. Evaluation of samples from
the two datasets shows that 99:98% of the images were correctly labeled. The
second contribution is a large dataset (called C3Wi) of camera-captured
characters and words images, comprising 1 million word images (10 million
character images), captured in a real camera-based acquisition. This dataset
can be used for training as well as testing of character recognition systems on
camera-captured documents. The third contribution is a novel method for the
recognition of cameracaptured document images. The proposed method is based on
Long Short-Term Memory and outperforms the state-of-the-art methods for camera
based OCRs. As a fourth contribution, various benchmark tests are performed to
uncover the behavior of commercial (ABBYY), open source (Tesseract), and the
presented camera-based OCR using the presented C3Wi dataset. Evaluation results
reveal that the existing OCRs, which already get very high accuracies on
scanned documents, have limited performance on camera-captured document images;
where ABBYY has an accuracy of 75%, Tesseract an accuracy of 50.22%, while the
presented character recognition system has an accuracy of 95.10%.
Linear Bandit algorithms using the Bootstrap
Authors: Nandan Sudarsanam, Balaraman Ravindran
Date: 2016-05-04 00:00:00
Tasks: Thompson Sampling

This study presents two new algorithms for solving linear stochastic bandit
problems. The proposed methods use an approach from non-parametric statistics
called bootstrapping to create confidence bounds. This is achieved without
making any assumptions about the distribution of noise in the underlying
system. We present the X-Random and X-Fixed bootstrap bandits which correspond
to the two well-known approaches for conducting bootstraps on models, in the
literature. The proposed methods are compared to other popular solutions for
linear stochastic bandit problems, namely, OFUL, LinUCB and Thompson Sampling.
The comparisons are carried out using a simulation study on a hierarchical
probability meta-model, built from published data of experiments, which are run
on real systems. The model representing the response surfaces is conceptualized
as a Bayesian Network which is presented with varying degrees of noise for the
simulations. One of the proposed methods, X-Random bootstrap, performs better
than the baselines in-terms of cumulative regret across various degrees of
noise and different number of trials. In certain settings the cumulative regret
of this method is less than half of the best baseline. The X-Fixed bootstrap
performs comparably in most situations and particularly well when the number of
trials is low. The study concludes that these algorithms could be a preferred
alternative for solving linear bandit problems, especially when the
distribution of the noise in the system is unknown.
A Step from Probabilistic Programming to Cognitive Architectures
Authors: Alexey Potapov
Date: 2016-05-04 00:00:00
Tasks: Probabilistic Programming

Probabilistic programming is considered as a framework, in which basic
components of cognitive architectures can be represented in unified and elegant
fashion. At the same time, necessity of adopting some component of cognitive
architectures for extending capabilities of probabilistic programming languages
is pointed out. In particular, implicit specification of generative models via
declaration of concepts and links between them is proposed, and usefulness of
declarative knowledge for achieving efficient inference is briefly discussed.
Towards Better Analysis of Deep Convolutional Neural Networks
Authors: Mengchen Liu, Jiaxin Shi, Zhen Li, Chongxuan Li, Jun Zhu, Shixia Liu
Date: 2016-04-24 00:00:00
Tasks: image-classification, Image Classification

Deep convolutional neural networks (CNNs) have achieved breakthrough
performance in many pattern recognition tasks such as image classification.
However, the development of high-quality deep models typically relies on a
substantial amount of trial-and-error, as there is still no clear understanding
of when and why a deep model works. In this paper, we present a visual
analytics approach for better understanding, diagnosing, and refining deep
CNNs. We formulate a deep CNN as a directed acyclic graph. Based on this
formulation, a hybrid visualization is developed to disclose the multiple
facets of each neuron and the interactions between them. In particular, we
introduce a hierarchical rectangle packing algorithm and a matrix reordering
algorithm to show the derived features of a neuron cluster. We also propose a
biclustering-based edge bundling method to reduce visual clutter caused by a
large number of connections between neurons. We evaluated our method on a set
of CNNs and the results are generally favorable.
Application of Deep Convolutional Neural Networks for Detecting Extreme Weather in Climate Datasets
Authors: Yunjie Liu, Evan Racah, Prabhat, Joaquin Correa, Amir Khosrowshahi, David Lavers, Kenneth Kunkel, Michael Wehner, William Collins
Date: 2016-05-04 00:00:00
Tasks: Event Detection

Detecting extreme events in large datasets is a major challenge in climate
science research. Current algorithms for extreme event detection are build upon
human expertise in defining events based on subjective thresholds of relevant
physical variables. Often, multiple competing methods produce vastly different
results on the same dataset. Accurate characterization of extreme events in
climate simulations and observational data archives is critical for
understanding the trends and potential impacts of such events in a climate
change content. This study presents the first application of Deep Learning
techniques as alternative methodology for climate extreme events detection.
Deep neural networks are able to learn high-level representations of a broad
class of patterns from labeled data. In this work, we developed deep
Convolutional Neural Network (CNN) classification system and demonstrated the
usefulness of Deep Learning technique for tackling climate pattern detection
problems. Coupled with Bayesian based hyper-parameter optimization scheme, our
deep CNN system achieves 89\%-99\% of accuracy in detecting extreme events
(Tropical Cyclones, Atmospheric Rivers and Weather Fronts
Ethnicity sensitive author disambiguation using semi-supervised learning
Authors: Gilles Louppe, Hussein Al-Natsheh, Mateusz Susik, Eamonn Maguire
Date: 2015-08-31 00:00:00
Tasks: Blocking, Clustering

Author name disambiguation in bibliographic databases is the problem of
grouping together scientific publications written by the same person,
accounting for potential homonyms and/or synonyms. Among solutions to this
problem, digital libraries are increasingly offering tools for authors to
manually curate their publications and claim those that are theirs. Indirectly,
these tools allow for the inexpensive collection of large annotated training
data, which can be further leveraged to build a complementary automated
disambiguation system capable of inferring patterns for identifying
publications written by the same person. Building on more than 1 million
publicly released crowdsourced annotations, we propose an automated author
disambiguation solution exploiting this data (i) to learn an accurate
classifier for identifying coreferring authors and (ii) to guide the clustering
of scientific publications by distinct authors in a semi-supervised way. To the
best of our knowledge, our analysis is the first to be carried out on data of
this size and coverage. With respect to the state of the art, we validate the
general pipeline used in most existing solutions, and improve by: (i) proposing
phonetic-based blocking strategies, thereby increasing recall; and (ii) adding
strong ethnicity-sensitive features for learning a linkage function, thereby
tailoring disambiguation to non-Western author names whenever necessary.
Learning from Binary Labels with Instance-Dependent Corruption
Authors: Aditya Krishna Menon, Brendan van Rooyen, Nagarajan Natarajan
Date: 2016-05-03 00:00:00

Suppose we have a sample of instances paired with binary labels corrupted by
arbitrary instance- and label-dependent noise. With sufficiently many such
samples, can we optimally classify and rank instances with respect to the
noise-free distribution? We provide a theoretical analysis of this question,
with three main contributions. First, we prove that for instance-dependent
noise, any algorithm that is consistent for classification on the noisy
distribution is also consistent on the clean distribution. Second, we prove
that for a broad class of instance- and label-dependent noise, a similar
consistency result holds for the area under the ROC curve. Third, for the
latter noise model, when the noise-free class-probability function belongs to
the generalised linear model family, we show that the Isotron can efficiently
and provably learn from the corrupted sample.
Semantics for probabilistic programming: higher-order functions, continuous distributions, and soft constraints
Authors: Sam Staton, Hongseok Yang, Chris Heunen, Ohad Kammar, Frank Wood
Date: 2016-01-19 00:00:00
Tasks: Probabilistic Programming

We study the semantic foundation of expressive probabilistic programming
languages, that support higher-order functions, continuous distributions, and
soft constraints (such as Anglican, Church, and Venture). We define a
metalanguage (an idealised version of Anglican) for probabilistic computation
with the above features, develop both operational and denotational semantics,
and prove soundness, adequacy, and termination. They involve measure theory,
stochastic labelled transition systems, and functor categories, but admit
intuitive computational readings, one of which views sampled random variables
as dynamically allocated read-only variables. We apply our semantics to
validate nontrivial equations underlying the correctness of certain compiler
optimisations and inference algorithms such as sequential Monte Carlo
simulation. The language enables defining probability distributions on
higher-order functions, and we study their properties.
RSG: Beating Subgradient Method without Smoothness and Strong Convexity
Authors: Tianbao Yang, Qihang Lin
Date: 2015-12-09 00:00:00

In this paper, we study the efficiency of a {\bf R}estarted {\bf S}ub{\bf
G}radient (RSG) method that periodically restarts the standard subgradient
method (SG). We show that, when applied to a broad class of convex optimization
problems, RSG method can find an $\epsilon$-optimal solution with a low
complexity than SG method. In particular, we first show that RSG can reduce the
dependence of SG's iteration complexity on the distance between the initial
solution and the optimal set to that between the $\epsilon$-level set and the
optimal set. In addition, we show the advantages of RSG over SG in solving
three different families of convex optimization problems. (a) For the problems
whose epigraph is a polyhedron, RSG is shown to converge linearly. (b) For the
problems with local quadratic growth property, RSG has an
$O(\frac{1}{\epsilon}\log(\frac{1}{\epsilon}))$ iteration complexity. (c) For
the problems that admit a local Kurdyka-\L ojasiewicz property with a power
constant of $\beta\in[0,1)$, RSG has an
$O(\frac{1}{\epsilon^{2\beta}}\log(\frac{1}{\epsilon}))$ iteration complexity.
On the contrary, with only the standard analysis, the iteration complexity of
SG is known to be $O(\frac{1}{\epsilon^2})$ for these three classes of
problems. The novelty of our analysis lies at exploiting the lower bound of the
first-order optimality residual at the $\epsilon$-level set. It is this novelty
that allows us to explore the local properties of functions (e.g., local
quadratic growth property, local Kurdyka-\L ojasiewicz property, more generally
local error bounds) to develop the improved convergence of RSG. We demonstrate
the effectiveness of the proposed algorithms on several machine learning tasks
including regression and classification.
Mining Discriminative Triplets of Patches for Fine-Grained Classification
Authors: Yaming Wang, Jonghyun Choi, Vlad I. Morariu, Larry S. Davis
Date: 2016-05-04 00:00:00
Proceeding: CVPR 2016 6
Tasks: Classification, General Classification

Fine-grained classification involves distinguishing between similar
sub-categories based on subtle differences in highly localized regions;
therefore, accurate localization of discriminative regions remains a major
challenge. We describe a patch-based framework to address this problem. We
introduce triplets of patches with geometric constraints to improve the
accuracy of patch localization, and automatically mine discriminative
geometrically-constrained triplets for classification. The resulting approach
only requires object bounding boxes. Its effectiveness is demonstrated using
four publicly available fine-grained datasets, on which it outperforms or
achieves comparable performance to the state-of-the-art in classification.
Optimizing Neural Networks with Kronecker-factored Approximate Curvature
Authors: James Martens, Roger Grosse
Date: 2015-03-19 00:00:00
Tasks: Stochastic Optimization

We propose an efficient method for approximating natural gradient descent in neural networks which we call Kronecker-Factored Approximate Curvature (K-FAC). K-FAC is based on an efficiently invertible approximation of a neural network's Fisher information matrix which is neither diagonal nor low-rank, and in some cases is completely non-sparse. It is derived by approximating various large blocks of the Fisher (corresponding to entire layers) as being the Kronecker product of two much smaller matrices. While only several times more expensive to compute than the plain stochastic gradient, the updates produced by K-FAC make much more progress optimizing the objective, which results in an algorithm that can be much faster than stochastic gradient descent with momentum in practice. And unlike some previously proposed approximate natural-gradient/Newton methods which use high-quality non-diagonal curvature matrices (such as Hessian-free optimization), K-FAC works very well in highly stochastic optimization regimes. This is because the cost of storing and inverting K-FAC's approximation to the curvature matrix does not depend on the amount of data used to estimate it, which is a feature typically associated only with diagonal or low-rank approximations to the curvature matrix.
Asymptotic Theory for Random Forests
Authors: Stefan Wager
Date: 2014-05-02 00:00:00

Random forests have proven to be reliable predictive algorithms in many
application areas. Not much is known, however, about the statistical properties
of random forests. Several authors have established conditions under which
their predictions are consistent, but these results do not provide practical
estimates of random forest errors. In this paper, we analyze a random forest
model based on subsampling, and show that random forest predictions are
asymptotically normal provided that the subsample size s scales as s(n)/n =
o(log(n)^{-d}), where n is the number of training examples and d is the number
of features. Moreover, we show that the asymptotic variance can consistently be
estimated using an infinitesimal jackknife for bagged ensembles recently
proposed by Efron (2014). In other words, our results let us both characterize
and estimate the error-distribution of random forest predictions, thus taking a
step towards making random forests tools for statistical inference instead of
just black-box predictive algorithms.
A heuristic algorithm for a single vehicle static bike sharing rebalancing problem
Authors: Fábio Cruz, Anand Subramanian, Bruno P. Bruck, Manuel Iori
Date: 2016-05-02 00:00:00

The static bike rebalancing problem (SBRP) concerns the task of repositioning
bikes among stations in self-service bike-sharing systems. This problem can be
seen as a variant of the one-commodity pickup and delivery vehicle routing
problem, where multiple visits are allowed to be performed at each station,
i.e., the demand of a station is allowed to be split. Moreover, a vehicle may
temporarily drop its load at a station, leaving it in excess or, alternatively,
collect more bikes from a station (even all of them), thus leaving it in
default. Both cases require further visits in order to meet the actual demands
of such station. This paper deals with a particular case of the SBRP, in which
only a single vehicle is available and the objective is to find a least-cost
route that meets the demand of all stations and does not violate the minimum
(zero) and maximum (vehicle capacity) load limits along the tour. Therefore,
the number of bikes to be collected or delivered at each station should be
appropriately determined in order to respect such constraints. We propose an
iterated local search (ILS) based heuristic to solve the problem. The ILS
algorithm was tested on 980 benchmark instances from the literature and the
results obtained are quite competitive when compared to other existing methods.
Moreover, our heuristic was capable of finding most of the known optimal
solutions and also of improving the results on a number of open instances.
MOT16: A Benchmark for Multi-Object Tracking
Authors: Anton Milan, Laura Leal-Taixe, Ian Reid, Stefan Roth, Konrad Schindler
Date: 2016-03-02 00:00:00
Tasks: Multi-Object Tracking, Multiple Object Tracking, Multiple People Tracking, Object, Object Tracking

Standardized benchmarks are crucial for the majority of computer vision
applications. Although leaderboards and ranking tables should not be
over-claimed, benchmarks often provide the most objective measure of
performance and are therefore important guides for reseach.
  Recently, a new benchmark for Multiple Object Tracking, MOTChallenge, was
launched with the goal of collecting existing and new data and creating a
framework for the standardized evaluation of multiple object tracking methods.
The first release of the benchmark focuses on multiple people tracking, since
pedestrians are by far the most studied object in the tracking community. This
paper accompanies a new release of the MOTChallenge benchmark. Unlike the
initial release, all videos of MOT16 have been carefully annotated following a
consistent protocol. Moreover, it not only offers a significant increase in the
number of labeled boxes, but also provides multiple object classes beside
pedestrians and the level of visibility for every single object of interest.
An evaluation of randomized machine learning methods for redundant data: Predicting short and medium-term suicide risk from administrative records and risk assessments
Authors: Thuong Nguyen, Truyen Tran, Shivapratap Gopakumar, Dinh Phung, Svetha Venkatesh
Date: 2016-05-03 00:00:00

Accurate prediction of suicide risk in mental health patients remains an open
problem. Existing methods including clinician judgments have acceptable
sensitivity, but yield many false positives. Exploiting administrative data has
a great potential, but the data has high dimensionality and redundancies in the
recording processes. We investigate the efficacy of three most effective
randomized machine learning techniques random forests, gradient boosting
machines, and deep neural nets with dropout in predicting suicide risk. Using a
cohort of mental health patients from a regional Australian hospital, we
compare the predictive performance with popular traditional approaches
clinician judgments based on a checklist, sparse logistic regression and
decision trees. The randomized methods demonstrated robustness against data
redundancies and superior predictive performance on AUC and F-measure.
Decentralized Dynamic Discriminative Dictionary Learning
Authors: Alec Koppel, Garrett Warnell, Ethan Stump, Alejandro Ribeiro
Date: 2016-05-03 00:00:00
Tasks: Dictionary Learning

We consider discriminative dictionary learning in a distributed online
setting, where a network of agents aims to learn a common set of dictionary
elements of a feature space and model parameters while sequentially receiving
observations. We formulate this problem as a distributed stochastic program
with a non-convex objective and present a block variant of the Arrow-Hurwicz
saddle point algorithm to solve it. Using Lagrange multipliers to penalize the
discrepancy between them, only neighboring nodes exchange model information. We
show that decisions made with this saddle point algorithm asymptotically
achieve a first-order stationarity condition on average.