pwc-archive/papers-with-abstracts huggingface dataset:
Contextual Bandits with Similarity Information
Authors: Aleksandrs Slivkins
Date: 2009-07-23 00:00:00
Tasks: Multi-Armed Bandits

In a multi-armed bandit (MAB) problem, an online algorithm makes a sequence
of choices. In each round it chooses from a time-invariant set of alternatives
and receives the payoff associated with this alternative. While the case of
small strategy sets is by now well-understood, a lot of recent work has focused
on MAB problems with exponentially or infinitely large strategy sets, where one
needs to assume extra structure in order to make the problem tractable. In
particular, recent literature considered information on similarity between
arms.
  We consider similarity information in the setting of "contextual bandits", a
natural extension of the basic MAB problem where before each round an algorithm
is given the "context" -- a hint about the payoffs in this round. Contextual
bandits are directly motivated by placing advertisements on webpages, one of
the crucial problems in sponsored search. A particularly simple way to
represent similarity information in the contextual bandit setting is via a
"similarity distance" between the context-arm pairs which gives an upper bound
on the difference between the respective expected payoffs.
  Prior work on contextual bandits with similarity uses "uniform" partitions of
the similarity space, which is potentially wasteful. We design more efficient
algorithms that are based on adaptive partitions adjusted to "popular" context
and "high-payoff" arms.
Bayesian estimation of possible causal direction in the presence of latent confounders using a linear non-Gaussian acyclic structural equation model with individual-specific effects
Authors: Shohei Shimizu, Kenneth Bollen
Date: 2013-10-24 00:00:00

We consider learning the possible causal direction of two observed variables
in the presence of latent confounding variables. Several existing methods have
been shown to consistently estimate causal direction assuming linear or some
type of nonlinear relationship and no latent confounders. However, the
estimation results could be distorted if either assumption is actually
violated. In this paper, we first propose a new linear non-Gaussian acyclic
structural equation model with individual-specific effects that allows latent
confounders to be considered. We then propose an empirical Bayesian approach
for estimating possible causal direction using the new model. We demonstrate
the effectiveness of our method using artificial and real-world data.
Fighting Authorship Linkability with Crowdsourcing
Authors: Mishari Almishari, Ekin Oguz, Gene Tsudik
Date: 2014-05-19 00:00:00
Tasks: Machine Translation, Translation

Massive amounts of contributed content -- including traditional literature,
blogs, music, videos, reviews and tweets -- are available on the Internet
today, with authors numbering in many millions. Textual information, such as
product or service reviews, is an important and increasingly popular type of
content that is being used as a foundation of many trendy community-based
reviewing sites, such as TripAdvisor and Yelp. Some recent results have shown
that, due partly to their specialized/topical nature, sets of reviews authored
by the same person are readily linkable based on simple stylometric features.
In practice, this means that individuals who author more than a few reviews
under different accounts (whether within one site or across multiple sites) can
be linked, which represents a significant loss of privacy.
  In this paper, we start by showing that the problem is actually worse than
previously believed. We then explore ways to mitigate authorship linkability in
community-based reviewing. We first attempt to harness the global power of
crowdsourcing by engaging random strangers into the process of re-writing
reviews. As our empirical results (obtained from Amazon Mechanical Turk)
clearly demonstrate, crowdsourcing yields impressively sensible reviews that
reflect sufficiently different stylometric characteristics such that prior
stylometric linkability techniques become largely ineffective. We also consider
using machine translation to automatically re-write reviews. Contrary to what
was previously believed, our results show that translation decreases authorship
linkability as the number of intermediate languages grows. Finally, we explore
the combination of crowdsourcing and machine translation and report on the
results.
Inference in High Dimensions with the Penalized Score Test
Authors: Arend Voorman, Ali Shojaie, Daniela Witten
Date: 2014-01-12 00:00:00
Tasks: regression, Variable Selection, Vocal Bursts Intensity Prediction

In recent years, there has been considerable theoretical development
regarding variable selection consistency of penalized regression techniques,
such as the lasso. However, there has been relatively little work on
quantifying the uncertainty in these selection procedures. In this paper, we
propose a new method for inference in high dimensions using a score test based
on penalized regression. In this test, we perform penalized regression of an
outcome on all but a single feature, and test for correlation of the residuals
with the held-out feature. This procedure is applied to each feature in turn.
Interestingly, when an $\ell_1$ penalty is used, the sparsity pattern of the
lasso corresponds exactly to a decision based on the proposed test. Further,
when an $\ell_2$ penalty is used, the test corresponds precisely to a score
test in a mixed effects model, in which the effects of all but one feature are
assumed to be random. We formulate the hypothesis being tested as a compromise
between the null hypotheses tested in simple linear regression on each feature
and in multiple linear regression on all features, and develop reference
distributions for some well-known penalties. We also examine the behavior of
the test on real and simulated data.
Online Stochastic Optimization under Correlated Bandit Feedback
Authors: Mohammad Gheshlaghi Azar, Alessandro Lazaric, Emma Brunskill
Date: 2014-02-04 00:00:00
Tasks: Reinforcement Learning, Stochastic Optimization

In this paper we consider the problem of online stochastic optimization of a
locally smooth function under bandit feedback. We introduce the high-confidence
tree (HCT) algorithm, a novel any-time $\mathcal{X}$-armed bandit algorithm,
and derive regret bounds matching the performance of existing state-of-the-art
in terms of dependency on number of steps and smoothness factor. The main
advantage of HCT is that it handles the challenging case of correlated rewards,
whereas existing methods require that the reward-generating process of each arm
is an identically and independent distributed (iid) random process. HCT also
improves on the state-of-the-art in terms of its memory requirement as well as
requiring a weaker smoothness assumption on the mean-reward function in compare
to the previous anytime algorithms. Finally, we discuss how HCT can be applied
to the problem of policy search in reinforcement learning and we report
preliminary empirical results.
Scalable Semidefinite Relaxation for Maximum A Posterior Estimation
Authors: Qixing Huang, Yuxin Chen, Leonidas Guibas
Date: 2014-05-19 00:00:00

Maximum a posteriori (MAP) inference over discrete Markov random fields is a
fundamental task spanning a wide spectrum of real-world applications, which is
known to be NP-hard for general graphs. In this paper, we propose a novel
semidefinite relaxation formulation (referred to as SDR) to estimate the MAP
assignment. Algorithmically, we develop an accelerated variant of the
alternating direction method of multipliers (referred to as SDPAD-LR) that can
effectively exploit the special structure of the new relaxation. Encouragingly,
the proposed procedure allows solving SDR for large-scale problems, e.g.,
problems on a grid graph comprising hundreds of thousands of variables with
multiple states per node. Compared with prior SDP solvers, SDPAD-LR is capable
of attaining comparable accuracy while exhibiting remarkably improved
scalability, in contrast to the commonly held belief that semidefinite
relaxation can only been applied on small-scale MRF problems. We have evaluated
the performance of SDR on various benchmark datasets including OPENGM2 and PIC
in terms of both the quality of the solutions and computation time.
Experimental results demonstrate that for a broad class of problems, SDPAD-LR
outperforms state-of-the-art algorithms in producing better MAP assignment in
an efficient manner.
Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms
Authors: Stefan Magureanu, Richard Combes, Alexandre Proutiere
Date: 2014-05-19 00:00:00
Tasks: Multi-Armed Bandits

We consider stochastic multi-armed bandit problems where the expected reward
is a Lipschitz function of the arm, and where the set of arms is either
discrete or continuous. For discrete Lipschitz bandits, we derive asymptotic
problem specific lower bounds for the regret satisfied by any algorithm, and
propose OSLB and CKL-UCB, two algorithms that efficiently exploit the Lipschitz
structure of the problem. In fact, we prove that OSLB is asymptotically
optimal, as its asymptotic regret matches the lower bound. The regret analysis
of our algorithms relies on a new concentration inequality for weighted sums of
KL divergences between the empirical distributions of rewards and their true
distributions. For continuous Lipschitz bandits, we propose to first discretize
the action space, and then apply OSLB or CKL-UCB, algorithms that provably
exploit the structure efficiently. This approach is shown, through numerical
experiments, to significantly outperform existing algorithms that directly deal
with the continuous set of arms. Finally the results and algorithms are
extended to contextual bandits with similarities.
Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians
Authors: Constantinos Daskalakis, Gautam Kamath
Date: 2013-12-04 00:00:00

We provide an algorithm for properly learning mixtures of two
single-dimensional Gaussians without any separability assumptions. Given
$\tilde{O}(1/\varepsilon^2)$ samples from an unknown mixture, our algorithm
outputs a mixture that is $\varepsilon$-close in total variation distance, in
time $\tilde{O}(1/\varepsilon^5)$. Our sample complexity is optimal up to
logarithmic factors, and significantly improves upon both Kalai et al., whose
algorithm has a prohibitive dependence on $1/\varepsilon$, and Feldman et al.,
whose algorithm requires bounds on the mixture parameters and depends
pseudo-polynomially in these parameters.
  One of our main contributions is an improved and generalized algorithm for
selecting a good candidate distribution from among competing hypotheses.
Namely, given a collection of $N$ hypotheses containing at least one candidate
that is $\varepsilon$-close to an unknown distribution, our algorithm outputs a
candidate which is $O(\varepsilon)$-close to the distribution. The algorithm
requires ${O}(\log{N}/\varepsilon^2)$ samples from the unknown distribution and
${O}(N \log N/\varepsilon^2)$ time, which improves previous such results (such
as the Scheff\'e estimator) from a quadratic dependence of the running time on
$N$ to quasilinear. Given the wide use of such results for the purpose of
hypothesis selection, our improved algorithm implies immediate improvements to
any such use.
Vesselness via Multiple Scale Orientation Scores
Authors: Julius Hannink, Remco Duits, Erik Bekkers
Date: 2014-02-20 00:00:00

The multi-scale Frangi vesselness filter is an established tool in (retinal)
vascular imaging. However, it cannot cope with crossings or bifurcations, since
it only looks for elongated structures. Therefore, we disentangle crossing
structures in the image via (multiple scale) invertible orientation scores. The
described vesselness filter via scale-orientation scores performs considerably
better at enhancing vessels throughout crossings and bifurcations than the
Frangi version. Both methods are evaluated on a public dataset. Performance is
measured by comparing ground truth data to the segmentation results obtained by
basic thresholding and morphological component analysis of the filtered images.
Modelling Data Dispersion Degree in Automatic Robust Estimation for Multivariate Gaussian Mixture Models with an Application to Noisy Speech Processing
Authors: Dalei Wu, Haiqing Wu
Date: 2014-05-19 00:00:00
Tasks: Speaker Recognition

The trimming scheme with a prefixed cutoff portion is known as a method of
improving the robustness of statistical models such as multivariate Gaussian
mixture models (MG- MMs) in small scale tests by alleviating the impacts of
outliers. However, when this method is applied to real- world data, such as
noisy speech processing, it is hard to know the optimal cut-off portion to
remove the outliers and sometimes removes useful data samples as well. In this
paper, we propose a new method based on measuring the dispersion degree (DD) of
the training data to avoid this problem, so as to realise automatic robust
estimation for MGMMs. The DD model is studied by using two different measures.
For each one, we theoretically prove that the DD of the data samples in a
context of MGMMs approximately obeys a specific (chi or chi-square)
distribution. The proposed method is evaluated on a real-world application with
a moderately-sized speaker recognition task. Experiments show that the proposed
method can significantly improve the robustness of the conventional training
method of GMMs for speaker recognition.
Multi-borders classification
Authors: Peter Mills
Date: 2014-04-15 00:00:00
Tasks: Binary Classification, Classification, General Classification, Multi-class Classification

The number of possible methods of generalizing binary classification to
multi-class classification increases exponentially with the number of class
labels. Often, the best method of doing so will be highly problem dependent.
Here we present classification software in which the partitioning of
multi-class classification problems into binary classification problems is
specified using a recursive control language.
ESSP: An Efficient Approach to Minimizing Dense and Nonsubmodular Energy Functions
Authors: Wei Feng, Jiaya Jia, Zhi-Qiang Liu
Date: 2014-05-19 00:00:00

Many recent advances in computer vision have demonstrated the impressive
power of dense and nonsubmodular energy functions in solving visual labeling
problems. However, minimizing such energies is challenging. None of existing
techniques (such as s-t graph cut, QPBO, BP and TRW-S) can individually do this
well. In this paper, we present an efficient method, namely ESSP, to optimize
binary MRFs with arbitrary pairwise potentials, which could be nonsubmodular
and with dense connectivity. We also provide a comparative study of our
approach and several recent promising methods. From our study, we make some
reasonable recommendations of combining existing methods that perform the best
in different situations for this challenging problem. Experimental results
validate that for dense and nonsubmodular energy functions, the proposed
approach can usually obtain lower energies than the best combination of other
techniques using comparably reasonable time.
Kronecker PCA Based Spatio-Temporal Modeling of Video for Dismount Classification
Authors: Kristjan H. Greenewald, Alfred O. Hero III
Date: 2014-05-19 00:00:00
Tasks: Classification, Dimensionality Reduction, Gender Classification, General Classification

We consider the application of KronPCA spatio-temporal modeling techniques
[Greenewald et al 2013, Tsiligkaridis et al 2013] to the extraction of
spatiotemporal features for video dismount classification. KronPCA performs a
low-rank type of dimensionality reduction that is adapted to spatio-temporal
data and is characterized by the T frame multiframe mean and covariance of p
spatial features. For further regularization and improved inverse estimation,
we also use the diagonally corrected KronPCA shrinkage methods we presented in
[Greenewald et al 2013]. We apply this very general method to the modeling of
the multivariate temporal behavior of HOG features extracted from pedestrian
bounding boxes in video, with gender classification in a challenging dataset
chosen as a specific application. The learned covariances for each class are
used to extract spatiotemporal features which are then classified, achieving
competitive classification performance.
A Distributed Algorithm for Training Nonlinear Kernel Machines
Authors: Dhruv Mahajan, S. Sathiya Keerthi, S. Sundararajan
Date: 2014-05-18 00:00:00

This paper concerns the distributed training of nonlinear kernel machines on
Map-Reduce. We show that a re-formulation of Nystr\"om approximation based
solution which is solved using gradient based techniques is well suited for
this, especially when it is necessary to work with a large number of basis
points. The main advantages of this approach are: avoidance of computing the
pseudo-inverse of the kernel sub-matrix corresponding to the basis points;
simplicity and efficiency of the distributed part of the computations; and,
friendliness to stage-wise addition of basis points. We implement the method
using an AllReduce tree on Hadoop and demonstrate its value on a few large
benchmark datasets.
A Memetic Algorithm for the Linear Ordering Problem with Cumulative Costs
Authors: Tao Ye, Kan Zhou, Zhipeng Lu, Jin-Kao Hao
Date: 2014-05-18 00:00:00

This paper introduces an effective memetic algorithm for the linear ordering
problem with cumulative costs. The proposed algorithm combines an order-based
recombination operator with an improved forward-backward local search procedure
and employs a solution quality based replacement criterion for pool updating.
Extensive experiments on 118 well-known benchmark instances show that the
proposed algorithm achieves competitive results by identifying 46 new upper
bounds. Furthermore, some critical ingredients of our algorithm are analyzed to
understand the source of its performance.
A Multi-parent Memetic Algorithm for the Linear Ordering Problem
Authors: Tao Ye, Tao Wang, Zhipeng Lu, Jin-Kao Hao
Date: 2014-05-18 00:00:00

In this paper, we present a multi-parent memetic algorithm (denoted by MPM)
for solving the classic Linear Ordering Problem (LOP). The MPM algorithm
integrates in particular a multi-parent recombination operator for generating
offspring solutions and a distance-and-quality based criterion for pool
updating. Our MPM algorithm is assessed on 8 sets of 484 widely used LOP
instances and compared with several state-of-the-art algorithms in the
literature, showing the efficacy of the MPM algorithm. Specifically, for the
255 instances whose optimal solutions are unknown, the MPM is able to detect
better solutions than the previous best-known ones for 66 instances, while
matching the previous best-known results for 163 instances. Furthermore, some
additional experiments are carried out to analyze the key elements and
important parameters of MPM.
Bag of Visual Words and Fusion Methods for Action Recognition: Comprehensive Study and Good Practice
Authors: Xiaojiang Peng, Li-Min Wang, Xingxing Wang, Yu Qiao
Date: 2014-05-18 00:00:00
Tasks: Action Recognition, Action Recognition In Videos, Temporal Action Localization

Video based action recognition is one of the important and challenging
problems in computer vision research. Bag of Visual Words model (BoVW) with
local features has become the most popular method and obtained the
state-of-the-art performance on several realistic datasets, such as the HMDB51,
UCF50, and UCF101. BoVW is a general pipeline to construct a global
representation from a set of local features, which is mainly composed of five
steps: (i) feature extraction, (ii) feature pre-processing, (iii) codebook
generation, (iv) feature encoding, and (v) pooling and normalization. Many
efforts have been made in each step independently in different scenarios and
their effect on action recognition is still unknown. Meanwhile, video data
exhibits different views of visual pattern, such as static appearance and
motion dynamics. Multiple descriptors are usually extracted to represent these
different views. Many feature fusion methods have been developed in other areas
and their influence on action recognition has never been investigated before.
This paper aims to provide a comprehensive study of all steps in BoVW and
different fusion methods, and uncover some good practice to produce a
state-of-the-art action recognition system. Specifically, we explore two kinds
of local features, ten kinds of encoding methods, eight kinds of pooling and
normalization strategies, and three kinds of fusion methods. We conclude that
every step is crucial for contributing to the final recognition rate.
Furthermore, based on our comprehensive study, we propose a simple yet
effective representation, called hybrid representation, by exploring the
complementarity of different BoVW frameworks and local descriptors. Using this
representation, we obtain the state-of-the-art on the three challenging
datasets: HMDB51 (61.1%), UCF50 (92.3%), and UCF101 (87.9%).
Online Learning with Composite Loss Functions
Authors: Ofer Dekel, Jian Ding, Tomer Koren, Yuval Peres
Date: 2014-05-18 00:00:00

We study a new class of online learning problems where each of the online
algorithm's actions is assigned an adversarial value, and the loss of the
algorithm at each step is a known and deterministic function of the values
assigned to its recent actions. This class includes problems where the
algorithm's loss is the minimum over the recent adversarial values, the maximum
over the recent values, or a linear combination of the recent values. We
analyze the minimax regret of this class of problems when the algorithm
receives bandit feedback, and prove that when the minimum or maximum functions
are used, the minimax regret is $\tilde \Omega(T^{2/3})$ (so called hard online
learning problems), and when a linear function is used, the minimax regret is
$\tilde O(\sqrt{T})$ (so called easy learning problems). Previously, the only
online learning problem that was known to be provably hard was the multi-armed
bandit with switching costs.
Multi-layered graph-based multi-document summarization model
Authors: Ercan Canhasi
Date: 2014-05-17 00:00:00
Tasks: Document Summarization, Extractive Document Summarization, Extractive Text Summarization, model, Multi-Document Summarization, Sentence, Sentence Similarity

Multi-document summarization is a process of automatic generation of a
compressed version of the given collection of documents. Recently, the
graph-based models and ranking algorithms have been actively investigated by
the extractive document summarization community. While most work to date
focuses on homogeneous connecteness of sentences and heterogeneous connecteness
of documents and sentences (e.g. sentence similarity weighted by document
importance), in this paper we present a novel 3-layered graph model that
emphasizes not only sentence and document level relations but also the
influence of under sentence level relations (e.g. a part of sentence
similarity).
Preliminary Report on the Structure of Croatian Linguistic Co-occurrence Networks
Authors: Domagoj Margan, Sanda Martinčić-Ipšić, Ana Meštrović
Date: 2014-05-17 00:00:00
Tasks: Clustering

In this article, we investigate the structure of Croatian linguistic
co-occurrence networks. We examine the change of network structure properties
by systematically varying the co-occurrence window sizes, the corpus sizes and
removing stopwords. In a co-occurrence window of size $n$ we establish a link
between the current word and $n-1$ subsequent words. The results point out that
the increase of the co-occurrence window size is followed by a decrease in
diameter, average path shortening and expectedly condensing the average
clustering coefficient. The same can be noticed for the removal of the
stopwords. Finally, since the size of texts is reflected in the network
properties, our results suggest that the corpus influence can be reduced by
increasing the co-occurrence window size.