CP-nets的可满足性序列求解算法研究

CP-nets是一种简单、直观的图形化偏好表示工具,成为近几年人工智能的一个研究热点。然而对于CP-nets的基础性质——可满足性序列的研究却较少。通过构造CP-nets导出图,利用改进的图的深度优先遍历算法实现二值网的强占优测试,对强占优测试得到的可达矩阵进行分析,得出任意结构CP-nets的可满足性序列个数关系;给出了生成全部可满足性序列的算法;强化和扩充了CP-nets的基本概念,深化了CP-nets的基础理论研究。

CP-nets的可满足性及一致性研究

CP-nets是一种简单而又直观的图形化偏好表示工具,成为近几年人工智能的一个研究热点,然而对于CP-nets的可满足性和一致性等相关性质的研究还很欠缺.既没有给出严格的定义,也没有探讨不同性质之间的联系,没有一个求可满足性序列的通用算法.从研究CP-nets的可满足性和一致性的关系着手,得出了任意结构二值CP-nets的可满足性判定算法及可满足性序列生成算法.首先通过构造CP-nets导出图及其性质的研究,得出CP-nets的可满足性及一致性的相关定理.再把不同性质结合起来分析,给出CP-nets可满足性等价于一致性的结论,从而利用拓扑排序的思想实现了任意结构二值CP-nets的可满足性序列的生成.强化和扩充了Boutilier所提出的一些概念,深化了CP-nets的基础理论研究.

CP-nets学习的复杂度

CP-nets是一种简单且直观的图形化偏好表示工具,其表示、推理和学习是3个基本问题。不同于基于统计学习理论的研究方法,文中基于逻辑理论来研究二值CP-nets的学习问题。首先,建立命题公式的可满足性和CPnets表示的偏好公式之间的联系,将CP-nets的学习问题转化为命题的推理问题。随后,给出两类具有特殊结构的CP-nets的学习问题的计算复杂度,其中最复杂的无环CP-nets上的学习问题是NP-complete,而最简单的集合结构CP-nets上的学习问题是P。这些结论给出了CP-nets(如链结构、有界树宽)学习问题复杂度的上下界。

CP-nets的定性偏好决策及一致性推理

CP-nets是一种简单而又直观的图形化偏好表示工具,特别适合描述不完全信息下的具有依赖关系的多属性定性偏好决策。首先通过构造CP-nets导出图及对其性质的研究,得出强占优测试本质上是导出图上顶点之间的可达性问题,从而利用图的深度优先遍历算法实现了二值网的强占优测试;然后分别从无环图、有环图的角度给出CP-nets一致性的相关定理和性质,提出了判断一致性的3种方法,使得CP-nets的一致性问题得到解决;强化和扩充了Boutilier所提出的一些概念,深化了CP-nets的基础理论研究。

基于表决策略的CP-Nets可满足性序列的聚合

条件偏好网(CP-Nets)的可满足性序列是由决策者的偏好信息得到的一个关于所有配置的排序表,其中偏好关系具有不完备性和传递性.主要分析借鉴传统的表决策略来实现CP-Nets的可满足性序列的聚合的可行性,介绍"少数服从多数"和"与位置相关"策略在CP-Nets的可满足性序列的聚合的具体实现并进行性能分析.实现传统表决系统的一个从完备到非完备的推广应用.

机器人的CP-nets优化类人轨迹规划（英文）

机器人移动轨迹按照人的手臂来模拟是提高机器人安全性和人机交互能力的有效方法;特别是针对机器人抓取路径不唯一的场合,类人行为对于人机系统表现更加自然.此前,通常利用Kinect等设备,基于人工神经网络和K近邻算法等智能算法对类人轨迹进行规划,但无法获得未采样过的最优轨迹.本文基于CP-nets采用偏好模型研究类人运动轨迹,然后将该模型应用于机器人控制,在没有采样的情况下,也可得到最优的类人轨迹.实验结果表明,基于CP-nets的类人规划轨迹具有较高的效率和舒适性,符合人的运动特征.

基于时间敏感滑动窗口的CP-nets结构学习

随着人工智能的发展,条件偏好网(Conditional Preference networks,CP-nets)的学习和表示被广泛研究.此前的研究工作主要集中于从静态数据库中挖掘用户的条件偏好,而在许多新兴应用中,数据通过互联网或传感器网络流动,偏好也会随之发生变化.将挖掘偏好的方法扩展到动态环境是一个挑战,遇到的问题主要包括对连续数据进行的快速处理、庞大的数据量以及有限的内存资源等.针对偏好数据流,提出一种基于时间敏感的滑动窗口模型来挖掘条件偏好关系和学习CP-nets结构的方法,该方法包括一个用来获取所有可能偏好关系的存储结构以及一个对偏好关系进行累积计数的数据结构,并提出基于时间敏感滑动窗口的条件偏好关系挖掘算法,根据输入的偏好数据流比较基本块与滑动窗口的大小对条件偏好关系进行插入和更新.实验结果表明,与其他学习CP-nets结构的方法相比,该方法所需的运行时间少,得到的CP-nets的结构更准确.

基于启发式算法的CP-nets学习研究

CP-nets(条件偏好网)是定性表达偏好关系的一种图形工具,作为一种表达能力的工具,CP-nets功能强大,能直观、自然地表达用户的偏好信息。但是对于CP-nets学习的研究还不够深入,在实际应用中,由于用户行为或者观测误差的随机性,可能导致数据集中存在噪声数据,使得许多传统的学习方法无法得到最优的CP-nets结构。本文提出基于启发式算法的学习方法来解决CP-nets的结构学习问题。与传统方法中直接学习CP-nets结构不同,本文将CP-nets的结构学习问题转化为寻找最短路径问题,利用启发式算法的能力来寻找最优的CP-nets。

结合反向矩阵和频繁模式树方法的CP-nets结构学习

提出一种基于反向矩阵结构在数据流上挖掘条件偏好和学习CP-nets的方法。利用反向矩阵的事务布局,减少了扫描数据库的次数,并且通过随机访问,在不到一次完整扫描的情况下得到频繁的偏好项。此外,通过建立频繁模式树FP-Tree,减少了候选项的生成。实验结果表明,与其他学习CP-nets结构的方法相比,该方法可以较快获得准确的CP-nets,在大型事务数据库方面表现出良好的性能,减少了内存需求。

基于特征选择的CP-nets结构学习

作为描述多属性之间定性条件偏好的一种图模型,条件偏好网(Conditional Preference networks,CP-nets)的结构学习问题在CP-nets的研究中起着重要的作用.不同于传统的CP-nets学习方法,提出基于信息论和特征选择的方法来研究偏好数据库上的CP-nets的结构学习问题.首先建立了偏好数据库上的互信息和条件互信息的求解方法,并将互信息看作一个属性和它的可行父亲之间的相关性,条件互信息看作可行父亲集中属性之间的冗余性,从而构造出极大相关极小冗余(Maximal Relevance Minimal Redundancy,mRMR)的目标函数,同时指出,一个属性的父亲集是由属性之间冗余度小,但对孩子属性的偏好却影响极大的属性子集组成的.随后基于特征选择中的mRMR方法来实现CP-nets的结构学习,并设计相应的算法来完成从偏好数据中学习CP-nets的结构.最后在电影推荐数据集上验证了算法的有效性.研究结果表明,基于mRMR的特征选择方法可有效获取变量之间的因果关系,从而求取出每个属性的父亲集合,进而获得CP-nets的结构.

基于滑动窗口的CP-nets增量式学习研究

偏好信息挖掘是人工智能领域数据挖掘中一个重要的研究内容,近年来得到了广泛的研究.随着当前社会发展和数字数据的急剧增长,实时应用中的偏好数据是以数据流的形式快速生成。然而,挖掘偏好的动态特性越来越需要适应流式数据变化的解决方案。造成这种情况的主要原因是用户的偏好不是静态的,可以随着时间的推移发生变化,而传统的偏好求取方法大多集中应用在静态数据集中,不能高效地处理数据流。本文主要采用基于窗口的CP-nets增量式学习算法处理偏好数据流。该算法在合成数据集和真实数据集上的实验结果表明本文提出的算法能够根据用户的上下文偏好信息得到与传统学习算法大体一致的较准确的用户CP-nets模型,并且与传统算法比较,该算法的时间复杂度低,算法效率更高。

一种基于UML和CP-net集成描述的面向对象软件的交互测试方法

面向对象技术在软件工程中的推广使用,使得传统的测试技术和方法受到了极大的冲击.对面向对象技术所引入的消息传递、数据抽象、封装、继承、多态等新特点,传统的测试技术已经无法有效的进行测试.对面向对象软件的测试,测试策略或方法都需要出现相应的变革或更新.本文给出一种基于UML和CP-net集成描述的面向对象软件的类集成测试方法,重点在于测试不同的类方法之间的交互行为.这种方法首先用UML和CP-net集成描述用户需求,然后基于这个描述模型,按照基本路径覆盖的标准自动产生测试例.

利用属性条件偏好推理的在线服务群体选择

在线服务群体选择能够在多人社交活动中提供适合群体的活动方案.在线服务群体选择中,如不考虑用户的服务属性偏好,则难以对未体验服务的偏好进行推理,导致对未体验服务的预测偏好与用户真实偏好存在差异,使得聚合个体用户偏好得到的群体选择结果难以真实反映群体对服务的偏好.为此,提出一种利用属性条件偏好推理的在线服务群体选择方法.首先根据用户对服务属性的偏好建立条件偏好表和属性之间的依赖关系;然后根据条件偏好网络(Condition Preference networks,CP-nets)的性质推理偏好导出图,偏好导出图的拓扑排序对应用户对服务属性值组合的偏好关系,得到个体用户的服务选择结果;最后使用社会选择函数Ranked Pairs对个体用户的服务选择结果进行聚合,得到群体的服务选择结果.通过实验验证了该方法的合理性和有效性.实验结果表明方法得到的群体结果与个体用户选择结果的平均nDCG(Normalized Discounted Cumulative Gain)比对比方法分别高11.4%、2.2%和11.1%,方法还满足多数准则、孔多赛性、抗操纵性等性质.

基于Colored Petri网的安全协议描述和验证

对网络安全协议进行形式化描述和正确性验证有助于消除协议的设计缺陷,发现协议的不精确性。本文将使用具有强数学基础和强分析能力的着色 Petri 网(Colored Petri Net,简称 CP-Nets)对 NS 公钥认证协议(Needham-Schroeder Public-Key Authentication Protocol)送行建模.在此基础上分析验证该协议,阐明协议存在的缺陷并给出改进的方法。

资源的形式化配置及其在医疗行业中的应用

基于经验的人工配置无法保证精准的需求表达,导致医疗资源的利用效率低下。提出一种医疗资源配置决策系统架构,兼顾需求表达的形式化表示及资源之间内在的制约关系。在给出医疗资源配置决策系统架构之后,采用社会选择和偏好理论对医疗资源分配问题进行建模,形式化表示资源数量需求,并实现基于CP-nets的资源依赖关系表示。通过对需求的收集和处理,进而确定个人偏好的最优方案,并得到可行配置方案的偏好排序。应用案例表明,提出的方法能有效地实现医疗资源的配置。

Web服务组合的有色网模型及运算性质

定义了一种基于有色Petri网的Web服务组合模型,这一模型能清晰表达服务组合中各组成部分之间的逻辑关系,并可模拟组合服务的执行,分析其动态性质．给出了服务、服务组合运算的定义及性质、服务组合的建立与执行算法．

基于定性多用户偏好的Web服务选择

随着Web服务数量逐渐增多,出现了许多服务提供者提供功能相同或相似服务的情况.如何在一些功能相似或相同的服务集合中,根据用户对服务质量的需求选出更符合用户要求的服务,是当前研究人员普遍关心的课题.本文提出一种定性的服务选择方法,用来解决涉及多个用户的Web服务选择问题.各用户对服务质量的需求被表示为偏好.提出的算法将能够综合考虑各个用户的偏好,使选出的服务尽可能满足大部分用户的偏好要求,并给出了一个实例说明该算法的应用.实验结果表明了算法的有效性.

复杂网络软件的着色Petri网层次建模及模型集成确认方法

为准确描述复杂网络软件多交互、高并发等行为特征,以提高复杂网络软件设计质量和效率,提出了一种基于着色Petri网(CP-net)的复杂网络软件层次化建模及模型集成确认方法。给出了复杂数据抽象、并发行为控制、同类实体建模等层次建模关键技术,以及功能单元覆盖划分、模型等价抽象等模型集成确认关键技术的解决方案,并以典型网络软件系统为例分析了上述方法的可用性和有效性。从目前鲜有对特定形式模型论述模型正确性确认方法的现状看,这种融合多种CP-net模型分析技术的模型集成确认方法能够有效确保层次模型正确描述网络软件多交互、高并发的复杂功能行为,为软件验证、一致性测试等重要软件分析过程的高效实施提供描述准确且规模可控的基础形式模型。

剪枝技术在占优查询中的应用

用户的偏好在很多情况下可以引导用户的选择,有关偏好查询的问题在关系型数据库中成为越来越重要的问题.在很多应用中,相对于定量偏好,定性偏好能够应用的范围更广.已有的多属性偏好研究中偏好属性都不具有依赖关系,而CP-nets是一种表示具有依赖关系的多属性定性偏好的图模型.目前,对偏好查询的处理主要使用占优查询,通过用户的偏好依次比较两个配置,从而得出满足用户偏好的配置.对配置进行两两比较会造成极大的资源浪费,为了降低其配置的比较次数.提出将剪枝技术应用于占优查询中,通过对翻转序列的路径进行修剪,从而有效地减少数据库搜索的空间.

基于Prüfer编码的随机图模型生成算法

根据图模型的结构特征和参数特征等要素设计生成随机的模型,根据顶点数与度的大小生成随机结构的CP-nets,其原理是通过改进Prufer编码得到DAG编码,又建立DAG编码与图结构的一对一映射实现图模型的随机生成。通过设计的占优查询算法与典型的占优查询相结合验证了占优查询算法的时间消耗严重依赖于图拓扑结构的随机性和参数数量的随机性。