Scruffy Knowledge Representation Schemes

• Semantic nets
  • Describe the world in terms of objects (nodes) and binary associations (labelled directed edges).
  • Example: Snow and ice
  • Common associations
    • Classification - instance_of/member_of
    • Aggregation - part_of
    • Generalization - is_a/subset_of
    • Example: My chair
  • Example: Choose a student
  • Richer associations.
    • Any can be made up
    • Hyper-edges for n-ary associations. Example: John gave Mary a book
    • Boxed relations for universal quantification. Double boxed relations for existential quantification. Example: Mary
  • Taking care with object nodes
    • Beware confusing instance_of and subset_of. Example: My chair is a chair
    • Beware confusion with relation on sets and instances, e.g., size_of people
    • Variable values. Example: John is taller than Bill
  • Reasoning
    • Paths between nodes (graph theory :-)
    • Inheritance in is_a and part_of associations. Examples: Ontology, the dog parts, Mary's legs
    • Intersection search. Example: Mary and people
    • Attaching epistemic and assertional status to associations
  • The SUMO and Cyc
  • Partitions allow
    • Quantification. Example: The biting dog
    • Meta-statements. Example [ala Lug p.227]
  • Implementation
    • Direct with linked structures
    • Using logic with binary predicates, and having formulae to express hierarchies, etc.
  • Careless use of associations leads to incompleteness (e.g., two labels for the same association).
    • Sets of "adequate" associations have been proposed.
    • Conceptual dependancies use hyper edges and a rich set of associations. Example: John ate the egg. Example: John prevented Mary from giving a book to Bill.
    • Conceptual graphs
      • Use nodes to implement hyper edges,
      • Objects have a type, and possibly a value
      • #numbers are used for values for unnamed objects, and objects with multiple names
      • Operations on CGs - copy, restrict, join, simplify - take advantage of a type hierarchy. Example: Emma eats a bone. These are rules of inference, but may be unsound.
      • Can be directly implemented in logic.

• Frames
  • A way of representing stereotypical objects and situations.
  • A "struct", whose slots may contain
    • Data (possibly a (link to) another frame
    • Default values
    • Constraints
    • Procedures to run when a value is needed, inserted, removed
  • Example: Hotel room
  • Reasoning
    • Default reasoning - slots exist => there exists a value, e.g., a room has a door.
    • Constraints provide information for reasoning, and violations suggest repairs.
    • Attaching epistemic and assertional status to slots
  • Can been seen as a constrained but extended form of semantic net.
    • Can be combined with semantic nets. Example: Animals
    • Combine semantic net and frame reasoning.
  • Implementation
    • Fixed frames in languages that allow code as data
    • Linked structures
    • Logic
  • Historical fact: helped produce the notion of OO programming

• Scripts
  • Frames for sequences of events. Example: Restaurant
  • Components
    • Track
    • Props
    • Roles/actors
    • Entry conditions
    • Exit results
    • Scenes
  • Reasoning
    • Examples: Restaurant queries

Exam Style Questions

• Explain how semantic nets and frames can be viewed as different implementations of the same basic knowledge representation schema. Suggest types of knowledge for which each is more suitable.
• Give a frame/semantic net representation of the following:

  Billy is a mountain. Ethel is a tree. All mountains have trees growing on them. Billy has one tree growing on him. Ethel grows on Billy.

• Explain what the following are in terms of scripts:
  • Track
  • Props
  • Roles
  • Entry conditions
  • Scenes
  • Results
• Give a script suitable for the typical exam writing event.