VP-Expert Primer

VP-Expert Primer

CIS 824: Artificial Intelligence in Decision Making



Contents:

VP-Expert is the expert system shell we will be using for this course. Like any shell, it contains everything needed for running the expert system (except for the knowledge base of rules for the particular domain). This includes: Note that this is a student version of VP-Expert, which means that some options will not be available, and that the size of your knowledge bases will be limited.

Running VP-Expert

You may either install VP-Expert on your own computer, or use your disk in one of the PCs in rooms 301-303 (302 works best). In either case, VP-Expert is designed to be run from DOS.

To run it, go to the disk and/or directory containing the files and type vpx

The VP-Expert main menu

Options from any menu can be selected by using the arrow keys, pressing a function key, a digit, or using the first letter of the option name. The line below the menu also shows the sub-menu (if any) of the option currently highlighted. Important options from the main menu are:

Editbuilt-in editor for creating and modifying a knowledge base
Consultexecute the expert system on the current knowledge base
Filenameselect another knowledge base (from the current directory) for editing or consulting
Pathchange the current drive or directory from which knowledge bases are selected
QuitExit VP-Expert

The Escape key can always be used to go back a step, in particular, to `escape' an option that has been selected. A consultation can be aborted by pressing Ctrl-C.

If no file is preselected (using the Filename option) both Edit and Consult will prompt for the file name. The user can than type a file name or select a file from the displayed list. For Edit, the file name may be new, if a new file is to be created (VP-Expert will prompt you to enter the new filename).


Running a Consultation


The process of using VP-Expert to solve a specific problem, based on the rules in its knowledge base, is called a "consultation." In general, the user does not put queries directly to the system (this is done in the ACTIONS section of the knowledge base), but does enter answers to questions relevant to the query.

To start a consultation, choose Consult from the main menu, and then choose Go

The consultation screen contains three windows:

The bottom windows are useful for `debugging' a knowledge base. When no longer needed, they can be made to disappear by inserting a RUNTIME statement in your knowledge base (see below).

Inputing Data to a Consultation

In order to answer a query, VP-Expert uses backward chaining to work from a goal to questions (a question being defined as any proposition which does not appear in the THEN part of any rule). When an answer to a question is needed, the question is presented to the user, possibly along with a menu of possible answers.

Extracting Explanations for a Consultation

VP-Expert also allows you to see explanations of how a variable was set, or why a question was asked. This can be done when the program is running by pressing the / key (which halts execution temporarily) and then selecting the desired option from the menu.

If how is selected, VP-Expert will then provide a menu of the variables used in the program. It will then print the BECAUSE part (see below) of the rule used to give that variable its value (if any).

If why is selected, VP-Expert will print the BECAUSE part (see below) of the rule responsible for causing the current question to be asked.

Performing a Trace of a Consultation

You can also save a copy (called a trace) of the inference tree created in the course of a consultation. This can allow you to examine in detail the reasoning process of the system, and is particularly useful for debugging.

To perform a trace:

A record of the rules consulted and facts found during the consultation will now be stored in some file filename.trc, where filename is the name of the knowledge base being consulted.

You can view or print it from your own editor, or you can view it directly from VP-Expert by choosing Tree and Text from the main menu.




Creating a Knowledge Base in VP-Expert

Basic structure of a Knowledge Base

Creating an expert system with VP Expert is basically a question of entering a knowledge base which consists of three parts:
ACTIONS
RULES
QUERY STAEMENTS

At the center of the process are variables, which take the place of propositions in VP-Expert. The main goal of the inference engine is usually to find a value for some ``goal'' variable(s), using backward chaining to seach for rules that would assign a value to that variable as part of its consequent.

Note that you can create comments using the ! symbol; the rest of the line after the ! will be ignored by VP-Expert:

! this is a comment
As with any other program, you are strongly encouraged to comment your code, particularly to explain the reasoning and/or source of your rules.


The ACTIONS block

The ACTIONS block consists of statements which control the actions of the shell. These statements are executed in the order in which they appear (the only part of the KB that does). In effect, the ACTIONS block is the `code' which controls the execution of the inference engine.

The following is an example of a (minimal) ACTIONS block:

ACTIONS

DISPLAY "Welcome to the expert system
Press any key to begin.~"
FIND Decision
DISPLAY "The decision in this case is {#Decision}.";


Note that it begins with the word ACTIONS and terminates with a semicolon (no semicolons between statements).

The first DISPLAY statement tells the user what to do. The FIND statement expresses the system's goal. The last statement DISPLAYs the results. Details of each of these statement types are discussed below.

The FIND statement

The basic form of this statement is:
FIND variable

This statement activates the inference engine, causing it to consult the knowledge base of rules until a value is found for the variable.

This follows the backward chaining described in class:

Note that it is possible to have more than one FIND statement in the ACTIONS block -- however, it is rare that we actually do so. It is usually more efficient (usually less questions are asked) to have a single FIND to begin the consulting process, and to use rules to make sure that other values are only found when needed.

The DISPLAY statement

Any desired text may be displayed on the screen using a DISPLAY statement and enclosing the text in double quotation marks:

DISPLAY "This is some text to be displayed for the user - perhaps to give instructions on how to use the system"

If you want to make sure that the user has time to read a message before it disappears from the screen, insert a "~" as the last character in the message. This suspends all processing until the user presses some key on the keyboard. The "~" itself is not displayed. Be sure to tell the user how to make the system resume execution:

DISPLAY "Here are some instructions. Press any key to continue~"

The value of any variable may be included in a displayed message simply by enclosing the variable name in curly brackets:

DISPLAY "I prescribe {treatment} for your {diagnosis}."

Note that you can also put DISPLAY statements in the THEN or ESLE part of a rule. This can be particularly useful for providing explanations, or for displaying information only if a certain condition holds.

Controling the User Interface

The following commands are related to setting up the initial state of the user interface, and as such must be placed before the ACTIONS: The following statments may appear in the ACTIONS, or in the THEN or ELSE part of rules:

Creating windows in VP-Expert

You can also create your own windows on the VP-Expert screen. These are particularly useful for presnting information (such as instructions) that you don't want scrolled off the screen.

Windows are created with the WOPEN command:

WOPEN window#, toprow#, leftcol#, #ofrows, #ofcols, color#
where
window#a number (between 1 and 8) used to tell VP-Expert what the current window is
toprow#, leftcol#the Y and X coordinates respectively of the top left corner of the window
#ofrowsthe number of rows in the window (between 2 and 20)
#ofcolsthe number of columns in the window (between 2 and 77)
color#the background color of the window (see BKCOLOR above)

Since there may be several windows open at any time, we can tell VP-Expert which is the "active" one (that is where text will be printed) with the command:

ACTIVE window#

For example:

WOPEN 1, 1, 1, 4, 50, 2
opens a window in the upper left corner of the screen which is 4 rows by 50 columns and has a green background, and
ACTIVE 1
indicates to VP-Expert that it is now the active window.

A window can also be deleted with the command:

WCLOSE window#
However, this sometimes has the effect of deleting all windows on the screen.



Production Rules in VP-Expert

The production rules of an expert system contain its domain knowledge, expressed as IF-THEN type rules. Unlike the staements in the ACTIONS section, they are not run in the order listed; insetead they are consulted as needed during the process of backward chaining. The order of rules is only important when there is more than one rule that can be used to give a variable a value, as the inference engine attempt to prove the rules in the order given (see below for an example).

Basic form of rules

The basic form of a rule is as follows:
RULE rulename
IF antecedent
THEN consequent;
Every rule must have a unique name (up to 40 chars in length) after the word RULE (leaving this out is a very common source of syntax errors). Like any other label you use in programming, it should be descriptive of what the rule means.

An example (very simple) rule:

RULE Diagnosis_of_measles
IF   Diagnosis = measles 
THEN Treatment = penicillin;
In this case, Diagnosis and Treatment are variables, and measles and penicillin are potential values for those variables. In other words, this rule states that if Diagnosis has the value measles, we may then assign Treatment the value penicillin.

If the inference engine was currently trying to use this rule to FIND a value for the variable Treatment, it would:

Relational operators in rule antecedents

The IF part of a rule consists of one (or more) simple premises of the form:
variable relational_operator value
where relational_operator is one of the following:
=is equal to
<>is not equal to (used instead of NOT by VP-Expert)
<is less than
<=is less than or equal to
>is greater than
>=is greater than or equal to
The latter four operators are primarily used for numeric values (see below).

The ELSE statement

Rules may also contain an ELSEstatement as part of their consequent. For example:
RULE Diagnosis_of_flu
IF   Diagnosis = flu
THEN Treatment = bed_rest
ELSE Treatment = get_back_to_work;
If the variable Treatment has been assigned no other value by this point in the KB (by any rule, not just the THEN part of this rule), it is assigned the value given by the ELSE.

Logical operators

The IF part of a rule can be composed of up to 20 simple premises connected by the logical operators OR or AND.

For example:

RULE measles
IF   temperature = very_high
AND  spots = yes
AND innoculated <> yes
THEN Diagnosis = measles;
If VP-Expert is attempting to use this rule to find a value for Diagnosis, it will first check whether temperature is very_high (finding a value for temperature if necessary), then whether spots is yes, and so on.

For efficiency, VP-Expert gives up on such a rule immediately if it cannot prove one of the premises. For example, if temperature is not very_high, it does not try to find spots or innoculated.

OR is handled differently. For example, consider:

RULE allergy
IF spots = yes
OR rash = yes
THEN Diagnosis = allergy;
Even if VP-Expert can prove spots = yes, it will still ask about rash (even though it doesn't need to). To decrease the number of questions asked, you would have to write two separate rules:
RULE allergy1
IF spots = yes
THEN Diagnosis = allergy;

RULE allergy2
IF rash = yes
THEN Diagnosis = allergy;

Note also that OR has higher precedence than AND. For example, the rule:

RULE flu
IF   throat = sore
AND  temperature = high
OR   temperature = very_high
THEN Diagnosis = flu;
is interpreted as (throat = sore) AND (temperature = high OR temperature = very_high). Note also that you cannot use parentheses to change the order of evaluation -- instead, something like (A AND B) OR C -> D must be broken up into two rules of the form A AND B -> D and C -> D.

Numeric assignment and evaluation

As with other languages, VP-Expert also allows you to store numeric values in variables, and to manipulate them with arithmetic experessions. Since VP-Expert is more concerned with logic, however, the syntax for doing so is rather limited.

Variables
Numeric computations usually include variables on the right side of the operator in assignment or conditional statements (we have only seen values up to this point). However, since VP-Expert does not allow you to declare your variables, it needs some way to tell a variable (such as diagnosis) from a value (such as measles) when used on the right side of the experession. This is done by enclosing the variable on the right side of the expression in parentheses. For example:

RULE own_pharmacy
IF   pharmacy_used = ours
THEN perscription = (treatment);
Computation
Arithmetic expressions are also enclosed in parentheses, and use most of the same syntax and operators as most programming languages:
RULE profit
IF   income > (expenses)  ! since expenses is a variable, it must be in parens
THEN profit = (income - expenses)
ELSE deficit = (expenses - income);
Note that VP-Expert only tries to FIND variables that are on the left side of an expression; for example, the above rule will try to FIND a value for income but not for expenses. If a value has not already been found for expenses, VP-Expert will treat it as "unknown", giving unpredictable results.

One way to fix this is to include a "dummy" condition in the rule to force it to FIND a value for expenses:

RULE profit
IF   expenses >= 0  ! hopefully this will always be true!
AND  income > (expenses)  ! will work, since expenses now found
THEN profit = (income - expenses)
ELSE deficit = (expenses - income);
Functions
VP-Expert also has a number of standard mathematical functions:
@ABS(X)       @COS(X)        @ACOS(X)
@LOG(X)       @SIN(X)        @ASIN(X)
@EXP(X)       @TAN(X)        @ATAN(X)
@SQRT(X)
Each begins with the @ symbol, and like other math expressions must be enclosed in parentheses:
side3 = (@SQRT(side1 + side2))

Multiple answers to queries

As stated above, the inference engine for VP-Expert will stop once it has found the first value of a variable it is trying to FIND. It is possible, however, to force it to find all values for variables instead. This is done with the PLURAL statement (which must be placed before the ACTIONS block):
PLURAL: list of variables;
While you don't have to make all of the variables in your knowledge base PLURAL, you must at least include all that would support the kind of multiple results you wish to obtain. In the "medical" knowledge base we have been working with so far, for example, if you wish to make treatment plural, then you must make diagnosis plural as well:
PLURAL: treatment, diagnosis;
You may also have to change the structure of your rules that deal with PLURAL variables. In particular, you cannot count on the "order of evaluation" when structuring your rules; nor can you use ELSE to set the value of a PLURAL variable, as it would always be used.

For example, if the variable cost were PLURAL, we could not use the following rules:

RULE cheap
IF price < 20
THEN cost = cheap;

RULE expensive
IF price < 100
THEN cost = medium
ELSE cost = expensive;
If price had value 10, then cost would be set to cheap, medium, and expensive! In general, such rules must be set up so that they are independent of the order in which they are tried:
RULE cheap
IF price < 20
THEN cost = cheap;

RULE medium
IF price < 100
AND price >= 20
THEN cost = medium;

RULE expensive
IF price >= 100
THEN cost = expensive;
Another way to deal with an ELSE is to replace it with a check for the value unknown:
RULE work
IF diagnosis = unknown
THEN treatment = get_back_to_work;
This rule will fire only if diagnosis has been given no value by this point. Like the ELSE, it should be the last rule involving treatment for this to work correctly.

PLURAL inputs
It is also possible to set up your ASK statements to allow the user to choose more than one option from the menu by making that variable PLURAL. This is often faster for the user than having to answer multiple questions. For example:

PLURAL: symptoms;
...
ASK symptoms: "Choose all symptoms that you have.";
CHOICES symptoms: sore_throat, spots, rash, none;
The user can then press ENTER by each one which holds, and press END to confirm the list.

Printing variables with multiple values
The DISPLAY statement works with PLURAL variables, printing all of its values in column format. For example, the code:

DISPLAY "I prescribe the following:"
DISPLAY "{treatment}"
might print:
I prescribe the following:
penicillin
allergy pills
bed rest

Adding explanations to rules

There are many situations where it is useful to justify the conclusions reached by an expert system. VP-Expert has (limited) capabilities for allowing you to add such explanations to rules, with the BECAUSE statement:
RULE measles
IF   temperature = very_high
AND  spots = yes
AND innoculated <> yes
THEN Diagnosis = measles
BECAUSE "A high temperature and spots are the usual symptoms of measles";
The text contained if the BECAUSE statement is printed if this rule is involved in either a how or why query. Note that the BECAUSE statement must be the last statement in the rule.

A couple of other notes:




Query Statements

Variables which do not appear as the consequent of some rule in the knowledge base (that is, are leafs in the deduction tree), are considered potential questions for the user. If the inference engine attempts to FIND such a variable, the user will be prompted for its value. This is done with ASK and CHOICES statements.

The ASK statement

The form of the prompt for a variable is defined by an ASK statement. It has the form:
ASK variable: "prompt";
For example:
ASK temperature: "Please take the patient's temperature, and enter it
into the system.";
As with any other program, these prompts should be informative -- that is, they should tell the user how to gather and enter the information.

The CHOICES statement

If there are a finite number of possible answers to a question they may be presented in a menu defined by a CHOICES statement. It has the form:
CHOICES variable: list of values;
For example:
CHOICES temperature: normal, high, very_high;
This menu is printed out when the question is ASKed. Note that if there is no CHOICES statement for a variable, the user will have to type in a value at the cursor after the prompt (this is how numeric variables are usually handled).

VP-Expert and Uncertainty

Uncertainty in VP-Expert is represented in terms of ``confidence factors'' (abbreviated CNF), which may take on any value between 0 and 100.

These confidences apply to the assignments done by the inference engine -- for example, something of the form

diagnosis = measles CNF 80
means that the system believes that diagnosis has the value measles with certainty of 80 out of 100 (note that this says nothing about any other possible values of diagnosis, an important point when dealing with PLURAL variables).

This form can be used to assign a confidence factor to any rule in a VP-Expert knowledge base, as part of the THEN or ELSE. For example:

RULE flu
IF temperature > 99
THEN diagnosis = flu CNF 90
ELSE diagnosis = goofing_off CNF 75;
This means that we have a confidence of 90 in the implication that temperature > 99 -> diagnosis = fever and a confidence of 75 in the implication temperature <= 99 -> diagnosis = goofing_off.

If no CNF is specified for an assignment is given, VP-Expert uses the default of 100 -- that is, unless told otherwise, VP-Expert assumes that all of its data and rules are completely reliable.

I/O of certainty factors

Users may also provide confidences in the data they input in response to questions. This can be done with the following steps: You can use the DISPLAY statement to show both the value(s) assigned to a variable and the confidence in that assignment. This is done by placing a # before the variable in the DISPLAY:
DISPLAY "I prescribe {#treatment} for your symptoms."
For example, if VP-Expert had assigned penicillin to treatment with a confidence of 85, this would print:
I prescribe penicillin CNF 85 for your symptoms."
Since it is not possible to display the confidence in a more informative way, your system should probably make clear to the user exactly what the CNF 85 means.

Computing certainty factors

The main purpose of giving rules/inputs certainty factors, of course, is to use them in some rational manner to compute the certainty of the conclusions reached by the system. VP-Expert uses a number of methods based on the MYCIN expert system.

Combining certainties of rules and premises
If both the premise (that is, the ``IF'' part) of a rule and the rule itself are uncertain, then the confidence of the conclusion of the rule is:

CNF of premise * CNF of rule / 100

For example, given the rule:

IF diagnosis = measles
THEN treatment = penicillin CNF 90
if the assignment diagnosis = measles has a confidence of 70, then the conclusion that treatment = penicillin has confidence of:

70 * 90 / 100 = 63

This should make sense, as uncertain premises and uncertain rules should result in even more uncertain conclusions.

Combining certainties in conjunctive premises
If two or more simple premises are linked by ANDs, then the overall confidence in their conjunction is the minimum of the confidences of the premises. For example, given:

IF temperature = very_high
AND spots = yes
AND innoculated = no
THEN diagnosis = measles
if temperature = very_high with confidence 90
and spots = yes with confidence 75
and innoculated = no with confidence 100
then the overall confidence in the premise IF temperature = very_high AND spots = yes AND innoculated = no is 75.

This should make sense, as the confidence in the overall premise can be no more certain than its least certain part.

Combining certainties in disjunctive premises
If two simple premises with confidences C1 and C2 are linked by OR, then the overall confidence in their disjunction is computed as:

C1 + C2 - (C1 * C2)/100

For example, given:

IF spots = yes
OR rash = yes
THEN diagnosis = allergy
if spots = yes with confidence 75
and rash = yes with confidence 80
then the overall confidence in the premise IF spots = yes OR rash = yes is

75 + 80 - (75 * 80)/100 = 95.

This should make sense, as additional evidence for a conclusion should increase its confidence.

Note that you must use the OR to combine evidence in this manner. If you break something like this up into two separate rules, such as:

IF spots = yes
THEN diagnosis = allergy

IF rash = yes
THEN diagnosis = allergy
then the inference engine will (as it usually does) stop trying to FIND a value for diagnosis after the first rule. This means that rash will not be factored into the deduction, and the confidence of diagnosis = allergy will be based on a premise of CNF 75 instead of CNF 95.

A final example
Suppose we are given the rule:

IF sore_throat = yes
AND temperature = high
OR temperature = very_high
THEN diagnosis = flu CNF 90;
Also suppose we have the following confidences (produced either by other rules or by user input):

sore_throat = yes CNF 70
temperature = high CNF 80
temperature = very_high CNF 60

To compute the confidence in diagnosis = flu:

Setting a truth threshold

It may be argued that conclusions should not be based on premises which are very unreliable; that is, if the premise of a rule has a CNF below some threshold, then the rule should ``fail'' and the expert system should try some more plausible rule in order to reach a conclusion. This kind of ``truth threshold'' can be particularly important for VP-Expert, which quits after finding the first value for a variable, no mater how implausible the evidence for assigning that value.

This is controlled with the TRUTHTHRESH value in VP-Expert. If the confidence in the premise of a rule is less than TRUTHTHRESH, then it fails and assigns no values. For example, given the rule

IF diagnosis = measles
THEN treatment = penicillin;
If TRUTHTHRESH is 40, and the confidence in the premise diagnosis = measles is 35, then this premise is considered to be FALSE, and the assignment treatment = penicillin is not done.

The default value of TRUTHTHRESH is 50. It can be changed in the ACTIONS block or a rule conclusion. For example, to change the threshold to 40, you would use the statement:

TRUTHTHRESH = 40

The VP-Expert Editor


VP-Expert includes a simple, but sufficient text editor that can be invoked from the Main Menu and the Consult Menu. It is also invoked automatically when a syntax error is detected in the knowledge base. If invoked from the Main Menu, the user will be prompted for the name of the file to be edited. The user can either type a name or select from the displayed list. A new file can be specified by typing a new name.

Because the editor is rather non-intuitive to use (and because it sometimes has problems loading in rooms 301 and 303), you are encourged to use whatever editor you prefer. Just make sure that the file you create ends in the extension .kbs

Once invoked, the VP-Expert editor acts like a normal text editor in insert mode, "pushing over" any text to the right of the cursor. The only exeption is the RETURN keyi, which just moves you down to the next line. To insert a new line, you must type Control-Enter.

The Editor Command Menu

When in edit mode, the bottom of the screen displays a list of editor commands that can be invoked using the function keys. Note that the choices in the list change when the Alt or Ctrl keys are held down. This shows the commands which can be invoked by combining one of these keys with the appropriate function key.

Editor Commands

The following table lists the most commonly used editor commands:

ALT-F6Save the current file and exit the editor
ALT-F8Exit the editor without saving
ALT-F5Save the current file without exiting
Control-EnterInsert a new line
DeleteDelete the character at the cursor position
BackspaceDelete the character to the left of the cursor position
Control-TDelete from cursor to end of word
Control-YDelete this line
PageUpUp one screen
PageDownDown one screen
HomeMove to beginning of line
EndMove to end of line