AI基础 L17 Logic Agents II
Logic in General
• Logics are formal languages for representing information such that conclusions can be drawn
• Syntax defines the sentences in the language
• Semantics define the “meaning” of sentences;
i.e., define truth of a sentence in a world
• E.g., the language of arithmetic
x + 2 ≥ y is a sentence;
x2 + y > is not a sentence
x + 2 ≥ y is true iff the number x + 2 is no less than the number y
x + 2 ≥ y is true in a world where x = 7
逻辑(Logics)
逻辑是一组规则和结构,用于表达和推理关于世界状态的信息。逻辑系统提供了一种方法来表述和分析陈述,并基于这些陈述得出结论。
例如,在命题逻辑中,一个常见的逻辑是: 推导
- 如果 P 并且 Q,那么 P 蕴含 Q。
这意味着如果 P 为真,并且 Q 为真,那么 P 蕴含 Q 也必须为真。
语法(Syntax)
语法定义了逻辑中句子的结构和形式。它规定了句子的组成部分、它们如何组合以及哪些组合是有效的句子。语法确保了句子的结构是正确的,但不涉及句子的实际含义或内容。
例如,在英语中,一个简单的句子可以有主语和谓语: 规则
- 主语(Subject):John
- 谓语(Predicate):plays football
组合起来就是一个语法上有效的句子:“John plays football.”
语义(Semantics)
语义定义了句子的“意义”,即句子在现实世界中的真值。它描述了句子在特定情境或世界状态下的有效性。语义确保了句子的内容和表述方式是相关的,并且有意义。
例如,在模态逻辑中,一个句子可以有真值,这取决于特定的世界状态: 意思
- 如果 P 在世界 w 中为真,那么句子 “It is possible that P” 在逻辑上为真。
这意味着如果 P 在某个世界 w 中为真,那么句子 “It is possible that P” 也为真。
Entailment
• Entailment means that one thing follows from another:
K B |= α
• Knowledge base K B entails sentence α
if and only if
α is true in all worlds where K B is true
• E.g. the K B containing “Arsenal won” and “Chelsea won”
entails “Either Arsenal won or Chelsea won”
E.g., x + y = 4 entails 4 = x + y
• Entailment is a relationship between sentences (i.e. syntax) that is based on semantics
蕴含(Entailment)
蕴含是指一个句子(或命题)从另一个句子(或命题)中推导出来的关系。如果一个知识库(KB)蕴含一个句子 α,那么 α 必须在所有 KB 为真的世界中都为真。
-
表示:
- K B |= α 表示知识库 K B 蕴含句子 α。
-
关系:
- K B |= α 成立当且仅当 α 在所有 K B 为真的世界中都是真的。
示例
-
Arsenal won 和 Chelsea won:
- 如果知识库包含“Arsenal won”和“Chelsea won”,那么根据这些信息,我们可以推断出“Either Arsenal won or Chelsea won”(要么阿森纳赢了,要么切尔西赢了)。这是因为如果两个队伍都赢了,那么这个结论就是真的。
-
x + y = 4 和 4 = x + y:
- 这两个句子在数学上是等价的,因为它们表达的是同一个数学事实。所以,如果 x + y = 4 成立,那么 4 = x + y 也必须成立。
蕴含的性质
蕴含是一种基于语义的关系,它存在于句子之间(即语法结构),并基于句子的意义。这意味着蕴含不仅仅取决于句子的结构,还取决于它们所表达的信息。
Models
• We say m is a model of a sentence α if α is true in m
• M (α) is the set of all models of α
• Then K B |= α if and only if M (K B) ⊆ M (α)
Entailment in the Wumpus World
Truth tables for inference 2**7 = 128 lines
Inference by Enumeration
• Depth-first enumeration of all models is sound and complete
• Procedure is also linear on the number of models
• Unfortunately O(2n) for n symbols;
• Problem is co-NP-complete 这意味着任何 NP 问题都可以在多项式时间内转换为这个方法的问题
Forward and backward chaining
• Horn Form (restricted)
K B = conjunction of Horn clauses
• Horn clause =
— proposition symbol; or
— (conjunction of symbols) ⇒ symbol
E.g., C ∧ (B ⇒ A) ∧ (C ∧ D ⇒ B)
• Modus Ponens (for Horn Form): complete for Horn KBs
• Can be used with forward chaining or backward chaining. These algorithms are very natural and run in linear time
Forward Chaining
从现有信息 A B开始推导 直到推到到结论Q
Backward chaining
• Idea: work backwards from the query q
• To prove q by BC:
— check if q is known already, or
— prove by BC all premises of some rule concluding q
• Avoid loops: check if new subgoal is already on the goal stack
• Avoid repeated work: check if new subgoal
1 has already been proved true, or
2 has already failed
• Essentially And-Or search:
— initial state = query
— goal state = KB
— actions = clauses
— states = models of KB
— if a plan exists q is true
(plan contains the inference steps)
AND-OR Graph Search
从结论开始出发 逆向推导直到支持结论的事实或规则
Forward vs. backward chaining
• FC is data-driven, cf. automatic, unconscious processing,
e.g., object recognition, routine decisions
— May do lots of work that is irrelevant to the goal
• BC is goal-driven, appropriate for problem-solving,
e.g., Where are my keys? How do I get into a PhD program?
— Complexity of BC can be much less than linear in the size of the KB
前向链(Forward Chaining)
-
数据驱动:
- 前向链从事实或已知信息出发,逐步推导出新的结论。
- 它类似于自动、无意识的处理,如对象识别或日常决策。
-
优势:
- 可以处理大量的数据,并且能够发现新的结论,即使这些结论与当前目标无关。
- 适用于需要处理大量数据的情况,例如在复杂的环境中进行推理。
-
劣势:
- 可能会执行大量与目标无关的工作,导致效率低下。
- 可能需要处理大量的事实和规则,这可能导致算法复杂度和计算成本增加。
后向链(Backward Chaining)
-
目标驱动:
- 后向链从目标或查询出发,逆向推理以找到支持目标的事实或规则。
- 它适合于解决问题,如“我的钥匙在哪里?”或“我如何进入博士项目?”
-
优势:
- 可以更直接地针对特定目标进行推理,从而减少与目标无关的工作。
- 在处理某些问题时,其复杂性可能比线性函数更小,这意味着它可能更高效。
-
劣势:
- 可能需要更多的规则和事实来支持目标,这可能导致知识库的规模增大。
- 可能需要更多的计算资源来处理复杂的推理路径。