«Far East Journal of Experimental and Theoretical Artificial Intelligence Volume 1, Issue 2, 2008, Pages 87-125 Published online: August 12, 2008 This ...»
CIRCSIM-Tutor engages in problem-solving dialogues. Each problem is posed as a “procedure” in medical parlance, an influence on the human organism that will affect blood pressure. The student predicts changes to physiological parameters that are involved in blood pressure regulation.
Figure 1 contains a view of the main screen with a description of the procedure that the student is working on, the predictions that the student has made so far, and the start of the remedial dialogue from Session 39 in November, 1999. Figure 2 contains just the dialogue itself.
Figure 1. CIRCSIM-Tutor screen containing a fragment of dialogue from Session 39.
CIRCSIM-Tutor presupposes that students have already been exposed to the relevant physiology. Our system is designed to help MICHAEL S. GLASS and MARTHA W. EVENS students learn to solve problems by asking questions and giving hints, as opposed to giving the student a lecture. So the dialogue in Figure 2 begins with a question.
T: You will now be asked questions regarding the subject matter.
Click on the button or press ENTER when you have finished typing the answer.
T: What are the determinants of Mean Arterial Pressure?
S: Ra T: What parameter in the prediction table relates to Arterial Resistance?
S: TPR T: Right, Arterial Resistance is part of Total Peripheral Resistance, which determines Mean Arterial Pressure.
T: MAP = TPR x what?
T: What is the other determinant of Mean Arterial Pressure?
S: CO T: Right, Cardiac Output is one determinant of Mean Arterial Pressure.
T: Mean Arterial Pressure is determined by Cardiac Output and Total Peripheral Resistance.
T: Which determinant is dominant in this case?
S: CO Figure 2. Dialogue fragment from Session 39.
CIRCSIM-Tutor’s input understander and its operation is the focus of this paper, but we will now describe each of the other major modules very briefly in order to help the reader understand the system context. Woo et al.  and Evens and Michael  provided a more detailed description of the system architecture.
The instructional planner is the central controller of the system .
It fetches and interprets plans from the Knowledge Base, and calls on the other major modules to carry out the steps in those plans. These plans are organized at four different levels. The highest level provides the overall structure for a tutoring session with an individual student. Each session is organized as an introduction followed by a series of problems to solve. Next is the problem level; the rules at this level provide the overall organization for tutoring a problem, beginning with the presentation of
EXTRACTING INFORMATION FOR AN ITS 95the problem, three separate stages of physiological response (the Direct Response Stage, the Reflex Response Stage, and the Steady State Stage), and the problem summary. Next comes the strategy level, with strategies for the problem-solving process and for teaching each topic within the problem. The bottom level is the tactical level, which provides tactics for teaching each concept in each topic.
The student modeler evaluates the student input and reports to the instructional planner about the student’s progress. It categorizes student responses as to whether they are correct, are near misses that the instructional planner can respond to, or exhibit known misconceptions.
Zhou et al. [73, 74] described some of these functions.
The text generator [11, 12] receives instructions from the instructional planner about the communicative goal (whether it is delivering an explanation, a hint, a question, a request, an acknowledgment, etc.) and the semantic content (represented as a logic form) of each sentence. It generates a sentence for display. The text generator uses a Lexical Functional Grammar and a lexicon for some utterances and a library of canned text and templates for others, providing a tradeoff between convenience and expressive power for the system developers. Generating a sentence at a time simplifies the task, but it occasionally produces an incoherent turn. Yang  has developed a turn planner to avoid this difficulty, but it was not available at the time of the experiment described here.
Figure 2 illustrates what happens when CIRCSIM-Tutor asks the student the question “What are the determinants of Mean Arterial Pressure?” and the student answers “Ra”. The instructional planner passes the question (expressed as a logic form) and the student’s input (a string) to the input understander.
The logic form for the question is:
(QUESTION (AFFECTED-BY *MAP*)).
The input understander tries to interpret the input as an answer to the tutor’s most recent question. The lexicon contains “Ra” as an abbreviation for “Arterial Resistance”. There are several possible synonyms in the lexicon which are all abbreviated as Ra internally. The input understander verifies with an ontology of neurological concepts that this answer is conceptually within the domain of possible answers that the MICHAEL S. GLASS and MARTHA W. EVENS system will be able to respond to. (In other words, it verifies that the student did not type “purple cow”.) It returns a logic form to the
The student modeler classifies this particular answer as a “near-miss”, i.e., it is a correct answer, although not the expected answer. The instructional planner decides that the next step is to hint, to push the student toward the expected answer. The planner produces the logic form
for this hint, which is realized as:
T: What parameter in the prediction table relates to Arterial Resistance?
This hint succeeds and the student names a correct parameter. However the original question should have elicited two determinants of MAP; the student has now produced only one. The system then delivers another hint “MAP = TPR * what?” to prompt the student to come up with the other part of the answer.
The New Input Understander
The task of the input understander is to correct spelling errors, if any, expand abbreviations and ellipses so “don’t” becomes “do not”, parse the input, produce the appropriate logic form, determine whether it is really within the domain of things that might constitute an answer or a question from the student, and return the result to the instructional planner. Robustness on the part of the input understander is vital to conducting an interactive dialogue of this type. Earlier versions of the system confused the student by rejecting unexpected but physiologically correct answers as wrong. The system often failed to recognize valid elliptical answers. Not all these issues can be solved by the input understander by itself, but the new software is an essential part of the solution.
The new input understander is based on cascaded finite state machines , a robust approach to language processing developed by the information extraction  community. Information extraction does not attempt to build comprehensive models of the text, but rather to seek out and extract from the text specific bits of knowledge.
EXTRACTING INFORMATION FOR AN ITS 97An alternative to finite state information extracting machines is symbolic parsing of messy text, as exemplified by Lavie’s  GLR* parser, based on Tomita’s Generalized LR Parsing Algorithm .
Tomita’s algorithm replaced the basic stack used in context-free parsing with a more complicated data structure, one that holds the results of many alternative parses at once and combines their common parts. Lavie deals with extragrammatical input by selectively omitting words that do not fit. The parse that succeeds after dropping the fewest words is chosen to represent the probable meaning.
Input understanding starts with the question most recently asked by the system in combination with the student’s response. Table 1 shows example questions and the logic form for each, along with each question’s expected answer. Some of these questions are expressed in different words if the system asks them again, but the content stays the same.
Table 1. Some CIRCSIM-Tutor Questions, Logic Forms, and Answers Here var is a physiological parameter, varlist is a list of parameters, val is +, –, or 0, for values that increased, decreased, or did not change mech is a mechanism of control, i.
e., NEURAL or PHYSICAL, rel is POSITIVE or NEGATIVE, the direction of a relationship between parameters,
Which determinant is dominant in this case?
(QUESTION (ACTUAL-DETERMINANT var)) (ANSWER (ACTUAL-DETERMINANT var)) Which variables are changed by the reflex?
(QUESTION (AFFECT REFLEX varlist)) (ANSWER (AFFECT REFLEX varlist)) Which of the variables in the prediction table are determinants of var?
(QUESTION (AFFECTED-BY var)) (ANSWER (AFFECTED-BY var ((varlist)) )) Will the reflex compensate for the change in Mean Arterial Pressure in DR?
(QUESTION (COMPENSATE REFLEX CHANGE *MAP*)) (ANSWER (y-or-n)) MICHAEL S. GLASS and MARTHA W. EVENS Will the reflex overcompensate for the change in Mean Arterial Pressure in DR?
(QUESTION (OVERCOMPENSATE REFLEX CHANGE *MAP*)) (ANSWER (y-or-n)) By what mechanism is var controlled?
(QUESTION (MECHANISM var)) (ANSWER (MECHANISM (mech) var)) Is the relationship from var-1 to var-2 direct or is it inverse?
(QUESTION (RELATION var-1 var-2)) (ANSWER ((rel) var-1 var-2)) What stage must the value of var follow in SS?
(QUESTION (FOLLOW var)) (ANSWER (stage)) Which variable is regulated by the baroreceptor reflex?
(QUESTION (REGULATE BARORECEPTOR-REFLEX var)) (ANSWER (var)) What is the correct value of var?
(QUESTION (VALUE var)) (ANSWER (VALUE var val)) What is the value of var in DR?
(QUESTION (VALUE-DR var)) (ANSWER (VALUE-DR var val)) Note: There are two more logic forms for RR and SS similar to VALUE-DR.
The input understander carries out the following stages of processing for each new piece of student input, as illustrated in the block diagram in
• Look up words in the lexicon
• Correct spelling (which is combined with lexical lookup)
• Recognize student initiatives and hedges using a finite state transducer
• Recognize possible answers to the question at hand with a cascade of finite state transducers
• Produce a logic form and check for errors
EXTRACTING INFORMATION FOR AN ITS 99Figure 3. Organization of the input understander.
Lexical lookup and spelling correction Spelling correction is an essential function in a system that accepts free text from users. In a dialogue situation, coming back to the user with a list of alternatives to a misspelled word is distracting. Our spelling correction is a process of quickly finding the closest match in the lexicon to the unrecognized word (Lee and Evens , and Elmi and Evens ).
A two-letter sliding window compares the i-th and (i + 1) -th letters of the unknown word with the j-th and ( j + 1) -th letters of a candidate word in the lexicon. The match process detects elided, added, and changed characters, as well as character reversals, which are common in keyboard entry. Weights are assigned to each mismatch in a scoring scheme informed by published data and our own experience. The result is a list of MICHAEL S. GLASS and MARTHA W. EVENS words from the lexicon with the lowest weighted error score. To increase the chance of correctly recognizing a word, most common abbreviations in our domain are included in the lexicon along with some common mistypings like “hte” for “the”. Given that we have observed users abbreviating words by shortening them, letters that have been dropped from the end of a word are weighted less than letters dropped from the middle.
There is a certain amount of polysemy built into our domain. Much of the tutoring revolves around qualitative change in cardiovascular parameters, and the major verbs of change in English are consistently spelled the same way as associated verbal nouns, like increase, decrease, rise, fall, and change itself. More polysemy is introduced by systematic abbreviation used in the physiology sessions we are automating.
Students use the letter D to stand for “direct” as well as “decrease” and “down”; similarly, the letter I indicates “inverse” or “indirect” as well as “increase”. The plus sign is used for both “increase” and “direct”. The minus sign (which also doubles as a hyphen) is used to signify both “decrease” and “indirect”.
Students in our experiments rarely use the string “I ” to indicate a personal pronoun in an answer to a system question. The personal pronoun does appear in hedges and student initiatives, as described below.
The handling of phrases in the lexical lookup phase is based on the “maximal munch” strategy. The system takes the longest phrase in the lexicon that matches the next segment of input words. To speed up this strategy we built a table of all proper prefixes of phrases in the lexicon. A proper prefix is a sequence of words up to but not including the whole phrase. For example “right” and “right atrial” are the proper prefixes of “right atrial pressure”.
Recognizing student initiatives and processing hedges Before the system attempts to extract an answer from the student utterance, two confounding factors are disposed of. The utterance is checked to see if it is a student initiative instead of an answer. If it is not an initiative, student hedges are recognized and stripped out.