Paper Group ANR 1275
Effective problem solving using SAT solvers. An Autonomous Performance Testing Framework using Self-Adaptive Fuzzy Reinforcement Learning. Conflict as an Inverse of Attention in Sequence Relationship. Restoring Chaos Using Deep Reinforcement Learning. Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation. Generative Learn …
Effective problem solving using SAT solvers
| Title | Effective problem solving using SAT solvers |
| Authors | Curtis Bright, Jürgen Gerhard, Ilias Kotsireas, Vijay Ganesh |
| Abstract | In this article we demonstrate how to solve a variety of problems and puzzles using the built-in SAT solver of the computer algebra system Maple. Once the problems have been encoded into Boolean logic, solutions can be found (or shown to not exist) automatically, without the need to implement any search algorithm. In particular, we describe how to solve the $n$-queens problem, how to generate and solve Sudoku puzzles, how to solve logic puzzles like the Einstein riddle, how to solve the 15-puzzle, how to solve the maximum clique problem, and finding Graeco-Latin squares. |
| Tasks | |
| Published | 2019-06-14 |
| URL | https://arxiv.org/abs/1906.06251v2 |
| https://arxiv.org/pdf/1906.06251v2.pdf | |
| PWC | https://paperswithcode.com/paper/effective-problem-solving-using-sat-solvers |
| Repo | |
| Framework | |
An Autonomous Performance Testing Framework using Self-Adaptive Fuzzy Reinforcement Learning
| Title | An Autonomous Performance Testing Framework using Self-Adaptive Fuzzy Reinforcement Learning |
| Authors | Mahshid Helali Moghadam, Mehrdad Saadatmand, Markus Borg, Markus Bohlin, Björn Lisper |
| Abstract | Test automation can result in reduction in cost and human effort. If the optimal policy, the course of actions taken, for the intended objective in a testing process could be learnt by the testing system (e.g., a smart tester agent), then it could be reused in similar situations, thus leading to higher efficiency, i.e., less computational time. Automating stress testing to find performance breaking points remains a challenge for complex software systems. Common approaches are mainly based on source code or system model analysis or use-case based techniques. However, source code or system models might not be available at testing time. In this paper, we propose a self-adaptive fuzzy reinforcement learning-based performance (stress) testing framework (SaFReL) that enables the tester agent to learn the optimal policy for generating stress test cases leading to performance breaking point without access to performance model of the system under test. SaFReL learns the optimal policy through an initial learning, then reuses it during a transfer learning phase, while keeping the learning running in the long-term. Through multiple experiments on a simulated environment, we demonstrate that our approach generates the stress test cases for different programs efficiently and adaptively without access to performance models. |
| Tasks | Transfer Learning |
| Published | 2019-08-19 |
| URL | https://arxiv.org/abs/1908.06900v1 |
| https://arxiv.org/pdf/1908.06900v1.pdf | |
| PWC | https://paperswithcode.com/paper/an-autonomous-performance-testing-framework |
| Repo | |
| Framework | |
Conflict as an Inverse of Attention in Sequence Relationship
| Title | Conflict as an Inverse of Attention in Sequence Relationship |
| Authors | Rajarshee Mitra |
| Abstract | Attention is a very efficient way to model the relationship between two sequences by comparing how similar two intermediate representations are. Initially demonstrated in NMT, it is a standard in all NLU tasks today when efficient interaction between sequences is considered. However, we show that attention, by virtue of its composition, works best only when it is given that there is a match somewhere between two sequences. It does not very well adapt to cases when there is no similarity between two sequences or if the relationship is contrastive. We propose an Conflict model which is very similar to how attention works but which emphasizes mostly on how well two sequences repel each other and finally empirically show how this method in conjunction with attention can boost the overall performance. |
| Tasks | |
| Published | 2019-06-20 |
| URL | https://arxiv.org/abs/1906.08593v2 |
| https://arxiv.org/pdf/1906.08593v2.pdf | |
| PWC | https://paperswithcode.com/paper/conflict-as-an-inverse-of-attention-in |
| Repo | |
| Framework | |
Restoring Chaos Using Deep Reinforcement Learning
| Title | Restoring Chaos Using Deep Reinforcement Learning |
| Authors | Sumit Vashishtha, Siddhartha Verma |
| Abstract | A catastrophic bifurcation in non-linear dynamical systems, called crisis, often leads to their convergence to an undesirable non-chaotic state after some initial chaotic transients. Preventing such behavior has proved to be quite challenging. We demonstrate that deep Reinforcement Learning (RL) is able to restore chaos in a transiently-chaotic regime of the Lorenz system of equations. Without requiring any a priori knowledge of the underlying dynamics of the governing equations, the RL agent discovers an effective perturbation strategy for sustaining the chaotic trajectory. We analyze the agent’s autonomous control-decisions, and identify and implement a simple control-law that successfully restores chaos in the Lorenz system. Our results demonstrate the utility of using deep RL for controlling the occurrence of catastrophes and extreme-events in non-linear dynamical systems. |
| Tasks | |
| Published | 2019-11-27 |
| URL | https://arxiv.org/abs/1912.00947v1 |
| https://arxiv.org/pdf/1912.00947v1.pdf | |
| PWC | https://paperswithcode.com/paper/restoring-chaos-using-deep-reinforcement |
| Repo | |
| Framework | |
Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation
| Title | Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation |
| Authors | Moses Charikar, Kirankumar Shiragur, Aaron Sidford |
| Abstract | Estimating symmetric properties of a distribution, e.g. support size, coverage, entropy, distance to uniformity, are among the most fundamental problems in algorithmic statistics. While each of these properties have been studied extensively and separate optimal estimators are known for each, in striking recent work, Acharya et al. 2016 showed that there is a single estimator that is competitive for all symmetric properties. This work proved that computing the distribution that approximately maximizes \emph{profile likelihood (PML)}, i.e. the probability of observed frequency of frequencies, and returning the value of the property on this distribution is sample competitive with respect to a broad class of estimators of symmetric properties. Further, they showed that even computing an approximation of the PML suffices to achieve such a universal plug-in estimator. Unfortunately, prior to this work there was no known polynomial time algorithm to compute an approximate PML and it was open to obtain a polynomial time universal plug-in estimator through the use of approximate PML. In this paper we provide a algorithm (in number of samples) that, given $n$ samples from a distribution, computes an approximate PML distribution up to a multiplicative error of $\exp(n^{2/3} \mathrm{poly} \log(n))$ in time nearly linear in $n$. Generalizing work of Acharya et al. 2016 on the utility of approximate PML we show that our algorithm provides a nearly linear time universal plug-in estimator for all symmetric functions up to accuracy $\epsilon = \Omega(n^{-0.166})$. Further, we show how to extend our work to provide efficient polynomial-time algorithms for computing a $d$-dimensional generalization of PML (for constant $d$) that allows for universal plug-in estimation of symmetric relationships between distributions. |
| Tasks | |
| Published | 2019-05-21 |
| URL | https://arxiv.org/abs/1905.08448v1 |
| https://arxiv.org/pdf/1905.08448v1.pdf | |
| PWC | https://paperswithcode.com/paper/efficient-profile-maximum-likelihood-for |
| Repo | |
| Framework | |
Generative Learning of Counterfactual for Synthetic Control Applications in Econometrics
| Title | Generative Learning of Counterfactual for Synthetic Control Applications in Econometrics |
| Authors | Chirag Modi, Uros Seljak |
| Abstract | A common statistical problem in econometrics is to estimate the impact of a treatment on a treated unit given a control sample with untreated outcomes. Here we develop a generative learning approach to this problem, learning the probability distribution of the data, which can be used for downstream tasks such as post-treatment counterfactual prediction and hypothesis testing. We use control samples to transform the data to a Gaussian and homoschedastic form and then perform Gaussian process analysis in Fourier space, evaluating the optimal Gaussian kernel via non-parametric power spectrum estimation. We combine this Gaussian prior with the data likelihood given by the pre-treatment data of the single unit, to obtain the synthetic prediction of the unit post-treatment, which minimizes the error variance of synthetic prediction. Given the generative model the minimum variance counterfactual is unique, and comes with an associated error covariance matrix. We extend this basic formalism to include correlations of primary variable with other covariates of interest. Given the probabilistic description of generative model we can compare synthetic data prediction with real data to address the question of whether the treatment had a statistically significant impact. For this purpose we develop a hypothesis testing approach and evaluate the Bayes factor. We apply the method to the well studied example of California (CA) tobacco sales tax of 1988. We also perform a placebo analysis using control states to validate our methodology. Our hypothesis testing method suggests 5.8:1 odds in favor of CA tobacco sales tax having an impact on the tobacco sales, a value that is at least three times higher than any of the 38 control states. |
| Tasks | |
| Published | 2019-10-16 |
| URL | https://arxiv.org/abs/1910.07178v1 |
| https://arxiv.org/pdf/1910.07178v1.pdf | |
| PWC | https://paperswithcode.com/paper/generative-learning-of-counterfactual-for |
| Repo | |
| Framework | |
Enhancing the Locality and Breaking the Memory Bottleneck of Transformer on Time Series Forecasting
| Title | Enhancing the Locality and Breaking the Memory Bottleneck of Transformer on Time Series Forecasting |
| Authors | Shiyang Li, Xiaoyong Jin, Yao Xuan, Xiyou Zhou, Wenhu Chen, Yu-Xiang Wang, Xifeng Yan |
| Abstract | Time series forecasting is an important problem across many domains, including predictions of solar plant energy output, electricity consumption, and traffic jam situation. In this paper, we propose to tackle such forecasting problem with Transformer [1]. Although impressed by its performance in our preliminary study, we found its two major weaknesses: (1) locality-agnostics: the point-wise dot-product self-attention in canonical Transformer architecture is insensitive to local context, which can make the model prone to anomalies in time series; (2) memory bottleneck: space complexity of canonical Transformer grows quadratically with sequence length $L$, making directly modeling long time series infeasible. In order to solve these two issues, we first propose convolutional self-attention by producing queries and keys with causal convolution so that local context can be better incorporated into attention mechanism. Then, we propose LogSparse Transformer with only $O(L(\log L)^{2})$ memory cost, improving forecasting accuracy for time series with fine granularity and strong long-term dependencies under constrained memory budget. Our experiments on both synthetic data and real-world datasets show that it compares favorably to the state-of-the-art. |
| Tasks | Time Series, Time Series Forecasting |
| Published | 2019-06-29 |
| URL | https://arxiv.org/abs/1907.00235v3 |
| https://arxiv.org/pdf/1907.00235v3.pdf | |
| PWC | https://paperswithcode.com/paper/enhancing-the-locality-and-breaking-the |
| Repo | |
| Framework | |
Natural Language Adversarial Attacks and Defenses in Word Level
| Title | Natural Language Adversarial Attacks and Defenses in Word Level |
| Authors | Xiaosen Wang, Hao Jin, Kun He |
| Abstract | Up until recent two years, inspired by the big amount of research about adversarial example in the field of computer vision, there has been a growing interest in adversarial attacks for Natural Language Processing (NLP). What followed was a very few works of adversarial defense for NLP. However, there exists no defense method against the successful synonyms substitution based attacks that aim to satisfy all the lexical, grammatical, semantic constraints and thus are hard to perceived by humans. To fill this gap, we postulate the generalization of the model leads to the existence of adversarial examples, and propose an adversarial defense method called Synonyms Encoding Method (SEM), which inserts an encoder before the input layer of the model and then trains the model to eliminate adversarial perturbations. Extensive experiments demonstrate that SEM can efficiently defend current best synonym substitution based adversarial attacks with almost no decay on the accuracy for benign examples. Besides, to better evaluate SEM, we also propose a strong attack method called Improved Genetic Algorithm (IGA) that adopts the genetic metaheuristic against synonyms substitution based attacks. Compared with existing genetic based adversarial attack, the proposed IGA can achieve higher attack success rate at the same time maintain the transferability of adversarial examples. |
| Tasks | Adversarial Attack, Adversarial Defense |
| Published | 2019-09-15 |
| URL | https://arxiv.org/abs/1909.06723v2 |
| https://arxiv.org/pdf/1909.06723v2.pdf | |
| PWC | https://paperswithcode.com/paper/natural-language-adversarial-attacks-and |
| Repo | |
| Framework | |
Learning GENERAL Principles from Hundreds of Software Projects
| Title | Learning GENERAL Principles from Hundreds of Software Projects |
| Authors | Suvodeep Majumder, Rahul Krishna, Tim Menzies |
| Abstract | When one exemplar project, which we call the “bellwether”, offers the best advice then it can be used to offer advice for many other projects. Such bellwethers can be used to make quality predictions about new projects, even before there is much experience with those new projects. But existing methods for bellwether transfer are very slow. When applied to the 697 projects studied here, they took 60 days of CPU to find and certify the bellwethers. Hence, we propose a GENERAL: a novel bellwether detection algorithm based on hierarchical clustering. At each level within a tree of clusters, one bellwether is computed from sibling projects, then promoted up the tree. This hierarchical method is a scalable approach to learning effective models from very large data sets. For example, for nearly 700 projects, the defect prediction models generated from GENERAL’s bellwether were just as good as those found via standard methods. |
| Tasks | |
| Published | 2019-11-06 |
| URL | https://arxiv.org/abs/1911.04250v1 |
| https://arxiv.org/pdf/1911.04250v1.pdf | |
| PWC | https://paperswithcode.com/paper/learning-general-principles-from-hundreds-of |
| Repo | |
| Framework | |
Coarse-To-Fine Visual Localization Using Semantic Compact Map
| Title | Coarse-To-Fine Visual Localization Using Semantic Compact Map |
| Authors | Ziwei Liao, Jieqi Shi, Xianyu Qi, Xiaoyu Zhang, Wei Wang, Yijia He, Ran Wei, Xiao Liu |
| Abstract | Robust visual localization for urban vehicles remains challenging and unsolved. The limitation of computation efficiency and memory size has made it harder for large-scale applications. Since semantic information serves as a stable and compact representation of the environment, we propose a coarse-to-fine localization system based on a semantic compact map. Pole-like objects are stored in the compact map, then are extracted from semantically segmented images as observations. Localization is performed by a particle filter, followed by a pose alignment module decoupling translation and rotation to achieve better accuracy. We evaluate our system both on synthetic and realistic datasets and compare it with two baselines, a state-of-art semantic feature-based system and a traditional SIFT feature-based system. Experiments demonstrate that even with a significantly small map, such as a 10 KB map for a 3.7 km long trajectory, our system provides a comparable accuracy with the baselines. |
| Tasks | Visual Localization |
| Published | 2019-10-11 |
| URL | https://arxiv.org/abs/1910.04936v2 |
| https://arxiv.org/pdf/1910.04936v2.pdf | |
| PWC | https://paperswithcode.com/paper/coarse-to-fine-visual-localization-using |
| Repo | |
| Framework | |
Neuro-SERKET: Development of Integrative Cognitive System through the Composition of Deep Probabilistic Generative Models
| Title | Neuro-SERKET: Development of Integrative Cognitive System through the Composition of Deep Probabilistic Generative Models |
| Authors | Tadahiro Taniguchi, Tomoaki Nakamura, Masahiro Suzuki, Ryo Kuniyasu, Kaede Hayashi, Akira Taniguchi, Takato Horii, Takayuki Nagai |
| Abstract | This paper describes a framework for the development of an integrative cognitive system based on probabilistic generative models (PGMs) called Neuro-SERKET. Neuro-SERKET is an extension of SERKET, which can compose elemental PGMs developed in a distributed manner and provide a scheme that allows the composed PGMs to learn throughout the system in an unsupervised way. In addition to the head-to-tail connection supported by SERKET, Neuro-SERKET supports tail-to-tail and head-to-head connections, as well as neural network-based modules, i.e., deep generative models. As an example of a Neuro-SERKET application, an integrative model was developed by composing a variational autoencoder (VAE), a Gaussian mixture model (GMM), latent Dirichlet allocation (LDA), and automatic speech recognition (ASR). The model is called VAE+GMM+LDA+ASR. The performance of VAE+GMM+LDA+ASR and the validity of Neuro-SERKET were demonstrated through a multimodal categorization task using image data and a speech signal of numerical digits. |
| Tasks | Speech Recognition |
| Published | 2019-10-20 |
| URL | https://arxiv.org/abs/1910.08918v2 |
| https://arxiv.org/pdf/1910.08918v2.pdf | |
| PWC | https://paperswithcode.com/paper/neuro-serket-development-of-integrative |
| Repo | |
| Framework | |
Application of Gaussian Process Regression to Koopman Mode Decomposition for Noisy Dynamic Data
| Title | Application of Gaussian Process Regression to Koopman Mode Decomposition for Noisy Dynamic Data |
| Authors | Akitoshi Masuda, Yoshihiko Susuki, Manel Martínez-Ramón, Andrea Mammoli, Atsushi Ishigame |
| Abstract | Koopman Mode Decomposition (KMD) is a technique of nonlinear time-series analysis that originates from point spectrum of the Koopman operator defined for an underlying nonlinear dynamical system. We present a numerical algorithm of KMD based on Gaussian process regression that is capable of handling noisy finite-time data. The algorithm is applied to short-term swing dynamics of a multi-machine power grid in order to estimate oscillatory modes embedded in the dynamics, and thereby the effectiveness of the algorithm is evaluated. |
| Tasks | Time Series, Time Series Analysis |
| Published | 2019-11-04 |
| URL | https://arxiv.org/abs/1911.01143v2 |
| https://arxiv.org/pdf/1911.01143v2.pdf | |
| PWC | https://paperswithcode.com/paper/application-of-gaussian-process-regression-to |
| Repo | |
| Framework | |
ADA-Tucker: Compressing Deep Neural Networks via Adaptive Dimension Adjustment Tucker Decomposition
| Title | ADA-Tucker: Compressing Deep Neural Networks via Adaptive Dimension Adjustment Tucker Decomposition |
| Authors | Zhisheng Zhong, Fangyin Wei, Zhouchen Lin, Chao Zhang |
| Abstract | Despite the recent success of deep learning models in numerous applications, their widespread use on mobile devices is seriously impeded by storage and computational requirements. In this paper, we propose a novel network compression method called Adaptive Dimension Adjustment Tucker decomposition (ADA-Tucker). With learnable core tensors and transformation matrices, ADA-Tucker performs Tucker decomposition of arbitrary-order tensors. Furthermore, we propose that weight tensors in networks with proper order and balanced dimension are easier to be compressed. Therefore, the high flexibility in decomposition choice distinguishes ADA-Tucker from all previous low-rank models. To compress more, we further extend the model to Shared Core ADA-Tucker (SCADA-Tucker) by defining a shared core tensor for all layers. Our methods require no overhead of recording indices of non-zero elements. Without loss of accuracy, our methods reduce the storage of LeNet-5 and LeNet-300 by ratios of 691 times and 233 times, respectively, significantly outperforming state of the art. The effectiveness of our methods is also evaluated on other three benchmarks (CIFAR-10, SVHN, ILSVRC12) and modern newly deep networks (ResNet, Wide-ResNet). |
| Tasks | |
| Published | 2019-06-18 |
| URL | https://arxiv.org/abs/1906.07671v1 |
| https://arxiv.org/pdf/1906.07671v1.pdf | |
| PWC | https://paperswithcode.com/paper/ada-tucker-compressing-deep-neural-networks |
| Repo | |
| Framework | |
Sample Complexity of Estimating the Policy Gradient for Nearly Deterministic Dynamical Systems
| Title | Sample Complexity of Estimating the Policy Gradient for Nearly Deterministic Dynamical Systems |
| Authors | Osbert Bastani |
| Abstract | Reinforcement learning is a promising approach to learning robot controllers. It has recently been shown that algorithms based on finite-difference estimates of the policy gradient are competitive with algorithms based on the policy gradient theorem. We propose a theoretical framework for understanding this phenomenon. Our key insight is that many dynamical systems (especially those of interest in robot control tasks) are \emph{nearly deterministic}—i.e., they can be modeled as a deterministic system with a small stochastic perturbation. We show that for such systems, finite-difference estimates of the policy gradient can have substantially lower variance than estimates based on the policy gradient theorem. We interpret these results in the context of counterfactual estimation. Finally, we empirically evaluate our insights in an experiment on the inverted pendulum. |
| Tasks | |
| Published | 2019-01-24 |
| URL | http://arxiv.org/abs/1901.08562v2 |
| http://arxiv.org/pdf/1901.08562v2.pdf | |
| PWC | https://paperswithcode.com/paper/sample-complexity-of-estimating-the-policy |
| Repo | |
| Framework | |
Facilitating Bayesian Continual Learning by Natural Gradients and Stein Gradients
| Title | Facilitating Bayesian Continual Learning by Natural Gradients and Stein Gradients |
| Authors | Yu Chen, Tom Diethe, Neil Lawrence |
| Abstract | Continual learning aims to enable machine learning models to learn a general solution space for past and future tasks in a sequential manner. Conventional models tend to forget the knowledge of previous tasks while learning a new task, a phenomenon known as catastrophic forgetting. When using Bayesian models in continual learning, knowledge from previous tasks can be retained in two ways: 1). posterior distributions over the parameters, containing the knowledge gained from inference in previous tasks, which then serve as the priors for the following task; 2). coresets, containing knowledge of data distributions of previous tasks. Here, we show that Bayesian continual learning can be facilitated in terms of these two means through the use of natural gradients and Stein gradients respectively. |
| Tasks | Continual Learning |
| Published | 2019-04-24 |
| URL | http://arxiv.org/abs/1904.10644v1 |
| http://arxiv.org/pdf/1904.10644v1.pdf | |
| PWC | https://paperswithcode.com/paper/facilitating-bayesian-continual-learning-by |
| Repo | |
| Framework | |
