论文部分内容阅读
传统的规划及搜索技术已经在诸多领域（如太空望远镜的调度安排、路线规划）得到了广泛的应用,但随着当前IT技术的快速发展（如互联网技术、AI技术）,对规划及搜索技术的研究及应用提出了新的要求,尤其是如何利用人类信息来更好地解决复杂的规划问题或实现更加高效的搜索已成为诸多新兴应用场景下亟待解决的关键问题（在本文中,把人们进行各种活动或行为形成的即时的或历史的信息数据统称为人类信息,如用户的账号信息、参与者的投票信息、执行者的决策信息等）。在传统的规划和搜索技术中,存在着一些较为通用的模型、算法、及相关理论,但都没有较好的和人类信息相结合。因此,本文将着重研究如何在规划和搜索技术中引入合适类型的人类信息,通过人类信息驱动,使得相应的模型和算法更加精准、更加高效,同时更加契合人们的实际应用需求。具体的研究内容包括:利用历史投票信息改进的部分可观察马尔可夫决策过程（Partially Observable Markov Decision Process,POMDP）、基于反馈信息的迁移学习（Transfer Learning）、账号信息辅助的网络搜索技术、经验信息引导的程序化内容生成（Procedural Content Generation,PCG）技术。具体阐述如下:1)在一些众包应用的场景下,往往需要对相关的信息（投票信息）进行收集,如何规划信息收集的终止时间节点是一个重要的研究问题。已有的研究在进行规划时主要基于POMDP模型,但是由于信息收集的环境未知,因而往往采用机器学习（Machine Learning,ML）等手段来训练POMDP模型的相关参数,从而可以有效地规划信息收集的终止时间节点。本文的研究进一步从两个方面改进了基于投票信息的POMDP模型:首先,众包任务往往基于单步收集信息（即单位信息）进行规划,而单位信息包含的信息量极少,从而在收集具有长序列证据信息特征的信息时效率低下,因此本文提出了一种基于多步收集信息的规划方法来有效提升规划效率;其次,在POMDP的规划过程中设计合理的提问可有效提升收集的信息中包含的信息量,因此,本文进一步研究了面向POMDP规划过程的提问策略,从而可以在每轮的多步收集后,基于众包任务的实际特征动态地调整提问的顺序,使得参与者在回答问题时能够提供更加精确或包含更多信息量的信息,这种提问策略的优化能加快众包任务的信息收集进程,得到更优的规划方案。通过在Galaxy Zoo 2的众包项目（全球范围内的星系问题投票）上的实验验证,本文所提出的基于多步信息收集的规划方法相比已有的单步规划方法（MC-VOI）具有显著的时间优势,同时相比于已有的多步规划方法（如有限视野算法LLA）,在节约信息收集成本和提高信息收集效率上取得了有效的提升。2)在模拟环境中模拟训练所输出的策略往往需要最终迁移到现实环境,但模拟环境和现实环境总是存在着差异,这使得迁移的策略有时无法达到预期的效果,甚至在某些极端的情况下会带来巨大的损失而不可接受,因此,基于反馈信息的迁移学习具有重要的研究意义。在已有的研究中,往往利用统计分析来确定盲点（由于模拟环境的局限性而导致决策在现实环境下形成的未知错误状态）。尽管已有的研究利用了反馈信息,但只是简单地基于经验对导致盲点的策略进行替换。在本文的研究中,利用近似动态策略规划（SADPP）方法来获得模拟环境下的策略并将现实环境建模成马尔可夫决策过程（Markov Decision Process,MDP）,同时根据采样的人类反馈信息提出了基于决策树的盲点划分方法（基于Dawid-Skene算法、C4.5算法）。最后,基于获得的盲点,设计了补充模型的建模方法,并通过补充模型和设计的FRU-SADPP算法,最终修正了迁移的策略。通过Py Game学习环境中的Catcher和Monster Kong游戏上的实验,验证了本文提出的方法用于修正策略的准确性和可扩展性。3)在许多应用中都需要处理图上的密集子图挖掘问题,而这个问题也一直是数据挖掘领域中的一个关键的研究点。在社交网络或商业网络的应用中往往存在着人工举报诈骗用户或商品ID的情况,为了根据这些ID进一步找到所涉及的诈骗集团,则需要进行局部最密子图的挖掘。针对这一应用场景,本文研究了ID信息辅助的网络密集子图搜索技术,这种技术将搜索诈骗集团的任务转化为一个局部最密子图的搜索问题,即找到无向图（二部图或者非二部图）上,包含或者邻近一个给定结点的平均度最大的子图,其中,给定结点由人工举报的诈骗ID信息确定。该研究相比于已有的研究,重要的改进在于以平均度来度量子图的密度,同时给出了搜索局部最密子图的Slither算法和Slither PR算法。根据在二部图和非二部图上的实验结果,提出的算法与其它局部子图搜索算法（Find Dense、Hi DDen、HPR）相比,在所找到子图的密集性、算法的适应性和可扩展性上具有一定的提升,最后,在一个大型社交网络Twitter上进行了真实环境下的诈骗集团检测,其结果验证了所提出的技术的有效性。4)PCG技术常用于当前很多游戏关卡的设计中,现有的PCG技术往往由机器独立生成游戏关卡,使得生成的关卡缺乏趣味性和难度。为了解决这一问题,通常采用针对已有关卡（人为设计）进行统计分析的方法,但收效甚微。因此,本文研究了一种经验信息引导的PCG技术,与已有研究不同的是,该技术直接从关卡设计者的经验信息出发,采用了反向设计的思想,将经验信息用于关卡轮廓的建模,随后通过多目标基因算法（NSGA-II）寻找由关卡轮廓到具体关卡的最优解,该最优解将关卡趣味性和难度作为优化目标,从而有效解决了趣味性和难度的难以保持的缺点。通过关卡求解器在生成的游戏关卡上的求解多样性（趣味性评估）和求解复杂性（难度评估）的分析,验证了所提出的PCG技术的有效性。