Computer information retrieval using latent semantic structure4839853Abstract A methodology for retrieving textual data objects is disclosed. The information is treated in the statistical domain by presuming that there is an underlying, latent semantic structure in the usage of words in the data objects. Estimates to this latent structure are utilized to represent and retrieve objects. A user query is recouched in the new statistical domain and then processed in the computer system to extract the underlying meaning to respond to the query. Claims What is claimed is: Description FIELD OF THE INVENTION
TABLE 2
______________________________________
DOCUMENTS
TERMS c1 c2 c3 c4 c5 m1 m2 m3 m4
______________________________________
human 1 0 0 1 0 0 0 0 0
interface
1 0 1 0 0 0 0 0 0
computer
1 1 0 0 0 0 0 0 0
user 0 1 1 0 1 0 0 0 0
system 0 1 1 2 0 0 0 0 0
response
0 1 0 0 1 0 0 0 0
time 0 1 0 0 1 0 0 0 0
EPS 0 0 1 1 0 0 0 0 0
survey 0 1 0 0 0 0 0 0 1
tree 0 0 0 0 0 1 1 1 0
graph 0 0 0 0 0 0 1 1 1
minor 0 0 0 0 0 0 0 1 1
______________________________________
For this example the documents and terms have been carefully selected to yield a good approximation in just two dimensions for expository purposes. FIG. 1 is a two dimensional graphical representation of the two largest dimensions resulting from the statistical process, singular value decomposition. Both document titles and the terms used in them are fit into the same space. Terms are shown as circles and labeled by number. Document titles are represented by squares with the numbers of constituent terms indicated parenthetically. The cosine or dot product between two objects (terms or documents) describe their estimated similarity. In this representation, the two types of documents form two distinct groups: all the mathematical graph theory occupy the same region in space (basically along Dimension 1 of FIG. 1) whereas a quite distinct group is formed for human/computer interaction titles (essentially along Dimension 2 of FIG. 1). To respond to a user query about "human computer interaction," the query is first folded into this two-dimensional space using those query terms that occur in the space (namely, "human" and "computer"). The query vector is located in the direction of the weighted average of these constituent terms, and is denoted by a directional arrow labeled "Q" in FIG. 1. A measure of closeness or similarity is related to the angle between the query vector and any given term or document vector. One such measure is the cosine between the query vector and a given term or document vector. In FIG. 1 the cosine between the query vector and each c1-c5 titles is greater than 0.90; the angle corresponding to the cosine value of 0.90 with the query is shown by the dashed lines in FIG. 1. With this technique, documents c3 and c5 would be returned as matches to the user query, even though they share no common terms with the query. This is because the latent semantic structure (represented in FIG. 1) fits the overall pattern of term usage across documents. Description of Singular Value Decomposition To obtain the data to plot FIG. 1, the "term-by-document" matrix of Table 2 is decomposed using singular value decomposition (SVD). A reduced SVD is employed to approximate the original matrix in terms of a much smaller number of orthogonal dimensions. This reduced SVD is used for retrieval; it describes major associational structures in the matrix but it ignores small variations in word usage. The number of dimensions to represent adequately a particular domain is largely an empirical matter. If the number of dimensions is too large, random noise or variations in word usage will be remodeled. If the number of dimensions is too small, significant semantic content will remain uncaptured. For diverse information sources, 100 or more dimensions may be needed. To illustrate the decomposition technique, the term-by-document matrix, denoted Y, is decomposed into three other matrices, namely, the term matrix (TERM), the document matrix (DOCUMENT), and a diagonal matrix of singular values (DIAGONAL), as follows: Y.sub.t,d TERM.sub.t,m DIAGONAL.sub.m,m DOCUMENT.sup.T hd m,d where Y is the original t-by-d matrix, TERM is the t-by-m DOCUMENT matrix with unit-length orthogonal columns, and DIAGONAL is the m-by-m diagonal matrix of singular values typically ordered by magnitude. The dimensionality of the full solution, denoted m, is the rank of the t-by-d matrix, that is, m.ltoreq.min(t,d). Tables 3, 4 and 5 below show the TERM and DOCUMENT matrices and the diagonal elements of the DIAGONAL matrix, respectively, as found via SVD.
TABLE 3
__________________________________________________________________________
TERM MATRIX (12 terms by 9 dimensions)
__________________________________________________________________________
human
0.22
-0.11
0.29
-0.41
-0.11
-0.34
-.52
-0.06
-0.41
interface
0.20
-0.07
0.14
-0.55
0.28
0.50
-0.07
-0.01
-0.11
computer
0.24
0.04
-0.16
-0.59
-0.11
-0.25
-0.30
0.06
0.49
user 0.40
0.06
-0.34
0.10
0.33
0.38
0.00
0.00
0.01
system
0.64
-0.17
0.36
0.33
-0.16
-0.21
-0.16
0.03
0.27
response
0.26
0.11
-0.42
0.07
0.08
-0.17
0.28
-0.02
-0.05
time 0.26
0.11
-0.42
0.07
0.08
-0.17
0.28
-0.02
-0.05
EPS 0.30
-0.14
0.33
0.19
0.11
0.27
0.03
-0.02
-0.16
survey
0.20
0.27
-0.18
-0.03
-0.54
0.08
-0.47
-0.04
-0.58
tree 0.01
0.49
0.23
0.02
0.59
-0.39
-0.29
0.25
-0.22
graph
0.04
0.62
0.22
0.00
-0.07
0.11
0.16
-0.68
0.23
minor
0.03
0.45
0.14
-0.01
-0.30
0.28
0.34
0.68
0.18
__________________________________________________________________________
As alluded to earlier, data to plot FIG. 1 was obtained by presuming that two-dimensions are sufficient to capture the major associational structure of the t-by-d matrix, that is, m is set to two in the expression for Y.sub.y,d, yielding an approximation of the original matrix. Only the first two columns of the TERM and DOCUMENT matrices are considered with the remaining columns being ignored. Thus, the term data point corresponding to "human" in FIG. 1 is plotted with coordinates (0.22,-0.11), which are extracted from the first row and the two left-most columns of the TERM matrix. Similarly, the document data point corresponding to title m1 has coordinates (0.00,0.19), coming from row six and the two left-most columns of the DOCUMENT matrix. General Model Details It is now elucidating to describe in somewhat more detail the mathematical model underlying the latent structure, singular value decomposition technique. Any rectangular matrix Y of t rows and d columns, for examples, a t-by-d matrix of terms and documents, can be decomposed into a product of three other matrices: Y=T.sub.o S.sub.o D.sup.T.sub.o, (1) such that T.sub.o and D.sub.o have unit-length orthogonal columns (i.e. T.sub.o.sup.T T.sub.o =I;D.sub.o.sup.T D.sub.o =I) and S.sub.o is diagonal. This is called the singular value decomposition (SVD) of Y. (A procedure for SVD is described in the text Numerical Recipes, by Press, Flannery, Teukolsky and Vetterling, 1986, Cambridge University Press, Cambridge, England). T.sub.o and D.sub.o are the matrices of left and right singular vectors and S.sub.o is the diagonal matrix of singular values. By convention, the diagonal elements of S.sub.o are ordered in decreasing magnitude. With SVD, it is possible to devise a simple strategy for an optimal approximation to Y using smaller matrices. The k largest singular values and their associated columns in T.sub.o and D.sub.o may be kept and the remaining entries set to zero. The product of the resulting matrices is a matrix Y.sub.R which is approximately equal to Y, and is of rank k. The new matrix Y.sub.R is the matrix of rank k which is the closest in the least squares sense to Y. Sine zeros were introduced into S.sub.o, the representatin of S.sub.o can be simplified by deleting the rows and columns having these zeros to obtain a new diagonal matrix S, and then deleting the corresponding columns of T.sub.o and D.sub.o to define new matrices T and D, respectively. The result is a reduced model such that Y.sub.R =TSD.sup.T. (2) The value of k is chosen for each application; it is generally such that k.gtoreq.100 for collections of 1000-3000 data objects. For discussion purposes, it is useful to interpret the SVD geometrically. The rows of the reduced matrices T and D may be taken as vectors representing the terms and documents, respectively, in a k-dimensional space. With appropriate rescaling of the axes, by quantities related to the associated diagonal values of S, dot products between points in the space can be used to access and compare objects. (A simplified approach which did not involve rescaling was used to plot the data of FIG. 1, but this was strictly for expository purposes.) These techniques are now discussed. Fundamental Comparisons There are basically three types of comparisons of interest: (i) those comparing two terms; (ii) those comparing two documents or text objects; and (iii) those comparing a term and a document or text object. As used throughout, the notion of a text object or data object is general whereas a document is a specific instance of a text object of data object. Also, text or data objects are stroed in the computer system in files. Two Terms: In the data, the dot product between two row vectors of Y.sub.R tells the extent to which two terms have a similar pattern of occurrence across the set of documents. The matrix Y.sub.R Y.sup.T .sub.R is the square symmetric matrix approximation containing all the term-by-term dot products. Using equation (2), Y.sub.R Y.sup.T.sub.R =(TSD.sup.T)(TSD.sup.T).sup.T =TS.sup.2 T.sup.T =(TS)(TS).sup.T. (3) This means that the dot product between the i-th row and the j-th row of Y.sub.R can be obtained by calculating the dot product between the i-th and j-th rows of the TS matrix. That is, considering the rows of TS as vectors representing the terms, dot products between these vectors give the comparison between the terms. The relation between taking the rows of T as vectors and those of TS as vectors is simple since S is a diagonal matrix; each vector element has been stretched or shrunk by the corresponding element of S. Two Documents: In this case, the dot product is between two column vectors of Y. The document-to-document dot product is approximated by Y.sup.T.sub.R Y.sub.R =(TSD.sup.T).sup.T (TSD.sup.T)=DS.sup.2 D.sup.T =(DS)(DS).sup.T. (4) Thus the rows of the DS matrix are taken as vectors representing the documents, and the comparison is via the dot product between the rows of the DS matrix. Term and Document: This comparison is somewhat different. Instead of trying to estimate the dot product between rows or between columns of Y, the fundamental comparison between a term and a document is the value of an individual cell in Y. The approximation of Y is simply equation (2), i.e., Y.sub.R =TSD.sup.T. The i,j cell of Y.sub.R may therefore be obtained by taking the dot product between the i-th row of the matrix TS.sup.1/2 and the j-th row of the matrix DS.sup.1/2. While the "within" (term or document) comparisons involved using rows of TS and DS as vectors, the "between" comparison requires TS.sup.1/2 and DS.sup.1/2 for coordinates. Thus it is not possible to make a single configuration of points in a space that will allow both "between" and "within" comparisons. They will be similar, however, differing only by a stretching or shrinking of the dimensional elements by a factor S.sup.1/2. Representations of Pseudo-Objects The previous results show how it is possible to compute comparisons between the various objects associated with the rows or columns of Y. It is very important in information retrieval applications to computer similar comparison quantities for objects such as queries that do not appear explicitly in Y. For example, it is necessary to be able to take a completely novel query, find a location in the k-dimensional latent semantic space for it, and then evaluate its cosine or inner product with respect to terms or objects in the space. Another example would be trying, after-the-fact, to find representations for documents that did not appear in the original space. The new objects for both these examples are equivalent to objects in the matrix Y in that they may be represented as vectors of terms. For this reason they are called pseudo-documents specifically or pseudo-objects generically. In order to compare pseudo-documents to other documents, the starting point is defining a pseudo-document vector, designated Y.sub.q. Then a representation D.sub.q is derived such that D.sub.q can be used just like a row of D in the comparison relationships described in the foregoing sections. One criterion for such a derivation is that the insertion of a real document Y.sub.i should give D.sub.i when the model is ideal (i.e., Y=Y.sub.R). With this constraint, Y.sub.q =TSD.sub.q.sup.T or, since T.sup.T T equals the identity matrix, D.sub.q.sup.T =S.sup.-1 T.sup.T Y.sub.q or, finally, D.sub.q =Y.sup.T.sub.q TS.sup.-1. (5) Thus, with appropriate rescaling of the axes, this amounts to placing the pseudo-object at the vector sum of its corresponding term points. Then D.sub.q may be used like any row of D and, appropriately scaled by S or S.sup.1/2, can be used like a usual document vector for making "within" and "between" comparisons. It is to be noted that if the measure of similarity to be used in comparing the query against all the documents is one in which only the angle between the vectors is important (such as the cosine), there is no difference for comparison purposes between placing the query at the vector average or the vector sum of its terms. Illustrative Embodiment The foundation principles presented in the foregoing sections are now applied to a practical example of way of teaching an illustrative embodiment in accordance with the present invention. The system under consideration is one that receives a request for technical information from a user and returns as a response display the most appropriate groups in a large, technically diverse company dealing with that technical information. The size of each group is from five to ten people. There is no expert who understands in detail what every group is accomplishing. Each person's understanding or knowledge of the company's technical work tends to be myopic, that is, each one knows their particular group's work, less about neighboring groups and their knowledge becomes less precise or even nonexistent as one moves further away from the core group. If each group can be described by a set of terms, then the latent semantic indexing procedure can be applied. For instance, one set of textural descriptions might include annual write-ups each group member must prepare in describing the planned activity for the coming year. Another input could be the abstracts of technical memoranda written by members of each group. The technique for processing the documents gathered together to represent the company technical information is shown in block diagram form in FIG. 2. The first processing activity, as illustrated by processing block 100, is that of text processing. All the combined text is preprocessed to identify terms and possible compound noun phrases. First, phrases are found by identifying all words between (1) a precompiled list of stop words; or (2) punctuation marks; or (3) parenthetical remarks. To obtain more stable estimates of word frequencies, all inflectional suffixes (past tense, plurals, adverbials, progressive tense, and so forth) are removed from the words. Inflectional suffixes, in contrast to derivational suffixes, are those that do not usually change the meaning of the base word. (For example, removing the "s" from "boys" does not change the meaning of the base word whereas stripping "ation" from "information" does change the meaning). Since no single set of pattern-action rules can correctly describe English language, the suffix stripper sub-program may contain an exception list. The next step to the processing is represented by block 110 in FIG. 2. Based upon the earlier text preprocessing, a system lexicon is created. The lexicon includes both single word and noun phases. The noun phrases provide for a richer semantic space. For example, the "information" in "information retrieval" and "information theory" have different meanings. Treating these as separate terms places each of the compounds at different places in the k-dimensional space. (for a word in radically different semantic environments, treating it as a single word tends to place the word in a meaningless place in k-dimensional space, whereas treating each of its different semantic environments separately using separate compounds yields spatial differentiation). Compound noun phrases may be extracted using a simplified, automatic procedure. First, phrases are found using the "pseudo" parsing technique described with respect to step 100. Then all left and right branching subphrases are found. Any phrase or subphrase that occurs in more than one document is a potential compound phrase. Compound phrases may range from two to many words (e.g., "semi-insulating Fe-doped InP current blocking layer"). From these potential compound phrases, all longest-matching phrases as well as single words making up the compounds are entered into the lexicon base to obtain spatial separation. In the illustrative embodiment, all inflectionally stripped single words occurring in more than one document and that are not on the list of most frequently used words in English (such as "the", "and") are also included in the system lexicon. Typically, the exclusion list comprises about 150 common words. From the list of lexicon terms, the Term-by-Document matrix is created, as depicted by processing block 120 in FIG. 2. In one exemplary situation, the matrix contained 7100 terms and 728 documents representing 480 groups. The next step is to perform the singular value decomposition on the Term-by-Document matrix, as depicted by processing block 130. This analysis is only effected once (or each time there is a significant update in the storage files). The last step in processing the documents prior to a user query is depicted by block 140. In order to relate a selected document to the group responsible for that document, an organizational database is constructed. This latter database may contain, for instance, the group manager's name and the manager's mail address. The user query processing activity is depicted on the right-hand side of FIG. 2. The first step, as represented by processing block 200, is to preprocess the query in the same way as the original documents. As then depicted by block 210 the longest matching compound phrases as well as single words not part of compound phrases are extracted from the query. For each query term also contained in the system lexicon, the k-dimensional vector is located. The query vector is the weighted vector average of the k-dimensional vectors. Processing block 220 depicts the generation step for the query vector. The next step in the query processing is depicted by processing block 230. In order that the best matching document is located, the query vector is compared to all documents in the space. The similarity metric used is the cosine between the query vector and the document vectors. A cosine of 1.0 would indicate that the query vector and the document vector were on top of one another in the space. The cosine metric is similar to a dot product measure except that it ignores the magnitude of the vectors and simply uses the angle between the vectors being compared. The cosines are sorted, as depicted by processing block 240, and for each of the best N matching documents (typically N=8), the value of the cosine along with organizational information corresponding to the document's group are displayed to the user, as depicted by processing block 250. Table 6 shows a typical input and output for N=5.
TABLE 6
__________________________________________________________________________
INPUT QUERY:
An Expert/Expert-Locating System Based on
Automatic Representation of Semantic Structure
OUTPUT RESULTS:
1. Group:B
Group Title:
Artificial Intelligence and
Information Science Research
Group Manager:
D. E. Walker, Address B, Phone B
Fit (Cosine):
0.67
2. Group: A
Group Title:
Artificial Intelligence and
Communications Research
Group Manager:
L. A. Streeter, Address A, Phone A
Fit (Cosine):
0.64
3. Group: E
Group Title:
Cognitive Science Research
Group Manager:
T. K. Laudauer, Address E, Phone E
Fit (Cosine):
0.63
4. Group:C
Group Title:
Experimental Systems
Group Manager:
C. A. Riley, Address C, Phone C
Fit (Cosine):
0.62
5. Group: D
Group Title:
Software Technology
Group Manager:
C. P. Lewis, Address D, Phone D
Fit (Cosine):
0.55
__________________________________________________________________________
It is to be further understood that the methodology described herein is not limited to the specific forms disclosed by way of illustration, but may assume other embodiments limited only by the scope of the appended claims.
|
Same subclass Same class Consider this |
||||||||||