pwc-archive/papers-with-abstracts huggingface dataset:
SECTOR: A Neural Model for Coherent Topic Segmentation and Classification
Authors: Sebastian Arnold, Rudolf Schneider, Philippe Cudré-Mauroux, Felix A. Gers, Alexander Löser
Date: 2019-02-13 00:00:00
Proceeding: TACL 2019 3
Tasks: Classification, General Classification, Reading Comprehension, Segmentation

When searching for information, a human reader first glances over a document,
spots relevant sections and then focuses on a few sentences for resolving her
intention. However, the high variance of document structure complicates to
identify the salient topic of a given section at a glance. To tackle this
challenge, we present SECTOR, a model to support machine reading systems by
segmenting documents into coherent sections and assigning topic labels to each
section. Our deep neural network architecture learns a latent topic embedding
over the course of a document. This can be leveraged to classify local topics
from plain text and segment a document at topic shifts. In addition, we
contribute WikiSection, a publicly available dataset with 242k labeled sections
in English and German from two distinct domains: diseases and cities. From our
extensive evaluation of 20 architectures, we report a highest score of 71.6% F1
for the segmentation and classification of 30 topics from the English city
domain, scored by our SECTOR LSTM model with bloom filter embeddings and
bidirectional segmentation. This is a significant improvement of 29.5 points F1
compared to state-of-the-art CNN classifiers with baseline segmentation.
On the Expressive Power of Kernel Methods and the Efficiency of Kernel Learning by Association Schemes
Authors: Pravesh K. Kothari, Roi Livni
Date: 2019-02-13 00:00:00

We study the expressive power of kernel methods and the algorithmic
feasibility of multiple kernel learning for a special rich class of kernels.
  Specifically, we define \emph{Euclidean kernels}, a diverse class that
includes most, if not all, families of kernels studied in literature such as
polynomial kernels and radial basis functions. We then describe the geometric
and spectral structure of this family of kernels over the hypercube (and to
some extent for any compact domain). Our structural results allow us to prove
meaningful limitations on the expressive power of the class as well as derive
several efficient algorithms for learning kernels over different domains.
Sample-Optimal Parametric Q-Learning Using Linearly Additive Features
Authors: Lin F. Yang, Mengdi Wang
Date: 2019-02-13 00:00:00
Tasks: Q-Learning

Consider a Markov decision process (MDP) that admits a set of state-action features, which can linearly express the process's probabilistic transition model. We propose a parametric Q-learning algorithm that finds an approximate-optimal policy using a sample size proportional to the feature dimension $K$ and invariant with respect to the size of the state space. To further improve its sample efficiency, we exploit the monotonicity property and intrinsic noise structure of the Bellman operator, provided the existence of anchor state-actions that imply implicit non-negativity in the feature space. We augment the algorithm using techniques of variance reduction, monotonicity preservation, and confidence bounds. It is proved to find a policy which is $\epsilon$-optimal from any initial state with high probability using $\widetilde{O}(K/\epsilon^2(1-\gamma)^3)$ sample transitions for arbitrarily large-scale MDP with a discount factor $\gamma\in(0,1)$. A matching information-theoretical lower bound is proved, confirming the sample optimality of the proposed method with respect to all parameters (up to polylog factors).
Distributed Online Linear Regression
Authors: Deming Yuan, Alexandre Proutiere, Guodong Shi
Date: 2019-02-13 00:00:00
Tasks: regression

We study online linear regression problems in a distributed setting, where
the data is spread over a network. In each round, each network node proposes a
linear predictor, with the objective of fitting the \emph{network-wide} data.
It then updates its predictor for the next round according to the received
local feedback and information received from neighboring nodes. The predictions
made at a given node are assessed through the notion of regret, defined as the
difference between their cumulative network-wide square errors and those of the
best off-line network-wide linear predictor. Various scenarios are
investigated, depending on the nature of the local feedback (full information
or bandit feedback), on the set of available predictors (the decision set), and
the way data is generated (by an oblivious or adaptive adversary). We propose
simple and natural distributed regression algorithms, involving, at each node
and in each round, a local gradient descent step and a communication and
averaging step where nodes aim at aligning their predictors to those of their
neighbors. We establish regret upper bounds typically in ${\cal O}(T^{3/4})$
when the decision set is unbounded and in ${\cal O}(\sqrt{T})$ in case of
bounded decision set.
Efficient Cross-Validation for Semi-Supervised Learning
Authors: Yong Liu, Jian Li, Guangjun Wu, Lizhong Ding, Weiping Wang
Date: 2019-02-13 00:00:00
Tasks: Model Selection

Manifold regularization, such as laplacian regularized least squares (LapRLS)
and laplacian support vector machine (LapSVM), has been widely used in
semi-supervised learning, and its performance greatly depends on the choice of
some hyper-parameters. Cross-validation (CV) is the most popular approach for
selecting the optimal hyper-parameters, but it has high complexity due to
multiple times of learner training. In this paper, we provide a method to
approximate the CV for manifold regularization based on a notion of robust
statistics, called Bouligand influence function (BIF). We first provide a
strategy for approximating the CV via the Taylor expansion of BIF. Then, we
show how to calculate the BIF for general loss function,and further give the
approximate CV criteria for model selection in manifold regularization. The
proposed approximate CV for manifold regularization requires training only
once, hence can significantly improve the efficiency of traditional CV.
Experimental results show that our approximate CV has no statistical
discrepancy with the original one, but much smaller time cost.
Evolutionary Algorithms for the Chance-Constrained Knapsack Problem
Authors: Yue Xie, Oscar Harper, Hirad Assimi, Aneta Neumann, Frank Neumann
Date: 2019-02-13 00:00:00
Tasks: Evolutionary Algorithms, Stochastic Optimization

Evolutionary algorithms have been applied to a wide range of stochastic problems. Motivated by real-world problems where constraint violations have disruptive effects, this paper considers the chance-constrained knapsack problem (CCKP) which is a variance of the binary knapsack problem. The problem aims to maximize the profit of selected items under a constraint that the knapsack capacity bound is violated with a small probability. To tackle the chance constraint, we introduce how to construct surrogate functions by applying well-known deviation inequalities such as Chebyshev's inequality and Chernoff bounds. Furthermore, we investigate the performance of several deterministic approaches and introduce a single- and multi-objective evolutionary algorithm to solve the CCKP. In the experiment section, we evaluate and compare the deterministic approaches and evolutionary algorithms on a wide range of instances. Our experimental results show that a multi-objective evolutionary algorithm outperforms its single-objective formulation for all instances and performance better than deterministic approaches according to the computation time. Furthermore, our investigation points out in which circumstances to favour Chebyshev's inequality or the Chernoff bound when dealing with the CCKP.
Wireless Traffic Prediction with Scalable Gaussian Process: Framework, Algorithms, and Verification
Authors: Yue Xu, Feng Yin, Wenjun Xu, Jia-Ru Lin, Shuguang Cui
Date: 2019-02-13 00:00:00
Tasks: Prediction, regression, Traffic Prediction

The cloud radio access network (C-RAN) is a promising paradigm to meet the
stringent requirements of the fifth generation (5G) wireless systems.
Meanwhile, wireless traffic prediction is a key enabler for C-RANs to improve
both the spectrum efficiency and energy efficiency through load-aware network
managements. This paper proposes a scalable Gaussian process (GP) framework as
a promising solution to achieve large-scale wireless traffic prediction in a
cost-efficient manner. Our contribution is three-fold. First, to the best of
our knowledge, this paper is the first to empower GP regression with the
alternating direction method of multipliers (ADMM) for parallel hyper-parameter
optimization in the training phase, where such a scalable training framework
well balances the local estimation in baseband units (BBUs) and information
consensus among BBUs in a principled way for large-scale executions. Second, in
the prediction phase, we fuse local predictions obtained from the BBUs via a
cross-validation based optimal strategy, which demonstrates itself to be
reliable and robust for general regression tasks. Moreover, such a
cross-validation based optimal fusion strategy is built upon a well
acknowledged probabilistic model to retain the valuable closed-form GP
inference properties. Third, we propose a C-RAN based scalable wireless
prediction architecture, where the prediction accuracy and the time consumption
can be balanced by tuning the number of the BBUs according to the real-time
system demands. Experimental results show that our proposed scalable GP model
can outperform the state-of-the-art approaches considerably, in terms of
wireless traffic prediction performance.
Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
Authors: Greg Yang
Date: 2019-02-13 00:00:00
Tasks: Gaussian Processes, Learning Theory

Several recent trends in machine learning theory and practice, from the design of state-of-the-art Gaussian Process to the convergence analysis of deep neural nets (DNNs) under stochastic gradient descent (SGD), have found it fruitful to study wide random neural networks. Central to these approaches are certain scaling limits of such networks. We unify these results by introducing a notion of a straightline \emph{tensor program} that can express most neural network computations, and we characterize its scaling limit when its tensors are large and randomized. From our framework follows (1) the convergence of random neural networks to Gaussian processes for architectures such as recurrent neural networks, convolutional neural networks, residual networks, attention, and any combination thereof, with or without batch normalization; (2) conditions under which the \emph{gradient independence assumption} -- that weights in backpropagation can be assumed to be independent from weights in the forward pass -- leads to correct computation of gradient dynamics, and corrections when it does not; (3) the convergence of the Neural Tangent Kernel, a recently proposed kernel used to predict training dynamics of neural networks under gradient descent, at initialization for all architectures in (1) without batch normalization. Mathematically, our framework is general enough to rederive classical random matrix results such as the semicircle and the Marchenko-Pastur laws, as well as recent results in neural network Jacobian singular values. We hope our work opens a way toward design of even stronger Gaussian Processes, initialization schemes to avoid gradient explosion/vanishing, and deeper understanding of SGD dynamics in modern architectures.
Multi-Prototype Networks for Unconstrained Set-based Face Recognition
Authors: Jian Zhao, Jianshu Li, Xiaoguang Tu, Fang Zhao, Yuan Xin, Junliang Xing, Hengzhu Liu, Shuicheng Yan, Jiashi Feng
Date: 2019-02-13 00:00:00
Tasks: Face Recognition

In this paper, we study the challenging unconstrained set-based face
recognition problem where each subject face is instantiated by a set of media
(images and videos) instead of a single image. Naively aggregating information
from all the media within a set would suffer from the large intra-set variance
caused by heterogeneous factors (e.g., varying media modalities, poses and
illuminations) and fail to learn discriminative face representations. A novel
Multi-Prototype Network (MPNet) model is thus proposed to learn multiple
prototype face representations adaptively from the media sets. Each learned
prototype is representative for the subject face under certain condition in
terms of pose, illumination and media modality. Instead of handcrafting the set
partition for prototype learning, MPNet introduces a Dense SubGraph (DSG)
learning sub-net that implicitly untangles inconsistent media and learns a
number of representative prototypes. Qualitative and quantitative experiments
clearly demonstrate superiority of the proposed model over state-of-the-arts.
The parallel texts of books translations in the quality evaluation of basic models and algorithms for the similarity of symbol strings
Authors: Sergej V. Znamenskij
Date: 2018-05-24 00:00:00
Tasks: Translation

This numeric evaluation of string metric accuracy is based on the following
idea: taking the paragraph of text in one language sort all paragraphs of the
document in other language by similarity with given paragraph string and
consider place of the right translation as the value of the evaluation score.
Such a search of proper translation provides an objective and reproducible
quality assessment for known similarity metrics and shows the most accurate
ones.
Session-based Sequential Skip Prediction via Recurrent Neural Networks
Authors: Lin Zhu, Yihong Chen
Date: 2019-02-13 00:00:00
Tasks: Prediction, Sequential skip prediction, Session-Based Recommendations

The focus of WSDM cup 2019 is session-based sequential skip prediction, i.e.
predicting whether users will skip tracks, given their immediately preceding
interactions in their listening session. This paper provides the solution of
our team \textbf{ekffar} to this challenge. We focus on
recurrent-neural-network-based deep learning approaches which have previously
been shown to perform well on session-based recommendation problems. We show
that by choosing an appropriate recurrent architecture that properly accounts
for the given information such as user interaction features and song metadata,
a single neural network could achieve a Mean Average Accuracy (AA) score of
0.648 on the withheld test data. Meanwhile, by ensembling several variants of
the core model, the overall recommendation accuracy can be improved even
further. By using the proposed approach, our team was able to attain the 1st
place in the competition. We have open-sourced our implementation at GitHub.
Uniform convergence may be unable to explain generalization in deep learning
Authors: Vaishnavh Nagarajan, J. Zico Kolter
Date: 2019-02-13 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Deep Learning, Generalization Bounds

Aimed at explaining the surprisingly good generalization behavior of overparameterized deep networks, recent works have developed a variety of generalization bounds for deep learning, all based on the fundamental learning-theoretic technique of uniform convergence. While it is well-known that many of these existing bounds are numerically large, through numerous experiments, we bring to light a more concerning aspect of these bounds: in practice, these bounds can {\em increase} with the training dataset size. Guided by our observations, we then present examples of overparameterized linear classifiers and neural networks trained by gradient descent (GD) where uniform convergence provably cannot "explain generalization" -- even if we take into account the implicit bias of GD {\em to the fullest extent possible}. More precisely, even if we consider only the set of classifiers output by GD, which have test errors less than some small $\epsilon$ in our settings, we show that applying (two-sided) uniform convergence on this set of classifiers will yield only a vacuous generalization guarantee larger than $1-\epsilon$. Through these findings, we cast doubt on the power of uniform convergence-based generalization bounds to provide a complete picture of why overparameterized deep networks generalize well.
Learning to Screen
Authors: Alon Cohen, Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Shay Moran
Date: 2019-02-13 00:00:00
Proceeding: NeurIPS 2019 12

Imagine a large firm with multiple departments that plans a large recruitment. Candidates arrive one-by-one, and for each candidate the firm decides, based on her data (CV, skills, experience, etc), whether to summon her for an interview. The firm wants to recruit the best candidates while minimizing the number of interviews. We model such scenarios as an assignment problem between items (candidates) and categories (departments): the items arrive one-by-one in an online manner, and upon processing each item the algorithm decides, based on its value and the categories it can be matched with, whether to retain or discard it (this decision is irrevocable). The goal is to retain as few items as possible while guaranteeing that the set of retained items contains an optimal matching. We consider two variants of this problem: (i) in the first variant it is assumed that the $n$ items are drawn independently from an unknown distribution $D$. (ii) In the second variant it is assumed that before the process starts, the algorithm has an access to a training set of $n$ items drawn independently from the same unknown distribution (e.g.\ data of candidates from previous recruitment seasons). We give tight bounds on the minimum possible number of retained items in each of these variants. These results demonstrate that one can retain exponentially less items in the second variant (with the training set).
Accurate 3D Cell Segmentation using Deep Feature and CRF Refinement
Authors: Jiaxiang Jiang, Po-Yu Kao, Samuel A. Belteton, Daniel B. Szymanski, B. S. Manjunath
Date: 2019-02-13 00:00:00
Tasks: Cell Segmentation, Segmentation

We consider the problem of accurately identifying cell boundaries and
labeling individual cells in confocal microscopy images, specifically, 3D image
stacks of cells with tagged cell membranes. Precise identification of cell
boundaries, their shapes, and quantifying inter-cellular space leads to a
better understanding of cell morphogenesis. Towards this, we outline a cell
segmentation method that uses a deep neural network architecture to extract a
confidence map of cell boundaries, followed by a 3D watershed algorithm and a
final refinement using a conditional random field. In addition to improving the
accuracy of segmentation compared to other state-of-the-art methods, the
proposed approach also generalizes well to different datasets without the need
to retrain the network for each dataset. Detailed experimental results are
provided, and the source code is available on GitHub.
Learning Ising Models with Independent Failures
Authors: Surbhi Goel, Daniel M. Kane, Adam R. Klivans
Date: 2019-02-13 00:00:00

We give the first efficient algorithm for learning the structure of an Ising
model that tolerates independent failures; that is, each entry of the observed
sample is missing with some unknown probability p. Our algorithm matches the
essentially optimal runtime and sample complexity bounds of recent work for
learning Ising models due to Klivans and Meka (2017).
  We devise a novel unbiased estimator for the gradient of the Interaction
Screening Objective (ISO) due to Vuffray et al. (2016) and apply a stochastic
multiplicative gradient descent algorithm to minimize this objective. Solutions
to this minimization recover the neighborhood information of the underlying
Ising model on a node by node basis.
A characterisation of S-box fitness landscapes in cryptography
Authors: Domagoj Jakobovic, Stjepan Picek, Marcella S. R. Martins, Markus Wagner
Date: 2019-02-13 00:00:00

Substitution Boxes (S-boxes) are nonlinear objects often used in the design
of cryptographic algorithms. The design of high quality S-boxes is an
interesting problem that attracts a lot of attention. Many attempts have been
made in recent years to use heuristics to design S-boxes, but the results were
often far from the previously known best obtained ones. Unfortunately, most of
the effort went into exploring different algorithms and fitness functions while
little attention has been given to the understanding why this problem is so
difficult for heuristics. In this paper, we conduct a fitness landscape
analysis to better understand why this problem can be difficult. Among other,
we find that almost each initial starting point has its own local optimum, even
though the networks are highly interconnected.
Beyond the Chinese Restaurant and Pitman-Yor processes: Statistical Models with Double Power-law Behavior
Authors: Fadhel Ayed, Juho Lee, François Caron
Date: 2019-02-13 00:00:00

Bayesian nonparametric approaches, in particular the Pitman-Yor process and the associated two-parameter Chinese Restaurant process, have been successfully used in applications where the data exhibit a power-law behavior. Examples include natural language processing, natural images or networks. There is also growing empirical evidence that some datasets exhibit a two-regime power-law behavior: one regime for small frequencies, and a second regime, with a different exponent, for high frequencies. In this paper, we introduce a class of completely random measures which are doubly regularly-varying. Contrary to the Pitman-Yor process, we show that when completely random measures in this class are normalized to obtain random probability measures and associated random partitions, such partitions exhibit a double power-law behavior. We discuss in particular three models within this class: the beta prime process (Broderick et al. (2015, 2018), a novel process called generalized BFRY process, and a mixture construction. We derive efficient Markov chain Monte Carlo algorithms to estimate the parameters of these models. Finally, we show that the proposed models provide a better fit than the Pitman-Yor process on various datasets.
Automated Segmentation of the Optic Disk and Cup using Dual-Stage Fully Convolutional Networks
Authors: Lei Bi, Yuyu Guo, Qian Wang, Dagan Feng, Michael Fulham, Jinman Kim
Date: 2019-02-13 00:00:00
Tasks: Segmentation

Automated segmentation of the optic cup and disk on retinal fundus images is
fundamental for the automated detection / analysis of glaucoma. Traditional
segmentation approaches depend heavily upon hand-crafted features and a priori
knowledge of the user. As such, these methods are difficult to be adapt to the
clinical environment. Recently, deep learning methods based on fully
convolutional networks (FCNs) have been successful in resolving segmentation
problems. However, the reliance on large annotated training data is problematic
when dealing with medical images. If a sufficient amount of annotated training
data to cover all possible variations is not available, FCNs do not provide
accurate segmentation. In addition, FCNs have a large receptive field in the
convolutional layers, and hence produce coarse outputs of boundaries. Hence, we
propose a new fully automated method that we refer to as a dual-stage fully
convolutional networks (DSFCN). Our approach leverages deep residual
architectures and FCNs and learns and infers the location of the optic cup and
disk in a step-wise manner with fine-grained details. During training, our
approach learns from the training data and the estimated results derived from
the previous iteration. The ability to learn from the previous iteration
optimizes the learning of the optic cup and the disk boundaries. During testing
(prediction), DSFCN uses test (input) images and the estimated probability map
derived from previous iterations to gradually improve the segmentation
accuracy. Our method achieved an average Dice co-efficient of 0.8488 and 0.9441
for optic cup and disk segmentation and an area under curve (AUC) of 0.9513 for
glaucoma detection.