pwc-archive/papers-with-abstracts huggingface dataset:
Stochastic Rank-1 Bandits
Authors: Sumeet Katariya, Branislav Kveton, Csaba Szepesvari, Claire Vernade, Zheng Wen
Date: 2016-08-10 00:00:00

We propose stochastic rank-$1$ bandits, a class of online learning problems
where at each step a learning agent chooses a pair of row and column arms, and
receives the product of their values as a reward. The main challenge of the
problem is that the individual values of the row and column are unobserved. We
assume that these values are stochastic and drawn independently. We propose a
computationally-efficient algorithm for solving our problem, which we call
Rank1Elim. We derive a $O((K + L) (1 / \Delta) \log n)$ upper bound on its
$n$-step regret, where $K$ is the number of rows, $L$ is the number of columns,
and $\Delta$ is the minimum of the row and column gaps; under the assumption
that the mean row and column rewards are bounded away from zero. To the best of
our knowledge, we present the first bandit algorithm that finds the maximum
entry of a rank-$1$ matrix whose regret is linear in $K + L$, $1 / \Delta$, and
$\log n$. We also derive a nearly matching lower bound. Finally, we evaluate
Rank1Elim empirically on multiple problems. We observe that it leverages the
structure of our problems and can learn near-optimal solutions even if our
modeling assumptions are mildly violated.
Initialization and Coordinate Optimization for Multi-way Matching
Authors: Da Tang, Tony Jebara
Date: 2016-11-02 00:00:00

We consider the problem of consistently matching multiple sets of elements to each other, which is a common task in fields such as computer vision. To solve the underlying NP-hard objective, existing methods often relax or approximate it, but end up with unsatisfying empirical performance due to a misaligned objective. We propose a coordinate update algorithm that directly optimizes the target objective. By using pairwise alignment information to build an undirected graph and initializing the permutation matrices along the edges of its Maximum Spanning Tree, our algorithm successfully avoids bad local optima. Theoretically, with high probability our algorithm guarantees an optimal solution under reasonable noise assumptions. Empirically, our algorithm consistently and significantly outperforms existing methods on several benchmark tasks on real datasets.
Context Gates for Neural Machine Translation
Authors: Zhaopeng Tu, Yang Liu, Zhengdong Lu, Xiaohua Liu, Hang Li
Date: 2016-08-22 00:00:00
Proceeding: TACL 2017 1
Tasks: Machine Translation, NMT, Translation

In neural machine translation (NMT), generation of a target word depends on
both source and target contexts. We find that source contexts have a direct
impact on the adequacy of a translation while target contexts affect the
fluency. Intuitively, generation of a content word should rely more on the
source context and generation of a functional word should rely more on the
target context. Due to the lack of effective control over the influence from
source and target contexts, conventional NMT tends to yield fluent but
inadequate translations. To address this problem, we propose context gates
which dynamically control the ratios at which source and target contexts
contribute to the generation of target words. In this way, we can enhance both
the adequacy and fluency of NMT with more careful control of the information
flow from contexts. Experiments show that our approach significantly improves
upon a standard attention-based NMT system by +2.3 BLEU points.
Scalable Greedy Feature Selection via Weak Submodularity
Authors: Rajiv Khanna, Ethan Elenberg, Alexandros G. Dimakis, Sahand Negahban, Joydeep Ghosh
Date: 2017-03-08 00:00:00
Tasks: feature selection

Greedy algorithms are widely used for problems in machine learning such as
feature selection and set function optimization. Unfortunately, for large
datasets, the running time of even greedy algorithms can be quite high. This is
because for each greedy step we need to refit a model or calculate a function
using the previously selected choices and the new candidate.
  Two algorithms that are faster approximations to the greedy forward selection
were introduced recently ([Mirzasoleiman et al. 2013, 2015]). They achieve
better performance by exploiting distributed computation and stochastic
evaluation respectively. Both algorithms have provable performance guarantees
for submodular functions.
  In this paper we show that divergent from previously held opinion,
submodularity is not required to obtain approximation guarantees for these two
algorithms. Specifically, we show that a generalized concept of weak
submodularity suffices to give multiplicative approximation guarantees. Our
result extends the applicability of these algorithms to a larger class of
functions. Furthermore, we show that a bounded submodularity ratio can be used
to provide data dependent bounds that can sometimes be tighter also for
submodular functions. We empirically validate our work by showing superior
performance of fast greedy approximations versus several established baselines
on artificial and real datasets.
On Approximation Guarantees for Greedy Low Rank Optimization
Authors: Rajiv Khanna, Ethan Elenberg, Alexandros G. Dimakis, Sahand Negahban
Date: 2017-03-08 00:00:00
Proceeding: ICML 2017 8
Tasks: Combinatorial Optimization

We provide new approximation guarantees for greedy low rank matrix estimation
under standard assumptions of restricted strong convexity and smoothness. Our
novel analysis also uncovers previously unknown connections between the low
rank estimation and combinatorial optimization, so much so that our bounds are
reminiscent of corresponding approximation bounds in submodular maximization.
Additionally, we also provide statistical recovery guarantees. Finally, we
present empirical comparison of greedy estimation with established baselines on
two important real-world problems.
Large Kernel Matters -- Improve Semantic Segmentation by Global Convolutional Network
Authors: Chao Peng, Xiangyu Zhang, Gang Yu, Guiming Luo, Jian Sun
Date: 2017-03-08 00:00:00
Proceeding: CVPR 2017 7
Tasks: Semantic Segmentation

One of recent trends [30, 31, 14] in network architec- ture design is
stacking small filters (e.g., 1x1 or 3x3) in the entire network because the
stacked small filters is more ef- ficient than a large kernel, given the same
computational complexity. However, in the field of semantic segmenta- tion,
where we need to perform dense per-pixel prediction, we find that the large
kernel (and effective receptive field) plays an important role when we have to
perform the clas- sification and localization tasks simultaneously. Following
our design principle, we propose a Global Convolutional Network to address both
the classification and localization issues for the semantic segmentation. We
also suggest a residual-based boundary refinement to further refine the ob-
ject boundaries. Our approach achieves state-of-art perfor- mance on two public
benchmarks and significantly outper- forms previous results, 82.2% (vs 80.2%)
on PASCAL VOC 2012 dataset and 76.9% (vs 71.8%) on Cityscapes dataset.
A Pursuit of Temporal Accuracy in General Activity Detection
Authors: Yuanjun Xiong, Yue Zhao, Li-Min Wang, Dahua Lin, Xiaoou Tang
Date: 2017-03-08 00:00:00
Tasks: Action Detection, Activity Detection, General Classification, Temporal Action Localization

Detecting activities in untrimmed videos is an important but challenging
task. The performance of existing methods remains unsatisfactory, e.g., they
often meet difficulties in locating the beginning and end of a long complex
action. In this paper, we propose a generic framework that can accurately
detect a wide variety of activities from untrimmed videos. Our first
contribution is a novel proposal scheme that can efficiently generate
candidates with accurate temporal boundaries. The other contribution is a
cascaded classification pipeline that explicitly distinguishes between
relevance and completeness of a candidate instance. On two challenging temporal
activity detection datasets, THUMOS14 and ActivityNet, the proposed framework
significantly outperforms the existing state-of-the-art methods, demonstrating
superior accuracy and strong adaptivity in handling activities with various
temporal structures.
Tree-Structured Reinforcement Learning for Sequential Object Localization
Authors: Zequn Jie, Xiaodan Liang, Jiashi Feng, Xiaojie Jin, Wen Feng Lu, Shuicheng Yan
Date: 2017-03-08 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Diversity, Object, Object Localization, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Existing object proposal algorithms usually search for possible object
regions over multiple locations and scales separately, which ignore the
interdependency among different objects and deviate from the human perception
procedure. To incorporate global interdependency between objects into object
localization, we propose an effective Tree-structured Reinforcement Learning
(Tree-RL) approach to sequentially search for objects by fully exploiting both
the current observation and historical search paths. The Tree-RL approach
learns multiple searching policies through maximizing the long-term reward that
reflects localization accuracies over all the objects. Starting with taking the
entire image as a proposal, the Tree-RL approach allows the agent to
sequentially discover multiple objects via a tree-structured traversing scheme.
Allowing multiple near-optimal policies, Tree-RL offers more diversity in
search paths and is able to find multiple objects with a single feed-forward
pass. Therefore, Tree-RL can better cover different objects with various scales
which is quite appealing in the context of object proposal. Experiments on
PASCAL VOC 2007 and 2012 validate the effectiveness of the Tree-RL, which can
achieve comparable recalls with current object proposal algorithms via much
fewer candidate windows.
Visual Search at Pinterest
Authors: Yushi Jing, David Liu, Dmitry Kislyuk, Andrew Zhai, Jiajing Xu, Jeff Donahue, Sarah Tavel
Date: 2015-05-28 00:00:00

We demonstrate that, with the availability of distributed computation
platforms such as Amazon Web Services and open-source tools, it is possible for
a small engineering team to build, launch and maintain a cost-effective,
large-scale visual search system with widely available tools. We also
demonstrate, through a comprehensive set of live experiments at Pinterest, that
content recommendation powered by visual search improve user engagement. By
sharing our implementation details and the experiences learned from launching a
commercial visual search engines from scratch, we hope visual search are more
widely incorporated into today's commercial applications.
Robust Adversarial Reinforcement Learning
Authors: Lerrel Pinto, James Davidson, Rahul Sukthankar, Abhinav Gupta
Date: 2017-03-08 00:00:00
Proceeding: ICML 2017 8
Tasks: Friction, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Deep neural networks coupled with fast simulation and improved computation
have led to recent successes in the field of reinforcement learning (RL).
However, most current RL-based approaches fail to generalize since: (a) the gap
between simulation and real world is so large that policy-learning approaches
fail to transfer; (b) even if policy learning is done in real world, the data
scarcity leads to failed generalization from training to test scenarios (e.g.,
due to different friction or object masses). Inspired from H-infinity control
methods, we note that both modeling errors and differences in training and test
scenarios can be viewed as extra forces/disturbances in the system. This paper
proposes the idea of robust adversarial reinforcement learning (RARL), where we
train an agent to operate in the presence of a destabilizing adversary that
applies disturbance forces to the system. The jointly trained adversary is
reinforced -- that is, it learns an optimal destabilization policy. We
formulate the policy learning as a zero-sum, minimax objective function.
Extensive experiments in multiple environments (InvertedPendulum, HalfCheetah,
Swimmer, Hopper and Walker2d) conclusively demonstrate that our method (a)
improves training stability; (b) is robust to differences in training/test
conditions; and c) outperform the baseline even in the absence of the
adversary.
Detecting Cancer Metastases on Gigapixel Pathology Images
Authors: Yun Liu, Krishna Gadepalli, Mohammad Norouzi, George E. Dahl, Timo Kohlberger, Aleksey Boyko, Subhashini Venugopalan, Aleksei Timofeev, Philip Q. Nelson, Greg S. Corrado, Jason D. Hipp, Lily Peng, Martin C. Stumpe
Date: 2017-03-03 00:00:00
Tasks: Medical Object Detection

Each year, the treatment decisions for more than 230,000 breast cancer
patients in the U.S. hinge on whether the cancer has metastasized away from the
breast. Metastasis detection is currently performed by pathologists reviewing
large expanses of biological tissues. This process is labor intensive and
error-prone. We present a framework to automatically detect and localize tumors
as small as 100 x 100 pixels in gigapixel microscopy images sized 100,000 x
100,000 pixels. Our method leverages a convolutional neural network (CNN)
architecture and obtains state-of-the-art results on the Camelyon16 dataset in
the challenging lesion-level tumor detection task. At 8 false positives per
image, we detect 92.4% of the tumors, relative to 82.7% by the previous best
automated approach. For comparison, a human pathologist attempting exhaustive
search achieved 73.2% sensitivity. We achieve image-level AUC scores above 97%
on both the Camelyon16 test set and an independent set of 110 slides. In
addition, we discover that two slides in the Camelyon16 training set were
erroneously labeled normal. Our approach could considerably reduce false
negative rates in metastasis detection.
Leveraging Sparsity for Efficient Submodular Data Summarization
Authors: Erik M. Lindgren, Shanshan Wu, Alexandros G. Dimakis
Date: 2017-03-08 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Clustering, Data Summarization, Image Retrieval, Retrieval

The facility location problem is widely used for summarizing large datasets
and has additional applications in sensor placement, image retrieval, and
clustering. One difficulty of this problem is that submodular optimization
algorithms require the calculation of pairwise benefits for all items in the
dataset. This is infeasible for large problems, so recent work proposed to only
calculate nearest neighbor benefits. One limitation is that several strong
assumptions were invoked to obtain provable approximation guarantees. In this
paper we establish that these extra assumptions are not necessary---solving the
sparsified problem will be almost optimal under the standard assumptions of the
problem. We then analyze a different method of sparsification that is a better
model for methods such as Locality Sensitive Hashing to accelerate the nearest
neighbor computations and extend the use of the problem to a broader family of
similarities. We validate our approach by demonstrating that it rapidly
generates interpretable summaries.
Exact MAP Inference by Avoiding Fractional Vertices
Authors: Erik M. Lindgren, Alexandros G. Dimakis, Adam Klivans
Date: 2017-03-08 00:00:00
Proceeding: ICML 2017 8
Tasks: Open-Ended Question Answering

Given a graphical model, one essential problem is MAP inference, that is,
finding the most likely configuration of states according to the model.
Although this problem is NP-hard, large instances can be solved in practice. A
major open question is to explain why this is true. We give a natural condition
under which we can provably perform MAP inference in polynomial time. We
require that the number of fractional vertices in the LP relaxation exceeding
the optimal solution is bounded by a polynomial in the problem size. This
resolves an open question by Dimakis, Gohari, and Wainwright. In contrast, for
general LP relaxations of integer programs, known techniques can only handle a
constant number of fractional vertices whose value exceeds the optimal
solution. We experimentally verify this condition and demonstrate how efficient
various integer programming methods are at removing fractional solutions.
Optimized Cost per Click in Taobao Display Advertising
Authors: Han Zhu, Junqi Jin, Chang Tan, Fei Pan, Yifan Zeng, Han Li, Kun Gai
Date: 2017-02-27 00:00:00

Taobao, as the largest online retail platform in the world, provides billions
of online display advertising impressions for millions of advertisers every
day. For commercial purposes, the advertisers bid for specific spots and target
crowds to compete for business traffic. The platform chooses the most suitable
ads to display in tens of milliseconds. Common pricing methods include cost per
mille (CPM) and cost per click (CPC). Traditional advertising systems target
certain traits of users and ad placements with fixed bids, essentially regarded
as coarse-grained matching of bid and traffic quality. However, the fixed bids
set by the advertisers competing for different quality requests cannot fully
optimize the advertisers' key requirements. Moreover, the platform has to be
responsible for the business revenue and user experience. Thus, we proposed a
bid optimizing strategy called optimized cost per click (OCPC) which
automatically adjusts the bid to achieve finer matching of bid and traffic
quality of page view (PV) request granularity. Our approach optimizes
advertisers' demands, platform business revenue and user experience and as a
whole improves traffic allocation efficiency. We have validated our approach in
Taobao display advertising system in production. The online A/B test shows our
algorithm yields substantially better results than previous fixed bid manner.
Sparse Quadratic Logistic Regression in Sub-quadratic Time
Authors: Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G. Dimakis, Sujay Sanghavi
Date: 2017-03-08 00:00:00
Tasks: regression

We consider support recovery in the quadratic logistic regression setting -
where the target depends on both p linear terms $x_i$ and up to $p^2$ quadratic
terms $x_i x_j$. Quadratic terms enable prediction/modeling of higher-order
effects between features and the target, but when incorporated naively may
involve solving a very large regression problem. We consider the sparse case,
where at most $s$ terms (linear or quadratic) are non-zero, and provide a new
faster algorithm. It involves (a) identifying the weak support (i.e. all
relevant variables) and (b) standard logistic regression optimization only on
these chosen variables. The first step relies on a novel insight about
correlation tests in the presence of non-linearity, and takes $O(pn)$ time for
$n$ samples - giving potentially huge computational gains over the naive
approach. Motivated by insights from the boolean case, we propose a non-linear
correlation test for non-binary finite support case that involves hashing a
variable and then correlating with the output variable. We also provide
experimental results to demonstrate the effectiveness of our methods.
Performance Bounds for Graphical Record Linkage
Authors: Rebecca C. Steorts, Matt Barnes, Willie Neiswanger
Date: 2017-03-08 00:00:00
Tasks: Clustering

Record linkage involves merging records in large, noisy databases to remove
duplicate entities. It has become an important area because of its widespread
occurrence in bibliometrics, public health, official statistics production,
political science, and beyond. Traditional linkage methods directly linking
records to one another are computationally infeasible as the number of records
grows. As a result, it is increasingly common for researchers to treat record
linkage as a clustering task, in which each latent entity is associated with
one or more noisy database records. We critically assess performance bounds
using the Kullback-Leibler (KL) divergence under a Bayesian record linkage
framework, making connections to Kolchin partition models. We provide an upper
bound using the KL divergence and a lower bound on the minimum probability of
misclassifying a latent entity. We give insights for when our bounds hold using
simulated data and provide practical user guidance.
Probing the Geometry of Data with Diffusion Fréchet Functions
Authors: Diego Hernán Díaz Martínez, Christine H. Lee, Peter T. Kim, Washington Mio
Date: 2016-05-16 00:00:00

Many complex ecosystems, such as those formed by multiple microbial taxa,
involve intricate interactions amongst various sub-communities. The most basic
relationships are frequently modeled as co-occurrence networks in which the
nodes represent the various players in the community and the weighted edges
encode levels of interaction. In this setting, the composition of a community
may be viewed as a probability distribution on the nodes of the network. This
paper develops methods for modeling the organization of such data, as well as
their Euclidean counterparts, across spatial scales. Using the notion of
diffusion distance, we introduce diffusion Frechet functions and diffusion
Frechet vectors associated with probability distributions on Euclidean space
and the vertex set of a weighted network, respectively. We prove that these
functional statistics are stable with respect to the Wasserstein distance
between probability measures, thus yielding robust descriptors of their shapes.
We apply the methodology to investigate bacterial communities in the human gut,
seeking to characterize divergence from intestinal homeostasis in patients with
Clostridium difficile infection (CDI) and the effects of fecal microbiota
transplantation, a treatment used in CDI patients that has proven to be
significantly more effective than traditional treatment with antibiotics. The
proposed method proves useful in deriving a biomarker that might help elucidate
the mechanisms that drive these processes.
A Novel Weight-Shared Multi-Stage CNN for Scale Robustness
Authors: Ryo Takahashi, Takashi Matsubara, Kuniaki Uehara
Date: 2017-02-12 00:00:00
Tasks: General Classification, image-classification, Image Classification

Convolutional neural networks (CNNs) have demonstrated remarkable results in
image classification for benchmark tasks and practical applications. The CNNs
with deeper architectures have achieved even higher performance recently thanks
to their robustness to the parallel shift of objects in images as well as their
numerous parameters and the resulting high expression ability. However, CNNs
have a limited robustness to other geometric transformations such as scaling
and rotation. This limits the performance improvement of the deep CNNs, but
there is no established solution. This study focuses on scale transformation
and proposes a network architecture called the weight-shared multi-stage
network (WSMS-Net), which consists of multiple stages of CNNs. The proposed
WSMS-Net is easily combined with existing deep CNNs such as ResNet and DenseNet
and enables them to acquire robustness to object scaling. Experimental results
on the CIFAR-10, CIFAR-100, and ImageNet datasets demonstrate that existing
deep CNNs combined with the proposed WSMS-Net achieve higher accuracies for
image classification tasks with only a minor increase in the number of
parameters and computation time.