DeepDFA: Automata Learning through Neural Probabilistic Relaxations
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.
Code (1)
Similar Papers 제목 키워드 기반
DeepDFA: Injecting Temporal Logic in Deep Learning for Sequential Subsymbolic Applications
Integrating logical knowledge into deep neural network training is still a hard challenge, especially for sequential or temporally extended domains involving subsymbolic observations. To address this problem, we propose …
Dataflow Analysis-Inspired Deep Learning for Efficient Vulnerability Detection
Deep learning-based vulnerability detection has shown great performance and, in some studies, outperformed static analysis tools. However, the highest-performing approaches use token-based transformer models, which are n…
Deep LearningGraph LearningLanguage ModellingLarge Language Model+1Mixed Nondeterministic-Probabilistic Automata: Blending graphical probabilistic models with nondeterminism
Graphical models in probability and statistics are a core concept in the area of probabilistic reasoning and probabilistic programming-graphical models include Bayesian networks and factor graphs. In this paper we develo…
Probabilistic ProgrammingOn the Derivational Entropy of Left-to-Right Probabilistic Finite-State Automata and Hidden Markov Models
Probabilistic finite-state automata are a formalism that is widely used in many problems of automatic speech recognition and natural language processing. Probabilistic finite-state automata are closely related to other f…
Automatic Speech RecognitionAutomatic Speech Recognition (ASR)speech-recognitionSpeech RecognitionThe problem with probabilistic DAG automata for semantic graphs
Semantic representations in the form of directed acyclic graphs (DAGs) have been introduced in recent years, and to model them, we need probabilistic models of DAGs. One model that has attracted some attention is the DAG…