pwc-archive/papers-with-abstracts huggingface dataset:
PCA-Based Out-of-Sample Extension for Dimensionality Reduction
Authors: Yariv Aizenbud, Amit Bermanis, Amir Averbuch
Date: 2015-11-03 00:00:00
Tasks: Dimensionality Reduction

Dimensionality reduction methods are very common in the field of high
dimensional data analysis. Typically, algorithms for dimensionality reduction
are computationally expensive. Therefore, their applications for the analysis
of massive amounts of data are impractical. For example, repeated computations
due to accumulated data are computationally prohibitive. In this paper, an
out-of-sample extension scheme, which is used as a complementary method for
dimensionality reduction, is presented. We describe an algorithm which performs
an out-of-sample extension to newly-arrived data points. Unlike other extension
algorithms such as Nystr\"om algorithm, the proposed algorithm uses the
intrinsic geometry of the data and properties for dimensionality reduction map.
We prove that the error of the proposed algorithm is bounded. Additionally to
the out-of-sample extension, the algorithm provides a degree of the abnormality
of any newly-arrived data point.
SAT as a game
Authors: Olivier Bailleux
Date: 2015-11-03 00:00:00

We propose a funny representation of SAT. While the primary interest is to
present propositional satisfiability in a playful way for pedagogical purposes,
it could also inspire new search heuristics.
Explore no more: Improved high-probability regret bounds for non-stochastic bandits
Authors: Gergely Neu
Date: 2015-06-10 00:00:00
Proceeding: NeurIPS 2015 12

This work addresses the problem of regret minimization in non-stochastic
multi-armed bandit problems, focusing on performance guarantees that hold with
high probability. Such results are rather scarce in the literature since
proving them requires a large deal of technical effort and significant
modifications to the standard, more intuitive algorithms that come only with
guarantees that hold on expectation. One of these modifications is forcing the
learner to sample arms from the uniform distribution at least
$\Omega(\sqrt{T})$ times over $T$ rounds, which can adversely affect
performance if many of the arms are suboptimal. While it is widely conjectured
that this property is essential for proving high-probability regret bounds, we
show in this paper that it is possible to achieve such strong results without
this undesirable exploration component. Our result relies on a simple and
intuitive loss-estimation strategy called Implicit eXploration (IX) that allows
a remarkably clean analysis. To demonstrate the flexibility of our technique,
we derive several improved high-probability bounds for various extensions of
the standard multi-armed bandit framework. Finally, we conduct a simple
experiment that illustrates the robustness of our implicit exploration
technique.
Water Detection through Spatio-Temporal Invariant Descriptors
Authors: Pascal Mettes, Robby T. Tan, Remco C. Veltkamp
Date: 2015-11-02 00:00:00
Tasks: Dynamic Texture Recognition, Material Recognition

In this work, we aim to segment and detect water in videos. Water detection
is beneficial for appllications such as video search, outdoor surveillance, and
systems such as unmanned ground vehicles and unmanned aerial vehicles. The
specific problem, however, is less discussed compared to general texture
recognition. Here, we analyze several motion properties of water. First, we
describe a video pre-processing step, to increase invariance against water
reflections and water colours. Second, we investigate the temporal and spatial
properties of water and derive corresponding local descriptors. The descriptors
are used to locally classify the presence of water and a binary water detection
mask is generated through spatio-temporal Markov Random Field regularization of
the local classifications. Third, we introduce the Video Water Database,
containing several hours of water and non-water videos, to validate our
algorithm. Experimental evaluation on the Video Water Database and the DynTex
database indicates the effectiveness of the proposed algorithm, outperforming
multiple algorithms for dynamic texture recognition and material recognition by
ca. 5% and 15% respectively.
Improved Deep Learning Baselines for Ubuntu Corpus Dialogs
Authors: Rudolf Kadlec, Martin Schmid, Jan Kleindienst
Date: 2015-10-13 00:00:00
Tasks: Conversational Response Selection, Deep Learning

This paper presents results of our experiments for the next utterance ranking
on the Ubuntu Dialog Corpus -- the largest publicly available multi-turn dialog
corpus. First, we use an in-house implementation of previously reported models
to do an independent evaluation using the same data. Second, we evaluate the
performances of various LSTMs, Bi-LSTMs and CNNs on the dataset. Third, we
create an ensemble by averaging predictions of multiple models. The ensemble
further improves the performance and it achieves a state-of-the-art result for
the next utterance ranking on this dataset. Finally, we discuss our future
plans using this corpus.
Artificial neural network approach for condition-based maintenance
Authors: Mostafa Sayyed
Date: 2015-11-03 00:00:00
Tasks: Management

In this research, computerized maintenance management will be investigated.
The rise of maintenance cost forced the research community to look for more
effective ways to schedule maintenance operations. Using computerized models to
come up with optimal maintenance policy has led to better equipment utilization
and lower costs. This research adopts Condition-Based Maintenance model where
the maintenance decision is generated based on equipment conditions. Artificial
Neural Network technique is proposed to capture and analyze equipment condition
signals which lead to higher level of knowledge gathering. This knowledge is
used to accurately estimate equipment failure time. Based on these estimations,
an optimal maintenance management policy can be achieved.
A Pareto Optimal D* Search Algorithm for Multiobjective Path Planning
Authors: Alexander Lavin
Date: 2015-11-03 00:00:00
Tasks: Multiobjective Optimization

Path planning is one of the most vital elements of mobile robotics, providing
the agent with a collision-free route through the workspace. The global path
plan can be calculated with a variety of informed search algorithms, most
notably the A* search method, guaranteed to deliver a complete and optimal
solution that minimizes the path cost. D* is widely used for its dynamic
replanning capabilities. Path planning optimization typically looks to minimize
the distance traversed from start to goal, but many mobile robot applications
call for additional path planning objectives, presenting a multiobjective
optimization (MOO) problem. Common search algorithms, e.g. A* and D*, are not
well suited for MOO problems, yielding suboptimal results. The search algorithm
presented in this paper is designed for optimal MOO path planning. The
algorithm incorporates Pareto optimality into D*, and is thus named D*-PO.
Non-dominated solution paths are guaranteed by calculating the Pareto front at
each search step. Simulations were run to model a planetary exploration rover
in a Mars environment, with five path costs. The results show the new, Pareto
optimal D*-PO outperforms the traditional A* and D* algorithms for MOO path
planning.
Mixing Time Estimation in Reversible Markov Chains from a Single Sample Path
Authors: Daniel Hsu, Aryeh Kontorovich, Csaba Szepesvári
Date: 2015-06-09 00:00:00
Proceeding: NeurIPS 2015 12

This article provides the first procedure for computing a fully
data-dependent interval that traps the mixing time $t_{\text{mix}}$ of a finite
reversible ergodic Markov chain at a prescribed confidence level. The interval
is computed from a single finite-length sample path from the Markov chain, and
does not require the knowledge of any parameters of the chain. This stands in
contrast to previous approaches, which either only provide point estimates, or
require a reset mechanism, or additional prior knowledge. The interval is
constructed around the relaxation time $t_{\text{relax}}$, which is strongly
related to the mixing time, and the width of the interval converges to zero
roughly at a $\sqrt{n}$ rate, where $n$ is the length of the sample path. Upper
and lower bounds are given on the number of samples required to achieve
constant-factor multiplicative accuracy. The lower bounds indicate that, unless
further restrictions are placed on the chain, no procedure can achieve this
accuracy level before seeing each state at least $\Omega(t_{\text{relax}})$
times on the average. Finally, future directions of research are identified.
A Practical Guide to Randomized Matrix Computations with MATLAB Implementations
Authors: Shusen Wang
Date: 2015-05-28 00:00:00
Tasks: Computational Efficiency

Matrix operations such as matrix inversion, eigenvalue decomposition,
singular value decomposition are ubiquitous in real-world applications.
Unfortunately, many of these matrix operations so time and memory expensive
that they are prohibitive when the scale of data is large. In real-world
applications, since the data themselves are noisy, machine-precision matrix
operations are not necessary at all, and one can sacrifice a reasonable amount
of accuracy for computational efficiency.
  In recent years, a bunch of randomized algorithms have been devised to make
matrix computations more scalable. Mahoney (2011) and Woodruff (2014) have
written excellent but very technical reviews of the randomized algorithms.
Differently, the focus of this manuscript is on intuition, algorithm
derivation, and implementation. This manuscript should be accessible to people
with knowledge in elementary matrix algebra but unfamiliar with randomized
matrix computations. The algorithms introduced in this manuscript are all
summarized in a user-friendly way, and they can be implemented in lines of
MATLAB code. The readers can easily follow the implementations even if they do
not understand the maths and algorithms.
PAC Learning-Based Verification and Model Synthesis
Authors: Yu-Fang Chen, Chiao Hsieh, Ondřej Lengál, Tsung-Ju Lii, Ming-Hsien Tsai, Bow-Yaw Wang, Farn Wang
Date: 2015-11-03 00:00:00
Tasks: model, PAC learning

We introduce a novel technique for verification and model synthesis of
sequential programs. Our technique is based on learning a regular model of the
set of feasible paths in a program, and testing whether this model contains an
incorrect behavior. Exact learning algorithms require checking equivalence
between the model and the program, which is a difficult problem, in general
undecidable. Our learning procedure is therefore based on the framework of
probably approximately correct (PAC) learning, which uses sampling instead and
provides correctness guarantees expressed using the terms error probability and
confidence. Besides the verification result, our procedure also outputs the
model with the said correctness guarantees. Obtained preliminary experiments
show encouraging results, in some cases even outperforming mature software
verifiers.
Data Generation as Sequential Decision Making
Authors: Philip Bachman, Doina Precup
Date: 2015-06-10 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Decision Making, Imputation, Sequential Decision Making

We connect a broad class of generative models through their shared reliance
on sequential decision making. Motivated by this view, we develop extensions to
an existing model, and then explore the idea further in the context of data
imputation -- perhaps the simplest setting in which to investigate the relation
between unconditional and conditional generative modelling. We formulate data
imputation as an MDP and develop models capable of representing effective
policies for it. We construct the models using neural networks and train them
using a form of guided policy search. Our models generate predictions through
an iterative process of feedback and refinement. We show that this approach can
learn effective policies for imputation problems of varying difficulty and
across multiple datasets.
Learning Unfair Trading: a Market Manipulation Analysis From the Reinforcement Learning Perspective
Authors: Enrique Martínez-Miranda, Peter McBurney, Matthew J. Howard
Date: 2015-11-02 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Market manipulation is a strategy used by traders to alter the price of
financial securities. One type of manipulation is based on the process of
buying or selling assets by using several trading strategies, among them
spoofing is a popular strategy and is considered illegal by market regulators.
Some promising tools have been developed to detect manipulation, but cases can
still be found in the markets. In this paper we model spoofing and pinging
trading, two strategies that differ in the legal background but share the same
elemental concept of market manipulation. We use a reinforcement learning
framework within the full and partial observability of Markov decision
processes and analyse the underlying behaviour of the manipulators by finding
the causes of what encourages the traders to perform fraudulent activities.
This reveals procedures to counter the problem that may be helpful to market
regulators as our model predicts the activity of spoofers.
Are You Talking to a Machine? Dataset and Methods for Multilingual Image Question Answering
Authors: Haoyuan Gao, Junhua Mao, Jie zhou, Zhiheng Huang, Lei Wang, Wei Xu
Date: 2015-05-21 00:00:00
Proceeding: NeurIPS 2015
Tasks: Question Answering, Sentence, Visual Question Answering (VQA)

In this paper, we present the mQA model, which is able to answer questions
about the content of an image. The answer can be a sentence, a phrase or a
single word. Our model contains four components: a Long Short-Term Memory
(LSTM) to extract the question representation, a Convolutional Neural Network
(CNN) to extract the visual representation, an LSTM for storing the linguistic
context in an answer, and a fusing component to combine the information from
the first three components and generate the answer. We construct a Freestyle
Multilingual Image Question Answering (FM-IQA) dataset to train and evaluate
our mQA model. It contains over 150,000 images and 310,000 freestyle Chinese
question-answer pairs and their English translations. The quality of the
generated answers of our mQA model on this dataset is evaluated by human judges
through a Turing Test. Specifically, we mix the answers provided by humans and
our model. The human judges need to distinguish our model from the human. They
will also provide a score (i.e. 0, 1, 2, the larger the better) indicating the
quality of the answer. We propose strategies to monitor the quality of this
evaluation process. The experiments show that in 64.7% of cases, the human
judges cannot distinguish our model from humans. The average score is 1.454
(1.918 for human). The details of this work, including the FM-IQA dataset, can
be found on the project page: http://idl.baidu.com/FM-IQA.html
From random walks to distances on unweighted graphs
Authors: Tatsunori B. Hashimoto, Yi Sun, Tommi S. Jaakkola
Date: 2015-11-02 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Clustering

Large unweighted directed graphs are commonly used to capture relations
between entities. A fundamental problem in the analysis of such networks is to
properly define the similarity or dissimilarity between any two vertices.
Despite the significance of this problem, statistical characterization of the
proposed metrics has been limited. We introduce and develop a class of
techniques for analyzing random walks on graphs using stochastic calculus.
Using these techniques we generalize results on the degeneracy of hitting times
and analyze a metric based on the Laplace transformed hitting time (LTHT). The
metric serves as a natural, provably well-behaved alternative to the expected
hitting time. We establish a general correspondence between hitting times of
the Brownian motion and analogous hitting times on the graph. We show that the
LTHT is consistent with respect to the underlying metric of a geometric graph,
preserves clustering tendency, and remains robust against random addition of
non-geometric edges. Tests on simulated and real-world data show that the LTHT
matches theoretical predictions and outperforms alternatives.
Pixel-wise Segmentation of Street with Neural Networks
Authors: Sebastian Bittel, Vitali Kaiser, Marvin Teichmann, Martin Thoma
Date: 2015-11-02 00:00:00
Tasks: Object Recognition, regression, Self-Driving Cars

Pixel-wise street segmentation of photographs taken from a drivers
perspective is important for self-driving cars and can also support other
object recognition tasks. A framework called SST was developed to examine the
accuracy and execution time of different neural networks. The best neural
network achieved an $F_1$-score of 89.5% with a simple feedforward neural
network which trained to solve a regression task.
Learning Sampling Distributions for Efficient Object Detection
Authors: Yanwei Pang, Jiale Cao, Xuelong. Li
Date: 2015-08-23 00:00:00
Tasks: Face Detection, Object, object-detection, Object Detection

Object detection is an important task in computer vision and learning
systems. Multistage particle windows (MPW), proposed by Gualdi et al., is an
algorithm of fast and accurate object detection. By sampling particle windows
from a proposal distribution (PD), MPW avoids exhaustively scanning the image.
Despite its success, it is unknown how to determine the number of stages and
the number of particle windows in each stage. Moreover, it has to generate too
many particle windows in the initialization step and it redraws unnecessary too
many particle windows around object-like regions. In this paper, we attempt to
solve the problems of MPW. An important fact we used is that there is large
probability for a randomly generated particle window not to contain the object
because the object is a sparse event relevant to the huge number of candidate
windows. Therefore, we design the proposal distribution so as to efficiently
reject the huge number of non-object windows. Specifically, we propose the
concepts of rejection, acceptance, and ambiguity windows and regions. This
contrasts to MPW which utilizes only on region of support. The PD of MPW is
acceptance-oriented whereas the PD of our method (called iPW) is
rejection-oriented. Experimental results on human and face detection
demonstrate the efficiency and effectiveness of the iPW algorithm. The source
code is publicly accessible.
Circle detection using isosceles triangles sampling
Authors: Hanqing Zhang, Krister Wiklund, Magnus Andersson
Date: 2015-11-02 00:00:00
Tasks: Clustering

Detection of circular objects in digital images is an important problem in
several vision applications. Circle detection using randomized sampling has
been developed in recent years to reduce the computational intensity.
Randomized sampling, however, is sensitive to noise that can lead to reduced
accuracy and false-positive candidates. This paper presents a new circle
detection method based upon randomized isosceles triangles sampling to improve
the robustness of randomized circle detection in noisy conditions. It is shown
that the geometrical property of isosceles triangles provide a robust criterion
to find relevant edge pixels and thereby efficiently provide an estimation of
the circle center and radii. The estimated results given by the isosceles
triangles sampling from each connected component of edge map were analyzed
using a simple clustering approach for efficiency. To further improve on the
accuracy we applied a two-step refinement process using chords and linear error
compensation with gradient information of the edge pixels. Extensive
experiments using both synthetic and real images were presented and results
were compared to leading state-of-the-art algorithms and showed that the
proposed algorithm: are efficient in finding circles with a low number of
iterations; has high rejection rate of false-positive circle candidates; and
has high robustness against noise, making it adaptive and useful in many vision
applications.
Learning Constructive Primitives for Online Level Generation and Real-time Content Adaptation in Super Mario Bros
Authors: Peizhi Shi, Ke Chen
Date: 2015-10-27 00:00:00
Tasks: Game Design

Procedural content generation (PCG) is of great interest to game design and
development as it generates game content automatically. Motivated by the recent
learning-based PCG framework and other existing PCG works, we propose an
alternative approach to online content generation and adaptation in Super Mario
Bros (SMB). Unlike most of existing works in SMB, our approach exploits the
synergy between rule-based and learning-based methods to produce constructive
primitives, quality yet controllable game segments in SMB. As a result, a
complete quality game level can be generated online by integrating relevant
constructive primitives via controllable parameters regarding geometrical
features and procedure-level properties. Also the adaptive content can be
generated in real time by dynamically selecting proper constructive primitives
via an adaptation criterion, e.g., dynamic difficulty adjustment (DDA). Our
approach is of several favorable properties in terms of content quality
assurance, generation efficiency and controllability. Extensive simulation
results demonstrate that the proposed approach can generate controllable yet
quality game levels online and adaptable content for DDA in real time.
Bidirectional Recurrent Neural Networks as Generative Models - Reconstructing Gaps in Time Series
Authors: Mathias Berglund, Tapani Raiko, Mikko Honkala, Leo Kärkkäinen, Akos Vetek, Juha Karhunen
Date: 2015-04-07 00:00:00
Proceeding: NeurIPS 2015
Tasks: Bayesian Inference, Time Series, Time Series Analysis

Bidirectional recurrent neural networks (RNN) are trained to predict both in
the positive and negative time directions simultaneously. They have not been
used commonly in unsupervised tasks, because a probabilistic interpretation of
the model has been difficult. Recently, two different frameworks, GSN and NADE,
provide a connection between reconstruction and probabilistic modeling, which
makes the interpretation possible. As far as we know, neither GSN or NADE have
been studied in the context of time series before. As an example of an
unsupervised task, we study the problem of filling in gaps in high-dimensional
time series with complex dynamics. Although unidirectional RNNs have recently
been trained successfully to model such time series, inference in the negative
time direction is non-trivial. We propose two probabilistic interpretations of
bidirectional RNNs that can be used to reconstruct missing gaps efficiently.
Our experiments on text data show that both proposed methods are much more
accurate than unidirectional reconstructions, although a bit less accurate than
a computationally complex bidirectional Bayesian inference on the
unidirectional RNN. We also provide results on music data for which the
Bayesian inference is computationally infeasible, demonstrating the scalability
of the proposed methods.
Z Specification for the W3C Editor's Draft Core SHACL Semantics
Authors: Arthur Ryman
Date: 2015-11-02 00:00:00

This article provides a formalization of the W3C Draft Core SHACL Semantics
specification using Z notation. This formalization exercise has identified a
number of quality issues in the draft. It has also established that the
recursive definitions in the draft are well-founded. Further formal validation
of the draft will require the use of an executable specification technology.