我们刚提的是 forward chaining,那当然我们 forward
就从 site 开始,就是以这个东西开始,位置一个一个找出来,当然我们同样可以反
向来操作,就是从我们想要找的目标然后反过来看,能不能导到这个目标。
那我们一样可以用类似 always 来写,但是我们现在换个说法来说, 就是我们用一个 and-or-graph
来讲哦,其实我们做,因为我们是一个 因为这些东西是 and
嘛,比如说 A and B 然后 我们现在 horn course 像这种东西,那其实相对应来说,就是你要得到
C 的话,那你需要一个 A 还有 B 你都必须要为 true,那你就画一个 and
这个符号大家应该还记得,我们在 non-classical search
那一讲又提到的 and-or-graph,所以你们我们把 KB 所有知道的东西全部画出来之后,如果全部画出来之后,我们就可以得到一个这样的
graph,我们要先给一个目标,然后之后从那个目标开始 backward 倒退回来。
那我们来看一下怎么做到。
好,那,这边我们用几个 sample 好吧,用红色的圆圈来当作
已知的,就是我们知道的 fact。像我们刚才 KB 里头我们知道 A 是 true B 是 true,然后我们把原文当作正要看的然后
整个实心的当作是已经 check 过的,那我们 先从 Q 开始 Q 就是我们现在正在看的东西,然后之后
Q 看过了, 我们要就把它涂实,然后之后我们要看的是 p,就是如果你要
我要导到 Q 为真的话,我的前提就是 P 必须要为真,好我们就这样 backward 这样导回去, 好,那接下来就是,接下来我
P 要为真的话,我必须就是 L 和 M,这是 M search 嘛,这是 and 好,那
A no 呢那我就 L 和 M 都必须要为真 好,那这时候呢,我们就在这时候,我们看一下,就是那
我 L 要为真的时候呢,我必须要做到的就是 A 为真而且
P 为真,就是我走着一条,L 有两种走法。
你 backward 的时候有走着一条和这一条,我们假设先从左边开始走,那这边是一个一样是 and。
好,A 和 P 必须要为真,可是这边产生一个 circle 嘛
circle 就是 我是从 P 开始的,那你又回到 P 要为真,所以这条路,我们遇到这边
遇到 circle 的时候就代表走不通,你不能 A,就是我要为真的时候,你要,然后你要,这条路代表你不
知道怎么怎么办,所以我们接下来就只好换着试走这一条,OK, 所以这一条是 fail 了,这一条 fail。
好,那接下来走右路,右路的时候你看这一边,就是 A、B,你会发现这两个我都知道。
这两个都是 true,所以你就可以得到就是 L 为真。
好,你就看这边,然后你就得到 L 为真,那这时候你就把 L 加在你的 已知的 fact 嘛,刚刚是有
A、B,所以我们现在用红圈来代表,就是已知的,然后接下来我们有一个正在 checking
的就是 M,对不对,我们刚也就 return 到这边,我们刚刚要 L、M 同时为真,那你再来看 M
的时候,M只有一条路,那这一样是 M search,所以你会需要这两个为真,那 这两个都已经是为真的,所以你就可以得到,
M 为真,然后接下来 return 回去,P 为真然后最后得到 Q 为真。
这就是一个 backward chaining,就是从后面用 tree search 的方式来 searh。
forward chaining 和 backward chaining 它的 complexity 呢,它的时间复杂度基本上都跟你的 knowledge base
的 size 成 linear 的关系,那有一些,因为它的本身特性不同,我们把 forward
chaining 又称为 data-driving,就是你有哪些资料,一开始你就一直 展下去。那
backward chaining 呢就是 goal-driven 你需要的一个目标,你从那边来开始导。
好,一般比较 general 而言,backward chaining 比较是人类在做 problem solving
的 事情,譬如说,我们在想说,我要是去哪里了或是我要怎么 pass 这一门课, 你可能是有目标,然后我再去找方法来做,那
forward chaining 比较不太 human 一点, 但是 forward chaining 有好有坏,它的好处是,它可以把所有
KB 能 entail 的东西全部都导出来,我们刚看过 iii 你就知道这种感觉。
KB entail
的是对的事情,它全部都会导出来,可是这个过程中呢,缺点就是你可能会导出很多没用的 conclusion, 你可能会跟你的目标毫无关系。
那一般而言,因为我的 backward chaining 是 goal-driving 我是
想要知道我要导什么,我再去做它的 influence,所以 in general
来说,backward chaining 的 速度会比 forward chaining 来得快一些。一般来说是这样的。
好,那我们再谈一下,我们这一讲,主要都在讲 propositional logic
我们再讲一下 propositional logic 的优缺点,当然好处其实蛮多的,第一个是像它是 declarative,也就是说
你只要把它宣告出来,那后面的 influence 可以蛮系统化了。
很多一些特性包含像它是 compositional,它是可以 组成的,就是它的语意基本上譬如说,B
1.1 P 1.2 这样的语意呢其实就是我不用额外再定义,我只要
我已知这个的 semantics 还有这个的 semantics 我就可以定义它的 semantics。
好,这个就是,在 1.1 我有感觉到 breeze 嘛,在 1.2 有
pit,你知道这两个语意的时候,你任何的 logic 任何的 and-or 组成,或是 indication 它的语意,自然而然的就被定出来了。
好,这是蛮好的一件事,那还有一个就是它的 意义呢,基本上就是所谓的我们叫
context independent 跟上下文无关, 就是跟上下文无关,那相对的有一种讲法,叫
context free 或 context indepentent,那像自然语言就不是了。
好,自然语言的话我们有很多,就有些讲话如果我们在讲双关语,将一些讽刺的话,那这- 个跟我们
就是你可能单看,就是有时候新闻媒体常做的事情是断章取义吗,你访问一个人,他讲一- 大堆话,
你就把他讲的某一段话,抽出来放在某些接在某些地方情况下,那我们会觉得他这句话,你就- 会觉得他是恶意的或是
它的代意义跟他原句,原文装是不太一样的,好,那在这 logic
里面是不会的,在 logic 它一句话就代表 只有它的意思跟上下文 independent。
那 propositional logic 当然有很多缺点,包含,像它的 expressive power 是不够的。
譬如说像我们刚刚在做 wumpus world 的时候,大家有看到,因为我们基本上有个 rule,就是说你只要站在
pit 的旁边,你就会感觉到 breeze, OK,那这句话你没办法在 propositional
logic 直接用一个 rule 定出来,我们要定得很累,就是你可能必须要 B
1.1 好然后它代表了 P 2.1 或 P 2.1,然后之后你还要再定一个
B 2.2,你又要再来,好,那这个东西,你对所有的 16 格,你可能都要
这样定,如果今天我的 wumpus 的世界在拓展,比如说,一百万乘一百万的格子, 你就等于说你要一百万乘一百万条
rule 来描述这件事,这是 propositional logic 做 不是很 express
的东西,那我们下一讲会讲到 first-order logic,这里面 introduce 一个 变数的概念,那就可以做到,因为我只要定义
B x.y,它就可以代表什么,可以代表 这边 introduce 变数,那我就可以用一条 rule 来描述我刚刚所讲的这句话。
好,以上我们总结一下我们这一讲的内容,基本上就是,我们使用了 逻辑式子
logic 来描述,然后我们所有的已知的东西,都会放在一个 knowledge base 里面。
好,那所有的这个 knowledge base 所表含的东西,所有它的 syntax 它的定义是有它
的语法和它语意所定出来的,那我们这边有讲到一个很重要的事情,大家记得一下,model 和
entailment 不管你用 syntax 来表示一件事情的时候,那它的 所以我们的
ground truth 就是你这个 knowledge base 所可以 entail 的任何东西,就是它的 ground truth。
好,那我们在 entail 上我们讲一些东西大家回想一下,那我们在讨论的时候,我们很在意的是 sound
还有 就是 sound 和 complete 这件事,在我们的任何 influence 来说就是已知的 导出来都是对的,对的你都能导出来,好,那在
propositional logic 里面,这样的 influence 是存在的,那 resolusion 就是其中一个,就是它记上的
又 complete,在你的 KB 表示成 conjunctive normal form 的情况下,那我们刚刚有讲过,任何一个逻辑
propositional logic 你都可以在 iii time 接近 linear time 你可以把它转成
conjunctive normal form,也就是说 resolution 是 iii
propositional logic,如果今天我们把 propositional logic 的范围再缩小一点。
这就是缩小到 horn cross,horn cross 的话,那这个不是全部的。
proposition 就是不是任何一个 propositional logic 的
syntax 都能转成 horn course 一个比较小的 subset,但是 anyway 如果在这个小一点的
subset 我们可以用 forward chaining 我们刚才讲的和 backward chaining,它基本上速度比 enquire
非常多,它基本上是 linear to knowledge base 的 size。
那尤其是 backward chaining 的话如果你已知你的目标,它的速度可以比 forward chaining 还更快一些,以上是我们这一讲的内容。