CS代写 COMP 424 - Artificial Intelligence Knowledge Representation and Logic

COMP 424 – Artificial Intelligence Knowledge Representation and Logic
Instructors: Jackie CK Cheung and Readings: R&N Ch 7

Abstract board games

Relatively easy to represent the states of these games and to
model the consequences of actions
• States were atomic for the most part
• Transitions were deterministic
COMP-424: Artificial intelligence
www.bobby-fischer.net

Complex games and problems
Control a civilization:
● buildings
● scientific research
● cultural evolution
● diplomacy
http://secondlife.com
COMP-424: Artificial intelligence

Complex games and problems
Control a civilization:
● buildings
● scientific research
● cultural evolution
● diplomacy
http://secondlife.com
We need a more expressive kind of knowledge:
• How to represent it
• How to reason about it → infer what to do next
COMP-424: Artificial intelligence 4

A knowledge-based agent
Two key components:
• The knowledge base, which contains a set of facts expressed in some formal, standard language
• The inference engine, which uses general rules to deduce new facts from those in the KB
Domain-specific content Domain-independent algorithms
Knowledge base
Inference engine
COMP-424: Artificial intelligence

A knowledge-based agent
Domain-specific content Domain-independent algorithms
• KB may be initialized with background knowledge
• When the agent perceives an observation, it adds the
related fact to its KB
• It queries the KB for what action to take in a given state
• It adds the fact that it took the action to the KB
• All the while, the inference engine may be expanding the
set of facts in the KB
Knowledge base
Inference engine
COMP-424: Artificial intelligence 6

Logic as a formal language
The formal language (today) is propositional logic
• A simple logic consisting of proposition symbols and logical
connectives
• It can handle propositions that are known true, known false, or unknown
This is how we can formally express our knowledge, perform inference and update operations on the KB.
Let’s start with an example world.
COMP-424: Artificial intelligence 7

An example: Wumpus World Percepts: Breeze, Glitter, Stench
(local perception only)
Actions: Turn-left, Turn-right, Forward, Grab, Shoot
Goal: Get the Gold and return to Start; Don’t enter a Pit or Wumpus square
Rules of the environment:
• Squares adjacent to Wumpus are smelly
• Squares adjacent to Pit are breezy
• Glitter if and only if Gold is in the same square
• Shooting kills the Wumpus if you are facing it
• Shooting uses up the only Arrow.
• Grabbing picks up the Gold if in the same square
COMP-424: Artificial intelligence 8

Wumpus World Characteristics
• The world is static: positions of the pits, gold, and monster do not change during the game
• The actions have deterministic effects
• The state is partially observable
• The agent doesn’t know the map beforehand and can only perceive what’s in the square it occupies
• → It must infer the map from local perception
• What’s the belief state for this domain?
COMP-424: Artificial intelligence 10

Exploring a Wumpus World
COMP-424: Artificial intelligence
A= Agent B= = Smell P= Pit
W= Wumpus OK = Safe
G = Glitter

Exploring a Wumpus World
A= Agent B= = Smell P= Pit
W= Wumpus OK = Safe
G = Glitter
COMP-424: Artificial intelligence

Using actions to gain knowledge
• Suppose we enter another Wumpus cave
• Perceive Smell in (1, 1) ⇒ cannot move
• Use a strategy of coercion:
• Shoot straight ahead
• Wumpus was there ⇒ dead ⇒ safe
• Wumpus wasn’t there ⇒ safe
Logic is a type of knowledge representation that supports this reasoning!
COMP-424: Artificial intelligence 19

• Logics are formal languages for representing information
• They enable conclusions to be drawn from what is known
• A logic is defined by the following:
• The syntax defines which sentences are allowed in the language
• The semantics define the “meaning” of sentences,
i.e., the truth of a sentence in a given world
An analogy: 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, y=1
x+2 ≥ y is false in a world where x=0, y=6
COMP-424: Artificial intelligence 21

Types of logic
• Logics are characterized by what they allow as “primitives”
• Ontological commitment: what exists? (facts/objects/time/beliefs)
• Epistemological commitment: what do we know? (states of knowledge)
Propositional logic First-order logic Temporal logic Probability theory Fuzzy logic
Ontological commitment
facts, objects, relations
facts, objects, relations, times facts
degree of truth
Epistemological commitment
true/false/unknown true/false/unknown true/false/unknown degree of belief [0, 1] degree of belief [0, 1]
COMP-424: Artificial intelligence

Propositional logic
• Propositions are the basic elements
• They are assertions about the state of the world/game/problem
• They can be true or false
• e.g. “Today is Thursday”, “Today is Wednesday”
• Syntax specifies the valid sentences in the logic
• Atomic sentences consist of a single proposition symbol, like the sentence P1 or the sentence P2
• Complex sentences are constructed from simpler sentences
• We combine sentences using parentheses and logical connectives
COMP-424: Artificial intelligence 23

Propositional logic: Syntax
There are five standard logical connectives: negation: ¬ conjunction: ∧ disjunction: ∨ implication: ⇒
biconditional: ⇔ iff
not and or
Syntax defines the allowable sentences: • Atomic sentences are sentences (obvs)
• If S is a sentence,
• If S1 and S2 are sentences,
• If S1 and S2 are sentences,
• If S1 and S2 are sentences,
• If S1 and S2 are sentences,
¬S is a sentence
S1 ∧ S2 is a sentence S1 ∨ S2 is a sentence S1 ⇒ S2 is a sentence S1 ⇔ S2 is a sentence
COMP-424: Artificial intelligence

Propositional logic: Semantics
The semantics defines the rules for determining the truth of a sentence
Truth is always determined with respect to a model
A model is an assignment of truth values, one for every proposition symbol. E.g.,
m = {P1 = true, P2 = false, P3 = true}
The model specifies the particular world the agent occupies,
by what is true and what is false in that world
A sentence may be true in one model and false in another COMP-424: Artificial intelligence 25

Propositional logic: Semantics
• The semantics defines the rules for determining the truth of a sentence, with respect to a particular model
• Rules for evaluating truth with respect to model m:
S1 ∧ S2 S1 ∨ S2 S1 ⇒ S2 S1 ⇔ S2
is true iff is true iff is true iff is true iff is true iff
S is false
S1 is true and S1 is true or S1 is false or S1⇒S2 istrue and
inm S2 is true inm S2 is true inm S2 is true inm S2⇒S1 istrue inm
COMP-424: Artificial intelligence

Interpretations: True or False
Some terminology:
• A sentence is valid if it is true in all models
• A sentence is satisfiable if it is true in at least one model
• A sentence is unsatisfiable if it is false in all models
• The truth of a sentence may depend on the model
• A model may also be called an interpretation
• A sentence may be true in one interpretation and false in another
E.g., Sentence = “I finished my AI homework.” Is this valid? Is it satisfiable?
COMP-424: Artificial intelligence

• For each of the following logical statements, say whether it is valid, satisfiable or unsatisfiable:
(A ∧ B) ∨ (¬A ∨ ¬B) ¬A ⇒ A
B ∧ (B ⇒ ¬B)
COMP-424: Artificial intelligence 28

• For each of the following logical statements, say whether it is valid, satisfiable or unsatisfiable:
(A ∧ B) ∨ (¬A ∨ ¬B) ¬A ⇒ A
B ∧ (B ⇒ ¬B)
satisfiable valid satisfiable unsatisfiable
COMP-424: Artificial intelligence

Using logic
We want to derive sound conclusions from what we already know
Thus, we want a process for generating new sentences that are guaranteed to be true
• (in any world in which the premises are true)
The first step is the concept of entailment: α ⊨ β
• We say α entails β
• Or, β follows logically from α
COMP-424: Artificial intelligence 30

Entailment
• Sentence α entails sentence β if and only if β is true in all worlds where α is true:
α ⊨ β if and only if M(α) ⊆ M(β)
COMP-424: Artificial intelligence

Entailment
• Sentence α entails sentence β if and only if β is true in all worlds where α is true:
COMP-424: Artificial intelligence
α ⊨ β if and only if
The set of all models in which α is true. “The set of all models that satisfy α.”

Entailment
Sentence α entails sentence β if and only if β is true in all worlds where α is true:
α ⊨ β if and only if ⊆ M(β)
The set of all models in which α is true.
“The set of all models that satisfy α.” α is a stronger assertion than β, since α rules out more
possible worlds
Another arithmetic illustration:
sentence x = 0 entails sentence xy = 0
COMP-424: Artificial intelligence 33

Entailment and the Knowledge-based Agent
• Recall our agent, with its knowledge base and inference procedure
• Now we have an idea for what the KB actually is:
• a set of sentences in propositional logic!
• We can also see the utility of entailment
If KB ⊨ α then:
• in every model in which KB is true, α is also true
• we can derive the conclusion α from what we already know (the KB)
COMP-424: Artificial intelligence 34

Inference procedure
means sentence α can be derived from KB by inference procedure i
• Desired qualities of inference procedure i:
Soundness: i is sound if, whenever KB ⊢i α is true, it is also true that
In other words, we only infer necessary truths.
Completeness: i is complete if, whenever KB ⊨ α is true, it is also true that KB ⊢i α.
In other words, we can generate all the necessary truths.
COMP-424: Artificial intelligence 36

Two inference methods
1. Model checking:
• Truth table enumeration
1. Application of inference rules
COMP-424: Artificial intelligence 37

Propositional inference
Truth table method:
Let α = A ∨ B and KB = (A ∨ C) ∧ (B ∨ ¬C) Is it the case that KB ⊨ α ?
Check all possible models: α must be true whenever KB is true.
COMP-424: Artificial intelligence 38

Propositional inference
Truth table method:
Let α = A ∨ B and KB = (A ∨ C) ∧ (B ∨ ¬C) Is it the case that KB ⊨ α ? YES!
Check all possible models: α must be true whenever KB is true.
COMP-424: Artificial intelligence 40

Entailment in Wumpus World
Let’s consider this situation:
• The agent detects Nothing in [1,1], moves right, and detects
Breeze in [2,1]
• The agent wants to infer the presence of pits in squares
[1,2], [2,2], and [3,1]
• There are 3 Boolean (true-false) choices:
• P[1,2] = true
• P[2,2] = true
• P[3,1] = true
P[1,2] = false P[2,2] = false P[3,1] = false
⇒ 8 possible models
COMP-424: Artificial intelligence 41

Models in Wumpus World
COMP-424: Artificial intelligence 42

KB in Wumpus World
• KB = wumpus-world rules + observations
COMP-424: Artificial intelligence 43

Model checking in Wumpus World
KB = wumpus-world rules + observations Consider α1 = “square [1,2] is safe”
Is it the case that KB ⊨ α1 ?
Let’s use model checking => Enumerate states and check
COMP-424: Artificial intelligence 44

KB = wumpus-world rules + observations Consider α1 = “square [1,2] is safe”
Model checking in Wumpus World
By model checking, KB ⊨ α1 😊
KB entails α if and only if α is true in all worlds where KB is true.
COMP-424: Artificial intelligence

Model checking in Wumpus World
KB = wumpus-world rules + observations Consider α2 = “square [2,2] is safe”
Is it the case that KB ⊨ α2 ?
COMP-424: Artificial intelligence

KB = wumpus-world rules + observations Consider α2 = “square [2,2] is safe”
Model checking in Wumpus World
By model checking, KB ⊭ α2 😞
KB entails α if and only if α is true in all worlds where KB is true.
COMP-424: Artificial intelligence

Properties of the truth table method
• Is it sound?
• Is it complete?
• Time / space complexity?
COMP-424: Artificial intelligence 48

Properties of the truth table method
• Is it sound? Yes.
• Is it complete? Yes. It checks truth in all possible models.
• Time / space complexity?
• Highly inefficient! 2n models for n literals!
• A literal is an atomic sentence (positive literal) or a negated atomic sentence (negative literal)
COMP-424: Artificial intelligence 50

Two kinds of inference methods
1. Model checking:
• Truth table enumeration (sound and complete, but expensive)
2. Application of inference rules (theorem proving):
• Sound generation of new sentences from old
• A proof is a sequence of inference rule applications that generates the desired sentence
• If the number of models is large relative to the length of the proof, then theorem proving can be more efficient than model checking
• We can use inference rules as operators in a standard search algorithm to automate theorem proving
COMP-424: Artificial intelligence 51

Normal forms
Application of inference rules often requires sentences to be expressed in standardized forms
Conjunctive Normal Form (CNF):
A sentence is in CNF if it is expressed as
a conjunction of
e.g., (A ∨ ¬B) ∧ (B ∨ ¬C ∨ ¬D) Isn’t this limiting?
a “clause”
COMP-424: Artificial intelligence
disjunctions of literals

Normal forms
Application of inference rules often requires sentences to be expressed in standardized forms
Conjunctive Normal Form (CNF):
A sentence is in CNF if it is expressed as
a conjunction of
e.g., (A ∨ ¬B) ∧ (B ∨ ¬C ∨ ¬D) Isn’t this limiting? Actually, no!
a “clause”
disjunctions of literals
Every sentence of propositional logic is logically equivalent to a conjunction of clauses.
COMP-424: Artificial intelligence 55

Normal forms
Application of inference rules often requires sentences to be expressed in standardized forms
Conjunctive Normal Form (CNF):
A sentence is in CNF if it is expressed as
a conjunction of
e.g., (A ∨ ¬B) ∧ (B ∨ ¬C ∨ ¬D) Isn’t this limiting? Actually, no!
Every sentence of propositional logic is of clauses.
a “clause”
COMP-424: Artificial intelligence
disjunctions of literals
logically equivalent
True in the same set of models
to a conjunction

Normal forms
Disjunctive Normal Form (DNF):
A sentence is in DNF if it is expressed as
a disjunction of conjunctions of literals
e.g., (A ∧ B) ∨ ( A ∧ ¬C) ∨ (A ∧ ¬D) ∨ (¬B ∧ ¬C) ∨ (¬B ∧ ¬D)
Horn Form:
A sentence is in Horn Form if it is expressed as
a conjunction of Horn clauses (clauses with ≤1 positive literal) e.g., (A ∨ ¬B) ∧ (B ∨ ¬C ∨ ¬D)
COMP-424: Artificial intelligence 57

Normal forms
Disjunctive Normal Form (DNF):
A sentence is in DNF if it is expressed as
a disjunction of conjunctions of literals
e.g., (A ∧ B) ∨ ( A ∧ ¬C) ∨ (A ∧ ¬D) ∨ (¬B ∧ ¬C) ∨ (¬B ∧ ¬D)
Horn Form:
A sentence is in Horn Form if it is expressed as
a conjunction of Horn clauses (clauses with ≤1 positive literal)
e.g., (A ∨ ¬B) ∧ (B ∨ ¬C ∨ ¬D)
Often written as set of implications: B ⇒ A and (C ∧ D) ⇒ B
COMP-424: Artificial intelligence 58

Inference rules for propositional logic
• Resolution (for CNF): complete for propositional logic (α∨β), (¬β∨γ)
COMP-424: Artificial intelligence

Inference rules for propositional logic
Resolution (for CNF): complete for propositional logic (α∨β), (¬β∨γ)
(for Horn Form): complete for Horn

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts