Apparatus, system and method for application-specific and customizable semantic similarity measurement

• US 9,672,206 B2
• Filed: 06/01/2015
• Issued: 06/06/2017
• Est. Priority Date: 06/01/2015
• Status: Active Grant

• Current Assignee: Information Extraction Systems, Inc.
• Original Assignee: Information Extraction Systems, Inc.
• Inventors: Carus, Alwin B, DePlonty, Thomas J.
• Primary Examiner(s): SINGH, SATWANT K
• Application Number:
  US14/727,451
• Publication Number:
  US 20160350283A1
• Time in Patent Office: 736 Days
• Field of Search: None
• CPC Class Codes: G06F 16/36 Creation of semantic tools, e.g. ontology or thesauri
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

The present invention relates to an apparatus system and method for creating a customizable and application-specific semantic similarity utility that uses a single similarity measuring algorithm with data from broad-coverage structured lexical knowledge bases (dictionaries and thesauri) and corpora (document collections). More specifically the invention includes the use of data from custom or application-specific structured lexical knowledge bases and corpora and semantic mappings from variant expressions to their canonical forms. The invention uses a combination of technologies to simplify the development of a generic semantic similarity utility; and minimize the effort and complexity of customizing the generic utility for a domain- or topic-dependent application. The invention makes customization modular and data-driven, allowing developers to create implementations at varying degrees of customization (e.g., generic, domain-level, company-level, application-level) and also as changes occur over time (e.g., when product and service mixes change).

Claims

1. A method for application-specific and customizable text similarity measurement, the method comprising the steps of:

determining, by a computer, a string similarity score of at least two texts based upon a string similarity database stored on said computer, said at least two texts comprising at least one input text and at least one target text;

determining, by said computer, a semantic similarity score of the at least two texts based upon a semantic similarity database stored on said computer, the semantic similarity score being determined as the sum of a distance between at least one term of each said at least two texts;

mapping, by said computer, said at least one target text and its respective canonical representations in a mappings database stored on said computer;

combining, by said computer, the string similarity score and the semantic similarity score of the at least two texts where the combined score is a weighted sum of the string similarity score and the semantic similarity score and where said at least two texts are ranked for similarity by sorting by their respective combined string and semantic similarity scores and where said texts that are included in the mappings database are also scored by similarity of their canonical forms; and

producing, by the computer, an output signal defining a list of best-scoring semantic mappings with associated scores, said computer adapted to transform said output signal into a display signal viewable on a monitor.

2. The method according to claim 1, further comprising the step of determining string similarity as the weighted substring similarity of the at least two texts.

3. The method according to claim 2, further comprising the step determining a plurality of sizes of substring.

4. The method according to claim 3, further comprising the step of determining substring weighting with tf-idf.

5. The method according to claim 4, further comprising the step of determining substring similarity with cosine distance.

6. The method according to claim 1, further comprising the step of determining a semantic similarity score of the at least two texts as the sum of a semantic distance between at least two terms of the at least two texts.

7. The method according to claim 6, further comprising the step of selecting a structured lexical knowledge base that contains definitions.

8. The method according to claim 7, further comprising the step of re-representing said structured lexical knowledge base in a computationally tractable form.

9. The method according to claim 8, where the structured lexical knowledge base comprises object-attribute-value (OAV) triplets that relate terms (objects) to properties (values) by relations (attributes).

10. The method according to claim 9 further comprising the step of constructing a first gloss corpus consisting of the definitions for each said term in the lexical knowledge base.

11. The method according to claim 10 further comprising the constructing a second gloss corpus including at least one expanded definition for each said term in said structured lexical knowledge base by adding to each of respective definition of said terms found in a specified set of semantic relationships to each respective term.

12. The method according to claim 11 further comprising the step of extracting said semantic relationships from the set of OA V triplets.

13. The method according to claim 12, where said semantic relations between the said terms used to construct the second gloss corpus include terms related by synonymy;

hypernymy and hyponymy; and

morphological derivation.

14. The method according to claim 1, where the string similarity data comprises a database of substrings of texts and statistics that relate said substrings to variant forms of each canonical form, and where said substrings are character ngrams of the target texts, respectively.

15. The method according to claim 14, where there are a plurality of sizes of character ngrams.

16. The method according to claim 15, where the character ngrams have tf-idf weights.

17. The method according to claim 16, further comprising the step of correlating each character ngram to each of the target texts in which it is respectively found.

18. The model according to claim 14, further comprising the step of creating a sample set of documents from a preferred set of collected documents.

19. The method according to claim 18, further comprising the step of converting the sample set of documents to a standardized format.

20. The method according to claim 19, further comprising the step of removing text markup from the converted sample set of documents.

21. The method according to claim 20, further comprising the step of converting characters to a uniform character set.

22. The method according to claim 21 where the sample set of documents is segmented into sections.

23. The method according to claim 22 where the sample set of documents is tokenized where said tokens are single or multiple word tokens.

24. The method according to claim 23 where the tokens are transformed by stemming or baseforming.

25. The method according to claim 24 where the tokens are transformed by capitalization folding.

26. The method according to claim 25 where specified tokens are ignored.

27. The method according to claim 26 where tokens are decorated with additional data.

28. The method according to claim 27 where said additional data is selected from the group consisting of part-of-speech, syntactic, named-entity and semantic labels.

29. The method according to claim 28 where multiword-tokens are identified as a sequence of two or more tokens with high mutual information.

30. The method according to claim 29 where the multiword-tokens are found in a predefined list of multi word tokens.

31. The method according to claim 30 further comprising the step of determining co-occurrence statistics to create a base model of term co-occurrence statistics from the tokenized text based on a configuration.

32. The method according to claim 31 where the number of terms to the left and right of a given focus term to use for term co-occurrence counts.

33. The method according to claim 32 where the semantic similarity data module uses a semantic indexing vector space model of term co-occurrence.

34. The method according to claim 33, further comprising the step of creating a first vector space model based upon the structured lexical knowledge base and the first gloss corpus.

35. The method according to claim 34, where the first vector space model is also based upon the second gloss corpus.

36. The method according to claim 35, where the first vector space model is a “

first-order”

vector space model of term co-occurrences from at least one of a broad-coverage structured lexical knowledge base or a domain- or application-specific lexical knowledge base that contains glosses of said terms.

37. The method according to claim 36, further comprising the step of creating a second vector space model of term co-occurrences for each term defined in the lexical knowledge base by summing co-occurrence vectors of each term found in the expanded gloss corpus for the given term.

38. The method according to claim 37, further comprising the step of removing low frequency co-occurrences.

39. The method according to claim 38, further comprising the step of removing low variance co-occurrences.

40. The method according to claim 39, further comprising the step of creating a third vector space model based upon the sample set of documents, said third vector space model being a “

first-order”

vector space model.

41. The method according to claim 40, further comprising the step of creating a fourth vector space model.

42. The method according to claim 41, where said fourth vector space model includes a combination of one or more vector space models drawn from a pool of lexical knowledge base and document collection vector space models.

43. The method according to claim 42 where the step of creating the fourth vector space model is a weighted sum of at least one of the second and third vector space models.

44. The method according to claim 43 where semantic distance is determined using the fourth vector space model of weighted term co-occurrence statistics.

45. The method according to claim 44, where the fourth vector space model uses random indexing.

46. The method according to claim 45, where said weighted term co-occurrence statistics includes pointwise mutual information.

47. The method according to claim 46, where the semantic distance includes a measure of correlation cosine distance.

48. The method according to claim 47, further comprising the step of combining vector distances using a best alignment strategy whereby said terms in the at least two texts are allowed by contributing their respective distances only once and only with their respective highest matching scores.

49. The method according to claim 48, where the at least two texts are ranked for similarity by sorting by their respective combined string and semantic similarity scores.

50. The method according to claim 49, where a score of canonical forms is determined by a k nearest neighbor score.

51. The method according to claim 50, where the score of canonical forms is determined as the sum of the scores of the k closest matching variant strings of canonical forms and further where k is a fixed number.

52. The method according to claim 51, where the canonical form is the normalized form of the target text.

53. The method according to claim 52, where metadata and categories are associated with canonical forms.

54. The method according to claim 53 where metadata includes the frequency of occurrence of each combination of metadata and categories.

55. The method according to claim 1, where the mappings database storing the at least one text and its respective canonical representation comprises semantic mappings between said text and its respective normative forms.

56. The method according to claim 55 where the string similarity databases comprises substrings of texts and statistics that relate said substrings to variant forms.

57. A data processing system, comprising a processor, a memory coupled to the processor, and a non-transitory computer readable storage device coupled to the processor, said storage device containing program code executable by the processor via the memory to implement a method for application-specific and customizable text similarity measurement, the processing system comprising:

first logic executable by the processor for determining a string similarity score of at least two texts based upon a string similarity database, said at least two texts comprises at least one input text and at least one target text;

second logic executable by the processor for determining a semantic similarity score of the at least two texts based upon a semantic similarity database, the semantic similarity score being determined as the sum of a distance between at least one term of each said at least two texts;

third logic executable by the processor for mapping said at least one target text and its respective canonical representations in a mappings database stored in said memory;

fourth logic executable by the processor for combining the string similarity score and the semantic similarity score of the at least two texts where the combined score is a weighted sum of the string similarity score and the semantic similarity score and where said at least two texts are ranked for similarity by sorting by their respective combined string and semantic similarity scores and where said texts that are included in the mappings database are also scored by similarity of their canonical forms; and

an output signal defining a list of best-scoring semantic mappings with associated scores, said program code executable to transform said output signal into a display signal viewable on a monitor.

58. A system, comprising a processor, a memory coupled to the processor, and a non-transitory computer readable storage device coupled to the processor, said storage device containing program code executable by the processor via the memory to implement a method useful for application-specific and customizable text similarity measurement, the system comprising:

a first computer store containing at least two texts defining string similarity of each of said texts, said at least two texts comprising at least one input text and at least one target text, where said defined string similarity is stored as a string similarity score in said first computer store;

a second computer store interconnected to the first computer store and housing a semantic similarity score of the at least two texts based the first computer store, where the semantic similarity score is determined as the sum of a distance between at least one term of each said at least two texts;

a third computer store interconnected to the first and second computers stores where said at least one target text and its respective canonical representations are mapped and housed in said third computer store; and

an output signal defining a list of best-scoring semantic mappings with associated scores, said program code executable to transform said output signal into a display signal viewable on a monitor,

wherein the string similarity score and the semantic similarity score of the at least two texts where the combined score is a weighted sum of the string similarity score and the semantic similarity score and where said at least two texts are ranked for similarity by sorting by their respective combined string and semantic similarity scores and where said texts that are included in the mappings database are also scored by similarity of their canonical forms.