Python implementation of lstar automata learning algorithm.
Project description
L*
Implementation of the discriminant tree L* algorithm DFA learning algorithm provided in [^1].
Table of Contents
Installation
If you just need to use lstar
, you can just run:
$ pip install lstar
For developers, note that this project uses the poetry python package/dependency management tool. Please familarize yourself with it and then run:
$ poetry install
Usage
The main entry point for using this library is the learn_dfa
function.
from lstar import learn_dfa
This function requires the arguments:
dfa = learn_dfa( inputs= .. , # Inputs over which the target concept is over. # Note: Sequence of Hashables. label=.., # Function answering whether a given word is in the target # language. # # Tuple[Alphabet] -> bool find_counter_example=.., # Function which takes a hypothesis DFA # and either returns None or a counter example, # i.e., an element misclassified by hypothesis # DFA. # # DFA -> Union[Tuple[Alphabet], None] )
Below is an example of learning following language over {0, 1}
:
The number of 1's in the word is a multiple of 4.
Label Queries
We start by defining the label query function.
Note that this implementation of lstar
assumes that this
function is either cheap (O(1)
-ish) to call or is memoized.
from functools import lru_cache @lru_cache(maxsize=None) # Memoize member queries def is_mult_4(word): """Want to learn 4 state counter""" return (sum(word) % 4) == 0
Equivalence Queries
Next you need to define a function which given a candidate DFA
returns either a counter example that this DFA
mislabels or None
.
Note that the DFA
type used comes from the dfa
package
(link).
lstar
provides two functions to make writing counterexample oracles
easier.
-
validate_ce
: Takes a counterexample oracle and retries if returned "counterexample" is not actually a counterexample. Useful if using heuristic solver or asking a human.from lstar import validate_ce @validate_ce(is_mult_4, retry=True) def ask_human(dfa): ...
-
iterative_deeping_ce
: This function performs an iterative deepening traversal of the candidate dfa and see's if it matches the labeler on all tested words.from lstar import iterative_deeping_ce find_ce = iterative_deeping_ce(is_mult_4, depth=10)
All together
dfa = learn_dfa( inputs={0, 1}, # Possible inputs. label=is_mult_4, # Does this sequence belong in the language. find_counter_example=iterative_deeping_ce(is_mult_4, depth=10) ) assert not dfa.label(()) assert not dfa.label((1,)) assert not dfa.label((1, 1, )) assert dfa.label((1, 1, 1)) assert dfa.label((1, 1, 0, 1))
Learning Moore Machines and DFA-labelers
By default, learn_dfa
learns as Deterministic Finite Acceptor;
however, by specifying the outputs
parameter and adjusting the
label
function, one can learn a Deterministic Finite Labeler
(which is isomorphic to a Moore Machine).
For example, the 4 state counter from before can be modified to output the current count rather than whether or not the word sums to a multiple of 4.
def sum_mod_4(state): return sum(state) % 4 dfl = learn_dfa( inputs={0, 1}, label=sum_mod_4, find_counter_example=ask_human, outputs={0, 1, 2, 3}, ) # Returns a Deterministic Finite Labeler. assert dfl.label(()) == 0 assert dfl.label((1,)) == 1 assert dfl.label((1, 1, )) == 2 assert dfl.label((1, 1, 1)) == 3 assert dfl.label((1, 1, 0, 1)) == 3 assert dfl.label((1, 1, 1, 1)) == 0
The deterministic labeler can be interpreted as a moore machine by
using the transduce
method rather than label
.
assert dfl.transduce(()) == () assert dfl.transduce((1,)) == (0,) assert dfl.transduce((1, 1, )) == (0, 1) assert dfl.transduce((1, 1, 1)) == (0, 1, 2) assert dfl.transduce((1, 1, 0, 1)) == (0, 1, 2, 2) assert dfl.transduce((1, 1, 1, 1, 1)) == (0, 1, 2, 3, 0)
Testing
This project uses pytest. Simply run
$ poetry run pytest
in the root of the repository.
Similar Libraries
Python Based
1. https://github.com/steynvl/inferrer : DFA learning
library supporting active and passive dfa learning. Active
learning is based on L* with an observation table. Also
supports learning NFAs.
-
https://gitlab.lis-lab.fr/dev/scikit-splearn/ : Library for learning weighted automata via the spectral method.
-
https://pypi.org/project/pylstar/ : Another L* based DFA learning library.
Java Based
- https://learnlib.de/ : State of the art automata learning toolbox. Supports passive and active learning algorithms for DFAs, Mealy Machines, and Visibly Push Down Automata.
- https://github.com/lorisdanto/symbolicautomata : Library for symbolic automata and symbolic visibly pushdown automata.
Footnotes
[^1]: Kearns, Michael J., Umesh Virkumar Vazirani, and Umesh Vazirani. An introduction to computational learning theory. MIT press, 1994.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Filename, size | File type | Python version | Upload date | Hashes |
---|---|---|---|---|
Filename, size lstar-0.2.9-py3-none-any.whl (8.2 kB) | File type Wheel | Python version py3 | Upload date | Hashes View |
Filename, size lstar-0.2.9.tar.gz (8.3 kB) | File type Source | Python version None | Upload date | Hashes View |