达娜·盎格鲁因（Dana Angluin）的算法有改进

Question

在1987年的开创性论文中，达纳·盎格鲁因（Dana Angluin）提出了一种多项式时间算法，用于从会员查询和理论查询（反例调查到拟议的DFA）学习DFA。

她表明，如果您试图用$ n $ state学习最小的DFA，而您最大的countexample是$ m $，那么您需要制作$ o（mn^2）$会员资格 - 最多最多$ n -1 $理论征服。

学习常规集所需的查询数量是否有显着改善？

---

参考和相关问题

• Dana Angluin（1987）“从查询和反例中学习常规集”，未来和计算75：87-106

• 在会员查询和反例模型中学习的下限

Answer 1

在 他的回答 在cstheory.se上， Lev Reyzin 指示我去 罗伯特·沙皮尔的论文 这改善了第5.4.5节中的$ O（n^2 + n log M）$成员资格查询。反例查询的数量保持不变。 Schapire算法在反例查询之后使用的内容有所不同。

---

改进的草图

在最高级别上，schapire $（s，e，t）$从angluin的算法中$（S，s，e，t）$和每个$ s_1，s_2 in s $如果$ s_1，则具有额外的条件 neq s_2 $然后$ row（s_1） neq row（s_2）$。这保证了$ | s | leq n $，也使 一致性 Angluin算法的属性要满足。为了确保这一点，他必须以不同的方式处理反例的结果。

给定反例$ z $，Angluin只是添加了$ z $及其所有前缀到$ s $。 Schapire可以通过将单个元素$ e $添加到$ e $来做一些更微妙的事情。这个新的$ e $将使$（s，e，t）$不为 关闭 从Angluin的意义上讲，将至少一个新字符串引入$ S $，同时将所有行截然不同。 $ e $的条件是：

$$ 存在s，s' in s，a in sigma quad text {st} quad row（s）= row（s'a）; text {and} ; o（ delta（q_0，se）） neq o（ delta（q_0，s'ae））$$

其中$ o $是输出函数，$ q_0 $是初始状态，而$ delta $ true“ Unknown” DFA的更新规则。另外，$ e $必须作为证人，将$ s $的未来与$ s'a $区分开。

为了找出$ z $的$ e $，我们进行二进制搜索以找出一个子字符串$ r_i $，以便$ z = p_ir_i $和$ 0 leq | p_i | = i <| z | $，使我们的猜想机器的行为基于一个输入字符有所不同。更详细地说，我们让$ s_i $成为与我们猜想机中所达到的状态相对应的字符串，遵循$ p_i $。我们使用二进制搜索（这是$ log m $来自的位置）来找到$ k $，使得$ o（ delta（q_0，s_kr_k）） neq o（ delta（q_0，s_ {k+1） } r_ {k+1}）$。换句话说，$ r_ {k+1} $区分了我们猜想的机器在$ e $上找到等价的两个状态，因此我们将其添加到$ e $中。

Answer 2

我不知道我的答案是否仍然相关。最近，它描述了一种新算法的实施，称为观察包，或者在某些情况下通过Falk Howar歧视树。该算法就像L*，但使用Rivest-Shapire或其他方法（请参阅Steffen和Isberner）进行反例分解；它使用数据结构，一种歧视树（二进制树）来有效地使“筛分”，即插入一个新状态的A型插入（一个是每个字母的符号），直到没有闭合性。该算法存在两个版本：OneGlobally和On OnClace，根据是否添加分解中的后缀是否添加到每个组件中（该算法背后的比率是组件中的所有前缀都等于短前缀，并且表示相同的状态，并表示相同的状态在目前发现的后缀中，在目标中。后来有了新的反例，发现新的后缀会区分同一组件的至少2个前缀。这会导致该组件在两个组件中的拆分）。随着局部性的范围，会员查询较少，但是与大型目标DFA相当的疑问的数量可能会大大增加。相反，OneGlobally的会员资格查询始终低于L*（但大于Oneclyly on Onecly）和类似数量的等价查询。

我知道这也存在另一种算法：TTT算法也比观察包更好，但我对它没有很好的了解。TTT算法应该是最先进的