Knowledge Representation and Reasoning Chapter

Knowledge

• When working with knowledge, there are two main aspects to consider: knowledge representation and reasoning.
• This chapter focuses on knowledge representation, which involves storing and processing knowledge efficiently.
• Knowledge, as distinct from data, is a collection of related information used for deductions and represents generalized behavior of the world.

Knowledge Representation

• Data refers to raw, verifiable facts, often abundant and constantly changing.
• Information is data that has been interpreted.

General Knowledge Representation Schemas

• There are several common schemas used to represent knowledge:
  • Logic-based representation:
    • Utilizes first-order predicate logic (FOL).
  • Procedural representation:
    • Uses production rules (if-then statements).
  • Network representation:
    • Employs semantic networks and conceptual graphs.
  • Structural representation:
    • Relies on scripts, frames, and objects.

Logic-based Representation - Propositional Logic

• Propositional logic represents knowledge as propositions, which are statements that are either true or false.
• Logical operators connect propositions in various ways:
  • Conjunction (and): ()
  • Disjunction (or): ()
  • Negation (not): ()
  • Implication (if-then): ()
  • Equivalence (if and only if): ()
• Limitations of Propositional logic:
  • It can only handle true or false values.
  • It does not allow expressing relations or properties of objects.
  • It lacks flexibility in handling changes to the knowledge base.

Logic-based Representation - First-Order Logic (FOL)

• FOL extends propositional logic by introducing:
  • Relations between objects in the world.
  • Functions that operate on objects.
• FOL constructs include:
  • Constants: Represent specific objects (e.g., john, apples).
  • Predicates: Describe properties and relations (e.g., likes(john, apples)).
  • Functions: Transform objects (e.g., fruit_of(apple_tree)).
  • Variables: Represent any object (e.g., likes(X, apples)).
  • Quantifiers: Qualify the values of variables:
    • Universal quantifier (): True for all objects.
    • Existential quantifier (): True for at least one object.

First-Order Logic and Prolog

• Prolog is a logic-based programming language designed for Artificial Intelligence applications.
• It uses first-order logic syntax.
• It consists of:
  • Facts.
  • Rules.

Procedural Representation: Production Rules

• Production rules consist of pairs in the form 'if condition then action'.
• The Match-Resolve-Act cycle governs their execution:
  • Match - The agent checks if a rule's condition is met.
  • Resolve - The agent selects a rule if multiple rules are applicable (conflict resolution).
  • Act - The agent performs the rule's specified action if the condition is true.
• Working memory stores knowledge that can be used to match other rules.

Network Representations: Semantic Networks

• Nodes in semantic networks represent objects or concepts.
• Relationships between objects are represented using arcs between nodes.
• Inheritance of properties is handled similarly to object-oriented programming.

Knowledge Representation

• Knowledge representation refers to the way knowledge is stored and processed effectively.
• This involves two key aspects:
  • How to represent the knowledge space (Chapters 2 & 3)
  • How to implement reasoning within that knowledge space (Chapters 4 & 5)
• The goal is to represent the world logically and enable an intelligent agent (program) to make informed decisions.
• Knowledge is crucial for intelligent systems to make decisions.
• Knowledge base (KB) represents facts about the world, essential for intelligent agents.

What is Knowledge

• Data is primitive, verifiable facts in any representation. It reflects the current world, often voluminous and frequently changing.
• Information is interpreted data.
• Knowledge is the relationship between sets of data (information) often used for further deduction. It's general, unlike data.
• Knowledge contains information about the behavior of abstract models of the world.

General Knowledge Representation Schemas

• Logic-based representation: First-order predicate logic (FOL)
• Procedural representation: Production rules
• Network representation: Semantic networks, conceptual graphs
• Structural representation: Scripts, frames, objects

Logic-based Representation: Propositional Logic

• Knowledge is represented as propositions, statements that are either true or false.
• Example: "Lobster is expensive."
• Logical operators:
  • Conjunction (and) ()
  • Disjunction (or) ()
  • Negation (not) ()
  • Implication ()
  • Equivalence ()

Propositional Logic Limitations

• Can only handle true or false values.
• Entire propositions are represented as single symbols, limiting the ability to talk about objects with properties (height, width, etc.) and relationships between objects.
• Doesn't easily support knowledge base changes.
• Lacks expressiveness and the ability to discuss specifics.
• Example: Describing that thousands of locations are free of dirt would require thousands of separate propositions.

Logic-based Representation: First Order Logic (FOL)

• FOL extends propositional logic by introducing relationships about things in the world: objects and functions on those objects.
• We can believe these relations are true, false, or unknown.

First-Order Logic Constructs

• Constants: Represent objects (e.g., John, apples)
• Predicates: Represent properties and relations (e.g., likes(john,apples))
• Functions: Transform objects (e.g., likes(john, fruit_of(apple_tree)))
• Variables: Represent any object (e.g., likes(X, apples))
• Quantifiers: Qualify variable values:
  • Universal quantifier (): True for all objects (e.g., X.likes(X,apples))
  • Existential quantifier (): Exists at least one object (e.g., X.likes(X,apples))

First Order Logic & Prolog

• Prolog: A declarative programming tool used to write artificial intelligence programs.
• Based on First Order Logic syntax.
• Consists of:
  • Facts
  • Rules

Procedural Representation: Production Rules

• Rule set of “if condition then action” pairs.
• Match-resolve-act cycle:
  • Match: Agent checks if each rule’s condition holds.
  • Resolve: Multiple rules may fire at once (conflict set). The agent must choose a rule from the set (conflict resolution).
  • Act: If the condition matches, the rule "fires" and the action is carried out.
• Working memory: Rules can write knowledge to working memory, which can then match and fire other rules.

Network Representations: Semantic Networks

• Nodes represent objects in a hierarchical network of relationships.
• Allows for inheritance of properties, similar to OOP objects.