Method and apparatus for automatic grammar generation from data entries

• US 20060129396A1
• Filed: 12/09/2004
• Published: 06/15/2006
• Est. Priority Date: 12/09/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ju, Yun-Cheng, Ollason, David G., Bhatia, Siddharth
• Granted Patent: US 7,636,657 B2
• Time in Patent Office: Days
• US Class Current: 704/243
• CPC Class Codes: G10L 15/063 Training
• CPC Class Codes: G10L 15/193 Formal grammars, e.g. finite state automata, context free grammars or word networks

Abstract

A method of generating an optimized grammar, for use in speech recognition, from a data set or big list of items, is disclosed. The method includes the steps of obtaining a tree representing items in the data set, and generating the grammar using the tree. The tree or tree data structure representing items in the data set is a simulated recognition search tree, representing items in the data set, which can be automatically generated from the data set.

Claims

1. A method of generating a grammar for use in speech recognition, the method comprising:

obtaining a tree representing items in a data set; and

generating the grammar using the tree.

2. The method of claim 1, wherein obtaining the tree representing items in the data set comprises obtaining a tree data structure representing items in the data set.

3. The method of claim 2, wherein obtaining the tree data structure representing items in the data set further comprises obtaining the tree data structure representing names in a list of names.

4. The method of claim 1, wherein obtaining the tree representing items in the data set comprises obtaining a simulated recognition search tree representing items in the data set.

5. The method of claim 4, wherein obtaining the simulated recognition search tree comprises generating the simulated recognition search tree from the data set.

6. The method of claim 5, wherein generating the simulated recognition search tree from the data set further comprises building the simulated recognition search tree such that each word to be recognized in the data set is represented by an arc between nodes in the simulated recognition search tree.

7. The method of claim 6, wherein building the simulated recognition search tree such that each word to be recognized in the data set is represented by an arc between nodes further comprises labeling each arc with its corresponding word to be recognized.

8. The method of claim 7, wherein labeling each arc with its corresponding word to be recognized further comprises labeling each arc with a weight.

9. The method of claim 8, wherein labeling each arc with a weight further comprises labeling each arc with a count of the phrases in the data set which share the word corresponding to the arc and which are represented by a path including the arc.

10. The method of claim 8, wherein generating the grammar using the tree further comprises generating the grammar with the weights that label the arcs of the simulated recognition search tree.

11. The method of claim 8, wherein building the simulated recognition search tree further comprises:

determining whether a phrase reaching a node is a complete expression to be accepted; and

identifying nodes corresponding to compete expressions to be accepted as terminal nodes.

12. The method of claim 11, and for each terminal node further comprising storing semantic markup language (SML), to be returned by a speech recognition engine in response to the complete expression, in association with the terminal node.

13. The method of claim 12, wherein generating the grammar further comprises identifying terminal nodes with two complete expressions which reach the terminal node, but with different SML to return, as being indicative of collisions.

14. A computer-readable medium having stored thereon computer-executable instructions for implementing speech recognition engine grammar generating steps comprising:

obtaining a tree representing items in a data set; and

generating the grammar using the tree.

15. The computer-readable medium of claim 14, wherein obtaining the tree representing items in the data set comprises obtaining a tree data structure representing items in the data set.

16. The computer-readable medium of claim 15, wherein obtaining the tree data structure representing items in the data set further comprises obtaining the tree data structure representing names in a list of names.

17. The computer-readable medium of claim 14, wherein obtaining the tree representing items in the data set comprises obtaining a simulated recognition search tree representing items in the data set.

18. The computer-readable medium of claim 17, wherein obtaining the simulated recognition search tree comprises generating the simulated recognition search tree from the data set.

19. The computer-readable medium of claim 18, wherein generating the simulated recognition search tree from the data set further comprises building the simulated recognition search tree such that each word to be recognized in the data set is represented by an arc between nodes in the simulated recognition search tree.

20. The computer-readable medium of claim 19, wherein building the simulated recognition search tree such that each word to be recognized in the data set is represented by an arc between nodes further comprises labeling each arc with its corresponding word to be recognized.

21. The computer-readable medium of claim 20, wherein labeling each arc with its corresponding word to be recognized further comprises labeling each arc with a weight.

22. The computer-readable medium of claim 21, wherein labeling each arc with a weight further comprises labeling each arc with a count of the phrases in the data set which share the word corresponding to the arc and which are represented by a path including the arc.

23. The computer-readable medium of claim 21, wherein generating the grammar using the tree further comprises generating the grammar with the weights that label the arcs of the simulated recognition search tree.

24. The computer-readable medium of claim 21, wherein building the simulated recognition search tree further comprises:

determining whether a phrase reaching a node is a complete expression to be accepted; and

identifying nodes corresponding to compete expressions to be accepted as terminal nodes.

25. The computer-readable medium of claim 24, and for each terminal node further comprising storing semantic markup language (SML), to be returned by a speech recognition engine in response to the complete expression, in association with the terminal node.

26. The computer-readable medium of claim 25, wherein generating the grammar further comprises identifying terminal nodes with two complete expressions which reach the terminal node, but with different SML to return, as being indicative of collisions.

27. A grammar generation system for generating a grammar for use by a speech recognition engine, the system comprising:

a search tree module configured to generate a simulated recognition search tree representing items in a data set; and

a grammar producing module configured to generate the grammar using the generated simulated recognition search tree.

28. The grammar generation system of claim 27, wherein the search tree module is configured to generate the simulated recognition search tree such that it represents names in a list of names comprising the data set.

29. The grammar generation system of claim 28, wherein the search tree module is configured to generate the simulated recognition search tree from the data set by building the simulated recognition search tree such that each word to be recognized in the data set is represented by an arc between nodes in the simulated recognition search tree.

30. The grammar generation system of claim 29, wherein the search tree module is configured to generate the simulated recognition search tree from the data set by labeling each arc with its corresponding word to be recognized.

31. The grammar generation system of claim 30, wherein the search tree module is configured to generate the simulated recognition search tree from the data set by labeling each arc with a weight.

32. The grammar generation system of claim 31, wherein the search tree module is configured to label each arc with a weight which is a count of the phrases in the data set which share the word corresponding to the arc and which are represented by a path including the arc.

33. The grammar generation system of claim 31, wherein the search tree module is further configured to build the simulated recognition search tree by:

determining whether a phrase reaching a node is a complete expression to be accepted; and

identifying nodes corresponding to compete expressions to be accepted as terminal nodes.

34. The grammar generation system of claim 33, wherein the search tree module is further configured to build the simulated recognition search tree by storing semantic markup language (SML), to be returned by a speech recognition engine in response to the complete expression, in association with the terminal node.