DeepDFA: Automata Learning through Neural Probabilistic Relaxations

• URL: http://arxiv.org/abs/2408.08622v1
• Date: Fri, 16 Aug 2024 09:30:36 GMT
• Title: DeepDFA: Automata Learning through Neural Probabilistic Relaxations
• Authors: Elena Umili, Roberto Capobianco,
• Abstract summary: We introduce DeepDFA, a novel approach to identifying Deterministic Finite Automata (DFAs) from traces. Inspired by both the probabilistic relaxation of DFAs and Recurrent Neural Networks (RNNs), our model offers interpretability post-training, alongside reduced complexity and enhanced training efficiency.
• Score: 2.3326951882644553
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we introduce DeepDFA, a novel approach to identifying Deterministic Finite Automata (DFAs) from traces, harnessing a differentiable yet discrete model. Inspired by both the probabilistic relaxation of DFAs and Recurrent Neural Networks (RNNs), our model offers interpretability post-training, alongside reduced complexity and enhanced training efficiency compared to traditional RNNs. Moreover, by leveraging gradient-based optimization, our method surpasses combinatorial approaches in both scalability and noise resilience. Validation experiments conducted on target regular languages of varying size and complexity demonstrate that our approach is accurate, fast, and robust to noise in both the input symbols and the output labels of training data, integrating the strengths of both logical grammar induction and deep learning.

Related papers

• Weighted Automata Extraction and Explanation of Recurrent Neural Networks for Natural Language Tasks [15.331024247043999]
  Recurrent Neural Networks (RNNs) have achieved tremendous success in processing sequential data, yet understanding and analyzing their behaviours remains a significant challenge. We propose a novel framework of Weighted Finite Automata (WFA) extraction and explanation to tackle the limitations for natural language tasks.
  arXiv  Detail & Related papers  (2023-06-24T19:16:56Z)
• Stochastic Unrolled Federated Learning [85.6993263983062]
  We introduce UnRolled Federated learning (SURF), a method that expands algorithm unrolling to federated learning. Our proposed method tackles two challenges of this expansion, namely the need to feed whole datasets to the unrolleds and the decentralized nature of federated learning.
  arXiv  Detail & Related papers  (2023-05-24T17:26:22Z)
• Latent Variable Representation for Reinforcement Learning [131.03944557979725]
  It remains unclear theoretically and empirically how latent variable models may facilitate learning, planning, and exploration to improve the sample efficiency of model-based reinforcement learning. We provide a representation view of the latent variable models for state-action value functions, which allows both tractable variational learning algorithm and effective implementation of the optimism/pessimism principle. In particular, we propose a computationally efficient planning algorithm with UCB exploration by incorporating kernel embeddings of latent variable models.
  arXiv  Detail & Related papers  (2022-12-17T00:26:31Z)
• Comparative Analysis of Interval Reachability for Robust Implicit and Feedforward Neural Networks [64.23331120621118]
  We use interval reachability analysis to obtain robustness guarantees for implicit neural networks (INNs) INNs are a class of implicit learning models that use implicit equations as layers. We show that our approach performs at least as well as, and generally better than, applying state-of-the-art interval bound propagation methods to INNs.
  arXiv  Detail & Related papers  (2022-04-01T03:31:27Z)
• Robust Learning via Ensemble Density Propagation in Deep Neural Networks [6.0122901245834015]
  We formulate the problem of density propagation through layers of a deep neural network (DNN) and solve it using an Ensemble Density propagation scheme. Experiments using MNIST and CIFAR-10 datasets show a significant improvement in the robustness of the trained models to random noise and adversarial attacks.
  arXiv  Detail & Related papers  (2021-11-10T21:26:08Z)
• Gone Fishing: Neural Active Learning with Fisher Embeddings [55.08537975896764]
  There is an increasing need for active learning algorithms that are compatible with deep neural networks. This article introduces BAIT, a practical representation of tractable, and high-performing active learning algorithm for neural networks.
  arXiv  Detail & Related papers  (2021-06-17T17:26:31Z)
• Fully differentiable model discovery [0.0]
  We propose an approach by combining neural network based surrogates with Sparse Bayesian Learning. Our work expands PINNs to various types of neural network architectures, and connects neural network-based surrogates to the rich field of Bayesian parameter inference.
  arXiv  Detail & Related papers  (2021-06-09T08:11:23Z)
• Influence Estimation and Maximization via Neural Mean-Field Dynamics [60.91291234832546]
  We propose a novel learning framework using neural mean-field (NMF) dynamics for inference and estimation problems. Our framework can simultaneously learn the structure of the diffusion network and the evolution of node infection probabilities.
  arXiv  Detail & Related papers  (2021-06-03T00:02:05Z)
• Network Diffusions via Neural Mean-Field Dynamics [52.091487866968286]
  We propose a novel learning framework for inference and estimation problems of diffusion on networks. Our framework is derived from the Mori-Zwanzig formalism to obtain an exact evolution of the node infection probabilities. Our approach is versatile and robust to variations of the underlying diffusion network models.
  arXiv  Detail & Related papers  (2020-06-16T18:45:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.