pwc-archive/papers-with-abstracts huggingface dataset:
Estimating Total Search Space Size for Specific Piece Sets in Chess
Authors: Azlan Iqbal
Date: 2018-02-27 00:00:00

Automatic chess problem or puzzle composition typically involves generating
and testing various different positions, sometimes using particular piece sets.
Once a position has been generated, it is then usually tested for positional
legality based on the game rules. However, it is useful to be able to estimate
what the search space size for particular piece combinations is to begin with.
So if a desirable chess problem was successfully generated by examining
'merely' 100,000 or so positions in a theoretical search space of about 100
billion, this would imply the composing approach used was quite viable and
perhaps even impressive. In this article, I explain a method of calculating the
size of this search space using a combinatorics and permutations approach.
While the mathematics itself may already be established, a precise method and
justification of applying it with regard to the chessboard and chess pieces has
not been documented, to the best of our knowledge. Additionally, the method
could serve as a useful starting point for further estimations of search space
size which filter out positions for legality and rotation, depending on how the
automatic composer is allowed to place pieces on the board (because this
affects its total search space size).
Generalized Binary Search For Split-Neighborly Problems
Authors: Stephen Mussmann, Percy Liang
Date: 2018-02-27 00:00:00
Tasks: Two-sample testing

In sequential hypothesis testing, Generalized Binary Search (GBS) greedily
chooses the test with the highest information gain at each step. It is known
that GBS obtains the gold standard query cost of $O(\log n)$ for problems
satisfying the $k$-neighborly condition, which requires any two tests to be
connected by a sequence of tests where neighboring tests disagree on at most
$k$ hypotheses. In this paper, we introduce a weaker condition,
split-neighborly, which requires that for the set of hypotheses two neighbors
disagree on, any subset is splittable by some test. For four problems that are
not $k$-neighborly for any constant $k$, we prove that they are
split-neighborly, which allows us to obtain the optimal $O(\log n)$ worst-case
query cost.
Federated Multi-Task Learning
Authors: Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, Ameet Talwalkar
Date: 2017-05-30 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: BIG-bench Machine Learning, Federated Learning, Multi-Task Learning

Federated learning poses new statistical and systems challenges in training
machine learning models over distributed networks of devices. In this work, we
show that multi-task learning is naturally suited to handle the statistical
challenges of this setting, and propose a novel systems-aware optimization
method, MOCHA, that is robust to practical systems issues. Our method and
theory for the first time consider issues of high communication cost,
stragglers, and fault tolerance for distributed multi-task learning. The
resulting method achieves significant speedups compared to alternatives in the
federated setting, as we demonstrate through simulations on real-world
federated datasets.
Train Feedfoward Neural Network with Layer-wise Adaptive Rate via Approximating Back-matching Propagation
Authors: Huishuai Zhang, Wei Chen, Tie-Yan Liu
Date: 2018-02-27 00:00:00

Stochastic gradient descent (SGD) has achieved great success in training deep
neural network, where the gradient is computed through back-propagation.
However, the back-propagated values of different layers vary dramatically. This
inconsistence of gradient magnitude across different layers renders
optimization of deep neural network with a single learning rate problematic. We
introduce the back-matching propagation which computes the backward values on
the layer's parameter and the input by matching backward values on the layer's
output. This leads to solving a bunch of least-squares problems, which requires
high computational cost. We then reduce the back-matching propagation with
approximations and propose an algorithm that turns to be the regular SGD with a
layer-wise adaptive learning rate strategy. This allows an easy implementation
of our algorithm in current machine learning frameworks equipped with
auto-differentiation. We apply our algorithm in training modern deep neural
networks and achieve favorable results over SGD.
Accelerating Asynchronous Algorithms for Convex Optimization by Momentum Compensation
Authors: Cong Fang, Yameng Huang, Zhouchen Lin
Date: 2018-02-27 00:00:00

Asynchronous algorithms have attracted much attention recently due to the
crucial demands on solving large-scale optimization problems. However, the
accelerated versions of asynchronous algorithms are rarely studied. In this
paper, we propose the "momentum compensation" technique to accelerate
asynchronous algorithms for convex problems. Specifically, we first accelerate
the plain Asynchronous Gradient Descent, which achieves a faster
$O(1/\sqrt{\epsilon})$ (v.s. $O(1/\epsilon)$) convergence rate for non-strongly
convex functions, and $O(\sqrt{\kappa}\log(1/\epsilon))$ (v.s. $O(\kappa
\log(1/\epsilon))$) for strongly convex functions to reach an $\epsilon$-
approximate minimizer with the condition number $\kappa$. We further apply the
technique to accelerate modern stochastic asynchronous algorithms such as
Asynchronous Stochastic Coordinate Descent and Asynchronous Stochastic Gradient
Descent. Both of the resultant practical algorithms are faster than existing
ones by order. To the best of our knowledge, we are the first to consider
accelerated algorithms that allow updating by delayed gradients and are the
first to propose truly accelerated asynchronous algorithms. Finally, the
experimental results on a shared memory system show that acceleration can lead
to significant performance gains on ill-conditioned problems.
Surrogate Model Assisted Cooperative Coevolution for Large Scale Optimization
Authors: Zhigang Ren, Bei Pang, Yongsheng Liang, An Chen, Yi-Peng Zhang
Date: 2018-02-27 00:00:00

It has been shown that cooperative coevolution (CC) can effectively deal with
large scale optimization problems (LSOPs) through a divide-and-conquer
strategy. However, its performance is severely restricted by the current
context-vector-based sub-solution evaluation method since this method needs to
access the original high dimensional simulation model when evaluating each
sub-solution and thus requires many computation resources. To alleviate this
issue, this study proposes a novel surrogate model assisted cooperative
coevolution (SACC) framework. SACC constructs a surrogate model for each
sub-problem obtained via decomposition and employs it to evaluate corresponding
sub-solutions. The original simulation model is only adopted to reevaluate some
good sub-solutions selected by surrogate models, and these real evaluated
sub-solutions will be in turn employed to update surrogate models. By this
means, the computation cost could be greatly reduced without significantly
sacrificing evaluation quality. To show the efficiency of SACC, this study uses
radial basis function (RBF) and success-history based adaptive differential
evolution (SHADE) as surrogate model and optimizer, respectively. RBF and SHADE
have been proved to be effective on small and medium scale problems. This study
first scales them up to LSOPs of 1000 dimensions under the SACC framework,
where they are tailored to a certain extent for adapting to the characteristics
of LSOP and SACC. Empirical studies on IEEE CEC 2010 benchmark functions
demonstrate that SACC significantly enhances the evaluation efficiency on
sub-solutions, and even with much fewer computation resource, the resultant
RBF-SHADE-SACC algorithm is able to find much better solutions than traditional
CC algorithms.
ReHAR: Robust and Efficient Human Activity Recognition
Authors: Xin Li, Mooi Choo Chuah
Date: 2018-02-27 00:00:00
Tasks: Activity Recognition, Human Activity Recognition, Optical Flow Estimation

Designing a scheme that can achieve a good performance in predicting single
person activities and group activities is a challenging task. In this paper, we
propose a novel robust and efficient human activity recognition scheme called
ReHAR, which can be used to handle single person activities and group
activities prediction. First, we generate an optical flow image for each video
frame. Then, both video frames and their corresponding optical flow images are
fed into a Single Frame Representation Model to generate representations.
Finally, an LSTM is used to pre- dict the final activities based on the
generated representations. The whole model is trained end-to-end to allow
meaningful representations to be generated for the final activity recognition.
We evaluate ReHAR using two well-known datasets: the NCAA Basketball Dataset
and the UCFSports Action Dataset. The experimental results show that the pro-
posed ReHAR achieves a higher activity recognition accuracy with an order of
magnitude shorter computation time compared to the state-of-the-art methods.
Salient Object Detection: A Benchmark
Authors: Ali Borji, Ming-Ming Cheng, Huaizu Jiang, Jia Li
Date: 2015-01-05 00:00:00
Tasks: Benchmarking, Object, object-detection, Object Detection, RGB Salient Object Detection, Salient Object Detection

We extensively compare, qualitatively and quantitatively, 40 state-of-the-art
models (28 salient object detection, 10 fixation prediction, 1 objectness, and
1 baseline) over 6 challenging datasets for the purpose of benchmarking salient
object detection and segmentation methods. From the results obtained so far,
our evaluation shows a consistent rapid progress over the last few years in
terms of both accuracy and running time. The top contenders in this benchmark
significantly outperform the models identified as the best in the previous
benchmark conducted just two years ago. We find that the models designed
specifically for salient object detection generally work better than models in
closely related areas, which in turn provides a precise definition and suggests
an appropriate treatment of this problem that distinguishes it from other
problems. In particular, we analyze the influences of center bias and scene
complexity in model performance, which, along with the hard cases for
state-of-the-art models, provide useful hints towards constructing more
challenging large scale datasets and better saliency models. Finally, we
propose probable solutions for tackling several open problems such as
evaluation scores and dataset bias, which also suggest future research
directions in the rapidly-growing field of salient object detection.
Cognitive Radar Antenna Selection via Deep Learning
Authors: Ahmet M. Elbir, Kumar Vijay Mishra, Yonina C. Eldar
Date: 2018-02-27 00:00:00
Tasks: Deep Learning, General Classification, Multi-class Classification

Direction of arrival (DoA) estimation of targets improves with the number of
elements employed by a phased array radar antenna. Since larger arrays have
high associated cost, area and computational load, there is recent interest in
thinning the antenna arrays without loss of far-field DoA accuracy. In this
context, a cognitive radar may deploy a full array and then select an optimal
subarray to transmit and receive the signals in response to changes in the
target environment. Prior works have used optimization and greedy search
methods to pick the best subarrays cognitively. In this paper, we leverage deep
learning to address the antenna selection problem. Specifically, we construct a
convolutional neural network (CNN) as a multi-class classification framework
where each class designates a different subarray. The proposed network
determines a new array every time data is received by the radar, thereby making
antenna selection a cognitive operation. Our numerical experiments show that
{the proposed CNN structure provides 22% better classification performance than
a Support Vector Machine and the resulting subarrays yield 72% more accurate
DoA estimates than random array selections.
Reinforcement Mechanism Design for e-commerce
Authors: Qingpeng Cai, Aris Filos-Ratsikas, Pingzhong Tang, Yiwei Zhang
Date: 2017-08-25 00:00:00
Tasks: Deep Reinforcement Learning, Reinforcement Learning

We study the problem of allocating impressions to sellers in e-commerce
websites, such as Amazon, eBay or Taobao, aiming to maximize the total revenue
generated by the platform. We employ a general framework of reinforcement
mechanism design, which uses deep reinforcement learning to design efficient
algorithms, taking the strategic behaviour of the sellers into account.
Specifically, we model the impression allocation problem as a Markov decision
process, where the states encode the history of impressions, prices,
transactions and generated revenue and the actions are the possible impression
allocations in each round. To tackle the problem of continuity and
high-dimensionality of states and actions, we adopt the ideas of the DDPG
algorithm to design an actor-critic policy gradient algorithm which takes
advantage of the problem domain in order to achieve convergence and stability.
We evaluate our proposed algorithm, coined IA(GRU), by comparing it against
DDPG, as well as several natural heuristics, under different rationality models
for the sellers - we assume that sellers follow well-known no-regret type
strategies which may vary in their degree of sophistication. We find that
IA(GRU) outperforms all algorithms in terms of the total revenue.
Online learning with kernel losses
Authors: Aldo Pacchiano, Niladri S. Chatterji, Peter L. Bartlett
Date: 2018-02-27 00:00:00

We present a generalization of the adversarial linear bandits framework,
where the underlying losses are kernel functions (with an associated
reproducing kernel Hilbert space) rather than linear functions. We study a
version of the exponential weights algorithm and bound its regret in this
setting. Under conditions on the eigendecay of the kernel we provide a sharp
characterization of the regret for this algorithm. When we have polynomial
eigendecay $\mu_j \le \mathcal{O}(j^{-\beta})$, we find that the regret is
bounded by $\mathcal{R}_n \le \mathcal{O}(n^{\beta/(2(\beta-1))})$; while under
the assumption of exponential eigendecay $\mu_j \le \mathcal{O}(e^{-\beta j
})$, we get an even tighter bound on the regret $\mathcal{R}_n \le
\mathcal{O}(n^{1/2}\log(n)^{1/2})$. We also study the full information setting
when the underlying losses are kernel functions and present an adapted
exponential weights algorithm and a conditional gradient descent algorithm.
Network-Clustered Multi-Modal Bug Localization
Authors: Thong Hoang, Richard J. Oentaryo, Tien-Duy B. Le, David Lo
Date: 2018-02-27 00:00:00
Tasks: Clustering, Information Retrieval, Retrieval

Developers often spend much effort and resources to debug a program. To help
the developers debug, numerous information retrieval (IR)-based and
spectrum-based bug localization techniques have been devised. IR-based
techniques process textual information in bug reports, while spectrum-based
techniques process program spectra (i.e., a record of which program elements
are executed for each test case). While both techniques ultimately generate a
ranked list of program elements that likely contain a bug, they only consider
one source of information--either bug reports or program spectra--which is not
optimal. In light of this deficiency, this paper presents a new approach dubbed
Network-clustered Multi-modal Bug Localization (NetML), which utilizes
multi-modal information from both bug reports and program spectra to localize
bugs. NetML facilitates an effective bug localization by carrying out a joint
optimization of bug localization error and clustering of both bug reports and
program elements (i.e., methods). The clustering is achieved through the
incorporation of network Lasso regularization, which incentivizes the model
parameters of similar bug reports and similar program elements to be close
together. To estimate the model parameters of both bug reports and methods,
NetML employs an adaptive learning procedure based on Newton method that
updates the parameters on a per-feature basis. Extensive experiments on 355
real bugs from seven software systems have been conducted to benchmark NetML
against various state-of-the-art localization methods. The results show that
NetML surpasses the best-performing baseline by 31.82%, 22.35%, 19.72%, and
19.24%, in terms of the number of bugs successfully localized when a developer
inspects the top 1, 5, and 10 methods and Mean Average Precision (MAP),
respectively.
High-dimensional ABC
Authors: D. J. Nott, V. M. -H. Ong, Y. Fan, S. A. Sisson
Date: 2018-02-27 00:00:00
Tasks: Vocal Bursts Intensity Prediction

This Chapter, "High-dimensional ABC", is to appear in the forthcoming
Handbook of Approximate Bayesian Computation (2018). It details the main ideas
and concepts behind extending ABC methods to higher dimensions, with supporting
examples and illustrations.
Supervised Dimensionality Reduction for Big Data
Authors: Joshua T. Vogelstein, Eric Bridgeford, Minh Tang, Da Zheng, Christopher Douville, Randal Burns, Mauro Maggioni
Date: 2017-09-05 00:00:00
Tasks: Computational Efficiency, Dimensionality Reduction, General Classification, Supervised dimensionality reduction, valid

To solve key biomedical problems, experimentalists now routinely measure millions or billions of features (dimensions) per sample, with the hope that data science techniques will be able to build accurate data-driven inferences. Because sample sizes are typically orders of magnitude smaller than the dimensionality of these data, valid inferences require finding a low-dimensional representation that preserves the discriminating information (e.g., whether the individual suffers from a particular disease). There is a lack of interpretable supervised dimensionality reduction methods that scale to millions of dimensions with strong statistical theoretical guarantees.We introduce an approach, XOX, to extending principal components analysis by incorporating class-conditional moment estimates into the low-dimensional projection. The simplest ver-sion, "Linear Optimal Low-rank" projection (LOL), incorporates the class-conditional means. We prove, and substantiate with both synthetic and real data benchmarks, that LOL and its generalizations in the XOX framework lead to improved data representations for subsequent classification, while maintaining computational efficiency and scalability. Using multiple brain imaging datasets consisting of >150 million features, and several genomics datasets with>500,000 features, LOL outperforms other scalable linear dimensionality reduction techniques in terms of accuracy, while only requiring a few minutes on a standard desktop computer.
Recurrent Residual Module for Fast Inference in Videos
Authors: Bowen Pan, Wuwei Lin, Xiaolin Fang, Chaoqin Huang, Bolei Zhou, Cewu Lu
Date: 2018-02-27 00:00:00
Proceeding: CVPR 2018 6
Tasks: object-detection, Object Detection, Pose Estimation, Video Object Detection, Video Recognition

Deep convolutional neural networks (CNNs) have made impressive progress in
many video recognition tasks such as video pose estimation and video object
detection. However, CNN inference on video is computationally expensive due to
processing dense frames individually. In this work, we propose a framework
called Recurrent Residual Module (RRM) to accelerate the CNN inference for
video recognition tasks. This framework has a novel design of using the
similarity of the intermediate feature maps of two consecutive frames, to
largely reduce the redundant computation. One unique property of the proposed
method compared to previous work is that feature maps of each frame are
precisely computed. The experiments show that, while maintaining the similar
recognition performance, our RRM yields averagely 2x acceleration on the
commonly used CNNs such as AlexNet, ResNet, deep compression model (thus 8-12x
faster than the original dense models using the efficient inference engine),
and impressively 9x acceleration on some binary networks such as XNOR-Nets
(thus 500x faster than the original model). We further verify the effectiveness
of the RRM on speeding up CNNs for video pose estimation and video object
detection.
Overview of Approximate Bayesian Computation
Authors: S. A. Sisson, Y. Fan, M. A. Beaumont
Date: 2018-02-27 00:00:00

This Chapter, "Overview of Approximate Bayesian Computation", is to appear as
the first chapter in the forthcoming Handbook of Approximate Bayesian
Computation (2018). It details the main ideas and concepts behind ABC methods
with many examples and illustrations.
Robust Actor-Critic Contextual Bandit for Mobile Health (mHealth) Interventions
Authors: Feiyun Zhu, Jun Guo, Ruoyu Li, Junzhou Huang
Date: 2018-02-27 00:00:00
Tasks: Decision Making

We consider the actor-critic contextual bandit for the mobile health
(mHealth) intervention. State-of-the-art decision-making algorithms generally
ignore the outliers in the dataset. In this paper, we propose a novel robust
contextual bandit method for the mHealth. It can achieve the conflicting goal
of reducing the influence of outliers while seeking for a similar solution
compared with the state-of-the-art contextual bandit methods on the datasets
without outliers. Such performance relies on two technologies: (1) the
capped-$\ell_{2}$ norm; (2) a reliable method to set the thresholding
hyper-parameter, which is inspired by one of the most fundamental techniques in
the statistics. Although the model is non-convex and non-differentiable, we
propose an effective reweighted algorithm and provide solid theoretical
analyses. We prove that the proposed algorithm can find sufficiently decreasing
points after each iteration and finally converges after a finite number of
iterations. Extensive experiment results on two datasets demonstrate that our
method can achieve almost identical results compared with state-of-the-art
contextual bandit methods on the dataset without outliers, and significantly
outperform those state-of-the-art methods on the badly noised dataset with
outliers in a variety of parameter settings.
Multi-Oriented Scene Text Detection via Corner Localization and Region Segmentation
Authors: Pengyuan Lyu, Cong Yao, Wenhao Wu, Shuicheng Yan, Xiang Bai
Date: 2018-02-25 00:00:00
Proceeding: CVPR 2018 6
Tasks: Multi-Oriented Scene Text Detection, object-detection, Object Detection, Scene Text Detection, Text Detection

Previous deep learning based state-of-the-art scene text detection methods
can be roughly classified into two categories. The first category treats scene
text as a type of general objects and follows general object detection paradigm
to localize scene text by regressing the text box locations, but troubled by
the arbitrary-orientation and large aspect ratios of scene text. The second one
segments text regions directly, but mostly needs complex post processing. In
this paper, we present a method that combines the ideas of the two types of
methods while avoiding their shortcomings. We propose to detect scene text by
localizing corner points of text bounding boxes and segmenting text regions in
relative positions. In inference stage, candidate boxes are generated by
sampling and grouping corner points, which are further scored by segmentation
maps and suppressed by NMS. Compared with previous methods, our method can
handle long oriented text naturally and doesn't need complex post processing.
The experiments on ICDAR2013, ICDAR2015, MSRA-TD500, MLT and COCO-Text
demonstrate that the proposed algorithm achieves better or comparable results
in both accuracy and efficiency. Based on VGG16, it achieves an F-measure of
84.3% on ICDAR2015 and 81.5% on MSRA-TD500.