Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2303.14111 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918128593666048 |
|---|---|
| author | Lutz, Simon Kaminskyi, Daniil Wittbold, Florian Dierl, Simon Howar, Falk König, Barbara Müller, Emmanuel Neider, Daniel |
| author_facet | Lutz, Simon Kaminskyi, Daniil Wittbold, Florian Dierl, Simon Howar, Falk König, Barbara Müller, Emmanuel Neider, Daniel |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_14111 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Unsupervised Automata Learning via Discrete Optimization Lutz, Simon Kaminskyi, Daniil Wittbold, Florian Dierl, Simon Howar, Falk König, Barbara Müller, Emmanuel Neider, Daniel Machine Learning Artificial Intelligence Formal Languages and Automata Theory F.4.3; I.2.6 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. |
| title | Unsupervised Automata Learning via Discrete Optimization |
| topic | Machine Learning Artificial Intelligence Formal Languages and Automata Theory F.4.3; I.2.6 |
| url | https://arxiv.org/abs/2303.14111 |