A Revised Algorithm for Latent Semantic Analysis

1 Introduction

The use of intelligent technology in education is on the rise. Inte lligent tutoring systems, once restricted to artificial in­ telli gence Jabs at major universities, are migrating to main­ stream schools [Koedinger et a!., 1997]. Intelligent tutoring systems (ITS) in this environment face a difficult challenge: to understand the student and manage the tutoring session in the face of vague or ungrammatical input. FormostiTSs, lan­ guage understanding and dialog management are core com­ ponents. Particularly in a classroom, these systems Jive or die by their ab.ility to understand w?at the student is trying to say. One techruque, Latent Semantic Analysis has been success­ fully developed for such purposes [Landauer et at., 1998b; Landauer and Dumais, 1997; Foltz et at., 1998; Graesser et a!., 2002]. LSA, a statistical technique utilizing unsupervised learning, .is both highly portable to other domains and adept at recogn1zmg vague or incomplete input.

This paper outlines some problems inherent in the tradi­ tional LSA algorithm and solutions to this problem by using a different LSA algorithm. Not only does this new algorithm increase the precision of ITS language understanding, but it also offers a new perspective on a commonly used technique in cognitive science, computational linguistics and artificial intelligence.

1.1 Latent Semantic Analysis

Latent Semantic Analysis is a statistical, corpus-based lan­ guage understanding technique that estimates similarities on a scale of- I to I between the latent semantic structure of terms and texts [Deerwester eta!., 1990]. The input to LSA is a set of corpora segmented into documents . These documents are typically paragraphs or sentences. Mathematical transfor­ mations creat~ a large term-document matrix from the input. For example, 1f there are m terms inn documents (usually m and n are very large, for now, assume n ~ m) , then a matrix o.f ~ = f;j X G (j) XL (i,j)mxn is obtained. The value of ];j IS a function of the integer that represents the number of times term i appears in document j L (i, j) is a loca l weight­ Ing of term i in document j and G ( i) is the global weighting for term i. Such a weighting function is used to differentially treat terms and documents to reflect knowledge that is be­ yond the collection of the documents. This matrix of A has however, lots of redundant information . Singular value de~ composition reduces this noise by linearly decomposing the matrix A into three matrices A = U I: VT ; U is m x m and V is n x n square matrices such that UU 1 = I · T . '. ·m x rn' VV = Inx n, and L IS m X n diagonal matrix with singular values on the diagonal. By removing dimensions corre­ sponding to small singular values and keeping the dimensions corresponding to larger singular values, the representation of e~ch te:m is further reduced to a smaller vector with only k dlll1ensiOns. The new representation for the terms (the re­ duced U matrix) are no longer orthogonal, but the advan­ tage of this is that only the most important dimensions that correspond to larger singular values are kept. This method of statistically representing knowledge has proven to be use­ ful in a range of studies. For instance, studies have shown that LSA performs as well as students on TOEFL (test of English as a foreign language) tests [Landauer and Dumais 1997], that it grades essays as reliably as humans [Landaue~ et a!., 1998a] and that it reliably measures the coherence between a sentence and successive sentences [Foltz et a!. , 1998]. Finally, LSA has successfully been used in intelli­ gent tutoring systems like Auto Tutor [ Graesser et a!. 2002· 1999]. , ,

1.2 AutoThtor

AutoTutor is a conversational agent that assists students in actively constructing knowledge by holding a conversation in natural language with them [Graesser et a!., 200 I] . In ad­ dition to latent semantic analysis, at least four other components can be distinguished: I) a dialog management sys­ tem guides the student through the tutor-student conversa­ tion. Fuzzy production rules and a Dialog Advancer Network fonn the basis of these conversational strategies; 2) curricu­ lum scripts organize the pedagogical macrostructure of the tutorial. These scripts keep track of the topic coverage and follow up on any problems the student might have; 3) a talk­ ing head with facial expressions and synthesized speech is used for the interface. Parameters of the facial expressions and rudimentary gestures are generated by fuzzy production rules; 4) mixed-initiative dialog, including the appropriate use of discourse markers to make the conversation smoother; a speech act classifier that accounts for the pragmatics of in­ coming expressions; and a question answering tool that dy­ namically answers student questions on a variety of topics.

AutoTutor was originally developed for computer literacy. Over the last two years a web version of Auto Tutor was de­ veloped that tutors in conceptual physics. In both domains world knowledge is provided by LSA spaces of domain spe­ cific text books.

2 An improved LSA algorithm

At the beginning of a session, Auto Tutor presents a question to the student, and the student responds to this question. Au­ toTutor analyzes the accuracy of this answer by comparing the student's answer with a series of expected ideal answers. Over the course of the tutoring session, the student covers each of the expectations. The tutor allows the student to move to the next problem only once all expectations are covered.

Although possible in theory, a single contribution from a student usually does not cover aU expectations at once. In­ stead, the student simply types one sentence at a time in the conversation with the tutor. Based on the student's responses, the tutor will then provide appropriate feedback based on the quality of responses. To provide feedback to a student's con­ tributions, the tutoring system needs to know the following:

1. information related to the expected answer elements that is I) new (what was not in the previous contributions); 2) old (what was in the previous contributions)
2. information not related to the expected answer elements that is I) new (what was not in the previous contribu­ tions); 2) old (what was in the previous contributions)

Depending on these four components, AutoTutor chooses the most appropriate feedback. This mechanism for student contributions is illustrated in Table I. For example, Auto­ Tutor needs to provide highly positive feedback when stu­ dents provide new relevant information (cell labeled++). For relevant but repeated information (cell labeled+) , AutoTutor needs to provide only some non-negative feedback. For irrel­ evant contributions, AutoTutor needs to point out the repeated misconceptions, eventually with negative feedback (cell with - -). The system returns non-positive feedback in cases of irrelevant information occurring the first time (cell with-).

The challenge for AutoTutor is to obtain information that belongs to each of the cells in the table. That is, the system needs to take into account both the relevance of the informa­ tion and whether or not the information is new.

• Question: Suppose a runner is running in a straight line at constant speed and throws a pumpkin straight up. Where will the pumpkin land? Explain why.
• Expectation: The pumpkin will land in the runner's hands .
• Student contributions:
• (I) I think, correct me if I am wrong, it will not land before or behind the man.
• The reason is clear, they have the same horizontal speed.
• The pumpkin will land in the runner's hand .
• Did I say anything wrong?
• Come on, I thought I have said that.

In earlier versions ofthe system, AutoTutor put all the stu­ dent contributions (from the first response to the most recent response) together as one document and would then compare with the expectation. One of the reasons for this was that it has often been claimed that the best performance in LSA comes from paragraphs rather than sentences (see [Foltz et a/., 1998]). However, simple vector algebra shows that vec­ tor summation of term-vectors for the combined contributions may in fact reduce the similarity between the expectation and contributions when contributions are added. This reduction is evident in the example given in second column of Table 2. The tutor asks the student a question at the start of a concep­ tual physics problem. The student's answer is matched with an ideal expected answer. The question now is what happens to the LSA coverage scores if the student submits (new/old) (relevant/irrelevant) multiple contributions.

From the expected answer we know that a student's answer like (I) is almost correct. Now imagine that the student an­ swers (2). The cosine match drops, resulting in AutoTutor asking for more information. Now assume that the student also answers (3), which is the exact ideal answer. Using a traditional vector addition algorithm, the similarity is not 1.0. This loss of precision results from the noise introduced by the irrelevant information in the student's answers. By adding the contributions' vectors, the system cannot distinguish between the different parts (new/old) (relevant/irrelevant) of the student's contributions. So although LSA effectively com­ pares semantic similarities between two large documents, LSA lacks precision for comparing smaller documents in a progressive sequence. Under a vector-addition model, a stu­ dent whose answers improve dramatically over the course of the tutoring session is "penalized" for an initial bad answer. To so lve this limitation, we propose an alternative solution. Instead of s imply combining contributions into a larger docu­ ment , each contribution is treated as "independent" in avec­ tor subspace. The combination of the contributions is then not represented as a simple vector summation, but instead as a span in the subspace. This way, the vector for any new contri bution can be algebraically decomposed into two com­ ponents. One component is the projection of the vector to the spanned subspace of the previous contributions, and the other component is perpendicular to the subspace. These two com­ ponents of the most recent contribution correspond to relevant information (projection to the subspace) and new information (the perpendicular component). Finally, the cosine match of the new infom1ation with the expectation is the measure of new (additional) coverage of the expectations. We applied this method to the example such as Table 2 and observed desirable increase in LSA's precision, as illustrated in col­ umn 3,4, and 5 of Table 2. The rows of Table 2 present the five student contributions. The column 'New Info' gives the pe rcentage of new information for each of the contributions, compared to the previous contributions. The third column is the relevance ofthe new contribution to the span. The final two co lumns give the old and new LSA scores.

Although contribution (3) is identical to the expectation, it sti ll is only 88% new. The reason is that contributions (I) and (2) already contain some of the information from (3 ). For example, although (2) contains 99% new information, it has only marginally (0.175) contributed as coverage. Notice that the quality in the subsequent student contributions does not deteriorate, but the old LSA values do. The new LSA values, on the other hand, account for additional relevant informa­ tion, even bringing the coverage score to the maximum value of I.

The method provided here can be used to compute all four cells in Table I, because it differentiates whether the informa­ tion is new or old, and whether it is relevant or not. Further­ more, since it provides information at every step, numerical information of the values can be used to provide secondary information for feedback . For example, the rate of increase in the new LSA algorithm provides us with information on the development student performance on a step-by-step ba­ sis. By being able to localize LSA scores, AutoTutor can now determine the effectiveness of its dialog moves.

The proposed new algorithm can potentially be used in ap­ plications I ike essay grading, where the student's compos it ion covers the key elements for a given essay. The algorithm can measure development of student performance and can take into account whether information is old or new, relevant or irrelevant.

3 Conclusion

This paper addressed the use of latent semantic analysis in intelligent tutoring systems like Auto Tutor. Despite the suc­ cess of LSA in Auto Tutor, previous versions were not able to differentiate between relevant/irrelevant or new/old infom13tion in student contributions. Replacing the vector-addition based algorithm with a span-based algorithm does not only improve Auto Tutor's evaluation of student contributions, but is most likely to improve LSA performance in a wide range of other natural language understanding applications.