Unsupervised Automata Learning via Discrete Optimization
This work addresses a gap in automata learning for unsupervised settings, which is incremental as it extends existing supervised methods to unlabeled data.
The paper tackles the problem of learning deterministic finite automata (DFAs) from unlabeled data, which is computationally hard, and proposes a framework with three constraint optimization algorithms and regularization schemes, demonstrating practical feasibility for unsupervised anomaly detection.
Automata learning is a successful tool for many application domains such as robotics and automatic verification. Typically, automata learning techniques operate in a supervised learning setting (active or passive) where they learn a finite state machine in contexts where additional information, such as labeled system executions, is available. However, other settings, such as learning from unlabeled data - an important aspect in machine learning - remain unexplored. To overcome this limitation, we propose a framework for learning a deterministic finite automaton (DFA) from a given multi-set of unlabeled words. We show that this problem is computationally hard and develop three learning algorithms based on constraint optimization. Moreover, we introduce novel regularization schemes for our optimization problems that improve the overall interpretability of our DFAs. Using a prototype implementation, we demonstrate practical feasibility in the context of unsupervised anomaly detection.