PDF《知识表示》

知识表示 从逻辑表示到知识表示 高阳http://cs.

nju.edu.cn/gaoy, 2016.9.21 一个例子 类层次是一种知识 那么类层次的通用机制? 如何定义类? 如何定义异常?如何进行推理?如何表示时间?如 何表示因果?如何表示不确定性? 基本概念 数据 信息的载体和表示 信息 数据的语义 知识 信息关联后所形成的信息结构:事实 &

规则 知识是智能的基础 获得知识,运用知识 知识表示 用来让计算机可以存储和处理知识的模式 不同于逻辑表示,知识表示有更多显式结构上的约束 知识特性 相对正确性 一定条件下/某种环境中 不确定性 中间状态/为真程度/随机性/模 糊性/经验性/不完全性 可表示/可利用性 语言/文字/图像/视频/图形/音频/神经网络/概率图 知识的分类 范围 常识性知识/领域性知识 作用 事实性知识/过程性知识/控制知识 确定 确定性知识/不确定性知识 表现 逻辑性知识/形象性知识 抽象 零级知识/一级知识/二级知识 常见的知识表示方法 一阶谓词表示 (First Order Predicate) 产生式表示 (Production) 语义网络表示 (Semantic Network) 框架表示 (Framework) 脚本表示 (Script) 选择合适的表示方法 ? 充分表示领域知识 ? 有利于对知识的利用 ? 便于理解和实现 ? 便于对知识的组织、管理和维护 一阶谓词表示 一阶谓词知识表示 谓词公式表示知识的步骤 (1)定义谓词及变元;

(2)变元赋值;

(3)连接词连接谓词,形成谓词公式. 谓词逻辑的推理规则 取式假言推理;

拒式假言推理;

P规则(在推理的任何步,引入前提);

T规则(在推理的任何步,引入永真蕴涵的公式);

CP规则(对任意引入的命题R和前提集合能推出S,则前提集合能推出S);

反证等. 机器人搬盒子 一室内,机器人在c处,a和b处各有一张桌子(a桌和b桌). a桌上有一 个盒子.要求机器人从c处出发,将盒子从a桌上拿到b桌上,然后回到c 处.请用谓词逻辑来表示机器人的行动过程. 定义两类谓词:状态、操作. 状态: Table(x): x是桌子 Empty(y): y手中是空的 At(y,z): y在z处Holds(y,w): y手中拿着w On(w,x): w在x上面 操作: Goto(x,y): 机器人从x处走到 y处Pickup(x): 在x处拿起盒子 Setdown(x): 在x处放下盒子 机器人搬盒子 初始状态: Table(a) Table(b) Empty(robot) At(robot,c) On(box,a) 目标状态: Table(a) Table(b) Empty(robot) At(robot,c) On(box,b) 机器人搬盒子 状态谓词合法性和导致的状态变化 Goto(x,y): 条件:At(robot,x) 状态变化:删除公式At(robot,x),添加公式At(robot,y) Pickup(x): 条件: Table(x),Empty(robot),At(robot,x),On(box,x) 状态变化:删除公式Empty(robot), On(box,x) ,添加公式Holds(robot,box) Setdown(x): 条件: Table(x), At(robot,x), Holds(robot,box) 状态变化:删除公式Holds(robot,box) ,添加公式Empty(robot), On(box,x) 最后采用合一和搜索完成规划求解 野人和修道士过河 野人(Missionaries)和修道士(Cannibals)(MC问题): 设在河的一岸有三个野人、三个修道士和一条船,修道士想用这条船把所有的人运 到河对岸,但受以下条件的约束: ? 修道士和野人都会划船,但每次船上至多可载两个人;

? 在河的任一岸,如果野人数目超过修道士数,修道士会被野人吃掉. 如果野人会服从任何一次过河安排,请规划一个确保修道士和野人都能过河,且没 有修道士被野人吃掉的安全过河计划. 状态谓词:? 操作谓词:? 规划:初始状态、目标状态、规划的解?? 缺陷 谓词演算语义 对合适表达式保持真值运算 心理/认知科学家 获取和使用知识的方法 ?x human(x) ? mortal(x) ?x mortal(x) ? human(x) 丢失了类的继承、关联和因果! 小结:一阶谓词表示 知识的表示 一元谓词:对象(x);

二元谓词:对象-属性(x,y);

三元谓词:对象-属性-值(x,y,z);

关系-对象1-对象2 (x,y,z);

四元谓词:三元谓词+可信度 一阶谓词表示优缺点 优点:精确,自然,严密,易于实现 缺点:表示和处理分离,组合爆炸导致效率低 产生式表示 产生式表示法 产生式规则(production rules)基本形式 例:如果汽车不能发动,则检查电池 P?Q 或IF P THEN Q. 与蕴涵式的区别 一阶谓词中蕴含式表示的知识是精确的(真或假) 而产生式表示的知识可以是不精确的(可信度) 产生式的推理匹配过程也可以是部分匹配 1936,数学家Emil Post的产生式计算模型:1972年,Newell和Simon的基于规则认知模型. 常用结构 原因?结果:天下雨,地上湿 条件?结论:将冰加热到0度以上,冰会融化成水 前提?操作:如果能找到合适的杠杆和支点,则可以翘起地球 事实?进展:夜来风雨声,花落知多少 情况?行为:手机开机了,则意味着可以收到别人发给我的信 息了 产生式系统 产生式系统(production system): 一组产生式,互相配合/协调,其中一个产生式产生的结论可以 作为另一个产生式的事实使用,以求解问题. 数据库 产生式 规则库 推理/控 制系统 产生式系统:规则库 规则库: ? 有效表达领域内的过程性知识. ? 对知识进行合理的组织与管理,提高问题求解效率. 数据库 产生式 规则库 推理/控 制系统 产生式系统:数据库 数据库(工作内存): ? 存放问题求解过程中的各种信息的数据结构,包括初始 状态、原始证据、中间结论、最终结论. ? 其内容在推理过程中在动态、不断变化的. 数据库 产生式 规则库 推理/控 制系统 产生式系统:控制系统 控制系统: ? 从规则库中选择规则,并与数据库中的已知事实进行匹配. ? 发生冲突时调用相应策略进行消解. ? 如果执行规则的右部是一个或多个结论,则将结论加入到数据库中. ? 如果执行规则的右部是一个或多个的操作,则执行这些操作.并将操作产生的 事实加入到数据库中. ? 对不确定性的知识,也计算结论的不确定性. ? 在适当时候终止系统运行. 数据库 产生式 规则库 推理/控 制系统 汽车故障检测系统 包含以下产生式: ? R1:如果发动机不能转动,且电池有电,则检查启动器. ? R2:如果没有火花,则检查电极尖端. ? R3:如果发动机能转动,但车子不能启动,则检查火花塞. ? R4:如果发动机不能转动,则检查电池. ? R5:如果电池没电,则充电. 目前有一个简单的事实: 发动机不能转动 整除问题 包含以下产生式: ? R1:如果能被12整除,则能被6整除. ? R2:如果能被20整除,则能被10整除. ? R3:如果能被6整除,则能被2整除. ? R4:能被10整除,则能被5整除. 目前有一个简单的事实:N能被12整除,也能被20整除 目标:判断N能否被5整除? 数据驱动:正向推理 procedure generate;

begin identify the set S of applicable rules;

while S is non-empty do begin select a rule R from S;

apply R;

if the problem is solved by the application of R then indicate SUCCESS else call ′generate′ recursively remove R from S and undo the effect of applying R end end;

N能被12整除,也能被20整除 迭代次数1:匹配产生式,冲突集 合R1和R2,选择R1执行 迭代次数2:在工作内存中产生事 实 能被6整除 ,匹配产生 式,应用规则R3 迭代次数3:失败,回溯,将事实 能被6整除 从工作内存中 去除.应用规则R2…… 本质是深度搜索! 目标驱动:反向推理 function validate(X:expression): boolean;

var result:boolean: begin result:=false;

identify the set of applicable rules S which have X on the right-hand side;

While (result = false) and (S is non-empty) do begin select and remove a rule R from S;

C:=the condition part of R;

if C is true in the database then result:=true else if C is false in the database then do nothing else if validate (C) is true then result:=true end;

validate:=result end;

N能被5整除 迭代次数1:匹配产生式,选择R4执行 迭代次数2:匹配 能被10整除 ,应用规则R2 迭代次数3:在数据库中匹配 了R2的左部 能被20整除 本质也是深度搜索! 混合驱动和控制策略 procedure mixed-method;

begin repeat let user enter data into the database;

call procedure ′generate′ to generate new facts which are added to the database;

call ′select-hypothesis′ to select a goal statement E;

ca........