pwc-archive/papers-with-abstracts huggingface dataset:
Finite Sample Prediction and Recovery Bounds for Ordinal Embedding
Authors: Lalit Jain, Kevin Jamieson, Robert Nowak
Date: 2016-06-22 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Prediction

The goal of ordinal embedding is to represent items as points in a
low-dimensional Euclidean space given a set of constraints in the form of
distance comparisons like "item $i$ is closer to item $j$ than item $k$".
Ordinal constraints like this often come from human judgments. To account for
errors and variation in judgments, we consider the noisy situation in which the
given constraints are independently corrupted by reversing the correct
constraint with some probability. This paper makes several new contributions to
this problem. First, we derive prediction error bounds for ordinal embedding
with noise by exploiting the fact that the rank of a distance matrix of points
in $\mathbb{R}^d$ is at most $d+2$. These bounds characterize how well a
learned embedding predicts new comparative judgments. Second, we investigate
the special case of a known noise model and study the Maximum Likelihood
estimator. Third, knowledge of the noise model enables us to relate prediction
errors to embedding accuracy. This relationship is highly non-trivial since we
show that the linear map corresponding to distance comparisons is
non-invertible, but there exists a nonlinear map that is invertible. Fourth,
two new algorithms for ordinal embedding are proposed and evaluated in
experiments.
Emulating Human Conversations using Convolutional Neural Network-based IR
Authors: Abhay Prakash, Chris Brockett, Puneet Agrawal
Date: 2016-06-22 00:00:00
Tasks: Information Retrieval, Retrieval

Conversational agents ("bots") are beginning to be widely used in
conversational interfaces. To design a system that is capable of emulating
human-like interactions, a conversational layer that can serve as a fabric for
chat-like interaction with the agent is needed. In this paper, we introduce a
model that employs Information Retrieval by utilizing convolutional deep
structured semantic neural network-based features in the ranker to present
human-like responses in ongoing conversation with a user. In conversations,
accounting for context is critical to the retrieval model; we show that our
context-sensitive approach using a Convolutional Deep Structured Semantic Model
(cDSSM) with character trigrams significantly outperforms several conventional
baselines in terms of the relevance of responses retrieved.
The Fourier Transform of Poisson Multinomial Distributions and its Algorithmic Applications
Authors: Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
Date: 2015-11-11 00:00:00
Tasks: Learning Theory

An $(n, k)$-Poisson Multinomial Distribution (PMD) is a random variable of
the form $X = \sum_{i=1}^n X_i$, where the $X_i$'s are independent random
vectors supported on the set of standard basis vectors in $\mathbb{R}^k.$ In
this paper, we obtain a refined structural understanding of PMDs by analyzing
their Fourier transform. As our core structural result, we prove that the
Fourier transform of PMDs is {\em approximately sparse}, i.e., roughly
speaking, its $L_1$-norm is small outside a small set. By building on this
result, we obtain the following applications:
  {\bf Learning Theory.} We design the first computationally efficient learning
algorithm for PMDs with respect to the total variation distance. Our algorithm
learns an arbitrary $(n, k)$-PMD within variation distance $\epsilon$ using a
near-optimal sample size of $\widetilde{O}_k(1/\epsilon^2),$ and runs in time
$\widetilde{O}_k(1/\epsilon^2) \cdot \log n.$ Previously, no algorithm with a
$\mathrm{poly}(1/\epsilon)$ runtime was known, even for $k=3.$
  {\bf Game Theory.} We give the first efficient polynomial-time approximation
scheme (EPTAS) for computing Nash equilibria in anonymous games. For normalized
anonymous games with $n$ players and $k$ strategies, our algorithm computes a
well-supported $\epsilon$-Nash equilibrium in time $n^{O(k^3)} \cdot
(k/\epsilon)^{O(k^3\log(k/\epsilon)/\log\log(k/\epsilon))^{k-1}}.$ The best
previous algorithm for this problem had running time $n^{(f(k)/\epsilon)^k},$
where $f(k) = \Omega(k^{k^2})$, for any $k>2.$
  {\bf Statistics.} We prove a multivariate central limit theorem (CLT) that
relates an arbitrary PMD to a discretized multivariate Gaussian with the same
mean and covariance, in total variation distance. Our new CLT strengthens the
CLT of Valiant and Valiant by completely removing the dependence on $n$ in the
error bound.
Toward Interpretable Topic Discovery via Anchored Correlation Explanation
Authors: Kyle Reing, David C. Kale, Greg Ver Steeg, Aram Galstyan
Date: 2016-06-22 00:00:00

Many predictive tasks, such as diagnosing a patient based on their medical
chart, are ultimately defined by the decisions of human experts. Unfortunately,
encoding experts' knowledge is often time consuming and expensive. We propose a
simple way to use fuzzy and informal knowledge from experts to guide discovery
of interpretable latent topics in text. The underlying intuition of our
approach is that latent factors should be informative about both correlations
in the data and a set of relevance variables specified by an expert.
Mathematically, this approach is a combination of the information bottleneck
and Total Correlation Explanation (CorEx). We give a preliminary evaluation of
Anchored CorEx, showing that it produces more coherent and interpretable topics
on two distinct corpora.
Efficient Attack Graph Analysis through Approximate Inference
Authors: Luis Muñoz-González, Daniele Sgandurra, Andrea Paudice, Emil C. Lupu
Date: 2016-06-22 00:00:00
Tasks: Bayesian Inference, Clustering

Attack graphs provide compact representations of the attack paths that an
attacker can follow to compromise network resources by analysing network
vulnerabilities and topology. These representations are a powerful tool for
security risk assessment. Bayesian inference on attack graphs enables the
estimation of the risk of compromise to the system's components given their
vulnerabilities and interconnections, and accounts for multi-step attacks
spreading through the system. Whilst static analysis considers the risk posture
at rest, dynamic analysis also accounts for evidence of compromise, e.g. from
SIEM software or forensic investigation. However, in this context, exact
Bayesian inference techniques do not scale well. In this paper we show how
Loopy Belief Propagation - an approximate inference technique - can be applied
to attack graphs, and that it scales linearly in the number of nodes for both
static and dynamic analysis, making such analyses viable for larger networks.
We experiment with different topologies and network clustering on synthetic
Bayesian attack graphs with thousands of nodes to show that the algorithm's
accuracy is acceptable and converge to a stable solution. We compare sequential
and parallel versions of Loopy Belief Propagation with exact inference
techniques for both static and dynamic analysis, showing the advantages of
approximate inference techniques to scale to larger attack graphs.
Active Algorithms For Preference Learning Problems with Multiple Populations
Authors: Aniruddha Bhargava, Ravi Ganti, Robert Nowak
Date: 2016-03-14 00:00:00
Tasks: Active Learning

In this paper we model the problem of learning preferences of a population as
an active learning problem. We propose an algorithm can adaptively choose pairs
of items to show to users coming from a heterogeneous population, and use the
obtained reward to decide which pair of items to show next. We provide
computationally efficient algorithms with provable sample complexity guarantees
for this problem in both the noiseless and noisy cases. In the process of
establishing sample complexity guarantees for our algorithms, we establish new
results using a Nystr{\"o}m-like method which can be of independent interest.
We supplement our theoretical results with experimental comparisons.
The IBM 2016 English Conversational Telephone Speech Recognition System
Authors: George Saon, Tom Sercu, Steven Rennie, Hong-Kwang J. Kuo
Date: 2016-04-27 00:00:00
Tasks: Language Modeling, Language Modelling, speech-recognition, Speech Recognition

We describe a collection of acoustic and language modeling techniques that
lowered the word error rate of our English conversational telephone LVCSR
system to a record 6.6% on the Switchboard subset of the Hub5 2000 evaluation
testset. On the acoustic side, we use a score fusion of three strong models:
recurrent nets with maxout activations, very deep convolutional nets with 3x3
kernels, and bidirectional long short-term memory nets which operate on FMLLR
and i-vector features. On the language modeling side, we use an updated model
"M" and hierarchical neural network LMs.
The word entropy of natural languages
Authors: Christian Bentz, Dimitrios Alikaniotis
Date: 2016-06-22 00:00:00
Tasks: Semantic Similarity, Semantic Textual Similarity, Translation

The average uncertainty associated with words is an information-theoretic
concept at the heart of quantitative and computational linguistics. The entropy
has been established as a measure of this average uncertainty - also called
average information content. We here use parallel texts of 21 languages to
establish the number of tokens at which word entropies converge to stable
values. These convergence points are then used to select texts from a massively
parallel corpus, and to estimate word entropies across more than 1000
languages. Our results help to establish quantitative language comparisons, to
understand the performance of multilingual translation systems, and to
normalize semantic similarity measures.
Personalized Prognostic Models for Oncology: A Machine Learning Approach
Authors: David Dooling, Angela Kim, Barbara McAneny, Jennifer Webster
Date: 2016-06-22 00:00:00
Tasks: BIG-bench Machine Learning, Epidemiology

We have applied a little-known data transformation to subsets of the
Surveillance, Epidemiology, and End Results (SEER) publically available data of
the National Cancer Institute (NCI) to make it suitable input to standard
machine learning classifiers. This transformation properly treats the
right-censored data in the SEER data and the resulting Random Forest and
Multi-Layer Perceptron models predict full survival curves. Treating the 6, 12,
and 60 months points of the resulting survival curves as 3 binary classifiers,
the 18 resulting classifiers have AUC values ranging from .765 to .885. Further
evidence that the models have generalized well from the training data is
provided by the extremely high levels of agreement between the random forest
and neural network models predictions on the 6, 12, and 60 month binary
classifiers.
Toward Word Embedding for Personalized Information Retrieval
Authors: Nawal Ould-Amer, Philippe Mulhem, Mathias Gery
Date: 2016-06-22 00:00:00
Tasks: Information Retrieval, Retrieval, Word Embeddings

This paper presents preliminary works on using Word Embedding (word2vec) for
query expansion in the context of Personalized Information Retrieval.
Traditionally, word embeddings are learned on a general corpus, like Wikipedia.
In this work we try to personalize the word embeddings learning, by achieving
the learning on the user's profile. The word embeddings are then in the same
context than the user interests. Our proposal is evaluated on the CLEF Social
Book Search 2016 collection. The results obtained show that some efforts should
be made in the way to apply Word Embedding in the context of Personalized
Information Retrieval.
Fast, Compact, and High Quality LSTM-RNN Based Statistical Parametric Speech Synthesizers for Mobile Devices
Authors: Heiga Zen, Yannis Agiomyrgiannakis, Niels Egberts, Fergus Henderson, Przemysław Szczepaniak
Date: 2016-06-20 00:00:00
Tasks: Quantization, Speech Synthesis

Acoustic models based on long short-term memory recurrent neural networks
(LSTM-RNNs) were applied to statistical parametric speech synthesis (SPSS) and
showed significant improvements in naturalness and latency over those based on
hidden Markov models (HMMs). This paper describes further optimizations of
LSTM-RNN-based SPSS for deployment on mobile devices; weight quantization,
multi-frame inference, and robust inference using an {\epsilon}-contaminated
Gaussian loss function. Experimental results in subjective listening tests show
that these optimizations can make LSTM-RNN-based SPSS comparable to HMM-based
SPSS in runtime speed while maintaining naturalness. Evaluations between
LSTM-RNN- based SPSS and HMM-driven unit selection speech synthesis are also
presented.
Simultaneous Control and Human Feedback in the Training of a Robotic Agent with Actor-Critic Reinforcement Learning
Authors: Kory W. Mathewson, Patrick M. Pilarski
Date: 2016-06-22 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

This paper contributes a preliminary report on the advantages and
disadvantages of incorporating simultaneous human control and feedback signals
in the training of a reinforcement learning robotic agent. While robotic
human-machine interfaces have become increasingly complex in both form and
function, control remains challenging for users. This has resulted in an
increasing gap between user control approaches and the number of robotic motors
which can be controlled. One way to address this gap is to shift some autonomy
to the robot. Semi-autonomous actions of the robotic agent can then be shaped
by human feedback, simplifying user control. Most prior work on agent shaping
by humans has incorporated training with feedback, or has included indirect
control signals. By contrast, in this paper we explore how a human can provide
concurrent feedback signals and real-time myoelectric control signals to train
a robot's actor-critic reinforcement learning control system. Using both a
physical and a simulated robotic system, we compare training performance on a
simple movement task when reward is derived from the environment, when reward
is provided by the human, and combinations of these two approaches. Our results
indicate that some benefit can be gained with the inclusion of human generated
feedback.
Towards stationary time-vertex signal processing
Authors: Nathanael Perraudin, Andreas Loukas, Francesco Grassi, Pierre Vandergheynst
Date: 2016-06-22 00:00:00
Tasks: Denoising

Graph-based methods for signal processing have shown promise for the analysis
of data exhibiting irregular structure, such as those found in social,
transportation, and sensor networks. Yet, though these systems are often
dynamic, state-of-the-art methods for signal processing on graphs ignore the
dimension of time, treating successive graph signals independently or taking a
global average. To address this shortcoming, this paper considers the
statistical analysis of time-varying graph signals. We introduce a novel
definition of joint (time-vertex) stationarity, which generalizes the classical
definition of time stationarity and the more recent definition appropriate for
graphs. Joint stationarity gives rise to a scalable Wiener optimization
framework for joint denoising, semi-supervised learning, or more generally
inversing a linear operator, that is provably optimal. Experimental results on
real weather data demonstrate that taking into account graph and time
dimensions jointly can yield significant accuracy improvements in the
reconstruction effort.
An Approach for Parallel Genetic Algorithms in the Cloud using Software Containers
Authors: Pasquale Salza, Filomena Ferrucci
Date: 2016-06-22 00:00:00

Genetic Algorithms (GAs) are a powerful technique to address hard
optimisation problems. However, scalability issues might prevent them from
being applied to real-world problems. Exploiting parallel GAs in the cloud
might be an affordable approach to get time efficient solutions that benefit of
the appealing features of the cloud, such as scalability, reliability,
fault-tolerance and cost-effectiveness. Nevertheless, distributed computation
is very prone to cause considerable overhead for communication and making GAs
distributed in an on-demand fashion is not trivial. Aiming to keep under
control the communication overhead and support GAs developers in the
construction and deployment of parallel GAs in the cloud, in this paper we
propose an approach to distribute GAs using the global parallelisation model,
exploiting software containers and their cloud orchestration. We also devised a
conceptual workflow covering each cloud GAs distribution phase, from resources
allocation to actual deployment and execution, in a DevOps fashion.
Do Prices Coordinate Markets?
Authors: Justin Hsu, Jamie Morgenstern, Ryan Rogers, Aaron Roth, Rakesh Vohra
Date: 2015-11-03 00:00:00

Walrasian equilibrium prices can be said to coordinate markets: They support
a welfare optimal allocation in which each buyer is buying bundle of goods that
is individually most preferred. However, this clean story has two caveats.
First, the prices alone are not sufficient to coordinate the market, and buyers
may need to select among their most preferred bundles in a coordinated way to
find a feasible allocation. Second, we don't in practice expect to encounter
exact equilibrium prices tailored to the market, but instead only approximate
prices, somehow encoding "distributional" information about the market. How
well do prices work to coordinate markets when tie-breaking is not coordinated,
and they encode only distributional information?
  We answer this question. First, we provide a genericity condition such that
for buyers with Matroid Based Valuations, overdemand with respect to
equilibrium prices is at most 1, independent of the supply of goods, even when
tie-breaking is done in an uncoordinated fashion. Second, we provide
learning-theoretic results that show that such prices are robust to changing
the buyers in the market, so long as all buyers are sampled from the same
(unknown) distribution.
Recognizing Surgical Activities with Recurrent Neural Networks
Authors: Robert DiPietro, Colin Lea, Anand Malpani, Narges Ahmidi, S. Swaroop Vedula, Gyusung I. Lee, Mija R. Lee, Gregory D. Hager
Date: 2016-06-20 00:00:00
Tasks: Gesture Recognition

We apply recurrent neural networks to the task of recognizing surgical
activities from robot kinematics. Prior work in this area focuses on
recognizing short, low-level activities, or gestures, and has been based on
variants of hidden Markov models and conditional random fields. In contrast, we
work on recognizing both gestures and longer, higher-level activites, or
maneuvers, and we model the mapping from kinematics to gestures/maneuvers with
recurrent neural networks. To our knowledge, we are the first to apply
recurrent neural networks to this task. Using a single model and a single set
of hyperparameters, we match state-of-the-art performance for gesture
recognition and advance state-of-the-art performance for maneuver recognition,
in terms of both accuracy and edit distance. Code is available at
https://github.com/rdipietro/miccai-2016-surgical-activity-rec .
Optimal Transport for Domain Adaptation
Authors: Nicolas Courty, Rémi Flamary, Devis Tuia, Alain Rakotomamonjy
Date: 2015-07-02 00:00:00
Tasks: Domain Adaptation

Domain adaptation from one data space (or domain) to another is one of the
most challenging tasks of modern data analytics. If the adaptation is done
correctly, models built on a specific data space become more robust when
confronted to data depicting the same semantic concepts (the classes), but
observed by another observation system with its own specificities. Among the
many strategies proposed to adapt a domain to another, finding a common
representation has shown excellent properties: by finding a common
representation for both domains, a single classifier can be effective in both
and use labelled samples from the source domain to predict the unlabelled
samples of the target domain. In this paper, we propose a regularized
unsupervised optimal transportation model to perform the alignment of the
representations in the source and target domains. We learn a transportation
plan matching both PDFs, which constrains labelled samples in the source domain
to remain close during transport. This way, we exploit at the same time the few
labeled information in the source and the unlabelled distributions observed in
both domains. Experiments in toy and challenging real visual adaptation
examples show the interest of the method, that consistently outperforms state
of the art approaches.
Robust Audio Event Recognition with 1-Max Pooling Convolutional Neural Networks
Authors: Huy Phan, Lars Hertel, Marco Maass, Alfred Mertins
Date: 2016-04-21 00:00:00

We present in this paper a simple, yet efficient convolutional neural network
(CNN) architecture for robust audio event recognition. Opposing to deep CNN
architectures with multiple convolutional and pooling layers topped up with
multiple fully connected layers, the proposed network consists of only three
layers: convolutional, pooling, and softmax layer. Two further features
distinguish it from the deep architectures that have been proposed for the
task: varying-size convolutional filters at the convolutional layer and 1-max
pooling scheme at the pooling layer. In intuition, the network tends to select
the most discriminative features from the whole audio signals for recognition.
Our proposed CNN not only shows state-of-the-art performance on the standard
task of robust audio event recognition but also outperforms other deep
architectures up to 4.5% in terms of recognition accuracy, which is equivalent
to 76.3% relative error reduction.
A Fuzzy Clustering Algorithm for the Mode Seeking Framework
Authors: Thomas Bonis, Steve Oudot
Date: 2014-06-27 00:00:00
Tasks: Clustering

In this paper, we propose a new fuzzy clustering algorithm based on the
mode-seeking framework. Given a dataset in $\mathbb{R}^d$, we define regions of
high density that we call cluster cores. We then consider a random walk on a
neighborhood graph built on top of our data points which is designed to be
attracted by high density regions. The strength of this attraction is
controlled by a temperature parameter $\beta > 0$. The membership of a point to
a given cluster is then the probability for the random walk to hit the
corresponding cluster core before any other. While many properties of random
walks (such as hitting times, commute distances, etc\dots) have been shown to
enventually encode purely local information when the number of data points
grows, we show that the regularization introduced by the use of cluster cores
solves this issue. Empirically, we show how the choice of $\beta$ influences
the behavior of our algorithm: for small values of $\beta$ the result is close
to hard mode-seeking whereas when $\beta$ is close to $1$ the result is similar
to the output of a (fuzzy) spectral clustering. Finally, we demonstrate the
scalability of our approach by providing the fuzzy clustering of a protein
configuration dataset containing a million data points in $30$ dimensions.