October 19, 2019

3012 words 15 mins read

Paper Group ANR 293

Pure-Exploration for Infinite-Armed Bandits with General Arm Reservoirs. NegPSpan: efficient extraction of negative sequential patterns with embedding constraints. Object Detection and Classification in Occupancy Grid Maps using Deep Convolutional Networks. Free-rider Episode Screening via Dual Partition Model. Revisiting Projection-Free Optimizati …

Pure-Exploration for Infinite-Armed Bandits with General Arm Reservoirs


Title	Pure-Exploration for Infinite-Armed Bandits with General Arm Reservoirs
Authors	Maryam Aziz, Kevin Jamieson, Javed Aslam
Abstract	This paper considers a multi-armed bandit game where the number of arms is much larger than the maximum budget and is effectively infinite. We characterize necessary and sufficient conditions on the total budget for an algorithm to return an {\epsilon}-good arm with probability at least 1 - {\delta}. In such situations, the sample complexity depends on {\epsilon}, {\delta} and the so-called reservoir distribution {\nu} from which the means of the arms are drawn iid. While a substantial literature has developed around analyzing specific cases of {\nu} such as the beta distribution, our analysis makes no assumption about the form of {\nu}. Our algorithm is based on successive halving with the surprising exception that arms start to be discarded after just a single pull, requiring an analysis that goes beyond concentration alone. The provable correctness of this algorithm also provides an explanation for the empirical observation that the most aggressive bracket of the Hyperband algorithm of Li et al. (2017) for hyperparameter tuning is almost always best.
Tasks
Published	2018-11-15
URL	http://arxiv.org/abs/1811.06149v2
PDF	http://arxiv.org/pdf/1811.06149v2.pdf
PWC	https://paperswithcode.com/paper/pure-exploration-for-infinite-armed-bandits
Repo
Framework

NegPSpan: efficient extraction of negative sequential patterns with embedding constraints


Title	NegPSpan: efficient extraction of negative sequential patterns with embedding constraints
Authors	Thomas Guyet, René Quiniou
Abstract	Mining frequent sequential patterns consists in extracting recurrent behaviors, modeled as patterns, in a big sequence dataset. Such patterns inform about which events are frequently observed in sequences, i.e. what does really happen. Sometimes, knowing that some specific event does not happen is more informative than extracting a lot of observed events. Negative sequential patterns (NSP) formulate recurrent behaviors by patterns containing both observed events and absent events. Few approaches have been proposed to mine such NSPs. In addition, the syntax and semantics of NSPs differ in the different methods which makes it difficult to compare them. This article provides a unified framework for the formulation of the syntax and the semantics of NSPs. Then, we introduce a new algorithm, NegPSpan, that extracts NSPs using a PrefixSpan depth-first scheme and enabling maxgap constraints that other approaches do not take into account. The formal framework allows for highlighting the differences between the proposed approach wrt to the methods from the literature, especially wrt the state of the art approach eNSP. Intensive experiments on synthetic and real datasets show that NegPSpan can extract meaningful NSPs and that it can process bigger datasets than eNSP thanks to significantly lower memory requirements and better computation times.
Tasks
Published	2018-04-04
URL	http://arxiv.org/abs/1804.01256v2
PDF	http://arxiv.org/pdf/1804.01256v2.pdf
PWC	https://paperswithcode.com/paper/negpspan-efficient-extraction-of-negative
Repo
Framework

Object Detection and Classification in Occupancy Grid Maps using Deep Convolutional Networks


Title	Object Detection and Classification in Occupancy Grid Maps using Deep Convolutional Networks
Authors	Sascha Wirges, Tom Fischer, Jesus Balado Frias, Christoph Stiller
Abstract	A detailed environment perception is a crucial component of automated vehicles. However, to deal with the amount of perceived information, we also require segmentation strategies. Based on a grid map environment representation, well-suited for sensor fusion, free-space estimation and machine learning, we detect and classify objects using deep convolutional neural networks. As input for our networks we use a multi-layer grid map efficiently encoding 3D range sensor information. The inference output consists of a list of rotated bounding boxes with associated semantic classes. We conduct extensive ablation studies, highlight important design considerations when using grid maps and evaluate our models on the KITTI Bird’s Eye View benchmark. Qualitative and quantitative benchmark results show that we achieve robust detection and state of the art accuracy solely using top-view grid maps from range sensor data.
Tasks	Object Detection, Sensor Fusion
Published	2018-05-02
URL	http://arxiv.org/abs/1805.08689v2
PDF	http://arxiv.org/pdf/1805.08689v2.pdf
PWC	https://paperswithcode.com/paper/object-detection-and-classification-in
Repo
Framework

Free-rider Episode Screening via Dual Partition Model


Title	Free-rider Episode Screening via Dual Partition Model
Authors	Xiang Ao, Yang Liu, Zhen Huang, Luo Zuo, Qing He
Abstract	One of the drawbacks of frequent episode mining is that overwhelmingly many of the discovered patterns are redundant. Free-rider episode, as a typical example, consists of a real pattern doped with some additional noise events. Because of the possible high support of the inside noise events, such free-rider episodes may have abnormally high support that they cannot be filtered by frequency based framework. An effective technique for filtering free-rider episodes is using a partition model to divide an episode into two consecutive subepisodes and comparing the observed support of such episode with its expected support under the assumption that these two subepisodes occur independently. In this paper, we take more complex subepisodes into consideration and develop a novel partition model named EDP for free-rider episode filtering from a given set of episodes. It combines (1) a dual partition strategy which divides an episode to an underlying real pattern and potential noises; (2) a novel definition of the expected support of a free-rider episode based on the proposed partition strategy. We can deem the episode interesting if the observed support is substantially higher than the expected support estimated by our model. The experiments on synthetic and real-world datasets demonstrate EDP can effectively filter free-rider episodes compared with existing state-of-the-arts.
Tasks
Published	2018-05-19
URL	http://arxiv.org/abs/1805.07505v1
PDF	http://arxiv.org/pdf/1805.07505v1.pdf
PWC	https://paperswithcode.com/paper/free-rider-episode-screening-via-dual
Repo
Framework

Revisiting Projection-Free Optimization for Strongly Convex Constraint Sets


Title	Revisiting Projection-Free Optimization for Strongly Convex Constraint Sets
Authors	Jarrid Rector-Brooks, Jun-Kun Wang, Barzan Mozafari
Abstract	We revisit the Frank-Wolfe (FW) optimization under strongly convex constraint sets. We provide a faster convergence rate for FW without line search, showing that a previously overlooked variant of FW is indeed faster than the standard variant. With line search, we show that FW can converge to the global optimum, even for smooth functions that are not convex, but are quasi-convex and locally-Lipschitz. We also show that, for the general case of (smooth) non-convex functions, FW with line search converges with high probability to a stationary point at a rate of $O\left(\frac{1}{t}\right)$, as long as the constraint set is strongly convex – one of the fastest convergence rates in non-convex optimization.
Tasks
Published	2018-11-14
URL	http://arxiv.org/abs/1811.05831v3
PDF	http://arxiv.org/pdf/1811.05831v3.pdf
PWC	https://paperswithcode.com/paper/revisiting-projection-free-optimization-for
Repo
Framework

Deep Learning Approximation: Zero-Shot Neural Network Speedup


Title	Deep Learning Approximation: Zero-Shot Neural Network Speedup
Authors	Michele Pratusevich
Abstract	Neural networks offer high-accuracy solutions to a range of problems, but are costly to run in production systems because of computational and memory requirements during a forward pass. Given a trained network, we propose a techique called Deep Learning Approximation to build a faster network in a tiny fraction of the time required for training by only manipulating the network structure and coefficients without requiring re-training or access to the training data. Speedup is achieved by by applying a sequential series of independent optimizations that reduce the floating-point operations (FLOPs) required to perform a forward pass. First, lossless optimizations are applied, followed by lossy approximations using singular value decomposition (SVD) and low-rank matrix decomposition. The optimal approximation is chosen by weighing the relative accuracy loss and FLOP reduction according to a single parameter specified by the user. On PASCAL VOC 2007 with the YOLO network, we show an end-to-end 2x speedup in a network forward pass with a 5% drop in mAP that can be re-gained by finetuning.
Tasks
Published	2018-06-15
URL	http://arxiv.org/abs/1806.05779v1
PDF	http://arxiv.org/pdf/1806.05779v1.pdf
PWC	https://paperswithcode.com/paper/deep-learning-approximation-zero-shot-neural
Repo
Framework

Bootstrapping Deep Neural Networks from Approximate Image Processing Pipelines


Title	Bootstrapping Deep Neural Networks from Approximate Image Processing Pipelines
Authors	Kilho Son, Jesse Hostetler, Sek Chai
Abstract	Complex image processing and computer vision systems often consist of a processing pipeline of functional modules. We intend to replace parts or all of a target pipeline with deep neural networks to achieve benefits such as increased accuracy or reduced computational requirement. To acquire a large amount of labeled data necessary to train the deep neural network, we propose a workflow that leverages the target pipeline to create a significantly larger labeled training set automatically, without prior domain knowledge of the target pipeline. We show experimentally that despite the noise introduced by automated labeling and only using a very small initially labeled data set, the trained deep neural networks can achieve similar or even better performance than the components they replace, while in some cases also reducing computational requirements.
Tasks
Published	2018-11-29
URL	http://arxiv.org/abs/1811.12108v2
PDF	http://arxiv.org/pdf/1811.12108v2.pdf
PWC	https://paperswithcode.com/paper/bootstrapping-deep-neural-networks-from
Repo
Framework

Learning Temporal Point Processes via Reinforcement Learning


Title	Learning Temporal Point Processes via Reinforcement Learning
Authors	Shuang Li, Shuai Xiao, Shixiang Zhu, Nan Du, Yao Xie, Le Song
Abstract	Social goods, such as healthcare, smart city, and information networks, often produce ordered event data in continuous time. The generative processes of these event data can be very complex, requiring flexible models to capture their dynamics. Temporal point processes offer an elegant framework for modeling event data without discretizing the time. However, the existing maximum-likelihood-estimation (MLE) learning paradigm requires hand-crafting the intensity function beforehand and cannot directly monitor the goodness-of-fit of the estimated model in the process of training. To alleviate the risk of model-misspecification in MLE, we propose to generate samples from the generative model and monitor the quality of the samples in the process of training until the samples and the real data are indistinguishable. We take inspiration from reinforcement learning (RL) and treat the generation of each event as the action taken by a stochastic policy. We parameterize the policy as a flexible recurrent neural network and gradually improve the policy to mimic the observed event distribution. Since the reward function is unknown in this setting, we uncover an analytic and nonparametric form of the reward function using an inverse reinforcement learning formulation. This new RL framework allows us to derive an efficient policy gradient algorithm for learning flexible point process models, and we show that it performs well in both synthetic and real data.
Tasks	Point Processes
Published	2018-11-12
URL	http://arxiv.org/abs/1811.05016v1
PDF	http://arxiv.org/pdf/1811.05016v1.pdf
PWC	https://paperswithcode.com/paper/learning-temporal-point-processes-via
Repo
Framework

BEBP: An Poisoning Method Against Machine Learning Based IDSs


Title	BEBP: An Poisoning Method Against Machine Learning Based IDSs
Authors	Pan Li, Qiang Liu, Wentao Zhao, Dongxu Wang, Siqi Wang
Abstract	In big data era, machine learning is one of fundamental techniques in intrusion detection systems (IDSs). However, practical IDSs generally update their decision module by feeding new data then retraining learning models in a periodical way. Hence, some attacks that comprise the data for training or testing classifiers significantly challenge the detecting capability of machine learning-based IDSs. Poisoning attack, which is one of the most recognized security threats towards machine learning-based IDSs, injects some adversarial samples into the training phase, inducing data drifting of training data and a significant performance decrease of target IDSs over testing data. In this paper, we adopt the Edge Pattern Detection (EPD) algorithm to design a novel poisoning method that attack against several machine learning algorithms used in IDSs. Specifically, we propose a boundary pattern detection algorithm to efficiently generate the points that are near to abnormal data but considered to be normal ones by current classifiers. Then, we introduce a Batch-EPD Boundary Pattern (BEBP) detection algorithm to overcome the limitation of the number of edge pattern points generated by EPD and to obtain more useful adversarial samples. Based on BEBP, we further present a moderate but effective poisoning method called chronic poisoning attack. Extensive experiments on synthetic and three real network data sets demonstrate the performance of the proposed poisoning method against several well-known machine learning algorithms and a practical intrusion detection method named FMIFS-LSSVM-IDS.
Tasks	Intrusion Detection
Published	2018-03-11
URL	http://arxiv.org/abs/1803.03965v1
PDF	http://arxiv.org/pdf/1803.03965v1.pdf
PWC	https://paperswithcode.com/paper/bebp-an-poisoning-method-against-machine
Repo
Framework

Sparse Travel Time Estimation from Streaming Data


Title	Sparse Travel Time Estimation from Streaming Data
Authors	Saif Eddin Jabari, Nikolaos M. Freris, Deepthi Mary Dilip
Abstract	We address two shortcomings in online travel time estimation methods for congested urban traffic. The first shortcoming is related to the determination of the number of mixture modes, which can change dynamically, within day and from day to day. The second shortcoming is the wide-spread use of Gaussian probability densities as mixture components. Gaussian densities fail to capture the positive skew in travel time distributions and, consequently, large numbers of mixture components are needed for reasonable fitting accuracy when applied as mixture components. They also assign positive probabilities to negative travel times. To address these issues, this paper derives a mixture distribution with Gamma component densities, which are asymmetric and supported on the positive numbers. We use sparse estimation techniques to ensure parsimonious models and propose a generalization of Gamma mixture densities using Mittag-Leffler functions, which provides enhanced fitting flexibility and improved parsimony. In order to accommodate within-day variability and allow for online implementation of the proposed methodology (i.e., fast computations on streaming travel time data), we introduce a recursive algorithm which efficiently updates the fitted distribution whenever new data become available. Experimental results using real-world travel time data illustrate the efficacy of the proposed methods.
Tasks
Published	2018-04-22
URL	https://arxiv.org/abs/1804.08130v4
PDF	https://arxiv.org/pdf/1804.08130v4.pdf
PWC	https://paperswithcode.com/paper/sparse-travel-time-estimation-from-streaming
Repo
Framework

An Application of ASP Theories of Intentions to Understanding Restaurant Scenarios: Insights and Narrative Corpus


Title	An Application of ASP Theories of Intentions to Understanding Restaurant Scenarios: Insights and Narrative Corpus
Authors	Qinglin Zhang, Chris Benton, Daniela Inclezan
Abstract	This paper presents a practical application of Answer Set Programming to the understanding of narratives about restaurants. While this task was investigated in depth by Erik Mueller, exceptional scenarios remained a serious challenge for his script-based story comprehension system. We present a methodology that remedies this issue by modeling characters in a restaurant episode as intentional agents. We focus especially on the refinement of certain components of this methodology in order to increase coverage and performance. We present a restaurant story corpus that we created to design and evaluate our methodology. Under consideration in Theory and Practice of Logic Programming (TPLP).
Tasks
Published	2018-09-30
URL	http://arxiv.org/abs/1810.00445v1
PDF	http://arxiv.org/pdf/1810.00445v1.pdf
PWC	https://paperswithcode.com/paper/an-application-of-asp-theories-of-intentions
Repo
Framework

LexNLP: Natural language processing and information extraction for legal and regulatory texts


Title	LexNLP: Natural language processing and information extraction for legal and regulatory texts
Authors	Michael J Bommarito II, Daniel Martin Katz, Eric M Detterman
Abstract	LexNLP is an open source Python package focused on natural language processing and machine learning for legal and regulatory text. The package includes functionality to (i) segment documents, (ii) identify key text such as titles and section headings, (iii) extract over eighteen types of structured information like distances and dates, (iv) extract named entities such as companies and geopolitical entities, (v) transform text into features for model training, and (vi) build unsupervised and supervised models such as word embedding or tagging models. LexNLP includes pre-trained models based on thousands of unit tests drawn from real documents available from the SEC EDGAR database as well as various judicial and regulatory proceedings. LexNLP is designed for use in both academic research and industrial applications, and is distributed at https://github.com/LexPredict/lexpredict-lexnlp.
Tasks
Published	2018-06-10
URL	http://arxiv.org/abs/1806.03688v1
PDF	http://arxiv.org/pdf/1806.03688v1.pdf
PWC	https://paperswithcode.com/paper/lexnlp-natural-language-processing-and
Repo
Framework

A Deep Learning Approach to the Inversion of Borehole Resistivity Measurements


Title	A Deep Learning Approach to the Inversion of Borehole Resistivity Measurements
Authors	M. Shahriari, D. Pardo, A. Picón, A. Galdrán, J. Del Ser, C. Torres-Verdín
Abstract	We use borehole resistivity measurements to map the electrical properties of the subsurface and to increase the productivity of a reservoir. When used for geosteering purposes, it becomes essential to invert them in real time. In this work, we explore the possibility of using Deep Neural Network (DNN) to perform a rapid inversion of borehole resistivity measurements. Herein, we build a DNN that approximates the following inverse problem: given a set of borehole resistivity measurements, the DNN is designed to deliver a physically meaningful and data-consistent piecewise one-dimensional layered model of the surrounding subsurface. Once the DNN is built, we can perform the actual inversion of the field measurements in real time. We illustrate the performance of DNN of logging-while-drilling measurements acquired on high-angle wells via synthetic data.
Tasks
Published	2018-10-05
URL	http://arxiv.org/abs/1810.04522v2
PDF	http://arxiv.org/pdf/1810.04522v2.pdf
PWC	https://paperswithcode.com/paper/a-deep-learning-approach-to-the-inversion-of
Repo
Framework

Semantic Explanations of Predictions


Title	Semantic Explanations of Predictions
Authors	Freddy Lecue, Jiewen Wu
Abstract	The main objective of explanations is to transmit knowledge to humans. This work proposes to construct informative explanations for predictions made from machine learning models. Motivated by the observations from social sciences, our approach selects data points from the training sample that exhibit special characteristics crucial for explanation, for instance, ones contrastive to the classification prediction and ones representative of the models. Subsequently, semantic concepts are derived from the selected data points through the use of domain ontologies. These concepts are filtered and ranked to produce informative explanations that improves human understanding. The main features of our approach are that (1) knowledge about explanations is captured in the form of ontological concepts, (2) explanations include contrastive evidences in addition to normal evidences, and (3) explanations are user relevant.
Tasks
Published	2018-05-27
URL	http://arxiv.org/abs/1805.10587v1
PDF	http://arxiv.org/pdf/1805.10587v1.pdf
PWC	https://paperswithcode.com/paper/semantic-explanations-of-predictions
Repo
Framework

What do RNN Language Models Learn about Filler-Gap Dependencies?


Title	What do RNN Language Models Learn about Filler-Gap Dependencies?
Authors	Ethan Wilcox, Roger Levy, Takashi Morita, Richard Futrell
Abstract	RNN language models have achieved state-of-the-art perplexity results and have proven useful in a suite of NLP tasks, but it is as yet unclear what syntactic generalizations they learn. Here we investigate whether state-of-the-art RNN language models represent long-distance filler-gap dependencies and constraints on them. Examining RNN behavior on experimentally controlled sentences designed to expose filler-gap dependencies, we show that RNNs can represent the relationship in multiple syntactic positions and over large spans of text. Furthermore, we show that RNNs learn a subset of the known restrictions on filler-gap dependencies, known as island constraints: RNNs show evidence for wh-islands, adjunct islands, and complex NP islands. These studies demonstrates that state-of-the-art RNN models are able to learn and generalize about empty syntactic positions.
Tasks
Published	2018-08-31
URL	http://arxiv.org/abs/1809.00042v1
PDF	http://arxiv.org/pdf/1809.00042v1.pdf
PWC	https://paperswithcode.com/paper/what-do-rnn-language-models-learn-about-1
Repo
Framework