您好、欢迎来到现金彩票网!
当前位置:如意彩票 > 非单调推理 >

高级人工智能-确定性推理

发布时间:2019-06-06 10:35 来源:未知 编辑:admin

  人工智能2016年秋季 罗平 罗平.cn 一般到个别的推理方法:从已知的一般性知识出发,去推出蕴含在这些已知知识中的适合于某种个别情况的结论 结论:由大前提推出的,并且适合于小前提的判断。例如,有如下三个判断: 计算机系的学生都会编程序;(一般性知识) 程强是计算机系的一位学生;(具体情况) 程强会编程序。(结论) 结论 结论是蕴含在大前提中 是蕴含在大前提中的的 完全归纳推理:是指在进行归纳时需要考察相应事物的全部对象,并根据这些对象是否都具有某种属性,推出该类事物是否具有此属性。 不完全归纳推理:是指在进行归纳时只考察了相应事物的部分对象,就得出了关于该事物的结论。例如,随机抽查。 枚举归纳推理:是指在进行归纳时,如果已知某类事物的有限可数个具体事物都具有某种属性,则可推出该类事物都具有此种属性。 例如,设有如下事例: 王强是计算机系学生,他会编程序; 高华是计算机系学生,她会编程序; 当这些具体事例足够多时,就可归纳出一个一般性的知识:凡是计算机系的学生,就一定会编程序。 类比归纳推理:是在两个或两类事物有许多属性都相同或相似的基础上,推出它们在其他属性上也相同或相似的一种归纳推理 设A、B分别是两类事物的集合: i=1,2,…..则当A与B中有一新的元素对出现时,若已知a有属性P,b有属性Q,即 类比归纳推理的基础是相似原理,其可靠程度取决于两个或两类事物的相似程度以及这两个或两类事物的相同属性与推出的那个属性之间的相 关程度。 在已知领域内的一般性知识的前提下,通过演绎求解一个求解一个 具体问题 具体问题或者证明一个结论的正确性 证明一个结论的正确性 不能增殖新知识:所得出的结论蕴含在一般性知识的前提中,推理过程是将已有事实揭露出来 增殖新知识的过程:是由个别事物或现象推出一般性知识的过程。 按所用知识的确定性分类确定性推理vs. 不确定性推理 按推理过程的单调性分类单调推理vs. 非单调推理 单调:不会由于新知识的加入否定前面的结论(不能 取消原有的结论) 非单调:知识不完全情况下,某些新知识的加入会否定前面的结论 推理策略主要解决推理方向、冲突消解等问题,如推理方向控制策略、求解策略、限制策略、冲突消解策略等 推理方向控制策略:确定推理的控制方向,可分为正向推理、逆向推理、混合推理及双向推理。 冲突消解策略:当推理过程有多条知识可用时,如何从这多条可用知识中选出一条最佳知识用于推理的策略。 先正向后逆向:先进行正向推理,从已知事实出发推出部分结果,然后再用逆向推理对这些结果进行证实或提高它们的可信度。 先逆向后正向:先进行逆向推理,从假设目标出发推出一些中间假设,然后再用正向推理对这些中间假设进行证实。 双向混合:正向推理和逆向推理同时进行,使推理过程在中间的某一步结合起来。 命题逻辑vs.谓词逻辑 命题逻辑:命题符号P,Q代表一定的命题,看不出关系,表达不出共同特征 命题公式的一个解释就是对该谓词公式中各个命题变元的一次真值指派 设D是谓词公式P的非空个体域,若对P中的个体常量、函数和谓词按如下规定赋值: –为每个个体常量指派D中的一个元素; –对每一个变元,指派D的一个非空集合,这是该变元的变域(个 到{F,T}的映射。则称这些指派为P在D上的一个解释I 解释,并指出在每一种解释下公式A的真值。解:由于公式A中没有包含个体常量和函数,故可直接为谓词指 派真值,设有 把P理解为一个元素为二元组的集合 P={(1,1),(2,1)} P(1,1)P(1,2) P(2,1) P(2,2) 解释,并指出在每一种解释下公式A的真值。解:由于公式A中没有包含个体常量和函数,故可直接为谓词指 派真值,设有 这就是公式A 即对x在D上的任意取值,都存在y=1使P(x,y)的真值为T。因此,在此解释下公式A的线)}说明:一个谓词公式在其个体域上的解释不是唯一的。例如, 对公式A,若给出另一组真值指派 这也是公式A 即对x在D上的任意取值,不存在一个y使得P(x,y)的真值为T。因此,在此解释下公式A的线) 设个体域D={1,2},给出公式B=(x)P(f(x), a)在D上的解释,并指出 在该解释下公式B的真值。 解:设对个体常量a和函数f(x)的值指派为: 对谓词的真值指派为: 根据此解释下有 即对x在D上的任意取值,都存在a=1使P(f(x),a)的真值为T。因此,在此 解释下公式B的真值为T。 可以看出,谓词公式的真值都是针对某一个解释而言的,它可能在某一 个解释下真值为T,而在另一个解释下为F。 P(1,1))P(1,2) P(2,1) P(2,2) 判定一谓词公式为判定一谓词公式为永真,必须对每个非空个体域上的每个解释逐 永真,必须对每个非空个体域上的每个解释逐 一进行 一进行判断 判断 可满足性(相容性):对于谓词公式P,如果至少存在D上的一个解释,使公式P在此解释下的真值为T,则称公式P在D上 是可满足的。 永假性(不可满足性):如果谓词公式P对非空个体域D上的任一解释都取真值F,则称P在D上是永假的;如果P在任何非 空个体域上均是永假的,则称P永假。 谓词公式的等价性:设P与Q是D上的两个谓词公式,若对D上的任意解释,P与Q都有 相同的真值,则称P与Q在D 上是等价的。 如果D是任意非空个体域,则称P与Q是等价的,记作PQ。 (10)量词分配律 常用常用的永真蕴含式如下: 的永真蕴含式如下: 全称固化全称固化 其中,其中,yy是个体域中的任一个体,依此可消去谓词公式中的全称量词。 是个体域中的任一个体,依此可消去谓词公式中的全称量词。 等价式和永真蕴含式也称推理规则范式是谓词公式的标准形式。在谓词逻辑中,范式分为两种: 任一谓词公式均可化为与其对应的Skolem范式设F为一谓词公式,如果其中的所有量词均非否定地出现在公式的最前面,且它 们的辖域为整个公式,则称F为前束范式。一般形式: )为母式,它是一个不含任何量词的谓词公式。如果前束范式中不包含存在量词且母式M是“合取范式”,则称这种形式的谓词 公式为Skolem范式。 置换可简单的理解为是在一个谓词公式中用置换项去替换用置换项去替换变量 变量 置换是形如 x与y之间出现了循环置换现象。即当用g(y)置换x,用f(g(y))置换y时,既没有消去x,也没有消去y 置换y,则消去了x和y 通常,置换是用希腊字母θ、σ、 }是一个置换,F是一个谓词公式,把公式F中出现的所有x (i=1,2,…,n),得到一个新的公式G,称G为F在置换θ下的例示,记作G=Fθ。 一个谓词公式的任何例示都是该公式的逻辑结论 合一:寻找项对变量的置换,使两个谓词公式一致 例如,设有公式集F={P(x,y,f(y)), 是它的一个合一。一个公式集的合一不是唯一的,但最一般合一是唯一的。 设有公式集F={F 是可合一的设σ是公式集F的一个合一,如果对F的任一个合一θ都存 在一个置换λ,使得θ=σλ,则称σ是一个最一般合一 如何高效实现合一算法呢?提示:由于谓词、函数等只是符号,合一过程中没有使 用其语义信息,仅仅使用其语法信息,因此,将其转换 成list的表示形式 合一的算法可以通过递归实现 自然演绎推理:从一组已知为真的事实出发,直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。 假言推理因此,Q为真 在人工智能中,很多问题都可以转化为一个定理证明问题,即对前提P和结论Q,证明PQ永线:证明PQ在任何一个非空的个体域上都永真(非常困难,甚至不 可实现)的 途径2:反证法.把关于永真性的证明转化为关于不可满足性的证明。即: 证明(PQ) 鲁宾逊于1965年在海伯伦(Herbrand)理论的基础上提出的基于逻辑的“反证法” 归结演绎推理是一种基于鲁宾逊(Robinson)归结原理的机器推理技术。 John Alan Robinson machine-orientedlogic based resolutionprinciple. Journal ACM,1965, 12(1):23-41 任何一个谓词公式都可以通过应用等价关系及推理规则化成相应的子句集。 消去连接词“”和“”反复使用等价 等价公式: 公式: 减少否定符号的辖域反复使用 双重否定双重否定律: 摩根摩根定律: 定律: ((PPQ) 量词转换量词转换律: 将每个否定符号“”移到紧靠谓词的位置,使得每个否定符号最多只作用于一个谓词上。 例如:(x)((y)P(x,y)(y)(Q(x,y)R(x,y)))经等价变换后为 对变元标准化在一个量词的辖域内,把谓词公式中受该量词约束的变元全部用另外 受该量词约束的变元全部用另外 一个没有出现过的任意变元代替 一个没有出现过的任意变元代替,使不同量词约束的变元有不同的名 把把所有量词都移到公式的左边,并且在移动时所有量词都移到公式的左边,并且在移动时不能改变其相对顺序。。 移动的可行性:由于变元已被标准化,每个量词都有自己的变元,消除了任何由变元引起冲突的可能。 存在量词不出现在全称量词的辖域内(即它的左边没有全称量词):只要用一个新的个体常量替换受该存在量词约束的 新的个体常量替换受该存在量词约束的 则需要用用SkolemSkolem函数 函数f(x 11,,xx xxnn ))替换受该存在量词约束的 替换受该存在量词约束的 y,然后再消去该存在量词例如,(x)(y) 化为Skolem标准形Skolem标准形: 把谓词公式化为把谓词公式化为Skolem Skolem标准形需要使用以下等价关系 标准形需要使用以下等价关系 化为Skolem标准形后为 由于母式中的全部变元均受全称量词的约束母式中的全部变元均受全称量词的约束,并且全称量词的次次 序已无关紧要 序已无关紧要,因此可以省掉全称量词 可以省掉全称量词。 消去全称量词后为(P(x,f(x))Q(x,g(x)) 母式:子句的合取式母式:子句的合取式 在母式中消去所有合取词母式中消去所有合取词,把母式用子句集的形式表示出来 更换变量名称对子句集中的某些变量重新命名,使任意两个子句中不 对子句集中的某些变量重新命名,使任意两个子句中不 出现相同的变量名。 出现相同的变量名。 例如,对前面的公式,可把第二个子句集中的变元名x更换为y, 得到如下子句集 前束范式Skolem标准化去掉所有的存在量词 Skolem标准化后去掉全称量词 转换成析取式的合取每个合取式为一个分离的子句 9a: 把分离的变元归一化10a: 由于在消去存在量词时所用的Skolem函数可以不同,因此化简后的标准子句集是不唯一的。 Skolem化后得到的公式与原公式不等价,但具有相同的不可满足性 定理 设有谓词公式F,其标准子句集为S,则F为不可 满足的充要条件是S为不可满足的。 --基本思想 子句子句集中的子句之间是合取 集中的子句之间是合取关系 关系: 子句集中只要有一个子句为 不可满足,则整个子句集就是不可满足的; 空子句是不可满足空子句是不可满足的的: 一个子句集中如果包含有空子句,则此子句集就一定是不可满足的。 首先把欲证明问题的结论否定,并加入子句集,得到一个扩充的子句集S。 然后设法检验子句集S是否含有空子句,若含有空子句,则表明S是不可满足的; 若不含有空子句,则继续使用归结法,在子句集中选择合适的子句进行归结,直至导出空子句或不能继续归结为止。 --命题逻辑的归结 互补文字互补文字: 中余下的部分按析取关系构成一个新的子句C12 ,则称这一过程 为归结,称C 12 12的亲本子句 亲本子句。 的归结式C12 的归结式C12 的归结式C123 然后再对C12 123=NIL 归结过程不唯一:如果改变归结 顺序,同样可以得到相同的结果 NIL--命题逻辑的归结 证明:设C ’关于解释I为线 ’关于解释I也为真因为,对于解释I,L和L中必有一个为假 为假,这将与前提假设C 因此,必有C12 关于解释I也为线 的逻辑结论。--命题逻辑的归结 定理:归结式C 12 是其亲本子句C 的逻辑结论证明:设S={ 的归结式,则用C12 的任一解释I,都可能有以下两种情况:解释I使C 12 中必有一个为假,即S是不可满足的。解释I使C 12 12为真,根据上述定理有(C 为假。即S也是不可满足的。因此可以得出 的不可满足性S的不可满足性--命题逻辑的归结 推论1:设C 是子句集S中的两个子句,C12 结式,若用C12 代替C 可满足性可以推出原子句集S的不可满足性。即:SS 11 的不可满足性 的不可满足性SS的不可满足性 的不可满足性 先证明 中必有一子句为假,因而S }必为不可满足。再证明 的任一解释I,都可能有以下两种情况:解释I使C 12 中必有一个为假,即S是不可满足的。解释I使C 12 12为线有(C 为假。即S也是不可满足的。由此可见S与S 的不可满足性--命题逻辑的归结 推论2:设C 是子句集S中的两个子句,C12 结式,若把C12 加入S中得到新的子句集S 为证明子句集S的不可满足性,只要对其中可进行归结的子句进行归结,并把归结式加入到子句集S中,或者用归结式 代替他的亲本子句,然后对新的子句集证明其不可满足性即 如果经归结能得到空子句,根据空子句的不可满足性,即可得到原子句集S是不可满足的结论。 在命题逻辑中,对不可满足的子句集S,归结原理是完备完备的。 --命题逻辑的归结 定理 子句集S是不可满足的,当且仅当存在一个从S到空 子句的归结过程。 例设已知的公式集为{P, T},求证结论R。解:假设结论R为假, 将R加入公式集,并化 为子句集 其归结过程如右图的归结演绎树所示。该树根为空子句。 其含义为:先假设子句集S中的所有子句均为真, 即原公式集为真,R也为真;然后利用归结原 理,对子句集进行归结,并把所得的归结式并 入子句集中;重复这一过程,最后归结出了空 子句。 NIL--命题逻辑的归结 在谓词逻辑中,由于子句集中的谓词一般都含有变元,因此不能象命题逻辑那样直接消去互补文字。而需要先用一个最最 一般合一 一般合一对变元进行代换,然后才能进行归结。 谓词逻辑中的归结式:—谓词逻辑的归结 12解:由于C 有相同的变元x,不符合定义3.20的要求。为了进行归结,需要修改C 的最一般合一是σ={b/x}。则有 作用,可以得到两个互补对。注意:求归结式不能同时消去两个互补对,这样的结果不是二 元归结式。如在σ={a/x, b/y}下,若同时消去两个互补对,所得的 R(z)不是C 的二元归结式。--谓词逻辑的归结 12解:对参加归结的某个子句,若其内部有可合一的文字,则在 进行归结之前应先对这些文字进行合一。 中有可合一的文字P(x)与P(f(a)),用它们的最一般合一σ={f(a)/x}进行代换,可得到C 的最一般合一是σ={f(a)/y},则可得到C 若子句C中有两个或两个以上的文字具有最一般合一σ,则称Cσ为子句C的因子。如果Cσ是一个单文字,则称它为C的单元因子。 --谓词逻辑的归结 定义 的二元归结式。这四种二元归结式都是子句C 的二元归结式,记为C12 --谓词逻辑的归结例3.15设C 归结(σ={g(a)/x}),可得到C 对谓词逻辑,归结式C12 是其亲本子句C 的逻辑结论。用归结式取代它在子句集S中的亲本子句,所得到的子句集仍然保持着原子句集S的不可满足性。 对谓词逻辑,从不可满足的意义上说,一阶谓词逻辑的归结原理也是完备的--谓词逻辑的归结 归结演绎推理实际上就是从子句集中不断寻找可进行归结的子句对,并通过对这些子句对的归结,最终得 出一个空子句的过程。 由于事先并不知道哪些子句对可进行归结,更不知道通过对哪些子句对的归结能尽快得到空子句,因此就 需要对子句集中的所有子句逐对进行比较,直到得出 空子句为止。 盲目的全面进行归结的方法,不仅会产生许多无用的归结式,更严重的是会产生组合爆炸问题。 中的全部子句作所有可能的归结,得到第一层归结式,把这些归结式的集合记为S 中的子句进行所有可能的归结,得到第二层归结式,把这些归结式的集合记为S 中的子句进行所有可能的归结,得到第三层归结式,把这些归结式的集合记为S 如此继续,直到得出空子句或不能再继续归结为止。例设有如下子句集:S={I(x)R(x), 用广度优先策略证明S为不可满足。广度优先策略的归结树如下: NILS0 S1 S2 广度优先对大问题的归结容易产生组合爆炸,但对小问题却仍是一种比较好的归结策略。 限制策略是通过对参加归结的子句进行某些限制,来减少归结的盲目性,以尽快得到空子句。 support):每一次参加归结的两个亲本子句中,至少应该有一个是由目标 公式的否定所得到的子句或它们的后裔。 支持集策略是完备的,即当子句集为不可满足时,则由支持集策略一定能够归结出一个空子句。 也可以把支持集策略看成是在广度优先策略中引入了某种限制条件,这种限制条件代表一种启发信息,因而有较高的效 NIL目标公式的否定 支持集策略限制了子句集元素的剧增,但会增加空子句所在的深度。 支持集策略具有逆向推理的含义,由于进行归结的亲本子句中至少有一个与目标子句有关,因此推理过程 可以看作是沿目标、子目标的方向前进的。 删除法主要想法是:把子句集中无用的子句删除掉,这就会缩小搜索范围,减少比较次数,从而提高归结效率。 如果某文字L在子句集中不存在可与其互补的文字L,则称该文字为纯文字。 在归结过程中,纯文字不可能被消除,用包含纯文字的子句进行归结也不可能得到空子句 对子句集而言,删除包含纯文字的子句,是不影响其不可满足性的。例如,对子句集 其中P是纯文字,因此可以将子句PQR从子句集S中删除。 如果一个子句中包含有互补的文字对,则称该子句为重言式。 例如P(x)P(x), 重言式是真值为真的子句。对一个子句集来说,不管是增加还是删除一个真值为真的子句,都不会影 响该子句集的不可满足性。因此,可从子句集中删 去重言式。 如果一个子句只包含一个文字,则称此子句为单文字子句。单文字子句策略是对支持集策略的进一步改进,它 要求每次参加归结的两个亲本子句中至少有一个子句是 单文字子句。 采用单文字子句策略,归结式包含的文字数将少于其非单文字亲本子句中的文字数,这将有利于向空子句的方 向发展,因此会有较高的归结效率。 例3.21 设有如下子句集: 是不完备的,即当子句集为不可满足时,用这种策略不一定能归结出空子句。 原因:没有可用的单文字字句例如:已知:AB, B,求证:AB化为字句集后为:AB, B,AB,不存在单文字的字句。但是可以消解出空。 线性输入策略(LinearInput) 要求每次参加归结的两个 亲本子句中,至少应该有一个是初始子句集中的子句。 初始子句集是指开始归结时所使用的子句集。 例设有如下子句集: 缺点:不完备例:设有子句集 祖先过滤策略(AncestryFiltering):满足以下两个条件中的任 意一个就可进行归结: 如果两个亲本子句都不是初始子句集中的子句,则一个子句应该是另一个子句的先辈子句。 NIL例:设有如下子句集:

http://mj-sports.net/feidandiaotuili/287.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有