pwc-archive/papers-with-abstracts huggingface dataset:
WxBS: Wide Baseline Stereo Generalizations
Authors: Dmytro Mishkin, Jiri Matas, Michal Perdoch, Karel Lenc
Date: 2015-04-24 00:00:00

We have presented a new problem -- the wide multiple baseline stereo (WxBS)
-- which considers matching of images that simultaneously differ in more than
one image acquisition factor such as viewpoint, illumination, sensor type or
where object appearance changes significantly, e.g. over time. A new dataset
with the ground truth for evaluation of matching algorithms has been introduced
and will be made public.
  We have extensively tested a large set of popular and recent detectors and
descriptors and show than the combination of RootSIFT and HalfRootSIFT as
descriptors with MSER and Hessian-Affine detectors works best for many
different nuisance factors. We show that simple adaptive thresholding improves
Hessian-Affine, DoG, MSER (and possibly other) detectors and allows to use them
on infrared and low contrast images.
  A novel matching algorithm for addressing the WxBS problem has been
introduced. We have shown experimentally that the WxBS-M matcher dominantes the
state-of-the-art methods both on both the new and existing datasets.
Spectral Clustering via the Power Method -- Provably
Authors: Christos Boutsidis, Alex Gittens, Prabhanjan Kambadur
Date: 2013-11-12 00:00:00
Tasks: Clustering

Spectral clustering is one of the most important algorithms in data mining
and machine intelligence; however, its computational complexity limits its
application to truly large scale data analysis. The computational bottleneck in
spectral clustering is computing a few of the top eigenvectors of the
(normalized) Laplacian matrix corresponding to the graph representing the data
to be clustered. One way to speed up the computation of these eigenvectors is
to use the "power method" from the numerical linear algebra literature.
Although the power method has been empirically used to speed up spectral
clustering, the theory behind this approach, to the best of our knowledge,
remains unexplored. This paper provides the \emph{first} such rigorous
theoretical justification, arguing that a small number of power iterations
suffices to obtain near-optimal partitionings using the approximate
eigenvectors. Specifically, we prove that solving the $k$-means clustering
problem on the approximate eigenvectors obtained via the power method gives an
additive-error approximation to solving the $k$-means problem on the optimal
eigenvectors.
Automatic Script Identification in the Wild
Authors: Baoguang Shi, Cong Yao, Chengquan Zhang, Xiaowei Guo, Feiyue Huang, Xiang Bai
Date: 2015-05-12 00:00:00
Tasks: General Classification, image-classification, Image Classification

With the rapid increase of transnational communication and cooperation,
people frequently encounter multilingual scenarios in various situations. In
this paper, we are concerned with a relatively new problem: script
identification at word or line levels in natural scenes. A large-scale dataset
with a great quantity of natural images and 10 types of widely used languages
is constructed and released. In allusion to the challenges in script
identification in real-world scenarios, a deep learning based algorithm is
proposed. The experiments on the proposed dataset demonstrate that our
algorithm achieves superior performance, compared with conventional image
classification methods, such as the original CNN architecture and LLC.
Comparing methods for Twitter Sentiment Analysis
Authors: Evangelos Psomakelis, Konstantinos Tserpes, Dimosthenis Anagnostopoulos, Theodora Varvarigou
Date: 2015-05-12 00:00:00
Tasks: Sentiment Analysis, Twitter Sentiment Analysis

This work extends the set of works which deal with the popular problem of
sentiment analysis in Twitter. It investigates the most popular document
("tweet") representation methods which feed sentiment evaluation mechanisms. In
particular, we study the bag-of-words, n-grams and n-gram graphs approaches and
for each of them we evaluate the performance of a lexicon-based and 7
learning-based classification algorithms (namely SVM, Na\"ive Bayesian
Networks, Logistic Regression, Multilayer Perceptrons, Best-First Trees,
Functional Trees and C4.5) as well as their combinations, using a set of 4451
manually annotated tweets. The results demonstrate the superiority of
learning-based methods and in particular of n-gram graphs approaches for
predicting the sentiment of tweets. They also show that the combinatory
approach has impressive effects on n-grams, raising the confidence up to 83.15%
on the 5-Grams, using majority vote and a balanced dataset (equal number of
positive, negative and neutral tweets for training). In the n-gram graph cases
the improvement was small to none, reaching 94.52% on the 4-gram graphs, using
Orthodromic distance and a threshold of 0.001.
Contour Detection Using Cost-Sensitive Convolutional Neural Networks
Authors: Jyh-Jing Hwang, Tyng-Luh Liu
Date: 2014-12-22 00:00:00
Tasks: Contour Detection

We address the problem of contour detection via per-pixel classifications of
edge point. To facilitate the process, the proposed approach leverages with
DenseNet, an efficient implementation of multiscale convolutional neural
networks (CNNs), to extract an informative feature vector for each pixel and
uses an SVM classifier to accomplish contour detection. The main challenge lies
in adapting a pre-trained per-image CNN model for yielding per-pixel image
features. We propose to base on the DenseNet architecture to achieve pixelwise
fine-tuning and then consider a cost-sensitive strategy to further improve the
learning with a small dataset of edge and non-edge image patches. In the
experiment of contour detection, we look into the effectiveness of combining
per-pixel features from different CNN layers and obtain comparable performances
to the state-of-the-art on BSDS500.
Fractional Max-Pooling
Authors: Benjamin Graham
Date: 2014-12-18 00:00:00
Tasks: Image Classification

Convolutional networks almost always incorporate some form of spatial
pooling, and very often it is alpha times alpha max-pooling with alpha=2.
Max-pooling act on the hidden layers of the network, reducing their size by an
integer multiplicative factor alpha. The amazing by-product of discarding 75%
of your data is that you build into the network a degree of invariance with
respect to translations and elastic distortions. However, if you simply
alternate convolutional layers with max-pooling layers, performance is limited
due to the rapid reduction in spatial size, and the disjoint nature of the
pooling regions. We have formulated a fractional version of max-pooling where
alpha is allowed to take non-integer values. Our version of max-pooling is
stochastic as there are lots of different ways of constructing suitable pooling
regions. We find that our form of fractional max-pooling reduces overfitting on
a variety of datasets: for instance, we improve on the state-of-the art for
CIFAR-100 without even using dropout.
Incorporating Type II Error Probabilities from Independence Tests into Score-Based Learning of Bayesian Network Structure
Authors: Eliot Brenner, David Sontag
Date: 2015-05-12 00:00:00

We give a new consistent scoring function for structure learning of Bayesian
networks. In contrast to traditional approaches to score-based structure
learning, such as BDeu or MDL, the complexity penalty that we propose is
data-dependent and is given by the probability that a conditional independence
test correctly shows that an edge cannot exist. What really distinguishes this
new scoring function from earlier work is that it has the property of becoming
computationally easier to maximize as the amount of data increases. We prove a
polynomial sample complexity result, showing that maximizing this score is
guaranteed to correctly learn a structure with no false edges and a
distribution close to the generating distribution, whenever there exists a
Bayesian network which is a perfect map for the data generating distribution.
Although the new score can be used with any search algorithm, in our related
UAI 2013 paper [BS13], we have given empirical results showing that it is
particularly effective when used together with a linear programming relaxation
approach to Bayesian network structure learning. The present paper contains all
details of the proofs of the finite-sample complexity results in [BS13] as well
as detailed explanation of the computation of the certain error probabilities
called beta-values, whose precomputation and tabulation is necessary for the
implementation of the algorithm in [BS13].
The Boundary Forest Algorithm for Online Supervised and Unsupervised Learning
Authors: Charles Mathy, Nate Derbinsky, José Bento, Jonathan Rosenthal, Jonathan Yedidia
Date: 2015-05-12 00:00:00

We describe a new instance-based learning algorithm called the Boundary
Forest (BF) algorithm, that can be used for supervised and unsupervised
learning. The algorithm builds a forest of trees whose nodes store previously
seen examples. It can be shown data points one at a time and updates itself
incrementally, hence it is naturally online. Few instance-based algorithms have
this property while being simultaneously fast, which the BF is. This is crucial
for applications where one needs to respond to input data in real time. The
number of children of each node is not set beforehand but obtained from the
training procedure, which makes the algorithm very flexible with regards to
what data manifolds it can learn. We test its generalization performance and
speed on a range of benchmark datasets and detail in which settings it
outperforms the state of the art. Empirically we find that training time scales
as O(DNlog(N)) and testing as O(Dlog(N)), where D is the dimensionality and N
the amount of data,
An iterative step-function estimator for graphons
Authors: Diana Cai, Nathanael Ackerman, Cameron Freer
Date: 2014-12-05 00:00:00
Tasks: Clustering, Graphon Estimation

Exchangeable graphs arise via a sampling procedure from measurable functions
known as graphons. A natural estimation problem is how well we can recover a
graphon given a single graph sampled from it. One general framework for
estimating a graphon uses step-functions obtained by partitioning the nodes of
the graph according to some clustering algorithm. We propose an iterative
step-function estimator (ISFE) that, given an initial partition, iteratively
clusters nodes based on their edge densities with respect to the previous
iteration's partition. We analyze ISFE and demonstrate its performance in
comparison with other graphon estimation techniques.
Adapting Improved Upper Confidence Bounds for Monte-Carlo Tree Search
Authors: Yun-Ching Liu, Yoshimasa Tsuruoka
Date: 2015-05-11 00:00:00

The UCT algorithm, which combines the UCB algorithm and Monte-Carlo Tree
Search (MCTS), is currently the most widely used variant of MCTS. Recently, a
number of investigations into applying other bandit algorithms to MCTS have
produced interesting results. In this research, we will investigate the
possibility of combining the improved UCB algorithm, proposed by Auer et al.
(2010), with MCTS. However, various characteristics and properties of the
improved UCB algorithm may not be ideal for a direct application to MCTS.
Therefore, some modifications were made to the improved UCB algorithm, making
it more suitable for the task of game tree search. The Mi-UCT algorithm is the
application of the modified UCB algorithm applied to trees. The performance of
Mi-UCT is demonstrated on the games of $9\times 9$ Go and $9\times 9$ NoGo, and
has shown to outperform the plain UCT algorithm when only a small number of
playouts are given, and rougly on the same level when more playouts are
available.
On Markov chain Monte Carlo methods for tall data
Authors: Rémi Bardenet, Arnaud Doucet, Chris Holmes
Date: 2015-05-11 00:00:00
Tasks: Bayesian Inference

Markov chain Monte Carlo methods are often deemed too computationally
intensive to be of any practical use for big data applications, and in
particular for inference on datasets containing a large number $n$ of
individual data points, also known as tall datasets. In scenarios where data
are assumed independent, various approaches to scale up the Metropolis-Hastings
algorithm in a Bayesian inference context have been recently proposed in
machine learning and computational statistics. These approaches can be grouped
into two categories: divide-and-conquer approaches and, subsampling-based
algorithms. The aims of this article are as follows. First, we present a
comprehensive review of the existing literature, commenting on the underlying
assumptions and theoretical guarantees of each method. Second, by leveraging
our understanding of these limitations, we propose an original
subsampling-based approach which samples from a distribution provably close to
the posterior distribution of interest, yet can require less than $O(n)$ data
point likelihood evaluations at each iteration for certain statistical models
in favourable scenarios. Finally, we have only been able so far to propose
subsampling-based methods which display good performance in scenarios where the
Bernstein-von Mises approximation of the target posterior distribution is
excellent. It remains an open challenge to develop such methods in scenarios
where the Bernstein-von Mises approximation is poor.
Sample complexity of learning Mahalanobis distance metrics
Authors: Nakul Verma, Kristin Branson
Date: 2015-05-11 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Metric Learning

Metric learning seeks a transformation of the feature space that enhances
prediction quality for the given task at hand. In this work we provide
PAC-style sample complexity rates for supervised metric learning. We give
matching lower- and upper-bounds showing that the sample complexity scales with
the representation dimension when no assumptions are made about the underlying
data distribution. However, by leveraging the structure of the data
distribution, we show that one can achieve rates that are fine-tuned to a
specific notion of intrinsic complexity for a given dataset. Our analysis
reveals that augmenting the metric learning optimization criterion with a
simple norm-based regularization can help adapt to a dataset's intrinsic
complexity, yielding better generalization. Experiments on benchmark datasets
validate our analysis and show that regularizing the metric can help discern
the signal even when the data contains high amounts of noise.
Improving neural networks with bunches of neurons modeled by Kumaraswamy units: Preliminary study
Authors: Jakub Mikolaj Tomczak
Date: 2015-05-11 00:00:00
Tasks: Object Recognition, speech-recognition, Speech Recognition

Deep neural networks have recently achieved state-of-the-art results in many
machine learning problems, e.g., speech recognition or object recognition.
Hitherto, work on rectified linear units (ReLU) provides empirical and
theoretical evidence on performance increase of neural networks comparing to
typically used sigmoid activation function. In this paper, we investigate a new
manner of improving neural networks by introducing a bunch of copies of the
same neuron modeled by the generalized Kumaraswamy distribution. As a result,
we propose novel non-linear activation function which we refer to as
Kumaraswamy unit which is closely related to ReLU. In the experimental study
with MNIST image corpora we evaluate the Kumaraswamy unit applied to
single-layer (shallow) neural network and report a significant drop in test
classification error and test cross-entropy in comparison to sigmoid unit, ReLU
and Noisy ReLU.
Relations between MDDs and Tuples and Dynamic Modifications of MDDs based constraints
Authors: Guillaume Perez, Jean-Charles Régin
Date: 2015-05-11 00:00:00

We study the relations between Multi-valued Decision Diagrams (MDD) and
tuples (i.e. elements of the Cartesian Product of variables). First, we improve
the existing methods for transforming a set of tuples, Global Cut Seeds,
sequences of tuples into MDDs. Then, we present some in-place algorithms for
adding and deleting tuples from an MDD. Next, we consider an MDD constraint
which is modified during the search by deleting some tuples. We give an
algorithm which adapts MDD-4R to these dynamic and persistent modifications.
Some experiments show that MDD constraints are competitive with Table
constraints.
A Two-Layer Local Constrained Sparse Coding Method for Fine-Grained Visual Categorization
Authors: Guo Lihua, Guo Chenggan
Date: 2015-05-11 00:00:00
Tasks: Diversity, Fine-Grained Visual Categorization

Fine-grained categories are more difficulty distinguished than generic
categories due to the similarity of inter-class and the diversity of
intra-class. Therefore, the fine-grained visual categorization (FGVC) is
considered as one of challenge problems in computer vision recently. A new
feature learning framework, which is based on a two-layer local constrained
sparse coding architecture, is proposed in this paper. The two-layer
architecture is introduced for learning intermediate-level features, and the
local constrained term is applied to guarantee the local smooth of coding
coefficients. For extracting more discriminative information, local orientation
histograms are the input of sparse coding instead of raw pixels. Moreover, a
quick dictionary updating process is derived to further improve the training
speed. Two experimental results show that our method achieves 85.29% accuracy
on the Oxford 102 flowers dataset and 67.8% accuracy on the CUB-200-2011 bird
dataset, and the performance of our framework is highly competitive with
existing literatures.
Training Deeper Convolutional Networks with Deep Supervision
Authors: Liwei Wang, Chen-Yu Lee, Zhuowen Tu, Svetlana Lazebnik
Date: 2015-05-11 00:00:00
Tasks: General Classification

One of the most promising ways of improving the performance of deep
convolutional neural networks is by increasing the number of convolutional
layers. However, adding layers makes training more difficult and
computationally expensive. In order to train deeper networks, we propose to add
auxiliary supervision branches after certain intermediate layers during
training. We formulate a simple rule of thumb to determine where these branches
should be added. The resulting deeply supervised structure makes the training
much easier and also produces better classification results on ImageNet and the
recently released, larger MIT Places dataset
A Constraint Programming Approach for Non-Preemptive Evacuation Scheduling
Authors: Caroline Even, Andreas Schutt, Pascal Van Hentenryck
Date: 2015-05-11 00:00:00
Tasks: Scheduling

Large-scale controlled evacuations require emergency services to select
evacuation routes, decide departure times, and mobilize resources to issue
orders, all under strict time constraints. Existing algorithms almost always
allow for preemptive evacuation schedules, which are less desirable in
practice. This paper proposes, for the first time, a constraint-based
scheduling model that optimizes the evacuation flow rate (number of vehicles
sent at regular time intervals) and evacuation phasing of widely populated
areas, while ensuring a nonpreemptive evacuation for each residential zone. Two
optimization objectives are considered: (1) to maximize the number of evacuees
reaching safety and (2) to minimize the overall duration of the evacuation.
Preliminary results on a set of real-world instances show that the approach can
produce, within a few seconds, a non-preemptive evacuation schedule which is
either optimal or at most 6% away of the optimal preemptive solution.
Constructing Long Short-Term Memory based Deep Recurrent Neural Networks for Large Vocabulary Speech Recognition
Authors: Xiangang Li, Xihong Wu
Date: 2014-10-16 00:00:00
Tasks: GPU, speech-recognition, Speech Recognition

Long short-term memory (LSTM) based acoustic modeling methods have recently
been shown to give state-of-the-art performance on some speech recognition
tasks. To achieve a further performance improvement, in this research, deep
extensions on LSTM are investigated considering that deep hierarchical model
has turned out to be more efficient than a shallow one. Motivated by previous
research on constructing deep recurrent neural networks (RNNs), alternative
deep LSTM architectures are proposed and empirically evaluated on a large
vocabulary conversational telephone speech recognition task. Meanwhile,
regarding to multi-GPU devices, the training process for LSTM networks is
introduced and discussed. Experimental results demonstrate that the deep LSTM
networks benefit from the depth and yield the state-of-the-art performance on
this task.
Automating change of representation for proofs in discrete mathematics
Authors: Daniel Raggi, Alan Bundy, Gudmund Grov, Alison Pease
Date: 2015-05-10 00:00:00

Representation determines how we can reason about a specific problem.
Sometimes one representation helps us find a proof more easily than others.
Most current automated reasoning tools focus on reasoning within one
representation. There is, therefore, a need for the development of better tools
to mechanise and automate formal and logically sound changes of representation.
  In this paper we look at examples of representational transformations in
discrete mathematics, and show how we have used Isabelle's Transfer tool to
automate the use of these transformations in proofs. We give a brief overview
of a general theory of transformations that we consider appropriate for
thinking about the matter, and we explain how it relates to the Transfer
package. We show our progress towards developing a general tactic that
incorporates the automatic search for representation within the proving
process.
Contrastive Pessimistic Likelihood Estimation for Semi-Supervised Classification
Authors: Marco Loog
Date: 2015-03-01 00:00:00
Tasks: Classification, General Classification, parameter estimation

Improvement guarantees for semi-supervised classifiers can currently only be
given under restrictive conditions on the data. We propose a general way to
perform semi-supervised parameter estimation for likelihood-based classifiers
for which, on the full training set, the estimates are never worse than the
supervised solution in terms of the log-likelihood. We argue, moreover, that we
may expect these solutions to really improve upon the supervised classifier in
particular cases. In a worked-out example for LDA, we take it one step further
and essentially prove that its semi-supervised version is strictly better than
its supervised counterpart. The two new concepts that form the core of our
estimation principle are contrast and pessimism. The former refers to the fact
that our objective function takes the supervised estimates into account,
enabling the semi-supervised solution to explicitly control the potential
improvements over this estimate. The latter refers to the fact that our
estimates are conservative and therefore resilient to whatever form the true
labeling of the unlabeled data takes on. Experiments demonstrate the
improvements in terms of both the log-likelihood and the classification error
rate on independent test sets.