Method and apparatus for building semantic structures using self-describing fragments

• US 20060047502A1
• Filed: 09/02/2004
• Published: 03/02/2006
• Est. Priority Date: 09/02/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ramsey, William D., Barklund, Par Jonas
• Granted Patent: US 7,593,846 B2
• Time in Patent Office: Days
• US Class Current: 704/10
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

A method and apparatus for identifying a semantic structure from text includes processing the input text to identify self-describing fragments of the input text based on a hierarchical schema defining a domain with at least one top-level node and child nodes. Each identified self-describing fragment includes hierarchical context of a portion of the input text. A semantic structure is provided based on the identified self-describing fragments.

Claims

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

receiving input text;

processing the input text to identify self-describing fragments of the input text based on a hierarchical schema defining a domain with at least one top-level node and child nodes, wherein each identified self-describing fragment includes hierarchical context of a portion of the input text; and

providing a semantic structure based on the identified self-describing fragments.

2. The method of claim 1 wherein processing includes combining the identified self-describing fragments and wherein providing a semantic structure is based on combined self-describing fragments.

3. The method of claim 2 wherein combining includes only combining those identified self-describing fragments that have a common top-level node.

4. The method of claim 3 wherein combining includes only combining those identified self-describing fragments that have corresponding portion of the input text that do not overlap.

5. The method of claim 4 wherein combining includes only combining those identified self-describing fragments that are unique from each other.

6. The method of claim 1 wherein providing a semantic structure comprises providing a set of semantic structures.

7. The method of claim 6 wherein providing the set of semantic structures comprises ranking the semantic structures relative to each other.

8. The method of claim 7 wherein ranking is based on the extent of the input text present in each semantic structure.

9. The method of claim 8 wherein the ranking is based on the hierarchical structure in each semantic structure.

10. The method of claim 7 wherein the ranking is based on the hierarchical structure in each semantic structure.

11. The method of claim 10 wherein the ranking is based on a comparison of the hierarchical structure in each semantic structure with statistical analysis of training data of the same.

12. The method of claim 7 wherein the schema includes encoded text of the domain contemplated to be in the input text, and wherein each node has associated encoded text therewith, and wherein processing includes analyzing the input text to identify portions having the encoded text, the encoded text be used to identify a node for the hierarchal context of the self-describing fragment.

13. The method of claim 12 wherein the ranking is based on the semantic structures acknowledging that the input text included encoded text corresponding to a top-level node.

14. The method of claim 12 wherein the ranking is based on how many nodes in the semantic structures acknowledge that the input text included corresponding encoded text for the nodes present in the semantic structures.

15. The method of claim 12 wherein the ranking is based on how close are the nodes in the hierarchical structure for the semantic structures that acknowledge that the input text included corresponding encoded text to the corresponding top-level node.

16. The method of claim 7 wherein the ranking is based on comparison of the input text with statistical analysis of training data text.

17. The method of claim 7 wherein the ranking is based on feedback from the user.

18. The method of claim 1 wherein the schema includes encoded text of the domain contemplated to be in the input text, and wherein each node has associated encoded text therewith, and wherein processing includes analyzing the input text to identify portions having the encoded text, the encoded text being used to identify a node for the hierarchal context of the self-describing fragment.

19. The method of claim 18 wherein processing includes concatenating together identifiers of nodes to provide the hierarchical context of each self-describing fragment.

20. The method of claim 18 herein the schema includes the encoded text directly therein and wherein processing comprises processing the schema to obtain the encoded text.

21. The method of claim 18 wherein schema includes a reference to a library to provide the encoded text, and wherein processing comprises accessing the library and analyzing the input text with respect to the library.

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

receiving input text;

tokenizing the input text into portions of text;

processing each portion of the text, wherein processing includes forming a self-describing fragment for each portion, the self-describing fragment being based on a hierarchical schema defining a domain with at least one top-level node and child nodes, wherein each self-describing fragment includes one or more indications of the nodes to form a hierarchical context with respect to the domain for each corresponding portion; and

combining one or more self-describing fragments to form one or more semantic structures.

23. The computer-readable medium of claim 22 wherein combining includes only combining the self-describing fragments that have a common top-level node.

24. The computer-readable medium of claim 23 wherein combining includes only combining the self-describing fragments that have corresponding portions of the input text that do not overlap.

25. The computer-readable medium of claim 24 wherein combining includes only combining the self-describing fragments that are unique from each other.

26. The computer-readable medium of claim 22 and further comprising ranking the semantic structures relative to each other.

27. The computer-readable medium of claim 26 wherein ranking is based on the number or portions of the input text present in each semantic structure.

28. The computer-readable medium of claim 27 wherein the ranking is based on the hierarchical structure.

29. The computer-readable medium of claim 28 wherein the ranking is based on the number of nodes of the hierarchical structure in each semantic structure.

30. The computer-readable medium of claim 29 wherein the ranking is based on an extent of depth of the hierarchical structure in each semantic structure.

31. The computer-readable medium of claim 28 wherein the ranking is based on an extent of depth of the hierarchical structure in each semantic structure.

32. The computer-readable medium of claim 26 wherein the schema includes encoded text of the domain contemplated to be in the input text, and wherein each node has associated encoded text therewith, and wherein processing includes analyzing the input text to identify portions having the encoded text, the encoded text be used to identify a node for the hierarchal context of the self-describing fragment, and wherein the ranking is based on the semantic structures acknowledging that the input text included encoded text corresponding to nodes.

33. The computer-readable medium of claim 22 wherein the schema includes encoded text of the domain contemplated to be in the input text, and wherein each node has associated encoded text therewith, and wherein processing includes analyzing each portion to identify if the portion comprises the encoded text, the encoded text being used to identify a node for the hierarchal context of the self-describing fragment.

34. The computer-readable medium of claim 33 wherein the schema includes the encoded text directly therein and wherein processing comprises processing the schema to obtain the encoded text.

35. The computer-readable medium of claim 34 wherein the schema includes a reference to a library to provide the encoded text, and wherein processing comprises accessing the library and analyzing the input text with respect to the library.

36. The computer-readable medium of claim 33 wherein processing includes concatenating together identifiers of nodes to provide the hierarchical context of each self-describing fragment.

37. A computer system for processing queries from a user, the system comprising:

at least one application for performing a task;

a schema defining a domain of contemplated text to be in the queries, the schema comprising a hierarchical structure with at least one top-level node and child nodes;

a semantic engine adapted to receive the queries and form at least one semantic structure that is provided to the application, the semantic engine adapted to tokenize each query into portions of text and process each portion of the text, wherein processing includes forming a self-describing fragment for each portion, wherein each self-describing fragment includes one or more indications of the nodes to form a hierarchical context with respect to the domain for each corresponding portion, and wherein the semantic engine is adapted to combine one or more self-describing fragments to form one or more semantic structures.

38. The system of claim 37 wherein the schema includes encoded text of the domain contemplated to be in the input text, and wherein each node has associated encoded text therewith, and wherein processing includes analyzing each portion to identify if the portion comprises the encoded text, the encoded text being used to identify a node for the hierarchal context of the self-describing fragment.

39. The system of claim 38 wherein the schema includes the encoded text directly therein and wherein processing comprises processing the schema to obtain the encoded text.

40. The system of claim 39 wherein the schema includes a reference to a library to provide the encoded text, and wherein processing comprises accessing the library and analyzing the input text with respect to the library.