Predicting whether strings identify a same subject
AssigneeMicrosoft Corporation
InventorCAROLYN P. JOHNSTON
Life of this patent
Estimating the term…
Abstract
The present invention is directed to predicting whether two character strings refer to a same subject. An exemplary embodiment includes using a set of character-string pairs, which have been identified as either matches or nonmatches, to learn a function. The function can then be applied to the two character strings to quantify a likelihood that they refer to the same subject matter. For example, a kernel-based classifier analyzes the set of character-string pairs using a kernel function. Based on the analysis the classifier can generate parameters. The parameters are usable to define a prediction algorithm that when applied to the two character strings generates a prediction value, which suggests whether the two characters are matches, i.e., refer to the same subject matter.
Claims20
Computer-readable media having computer-executable instructions embodied thereon that, when executed, cause a computing device to perform a method of predicting whether character strings refer to a same subject matter, the method comprising:
- identifying in a database a first character string and a second character string that are included in a set of text documents;
- utilizing the computing device to generate a prediction value, which quantifies likelihood that the first character string and the second character string refer to the same subject matter, by applying a prediction algorithm to each of the first character string and the second character string,
- (1) wherein the prediction algorithm is determined based on an analysis of a training set of data, which includes a plurality of character strings that are included in the set of text documents and that are combinable into character-string pairs,
- (2) wherein the analysis of the training set of data includes generating from a mapping of the character-string pairs parameters that are usable to define the prediction algorithm, and
- (3) wherein the mapping is based on a first kernel function that combines a measure of similarity of a character-string pair with a measure of document frequency of strings of the character-string pair, and
- based on the prediction value, associating in the database the first character string with the second character string.
A computer-implemented method of predicting whether character strings refer to a same subject matter, the method comprising:
- referencing in a database a first character string and a second character string that are included in a set of text documents;
- utilizing a processor to apply a prediction algorithm to each of the first character string and the second character string, the prediction algorithm being usable to quantify a likelihood that the first character string and the second character string refer to the same subject matter,
- (1) wherein the prediction algorithm is learned by a support vector machine based on an inner product that is determined using a mapping of a training set of data, and
- (2) wherein the mapping is based on a first kernel function that combines a measure of similarity of a character-string pair with inverse document-frequency values of strings of the character-string pair;
- and
- based on a prediction value, which is generated by applying the prediction algorithm to each of the first string of characters and the second string of characters, associating in the database the first character string with the second character string.
Computer-readable media having computer-executable instructions embodied thereon that, when executed, cause a computing device to perform a method of predicting whether character strings refer to a same subject matter, the method comprising:
- referencing in a database a plurality of character strings that are combinable into pairs of character strings and that are included in a set of text documents;
- determining an inverse document-frequency value of each character string, wherein each inverse document-frequency value describes an inverse measure of a number of occurrences of a respective character string in the set of text documents;
- using the computing device to conduct an analysis of the plurality of character strings with a kernel-based classifier, which applies to the plurality of character strings a first kernel function,
- (1) wherein the first kernel function combines a measure of similarity between a pair of character strings and inverse document-frequency values of each string included in the pair of character strings, and
- (2) wherein based on the analysis, the kernel-based classifier determines a prediction algorithm, which is usable to determine whether two character strings include a similar set of characters;
- and
- using the computing device to calculate a prediction value, which quantifies a likelihood that the first character string and the second character string refer to the same subject matter, by applying the prediction algorithm to the two character strings.
Dependencies are inferred from the claim text.