Processing Question-Answer Pairs In Tutor
and the Tutor Research Group
Department of Mathematical Sciences
April 29, 1998
Abstract
This paper describes a solution to the problem of processing Question-Answer pairs in Tutor. Processing a Question-Answer pair involves both detection that the given input is within a class of questions and if so, returning the correct answer to the question. Tutor, an automated tutoring system, is described, with the emphasis on the student’s collaborative dialogue with the software agent. Tutor’s curriculum scripts, which comprise the subject agenda, are then discussed, with the focus on the script’s Question-Answer pairs. A corpus of potential student questions has been generated, and both the methods of generation and corpus components are detailed. There is then discussion on the research which inspired the current implementation method. The implementation algorithm to handle the Question-Answer pairs is then detailed. Results on how the program performs and future extensions are discussed.
Introduction
Tutor is an automated tutoring system currently being developed by the Tutor Research Group at the University of Memphis (Graesser et al., 1998; Graesser et al., 1997). Tutor performs the collaborative dialogue found in human tutoring (Graesser, Person, & Magliano, 1995). Tutor presents the student with information from a curriculum script, described in the next section. Tutor takes a student’s input from the keyboard. This contribution is classified into the appropriate speech act (i.e. statement, question, exclamation). From that, Tutor uses natural language processing techniques such as Latent Semantic Analysis to determine the correctness of the student response (Landauer, Foltz, & Laham). Once the student contribution is rated, fuzzy dialog moves are utilized to determine Tutor’s next communication to the student. Tutor may give the student a hint, prompt for more information, display a summary, etc. Tutor communicates with students via text, illustrations, and cartoon-like agents (Microsoft Corporation, 1998). The questions Tutor asks a student are designed to create a collaborative dialogue between the tutee and Tutor; Tutor’s questions are not designed to elicit one word responses.
Within this dialog exchange, the student may ask Tutor a question. The questions Tutor asks the student are known as Tutor questions, while the cases where the student desires a response are known as tutee questions. Tutee questions are often focused on definitional clarification of a word found in the Tutor question. For example, the tutee might ask, "What does pixel mean?" While clearly not all tutee questions are of this type, in this paper tutee questions refer to only questions of this definitional clarification nature unless otherwise noted. Tutee questions requiring a canned definitional response are known as Question-Answer pairs. It is predicted that Tutee questions will follow the model predicted by QUEST, a cognitive model on question answering (Graesser & Franklin, 1990).
This paper describes the resolution to the problem of processing Question-Answer pairs when received by Tutor. Tutor’s curriculum scripts are presented. These scripts comprise Tutor’s agenda, and contain the expected tutee questions, along with the appropriate answers. The current corpus of tutee questions is described. This corpus is utilized both in the curriculum scripts and in the creation of a grammar for the natural language processing portion of Tutor which handles question-answer pairs. Research related to this portions implementation is explored. The implementation is then detailed. Finally, initial results and potential future extensions of this program are described.
Curriculum Scripts
Tutor’s agenda is set by predetermined scripts, known as curriculum scripts. A curriculum script is "a loosely ordered but well defined set of skills and concepts students are expected to learn, along with the activities and strategies for teaching this material" (Putnam, 1987). Currently, Tutor has one curriculum script in the domain of Computer Literacy. Each script is broken down into three topics (i.e. Computer Hardware, Operating Systems, and the Internet). Each topic is broken into a series of broad based questions, known as subtopics, which are constructed into easy, medium, and hard difficulty levels in accordance with Bloom’s taxonomy of cognitive objects (Bloom, 1956). These subtopic questions are designed to elicit a collaborative dialog with the tutee, not simply a one word response. Currently there are thirty-seven subtopics.
Each subtopic contains an ideal student response. It also contains potential student good answers, bad answers, and good and bad keywords which might make up these answers. Student’s contributions, if classified as a potential answer by a speech act classifier, are compared, using Latent Semantic Analysis, to the ideal answer and a relevant Computer Literacy corpus to get the accuracy of the contribution (Landauer, et. al, 1997). Depending on the student’s response, Tutor’s action selection mechanism determines one of several actions. Hints, prompts, elaborations, and a summary are all actions, represented within the subtopic, which can be presented to the tutee. Tutor can also choose to move onto the next subtopic.
Each subtopic also contains potential tutee questions. A current subtopic from the Internet topic, medium difficulty, is, "How does remote login via Telnet work?" In this case, potential Computer Literacy tutee questions would most likely be about remote login and telnet. For example, a student may ask, "What is telnet," "What does telnet mean," "What is the definition of telnet," etc.
Since there are many ways of representing tutee questions, they are simply represented in the curriculum script by the question’s focus keyword (i.e. remote login, telnet). The answer to the question is paired to the keyword. For example, if the student asks about remote login, the answer returned is, "Remote login is the ability of a user on one system to access other host systems across a network." Currently, these answers are content-independent across subtopic. In other words, if another subtopic addresses remote login in a different context, the answer associated with the keyword will be the same.
Question Corpus
A corpus of potential questions has been generated. This corpus was generated by presenting approximately one hundred Computer Literacy students with a random distribution of twelve of the thirty-seven topics at the start of the Spring 1998 semester. At the end of the semester, the same students were presented with six of the subtopics they had previously answered and six randomly chosen ones. Student’s were given extra credit for "thoughtful" work as hopeful incentive for thoughtful responses. Currently only the responses to the initial semester querying have been analyzed.
After answering each subtopic question, student’s were asked, "What are the most difficult parts of this question?" Student’s responses were of the form of both questions and statements. An example student question is, "What are peripherals" (punctuation not included by the student). An example student statement is, "Not knowing the exact function of the CPU." Student questions were added to the corpus if they were of the definitional clarification type. Also, appropriate student statements were converted to questions. In doing so, extreme effort was used to place as many words as possible from the original statement into the generated question. For example, the above statement was converted to, "What is the exact function of the CPU?" As Tutor moves into the initial testing phase, this corpus will be augmented by actual tutee responses and by input from an expert in the field. This corpus represents a significant advance on its own as it represents potential student questions across the Computer Literacy domain.
When analyzing this corpus, it becomes evident there is a fixed number of introductory "stems" students use to phrase their questions (i.e. What’s the definition of, What are, I don’t understand what, etc.). Each of these stems is followed by one or more of the keywords found in the curriculum script. A Question-Answer pair question, therefore, can be considered to be a tutee question which contains one of the definitional stems immediately followed by one or more keywords from the curriculum script. The remaining sections discuss the techniques currently used to detect Question-Answer pair questions and return the appropriate answer.
Related Research
The current implementation has its roots in partial syntactic bottom-up chart parsing, semantic grammars, template matching, and compiler symbol table design (Allen, 1995; Aho, Sethi, & Ullman, 1988). When representing grammar rules as a tree, a bottom-up parser begins at the leaves, matching its current input to the grammar rules’ right-hand side. To avoid the parser duplicating its matching attempts, a chart storing partial results is utilized. Keys, such as NP for noun phrase, are used to represent a focal portion of each grammar rule.
Partial parsing is often used in ambiguity resolution, focusing on fragments of sentences which can be accurately classified. While most sentences cannot be completely parsed using this technique, certain structures can be reliably identified: noun groups, verb groups, and proper noun phrases. In partial parsing, syntactic fragments are placed on the chart by the bottom-up parser for use in later processing, such as during semantic interpretation.
Semantic grammars, while not readily portable across domains, are useful in areas where there is a specific context. In these cases, a semantic grammar rule can replace the more general syntactic rule. Often there is a semantic grammar rule for each of the domain’s significant semantic categories. Semantic grammar rules facilitate input interpretation as the necessary semantic information is encapsulated within the rule.
Template matching techniques utilize the fact that in certain domains, only very specific information needs to be understood. These techniques often perform more successfully than a generalized syntactic to semantic based parser. In template matching systems, simple patterns are indicated which specify important domain information. When found, these keys are used to fill representative templates. There can be a template for each major element in the domain (i.e. one for each class of potential input). Template matching systems normally parse input to the identification of noun phrases and where variant forms of words are simplified. Template matching systems have successfully been utilized in domains such as the understanding of email messages (Zhang et. al, 1998; Bogner, 1998, pp. 16-18).
The symbol table plays an essential role in compilers. During the lexical analysis phase, when an identifier is recognized, it is placed on the symbol table. In later phases of the compilation process, such as during semantic analysis and intermediate code generation, additional information about the identifier is placed into the symbol table and utilized. Symbol table routines are primarily concerned with the storage and retrieval of lexemes and reserved keywords. In the retrieval phase, a symbol is searched for every time a keyword is encountered in the input. Hash tables are a common technique for symbol table representation. Hashing’s appeal is the constant time, on average, for dictionary operations (Aho & Ullman, 1992, pp. 348, 351).
Question-Answer Pair Processing
This section describes the portion of Tutor which processes Question-Answer pairs, known through the remainder as Qa_pairs. Qa_pairs draws heavily from partial parsing techniques, and utilizes hash tables for template matching. The implementation is relatively straight forward, and is easily extensible. The implementation does a very effective job of:
There are two forms of this module. The first, compiled in Tutor, is a Qa_pairs library. The functions described in the following sections are all contained in this library. The second form is that of a stand alone program, which contains the library plus a menu of choices allowing for individual testing and demonstration of this specific module. The code is written in ANSI C. C was chosen for its cross-platform portability, speed, easy and well documented interface techniques with other languages, and its flexibility in dealing with streams of text.
Grammar Representation
Qa_pairs allows an extremely flexible grammar representation. A complete grammar in the sense of representing full sentences is not specified. Instead, the grammar represents only the question stems, discussed above, which are found in Question-Answer pairs. Specifically, each rule should represent a specific stem. For example, a possible rule could represent, "What is", "What’s," etc. Grammar rules are separated by the newline character. There are three grammar forms which over Tutor’s lifetime have the most likely potential to be utilized:
Curriculum Script Representation
A specific file format for the curriculum script files has been developed (Bogner, 1998). This file contains each topic and its associated members. Each portion is signified by a series of tags (i.e. \ideal1 to represent the ideal answer of topic one). Qa_pairs processes the curriculum script file in its standard format. Specifically, Qa_pairs utilizes each subtopic’s Question-Answer pairs.
Internal Representation of Grammar and Question-Answer Pairs
Two hash tables, grammar_hash and qa_pairs_hash, are used to store the grammar rules and Question-Answer pairs respectively. The function read_in_grammarfile and its associated functions are responsible for reading in the grammar rules and placing them in grammar_hash. Each grammar rule as a whole is used as the hashing key. Therefore, there is one bucket per grammar rule. The bucket holds no other information but the grammar rule. Currently for simplicity, all elements of the rule are capitalized before placement in grammar_hash.
The function read_in_scriptfile and its associated functions are responsible for reading in the Question-Answer pairs from the script file and placing them in qa_pairs_hash. Each question keyword (i.e. RAM) is used as the hashing key. Each bucket not only contains the question keyword but also the appropriate answer. When read in, the question keywords are capitalized before being placed in qa_pairs_hash. Both the grammar file and the curriculum script can be read into Qa_pairs while the program is running; therefore, the grammar rules or question-answer pairs can be modified on the fly.
Parsing Tutee Contributions
The student’s input contribution is passed to the parse_input function and converted to all uppercase. This method allows for the grammar rules described in section 6.1, number 3. In the future, if student input is syntactically or semantically parsed, then Qa_pairs can already correctly handle other rule types.
The algorithm used in parse_input is:
Results and Conclusions
Qa_pairs is a module which is currently being placed in Tutor. As a standalone program, it appears to work extremely well in initial testing. The question stems from the corpus have been used in the grammar file, and the Computer Literacy curriculum script file gets entered and interally represented. Several users have acted as tutees, and there have been approximately one hundred contributions entered. For every case, Qa_pairs found whether or not the contribution was a Question-Answer pair question. In all cases but one, the keyword was detected and the appropriate answer returned. The one keyword which was not detected, "486/25", was treated as two words. This problem has been rectified. Strenuous testing should occur relatively soon when this module is completely integrated with Tutor. Answer retrieval happens at almost immediate speed.
Qa_pairs provides a rapid, simple, and effective way to hand Tutor’s Question-Answer pairs. Over time, the module has the potential to be extended. Student contributions could be parsed, and a synonym check could be done on the student’s input to see if the appropriate keyword is closely represented. As this is only the first year of a multi-year NSF grant, hopefully, many of these extensions can be implemented.
References
Aho, A., Sethi, R., & Ullman, J. (1986). Compilers: Principles, techniques, and tools.
Reading, MA: Addison-Wesley Publishing Company.
Aho, A. & Ullman, J. (1992). Foundations of computer science. New York: Computer
Science Press, 348, 351.
Allen, J. (1995). Natural language understanding. Redwood City, CA: The
Benjamin/Cummings Publishing Company, Inc.
Bloom, B. (1956). "Taxonomy of educational objectives: The classification of educational
goals." Handbook I: Cognitive domain. New York: McKay.
Bogner, M. (1998). Creating a conscious agent. Unpublished master’s thesis, The University of
Memphis, 16-18.
Bogner, M. (1998). Tutor’s curriculum script format.
http://www.msci.memphis.edu/~bognerm/cur_script/script_format.html.
Graesser, A. & Franklin, S. (1990). "QUEST: A cognitive model of question answering".
Discourse processes, 13, 279-303.
Graesser, A., Person, N., & Magliano, J. (1995). "Collaborative dialogue patterns in naturalistic
one-on-one tutoring". Applied cognitive psychology, 9, 359-387.
Graesser, A. & the Tutor Research Group. (1997). Simulating tutors with natural dialog and
pedagogical strategies. http://www.psyc.memphis.edu/TRG/NSFproposal.htm.
Graesser, A. & the Tutor Research Group. (1998). Text for Society and Discourse symposium
proposal. http://www.psyc.memphis.edu/trg/st&d1998.htm.
Landauer, T., Foltz, P., & Laham, D. Introduction to Latent Semantic Analysis.
Landauer, T., Laham, D., Rehder, B., & Schreiner, M. (1997). "How well can passage meaning
be derived without using word order? A comparison of Latent Semantic Analysis and
humans." Proceedings of cognitive science, 1997.
Microsoft Corporation. (1998). Microsoft agent. http://www.microsoft.com/intdev/agent.
Putnam, R. (1987). Structuring and adjusting content for students: A study of live and simulated
tutoring of addition. American educational research journal, 24, 13-48.
Zhang, Z., Olde, B., Graesser, A., & Wan, Y. (1998, to appear). "Natural language sensing for
autonomous agents". International IEEE joint symposia on intelligence and sytems.