Transcript ICT619 Intelligent Systems

ICT619 Intelligent
Systems
Topic 2: Expert Systems
Expert Systems
PART A (last week)
 Introduction
Applications of expert systems
 Structure of an expert system
 An example rule base
 Reasoning in a rule-based expert system
 Reasoning using forward and backward chaining
 Dealing with uncertainty
PART B
 Frame-based expert systems
 Developing expert systems
 Advantages and disadvantages of expert systems
 Case studies
ICT619
2
PART B
 Frame-based expert systems
 Developing expert systems
 Advantages and disadvantages of
expert systems
 Case Studies
ICT619
3
Frame-based expert systems – what
is a frame? (Negnevitsky, 2005)
 A frame is a data structure
with typical knowledge about
a particular object or concept.
 Frames were first proposed
by Marvin Minsky in the
1970s.
 Each frame has its own name
and a set of attributes
associated with it. Carrier,
Name, Flight, Date, … Gate
are slots in the frame
Boarding pass.
ICT619
QANTAS BOARDING PASS
AI
Carrier:
QANTAS AIRWAYS
Ca
Name:
MR N BLACK
Na
Flight:
QF 612
Fl
Date:
29DEC
Da
Seat:
23A
Se
From:
HOBART
Fr
To:
MELBOURNE
To
Boarding:
0620
Bo
Gate:
2
Ga
4
Frame-based expert systems – what
is a frame? (cont’d)
 Frames provide a natural, concise way to represent knowledge.
 Frames are an early application of object-oriented programming
for expert systems.
 A knowledge engineer refers to, what is an equivalent of an object
in OOP, as a frame
ICT619
5
Object-oriented Programming

Object-Oriented Programming (OOP) is a programming method that
uses instances (known as objects) of different classes of entities for
problem solving

A class in OOP defines an abstraction of entities with a common set of
characteristics (attributes) and behaviours

An example of an attribute is a variable type such as a string. An entity
('message') might have an attribute ('type::string') with value ("Hello to
everybody listening!"). Or an entity ('cat') might have an attribute ('colour')
with value ('white')

Entities often have a list of attribute-value pairs

Behaviours are represented by procedures applicable to objects of that
class (called methods in OOP).
ICT619
6
Frames as a knowledge
representation technique
 The concept of a frame is defined by a collection of slots.
 Each slot describes a particular attribute or operation of the frame.
 Slots are used to store values.
 A slot may contain a default value, a pointer to another frame, a
set of rules or procedure by which the slot value is computed.
 Such procedures are executed only when the slot in which they sit
is accessed
ICT619
7
Classes and instances
 A group of similar objects belong to a class
 The word frame may refer to a particular object or instance of a
class
 To be more precise, a class-frame describes a group of objects
with common attributes.
 Instance-frame refers to a particular object
- Animal, person, car and computer are all class-frames.
- Mammal, Jane Doe, Toyota, Dell Inspiron are all instanceframes.
 Frame-based systems are characterized by inheritance.
 Inheritance is the process by which all characteristics of a classframe are assumed by an instance-frame as well as any subclasses.
ICT619
8
A Class Frame
CLASS:
[Str]
[Str]
[Str]
[Str]
[Str]
[Str]
[Str]
[Str]
[Str]
[Str]
[Str]
[N]
[Str]
Computer
Item Code:
Model:
Processor:
Memory:
Hard Drive:
Floppy:
CD-ROM:
Mouse:
Keyboard:
Power Supply:
Warranty:
Cost:
Stock:
[Default]
3.5”; 1.44MB
[Default]
[Default]
145 Watt
3 years
[Initial]
In stock
ICT619
9
Two Instance Frames
INSTANCE: IBM Aptiva S35
INSTANCE: IBM Aptiva S9C
Class:
[Str]
[Str]
[Str]
[Str]
[Str]
[Str]
[Str]
[Str]
[Str]
[Str]
[Str]
[N]
[Str]
Class:
[Str]
[Str]
[Str]
[Str]
[Str]
[Str]
[Str]
[Str]
[Str]
[Str]
[Str]
[N]
[Str]
Computer
Item Code:
SY7973
Model:
IBM Aptiva S35
Processor:
Pentium 233MHz
Memory:
48MB
Hard Drive:
6.4GB
Floppy:
3.5"; 1.44MB
CD-ROM:
24X
Mouse:
Cordless Mouse
Keyboard:
104-key
Power Supply: 145 Watt
Warranty:
3 years
Cost:
1199.99
Stock:
In stock
ICT619
Computer
Item Code:
SY7975
Model:
IBM S9C
Processor:
Pentium 200MHz
Memory:
32MB
Hard Drive:
4.2GB
Floppy:
3.5"; 1.44MB
CD-ROM:
16X
Mouse:
2-button mouse
Keyboard:
104-key
Power Supply: 145 Watt
Warranty:
3 years
Cost:
999.99
Stock:
In stock
10
Methods and Demons
 Expert systems are required not only to store the knowledge but
also to validate and manipulate this knowledge.

To add actions to frames, a procedures is associated with a frame
attribute that is executed whenever requested.
 Frame procedures are known as methods and demons
 Demons are limited to IF-THEN statements, but methods can be
more complex.
ICT619
11
Methods and Demons (cont’d)
 Most frame-based expert systems use two types of methods:
WHEN NEEDED and WHEN CHANGED

A WHEN NEEDED method is executed when information
associated with a particular attribute is needed for solving the
problem, but the attribute value is undetermined.
 A WHEN CHANGED method is executed immediately when the
value of its attribute changes.
 The following simple example illustrates the use of WHEN
CHANGED methods in a class at run-time.
ICT619
12
An ES to assist a loan officer in evaluating credit
requests from small business ventures

A credit request is to be classified into one of three categories,
“Give credit”, “Deny credit” or “Consult a superior”.

When a loan officer provides a qualitative rating of the expected
yield from the loan, the expert system:
1. Compares the business collateral with the amount of credit
requested
2. Evaluates a financial rating based on a weighted sum of




the business’s net worth to assets
last year’s sales growth
gross profit on sales and
short-term debt to sales
3. Determines a category for the credit request.
ICT619
13
Input display for the request selection
Credit Evaluation Advisor
Requested credit
50000
Currency deposit
50000
Stocks
9000
Mortgages
12000
List of Requests
No
CN001-98
CN002-98
CN003-98
CN001-98
Applicant Name
Mrs White, J.
Mr Black, N.
Mr Green, P.
Mr Clark, E.
Net worth to assets
40
Last year’s sales growth
20
Gross profit on sales
45
Previous
Next
9
First
Last
Short-term debt to sales
Expected yeld
Excellent
The Credit Evaluation Advisor
has determined the category of
the credit request as
Evaluate Credit
Collateral
Excellent
Financial rating
Help
Give Credit
Good
Restart
Exit
ICT619
14
The class Action Data and WHEN CHANGED methods
CLASS:
Action Data
[S] Goto Next:
[WHEN CHANGED]
[S] Goto Previous: [WHEN CHANGED]
[S] Goto First:
[WHEN CHANGED]
[S] Goto Last:
[WHEN CHANGED]
INSTANCE:
Action Data 1
Class:
Action Data
[S] Goto Next:
TRUE
[S] Goto Previous: UNDETERMINED
[S] Goto First:
UNDETERMINED
[S] Goto Last:
UNDETERMINED
WHEN CHANGED
BEGIN
Current Request Number := Request Number OF Request
FIND Request
LIMIT 1
WHERE Request Number OF Request > Current Request Number
FIND END
END
WHEN CHANGED
BEGIN
Target Request Number := Request Number OF Request - 1
IF Target Request Number > 0 THEN
BEGIN
FIND Request
LIMIT 1
WHERE Request Number OF Request = Target Request Number
FIND END
END
END
WHEN CHANGED
BEGIN
FIND Request
LIMIT 1
FIND END
END
WHEN CHANGED
BEGIN
Target Request Number := Total Number of Requests
FIND Request
LIMIT 1
WHERE Request Number OF Request = Target Request Number
FIND END
END ICT619
15
Class Request
CLASS:
Request
[Str] Applicant’s name:
[Str] Application no.:
[N] Requested credit:
[N] Currency deposits:
[N] Stocks:
[N] Mortgages:
[N] Net worth to assets:
[N] Last year's sales growth:
[N] Gross profits on sales:
[N] Short-term debt to sales:
[C] Expected yield
Excellent:
Reasonable:
Poor:
[N] Request Number:
ICT619
16
Instances of the Class Request
INSTANCE:
Request 1
Class:
Request
[Str] Applicant’s name:
Mrs White, J.
[Str] Application no.:
CN001-98
[N] Requested credit:
50000
[N] Currency deposits:
50000
[N] Stocks:
9000
[N] Mortgages:
12000
[N] Net worth to assets:
40
[N] Last year's sales growth: 20
[N] Gross profits on sales:
45
[N] Short-term debt to sales: 9
[C] Expected yield
Excellent:
TRUE
Reasonable:
FALSE
Poor:
FALSE
[N] Request Number:
1
INSTANCE:
Request 2
Class:
Request
[Str] Applicant’s name:
Mr Black, N.
[Str] Application no.:
CN002-98
[N] Requested credit:
75000
[N] Currency deposits:
45000
[N] Stocks:
10000
[N] Mortgages:
20000
[N] Net worth to assets:
45
[N] Last year's sales growth: 25
[N] Gross profits on sales:
35
[N] Short-term debt to sales: 10
[C] Expected yield
Excellent:
FALSE
Reasonable:
TRUE
Poor:
FALSE
[N] Request Number:
2
ICT619
17
Inference in a frame-based system
 Most frame-based expert systems allow the use of a set of rules to
evaluate information contained in frames.
 Similar to a goal-driven rule-based system, the inference engine in
a frame-based system also searches for the goal.
 But rules in such a system play an auxiliary role.
 Frames represent here a major source of knowledge, and both
methods and demons are used to add actions to the frames.
 Thus, the goal in a frame-based system can be established either
in a method or in a demon.
ICT619
18
Example: Evaluation of credit
request
 The expert system is expected to begin the evaluation
when the user clicks the Evaluate Credit pushbutton on
the input display.
 This pushbutton is attached to the attribute Evaluate
Credit of the class Credit Evaluation.
ICT619
19
The Credit Evaluation class, WHEN CHANGED
and WHEN NEEDED methods
CLASS:
Credit Evaluation
[S] Evaluate Credit:
[WHEN CHANGED]
[C] Collateral:
Excellent:
Good:
Moderate:
[C] Financial rating:
Excellent:
Good:
Medium:
Bad:
[C] Evaluation:
[WHEN NEEDED]
Give credit:
Deny credit:
Consult a superior:
WHEN CHANGED
BEGIN
PURSUE Evaluation OF Credit Evaluation
END
WHEN NEEDED
BEGIN
Evaluation OF Credit Evaluation IS Consult
superior := TRUE
END
ICT619
20
The rule-base
RULE 1
IF Currency deposits OF Request >= Requested credit OF Request
THEN Collateral OF Credit Evaluation IS Excellent
RULE 2
IF Currency deposits OF Request >= Requested credit OF Request * 0.7
AND (Currency deposits OF Request + Stocks OF Request) >= Requested credit OF Request
THEN Collateral OF Credit Evaluation IS Excellent
RULE 3
IF (Currency deposits OF Request + Stocks OF Request) > Requested credit OF Request * 0.6
AND (Currency deposits OF Request + Stocks OF Request) < Requested credit OF Request * 0.7
AND (Currency deposits OF Request + Stocks OF Request + Mortgages OF Request) >= Requested
credit OF Request
THEN Collateral OF Credit Evaluation IS Good
RULE 4
IF (Currency deposits OF Request + Stocks OF Request + Mortgages OF Request) <= Requested credit
OF Request
THEN Collateral OF Credit Evaluation IS Moderate
RULE 5
IF Net worth to assets OF Request * 5 + Last year's sales growth OF Request + Gross profits on sales OF
Request * 5 + Short term debt to sales OF RequestICT619
* 2 <= -500
21
THEN Financial rating OF Credit Evaluation IS Bad
Example: Evaluation of credit
request (cont’d)
 The WHEN NEEDED method attached to the attribute Evaluation
is used to establish its value.
 The inference engine executes this method when it needs to
determine the value of Evaluation.
 If based on the set of rules provided for credit evaluation, the
inference engine cannot establish the value of the attribute
Evaluation, the attribute Evaluation receives the value Consult a
superior.
 The task of developing a frame-based ES can be difficult for the
knowledge engineer due to the complexity of inheritance.
ICT619
22
Developing an expert system
- issues to be considered

Does the task require knowledge available from human experts?

Are human experts too expensive and scarce?

Is the problem domain well-structured?
 Problem domain must be well-defined and formalised.
 Amount of knowledge required to solve such problems should not be "too
large".
 No commonsense reasoning (that can't be reduced to rules)

Can the problem be solved by traditional computing methods?
Numerical, statistical or operations research methods, if applicable, are likely
to do better than heuristic solution

Are cooperative, articulate and enthusiastic human experts available?
 Expert can articulate reasoning process with a high degree of confidence
 Expert convinced of the benefit of the ES, and does not feel threatened
 Expert has the time
ICT619
23
Developing an expert system
- issues (cont’d)

Adequate management support (expert's boss has to be on board)

How big and complex is the problem?

Available technology must be able to handle required knowledge base
efficiently

Is development cost justified by returns?

Is the solution found likely to remain valuable for several years to come?

The cost (and availability) of the human expert needs to be compared
with the cost of developing the ES

Cost can be reduced by development tools like ES shells

Will there be adequate infrastructure and management support for ES
maintenance in future?
ICT619
24
Developing an expert system - the
people
1. The knowledge group (knowledge engineer + the domain
expert)
2. The developer group
3. The user group
 Knowledge engineer
 Usually a system analyst with background in AI
 extracts knowledge from domain expert and formalizes it
into a knowledge base
 decides on the




knowledge representation scheme
strategies for reasoning and searching the knowledge base
design of the user interface.
hardware and software.
ICT619
25
Knowledge engineer (cont’d)
 May not initially have any experience of the ES problem
domain (but tends to learn some during the project)
 Sessions with the domain expert are the usual method used
for knowledge gathering
 Machine learning techniques such as decision trees (subject
of a later topic) can also be used
 Time taken by knowledge acquisition process – approx. 60 to
70% of overall ES development time
ICT619
26
The Developer and User groups
The developer group
 Implements the expert system in close cooperation with the
knowledge group and the user group.
 Either programs the system from scratch or makes use of existing
software products like an expert system shell
The user group
Can be a regular user, eg, an employee of the organization
 May be an irregular user such as bank customer
 Needs and characteristics of both categories of users need to be
taken into account, particularly for the user interface design.
 The user must feel confident and happy with the system
 So a usability evaluation should be conducted with these people
ICT619
27
The expert system development
cycle
Development strategy

Early prototyping and incremental development

Mistakes found during development lead to correction and
addition to the knowledge base
Steps usually followed:
1.
Knowledge engineer gains familiarity with the problem domain
2.
Knowledge engineer and domain expert start knowledge
extraction (knowledge elicitation) process
Difficult because

Experts don't know how they know

Experts may disagree

Experts may be wrong, or fuzzy on details
ICT619
28
The expert system development
cycle (cont’d)
3. Knowledge engineer decides on representation scheme, search
strategy, user interface
4. Prototype built
5. Knowledge engineer and domain expert test prototype, corrects,
refines and redesigns if necessary
6. Final version built and evaluated.
ES knowledge base must be continuously updated by adding,
deleting or changing rules to keep up with new knowledge and
changed circumstances
ICT619
29
Expert system shells
 A general expert system development product for the market
 An expert system shell has all components of an expert system except the knowledge-base
User
Interface:
Knowledgebase editor
- Menudriven
User
- GUI
Knowledge-base
Inference
engine
Working memory
- Natural
language
Explanation
sub-system
ICT619
30
Expert system shells (cont’d)
 Good shells also provide facilities for communication with external
sources including
 Database management systems
 Spreadsheets
 Graphics packages.
 Shell selected must match reasoning process (goal driven or data
driven) characterising given problem domain
 Other features to be considered
 knowledge representation scheme and the knowledge base
editor
 user interface
 explanation capabilities.
ICT619
31
Testing expert systems
Correctness of ES can not be guaranteed due to its heuristic nature
Some test strategies

Use of historical data
Data on existing cases fed to the system, and the outputs
analysed
Inconsistency of human decisions taken into account in case of
any difference between the data and ES

ES against Expert
ES tested against the expert by presenting both with hypothetical
or actual cases
Expert’s reasoning compared with that of the ES to make sure
both arrived at the same conclusion for the same reasons
ICT619
32
Testing expert systems (cont’d)
 Field tests
Users in the field use the system for a given period of time
Favourable results in the field add to ES validity
Serious problems in field tests indicate need for further
improvement of the design
 Turing test
ES and a human expert are subjected to blind user evaluation
User’s failure to differentiate between answers produced by the
two enables the ES to pass
ICT619
33
Some limitations of expert systems
 Knowledge acquisition remains the major bottleneck in applying
ES technology to new domains.
 Not adaptive
Knowledge engineer responsible for revising and maintaining
system.
 Evaluating expert system correctness is difficult
 Explanation of an outcome in terms of the reasoning process can
be time consuming for large amounts of data
ICT619
34
Some limitations of expert systems
(cont’d)
 Self-explanatory individual rules, but difficult to relate to overall
strategy due to lack of hierarchy
 Maintenance and extension of a rule base can be difficult for a
relatively large rule base (beyond 100 rules).
 ES are not as compact as neural network and genetic algorithm
systems.
This makes them harder to embed in other systems, as the
inference engine and working memory must be part of the system
at run-time.
ICT619
35
Case Studies
Case 1: An Expert System for Pattern Directed Data Mining of
Point-Of-Sale Data (see Dhar & Stein pp.244-).
Objective
 Supermarkets need to know how different product categories
performed over certain periods of time in particular regions and
nationally
 Some experts are able to detect significant trends in these data –
what is happening in the market place?
 A.C. Nielsen wanted to create an expert system with this expertise
and make it available to its sales reps
ICT619
36
Case 1: An Expert System for
Pattern Directed Data Mining
Requirements and constraints
 Enable reps to put together a clear and unambiguous story for
their customer
 Use vocabulary commonly used by sales reps
 Able to work with Nielsen’s databases
 Be distributable on low-end PCs to sales reps across the country
 Reports able to be produced under five minutes\
 High explainability to enable reps to construct stories
 Six months development time – Nielsen wanted to leap frog rival
ICT619
37
Case 1: An Expert System for
Pattern Directed Data Mining
(cont’d)
Objectives and constraints were clear, but not so outputs – eg, use of
imprecise linguistic terms
 Decision:- Produce outputs to focus attention on areas of unusual
activity (eg, abnormal shift in sales volume, market share, price)
accompanied by associated factors to explain observation
 Problem domain not complex but universally (across all products,
regions, seasons) applicable principles were difficult to identify
 Decision:- System to be flexible with parameterizable rules to suit
specific circumstances
 Market data was of high quality
ICT619
38
Case 1: An Expert System for
Pattern Directed Data Mining
(cont’d)
Implementation
 The ES SPOTLIGHT was implemented using a rule based control
engine written in C
 Sales database and rule base were 15 segments
 Loaded one segment at a time due to memory constraints
 Results of running each rule base on each segment of data
integrated into final report
Results
 Completed in 1991, SPOTLIGHT proved highly popular with sales
reps and their clients
 Demonstrated feasibility of expert systems based on conventional
technology - written in C for a PC platform, rather than in an AI
language such as LISP for AI workstation
 First (?) successful data mining application of an expert system
Case 1: An Expert System for
Pattern Directed Data Mining
(cont’d)
Some limitations
 Gave limited analyses, and not interactive as a decision support
tool
 Provided insight into what was happening in the market place, but
not what action to take to follow up
 Parameterizing rules was not a good long-term solution to making
rules sensitive to market context
 Nielsen developed an object-oriented version called Opportunity
Explorer (OE) with a Windows-based GUI interface
 Rules in OE could be attached to classes of consumer goods, so
analysis became automatically sensitive to context
ICT619
40
REFERENCES

AI Expert, October 1991 – presents applications of expert systems

Dhar, V., & Stein, R., Seven Methods for Transforming Corporate Data
into Business Intelligence., Prentice Hall 1997, Ch 7

Giarratano, J., & Riley, G. Expert Systems Principles and Programming,
Thomson Course Technology, 2005.

Negnevitsky, M. Artificial Intelligence A Guide to Intelligent Systems,
Addison-Wesley 2005.
(Source of slides on frame-based systems used in this presentation )

Zahedi, F., Intelligent systems for Business, Wadsworth Publishing,
Belmont, California, 1993.
ICT619
41