lstar自动机学习算法的python实现。
lstar的Python项目详细描述
l*
判别树l*算法dfa学习算法的实现 在“^1”中提供。
目录
安装
如果您只需要使用lstar，您可以运行：
$ pip install lstar
对于开发人员，请注意此项目使用 poetrypython包/依赖项 管理工具。请熟悉它，然后 运行：
$ poetry install
用法
使用这个库的主要入口点是learn_dfa
功能。
fromlstarimportlearn_dfa
此函数需要参数：
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] -> boolfind_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])
下面是通过{0, 1}学习以下语言的示例：
The number of 1's in the word is a multiple of 4.
标签查询
我们首先定义label查询函数。
注意lstar的这个实现假定
函数要么是廉价的（O(1)-ish）调用，要么是被记住的。
fromfunctoolsimportlru_cache@lru_cache(maxsize=None)# Memoize member queries defis_mult_4(word):"""Want to learn 4 state counter"""return(sum(word)%4)==0
等价查询
接下来，您需要定义一个给定候选DFA的函数。
返回此DFA错误标签或None错误标签的计数器示例。
注意，使用的DFA类型来自dfa包
（link）。
lstar提供两个函数来编写反例oracle
更容易的。
validate_ce：以oracle为反例并重试 如果返回的“反例”实际上不是反例。 在使用启发式求解器或询问人类时很有用。fromlstarimportvalidate_ce@validate_ce(is_mult_4,retry=True)defask_human(dfa):...
iterative_deeping_ce：这个函数执行一个迭代 深化候选dfa的遍历并查看它是否匹配 所有测试单词上的标签。fromlstarimportiterative_deeping_cefind_ce=iterative_deeping_ce(is_mult_4,depth=10)
一起
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))assertnotdfa.label(())assertnotdfa.label((1,))assertnotdfa.label((1,1,))assertdfa.label((1,1,1))assertdfa.label((1,1,0,1))
学习摩尔机器和DFA贴标机
默认情况下，learn_dfa学习为确定性有限受体；
但是，通过指定outputs参数并调整
label函数，可以学习确定性有限标号
（与摩尔机器同构）。
例如，可以将之前的4状态计数器修改为输出 当前计数，而不是这个词是否等于 4的倍数。
defsum_mod_4(state):returnsum(state)%4dfl=learn_dfa(inputs={0,1},label=sum_mod_4,find_counter_example=ask_human,outputs={0,1,2,3},)# Returns a Deterministic Finite Labeler.assertdfl.label(())==0assertdfl.label((1,))==1assertdfl.label((1,1,))==2assertdfl.label((1,1,1))==3assertdfl.label((1,1,0,1))==3assertdfl.label((1,1,1,1))==0
确定性贴标机可以解释为摩尔机器
使用transduce方法而不是label。
assertdfl.transduce(())==()assertdfl.transduce((1,))==(0,)assertdfl.transduce((1,1,))==(0,1)assertdfl.transduce((1,1,1))==(0,1,2)assertdfl.transduce((1,1,0,1))==(0,1,2,2)assertdfl.transduce((1,1,1,1,1))==(0,1,2,3,0)
测试
这个项目使用pytest。只需运行
$ poetry run pytest
在存储库的根目录中。
类似的库
基于python的
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/：学习图书馆 通过谱方法的加权自动机。
https://pypi.org/project/pylstar/：另一个基于l*的dfa 学习图书馆。
基于Java的
- https://learnlib.de/：最先进的自动机学习 工具箱。支持DFA的被动和主动学习算法， 米利机器，和明显的推倒自动机。
- https://github.com/lorisdanto/symbolicautomata：的库 符号自动机和符号可视下推自动机。
脚注
[^1]：卡恩斯、迈克尔J、乌梅什·维库马尔·瓦齐拉尼和乌梅什·瓦齐拉尼。计算学习理论概论。麻省理工学院出版社，1994年。
欢迎加入QQ群-->： 979659372
