Frames

Introduction

Frames: structured knowledge representation dividing knowledge into cohesive chunks (frames). Frame represents concept, object type, or situation. Contains slots (attributes) storing relevant information. Inheritance enables property propagation: specific instances inherit attributes from general classes.

Originated in Marvin Minsky's 1975 work on knowledge representation. Motivation: pure logical representations (propositional, first-order logic) lack structure, not intuitive for human experts, inefficient for large knowledge bases.

Key advantages: hierarchical organization, default values for quick reasoning, inheritance reducing redundancy, procedural attachment enabling computation. Trade-off: less formal than logic, harder to verify correctness, less suitable for open-world reasoning.

"Frames provide structured way to organize knowledge about categories and individuals. Combining defaults, inheritance, and procedures, frames enable efficient reasoning matching human conceptual organization." -- Knowledge representation design

Motivation and Limitations of Logic

Logical Representation Issues

Pure first-order logic treats all knowledge uniformly. No distinguished structure. To reason about a person: must assert numerous independent facts (height, age, occupation, etc.). Information scattered across knowledge base.

Inefficiency for Defaults

People don't know everything. Use defaults: birds typically fly, people typically mortal, cars typically have four wheels. Logic awkward expressing defaults: must explicitly state exceptions, non-monotonic reasoning complex.

Lack of Closure

Closed-world assumption (facts not provable are false) dangerous in open domains. Frames support open-world: unknown values left unfilled, inference happens when needed.

Granularity Problem

What level organize knowledge? Classes vs. properties vs. relationships? Logic doesn't guide this. Frames suggest natural units (frames) matching human conceptualization.

Frame Solution

Frames bundle related information. Organize hierarchically. Inheritance reduces redundancy. Defaults enable quick reasoning. Procedures compute on-demand. Combined: efficient, intuitive representation.

Frame Concept and Structure

Frame Definition

Frame: named structure (node in knowledge graph) representing concept or individual. Contains slots (attributes). Each slot can hold values, constraints, pointers to other frames.

Basic Structure

Frame: BIRD
 class: ANIMAL
 legs: 2
 wings: TRUE
 can-fly: TRUE (default)
 color: {red, blue, yellow} (constraints)
 habitat: not-specified (unknown)
 diet: seeds, insects
 reproduction: laying eggs

Slot Components

Each slot contains: value (current assignment), type (expected type), cardinality (single, multiple), constraints (value restrictions), default (assumed value), source (who provided), confidence (certainty level).

Values Representation

Slot value: atomic (number, string), reference to another frame (pointer), set of values, computed (procedure), unknown. Flexibility: represent diverse information types.

Slot Facets

Facet: property of slot itself. Example facets: constraint (value must satisfy), default (fallback value), if-added (action when value added), if-needed (compute if not present), if-removed (action on removal).

Example Frame Instance

Frame: Tweety
 isa: BIRD
 color: yellow
 size: small
 owner: not-specified
 can-fly: TRUE (inherited from BIRD)

Slots and Attributes

Slot Types

Descriptive slots: describe properties (color, size, age). Relational slots: connect to other frames (owner, parent, friend). Functional slots: computed values. Procedural slots: trigger actions.

Value Assignment Strategies

Explicit: slot directly filled. Inherited: value obtained from parent class. Default: fallback value if not specified. Computed: derived from procedure. Unknown: explicitly marked unfilled.

Constraints on Slots

Type constraint: value must be number, string, or reference to frame of type X. Value constraint: value must satisfy predicate (age > 0). Cardinality: single value vs. list. Help maintain knowledge base consistency.

Multi-Valued Slots

Slot holds list of values. Example: PERSON has hobbies [reading, hiking, painting]. Supports many-to-many relationships efficiently.

Inverse Relations

Explicit maintain bidirectional links. Frame A points to frame B via slot, frame B points back via inverse slot. Consistency check: if X is-parent-of Y, then Y has-parent X.

Default Values and Facets

Defaults in Frames

Default value: assumed unless contradicted. Example: birds can fly (default), but ostrich cannot (exception). Enables quick inference without proving everything. Reflects commonsense reasoning patterns.

Default Inheritance

Inherit defaults from parent class. Specific instance can override. BIRD: can-fly=TRUE. Penguin (subclass BIRD): can-fly=FALSE overrides. Tweety (instance BIRD): inherits can-fly=TRUE unless specified otherwise.

Facet Types

Value facet: current value. Type facet: expected type. Default facet: fallback. Constraint facet: acceptable values. Range facet: numeric bounds. Cardinality facet: how many values. Source facet: origin of knowledge.

If-Needed Facets (Lazy Evaluation)

If-needed: procedure executed when slot accessed if value not present. Compute on-demand. Example: height computed from weight-class rather than stored explicitly. Saves memory.

If-Added Facets (Triggers)

If-added: action triggered when value added. Maintain consistency. Example: adding to parent list automatically updates inverse child list. Propagate constraint violations.

If-Removed Facets

If-removed: action on value deletion. Example: removing owner updates inverse pet list. Maintain bidirectional links. Enable cascade deletions.

Inheritance in Frame Systems

Single Inheritance

Frame inherits from one parent. BIRD inherits from ANIMAL. Penguin inherits from BIRD. Clear hierarchy, simple to implement. Each frame has one isa link.

Multiple Inheritance

Frame inherits from multiple parents. Amphibian inherits from Vertebrate (biological) and CanLiveInWater (habitat). Captures complex relationships. Risk: conflicts, ambiguity.

Inheritance Chain

Properties propagate through hierarchy. Tweety is instance of BIRD, BIRD is subclass of ANIMAL, ANIMAL is subclass of PHYSICAL-OBJECT. Tweety inherits properties transitively.

Attribute Lookup

To get slot value for frame:
1. Check frame itself
2. If not found, check parents (isa frames)
3. Recursively check grandparents
4. Return value or default
5. If all fail, value unknown

Inheritance Priorities

Specific overrides general. Instance Tweety's can-fly can override class BIRD's default. Own slot overrides inherited. More specific class overrides less specific.

Performance Advantage

Inheritance avoids redundancy. Store fly-capability once in BIRD, all birds inherit. Millions of individuals? Single change updates all. Contrast storing fact for each.

Instance vs. Class Frames

Class Frames

Class frame represents category. BIRD, MAMMAL, VEHICLE. Contains general properties. Multiple instances inherit from class. Defines what members have in common.

Instance Frames

Instance frame represents individual. Tweety (specific bird), John (specific person). Points to class via isa link. Contains individual-specific values. Inherits from class.

Class Hierarchy

PHYSICAL-OBJECT (most general)
 ├── ANIMAL
 │ ├── BIRD
 │ │ ├── Tweety (instance)
 │ │ └── Polly (instance)
 │ └── MAMMAL
 └── VEHICLE

Slots at Different Levels

Class slots: typical values for category. BIRD: legs=2, can-fly=TRUE. Instance slots: specific values. Tweety: color=yellow, age=3. Mix both: instance uses class info, adds specifics.

Polymorphism

Same slot name, different meaning in different frames. But connected via hierarchy: ANIMAL frame defines slot, subclasses specialize. Enables method-like behavior.

Abstract Classes

Abstract frame represents concept not instantiated. MAMMAL (abstract): define characteristic slots. Never create MAMMAL instance directly. Create DOG, CAT (concrete subclasses).

Procedural Attachments and Demons

Procedural Attachment Concept

Attach procedures (demons) to frame slots. Execute when conditions met. Enable computation beyond static data. Marriage ceremony: when new value added to spouse slot, automatically add to spouse's spouse slot.

Demon Types

If-added: execute when value added. If-needed: execute when value accessed (compute on-demand). If-removed: execute when value deleted. General-if: execute when some condition becomes true.

Example Demons

PERSON frame:
 age:
 value: unknown
 if-needed: compute from birth-date (today - birth-date)
 salary:
 if-added: [update tax amount, update benefits package]
 retirement-eligible:
 general-if: age >= 65 (compute automatically)

Advantages

Reduce stored knowledge: compute rather than store. Maintain consistency: demons ensure updates propagate. Encapsulation: hide computation details. Flexibility: behavior defined with knowledge.

Challenges

Execution order complex with multiple demons. Difficult debugging: procedures hidden. Efficiency: demons add overhead. Need careful design to avoid infinite loops.

Modern Systems

Object-oriented programming evolved from frames. Methods = demons. Encapsulation, inheritance, polymorphism rooted in frame-based representation. Many modern languages support similar concepts.

Inheritance Conflicts and Resolution

Conflict Sources

Multiple inheritance: ambiguity which parent's value to inherit. Diamond problem: same ancestor accessed via different paths. Conflicting defaults: parents disagree on value.

Diamond Problem Example

 MAMMAL
 / \
 / \
 DOG CAT
 \ /
 \ /
 HYBRID

From which class inherit MAMMAL properties? Dog or cat version?

Resolution Strategies

Priority ordering: left-to-right parent order (first parent priority). Specificity: more specific class overrides general. Closest parent: shortest path to ancestor. Explicit: program declares preference.

Shadowing

Child slot definition shadows (hides) parent's. Tweety: can-fly=FALSE shadows BIRD: can-fly=TRUE. Explicit override. Clear resolution: use most recent definition.

Non-Monotonic Semantics

Inheritance non-monotonic: adding information can retract conclusions. BIRD: can-fly=TRUE. Learn penguin is bird? Retract can-fly for penguins. Differs from pure logic.

Blocking Inheritance

Prevent inheritance by marking property not-inherited or explicitly blocking. Example: tall (for humans) shouldn't inherit to species (doesn't make sense). Exceptional reasoning.

Reasoning with Frames

Property Lookup

Query: does Tweety have property can-fly? Traverse inheritance hierarchy. Found in BIRD class. Return value (default TRUE). Combine with potential exceptions.

Pattern Matching

Find frames matching pattern. Pattern: PERSON with age > 65 and salary > 100K. Scan frame instances, match constraints. Used for rule-based reasoning, query answering.

Slot Filling

Given partial frame, fill missing slots. Input: person named john, age 30. Find matching frames, complete description. Used in dialogue systems, case-based reasoning.

Spreading Activation

Activate related frames. Query about dog: activate ANIMAL, DOG, MAMMAL, related frames. Activation spreads along links. Parallel activation of relevant knowledge. Model attention.

Conflict Resolution in Rules

Frames support production rules (if-then). When multiple rules fire, conflict resolution determines which execute. Strategies: specificity (more specific fires first), recency (recent facts fire first), priority (explicit ranking).

Consistency Maintenance

If-added/if-removed demons ensure consistency. Update parent affects children. Constraint violations detected. Frameworks support truth maintenance: track justifications, revert when premises invalidated.

Frames vs. Other Representations

Frames vs. First-Order Logic

Frames vs. Semantic Networks

Semantic networks: graphs of nodes (concepts) and labeled edges (relations). Frames more structured: nodes contain attributes. Semantic networks simpler but less organized. Frames evolved from semantic networks.

Frames vs. Object-Oriented Programming

Frames influenced OOP. Both: classes, inheritance, methods (demons). OOP: imperative, algorithms. Frames: declarative, inference. OOP better for implementation, frames for knowledge representation.

Integration Approaches

Hybrid systems combine frames with logic. Use frames for structure, logic for reasoning. Enables both efficiency and correctness checking. Many knowledge bases use layered approach.

Applications in AI Systems

Expert Systems

Frame-based expert systems organize domain knowledge. Medical diagnosis: disease frames contain symptoms, tests, treatments. Consultation engine matches patient symptoms to disease frames, infers condition.

Natural Language Processing

Frames represent scenarios, events, participants. Story understanding: activate appropriate frame (restaurant, hospital), fill slots with parsed information. Semantic parsing uses frames.

Case-Based Reasoning

Store past cases as frames. Retrieve similar cases via pattern matching. Adapt solutions to new problems. Legal reasoning, medical diagnosis use case-based approach with frames.

Planning and Scheduling

Frames represent actions, resources, constraints. Planning engine selects action frames, instantiates for current situation. Inheritance enables template-based planning.

Ontologies and Knowledge Graphs

Modern ontologies (semantic web, linked data) descended from frames. RDF resources have properties (slots). OWL classes have inheritance hierarchies. Frame concept persists.

Dialogue Systems

Dialogue frames represent conversation topics, participants, context. Dialogue manager uses frames to understand intent, maintain context, generate responses. Enables coherent multi-turn conversations.

References

• Minsky, M. "A Framework for Representing Knowledge." MIT-AI Laboratory Memo 306, 1974.
• Brachman, R. J., and Levesque, H. J. "Knowledge Representation and Reasoning." Morgan Kaufmann, 2004.
• Genesereth, M. R., and Nilsson, N. J. "Logical Foundations of Artificial Intelligence." Morgan Kaufmann, 1987.
• Russell, S. J., and Norvig, P. "Artificial Intelligence: A Modern Approach." Prentice Hall, 4th edition, 2020.
• Quillian, M. R. "Semantic Memory." Carnegie Institute of Technology Ph.D. dissertation, 1966.