pwc-archive/papers-with-abstracts huggingface dataset:
Online Tracking by Learning Discriminative Saliency Map with Convolutional Neural Network
Authors: Seunghoon Hong, Tackgeun You, Suha Kwak, Bohyung Han
Date: 2015-02-24 00:00:00
Tasks: Visual Tracking

We propose an online visual tracking algorithm by learning discriminative
saliency map using Convolutional Neural Network (CNN). Given a CNN pre-trained
on a large-scale image repository in offline, our algorithm takes outputs from
hidden layers of the network as feature descriptors since they show excellent
representation performance in various general visual recognition problems. The
features are used to learn discriminative target appearance models using an
online Support Vector Machine (SVM). In addition, we construct target-specific
saliency map by backpropagating CNN features with guidance of the SVM, and
obtain the final tracking result in each frame based on the appearance model
generatively constructed with the saliency map. Since the saliency map
visualizes spatial configuration of target effectively, it improves target
localization accuracy and enable us to achieve pixel-level target segmentation.
We verify the effectiveness of our tracking algorithm through extensive
experiment on a challenging benchmark, where our method illustrates outstanding
performance compared to the state-of-the-art tracking algorithms.
Using Riemannian geometry for SSVEP-based Brain Computer Interface
Authors: Emmanuel K. Kalunga, Sylvain Chevallier, Quentin Barthelemy
Date: 2015-01-14 00:00:00
Tasks: Brain Computer Interface, EEG, Electroencephalogram (EEG), SSVEP

Riemannian geometry has been applied to Brain Computer Interface (BCI) for
brain signals classification yielding promising results. Studying
electroencephalographic (EEG) signals from their associated covariance matrices
allows a mitigation of common sources of variability (electronic, electrical,
biological) by constructing a representation which is invariant to these
perturbations. While working in Euclidean space with covariance matrices is
known to be error-prone, one might take advantage of algorithmic advances in
information geometry and matrix manifold to implement methods for Symmetric
Positive-Definite (SPD) matrices. This paper proposes a comprehensive review of
the actual tools of information geometry and how they could be applied on
covariance matrices of EEG. In practice, covariance matrices should be
estimated, thus a thorough study of all estimators is conducted on real EEG
dataset. As a main contribution, this paper proposes an online implementation
of a classifier in the Riemannian space and its subsequent assessment in
Steady-State Visually Evoked Potential (SSVEP) experimentations.
On the Complexity of A/B Testing
Authors: Emilie Kaufmann, Olivier Cappé, Aurélien Garivier
Date: 2014-05-13 00:00:00

A/B testing refers to the task of determining the best option among two
alternatives that yield random outcomes. We provide distribution-dependent
lower bounds for the performance of A/B testing that improve over the results
currently available both in the fixed-confidence (or delta-PAC) and
fixed-budget settings. When the distribution of the outcomes are Gaussian, we
prove that the complexity of the fixed-confidence and fixed-budget settings are
equivalent, and that uniform sampling of both alternatives is optimal only in
the case of equal variances. In the common variance case, we also provide a
stopping rule that terminates faster than existing fixed-confidence algorithms.
In the case of Bernoulli distributions, we show that the complexity of
fixed-budget setting is smaller than that of fixed-confidence setting and that
uniform sampling of both alternatives -though not optimal- is advisable in
practice when combined with an appropriate stopping criterion.
Discrete Wavelet Transform and Gradient Difference based approach for text localization in videos
Authors: B. H. Shekar, Smitha M. L., P. Shivakumara
Date: 2015-02-24 00:00:00
Tasks: Retrieval, Text Detection, Video Retrieval

The text detection and localization is important for video analysis and
understanding. The scene text in video contains semantic information and thus
can contribute significantly to video retrieval and understanding. However,
most of the approaches detect scene text in still images or single video frame.
Videos differ from images in temporal redundancy. This paper proposes a novel
hybrid method to robustly localize the texts in natural scene images and videos
based on fusion of discrete wavelet transform and gradient difference. A set of
rules and geometric properties have been devised to localize the actual text
regions. Then, morphological operation is performed to generate the text
regions and finally the connected component analysis is employed to localize
the text in a video frame. The experimental results obtained on publicly
available standard ICDAR 2003 and Hua dataset illustrate that the proposed
method can accurately detect and localize texts of various sizes, fonts and
colors. The experimentation on huge collection of video databases reveal the
suitability of the proposed method to video databases.
1-Bit Matrix Completion under Exact Low-Rank Constraint
Authors: Sonia Bhaskar, Adel Javanmard
Date: 2015-02-24 00:00:00
Tasks: Matrix Completion

We consider the problem of noisy 1-bit matrix completion under an exact rank
constraint on the true underlying matrix $M^*$. Instead of observing a subset
of the noisy continuous-valued entries of a matrix $M^*$, we observe a subset
of noisy 1-bit (or binary) measurements generated according to a probabilistic
model. We consider constrained maximum likelihood estimation of $M^*$, under a
constraint on the entry-wise infinity-norm of $M^*$ and an exact rank
constraint. This is in contrast to previous work which has used convex
relaxations for the rank. We provide an upper bound on the matrix estimation
error under this model. Compared to the existing results, our bound has faster
convergence rate with matrix dimensions when the fraction of revealed 1-bit
observations is fixed, independent of the matrix dimensions. We also propose an
iterative algorithm for solving our nonconvex optimization with a certificate
of global optimality of the limiting point. This algorithm is based on low rank
factorization of $M^*$. We validate the method on synthetic and real data with
improved performance over existing methods.
Transformation of basic probability assignments to probabilities based on a new entropy measure
Authors: Xinyang Deng, Yong Deng
Date: 2015-02-24 00:00:00
Tasks: Decision Making

Dempster-Shafer evidence theory is an efficient mathematical tool to deal
with uncertain information. In that theory, basic probability assignment (BPA)
is the basic element for the expression and inference of uncertainty.
Decision-making based on BPA is still an open issue in Dempster-Shafer evidence
theory. In this paper, a novel approach of transforming basic probability
assignments to probabilities is proposed based on Deng entropy which is a new
measure for the uncertainty of BPA. The principle of the proposed method is to
minimize the difference of uncertainties involving in the given BPA and
obtained probability distribution. Numerical examples are given to show the
proposed approach.
User Clustering in Online Advertising via Topic Models
Authors: Sahin Cem Geyik, Ali Dasdan, Kuang-Chih Lee
Date: 2015-01-26 00:00:00
Tasks: Clustering, Topic Models, valid

In the domain of online advertising, our aim is to serve the best ad to a
user who visits a certain webpage, to maximize the chance of a desired action
to be performed by this user after seeing the ad. While it is possible to
generate a different prediction model for each user to tell if he/she will act
on a given ad, the prediction result typically will be quite unreliable with
huge variance, since the desired actions are extremely sparse, and the set of
users is huge (hundreds of millions) and extremely volatile, i.e., a lot of new
users are introduced everyday, or are no longer valid. In this paper we aim to
improve the accuracy in finding users who will perform the desired action, by
assigning each user to a cluster, where the number of clusters is much smaller
than the number of users (in the order of hundreds). Each user will fall into
the same cluster with another user if their event history are similar. For this
purpose, we modify the probabilistic latent semantic analysis (pLSA) model by
assuming the independence of the user and the cluster id, given the history of
events. This assumption helps us to identify a cluster of a new user without
re-clustering all the users. We present the details of the algorithm we
employed as well as the distributed implementation on Hadoop, and some initial
results on the clusters that were generated by the algorithm.
Learning Fast-Mixing Models for Structured Prediction
Authors: Jacob Steinhardt, Percy Liang
Date: 2015-02-24 00:00:00
Tasks: Prediction, Structured Prediction

Markov Chain Monte Carlo (MCMC) algorithms are often used for approximate
inference inside learning, but their slow mixing can be difficult to diagnose
and the approximations can seriously degrade learning. To alleviate these
issues, we define a new model family using strong Doeblin Markov chains, whose
mixing times can be precisely controlled by a parameter. We also develop an
algorithm to learn such models, which involves maximizing the data likelihood
under the induced stationary distribution of these chains. We show empirical
improvements on two challenging inference tasks.
Reified Context Models
Authors: Jacob Steinhardt, Percy Liang
Date: 2015-02-24 00:00:00

A classic tension exists between exact inference in a simple model and
approximate inference in a complex model. The latter offers expressivity and
thus accuracy, but the former provides coverage of the space, an important
property for confidence estimation and learning with indirect supervision. In
this work, we introduce a new approach, reified context models, to reconcile
this tension. Specifically, we let the amount of context (the arity of the
factors in a graphical model) be chosen "at run-time" by reifying it---that is,
letting this choice itself be a random variable inside the model. Empirically,
we show that our approach obtains expressivity and coverage on three natural
language tasks.
Multi-Touch Attribution Based Budget Allocation in Online Advertising
Authors: Sahin Cem Geyik, Abhishek Saxena, Ali Dasdan
Date: 2015-02-24 00:00:00

Budget allocation in online advertising deals with distributing the campaign
(insertion order) level budgets to different sub-campaigns which employ
different targeting criteria and may perform differently in terms of
return-on-investment (ROI). In this paper, we present the efforts at Turn on
how to best allocate campaign budget so that the advertiser or campaign-level
ROI is maximized. To do this, it is crucial to be able to correctly determine
the performance of sub-campaigns. This determination is highly related to the
action-attribution problem, i.e. to be able to find out the set of ads, and
hence the sub-campaigns that provided them to a user, that an action should be
attributed to. For this purpose, we employ both last-touch (last ad gets all
credit) and multi-touch (many ads share the credit) attribution methodologies.
We present the algorithms deployed at Turn for the attribution problem, as well
as their parallel implementation on the large advertiser performance datasets.
We conclude the paper with our empirical comparison of last-touch and
multi-touch attribution-based budget allocation in a real online advertising
setting.
On The Identifiability of Mixture Models from Grouped Samples
Authors: Robert A. Vandermeulen, Clayton D. Scott
Date: 2015-02-23 00:00:00

Finite mixture models are statistical models which appear in many problems in statistics and machine learning. In such models it is assumed that data are drawn from random probability measures, called mixture components, which are themselves drawn from a probability measure P over probability measures. When estimating mixture models, it is common to make assumptions on the mixture components, such as parametric assumptions. In this paper, we make no assumption on the mixture components, and instead assume that observations from the mixture model are grouped, such that observations in the same group are known to be drawn from the same component. We show that any mixture of m probability measures can be uniquely identified provided there are 2m-1 observations per group. Moreover we show that, for any m, there exists a mixture of m probability measures that cannot be uniquely identified when groups have 2m-2 observations. Our results hold for any sample space with more than one element.
Optimal Sparse Linear Auto-Encoders and Sparse PCA
Authors: Malik Magdon-Ismail, Christos Boutsidis
Date: 2015-02-23 00:00:00
Tasks: Natural Questions

Principal components analysis (PCA) is the optimal linear auto-encoder of
data, and it is often used to construct features. Enforcing sparsity on the
principal components can promote better generalization, while improving the
interpretability of the features. We study the problem of constructing optimal
sparse linear auto-encoders. Two natural questions in such a setting are: i)
Given a level of sparsity, what is the best approximation to PCA that can be
achieved? ii) Are there low-order polynomial-time algorithms which can
asymptotically achieve this optimal tradeoff between the sparsity and the
approximation quality?
  In this work, we answer both questions by giving efficient low-order
polynomial-time algorithms for constructing asymptotically \emph{optimal}
linear auto-encoders (in particular, sparse features with near-PCA
reconstruction error) and demonstrate the performance of our algorithms on real
data.
Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems
Authors: Yash Deshpande, Andrea Montanari
Date: 2015-02-23 00:00:00
Tasks: Two-sample testing

Given a large data matrix $A\in\mathbb{R}^{n\times n}$, we consider the
problem of determining whether its entries are i.i.d. with some known marginal
distribution $A_{ij}\sim P_0$, or instead $A$ contains a principal submatrix
$A_{{\sf Q},{\sf Q}}$ whose entries have marginal distribution $A_{ij}\sim
P_1\neq P_0$. As a special case, the hidden (or planted) clique problem
requires to find a planted clique in an otherwise uniformly random graph.
  Assuming unbounded computational resources, this hypothesis testing problem
is statistically solvable provided $|{\sf Q}|\ge C \log n$ for a suitable
constant $C$. However, despite substantial effort, no polynomial time algorithm
is known that succeeds with high probability when $|{\sf Q}| = o(\sqrt{n})$.
Recently Meka and Wigderson \cite{meka2013association}, proposed a method to
establish lower bounds within the Sum of Squares (SOS) semidefinite hierarchy.
  Here we consider the degree-$4$ SOS relaxation, and study the construction of
\cite{meka2013association} to prove that SOS fails unless $k\ge C\,
n^{1/3}/\log n$. An argument presented by Barak implies that this lower bound
cannot be substantially improved unless the witness construction is changed in
the proof. Our proof uses the moments method to bound the spectrum of a certain
random association scheme, i.e. a symmetric random matrix whose rows and
columns are indexed by the edges of an Erd\"os-Renyi random graph.
Shannon, Tsallis and Kaniadakis entropies in bi-level image thresholding
Authors: Amelia Carolina Sparavigna
Date: 2015-02-23 00:00:00

The maximum entropy principle is often used for bi-level or multi-level
thresholding of images. For this purpose, some methods are available based on
Shannon and Tsallis entropies. In this paper, we discuss them and propose a
method based on Kaniadakis entropy.
An Algorithm for Online K-Means Clustering
Authors: Edo Liberty, Ram Sriharsha, Maxim Sviridenko
Date: 2014-12-18 00:00:00
Tasks: Clustering

This paper shows that one can be competitive with the k-means objective while
operating online. In this model, the algorithm receives vectors v_1,...,v_n one
by one in an arbitrary order. For each vector the algorithm outputs a cluster
identifier before receiving the next one. Our online algorithm generates ~O(k)
clusters whose k-means cost is ~O(W*). Here, W* is the optimal k-means cost
using k clusters and ~O suppresses poly-logarithmic factors. We also show that,
experimentally, it is not much worse than k-means++ while operating in a
strictly more constrained computational model.
From Seed AI to Technological Singularity via Recursively Self-Improving Software
Authors: Roman V. Yampolskiy
Date: 2015-02-23 00:00:00
Tasks: Survey

Software capable of improving itself has been a dream of computer scientists
since the inception of the field. In this work we provide definitions for
Recursively Self-Improving software, survey different types of self-improving
software, review the relevant literature, analyze limits on computation
restricting recursive self-improvement and introduce RSI Convergence Theory
which aims to predict general behavior of RSI systems. Finally, we address
security implications from self-improving intelligent software.
Bandit Convex Optimization: sqrt{T} Regret in One Dimension
Authors: Sébastien Bubeck, Ofer Dekel, Tomer Koren, Yuval Peres
Date: 2015-02-23 00:00:00
Tasks: Thompson Sampling

We analyze the minimax regret of the adversarial bandit convex optimization
problem. Focusing on the one-dimensional case, we prove that the minimax regret
is $\widetilde\Theta(\sqrt{T})$ and partially resolve a decade-old open
problem. Our analysis is non-constructive, as we do not present a concrete
algorithm that attains this regret rate. Instead, we use minimax duality to
reduce the problem to a Bayesian setting, where the convex loss functions are
drawn from a worst-case distribution, and then we solve the Bayesian version of
the problem with a variant of Thompson Sampling. Our analysis features a novel
use of convexity, formalized as a "local-to-global" property of convex
functions, that may be of independent interest.
Convolutional Patch Networks with Spatial Prior for Road Detection and Urban Scene Understanding
Authors: Clemens-Alexander Brust, Sven Sickert, Marcel Simon, Erik Rodner, Joachim Denzler
Date: 2015-02-23 00:00:00
Tasks: Scene Understanding

Classifying single image patches is important in many different applications,
such as road detection or scene understanding. In this paper, we present
convolutional patch networks, which are convolutional networks learned to
distinguish different image patches and which can be used for pixel-wise
labeling. We also show how to incorporate spatial information of the patch as
an input to the network, which allows for learning spatial priors for certain
categories jointly with an appearance model. In particular, we focus on road
detection and urban scene understanding, two application areas where we are
able to achieve state-of-the-art results on the KITTI as well as on the
LabelMeFacade dataset.
  Furthermore, our paper offers a guideline for people working in the area and
desperately wandering through all the painstaking details that render training
CNs on image patches extremely difficult.
Differentially Private Bayesian Optimization
Authors: Matt J. Kusner, Jacob R. Gardner, Roman Garnett, Kilian Q. Weinberger
Date: 2015-01-16 00:00:00
Tasks: Bayesian Optimization, BIG-bench Machine Learning

Bayesian optimization is a powerful tool for fine-tuning the hyper-parameters
of a wide variety of machine learning models. The success of machine learning
has led practitioners in diverse real-world settings to learn classifiers for
practical problems. As machine learning becomes commonplace, Bayesian
optimization becomes an attractive method for practitioners to automate the
process of classifier hyper-parameter tuning. A key observation is that the
data used for tuning models in these settings is often sensitive. Certain data
such as genetic predisposition, personal email statistics, and car accident
history, if not properly private, may be at risk of being inferred from
Bayesian optimization outputs. To address this, we introduce methods for
releasing the best hyper-parameters and classifier accuracy privately.
Leveraging the strong theoretical guarantees of differential privacy and known
Bayesian optimization convergence bounds, we prove that under a GP assumption
these private quantities are also near-optimal. Finally, even if this
assumption is not satisfied, we can use different smoothness guarantees to
protect privacy.
Compressive Hyperspectral Imaging with Side Information
Authors: Xin Yuan, Tsung-Han Tsai, Ruoyu Zhu, Patrick Llull, David Brady, Lawrence Carin
Date: 2015-02-22 00:00:00
Tasks: Compressive Sensing

A blind compressive sensing algorithm is proposed to reconstruct
hyperspectral images from spectrally-compressed measurements.The
wavelength-dependent data are coded and then superposed, mapping the
three-dimensional hyperspectral datacube to a two-dimensional image. The
inversion algorithm learns a dictionary {\em in situ} from the measurements via
global-local shrinkage priors. By using RGB images as side information of the
compressive sensing system, the proposed approach is extended to learn a
coupled dictionary from the joint dataset of the compressed measurements and
the corresponding RGB images, to improve reconstruction quality. A prototype
camera is built using a liquid-crystal-on-silicon modulator. Experimental
reconstructions of hyperspectral datacubes from both simulated and real
compressed measurements demonstrate the efficacy of the proposed inversion
algorithm, the feasibility of the camera and the benefit of side information.
Generative Deep Deconvolutional Learning
Authors: Yunchen Pu, Xin Yuan, Lawrence Carin
Date: 2014-12-18 00:00:00
Tasks: Dictionary Learning, General Classification

A generative Bayesian model is developed for deep (multi-layer) convolutional
dictionary learning. A novel probabilistic pooling operation is integrated into
the deep model, yielding efficient bottom-up and top-down probabilistic
learning. After learning the deep convolutional dictionary, testing is
implemented via deconvolutional inference. To speed up this inference, a new
statistical approach is proposed to project the top-layer dictionary elements
to the data level. Following this, only one layer of deconvolution is required
during testing. Experimental results demonstrate powerful capabilities of the
model to learn multi-layer features from images. Excellent classification
results are obtained on both the MNIST and Caltech 101 datasets.
Some enumerations of binary digital images
Authors: P. Christopher Staecker
Date: 2015-02-22 00:00:00

The topology of digital images has been studied much in recent years, but no
attempt has been made to exhaustively catalog the structure of binary images of
small numbers of points. We produce enumerations of several classes of digital
images up to isomorphism and decide which among them are homotopy equivalent to
one another. Noting some patterns in the results, we make some conjectures
about digital images which are irreducible but not rigid.