pwc-archive/papers-with-abstracts huggingface dataset:
On the Optimal Sample Complexity for Best Arm Identification
Authors: Lijie Chen, Jian Li
Date: 2015-11-12 00:00:00

We study the best arm identification (BEST-1-ARM) problem, which is defined
as follows. We are given $n$ stochastic bandit arms. The $i$th arm has a reward
distribution $D_i$ with an unknown mean $\mu_{i}$. Upon each play of the $i$th
arm, we can get a reward, sampled i.i.d. from $D_i$. We would like to identify
the arm with the largest mean with probability at least $1-\delta$, using as
few samples as possible. We provide a nontrivial algorithm for BEST-1-ARM,
which improves upon several prior upper bounds on the same problem. We also
study an important special case where there are only two arms, which we call
the sign problem. We provide a new lower bound of sign, simplifying and
significantly extending a classical result by Farrell in 1964, with a
completely new proof. Using the new lower bound for sign, we obtain the first
lower bound for BEST-1-ARM that goes beyond the classic Mannor-Tsitsiklis lower
bound, by an interesting reduction from Sign to BEST-1-ARM. We propose an
interesting conjecture concerning the optimal sample complexity of BEST-1-ARM
from the perspective of instance-wise optimality.
Fathom: Reference Workloads for Modern Deep Learning Methods
Authors: Robert Adolf, Saketh Rama, Brandon Reagen, Gu-Yeon Wei, David Brooks
Date: 2016-08-23 00:00:00
Tasks: Deep Learning, Specificity

Deep learning has been popularized by its recent successes on challenging
artificial intelligence problems. One of the reasons for its dominance is also
an ongoing challenge: the need for immense amounts of computational power.
Hardware architects have responded by proposing a wide array of promising
ideas, but to date, the majority of the work has focused on specific algorithms
in somewhat narrow application domains. While their specificity does not
diminish these approaches, there is a clear need for more flexible solutions.
We believe the first step is to examine the characteristics of cutting edge
models from across the deep learning community.
  Consequently, we have assembled Fathom: a collection of eight archetypal deep
learning workloads for study. Each of these models comes from a seminal work in
the deep learning community, ranging from the familiar deep convolutional
neural network of Krizhevsky et al., to the more exotic memory networks from
Facebook's AI research group. Fathom has been released online, and this paper
focuses on understanding the fundamental performance characteristics of each
model. We use a set of application-level modeling tools built around the
TensorFlow deep learning framework in order to analyze the behavior of the
Fathom workloads. We present a breakdown of where time is spent, the
similarities between the performance profiles of our models, an analysis of
behavior in inference and training, and the effects of parallelism on scaling.
Inception-v4, Inception-ResNet and the Impact of Residual Connections on Learning
Authors: Christian Szegedy, Sergey Ioffe, Vincent Vanhoucke, Alex Alemi
Date: 2016-02-23 00:00:00
Tasks: Classification, General Classification, Image Classification

Very deep convolutional networks have been central to the largest advances in
image recognition performance in recent years. One example is the Inception
architecture that has been shown to achieve very good performance at relatively
low computational cost. Recently, the introduction of residual connections in
conjunction with a more traditional architecture has yielded state-of-the-art
performance in the 2015 ILSVRC challenge; its performance was similar to the
latest generation Inception-v3 network. This raises the question of whether
there are any benefit in combining the Inception architecture with residual
connections. Here we give clear empirical evidence that training with residual
connections accelerates the training of Inception networks significantly. There
is also some evidence of residual Inception networks outperforming similarly
expensive Inception networks without residual connections by a thin margin. We
also present several new streamlined architectures for both residual and
non-residual Inception networks. These variations improve the single-frame
recognition performance on the ILSVRC 2012 classification task significantly.
We further demonstrate how proper activation scaling stabilizes the training of
very wide residual Inception networks. With an ensemble of three residual and
one Inception-v4, we achieve 3.08 percent top-5 error on the test set of the
ImageNet classification (CLS) challenge
Computation of Stackelberg Equilibria of Finite Sequential Games
Authors: Branislav Bosansky, Simina Branzei, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sorensen
Date: 2015-07-28 00:00:00

The Stackelberg equilibrium solution concept describes optimal strategies to
commit to: Player 1 (termed the leader) publicly commits to a strategy and
Player 2 (termed the follower) plays a best response to this strategy (ties are
broken in favor of the leader). We study Stackelberg equilibria in finite
sequential games (or extensive-form games) and provide new exact algorithms,
approximate algorithms, and hardness results for several classes of these
sequential games.
A Non-Local Conventional Approach for Noise Removal in 3D MRI
Authors: Sona Morajab, Mehregan Mahdavi
Date: 2016-08-23 00:00:00
Tasks: Denoising

In this paper, a filtering approach for the 3D magnetic resonance imaging
(MRI) assuming a Rician model for noise is addressed. Our denoising method is
based on the Conventional Approach (CA) proposed to deal with the noise issue
in the squared domain of the acquired magnitude MRI, where the noise
distribution follows a Chi-square model rather than the Rician one. In the CA
filtering method, the local samples around each voxel is used to estimate the
unknown signal value. Intrinsically, such a method fails to achieve the best
results where the underlying signal values have different statistical
properties. On the contrary, our proposal takes advantage of the data
redundancy and self-similarity properties of real MR images to improve the
noise removal performance. In other words, in our approach, the statistical
momentums of the given 3D MR volume are first calculated to explore the similar
patches inside a defined search volume. Then, these patches are put together to
obtain the noise-free value for each voxel under processing. The experimental
results on the synthetic as well as the clinical MR data show our proposed
method outperforms the other compared denoising filters.
Neural Networks with Smooth Adaptive Activation Functions for Regression
Authors: Le Hou, Dimitris Samaras, Tahsin M. Kurc, Yi Gao, Joel H. Saltz
Date: 2016-08-23 00:00:00
Tasks: regression

In Neural Networks (NN), Adaptive Activation Functions (AAF) have parameters
that control the shapes of activation functions. These parameters are trained
along with other parameters in the NN. AAFs have improved performance of Neural
Networks (NN) in multiple classification tasks. In this paper, we propose and
apply AAFs on feedforward NNs for regression tasks. We argue that applying AAFs
in the regression (second-to-last) layer of a NN can significantly decrease the
bias of the regression NN. However, using existing AAFs may lead to
overfitting. To address this problem, we propose a Smooth Adaptive Activation
Function (SAAF) with piecewise polynomial form which can approximate any
continuous function to arbitrary degree of error. NNs with SAAFs can avoid
overfitting by simply regularizing the parameters. In particular, an NN with
SAAFs is Lipschitz continuous given a bounded magnitude of the NN parameters.
We prove an upper-bound for model complexity in terms of fat-shattering
dimension for any Lipschitz continuous regression model. Thus, regularizing the
parameters in NNs with SAAFs avoids overfitting. We empirically evaluated NNs
with SAAFs and achieved state-of-the-art results on multiple regression
datasets.
Using Semantic Similarity for Input Topic Identification in Crawling-based Web Application Testing
Authors: Jun-Wei Lin, Farn Wang
Date: 2016-08-23 00:00:00
Tasks: Semantic Similarity, Semantic Textual Similarity

To automatically test web applications, crawling-based techniques are usually
adopted to mine the behavior models, explore the state spaces or detect the
violated invariants of the applications. However, in existing crawlers, rules
for identifying the topics of input text fields, such as login ids, passwords,
emails, dates and phone numbers, have to be manually configured. Moreover, the
rules for one application are very often not suitable for another. In addition,
when several rules conflict and match an input text field to more than one
topics, it can be difficult to determine which rule suggests a better match.
This paper presents a natural-language approach to automatically identify the
topics of encountered input fields during crawling by semantically comparing
their similarities with the input fields in labeled corpus. In our evaluation
with 100 real-world forms, the proposed approach demonstrated comparable
performance to the rule-based one. Our experiments also show that the accuracy
of the rule-based approach can be improved by up to 19% when integrated with
our approach.
Is a good offensive always the best defense?
Authors: J. Quetzalcóatl Toledo-Marín, Rogelio Díaz-Méndez, Marcelo del Castillo Mussot
Date: 2016-08-23 00:00:00

A checkers-like model game with a simplified set of rules is studied through
extensive simulations of agents with different expertise and strategies. The
introduction of complementary strategies, in a quite general way, provides a
tool to mimic the basic ingredients of a wide scope of real games. We find that
only for the player having the higher offensive expertise (the dominant player
), maximizing the offensive always increases the probability to win. For the
non-dominant player, interestingly, a complete minimization of the offensive
becomes the best way to win in many situations, depending on the relative
values of the defense expertise. Further simulations on the interplay of
defense expertise were done separately, in the context of a fully-offensive
scenario, offering a starting point for analytical treatments. In particular,
we established that in this scenario the total number of moves is defined only
by the player with the lower defensive expertise. We believe that these results
stand for a first step towards a new way to improve decisions-making in a large
number of zero-sum real games.
On Simulated Annealing Dedicated to Maximin Latin Hypercube Designs
Authors: Pierre Bergé, Kaourintin Le Guiban, Arpad Rimmel, Joanna Tomasik
Date: 2016-08-23 00:00:00

The goal of our research was to enhance local search heuristics used to
construct Latin Hypercube Designs. First, we introduce the \textit{1D-move}
perturbation to improve the space exploration performed by these algorithms.
Second, we propose a new evaluation function $\psi_{p,\sigma}$ specifically
targeting the Maximin criterion.
  Exhaustive series of experiments with Simulated Annealing, which we used as a
typically well-behaving local search heuristics, confirm that our goal was
reached as the result we obtained surpasses the best scores reported in the
literature. Furthermore, the $\psi_{p,\sigma}$ function seems very promising
for a wide spectrum of optimization problems through the Maximin criterion.
Searching Action Proposals via Spatial Actionness Estimation and Temporal Path Inference and Tracking
Authors: Nannan Li, Dan Xu, Zhenqiang Ying, Zhihao LI, Ge Li
Date: 2016-08-23 00:00:00

In this paper, we address the problem of searching action proposals in
unconstrained video clips. Our approach starts from actionness estimation on
frame-level bounding boxes, and then aggregates the bounding boxes belonging to
the same actor across frames via linking, associating, tracking to generate
spatial-temporal continuous action paths. To achieve the target, a novel
actionness estimation method is firstly proposed by utilizing both human
appearance and motion cues. Then, the association of the action paths is
formulated as a maximum set coverage problem with the results of actionness
estimation as a priori. To further promote the performance, we design an
improved optimization objective for the problem and provide a greedy search
algorithm to solve it. Finally, a tracking-by-detection scheme is designed to
further refine the searched action paths. Extensive experiments on two
challenging datasets, UCF-Sports and UCF-101, show that the proposed approach
advances state-of-the-art proposal generation performance in terms of both
accuracy and proposal quantity.
Adversarial Training For Sketch Retrieval
Authors: Antonia Creswell, Anil Anthony Bharath
Date: 2016-07-10 00:00:00
Tasks: Image Generation, Retrieval, Scene Classification, Translation

Generative Adversarial Networks (GAN) are able to learn excellent
representations for unlabelled data which can be applied to image generation
and scene classification. Representations learned by GANs have not yet been
applied to retrieval. In this paper, we show that the representations learned
by GANs can indeed be used for retrieval. We consider heritage documents that
contain unlabelled Merchant Marks, sketch-like symbols that are similar to
hieroglyphs. We introduce a novel GAN architecture with design features that
make it suitable for sketch retrieval. The performance of this sketch-GAN is
compared to a modified version of the original GAN architecture with respect to
simple invariance properties. Experiments suggest that sketch-GANs learn
representations that are suitable for retrieval and which also have increased
stability to rotation, scale and translation compared to the standard GAN
architecture.
Tracking Amendments to Legislation and Other Political Texts with a Novel Minimum-Edit-Distance Algorithm: DocuToads
Authors: Henrik Hermansson, James P. Cross
Date: 2016-08-23 00:00:00

Political scientists often find themselves tracking amendments to political
texts. As different actors weigh in, texts change as they are drafted and
redrafted, reflecting political preferences and power. This study provides a
novel solution to the prob- lem of detecting amendments to political text based
upon minimum edit distances. We demonstrate the usefulness of two
language-insensitive, transparent, and efficient minimum-edit-distance
algorithms suited for the task. These algorithms are capable of providing an
account of the types (insertions, deletions, substitutions, and trans-
positions) and substantive amount of amendments made between version of texts.
To illustrate the usefulness and efficiency of the approach we replicate two
existing stud- ies from the field of legislative studies. Our results
demonstrate that minimum edit distance methods can produce superior measures of
text amendments to hand-coded efforts in a fraction of the time and resource
costs.
Failure Detection for Facial Landmark Detectors
Authors: Andreas Steger, Radu Timofte, Luc van Gool
Date: 2016-08-23 00:00:00
Tasks: Facial Landmark Detection

Most face applications depend heavily on the accuracy of the face and facial
landmarks detectors employed. Prediction of attributes such as gender, age, and
identity usually completely fail when the faces are badly aligned due to
inaccurate facial landmark detection. Despite the impressive recent advances in
face and facial landmark detection, little study is on the recovery from and
detection of failures or inaccurate predictions. In this work we study two top
recent facial landmark detectors and devise confidence models for their
outputs. We validate our failure detection approaches on standard benchmarks
(AFLW, HELEN) and correctly identify more than 40% of the failures in the
outputs of the landmark detectors. Moreover, with our failure detection we can
achieve a 12% error reduction on a gender estimation application at the cost of
a small increase in computation.
A Delay-Tolerant Potential-Field-Based Network Implementation of an Integrated Navigation System
Authors: Rachana Ashok Gupta, Ahmad A. Masoud, Mo-Yuen Chow
Date: 2016-08-23 00:00:00

Network controllers (NCs) are devices that are capable of converting dynamic,
spatially extended, and functionally specialized modules into a taskable
goal-oriented group called networked control system. This paper examines the
practical aspects of designing and building an NC that uses the Internet as a
communication medium. It focuses on finding compatible controller components
that can be integrated via a host structure in a manner that makes it possible
to network, in real-time, a webcam, an unmanned ground vehicle (UGV), and a
remote computer server along with the necessary operator software interface.
The aim is to deskill the UGV navigation process and yet maintain a robust
performance. The structure of the suggested controller, its components, and the
manner in which they are interfaced are described. Thorough experimental
results along with performance assessment and comparisons to a previously
implemented NC are provided.
Convolutional Network for Attribute-driven and Identity-preserving Human Face Generation
Authors: Mu Li, WangMeng Zuo, David Zhang
Date: 2016-08-23 00:00:00
Tasks: Attribute, Face Generation

This paper focuses on the problem of generating human face pictures from
specific attributes. The existing CNN-based face generation models, however,
either ignore the identity of the generated face or fail to preserve the
identity of the reference face image. Here we address this problem from the
view of optimization, and suggest an optimization model to generate human face
with the given attributes while keeping the identity of the reference image.
The attributes can be obtained from the attribute-guided image or by tuning the
attribute features of the reference image. With the deep convolutional network
"VGG-Face", the loss is defined on the convolutional feature maps. We then
apply the gradient decent algorithm to solve this optimization problem. The
results validate the effectiveness of our method for attribute driven and
identity-preserving face generation.
Scan, Attend and Read: End-to-End Handwritten Paragraph Recognition with MDLSTM Attention
Authors: Théodore Bluche, Jérôme Louradour, Ronaldo Messina
Date: 2016-04-12 00:00:00
Tasks: Handwriting Recognition, Image Captioning, Segmentation, speech-recognition, Speech Recognition, Translation

We present an attention-based model for end-to-end handwriting recognition.
Our system does not require any segmentation of the input paragraph. The model
is inspired by the differentiable attention models presented recently for
speech recognition, image captioning or translation. The main difference is the
covert and overt attention, implemented as a multi-dimensional LSTM network.
Our principal contribution towards handwriting recognition lies in the
automatic transcription without a prior segmentation into lines, which was
crucial in previous approaches. To the best of our knowledge this is the first
successful attempt of end-to-end multi-line handwriting recognition. We carried
out experiments on the well-known IAM Database. The results are encouraging and
bring hope to perform full paragraph transcription in the near future.
Stability revisited: new generalisation bounds for the Leave-one-Out
Authors: Alain Celisse, Benjamin Guedj
Date: 2016-08-23 00:00:00
Tasks: regression

The present paper provides a new generic strategy leading to non-asymptotic
theoretical guarantees on the Leave-one-Out procedure applied to a broad class
of learning algorithms. This strategy relies on two main ingredients: the new
notion of $L^q$ stability, and the strong use of moment inequalities. $L^q$
stability extends the ongoing notion of hypothesis stability while remaining
weaker than the uniform stability. It leads to new PAC exponential
generalisation bounds for Leave-one-Out under mild assumptions. In the
literature, such bounds are available only for uniform stable algorithms under
boundedness for instance. Our generic strategy is applied to the Ridge
regression algorithm as a first step.
lpopt: A Rule Optimization Tool for Answer Set Programming
Authors: Manuel Bichler, Michael Morak, Stefan Woltran
Date: 2016-08-19 00:00:00

State-of-the-art answer set programming (ASP) solvers rely on a program
called a grounder to convert non-ground programs containing variables into
variable-free, propositional programs. The size of this grounding depends
heavily on the size of the non-ground rules, and thus, reducing the size of
such rules is a promising approach to improve solving performance. To this end,
in this paper we announce lpopt, a tool that decomposes large logic programming
rules into smaller rules that are easier to handle for current solvers. The
tool is specifically tailored to handle the standard syntax of the ASP language
(ASP-Core) and makes it easier for users to write efficient and intuitive ASP
programs, which would otherwise often require significant hand-tuning by expert
ASP engineers. It is based on an idea proposed by Morak and Woltran (2012) that
we extend significantly in order to handle the full ASP syntax, including
complex constructs like aggregates, weak constraints, and arithmetic
expressions. We present the algorithm, the theoretical foundations on how to
treat these constructs, as well as an experimental evaluation showing the
viability of our approach.
Learning to Communicate: Channel Auto-encoders, Domain Specific Regularizers, and Attention
Authors: Timothy J. O'Shea, Kiran Karra, T. Charles Clancy
Date: 2016-08-23 00:00:00
Tasks: Decoder

We address the problem of learning efficient and adaptive ways to communicate
binary information over an impaired channel. We treat the problem as
reconstruction optimization through impairment layers in a channel autoencoder
and introduce several new domain-specific regularizing layers to emulate common
channel impairments. We also apply a radio transformer network based attention
model on the input of the decoder to help recover canonical signal
representations. We demonstrate some promising initial capacity results from
this architecture and address several remaining challenges before such a system
could become practical.
Online Learning to Rank with Top-k Feedback
Authors: Sougata Chaudhuri, Ambuj Tewari
Date: 2016-08-23 00:00:00
Tasks: Learning-To-Rank

We consider two settings of online learning to rank where feedback is
restricted to top ranked items. The problem is cast as an online game between a
learner and sequence of users, over $T$ rounds. In both settings, the learners
objective is to present ranked list of items to the users. The learner's
performance is judged on the entire ranked list and true relevances of the
items. However, the learner receives highly restricted feedback at end of each
round, in form of relevances of only the top $k$ ranked items, where $k \ll m$.
The first setting is \emph{non-contextual}, where the list of items to be
ranked is fixed. The second setting is \emph{contextual}, where lists of items
vary, in form of traditional query-document lists. No stochastic assumption is
made on the generation process of relevances of items and contexts. We provide
efficient ranking strategies for both the settings. The strategies achieve
$O(T^{2/3})$ regret, where regret is based on popular ranking measures in first
setting and ranking surrogates in second setting. We also provide impossibility
results for certain ranking measures and a certain class of surrogates, when
feedback is restricted to the top ranked item, i.e. $k=1$. We empirically
demonstrate the performance of our algorithms on simulated and real world
datasets.