pwc-archive/papers-with-abstracts huggingface dataset:
Subspace Estimation from Incomplete Observations: A High-Dimensional Analysis
Authors: Chuang Wang, Yonina C. Eldar, Yue M. Lu
Date: 2018-05-17 00:00:00
Tasks: Vocal Bursts Intensity Prediction

We present a high-dimensional analysis of three popular algorithms, namely,
Oja's method, GROUSE and PETRELS, for subspace estimation from streaming and
highly incomplete observations. We show that, with proper time scaling, the
time-varying principal angles between the true subspace and its estimates given
by the algorithms converge weakly to deterministic processes when the ambient
dimension $n$ tends to infinity. Moreover, the limiting processes can be
exactly characterized as the unique solutions of certain ordinary differential
equations (ODEs). A finite sample bound is also given, showing that the rate of
convergence towards such limits is $\mathcal{O}(1/\sqrt{n})$. In addition to
providing asymptotically exact predictions of the dynamic performance of the
algorithms, our high-dimensional analysis yields several insights, including an
asymptotic equivalence between Oja's method and GROUSE, and a precise scaling
relationship linking the amount of missing data to the signal-to-noise ratio.
By analyzing the solutions of the limiting ODEs, we also establish phase
transition phenomena associated with the steady-state performance of these
techniques.
Memoryless Exact Solutions for Deterministic MDPs with Sparse Rewards
Authors: Joshua R. Bertram, Peng Wei
Date: 2018-05-17 00:00:00

We propose an algorithm for deterministic continuous Markov Decision
Processes with sparse rewards that computes the optimal policy exactly with no
dependency on the size of the state space. The algorithm has time complexity of
$O( |R|^3 \times |A|^2 )$ and memory complexity of $O( |R| \times |A| )$, where
$|R|$ is the number of reward sources and $|A|$ is the number of actions.
Furthermore, we describe a companion algorithm that can follow the optimal
policy from any initial state without computing the entire value function,
instead computing on-demand the value of states as they are needed. The
algorithm to solve the MDP does not depend on the size of the state space for
either time or memory complexity, and the ability to follow the optimal policy
is linear in time and space with the path length of following the optimal
policy from the initial state. We demonstrate the algorithm operation side by
side with value iteration on tractable MDPs.
Fast Online Exact Solutions for Deterministic MDPs with Sparse Rewards
Authors: Joshua R. Bertram, Xuxi Yang, Peng Wei
Date: 2018-05-08 00:00:00
Tasks: Decision Making, Decision Making Under Uncertainty, Sequential Decision Making

Markov Decision Processes (MDPs) are a mathematical framework for modeling
sequential decision making under uncertainty. The classical approaches for
solving MDPs are well known and have been widely studied, some of which rely on
approximation techniques to solve MDPs with large state space and/or action
space. However, most of these classical solution approaches and their
approximation techniques still take much computation time to converge and
usually must be re-computed if the reward function is changed. This paper
introduces a novel alternative approach for exactly and efficiently solving
deterministic, continuous MDPs with sparse reward sources. When the environment
is such that the "distance" between states can be determined in constant time,
e.g. grid world, our algorithm offers $O( |R|^2 \times |A|^2 \times |S|)$,
where $|R|$ is the number of reward sources, $|A|$ is the number of actions,
and $|S|$ is the number of states. Memory complexity for the algorithm is $O(
|S| + |R| \times |A|)$. This new approach opens new avenues for boosting
computational performance for certain classes of MDPs and is of tremendous
value for MDP applications such as robotics and unmanned systems. This paper
describes the algorithm and presents numerical experiment results to
demonstrate its powerful computational performance. We also provide rigorous
mathematical description of the approach.
Disparity Sliding Window: Object Proposals From Disparity Images
Authors: Julian Müller, Andreas Fregin, Klaus Dietmayer
Date: 2018-05-17 00:00:00
Tasks: Object, object-detection, Object Detection, Object Recognition, Pedestrian Detection

Sliding window approaches have been widely used for object recognition tasks
in recent years. They guarantee an investigation of the entire input image for
the object to be detected and allow a localization of that object. Despite the
current trend towards deep neural networks, sliding window methods are still
used in combination with convolutional neural networks. The risk of overlooking
an object is clearly reduced compared to alternative detection approaches which
detect objects based on shape, edges or color. Nevertheless, the sliding window
technique strongly increases the computational effort as the classifier has to
verify a large number of object candidates. This paper proposes a sliding
window approach which also uses depth information from a stereo camera. This
leads to a greatly decreased number of object candidates without significantly
reducing the detection accuracy. A theoretical investigation of the
conventional sliding window approach is presented first. Other publications to
date only mentioned rough estimations of the computational cost. A mathematical
derivation clarifies the number of object candidates with respect to parameters
such as image and object size. Subsequently, the proposed disparity sliding
window approach is presented in detail. The approach is evaluated on pedestrian
detection with annotations and images from the KITTI object detection
benchmark. Furthermore, a comparison with two state-of-the-art methods is made.
Code is available in C++ and Python https://github.com/julimueller/
disparity-sliding-window.
The Blessings of Multiple Causes
Authors: Yixin Wang, David M. Blei
Date: 2018-05-17 00:00:00
Tasks: Causal Inference

Causal inference from observational data often assumes "ignorability," that
all confounders are observed. This assumption is standard yet untestable.
However, many scientific studies involve multiple causes, different variables
whose effects are simultaneously of interest. We propose the deconfounder, an
algorithm that combines unsupervised machine learning and predictive model
checking to perform causal inference in multiple-cause settings. The
deconfounder infers a latent variable as a substitute for unobserved
confounders and then uses that substitute to perform causal inference. We
develop theory for the deconfounder, and show that it requires weaker
assumptions than classical causal inference. We analyze its performance in
three types of studies: semi-simulated data around smoking and lung cancer,
semi-simulated data around genome-wide association studies, and a real dataset
about actors and movie revenue. The deconfounder provides a checkable approach
to estimating closer-to-truth causal effects.
Robustness of Rotation-Equivariant Networks to Adversarial Perturbations
Authors: Beranger Dumont, Simona Maggio, Pablo Montalvo
Date: 2018-02-19 00:00:00

Deep neural networks have been shown to be vulnerable to adversarial
examples: very small perturbations of the input having a dramatic impact on the
predictions. A wealth of adversarial attacks and distance metrics to quantify
the similarity between natural and adversarial images have been proposed,
recently enlarging the scope of adversarial examples with geometric
transformations beyond pixel-wise attacks. In this context, we investigate the
robustness to adversarial attacks of new Convolutional Neural Network
architectures providing equivariance to rotations. We found that
rotation-equivariant networks are significantly less vulnerable to
geometric-based attacks than regular networks on the MNIST, CIFAR-10, and
ImageNet datasets.
Annotating Electronic Medical Records for Question Answering
Authors: Preethi Raghavan, Siddharth Patwardhan, Jennifer J. Liang, Murthy V. Devarakonda
Date: 2018-05-17 00:00:00
Tasks: Question Answering

Our research is in the relatively unexplored area of question answering
technologies for patient-specific questions over their electronic health
records. A large dataset of human expert curated question and answer pairs is
an important pre-requisite for developing, training and evaluating any question
answering system that is powered by machine learning. In this paper, we
describe a process for creating such a dataset of questions and answers. Our
methodology is replicable, can be conducted by medical students as annotators,
and results in high inter-annotator agreement (0.71 Cohen's kappa). Over the
course of 11 months, 11 medical students followed our annotation methodology,
resulting in a question answering dataset of 5696 questions over 71 patient
records, of which 1747 questions have corresponding answers generated by the
medical students.
Cross-domain attribute representation based on convolutional neural network
Authors: Guohui Zhang, Gaoyuan Liang, Fang Su, Fanxin Qu, Jing-Yan Wang
Date: 2018-05-17 00:00:00
Tasks: Attribute, Transfer Learning

In the problem of domain transfer learning, we learn a model for the
predic-tion in a target domain from the data of both some source domains and
the target domain, where the target domain is in lack of labels while the
source domain has sufficient labels. Besides the instances of the data,
recently the attributes of data shared across domains are also explored and
proven to be very helpful to leverage the information of different domains. In
this paper, we propose a novel learning framework for domain-transfer learning
based on both instances and attributes. We proposed to embed the attributes of
dif-ferent domains by a shared convolutional neural network (CNN), learn a
domain-independent CNN model to represent the information shared by dif-ferent
domains by matching across domains, and a domain-specific CNN model to
represent the information of each domain. The concatenation of the three CNN
model outputs is used to predict the class label. An iterative algo-rithm based
on gradient descent method is developed to learn the parameters of the model.
The experiments over benchmark datasets show the advantage of the proposed
model.
Faster Rates for Convex-Concave Games
Authors: Jacob Abernethy, Kevin A. Lai, Kfir. Y. Levy, Jun-Kun Wang
Date: 2018-05-17 00:00:00

We consider the use of no-regret algorithms to compute equilibria for
particular classes of convex-concave games. While standard regret bounds would
lead to convergence rates on the order of $O(T^{-1/2})$, recent work
\citep{RS13,SALS15} has established $O(1/T)$ rates by taking advantage of a
particular class of optimistic prediction algorithms. In this work we go
further, showing that for a particular class of games one achieves a $O(1/T^2)$
rate, and we show how this applies to the Frank-Wolfe method and recovers a
similar bound \citep{D15}. We also show that such no-regret techniques can even
achieve a linear rate, $O(\exp(-T))$, for equilibrium computation under
additional curvature assumptions.
Class-Splitting Generative Adversarial Networks
Authors: Guillermo L. Grinblat, Lucas C. Uzal, Pablo M. Granitto
Date: 2017-09-21 00:00:00
Tasks: Clustering, Conditional Image Generation, Image Generation

Generative Adversarial Networks (GANs) produce systematically better quality
samples when class label information is provided., i.e. in the conditional GAN
setup. This is still observed for the recently proposed Wasserstein GAN
formulation which stabilized adversarial training and allows considering high
capacity network architectures such as ResNet. In this work we show how to
boost conditional GAN by augmenting available class labels. The new classes
come from clustering in the representation space learned by the same GAN model.
The proposed strategy is also feasible when no class information is available,
i.e. in the unsupervised setup. Our generated samples reach state-of-the-art
Inception scores for CIFAR-10 and STL-10 datasets in both supervised and
unsupervised setup.
Logically-Constrained Reinforcement Learning
Authors: Mohammadhosein Hasanbeig, Alessandro Abate, Daniel Kroening
Date: 2018-01-24 00:00:00
Tasks: Decision Making, Decision Making Under Uncertainty, Hierarchical Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Safe Reinforcement Learning

We present the first model-free Reinforcement Learning (RL) algorithm to
synthesise policies for an unknown Markov Decision Process (MDP), such that a
linear time property is satisfied. The given temporal property is converted
into a Limit Deterministic Buchi Automaton (LDBA) and a robust reward function
is defined over the state-action pairs of the MDP according to the resulting
LDBA. With this reward function, the policy synthesis procedure is
"constrained" by the given specification. These constraints guide the MDP
exploration so as to minimize the solution time by only considering the portion
of the MDP that is relevant to satisfaction of the LTL property. This improves
performance and scalability of the proposed method by avoiding an exhaustive
update over the whole state space while the efficiency of standard methods such
as dynamic programming is hindered by excessive memory requirements, caused by
the need to store a full-model in memory. Additionally, we show that the RL
procedure sets up a local value iteration method to efficiently calculate the
maximum probability of satisfying the given property, at any given state of the
MDP. We prove that our algorithm is guaranteed to find a policy whose traces
probabilistically satisfy the LTL property if such a policy exists, and
additionally we show that our method produces reasonable control policies even
when the LTL property cannot be satisfied. The performance of the algorithm is
evaluated via a set of numerical examples. We observe an improvement of one
order of magnitude in the number of iterations required for the synthesis
compared to existing approaches.
Strict Very Fast Decision Tree: a memory conservative algorithm for data stream mining
Authors: Victor Guilherme Turrisi da Costa, André Carlos Ponce de Leon Ferreira de Carvalho, Sylvio Barbon Junior
Date: 2018-05-16 00:00:00

Dealing with memory and time constraints are current challenges when learning
from data streams with a massive amount of data. Many algorithms have been
proposed to handle these difficulties, among them, the Very Fast Decision Tree
(VFDT) algorithm. Although the VFDT has been widely used in data stream mining,
in the last years, several authors have suggested modifications to increase its
performance, putting aside memory concerns by proposing memory-costly
solutions. Besides, most data stream mining solutions have been centred around
ensembles, which combine the memory costs of their weak learners, usually
VFDTs. To reduce the memory cost, keeping the predictive performance, this
study proposes the Strict VFDT (SVFDT), a novel algorithm based on the VFDT.
The SVFDT algorithm minimises unnecessary tree growth, substantially reducing
memory usage and keeping competitive predictive performance. Moreover, since it
creates much more shallow trees than VFDT, SVFDT can achieve a shorter
processing time. Experiments were carried out comparing the SVFDT with the VFDT
in 11 benchmark data stream datasets. This comparison assessed the trade-off
between accuracy, memory, and processing time. Statistical analysis showed that
the proposed algorithm obtained similar predictive performance and
significantly reduced processing time and memory use. Thus, SVFDT is a suitable
option for data stream mining with memory and time limitations, recommended as
a weak learner in ensemble-based solutions.
Situation Assessment for Planning Lane Changes: Combining Recurrent Models and Prediction
Authors: Oliver Scheel, Loren Schwarz, Nassir Navab, Federico Tombari
Date: 2018-05-17 00:00:00

One of the greatest challenges towards fully autonomous cars is the
understanding of complex and dynamic scenes. Such understanding is needed for
planning of maneuvers, especially those that are particularly frequent such as
lane changes. While in recent years advanced driver-assistance systems have
made driving safer and more comfortable, these have mostly focused on car
following scenarios, and less on maneuvers involving lane changes. In this work
we propose a situation assessment algorithm for classifying driving situations
with respect to their suitability for lane changing. For this, we propose a
deep learning architecture based on a Bidirectional Recurrent Neural Network,
which uses Long Short-Term Memory units, and integrates a prediction component
in the form of the Intelligent Driver Model. We prove the feasibility of our
algorithm on the publicly available NGSIM datasets, where we outperform
existing methods.
Optimal Low-Rank Dynamic Mode Decomposition
Authors: Patrick Héas, Cédric Herzet
Date: 2017-01-04 00:00:00

Dynamic Mode Decomposition (DMD) has emerged as a powerful tool for analyzing
the dynamics of non-linear systems from experimental datasets. Recently,
several attempts have extended DMD to the context of low-rank approximations.
This extension is of particular interest for reduced-order modeling in various
applicative domains, e.g. for climate prediction, to study molecular dynamics
or micro-electromechanical devices. This low-rank extension takes the form of a
non-convex optimization problem. To the best of our knowledge, only sub-optimal
algorithms have been proposed in the literature to compute the solution of this
problem. In this paper, we prove that there exists a closed-form optimal
solution to this problem and design an effective algorithm to compute it based
on Singular Value Decomposition (SVD). A toy-example illustrates the gain in
performance of the proposed algorithm compared to state-of-the-art techniques.
Reduced-Order Modeling Of Hidden Dynamics
Authors: Patrick Héas, Cédric Herzet
Date: 2015-10-08 00:00:00

The objective of this paper is to investigate how noisy and incomplete
observations can be integrated in the process of building a reduced-order
model.
  This problematic arises in many scientific domains where there exists a need
for accurate low-order descriptions of highly-complex phenomena, which can not
be directly and/or deterministically observed. Within this context, the paper
proposes a probabilistic framework for the construction of "POD-Galerkin"
reduced-order models. Assuming a hidden Markov chain, the inference integrates
the uncertainty of the hidden states relying on their posterior distribution.
Simulations show the benefits obtained by exploiting the proposed framework.
Interpolatron: Interpolation or Extrapolation Schemes to Accelerate Optimization for Deep Neural Networks
Authors: Guangzeng Xie, Yitan Wang, Shuchang Zhou, Zhihua Zhang
Date: 2018-05-17 00:00:00

In this paper we explore acceleration techniques for large scale nonconvex
optimization problems with special focuses on deep neural networks. The
extrapolation scheme is a classical approach for accelerating stochastic
gradient descent for convex optimization, but it does not work well for
nonconvex optimization typically. Alternatively, we propose an interpolation
scheme to accelerate nonconvex optimization and call the method Interpolatron.
We explain motivation behind Interpolatron and conduct a thorough empirical
analysis. Empirical results on DNNs of great depths (e.g., 98-layer ResNet and
200-layer ResNet) on CIFAR-10 and ImageNet show that Interpolatron can converge
much faster than the state-of-the-art methods such as the SGD with momentum and
Adam. Furthermore, Anderson's acceleration, in which mixing coefficients are
computed by least-squares estimation, can also be used to improve the
performance. Both Interpolatron and Anderson's acceleration are easy to
implement and tune. We also show that Interpolatron has linear convergence rate
under certain regularity assumptions.
Action Completion: A Temporal Model for Moment Detection
Authors: Farnoosh Heidarivincheh, Majid Mirmehdi, Dima Damen
Date: 2018-05-17 00:00:00
Tasks: General Classification, model, regression

We introduce completion moment detection for actions - the problem of
locating the moment of completion, when the action's goal is confidently
considered achieved. The paper proposes a joint classification-regression
recurrent model that predicts completion from a given frame, and then
integrates frame-level contributions to detect sequence-level completion
moment. We introduce a recurrent voting node that predicts the frame's relative
position of the completion moment by either classification or regression. The
method is also capable of detecting incompletion. For example, the method is
capable of detecting a missed ball-catch, as well as the moment at which the
ball is safely caught. We test the method on 16 actions from three public
datasets, covering sports as well as daily actions. Results show that when
combining contributions from frames prior to the completion moment as well as
frames post completion, the completion moment is detected within one second in
89% of all tested sequences.
Non-Linear Reduced Modeling by Generalized Kernel-Based Dynamic Mode Decomposition
Authors: Patrick Héas, Cédric Herzet, Benoit Combès
Date: 2017-10-30 00:00:00

Reduced modeling of a computationally demanding dynamical system aims at approximating its trajectories, while optimizing the trade-off between accuracy and computational complexity. In this work, we propose to achieve such an approximation by first embedding the trajectories in a reproducing kernel Hilbert space (RKHS), which exhibits appealing approximation and computational capabilities, and then solving the associated reduced model problem. More specifically, we propose a new efficient algorithm for data-driven reduced modeling of non-linear dynamics based on linear approximations in a RKHS. This algorithm takes advantage of the closed-form solution of a low-rank constraint optimization problem while exploiting advantageously kernel-based computations. Reduced modeling with this algorithm reveals a gain in approximation accuracy, as shown by numerical simulations, and in complexity with respect to existing approaches.
Low-Rank Dynamic Mode Decomposition: An Exact and Tractable Solution
Authors: Patrick Héas, Cédric Herzet
Date: 2016-10-10 00:00:00

This work studies the linear approximation of high-dimensional dynamical systems using low-rank dynamic mode decomposition (DMD). Searching this approximation in a data-driven approach is formalised as attempting to solve a low-rank constrained optimisation problem. This problem is non-convex and state-of-the-art algorithms are all sub-optimal. This paper shows that there exists a closed-form solution, which is computed in polynomial time, and characterises the l2-norm of the optimal approximation error. The paper also proposes low-complexity algorithms building reduced models from this optimal solution, based on singular value decomposition or eigen value decomposition. The algorithms are evaluated by numerical simulations using synthetic and physical data benchmarks.