pwc-archive/papers-with-abstracts huggingface dataset:
Extending Consequence-Based Reasoning to SRIQ
Authors: Andrew Bate, Boris Motik, Bernardo Cuenca Grau, František Simančík, Ian Horrocks
Date: 2016-02-14 00:00:00

Consequence-based calculi are a family of reasoning algorithms for
description logics (DLs), and they combine hypertableau and resolution in a way
that often achieves excellent performance in practice. Up to now, however, they
were proposed for either Horn DLs (which do not support disjunction), or for
DLs without counting quantifiers. In this paper we present a novel
consequence-based calculus for SRIQ---a rich DL that supports both features.
This extension is non-trivial since the intermediate consequences that need to
be derived during reasoning cannot be captured using DLs themselves. The
results of our preliminary performance evaluation suggest the feasibility of
our approach in practice.
Unsupervised Ensemble Learning with Dependent Classifiers
Authors: Ariel Jaffe, Ethan Fetaya, Boaz Nadler, Tingting Jiang, Yuval Kluger
Date: 2015-10-20 00:00:00
Tasks: Diversity, Ensemble Learning

In unsupervised ensemble learning, one obtains predictions from multiple
sources or classifiers, yet without knowing the reliability and expertise of
each source, and with no labeled data to assess it. The task is to combine
these possibly conflicting predictions into an accurate meta-learner. Most
works to date assumed perfect diversity between the different sources, a
property known as conditional independence. In realistic scenarios, however,
this assumption is often violated, and ensemble learners based on it can be
severely sub-optimal. The key challenges we address in this paper are:\ (i) how
to detect, in an unsupervised manner, strong violations of conditional
independence; and (ii) construct a suitable meta-learner. To this end we
introduce a statistical model that allows for dependencies between classifiers.
Our main contributions are the development of novel unsupervised methods to
detect strongly dependent classifiers, better estimate their accuracies, and
construct an improved meta-learner. Using both artificial and real datasets, we
showcase the importance of taking classifier dependencies into account and the
competitive performance of our approach.
The IBM 2016 Speaker Recognition System
Authors: Seyed Omid Sadjadi, Sriram Ganapathy, Jason W. Pelecanos
Date: 2016-02-23 00:00:00
Tasks: 2k, Automatic Speech Recognition, Automatic Speech Recognition (ASR), Speaker Recognition, speech-recognition, Speech Recognition

In this paper we describe the recent advancements made in the IBM i-vector
speaker recognition system for conversational speech. In particular, we
identify key techniques that contribute to significant improvements in
performance of our system, and quantify their contributions. The techniques
include: 1) a nearest-neighbor discriminant analysis (NDA) approach that is
formulated to alleviate some of the limitations associated with the
conventional linear discriminant analysis (LDA) that assumes Gaussian
class-conditional distributions, 2) the application of speaker- and
channel-adapted features, which are derived from an automatic speech
recognition (ASR) system, for speaker recognition, and 3) the use of a deep
neural network (DNN) acoustic model with a large number of output units (~10k
senones) to compute the frame-level soft alignments required in the i-vector
estimation process. We evaluate these techniques on the NIST 2010 speaker
recognition evaluation (SRE) extended core conditions involving telephone and
microphone trials. Experimental results indicate that: 1) the NDA is more
effective (up to 35% relative improvement in terms of EER) than the traditional
parametric LDA for speaker recognition, 2) when compared to raw acoustic
features (e.g., MFCCs), the ASR speaker-adapted features provide gains in
speaker recognition performance, and 3) increasing the number of output units
in the DNN acoustic model (i.e., increasing the senone set size from 2k to 10k)
provides consistent improvements in performance (for example from 37% to 57%
relative EER gains over our baseline GMM i-vector system). To our knowledge,
results reported in this paper represent the best performances published to
date on the NIST SRE 2010 extended core tasks.
Submodular Functions: from Discrete to Continous Domains
Authors: Francis Bach
Date: 2015-11-02 00:00:00
Tasks: Combinatorial Optimization

Submodular set-functions have many applications in combinatorial
optimization, as they can be minimized and approximately maximized in
polynomial time. A key element in many of the algorithms and analyses is the
possibility of extending the submodular set-function to a convex function,
which opens up tools from convex optimization. Submodularity goes beyond
set-functions and has naturally been considered for problems with multiple
labels or for functions defined on continuous domains, where it corresponds
essentially to cross second-derivatives being nonpositive. In this paper, we
show that most results relating submodularity and convexity for set-functions
can be extended to all submodular functions. In particular, (a) we naturally
define a continuous extension in a set of probability measures, (b) show that
the extension is convex if and only if the original function is submodular, (c)
prove that the problem of minimizing a submodular function is equivalent to a
typically non-smooth convex optimization problem, and (d) propose another
convex optimization problem with better computational properties (e.g., a
smooth dual problem). Most of these extensions from the set-function situation
are obtained by drawing links with the theory of multi-marginal optimal
transport, which provides also a new interpretation of existing results for
set-functions. We then provide practical algorithms to minimize generic
submodular functions on discrete domains, with associated convergence rates.
Learning to Remove Multipath Distortions in Time-of-Flight Range Images for a Robotic Arm Setup
Authors: Kilho Son, Ming-Yu Liu, Yuichi Taguchi
Date: 2016-01-08 00:00:00

Range images captured by Time-of-Flight (ToF) cameras are corrupted with
multipath distortions due to interaction between modulated light signals and
scenes. The interaction is often complicated, which makes a model-based
solution elusive. We propose a learning-based approach for removing the
multipath distortions for a ToF camera in a robotic arm setup. Our approach is
based on deep learning. We use the robotic arm to automatically collect a large
amount of ToF range images containing various multipath distortions. The
training images are automatically labeled by leveraging a high precision
structured light sensor available only in the training time. In the test time,
we apply the learned model to remove the multipath distortions. This allows our
robotic arm setup to enjoy the speed and compact form of the ToF camera without
compromising with its range measurement errors. We conduct extensive
experimental validations and compare the proposed method to several baseline
algorithms. The experiment results show that our method achieves 55% error
reduction in range estimation and largely outperforms the baseline algorithms.
Petrarch 2 : Petrarcher
Authors: Clayton Norris
Date: 2016-02-23 00:00:00
Tasks: Sentence

PETRARCH 2 is the fourth generation of a series of Event-Data coders stemming
from research by Phillip Schrodt. Each iteration has brought new functionality
and usability, and this is no exception.Petrarch 2 takes much of the power of
the original Petrarch's dictionaries and redirects it into a faster and smarter
core logic. Earlier iterations handled sentences largely as a list of words,
incorporating some syntactic information here and there. Petrarch 2 now views
the sentence entirely on the syntactic level. It receives the syntactic parse
of a sentence from the Stanford CoreNLP software, and stores this data as a
tree structure of linked nodes, where each node is a Phrase object.
Prepositional, noun, and verb phrases each have their own version of this
Phrase class, which deals with the logic particular to those kinds of phrases.
Since this is an event coder, the core of the logic focuses around the verbs:
who is acting, who is being acted on, and what is happening. The theory behind
this new structure and its logic is founded in Generative Grammar, Information
Theory, and Lambda-Calculus Semantics.
Permutational Rademacher Complexity: a New Complexity Measure for Transductive Learning
Authors: Ilya Tolstikhin, Nikita Zhivotovskiy, Gilles Blanchard
Date: 2015-05-12 00:00:00
Tasks: Learning Theory, Transductive Learning

Transductive learning considers situations when a learner observes $m$
labelled training points and $u$ unlabelled test points with the final goal of
giving correct answers for the test points. This paper introduces a new
complexity measure for transductive learning called Permutational Rademacher
Complexity (PRC) and studies its properties. A novel symmetrization inequality
is proved, which shows that PRC provides a tighter control over expected
suprema of empirical processes compared to what happens in the standard i.i.d.
setting. A number of comparison results are also provided, which show the
relation between PRC and other popular complexity measures used in statistical
learning theory, including Rademacher complexity and Transductive Rademacher
Complexity (TRC). We argue that PRC is a more suitable complexity measure for
transductive learning. Finally, these results are combined with a standard
concentration argument to provide novel data-dependent risk bounds for
transductive learning.
The ImageNet Shuffle: Reorganized Pre-training for Video Event Detection
Authors: Pascal Mettes, Dennis C. Koelma, Cees G. M. Snoek
Date: 2016-02-23 00:00:00
Tasks: Event Detection, Object Recognition

This paper strives for video event detection using a representation learned
from deep convolutional neural networks. Different from the leading approaches,
who all learn from the 1,000 classes defined in the ImageNet Large Scale Visual
Recognition Challenge, we investigate how to leverage the complete ImageNet
hierarchy for pre-training deep networks. To deal with the problems of
over-specific classes and classes with few images, we introduce a bottom-up and
top-down approach for reorganization of the ImageNet hierarchy based on all its
21,814 classes and more than 14 million images. Experiments on the TRECVID
Multimedia Event Detection 2013 and 2015 datasets show that video
representations derived from the layers of a deep neural network pre-trained
with our reorganized hierarchy i) improves over standard pre-training, ii) is
complementary among different reorganizations, iii) maintains the benefits of
fusion with other modalities, and iv) leads to state-of-the-art event detection
results. The reorganized hierarchies and their derived Caffe models are
publicly available at http://tinyurl.com/imagenetshuffle.
Learning Efficient Algorithms with Hierarchical Attentive Memory
Authors: Marcin Andrychowicz, Karol Kurach
Date: 2016-02-09 00:00:00

In this paper, we propose and investigate a novel memory architecture for
neural networks called Hierarchical Attentive Memory (HAM). It is based on a
binary tree with leaves corresponding to memory cells. This allows HAM to
perform memory access in O(log n) complexity, which is a significant
improvement over the standard attention mechanism that requires O(n)
operations, where n is the size of the memory.
  We show that an LSTM network augmented with HAM can learn algorithms for
problems like merging, sorting or binary searching from pure input-output
examples. In particular, it learns to sort n numbers in time O(n log n) and
generalizes well to input sequences much longer than the ones seen during the
training. We also show that HAM can be trained to act like classic data
structures: a stack, a FIFO queue and a priority queue.
A Streaming Algorithm for Crowdsourced Data Classification
Authors: Thomas Bonald, Richard Combes
Date: 2016-02-23 00:00:00
Tasks: Binary Classification, Classification, General Classification

We propose a streaming algorithm for the binary classification of data based
on crowdsourcing. The algorithm learns the competence of each labeller by
comparing her labels to those of other labellers on the same tasks and uses
this information to minimize the prediction error rate on each task. We provide
performance guarantees of our algorithm for a fixed population of independent
labellers. In particular, we show that our algorithm is optimal in the sense
that the cumulative regret compared to the optimal decision with known labeller
error probabilities is finite, independently of the number of tasks to label.
The complexity of the algorithm is linear in the number of labellers and the
number of tasks, up to some logarithmic factors. Numerical experiments
illustrate the performance of our algorithm compared to existing algorithms,
including simple majority voting and expectation-maximization algorithms, on
both synthetic and real datasets.
SIFT: An Algorithm for Extracting Structural Information From Taxonomies
Authors: Jorge Martinez-Gil
Date: 2016-02-23 00:00:00

In this work we present SIFT, a 3-step algorithm for the analysis of the
structural information represented by means of a taxonomy. The major advantage
of this algorithm is the capability to leverage the information inherent to the
hierarchical structures of taxonomies to infer correspondences which can allow
to merge them in a later step. This method is particular relevant in scenarios
where taxonomy alignment techniques exploiting textual information from
taxonomy nodes cannot operate successfully.
Minimum Conditional Description Length Estimation for Markov Random Fields
Authors: Matthew G. Reyes, David L. Neuhoff
Date: 2016-02-09 00:00:00

In this paper we discuss a method, which we call Minimum Conditional
Description Length (MCDL), for estimating the parameters of a subset of sites
within a Markov random field. We assume that the edges are known for the entire
graph $G=(V,E)$. Then, for a subset $U\subset V$, we estimate the parameters
for nodes and edges in $U$ as well as for edges incident to a node in $U$, by
finding the exponential parameter for that subset that yields the best
compression conditioned on the values on the boundary $\partial U$. Our
estimate is derived from a temporally stationary sequence of observations on
the set $U$. We discuss how this method can also be applied to estimate a
spatially invariant parameter from a single configuration, and in so doing,
derive the Maximum Pseudo-Likelihood (MPL) estimate.
Finding Needle in a Million Metrics: Anomaly Detection in a Large-scale Computational Advertising Platform
Authors: Bowen Zhou, Shahriar Shariat
Date: 2016-02-23 00:00:00
Tasks: Anomaly Detection

Online media offers opportunities to marketers to deliver brand messages to a
large audience. Advertising technology platforms enables the advertisers to
find the proper group of audiences and deliver ad impressions to them in real
time. The recent growth of the real time bidding has posed a significant
challenge on monitoring such a complicated system. With so many components we
need a reliable system that detects the possible changes in the system and
alerts the engineering team. In this paper we describe the mechanism that we
invented for recovering the representative metrics and detecting the change in
their behavior. We show that this mechanism is able to detect the possible
problems in time by describing some incident cases.
POMDP-lite for Robust Robot Planning under Uncertainty
Authors: Min Chen, Emilio Frazzoli, David Hsu, Wee Sun Lee
Date: 2016-02-16 00:00:00
Tasks: Reinforcement Learning, Reinforcement Learning (RL)

The partially observable Markov decision process (POMDP) provides a
principled general model for planning under uncertainty. However, solving a
general POMDP is computationally intractable in the worst case. This paper
introduces POMDP-lite, a subclass of POMDPs in which the hidden state variables
are constant or only change deterministically. We show that a POMDP-lite is
equivalent to a set of fully observable Markov decision processes indexed by a
hidden parameter and is useful for modeling a variety of interesting robotic
tasks. We develop a simple model-based Bayesian reinforcement learning
algorithm to solve POMDP-lite models. The algorithm performs well on
large-scale POMDP-lite models with up to $10^{20}$ states and outperforms the
state-of-the-art general-purpose POMDP algorithms. We further show that the
algorithm is near-Bayesian-optimal under suitable conditions.
An Improved Gap-Dependency Analysis of the Noisy Power Method
Authors: Maria Florina Balcan, Simon S. Du, Yining Wang, Adams Wei Yu
Date: 2016-02-23 00:00:00

We consider the noisy power method algorithm, which has wide applications in
machine learning and statistics, especially those related to principal
component analysis (PCA) under resource (communication, memory or privacy)
constraints. Existing analysis of the noisy power method shows an
unsatisfactory dependency over the "consecutive" spectral gap
$(\sigma_k-\sigma_{k+1})$ of an input data matrix, which could be very small
and hence limits the algorithm's applicability. In this paper, we present a new
analysis of the noisy power method that achieves improved gap dependency for
both sample complexity and noise tolerance bounds. More specifically, we
improve the dependency over $(\sigma_k-\sigma_{k+1})$ to dependency over
$(\sigma_k-\sigma_{q+1})$, where $q$ is an intermediate algorithm parameter and
could be much larger than the target rank $k$. Our proofs are built upon a
novel characterization of proximity between two subspaces that differ from
canonical angle characterizations analyzed in previous works. Finally, we apply
our improved bounds to distributed private PCA and memory-efficient streaming
PCA and obtain bounds that are superior to existing results in the literature.
Mobile Big Data Analytics Using Deep Learning and Apache Spark
Authors: Mohammad Abu Alsheikh, Dusit Niyato, Shaowei Lin, Hwee-Pink Tan, Zhu Han
Date: 2016-02-23 00:00:00
Tasks: Activity Recognition, Deep Learning

The proliferation of mobile devices, such as smartphones and Internet of
Things (IoT) gadgets, results in the recent mobile big data (MBD) era.
Collecting MBD is unprofitable unless suitable analytics and learning methods
are utilized for extracting meaningful information and hidden patterns from
data. This article presents an overview and brief tutorial of deep learning in
MBD analytics and discusses a scalable learning framework over Apache Spark.
Specifically, a distributed deep learning is executed as an iterative MapReduce
computing on many Spark workers. Each Spark worker learns a partial deep model
on a partition of the overall MBD, and a master deep model is then built by
averaging the parameters of all partial models. This Spark-based framework
speeds up the learning of deep models consisting of many hidden layers and
millions of parameters. We use a context-aware activity recognition application
with a real-world dataset containing millions of samples to validate our
framework and assess its speedup effectiveness.
Latent Skill Embedding for Personalized Lesson Sequence Recommendation
Authors: Siddharth Reddy, Igor Labutov, Thorsten Joachims
Date: 2016-02-23 00:00:00
Tasks: Collaborative Filtering, Recommendation Systems

Students in online courses generate large amounts of data that can be used to
personalize the learning process and improve quality of education. In this
paper, we present the Latent Skill Embedding (LSE), a probabilistic model of
students and educational content that can be used to recommend personalized
sequences of lessons with the goal of helping students prepare for specific
assessments. Akin to collaborative filtering for recommender systems, the
algorithm does not require students or content to be described by features, but
it learns a representation using access traces. We formulate this problem as a
regularized maximum-likelihood embedding of students, lessons, and assessments
from historical student-content interactions. An empirical evaluation on
large-scale data from Knewton, an adaptive learning technology company, shows
that this approach predicts assessment results competitively with benchmark
models and is able to discriminate between lesson sequences that lead to
mastery and failure.
Maximum margin classifier working in a set of strings
Authors: Hitoshi Koyano, Morihiro Hayashida, Tatsuya Akutsu
Date: 2014-06-03 00:00:00

Numbers and numerical vectors account for a large portion of data. However,
recently the amount of string data generated has increased dramatically.
Consequently, classifying string data is a common problem in many fields. The
most widely used approach to this problem is to convert strings into numerical
vectors using string kernels and subsequently apply a support vector machine
that works in a numerical vector space. However, this non-one-to-one conversion
involves a loss of information and makes it impossible to evaluate, using
probability theory, the generalization error of a learning machine, considering
that the given data to train and test the machine are strings generated
according to probability laws. In this study, we approach this classification
problem by constructing a classifier that works in a set of strings. To
evaluate the generalization error of such a classifier theoretically,
probability theory for strings is required. Therefore, we first extend a limit
theorem on the asymptotic behavior of a consensus sequence of strings, which is
the counterpart of the mean of numerical vectors, as demonstrated in the
probability theory on a metric space of strings developed by one of the authors
and his colleague in a previous study [18]. Using the obtained result, we then
demonstrate that our learning machine classifies strings in an asymptotically
optimal manner. Furthermore, we demonstrate the usefulness of our machine in
practical data analysis by applying it to predicting protein--protein
interactions using amino acid sequences.
A survey of sparse representation: algorithms and applications
Authors: Zheng Zhang, Yong Xu, Jian Yang, Xuelong. Li, David Zhang
Date: 2016-02-23 00:00:00
Tasks: Survey

Sparse representation has attracted much attention from researchers in fields
of signal processing, image processing, computer vision and pattern
recognition. Sparse representation also has a good reputation in both
theoretical research and practical applications. Many different algorithms have
been proposed for sparse representation. The main purpose of this article is to
provide a comprehensive study and an updated review on sparse representation
and to supply a guidance for researchers. The taxonomy of sparse representation
methods can be studied from various viewpoints. For example, in terms of
different norm minimizations used in sparsity constraints, the methods can be
roughly categorized into five groups: sparse representation with $l_0$-norm
minimization, sparse representation with $l_p$-norm (0$<$p$<$1) minimization,
sparse representation with $l_1$-norm minimization and sparse representation
with $l_{2,1}$-norm minimization. In this paper, a comprehensive overview of
sparse representation is provided. The available sparse representation
algorithms can also be empirically categorized into four groups: greedy
strategy approximation, constrained optimization, proximity algorithm-based
optimization, and homotopy algorithm-based sparse representation. The
rationales of different algorithms in each category are analyzed and a wide
range of sparse representation applications are summarized, which could
sufficiently reveal the potential nature of the sparse representation theory.
Specifically, an experimentally comparative study of these sparse
representation algorithms was presented. The Matlab code used in this paper can
be available at: http://www.yongxu.org/lunwen.html.