, the goal Class , and a training
set Example of records. The following is the pseudocode for id3:
This chapter defines the functional requirements of the system, identifying the types of features that will be presented to a user. Then it discusses the computer platform and programming language needed to build the package. The chapter closes with PETIL's general architecture.
PETIL will be used to help patients evaluate their own preferences between alternate outcomes of taking estrogen. PETIL will behave as follows:
(Testing continues...)
This section explains what Java is and some object-oriented programming concepts that Java uses. These concepts are platform-independence, bytecodes, applications, applets, inheritance, class, attributes and methods. At the end of the section there is an explanation on how PETIL shall be implemented.
This system is written in JAVA and accessible through the World Wide Web. PETIL will take advantage of the derivation and inheritance for the classes and the use of objects in this language where possible. We will use an existing id3 program, written in Prolog.
Java is a new object-oriented programming (OOP) language for the Internet developed by Sun Microsystems. Java is platform-independent at the source and at the binary level. Platform-independence is a program's capability of moving easily from one computer system to another. This portability is possible because Java generates bytecodes when it is compiled. Bytecodes are a set of instructions that looks a lot like some machine codes, but that is not specific to any one processor [#!lemay!#].
Java programs are applications and applets. Applications are stand-alone programs, such as the HotJava browser. Applets are similar to applications, but they don't run on their own. They need a Java-compatible browser [#!lemay!#].
For security reasons, Java cannot create system files. I will write a file to the system from PETIL through a server and a program written in C language.
OOP extends abstract data types through the concepts of inheritance. Inheritance allows data classes to reimplement and share characteristics. In Java, inheritance is implemented through subclassing. Using subclassing with Java we just need to define the difference between the new class and its parent. The additional behavior is all available to the new class through inheritance.
A class is a template for multiple objects with similar features. A class contains variables and methods representing attributes and behavior of an object respectively. Attributes are the individual things that differentiate one object from another and determine the appearance, state, or other qualities of that object. Methods define the behavior of an object. Methods in Java are the same as functions in C language. They are defined inside classes that operate on objects of those classes. Classes are used in PETIL to share like data and functionality.
As a main tool, PETIL will use the SRGM to assess patient preferences for different outcomes based on his or her own feelings about risk and quality of life, as discussed in Chapter 2. PETIL will also use id3 to induce patient preferences from a set of observed instances.
PETIL will follow SRGM steps, that is, it will display the outcomes of taking estrogen, and will ask the patient to rank them. It will ask the patient how many examples to provide.
Each hypothetical scenario will be constructed as follows: pick any 3 outcomes at random, order them according to patient's preferences, such that the best gamble is the most important, the sure thing is in the middle, and the worst gamble is the least important. Generate at random the winning probability of the best gamble.
In the training part, generate a scenario for each example. Present it to the patient and ask if she would take estrogen. With the information of the scenario and the answer write the EXAMPLE file. Since Java cannot write directly to a file, PETIL will use a server program to send and write this information. It will also use a program written in C language to start the server in the background and to run the id3 prolog program. This is done is this way because Java does provide the facility of making systems calls. Each example will generate a record in the training set. When all the examples have been presented to the user, apply id3 algorithm to the training set as explained in Chapter 3. Id3 should write the resulting decision tree in the TREE file.
Generate a set of testing examples as follows: for each example, generate a scenario, and evaluate the goal predicate, instead of asking the patient if would take estrogen. Then flip the second half of the examples, that is, the ones with "no" answer will be flipped to "yes" and viceversa. Shuffle the set of testing examples. Ask the patient if agrees or disagrees with the result of the evaluation.
Finally compute the error of the SRG exercise by adding the "bad" answers and dividing it by the number of testing examples. The "bad" answers are those in which the patient agrees with flipped examples and those in which the patient disagrees with unflipped examples.
The user interface allows the patient to communicate with PETIL. The Training module produces the training set which is written to a file called EXAMPLE. PETIL will write this file through the Server module. Once the training set is written, PETIL will run id3, which is a prolog program running totally independent of PETIL. The Testing module reads the TREE file generated by id3 and interpreter the decision tree to induce patient's preferences. It also presents a series of scenarios to test the SRG exercise.
This chapter will present the classes used from Java and the classes and methods provided by myself for each of PETIL's module. At the end of this chapter I will present a running example using PETIL.
The user interface takes advantage of the capability of Java of using User Interface (UI) components to make PETIL friendlier. The classes used from Java to generate PETIL's interface are the following:
The classes from myself to build PETIL's interface are listed below:
/*******************************************************************
Preference Evaluation Tool using Inductive Learning
class: Petil
Superclass: Applet
*******************************************************************/
import java.awt.*;
public class Petil extends java.applet.Applet {
MyFrame window;
public void init() {
add( new Button( "P E T I L" ) );
window = new MyFrame();
window.resize( 500, 410 );
window.move( 25, 290 );
}
public boolean action( Event evt, Object arg ) {
if ( evt.target instanceof Button ) {
String label = (String) arg;
if ( label.equals( "P E T I L" ) )
window.show();
return true;
}
else return false;
}
}
/*******************************************************************
class: MyFrame
Superclass: Frame
Calling class: Petil
Action: Displays Main menu bar and submenus.
********************************************************************/
import java.awt.*;
import java.io.*;
import java.net.*;
public class MyFrame extends Frame {
/* V a r i a b l e s */
MenuItem subUti, subRank, subStartTrn,
subTest, subNumEx,subError;
DialogNumExamples dNumExamples;
TestExample examples[ ] = new
TestExample[maxExamples];
TableOutcomesAndRanks dRanks;
PresentScenarios dScenarios;
/* M e t h o d s */
/* Shows and controls the menubar */
MyFrame( String title )
/* Ranks the outcomes */
void displayRanks()
/* Reads the number of examples the patient will provide */
void readNumberExamples()
/* Generates the training file */
void generateTrainingFile()
/* Flips and shuffles the training set */
void flip()
/* Asks patient if agrees with the induced rules */
void askPatient()
/* Computes the error of the SRG exercise */
void computeError()
/* Handles the actions of the menubar */
public boolean action( Event evt, Object arg )
}
/*******************************************************************
class: DialogMessage
Superclass: Dialog
Calling class: TableOutcomesAndRanks and MyFrame
Action: Constructs an initially invisible window
to display a message.
*******************************************************************/
import java.awt.*;
public class DialogMessage extends Dialog {
public DialogMessage( Frame parent,
boolean modal,
String message1,
String message2,
String message3 ) {
super( parent, modal );
/* Setting up layout to four rows and one column */
setLayout( new GridLayout( 4, 1, 10, 10 ) );
add( new Label( message1, Label.CENTER ) );
add( new Label( message2, Label.CENTER ) );
add( new Label( message3, Label.CENTER ) );
add( new Button( "OK" ) );
this.resize( 300, 200 );
}
public boolean action( Event evt, Object arg ) {
if ( evt.target instanceof Button) {
String label = (String) arg;
if ( label.equals( "OK" ) )
this.hide();
return true;
}
return false;
}
}
This module generates at random 3 outcomes (the best gamble, the sure thing and the worst gamble) and the winning probability of the best gamble. With this information presents a scenario to the user, and asks him or her if is willing to take the risk. This information is written to a file called EXAMPLE, which will be the input to the Learning module. This file is generated through a server. PresentScenarios is the class that performs this actions and is defined below:
/*******************************************************************
Subclass: PresentScenarios
Superclass: Dialog
Calling class: MyFrame
Action : For each example, it presents a scenario containing
3 outcomes ( the sure thing, the best gamble, and
the worst gamble ) and the probability of winning
the best gamble. Then, asks the patient if would
accept the gamble. It uses 2 buttons, containing
"yes" and "no" to accept the answer, so that the
patient won't make mistakes.
*******************************************************************/
import java.awt.*;
import java.io.*;
import java.net.*;
public class PresentScenarios extends Dialog {
/* V a r i a b l e s */
Socket id3Socket;
PrintStream os;
RandomGenerator rgLikelihood;
URL inURL;
TextArea ta = new
TextArea("Getting text...", 20, 50);
/* M e t h o d s */
PresentScenarios(Frame parent,
boolean modal,
int numExamples,
int numOutcomes,
int rank[ ],
String outcome[ ])
/* Generates a new example */
void newExample()
/* Opens the example file through the server.
It uses the port number 5881. */
void openTrainingFile()
}
/*******************************************************************
class: RandomGenerator
Calling class: RandomOutcomes
Action: Generates random numbers from
leftQuote to rightQuote.
*******************************************************************/
import java.awt.*;
public class RandomGenerator {
private long seed;
private final static long multiplier = 0x5DEECE66DL;
private final static long addend = 0xBL;
private final static long mask = (1L << 48) - 1;
public RandomGenerator() {
this(System.currentTimeMillis());
}
synchronized public void setSeed( long seed ) {
this.seed = ( seed ^ multiplier ) & mask;
}
synchronized private int next(int bits) {
long nextseed = ( seed * multiplier + addend ) & mask;
seed = nextseed;
return (int)(nextseed >>> (48 - bits));
}
public int nextInt() {
return next( 4 );
}
int randomNumber( int leftQuote, int rightQuote ) {
int random;
do {
random = nextInt();
} while ( (random < leftQuote) ||
(random > rightQuote) );
return random;
}
}
For security reasons Java does not allow to write directly to the system from the World Wide Web. PETIL, acting as a client, writes a file through a server. The server is an independent Java program called ServerWrite running in the background. ServerWrite is not an applet. It is an stand-alone application. It does not need a browser to run. The server is started from PETIL through a native method written in C language because the Java class library does not already provide this facility. Native methods are those functions implemented by a language other than Java.
The code of ServerWrite is as follows:
/*******************************************************************
class: ServerWrite (Stand alone application)
called from: PresentScenarios through a native code written
in C language.
Action: Starts the server and waits until client wants talk.
Writes to a file called example whatever cames from
the client.
*******************************************************************/
import java.net.*;
import java.io.*;
class ServerWrite {
public static void main(String args[ ]) {
ServerSocket serverSocket = new ServerSocket(5881);
Socket clientSocket = serverSocket.accept();
DataInputStream is = new DataInputStream(
new BufferedInputStream(
clientSocket.getInputStream()));
String inputLine = null;
/* Wait until client wants to talk */
while (inputLine == null)
inputLine = is.readLine();
/* Open the training file */
PrintStream s = new PrintStream(
new FileOutputStream("example"));
s.println( inputLine );
/* Keep reading while client wants to talk */
while ( (inputLine = is.readLine()) != null )
s.println( inputLine );
is.close();
clientSocket.close();
serverSocket.close();
}
}
The Learning module is a prolog program called id3, running independently
from PETIL. It takes
as input the file example generated by Training module and written by
Server module. Then, it initializes the knowledge base and builds the decision tree
given a set of attributes , the goal Class , and a training
set Example of records. The following is the pseudocode for id3:
function ID3 ( Example : List of examples,
Attributes: List of attributes,
Class : Node ID of class or leaf(class) (the goal))
Returns a decision tree;
begin
If Example is empty, return a single node with value Failure;
If Example consists of records all with the same value for
the goal, return a single node with that value;
If Attributes is empty, then return a single node with as value
the most frequent of the values of the goal
that are found in records of Example;
[note that then there will be errors, that is, records
that will be improperly classified];
Let D be the attribute with largest GainRatio(D,Example)
among attributes in Attributes;
Let {dj| j=1,2, .., m} be the values of attribute D;
Let {Ej| j=1,2, .., m} be the subsets of Example consisting
respectively of records with value dj for attribute D;
Return a tree with root labeled D and arcs labeled
d1, d2, .., dm going respectively to the trees;
ID3(Attributes-{D}, goal, E1),
ID3(Attributes-{D}, goal, E2), ...,
ID3(Attributes-{D}, goal, Em);
end ID3;
At the end, the program uses a simple pretty-print procedure for displaying decision trees to write the TREE file.
This module performs the following actions:
To accomplish the actions listed above, the Testing module uses the following classes and methods:
/*******************************************************************
class: PresentTestExamples
Superclass: Dialog
Calling class: MyFrame
Action : Presents the patient a set of test examples.
Asks if agree or disagree with evaluations.
*******************************************************************/
import java.awt.*;
public class PresentTestExamples extends Dialog {
TestExample examples[ ];
int randomIndex[ ];
PresentTestExamples(Frame parent,
String title,
boolean modal,
TestExample examples[ ],
int numExamples,
int randomIndex[ ])
void newExample()
}
/*******************************************************************
class: TestExample
Calling class: MyFrame
Action: Creates a test example.
*******************************************************************/
import java.awt.*;
public class TestExample {
String goal; // Value of the goal predicate assigned
int pBG; // Winning probability of best gamble.
boolean agree; // True if patient agrees with the evaluation.
boolean flipped; // True if the value of the goal variable has
// been flipped.
public TestExample( Frame outerparent,
String line[ ],
int length[ ],
int numLines )
char parser(String intermOutcome, String likelihood,
String line[ ], int length[ ], int numLines)
}
/*******************************************************************
class: Shuffle
Calling class: MyFrame
Action: Fills the array index with maxTestEx
random numbers
*******************************************************************/
import java.awt.*;
public class Shuffle {
final int maxTestEx = 15;
int index[] = new int[maxTestEx];
public Shuffle( int totalExamples ) {
RandomGenerator rg = new RandomGenerator();
boolean repeated[] = new boolean[maxTestEx];
int randomIndex = 0;
boolean found = false;
for (int i = 0; i < totalExamples; i ++)
repeated[i] = false;
for (int i = 0; i < totalExamples; i ++) {
found = false;
while ( ! found ) {
randomIndex =
rg.randomNumber( 0, totalExamples -1 );
if ( ! repeated[randomIndex] ) {
repeated[randomIndex] = true;
index[i] = randomIndex;
found = true;
}
}
}
}
}
The EXAMPLE file contains the training set generated by the Training module
and it is divided into two sections: the declaration records and the
example records. The 2 declaration records contain:
class([yes/no]).
where yes and no are the possible values of GOAL.
attributes([theBestG, theWorstG, pBestG, theSureT]).
where theBestG, theWorstG and theSureT are outcomes representing the best gamble,
the worst gamble and the sure thing respectively. pBestG represents the
winning probability of the best gamble.
The example records are of the form:
example(i ,goal ,[theBestG = tBG , theWorstG = tWG , pBestG = pBG , theSureT = tST ]).
where I is the number of the example, GOAL is yes or no according to patient's answers.
The number of examples records is determined by the patient.
The TREE file contains the decision tree generated after applying id3 to the training set. Its format varies according to the rules generated by id3.
This section presents a short example showing how to help a 50-year old woman with menopause sings to evaluate her own preferences using PETIL. The appendix User's Manual, explains in detail how to use it properly. In this example, PETIL will learn a definition for the goal predicate wouldTakeEstrogen given a set of examples, where the definition of taking or not the risk is expressed as a yes/no answer.
Once you are running PETIL, select the decision estrogen. Suppose that she ranked the outcomes.
Lets indicate the system that she will provide 35 examples as shown in
After she responds to the Testing module according with her preferences, we can consult the EXAMPLE file shown below:
classes([yes,no]). attributes([theBestG, theWorstG, pBestG, theSureT]). example(1,no, [theBestG=breastC, theWorstG=premDea, pBestG=60, theSureT=coronar]). example(2,no, [theBestG=wellOnE, theWorstG=premDea, pBestG=40, theSureT=coronar]). example(3,yes, [theBestG=breastC, theWorstG=hipFrac, pBestG=90, theSureT=coronar]). example(4,no, [theBestG=wellOff, theWorstG=premDea, pBestG=50, theSureT=vertebr]). example(5,no, [theBestG=wellOff, theWorstG=premDea, pBestG=80, theSureT=wellOnE]). example(6,no, [theBestG=breastC, theWorstG=hipFrac, pBestG=50, theSureT=coronar]). example(7,yes, [theBestG=wellOnE, theWorstG=coronar, pBestG=80, theSureT=breastC]). example(8,yes, [theBestG=wellOff, theWorstG=premDea, pBestG=70, theSureT=hipFrac]). example(9,no, [theBestG=wellOff, theWorstG=premDea, pBestG=40, theSureT=wellOnE]). example(10,yes, [theBestG=wellOff, theWorstG=stroke , pBestG=80, theSureT=hipFrac]). example(11,yes, [theBestG=wellOff, theWorstG=hipFrac, pBestG=90, theSureT=coronar]). example(12,yes, [theBestG=wellOff, theWorstG=coronar, pBestG=90, theSureT=wellOnE]). example(13,yes, [theBestG=breastC, theWorstG=hipFrac, pBestG=90, theSureT=coronar]). example(14,yes, [theBestG=wellOff, theWorstG=hipFrac, pBestG=80, theSureT=coronar]). example(15,no, [theBestG=breastC, theWorstG=premDea, pBestG=40, theSureT=stroke ]). example(16,no, [theBestG=breastC, theWorstG=premDea, pBestG=70, theSureT=vertebr]). example(17,no, [theBestG=hipFrac, theWorstG=premDea, pBestG=50, theSureT=vertebr]). example(18,yes, [theBestG=wellOnE, theWorstG=premDea, pBestG=90, theSureT=vertebr]). example(19,yes, [theBestG=wellOff, theWorstG=hipFrac, pBestG=60, theSureT=wellOnE]). example(20,no, [theBestG=vertebr, theWorstG=premDea, pBestG=50, theSureT=stroke ]). example(21,no, [theBestG=wellOnE, theWorstG=stroke , pBestG=80, theSureT=breastC]). example(22,no, [theBestG=wellOff, theWorstG=hipFrac, pBestG=60, theSureT=wellOnE]). example(23,yes, [theBestG=wellOnE, theWorstG=stroke , pBestG=80, theSureT=hipFrac]). example(24,no, [theBestG=breastC, theWorstG=premDea, pBestG=40, theSureT=vertebr]). example(25,yes, [theBestG=vertebr, theWorstG=premDea, pBestG=80, theSureT=stroke ]). example(26,no, [theBestG=wellOnE, theWorstG=vertebr, pBestG=60, theSureT=breastC]). example(27,no, [theBestG=wellOff, theWorstG=premDea, pBestG=70, theSureT=vertebr]). example(28,no, [theBestG=breastC, theWorstG=premDea, pBestG=60, theSureT=vertebr]). example(29,no, [theBestG=wellOff, theWorstG=premDea, pBestG=90, theSureT=breastC]). example(30,yes, [theBestG=wellOff, theWorstG=vertebr, pBestG=80, theSureT=wellOnE]). example(31,no, [theBestG=coronar, theWorstG=premDea, pBestG=70, theSureT=hipFrac]). example(32,no, [theBestG=wellOff, theWorstG=vertebr, pBestG=40, theSureT=wellOnE]). example(33,no, [theBestG=wellOff, theWorstG=premDea, pBestG=40, theSureT=breastC]). example(34,yes, [theBestG=wellOff, theWorstG=vertebr, pBestG=70, theSureT=coronar]). example(35,no, [theBestG=breastC, theWorstG=premDea, pBestG=90, theSureT=stroke ]).
With EXAMPLE file PETIL will run ID3 program to get the TREE file. We can consult it using PETIL as shown below:
pBestG=50 ==> class=no
pBestG=60 and theBestG=wellOff and theWorstG=hipFrac and theSureT=wellOnE
==> class=no
theSureT=wellOnE ==> class=yes
theBestG=wellOnE ==> class=no
theBestG=breastC ==> class=no
pBestG=80 and theSureT=coronar ==> class=yes
theSureT=breastC and theBestG=wellOnE and theWorstG=coronar
==> class=yes
theWorstG=stroke ==> class=no
theSureT=hipFrac ==> class=yes
theSureT=stroke ==> class=yes
theSureT=wellOnE and theBestG=wellOff and theWorstG=premDea
==> class=no
theWorstG=vertebr ==> class=yes
pBestG=40 ==> class=no
pBestG=70 and theWorstG=premDea and theSureT=vertebr ==> class=no
theSureT=hipFrac and theBestG=wellOff ==> class=yes
theBestG=coronar ==> class=no
theWorstG=vertebr ==> class=yes
pBestG=90 and theSureT=wellOnE ==> class=yes
theSureT=coronar ==> class=yes
theSureT=vertebr ==> class=yes
theSureT=breastC ==> class=no
theSureT=stroke ==> class=no
The decision tree is used to evaluate the testing examples, then the system will ask her "agree" or "disagree".
After the testing you can consult the error of this SRG exercise.
In order to properly run PETIL, one must do the following:
ln -s /usr/local/lib/netscape2/moz2_0.zip moz2_0.zip
You may run PETIL from the internet. You will need a Java-compatible browser
like Netscape 2.0 or
HotJava to be able to see and run the interface. PETIL's
site is
http://lombok.cs.uwm.edu/maria/JAVA/petil.html
When PETIL first starts, you will see a page including a title in blue, a brief description of the program, and a button.
Click the button to get PETIL's main menu. This is a menu bar containing all the options of the system.
Now choose the decision (estrogen, menopause, back pain, etc. ) that you want to work with. At this point all the menus are disabled except Decision so that you will not make mistakes. If you choose estrogen, you will see the following label under the main menu:
D E C I S I O N: E S T R O G E N S
Then you may choose the option Outcome to rank the outcomes in order of your preference.
In front of each outcome you will see a button which is a choice menu, click on it and it will display a menu of choices from 1 to n, where n is the number of outcomes. When you have established your preferences click on the Continue button. If you have not ranked an outcome or if you have repeated a rank, the system will display the message that indicates there is an error. If this happens, click on OK and PETIL will return to the dialog window showing the outcomes so that you can correct the error.
Now go to the Utility assessment menu and choose Training from there. Now choose Number of examples, and you should see a dialog window.
Indicate the number of examples that you will provide to the system by choosing from the choice menu from 10 to 40. When you have finished, click on Continue.
To start the training, choose Start training from Utility assessment menu. In this part of the program you will be asked to imagine a hypothetical situation that might be worse than the one that you actually are facing. Then you will be asked if you accept a gamble with a winning probability.
After finishing the training, you can consult the training set and the decision tree through PETIL. A.9 respectively.
Now, you can test if PETIL actually learned from your examples by choosing option Testing from Utility assessment menu. In this case, you will be presented with a gamble, a probability of winning that gamble, and a decision of whether or not to take the gamble. The value of the decision has been determined by the examples that you have provided in the training part. Here you have to agree or disagree with PETIL's decision in order to compute the error of this SRG exercise. It will appear on screen in the dialog window.
Finally, to find the error of this SRG exercise choose Compute error option from Utility assessment menu, and you will get a dialog window.
Whenever you need help in how to use PETIL, click on the Help menu. This menu containes the options listed.
When you choose the option How to use PETIL, you will see a display.
If you click on About Inductive Learning, you will see a description of inductive learning. You can use the scrollbar to entirely see the help screen.
When you have finished consulting the help facility, click on Continue.
If you want to quit PETIL, click on the Exit menu and select the option Quit PETIL.