Explore
For Enterprise
Join for Free
Log In

浏览
搜索
企业版
登录
免费加入

6-7 Backward Chaining, Pros and Cons of Propositional Logic

Loading...

人工智慧：搜尋方法與邏輯推論 (Artificial Intelligence - Search & Logic)

国立台湾大学

4.8（162 个评分） | 16K 名学生已注册

本課程分為人工智慧（上）、人工智慧（下）兩部份，第一部分除了人工智慧概論外，著重在目標搜尋、meta heuristic、電腦對弈、演繹學習（包含證言邏輯、一階邏輯及 planning ）等技術。這些技術主要發展時機為人工智慧的第一波及第二波熱潮，也就是 1950 年代至 1990 年代附近的主流發展，即使到現在也在各個領域廣為應用。課程教學目標：使同學對人工智慧有基礎概念同學能夠理解如何運用目標搜尋技術及演繹學習方式達成人工智慧同學能將相關技術應用到自己的問題上

查看授课大纲

您将学习的技能

Artificial Intelligence (AI), Search Algorithm, A.I. Artificial Intelligence, Algorithms

审阅

4.8（162 个评分）

5 stars
130 ratings
4 stars
25 ratings
3 stars
6 ratings
2 stars
1 ratings

从本节课中

Propositional Logic

6-1 Logical Agents (i) - Generic Knowledge-Based Agent, PEAS16:35

6-2 Logical Agents (ii) - Logic, Entailment and Models21:19

6-3 Propositional Logic, Inference (i) - Enumeration, Validity and Satisfiability19:16

6-4 Inference (ii) - Simple Knowledge, Resolution and CNF (i) - Proof by Resolution, CNF Conversion, Resolution Algorithm18:33

6-5 Resolution and CNF (ii) - Properties of Resolution, Ground Resolution Theorem11:59

6-6 Resolution and CNF (iii) - Horn and Definite Clauses, Forward Chaining17:07

6-7 Backward Chaining, Pros and Cons of Propositional Logic10:28

教学方

于天立
副教授 (Associate Professor)

脚本

我们刚提的是 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 还更快一些，以上是我们这一讲的内容。

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2019 Coursera Inc. 保留所有权利。

通过 Google Play 获取

Coursera
关于
管理团队
工作机会
目录
证书
MasterTrack™ 证书
学位
企业版
政府版
面向校园

社区
Learners
Partners
Developers
Beta Testers
Translators

连接
博客
Facebook
领英
Twitter
Instagram
YouTube
技术博客

更多
条款
隐私
帮助
内容访问
媒体
联系我们
目录
附属公司