Expert Systems

Goals:

This laboratory exercise introduces the concept of expert systems in general and a specific expert system in particular. Further, since such programs often utilize file input, this application provides an example of the need to convert data generated by one program into a different form for use in another program.

Background

Every college and university must decide how to place incoming students in appropriate courses. In many cases, placement recommendations may be based on standardized tests (SATs, ACTs, Achievement Tests, Advanced Placement (AP) scores, International Baccalaureate (IB) scores) and high school transcripts. Historically at Grinnell, faculty reviewed such data manually and made recommendations.

While faculty continue to be actively involved, the Mathematics and Computer Science now uses an expert system to automate much of this process. The first version of the current program was developed in the Spring, 1993, as a student-faculty project; students Vikram Subramaniam and Ivan Sykes worked with faculty member Henry Walker. The program has been refined and expanded several times over the years to reflect new or revised courses.

Overview of the Placement Program

The main program can be used in several ways:

• users can run the program interactively at a terminal window with the user entering needed data,
• the program can process information received electronically from the Registrar, producing letters for students, or
• users can use a World-Wide-Web interface to enter data and view placement conclusions.

The Web interface is simplest.

1. Try running this program through a Web browser, using the address http://www.walker.cs.grinnell.edu/placement/placement-form.html

While the placement program is written in LISP, the code and run-time environment are quite similar to Scheme. To run the program in the relatively familiar terminal-window environment, follow these steps:

2. Run CMU Common Lisp in a terminal by typing the command

          lisp
   

3. At the new prompt, type

          (load "/home/walker/placement/newstudents.lsp")
          (placement) 
   

4. When the menu appears, use the "I" option to run the program interactively. Then, enter data for yourself or for a hypothetical student as requested.

5. When you are done, type "Q" to quit the menu. Then at the "USER" prompt, type

          (quit)
   

This application illustrates the structure of many expert systems. This system has two basic parts:

• A rule base, found in file "~walker/placement/newstudents.lsp", which contains about 100 rules concerning the placement of students.
• An inference engine, found in file "~walker/placement/tmycin.lsp", which applies the rules to specific cases.

Each part is written in LISP, the most common computer language for artificial intelligence. The inference engine is based on the program TMYCIN, written by Gordon Novak at the Artificial Intelligence Laboratory of the University of Texas at Austin.

6. To view the rules in a terminal window, type

          more ~walker/placement/newstudents.lsp
   

   This command displays the first screen of the rule base. Hit the space bar to view subsequent screens.
   While the programming details require considerable sophistication in LISP, you will notice that many elements of the code are reasonably similar to Scheme -- following a list-oriented format. The general organization of the rule base is reasonably straightforward:
   • After loading the inference engine ("/users/walker/placement/tmycin.lsp"), the main variables (i.e., the context) for placement is given.
   • Semesters of English and high school credits are used to infer how many semesters of high school work are recorded on the current transcript.
   • Standardized test scores are classified superior, high, good, fair, poor, and low.
   • Preliminary placements are made for mathematics and then for computer science by considering minimum cutoff levels. (Note, as the rules specify minimums, someone prepared for calculus II also will be adequately prepared for calculus I.)
   • Final placements are determined as the highest tentative placement.
   A certainty factor is associated with each rule, based on a 1000 point scale. A factor of 1000 indicates great confidence with the conclusion, while 700 or 500 shows must less certainty in the result.

   Use your knowledge of Scheme/LISP lists to interpret the likely syntax of rules in this system.

Input Consistency Checking

When programs are to be run by general users, the programs usually should check that user input is reasonable and consistent. Typically, input errors fall into three categories:

• input that is impossible,
• input that is unlikely but possible, and
• plausible input that is incorrect.

Impossible Input

In some situations, we can determine that a particular input value could not possible be correct. For example, SAT scores must be between 200 and 800. In such cases, programs could check that whether an input value is possible. If not, the program could either ignore the data or ask the user to re-enter the value.

7. Run the interactive version of the placement expert system, and enter some scores that are impossible. How does the program behave when just one or just a few data values are impossible? In this test, include both integer values that are out of range and a misspelling of "Unknown".

8. Repeat the previous step using the Web-based interface to the placement expert system.

Possible, but Unlikely, Input

In other applications, we may want a user to double-check an input value before the program continues. We might expect values of a certain type or range, but we cannot rule out the possibility of other values. For example, in a grocery store, we expect most individual items to be between $0.00 and $100.00 (exclusive). Items over $100.00 are very unlikely although they are possible. (E.g., one side of beef from the meat department could exceed this amount. )

In such cases, a program might review an input value to see if it is unlikely to be correct, and the program may ask the user to verify the correctness of the datum. For example, if a grocery item costs $150.00, the programmer might question if the cashier has entered an extra 0, and the program might give the opportunity to correct this value. Since this value is possible, however, the program should allow the value to be processed.

9. One might anticipate that the placement program will be used by college-bound students. Can you identify any input values that would be possible, but unlikely?

   What happens when such values are entered into the Web-based placement interface?

Possible, but Incorrect, Input

The job of verifying input is particularly difficult when the values seem plausible. For example, if an SAT score of 650 is entered as 560, a program will have difficulty identifying the error.

In programming, one approach to such data entry errors is to ignore them, as they may be too costly or time consuming to find them. A second approach involves supplying the user with a printout of all data entered, so the user can check the values manually. (The paper receipt at the grocery store allows this type of checking.)

10. How often have you reviewed the paper receipt you obtained from a grocery store? Discuss your answer briefly.

11. The Web-based program displays both the potential placement and the data entered by the user. To what extent does this seem effective within this Web application in encouraging a user to check the data entered?

This document is available on the World Wide Web as

http://www.walker.cs.grinnell.edu/courses/153.sp05/labs/lab-placement.shtml

created January 8, 1998 by John David Stone last revised February 3, 2005 by Henry M. Walker
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.