Knowledge Representation

Knowledge Representation

Overview

• Course: CSC-4240/5240: ARTIFICIAL INTELLIGENCE

• Instructor: Amr Hilal, Associate Professor

• Date: 10/14/2025

First Order Definite Clauses

• Definition: A clause that is a disjunction of literals with exactly one positive literal.

  • Example:
    eg A \/
    eg B \/
    eg C \ / D (equivalent to $A \land B \land C \rightarrow D$)

• Not all logical sentences can be expressed as definite clauses, limiting the use of Forward Chaining.

• Structure of rules: Antecedent → Consequent covers various real-world systems.

Forward Chaining

• Process:

  1. Matching all rules against all known facts.

  • Example: $orall x (Missile(x) \land Owns(Nono,x) \rightarrow Sells(West,x,Nono))$

  1. Challenges:

  • Conjunct Ordering: Finding the optimal order to match variables is NP-Hard.

    • Remedy: Use heuristics.

  1. Rechecking every rule on each iteration.

  • Condition: New facts inferred must derive from at least one new fact inferred in the previous iteration.

    • Remedy: Only check rules where the premise includes a conjunct that unifies with newly inferred facts from the previous iteration.

  1. Handling irrelevant facts (e.g., $Enemy(Wumpus,America)$).

  • Remedy: Use Backward Chaining.

Backward Chaining

• Definition: Also applies to definite clauses, functioning in a reverse manner.

• Process:

  • Proves each premise of a rule by attempting to satisfy the goal.

  • For each clause in the knowledge base whose positive literal unifies with the goal, a recursive call is created.

  • If the goal unifies with a known fact, no new subgoals are added, and the goal is resolved.

  • Utilizes a Depth-First Search (DFS) approach.

• Application: Forms the basis for logic programming (e.g., Prolog).

Homework Example: Backward Chaining

• Given statements:

  1. $Pig(y) \land Slug(z) \rightarrow Faster(y,z)$

  2. $Slimy(z) \land Creeps(z) \rightarrow Slug(z)$

  3. $Pig(Pat)$

  4. $Slimy(Steve)$

  5. $Creeps(Steve)$

• Goal: Prove $Faster(Pat,Steve)$.

Resolution in First Order Logic (FOL)

• Context: Forward and Backward chaining requires rules to be definite clauses; not all problems fit this model.

• Resolution: Works for any knowledge base; applicable beyond definite clauses.

  • Example Clause Resolution: If given clauses $A \lor B$ and $\neg B \lor C$, we can derive $A \lor C$.

Full Resolution in Propositional Logic (PL)

• Example:

  • From $A \lor B$ and $\neg B \lor C$, we eliminate complementary literals (negations) to determine $A \lor C$.

• Conjunctive Normal Form (CNF): Clauses must be standardized so they share no variables.

• Resolution Rule: In FOL, two clauses can resolve if they contain complementary literals (one must unify with the negation of the other).

Proof by Refutation Using Resolution

• Concept: Prove that Knowledge Base (KB) entails α by proving that $KB \land \neg α$ is unsatisfiable, which is done by deriving the empty clause.

• Process Steps:

  1. Convert each statement in KB to CNF.

  2. Negate the goal statement and convert it to CNF.

  3. Apply resolution repeatedly to generate new statements.

  4. If an empty statement $[]$ is generated, the proof is complete (KB entails α).

  5. If no new clauses can be added, then KB does NOT entail α.

• Relation to Propositional Logic: This methodology can also apply to PL.

• Inference Completeness: Inference in FOL through resolution is complete.

Knowledge Representation (KR) Overview

• Focused on enabling an agent with a knowledge base to make inferences for appropriate actions.

• Previously, learned Predicate Logic (PL) and First Order Logic (FOL) for representing knowledge with limited examples.

• This segment addresses how to effectively represent facts about the world in a structured and scalable manner.

Ontological Engineering

• Objective: Develop more general and flexible knowledge representations.

• FOL vs. PL: FOL better handles complex representations involving actions, time, physical objects, and beliefs.

• Domains: Functional across various domains; OOP designs and patterns can be applied here.

• Upper Ontology:

  • Defines a framework for general concepts.

  • Similar to how Wikipedia represents knowledge in graph forms.

• Limitations: FOL has exceptions requiring specialized handling; no universally accepted general ontology exists, but special-purpose ontologies are present.

The Upper Ontology of the World

• Categories Included:

  • Anything

  • Abstract Objects

  • Generalized Events

  • Sets, Numbers, Intervals, Places

  • Physical Objects, Processes, Categories

  • Sentences, Measurements, Moments

  • Times, Weights, Animals, Agents, Substances

General vs. Special-Purpose Ontologies

• General-purpose ontology: Broadly useful across special-purpose domains with added domain-specific axioms.

• Should facilitate reasoning and problem-solving across multiple disciplines.

• Example considerations include: Categories, Measures, Time, Space, Change, Events, and Objects.

Categories and Objects in KR

• Organization: KR requires the systematic organization of objects into categories.

• Interaction primarily occurs at the object level; reasoning usually at the category level.

• Inference Example:

  • Attributes inform category recognition.

  • If an object is identified as orange, made of leather, and has a diameter of 9.5”, it is inferred to be a basketball.

• Formal Representation: Categories can be denoted as

  • Predicates: $apple(x)$

  • Reification of Categories: $Member(b, Apples)$ (easier for ontological use).

Category Organization

• Inheritance Relations: Defines the taxonomy of relationships.

  • Example: If all instances of food are edible, fruit is a subclass of food, hence, apples are edible.

FOL and Categories

• An object belongs to a category:

  • $MemberOf(BB12, Basketballs)$

• A category may be a subclass of another:

  • $SubsetOf(Basketballs,Balls)$

• Properties are attributed to all members of a category:

  • $\forall x (MemberOf(x,Basketballs) \Rightarrow Round(x))$

• Recognizing properties by inference:

  • $\forall x (Orange(x) \land Round(x) \land Diameter(x)=9.5in \land MemberOf(x,Balls) \Rightarrow MemberOf(x,BasketBalls))$

• Properties at Category Level:

  • $MemberOf(Dogs,DomesticatedSpecies) \rightarrow Dogs \text{ inherit the properties of domesticated species}$

Relations Between Categories

• Important to define relations among categories that are not subclasses of each other.

• Disjoint Categories:

  • Two or more categories have no members in common:

  • $Disjoint(s) \iff (\forall c<em>1,c</em>2 (c<em>1 \in s \land c</em>2 \in s \land c<em>1 \neq c</em>2 \Rightarrow Intersection(c<em>1,c</em>2) = \emptyset)$

  • Example: $Disjoint({animals, vegetables})$

• Exhaustive Decomposition:

  • A set of categories constitutes an exhaustive decomposition if all members of a category are covered by that set:

  • $ExhaustiveDecomposition(s,c) \iff (\forall i (i \in c \Rightarrow \exists c<em>2 (c</em>2 \in s \land i \in c_2)))$

  • Questions posed:

  • Is $ExhaustiveDecomposition({two-legged, four-legged}, Animals)$ valid?

  • Is $ExhaustiveDecomposition({undergraduates, graduates}, students)$ valid?

Further Relations Between Categories

• Partition Definition: A partition represents a disjoint exhaustive decomposition.

  • Expressed as:

  • $Partition(s,c) \iff Disjoint(s) \land ExhaustiveDecomposition(s,c)$

  • Query: Is ${Americans, Canadians, Mexicans}$ a partition of North Americans?

Physical Composition

• An object can be a part of another:

  • $PartOf(Bucharest, Romania)$

  • $PartOf(Romania, EasternEurope)$

  • $PartOf(EasternEurope, Europe)$

• Transitive and Reflexive Properties:

  • $\forall x PartOf(x,x)$

  • $\forall x,y,z (PartOf(x,y) \land PartOf(y,z) \Rightarrow PartOf(x,z)$

  • Example Inference: $PartOf(Bucharest, Europe)$ is inferred.

Structural Relations Among Parts

• Categories of composite objects often involve detailing structural relations among parts.

• Example: A Biped is characterized as having specifically two legs.

Measurements

• Objects possess attributes such as height, mass, cost, etc.

• Measure Values:

  • Combine unit functions with numeric values:

  • Example: $Length(L1) = Inches(1.5) = Centimeters(3.81)$

• Conversion:

  • $\forall i (Centimeters(2.54 \times i) = Inches(i))$

No Scale Measurements

• Some measures lack a scale (e.g., beauty, difficulty).

• Key aspect: Measures can be ordered despite their numeric values.

Additional Representations and Reading

• Suggested further reading:

  • Event Calculus: section 10.3

  • Mental Objects: section 10.4