pwc-archive/papers-with-abstracts huggingface dataset:
A description length approach to determining the number of k-means clusters
Authors: Hiromitsu Mizutani, Ryota Kanai
Date: 2017-02-28 00:00:00
Tasks: Clustering, Data Compression, Dimensionality Reduction

We present an asymptotic criterion to determine the optimal number of
clusters in k-means. We consider k-means as data compression, and propose to
adopt the number of clusters that minimizes the estimated description length
after compression. Here we report two types of compression ratio based on two
ways to quantify the description length of data after compression. This
approach further offers a way to evaluate whether clusters obtained with
k-means have a hierarchical structure by examining whether multi-stage
compression can further reduce the description length. We applied our criteria
to determine the number of clusters to synthetic data and empirical
neuroimaging data to observe the behavior of the criteria across different
types of data set and suitability of the two types of criteria for different
datasets. We found that our method can offer reasonable clustering results that
are useful for dimension reduction. While our numerical results revealed
dependency of our criteria on the various aspects of dataset such as the
dimensionality, the description length approach proposed here provides a useful
guidance to determine the number of clusters in a principled manner when
underlying properties of the data are unknown and only inferred from
observation of data.
Hashing in the Zero Shot Framework with Domain Adaptation
Authors: Shubham Pachori, Ameya Deshpande, Shanmuganathan Raman
Date: 2017-02-07 00:00:00
Tasks: Domain Adaptation, Image Retrieval, Quantization, Retrieval, Unsupervised Domain Adaptation

Techniques to learn hash codes which can store and retrieve large dimensional
multimedia data efficiently have attracted broad research interests in the
recent years. With rapid explosion of newly emerged concepts and online data,
existing supervised hashing algorithms suffer from the problem of scarcity of
ground truth annotations due to the high cost of obtaining manual annotations.
Therefore, we propose an algorithm to learn a hash function from training
images belonging to `seen' classes which can efficiently encode images of
`unseen' classes to binary codes. Specifically, we project the image features
from visual space and semantic features from semantic space into a common
Hamming subspace. Earlier works to generate hash codes have tried to relax the
discrete constraints on hash codes and solve the continuous optimization
problem. However, it often leads to quantization errors. In this work, we use
the max-margin classifier to learn an efficient hash function. To address the
concern of domain-shift which may arise due to the introduction of new classes,
we also introduce an unsupervised domain adaptation model in the proposed
hashing framework. Results on the three datasets show the advantage of using
domain adaptation in learning a high-quality hash function and superiority of
our method for the task of image retrieval performance as compared to several
state-of-the-art hashing methods.
Lipschitz Optimisation for Lipschitz Interpolation
Authors: Jan-Peter Calliess
Date: 2017-02-28 00:00:00
Tasks: Prediction

Techniques known as Nonlinear Set Membership prediction, Kinky Inference or
Lipschitz Interpolation are fast and numerically robust approaches to
nonparametric machine learning that have been proposed to be utilised in the
context of system identification and learning-based control. They utilise
presupposed Lipschitz properties in order to compute inferences over unobserved
function values. Unfortunately, most of these approaches rely on exact
knowledge about the input space metric as well as about the Lipschitz constant.
Furthermore, existing techniques to estimate the Lipschitz constants from the
data are not robust to noise or seem to be ad-hoc and typically are decoupled
from the ultimate learning and prediction task. To overcome these limitations,
we propose an approach for optimising parameters of the presupposed metrics by
minimising validation set prediction errors. To avoid poor performance due to
local minima, we propose to utilise Lipschitz properties of the optimisation
objective to ensure global optimisation success. The resulting approach is a
new flexible method for nonparametric black-box learning. We provide
experimental evidence of the competitiveness of our approach on artificial as
well as on real data.
On the Interpretability of Conditional Probability Estimates in the Agnostic Setting
Authors: Yihan Gao, Aditya Parameswaran, Jian Peng
Date: 2015-06-09 00:00:00
Tasks: Binary Classification, General Classification

We study the interpretability of conditional probability estimates for binary
classification under the agnostic setting or scenario. Under the agnostic
setting, conditional probability estimates do not necessarily reflect the true
conditional probabilities. Instead, they have a certain calibration property:
among all data points that the classifier has predicted P(Y = 1|X) = p, p
portion of them actually have label Y = 1. For cost-sensitive decision
problems, this calibration property provides adequate support for us to use
Bayes Decision Theory. In this paper, we define a novel measure for the
calibration property together with its empirical counterpart, and prove an
uniform convergence result between them. This new measure enables us to
formally justify the calibration property of conditional probability
estimations, and provides new insights on the problem of estimating and
calibrating conditional probabilities.
Low-rank Label Propagation for Semi-supervised Learning with 100 Millions Samples
Authors: Raphael Petegrosso, Wei zhang, Zhuliu Li, Yousef Saad, Rui Kuang
Date: 2017-02-28 00:00:00

The success of semi-supervised learning crucially relies on the scalability
to a huge amount of unlabelled data that are needed to capture the underlying
manifold structure for better classification. Since computing the pairwise
similarity between the training data is prohibitively expensive in most kinds
of input data, currently, there is no general ready-to-use semi-supervised
learning method/tool available for learning with tens of millions or more data
points. In this paper, we adopted the idea of two low-rank label propagation
algorithms, GLNP (Global Linear Neighborhood Propagation) and Kernel Nystr\"om
Approximation, and implemented the parallelized version of the two algorithms
accelerated with Nesterov's accelerated projected gradient descent for Big-data
Label Propagation (BigLP).
  The parallel algorithms are tested on five real datasets ranging from 7000 to
10,000,000 in size and a simulation dataset of 100,000,000 samples. In the
experiments, the implementation can scale up to datasets with 100,000,000
samples and hundreds of features and the algorithms also significantly improved
the prediction accuracy when only a very small percentage of the data is
labeled. The results demonstrate that the BigLP implementation is highly
scalable to big data and effective in utilizing the unlabeled data for
semi-supervised learning.
Clipper: A Low-Latency Online Prediction Serving System
Authors: Daniel Crankshaw, Xin Wang, Giulio Zhou, Michael J. Franklin, Joseph E. Gonzalez, Ion Stoica
Date: 2016-12-09 00:00:00
Tasks: BIG-bench Machine Learning, Model Selection, Prediction

Machine learning is being deployed in a growing number of applications which
demand real-time, accurate, and robust predictions under heavy query load.
However, most machine learning frameworks and systems only address model
training and not deployment.
  In this paper, we introduce Clipper, a general-purpose low-latency prediction
serving system. Interposing between end-user applications and a wide range of
machine learning frameworks, Clipper introduces a modular architecture to
simplify model deployment across frameworks and applications. Furthermore, by
introducing caching, batching, and adaptive model selection techniques, Clipper
reduces prediction latency and improves prediction throughput, accuracy, and
robustness without modifying the underlying machine learning frameworks. We
evaluate Clipper on four common machine learning benchmark datasets and
demonstrate its ability to meet the latency, accuracy, and throughput demands
of online serving applications. Finally, we compare Clipper to the TensorFlow
Serving system and demonstrate that we are able to achieve comparable
throughput and latency while enabling model composition and online learning to
improve accuracy and render more robust predictions.
Neural Tree Indexers for Text Understanding
Authors: Tsendsuren Munkhdalai, Hong Yu
Date: 2016-07-15 00:00:00
Proceeding: EACL 2017 4
Tasks: Natural Language Inference, Sentence, Sentence Classification

Recurrent neural networks (RNNs) process input text sequentially and model
the conditional transition between word tokens. In contrast, the advantages of
recursive networks include that they explicitly model the compositionality and
the recursive structure of natural language. However, the current recursive
architecture is limited by its dependence on syntactic tree. In this paper, we
introduce a robust syntactic parsing-independent tree structured model, Neural
Tree Indexers (NTI) that provides a middle ground between the sequential RNNs
and the syntactic treebased recursive models. NTI constructs a full n-ary tree
by processing the input text with its node function in a bottom-up fashion.
Attention mechanism can then be applied to both structure and node function. We
implemented and evaluated a binarytree model of NTI, showing the model achieved
the state-of-the-art performance on three different NLP tasks: natural language
inference, answer sentence selection, and sentence classification,
outperforming state-of-the-art recurrent and recursive neural networks.
Reasoning with Memory Augmented Neural Networks for Language Comprehension
Authors: Tsendsuren Munkhdalai, Hong Yu
Date: 2016-10-20 00:00:00
Tasks: Reading Comprehension, Two-sample testing

Hypothesis testing is an important cognitive process that supports human
reasoning. In this paper, we introduce a computational hypothesis testing
approach based on memory augmented neural networks. Our approach involves a
hypothesis testing loop that reconsiders and progressively refines a previously
formed hypothesis in order to generate new hypotheses to test. We apply the
proposed approach to language comprehension task by using Neural Semantic
Encoders (NSE). Our NSE models achieve the state-of-the-art results showing an
absolute improvement of 1.2% to 2.6% accuracy over previous results obtained by
single and ensemble systems on standard machine comprehension benchmarks such
as the Children's Book Test (CBT) and Who-Did-What (WDW) news article datasets.
Proportional Representation in Vote Streams
Authors: Palash Dey, Nimrod Talmon, Otniel van Handel
Date: 2017-02-28 00:00:00

We consider elections where the voters come one at a time, in a streaming
fashion, and devise space-efficient algorithms which identify an approximate
winning committee with respect to common multiwinner proportional
representation voting rules; specifically, we consider the Approval-based and
the Borda-based variants of both the Chamberlin-- ourant rule and the Monroe
rule. We complement our algorithms with lower bounds. Somewhat surprisingly,
our results imply that, using space which does not depend on the number of
voters it is possible to efficiently identify an approximate representative
committee of fixed size over vote streams with huge number of voters.
Incremental Robot Learning of New Objects with Fixed Update Time
Authors: Raffaello Camoriano, Giulia Pasquale, Carlo Ciliberto, Lorenzo Natale, Lorenzo Rosasco, Giorgio Metta
Date: 2016-05-17 00:00:00
Tasks: Active Learning, General Classification, Lifelong learning, Object, Object Recognition

We consider object recognition in the context of lifelong learning, where a
robotic agent learns to discriminate between a growing number of object classes
as it accumulates experience about the environment. We propose an incremental
variant of the Regularized Least Squares for Classification (RLSC) algorithm,
and exploit its structure to seamlessly add new classes to the learned model.
The presented algorithm addresses the problem of having an unbalanced
proportion of training examples per class, which occurs when new objects are
presented to the system for the first time.
  We evaluate our algorithm on both a machine learning benchmark dataset and
two challenging object recognition tasks in a robotic setting. Empirical
evidence shows that our approach achieves comparable or higher classification
performance than its batch counterpart when classes are unbalanced, while being
significantly faster.
Frugal Bribery in Voting
Authors: Palash Dey, Neeldhara Misra, Y. Narahari
Date: 2015-04-30 00:00:00

Bribery in elections is an important problem in computational social choice
theory. However, bribery with money is often illegal in elections. Motivated by
this, we introduce the notion of frugal bribery and formulate two new pertinent
computational problems which we call Frugal-bribery and Frugal- $bribery to
capture bribery without money in elections. In the proposed model, the briber
is frugal in nature and this is captured by her inability to bribe votes of a
certain kind, namely, non-vulnerable votes. In the Frugal-bribery problem, the
goal is to make a certain candidate win the election by changing only
vulnerable votes. In the Frugal-{dollar}bribery problem, the vulnerable votes
have prices and the goal is to make a certain candidate win the election by
changing only vulnerable votes, subject to a budget constraint of the briber.
We further formulate two natural variants of the Frugal-{dollar}bribery problem
namely Uniform-frugal-{dollar}bribery and Nonuniform-frugal-{dollar}bribery
where the prices of the vulnerable votes are, respectively, all the same or
different.
  We study the computational complexity of the above problems for unweighted
and weighted elections for several commonly used voting rules. We observe that,
even if we have only a small number of candidates, the problems are intractable
for all voting rules studied here for weighted elections, with the sole
exception of the Frugal-bribery problem for the plurality voting rule. In
contrast, we have polynomial time algorithms for the Frugal-bribery problem for
plurality, veto, k-approval, k-veto, and plurality with runoff voting rules for
unweighted elections. However, the Frugal-{dollar}bribery problem is
intractable for all the voting rules studied here barring the plurality and the
veto voting rules for unweighted elections.
Estimation of Graphlet Statistics
Authors: Ryan A. Rossi, Rong Zhou, Nesreen K. Ahmed
Date: 2017-01-06 00:00:00

Graphlets are induced subgraphs of a large network and are important for
understanding and modeling complex networks. Despite their practical
importance, graphlets have been severely limited to applications and domains
with relatively small graphs. Most previous work has focused on exact
algorithms, however, it is often too expensive to compute graphlets exactly in
massive networks with billions of edges, and finding an approximate count is
usually sufficient for many applications. In this work, we propose an unbiased
graphlet estimation framework that is (a) fast with significant speedups
compared to the state-of-the-art, (b) parallel with nearly linear-speedups, (c)
accurate with <1% relative error, (d) scalable and space-efficient for massive
networks with billions of edges, and (e) flexible for a variety of real-world
settings, as well as estimating macro and micro-level graphlet statistics
(e.g., counts) of both connected and disconnected graphlets. In addition, an
adaptive approach is introduced that finds the smallest sample size required to
obtain estimates within a given user-defined error bound. On 300 networks from
20 domains, we obtain <1% relative error for all graphlets. This is
significantly more accurate than existing methods while using less data.
Moreover, it takes a few seconds on billion edge graphs (as opposed to
days/weeks). These are by far the largest graphlet computations to date.
Learning Deep Nearest Neighbor Representations Using Differentiable Boundary Trees
Authors: Daniel Zoran, Balaji Lakshminarayanan, Charles Blundell
Date: 2017-02-28 00:00:00
Tasks: Retrieval

Nearest neighbor (kNN) methods have been gaining popularity in recent years
in light of advances in hardware and efficiency of algorithms. There is a
plethora of methods to choose from today, each with their own advantages and
disadvantages. One requirement shared between all kNN based methods is the need
for a good representation and distance measure between samples.
  We introduce a new method called differentiable boundary tree which allows
for learning deep kNN representations. We build on the recently proposed
boundary tree algorithm which allows for efficient nearest neighbor
classification, regression and retrieval. By modelling traversals in the tree
as stochastic events, we are able to form a differentiable cost function which
is associated with the tree's predictions. Using a deep neural network to
transform the data and back-propagating through the tree allows us to learn
good representations for kNN methods.
  We demonstrate that our method is able to learn suitable representations
allowing for very efficient trees with a clearly interpretable structure.
QoS-Aware Multi-Armed Bandits
Authors: Lenz Belzner, Thomas Gabor
Date: 2017-02-28 00:00:00
Tasks: Decision Making, Multi-Armed Bandits, Thompson Sampling

Motivated by runtime verification of QoS requirements in self-adaptive and
self-organizing systems that are able to reconfigure their structure and
behavior in response to runtime data, we propose a QoS-aware variant of
Thompson sampling for multi-armed bandits. It is applicable in settings where
QoS satisfaction of an arm has to be ensured with high confidence efficiently,
rather than finding the optimal arm while minimizing regret. Preliminary
experimental results encourage further research in the field of QoS-aware
decision making.
Interactive Prior Elicitation of Feature Similarities for Small Sample Size Prediction
Authors: Homayun Afrabandpey, Tomi Peltola, Samuel Kaski
Date: 2016-12-08 00:00:00
Tasks: Prediction, regression

Regression under the "small $n$, large $p$" conditions, of small sample size
$n$ and large number of features $p$ in the learning data set, is a recurring
setting in which learning from data is difficult. With prior knowledge about
relationships of the features, $p$ can effectively be reduced, but explicating
such prior knowledge is difficult for experts. In this paper we introduce a new
method for eliciting expert prior knowledge about the similarity of the roles
of features in the prediction task. The key idea is to use an interactive
multidimensional-scaling (MDS) type scatterplot display of the features to
elicit the similarity relationships, and then use the elicited relationships in
the prior distribution of prediction parameters. Specifically, for learning to
predict a target variable with Bayesian linear regression, the feature
relationships are used to construct a Gaussian prior with a full covariance
matrix for the regression coefficients. Evaluation of our method in experiments
with simulated and real users on text data confirm that prior elicitation of
feature similarities improves prediction accuracy. Furthermore, elicitation
with an interactive scatterplot display outperforms straightforward elicitation
where the users choose feature pairs from a feature list.
Deep Nonparametric Estimation of Discrete Conditional Distributions via Smoothed Dyadic Partitioning
Authors: Wesley Tansey, Karl Pichotta, James G. Scott
Date: 2017-02-23 00:00:00

We present an approach to deep estimation of discrete conditional probability
distributions. Such models have several applications, including generative
modeling of audio, image, and video data. Our approach combines two main
techniques: dyadic partitioning and graph-based smoothing of the discrete
space. By recursively decomposing each dimension into a series of binary splits
and smoothing over the resulting distribution using graph-based trend
filtering, we impose a strict structure to the model and achieve much higher
sample efficiency. We demonstrate the advantages of our model through a series
of benchmarks on both synthetic and real-world datasets, in some cases reducing
the error by nearly half in comparison to other popular methods in the
literature. All of our models are implemented in Tensorflow and publicly
available at https://github.com/tansey/sdp .
Unsupervised Triplet Hashing for Fast Image Retrieval
Authors: Shanshan Huang, Yichao Xiong, Ya zhang, Jia Wang
Date: 2017-02-28 00:00:00
Tasks: Image Retrieval, Quantization, Retrieval, Triplet

Hashing has played a pivotal role in large-scale image retrieval. With the
development of Convolutional Neural Network (CNN), hashing learning has shown
great promise. But existing methods are mostly tuned for classification, which
are not optimized for retrieval tasks, especially for instance-level retrieval.
In this study, we propose a novel hashing method for large-scale image
retrieval. Considering the difficulty in obtaining labeled datasets for image
retrieval task in large scale, we propose a novel CNN-based unsupervised
hashing method, namely Unsupervised Triplet Hashing (UTH). The unsupervised
hashing network is designed under the following three principles: 1) more
discriminative representations for image retrieval; 2) minimum quantization
loss between the original real-valued feature descriptors and the learned hash
codes; 3) maximum information entropy for the learned hash codes. Extensive
experiments on CIFAR-10, MNIST and In-shop datasets have shown that UTH
outperforms several state-of-the-art unsupervised hashing methods in terms of
retrieval accuracy.
Discriminative Neural Topic Models
Authors: Gaurav Pandey, Ambedkar Dukkipati
Date: 2017-01-24 00:00:00
Tasks: GPU, Topic Models

We propose a neural network based approach for learning topics from text and
image datasets. The model makes no assumptions about the conditional
distribution of the observed features given the latent topics. This allows us
to perform topic modelling efficiently using sentences of documents and patches
of images as observed features, rather than limiting ourselves to words.
Moreover, the proposed approach is online, and hence can be used for streaming
data. Furthermore, since the approach utilizes neural networks, it can be
implemented on GPU with ease, and hence it is very scalable.
MILD: Multi-Index hashing for Loop closure Detection
Authors: Lei Han, Lu Fang
Date: 2017-02-28 00:00:00
Tasks: Loop Closure Detection

Loop Closure Detection (LCD) has been proved to be extremely useful in global
consistent visual Simultaneously Localization and Mapping (SLAM) and
appearance-based robot relocalization. Methods exploiting binary features in
bag of words representation have recently gained a lot of popularity for their
efficiency, but suffer from low recall due to the inherent drawback that high
dimensional binary feature descriptors lack well-defined centroids. In this
paper, we propose a realtime LCD approach called MILD (Multi-Index Hashing for
Loop closure Detection), in which image similarity is measured by feature
matching directly to achieve high recall without introducing extra
computational complexity with the aid of Multi-Index Hashing (MIH). A
theoretical analysis of the approximate image similarity measurement using MIH
is presented, which reveals the trade-off between efficiency and accuracy from
a probabilistic perspective. Extensive comparisons with state-of-the-art LCD
methods demonstrate the superiority of MILD in both efficiency and accuracy.