THEO

Authors

School of Computer Science, Carnegie Mellon University

Philosophy

• General framework for learning and problem solving trying to be an unified architecture supporting general intelligence.
• Self-improving system
• Basic research on general problem solving, learning and knowledge representation, and especially the interaction among these three issues.
• Accrection of research results in a form that other may reuse and extend.

  --> Theo is organized so that new representational features, new inference methods, and new learning mechanisms are each defined in terms of new slot definitions which can be incorporated by other users.

• An efficient framework for developing efficient knowledge-based systems. --> Theo is intended to provide a range of sophistication and efficiency depending on the user's needs.
• Theo is an infinitly large virtual datastructure which is incrementally made explicit on demand.

Architecture

• Frame-oriented architecture <-- Knowledge representation
• Highly uniform representation
  • (< entity >< slot >)= value
  • Belief, problem instances, problem class, problem solving methods use the same representation form.
  • Predefined slots of slots such as DEFINITIONS, DOMAIN, RANGE, INVERSE,TOGET, AVAILABLE METHODS etc..
  • Virtual and explicit entities, slots and values --> Expressions can refer to slot values that are not explicitly described by the current datastructures in memory, but which must be infered on demand.
  • Slots with no value --> If a slot value is not known ,token *NOVALUE* is stored in the value field of the slot.
  • Absolute and relative entity address --> Relative addresses are convenient when specifying a slot when refer to addresses of other slots relative to the slot whose value is to be infered.
• Basic function for Theo is to access slot values
• Three learning mechanisms
  • Caching

    --> Storing infered values so that it can be reused in subsequent inferences without recomputing, without any generalization.

  • EBL
    • Macro-methods(TMAC) --> Effective for the situation of frequently updated slot values.
    • Taking simple truth maintenance method so that if a belief changes, then the dependent beliefs are removed.
  • Inductive learning(SE)

    --> For ordering the available methods, it estimates the costs of applying various methods based on statistical data sampled.

• Effective indexing of acquired knowledge
  • Problem names serve as the indices to the problem definition, its solution, available problem solving methods, control information, explanations, and other properties of the problems.
  • The address of a slot is identical to the name of the Theo entity represented by that slot.

Issues

• Each learning mechanism changes the computational environment in a way that impact the others.

  --> For example, caching changes various computational data so that SE's estimates of the costs of applying various methods can become out of date.

• Macro-methods can cause Theo unnecessary amount of work by causing it to overlook available slot values.
• Theo should learn about the relative reliabilies of its methods.
• Theo should be able to decide when it is worth deliberating and when it is worth learning.

Comparison with Soar (Laird et al., 1987)

• Correspondence
  • Uniform problem representation --> Soar is organized around problem space, while Theo is descibed by pairs of the form (< entity >< slot >).
  • Problem solving knowledge indexing problem description --> In Soar, problem solving knowledge is stored in productions whose conditions test the problem space description. In Theo, problem solving knowledge resides in the subslots of the (< entity >< slot >).
  • Use of impasse-driven computation --> In Soar, such impasses lead to solving problems in another problem space. In Theo, impasses correspond to queries of slots whose values are unknown, and result in the subtask of inferring the corresponding slot values.
  • Caching results of impasses --> In Soar, solutions to impasses are stored in productions whose condition elements mention only those features of the problem which were used to resolve the impasse. In Theo, solution to impasses are simply the inferred slot values, and are stored directly in the subslots of the problem instance.
• Differences
  • Different representations for control knowledge --> In Soar, knowledge to control search is expressed by explicitly asserted preferences. In Theo, control knowledge is currently described by a sorted list of methods, but there are no explicitly asserted preferences between individual methods in this list.
  • Difference in uniformity of representation --> Theo's slots avoid the distinction made in Soar between problem space and attributes used in data representations.
  • Different commitments to performence and explicitness of explanations --> Theo records permanent explicit explanations for its beliefs, and these can be examined by the system. They are also used by Theo to maintain dependencies and to remove beliefs whose explanations cease to hold. Soar uses similar dependencies when constructing its 'chunks', but it neither records these dependencies permanently, nor makes them available to the non-architectural portion of the system.
  • Different memory indexing scheme --> Soar's long term memory consists soly of productions, while Theo's consists soly of entities and beliefs about them. Theo is more economical in terms of storage cost and retrieval speed.
  • Difference in use of explicit beliefs about problem classes --> Theo explicitly represents beliefs about ploblem classes, such as beliefs about their domain, range, inverse, generalizations, and specializations.
  • Different learning Mechanisms --> Soar presently has only one learning mechanism, and Theo has three. Chunking in Soar is used to cover the same kinds of learning tasks that caching and explanation-based learning cover in Theo. Theo's third learning mechanism, the inductive inference method for inferring methods orderings, has no inductive counterpart in Soar.

Comparison with RLL(Greiner & Lenat, 1980)

RLL and Theo, both are viewed as self-desciptive, frame-based representation systems.

• Goto the title page
• Goto the specific architecture list