TTT算法( 二 ) _序列模式

反例是假设验证的关键
案例：
图3 运行实例:(a)目标DFA a和最终假设H2，(b)最终判别树T2，?最终假设的判别器
输入{a,b}
图3 a中的状态转移由前缀闭包Sp维护，Sp={ε, a, aa, aaa} 。a中的状态和b中的叶子节点相对应。b中对于每一对不同的状态，可以通过查看对应叶的最低共同祖先的标签来获得一个分隔符。内部节点的标签充当分隔符。当它们形成后缀封闭集时，它们可以紧凑地存储在一个trie中。这三个节点中的每个节点都表示一个单词，这个单词可以通过沿着路径找到根来构造。因此，词根本身对应的是空ε 。
1）假设提出
状态是通过一个前缀闭合的集合来确定的，对应于 tree的叶子节点，图4ab
数学公式: $ q_0 $状态由数学公式: $ \ $确定
过渡目标是通过筛选来确定的:给定状态q，由前缀u∈Sp识别，a的下一个状态是通过筛选ua到T来确定的。
最终状态对应判别树的右子树
（2）假设完善
模型完善的关键是反例
反例输入到状态机和假设中结果不同就会导致状态分解。
将ε·a和ε·b输入，导致数学公式: $ q_0 $ 。因此，所有形成自反边。对于图4 a中的状态机，一个可能的反例是w =。这个反例包含了很多多余的信息:b符号只在图4a中运行自循环，因此对新状态的发现没有贡献。部分(但不是全部)冗余信息将由第一个反例分析步骤消除，该步骤生成分解。因此，图4c里增加一个可以接收a的新状态数学公式: $ q_1 $
（3）假设稳定
作为前一步的结果，可能会发生构建的假设与存在于判别树中的信息相矛盾。对于反例的处理流程，首先对其进行分解，然后在判别树中分解相应的叶子，从而在假设中引入一个新的状态。
继续寻找反例，
（4）判别器确认
简化，如从图4e到图3b
寻找反例，有很多冗余
三个树状数据结构。
tree：定义唯一访问序列的生成树，嵌入到假设的过渡图中
tree：区分状态
trie：鉴别树，存储后缀闭式判别器集。每个节点都表示一个单词，这个单词可以通过沿着路径找到根来构造。root对应的是空ε 。
所有数据结构所需的组合空间与假设的大小Θ(kn)大致相同
效率
k是字母Σ的大小，目标DFA A有n个状态，等价查询返回的最长反例长度为m 。
-查询复杂度，即算法提出的所有成员查询的数量。最坏情况O(n)
-符号复杂度，即所有这些成员关系查询中包含的符号总数。最坏情况O(kn^2+n logm)
-空间复杂度，即算法内部数据结构所占用的空间量。O(kn)
四、总结
当考虑所有示例的成员查询总数时，TTT优于其他学习算法；当考虑符号的数量时，和的算法实际上在三分之一的系统中优于TTT（即使它需要更高数量的成员查询）。
然而，所讨论的系统是最小的一个，在所有其他系统上，和的算法表现很差。平均而言，与排名第二的观察包算法（ Pack ）相比，TTT在符号执行方面降低一到两个数量级，并且在调用系统上的操作序列方面降低50%-75% 。
资料
模型学习L*算法学习笔记 - 知乎 ()
-ttt
模型学习