（计算机应用技术专业论文）主题网络蜘蛛的研究与实现.pdf

摘要 摘要 伴随着因特网技术的快速发展，因特网上的信息资源以惊人的速度不断增 长。在对这些海量的信息进行检索的过程中，传统的w e b 搜索引擎越来越无法 满足人们的需要。在这种情况下，各类主题搜索引擎应运而生，成为研究的热点。 而作为主题搜索引擎重要组成部分，网络蜘蛛的搜索算法问题的研究具有极其重 要的意义。 本文从机器学习的理论角度出发，围绕如何提高网络蜘蛛的资源采集效率问 题，采用了机器学习中的增强学习( r e i n f o r c e m e n tl e a r n i n g ) 方法，对主题搜索引 擎网络蜘蛛的搜索算法进行了深入的研究。 本文首先介绍了增强学习的基本概念和网络蜘蛛搜索策略的研究进展，在分 析和比较现有专业搜索引擎网络蜘蛛搜索策略的特点和优缺点的基础上，归纳了 提高搜索效率的几个关键因素。 文中针对提高网络蜘蛛的学习效率问题展开研究，提出了一种基于经验偏向 信息学习机制的增强学习模型。主要思想是，通过学习环境状态中的经验偏向信 息，动态调整增强学习代理体的搜索策略，以减小搜索空间，提高学习效率。在 此基础上，本文提出了一种基于经验偏向信息学习机制的主题网络蜘蛛学习算 法，实验表明，该算法可以明显提高主题网络蜘蛛的学习效率。 针对传统的主题网络蜘蛛存在链接价值评价标准单一的问题，本文提出了一 种基于增强学习的启发式主题网络蜘蛛模型，新模型将立即回报价值和未来回报 价值结合，用于计算链接的综合回报价值。为解决对立即回报价值和未来回报价 值信任度的权衡问题，本文引入了价值置信函数的概念，提出了对于未来回报置 信度递减的启发式搜索算法，该算法的主要思想是将两类评价标准的优势相结 合，以提高整体的搜索效率。针对于实际环境的搜索测试表明，新算法在性能上 优于传统的主题网络蜘蛛搜索算法。 最后，将提出的算法和技术相结合，实现了一个基于增强学习的对计算机相 关论文进行搜索的主题搜索引擎网络蜘蛛的系统原型。 关键词主题网络蜘蛛；搜索引擎；增强学习 a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ei n t e m e t ，q u a n t i t yo ft h ei n f o r m a t i o ni s i n c r e a s i n gi na l li n c r e d i b l ew a y 1 1 1 et r a d i t i o n a lw e bs e a r c he n g i n e sa r eb e c o m i n g m o r ea n dm o r ei n c a p a b l et oh a n d l et h ev a r i a b l en e e d so fp e o p l et oi n d e xt h e i n f o r m a t i o n u n d e rt h i ss i t u a t i o nt h et o p i c s p e c i f i cs e a r c he n g i n e sc a l l l eu p r e s e a r c ho nf i n d i n ge f f i c i e n ts e a r c h i n gs t r a t e g i e sp l a y sa ne s s e n t i a lr o l ei nt h e a p p l i c a t i o na n dt h ep r o g r e s so ft h et o p i c s p e c i f i cs e a r c he n g i n e s i nt h ep e r s p e c t i v eo ft h ea p p l i c a t i o no ft h er e i n f o r c e m e n tl e a r n i n go nw e bs p i d e r s ， t h i sp a p e rm a i n l yf o c u s e so nt h ew o r ko ff i n d i n ge f f i c i e n ts e a r c h i n gs t r a t e g i e s 1 1 1 ec o n c e p to fr e i n f o r c e m e n tl e a r n i n ga n dt h er e c e n tr e s e a r c h e so ns e a r c h i n g s t r a t e g i e s o fw 曲s p i d e r sa r ef i r s ti n t r o d u c e d b a s e do nt h ea n a l y s e so ft h e c h a r a c t e r i s t i co fe a c hs p i d e ra n di t sa d v a n t a g ea n dd i s a d v a n t a g e ，t h ep a p e rs u n l su p t h ek e y st oi m p r o v i n gt h ee f f i c i e n c yo f w 曲s p i d e r s w i mt h ev i e wo f r e d u c i n gt h et i m ec o n s u m p t i o na n dc o m p l e x i t yo fs t a t es p a c e ， t h ep a p e ra i m sa ti m p r o v i n gt h es t u d y i n ge f f i c i e n c yo ft h ew e bs p i d e rb a s e do n r e i n f o r c e m e n tl e a r n i n g an e wr e i n f o r c e m e n tl e a r n i n ga l g o r i t h mb a s e do ne x p e r i e n c e s b i a s i n gi n f o r m a t i o nl e a r n i n gi sp r o p o s e d t h em a i ni d e ao f t h i sa l g o r i t h mi st ot a k e a d v a n t a g eo fs o m eu s e f u ls t a t ef e a t u r e st oe x p l o r em o r ee f f e c t i v e l y a sar e s u l t ，t h e e f f i c i e n c yo fs t u d yi si m p r o v e d t h er e s u l t ss h o wt h a tt h en e wa l g o r i t h mh a sb e t t e r p e r f o r m a n c e 砀ea p p l i c a t i o no ft h en e wa l g o r i t h mo n 黜s p i d e ri sd i s c u s s e da n dan e w s p i d e rl e a r n i n ga l g o r i t h mb a s e do ne x p e r i e n c e sb i a s i n gi n f o r m a t i o nl e a r n i n gi s p r o p o s e d w ev a l i d a t eo u rn e wa l g o r i t h mb ye x p e r i m e n to nw e b s i t el e a r n i n g 1 1 1 e r e s u l t ss h o wt h a tt h en e w a l g o r i t h mh a sb e t t e rp e r f o r m a n c e t oi m p r o v et h ea c c u r a c yo fe v a l u a t i o no ft h ev a l u eo fh y p e r l i n k s ，t h ep a p e r c o m b i n e st w oe v a l u a t i o nm e t h o d so ft h ev a l u eo ft h eh y p e r l i n k s ，n a m e l yt h em e t h o d b a s e do nt h ee v a l u a t i o no fi m m e d i a t er e w a r dv a l u ea n dt h em e t h o db a s e do nt h e e v a l u a t i o no ff u t u r er e w a r dv a l u e b a s e do nt h i s ，an o v e lw e bs p i d e rm o d e li s p r o p o s e d an e wf u n c t i o nn a m e dv a l u eb e l i e ff u n c t i o ni sc o n t r i b u t e dt os o l v et h e p r o b l e mo fb e l i e fa s s i g n m e n to ft h ei m m e d i a t er e w a r dv a l u ea n dt h ef u t u r er e w a r d v a l u e t h e nah e u r i s t i cs e a r c h i n ga l g o r i t h mb a s e do nd e g r a d i n gt h eb e l i e fo ff u t u r e r e w a r dv a l u ei sp r o p o s e d ，1 1 1 em a i ni d e ao ft h ea l g o r i t h mi st oe n h a n c ee x p l o r a t i o nb y a s s i g n i n gl a r g e rb e l i e fv a l u eo ff u t u r er e w a r da tt h ee a r l i e rs t a g eo fs e a r c h i n gp r o c e s s a n dg r a d u a l l yt oa t t a c hm o r ei m p o r t a n c eo ne x p l o i t a t i o nb yd e g r a d i n gt h eb e l i e fv a l u e o ff u t u r er e w a r da tt h el a t e rs t a g eo fs e a r c h i n gp r o c e s s t h er e s u l t so fs e a r c h i n g i i i 北京1 = 业大学工学硕f 二学位论文 e x p e r i m e n to nr e a lw e b s i t es h o wt h a tt h en e wa l g o r i t h mh a sb e t t e rp e r f o r m a n c et h a n t h et r a d i t i o n a la l g o r i t h m s k e y w o r d sf o c u s e dc r a w l e r ；s e a r c he n g i n e ；r e i n f o r c e m e n tl e a r n i n g i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：塑盟导师签名：日期： 第1 章绪论 1 1 研究背景 第1 章绪论 近年来，互联网迅速发展，网络用户迅速增多，截至2 0 0 8 年6 月底，中国 网民数量达到2 5 3 亿人，2 0 0 7 年底美国网民数为2 1 8 亿人。人们的生活越来 越离不开互联网，为人们提供方便快捷的互联网信息服务的w w w ( w o r l dw i d ew e b ) 技术因为其直观、简单、表现形式丰富等特点得到了空前得发展，据调查，目前 中国网站数量已达1 9 1 9 万个，年增长率达到4 6 3 。而且继续保持快速增长的 势头。这带给了人们前所未有的丰富的信息资源。然而，随着w e b 信息量的急速 增长，人们在享受其提供丰富信息的同时，却发现要想很快很便捷的找到自己所 需要的信息实在是太困难了，就像是大海捞针一样。 为了解决这个问题，搜索引擎应运而生。搜索引擎的出现，让人们感觉像是 在大海中找到了一颗救命稻草，用户寻找自己需要的特定信息，有了更加便捷的 途径，不需要在网络中漫无边际的寻找了。搜索引擎的这一特性使得它迅速成为 人们找寻信息资源的一把利器。用户量迅速增加。 根据中国互联网络中, i , , 2 0 0 8 年7 月发布的中国互联网发展状况统计报告 n 3 ，搜索引擎的用户规模是1 亿7 千万，占互联网用户总数的6 9 2 ，在包括网络 音乐，网络新闻，即时通信，网络视频等十大网络应用中排在第五位。搜索引擎 的用户在2 0 0 8 年上半年增长了2 3 0 4 万人，半年增长率达到1 5 5 。在美国，搜索 引擎是第二大网络应用，使用率达到了9 1 。 但是，互联网的信息量呈爆炸趋势增长，海量数据的增加带来的是传统综合 搜索引擎( 又称为水平搜索引擎) ，如百度和g o o g l e 的搜索品质的下降。搜索引擎 在搜集网络信息方面远远赶不上网络信息的增长速度，庞大的网络信息资源使得 搜索变得越来越难以控制。目前，尽管搜索引擎技术的发展日益成熟，但是要准 确、快速地查找到所需要的信息却越来越困难。一是查询的结果集是海量的，经 常是几十万笔的资料，在这些庞大的信息群中，有用的信息只是其中一小部分， 可谓“冰山一角”，而且，这些搜索结果中存在着大量的重复信息和垃圾信息， 用户很难在短时间内准确地筛选出需要的内容，出现所谓的“认知过载。二是 目前的搜索引擎都是要求用户严格按照所规定的格式输入查询词，但种种限制使 用户不知道如何确切地表达自己的信息需求。这些用户需求和市场服务之间的巨 大反差所产生的问题使人们开始呼唤更有针对性的搜索引擎的出现。 主题搜索引擎的产生正是有效地解决了综合搜索引擎搜索质量的问题。它为 用户提供的不再是成千上万的相关网页信息，而是范围很小，且极具针对性的具 北京工业大学- t 学硕二 学位论文 体信息。那么，什么是主题搜索引擎。主题搜索引擎或称垂直搜索引擎( v e r t i c a l s e a r c he n g i n e ) 的定义： ( 1 ) 是指应用于搜索某一学科领域或某一类信息( 如图像、影像) 的专业搜索引 擎，又称为专题搜索引擎、专门搜索引擎，是搜索引擎的细分和延伸。 ( 2 ) 是专为查询某一学科或主题的信息而产生的查询工具，是相对综合搜索引擎 的信息量大、查询不准确、深度不够等提出来的新的搜索引擎服务模式。 ( 3 ) 是以构筑某一专题或学科领域的i n t e r n e t 网络信息资源库为目标，智能地在 互联网上搜集符合这一专题或领域需要的信息资源，能够为包括学科信息门户、 专业信息机构、特定行业领域、公司信息中心、行业专家等等在内的信息用户， 提供整套的网络信息资源开发方案的信息查询与服务的网站。 主题搜索引擎和综合搜索引擎所采用的基本技术非常相似，主要区别是主题 搜索引擎利用的搜索器只搜索特定的主题信息，并按照预先已定义好的专题有选 择地收集相关的网页。这样一来大大降低了收集信息的难度，提高了信息的质量。 由于所收集的学科领域小，信息量相对较少，因此可采用“专家分类标引”的方法 对搜集到的信息进行组织整理，进一步提高信息的质量，建立起一个高质量的、专 业信息收集全、能实时更新的索引数据库。同时，由于主题搜索引擎只涉及一个 或几个领域，词汇和用语“一词( 一语) 多意”的可能性降低，而且可以利用专业 词表进行规范和控制，因此大大提高了查全率和查准率。 1 2 国内外研究现状 专业搜索引擎中，主题网络蜘蛛( 或称爬虫、代理体) 的任务是获取w e b 页面 和决定链接的访问顺序，它通常从一个“种子集 ( 如用户查询、种子链接或种 子页面) 出发，以迭代的方式访问页面和提取链接。搜索过程中，未访问的链接 被暂存在一个称为“优先权列表 ( f r o n t i e r ) 的队列中，主题网络蜘蛛根据搜索 优先权列表中链接的“重要程度”决定下一个要访问的链接。如何评价和预测链 接的“重要程度”( 或称价值) 是决定主题网络蜘蛛搜索的关键。针对这一问题， 近年来学者们提出了许多评价标准和模型。 由于w e b 检索类似于传统信息检索中的文本检索，有些学者考虑是否可以利 用文本相似度的计算方法评价页面文本与主题集之间相似程度，然后再根据相似 度的高低决定页面中的链接的访问顺序。d eb r a 乜1 等将这一思想引入网络蜘蛛的 搜索策略，提出的f i s h s e a r c h 算法。它将用户输入的查询关键词或短语作为主 题，将包含查询串的页面看作与主题相关，且仅搜索主题相关页面。这种相似度 的评价方法只能确定页面与主题是否相关，不能评价相关程度的高低，因此具有 局限性。 第1 章绪论 h e r s o v i c i 口1 对f i s h - s e a r c h 算法进行了改进，采用基于连续值的相似度函 数计算链接价值，这样不但可以计算出哪些页面与主题相关，还可以得出相关性 的大小。 类似地，c h o “1 提出了b e s t f i r s t 算法，利用向量空间模型计算页面与主题的 相似度。 考虑至u w e b 页面不同于传统的文本，它是一种半结构化的文档，包含许多结 构信息；w e b 页面不是单独存在的，页面中的链接指示了页面之间的相互关系， s e r g e yb r i n 和l a w r e n c ep a g e 璐1 尝试利用这些结构特征来评价页面和链接的重要 性，以此决定搜索顺序，提出p a g e r a n k 方法。 r e n n i e 和m c c a l l u m 阻1 将巩固学习( r e i n f o r c e m e n tl e a r n i n g ) 引入网络蜘蛛 的学习过程。巩固学习的优势在于能够预测状态的远期回报价值( 或称未来回报 价值) 。由于在巩固学习模型中，未来回报价值是用q 价值表示的，因而这种方法 的核心就是学习如何计算链接的q 价值。 考虑至u w e b 上主题相关页面往往具有某种层次关系，且这些层次关系之间存 在某种相似性等特点，d i l i g e n t i h l 提出了基于“语境图”( c o n t e x tg r a p h s ) 的 搜索策略，它通过构建典型页面的w e b “语境图”来估计离目标页面的距离，距 离较近的页面较早得到访问。 在国外，己经有相应的系统，下面介绍一些典型的系纠即： ( 1 ) e i s e v i e r 的s c ir u s 系统s c i m s 科学搜索引擎是一种专为搜索高度相关 的科学信息而设计的搜索引擎，获得2 0 0 1 年搜索引擎观察授予的“最佳专业 搜索引擎奖。s c i m s 是目前互联网上最全面、综合性最强的科技文献门户网站 之一。它只面向包含有科学内容的网站，如大学和作者个人主页以及e l s e v i e r 自 己的数据库。 ( 2 ) n e c 研究院的c lt e s e e r c i t e s e c r 是因特网上使用最广泛的针对计算机 领域的科学论文检索系统。c i t e s e e r 的核心是a c i ( a u t o m a t i c a l l yc i t a t i o ni n d e x ) ， 它可以自动地对网上的电子文件( p o s t s c r i p t v - r - 和p d f 等格式) 进行索引并分类。 ( 3 ) b e r k ele y 的f o c u s e dp r o j e c t 该系统通过两个程序来指导爬行器：一个 是分类器c l a s s i f i e r ，用来计算下载文档与预订主题的相关度。另一个程序是净化 器d i s t i l l e r ，用来确定那些指向很多相关资源的页面( 在h i t s 算法中，称之为中心 网页) 。 ( 4 ) 美国国家科学数字图书馆的c o l l e c t i o nb u i l d i n gp r o g r a m ( c b p ) 这个项 目旨在为科学、数学、工程和技术创建大规模的在线数字图书馆，试图研究在某 一主题上资源自动建设的可能性。c b p 具有自己的特点：第一，因为c b p 是面向 教育、面向教学，主题精确度( p r e c i s i o n ) 比覆盖度( r e c a l l ) 更为重要；第二， c b p 不存储资源原文，只是提供u r l 。第三，c b p 只需要用户最少量的输入，如 关键词，系统就可以全自动的将有关该主题的最相关的有限数量u r l ，返回给用 北京t 业大学t 学硕士学位论文 户。 在国内，研究主题搜索引擎的团队也越来越多。现在开始研究该领域的主要 是一些大学的研究机构和一些搜索引擎公司。比如，北京化工大学就推出了关于 化工方面的专业搜索引擎，其他方面如医药、林业等也有相应的产品。百度等也 相应的推出了图片搜索、m p 3 搜索。这些都可以看作是主题式搜索引擎的应用。 1 3 本文的工作 从前面的分析可以发现主题搜索引擎受到越来越多的研究人员的关注，并且 越来越多的相关研究成果被发表，成熟的商业运行模式也取得了成功。对主题搜 索引擎研究的根本目的是为了能够自动地获取利用自由分布在整个互联网上的 关于某一主题的丰富信息。 虽然整个w e b 资源几乎包含了关于某一主题的全部信息，如数码产品类的主 题网页，包括产品型号、价格、销售商、网友点评等，但要想以手工的方式对其 进行抓取整理加以利用，在实际操作中是一件非常困难的事情。而对主题资源的 有效搜索、整合正是为了以尽可能自动的方式来完成对w e b 数据库中信息的有效 利用。正是基于这种认识，本文在学习传统搜索引擎技术的基础上，对主题搜索 引擎系统的关键技术进行了深入研究，并结合增强学习算法实现了一个主题网络 蜘蛛系统，并将其应用于主题搜索引擎原型系统中。本文的主要研究内容如下： ( 1 ) 对国内外增强学习和主题搜索引擎的研究现状进行分析、总结，阐明了 增强学习算法能够用在主题搜索引擎网络蜘蛛中的可行性以及优势，在简要介绍 了增强学习和主题网络蜘蛛的原理和相关算法的基础上，设计提出了基于增强学 习的主题搜索引擎网络蜘蛛，在第5 章中对它的设计结构以及各模块的功能进行 了详细阐述。 ( 2 ) 针对于传统的主题网络蜘蛛存在链接价值评价标准单一，导致价值预测的 准确性低的问题，本文提出了一种基于增强学习的启发式主题网络蜘蛛模型， 相对于传统模型，新模型将立即回报价值和未来回报价值结合，用于计算链接 的综合回报价值。为解决对立即回报价值和未来回报价值信任度的权衡问题， 本文引入了价值置信函数的概念，在分析基于立即回报价值和基于未来回报价 值两类搜索策略特点的基础上，提出了基于未来回报信度递减的启发式搜索算 法，该算法的主要思想是将两类搜索策略的优势相结合，即在搜索初期，赋予 未来回报较大的信任度，使主题网络蜘蛛注重对资源的探测( e x p l o r a t i o n ) ，然后 逐步增加对立即回报的信任度，使主题网络蜘蛛更注重对资源的发掘 ( e x p l o i t a t i o n ) ，从而提高整体的搜索效率。 ( 3 ) 针对增强学习中的立即回报和未来回报的权衡问题，本文在设置主题网 第1 章绪论 络蜘蛛的架构时，也对这方面进行了考虑，设置了未来回报因子( 0 f l 1 ) ，在 初始训练时，由于处在增强学习的“探测”阶段，给予未来回报因子较大的值， 当训练之后，在抓取过程中，逐渐减少未来回报因子的值，以增大对立即回报的 权重，使主题网络蜘蛛更加注重对资源的发现。 ( 4 ) 设计实现了一个以“计算机 为专题的主题搜索引擎原型系统，在设计 中，采用l u c e n e 对保存的主题相关信息建立索引，通过实验分析，可以在很大程 度上提高用户体验，提高系统的查全率和查准率。 1 4 本文的组织 本文的内容共分为六章： 第1 章介绍了搜索引擎的发展概况并提出综合搜索引擎所面临的问题，分析 了主题搜索引擎国内外研究现状，并给出了本文的研究内容和结构安排。 第2 章对增强学习理论进行了简要介绍，并重点阐述了基于经验偏向信息学 习的增强学习算法及其改进，通过实验验证了改进算法能够大大提高解决问题的 效率。 第3 章介绍了主题网络蜘蛛的原理、分类，并对各种主题网络蜘蛛算法进行 了分析从而总结出主题网络蜘蛛搜索算法的性能评价标准。 第4 章将增强学习的思想和搜索引擎的网络蜘蛛的爬行策略相结合，提出将 经过改进的基于偏向信息学习机制的增强学习方法应用到主题搜索引擎网络蜘 蛛的搜索算法中的思想。 ，； 第5 章在学习研究开源全文搜索引擎n u t c h 的基础上，总结了它的总体架构 和工作方式，并对其架构和模块进行了扩充，最后设计了面向主题的搜索引擎网 络蜘蛛，详细说明了各个模块的流程、功能。对页面更新的重复抓取问题采用 m d 5 函数解决。 第6 章对本文设计的网络蜘蛛与开源网络蜘蛛w e b l o u p e 的抓取效果进行了 横向比较，并自身设置不同的系统参数，根据这些参数进行抓取实验，对抓取的 数据进行性能分析。 第2 章增强学习的算法研究 2 1 增强学习理论简介 2 1 1 增强学习简述 机器学习这门学科所关注的问题是：计算机程序如何随着经验积累自动提高 性能【9 】。近年来，机器学习被成功地应用于很多领域，从检测信用卡交易欺诈的 数据挖掘程序，到获取用户阅读兴趣的信息过滤系统，再到能在高速公路上自动 行驶的汽车等。机器学习理论致力于回答这样的问题【1 0 , 1 1 , 1 2 , 1 3 】：“学习性能是怎样 随着给定的训练样例的数量而变化的? 和“对于各种不同类型的学习任务，哪 个学习方法最合适? ” 在机器学习领域，大致可以将学习分为监督学习( s u p e r v i s e dl e a r n i n g ) 、非 监督学习( u n s u p e r v i s e dl e a r n i n g ) 和增强学习( r e i n f o r c e m e n tl e a r n i n g ) 三大 类。 监督学习，就是对于每一个输入，学习者都被提供一个目标，即环境或者“施 教者来告诉学习者，对于每次的输入应该做出如何回应。例如辨别是何种乐器 发出的声音。 非监督学习，主要是建立一个模型，用其试着对输入的数据进行解释，并用 于下次输入。采用隐马尔科夫模型( h m m ) 的语音识别系统，就是采用的这一 学习类型，h m m 通过在训练中记录下每一个语音之后，就可以用这些来识别输 入的语音了。 增强学习要解决的是这样的问题：一个能够感知环境的自治代理体( a g e n t ) ， 怎样通过学习选择能达到其目标的最优动作。当代理体在其环境中做出每一个动 作时，环境会提供奖励或惩罚信息，以表示结果状态的正确与否【1 4 , 1 5 , 1 6 】。例如， 在训练代理体进行棋类对弈时，施教者可在游戏胜利时给出正回报，而在游戏失 败时给出负回报，其他时候为零回报。代理体的任务就是从这个非直接的、有延 迟的回报中学习，以便后续的动作产生最大的累积回报。自上世纪8 0 年代末以 来，由于数学理论上的突破而取得了长足的发展，增强学习现在已经是机器学习 领域的热点方 占- j 1 1 7 , 1 8 】。 我们通过观察幼儿的活动可以发现，他们从来都不是静止的被动等待环境对 他进行刺激，而是动态的主动去试探环境。并通过环境对试探动作所发生的反馈 来选择下面继续做何种试探。 北京t 业大学t 掌硕十学位论文 从图2 1 可以看到增强学习由环境和代理体两部分组成【l9 1 。代理体学习一个 控制策略以使累积回报最大化，这个控制策略可以归结为一个通过学习来控制序 列过程问题。从图中可以看出此代理体生存的环境被描述为某可能的状态集合 s 。它可执行任意的可能动作集合a 。每次在某个状态s ，下执行一动作a t ，此代 理体会收到一个实值回报，：，它表示此状态动作转换的立即值。如此产生了一 系列的状态墨，动作q 和立即回报i 的集合。如图所示，代理体的任务是学习一 个控制策略万：sja ，它使这些回报的和的期望值最大化，其中后面的回报值 随着他们的延迟而指数减小。 q口2 7 而1 屯1 簟 图2 - l 增强学习的系统结构图 f i g u r e2 - 1s y s t e ms n i l c t i l r eo f r e i n f o r c e m e n tl e a r n i n g 我们假定代理体学习最优控制策略的问题是一个马尔可夫( m a r k o v ) 决策过 程问题2 们，在马氏决策过程( m a r k o vd e c i s i o np r o c e s s ，m d p ) q a ，代理体感知到当 前状态岛，选择当前动作a ，并执行它。环境响应此代理体，给出回报，；= ，( 暑，a ，) ， 并产生一个后继状态s = 万( _ ，a t ) 。这里万和，可为非确定性函数，但我们首先 从确定性的情形开始。 代理体的任务是学习一个策略万：s a ，它基于当前观察到的状态s ，选择 下一步动作a t ，即石( _ ) = a t 。如何精确指定此代理体要学习的策略万呢? 一个明 显的方法是要求此策略对代理体产生最大的累积回报。为精确地表达这个要求， 我们定义：通过遵循一个任意策略7 r 从任意初始状态s t 获得的累积v 石( s 。) 为： y 疗( 墨) 三，；+ y + l + 厂2 ，；+ 2 + ( 2 - 1 ) 第2 苹增强学习的算法研冗 三7 ，；“ 其中是代理体从状态到状态+ 。所产生的立即回报，r ( o 7 t oe x a m p l e s e l s ei fp o s i t i v e e x a m p l e ( a ，s ，q t a b l e ) a d d ( 易( j ，暑) ，口) t oe x a m p l e s n e g a t i v e e x a m p l e ( a ，s ，q - t a b l e ) i fq ( s ，a ) = 0 r e t u r nt 1 1 l e e l s e r e t u r nf a l s e p o s i t i v e e x a m p l e ( a ，s ，q t a b l e ) i fq ( s ，a ) = m a x 。q ( s ，a 。) r e t u r nt r u e e l s e r e t u r nf a l s e 我们对这个算法作一些评注：首先在进行q 学习生成q 值表的过程中，局部 状态特征并没有被使用。在简单训练任务上的q 学习只是使用标准的状态来进 行。局部状态特征仅是在产生状态行为训练样例的时候才使用。这个不同导致 两个状态的局部状态特征值可能是相同的而每一个状态的特定最优行为是不同 的。第二，如果除了使代理体移动到目标状态的行为外，给其他所有的行为都赋 一个非常小的负回报，那么如果将表2 2 算法中n e g a t i v e函数的“if_example q ( s ，口) = o 行改为“i fq ( s ，口) o ”，则上述算法仍成立。即是在这个新的回报结 构下，导致失败的行为将有一个负值，而最终走向目标状态的行为将有一个正值。 注意这些负回报在绝对值上必须小于任何到达目标的最优路径的折扣价值。第 三，出于实用性考虑，一个q 学习通常不需要覆盖所有的q 价值，尤其是那些它 没有发现导向目标状态的情况。为了避免生成很多噪声样例，只有被访问了指定 次数的状态才能被使用。 ( 3 ) 建立分类器集样例集合( 见表2 2 ) 包含以局部状态特征作为参数，以 尝试或者不尝试某个行为作为输出的实例。 为了使这些信息对解决新的任务有帮助，我们需要将其精简为能够很快说出 在任何状态下哪些行为值得尝试，哪些行为不值得尝试的形式。此外，由于不是 所有可能的局部状态特征集都己被发现，从数据中进行一些概括还是必要的。 使用标准的机器学习分类算法的一个困难是对于任何的状态，期望的输出 是：每个行为应该或不应该去尝试，而不是输出一个简单的值。有一个简单的解 决方案，对于每个行为训练一个的分类器，结果输出这个行为是否值得尝试。 我们学习一个分类器集合，每个分类器将局部状态特征映射到一个行为是否 值得尝试，并且这个映射是基于训练任务中得到的q 值表中的经验信息。 ( 4 ) 偏向探索最后一步是在新的任务中使用分类器集合，使增强学习进行偏 向探索。 当一个增强学习代理体尝试去决定采用什么行为时，它给每一个当前时刻t 下状态s 的可选行为口赋一个选择概率只( 口，j ) ，( 。只( 口，s ) = 1 ) 。这个概率分布 通常是基于增强学习代理体的探索策略和当前的q 值。然后增强学习代理体根据 概率分布任意选择一个行为。 我们结合学习后的分类器来提供一个新的偏向机制改变这个概率分布。 假设这些分类器只是根据训练数据返回每个行为应该或不应该尝试。那么我 们更愿意给分类器认为应该尝试的行为更高的概率权重。 我们正式为所有的行为a 和状态s 定义权重函数w 如下： 俐泛蓼0 等曼 ( 2 - 1 7 ) 其中和 w n e g 是预定义的一个大数和小数，对应于分类器返回的某个行为 应该或不应该尝试。 此外，分类器也可以在分类的同时返回一个置信值。算法就可以根据置信值 去权衡不同的行为。所以对于所有的行为口和状态s ，使得 w ( a ，s ) = 厂( 巳( s ) ) ( 2 - 1 8 ) 其中，分类器乞现在返回一个直接与置信值成比例的值。其中，厂是任何非 递减的非负函数。 我们接下来引入一个仅基于分类器的探索策略，它只决定于经过学习的分类 器。假设增强学习代理体用w ( 口，s ) 值来权衡每一个行为，则行为口被选择的概率 是： 丛! ! 兰! z a w ( a ，s ) ( 2 1 9 ) 北京t 业大学t 学硕i ：学位论文 在我们的整个方法中，经过学习的分类器可以和任何内建的探索策略结合， 我们采用b o l t z r n a n n 探索策略。我们让p t ( a ，j ) 来获取偏向信息。下面，我们引入 联合分类器内置探索策略。其中，行为a 以概率 w ( a ，s ) p t ( a ，s ) 。巾，j ) c ( 口，s ) ( 2 - 2 0 ) 被随机选择。即增强学习代理体根据分类器导出的w ( a ，s ) 值来权衡概率。 特殊情况下，如果= 1 并且馏= o ，那么只有根据分类器得到的行为才会 被真正采用( 所有被分类器否决掉的行为都为权重w 懈) 。这无形中剪除了很大 一部分搜索空间，但是它要求分类器有很高的精确度来保证最优策略的实现。 2 3 实验 我们将基于经验偏向信息学习机制的增强学习方法加以实现，并在多个迷宫 任务中进行了测试。在训练任务中我们采用了经典的q 学习方法。 开始，在一个简单的迷宫任务中，我们使用一个决策树作为状态行为分类 器。决策树提供了一个偏向机制来学习新的迷宫任务，这大大减少了搜索时间。 在本文中，我们在复杂的推箱子任务中进行了试验，下面我们简单介绍一下 推箱子任务和试验的建立。 2 3 1 推箱子任务( $ o k o b a n ) 推箱子任务的目标是将方格中所有的小球移动到目标方格。每一个方格或者 是开放或者是受到墙的阻塞。一个开放的方格可能是如下情况： 里面有一个小球； 里面是一个代理体； 此方格是目标位置。 作为代理体有如下行动规则： 有最多四个确定的可能行为：向北，东，南，西移动； 不能移动到阻塞位置； 如果代理体移动到邻接方格中有小球的方格则推动小球；就是说如果代 理体在位置( x ，”，并且在它的北边有一个小球，坐标为( x ，y + 1 ) ，那么当 代理体向北移动时，代理体和小球的新位置在( x ，y + 1 ) 和( x ，y + 2 ) ； 不能将小球顶着墙推； 第2 章增强学习的算法研究 因为代理体只能推动而不能拖动小球，所以有很多种情况会导致小球被卡 住。例如，如果小球被推到拐角则小球就动不了了，并且如果小球被推到墙上， 则小球只能沿着墙走，除非在小球被移到拐角之前墙就到头了。因此，很多小的 方格阵中的推箱任务是非常难以解决的。如果能避开这些会被卡住的位置将会很 大的缩小搜索空间。但是应该注意的是很多这种位置是很难事先发现的。 2 3 2 实验建立 我们将状态定义为代理体和每个小球所处的位置。每移动一步给一个小的负 回报，所有的小球都被移动到目标位置，给一个大的正回报。因为可能会出现走 到某一步无法达到目标状态的情况，并且这种情况很难事先看出来。故限定当推 箱次数达到一个上限时则此任务被重置。 局部状态特征用来描述以代理体的所在位置为中心，为半径的区域内的方 格位置。注意半径，至少为3 ，以表明一个移动是否会将球推到墙上或拐角。在 我们下面的试验中我们设定，= 4 。每一个局部状态位置用三个属性之一描述：阻 塞、有球、是目标方格。 需要注意的是方格阵有着固有的对称性。例如，从某方格的小球向东移动一 格相当于整个方格阵逆时针旋转9 0 度后小球向北移动一格。因此我们为北移行 为生成一个分类器。我们使用一个标准的反向传播神经网络。它的输入是局部状 态特征( r - - 4 ) ，输出是向北移动这个行为是否值得尝试。 在处理一个新任务时，当前状态的状态特征值和它的每一个旋转都依次提交 给分类器以确定四个方向移动是否值得。 2 3 3 实验结果 推箱子任务的第一个测试中，我们首先使用q 学习方法来学习1 2 个简单任 务。每个任务仅包含一个球和一个目标位置和一个外围的墙。不同任务改变开放 空间的数量，方格的大小分别是5 5 ，l o x l 0 和2 0 x 2 0 ( 见图2 4 ( a ) ) 。 北京t 业大学t 学硕十学位论文 n b d _ b ( a ) ( b ) 图2 - 4 两种推箱子任务的方格阵 f i g u r e2 - 4t w oe x a m p l es o k o b a ng r i d 在q 学习解决了这些训练任务之后，我们开始测试一些相似的方格，如8 x 8 ， 1 6 x 1 6 方格。 作为对比，q 学习在这些方格上测试时使用分类器运行一遍，再不使用分类 器运行一遍。基于经验偏向机制的增强学习代理体使用同样的内置探索偏向机制 进行标准q 学习并且使用= 1 和曙= 0 的分类器。 我们定义“试探 为导向目标状态的行为集或者1 0 0 0 0 次移动的集合，只要 二者发生其- - n 称为一个试探。对于允许q 学习运行的每一次试探，基于学习到 的q 值表运行一个测试。特别的，这个测试包括完善q 值表，并且允许代理体遵 循当前q 值表定义的策略( 在若干行为被同等最大化的情况下，一个行为被等概 率得随机选择) 。这样做1 0 0 次，每次最多允许代理体移动1 0 0 0 0 次，当代理体 达到目标的时候，到达目标的平均移动次数被记录下来。 我们作了大量的试验进行测试。图2 5 显示了对于8 8 开放式方格的试验结 果。图中显示了不同球布局和目标位置的试验结果。x 轴表示试探的次数，y 轴 表示到达目标状态的平均步数。如果在某个测试中上百次运行但没有一次成功到 达目标状态，那么就不标注数据点。每一个测试中代理体的摆放是随机的，因此 在图中即使q 值表已经收敛了，平均移动步数可能也不是恒定的，这是图中出现 摆动的原因。 至! 兰兰翌茎至墼至鎏鐾蓍 8 x 8 开放式方格阵 3 u 2 8 2 6 2 4 1 方格阵1 的偏向探索 裁2 2 方格阵2 的偏向探索 蛰2 d 方格阵l 的标准探索 1 8虬n 睁每a e l & 出比 、 1 5 方格阵2 的标准探索 1 4 1 2 1 n 试探次数 图2 - 5 开放式8 x 8 方格阵中的测试 f i g u r e 2 - 5 t 缸k o n8 x 8o p 蚰9 础 正如图中所显示的，使用经过学习的分类器后学习代理体的收敛速度明显加 快了。在所有的情况下，基于经验偏向机制的增强学习代理体收敛到的策略不会 次于或者说好于不使用偏向机制的标准学习体。 作为第二个测试，在1 2 个更复杂的大小为2 0 x 2 0 ，有几个阻塞位置的