pwc-archive/papers-with-abstracts huggingface dataset:
Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory
Authors: Bin Hu, Usman Ahmed Syed
Date: 2019-06-16 00:00:00
Proceeding: NeurIPS 2019 12

In this paper, we provide a unified analysis of temporal difference learning algorithms with linear function approximators by exploiting their connections to Markov jump linear systems (MJLS). We tailor the MJLS theory developed in the control community to characterize the exact behaviors of the first and second order moments of a large family of temporal difference learning algorithms. For both the IID and Markov noise cases, we show that the evolution of some augmented versions of the mean and covariance matrix of the TD estimation error exactly follows the trajectory of a deterministic linear time-invariant (LTI) dynamical system. Applying the well-known LTI system theory, we obtain closed-form expressions for the mean and covariance matrix of the TD estimation error at any time step. We provide a tight matrix spectral radius condition to guarantee the convergence of the covariance matrix of the TD estimation error, and perform a perturbation analysis to characterize the dependence of the TD behaviors on learning rate. For the IID case, we provide an exact formula characterizing how the mean and covariance matrix of the TD estimation error converge to the steady state values. For the Markov case, we use our formulas to explain how the behaviors of TD learning algorithms are affected by learning rate and the underlying Markov chain. For both cases, upper and lower bounds for the mean square TD error are provided. The mean square TD error is shown to converge linearly to an exact limit.
Global Convergence of Least Squares EM for Demixing Two Log-Concave Densities
Authors: Wei Qian, Yuqian Zhang, Yudong Chen
Date: 2019-06-16 00:00:00
Proceeding: NeurIPS 2019 12

This work studies the location estimation problem for a mixture of two rotation invariant log-concave densities. We demonstrate that Least Squares EM, a variant of the EM algorithm, converges to the true location parameter from a randomly initialized point. We establish the explicit convergence rates and sample complexity bounds, revealing their dependence on the signal-to-noise ratio and the tail property of the log-concave distribution. Moreover, we show that this global convergence property is robust under model mis-specification. Our analysis generalizes previous techniques for proving the convergence results for Gaussian mixtures. In particular, we make use of an angle-decreasing property for establishing global convergence of Least Squares EM beyond Gaussian settings, as $\ell_2$ distance contraction no longer holds globally for general log-concave mixtures.
On the Self-Similarity of Natural Stochastic Textures
Authors: Samah Khawaled, Yehoshua Y. Zeevi
Date: 2019-06-16 00:00:00
Tasks: Two-sample testing

Self-similarity is the essence of fractal images and, as such, characterizes natural stochastic textures. This paper is concerned with the property of self-similarity in the statistical sense in the case of fully-textured images that contain both stochastic texture and structural (mostly deterministic) information. We firstly decompose a textured image into two layers corresponding to its texture and structure, and show that the layer representing the stochastic texture is characterized by random phase of uniform distribution, unlike the phase of the structured information which is coherent. The uniform distribution of the the random phase is verified by using a suitable hypothesis testing framework. We proceed by proposing two approaches to assessment of self-similarity. The first is based on patch-wise calculation of the mutual information, while the second measures the mutual information that exists across scales. Quantifying the extent of self-similarity by means of mutual information is of paramount importance in the analysis of natural stochastic textures that are encountered in medical imaging, geology, agriculture and in computer vision algorithms that are designed for application on fully-textures images.
Finding the Needle in the Haystack with Convolutions: on the benefits of architectural bias
Authors: Stéphane d'Ascoli, Levent Sagun, Joan Bruna, Giulio Biroli
Date: 2019-06-16 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Navigate

Despite the phenomenal success of deep neural networks in a broad range of learning tasks, there is a lack of theory to understand the way they work. In particular, Convolutional Neural Networks (CNNs) are known to perform much better than Fully-Connected Networks (FCNs) on spatially structured data: the architectural structure of CNNs benefits from prior knowledge on the features of the data, for instance their translation invariance. The aim of this work is to understand this fact through the lens of dynamics in the loss landscape. We introduce a method that maps a CNN to its equivalent FCN (denoted as eFCN). Such an embedding enables the comparison of CNN and FCN training dynamics directly in the FCN space. We use this method to test a new training protocol, which consists in training a CNN, embedding it to FCN space at a certain ``relax time'', then resuming the training in FCN space. We observe that for all relax times, the deviation from the CNN subspace is small, and the final performance reached by the eFCN is higher than that reachable by a standard FCN of same architecture. More surprisingly, for some intermediate relax times, the eFCN outperforms the CNN it stemmed, by combining the prior information of the CNN and the expressivity of the FCN in a complementary way. The practical interest of our protocol is limited by the very large size of the highly sparse eFCN. However, it offers interesting insights into the persistence of architectural bias under stochastic gradient dynamics. It shows the existence of some rare basins in the FCN loss landscape associated with very good generalization. These can only be accessed thanks to the CNN prior, which helps navigate the landscape during the early stages of optimization.
Defending Against Adversarial Attacks Using Random Forests
Authors: Yifan Ding, Liqiang Wang, huan zhang, Jin-Feng Yi, Deliang Fan, Boqing Gong
Date: 2019-06-16 00:00:00

As deep neural networks (DNNs) have become increasingly important and popular, the robustness of DNNs is the key to the safety of both the Internet and the physical world. Unfortunately, some recent studies show that adversarial examples, which are hard to be distinguished from real examples, can easily fool DNNs and manipulate their predictions. Upon observing that adversarial examples are mostly generated by gradient-based methods, in this paper, we first propose to use a simple yet very effective non-differentiable hybrid model that combines DNNs and random forests, rather than hide gradients from attackers, to defend against the attacks. Our experiments show that our model can successfully and completely defend the white-box attacks, has a lower transferability, and is quite resistant to three representative types of black-box attacks; while at the same time, our model achieves similar classification accuracy as the original DNNs. Finally, we investigate and suggest a criterion to define where to grow random forests in DNNs.
Parametric Resynthesis with neural vocoders
Authors: Soumi Maiti, Michael I Mandel
Date: 2019-06-16 00:00:00
Tasks: Resynthesis

Noise suppression systems generally produce output speech with compromised quality. We propose to utilize the high quality speech generation capability of neural vocoders for noise suppression. We use a neural network to predict clean mel-spectrogram features from noisy speech and then compare two neural vocoders, WaveNet and WaveGlow, for synthesizing clean speech from the predicted mel spectrogram. Both WaveNet and WaveGlow achieve better subjective and objective quality scores than the source separation model Chimera++. Further, WaveNet and WaveGlow also achieve significantly better subjective quality ratings than the oracle Wiener mask. Moreover, we observe that between WaveNet and WaveGlow, WaveNet achieves the best subjective quality scores, although at the cost of much slower waveform generation.
Self-organized inductive reasoning with NeMuS
Authors: Leonardo Barreto, Edjard Mota
Date: 2019-06-16 00:00:00
Tasks: BIG-bench Machine Learning, Inductive Learning

Neural Multi-Space (NeMuS) is a weighted multi-space representation for a portion of first-order logic designed for use with machine learning and neural network methods. It was demonstrated that it can be used to perform reasoning based on regions forming patterns of refutation and also in the process of inductive learning in ILP-like style. Initial experiments were carried out to investigate whether a self-organizing the approach is suitable to generate similar concept regions according to the attributes that form such concepts. We present the results and make an analysis of the suitability of the method in the process of inductive learning with NeMuS.
Theoretical Limitations of Self-Attention in Neural Sequence Models
Authors: Michael Hahn
Date: 2019-06-16 00:00:00
Proceeding: TACL 2020 1
Tasks: Hard Attention

Transformers are emerging as the new workhorse of NLP, showing great success across tasks. Unlike LSTMs, transformers process input sequences entirely through self-attention. Previous work has suggested that the computational capabilities of self-attention to process hierarchical structures are limited. In this work, we mathematically investigate the computational power of self-attention to model formal languages. Across both soft and hard attention, we show strong theoretical limitations of the computational abilities of self-attention, finding that it cannot model periodic finite-state languages, nor hierarchical structure, unless the number of layers or heads increases with input length. These limitations seem surprising given the practical success of self-attention and the prominent role assigned to hierarchical structure in linguistics, suggesting that natural language can be approximated well with models that are too weak for the formal languages typically assumed in theoretical linguistics.
ConTrOn: Continuously Trained Ontology based on Technical Data Sheets and Wikidata
Authors: Kobkaew Opasjumruskit, Diana Peters, Sirko Schindler
Date: 2019-06-16 00:00:00

In engineering projects involving various parts from global suppliers, one common task is to determine which parts are best suited for the project requirements. Information about specific parts' characteristics is published in so called data sheets. However, these data sheets are oftentimes only published in textual form, e.g., as a PDF. Hence, they have to be transformed into a machine-interpretable format. This transformation process still requires a lot of manual intervention and is prone to errors. Automated approaches make use of ontologies to capture the given domain and thus improve automated information extraction from the data sheets. However, ontologies rely solely on experiences and perspectives of their creators at the time of creation and cannot accumulate knowledge over time on their own. This paper presents ConTrOn -- Continuously Trained Ontology -- a system that automatically augments ontologies. ConTrOn tackles terminology problems by combining the knowledge extracted from data sheets with an ontology created by domain experts and external knowledge bases such as WordNet and Wikidata. To demonstrate how the enriched ontology can improve the information extraction process, we selected data sheets from spacecraft development as a use case. The evaluation results show that the amount of information extracted from data sheets based on ontologies is significantly increased after the ontology enrichment.
A concise guide to existing and emerging vehicle routing problem variants
Authors: Thibaut Vidal, Gilbert Laporte, Piotr Matl
Date: 2019-06-16 00:00:00
Tasks: Diversity

Vehicle routing problems have been the focus of extensive research over the past sixty years, driven by their economic importance and their theoretical interest. The diversity of applications has motivated the study of a myriad of problem variants with different attributes. In this article, we provide a concise overview of existing and emerging problem variants. Models are typically refined along three lines: considering more relevant objectives and performance metrics, integrating vehicle routing evaluations with other tactical decisions, and capturing fine-grained yet essential aspects of modern supply chains. We organize the main problem attributes within this structured framework. We discuss recent research directions and pinpoint current shortcomings, recent successes, and emerging challenges.
Multi-scale Embedded CNN for Music Tagging (MsE-CNN)
Authors: Nima Hamidi, Mohsen Vahidzadeh, Stephen Baek
Date: 2019-06-16 00:00:00
Tasks: BIG-bench Machine Learning, General Classification, Music Classification, Music Tagging

Convolutional neural networks (CNN) recently gained notable attraction in a variety of machine learning tasks: including music classification and style tagging. In this work, we propose implementing intermediate connections to the CNN architecture to facilitate the transfer of multi-scale/level knowledge between different layers. Our novel model for music tagging shows significant improvement in comparison to the proposed approaches in the literature, due to its ability to carry low-level timbral features to the last layer.
Persuasion for Good: Towards a Personalized Persuasive Dialogue System for Social Good
Authors: Xuewei Wang, Weiyan Shi, Richard Kim, Yoojung Oh, Sijia Yang, Jingwen Zhang, Zhou Yu
Date: 2019-06-16 00:00:00
Proceeding: ACL 2019 7
Tasks: Persuasion Strategies, Sentence

Developing intelligent persuasive conversational agents to change people's opinions and actions for social good is the frontier in advancing the ethical development of automated dialogue systems. To do so, the first step is to understand the intricate organization of strategic disclosures and appeals employed in human persuasion conversations. We designed an online persuasion task where one participant was asked to persuade the other to donate to a specific charity. We collected a large dataset with 1,017 dialogues and annotated emerging persuasion strategies from a subset. Based on the annotation, we built a baseline classifier with context information and sentence-level features to predict the 10 persuasion strategies used in the corpus. Furthermore, to develop an understanding of personalized persuasion processes, we analyzed the relationships between individuals' demographic and psychological backgrounds including personality, morality, value systems, and their willingness for donation. Then, we analyzed which types of persuasion strategies led to a greater amount of donation depending on the individuals' personal backgrounds. This work lays the ground for developing a personalized persuasive dialogue system.
A fast tunable blurring algorithm for scattered data
Authors: Gregor Robinson, Ian Grooms
Date: 2019-06-16 00:00:00
Tasks: Deblurring, State Estimation

A blurring algorithm with linear time complexity can reduce the small-scale content of data observed at scattered locations in a spatially extended domain of arbitrary dimension. The method works by forming a Gaussian interpolant of the input data, and then convolving the interpolant with a multiresolution Gaussian approximation of the Green's function to a differential operator whose spectrum can be tuned for problem-specific considerations. Like conventional blurring algorithms, which the new algorithm generalizes to data measured at locations other than a uniform grid, applications include deblurring and separation of spatial scales. An example illustrates a possible application toward enabling importance sampling approaches to data assimilation of geophysical observations, which are often scattered over a spatial domain, since blurring observations can make particle filters more effective at state estimation of large scales. Another example, motivated by data analysis of dynamics like ocean eddies that have strong separation of spatial scales, uses the algorithm to decompose scattered oceanographic float measurements into large-scale and small-scale components.
Dispersed Exponential Family Mixture VAEs for Interpretable Text Generation
Authors: Wenxian Shi, Hao Zhou, Ning Miao, Lei LI
Date: 2019-06-16 00:00:00
Tasks: Language Modelling, Text Generation

Deep generative models are commonly used for generating images and text. Interpretability of these models is one important pursuit, other than the generation quality. Variational auto-encoder (VAE) with Gaussian distribution as prior has been successfully applied in text generation, but it is hard to interpret the meaning of the latent variable. To enhance the controllability and interpretability, one can replace the Gaussian prior with a mixture of Gaussian distributions (GM-VAE), whose mixture components could be related to hidden semantic aspects of data. In this paper, we generalize the practice and introduce DEM-VAE, a class of models for text generation using VAEs with a mixture distribution of exponential family. Unfortunately, a standard variational training algorithm fails due to the mode-collapse problem. We theoretically identify the root cause of the problem and propose an effective algorithm to train DEM-VAE. Our method penalizes the training with an extra dispersion term to induce a well-structured latent space. Experimental results show that our approach does obtain a meaningful space, and it outperforms strong baselines in text generation benchmarks. The code is available at https://github.com/wenxianxian/demvae.
Neural Decipherment via Minimum-Cost Flow: from Ugaritic to Linear B
Authors: Jiaming Luo, Yuan Cao, Regina Barzilay
Date: 2019-06-16 00:00:00
Proceeding: ACL 2019 7
Tasks: Decipherment

In this paper we propose a novel neural approach for automatic decipherment of lost languages. To compensate for the lack of strong supervision signal, our model design is informed by patterns in language change documented in historical linguistics. The model utilizes an expressive sequence-to-sequence model to capture character-level correspondences between cognates. To effectively train the model in an unsupervised manner, we innovate the training procedure by formalizing it as a minimum-cost flow problem. When applied to the decipherment of Ugaritic, we achieve a 5.5% absolute improvement over state-of-the-art results. We also report the first automatic results in deciphering Linear B, a syllabic language related to ancient Greek, where our model correctly translates 67.3% of cognates.
MoËT: Mixture of Expert Trees and its Application to Verifiable Reinforcement Learning
Authors: Marko Vasic, Andrija Petrovic, Kaiyuan Wang, Mladen Nikolic, Rishabh Singh, Sarfraz Khurshid
Date: 2019-06-16 00:00:00
Tasks: Game of Go, Imitation Learning, Mixture-of-Experts, OpenAI Gym, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Self-Driving Cars

Rapid advancements in deep learning have led to many recent breakthroughs. While deep learning models achieve superior performance, often statistically better than humans, their adoption into safety-critical settings, such as healthcare or self-driving cars is hindered by their inability to provide safety guarantees or to expose the inner workings of the model in a human understandable form. We present Mo\"ET, a novel model based on Mixture of Experts, consisting of decision tree experts and a generalized linear model gating function. Thanks to such gating function the model is more expressive than the standard decision tree. To support non-differentiable decision trees as experts, we formulate a novel training procedure. In addition, we introduce a hard thresholding version, Mo\"ETH, in which predictions are made solely by a single expert chosen via the gating function. Thanks to that property, Mo\"ETH allows each prediction to be easily decomposed into a set of logical rules in a form which can be easily verified. While Mo\"ET is a general use model, we illustrate its power in the reinforcement learning setting. By training Mo\"ET models using an imitation learning procedure on deep RL agents we outperform the previous state-of-the-art technique based on decision trees while preserving the verifiability of the models. Moreover, we show that Mo\"ET can also be used in real-world supervised problems on which it outperforms other verifiable machine learning models.
Interpretations of Deep Learning by Forests and Haar Wavelets
Authors: Changcun Huang
Date: 2019-06-16 00:00:00
Tasks: Deep Learning

This paper presents a basic property of region dividing of ReLU (rectified linear unit) deep learning when new layers are successively added, by which two new perspectives of interpreting deep learning are given. The first is related to decision trees and forests; we construct a deep learning structure equivalent to a forest in classification abilities, which means that certain kinds of ReLU deep learning can be considered as forests. The second perspective is that Haar wavelet represented functions can be approximated by ReLU deep learning with arbitrary precision; and then a general conclusion of function approximation abilities of ReLU deep learning is given. Finally, generalize some of the conclusions of ReLU deep learning to the case of sigmoid-unit deep learning.
Using Automatically Extracted Minimum Spans to Disentangle Coreference Evaluation from Boundary Detection
Authors: Nafise Sadat Moosavi, Leo Born, Massimo Poesio, Michael Strube
Date: 2019-06-16 00:00:00
Proceeding: ACL 2019 7
Tasks: Boundary Detection, coreference-resolution, Coreference Resolution, Prepositional Phrase Attachment

The common practice in coreference resolution is to identify and evaluate the maximum span of mentions. The use of maximum spans tangles coreference evaluation with the challenges of mention boundary detection like prepositional phrase attachment. To address this problem, minimum spans are manually annotated in smaller corpora. However, this additional annotation is costly and therefore, this solution does not scale to large corpora. In this paper, we propose the MINA algorithm for automatically extracting minimum spans to benefit from minimum span evaluation in all corpora. We show that the extracted minimum spans by MINA are consistent with those that are manually annotated by experts. Our experiments show that using minimum spans is in particular important in cross-dataset coreference evaluation, in which detected mention boundaries are noisier due to domain shift. We will integrate MINA into https://github.com/ns-moosavi/coval for reporting standard coreference scores based on both maximum and automatically detected minimum spans.