pwc-archive/papers-with-abstracts huggingface dataset:
The Robustness of Estimator Composition
Authors: Pingfan Tang, Jeff M. Phillips
Date: 2016-09-05 00:00:00
Proceeding: NeurIPS 2016 12

We formalize notions of robustness for composite estimators via the notion of
a breakdown point. A composite estimator successively applies two (or more)
estimators: on data decomposed into disjoint parts, it applies the first
estimator on each part, then the second estimator on the outputs of the first
estimator. And so on, if the composition is of more than two estimators.
Informally, the breakdown point is the minimum fraction of data points which if
significantly modified will also significantly modify the output of the
estimator, so it is typically desirable to have a large breakdown point. Our
main result shows that, under mild conditions on the individual estimators, the
breakdown point of the composite estimator is the product of the breakdown
points of the individual estimators. We also demonstrate several scenarios,
ranging from regression to statistical testing, where this analysis is easy to
apply, useful in understanding worst case robustness, and sheds powerful
insights onto the associated data analysis.
Structure from Motion on a Sphere
Authors: Jonathan Ventura
Date: 2016-04-01 00:00:00

We describe a special case of structure from motion where the camera rotates
on a sphere. The camera's optical axis lies perpendicular to the sphere's
surface. In this case, the camera's pose is minimally represented by three
rotation parameters. From analysis of the epipolar geometry we derive a novel
and efficient solution for the essential matrix relating two images, requiring
only three point correspondences in the minimal case. We apply this solver in a
structure-from-motion pipeline that aggregates pairwise relations by rotation
averaging followed by bundle adjustment with an inverse depth parameterization.
Our methods enable scene modeling with an outward-facing camera and object
scanning with an inward-facing camera.
The Semantic Knowledge Graph: A compact, auto-generated model for real-time traversal and ranking of any relationship within a domain
Authors: Trey Grainger, Khalifeh Aljadda, Mohammed Korayem, Andries Smith
Date: 2016-09-02 00:00:00
Tasks: Anomaly Detection

This paper describes a new kind of knowledge representation and mining system
which we are calling the Semantic Knowledge Graph. At its heart, the Semantic
Knowledge Graph leverages an inverted index, along with a complementary
uninverted index, to represent nodes (terms) and edges (the documents within
intersecting postings lists for multiple terms/nodes). This provides a layer of
indirection between each pair of nodes and their corresponding edge, enabling
edges to materialize dynamically from underlying corpus statistics. As a
result, any combination of nodes can have edges to any other nodes materialize
and be scored to reveal latent relationships between the nodes. This provides
numerous benefits: the knowledge graph can be built automatically from a
real-world corpus of data, new nodes - along with their combined edges - can be
instantly materialized from any arbitrary combination of preexisting nodes
(using set operations), and a full model of the semantic relationships between
all entities within a domain can be represented and dynamically traversed using
a highly compact representation of the graph. Such a system has widespread
applications in areas as diverse as knowledge modeling and reasoning, natural
language processing, anomaly detection, data cleansing, semantic search,
analytics, data classification, root cause analysis, and recommendations
systems. The main contribution of this paper is the introduction of a novel
system - the Semantic Knowledge Graph - which is able to dynamically discover
and score interesting relationships between any arbitrary combination of
entities (words, phrases, or extracted concepts) through dynamically
materializing nodes and edges from a compact graphical representation built
automatically from a corpus of data representative of a knowledge domain.
Bi-Text Alignment of Movie Subtitles for Spoken English-Arabic Statistical Machine Translation
Authors: Fahad Al-Obaidli, Stephen Cox, Preslav Nakov
Date: 2016-09-05 00:00:00
Tasks: Machine Translation, Translation

We describe efforts towards getting better resources for English-Arabic
machine translation of spoken text. In particular, we look at movie subtitles
as a unique, rich resource, as subtitles in one language often get translated
into other languages. Movie subtitles are not new as a resource and have been
explored in previous research; however, here we create a much larger bi-text
(the biggest to date), and we further generate better quality alignment for it.
Given the subtitles for the same movie in different languages, a key problem is
how to align them at the fragment level. Typically, this is done using
length-based alignment, but for movie subtitles, there is also time
information. Here we exploit this information to develop an original algorithm
that outperforms the current best subtitle alignment tool, subalign. The
evaluation results show that adding our bi-text to the IWSLT training bi-text
yields an improvement of over two BLEU points absolute.
Latent Tree Language Model
Authors: Tomas Brychcin
Date: 2016-07-24 00:00:00
Tasks: Language Modeling, Language Modelling, model, Sentence

In this paper we introduce Latent Tree Language Model (LTLM), a novel
approach to language modeling that encodes syntax and semantics of a given
sentence as a tree of word roles.
  The learning phase iteratively updates the trees by moving nodes according to
Gibbs sampling. We introduce two algorithms to infer a tree for a given
sentence. The first one is based on Gibbs sampling. It is fast, but does not
guarantee to find the most probable tree. The second one is based on dynamic
programming. It is slower, but guarantees to find the most probable tree. We
provide comparison of both algorithms.
  We combine LTLM with 4-gram Modified Kneser-Ney language model via linear
interpolation. Our experiments with English and Czech corpora show significant
perplexity reductions (up to 46% for English and 49% for Czech) compared with
standalone 4-gram Modified Kneser-Ney language model.
The Player Kernel: Learning Team Strengths Based on Implicit Player Contributions
Authors: Lucas Maystre, Victor Kristof, Antonio J. González Ferrer, Matthias Grossglauser
Date: 2016-09-05 00:00:00
Tasks: General Classification

In this work, we draw attention to a connection between skill-based models of
game outcomes and Gaussian process classification models. The Gaussian process
perspective enables a) a principled way of dealing with uncertainty and b) rich
models, specified through kernel functions. Using this connection, we tackle
the problem of predicting outcomes of football matches between national teams.
We develop a player kernel that relates any two football matches through the
players lined up on the field. This makes it possible to share knowledge gained
from observing matches between clubs (available in large quantities) and
matches between national teams (available only in limited quantities). We
evaluate our approach on the Euro 2008, 2012 and 2016 final tournaments.
Performance Localisation
Authors: Brendan Cody-Kenny, Michael O'Neill, Stephen Barrett
Date: 2016-03-04 00:00:00

Performance becomes an issue particularly when execution cost hinders the
functionality of a program. Typically a profiler can be used to find program
code execution which represents a large portion of the overall execution cost
of a program. Pinpointing where a performance issue exists provides a starting
point for tracing cause back through a program.
  While profiling shows where a performance issue manifests, we use mutation
analysis to show where a performance improvement is likely to exist. We find
that mutation analysis can indicate locations within a program which are highly
impactful to the overall execution cost of a program yet are executed
relatively infrequently. By better locating potential performance improvements
in programs we hope to make performance improvement more amenable to
automation.
Using Kernel Methods and Model Selection for Prediction of Preterm Birth
Authors: Ilia Vovsha, Ansaf Salleb-Aouissi, Anita Raja, Thomas Koch, Alex Rybchuk, Axinia Radeva, Ashwath Rajan, Yiwen Huang, Hatim Diab, Ashish Tomar, Ronald Wapner
Date: 2016-07-27 00:00:00
Tasks: Model Selection

We describe an application of machine learning to the problem of predicting
preterm birth. We conduct a secondary analysis on a clinical trial dataset
collected by the National In- stitute of Child Health and Human Development
(NICHD) while focusing our attention on predicting different classes of preterm
birth. We compare three approaches for deriving predictive models: a support
vector machine (SVM) approach with linear and non-linear kernels, logistic
regression with different model selection along with a model based on decision
rules prescribed by physician experts for prediction of preterm birth. Our
approach highlights the pre-processing methods applied to handle the inherent
dynamics, noise and gaps in the data and describe techniques used to handle
skewed class distributions. Empirical experiments demonstrate significant
improvement in predicting preterm birth compared to past work.
Reflections on Shannon Information: In search of a natural information-entropy for images
Authors: Kieran G. Larkin
Date: 2016-09-05 00:00:00

It is not obvious how to extend Shannon's original information entropy to
higher dimensions, and many different approaches have been tried. We replace
the English text symbol sequence originally used to illustrate the theory by a
discrete, bandlimited signal. Using Shannon's later theory of sampling we
derive a new and symmetric version of the second order entropy in 1D. The new
theory then naturally extends to 2D and higher dimensions, where by naturally
we mean simple, symmetric, isotropic and parsimonious. Simplicity arises from
the direct application of Shannon's joint entropy equalities and inequalities
to the gradient (del) vector field image embodying the second order relations
of the scalar image. Parsimony is guaranteed by halving of the vector data rate
using Papoulis' generalized sampling expansion. The new 2D entropy measure,
which we dub delentropy, is underpinned by a computable probability density
function we call deldensity. The deldensity captures the underlying spatial
image structure and pixel co-occurrence. It achieves this because each scalar
image pixel value is nonlocally related to the entire gradient vector field.
Both deldensity and delentropy are highly tractable and yield many interesting
connections and useful inequalities. The new measure explicitly defines a
realizable encoding algorithm and a corresponding reconstruction. Initial tests
show that delentropy compares favourably with the conventional intensity-based
histogram entropy and the compressed data rates of lossless image encoders
(GIF, PNG, WEBP, JP2K-LS and JPG-LS) for a selection of images. The symmetric
approach may have applications to higher dimensions and problems concerning
image complexity measures.
Deep Retinal Image Understanding
Authors: Kevis-Kokitsi Maninis, Jordi Pont-Tuset, Pablo Arbeláez, Luc van Gool
Date: 2016-09-05 00:00:00
Tasks: General Classification, image-classification, Image Classification, object-detection, Object Detection, Optic Disc Segmentation, Segmentation

This paper presents Deep Retinal Image Understanding (DRIU), a unified
framework of retinal image analysis that provides both retinal vessel and optic
disc segmentation. We make use of deep Convolutional Neural Networks (CNNs),
which have proven revolutionary in other fields of computer vision such as
object detection and image classification, and we bring their power to the
study of eye fundus images. DRIU uses a base network architecture on which two
set of specialized layers are trained to solve both the retinal vessel and
optic disc segmentation. We present experimental validation, both qualitative
and quantitative, in four public datasets for these tasks. In all of them, DRIU
presents super-human performance, that is, it shows results more consistent
with a gold standard than a second human annotator used as control.
A max-cut approach to heterogeneity in cryo-electron microscopy
Authors: Yariv Aizenbud, Yoel Shkolnisky
Date: 2016-09-05 00:00:00
Tasks: Classification, General Classification

The field of cryo-electron microscopy has made astounding advancements in the past few years, mainly due to advancements in electron detectors' technology. Yet, one of the key open challenges of the field remains the processing of heterogeneous data sets, produced from samples containing particles at several different conformational states. For such data sets, the algorithms must include some classification procedure to identify homogeneous groups within the data, so that the images in each group correspond to the same underlying structure. The fundamental importance of the heterogeneity problem in cryo-electron microscopy has drawn many research efforts, and resulted in significant progress in classification algorithms for heterogeneous data sets. While these algorithms are extremely useful and effective in practice, they lack rigorous mathematical analysis and performance guarantees. In this paper, we attempt to make the first steps towards rigorous mathematical analysis of the heterogeneity problem in cryo-electron microscopy. To that end, we present an algorithm for processing heterogeneous data sets, and prove accuracy and stability bounds for it. We also suggest an extension of this algorithm that combines the classification and reconstruction steps. We demonstrate it on simulated data, and compare its performance to the state-of-the-art algorithm in RELION.
GTApprox: surrogate modeling for industrial design
Authors: Mikhail Belyaev, Evgeny Burnaev, Ermek Kapushev, Maxim Panov, Pavel Prikhodko, Dmitry Vetrov, Dmitry Yarotsky
Date: 2016-09-05 00:00:00
Tasks: Model Selection

We describe GTApprox - a new tool for medium-scale surrogate modeling in
industrial design. Compared to existing software, GTApprox brings several
innovations: a few novel approximation algorithms, several advanced methods of
automated model selection, novel options in the form of hints. We demonstrate
the efficiency of GTApprox on a large collection of test problems. In addition,
we describe several applications of GTApprox to real engineering problems.
Difference of Convex Functions Programming Applied to Control with Expert Data
Authors: Bilal Piot, Matthieu Geist, Olivier Pietquin
Date: 2016-06-03 00:00:00
Tasks: General Classification, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

This paper reports applications of Difference of Convex functions (DC)
programming to Learning from Demonstrations (LfD) and Reinforcement Learning
(RL) with expert data. This is made possible because the norm of the Optimal
Bellman Residual (OBR), which is at the heart of many RL and LfD algorithms, is
DC. Improvement in performance is demonstrated on two specific algorithms,
namely Reward-regularized Classification for Apprenticeship Learning (RCAL) and
Reinforcement Learning with Expert Demonstrations (RLED), through experiments
on generic Markov Decision Processes (MDP), called Garnets.
Classifying and sorting cluttered piles of unknown objects with robots: a learning approach
Authors: Janne V. Kujala, Tuomas J. Lukka, Harri Holopainen
Date: 2016-09-05 00:00:00
Tasks: Active Learning

We consider the problem of sorting a densely cluttered pile of unknown
objects using a robot. This yet unsolved problem is relevant in the robotic
waste sorting business.
  By extending previous active learning approaches to grasping, we show a
system that learns the task autonomously. Instead of predicting just whether a
grasp succeeds, we predict the classes of the objects that end up being picked
and thrown onto the target conveyor. Segmenting and identifying objects from
the uncluttered target conveyor, as opposed to the working area, is easier due
to the added structure since the thrown objects will be the only ones present.
  Instead of trying to segment or otherwise understand the cluttered working
area in any way, we simply allow the controller to learn a mapping from an RGBD
image in the neighborhood of the grasp to a predicted result---all segmentation
etc. in the working area is implicit in the learned function. The grasp
selection operates in two stages: The first stage is hardcoded and outputs a
distribution of possible grasps that sometimes succeed. The second stage uses a
purely learned criterion to choose the grasp to make from the proposal
distribution created by the first stage.
  In an experiment, the system quickly learned to make good pickups and predict
correctly, in advance, which class of object it was going to pick up and was
able to sort the objects from a densely cluttered pile by color.
Towards optimal nonlinearities for sparse recovery using higher-order statistics
Authors: Steffen Limmer, Sławomir Stańczak
Date: 2016-05-26 00:00:00

We consider machine learning techniques to develop low-latency approximate
solutions to a class of inverse problems. More precisely, we use a
probabilistic approach for the problem of recovering sparse stochastic signals
that are members of the $\ell_p$-balls. In this context, we analyze the
Bayesian mean-square-error (MSE) for two types of estimators: (i) a linear
estimator and (ii) a structured estimator composed of a linear operator
followed by a Cartesian product of univariate nonlinear mappings. By
construction, the complexity of the proposed nonlinear estimator is comparable
to that of its linear counterpart since the nonlinear mapping can be
implemented efficiently in hardware by means of look-up tables (LUTs). The
proposed structure lends itself to neural networks and iterative
shrinkage/thresholding-type algorithms restricted to a single iterate (e.g. due
to imposed hardware or latency constraints). By resorting to an alternating
minimization technique, we obtain a sequence of optimized linear operators and
nonlinear mappings that converge in the MSE objective. The result is attractive
for real-time applications where general iterative and convex optimization
methods are infeasible.
Probabilistic Knowledge Graph Construction: Compositional and Incremental Approaches
Authors: Dongwoo Kim, Lexing Xie, Cheng Soon Ong
Date: 2016-08-21 00:00:00
Tasks: graph construction

Knowledge graph construction consists of two tasks: extracting information
from external resources (knowledge population) and inferring missing
information through a statistical analysis on the extracted information
(knowledge completion). In many cases, insufficient external resources in the
knowledge population hinder the subsequent statistical inference. The gap
between these two processes can be reduced by an incremental population
approach. We propose a new probabilistic knowledge graph factorisation method
that benefits from the path structure of existing knowledge (e.g. syllogism)
and enables a common modelling approach to be used for both incremental
population and knowledge completion tasks. More specifically, the probabilistic
formulation allows us to develop an incremental population algorithm that
trades off exploitation-exploration. Experiments on three benchmark datasets
show that the balanced exploitation-exploration helps the incremental
population, and the additional path structure helps to predict missing
information in knowledge completion.
Convexified Convolutional Neural Networks
Authors: Yuchen Zhang, Percy Liang, Martin J. Wainwright
Date: 2016-09-04 00:00:00
Proceeding: ICML 2017 8
Tasks: Denoising

We describe the class of convexified convolutional neural networks (CCNNs),
which capture the parameter sharing of convolutional neural networks in a
convex manner. By representing the nonlinear convolutional filters as vectors
in a reproducing kernel Hilbert space, the CNN parameters can be represented as
a low-rank matrix, which can be relaxed to obtain a convex optimization
problem. For learning two-layer convolutional neural networks, we prove that
the generalization error obtained by a convexified CNN converges to that of the
best possible CNN. For learning deeper networks, we train CCNNs in a layer-wise
manner. Empirically, CCNNs achieve performance competitive with CNNs trained by
backpropagation, SVMs, fully-connected neural networks, stacked denoising
auto-encoders, and other baseline methods.
A General Framework for Constrained Bayesian Optimization using Information-based Search
Authors: José Miguel Hernández-Lobato, Michael A. Gelbart, Ryan P. Adams, Matthew W. Hoffman, Zoubin Ghahramani
Date: 2015-11-30 00:00:00
Tasks: Bayesian Optimization, CPU, GPU

We present an information-theoretic framework for solving global black-box
optimization problems that also have black-box constraints. Of particular
interest to us is to efficiently solve problems with decoupled constraints, in
which subsets of the objective and constraint functions may be evaluated
independently. For example, when the objective is evaluated on a CPU and the
constraints are evaluated independently on a GPU. These problems require an
acquisition function that can be separated into the contributions of the
individual function evaluations. We develop one such acquisition function and
call it Predictive Entropy Search with Constraints (PESC). PESC is an
approximation to the expected information gain criterion and it compares
favorably to alternative approaches based on improvement in several synthetic
and real-world problems. In addition to this, we consider problems with a mix
of functions that are fast and slow to evaluate. These problems require
balancing the amount of time spent in the meta-computation of PESC and in the
actual evaluation of the target objective. We take a bounded rationality
approach and develop partial update for PESC which trades off accuracy against
speed. We then propose a method for adaptively switching between the partial
and full updates for PESC. This allows us to interpolate between versions of
PESC that are efficient in terms of function evaluations and those that are
efficient in terms of wall-clock time. Overall, we demonstrate that PESC is an
effective algorithm that provides a promising direction towards a unified
solution for constrained Bayesian optimization.
Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences
Authors: Chi Jin, Yuchen Zhang, Sivaraman Balakrishnan, Martin J. Wainwright, Michael Jordan
Date: 2016-09-04 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Open-Ended Question Answering

We provide two fundamental results on the population (infinite-sample)
likelihood function of Gaussian mixture models with $M \geq 3$ components. Our
first main result shows that the population likelihood function has bad local
maxima even in the special case of equally-weighted mixtures of well-separated
and spherical Gaussians. We prove that the log-likelihood value of these bad
local maxima can be arbitrarily worse than that of any global optimum, thereby
resolving an open question of Srebro (2007). Our second main result shows that
the EM algorithm (or a first-order variant of it) with random initialization
will converge to bad critical points with probability at least
$1-e^{-\Omega(M)}$. We further establish that a first-order variant of EM will
not converge to strict saddle points almost surely, indicating that the poor
performance of the first-order method can be attributed to the existence of bad
local maxima rather than bad saddle points. Overall, our results highlight the
necessity of careful initialization when using the EM algorithm in practice,
even when applied in highly favorable settings.