Method and device for measuring relevancy of a document to a keyword(s)

A method is presented for ranking documents identified in a search relative to a keyword. The method utilizes a set of training documents to provide a co-occurrence matrix and a transition matrix. A word pair relevancy measure is calculated for each word of the document to be ranked. These word pair relevancy measures are based upon the co-occurrence and transition matrices obtained from the training set and are utilized to calculate a document relevance measure. Documents identified in a search are ranked utilizing the document relevance measure.

FIELD OF THE INVENTION

This invention is generally directed to a method and device for determining the relevancy of pairs of words and to a method and device for ranking the relevancy of documents to a keyword based upon the relevancy of the pairs of words.

BACKGROUND OF THE INVENTION

Identifying information related to a given topic within large collections of documents is an ongoing challenge. The most common method is to use Boolean keyword searches to find documents that mention particular terms, but there are inherent limitations to using Boolean keyword searches to identify documents of potential interest. One limitation is that when a specific keyword is used in the Boolean search, there is a risk that the Boolean search will not return a relevant document because the document does not use the same phrasing or nomenclature of that specific keyword. On the other hand if a more general keyword is used in the Boolean search, there is a risk that the Boolean search will return a set of documents too large for a searcher to analyze all of the documents within a reasonable time. Thus, the limitations provided by using Boolean searches to gauge the relevancy of a document to a keyword reduces the efficiency with which information can be gleaned from large sets of documents. Although a human who manually searches documents for text relevant to a keyword often easily addresses the shortcomings of a Boolean search by employing intuition developed through years of familiarity with language as well as familiarity with a breadth of topics, when large document sets are to be reviewed, manual review is not practical.

In an effort to increase the efficiency with which sets of documents can be reviewed, other methods are used to assess the relevancy of documents identified by a search. Some internet search engines, for example, assess relevancy by prioritizing the documents (for example, web pages) that are returned to the user. More specifically, for example, some search engines use crowd sourcing which ranks the relevancy of documents returned from a Boolean search based upon the popularity or page-rank of those documents. Although priority or relevancy rankings based upon crowd sourcing works very well in instances where the search engine has sufficient users to generate the necessary statistics, it is poorly suited to more niche applications. For example, crowd sourcing is ill suited to small intranets, or within a single internet domain, because the volume of users may not be large enough to generate accurate relevancy rankings. Additionally, crowd sourcing may not generate accurate relevancy rankings when obscure search terms are used because the yielded results have not been viewed a sufficient number of times to be prioritized by popularity.

Because, many documents include common words (e.g. “the”, “a”, “that”, . . . ) which have no particular relevancy to the document or the keyword, some prior art methods for determining the relevancy of documents involve the elimination of the effect of these common words on the results. Such methods require, however, the identification of the common words and therefore knowledge of the language utilized in the documents containing these words is required.

SUMMARY OF THE INVENTION

Briefly, the present invention discloses a method and device for determining the relevancy of a pair of words (i.e. the relevancy of a first word in the pair to the second word in the pair) and for ranking relevancy of documents to a keyword(s) based upon the word pair relevancy measures. A first set (training set) of documents is used to determine word pair relevancy measures. The word pair relevancy measures are determined based upon a co-occurrence matrix, a probability matrix, a transition matrix and an expected search distance measure. These word pair relevancy measures are then utilized to determine document relevancy measures for documents in a second set (live set). Once document relevancy measures are determined, the documents of the second set are ranked in accordance with the relevancy measures.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

The present invention provides a device and method for determining the relevancy of pairs of words and for determining the relevancy of a keyword(s) to a document. The invention utilizes the following assumptions. The first assumption is that the occurrence of words together in a unit of text implies a relevancy between those words, i.e. the occurrence of a first word and a second word in the same unit of text implies a relevancy between the first word and the second word. A second, further assumption is that the relevancy between the first word and the second wind is weakly transitive, i.e. the occurrence of the second word in the same unit of text as a third word, but different from the unit of text that contained both the first and second word, implies a relevancy between the first word and the third word. The relevancy between the first word and the third word is not as strong, however, as the relevancy between the first word and the second word (or the relevancy between the second word and the third word). Utilizing these assumptions, the present invention provides an approximation of the intuition provided by a human reviewer and allows large data sets to be handled efficiently.

The assumption that the occurrence of a pair of words in a unit of text implies relevancy provides a basis for the relevancy model utilized by the present invention. This relevancy model is illustrated inFIG. 1.

The relevancy model illustrated inFIG. 1illustrates how the above assumptions are utilized to measure the relevancy of a pair of words, e.g. a first word and a second word.FIG. 1includes a plurality of blocks12. Each block (12a,12b,12c, . . .12x) ofFIG. 1includes a word node column14and a unit node column16. The word node column14represents each of the words (d) which occur in a body of documents and the unit node column16represents units of text (p) within the body of documents. At block12athe search word dsis identified in word node column14aand is used as the first word of the pair. A search then proceeds to locate the second word or keyword dk. At block12b, each of the units p including the search word dsare identified. The arrows18leading from dsof the word node column14bto the unit node of column16billustrate the possible transitions from the node dsof the word node column14bto a node in the unit node column16b. A unit pkis randomly selected from these identified units in the unit node column16b. Next, at block12c, the words included in the unit pkare identified by the arrows20leading from pkto the word node column14c. All arrows that originate at a particular node will connect with nodes in the opposite column. The arrows (which are not all shown) represent the presence of a particular word in a particular unit (represented by arrows directed from the word node column14to the unit node column16) or represent the presence of the words provided in a particular unit (represented by arrows directed from the unit node column16to the word node column14). All of the arrows originating at a particular node have equal transition probabilities.

After the identification of the words in the selected unit, a new search word djis randomly selected from the identified words. At block12d, the units of column16dincluding the new search word djare identified. The arrows22leading from word node djto the second column16dillustrate the possible transitions from the node djof the word node column14dto a node in the unit node columnvc16d. One of the identified units, p4, is randomly selected from the unit node column16dof block12d. This process continues until at block12xa unit p3is selected which includes the keyword dk. As additional units are examined to determine the presence of the keyword dk, the search distance increases. A “search distance” is defined therefore as the number of word nodes traversed in the search while transitioning from the node representing the first word dior search word dsto the node representing the second word djor key word dk.

Because the model provides that the units and search words are selected randomly, a different chain of words and units will result each time the model is applied thereby resulting in the possibility that a different search distance will be determined when the search is repeated for the same pair of words. It is therefore useful to determine the mean search distance of a pair of words. This mean is identified as the “expected search distance.”

The search model described above provides a basis for determining the expected search distance from which a word pair relevancy can be determined for a pair of words. These determinations are made based upon a first set of documents, sometimes referred to herein as “training documents” or collectively referred to as a “training set” X.

The method100of calculating a word pair relevancy is illustrated inFIG. 2. As illustrated inFIG. 2, the process100begins at step102by identifying a training set of documents. In addition to other types of documents, this training set, X, preferably includes literature from the same general field as the documents to be ranked (i.e., the “live documents”). The training set can, for example, be created from open sources such as Wikipedia, free e-books, openly available scientific papers, articles, or Tweets. Alternatively, for example, the training set, X, could be created from a specialized private collection of documents. A simplified example of a training set X, is illustrated inFIG. 3. As illustrated the training set includes three documents126a,126b, and126c.

As illustrated inFIG. 2, once the training set, X, has been identified at step102, at step104each word of each training document within the training set is identified, and a search word list, Ω, is created. Each of the words on this list will be referred to as a search word. Search words can be identified, for example, utilizing a computer program such as Python's Natural Language Tool Kit, to remove all punctuation from the documents and then identify all strings of characters separated by spaces. These strings of characters are identified as search words and are utilized to create the search word list, Ω. Duplicates are not included in the search word list, Ω. Therefore, the search word list, Ω, provides a set of unique words found in the training set. It is to be understood that the search word list, Ω, may include, for example, words from multiple languages, series of numbers or mathematical symbols. A search word list, Ω, derived from the training set X ofFIG. 3is illustrated inFIG. 4. The search word list includes a plurality of search words128.

As illustrated inFIG. 2, at step106, the training documents are portioned into units of text, i.e. “units”. It should be noted that the definition of a unit may vary for different applications. A unit can be, for example, a paragraph. Alternatively, a unit can be defined as a sentence, or a chapter, for example. It has been found that, for western languages, defining the unit as a paragraph has been beneficial. If for example the unit is defined as a paragraph, break lines between paragraphs can be used to identify the units. If the unit is defined as a sentence, ending punctuation (i.e. period, question mark, exclamation mark . . . ) may be used to identify the units. If the unit is to be defined as a page, a page break can be used to define the units. Thus, a variety of methods may be used to portion the training documents into units. As illustrated inFIG. 5, units130were derived from the set, X, ofFIG. 3. As illustrated, sentences were selected as the units and five units of text130are provided.

Referring back toFIG. 2, at step108unit word sets are created. Once the units have been identified, a unit word set is created for each unit of text. The unit word set consists of each word identified in the unit. If a word is repeated within the unit, the unit word set contains only one instance of the word, thereby removing any redundancy within the unit word set.

As noted above, the intuition provided by human searching can, in part, be approximated by utilizing the assumption that the occurrence of words together in a unit of text implies a relevancy between those words. Thus, determining the likelihood that two words will appear together in a unit will assist in determining the relevancy of the words. At step110, therefore, word pairs are identified. More specifically, each word from the search word list, Ω, is paired with another word from the search word list, Ω, to define search word pairs (di, dj).

At step111the co-occurrence matrix, C (X), is created. The co-occurrence matrix provides a column associated with each word from the search word list, Ω, and a row associated with each word from the search word list, Q. The size of the co-occurrence matrix is, therefore, |Ω| by |Ω|. Each matrix entry associated with a particular column and row identifies a training pair count Ci,j(X). The training pair count, Ci,j(X), represents the number of units where the words diand djoccur together in a unit and the words are in the search word list Q. It is understood that many of the entries, Ci,j(X), of the co-occurrence matrix, may be zero. Therefore, when storing the co-occurrence matrix on a computer, the size of the co-occurrence matrix may be greatly reduced by eliminating the zero entries from the co-occurrence matrix. A co-occurrence matrix140is illustrated inFIG. 6and represents the co-occurrence matrix relating to the simplified training set, X, ofFIG. 3. Each search word128of the search word list, Ω, is provided in a column to provide a plurality of first words, di, and each search word128of the search word list, Ω, is provided in row to provide a plurality of second words, dj. The search pair count Ci,j(X) is provided for each entry of the co-occurrence matrix. As shown inFIG. 6, the search pair (the, man) was found in two unit word sets (i.e. Unit 1 and Unit 2) and the search pair (dog, chased) was found in one unit word set (Unit 3). It should be noted that the entry for any instance wherein the column and the row identify the same search word (i.e. where diand djare the same word) will be one or greater if the word occurred in the set, as it is a count of the number of units that contained that search word.

As noted above, the intuition provided by human searching can, in part, be approximated by utilizing the assumption that the relevancy of words occurring together is weakly transitive. It is therefore useful to quantify the transitive relationship of words in the training set. At step112ofFIG. 2therefore, the probability of observing djin a unit given that diis in the unit is calculated. χ represents the total number of units provided in the training set X, and Ci,irepresents the total number of units provided in the training set X that contain di. The co-occurrence matrix C(X) is divided by the total number of units in the training set, χ, to give the probability P(di, dj) of observing words diand djtogether in a unit. The elements Ci,iare divided by χ to give the probability P(di) of observing the word diin a unit. A probability matrix M, can therefore be created from the co-occurrence matrix as follows:

The probability matrix, Mi,jtherefore represents the probability of observing word djin a unit given that diis in the unit; i.e. a conditional co-occurrence probability. A probability matrix,142derived from the co-occurrence matrix140is illustrated inFIG. 7.

Referring back toFIG. 2, at step114the probability matrix, M, is then row-normalized to provide the transition matrix, R, as follows:

Ri,j=Ci,j∑s⁢Ci,s
The transition matrix element Ri,jrepresents the probability of transitioning from a first search word, di, to a second search word, djin a single step; i.e. the transition probability reflects the probability, when randomly choosing from the units containing the word, di, that a unit having the word, dj, will be chosen. The closer the relationship between the words diand dj, the greater the transition probability. A transition matrix,144derived from the probability matrix142of FIG. co-occurrence matrix140is illustrated inFIG. 8.

A search distance can be utilized to quantify the relationship of a pair of words (di, dj) provided by the training set. (i.e., a search word pair). As discussed above, the search model provides a search distance which is defined as the number of searches needed (or word nodes traversed) to transition from a first word to second word. At step116, the seed word-keyword pair (ds, dk) for which relevancy is to be determined is identified.

At step118, an expected search distance is calculated for the identified seed word-keyword pair. The expected search distance of the seed word-keyword pair is determined based upon the co-occurrence information provided by the training set, the probability matrix and transition matrix. The expected search distance for each identified seed word-keyword pair thereby quantifies the transitive relationship of the seed word-key word pairs. More specifically, the expected search distance is expressed as:

c_d,k=∑n=1∞⁢n⁡[Γ→⁡(d)]T·[(I-Γ→⁡(k)⊗Γ→⁡(k))·R·(I-Γ→⁡(k)⊗Γ→⁡(k))]n-1·M·Γ→⁡(k)⁢c_d,k=∑n=1∞⁢n⁡[Γ→⁡(d)]T·α→n⁡(k)
where
{right arrow over (α)}1(k)=M·{right arrow over (Γ)}(k), forn=1;
and
{right arrow over (α)}n(k)=[(1−{right arrow over (Γ)}(k)⊗{right arrow over (Γ)}(k))·R·(I−{right arrow over (Γ)}(k)⊗{right arrow over (Γ)}(k))]·{right arrow over (α)}n-1(k), forn≥2

T indicates the transpose of the vector, while the superscript “n−1” indicates exponentiation of the square matrix.

Γ(j) is a vector that identifies the entries in the transition matrix R and the probability matrix M which relate to the particular seed word or keyword such that
Γi=δi,j∀di,dj∈Ω,
where δi,jis the Kronecker delta. I is a |Ω| by |Ω| identity matrix, and ⊗ is the outer product.

The expected search distance,cd,k, for disjointed words will have a measure of infinity. The expected search distance,cd,k, for highly related words will have a very low measure. Although the equation provided above indicates the expected search distance requires an infinite summation, in practice a few hundred transitions are sufficient before a useful precision of several decimal points is reached.cd,kis therefore represented by:

c_d,k=∑n=1g⁢n⁡[Γ→⁡(d)]T·[(I-Γ→⁡(k)⊗Γ→⁡(k))·R·(I-Γ→⁡(k)⊗Γ→⁡(k))]n-1·M·Γ→⁡(k)
where g is the upper limit of the summation.

Because the expected search distance will be affected by the frequency with which a word occurs, a weighted average expected search distance is calculated at step120. The weighted average expected search distance is calculated as follows:

ψi=P⁡(di)∑dj∈Ω⁢P⁡(dj)=Ci,j∑ij⁢Cj,j
and wherein ψirepresents the probability of randomly selecting a unit that contains the word di. ψiprovides the ability to calibrate the measure relative to the average distance it would take to traverse from a randomly chosen word to the keyword, dk. {tilde over (c)}ktherefore, represents the weighted average expected search distance from all possible seed words, ds, to the keyword, dk. The upper limit of the summation can again be defined as g and {tilde over (c)}kis represented by:

As noted, common words occurring in the training set will bias the expected search distancecd,kmaking common words appear to be relevant to all words. Calibration of the expected search distance using the weighted average expected search distance mitigates the effects of common words on the expected search distance measurement. Thus, rather than using the expected search distance directly, at step122, a word pair relevancy measure is calculated. The word pair relevancy is provided by the ratio of the expected search distance for the seed word-keyword pair relative to the weighted average expected search distance of the keyword (averaged over all possible seed words). This word pair relevancy measure is provided by:

Although the expected search distance,cd,k, is biased and makes all common words appear to be important, whencd,kis divided by the corresponding weighted average expected search distance, {tilde over (c)}k, the impact of that bias is greatly reduced and a particularly useful word pair relevancy measurement is provided.

With this calibration, a word that is neutrally relevant to all words will have a word pair relevancy measure near 1 with all words, and a word that is perfectly correlated with a keyword will have a word pair relevancy measure of (1/{tilde over (c)}k). The word pair relevancy measure for disjointed words will be near infinity.

This calibrated word pair relevancy measure has a variety of advantages over the measure of expected search distance. One advantage is that the measurement of the relevancy of a particular seed word to itself is a function of the average search distance from a random seed word to it. Therefore, very common words such as “the” will have less significant scores to themselves than uncommon words. The examples provided herein will demonstrate that this feature eliminates the need to identity and remove common words from the analysis. Ranking documents relative to a keyword without the need to explicitly account for common or rare words in pre-processing distinguishes the present invention from prior art searching and ranking methods. Although 0≤sd,k≤∞ in principle, the summation over the number of searches (transitions) n will be finite in practice, so 1/N≤sd,k≤N when the summation is over N searches.

FIG. 9illustrates a device150of the present invention for determining relevancy of a pair of words (e.g., a first word and a second word, or a seed word and a keyword). The device150generally includes an interface152, a word identifier154, a unit portioner156, a word pair identifier158, a co-occurrence matrix generator160, a word pair selector162, a probability matrix generator164, a matrix normalizer166, an expected search distance generator168, a calibrating vector generator170, a weighted average expected search distance generator172, and a calibrator174.

The interface152includes an input178and an output180. Information regarding a first set of documents is received on the input178. Information regarding the first set (i.e. the training set) of documents, X, and regarding individual documents in the training set is received by the interface152. The interface152provides information regarding the training documents at the output180of the interface152.

The word identifier154identifies the words of the training set, X. The word identifier154is in communication with the interface152via the output180of the interface152. The word identifier154further includes an output182for communication with the word pair identifier158. As noted above, the word identifier154may, for example, utilize a computer program such as Python's Natural Language Tool Kit. Upon identifying the unique search words of the training set documents, the search word list, Ω, is created and provided on the output182.

The word pair identifier158includes a first input and an output188. The input of the word pair identifier158is in communication with the word identifier154via the output182of the word identifier154. The word pair identifier158pairs each search word, di, with another search word, dj, to define search word pairs (di, dj), where di, and dj, may be the same word, thereby identifying each possible pair which can be identified from the search word list. Each word pair identified is provided at the output188and is provided to the unit portioner156, the co-occurrence matrix generator160, and the word pair selector162. The word pair identifier158is realized on a microprocessor, a discreet circuit, or an ASIC.

The unit portioner156is in communication with the output180of the interface152, to receive information regarding the training documents. The unit portioner156identifies the “units” of the training documents. The unit portioner156has a first input associated with the output180of the interface152, a second input associated with the output188of the word pair identifier158, and an output186at which the unit portion information is provided. As noted above, the user-definable units identified by the unit portioner156may be a sentence, a paragraph, a page, a chapter, or any other user-definable unit. If for example, the unit is defined as a paragraph, break lines between paragraphs may be used to identify the units. The unit portioner156is realized on a microprocessor, a discreet circuit, or an ASIC.

The co-occurrence matrix generator160creates a co-occurrence matrix, C(X). As discussed above, the co-occurrence matrix, C(X) is created utilizing the search word list, Ω. In the co-occurrence matrix C(X), each search word diis provided in a row and each search word djis also provided in a column. For each search word pair (di, dj) identified by the word pair identifier158, the number of units in which the search word pair (di, dj) is present are counted and recorded in the co-occurrence matrix as the search pair count Ci,j(X). Ci,j(X) represents, therefore, the number of unit word sets where the words diand djoccur together in a unit and are both from the search word list Ω. The size of the co-occurrence matrix is, therefore, |Ω| by |Ω|. The co-occurrence matrix generator160has a first input connected to the output186of the unit portioner156, a second input connected to the output188of the word pair identifier158, and an output190at which appears the co-occurrence matrix. The co-occurrence matrix generator160is realized on a microprocessor, a discreet circuit, or an ASIC. It is understood that many of the entries in the co-occurrence matrix, Ci,j(X), may be zero. Therefore, when storing the co-occurrence matrix on a computer, the size of the co-occurrence matrix may be greatly reduced by eliminating the zero entries from the co-occurrence matrix.

The word pair selector162of the device150, selects a combination of the two words from the training word list, Ω, to provide a seed word-keyword pair. The word pair selector162has an input connected to the output188of the word pair identifier158, and has an output196at which appears first and second vectors identifying the first and second words of the seed word-keyword pail. The word pair selector162is realized on a microprocessor, a discreet circuit, or an ASIC.

The probability matrix generator164of the device150generates a probability matrix as a function of the co-occurrence matrix. The probability matrix generator164has an input connected to the output190of the co-occurrence matrix generator160and an output192at which appears the probability matrix. The probability matrix generator164divides each entry in the co-occurrence matrix by the total number of the units of the first set or training set, X, to give the probability P(di, dj) of observing words diand djtogether in a unit. The probability matrix generator164divides the diagonal entries of the co-occurrence matrix by the number of units of the first set or training set, X, to give the probability P(di) of observing the word diin a unit, and divides this into P(di, dj) to give the probability P(di|dj) of observing word djin a unit given that diis in the unit. The results are stored in the probability matrix where the words of the search word list, Ω, represent the rows and columns of the probability matrix. The probability matrix generator164is realized on a microprocessor, a discreet circuit, or an ASIC.

The matrix normalizer166of the device150row-normalizes the probability matrix generated by the probability matrix generator164to form a transition matrix representing the transition probability. The matrix normalizer166includes a first input connected to the output192of the probability matrix164and an output194connected to the expected search distance calculator168and to the weighted average expected search distance generator172. The transition matrix appears on the output194. The matrix normalizer166sums each row in the probability matrix, divides each entry in the probability matrix in a particular row by the sum of that row, and stores the result in a corresponding location in the transition matrix. The matrix normalizer166is realized on a microprocessor, a discreet circuit, or an ASIC. The transition matrix entries represent the probability of transitioning from the word dito the word djin a single step; i.e. the transition probability. The transition probability reflects the probability, when randomly choosing from the units containing the word, di, that a unit having the word, dj, will be chosen. The closer the relationship between the words diand dj, the greater the transition probability.

The expected search distance generator168determines an expected search distance for the seed word-keyword pair as a function of the probability matrix and the transition matrix, the first column vector, and the second column vector. The expected search distance generator168includes a user input197for receiving a user-definable value g, a second input in communication with the output192of probability matrix generator164, a third input in communication with the output194of the matrix normalizer166, a fourth input connected to the output196of the pair selector162, a first output198at which appears the expected search distance for the seed word-key word pair, and has a second output199at which appears the second column vector. The expected search distance generator168is realized on a microprocessor, a discreet circuit, or an ASIC. The expected search distance generator168determines an expected search distance as follows:

c_d,k=∑n=1∞⁢n⁡[Γ→⁡(d)]T·[(I-Γ→⁡(k)⊗Γ→⁡(k))·R·(I-Γ→⁡(k)⊗Γ→⁡(k))]n-1·M·Γ→⁡(k)⁢c_d,k=∑n=1∞⁢n⁡[Γ→⁡(d)]T·α→n⁡(k)
where
{right arrow over (α)}1(k)=M·{right arrow over (Γ)}(k)
{right arrow over (α)}n(k)=[(1−{right arrow over (Γ)}(k)⊗{right arrow over (Γ)}(k))·R·(I−{right arrow over (Γ)}(k)⊗{right arrow over (Γ)}(k))]·{right arrow over (α)}n-1(k)
for n≥2.
where d corresponds to the first word or seed word in the selected word pair, k corresponds to the second word or keyword in the selected word pair. As noted, above, the summation is limited by the value, g, which may be a user-defined value. {right arrow over (Γ)}(d) is the first column vector that includes all zeros and one 1 for selecting values in the transition matrix related to the first word or seed word in the selected word pair, R is the transition matrix, {right arrow over (Γ)}(k) is the second column vector that includes all zeros and one 1 for selecting values in the transition matrix related to the second word or keyword in the selected word pair, I is an identity matrix, and ⊗ is a tensor, or outer, product of two vectors.

The details of the expected search distance generator168are described below and illustrated inFIG. 10. The expected search distance,cd,k, for disjointed words will have a value that is very large (e.g., approaching infinity). The expected search distance,cd,k, for highly related words will have a very low value. In theory, the expected search distance requires an infinite summation. In practice, however, a few hundred transitions are sufficient before a useful precision of several decimal points is reached, the summation, therefore is limited by the user-defined value, g.

The device150ofFIG. 9also includes a calibrating vector generator170for generating a calibrating vector that consists of a normalized version of the diagonal entries of the co-occurrence matrix. The calibrating vector generator170has an input connected to the output190of the co-occurrence matrix generator160, and has an output195at which appears the calibrating vector ψi. The calibrating vector ψiis created as follows:

ψi=P⁡(di)∑dj∈Ω⁢P⁡(dj)=Ci,i∑ji⁢Cj,j
The calibrating vector generator170is realized on a microprocessor, a discreet circuit, or an ASIC.

The device150also includes a weighted average expected search distance generator172for determining a weighted average expected search distance for the second or keyword in the selected word pair as a function of the transition matrix, the second column vector, and the third column vector. The weighted average expected search distance generator172has a first input connected to the output199of the expected search distance generator168, has a second input connected to the output194of the matrix normalizer166, a third input connected to the output195of the calibrating vector generator170, the user-defined input197for receiving a user-definable value g, and an output193at which appears the weighted average expected search distance for the keyword of the selected seed word-keyword pair. The weighted average expected search distance generator172is realized on a microprocessor, a discreet circuit, or an ASIC. The weighted average expected search distance generator172determines a weighted average expected search distance as follows:

The device150also includes calibrator174for determining the relevancy of the seed word of the selected word pair to the keyword in the selected word pair as the first output198of the expected search distance generator168divided by the output193of the weighted average expected search distance generator172. The calibrator174has a first input connected to the first output198of the expected search distance generator168, a second input connected to the output193of the weighted average expected search distance generator172, and has an output191at which appears the word pair relevancy measure which provides the relevancy of the first word (seed word) in the selected word pair to the second word (keyword) in the selected word pair. It is noted that the smaller the word pair relevancy measure, the more relevancy there is between the first and second word of the selected word pair.

FIG. 10provides a detailed block diagram of the expected search distance generator168ofFIG. 9. The expected search distance generator168includes a column vector generator200, a first multiplier202, a dot product generator204, an identity matrix generator206, a subtractor208, a second multiplier210, an integer generator212, a third multiplier214, a transposer216, a fourth multiplier218, a fifth multiplier220, and a summer222.

The column vector generator200includes a first input in communication with the output196of the word pair selector162and a second input in communication with the output194of the matrix normalizer166for receiving the transition matrix R. The column vector generator200further includes a first output224on which the first column vector {right arrow over (Γ)}(d) is provided. A second output of the column vector generator200provides the output199of the expected search distance generator169. The second column vector f (k) is provided on the output199.

The first multiplier202of the expected search distance generator168includes a first input connected to the output192of the probability matrix generator164, a second input in communication with the second output199of the column vector generator200, and an output228. The first input receives the probability matrix M and the second input receives the second column vector. The output228provides the product of the probability matrix M and the second column vector {right arrow over (Γ)}(k).

The dot product generator204of the expected search distance generator168includes two inputs in communication with output199of the column vector generator. The dot product generator204includes an output230at which the dot product of second column vector {right arrow over (Γ)}(k) with itself appears.

The expected search distance generator168also includes an identity matrix generator206. The identity matrix generator206includes an input in communication with the output194of the matrix normalizer166and an output232at which appears an identity matrix (i.e., a matrix that has ones on its diagonal and zeros everywhere else). The identify matrix is equivalent in size to the transition matrix received at the input of the identify matrix generator206.

The subtractor208of the expected search distance generator168includes a first input connected to the output230of the dot product generator204, a second input connected to the output232of the identity matrix generator206, and an output234at which appears the difference between the identity matrix and the dot product of the second column vector {right arrow over (Γ)}(k) and itself

The second multiplier210of the expected search distance generator168includes a first input which receives the transition matrix, R and second and third inputs in communication with the output of the subtractor208. The second multiplier210further includes an output236on which appear the product of the three inputs to the second multiplier210.

The integer generator212of the expected search distance generator168includes an input in communication with the input197for receiving a user-definable value g and an output238at which appears the value g and n integers, where the integers range from 1 to g.

The third multiplier214of the expected search distance generator168includes a first input connected to the output238of the integer generator212, a second input connected to the output228of the first multiplier282, a third input connected to the output236of the second multiplier210, and a fourth input at which the output of the third multiplier214is fed back to the third multiplier214. The third multiplier214further includes an output240at which appears
{right arrow over (α)}1(k)=M·{right arrow over (Γ)}(k)
and
{right arrow over (α)}n(k)=[(1−{right arrow over (Γ)}(k)⊗{right arrow over (Γ)}(k))·R·(I−{right arrow over (Γ)}(k)⊗{right arrow over (Γ)}(k))]·{right arrow over (α)}n-1(k)

for n≥2.

The transposer216of the expected search distance generator168includes a first input connected to the first output224of the column vector generator200, a second input connected to the output194of the matrix normalizer166, and an output at which appears the transposed first column vector {right arrow over (Γ)}(d).

The fourth multiplier218of the expected search distance generator168includes a first input in communication with the output238of the integer generator212, a second input in communication with the output242of the transposer216, and an output246at which appears the product of the transposed first column vector {right arrow over (Γ)}(d) and the values n, where the values n are the integers from 1 to g.

The fifth multiplier220of the expected search distance generator168includes a first input in communication with the output238of the integer generator212, a second input in communication with the output246of the fourth multiplier218, and a third input in communication with the output240of the third multiplier214. The fifth multiplier further includes an output248at which appears the products of the output240of the third multiplier214and the output246of the fourth multiplier218for the values n, where the values n are the integers from 1 to g.

The summation block222of the expected search distance generator168includes a first input in communication with the output238of the integer generator212, a second input in communication with the output248of the fifth multiplier220. The summation block222also includes an output in communication with the output198of the expected search distance generator168at which appears the expected search distance as follows:

FIG. 11provides a detailed block diagram of the weighted average expected search distance generator172ofFIG. 9. The weighted average expected search distance generator172generally includes a first multiplier250, a dot product generator252, an identity matrix generator254, a subtractor256, a second multiplier258, an integer generator260, a third multiplier262, a transposer264, a fourth multiplier266, a firth multiplier268, and a summation bock270.

The first multiplier250generally includes a first input, a second input and an output272. The first input is in communication with the output199of the expected search distance generator168on which the second column vector {right arrow over (Γ)}(k) is provided. The second input is in communication with the output192of the probability matrix generator164on which the probability matrix, M, is provided. The output272of the first multiplier provides the product of the probability matrix and the second column vector {right arrow over (Γ)}(k).

The dot product generator252includes first and second inputs and an output274. The first and second inputs are in communication with the output199of the expected search distance generator168on which the second column vector {right arrow over (Γ)}(k) is provided. The dot product of second column vector {right arrow over (Γ)}(k) with itself is provided on the output274.

The identity matrix254includes an input in communication with the output194of the matrix normalizer166and an output276at which appears an identity matrix (i.e., a matrix that has ones on its diagonal and zeros everywhere else) which is the size of the transition matrix received at its first input.

The subtractor256includes first and second inputs and an output278. The first input is in communication with the output274of the dot product generator252and the second input is in communication with the output276of the identity matrix generator254. The output278provides the difference between the identity matrix and the dot product of the second column vector {right arrow over (Γ)}(k) and itself.

The second multiplier258includes first, second and third inputs and an output280. The first input is in communication with the output194of the matrix normalize. The second and third inputs are in communication with the output278of the subtractor256. The product of the first, second, and third inputs is provided on the output280of the second multiplier258.

The integer generator260includes an input in communication with the user-defined input197for receiving a user-definable value g and an output282at which appears the value g and n integers, n, where the integers range from 1 to g.

The third multiplier262includes first, second, third and fourth inputs and an output284. The first input is in communication with the output282of the integer generator260. The second input is in communication with the output272of the first multiplier250. The third input is in communication with the output280of the second multiplier258. The fourth input is fed back from the output284of the third multiplier262. The output284provides the following products:
{right arrow over (α)}1(k)=M·{right arrow over (Γ)}(k), forn=1, and
{right arrow over (α)}n(k)=[(1−{right arrow over (Γ)}(k)⊗{right arrow over (Γ)}(k))·R·(I−{right arrow over (Γ)}(k)⊗{right arrow over (Γ)}(k))]·{right arrow over (α)}n-1(k)
for n≥2.

The transposer264includes a first input in communication with the output195of the third column vector generator170and a second input in communication with the output194of the matrix normalizer166on which normalized transition matrix R is provided. The transposer264further includes an output286at which appears the calibrating column vector transposed.

The fourth multiplier266includes a first input in communication with the output282of the integer generator260, a second input in communication with the output286of the transposer264, and has an output288at which appears the products of the transposed third column vector {right arrow over (Ψ)} and n integers, where the integers range from 1 to g.

The fifth multiplier268includes a first input in communication with the output282of the integer generator260, a second input in communication with the output284of the third multiplier262, and a third input in communication with the output288of the fourth multiplier266. The fifth multiplier268further includes an output290at which appears the products of the corresponding outputs of the integer generator260, the third multiplier262and the fourth multiplier266for the values n, where the values n are the integers from 1 to g.

The summation block270includes a first input in communication with the output282of the integer generator260and a second input in communication with the output290of the fifth multiplier268. The summation block270further includes an output which provides the output193of the weighted average expected search distance generator172at which appears the weighted average expected search distance as follows:

A word pair relevancy measure is provided by the method100ofFIG. 2and by the device150ofFIG. 9. Examples of word pair relevancy measures utilizing the method100and the device150are provided in Tables 1 and 2. The training set used in connection with the examples of Tables 1 and 2 was the Mar. 14, 2012 version of the English Wikipedia. The unit text size was a paragraph as defined by the Wikipedia xml schema.

Table 1 provides the word pair relevancy measure, sd,k, with the first words (seed words) provided in the columns and the second words (keywords) on the left. As noted above, the smaller the value provided for the word pair relevancy measure, the more significant the relationship between the keyword, k, and the search word, d. Disjointed words, on the other hand, will have a measure near infinity. It is noted that each of the first words (search words) provided in Table 1 are “common words”, i.e. words that have no particular relevancy to the keywords, k.

As noted above, the word pair relevancy measure does not utilize the expected search distance directly, but rather utilizes the ratio of the expected search distance from a seed word to the keyword relative to the weighted average expected search distance of the keyword (averaged over all possible seed words). As a result, a word that is neutrally relevant to all words will have a word pair relevancy measure near 1 with all words, and a word that is perfectly correlated with a keyword will have a measurement of (1/{tilde over (c)}k) where {tilde over (c)}kis the weighted average expected search distance from all possible search words to the keyword, k. For each of the search words provided in Table 1, the word pair relevancy measures are very near one (1) indicating that each of the search words is neutrally relevant with respect to each of the keywords.

Table 2 provides word pair relevancy measures, sd,k, with the words on the left as the keywords, k, and the seed words, d, provided in the columns. The smaller the value of the measure provided in the table, the more significant the relationship between the keyword, k, and the seed word, d. The seed words selected in Table 2 include words in addition to the common words “the” and “and”. The common seed words are associated with word pair relevancy measures very near 1. In contrast however, the remaining seed words have smaller word pair relevancy measures if the seed word is relevant to the keyword.

It is noted that the word pair relevancy measure, sd,k, is a relative measure, and not an absolute measure. Therefore, word pair relevancy measurements from different keywords, k1and k2, cannot be compared directly. As a result, an understanding of the difference between two relevancy measurements sd,k1and sd,k2is not intuitive. As discussed below, in some instances, the ability to gauge the significance of a particular relevancy measure to multiple keywords is desired. The present invention, therefore, provides a normalized word pair relevancy measure to allow the significance of the word pair relevancy measures to multiple keywords to be easily understood.

The method for determining the normalized word pair relevancy measure is illustrated inFIG. 12. As illustrated inFIG. 12, the process300for determining the normalized word pair relevancy begins at step302by defining a set of reference words A. For example, the reference words may be the set of “common” words, such as “the”, “a”, “that”, “there”, etc. Alternatively, for example, the set of reference words, may be the ten most common words of the set. The set, A, of reference words includes words which are anticipated to have no connection to most or all of the search terms. More specifically, the set A of reference words includes words which are not relevant (i.e. have no significance) to either of the keywords, k1or k2, to be compared.

Having defined the set A at step302, the word pair relevancy for each reference word-keyword pair (or “reference word pair”) is calculated at step304in accordance with the method100described inFIG. 2. The word pair relevancy for each reference word-keyword pair is identified as sa,k.

Next, at step306the word pair relevancy for the seed word-keyword pair sd,k. is calculated in accordance with the method100described inFIG. 2.

Next, at step308the normalized word pair relevancy measure, s′d,k, is calculated for the identified seed word-keyword pair. An example for calculating the normalized word pair relevancy measure s′d,kis:

μk⁡(A)=1A⁢∑a∈A⁢sa,k
and

A device for determining the normalized word pair relevancy measure is illustrated inFIG. 13. The device350generally includes, the word pair relevancy measuring device150, a reference word set identifier352, a reference word pair relevancy identifier354, a reference word pair summer356, and a normalized word pail relevancy calculator358. The word pair relevancy measure150is discussed in detail with respect toFIG. 9

The reference word set identifier352includes an input362which receives the reference words, a, to define a set of reference words A. A first output364of the identifier352identifies the reference words, a, and a second output366identifies the magnitude of the set A.

The reference word pair relevancy identifier354includes a first input which receives the output191of the word pair relevancy measuring device150on which the word pair relevancy measure sd,kis provided. A second input of the identifier354is in communication with the output364of the reference word set identifier352. An output368of the reference word pair relevancy identifier354provides a word pair relevancy measure sa,kfor each reference word, a.

The reference word pair summer356includes a first input in communication with the output368of the identifier354and an output370. The output370provides the sum of the word pair relevancy measures sa,kfor each reference word, a, in the set A.

The normalized word pair relevancy calculator358includes a first input connected to the output191of the word pair relevancy measure150, a second input connected to the output370of the word pair relevancy summer356, a third input connected to the output366of the reference word set identifier352, and an output372. The output372of the normalized word pair relevancy calculator provides a normalized word pair relevancy measure, s′d,k, for the seed word-keyword pair (d,k).

The normalized word pair relevancy measure as described above utilizes a standard statistical normalization method. It is to be understood, however, that different methods may be utilized for providing a normalized relevancy measure. For example, a Bayesian regression may be used to calculate a normalized relevancy measure, s′d,k.

TABLE 3Normalized word pair relevancy measures, s′d,kfor pairs of words.theandagricultureautomobilefordcartractorfoodAgriculture0.59−0.47−494−5.48−0.560.38−39−10Automobile−0.75−1.27−29−2603−85−63−527−0.65Ford−0.84−1.70−19−157−2240−133−200.15

Table 3 provides the normalized word pair relevancy measure, s′d,k, for the same search words and keywords included in Table 2. These normalized calculations allow for a direct comparison of the normalized word pair relevancy measures for different keywords; i.e., the measurements provided in Table 3 indicate that the seed word “agriculture” is less relevant to the keyword “automobile” than the seed word “ford” is to the keyword “automobile”.

The word pair relevancy measures in Table 1 and 2 can be used to effectively rank the relevancy of seed words to a particular keyword, but only the normalized word pair relevancy measures of Table 3 can be compared across keywords. For example, using Table 2, it would appear that the relevancy of “agriculture” to itself is as strong as “automobile” to itself. However, Table 3 suggests that finding a document with the word “automobile” when the keyword is “automobile” is much more significant than finding a document with the word “agriculture” when the keyword is “agriculture.” This is an artifact of the word “agriculture” being more common in the training set than the word “automobile,” and this successfully mimics a human's intuition which would take into account the rarity of a keyword when judging the significance of finding documents with that keyword. Tables 2 and 3 together provide confidence with respect to the normalized word pair measurement.

s′d,k(A), therefore, represents the number of standard deviations sd,kis from the mean of measures to the reference words. A rule of thumb is that pairs of words with measures s′≤−3 are potentially relevant to each other, and words with measures s′≤−6 are likely relevant to each other.

A notable drawback of this normalized word pair relevancy measure is that it requires a user to define the set of reference words A. It is noted, however, that the set A of reference words can be defined automatically without requiring user input by utilizing an automated method.

To further illustrate how the normalized word pair relevancy measure can be used to mimic the intuition that would be employed by a person, consider the following example of determining the relevancy of the names of four countries to a list of former heads of state and names of provinces from these countries. The list of the former heads of state along with the normalized word pair relevancy measure, s′d,kfor each is given in Table 4. The list has been sorted in accordance with the normalized word pair relevancy measures. In calculating the normalized word pair relevancy measure, s′d,k, set A was defined as including the common words either, or, not, only, but, also, neither, nor, both, and, whether, just, as, so, of to, in, for, on, that, there, the, a, an, thee, whence, was, with, if at, from, among, within.

In each column, the four terms in the list that are related to their keyword country appear much more relevant than the other words, where lower scores imply stronger relevancy. For example, the normalized word pair relevancy measures provided in Table 4 indicate that the relevancy measurement for the word pair (France, Sarkozy) is more significant than the relevancy measurement for the word pair (France, Fox). As will be discussed below, the word pair relevancy measures provided by the present invention are utilized to rank the relevancy of documents to a keyword(s). Thus, someone querying for documents related to France, for example, would have documents ranked near the top if they discussed Sarkozy's presidency, even without the documents ever explicitly mentioning France. It is worth taking note of how Fox scored. The term “fox” is an ambiguous term because “fox” could refer to the former Mexican president Vicente Fox or to a small animal. The term “fox” scores highly with respect to Mexico, but less highly than terms that are unambiguously connected to Mexico. It also scores somewhat highly with respect to the other countries, which all have the small animals in them, but much less highly than it does with Mexico. This is exactly the behavior that is desired.

Ranking Documents in the Live Set

When the live set (i.e. a collection of live documents) is provided to a searcher and the searcher is tasked with finding information relevant to a particular keyword from these live documents, the searcher needs the ability to locate and rank the potentially relevant live documents. The present invention utilizes the word pair relevancy calculations or the normalized word pair relevancy calculations provided by the training documents to determine the relevancy of a live document to a particular keyword. Specifically, each word in the live document is identified as a seed word, d, and each seed word, d, is paired with the keyword, k to provide seed word-keyword pairs (d,k). The calibrated word pair relevancy or normalized word pair relevancy for each seed word-keyword pair associated with the document is then utilized to provide a document relevancy measure as will be discussed herein. This relevancy determination is then utilized to provide a ranking of the documents in the live set. Thus, the notion of relevancy derived for the search word pairs of the training set is expanded to a notion of relevancy of documents from a live set of documents.

The invention provides several options, of varying rigor, for finding a measure of relevancy between a keyword, k, and a live set document, D.

A first and relatively simple method400for ranking live documents relative to a keyword is illustrated inFIG. 14. The process begins at step402by identifying the documents of the live set to be ranked. Next, at step404a keyword is identified and at step406a particular document to be ranked is identified. At step408, the live document word pairs are identified, wherein each word in the document is utilized as a seed word, d, and paired with the selected keyword, k, to provide a plurality of live document seed word-keyword pairs (d, k) associated with the live document. Next, at step410, the word pair relevancy measures associated with each identified live document seed word-keyword pair (d, k) is determined. For example, the word pair relevancy measure described in connection withFIG. 2, may be utilized for determining the word pair relevancy measure for each live document seed word-keyword pair. Next, at step412, the product of the word pair relevancy measures is calculated to provide the document relevancy measure. The document relevancy measure can be expressed as:
S(D˜k)=Πd∈Dsd,k

D represents the set of words din the document D, with duplicates. The product of all word pair relevancy measures, sd,k, for each live document seed word-keyword pair (d,k) (or “live document word pair”) associated with the document D provides the document relevancy of D to the keyword k, S(D˜k), i.e. the document relevancy measure. Since reference words are neutrally correlated to the keyword, reference words tend to have a word pair relevancy measurement near 1 and the product of measurements for individual seed word-keyword pairs (live document word pairs) can be used to score a document without the document words that are neutrally correlated to the keyword(s) having much effect on the final outcome.

At step414it is determined whether the relevancy measure for each document to be ranked has been calculated. If additional document relevancy measurements are to be determined, the process returns to step406. If at step414it is determined that a document relevancy measurement has been determined for each document to be ranked, the process proceeds to step416.

At step416the document relevancy measures are utilized to rank the relevancy of the live documents relative to the keyword.

A device for ranking documents based upon document relevancy measure is illustrated inFIG. 17. The device600generally includes an interface602, a live document identifier604, a live document word pair identifier606, a word pair relevancy measurer150, a document relevancy calculator610, a memory612, and a sorter614.

The interface602retrieves information regarding the live documents to be ranked. The interface602includes an input620on which information regarding the live documents is received and an output622on which information regarding the live documents is provided to the device600.

The live document identifier604includes a first input in communication with the output622of the interface602and a second input624from which the user may identify a live document to be ranked. The identifier604further includes an output626on which information regarding the live document is provided.

The live document word pair identifier606includes a first input in communication with the output626of the live document identifier604and a second input628from which a user may define a keyword, k. The live document word pair identifier further includes an output630on which the identified live document seed word-keyword pairs (d,k) are provided.

The word pair relevancy measurer150includes an input in communication with the output630of the live document word pair identifier606and an output191. The word pair relevancy measurer150is described in detail in connection withFIG. 9. The identified live document seed word-keyword pairs are provided to the word pair relevancy measurer150and the word pair measurer150provides the word pair relevancy measure for each of the live document seed word-keyword pairs for the identified document on the output191.

The document relevancy calculator610is provided by a multiplier. The multiplier610includes an input in communication with the output191and an output632. The multiplier multiplies the word pair relevancy measures of the live document seed word-keyword pairs and provides the product as the document relevancy measure on the output632.

The memory612includes an input in communication with the output632of the multiplier610and an output634. The memory stores the product provided by the multiplier for each live document identified by the live document identifier604.

The sorter616includes an input in communication with the memory612and an output636. The sorter616receives the document relevancy measures from the memory612and sorts the measures to provide a ranking of the document relevancy measures on the output636.

The document relevancy measure provided by the method400and the device600is beneficial because it can be computed quickly, it reasonably mimics a human's ranking of relevancy, and it does not require a set of reference words A to be defined or an additional set of documents, Δ, that will be required for greater rigor (as will be discussed below). Upon calculating the document relevancy measure, S(D˜k) for each document, the documents are ranked in accordance with the document relevancy measures. An example of utilizing the document relevancy measure provided above to rank documents of interest to a searcher was conducted. The keyword searched was “cosmology”. The set of documents, D, included all of the Reuters articles from 3-28-2012. Using a Boolean keyword search, no results were returned to the searcher because the word cosmology did not appear in any of the articles that day. However, when ranking the news articles utilizing the document relevancy calculation, S(D˜k), provided above, an article about the astronomy of exoplanets was ranked highest. This article was clearly relevant to cosmology, and would probably be of interest to many readers who were particularly interested in cosmology, even though the article was not strictly about the origin and fate of the universe.

Similarly, a ranking of the relevancy of documents to the keyword NAFTA (North American Free Trade Agreement) provided the highest ranking to an article about a Mexican presidential candidate, even though the article did not contain the term NAFTA. These examples illustrate that document relevancy calculations and rankings provided by the present invention are particularly useful when Boolean searches fail (e.g. when the keyword is not present in the relevant document).

Although the document relevancy measure S(D˜k) provided above can be used to properly rank documents from a single language based on a single keyword, it is difficult to directly generalize rankings that involve multiple keywords, because each relevancy measure is made from a unique reference point. When a set of reference or irrelevant words A is available, however, a ranking relative to multiple keywords can be accomplished utilizing the normalized word pair relevancy measure discussed above.

The method450of ranking documents relative to a keyword(s) utilizing a normalized document relevancy measurement is illustrated inFIG. 15. The process begins at step452by identifying the documents of the live set to be ranked. Next, at step454a keyword is identified and at step456a particular document, D, to be ranked is identified. At step458, the live document seed word-keyword pairs are identified utilizing each word d, of the document, D, as a seed word. Each seed word is paired with the selected keyword to provide a live document seed word-keyword pairs.

Next, at step460, the normalized word pair relevancy measure, s′d,k, associated with each identified live document seed word-keyword pair (d, k) is calculated utilizing the normalized word pair relevancy calculation discussed above in connection withFIG. 4.

Next, at step462, the sum of the normalized word pair relevancy measures is calculated to provide the normalized document relevancy measure. The normalized document relevancy measure, S(D˜k|A), is calculated as follows:
S(D˜k|A)=Σd∈Ds′d,k.
D represents the set of words din the live document D, with duplicates. The sum of all normalized word pair relevancy measures, s′d,k, for each word d, provides the relevancy of D to the keyword k, S(D˜k|A), i.e. the normalized document relevancy measure.

At step464an inquiry is made as to whether a normalized document relevancy measure has been calculated for each document of the live set to be ranked. Once all of the normalized relevancy measures have been calculated for the keyword identified, at step466an inquiry is made as to whether the relevancy of documents to additional keywords is to be determined. If additional normalized document relevancy measures are to be made for additional keywords, the process returns to step456. Once the relevancy of documents to all keywords has been determined, at step468, the documents are ranked relative to the keyword(s).

A device for ranking documents utilizing the normalized document relevancy measure is illustrated inFIG. 18. The device700generally includes an interface702, a live document identifier704, a live document word pair identifier706, a normalized word pair relevancy measurer350, a document relevancy calculator710, a memory712, and a sorter714.

The interface702retrieves information regarding the live documents to be ranked. The interface702includes an input720on which information regarding the live documents is received and an output722on which information regarding the live documents is provided.

The live document identifier704includes a first input in communication with the output722of the interface702and a second input724from which the user may identify a live document to be ranked. The identifier704further includes an output726on which information regarding the live document is provided.

The live document word pair identifier706includes a first input in communication with the output726of the live document identifier704and a second input728from which a user may define a keyword, k. The live document word pair identifier further includes an output730on which the identified live document seed word-keyword pairs (d,k) are provided.

The normalized word pair relevancy measurer350includes an input in communication with the output730of the live document word pair identifier706and an output370. The normalized word pair relevancy measurer350is described in detail in connection withFIG. 13. The identified live document seed word-keyword pairs are provided to the normalized word pair relevancy measurer350and the normalized word pair measurer350provides the normalized word pair relevancy measure for each of the live document seed word-keyword pairs for the identified document on the output370.

The document relevancy calculator710is provided by a summer. The summer710includes an input in communication with the output370and an output732. The summer sums the normalized word pair relevancy measures of the live document word pairs and provides the sum as the normalized document relevancy measure on the output732.

The memory712includes an input in communication with the output732of the summer710and an output734. The memory712stores the sums provided by the summer for each live document identified by the live document identifier704. If relevancy relative to multiple keywords is to be evaluated, the memory172includes normalized document relevancy measures for each keyword to be evaluated.

The sorter714includes an input in communication with the output734of the memory712and an output736. The sorter714receives the document relevancy measures from the memory712and sorts the measures to provide a ranking of the document relevancy measures on the output736. If normalized document relevancy measures provided by the memory, include the document relevancy measures for multiple keywords, the ranking provided by the sorter provides an indication as to the relevancy of the live documents relative to multiple keywords.

Just as the normalized word pair relevancy calculation, s′d,k, provided clearer results than the word pair relevancy measure, sd,k, by normalizing the relevancy relative to reference words, the normalized document relevancy calculation S(D˜k|A) provides a clearer result than the document relevancy calculation S(D˜k) by normalizing the relevancy relative to reference words. The normalized word pair relevancy measures, s′d,k, utilized in the normalized document measure have a mean of 0 for reference words. Thus, the normalized word pair measures for each live document seed word-keyword pair (d,k) of the document, D, can simply be added to provide the normalized document measure and will minimally impact the normalized document relevancy measure when many reference words occur in the document.

At least two methods for calculating the normalized relevancy measure S′d,khave been described above and it is to be understood that additional methods may be utilized for providing a normalized relevancy measure for the word pairs. Regardless of the method used to calculate the normalized relevancy measure for the word pairs, the normalized document measure, S(K˜k|A), can be calculated as described herein.

This normalized document measure, S(D˜k|A), works well when ranking documents relative to a single keyword and works fairly well for ranking documents with respect to multiple keywords as will be illustrated below. However, because shorter documents provide less data from which a conclusion can be drawn as to the relevancy of the document, D, to a keyword, k, the document relevancy calculations for shorter documents is less certain. Thus, the normalized document relevancy calculation can occasionally give misleading results when comparing short documents to rather long documents (e.g. comparing a tweet to a book) but is particularly useful when ranking documents which are of similar length, for example, within a couple thousand words of each other.

In order to overcome the difficulties of ranking documents of varying length, an even more rigorous method for measuring the relevancy of a keyword to a document is provided. This method provides a modified document relevancy measure which requires the use of a reference set of documents Δ. The reference set of documents, Δ, represents a large set of documents. The reference set of documents, Δ, could be, for example, the training set of documents which was used to determine the relevancy measures of the seed word-keyword pairs or it could be a different set of documents distinct from the training set of documents and distinct from the live set of documents. It is important, however, that the reference set of documents, Δ, is large enough that the probability of observing particular relevancy measures between a keyword and a document in the live set can be accurately estimated. Whether the reference set of documents, Δ, is sufficiently large heavily depends on the type of data being analyzed in the live set.

The modified document ranking method is illustrated inFIGS. 16a-16c. The process begins at step502by identifying the live set of documents. At step504a keyword is identified. At step506a live document to be ranked is identified. At step510, the seed word-keyword pairs arc identified utilizing the words in the identified live document as seed words. Next, at step512the normalized word pair relevancy measure associated with each identified live seed word-keyword pair is determined. At step514the sum of the normalized word pair relevancy measures is calculated to provide a specified live document relevancy measure.

Proceeding to step516(See,FIG. 16b), a set of documents is identified as the referral set of documents, Δ. Next, at step518the possible document lengths are defined. For example, defined possible document lengths may be <500 words, 500-999 words, 1000-1999 words, 2000-2999 words, etc. At step520, a referral document from the set, Δ, to be measured is identified. At step522, the length of the document to be measured is determined based upon the defined document lengths. At step524, the referral document word pairs are identified utilizing the words in the referral document as seed words. Next, at step526, the normalized word pair relevancy measure, s′d,k, associated with each identified referral word pair is determined. The normalized word pair relevancy measure, s′d,k, for each referral word pair is determined as discussed above.

At step528, the sum of the normalized word pair relevancy measures is calculated to provide the normalized document relevancy measure of the referral document. At step530it is determined whether all normalized document measures have been calculated for each referral document in the referral set. If at step530all normalized document measures have not been calculated, then the process returns to step520. Once it has been determined at step530that the normalized document measure has been calculated for each document of the referral set, the process proceeds to step532. At step532, for each referral document length that has been determined, a referral probability is calculated. Each referral probability represents the probability of randomly selecting a document with a normalized document measure less than or equal to the specified normalized measure from step514. This probability is represented as follows:
S(D˜k|Δ)=P(S(D′˜k)≤S(D˜k)|D′∈Δ)

At step534(seeFIG. 7c), the probability S(D˜k|Δ) calculated at step532is determined to be the modified document relevancy measure for the identified live document. Thus, the modified normalized document relevancy measure of the live document is provided by the probability that a document D′ of length |D|, randomly selected from the referral set has a normalized document measure SD′˜k less than or equal to a specified live document measure S(D˜k). An inquiry is provided at step536to determine whether the modified document measure for each live document has been determined. If the modified document measure for each live document has not been determined, at step538the process returns to step506. If at step536it is determined that the modified normalized document measure for each live document has been determined, the process proceeds to step540where the live documents are ranked based upon the modified document relevancy measures.

A device for determining a modified document ranking is illustrated inFIG. 19. The device800generally includes a live document set interface802, a live document identifier804, a normalized document relevancy measurer806, a referral set interface808, a referral document identifier810, a document length identifier812, a normalized document relevancy measuring device814, a document length identifier816, a memory818, a probability calculator820, a memory822, and a sorter824.

The interface802retrieves information regarding the live documents to be ranked. The interface802includes an input850on which information regarding the live documents is received and an output852on which information regarding the live documents is provided.

The live document identifier804includes a first input in communication with the output852of the interface802and a second input854from which the user may select a live document to be ranked. The identifier804further includes an output856on which information regarding the selected live document is provided.

The normalized document relevancy measuring device806includes a first input in communication with the output856of the live document identifier804and a second user defined input858on which a user defines the keyword, k. The normalized document relevancy measuring device806includes an output860. The normalized document relevancy measuring device806calculates the normalized document relevancy for the selected document relative to the keyword, k, in a manner similar to the normalized document relevancy measuring device700described in detail in connection withFIG. 18. The normalized document relevancy measure provided by the device806is provided on the output860.

The referral set interface808includes an input868for receiving information regarding the referral set, Δ. The referral set interface808further includes an output870on which information regarding documents in the referral set, Δ, is provided.

The document length definer812includes a user input872on which the user can define document length ranges and an output874on which the document length range information is provided.

The referral document identifier810includes an input in communication with the output870of the referral set interface808. The referral document identifier810identifies a referral document from the set Δ. The referral document identifier includes an output878on which information regarding the selected referral document is provided.

The normalized document relevancy measuring device814includes a first input in communication with the output878of the referral document identifier810and a second user defined input880on which a user defines the keyword, k. The normalized document relevancy measuring device814includes an output882. The normalized document relevancy measuring device810calculates the normalized document relevancy for the selected referral document relative to the keyword, k, in a manner similar to the normalized document relevancy measuring device700described in detail in connection withFIG. 18. The normalized document relevancy measure provided by the device814is provided on the output882.

The document length determiner816includes a first input in communication with the output878of the referral document identifier and a second input in communication with the output874of the document length definer. The document length determiner816includes an output890. The document length determiner816determines the length of the selected referral document based upon the defined document lengths provided by the document length definer874and provides the determined length of the selected referral document on the output890.

The memory818includes a first input in communication with the output882of the normalized document relevancy measuring device814and a second input in communication with the output890of the document length determiner816. The memory includes an output892on which normalized document relevancy measures corresponding to the length of the referral document is provided.

The probability calculator820includes a first input in communication with the output860of the normalized document relevancy measuring device806and a second input in communication with the output892of the memory818. The probability calculator calculates the probability that a document randomly selected from the document set Δ and having a particular length will have a document relevancy score less than the document relevancy score provided by the device806. This probability calculated by the calculator820defines the modified document relevancy measure for the selected live document and is provided on the output894.

The memory822includes an input in communication with the output894of the probability calculator820and an output896. The memory822stores the modified document relevancy measure for each live document to be ranked.

The sorter824includes an input in communication with the output896of the memory822. The sorter898further includes an output898. The sorter receives the modified document relevancy measures for each of the live documents to be ranked and sorts the measures to provide a ranking of the live documents in the live document set relative to the keyword858. In the event that multiple keywords are utilized, the sorter sorts the measures to provide a ranking of the live documents relative to the multiple keywords.

Use of the modified document relevancy measure further reduces any bias that exists when ranking documents of varying lengths, provided that the referral set of documents, A, used to estimate the probabilities has documents of varied length and subject. Because this measure allows documents of different lengths to be analyzed with respect to different keywords on the same footing, it is suitable for most scenarios.

Searching with Multiple Keywords and Boolean Searching

Measuring the relevancy of documents to multiple keywords is useful for clarifying rankings and adding precision to the rankings by letting the searcher employ operations that mimic the Boolean operations of OR, AND, and NOT. Approximations of these Boolean operations can be used with the document relevancy measure, the normalized document relevancy measure, and the modified document measure to clarify the rankings of documents. The relevancy measures for each of the Boolean operations OR, AND, NOT for each of the document relevancy measure, normalized document relevancy measure and modified document relevancy measure are provided below.

The following equations provide approximations for the Boolean operation OR.
S([D˜k1]∨[D˜k2])=max{S(D˜k1),S(D˜k2)}

This first equation provides an option for ranking a document's relevancy to either a keyword, k1, OR keyword, k2, based on a document relevancy measure.
S([D˜k1]∨[D˜k2]|A)=max{S(D˜k1|A),S(D˜k2|A)}

This second equation provides an option for ranking a document's relevancy to either a keyword k1OR keyword, k2, based on a normalized document relevancy measure. As noted above, the normalized word pair measures for referral words have a mean of zero (0). Thus, the word pair measures can simply be added to give the document relevancy measure. Furthermore, the document relevancy for multiple keywords k1, k2, can be directly utilized to measure the relevancy of a document with respect to multiple keywords.
S([D˜k1]∧|∨[[D˜k2]Δ])=1−P(S(D′˜k1)≥S(D˜k1),S(D′˜k2)≥S(D˜k2)|D′∈Δ)

This third equation provides an option for ranking a document's relevancy to either a keyword k1OR keyword, k2, based on a modified document relevancy measure. Although the first and second equations provide a useful approximation of the Boolean operation OR, the third equation, which utilizes the modified document relevancy measure provides an even more accurate approximation of the Boolean operation OR. In order to approximate the Boolean operation OR utilizing the modified document relevancy measure, however, the document relevancy measure of the documents in a training set Δ must be determined.

The following equations provide approximations for the Boolean operation AND.
S([D˜k1]*[D˜k2])·S(D˜k1)·S(D˜k2)
This first equation provides an option for ranking a document's relevancy to both keyword, k1, AND keyword, k2, based on a document relevancy measure.
S([D˜k1]*[D˜k2]|A)=S(D˜k1|A)+S(D˜k2|A)

This second equation provides an option for ranking a document's relevancy to both a keyword k1AND keyword, k2, based on a normalized document relevancy measure.
S([D˜k1|∧]*[[n˜k2|Δ]])=P(S(D′˜k1)≤S(D˜1),S(D′˜k2)≤S(D˜k2)|D′∈Δ)

This third equation provides an option for ranking a document's relevancy to both a keyword k1AND keyword, k2, based on a modified document relevancy measure. Although the first and second equations provide a useful approximation of the Boolean operation AND, the third equation, which utilizes the modified document relevancy measure, achieves an accurate approximation of the Boolean operation AND. In order to approximate the Boolean operation AND utilizing the modified document relevancy measure, however, the document relevancy measure of the documents in a training set Δ must be determined.

The most difficult of the three operations to use for clarifying rankings in an intuitive manner is NOT, which may be used to find documents not relevant to a keyword. The problem with using NOT to clarify rankings based on relevancy stems from the fact that humans can fairly easily determine if a document is not relevant to a keyword in a binary fashion, but not in a ranking fashion. To illustrate this issue, consider a search that includes a document about automobiles and a document about astronomy, with a keyword of NOT-flower. Although humans would generally conclude that both documents correspond to NOT-flower, they would have trouble determining which document ranks higher with respect to NOT-flower.

A method for providing the NOT operation is to simply have NOT correspond to the inverse of the measure.

This equation utilizes the document relevancy measure and the multiplicative inverse to denote the exclusion of a particular keyword.

Another method for providing the NOT operation is as follows:
S([D˜k1]*[D˜k2]|A)=S(D˜k1|A)−S(D˜k2|A)

This equation utilizes the normalized document relevancy measure and the additive inverse, to denote the exclusion of a particular keyword.

Another alternative is to take advantage of the set of documents, Δ, using
S([D˜k1|Δ]*[[D˜k2|Δ]])=P(S(D′˜k1)≤S(D˜k1),S(D′˜k2)≥S(D′˜k2)|D′∈Δ)

This equation utilizes the modified document measure to find the probability of observing documents at random in the referral set, Δ, that are both more relevant to the keyword k1while also being less relevant to the keyword k2than the document D.

The present invention provides several advantages over prior art methods. For example, the present invention provides a method of determining relevancy for the purpose of ranking documents within large repositories even when other search and rank methods such as Boolean type searches are inadequate, for example, when the keyword is not present in the documents searched.

Another advantage provided by the present invention is the ability to search documents in multiple languages and to search documents in languages other than the language of the keyword. Without the present invention, choosing a keyword to find documents related to a particular topic can be challenging when the searcher does not know the language or the precise nomenclature used by the authors of the various documents being searched. This can be particularly difficult when the documents in the live set span multiple languages, as is the case with web pages on the internet. In contrast to prior art methods which require use of a translation tool to translate the documents to be searched to the language of the searcher prior to searching, no such translation is required by the present invention. By simply including a translational dictionary in the training set of documents, the relevancy between the words will be apparent.

Additionally, the present invention will determine the relevancy of words in a foreign language even if the word is not defined in a translational dictionary. For example, as societies and languages evolve (e.g. as new technologies and new concepts are introduced, each society will develop a nomenclature to accommodate them with either novel words or novel combinations of words) there will be temporary gaps in translational dictionaries. Using the prior art methods, therefore, no relevancy will be determined between the keyword and the translation of the keyword due to the gap. Thus the prior art method of translating documents does not work well for terms that are not well established in the lexicon and do not have counterparts in the translational dictionaries. The present invention, however, overcomes this limitation by including translational dictionaries along with texts from the various languages in the training set. When the calibrated expected search distances are calculated, the sense of relevancy will be drawn from words in the searcher's language to the words in other languages. So long as the search word occurs in the training set, even if the translational dictionaries are incomplete, the document relevancy measures will account for these foreign language terms. Thus, utilizing the present invention, a searcher may use a keyword in the searcher's own language to identify relevant documents from other languages without requiring translation of the documents.

The present invention also provides for easy clustering of documents even in the event the keyword is not present in the document. For example, a number of documents could be measured for relevancy relative to keywords such as physics, biology, or chemistry. In addition, the documents could be measured for relevancy relative to the keyword politics. These measures of relevancy can then be combined to determine a cluster of documents relative to physics and politics, for example. Clustering of these documents relative to the keywords “physics” and “politics” is possible even when the documents do not include either or both keywords.

The present invention provides a relatively simply way of determining relevance without requiring significant involvement by an expert to create the relevance model. For example, prior art methods of ranking utilize algorithms which attempt to take advantage of the nuanced details of a document in order to rank the relevancy of that document. One method in particular utilizes the order of the words in the document may in an attempt to determine the meaning conveyed by the words. These methods seek to take advantage of the complexity of a language but require significant involvement by an expert to create the relevancy model. Utilizing the present invention, documents are treated as an unordered set of words for ranking purposes. Expert input concerning language structure is not needed and the process may be fully automated. The method of ranking documents provided by the present invention is based on a calculated expected search distance and reasonably mimics the ranking a person might perform without requiring involvement by an expert to model the complexity of the language and without requiring nuanced details regarding the document in the live or the training set, or human intervention.

While preferred embodiments of the present invention are shown and described, it is envisioned that those skilled in the art may devise various modifications of the present invention without departing from the spirit and scope of the appended claims.