基于偏好优先级进行CP-nets一致性序列求解

首先,设计CP-nets一致排序生成算法,该方法通过量化用户的每个结果属性的偏好,获取结果属性的偏好优先级,这些值能准确地反映出用户的偏好,从而得出任意结构CP-nets的一致排序。最后通过实验验证,与其他方法相比,该方法获得一致性序列所需的运行时间少,推理速度快,得到结果的效率更高。

CP-nets的完备性及一致性研究

CP-nets是一种简单而又直观的图形化偏好表示工具,成为近几年人工智能的一个研究热点.然而,任意二值CP-nets上的强占优算法还没有给出,CP-nets可表示的偏好的完备性还无人研究,CP-nets所能表示的偏好是否一致也还未彻底解决.基于CP-nets上的强占优运算研究CP-nets的完备性和一致性.首先,通过构造CP-nets导出图及其性质的研究,得出强占优的本质是求取翻转关系的传递闭包,从而利用Warshall算法求出可判断任意CP-nets的强占优;其次,通过求取3种不同结构(可分离的、链表结构和树形结构)的CP-nets的偏好个数,给出了CP-nets可表达的偏好的不完备性定理,并给出了可分离的CP-nets中偏好的计数公式;最后,研究CP-nets的一致性,给出了CP-nets的一致性判定定理及其算法.所做工作不仅解决了Boutilier和Goldsmith提出的一些难题,还深化了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是一种简单、直观的图形化偏好表示工具,成为近几年人工智能的一个研究热点。然而对于CP-nets的基础性质——可满足性序列的研究却较少。通过构造CP-nets导出图,利用改进的图的深度优先遍历算法实现二值网的强占优测试,对强占优测试得到的可达矩阵进行分析,得出任意结构CP-nets的可满足性序列个数关系;给出了生成全部可满足性序列的算法;强化和扩充了CP-nets的基本概念,深化了CP-nets的基础理论研究。

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

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

CP-nets及其表达能力研究

偏好处理是人工智能中的一个重要研究内容,它的4个研究热点是偏好的表示、提取、聚合和推理.条件偏好网(Conditional preference networks,CP-nets)是一种简单直观的偏好表示的图形工具,但很少有工作研究CP-nets的表达能力.本文研究CP-nets的表达能力,详细研究了CP-nets表达偏好的完备性,其上构造的运算复杂度以及适用的场合.首先给出了CP-nets模型上的几个运算,利用改进的Warshall算法求出了二值网的强占优测试在最坏情况下的复杂度为O(4n).其次通过构造CP-nets导出图及其性质的研究,得出CP-nets特别适合不完全信息下的多属性定性偏好决策.当需要处理更完全信息时,可借助于与Agent的交互来完成.虽然我们给出了CP-nets的强占优测试的理论解,但其理论上可解,实际上不可解.为了解决强占优测试的指数级复杂度问题,本文最后给出了一种带有软约束的满足问题(Soft constraint satisfactionproblem,SCSP)的求解方法.它把CP-nets中的定性运算转为约束半环中的定量运算,从而将指数级的复杂度转化为多项式的复杂度,间接提高了部分CP-nets的表达能力.本文所做的工作是对Boutilier和Bistarelli工作的改进和提高.

CP-nets学习的复杂度

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

利用SCSP实现CP-nets的强占优测试

基于"从CP-nets向SCSP规约"的思想来实现CP-nets的强占优测试,实现了CP-nets中的定性判断向约束半环中的定量判断的转换.通过重新定义转换规则,修正了刘惊雷提出的方法中的错误,文中阐述了具体的实现方法.

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

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

CP-nets上的正则化路径查询

从表示偏好知识的条件偏好网(CP-nets)模型出发,研究该模型上的正则化路径查询问题.首先从数据库的观点给出偏好数据库的两类查询(顶点查询和路径查询),并证明偏好数据库的表达能力强于关系数据库.其次,通过构造正则表达式的语法解析二叉树,求出各自原子表达式诱导的可达关系,从而利用动态规划法求解出CP-nets上正则表达式所诱导的可达关系,并证明算法的正确性,分析其组合复杂度.最后,给出正则化路径查询的可能应用,即可在偏好操作序列的规划中使用.

基于精确P值计算学习无环CP-nets

作为一种简单直观的图形表示工具,条件偏好网(conditional preference networks,CP-nets)可表示ceteris paribus(其他条件都不变)的偏好关系.学习无环CP-nets是人工智能领域中的一个重要的研究内容,它可广泛使用在推荐系统、信息检索和群体抉择中.特别是有效地学习无环CP-nets的结构,即获取变量之间的因果关系,是当前最主要的研究任务.传统的算法利用不同的方式对CP-nets的结构进行学习,但很多方法学习得到的并不是无环CP-nets.采用精确P值计算学习方法,根据Dijkstra算法原理,设计了新的算法——PALA,并通过该算法学习无环CP-nets结构.随后证明了算法的时间复杂度是O(n3·2n).作为一种精确学习方法,精确P值计算方法可有效衡量变量之间的依赖程度,确定变量之间的因果关系,进而学习得到无环CP-nets结构.实验结果表明,与其他算法相比,PALA算法通常能够发现高质量的、结构最优的无环CP-nets.研究结果还表明,无环CP-nets学习问题的解决显著地提高了PALA算法的效率.

基于CP-nets的多议题对称依赖关系的研究

为了进一步丰富CP-nets对偏好语言的描述能力,提出了一种名为SDCP-nets的图形工具。该工具利用效用矩阵,刻画议题间的对称依赖关系,在SDCP-nets中,条件偏好关系的刻画使得择优选择和搜索最佳方案更加有效,对称依赖关系的描述又进一步确保了算法结果的准确性。形式化定义了SDCP-nets的结构、语义和一致性,给出了关于SDCP-nets的择优选择算法和最佳方案选择算法。实验结果表明,利用SDCP-nets来描述用户的偏好语言具有较高的准确度。

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

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

基于Dandelion编码生成有界树宽CP-nets

针对条件偏好网络(CP-nets)图模型在进行推理运算时的高时间复杂度的问题,提出了一种基于Dandelion编码生成有界树宽的CP-nets(BTW-CP-nets Gen)算法。首先,通过Dandelion编码与树宽为k的树结构(ktree)之间的双向映射原理推导出Dandelion编码与k-tree之间的解码与编码算法,实现编码与树结构的一对一映射;其次,利用k-tree来约束CP-nets结构的树宽,并利用k-tree的特征树得到了CP-nets的有向无环图结构;最后,利用离散多值函数的双射计算出各CP-nets结构节点的条件偏好表,然后针对生成的有界树宽CP-nets进行占优查询检测。理论分析和实验数据表明,与Pruffer编码生成k-tree(Pruffer code)算法相比,BTW-CP-nets Gen算法的运行时间在生成简单结构和复杂结构时的下降幅度分别为21.1%和30.5%;而BTW-CP-nets Gen算法所生成的图模型在进行占优查询时的节点遍历比在简单结构和复杂结构上分别提高了18.48%和29.03%。BTW-CP-nets Gen算法在更短的时间内,占优查询时遍历的节点率更高。可见,BTW-CP-nets Gen算法在图模型的推理中能够有效提高算法效率。

CP-nets的代数表示及其模型求取算法

条件偏好网(CP-nets)是一种表示定性条件偏好关系的语言.针对目前CP-nets的图形表示方法难以实现运算的特点提出一种二值无环CP-nets的代数表示方法.该方法将CP-nets组织成邻接链表的形式,纵向存储CP-nets拓扑排序的序列,其结点域以命题逻辑的主析取范式来表示二值CP-nets的条件偏好表.横向存储各个顶点的父亲集,它对应决策属性的条件集.随后基于CP-nets的代数表示方法,研究二值无环CP-nets上的直接模型和间接模型的求取算法.实验结果表明,CP-nets不仅能用直观的图形来表示,也可用紧凑的代数方法来表示.

从偏好数据库中挖掘Ceteris Paribus偏好

针对传统的推荐系统需要用户给出明确的偏好矩阵(U-I矩阵),进而使用自动化技术来获取用户偏好的问题,提出了一种从偏好数据库中挖掘出Agent的偏好信息的方法。从知识发现的角度,通过Ceteris Paribus规则(CP规则),提出了k阶偏好挖掘算法(kPreM)。在算法中,利用k阶CP规则对偏好数据库中的信息进行剪枝处理,减少了数据库扫描次数,从而提高了偏好信息的挖掘效率。随后以一种通用的图模型——条件偏好网(CP-nets)为工具,揭示了用户的偏好可近似表达为CP-nets的定性条件偏好网。实验结果表明,用户的偏好都是带有条件的偏好。另外,通过挖掘得出的CP-nets偏好模型,为设计个性化的推荐系统提供了理论基础。

基于可能性条件偏好网络的交互式遗传算法及其应用

根据用户实施的人机交互行为而隐式地获取用户偏好的交互式进化优化算法,可有效减轻用户疲劳,提高个性化搜索或推荐的效率.但是,已有研究没有考虑用户交互行为和偏好的不确定性,影响了对用户偏好的拟合精度以及基于该偏好表达的进化搜索.针对该问题,提出基于可能性条件偏好网络的交互式遗传算法,以刻画用户交互行为和偏好的不确定性,并提高算法的搜索性能.首先,采用交互时间表示交互行为,考虑交互行为的不确定性,给出交互时间可信度的定义,并基于该定义给出了用户不确定偏好的表达函数;其次,利用可信交互时间和偏好函数,定义了用户对评价对象的偏好权重,并利用该权重,设计(更新)可以定量表示用户不确定偏好的可能性条件偏好网络,以更好地拟合用户偏好;然后,结合评价不确定性和可能性条件偏好网络,提出了改进的个体适应值估计策略,以更好地引导搜索;最后,将所提算法应用于图书个性化搜索中,结果表明了算法搜索的可靠性和高效性.

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

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

个人空间中结合人员偏好的空调自学习控制方法

室内环境影响着人们的身心健康和工作效率,而热舒适度是影响室内环境质量的最重要因素,但个体间热舒适存在很大差异,有明显的人员偏好。随着智能时代的到来,人们对空调的个性化和智能化需求也不断增长。因此本文设计并实现了一种适用于个人空间的结合人员偏好的空调自学习控制方法,基于人员历史空调使用行为对人员偏好分类,基于朴素贝叶斯分类器和神经网络模型的人员偏好预测模型来刻画和学习人员的温度偏好和降温/升温速率偏好,将人员偏好分类和预测模型集成到空调控制系统中,结合多阶跃输入的空调控制方法,提供不同人员所需的室内环境条件。在实际运行中,随着人员空调使用行为反馈和模型更新,将持续优化学习结果并且实现更优的控制效果。同时,该方法在现有空调系统的基础上无需增加额外的传感器,利于推广和应用。通过模拟和实验的方式验证了结合人员偏好的空调自学习控制方法的有效性和准确性;通过能耗模拟验证了结合人员偏好的空调自学习控制方法在提高人员舒适度的前提下不会增加许多能耗,甚至可以节省能耗。研究表明,结合人员偏好的空调自学习控制方法能够准确预测人员偏好,提供个性化舒适的室内环境,且具有一定的节能潜力。