# Unsupervised Automata Learning via Discrete Optimization

arXiv: https://arxiv.org/abs/2303.14111 · HTML: https://mlsanity.com/paper/2303.14111/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 54 references that are in the map.
- First posted on arXiv 24 Mar 2023.

## Builds on (most cited first, 4 of 4)

- [ALFRED: A Benchmark for Interpreting Grounded Instructions for Everyday Tasks](https://mlsanity.com/paper/1912.01734/) (2019)
- [Loghub: A Large Collection of System Log Datasets for AI-driven Log Analytics](https://mlsanity.com/paper/2008.06448/) (2020)
- [Interpretable Sequence Classification via Discrete Optimization](https://mlsanity.com/paper/2010.02819/) (2020)
- [Active Automata Learning with Adaptive Distinguishing Sequences](https://mlsanity.com/paper/1902.01139/) (2019)

## Abstract (arXiv)

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.