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

• US 7,593,846 B2
• Filed: 09/02/2004
• Issued: 09/22/2009
• Est. Priority Date: 09/02/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Barklund, Par Jonas, Ramsey, William D.
• Primary Examiner(s): Hudspeth; David R
• Assistant Examiner(s): Rider; Justin W
• Application Number:
  US10/933,046
• Publication Number:
  US 20060047502A1
• Time in Patent Office: 1,846 Days
• Field of Search: 704/10
• 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 providing semantic information related to the meaning of input text, the method comprising with a processor:

receiving input text;

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

providing semantic information related to the meaning of at least some portion of the input text 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 semantic information related to the meaning of at least some portion of the input textis 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 semantic information related to the meaning of at least some portion of the input text based on the identified self-describing fragments comprises providing a set of semantic solutions, each solution being a potential meaning of at least a portion of the input text.

7. The method of claim 6 wherein providing the set of semantic solutions comprises ranking the semantic solutions 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 solution.

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

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

11. The method of claim 10 wherein the ranking is based on a comparison of the hierarchical structure in each semantic solution 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 solutions 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 solutions acknowledge that the input text included corresponding encoded text for the nodes present in the semantic solutions.

15. The method of claim 12 wherein the ranking is based on how close are the nodes in the hierarchical structure for the semantic solutions 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 wherein 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 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.

22. A computer-readable storage medium having computer-executable instructions, which when executed by a processor comprises:

receiving input text;

tokenizing the input text into portions of text;

processing each portion of the text to provide indications of the meaning of at least some portion of the input 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 positional information of words forming the corresponding portion in the input text; and

combining one or more self-describing fragments to form one or more semantic solutions, each semantic solution being a potential meaning of at least a portion of the input text.

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

24. The computer-readable storage 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 storage medium of claim 24 wherein combining includes only combining the self-describing fragments that are unique from each other.

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

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

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

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

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

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

32. The computer-readable storage 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 solutions acknowledging that the input text included encoded text corresponding to nodes.

33. The computer-readable storage 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 storage 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 storage 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 storage 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:

a processor;

computer readable storage media having instructions operable on the processor 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 solution that is provided to the application, the semantic solution being indicative of the meaning of at least some portion of a received query, 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 positional information of words forming the corresponding portion in the received query, and wherein the semantic engine is adapted to combine one or more self-describing fragments to form one or more semantic solutions.

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.