Context vector generation and retrieval

• US 7,251,637 B1
• Filed: 09/27/2000
• Issued: 07/31/2007
• Est. Priority Date: 09/20/1993
• Status: Expired due to Fees

• Current Assignee: Fair Isaac Corporation
• Original Assignee: Fair Isaac Corporation
• Inventors: Carleton, Joel Lawrence, Caid, William Robert, Sudbeck, David John, Oing, Pu
• Primary Examiner(s): Hirl; Joseph P
• Application Number:
  US09/672,237
• Time in Patent Office: 2,498 Days
• Field of Search: 706/15, 706/20, 706/26, 707/100
• US Class Current: 706/15
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 16/58 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06V 10/451 with interaction between the filter responses, e.g. cortical complex cells

Abstract

A system and method for generating context vectors for use in storage and retrieval of documents and other information items. Context vectors represent conceptual relationships among information items by quantitative means. A neural network operates on a training corpus of records to develop relationship-based context vectors based on word proximity and co-importance using a technique of “windowed co-occurrence”. Relationships among context vectors are deterministic, so that a context vector set has one logical solution, although it may have a plurality of physical solutions. No human knowledge, thesaurus, synonym list, knowledge base, or conceptual hierarchy, is required. Summary vectors of records may be clustered to reduce searching time, by forming a tree of clustered nodes. Once the context vectors are determined, records may be retrieved using a query interface that allows a user to specify content terms, Boolean terms, and/or document feedback. The present invention further facilitates visualization of textual information by translating context vectors into visual and graphical representations. Thus, a user can explore visual representations of meaning, and can apply human visual pattern recognition skills to document searches.

Claims

1. In a computer having a processor, a storage, and a display unit, a computer implemented method of generating context vectors representing information items for retrieval of the information items or records containing the information items, the method comprising:

initializing the context vectors such that the context vectors are substantially orthogonal to each other in a vector space;

assigning a context vector to each of a plurality of information items;

determining proximal co-occurrences of the information items;

adjusting the context vectors based on the proximal co-occurrences of the information items, such that the information items that frequently proximally co-occur have context vectors with similar orientations in the vector space; and

using said adjusted context vectors for retrieving said information items or records containing said information items; and

displaying on said display unit said retrieved information items or records containing the information items.

2. The method of claim 1, wherein initializating the context vectors further comprises:

assigning vector components to the vectors using zero-mean, unit-variance Gaussian random number generation.

3. The method of claim 1, wherein a target context vector is a context vector assigned to a target information item, and a neighbor context vector is a context vector assigned to an information item that proximally co-occurs with the target context vector, and wherein adjusting the context vectors comprises:

for each target context vector to be adjusted;

determining an error vector between a target context vector and each neighbor context vector;

updating the target context vector as a function of the error vectors.

4. The method of claim 3, wherein updating the target context vector as a function of the error vectors comprises:

determining a correction vector from the error vectors, where the correction vector is;

$C_j=\underset{i}{\overset{\mathrm{WS}}{\sum <br><br>}}<br><br><br><br>\left(<br><br>E_{\mathrm{ij}}<br><br>-{\mathrm{\alpha <br><br>}}_{\mathrm{ij}}\right)<br><br>{\hat{E}}_{\mathrm{ij}}$

where;

E_ij is the error vector E_ij=N_ij−

T_j between the neighbor context vector N_ij and a target context vector T_j;

WS is a window size containing the target context vector and the neighbor context vectors; and

α

is a proximity constraint; and

updating the target context vector as.

$T_j^{\mathrm{NEW}}=T_j^{\mathrm{OLD}}+\frac{\mathrm{\gamma <br><br>}}{F_j}<br><br>\underset{i=1}{\overset{F_j}{\sum <br><br>}}<br><br><br><br>C_j-M$

where;

γ

is a step size;

F_j is the total number of occurrences of information item j; and

M is a mean context vector for all unique context vectors.

5. The method of claim 1 wherein a target context vector is a context vector assigned to a target information item, and a neighbor context vector is a context vector assigned to an information item that proximally co-occurs with the target context vector, and wherein adjusting the context vectors comprises:

determining a weighted sum vector of neighbor context vectors of a target context vector;

applying the weight sum vector to the target context vector.

6. The method of claim 5, further comprising:

determining the weighted sum vector according to the equation;

$W_j=\underset{i}{\overset{\mathrm{WS}}{\sum <br><br>}}<br><br><br><br>\frac{G<br><br>\left(i\right)}{D_j}<br><br>N_{\mathrm{ij}}$

where;

W is the weighted sum vector;

N_ij is the neighbor context vector to target context vector T_j;

G(i) is a Gaussian weight for the neighbor context vector i; and

D_j is the number of documents that contain target information item j; and

applying the weighted sum vector to the target context vector according to the equation;

$T_j^{\mathrm{NEW}}=T_j^{\mathrm{OLD}}+W_j$

where;

T_j^NEW is the updated target context vector; and

T_j^OLD is the un-updated target context vector.

7. The method of claim 1 wherein a target context vector is a context vector assigned to a target information item, and a neighbor context vector is a context vector assigned to an information item that proximally co-occurs with the target context vector, and wherein adjusting the context vectors comprises:

determining a weighted sum vector of neighbor context vectors of a target context vector according to the equation

$W_j=\underset{i}{\overset{\mathrm{WS}}{\sum <br><br>}}<br><br><br><br>\frac{G<br><br>\left(i\right)}{D_j}<br><br>N_{\mathrm{ij}}$

where;

W is the weighted sum vector;

G(i) is a Gaussian weight for the neighbor context vector i; and

D_j is the number of documents that contain target information item j;

determining an error vector from the weighted sum vector and the target context vector;

E_j=W_j−

T_j

where

E is the error vector;

T is target context vector;

determining a correction vector C from the error vectors of the neighbor context vectors;

$C_j=\underset{i=1}{\overset{F_j}{\sum <br><br>}}<br><br><br><br>E_j$

applying the correct vector to the target vector;

$T_j^{\mathrm{NEW}}=T_j^{\mathrm{OLD}}+\mathrm{\gamma <br><br>}<br><br><br><br>C_j-M$

where;

T_j^NEW is the updated target context vector; and

T_j^OLD is the un-updated target context vector;

γ

is a step size; and

M is a mean context vector for all unique context vectors.

8. The method of claim 1, wherein the vector space is defined by a plurality of axes, and the context vector include vector components corresponding to the respective axes, and wherein the axes individually do not have specific semantic associations.

9. The method of claim 1, wherein a target context vector is a context vector assigned to a target information-item, and a neighbor context vector is a context vector assigned to an information item that proximally co-occurs with the target context vector, and wherein adjusting the context vectors comprises:

adjusting the target context vector as a function of the relative importance of at least one of either the target information element or the neighbor context vector with respect to the plurality of information item.

10. The method of claim 1, wherein a target context vector is a context vector assigned to a target information item, and a neighbor context vector is a context vector assigned to an information item that proximally co-occurs with the target context vector, and wherein adjusting the context vectors comprises:

adjusting the target context vector as a function of the frequency of occurrence of the target information item;

the frequency of occurrence of the neighbor information item;

a total number of records containing the target information item, and a total number of record containing the neighbor information item.

11. The method of claim 1, wherein a target context vector is a context vector assigned to a target information item, and a neighbor context vector is a context vector assigned to an information item that proximally co-occurs with the target context vector, and wherein adjusting the context vectors further comprises:

adjusting the target context vector as a function of;

a distance of the neighbor information item from the target information item, so that neighbor information items that are closer to the target information item cause the target context vector to be adjusted to be closer to the neighbor context vector; and

a frequency of occurrence of the neighbor information item in records containing the information items, such that a neighbor information item that is less frequently occurring more strongly causes the target context vector to be adjusted to be closer to that neighbor context vector than a neighbor information item that is more frequently occurring.

12. The method of claim 1, further comprising:

for at least one record comprising a plurality of information items, determining a summary context vector for the record from the normalized sum of the context vectors of the information items that comprise the record.

13. The method of claim 12, further comprising:

receiving a query comprising at least one information item;

generating a query context vector from the information item that comprise the query;

retrieving at least one record having a summary context vector with a orientation in the vector space similar to the orientation of the query context vector.

14. The method of claim 13, wherein retrieving at least one record having a summary context vector with a orientation in the vector space similar to the orientation of the query context vector further comprising:

a tree walk of a cluster tree, the cluster tree comprising a hierarchical plurality of nodes, each node having a cluster centroid vector, each cluster centroid vector associated with a cluster of one or more records, and derived from the one or more records contained in the cluster, the tree walk performed by iteratively selecting a node of the cluster tree that has a centroid cluster vector with a closest orientation in the vector space to the query context vector.

15. The method of claim 1, further comprising:

clustering the context vectors into a plurality of clusters, each cluster having a centroid vector derived from the plurality of context vector contained in the cluster.

16. The method of claim 1, wherein:

information items having similar meaning have context vectors with similar orientations in the vector space.

17. The method of claim 1, further comprising:

determining a similarity of meaning between a first information item and a second information item by performing a vector operation on the context vectors of the first and second information items.

19. The method of claim 13, wherein the mutual co-occurrence matrix comprises for each pair of selected information items, a normalized measure of the frequency of proximal co-occurrence of the pair of selected information items.

20. The method of claim 13, wherein the selected set of information items comprises a first selected set, the method further comprising:

selecting a second set of information items different from the first selected set of information items;

associating each of the second set of information items with a second context vector; and

updating the second context vectors at least once using the first context vectors, wherein the first context vectors are fixed during at least one update of the second context vectors.

18. In a computer having a processor, a database, and a display unit, a computer implemented method of generating vectors representing information items for retrieval of the information items, the method comprising:

selecting a set of R information items in the database;

determining for the selected set of information elements an R×

R mutual co-occurrence matrix based on proximal co-occurences of the information items in a plurality of documents;

applying Singular Value Decomposition to the mutual co-occurrence matrix to produce a set of first context vectors; and

wherein each first context vector is uniquely associated with one of the selected information items, and wherein information items having similar meaning have respective first context vectors with similar orientations in the vector space; and

using said context vectors for retrieval of information items from said database; and

displaying said retrieved information items on said display unit.

21. In a computer having a processor, a database, and a display unit, a computer implemented method of retrieving a record from the database containing a plurality of records, each record containing at least one information item having an associated context vector, the method comprising:

for each of a plurality of information items, storing context vectors associated with the information item the context vectors having the properties that information items having similar meaning have context vectors with similar orientations in a vector space, and information items having dissimilar meanings have context vectors with dissimilar orientations in the vector space;

for each of the plurality of records from said database containing said plurality of records, storing a summary context vector derived from context vectors respectively associated with information items that comprise the record;

receiving a query;

deriving at least one query information item from the query;

generating a query context vector from the query information item; and

selecting at least one record from said database having a summary context vector with orientation in the vector space that is similar to the orientation of the query context vector; and

displaying said selected at least one record on said display unit.

22. The method of claim 21, wherein selecting at least one record further comprises:

for each of a plurality of records, determining a distance in the vector space between the query context vector and a summary context vector of a record; and

selecting the record having a least distance between its summary context vector and the query context vector.

23. In a computer having a processor, a data storage, and a display unit, a computer implemented method of providing a space for information items, said information items encoding and representing predetermined meanings, the method comprising:

selecting a set of first information items in a corpus of records in said data storage;

creating a first set of context vectors based on proximal co-occurrences of the first information items, each first context vector uniquely associated with one of the first information items, the context vectors having an orientation in a vector space, such that first information items having similar predetermined encoded meaning have context vectors with similar orientations in the vector space;

selecting a set of second information items in said data storage, the second information items being different from the first information items;

selecting a subset of the first information items;

for each first information item in the subset, selecting a corresponding second information item representing a predetermined encoded meaning substantially identical to the predetermined encoded meaning of the first information item;

for each of the selected second information items, associating the second information item with the context vector of the corresponding first information item;

assigning a context vector to each non-selected second information item;

adjusting the context vectors of the non-selected second information items using the context vectors of the selected second information items; and

using any of said context vectors for later retrieval of said first information items; and

displaying said retrieved first information items on said display unit.

24. The method of claim 23, wherein:

the first information items are words of a first language, and the second information items are words of a second, different language; and

the subset of first information items and the corresponding second information items have substantially identical encoded meaning.

25. The method of claim 23, wherein:

the first information items are symbolic representations of words of a language encoded in a first data format, and the second information items are symbolic representations of non-text data encoded in a second data format different from the first format; and

the subset of first information items and the corresponding second information items have substantially related predetermined encoded meaning even though they have different data formats and different symbolic representations.

26. The method of claim 23, wherein adjusting the context vectors of the non-selected second information items further comprises:

adjusting the context vectors of the non-selected second information items, such that non-selected second information items and selected second information items having similar predetermined encoded meaning have context vectors with similar orientations in the vector space.

27. In a computer having a processor, a database of records, and a display unit, a computer implemented method of generating a dictionary of information items for said database of records, each record including at least one information item, each information item associated with a context vector, each information item having a determinate proximity to other information items in a record, wherein a neighbor information item is an information item that occurs proximate a target information item in at least one record in the database, the method comprising:

initializing the context vectors such that initial context vectors are substantially orthogonal to each other in a vector space;

associating the context vectors with information items in the dictionary of information items for said database of records; and

for each information item being a target information item;

selecting neighbor information items of the target information item in at least one record; and

modifying the context vector of the target information item using the context vectors of each selected neighbor information items as a function of the proximity of each neighbor information item to the target information item, and a co-importance of the target information item and the neighbor information item;

using said dictionary for retrieving information items representing media during a search; and

displaying said retrieved information items on said display unit.

28. The method of claim 27, further comprising:

determining the co-importance according to the relative importance of the target information item and the relative importance of the neighbor information item.

29. The method of claim 28, wherein determining the co-importance comprises:

determining a first relative importance of the target information item, inversely according to the frequency of occurrence of the target information item in the records;

determining a second relative importance of the neighbor information item inversely according to the frequency of occurrence of the neighbor information item in records; and

determining the co-importance as a function of the first relative importance and the second relative importance.

30. The method of claim 29, further comprising:

determining the relative importance of an information item by the equation;

$I_j=B+\left(1-B\right)<br><br>\left(1-\frac{\log <br><br>\left(\frac{1}{{\mathrm{ND}}_j}\right)}{\log <br><br>\left(\frac{1}{\mathrm{TND}}\right)}\right),$

wherein;

I_j is the relative importance of information item J;

B represents a predefined lower bound;

ND_j represents the number of records containing information item J; and

TND represents the total number of records.

31. The method of claim 27, wherein the co-importance of the target information item and the neighbor information item is determined using the equations:

^C_TN=I_TI_N 

 

1)

wherein;

C_TN is the co-importance of the target information item and the neighbor information item;

I_T is the relative importance of the target information item; and

I_N is the relative importance of the neighbor information item; and

$2)<br><br><br><br>I_j=B+\left(1-B\right)<br><br>\left(1-\frac{\log <br><br>\left(\frac{1}{{\mathrm{ND}}_j}\right)}{\log <br><br>\left(\frac{1}{\mathrm{TND}}\right)}\right),$

wherein;

I_j is the relative importance of an information item J;

B represents a predefined lower bound;

ND_j represents the number of records containing information item J; and

TND represents the total number of records.

32. The method of claim 27, wherein a proximity constraint varies a magnitude of the modification to the context vector of the target information item as a function of both the frequency of occurrence of the target information item and the frequency of the occurrence of each neighbor information item in the records, so that the context vectors of information items that frequently proximally co-occur do not converge.

33. In a computer system including a storage device containing a plurality of records, each record containing a plurality of information items, a computer readable medium for configuring and controlling the computer system to generate a plurality of context vectors, the computer readable medium comprising:

an initial context vector generation module, adapted to read and write to the storage device, which initializes to each of a plurality of selected information items an initial context vector, such that the initial context vectors are substantially orthogonal to each other in a vector space, and which writes the initial context vectors to the storage device in association with respective information items;

a vector training module, adapted to read and write to the storage device, for modifying the context vector of a selected information item, being a target information item, using the context vectors of neighbor information items that proximally co-occur with the target information item, as a function of the proximity of each neighbor information item to the target information item, and a co-importance of the target information item and the neighbor information item;

a retrieval module configured to use said initial context vector generation module and said vector training module in retrieving information items or records containing said information items, said information items representing media; and

a display module for displaying said retrieved information items or records.

34. In a computer having a processor, a database, and a display unit, a computer implemented method of automatically indexing documents using a defined index of terms, the method comprising:

providing an indexed collection of documents in said database, each document having at least one index term assigned to the document;

providing a plurality terms, including the index terms, each term associated with a context vector, the context vector having the properties that that terms having similar meaning have context vectors with similar orientations in a vector space, terms having dissimilar meanings have context vectors with dissimilar orientations in the vector space, and terms which frequently proximally co-occur have context vectors with similar orientations in the vector space; and

generating for each indexed document a context vector from the context vectors of selected terms that comprise the document;

receiving a new document in said database to be indexed;

generating a new context vector of the new document, the new context vector generated from the context vectors of selected terms that comprise the new document;

selecting at least one indexed document having a context vector similar to the new context vector;

assigning to the new document at least one index term assigned to a selected indexed document;

such that said new document can later be retrieved from said database; and

displaying said retrieved document on said display unit.

35. The method of claim 34, wherein assigning to the new document at least one index term further comprises:

for each selected indexed document, assigning a weight to each index term assigned to the indexed document, the weight proportional to the similarity between the new context vector and the context vector of the indexed document, such that the weight is higher where the context vectors are more similar;

for each index term, generating an index term score as a function of a number of occurrences of the index term in each selected indexed document, and the weight of the index term with respect to each selected indexed document, such that the index term score is higher as the number of occurrences of an index term increases; and

assigning to the new document at least one of the index terms with a high index term score.