pwc-archive/papers-with-abstracts huggingface dataset:
Minimax Optimal Convergence Rates for Estimating Ground Truth from Crowdsourced Labels
Authors: Chao Gao, Dengyong Zhou
Date: 2013-10-22 00:00:00

Crowdsourcing has become a primary means for label collection in many
real-world machine learning applications. A classical method for inferring the
true labels from the noisy labels provided by crowdsourcing workers is
Dawid-Skene estimator. In this paper, we prove convergence rates of a projected
EM algorithm for the Dawid-Skene estimator. The revealed exponent in the rate
of convergence is shown to be optimal via a lower bound argument. Our work
resolves the long standing issue of whether Dawid-Skene estimator has sound
theoretical guarantees besides its good performance observed in practice. In
addition, a comparative study with majority voting illustrates both advantages
and pitfalls of the Dawid-Skene estimator.
Learning the image processing pipeline
Authors: Haomiao Jiang, Qiyuan Tian, Joyce Farrell, Brian Wandell
Date: 2016-05-30 00:00:00

Many creative ideas are being proposed for image sensor designs, and these
may be useful in applications ranging from consumer photography to computer
vision. To understand and evaluate each new design, we must create a
corresponding image processing pipeline that transforms the sensor data into a
form that is appropriate for the application. The need to design and optimize
these pipelines is time-consuming and costly. We explain a method that combines
machine learning and image systems simulation that automates the pipeline
design. The approach is based on a new way of thinking of the image processing
pipeline as a large collection of local linear filters. We illustrate how the
method has been used to design pipelines for novel sensor architectures in
consumer photography applications.
Learning to Filter with Predictive State Inference Machines
Authors: Wen Sun, Arun Venkatraman, Byron Boots, J. Andrew Bagnell
Date: 2015-12-30 00:00:00
Tasks: State Space Models

Latent state space models are a fundamental and widely used tool for modeling
dynamical systems. However, they are difficult to learn from data and learned
models often lack performance guarantees on inference tasks such as filtering
and prediction. In this work, we present the PREDICTIVE STATE INFERENCE MACHINE
(PSIM), a data-driven method that considers the inference procedure on a
dynamical system as a composition of predictors. The key idea is that rather
than first learning a latent state space model, and then using the learned
model for inference, PSIM directly learns predictors for inference in
predictive state space. We provide theoretical guarantees for inference, in
both realizable and agnostic settings, and showcase practical performance on a
variety of simulated and real world robotics benchmarks.
k2-means for fast and accurate large scale clustering
Authors: Eirikur Agustsson, Radu Timofte, Luc van Gool
Date: 2016-05-30 00:00:00
Tasks: Clustering

We propose k^2-means, a new clustering method which efficiently copes with
large numbers of clusters and achieves low energy solutions. k^2-means builds
upon the standard k-means (Lloyd's algorithm) and combines a new strategy to
accelerate the convergence with a new low time complexity divisive
initialization. The accelerated convergence is achieved through only looking at
k_n nearest clusters and using triangle inequality bounds in the assignment
step while the divisive initialization employs an optimal 2-clustering along a
direction. The worst-case time complexity per iteration of our k^2-means is
O(nk_nd+k^2d), where d is the dimension of the n data points and k is the
number of clusters and usually n << k << k_n. Compared to k-means' O(nkd)
complexity, our k^2-means complexity is significantly lower, at the expense of
slightly increasing the memory complexity by O(nk_n+k^2). In our extensive
experiments k^2-means is order(s) of magnitude faster than standard methods in
computing accurate clusterings on several standard datasets and settings with
hundreds of clusters and high dimensional data. Moreover, the proposed divisive
initialization generally leads to clustering energies comparable to those
achieved with the standard k-means++ initialization, while being significantly
faster.
Internal Guidance for Satallax
Authors: Michael Färber, Chad Brown
Date: 2016-05-30 00:00:00
Tasks: General Classification

We propose a new internal guidance method for automated theorem provers based
on the given-clause algorithm. Our method influences the choice of unprocessed
clauses using positive and negative examples from previous proofs. To this end,
we present an efficient scheme for Naive Bayesian classification by
generalising label occurrences to types with monoid structure. This makes it
possible to extend existing fast classifiers, which consider only positive
examples, with negative ones. We implement the method in the higher-order logic
prover Satallax, where we modify the delay with which propositions are
processed. We evaluated our method on a simply-typed higher-order logic version
of the Flyspeck project, where it solves 26% more problems than Satallax
without internal guidance.
Robust Gaussian Filtering using a Pseudo Measurement
Authors: Manuel Wüthrich, Cristina Garcia Cifuentes, Sebastian Trimpe, Franziska Meier, Jeannette Bohg, Jan Issac, Stefan Schaal
Date: 2015-09-14 00:00:00

Many sensors, such as range, sonar, radar, GPS and visual devices, produce
measurements which are contaminated by outliers. This problem can be addressed
by using fat-tailed sensor models, which account for the possibility of
outliers. Unfortunately, all estimation algorithms belonging to the family of
Gaussian filters (such as the widely-used extended Kalman filter and unscented
Kalman filter) are inherently incompatible with such fat-tailed sensor models.
The contribution of this paper is to show that any Gaussian filter can be made
compatible with fat-tailed sensor models by applying one simple change: Instead
of filtering with the physical measurement, we propose to filter with a pseudo
measurement obtained by applying a feature function to the physical
measurement. We derive such a feature function which is optimal under some
conditions. Simulation results show that the proposed method can effectively
handle measurement outliers and allows for robust filtering in both linear and
nonlinear systems.
Transforming Wikipedia into an Ontology-based Information Retrieval Search Engine for Local Experts using a Third-Party Taxonomy
Authors: Gregory Grefenstette, Karima Rafes
Date: 2015-11-04 00:00:00
Tasks: Information Retrieval, Retrieval

Wikipedia is widely used for finding general information about a wide variety
of topics. Its vocation is not to provide local information. For example, it
provides plot, cast, and production information about a given movie, but not
showing times in your local movie theatre. Here we describe how we can connect
local information to Wikipedia, without altering its content. The case study we
present involves finding local scientific experts. Using a third-party
taxonomy, independent from Wikipedia's category hierarchy, we index information
connected to our local experts, present in their activity reports, and we
re-index Wikipedia content using the same taxonomy. The connections between
Wikipedia pages and local expert reports are stored in a relational database,
accessible through as public SPARQL endpoint. A Wikipedia gadget (or plugin)
activated by the interested user, accesses the endpoint as each Wikipedia page
is accessed. An additional tab on the Wikipedia page allows the user to open up
a list of teams of local experts associated with the subject matter in the
Wikipedia page. The technique, though presented here as a way to identify local
experts, is generic, in that any third party taxonomy, can be used in this to
connect Wikipedia to any non-Wikipedia data source.
Learning Combinatorial Functions from Pairwise Comparisons
Authors: Maria-Florina Balcan, Ellen Vitercik, Colin White
Date: 2016-05-30 00:00:00
Tasks: BIG-bench Machine Learning

A large body of work in machine learning has focused on the problem of
learning a close approximation to an underlying combinatorial function, given a
small set of labeled examples. However, for real-valued functions, cardinal
labels might not be accessible, or it may be difficult for an expert to
consistently assign real-valued labels over the entire set of examples. For
instance, it is notoriously hard for consumers to reliably assign values to
bundles of merchandise. Instead, it might be much easier for a consumer to
report which of two bundles she likes better. With this motivation in mind, we
consider an alternative learning model, wherein the algorithm must learn the
underlying function up to pairwise comparisons, from pairwise comparisons. In
this model, we present a series of novel algorithms that learn over a wide
variety of combinatorial function classes. These range from graph functions to
broad classes of valuation functions that are fundamentally important in
microeconomic theory, the analysis of social networks, and machine learning,
such as coverage, submodular, XOS, and subadditive functions, as well as
functions with sparse Fourier support.
Deep Reinforcement Learning Radio Control and Signal Detection with KeRLym, a Gym RL Agent
Authors: Timothy J. O'Shea, T. Charles Clancy
Date: 2016-05-30 00:00:00
Tasks: Deep Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

This paper presents research in progress investigating the viability and
adaptation of reinforcement learning using deep neural network based function
approximation for the task of radio control and signal detection in the
wireless domain. We demonstrate a successful initial method for radio control
which allows naive learning of search without the need for expert features,
heuristics, or search strategies. We also introduce Kerlym, an open Keras based
reinforcement learning agent collection for OpenAI's Gym.
Going Deeper for Multilingual Visual Sentiment Detection
Authors: Brendan Jou, Shih-Fu Chang
Date: 2016-05-30 00:00:00
Tasks: TAG

This technical report details several improvements to the visual concept
detector banks built on images from the Multilingual Visual Sentiment Ontology
(MVSO). The detector banks are trained to detect a total of 9,918
sentiment-biased visual concepts from six major languages: English, Spanish,
Italian, French, German and Chinese. In the original MVSO release,
adjective-noun pair (ANP) detectors were trained for the six languages using an
AlexNet-styled architecture by fine-tuning from DeepSentiBank. Here, through a
more extensive set of experiments, parameter tuning, and training runs, we
detail and release higher accuracy models for detecting ANPs across six
languages from the same image pool and setting as in the original release using
a more modern architecture, GoogLeNet, providing comparable or better
performance with reduced network parameter cost.
  In addition, since the image pool in MVSO can be corrupted by user noise from
social interactions, we partitioned out a sub-corpus of MVSO images based on
tag-restricted queries for higher fidelity labels. We show that as a result of
these higher fidelity labels, higher performing AlexNet-styled ANP detectors
can be trained using the tag-restricted image subset as compared to the models
in full corpus. We release all these newly trained models for public research
use along with the list of tag-restricted images from the MVSO dataset.
Generalized Support and Formal Development of Constraint Propagators
Authors: James Caldwell, Ian P. Gent, Peter Nightingale
Date: 2015-04-22 00:00:00
Tasks: ARC

Constraint programming is a family of techniques for solving combinatorial
problems, where the problem is modelled as a set of decision variables
(typically with finite domains) and a set of constraints that express relations
among the decision variables. One key concept in constraint programming is
propagation: reasoning on a constraint or set of constraints to derive new
facts, typically to remove values from the domains of decision variables.
Specialised propagation algorithms (propagators) exist for many classes of
constraints.
  The concept of support is pervasive in the design of propagators.
Traditionally, when a domain value ceases to have support, it may be removed
because it takes part in no solutions. Arc-consistency algorithms such as
AC2001 make use of support in the form of a single domain value. GAC algorithms
such as GAC-Schema use a tuple of values to support each literal. We generalize
these notions of support in two ways. First, we allow a set of tuples to act as
support. Second, the supported object is generalized from a set of literals
(GAC-Schema) to an entire constraint or any part of it.
  We design a methodology for developing correct propagators using generalized
support. A constraint is expressed as a family of support properties, which may
be proven correct against the formal semantics of the constraint. Using
Curry-Howard isomorphism to interpret constructive proofs as programs, we show
how to derive correct propagators from the constructive proofs of the support
properties. The framework is carefully designed to allow efficient algorithms
to be produced. Derived algorithms may make use of dynamic literal triggers or
watched literals for efficiency. Finally, two case studies of deriving
efficient algorithms are given.
Hyperspectral Image Classification with Support Vector Machines on Kernel Distribution Embeddings
Authors: Gianni Franchi, Jesus Angulo, Dino Sejdinovic
Date: 2016-05-30 00:00:00
Tasks: Classification, General Classification, Hyperspectral Image Classification, image-classification, Image Classification

We propose a novel approach for pixel classification in hyperspectral images,
leveraging on both the spatial and spectral information in the data. The
introduced method relies on a recently proposed framework for learning on
distributions -- by representing them with mean elements in reproducing kernel
Hilbert spaces (RKHS) and formulating a classification algorithm therein. In
particular, we associate each pixel to an empirical distribution of its
neighbouring pixels, a judicious representation of which in an RKHS, in
conjunction with the spectral information contained in the pixel itself, give a
new explicit set of features that can be fed into a suite of standard
classification techniques -- we opt for a well-established framework of support
vector machines (SVM). Furthermore, the computational complexity is reduced via
random Fourier features formalism. We study the consistency and the convergence
rates of the proposed method and the experiments demonstrate strong performance
on hyperspectral data with gains in comparison to the state-of-the-art results.
Classification under Streaming Emerging New Classes: A Solution using Completely Random Trees
Authors: Xin Mu, Kai Ming Ting, Zhi-Hua Zhou
Date: 2016-05-30 00:00:00
Tasks: Classification, General Classification

This paper investigates an important problem in stream mining, i.e.,
classification under streaming emerging new classes or SENC. The common
approach is to treat it as a classification problem and solve it using either a
supervised learner or a semi-supervised learner. We propose an alternative
approach by using unsupervised learning as the basis to solve this problem. The
SENC problem can be decomposed into three sub problems: detecting emerging new
classes, classifying for known classes, and updating models to enable
classification of instances of the new class and detection of more emerging new
classes. The proposed method employs completely random trees which have been
shown to work well in unsupervised learning and supervised learning
independently in the literature. This is the first time, as far as we know,
that completely random trees are used as a single common core to solve all
three sub problems: unsupervised learning, supervised learning and model update
in data streams. We show that the proposed unsupervised-learning-focused method
often achieves significantly better outcomes than existing
classification-focused methods.
Control of Memory, Active Perception, and Action in Minecraft
Authors: Junhyuk Oh, Valliappa Chockalingam, Satinder Singh, Honglak Lee
Date: 2016-05-30 00:00:00
Tasks: Deep Reinforcement Learning, Minecraft, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

In this paper, we introduce a new set of reinforcement learning (RL) tasks in
Minecraft (a flexible 3D world). We then use these tasks to systematically
compare and contrast existing deep reinforcement learning (DRL) architectures
with our new memory-based DRL architectures. These tasks are designed to
emphasize, in a controllable manner, issues that pose challenges for RL methods
including partial observability (due to first-person visual observations),
delayed rewards, high-dimensional visual observations, and the need to use
active perception in a correct manner so as to perform well in the tasks. While
these tasks are conceptually simple to describe, by virtue of having all of
these challenges simultaneously they are difficult for current DRL
architectures. Additionally, we evaluate the generalization performance of the
architectures on environments not used during training. The experimental
results show that our new architectures generalize to unseen environments
better than existing DRL architectures.
The Multiscale Laplacian Graph Kernel
Authors: Risi Kondor, Horace Pan
Date: 2016-03-20 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Graph Classification

Many real world graphs, such as the graphs of molecules, exhibit structure at
multiple different scales, but most existing kernels between graphs are either
purely local or purely global in character. In contrast, by building a
hierarchy of nested subgraphs, the Multiscale Laplacian Graph kernels (MLG
kernels) that we define in this paper can account for structure at a range of
different scales. At the heart of the MLG construction is another new graph
kernel, called the Feature Space Laplacian Graph kernel (FLG kernel), which has
the property that it can lift a base kernel defined on the vertices of two
graphs to a kernel between the graphs. The MLG kernel applies such FLG kernels
to subgraphs recursively. To make the MLG kernel computationally feasible, we
also introduce a randomized projection procedure, similar to the Nystr\"om
method, but for RKHS operators.
Image segmentation based on the hybrid total variation model and the K-means clustering strategy
Authors: Baoli Shi, Zhi-Feng Pang, Jing Xu
Date: 2016-05-30 00:00:00
Tasks: Clustering, Image Segmentation, Segmentation, Semantic Segmentation

The performance of image segmentation highly relies on the original inputting
image. When the image is contaminated by some noises or blurs, we can not
obtain the efficient segmentation result by using direct segmentation methods.
In order to efficiently segment the contaminated image, this paper proposes a
two step method based on the hybrid total variation model with a box constraint
and the K-means clustering method. In the first step, the hybrid model is based
on the weighted convex combination between the total variation functional and
the high-order total variation as the regularization term to obtain the
original clustering data. In order to deal with non-smooth regularization term,
we solve this model by employing the alternating split Bregman method. Then, in
the second step, the segmentation can be obtained by thresholding this
clustering data into different phases, where the thresholds can be given by
using the K-means clustering method. Numerical comparisons show that our
proposed model can provide more efficient segmentation results dealing with the
noise image and blurring image.
ParMAC: distributed optimisation of nested functions, with application to learning binary autoencoders
Authors: Miguel Á. Carreira-Perpiñán, Mehdi Alizadeh
Date: 2016-05-30 00:00:00
Tasks: Image Retrieval, Retrieval

Many powerful machine learning models are based on the composition of
multiple processing layers, such as deep nets, which gives rise to nonconvex
objective functions. A general, recent approach to optimise such "nested"
functions is the method of auxiliary coordinates (MAC). MAC introduces an
auxiliary coordinate for each data point in order to decouple the nested model
into independent submodels. This decomposes the optimisation into steps that
alternate between training single layers and updating the coordinates. It has
the advantage that it reuses existing single-layer algorithms, introduces
parallelism, and does not need to use chain-rule gradients, so it works with
nondifferentiable layers. With large-scale problems, or when distributing the
computation is necessary for faster training, the dataset may not fit in a
single machine. It is then essential to limit the amount of communication
between machines so it does not obliterate the benefit of parallelism. We
describe a general way to achieve this, ParMAC. ParMAC works on a cluster of
processing machines with a circular topology and alternates two steps until
convergence: one step trains the submodels in parallel using stochastic
updates, and the other trains the coordinates in parallel. Only submodel
parameters, no data or coordinates, are ever communicated between machines.
ParMAC exhibits high parallelism, low communication overhead, and facilitates
data shuffling, load balancing, fault tolerance and streaming data processing.
We study the convergence of ParMAC and propose a theoretical model of its
runtime and parallel speedup. We develop ParMAC to learn binary autoencoders
for fast, approximate image retrieval. We implement it in MPI in a distributed
system and demonstrate nearly perfect speedups in a 128-processor cluster with
a training set of 100 million high-dimensional points.
No bad local minima: Data independent training error guarantees for multilayer neural networks
Authors: Daniel Soudry, Yair Carmon
Date: 2016-05-26 00:00:00

We use smoothed analysis techniques to provide guarantees on the training
loss of Multilayer Neural Networks (MNNs) at differentiable local minima.
Specifically, we examine MNNs with piecewise linear activation functions,
quadratic loss and a single output, under mild over-parametrization. We prove
that for a MNN with one hidden layer, the training error is zero at every
differentiable local minimum, for almost every dataset and dropout-like noise
realization. We then extend these results to the case of more than one hidden
layer. Our theoretical guarantees assume essentially nothing on the training
data, and are verified numerically. These results suggest why the highly
non-convex loss of such MNNs can be easily optimized using local updates (e.g.,
stochastic gradient descent), as observed empirically.
Learning Natural Language Inference using Bidirectional LSTM model and Inner-Attention
Authors: Yang Liu, Chengjie Sun, Lei Lin, Xiaolong Wang
Date: 2016-05-30 00:00:00
Tasks: Natural Language Inference, Sentence

In this paper, we proposed a sentence encoding-based model for recognizing
text entailment. In our approach, the encoding of sentence is a two-stage
process. Firstly, average pooling was used over word-level bidirectional LSTM
(biLSTM) to generate a first-stage sentence representation. Secondly, attention
mechanism was employed to replace average pooling on the same sentence for
better representations. Instead of using target sentence to attend words in
source sentence, we utilized the sentence's first-stage representation to
attend words appeared in itself, which is called "Inner-Attention" in our paper
. Experiments conducted on Stanford Natural Language Inference (SNLI) Corpus
has proved the effectiveness of "Inner-Attention" mechanism. With less number
of parameters, our model outperformed the existing best sentence encoding-based
approach by a large margin.