没有合适的资源?快使用搜索试试~ 我知道了~
∈ CRCR∈R理论计算机科学电子笔记248(2009)47-56www.elsevier.com/locate/entcs基于JFLAP1的确定性有限自动机学习算法Mikel Alecha和Montserrat HermoDpto. deLe n guajesySistemasInforma'ti cos.我知道了。 普雷斯大学.Paseo Manuel de Lardizbal,1 20018-SanSe bastia'n,Spain.摘要JFLAP包是一个免费的交互式可视化和形式语言教学工具。 JFLAP基于这样一个原则,即概念的图片比文本表示更容易理解。在这个软件包的帮助下,我们实现了Dana Angluin的算法,该算法能够学习确定性有限自动机。JFLAP的使用允许用户可视化学习过程中的每一步。 该算法所使用的协议被称为精确学习的成员资格和等价查询。这个协议也是由Dana Angluin介绍的,他证明了她的学习算法在高效的运行时间内发现了与查询一致的唯一最小自动机保留字:精确学习模型,确定性有限自动机,JFLAP1引言DanaAngluin [2]考虑了通过允许学习算法对未知目标概念c进行特定类型的查询来学习概念类的表示类的问题。例如,如果是字母表上的确定有限自动机DFA的类,则概念类是字母表上的正则语言的集合,并且目标概念是特定正则语言我知道。Dana Angluin考虑的查询类型如下。– 成员资格:成员资格查询的输入是一个元素w,如果w∈c,则其答案为YES,如果w/∈c,则答案为NO。在我们的例子中,只要w∈L,答案就为YES。– 等价性:输入是一个假设h如果ch,则输出为YESc, 其中ch是由h表示的概念,否则为NO。如果答案是否定1这项工作得到了西班牙项目TIN 2007 -66523的部分支持1571-0661 © 2009 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2009.07.05848M. Alecha,M.Hermo/Electronic Notes in Theoretical Computer Science 248(2009)47R∈∈ −∈返回在ch和c的对称差中的元素x 如果x cch然后 x称为正反例。否则,它就是一个反例。 在我们的例子中,假设是一个特定的确定性有限自动机M∈DFA。如果L(M)/L,则反例必须是一串。反例的特定选择被假定为任意的,也就是说,一个成功的学习算法必须工作,无论提供什么反例。此外,该算法必须输出假设等价的表示到目标概念c,并且必须在时间多项式w.r.t. c的最小表示的大小,以及接收到的最大反例的长度。当这种情况发生时,可以说这是通过成员资格和等价查询的。在我们的示例中,学习算法必须输出特定的MDFA,使得L(M)=L,并且它必须在时间多项式w.r.t.中工作。识别L的最小自动机的大小和作为反例给出的最大字符串的长度w。在[1]中,证明了DFA类可以通过成员和等价查询有效地精确学习。此外,该算法找到了唯一的最小自动机等价于目标语言。在本文中,我们提出了一个实现的学习算法的DFA以下的思想[3,5]。新的是使用JFLAP工具[4]来可视化算法的步骤。我们的算法要求用户提供必须根据它们是否是目标语言来回答的字符串(显然,算法的前提条件是目标语言必须是正则的)。此外,当算法要求用户提供特定的自动机时,它通过JFLAP工具提供了一个可视化的图片。这是非常有用的,因为如果给定的自动机不等价于目标语言,它可以更容易地找到反例。该应用程序在http://www.sc.ehu.es/jiwhehum2/DFA/dfa.jar/上公开提供,读者只要有JAVA虚拟机就可以执行它。本文的其余部分组织如下。在下一节中,我们将解释该算法如何能够使用特定示例学习DFA。第3节介绍了另外两个例子。第4节描述了一些实现细节。最后,第5节结束。2学习算法通过一个例子由于Dana Angluin的算法及其不同版本在本领域中是众所周知的,并且在本文的参考文献中也有引用,因此我们不打算对所用算法的结构进行深入分析,它的运作方式。与其这样,我们将简要介绍其操作方法,然后我们将继续展示其执行的基础知识在我们的应用程序中通过一个例子和一系列标题。让我们从算法的一般概述开始。如前M. Alecha,M.Hermo/Electronic Notes in Theoretical Computer Science 248(2009)4749--整个过程涉及从外部来源(在我们的情况下,用户)请求特定信息,并对其进行处理以扩展概念的知识。 更具体地说,该算法首先收集以下基本信息: 目标(特定的常规语言)。一旦它完成了这一点,它就进入了一个由两个阶段组成的循环:首先,在用户的指导下,用户必须回答一组成员资格查询,它构建了一个假设自动机;一旦它完成了这一点,它向用户显示假设并询问该假设是否准确地识别目标。如果是,过程结束;否则,它会询问用户关于为什么它的假设与目标不同的信息,处理它并再次开始循环。现在,我们将使用一个示例来查看更详细的视图,该示例是当目标是语言时构建的自动化模型L={w∈{a,b,c}<$:|W|am o d 2=0|W|bm o d 2=1}。这意味着L包含字母表a,b,c上的字符串,其中a的个数为第一步是定义应用程序的字母表,这是它在开始执行学习算法之前需要的。一旦输入了工作字母表,算法就开始询问是否接受空字符串。换句话说,这个字符串是否在目标语言中。对成员资格查询的响应是通过一个由Yes/No按钮组成的简单界面输入的。应用程序存储给出的答案供以后使用,这样用户就不会被多次询问相同的成员资格查询。此外,所有给定的答案也可由用户访问,如有必要,可进行检查。在我们的例子中,第一个问题的答案必须是否定的。然后,假设自动机M1(见上图)被构建并显示,以便用户可以将其与L进行比较。 在这一点上,算法需要知道是否L(M1)=L。 如果 算法并不需要一个反例来证明这一说法,50M. Alecha,M.Hermo/Electronic Notes in Theoretical Computer Science 248(2009)47/用户必须通过用于等价查询的接口输入该等价查询。在我们的例子中,M1的一个有效反例可以是字符串aabc。接下来,该算法需要将从这个例子中收集的信息处理到它的主要数据结构中:分类树。为此目的,将以与之前相同的方式向用户进行另一系列成员资格查询,还存储结果以供以后进一步重用。一旦算法认为它已经在分类树中收集了足够的信息,它就准备好了 再次开始构建假设自动机M2的过程。 M2比M1多一个状态.在我们的例子中,在构造M2之前,算法要求的字符串及其相应的答案是:一BC阿拉伯联合银行阿拉伯银行理事会美国农业信贷理事会没有是的没有没有没有是的当L(M2)= L时,用户必须提供另一个反例. 例如,字符串AB。有了这些信息,算法继续询问所有这些成员资格查询:CB阿拉伯联合酋长国AABCBBAAAABABB ACACB是的没有是的没有是的没有没有没有接下来,该算法产生M3.如果用户决定给出字符串baa作为反例,则新的成员资格查询集如下所示BABab阿拉伯联合酋长国通讯社ABAACABabb巴巴BAC巴克布巴卡没有没有是的是的没有没有没有没有没有 是的现在,假设M4验证了L(M4)=L,并且如果用户确认它,该过程可以完成。正如我们之前所说的,该算法找到了与目标语言等价的唯一最小自动机为了完成本节,值得注意的是,学习算法的主循环执行的次数正好是大小(M4)。也就是M4中的状态数。 这是因为算法总是从考虑一个单态自动机,并在每个循环期间将状态计数增加1。此外,主循环的每次执行都需要在一个反例的帮助下更新分类树。 如果这个反例的长度是m,那么这个过程最多需要m次操作。因此,我们有size(M4)主循环执行,每个循环都需要O(size(M4)+n)操作,其中n是最长反例的长度M. Alecha,M.Hermo/Electronic Notes in Theoretical Computer Science 248(2009)4751--3另外两个例子可用应用2保持用户通过执行提供的所有答案。因此,正如我们之前所说的,用户不会被多次询问相同的成员身份查询。此外,该算法总是建立一个新的假设自动机,这是一致的,与以前的反例。例如,设L是字母表0, 1上的语言,其字符串包含子串11,但不包含子串00。正式L={w∈{0,1}<$:11<$w<$00/<$w}2http://www.sc.ehu.es/jiwhehum2/DFA/dfa.jar52M. Alecha,M.Hermo/Electronic Notes in Theoretical Computer Science 248(2009)47算法开始询问空字符串是否在L中。在这种情况下,答案是否定的,算法建立的假设是M1。M1的一个有效的反例是字符串01101.如果这是用户提供的反例,则算法开始询问一系列成员资格查询。0101101001101101011110100101没有没有是的是的没有是的是的没有没有接下来,算法构建M2.如果用户决定给出字符串011001作为反例,则新的成员资格查询序列为0110011000110100010110是的没有没有是的一旦算法显示假设M3,如果用户给出字符串00110作为反例,则算法询问的成员资格查询如下0000100110101101001100000010001100111010011没有没有没有是的没有没有没有没有没有没有此时,算法给出了识别L的最小自动机M4的假设.M. Alecha,M.Hermo/Electronic Notes in Theoretical Computer Science 248(2009)4753≥关于用户提供的所有答案都在存储期间存储的事实,该过程中,应该注意的是,用户有可能在任何时候显示所有这些信息。例如,在这个例子中,上图显示了当用户要求对字符串进行分类时算法第三个例子结束了这一节。目标语言是3的倍数的自然数的集合。 记住要找出一个数是否可除我们必须把这个数中的所有数字加起来,并检查总和是否可除了3.例如:12123的数字之和是1+ 2 + 1 + 2 + 3= 9,因为9可以被3整除,所以12123也是。目标语言可以定义如下L={n∈{0,1,2,3,4,5,6,7,8,9}n:nmod3=0}根据这个定义,字符串000360代表自然的360,属于L。 我们考虑0(因此任何形式为0 i的字符串,其中i第一章 在目标语言中,以及空字符串。应用程序将M1显示为假设,并且一旦字符串14作为反例给出,并且在进行一系列成员资格查询之后,它显示识别L的M2。在M1和M2之间,成员资格查询的顺序如下0123456789140141是的没有没有是的没有没有是的没有没有是的没有 是的54M. Alecha,M.Hermo/Electronic Notes in Theoretical Computer Science 248(2009)47142143144145146147148149244454没有没有是的没有没有是的没有没有是的没有是的7484140414241434145414641484149410104没有是的是的没有是的没有是的 没有是的 没有没有1111412131341516164171741819194没有是的是的没有没有是的没有没有没有是的是的没有没有下图显示了当用户询问此信息时字符串的当前分类4执行该算法已在Java语言中实现的一个主要原因:能够利用必要的JFLAP工具源代码模块。其次是机器兼容性的原因,但这个工具的目的之一是方便用户在此基础上,实现分为两个部分:一方面是主要的算法程序,基本数据结构和用户交互界面;另一方面是假设自动机的图形表示界面,它将前一部分与JFLAP模块连接起来,允许管理自动机数据结构和在屏幕上描绘图形表示的模块M. Alecha,M.Hermo/Electronic Notes in Theoretical Computer Science 248(2009)4755数据结构相当简单:被查询或作为反例给出的字母表上的字符串通过向量管理,分类树通过二叉树管理所有这些都是在各自的Java类中构建的,以及它们自己的构造函数和方法,除了一些自动机数据结构,它仍然是JFLAP类。负责处理图形表示的类是一个更复杂的类,因为它必须同时处理运行算法的请求和与不同JFLAP模块的通信。一旦JFLAP模块被正确链接,这种通信的大部分(例如重新塑造所显示的自动机的表示的事件其他操作,例如自动机的组装和拆卸,需要显式处理,并使用对自动机数据结构的各种方法的直接调用。此外,该应用程序可以处理许多可选功能的添加,是- yond算法的执行和自动机的图形显示。 最早实现的一个是能够记住以前回答的成员资格查询的答案,这减少了用户方面的工作。另一个重要的问题是允许用户访问分类通过一个新的界面,允许他们在必要时查看这些值。其他功能包括随时重置应用程序的选项,以及将屏幕上构建的自动机保存到JFLAP工具识别的文件中的能力。最后一个功能在用户希望进一步使用通过我们的应用程序学习的自动机结构的情况下特别有用。它可以保存一个自动机,通过JFLAP加载它,然后用各种自动机相关的工具编辑它。默认情况下,应用程序被设置为在可能的情况下自行回答等价查询。基于学习和存储到等价查询点的信息,它会自动检查构建的假设自动机,以查看是否有任何记忆的单词可以作为反例。这样,如果任何单词确实充当反例,则查询永远不会显示给用户,用户将仅在应用程序确认其需要来自用户的输入以继续时才需要回答等价查询。但是,用户仍然可以停用此功能。这样学习过程变得不那么有效,但它允许用户更接近实际的学习算法[5]:学习迭代变得更加清晰地彼此分离。它还允许用户使用自己的不同反例输入进行实验,而不是由程序选择。可以在执行过程中通过选项菜单随时打开和关闭此功能。最新实现的功能之一也是在学习过程中撤销用户操作的系统。此功能特别有用,因为它使用户无需从头开始重新启动学习过程,以防他们意外地错误回答查询或输入不需要的反例。这是相当必要的56M. Alecha,M.Hermo/Electronic Notes in Theoretical Computer Science 248(2009)47对于想要使用大型复杂自动机的用户,其学习过程涉及大量查询和相当长的单词。然而,由于算法的内部结构和应用程序围绕它的实现,撤销功能只有在给出进程的第一个反例之后才对用户可用。一旦它被激活,也不可能撤消该点之前的操作。其根源在于算法使用它接收到的信息来调整其数据结构的方式,遵循与其余学习过程由此产生的界面允许用户接收来自算法的查询,输入答案和反例,观察自动机的图形表示,并改变其不同状态的屏幕上的位置,以获得更好的可见性和理解。它还允许用户遵循学习过程以说教的方式一步一步地。5结论JFLAP集成了可视化和交互式工具,使用户能够通过理论概念获得实践经验在学习算法的情况下,该包使用户与学习者的交互更容易。JFLAP具有比较有限自动机的能力;将非确定性有限自动机和正则表达式转换为最小确定性有限自动机;确定特定字符串是否被有限自动机识别。这意味着,即使是包也允许我们直接与JFLAP本身交互JFLAP最初是一系列工具,学生们在SusanRodger的指导下工作(http://www.jflap.org/)。我们计划把学习算法的实现发给她,为JFLAP增加一个新的功能。引用[1] D.王文,从查询和反例中学习正则集,信息与计算,第75卷,1987年,第87[2] D.王志文,机器学习,第二卷,1988年,第319-342页[3] J.L. Balc'azar,J. 达兹河 Gavald'a和O. Watana be,Le arning有限Automatafrom的租赁:统一的观点。《算法、语言和复杂性的进展》(Advances in Algorithms,Languages,and Complexity)Z. Du和K.-I. Ko(eds.),Kluwer Academic Publishers,1997,73[4] S.H.罗杰和T.W.芬利,JFLAP。一个交互式的形式语言和自动机包,琼斯和巴特利特出版社,2006年。http://www.jflap.org/。[5] 王文,计算学习理论导论,北京大学出版社,1997年。
下载后可阅读完整内容,剩余1页未读,立即下载
![.pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- BSC绩效考核指标汇总 (2).docx
- BSC资料.pdf
- BSC绩效考核指标汇总 (3).pdf
- C5000W常见问题解决方案.docx
- BSC概念 (2).pdf
- ESP8266智能家居.docx
- ESP8266智能家居.pdf
- BSC概念 HR猫猫.docx
- C5000W常见问题解决方案.pdf
- BSC模板:关键绩效指标示例(财务、客户、内部运营、学习成长四个方面).docx
- BSC概念.docx
- BSC模板:关键绩效指标示例(财务、客户、内部运营、学习成长四个方面).pdf
- BSC概念.pdf
- 各种智能算法的总结汇总.docx
- BSC概念 HR猫猫.pdf
- bsc概念hr猫猫.pdf
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)