pwc-archive/papers-with-abstracts huggingface dataset:
Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularities
Authors: Ruitong Huang, Tor Lattimore, András György, Csaba Szepesvári
Date: 2017-02-10 00:00:00
Proceeding: NeurIPS 2016 12

The follow the leader (FTL) algorithm, perhaps the simplest of all online
learning algorithms, is known to perform well when the loss functions it is
used on are convex and positively curved. In this paper we ask whether there
are other "lucky" settings when FTL achieves sublinear, "small" regret. In
particular, we study the fundamental problem of linear prediction over a
non-empty convex, compact domain. Amongst other results, we prove that the
curvature of the boundary of the domain can act as if the losses were curved:
In this case, we prove that as long as the mean of the loss vectors have
positive lengths bounded away from zero, FTL enjoys a logarithmic growth rate
of regret, while, e.g., for polytope domains and stochastic data it enjoys
finite expected regret. Building on a previously known meta-algorithm, we also
get an algorithm that simultaneously enjoys the worst-case guarantees and the
bound available for FTL.
Multi-agent Reinforcement Learning in Sequential Social Dilemmas
Authors: Joel Z. Leibo, Vinicius Zambaldi, Marc Lanctot, Janusz Marecki, Thore Graepel
Date: 2017-02-10 00:00:00
Tasks: Multi-agent Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Matrix games like Prisoner's Dilemma have guided research on social dilemmas
for decades. However, they necessarily treat the choice to cooperate or defect
as an atomic action. In real-world social dilemmas these choices are temporally
extended. Cooperativeness is a property that applies to policies, not
elementary actions. We introduce sequential social dilemmas that share the
mixed incentive structure of matrix game social dilemmas but also require
agents to learn policies that implement their strategic intentions. We analyze
the dynamics of policies learned by multiple self-interested independent
learning agents, each using its own deep Q-network, on two Markov games we
introduce here: 1. a fruit Gathering game and 2. a Wolfpack hunting game. We
characterize how learned behavior in each domain changes as a function of
environmental factors including resource abundance. Our experiments show how
conflict can emerge from competition over shared resources and shed light on
how the sequential nature of real world social dilemmas affects cooperation.
Local System Voting Feature for Machine Translation System Combination
Authors: Markus Freitag, Jan-Thorsten Peter, Stephan Peitz, Minwei Feng, Hermann Ney
Date: 2017-02-10 00:00:00
Proceeding: WS 2015 9
Tasks: Machine Translation, Sentence, Translation

In this paper, we enhance the traditional confusion network system
combination approach with an additional model trained by a neural network. This
work is motivated by the fact that the commonly used binary system voting
models only assign each input system a global weight which is responsible for
the global impact of each input system on all translations. This prevents
individual systems with low system weights from having influence on the system
combination output, although in some situations this could be helpful. Further,
words which have only been seen by one or few systems rarely have a chance of
being present in the combined output. We train a local system voting model by a
neural network which is based on the words themselves and the combinatorial
occurrences of the different system outputs. This gives system combination the
option to prefer other systems at different word positions even for the same
sentence.
A New Rank Constraint on Multi-view Fundamental Matrices, and its Application to Camera Location Recovery
Authors: Soumyadip Sengupta, Tal Amir, Meirav Galun, Tom Goldstein, David W. Jacobs, Amit Singer, Ronen Basri
Date: 2017-02-10 00:00:00
Proceeding: CVPR 2017 7

Accurate estimation of camera matrices is an important step in structure from
motion algorithms. In this paper we introduce a novel rank constraint on
collections of fundamental matrices in multi-view settings. We show that in
general, with the selection of proper scale factors, a matrix formed by
stacking fundamental matrices between pairs of images has rank 6. Moreover,
this matrix forms the symmetric part of a rank 3 matrix whose factors relate
directly to the corresponding camera matrices. We use this new characterization
to produce better estimations of fundamental matrices by optimizing an L1-cost
function using Iterative Re-weighted Least Squares and Alternate Direction
Method of Multiplier. We further show that this procedure can improve the
recovery of camera locations, particularly in multi-view settings in which
fewer images are available.
Network Maximal Correlation
Authors: Soheil Feizi, Ali Makhdoumi, Ken Duffy, Muriel Medard, Manolis Kellis
Date: 2016-06-15 00:00:00
Tasks: graph partitioning

We introduce Network Maximal Correlation (NMC) as a multivariate measure of
nonlinear association among random variables. NMC is defined via an
optimization that infers transformations of variables by maximizing aggregate
inner products between transformed variables. For finite discrete and jointly
Gaussian random variables, we characterize a solution of the NMC optimization
using basis expansion of functions over appropriate basis functions. For finite
discrete variables, we propose an algorithm based on alternating conditional
expectation to determine NMC. Moreover we propose a distributed algorithm to
compute an approximation of NMC for large and dense graphs using graph
partitioning. For finite discrete variables, we show that the probability of
discrepancy greater than any given level between NMC and NMC computed using
empirical distributions decays exponentially fast as the sample size grows. For
jointly Gaussian variables, we show that under some conditions the NMC
optimization is an instance of the Max-Cut problem. We then illustrate an
application of NMC in inference of graphical model for bijective functions of
jointly Gaussian variables. Finally, we show NMC's utility in a data
application of learning nonlinear dependencies among genes in a cancer dataset.
Local Rademacher Complexity-based Learning Guarantees for Multi-Task Learning
Authors: Niloofar Yousefi, Yunwen Lei, Marius Kloft, Mansooreh Mollaghasemi, Georgios Anagnostopoulos
Date: 2016-02-18 00:00:00
Tasks: Multi-Task Learning

We show a Talagrand-type concentration inequality for Multi-Task Learning
(MTL), using which we establish sharp excess risk bounds for MTL in terms of
distribution- and data-dependent versions of the Local Rademacher Complexity
(LRC). We also give a new bound on the LRC for norm regularized as well as
strongly convex hypothesis classes, which applies not only to MTL but also to
the standard i.i.d. setting. Combining both results, one can now easily derive
fast-rate bounds on the excess risk for many prominent MTL methods,
including---as we demonstrate---Schatten-norm, group-norm, and
graph-regularized MTL. The derived bounds reflect a relationship akeen to a
conservation law of asymptotic convergence rates. This very relationship allows
for trading off slower rates w.r.t. the number of tasks for faster rates with
respect to the number of available samples per task, when compared to the rates
obtained via a traditional, global Rademacher analysis.
Multi-step Off-policy Learning Without Importance Sampling Ratios
Authors: Ashique Rupam Mahmood, Huizhen Yu, Richard S. Sutton
Date: 2017-02-09 00:00:00

To estimate the value functions of policies from exploratory data, most
model-free off-policy algorithms rely on importance sampling, where the use of
importance sampling ratios often leads to estimates with severe variance. It is
thus desirable to learn off-policy without using the ratios. However, such an
algorithm does not exist for multi-step learning with function approximation.
In this paper, we introduce the first such algorithm based on
temporal-difference (TD) learning updates. We show that an explicit use of
importance sampling ratios can be eliminated by varying the amount of
bootstrapping in TD updates in an action-dependent manner. Our new algorithm
achieves stability using a two-timescale gradient-based TD update. A prior
algorithm based on lookup table representation called Tree Backup can also be
retrieved using action-dependent bootstrapping, becoming a special case of our
algorithm. In two challenging off-policy tasks, we demonstrate that our
algorithm is stable, effectively avoids the large variance issue, and can
perform substantially better than its state-of-the-art counterpart.
A large comparison of feature-based approaches for buried target classification in forward-looking ground-penetrating radar
Authors: Joseph A. Camilo, Leslie M. Collins, Jordan M. Malof
Date: 2017-02-09 00:00:00
Tasks: General Classification, Object Recognition

Forward-looking ground-penetrating radar (FLGPR) has recently been
investigated as a remote sensing modality for buried target detection (e.g.,
landmines). In this context, raw FLGPR data is beamformed into images and then
computerized algorithms are applied to automatically detect subsurface buried
targets. Most existing algorithms are supervised, meaning they are trained to
discriminate between labeled target and non-target imagery, usually based on
features extracted from the imagery. A large number of features have been
proposed for this purpose, however thus far it is unclear which are the most
effective. The first goal of this work is to provide a comprehensive comparison
of detection performance using existing features on a large collection of FLGPR
data. Fusion of the decisions resulting from processing each feature is also
considered. The second goal of this work is to investigate two modern feature
learning approaches from the object recognition literature: the
bag-of-visual-words and the Fisher vector for FLGPR processing. The results
indicate that the new feature learning approaches outperform existing methods.
Results also show that fusion between existing features and new features yields
little additional performance improvements.
Real-time interactive sequence generation and control with Recurrent Neural Network ensembles
Authors: Memo Akten, Mick Grierson
Date: 2016-12-14 00:00:00
Tasks: continuous-control, Continuous Control

Recurrent Neural Networks (RNN), particularly Long Short Term Memory (LSTM)
RNNs, are a popular and very successful method for learning and generating
sequences. However, current generative RNN techniques do not allow real-time
interactive control of the sequence generation process, thus aren't well suited
for live creative expression. We propose a method of real-time continuous
control and 'steering' of sequence generation using an ensemble of RNNs and
dynamically altering the mixture weights of the models. We demonstrate the
method using character based LSTM networks and a gestural interface allowing
users to 'conduct' the generation of text.
Fixing an error in Caponnetto and de Vito (2007)
Authors: Danica J. Sutherland
Date: 2017-02-09 00:00:00
Tasks: regression

The seminal paper of Caponnetto and de Vito (2007) provides minimax-optimal rates for kernel ridge regression in a very general setting. Its proof, however, contains an error in its bound on the effective dimensionality. In this note, we explain the mistake, provide a correct bound, and show that the main theorem remains true.
On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
Authors: Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, Ping Tak Peter Tang
Date: 2016-09-15 00:00:00

The stochastic gradient descent (SGD) method and its variants are algorithms
of choice for many Deep Learning tasks. These methods operate in a small-batch
regime wherein a fraction of the training data, say $32$-$512$ data points, is
sampled to compute an approximation to the gradient. It has been observed in
practice that when using a larger batch there is a degradation in the quality
of the model, as measured by its ability to generalize. We investigate the
cause for this generalization drop in the large-batch regime and present
numerical evidence that supports the view that large-batch methods tend to
converge to sharp minimizers of the training and testing functions - and as is
well known, sharp minima lead to poorer generalization. In contrast,
small-batch methods consistently converge to flat minimizers, and our
experiments support a commonly held view that this is due to the inherent noise
in the gradient estimation. We discuss several strategies to attempt to help
large-batch methods eliminate this generalization gap.
Pathwise Coordinate Optimization for Sparse Learning: Algorithm and Theory
Authors: Tuo Zhao, Han Liu, Tong Zhang
Date: 2014-12-23 00:00:00
Tasks: parameter estimation, Sparse Learning

The pathwise coordinate optimization is one of the most important
computational frameworks for high dimensional convex and nonconvex sparse
learning problems. It differs from the classical coordinate optimization
algorithms in three salient features: {\it warm start initialization}, {\it
active set updating}, and {\it strong rule for coordinate preselection}. Such a
complex algorithmic structure grants superior empirical performance, but also
poses significant challenge to theoretical analysis. To tackle this long
lasting problem, we develop a new theory showing that these three features play
pivotal roles in guaranteeing the outstanding statistical and computational
performance of the pathwise coordinate optimization framework. Particularly, we
analyze the existing pathwise coordinate optimization algorithms and provide
new theoretical insights into them. The obtained insights further motivate the
development of several modifications to improve the pathwise coordinate
optimization framework, which guarantees linear convergence to a unique sparse
local optimum with optimal statistical properties in parameter estimation and
support recovery. This is the first result on the computational and statistical
guarantees of the pathwise coordinate optimization framework in high
dimensions. Thorough numerical experiments are provided to support our theory.
EAC-Net: A Region-based Deep Enhancing and Cropping Approach for Facial Action Unit Detection
Authors: Wei Li, Farnaz Abtahi, Zhigang Zhu, Lijun Yin
Date: 2017-02-09 00:00:00
Tasks: Action Unit Detection, Facial Action Unit Detection

In this paper, we propose a deep learning based approach for facial action
unit detection by enhancing and cropping the regions of interest. The approach
is implemented by adding two novel nets (layers): the enhancing layers and the
cropping layers, to a pretrained CNN model. For the enhancing layers, we
designed an attention map based on facial landmark features and applied it to a
pretrained neural network to conduct enhanced learning (The E-Net). For the
cropping layers, we crop facial regions around the detected landmarks and
design convolutional layers to learn deeper features for each facial region
(C-Net). We then fuse the E-Net and the C-Net to obtain our Enhancing and
Cropping (EAC) Net, which can learn both feature enhancing and region cropping
functions. Our approach shows significant improvement in performance compared
to the state-of-the-art methods applied to BP4D and DISFA AU datasets.
Dynamic Allocation of Crowd Contributions for Sentiment Analysis during the 2016 U.S. Presidential Election
Authors: Mehrnoosh Sameki, Mattia Gentil, Kate K. Mays, Lei Guo, Margrit Betke
Date: 2016-08-31 00:00:00
Tasks: Sentiment Analysis

Opinions about the 2016 U.S. Presidential Candidates have been expressed in
millions of tweets that are challenging to analyze automatically. Crowdsourcing
the analysis of political tweets effectively is also difficult, due to large
inter-rater disagreements when sarcasm is involved. Each tweet is typically
analyzed by a fixed number of workers and majority voting. We here propose a
crowdsourcing framework that instead uses a dynamic allocation of the number of
workers. We explore two dynamic-allocation methods: (1) The number of workers
queried to label a tweet is computed offline based on the predicted difficulty
of discerning the sentiment of a particular tweet. (2) The number of crowd
workers is determined online, during an iterative crowd sourcing process, based
on inter-rater agreements between labels.We applied our approach to 1,000
twitter messages about the four U.S. presidential candidates Clinton, Cruz,
Sanders, and Trump, collected during February 2016. We implemented the two
proposed methods using decision trees that allocate more crowd efforts to
tweets predicted to be sarcastic. We show that our framework outperforms the
traditional static allocation scheme. It collects opinion labels from the crowd
at a much lower cost while maintaining labeling accuracy.
Spatial Filtering for EEG-Based Regression Problems in Brain-Computer Interface (BCI)
Authors: Dongrui Wu, Jung-Tai King, Chun-Hsiang Chuang, Chin-Teng Lin, Tzyy-Ping Jung
Date: 2017-02-09 00:00:00
Tasks: Brain Computer Interface, Classification, EEG, Electroencephalogram (EEG), General Classification, regression

Electroencephalogram (EEG) signals are frequently used in brain-computer
interfaces (BCIs), but they are easily contaminated by artifacts and noises, so
preprocessing must be done before they are fed into a machine learning
algorithm for classification or regression. Spatial filters have been widely
used to increase the signal-to-noise ratio of EEG for BCI classification
problems, but their applications in BCI regression problems have been very
limited. This paper proposes two common spatial pattern (CSP) filters for
EEG-based regression problems in BCI, which are extended from the CSP filter
for classification, by making use of fuzzy sets. Experimental results on
EEG-based response speed estimation from a large-scale study, which collected
143 sessions of sustained-attention psychomotor vigilance task data from 17
subjects during a 5-month period, demonstrate that the two proposed spatial
filters can significantly increase the EEG signal quality. When used in LASSO
and k-nearest neighbors regression for user response speed estimation, the
spatial filters can reduce the root mean square estimation error by
10.02-19.77%, and at the same time increase the correlation to the true
response speed by 19.39-86.47%.
Switching EEG Headsets Made Easy: Reducing Offline Calibration Effort Using Active Weighted Adaptation Regularization
Authors: Dongrui Wu, Vernon J. Lawhern, W. David Hairston, Brent J. Lance
Date: 2017-02-09 00:00:00
Tasks: Active Learning, Brain Computer Interface, Classification, EEG, Electroencephalogram (EEG), General Classification, Transfer Learning

Electroencephalography (EEG) headsets are the most commonly used sensing
devices for Brain-Computer Interface. In real-world applications, there are
advantages to extrapolating data from one user session to another. However,
these advantages are limited if the data arise from different hardware systems,
which often vary between application spaces. Currently, this creates a need to
recalibrate classifiers, which negatively affects people's interest in using
such systems. In this paper, we employ active weighted adaptation
regularization (AwAR), which integrates weighted adaptation regularization
(wAR) and active learning, to expedite the calibration process. wAR makes use
of labeled data from the previous headset and handles class-imbalance, and
active learning selects the most informative samples from the new headset to
label. Experiments on single-trial event-related potential classification show
that AwAR can significantly increase the classification accuracy, given the
same number of labeled samples from the new headset. In other words, AwAR can
effectively reduce the number of labeled samples required from the new headset,
given a desired classification accuracy, suggesting value in collating data for
use in wide scale transfer-learning applications.
Driver Drowsiness Estimation from EEG Signals Using Online Weighted Adaptation Regularization for Regression (OwARR)
Authors: Dongrui Wu, Vernon J. Lawhern, Stephen Gordon, Brent J. Lance, Chin-Teng Lin
Date: 2017-02-09 00:00:00
Tasks: Domain Adaptation, EEG, Electroencephalogram (EEG), regression, Transfer Learning

One big challenge that hinders the transition of brain-computer interfaces
(BCIs) from laboratory settings to real-life applications is the availability
of high-performance and robust learning algorithms that can effectively handle
individual differences, i.e., algorithms that can be applied to a new subject
with zero or very little subject-specific calibration data. Transfer learning
and domain adaptation have been extensively used for this purpose. However,
most previous works focused on classification problems. This paper considers an
important regression problem in BCI, namely, online driver drowsiness
estimation from EEG signals. By integrating fuzzy sets with domain adaptation,
we propose a novel online weighted adaptation regularization for regression
(OwARR) algorithm to reduce the amount of subject-specific calibration data,
and also a source domain selection (SDS) approach to save about half of the
computational cost of OwARR. Using a simulated driving dataset with 15
subjects, we show that OwARR and OwARR-SDS can achieve significantly smaller
estimation errors than several other approaches. We also provide comprehensive
analyses on the robustness of OwARR and OwARR-SDS.
Online and Offline Domain Adaptation for Reducing BCI Calibration Effort
Authors: Dongrui Wu
Date: 2017-02-09 00:00:00
Tasks: Brain Computer Interface, Domain Adaptation, EEG, Electroencephalogram (EEG), ERP

Many real-world brain-computer interface (BCI) applications rely on
single-trial classification of event-related potentials (ERPs) in EEG signals.
However, because different subjects have different neural responses to even the
same stimulus, it is very difficult to build a generic ERP classifier whose
parameters fit all subjects. The classifier needs to be calibrated for each
individual subject, using some labeled subject-specific data. This paper
proposes both online and offline weighted adaptation regularization (wAR)
algorithms to reduce this calibration effort, i.e., to minimize the amount of
labeled subject-specific EEG data required in BCI calibration, and hence to
increase the utility of the BCI system. We demonstrate using a visually-evoked
potential oddball task and three different EEG headsets that both online and
offline wAR algorithms significantly outperform several other algorithms.
Moreover, through source domain selection, we can reduce their computational
cost by about 50%, making them more suitable for real-time applications.
Answer Set Solving with Bounded Treewidth Revisited
Authors: Johannes Fichte, Markus Hecher, Michael Morak, Stefan Woltran
Date: 2017-02-09 00:00:00

Parameterized algorithms are a way to solve hard problems more efficiently,
given that a specific parameter of the input is small. In this paper, we apply
this idea to the field of answer set programming (ASP). To this end, we propose
two kinds of graph representations of programs to exploit their treewidth as a
parameter. Treewidth roughly measures to which extent the internal structure of
a program resembles a tree. Our main contribution is the design of
parameterized dynamic programming algorithms, which run in linear time if the
treewidth and weights of the given program are bounded. Compared to previous
work, our algorithms handle the full syntax of ASP. Finally, we report on an
empirical evaluation that shows good runtime behaviour for benchmark instances
of low treewidth, especially for counting answer sets.