第3章确定性推理方法.

人工智能原理及应用第3章确定性推理方法PrinciplesandApplicationsofArtificialIntelligence知识表示：将知识以某种模式存储到计算机中。智能：知识能力+思维能力（运用知识求解问题）推理：计算机的逻辑思维第3章确定性推理方法3.1推理的基本概念3.2自然演绎推理3.3谓词公式转换为子句集3.4消解原理3.5归结反演3.1推理的基本概念推理已知事实（证据）已有知识新的事实（结论）3.1推理的基本概念推理方式演绎推理(deductivereasoning)由一般到个别大前提:BC小前提:AB三段论:AC3.1推理的基本概念推理方式演绎推理(deductivereasoning)由一般到个别大前提:计算机学院的学生都会编程序小前提:李强是一名计算机学院的学生结论:李强会编程序3.1推理的基本概念推理方式演绎推理(deductivereasoning)归纳推理(inductivereasoning)由个别到一般A的所有实例具有X属性(完全归纳)结论:A具有X属性3.1推理的基本概念推理方式演绎推理(deductivereasoning)归纳推理(inductivereasoning)由个别到一般检查某厂的所有产品均合格(完全归纳)结论:该厂的产品合格3.1推理的基本概念推理方式演绎推理(deductivereasoning)归纳推理(inductivereasoning)由个别到一般A的部分实例具有X属性(部分归纳)结论:A具有X属性3.1推理的基本概念推理方式演绎推理(deductivereasoning)归纳推理(inductivereasoning)由个别到一般抽查某厂的一部分产品合格(部分归纳)结论:该厂的产品合格3.1推理的基本概念推理方式演绎推理(deductivereasoning)归纳推理(inductivereasoning)由个别到一般A具有X属性B与A类似(类比归纳)结论:B具有X属性3.1推理的基本概念推理方式演绎推理(deductivereasoning)归纳推理(inductivereasoning)由个别到一般软件工程专业的学生都会编程序计算机科学与技术与软件工程专业方向类似(类比归纳)结论:计算机科学与技术专业的学生都会编程序3.1推理的基本概念推理方式演绎推理(deductivereasoning)归纳推理(inductivereasoning)缺省推理(defaultreasoning)知识不完全的情况下的推理AB没有证据证明A结论:B3.1推理的基本概念推理方式演绎推理(deductivereasoning)归纳推理(inductivereasoning)缺省推理(defaultreasoning)知识不完全的情况下的推理未满18岁不能进入营业性网吧不知道学生李强的真实年龄李强不能进入营业性网吧3.1推理的基本概念推理方式确定性推理:证据和知识都是确定的——结论也是确定的不确定性推理:证据和知识不都是确定——结论也是不确定的已知事实（证据）已有知识新的事实（结论）3.1推理的基本概念推理方式单调推理:从证据不断接近结论非单调推理:可能推翻已有的结论已知事实（证据）已有知识新的事实（结论）3.1推理的基本概念推理方式启发式推理:推理过程中运用了启发式知识非启发式推理已知事实（证据）已有知识新的事实（结论）3.1推理的基本概念推理的方向正向推理:从已知事实出发，逐步尝试推导出结论，或证明问题无解把初始证据放入DB形成可用知识集按照冲突消解策略从该知识集中选出一条知识进行推理把新事实放入DBDB中有解吗？KB中有可用知识吗？推出的是新事实吗？N可用知识集空吗？成功退出把用户补充的新事实加入到DB中用户可补充新事实吗？失败退出YNNYNYNYNNY3.1推理的基本概念推理系统的基本要素知识库数据库推理机3.1推理的基本概念正向推理事实:AB知识:ACDBEF目标:CFABABABCDEFCF目标匹配匹配F规则已知事实r1r23.1推理的基本概念正向推理事实:P(x,y)(Q(x)R(v,y))知识:P(u,v)(S(u)N(v))目标:S(x)N(y)Q(x)推理示例知识库平均绩点超过4.5分的学生，授予一等奖学金评为优秀研究生的学生，平均绩点不能少于4分事实10名学生中，3人绩点超过4.5，其余绩点均低于4目标结论评为优秀研究生的学生都获得了一等奖学金获得了一等奖学金的学生都被评为优秀研究生推理示例g(x)4.5g(x)4g(x)4.5∨g(x)4g(x)4.5A(x)g(x)4E(x)A(x)E(x)E(x)A(x)推理示例如何对事实进行合理的归纳？如何选择事实的推理顺序？3.1推理的基本概念推理的方向正向推理:从已知事实出发，逐步尝试推导出结论，或证明问题无解逆向推理:从假设目标出发，逐步尝试找出其证据，或证明问题无解初始化DB和假设集将KB中所有能导出此假设的知识构成一个可用知识集按照冲突消解策略从该知识集中选出一条知识进行推理将该知识前提中的每个子条件作为新的假设加入假设集该假设是DB中的事实吗？该假设能被DB中的知识导出吗？N可用知识集空吗？成功退出该假设成立询问用户有此事实吗？失败退出YNYNNN从假设集中取出一个假设还有新的假设吗？该假设成立并放入DBYYY推理示例知识库4个嫌疑犯中有一个是小偷，且4人中只有一个说假话事实A说“我不是小偷”B说“C是小偷”C说“D是小偷”D说“C说谎”问题：请问谁是小偷？推理示例如何选择假设的验证顺序？3.1推理的基本概念推理的方向正向推理:从已知事实出发，逐步尝试推导出结论，或证明问题无解逆向推理:从假设目标出发，逐步尝试找出其证据，或证明问题无解混合推理推理起始以正向推理结果为假设输入进行反向推理需要进行反向推理吗？需要进行正向推理吗？输出结果成功退出NNYY进行正向推理Y3.1推理的基本概念冲突：已知事实可与知识库中的多条知识匹配冲突消解按针对性排序按事实新鲜性排序按匹配度排序按条件个数排序3.2自然演绎推理命题公式及其等价式（1）双重否定律：（2）交换律：（3）结合律：（4）分配律：（5）摩根定律：PP~~)()(),()(PQQPPQQP)()(RQPRQP)()(RQPRQP)()()(RPQPRQP)()()(RPQPRQP~(P∨Q)~P∧~Q~(P∧Q)~P∨~Q3.2自然演绎推理命题公式及其等价式（6）吸收律：（7）补余律:（8）连词化归律:（9）量词转换律:（10）量词分配律:PQPP)(PQPP)(FPPTPP,QPQP~)()(PQQPQP))(~(P~Pxx）（))(~()(~PxPxQxPxQPx)()())((QxPxQPx)()())((P-Q)(P∧Q)∨(~Q∧~P)3.2自然演绎推理永真蕴含式（1）化简式：（2）附加式：（3）析取三段论：（4）假言推理：（5）拒取式：QQPPQP,QPQQPP,QQPP,~QQPP,PQPQ,~3.2自然演绎推理永真蕴含式（6）假言三段论：（7）二难推理：（8）全称固化：其中，y是个体域中的任一个体，依此可消去谓词公式中的全称量词。（9）存在固化：其中，y是个体域中某一个可以使P(y)为真的个体，依此可消去谓词公式中的存在量词。RPRQQP,RRQRPQP,,),()()(yPxPx,)()()(yPxPx3.3谓词公式转换为子句集文字:原子公式或其否定子句:文字的析取式谓词:子句的合取式3.3谓词公式转换为子句集文字:原子公式或其否定子句:文字的析取式谓词:子句的合取式1)消去连接词“→”和“↔”2)把否定符号“～”移到每个谓词符号的前面3)变量标准化（使不同量词约束的变量有不同的名字）4)引入Skolem函数消去存在量词5)化为前束形（使所有全称量词在公式最前面）6)化为Skolem标准形（子句的合取式）7)略去全称量词8)断开合取式得到子句集9)变量名标准化3.3谓词公式转换为子句集)]()()[()]}(),()[()](~)(){[~(xBxPxxQyxSyxQxPx)]()()[()]}(),()[()](~)([~){~(xBxPxxQyxSyxQxPx)]()()[()]}(),()[()]()(){[(xBxPxxQyxSyxQxPx)]()()[()]}(),()[()]()(){[(wBwPwxQyxSyxQxPx)]()()[()]}())(,([)]()(){[(wBwPwxQxfxSxQxPx)]()([)]}())(,([)]()(){[)((wBwPxQxfxSxQxPwx)]()([)())](,()(){[)((wBwPxQxfxSxPwx)]()([)())](,()([wBwPxQxfxSxP))](,()([xfxSxP)(xQ)]()([wBwP))](,()([xfxSxP()Qy)]()([wBwP3.4消解原理消解原理(RobinsonTheorem)命题逻辑中的归结原理:如果C1和C2为真，则C12为真推论1:C1,C2S,则S{C1|C12,C2|C12}不可满足S不可满足推论2:C1,C2S,则S{C12}不可满足S不可满足C1:PQC2:PRC12:QR3.4消解原理消解原理(RobinsonTheorem)谓词逻辑中的归结原理:如果C1和C2为真，则C12为真推论1:C1,C2S,则S{C1|C12,C2|C12}不可满足S不可满足推论2:C1,C2S,则S{C12}不可满足S不可满足C1:P(x)Q(x)C2:P(a)R(y)C12:Q(a)R(y)3.5归结反演归结反演(1)将已知前提表示为谓词F(2)将待证明结果表示为谓词Q(3)将谓词公式FQ化为子句集S(4)应用归结原理对S中的子句进行归结，直至出现空子句，则证明Q为真推理示例知识库天使只说真话不说假话魔鬼只说假话不说真话凡人有时候说真话有时候说假话事实A,B,C三人分别是天使、魔鬼和凡人A说“我不是天使”。B说“我不是魔鬼”。C说“我不是凡人”问题：请问谁是天使，谁是魔鬼，谁是凡人？3.5归结反演归结反演:可能产生大量不必要的归结式控制策略删除无用子句限制子句的归结范围案例研究:故障推理(USB驱动安装错误)∨(USB口损坏)(USB口无法使用)(设置了静音)∨(音频设备错误)(没有声音)(音频设备被禁用)∨(声卡驱动安装错误)∨(病毒程序破坏了音频服务)∨(声卡硬件损坏)∨(扬声器硬件损坏)(音频设备错误)人工智能推理领域学术刊物重要国际期刊InternationalJournalofApproximateReasoning,Elsevier()IF:1.729JournalofAutomatedReasoning,Springer(link.springer.com/journal/10817)IF:0.567人工智能推理领域学术刊物重要国际会议InternationalJointConferenceonAutomatedReasoning(IJCAR),