Method and apparatus for identifying semantic structures from text

• US 20050075859A1
• Filed: 10/06/2003
• Published: 04/07/2005
• Est. Priority Date: 10/06/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ramsey, William D.
• Granted Patent: US 7,593,845 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method and apparatus for identifying a semantic structure from an input text forms at least two candidate semantic structures. A semantic score is determined for each candidate semantic structure based on the likelihood of the semantic structure. A syntactic score is also determined for each semantic structure based on the position of a word in the text and the position in the semantic structure of a semantic entity formed from the word. The syntactic score and the semantic score are combined to select a semantic structure for at least a portion of the text. In many embodiments, the semantic structure is built incrementally by building and scoring candidate structures for a portion of the text, pruning low scoring candidates, and adding additional semantic elements to the retained candidates.

Claims

1. A method of identifying a semantic structure from a text, the method comprising:

identifying semantic entities from the text;

combining semantic entities to form at least two candidate semantic structures;

generating a semantic score for each candidate semantic structure based on the likelihood of the semantic structures;

generating a syntactic score for each candidate semantic structure based in part on the position of a word in the text and the position in the semantic structure of a semantic entity formed from the word; and

combining the syntactic score and the semantic score for each semantic structure to select one of the candidate semantic structures for at least a portion of the text.

2. The method of claim 1 wherein generating a syntactic score comprises for each parent-child relationship between semantic entities in a candidate semantic structure, identifying a token position of a word associated with a parent semantic entity and identifying a token position of a word associated with a child semantic entity and determining a probability based on the token positions.

3. The method of claim 1 further comprising generating a transition score based on the order in which semantic entities identified from the text are aligned with the text.

4. The method of claim 3 wherein generating a transition score comprises generating a separate transition probability for each pair of semantic entities that appear on a same level in a candidate semantic structure.

5. The method of claim 1 wherein using semantic entities to form a candidate semantic structure comprises including semantic entities in the candidate semantic structure that are not identified from the text.

6. The method of claim 5 wherein generating a semantic score comprises using a penalty factor to discount a probability of a semantic entity if the semantic entity was not identified from the text.

7. The method of claim 1 wherein identifying semantic entities comprises using a schema in which text is associated with semantic entities.

8. The method of claim 7 wherein a single word is associated with multiple semantic entities in the schema.

9. The method of claim 7 wherein using semantic entities to form a semantic structure comprises basing the semantic structure on relationships between semantic entities that are defined in a schema.

10. The method of claim 9 wherein the schema that defines the relationships between semantic entities and the schema that associates text with semantic entities is the same schema.

11. The method of claim 9 wherein basing the semantic structure on relationships that are defined in a schema comprises:

constructing a table with an entry that is indexed by two semantic entities and that contains a set of semantic structures found in the schema, each semantic structure containing the two semantic entities used to index the entry;

searching the table using the two semantic entities to locate the set of semantic structures; and

forming a semantic structure for each semantic structure in the set of semantic structures.

12. The method of claim 1 further comprising combining a selected semantic structure with a further semantic entity identified from the text to form an expanded semantic structure.

13. The method of claim 12 further comprising generating a semantic score and a syntactic score for the expanded semantic structure.

14. The method of claim 12 wherein combining a selected semantic structure with a further semantic entity comprises performing an ordered search comprising:

determining if the further semantic entity can be placed beneath any of the entities in the selected semantic structure;

determining if a head of the selected semantic structure can be placed beneath the further semantic entity; and

determining if there is a common ancestor entity that both the further semantic entity and the head of the selected semantic structure can be placed beneath.

15. The method of claim 1 further comprising:

determining that a selected semantic structure is not a command semantic structure;

placing the selected semantic structure in a command semantic structure; and

identifying the command semantic structure as the semantic structure of the text.

16. The method of claim 15 further comprising placing the selected semantic structure in multiple command semantic structures.

17. The method of claim 16 further comprising scoring each command semantic structure and selecting a highest scoring command semantic structure as the semantic structure of the text.

18. The method of claim 1 further comprising pruning a candidate semantic structure from further consideration based on the syntactic score and the semantic score for the semantic structure.

19. A computer-readable medium having computer-executable instructions for performing steps comprising:

identifying semantic entities from a text;

forming a set of partial semantic structures from the semantic entities;

scoring each of the partial semantic structures to provide a score for each partial semantic structure;

pruning at least one partial semantic structure and retaining at least one partial semantic structure based on the scores for the partial semantic structures; and

forming a full semantic structure from a retained partial semantic structure.

20. The computer-readable medium of claim 19 wherein identifying semantic entities comprises utilizing a schema in which semantic entities are associated with text.

21. The computer-readable medium of claim 19 wherein forming a set of partial semantic structures comprises:

accessing a table to find an entry indexed by two semantic entities identified from the text, the entry providing a plurality of semantic structures that include both of the two semantic entities; and

forming a partial semantic structure for each of the semantic structures provided by the entry.

22. The computer-readable medium of claim 21 further comprising building the table from a schema that describes relationships between semantic entities.

23. The computer-readable medium of claim 21 wherein at least one partial semantic structure comprises a semantic entity that is not identified from the text.

24. The computer-readable medium of claim 23 wherein scoring a partial semantic structure comprises calculating a score for each entity in the partial semantic structure, wherein the score for an entity is reduced if the entity was not identified from the text.

25. The computer-readable medium of claim 19 wherein forming a full semantic structure comprises combining a partial semantic structure with a semantic entity identified from the text.

26. The computer-readable medium of claim 25 wherein forming a full semantic structure comprises:

determining if the semantic entity can be placed beneath any of the entities in the partial semantic structure;

determining if a head of the partial semantic structure can be placed beneath the semantic entity; and

determining if a head of the partial semantic structure and the semantic entity can both be placed beneath a common ancestor entity.

27. The computer-readable medium of claim 19 further comprising determining that the full semantic structure is not a command semantic structure and placing the full semantic structure in a command semantic structure.

28. The computer-readable medium of claim 27 further comprising placing the full semantic structure in multiple command semantic structures, scoring each command semantic structure, and selecting one of the command semantic structures based on the scores.

29. The computer-readable medium of claim 19 wherein scoring a partial semantic structure comprises determining a semantic score based on the semantic entities in the partial semantic structure and the relationships between the semantic entities in the partial semantic structure.

30. The computer-readable medium of claim 29 wherein scoring a partial semantic structure further comprises determining a syntactic score based on positions of words in the text associated with the semantic entities.

31. The computer-readable medium of claim 30 wherein scoring a partial semantic structure further comprises determining a transition score based on the order of semantic entities, wherein the order is set by the alignment of the semantic entities to the text that is associated with the semantic entities.