role of framebased

THE ROLE OF FRAME-BASEDREPRESENTATIONIN REASONING: 

THE ROLE OF FRAME-BASED REPRESENTATION IN REASONING YONSEI UNIV. CADCAM LAB. 구진모

Slide2: 

A frame-based representation facility A knowledge system’s ability to reason The system designer in determining strategies for controlling the system’s reasoning contributes to can assist

A Fundamental observation in AI : 

Expertise in a task domain requires substantial knowledge about that domain Effective representation of domain knowledge → the keystone to the success of AI programs A Fundamental observation in AI

The kinds of knowledge that can go into a knowledge base: 

The kinds of knowledge that can go into a knowledge base

Forms of domain knowledge: 

Descriptive definitions of domain-specific terms ‘power plant’, ‘pump’, ‘flow’, ‘pressure’ Descriptions of individual domain objects and relationships to each other ‘P1 is a pump whose pressure is 230 psi’ Criteria for making decisions If…, then... Forms of domain knowledge

Knowledge-based systems: 

Knowledge-based systems Because of the emphasis on representation and domain knowledge, the systems that use AI techniques to achieve expertise are often referred to as knowledge-based systems, or simply as knowledge systems.

The basic criteria for...: 

The basic criteria for... In order for a knowledge system to use domain-specific knowledge, it must have a language for representing that knowledge The basic criteria for a knowledge representation language Expressive power Understandability Accessibility

Early attempts...: 

Early attempts... Early attempts at building intelligent systems used the first-order predicate calculus as their representation language

The predicate calculus: 

The predicate calculus Appealing Very general expressive power Well-defined semantics Difficulties in using... Very fine grained language constructs → do not provide adequate facilities for defining more complex constructs The generality → a significant barrier to the development of effective deduction facilities for using knowledge

Difficulties...: 

Difficulties... Difficulties using the predicate calculus helped motivate the development of ‘semantic networks’ and ‘object oriented’ representation languages based on frames

Frame languages: 

Frame languages An easy means of describing the types of domain objects A structured representation of an object or a class of objects

The advantages...: 

The advantages... The advantages of frame languages Capture the way experts typically think about Provide a concise structural representation of useful relations Support a concise definition-by-specialization technique

Frame languages are powerful: 

Frame languages are powerful Because… The taxonomic relationships among frames enable descriptive information to be shared among multiple frames The internal structure of frames enables semantic integrity constraints to be automatically maintained

One of the basic tenets...: 

One of the basic tenets... Represented in Declarative form Procedural form

Production rules: 

Production rules Production rules Pattern/ action decision rules The most popular and effective representational form for declarative descriptions of domain-dependent behavioral knowledge in knowledge systems

However...: 

However... Production rules do not provide an effective representation facility (inadequate for defining terms and for describing domain objects and static relationships) ↔ effectively handled by frames

Hybrid representation facilities: 

Hybrid representation facilities Combine the advantages of frame and production rule languages LOOPS, KEE, CENTAUR... Can be used to partition, index, and organize a system’s production rules. Makes it easier to construct and understand rules control particular collections of rules

The structural features...: 

The structural features... The structural features of frame language Very useful for organizing and controlling the behavior of large collection of production rules

I. Components of...: 

I. Components of... Components of a frame-based representation facility The KEE (; Knowledge Engineering Environment) system

I-1. Structural Features: 

I-1. Structural Features I-1-1. Taxonomy Descriptions Two constructs representing relationships between frames Member links ; representing class membership Subclass links ; representing class containment or specialization Frames provide structured representations of objects or classes of objects

Slide21: 

The transportation KB (knowledge base) class - subclass class - member

I-1. Structural Features: 

I-1. Structural Features Slots ; sets of attribute descriptions Own slots occur in any frame describe attributes of the object or class itself Member slots occur in frames representing classes describe attributes of each member of the class

I-1. Structural Features: 

I-1. Structural Features class TRUCKS - subclass of class VEHICLES member of class CLASSES.OF.PHYSICAL.OBJECT MemberSlot (HEIGHT, LENGTH) - prototype description of each class member OwnSlot (LONGEST, TALLEST) - describe attributes of the class as a whole Frame : TRUCKS Superclasses : VEHICLES Subclasses : BIG.NON.RED.TRUCKS, HUGE.GREY.TRUCKS MemberOf : CLASSES.OF.PHYSICAL.OBJECTS MemberSlot : HEIGHT from PHYSICAL.OBJECTS MemberSlot : LENGTH from PHYSICAL.OBJECTS OwnSlot : LONGEST from CLASS.OF.PHYSICAL.OBJECTS OwnSlot : TALLEST from CLASS.OF.PHYSICAL.OBJECTS

I-1. Structural Features: 

I-1. Structural Features I-1-2. Attribute Descriptions Slots can have multiple values and set of properties, facets Facets constraining number of values for an attribute represented by a slot CardinalityMin value of m attribute has at least m distinct values CardinalityMax value of n attribute has at most n distinct values

I-1. Structural Features: 

Unit : TRUCK1 in knowledge base TRANSPORTATION Member : THINGS.OWNED.BY.PAUL, HUGE.GREY.TRUCKS OwnSlot : OWNER ValueClass : MEN (UNION DOCTORS LAWYERS) (NOT.ONE.OF FRED) Cardinality.Max : 1 Values : PAUL OwnSlot : WHEELS from HUGE.GREY.TRUCKS Cardinality.Min : 16 Comment : “The vehicle’s wheels” Values : Unknown I-1. Structural Features Cardinality.Min facet of the WHEEL slot → The truck must have at least 16 wheels ValueClass facet of the OWNER slot → Its owner must be a man who is either a doctor or a lawyer and not Fred

I-2. Behavioral Properties: 

I-2. Behavioral Properties Frame languages no specific facilities for declaratively describing behavior but various ways of attaching procedural information expressed in some other languages

I-2. Behavioral Properties: 

I-2. Behavioral Properties Two standard forms of procedural attachment Methods LISP procedures attached to frames that respond to messages sent to the frames Active values Procedures or collections of production rules attached to slots that are invoked when the slot’s values are accessed or stored Behave like ‘demons’ monitoring changes and uses of the values

I-2. Behavioral Properties: 

Frame : TRUCKS Superclasses : VEHICLES Subclasses : BIG.NON.RED.TRUCKS, HUGE.GREY.TRUCKS MemberOf : CLASSES.OF.PHYSICAL.OBJECTS MemberSlot : DIAGNOSE from TRUCKS Inheritance : METHOD Comment : “A method for diagnosing electrical faults”... MemberSlot : LOCATION from PHYSICAL.OBJECTS ActiveValues : UPDATE.LOCATION I-2. Behavioral Properties DIAGNOSE slot - a method for diagnosing electrical faults Demon (ActiveValues facet) - update whenever the slot’s value changes

I-3. Reasoning services: 

I-3. Reasoning services I-3-1. Inheritance Frame can have a member link to one or more class frames A frame is said to inherit the member slots of the class frames to which it has member links Class frames can have subclass links to one or more other class frames A subclass frame inherits the member slots of its superclass frames

I-3. Reasoning services: 

I-3. Reasoning services I-3-2. ValueClass and CardinalityReasoning Value-class and cardinality specifications → constraints on the legal values of a slot An item is excluded if… the slot already has its maximum number of allowable values the item is not a member of the slot’s value class

II. Frames as a foundation for production-rule systems: 

II. Frames as a foundation for production-rule systems Frame-based representation facility is an important component of… the design of a production-rule language the reasoning facilities that interpreting rules supplies an expressively powerful language for describing the objects

II. Frames as a foundation for production-rule systems: 

Production-rule facility in the KEE system is represented as a frame is parsed by a method attached to the frame II. Frames as a foundation for production-rule systems

II. Frames as a foundation for production-rule systems: 

Unit : BIG.NON.RED.TRUCKS.RULE in KB TRANSPORTATION Member : TRUCK.CLASSIFICATION.RULES OwnSlot : EXTERNAL.FORM from BIG.NON.RED.TRUCKS.RULE Inheritance : SAME OwnSlot : PARSE from RULES Inheritance : METHOD OwnSlot : PREMISE from BIG.NON.RED.TRUCKS.RULE Inheritance : UNION OwnSlot : ACTION from RULES Inheritance : UNION OwnSlot : ASSERTION from BIG.NON.RED.TRUCKS.RULE Inheritance : UNION EXTERNAL.FORM slot - contains the rule as the user wrote PARSE method - converts the rule into an internal form consisting of lists of expressions that are values of the PREMISE, ASSERTION, and ACTION slots II. Frames as a foundation for production-rule systems

II. Frames as a foundation for production-rule systems: 

Frame : PHYSICAL.OBJECTS Superclasses :… Subclasses :… MemberOf :… MemberSlot : COLOR Valueclass : … Cardinality.Min : 1 Cardinality.Max : 1 PHYSICAL.OBJECT is a class of objects having at most one color each II. Frames as a foundation for production-rule systems

II. Frames as a foundation for production-rule systems: 

Frame : TRUCKS Superclasses : PHYSICAL.OBJECTS Subclasses :… MemberOf :… MemberSlot : WHEELS Valueclass : … Cardinality.Min : 4 TRUCK is a subclass of PHYSICAL.OBJECTS II. Frames as a foundation for production-rule systems

II. Frames as a foundation for production-rule systems: 

Frame : HUGE.GREY.TRUCKS Superclasses : TRUCKS Subclasses :… MemberOf :… MemberSlot : COLOR from PHYSICAL.OBJECTS Valueclass : … Cardinality.Min : 1 Cardinality.Max : 1 Values : GREY MemberSlot : WHEELS from TRUCKS ValueClass : … Cardinality.Min : 16 HUGE.GREY.TRUCKS is a subclass of TRUCKS, the members of which have color grey and at least 16 wheels II. Frames as a foundation for production-rule systems

II. Frames as a foundation for production-rule systems: 

Frame : TRUCK1 MemberOf : HUGE.GREY.TRUCKS OwnSlot : WEIGHT Value : 15,000 TRUCK1 is a huge grey truck weighing 15,000 pounds II. Frames as a foundation for production-rule systems

III. Using frames to manage rule-based reasoning: 

III. Using frames to manage rule-based reasoning Frame-based representation facility provides a means of organizing and indexing modular collections of production rules

III. Using frames to manage rule-based reasoning: 

III. Using frames to manage rule-based reasoning III-1. Classification of situations An effective way to proceed → use a class-subclass taxonomy

III. Using frames to manage rule-based reasoning: 

III. Using frames to manage rule-based reasoning Physical objects Buildings Statues Vehicles Boats Trucks Automobiles Station wagons Coupes Sedans Is it a physical object? Is it a vehicle? Is it an automobile? Is it a sedan? Class-subclass frame taxonomy → Classification by successive refinement

III. Using frames to manage rule-based reasoning: 

III. Using frames to manage rule-based reasoning III-2. Reasoning from Significant Events The STAR-PLAN system Ford Aerospace and Communication Corporation An intelligent aid to human satellite operators in the diagnosis and correction of satellite malfunctions An interesting example of how reasoning based on responses to significant events can be controlled

III. Using frames to manage rule-based reasoning: 

III. Using frames to manage rule-based reasoning III-2. Reasoning from Significant Events The STAR-PLAN system The system makes effective use of frames, including prototype expert frames that are instantiated and deleted dynamically as needed during operation of the system The use of frames to build the system’s models allowed the designers to organize them so that the knowledge could be easily accessible and comprehensible to both diagnostic experts and satellite operators

Conclusions: 

Conclusions The characteristic features of frame-based knowledge representation facilities how they can provide a foundation for a variety of knowledge-system functions how frames can contribute to a knowledge system’s reasoning activities how they can be used to organize and direct those activities

Conclusions: 

Conclusions The advantages of integrating frames and production rules into a single unified representation facility → Hybrid facility makes the organizational and expressive power of object-oriented programming available to domain experts who are not programmers makes knowledge-system technology directly available to the application-domain experts who most need it to solve their problems

Q&A 1.Frame Theory vs. OOP: 

Q&A 1.Frame Theory vs. OOP Frame Theory 인공지능분야에서 지식표현의 기본적인 연구방식 중 하나 인간의 지식을 프레임이라고 부르는 자료구조를 사용하여 표현 지적활동(언어이해, 패턴인식, 문제해결…)은 외부로부터의 입력과 내부 프레임과의 상호작용으로 간주 예 KRL(Knowledge Representation Language) FRL(Frame Representation Language) UNIT

Q&A 1.Frame Theory vs. OOP: 

Q&A 1.Frame Theory vs. OOP OOP 프로그래밍에 객체의 개념을 도입하여 프로그램의 재사용 가능성을 높임으로써 생산성을 향상시키려는 연구 예 Smalltalk-80 C++ Objective C OOPSLA

Q&A 2. Production Rule: 

Q&A 2. Production Rule 인공지능기법을 이용하여 문제를 해결하는 방법중 하나 ‘If~ then~’의 형태로 표현되는 인간의 인지적인 모델을 기반으로 하는 문제해결 방법 주요요소 규칙의 집합 : 규칙의 정의와 수행 데이터베이스 : 문제풀이를 위한 구조화된 정보 제어전략 : 규칙과 데이터베이스의 정보와 비교되는 순서제어, 규칙충돌 해결

Q&A 3. Fine-grained structure: 

Q&A 3. Fine-grained structure Granularity 구문(context)에 있어서의 코드 단위의 크기 Fine-grained structure 각 task가 코드의 크기와 수행시간에 비해 작다. 병렬성 증가, 속도향상 synchronization, communication의 overhead 증가 Coarse-grained structure

Q&A 4. Predicate calculus: 

Q&A 4. Predicate calculus 1st order Predicate Calculus (1차 서술논리) 수학적 논리학에서 사실이나 개념을 표현하는 방법 인공지능분야에서 많이 사용 서술논리문 > Well-Formed Formula > 기호 기호 (상수심볼, 변수심볼, 함수심볼, 서술심볼(;문장)) 예 MAN(KIM) COLOR(ELEPHANT, GRAY) DOCTOR(JOE)^HUSBAND(JOE, MARY) (Ax)[MAN(x)=>DIE(x)], (Ex)[MAN(x)^~DIE(x)] 한정사는 서술심볼을 한정하지않고 변수만을 한정 → 1차서술 논리문