pwc-archive/papers-with-abstracts huggingface dataset:
Algorithms for Linear Bandits on Polyhedral Sets
Authors: Manjesh K. Hanawal, Amir Leshem, Venkatesh Saligrama
Date: 2015-09-26 00:00:00

We study stochastic linear optimization problem with bandit feedback. The set
of arms take values in an $N$-dimensional space and belong to a bounded
polyhedron described by finitely many linear inequalities. We provide a lower
bound for the expected regret that scales as $\Omega(N\log T)$. We then provide
a nearly optimal algorithm and show that its expected regret scales as
$O(N\log^{1+\epsilon}(T))$ for an arbitrary small $\epsilon >0$. The algorithm
alternates between exploration and exploitation intervals sequentially where
deterministic set of arms are played in the exploration intervals and greedily
selected arm is played in the exploitation intervals. We also develop an
algorithm that achieves the optimal regret when sub-Gaussianity parameter of
the noise term is known. Our key insight is that for a polyhedron the optimal
arm is robust to small perturbations in the reward function. Consequently, a
greedily selected arm is guaranteed to be optimal when the estimation error
falls below some suitable threshold. Our solution resolves a question posed by
Rusmevichientong and Tsitsiklis (2011) that left open the possibility of
efficient algorithms with asymptotic logarithmic regret bounds. We also show
that the regret upper bounds hold with probability $1$. Our numerical
investigations show that while theoretical results are asymptotic the
performance of our algorithms compares favorably to state-of-the-art algorithms
in finite time as well.
Zero-Shot Learning via Semantic Similarity Embedding
Authors: Ziming Zhang, Venkatesh Saligrama
Date: 2015-09-15 00:00:00
Proceeding: ICCV 2015 12
Tasks: Semantic Similarity, Semantic Textual Similarity, Zero-Shot Learning

In this paper we consider a version of the zero-shot learning problem where
seen class source and target domain data are provided. The goal during
test-time is to accurately predict the class label of an unseen target domain
instance based on revealed source domain side information (\eg attributes) for
unseen classes. Our method is based on viewing each source or target data as a
mixture of seen class proportions and we postulate that the mixture patterns
have to be similar if the two instances belong to the same unseen class. This
perspective leads us to learning source/target embedding functions that map an
arbitrary source/target domain data into a same semantic space where similarity
can be readily measured. We develop a max-margin framework to learn these
similarity functions and jointly optimize parameters by means of cross
validation. Our test results are compelling, leading to significant improvement
in terms of accuracy on most benchmark datasets for zero-shot recognition.
Person Recognition in Personal Photo Collections
Authors: Seong Joon Oh, Rodrigo Benenson, Mario Fritz, Bernt Schiele
Date: 2015-09-11 00:00:00
Proceeding: ICCV 2015 12
Tasks: Informativeness, Person Recognition

Recognising persons in everyday photos presents major challenges (occluded
faces, different clothing, locations, etc.) for machine vision. We propose a
convnet based person recognition system on which we provide an in-depth
analysis of informativeness of different body cues, impact of training data,
and the common failure modes of the system. In addition, we discuss the
limitations of existing benchmarks and propose more challenging ones. Our
method is simple and is built on open source and open data, yet it improves the
state of the art results on a large dataset of social media photos (PIPA).
Selecting Relevant Web Trained Concepts for Automated Event Retrieval
Authors: Bharat Singh, Xintong Han, Zhe Wu, Vlad I. Morariu, Larry S. Davis
Date: 2015-09-25 00:00:00
Proceeding: ICCV 2015 12
Tasks: Domain Adaptation, Retrieval

Complex event retrieval is a challenging research problem, especially when no
training videos are available. An alternative to collecting training videos is
to train a large semantic concept bank a priori. Given a text description of an
event, event retrieval is performed by selecting concepts linguistically
related to the event description and fusing the concept responses on unseen
videos. However, defining an exhaustive concept lexicon and pre-training it
requires vast computational resources. Therefore, recent approaches automate
concept discovery and training by leveraging large amounts of weakly annotated
web data. Compact visually salient concepts are automatically obtained by the
use of concept pairs or, more generally, n-grams. However, not all visually
salient n-grams are necessarily useful for an event query--some combinations of
concepts may be visually compact but irrelevant--and this drastically affects
performance. We propose an event retrieval algorithm that constructs pairs of
automatically discovered concepts and then prunes those concepts that are
unlikely to be helpful for retrieval. Pruning depends both on the query and on
the specific video instance being evaluated. Our approach also addresses
calibration and domain adaptation issues that arise when applying concept
detectors to unseen videos. We demonstrate large improvements over other vision
based systems on the TRECVID MED 13 dataset.
Generalization in Adaptive Data Analysis and Holdout Reuse
Authors: Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Roth
Date: 2015-06-08 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Holdout Set

Overfitting is the bane of data analysts, even when data are plentiful.
Formal approaches to understanding this problem focus on statistical inference
and generalization of individual analysis procedures. Yet the practice of data
analysis is an inherently interactive and adaptive process: new analyses and
hypotheses are proposed after seeing the results of previous ones, parameters
are tuned on the basis of obtained results, and datasets are shared and reused.
An investigation of this gap has recently been initiated by the authors in
(Dwork et al., 2014), where we focused on the problem of estimating
expectations of adaptively chosen functions.
  In this paper, we give a simple and practical method for reusing a holdout
(or testing) set to validate the accuracy of hypotheses produced by a learning
algorithm operating on a training set. Reusing a holdout set adaptively
multiple times can easily lead to overfitting to the holdout set itself. We
give an algorithm that enables the validation of a large number of adaptively
chosen hypotheses, while provably avoiding overfitting. We illustrate the
advantages of our algorithm over the standard use of the holdout set via a
simple synthetic experiment.
  We also formalize and address the general problem of data reuse in adaptive
data analysis. We show how the differential-privacy based approach given in
(Dwork et al., 2014) is applicable much more broadly to adaptive data analysis.
We then show that a simple approach based on description length can also be
used to give guarantees of statistical validity in adaptive settings. Finally,
we demonstrate that these incomparable approaches can be unified via the notion
of approximate max-information that we introduce.
Computational Intelligence Challenges and Applications on Large-Scale Astronomical Time Series Databases
Authors: Pablo Huijse, Pablo A. Estevez, Pavlos Protopapas, Jose C. Principe, Pablo Zegers
Date: 2015-09-25 00:00:00
Tasks: Astronomy, BIG-bench Machine Learning, Time Series, Time Series Analysis

Time-domain astronomy (TDA) is facing a paradigm shift caused by the
exponential growth of the sample size, data complexity and data generation
rates of new astronomical sky surveys. For example, the Large Synoptic Survey
Telescope (LSST), which will begin operations in northern Chile in 2022, will
generate a nearly 150 Petabyte imaging dataset of the southern hemisphere sky.
The LSST will stream data at rates of 2 Terabytes per hour, effectively
capturing an unprecedented movie of the sky. The LSST is expected not only to
improve our understanding of time-varying astrophysical objects, but also to
reveal a plethora of yet unknown faint and fast-varying phenomena. To cope with
a change of paradigm to data-driven astronomy, the fields of astroinformatics
and astrostatistics have been created recently. The new data-oriented paradigms
for astronomy combine statistics, data mining, knowledge discovery, machine
learning and computational intelligence, in order to provide the automated and
robust methods needed for the rapid detection and classification of known
astrophysical objects as well as the unsupervised characterization of novel
phenomena. In this article we present an overview of machine learning and
computational intelligence applications to TDA. Future big data challenges and
new lines of research in TDA, focusing on the LSST, are identified and
discussed from the viewpoint of computational intelligence/machine learning.
Interdisciplinary collaboration will be required to cope with the challenges
posed by the deluge of astronomical data coming from the LSST.
Predicting Deep Zero-Shot Convolutional Neural Networks using Textual Descriptions
Authors: Jimmy Ba, Kevin Swersky, Sanja Fidler, Ruslan Salakhutdinov
Date: 2015-06-01 00:00:00
Proceeding: ICCV 2015 12
Tasks: Articles, Zero-Shot Learning

One of the main challenges in Zero-Shot Learning of visual categories is
gathering semantic attributes to accompany images. Recent work has shown that
learning from textual descriptions, such as Wikipedia articles, avoids the
problem of having to explicitly define these attributes. We present a new model
that can classify unseen categories from their textual description.
Specifically, we use text features to predict the output weights of both the
convolutional and the fully connected layers in a deep convolutional neural
network (CNN). We take advantage of the architecture of CNNs and learn features
at different layers, rather than just learning an embedding space for both
modalities, as is common with existing approaches. The proposed model also
allows us to automatically generate a list of pseudo- attributes for each
visual category consisting of words from Wikipedia articles. We train our
models end-to-end us- ing the Caltech-UCSD bird and flower datasets and
evaluate both ROC and Precision-Recall curves. Our empirical results show that
the proposed model significantly outperforms previous methods.
On Data Preconditioning for Regularized Loss Minimization
Authors: Tianbao Yang, Rong Jin, Shenghuo Zhu, Qihang Lin
Date: 2014-08-13 00:00:00

In this work, we study data preconditioning, a well-known and long-existing
technique, for boosting the convergence of first-order methods for regularized
loss minimization. It is well understood that the condition number of the
problem, i.e., the ratio of the Lipschitz constant to the strong convexity
modulus, has a harsh effect on the convergence of the first-order optimization
methods. Therefore, minimizing a small regularized loss for achieving good
generalization performance, yielding an ill conditioned problem, becomes the
bottleneck for big data problems. We provide a theory on data preconditioning
for regularized loss minimization. In particular, our analysis exhibits an
appropriate data preconditioner and characterizes the conditions on the loss
function and on the data under which data preconditioning can reduce the
condition number and therefore boost the convergence for minimizing the
regularized loss. To make the data preconditioning practically useful, we
endeavor to employ and analyze a random sampling approach to efficiently
compute the preconditioned data. The preliminary experiments validate our
theory.
A Mathematical Theory for Clustering in Metric Spaces
Authors: Cheng-Shang Chang, Wanjiun Liao, Yu-Sheng Chen, Li-Heng Liou
Date: 2015-09-25 00:00:00
Tasks: Clustering

Clustering is one of the most fundamental problems in data analysis and it
has been studied extensively in the literature. Though many clustering
algorithms have been proposed, clustering theories that justify the use of
these clustering algorithms are still unsatisfactory. In particular, one of the
fundamental challenges is to address the following question:
  What is a cluster in a set of data points?
  In this paper, we make an attempt to address such a question by considering a
set of data points associated with a distance measure (metric). We first
propose a new cohesion measure in terms of the distance measure. Using the
cohesion measure, we define a cluster as a set of points that are cohesive to
themselves. For such a definition, we show there are various equivalent
statements that have intuitive explanations. We then consider the second
question:
  How do we find clusters and good partitions of clusters under such a
definition?
  For such a question, we propose a hierarchical agglomerative algorithm and a
partitional algorithm. Unlike standard hierarchical agglomerative algorithms,
our hierarchical agglomerative algorithm has a specific stopping criterion and
it stops with a partition of clusters. Our partitional algorithm, called the
K-sets algorithm in the paper, appears to be a new iterative algorithm. Unlike
the Lloyd iteration that needs two-step minimization, our K-sets algorithm only
takes one-step minimization.
  One of the most interesting findings of our paper is the duality result
between a distance measure and a cohesion measure. Such a duality result leads
to a dual K-sets algorithm for clustering a set of data points with a cohesion
measure. The dual K-sets algorithm converges in the same way as a sequential
version of the classical kernel K-means algorithm. The key difference is that a
cohesion measure does not need to be positive semi-definite.
Efficient Computation of the Quasi Likelihood function for Discretely Observed Diffusion Processes
Authors: Lars Josef Höök, Erik Lindström
Date: 2015-09-25 00:00:00
Tasks: All

We introduce a simple method for nearly simultaneous computation of all
moments needed for quasi maximum likelihood estimation of parameters in
discretely observed stochastic differential equations commonly seen in finance.
The method proposed in this papers is not restricted to any particular dynamics
of the differential equation and is virtually insensitive to the sampling
interval. The key contribution of the paper is that computational complexity is
sublinear in the number of observations as we compute all moments through a
single operation. Furthermore, that operation can be done offline. The
simulations show that the method is unbiased for all practical purposes for any
sampling design, including random sampling, and that the computational cost is
comparable (actually faster for moderate and large data sets) to the simple,
often severely biased, Euler-Maruyama approximation.
Online Stochastic Linear Optimization under One-bit Feedback
Authors: Lijun Zhang, Tianbao Yang, Rong Jin, Zhi-Hua Zhou
Date: 2015-09-25 00:00:00

In this paper, we study a special bandit setting of online stochastic linear
optimization, where only one-bit of information is revealed to the learner at
each round. This problem has found many applications including online
advertisement and online recommendation. We assume the binary feedback is a
random variable generated from the logit model, and aim to minimize the regret
defined by the unknown linear function. Although the existing method for
generalized linear bandit can be applied to our problem, the high computational
cost makes it impractical for real-world problems. To address this challenge,
we develop an efficient online learning algorithm by exploiting particular
structures of the observation model. Specifically, we adopt online Newton step
to estimate the unknown parameter and derive a tight confidence region based on
the exponential concavity of the logistic loss. Our analysis shows that the
proposed algorithm achieves a regret bound of $O(d\sqrt{T})$, which matches the
optimal result of stochastic linear bandits.
Utility-based Dueling Bandits as a Partial Monitoring Game
Authors: Pratik Gajane, Tanguy Urvoy
Date: 2015-07-10 00:00:00
Tasks: Decision Making, Sequential Decision Making

Partial monitoring is a generic framework for sequential decision-making with
incomplete feedback. It encompasses a wide class of problems such as dueling
bandits, learning with expect advice, dynamic pricing, dark pools, and label
efficient prediction. We study the utility-based dueling bandit problem as an
instance of partial monitoring problem and prove that it fits the time-regret
partial monitoring hierarchy as an easy - i.e. Theta (sqrt{T})- instance. We
survey some partial monitoring algorithms and see how they could be used to
solve dueling bandits efficiently. Keywords: Online learning, Dueling Bandits,
Partial Monitoring, Partial Feedback, Multiarmed Bandits
A hybrid COA$ε$-constraint method for solving multi-objective problems
Authors: Mahdi parvizi, Elham Shadkam, Niloofar Jahani
Date: 2015-09-25 00:00:00

In this paper, a hybrid method for solving multi-objective problem has been
provided. The proposed method is combining the {\epsilon}-Constraint and the
Cuckoo algorithm. First the multi objective problem transfers into a
single-objective problem using $\epsilon$-Constraint, then the Cuckoo
optimization algorithm will optimize the problem in each task. At last the
optimized Pareto frontier will be drawn. The advantage of this method is the
high accuracy and the dispersion of its Pareto frontier. In order to testing
the efficiency of the suggested method, a lot of test problems have been solved
using this method. Comparing the results of this method with the results of
other similar methods shows that the Cuckoo algorithm is more suitable for
solving the multi-objective problems.
Dense image registration and deformable surface reconstruction in presence of occlusions and minimal texture
Authors: Dat Tien Ngo, Sanghuyk Park, Anne Jorstad, Alberto Crivellaro, Chang Yoo, Pascal Fua
Date: 2015-03-11 00:00:00
Proceeding: ICCV 2015 12
Tasks: 3D Reconstruction, Image Registration, Surface Reconstruction, Template Matching

Deformable surface tracking from monocular images is well-known to be
under-constrained. Occlusions often make the task even more challenging, and
can result in failure if the surface is not sufficiently textured. In this
work, we explicitly address the problem of 3D reconstruction of poorly
textured, occluded surfaces, proposing a framework based on a template-matching
approach that scales dense robust features by a relevancy score. Our approach
is extensively compared to current methods employing both local feature
matching and dense template alignment. We test on standard datasets as well as
on a new dataset (that will be made publicly available) of a sparsely textured,
occluded surface. Our framework achieves state-of-the-art results for both well
and poorly textured, occluded surfaces.
Feature Evaluation of Deep Convolutional Neural Networks for Object Recognition and Detection
Authors: Hirokatsu Kataoka, Kenji Iwata, Yutaka Satoh
Date: 2015-09-25 00:00:00
Tasks: General Classification, Object Recognition

In this paper, we evaluate convolutional neural network (CNN) features using
the AlexNet architecture and very deep convolutional network (VGGNet)
architecture. To date, most CNN researchers have employed the last layers
before output, which were extracted from the fully connected feature layers.
However, since it is unlikely that feature representation effectiveness is
dependent on the problem, this study evaluates additional convolutional layers
that are adjacent to fully connected layers, in addition to executing simple
tuning for feature concatenation (e.g., layer 3 + layer 5 + layer 7) and
transformation, using tools such as principal component analysis. In our
experiments, we carried out detection and classification tasks using the
Caltech 101 and Daimler Pedestrian Benchmark Datasets.
Self-localization Using Visual Experience Across Domains
Authors: Taisho Tsukamoto, Kanji Tanaka
Date: 2015-09-25 00:00:00
Tasks: Retrieval

In this study, we aim to solve the single-view robot self-localization
problem by using visual experience across domains. Although the bag-of-words
method constitutes a popular approach to single-view localization, it fails
badly when it's visual vocabulary is learned and tested in different domains.
Further, we are interested in using a cross-domain setting, in which the visual
vocabulary is learned in different seasons and routes from the input
query/database scenes. Our strategy is to mine a cross-domain visual
experience, a library of raw visual images collected in different domains, to
discover the relevant visual patterns that effectively explain the input scene,
and use them for scene retrieval. In particular, we show that the appearance
and the pose of the mined visual patterns of a query scene can be efficiently
and discriminatively matched against those of the database scenes by employing
image-to-class distance and spatial pyramid matching. Experimental results
obtained using a novel cross-domain dataset show that our system achieves
promising results despite our visual vocabulary being learned and tested in
different domains.
Discriminative Map Retrieval Using View-Dependent Map Descriptor
Authors: Enfu Liu, Kanji Tanaka
Date: 2015-09-25 00:00:00
Tasks: Autonomous Navigation, Descriptive, Retrieval, Scene Parsing

Map retrieval, the problem of similarity search over a large collection of 2D
pointset maps previously built by mobile robots, is crucial for autonomous
navigation in indoor and outdoor environments. Bag-of-words (BoW) methods
constitute a popular approach to map retrieval; however, these methods have
extremely limited descriptive ability because they ignore the spatial layout
information of the local features. The main contribution of this paper is an
extension of the bag-of-words map retrieval method to enable the use of spatial
information from local features. Our strategy is to explicitly model a unique
viewpoint of an input local map; the pose of the local feature is defined with
respect to this unique viewpoint, and can be viewed as an additional invariant
feature for discriminative map retrieval. Specifically, we wish to determine a
unique viewpoint that is invariant to moving objects, clutter, occlusions, and
actual viewpoints. Hence, we perform scene parsing to analyze the scene
structure, and consider the "center" of the scene structure to be the unique
viewpoint. Our scene parsing is based on a Manhattan world grammar that imposes
a quasi-Manhattan world constraint to enable the robust detection of a scene
structure that is invariant to clutter and moving objects. Experimental results
using the publicly available radish dataset validate the efficacy of the
proposed approach.
Sentiment Uncertainty and Spam in Twitter Streams and Its Implications for General Purpose Realtime Sentiment Analysis
Authors: Nils Haldenwang, Oliver Vornberger
Date: 2015-09-25 00:00:00
Tasks: Sentiment Analysis, Twitter Sentiment Analysis

State of the art benchmarks for Twitter Sentiment Analysis do not consider
the fact that for more than half of the tweets from the public stream a
distinct sentiment cannot be chosen. This paper provides a new perspective on
Twitter Sentiment Analysis by highlighting the necessity of explicitly
incorporating uncertainty. Moreover, a dataset of high quality to evaluate
solutions for this new problem is introduced and made publicly available.