Method and System for Determining Word Senses by Latent Semantic Distance

• US 20130197900A1
• Filed: 05/09/2011
• Published: 08/01/2013
• Est. Priority Date: 06/29/2010
• Status: Abandoned Application

• Current Assignee: SpringSense Pty., Ltd.
• Original Assignee: SpringSense Pty., Ltd.
• Inventors: Rotbart, Frederick Charles, Rotbart, Tal
• Application Number:
  US13/701,897
• Publication Number:
  US 20130197900A1
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30

Abstract

The invention relates to methods and systems for semantic disambiguation of a plurality of words. A representative method comprises providing a dataset of words associated by meaning into sets of synonyms; locating said sets at respective vertices of a graph according to semantic similarity and semantic relationship; transforming the graph into a Euclidean vector space comprising vectors indicative of respective locations of said sets; identifying a first group of said sets which include a first of said pair of words; identifying a second group of said sets which include a second of said pair of words; determining a closest pair in said vector space of said sets taken from said first and second groups of sets respectively; and outputting a meaning, of said plurality of words based on said closest pair of said sets and at least one of said semantic relationships between said closest pair of said sets.

Claims

1-34. -34. (canceled)

35. A computer implemented method of semantic disambiguation of a plurality of words, the method comprising:

providing a dataset of words associated by meaning into sets of synonyms;

locating said sets at respective vertices of a graph, at least some pairs of said sets being spaced according to semantic similarity and categorised according to semantic relationship;

transforming the graph into a Euclidean vector space comprising vectors indicative of respective locations of said sets in said vector space;

identifying a first group of said sets comprising those of said sets that include a first of said pair of words;

identifying a second group of said sets comprising those of said sets that include a second of said pair of words;

determining a closest pair in said vector space of said sets taken from said first and second groups of sets respectively; and

outputting a meaning of said plurality of words based on said closest pair of said sets and at least one of said semantic relationships between said closest pair of said sets.

36. The method of claim 35, wherein the dataset of words may be sourced from a lexical database.

37. The method of claim 35, further comprising categorising at least some pairs of said sets according to one or more semantic relationships using a semantic similarity measure.

38. The method of claim 37, wherein the one or more categories of semantic relationships comprise a “

is-a”

relationship, a “

is-part-of”

relationship or a “

is-semantically-similar-to”

relationship.

39. The method of claim 35, wherein the dataset of words may comprise single seed words and pairs of seed words.

40. The method of claim 35, wherein locating said sets at respective vertices of a graph comprises one or more of:

for each seed word that corresponds to an entry in a set, progressively locating said set as a vertex (V_s) to said graph;

for each seed word that corresponds to a term, determining if a set is deriveable for said term and locating said derived set as a vertex of said graph; and

for each pair of seed words;

determining if the sets of said pair have a semantic overlap;

linking a pair of sets determined to have a semantic overlap; and

determining a weight to be assigned to the linked pair of sets.

47. The method of claim 40, wherein linking said pair of sets determined to have a semantic overlap is dependent on the calculated weight.

65. Computer-readable storage storing computer program code executable to cause a computer system or computing device to perform the method of claim 35.

41. The method of 40, wherein progressively locating said set as a vertex to the graph further comprises:

determining a hypernym of said seed word;

locating said hypernym as a vertex V_h to the graph; and

linking vertices V_h and V_s and assigning a weight to said link.

42. The method of claim 41, wherein the weight assigned to the pair of vertices V_h and V_s is a constant weight.

43. The method of claim 41, wherein the weight to be assigned to said linked pair of sets is a constant.

44. The method of claim 41, wherein, for a seed word having a plurality of hypernyms, the respective vertices V_h are linked to vertex V_s by the same weight.

45. The method of claim 41, wherein assigning a weight to said linked pair comprises calculating a similarity measure for said pair of sets.

46. The method of claim 45, wherein the similarity measure is one of a Modified Lesk and a similarity measure based on annotated glosses overlap.

48. A computer implemented method of determining a latent distance between a pair of vertices of a graph, the method comprising:

providing a dataset comprising data points, wherein each of said data points is associated with at least one other of said data points, and a degree of association between respective pairs of said data points is represented by a weighted measure;

locating said data points at respective vertices of a graph with said respective pairs of said data points spaced according said weighted measures;

transforming the graph into a Euclidean vector space comprising vectors to create said vector space; and

using said vector space to determine said latent distance between said pair of vertices, said latent distance being a distance between said pair of vertices in said vector space.

49. The method of claim 48, wherein the transforming comprises deriving eigenvectors and eigenvalues.

50. The method of claim 48, wherein the transforming comprises taking the pseudo-inverse of the graph.

51. The method of claim 48, further comprising applying a degree of association between respective pairs of said data points, wherein said degree of association between respective pairs of said data points is dependent on the type of dataset utilised.

52. The method of claim 48, wherein transforming the graph into a Euclidean vector space comprises deriving an un-normalised Graph Laplacian matrix.

53. The method of claim 48, wherein semantic relationships between any pair of said data points are categorised according to one or more categories of semantic relationship, including a “

is-a”

relationship, a “

is-part-of”

relationship or a “

is-semantically-similar-to”

relationship.

54. The method of claim 48, further comprising reducing the dimensionality of the Euclidean space such that the resulting Euclidean vector semantic space is of dimension n×

k where n is the number of vertices, k<

<

n is the reduced dimension and k is sufficiently large such that the Euclidean distances are preserved to within a determined error.

55. A computer implemented method of forming a graph structure, the computer implemented method comprising:

at a server, providing a dataset comprising data points, said data points representing seed words and seed pairs, wherein each of said data points is associated with at least one other of said data points using hypernym and hyponym relations from contents of an electronic lexical database, and wherein a degree of association between respective pairs of said data points is represented by a weighted measure; and

locating said data points at respective vertices of a graph with said respective pairs of said data points spaced according to said weighted measures.

56. The method of claim 55, further comprising determining those seed words that comprise a synset and for said seed words, adding respective synsets as data points to the graph.

57. The method of claim 55, further comprising, for each seed word, recursively adding hypernyms of said seed word as data points, where said seed word is associated with each respective hypernym and represented by the same weighted measure.

58. The method of claim 55, further comprising determining those seed words that comprise a term, and for said seed words, deriving synsets for respective terms and adding said derived synsets as data points.

59. The method of claim 55, further comprising for a pair of associated data points, calculating the weighted value using a semantic similarity measure.

60. The method of claim 55, further comprising adjusting the weighted measure of hyponyms according to the number of hyponyms of a particular data point.

61. The method of claim 55, further comprising limiting the number of weighted measures to a particular data point such that the number of weighted measures does not exceed a preset maximum.

62. The method of claim 55, further comprising compacting said graph by recursively removing hypernyms that have only one hyponym and linking said hyponym to a hypernym of the removed hypernym.

63. A method to enable disambiguation of word senses, the method comprising:

accessing an electronic lexical database;

sourcing data points representing seed words and seed pairs;

using the electronic lexical database and the data points to generate a graph, wherein the data points are located at respective vertices of the graph, with respective ones of pairs of data points being spaced in the graph according to a weighted measure of a degree of association between the ones of pairs of data points;

generating a vector space based on the graph, wherein a distance between a pair of vertices in the vector space corresponds to a latent distance between the pair of vertices in the graph, and wherein the distance is usable for disambiguation of word senses.

64. The method of claim 63, further comprising receiving disambiguation input comprising a word pair or a sentence as input and using the vector space to generate disambiguation output regarding the word pair or the sentence.

66. A system to enable disambiguation of word senses, the system comprising:

at least one processor; and

memory accessible to the at least one processor and storing program code executable to implement a vector space generator, the vector space generator having access to an electronic lexical database and receiving data points representing seed words and seed pairs, the vector space generator configured to;

generate a graph by locating the data points at respective vertices of a graph, with respective ones of pairs of data points being spaced in the graph according to a weighted measure of a degree of association between the ones of pairs of data points, and generate a vector space based on the graph;

wherein the vector space is usable to determine a latent distance between a pair of vertices in the graph by determining a distance between the pair of vertices in the vector space and the latent distance is usable for disambiguation of word senses.

67. The system of claim 66, further comprising a disambiguation engine that has access to the vector space, the disambiguation engine being configured to provide disambiguation output in response to input of at least one of a word pair and a sentence