January 25, 2020

3234 words 16 mins read

Paper Group ANR 1672

Stability of decision trees and logistic regression. What You See Is What You Get? The Impact of Representation Criteria on Human Bias in Hiring. Testing randomness. Q-MIND: Defeating Stealthy DoS Attacks in SDN with a Machine-learning based Defense Framework. Program Synthesis and Semantic Parsing with Learned Code Idioms. Interpretable Self-Atten …

Stability of decision trees and logistic regression


Title	Stability of decision trees and logistic regression
Authors	Nino Arsov, Martin Pavlovski, Ljupco Kocarev
Abstract	Decision trees and logistic regression are one of the most popular and well-known machine learning algorithms, frequently used to solve a variety of real-world problems. Stability of learning algorithms is a powerful tool to analyze their performance and sensitivity and subsequently allow researchers to draw reliable conclusions. The stability of these two algorithms has remained obscure. To that end, in this paper, we derive two stability notions for decision trees and logistic regression: hypothesis and pointwise hypothesis stability. Additionally, we derive these notions for L2-regularized logistic regression and confirm existing findings that it is uniformly stable. We show that the stability of decision trees depends on the number of leaves in the tree, i.e., its depth, while for logistic regression, it depends on the smallest eigenvalue of the Hessian matrix of the cross-entropy loss. We show that logistic regression is not a stable learning algorithm. We construct the upper bounds on the generalization error of all three algorithms. Moreover, we present a novel stability measuring framework that allows one to measure the aforementioned notions of stability. The measures are equivalent to estimates of expected loss differences at an input example and then leverage bootstrap sampling to yield statistically reliable estimates. Finally, we apply this framework to the three algorithms analyzed in this paper to confirm our theoretical findings and, in addition, we discuss the possibilities of developing new training techniques to optimize the stability of logistic regression, and hence decrease its generalization error.
Tasks
Published	2019-03-03
URL	http://arxiv.org/abs/1903.00816v1
PDF	http://arxiv.org/pdf/1903.00816v1.pdf
PWC	https://paperswithcode.com/paper/stability-of-decision-trees-and-logistic
Repo
Framework

What You See Is What You Get? The Impact of Representation Criteria on Human Bias in Hiring


Title	What You See Is What You Get? The Impact of Representation Criteria on Human Bias in Hiring
Authors	Andi Peng, Besmira Nushi, Emre Kiciman, Kori Inkpen, Siddharth Suri, Ece Kamar
Abstract	Although systematic biases in decision-making are widely documented, the ways in which they emerge from different sources is less understood. We present a controlled experimental platform to study gender bias in hiring by decoupling the effect of world distribution (the gender breakdown of candidates in a specific profession) from bias in human decision-making. We explore the effectiveness of \textit{representation criteria}, fixed proportional display of candidates, as an intervention strategy for mitigation of gender bias by conducting experiments measuring human decision-makers’ rankings for who they would recommend as potential hires. Experiments across professions with varying gender proportions show that balancing gender representation in candidate slates can correct biases for some professions where the world distribution is skewed, although doing so has no impact on other professions where human persistent preferences are at play. We show that the gender of the decision-maker, complexity of the decision-making task and over- and under-representation of genders in the candidate slate can all impact the final decision. By decoupling sources of bias, we can better isolate strategies for bias mitigation in human-in-the-loop systems.
Tasks	Decision Making
Published	2019-09-08
URL	https://arxiv.org/abs/1909.03567v1
PDF	https://arxiv.org/pdf/1909.03567v1.pdf
PWC	https://paperswithcode.com/paper/what-you-see-is-what-you-get-the-impact-of
Repo
Framework

Testing randomness


Title	Testing randomness
Authors	Vladimir Vovk
Abstract	The hypothesis of randomness is fundamental in statistical machine learning and in many areas of nonparametric statistics; it says that the observations are assumed to be independent and coming from the same unknown probability distribution. This hypothesis is close, in certain respects, to the hypothesis of exchangeability, which postulates that the distribution of the observations is invariant with respect to their permutations. This paper reviews known methods of testing the two hypotheses concentrating on the online mode of testing, when the observations arrive sequentially. All known online methods for testing these hypotheses are based on conformal martingales, which are defined and studied in detail. The paper emphasizes conceptual and practical aspects and states two kinds of results. Validity results limit the probability of a false alarm or the frequency of false alarms for various procedures based on conformal martingales, including conformal versions of the CUSUM and Shiryaev-Roberts procedures. Efficiency results establish connections between randomness, exchangeability, and conformal martingales.
Tasks
Published	2019-06-21
URL	https://arxiv.org/abs/1906.09256v3
PDF	https://arxiv.org/pdf/1906.09256v3.pdf
PWC	https://paperswithcode.com/paper/power-and-limitations-of-conformal
Repo
Framework

Q-MIND: Defeating Stealthy DoS Attacks in SDN with a Machine-learning based Defense Framework


Title	Q-MIND: Defeating Stealthy DoS Attacks in SDN with a Machine-learning based Defense Framework
Authors	Trung V. Phan, T M Rayhan Gias, Syed Tasnimul Islam, Truong Thu Huong, Nguyen Huu Thanh, Thomas Bauschert
Abstract	Software Defined Networking (SDN) enables flexible and scalable network control and management. However, it also introduces new vulnerabilities that can be exploited by attackers. In particular, low-rate and slow or stealthy Denial-of-Service (DoS) attacks are recently attracting attention from researchers because of their detection challenges. In this paper, we propose a novel machine learning based defense framework named Q-MIND, to effectively detect and mitigate stealthy DoS attacks in SDN-based networks. We first analyze the adversary model of stealthy DoS attacks, the related vulnerabilities in SDN-based networks and the key characteristics of stealthy DoS attacks. Next, we describe and analyze an anomaly detection system that uses a Reinforcement Learning-based approach based on Q-Learning in order to maximize its detection performance. Finally, we outline the complete Q-MIND defense framework that incorporates the optimal policy derived from the Q-Learning agent to efficiently defeat stealthy DoS attacks in SDN-based networks. An extensive comparison of the Q-MIND framework and currently existing methods shows that significant improvements in attack detection and mitigation performance are obtained by Q-MIND.
Tasks	Anomaly Detection, Q-Learning
Published	2019-07-27
URL	https://arxiv.org/abs/1907.11887v2
PDF	https://arxiv.org/pdf/1907.11887v2.pdf
PWC	https://paperswithcode.com/paper/q-mind-defeating-stealthy-dos-attacks-in-sdn
Repo
Framework

Program Synthesis and Semantic Parsing with Learned Code Idioms


Title	Program Synthesis and Semantic Parsing with Learned Code Idioms
Authors	Richard Shin, Miltiadis Allamanis, Marc Brockschmidt, Oleksandr Polozov
Abstract	Program synthesis of general-purpose source code from natural language specifications is challenging due to the need to reason about high-level patterns in the target program and low-level implementation details at the same time. In this work, we present PATOIS, a system that allows a neural program synthesizer to explicitly interleave high-level and low-level reasoning at every generation step. It accomplishes this by automatically mining common code idioms from a given corpus, incorporating them into the underlying language for neural synthesis, and training a tree-based neural synthesizer to use these idioms during code generation. We evaluate PATOIS on two complex semantic parsing datasets and show that using learned code idioms improves the synthesizer’s accuracy.
Tasks	Code Generation, Program Synthesis, Semantic Parsing
Published	2019-06-26
URL	https://arxiv.org/abs/1906.10816v4
PDF	https://arxiv.org/pdf/1906.10816v4.pdf
PWC	https://paperswithcode.com/paper/program-synthesis-and-semantic-parsing-with
Repo
Framework

Interpretable Self-Attention Temporal Reasoning for Driving Behavior Understanding


Title	Interpretable Self-Attention Temporal Reasoning for Driving Behavior Understanding
Authors	Yi-Chieh Liu, Yung-An Hsieh, Min-Hung Chen, Chao-Han Huck Yang, Jesper Tegner, Yi-Chang James Tsai
Abstract	Performing driving behaviors based on causal reasoning is essential to ensure driving safety. In this work, we investigated how state-of-the-art 3D Convolutional Neural Networks (CNNs) perform on classifying driving behaviors based on causal reasoning. We proposed a perturbation-based visual explanation method to inspect the models’ performance visually. By examining the video attention saliency, we found that existing models could not precisely capture the causes (e.g., traffic light) of the specific action (e.g., stopping). Therefore, the Temporal Reasoning Block (TRB) was proposed and introduced to the models. With the TRB models, we achieved the accuracy of $\mathbf{86.3%}$, which outperform the state-of-the-art 3D CNNs from previous works. The attention saliency also demonstrated that TRB helped models focus on the causes more precisely. With both numerical and visual evaluations, we concluded that our proposed TRB models were able to provide accurate driving behavior prediction by learning the causal reasoning of the behaviors.
Tasks
Published	2019-11-06
URL	https://arxiv.org/abs/1911.02172v1
PDF	https://arxiv.org/pdf/1911.02172v1.pdf
PWC	https://paperswithcode.com/paper/interpretable-self-attention-temporal
Repo
Framework

Potential-Based Advice for Stochastic Policy Learning


Title	Potential-Based Advice for Stochastic Policy Learning
Authors	Baicen Xiao, Bhaskar Ramasubramanian, Andrew Clark, Hannaneh Hajishirzi, Linda Bushnell, Radha Poovendran
Abstract	This paper augments the reward received by a reinforcement learning agent with potential functions in order to help the agent learn (possibly stochastic) optimal policies. We show that a potential-based reward shaping scheme is able to preserve optimality of stochastic policies, and demonstrate that the ability of an agent to learn an optimal policy is not affected when this scheme is augmented to soft Q-learning. We propose a method to impart potential based advice schemes to policy gradient algorithms. An algorithm that considers an advantage actor-critic architecture augmented with this scheme is proposed, and we give guarantees on its convergence. Finally, we evaluate our approach on a puddle-jump grid world with indistinguishable states, and the continuous state and action mountain car environment from classical control. Our results indicate that these schemes allow the agent to learn a stochastic optimal policy faster and obtain a higher average reward.
Tasks	Q-Learning
Published	2019-07-20
URL	https://arxiv.org/abs/1907.08823v1
PDF	https://arxiv.org/pdf/1907.08823v1.pdf
PWC	https://paperswithcode.com/paper/potential-based-advice-for-stochastic-policy
Repo
Framework

XL-Editor: Post-editing Sentences with XLNet


Title	XL-Editor: Post-editing Sentences with XLNet
Authors	Yong-Siang Shih, Wei-Cheng Chang, Yiming Yang
Abstract	While neural sequence generation models achieve initial success for many NLP applications, the canonical decoding procedure with left-to-right generation order (i.e., autoregressive) in one-pass can not reflect the true nature of human revising a sentence to obtain a refined result. In this work, we propose XL-Editor, a novel training framework that enables state-of-the-art generalized autoregressive pretraining methods, XLNet specifically, to revise a given sentence by the variable-length insertion probability. Concretely, XL-Editor can (1) estimate the probability of inserting a variable-length sequence into a specific position of a given sentence; (2) execute post-editing operations such as insertion, deletion, and replacement based on the estimated variable-length insertion probability; (3) complement existing sequence-to-sequence models to refine the generated sequences. Empirically, we first demonstrate better post-editing capabilities of XL-Editor over XLNet on the text insertion and deletion tasks, which validates the effectiveness of our proposed framework. Furthermore, we extend XL-Editor to the unpaired text style transfer task, where transferring the target style onto a given sentence can be naturally viewed as post-editing the sentence into the target style. XL-Editor achieves significant improvement in style transfer accuracy and also maintains coherent semantic of the original sentence, showing the broad applicability of our method.
Tasks	Style Transfer, Text Style Transfer
Published	2019-10-19
URL	https://arxiv.org/abs/1910.10479v1
PDF	https://arxiv.org/pdf/1910.10479v1.pdf
PWC	https://paperswithcode.com/paper/xl-editor-post-editing-sentences-with-xlnet
Repo
Framework

SySCD: A System-Aware Parallel Coordinate Descent Algorithm


Title	SySCD: A System-Aware Parallel Coordinate Descent Algorithm
Authors	Nikolas Ioannou, Celestine Mendler-Dünner, Thomas Parnell
Abstract	In this paper we propose a novel parallel stochastic coordinate descent (SCD) algorithm with convergence guarantees that exhibits strong scalability. We start by studying a state-of-the-art parallel implementation of SCD and identify scalability as well as system-level performance bottlenecks of the respective implementation. We then take a principled approach to develop a new SCD variant which is designed to avoid the identified system bottlenecks, such as limited scaling due to coherence traffic of model sharing across threads, and inefficient CPU cache accesses. Our proposed system-aware parallel coordinate descent algorithm (SySCD) scales to many cores and across numa nodes, and offers a consistent bottom line speedup in training time of up to x12 compared to an optimized asynchronous parallel SCD algorithm and up to x42, compared to state-of-the-art GLM solvers (scikit-learn, Vowpal Wabbit, and H2O) on a range of datasets and multi-core CPU architectures.
Tasks
Published	2019-11-18
URL	https://arxiv.org/abs/1911.07722v1
PDF	https://arxiv.org/pdf/1911.07722v1.pdf
PWC	https://paperswithcode.com/paper/syscd-a-system-aware-parallel-coordinate-1
Repo
Framework

Shaping the Narrative Arc: An Information-Theoretic Approach to Collaborative Dialogue


Title	Shaping the Narrative Arc: An Information-Theoretic Approach to Collaborative Dialogue
Authors	Kory W. Mathewson, Pablo Samuel Castro, Colin Cherry, George Foster, Marc G. Bellemare
Abstract	We consider the problem of designing an artificial agent capable of interacting with humans in collaborative dialogue to produce creative, engaging narratives. In this task, the goal is to establish universe details, and to collaborate on an interesting story in that universe, through a series of natural dialogue exchanges. Our model can augment any probabilistic conversational agent by allowing it to reason about universe information established and what potential next utterances might reveal. Ideally, with each utterance, agents would reveal just enough information to add specificity and reduce ambiguity without limiting the conversation. We empirically show that our model allows control over the rate at which the agent reveals information and that doing so significantly improves accuracy in predicting the next line of dialogues from movies. We close with a case-study with four professional theatre performers, who preferred interactions with our model-augmented agent over an unaugmented agent.
Tasks
Published	2019-01-31
URL	http://arxiv.org/abs/1901.11528v1
PDF	http://arxiv.org/pdf/1901.11528v1.pdf
PWC	https://paperswithcode.com/paper/shaping-the-narrative-arc-an-information
Repo
Framework

Linear Speedup in Saddle-Point Escape for Decentralized Non-Convex Optimization


Title	Linear Speedup in Saddle-Point Escape for Decentralized Non-Convex Optimization
Authors	Stefan Vlaski, Ali H. Sayed
Abstract	Under appropriate cooperation protocols and parameter choices, fully decentralized solutions for stochastic optimization have been shown to match the performance of centralized solutions and result in linear speedup (in the number of agents) relative to non-cooperative approaches in the strongly-convex setting. More recently, these results have been extended to the pursuit of first-order stationary points in non-convex environments. In this work, we examine in detail the dependence of second-order convergence guarantees on the spectral properties of the combination policy for non-convex multi agent optimization. We establish linear speedup in saddle-point escape time in the number of agents for symmetric combination policies and study the potential for further improvement by employing asymmetric combination weights. The results imply that a linear speedup can be expected in the pursuit of second-order stationary points, which exclude local maxima as well as strict saddle-points and correspond to local or even global minima in many important learning settings.
Tasks	Stochastic Optimization
Published	2019-10-30
URL	https://arxiv.org/abs/1910.13852v1
PDF	https://arxiv.org/pdf/1910.13852v1.pdf
PWC	https://paperswithcode.com/paper/linear-speedup-in-saddle-point-escape-for
Repo
Framework

Self-driving scale car trained by Deep reinforcement learning


Title	Self-driving scale car trained by Deep reinforcement learning
Authors	Qi Zhang, Tao Du, Changzheng Tian
Abstract	The self-driving based on deep reinforcement learning, as the most important application of artificial intelligence, has become a popular topic. Most of the current self-driving methods focus on how to directly learn end-to-end self-driving control strategy from the raw sensory data. Essentially, this control strategy can be considered as a mapping between images and driving behavior, which usually faces a problem of low generalization ability. To improve the generalization ability for the driving behavior, the reinforcement learning method requires extrinsic reward from the real environment, which may damage the car. In order to obtain a good generalization ability in safety, a virtual simulation environment that can be constructed different driving scene is designed by Unity. A theoretical model is established and analyzed in the virtual simulation environment, and it is trained by double Deep Q-network. Then, the trained model is migrated to a scale car in real world. This process is also called a sim2real method. The sim2real training method efficiently handle the these two problems. The simulations and experiments are carried out to evaluate the performance and effectiveness of the proposed algorithm. Finally, it is demonstrated that the scale car in real world obtain the capability for autonomous driving.
Tasks	Autonomous Driving, Q-Learning
Published	2019-09-08
URL	https://arxiv.org/abs/1909.03467v3
PDF	https://arxiv.org/pdf/1909.03467v3.pdf
PWC	https://paperswithcode.com/paper/self-driving-scale-car-trained-by-deep
Repo
Framework

Probabilistic Motion Modeling from Medical Image Sequences: Application to Cardiac Cine-MRI


Title	Probabilistic Motion Modeling from Medical Image Sequences: Application to Cardiac Cine-MRI
Authors	Julian Krebs, Tommaso Mansi, Nicholas Ayache, Hervé Delingette
Abstract	We propose to learn a probabilistic motion model from a sequence of images. Besides spatio-temporal registration, our method offers to predict motion from a limited number of frames, useful for temporal super-resolution. The model is based on a probabilistic latent space and a novel temporal dropout training scheme. This enables simulation and interpolation of realistic motion patterns given only one or any subset of frames of a sequence. The encoded motion also allows to be transported from one subject to another without the need of inter-subject registration. An unsupervised generative deformation model is applied within a temporal convolutional network which leads to a diffeomorphic motion model, encoded as a low-dimensional motion matrix. Applied to cardiac cine-MRI sequences, we show improved registration accuracy and spatio-temporally smoother deformations compared to three state-of-the-art registration algorithms. Besides, we demonstrate the model’s applicability to motion transport by simulating a pathology in a healthy case. Furthermore, we show an improved motion reconstruction from incomplete sequences compared to linear and cubic interpolation.
Tasks	Super-Resolution
Published	2019-07-31
URL	https://arxiv.org/abs/1907.13524v2
PDF	https://arxiv.org/pdf/1907.13524v2.pdf
PWC	https://paperswithcode.com/paper/probabilistic-motion-modeling-from-medical
Repo
Framework

Gaze-in-wild: A dataset for studying eye and head coordination in everyday activities


Title	Gaze-in-wild: A dataset for studying eye and head coordination in everyday activities
Authors	Rakshit Kothari, Zhizhuo Yang, Christopher Kanan, Reynold Bailey, Jeff Pelz, Gabriel Diaz
Abstract	The interaction between the vestibular and ocular system has primarily been studied in controlled environments. Consequently, off-the shelf tools for categorization of gaze events (e.g. fixations, pursuits, saccade) fail when head movements are allowed. Our approach was to collect a novel, naturalistic, and multimodal dataset of eye+head movements when subjects performed everyday tasks while wearing a mobile eye tracker equipped with an inertial measurement unit and a 3D stereo camera. This Gaze-in-the-Wild dataset (GW) includes eye+head rotational velocities (deg/s), infrared eye images and scene imagery (RGB+D). A portion was labelled by coders into gaze motion events with a mutual agreement of 0.72 sample based Cohen’s $\kappa$. This labelled data was used to train and evaluate two machine learning algorithms, Random Forest and a Recurrent Neural Network model, for gaze event classification. Assessment involved the application of established and novel event based performance metrics. Classifiers achieve $\sim$90$%$ human performance in detecting fixations and saccades but fall short (60$%$) on detecting pursuit movements. Moreover, pursuit classification is far worse in the absence of head movement information. A subsequent analysis of feature significance in our best-performing model revealed a reliance upon absolute eye and head velocity, indicating that classification does not require spatial alignment of the head and eye tracking coordinate systems. The GW dataset, trained classifiers and evaluation metrics will be made publicly available with the intention of facilitating growth in the emerging area of head-free gaze event classification.
Tasks	Eye Tracking
Published	2019-05-09
URL	https://arxiv.org/abs/1905.13146v1
PDF	https://arxiv.org/pdf/1905.13146v1.pdf
PWC	https://paperswithcode.com/paper/190513146
Repo
Framework

Discovering Context Effects from Raw Choice Data


Title	Discovering Context Effects from Raw Choice Data
Authors	Arjun Seshadri, Alexander Peysakhovich, Johan Ugander
Abstract	Many applications in preference learning assume that decisions come from the maximization of a stable utility function. Yet a large experimental literature shows that individual choices and judgements can be affected by “irrelevant” aspects of the context in which they are made. An important class of such contexts is the composition of the choice set. In this work, our goal is to discover such choice set effects from raw choice data. We introduce an extension of the Multinomial Logit (MNL) model, called the context dependent random utility model (CDM), which allows for a particular class of choice set effects. We show that the CDM can be thought of as a second-order approximation to a general choice system, can be inferred optimally using maximum likelihood and, importantly, is easily interpretable. We apply the CDM to both real and simulated choice data to perform principled exploratory analyses for the presence of choice set effects.
Tasks
Published	2019-02-08
URL	https://arxiv.org/abs/1902.03266v2
PDF	https://arxiv.org/pdf/1902.03266v2.pdf
PWC	https://paperswithcode.com/paper/discovering-context-effects-from-raw-choice
Repo
Framework