KBS : Knowledge-Based System Design Material

KBS : Knowledge-Based System Design ... validation and verification of the tools used ... the linear model of ES development is an adaptation of the...

0 downloads 45 Views 320KB Size

KBS : Knowledge-Based System Design ‹ Motivation ‹ Chapter ‹ ‹ ‹

Engineering and ES Design

‹ ‹ ‹ ‹ ‹ ‹



Review of relevant concepts Overview new topics Terminology

‹ ES

[Awad 1996] ‹ Chapter 5: Expert System Development Life Cycle ‹ Chapter 15: Verification and Validation ‹ Chapter 17: Implementing the Expert System ‹ Chapter 18: Organizational and Managerial Impact

‹ Software

‹ Objectives

‹ Linear ‹

Development Life Cycle

Feasibility Study Rapid Prototype Refined System Field Testable Commercial Quality Maintenance and Evolution

Software Development Life Cycle

‹ ‹ ‹

Model ES Life Cycle

Planning Knowledge Definition Knowledge Design Knowledge Verification

‹ Important

Concepts and Terms ‹ Chapter Summary

[Durkin 1994] ‹ ‹ ‹ ‹

Chapter: 8: Designing Backward-Chaining Rule-Based Systems Chapter 10: Designing Forward-Chaining Rule-Based Systems Chapter 15: Designing Frame-Based Expert Systems Chapter 18: Knowledge Engineering

KBS Design 1

KBS Design 2



[Sommerville 2001] ‹ Chapter 3: Software processes ‹ ‹


‹ ‹

to study the concepts and methods in the

chapter ‹ main

spiral model

advantages benefits

‹ potential

formal methods reuse-based methods

‹ Chapter ‹

‹ reasons

waterfall model evolutionary development

‹ understanding ‹ relationships

8: Software prototyping

rapid prototyping techniques

of the concepts and methods to other topics in the same or related


[Jackson 1999] ‹ Chapter 14, 15: Constructive Problem Solving ‹ Chapter 16: Designing for Explanation KBS Design 3

KBS Design 4



ES Development Methods

‹ regurgitate ‹

‹ commercial

quality systems require a systematic development approach

basic facts and concepts

‹ understand ‹ ‹ ‹ ‹

‹ ad

hoc approaches may be suitable for research prototypes or personal use, but not for widely used or critical systems

elementary methods more advanced methods scenarios and applications for those methods important characteristics ™

differences between methods, advantages, disadvantages, performance, typical scenarios

‹ some

software engineering methods are suitable for the development of expert systems

‹ evaluate ‹

application of methods to scenarios or tasks

‹ apply ‹

methods to simple problems

KBS Design 5

KBS Design 6

Problem Selection

Project Management

‹ the

development of an expert system should be based on a specific problem to be addressed by the system ‹ it should be verified that expert systems are the right paradigm to solve that type of problem ‹ not

all problems are amenable to ES-based solutions

‹ availability

‹ activity


‹ planning,

‹ product

‹ product ‹ change

‹ resource

of resources for the development

scheduling, chronicling, analysis

configuration management management management


‹ need

determination ‹ acquisition resources ‹ assignment of responsibilities ‹ identification of critical resources

‹ experts/expertise ‹ hardware/software ‹ users ‹ sponsors/funds

KBS Design 7

KBS Design 8


ES Development Stages ‹ feasibility ‹ ‹

prototype system


system tested by selected end users

‹ commercial ‹

quality system

deployed to a large set of end users

‹ maintenance ‹ ‹

errors errors ‹ syntax errors ‹ inference engine errors ‹ inference chain errors ‹ limits of ignorance errors ‹ semantic

in-house verification by knowledge engineers, experts

‹ field ‹

‹ knowledge

quick and dirty implementation of the main idea(s)

‹ refined ‹


paper-based explanation of the main idea(s) no implementation

‹ rapid ‹

Error Sources in ES Development

and evolution

elimination of bugs additional functionalities KBS Design 9

KBS Design 10

Knowledge Errors

Semantic Errors

‹ problem:

knowledge provided by the expert is incorrect or incomplete ‹ reflection

of expert’s genuine belief of important aspects ‹ inadequate formulation of the knowledge by the expert ‹ omission

‹ consequences

solution not found ‹ wrong conclusions

‹ knowledge

engineer encodes rules that do not reflect what the domain expert stated ‹ expert misinterprets questions from the knowledge engineer ‹ incorrect

knowledge, inappropriate solutions, solutions not


‹ remedy ™

the meaning of knowledge is not properly communicated

‹ consequences

‹ existing

‹ validation

‹ problem:

‹ remedy

and verification of the knowledge

‹ formalized

may be expensive

‹ validation KBS Design 11

protocol for knowledge elicitation of the knowledge base by domain experts KBS Design 12


Syntax Errors

Inference Engine Errors

‹ problem:

rules or facts do not follow the syntax required by the tool used ‹ knowledge

engineer is not familiar with the method/tool ‹ syntax not clearly specified ‹ consequences ‹ knowledge

‹ problem:

malfunctions in the inference component of the expert system ‹ bugs ‹ resource ™


e.g. memory

‹ consequences

can’t be used

‹ system

crash solutions ‹ existing solutions not found

‹ solutions

‹ incorrect

‹ syntax

checking and debugging tools in the ES development environment

‹ remedy ‹ validation

and verification of the tools used

KBS Design 13

Inference Chain Errors

Limits of Ignorance Errors

‹ problem:

although each individual inference step may be correct, the overall conclusion is incorrect or inappropriate ‹ causes:

errors listed above; inappropriate priorities of rules, interactions between rules, uncertainty, nonmonotonicity

‹ consequences ‹ inappropriate

KBS Design 14

‹ problem:

the expert system doesn’t know what it doesn’t know ‹ human

experts usually are aware of the limits of their expertise

‹ consequences ‹ inappropriate ‹ incorrect


confidence in conclusions conclusions

‹ remedy

‹ remedy

‹ meta-reasoning

methods that explore the limits of the knowledge available to the ES

‹ formal

validation and verification ‹ use of a different inference method KBS Design 15

KBS Design 16


KBS and Software Engineering ‹ software

process models

Generic Software Process Models ‹ waterfall

‹ waterfall

and distinct phases of specification and development

‹ spiral

‹ use ‹ ES


‹ separate

of SE models for ES development development models

‹ evolutionary


‹ specification

‹ evolutionary

model ‹ incremental model ‹ spiral model

‹ formal

and development are interleaved

systems development


mathematical system model is formally transformed to an implementation

‹ reuse-based ‹ the


system is assembled from existing components

KBS Design 17

[Sommerville 2001]

KBS Design 18

Suitability of Software Models for ES Development

Waterfall Model Requirements definition

‹ the

following worksheets help with the evaluation of software models for use in the development of expert systems

System and software design

identify the key differences between conventional software development and ES development

‹ ‹

what are the positive and negative aspects of the model for ES development evaluate the above issues, and give the model a score


determine the overall suitability


Implementation and unit testing Integration and system testing


Operation and maintenance

[Sommerville 2001]


KBS Design 19

™ ™

with respect to a specific model

10 for perfectly suited, 0 for completely unsuitable high, medium low explanation

KBS Design 20


Evolutionary Development

Evolutionary Development ‹ exploratory

Concurrent activities


‹ objective

is to work with customers and to evolve a final system from an initial outline specification. should start with well-understood requirements

‹ throw-away


Initial version


Intermediate versions


Final version


‹ objective

is to understand the system requirements. should start with poorly understood requirements

[Sommerville 2001]

KBS Design 21

Incremental Development ‹ development

Outline description

[Sommerville 2001]

KBS Design 22

Incremental Development

and delivery is broken down into

increments ‹ each

‹ user

increment delivers part of the required functionality

requirements are prioritised

highest priority requirements are included in early increments

Define outline requirements

Assign requirements to increments

Design system architecture

‹ the

the development of an increment is started, the requirements are frozen

Develop system increment

Validate increment

Integrate increment

‹ once

‹ requirements

Validate system Final system

System incomplete

for later increments can continue to evolve

[Sommerville 2001]

KBS Design 23

[Sommerville 2001]

KBS Design 24


Spiral Development

Spiral Model Sectors

‹ process

is represented as a spiral rather than as a sequence of activities with backtracking ‹ each ‹ no ™

loop in the spiral represents a phase in the process. fixed phases such as specification or design

loops in the spiral are chosen depending on what is required

‹ risks

are explicitly assessed and resolved throughout the process

‹ similar

‹ for

quadrants in the coordinate system represent specific aspects ‹ objective ™

‹ risk ™

assessment and reduction

risks are assessed and activities put in place to reduce the key risks

‹ development ™

to incremental development


specific objectives for the phase are identified

and validation

a development model for the system is chosen which can be any of the generic models

‹ planning ™

[Sommerville 2001]

KBS Design 25

[Sommerville 2001]

Spiral Model Determine objectives alternatives and constraints

Risk analysis Risk analysis Risk analysis

Prototype 3 Prototype 2


Plan next phase

Operational protoype

Risk analysis Prototype 1

S/W requirements

Development plan

Requirement validation

Integration and test plan

Design V&V Service

[Sommerville 2001]

‹ based

on the transformation of a mathematical specification through different representations to an executable program ‹ transformations are ‘correctness-preserving’ ‹ it

Simulations, models, benchmarks Concept of Operation

KBS Design 26

Formal systems development Evaluate alternatives identify, resolve risks

Requirements plan Life-cycle plan

the project is reviewed and the next phase of the spiral is planned

Acceptance test

Product design

Detailed design

Code Unit test

is straightforward to show that the program conforms to its specification

‹ embodied

in the ‘cleanroom’ approach to software development

Integration test Develop, verify next-level product

KBS Design 27

[Sommerville 2001]

KBS Design 28


Formal Transformation Model

Reuse-Oriented Development ‹ based

Formal transformations T2 T3


on systematic reuse

‹ systems

are integrated from existing components or COTS (commercial-off-the-shelf) systems


‹ process Formal specification





Executable program





‹ component

analysis modification ‹ system design with reuse ‹ development and integration ‹ requirements

‹ this

approach is becoming more important but still limited experience with it

Proofs of transformation correctness

[Sommerville 2001]

KBS Design 29

[Sommerville 2001]

Reuse-oriented development

KBS Design 30

Model Worksheets Aspect



key differences

Requirements specification

Component analysis

Requirements modification

System design with reuse

Development and integration


System validation


‹ overall ‹ [Sommerville 2001]

KBS Design 31





explanation KBS Design 32


Generic System Design Process

System Evolution

Requirements specification Design activities Architectural design

Abstract specification

Interface design

Component design

Data structure design

Algorithm design

System architecture

Software specification

Interface specification

Component specification

Data structure specification

Algorithm specification

Define system requirements

Modify systems

Propose system changes

Assess existing systems

Existing systems

New system

Design products

[Sommerville 2001]

KBS Design 33

[Sommerville 2001]

Linear Model of ES Development ‹ the

Linear Model Diagram Knowledge Baseline

life cycle repeats a sequence of stages

Design Baseline

Product Baseline

Work Plan

KBS Design 35

Knowledge Review

Prelim. Data Review

Knowl. System Design Review

Test Readiness Review

System Evaluation

Test Analysis

Knowledge Verification Formal Test

definition design ‹ code & checkout ‹ knowledge verification ‹ system evaluation ‹ knowledge

Detailed Design

‹ knowledge

Knowledge Design Definition

‹ planning

Knowledge Definition Source Identification & Selection

‹ stages


‹ once

Code & Checkout

‹ variation

Acquisition Analysis & Extraction

of the incremental model iteration of the sequence roughly corresponds to one circuit in the spiral model

KBS Design 34

Test Audit Review

Fina Interm Revie

KBS Design 36



Knowledge Definition ‹ knowledge

source identification and selection

‹ feasibility

assessment management ‹ task phasing ‹ schedules ‹ high-level requirements ‹ preliminary functional layout ‹ resource

‹ ‹ ‹ ‹

‹ knowledge

acquisition, analysis and extraction

source identification source importance source availability source selection

‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹

acquisition strategy knowledge element identification knowledge classification system detailed functional layout preliminary control flow preliminary user’s manual requirements specifications knowledge baseline

KBS Design 37

KBS Design 38

Knowledge Design ‹ knowledge ‹ ‹ ‹ ‹ ‹


‹ detailed

knowledge representation detailed control structure internal fact structure preliminary user interface initial test plan

‹ ‹ ‹ ‹ ‹

Knowledge Verification


design structure implementation strategy detailed user interface design specifications and report detailed test plan


formal tests ‹ ‹

test procedures test reports

‹ ‹ ‹

coding tests source listings

‹ ‹

‹ ‹

results evaluation recommendations



summarized version of the activity from the previous stage

‹ recommendations ‹


test analysis

System Evaluation ‹ results

Code & Checkout


user manuals installation and operations guide system description document

as above

‹ validation ‹

system conforms to user requirements and user needs

‹ interim KBS Design 39

or final report KBS Design 40


Linear Model Exercise ‹ apply

Summary Expert System Design ‹ the

the linear model to your team project

‹ map

activities, tasks, milestones and deliverables that you have identified to the respective stages in the linear model ‹ use the linear model to sketch a rough timeline that involves two iterations ™ ™

first prototype final system

design and development of knowledge-based systems uses similar methods and techniques as software engineering ‹ some

modifications are necessary linear model of ES development is an adaptation of the incremental SE model

‹ the

‹ possible

‹ estimate

the overhead needed for the application of the linear model in our context

KBS Design 41

sources of errors are

‹ knowledge

and limits of knowledge errors and semantical errors ‹ inference engine and inference chain errors ‹ syntactical

KBS Design 42

Important Concepts and Terms ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹

evolutionary development expert system (ES) expert system shell explanation feasibility study inference inference mechanism If-Then rules incremental development knowledge knowledge acquisition knowledge base knowledge-based system

‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹

knowledge definition knowledge design knowledge representation knowledge verification limits of ignorance linear model ES life cycle maintenance rapid prototyping reasoning rule semantic error software development life cycle spiral development syntactic error waterfall model

KBS Design 43