Phrase-based dialogue modeling with particular application to creating recognition grammars for voice-controlled user interfaces

• US 20020128821A1
• Filed: 03/11/2002
• Published: 09/12/2002
• Est. Priority Date: 05/28/1999
• Status: Active Grant

• Current Assignee: Nant Holdings IP, LLC (NantWorks, LLC)
• Original Assignee: Fluential, LLC
• Inventors: Ehsani, Farzad, Knodt, Eva M.
• Granted Patent: US 8,374,871 B2
• Time in Patent Office: Days
• US Class Current: 704/10
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms
• CPC Class Codes: G06F 40/279 Recognition of textual entities
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06F 40/35 Discourse or dialogue representation
• CPC Class Codes: G10L 15/005 Language recognition
• CPC Class Codes: G10L 15/183 using context dependencies, e.g. language models
• CPC Class Codes: G10L 15/193 Formal grammars, e.g. finite state automata, context free grammars or word networks
• CPC Class Codes: G10L 15/197 Probabilistic grammars, e.g. word n-grams
• CPC Class Codes: G10L 15/22 Procedures used during a speech recognition process, e.g. man-machine dialogue

Abstract

The invention enables creation of grammar networks that can regulate, control, and define the content and scope of human-machine interaction in natural language voice user interfaces (NLVUI). More specifically, the invention concerns a phrase-based modeling of generic structures of verbal interaction and use of these models for the purpose of automating part of the design of such grammar networks.

Claims

1. A method for producing a phrase thesaurus, comprising the steps of:

identifying a plurality of valid phrases that occur within a text corpus;

determining the degree of similarity between the valid phrases; and

grouping the valid phrases into classes of equivalent valid phrases based upon the determined degree of similarity between valid phrases.

2. A method as in claim 1, wherein the step of identifying a plurality of valid phrases that occur within a text corpus further comprises the step of extracting candidate phrases from the text corpus.

3. A method as in claim 2, wherein the step of extracting candidate phrases from the text corpus further comprises the step of identifying a first set of candidate phrases that includes phrases that occur in the text corpus with greater than a predetermined frequency.

4. A method as in claim 3, wherein the step of extracting candidate phrases from the text corpus further comprises the step of filtering the first set of candidate phrases to eliminate phrases from the first set of candidate phrases in accordance with one or more predetermined criteria.

5. A method as in claim 4, wherein the step of filtering further comprises the step of eliminating candidate phrases that occur with less than a predetermined frequency from the first set of candidate phrases.

6. A method as in claim 5, wherein the predetermined frequency varies in accordance with the number of words in a candidate phrase.

7. A method as in claim 6, wherein the predetermined frequency decreases as the number of words in a candidate phrase increases.

8. A method as in claim 4, wherein the step of filtering further comprises the steps of:

calculating the surrounding perplexity of each of the candidate phrases; and

eliminating candidate phrases having less than a predetermined surrounding perplexity from the first set of candidate phrases.

9. A method as in claim 3, wherein the step of extracting candidate phrases from the text corpus further comprises the step of adding phrase templates and/or non-contiguous phrases to the first set of candidate phrases in accordance with one or more predetermined criteria.

10. A method as in claim 9, wherein the step of adding phrase templates and/or non-contiguous phrases further comprises the steps of:

creating one or more contexts for each phrase in the first set of candidate phrases, each context for a phrase being a sentence that contains the phrase; and

evaluating words surrounding a phrase in the contexts for that phrase to enable identification of phrase templates and/or non-contiguous phrases.

11. A method as in claim 9, wherein the step of adding phrase templates and/or non-contiguous phrases further comprises the steps of:

determining the frequency of occurrence in the first set of candidate phrases of word pairs such that each word of the word pair is separated by no more than a predetermined number of words; and

identifying word pairs that occur with greater than a predetermined frequency to enable identification of phrase templates and/or non-contiguous phrases containing such word pairs.

12. A method as in claim 11, wherein the predetermined number of words is 5.

13. A method as in claim 11, wherein the predetermined frequency is greater than or equal to the frequency of all but a predetermined number of word pairs.

14. A method as in claim 9, wherein the step of extracting candidate phrases from the text corpus further comprises the step of filtering the added phrase templates and/or non-contiguous phrases to eliminate phrase templates and/or non-contiguous phrases from the first set of candidate phrases in accordance with one or more predetermined criteria.

15. A method as in claim 14, wherein the step of filtering further comprises the steps of:

determining the words and/or word sequences surrounding each phrase template and/or non-contiguous phrase with greater than a predetermined frequency;

calculating the mutual information for each phrase template and/or non-contiguous phrase and the surrounding words and/or word sequences occurring with greater than the predetermined frequency; and

modifying the set of candidate phrases in accordance with the value of mutual information.

16. A method as in claim 14, wherein the step of filtering further comprises the steps of:

determining a main component of each phrase template and/or non-contiguous phrase;

determining a sub-component of each phrase template and/or non-contiguous phrase;

calculating the probability distribution of the sub-component with respect to other words or phrases in the same context; and

modifying the set of candidate phrases in accordance with the value of the probability distribution.

17. A method as in claim 14, wherein the step of filtering further comprises the step of manually reviewing and eliminating phrase templates and/or non-contiguous phrases from the first set of candidate phrases in accordance with one or more predetermined criteria.

18. A method as in claim 2, wherein the step of identifying further comprises the step of eliminating overlapping candidate phrases.

19. A method as in claim 18, wherein the step of eliminating overlapping candidate phrases further comprises the steps of:

dividing the text corpus into first and second complementary subsets of the text corpus;

performing a preliminary parse into phrases of the first subset of the text corpus;

creating a language model of the first subset of the text corpus based on the preliminary parse of the first subset of the text corpus;

performing a parse into phrases of the second subset of the text corpus based on the language model of the first subset of the text corpus;

creating a language model of the second subset of the text corpus based on the parse of the second subset of the text corpus;

performing a parse into phrases of the first subset of the text corpus based on the language model of the second subset of the text corpus;

comparing the parse of first subset of the text corpus to the parse of the second subset of the text corpus; and

modifying the set of candidate phrases in accordance with the comparison between the parse of first subset of the text corpus and the parse of the second subset of the text corpus.

20. A method as in claim 19, wherein the first and second subsets of the text corpus are of substantially equal size.

21. A method as in claim 19, wherein:

the first subset of the text corpus can be parsed in a plurality of ways; and

the step of performing a preliminary parse of the first subset of the text corpus further comprises the step of selecting the parse that includes the longest candidate phrases as determined in accordance with one or more predetermined criteria.

22. A method as in claim 19, wherein:

the first subset of the text corpus can be parsed in a plurality of ways; and

the step of performing a preliminary parse of the first subset of the text corpus further comprises the step of selecting the parse that minimizes the number of candidate phrases in the preliminary parse.

23. A method as in claim 19, further comprising:

alternately repeating the steps of;

creating a language model of one of the first or second subsets of the text corpus based on the preliminary parse of that one of the first or second subsets of the text corpus;

performing a parse into phrases of the other of the first or second subsets of the text corpus based on the language model of the one of the first or second subsets of the text corpus; and

comparing the parse of the other of the first or second subsets of the text corpus to a previous parse of the one of the first or second subsets of the text corpus for which a language model was most recently created; and

terminating the method when the difference between one or more n-gram probability scores for the two compared parses is less than a threshold amount.

24. A method as in claim 1, wherein the step of determining the degree of similarity between valid phrases further comprises the step of determining the degree of semantic similarity between valid phrases.

25. A method as in claim 24, wherein the step of determining the degree of semantic similarity between valid phrases further comprises the steps of:

creating one or more contexts for each valid phrase, each context for a valid phrase being a word or phrase that appears adjacent to the valid phrase in the text corpus; and

determining the degree of overlap of the contexts of each valid phrase with the contexts of each other valid phrase.

26. A method as in claim 25, wherein the step of determining the degree of overlap further comprises the step of calculating one or more association coefficients between the contexts of each valid phrase and the contexts of each other valid phrase.

27. A method as in claim 25, wherein the step of determining the degree of overlap further comprises the steps of:

creating a matrix in which each entry indicates the frequency of occurrence of a particular context with a particular valid phrase;

eliminating entries from the matrix having a frequency less than a predetermined magnitude, thereby enabling production of a reduced matrix; and

manipulating the matrix to determine the degree of overlap of the contexts of each valid phrase with the contexts of each other valid phrase.

28. A method as in claim 27, wherein the step of eliminating is performed using singular value decomposition.

29. A method as in claim 1, wherein the step of determining the degree of similarity between valid phrases further comprises the step of determining the degree of syntactic similarity between valid phrases.

30. A method as in claim 1, wherein the step of determining the degree of similarity between valid phrases further comprises the step of determining the degree of pragmatic similarity between valid phrases.

31. A method as in claim 1, wherein the step of determining the degree of similarity between valid phrases further comprises the steps of:

determining two or more of the degree of semantic, similarity between valid phrases, the degree of syntactic similarity between valid phrases and the degree of pragmatic similarity between valid phrases; and

combining the determinations of degree of similarity to produce an overall degree of similarity between valid phrases.

32. A method as in claim 25, wherein the step of grouping valid phrases into classes of equivalent valid phrases further comprises the step of identifying equivalent valid phrases as valid phrases having contexts that overlap by greater than a predetermined degree.

33. A method as in claim 32, wherein the step of grouping valid phrases into classes of equivalent valid phrases is performed using one or more agglomerative clustering methods.

34. A method as in claim 1, further comprising the step of arranging valid phrases within a phrase class in order of frequency of occurrence within the text corpus.

35. A method as in claim 1, further comprising the step of tagging each of one or more phrase classes with a descriptor denoting a conceptual representation of the valid phrases contained in the phrase class.

36. A method as in claim 35, wherein the descriptor or descriptors include one or more of speech act classifications for verb phrases, object nouns and/or proper names.

37. A method as in claim 1, further comprising the step of normalizing the text corpus before performing the step of identifying.

38. A method as in claim 37, wherein the step of normalizing the text corpus further comprises the step of marking sentence boundaries in the text corpus.

39. A method as in claim 38, wherein the step of normalizing the text corpus further comprises the steps of:

expanding parts of the text corpus that are not full words into full words; and

correcting typographical errors.

40. A method as in claim 1, wherein the plurality of valid phrases includes one or more phrase templates.

41. A method as in claim 40, further comprising the step of including in the phrase thesaurus lexical items that can be used to complete a phrase template.

42. A method as in claim 1, further comprising the step of including in the phrase thesaurus data regarding the frequency of occurrence of valid phrases within the text corpus.

43. A method as in claim 1, wherein a valid phrase can be included in more than one phrase class.

44. A method as in claim 1, wherein the classes of equivalent valid phrases are arranged in a hierarchical structure.

45. A method as in claim 1, wherein the text corpus comprises a transcript of television programming.

46. A method as in claim 1, wherein the text corpus comprises the text of one or more Internet news sources.

47. A method as in claim 1, wherein the text corpus comprises the text of a plurality of electronic mail messages.

48. A method as in claim 1, wherein the text corpus comprises a transcript of spoken discourse.

49. A system for producing a phrase thesaurus, comprising:

means for identifying a plurality of valid phrases that occur within a text corpus;

means for determining the degree of similarity between the valid phrases; and

means for grouping the valid phrases into classes of equivalent valid phrases based upon the determined degree of similarity between valid phrases.

50. A computer readable storage medium encoded with one or more computer programs for enabling production of a phrase thesaurus, comprising:

instructions for identifying a plurality of valid phrases that occur within a text corpus;

instructions for determining the degree of similarity between the valid phrases; and

instructions for grouping the valid phrases into classes of equivalent valid phrases based upon the determined degree of similarity between valid phrases.

51. A method for creating a recognition grammar for use with an interactive user interface that is responsive to spoken input, comprising the steps of:

formulating an expression of each of one or more anticipated spoken inputs to the interface, wherein each formulated expression can be constructed as one or more combinations of one or more phrases in a phrase thesaurus; and

using the phrase thesaurus to construct one or more equivalent expressions of one or more formulated expressions, wherein the recognition grammar comprises the collection of all of the expressions.

52. A method as in claim 51, wherein expressions of a plurality of spoken inputs are formulated and the phrase thesaurus is used to identify equivalent expressions for a plurality of formulated expressions.

53. A method as in claim 51, wherein an equivalent expression of a formulated expression is constructed using a method comprising the steps of:

selecting a combination of one or more phrases representing the formulated expression, wherein the phrases of the selected combination of one or more phrases are original phrases of the formulated expression;

identifying an equivalent phrase for each of one or more original phrases of the formulated expression; and

producing a new combination of one or more phrases representing the formulated expression, the new combination including at least one of the identified equivalent phrases, wherein the new combination represents the equivalent expression.

54. A method as in claim 53, wherein:

phrases in the phrase thesaurus have a probability of occurrence associated therewith;

one or more original phrases has a plurality of equivalent phrases; and

the step of identifying an equivalent phrase further comprises the step of selecting an equivalent phrase having the highest probability of occurrence.

55. A method as in claim 53, wherein equivalent phrases are grouped in classes and each class of equivalent phrases has associated therewith a descriptor denoting a conceptual representation of the phrases contained in that phrase class, the method further comprising the step of tagging each equivalent expression with the descriptor or descriptors associated with phrases of the equivalent expression.

56. A method as in claim 51, further comprising the step of translating the recognition grammar into a form that can be processed by a speech recognition system.

57. A method as in claim 51, further comprising the step of manually editing the recognition grammar.

59. A system as in claim 58, wherein the means for formulating an expression of each of one or more anticipated spoken inputs to the interface further comprises a graphical user interface device.

60. A system as in claim 58, further comprising data storage means for storing data representing the phrase thesaurus and the recognition grammar.

61. A system as in claim 60, wherein the data storage means further stores data representing lexical items that can be used to complete a phrase template.

62. A system as in claim 60, wherein the data storage means further stores data representing a probability of occurrence of phrases.

63. A system as in claim 62, wherein the phrases are stored in the data storage means in accordance with the corresponding probability of occurrence.

64. A system as in claim 62, wherein the step of using the phrase thesaurus to construct a recognition grammar further comprises the step of using the data representing a probability of occurrence of phrases to construct a probabilistic grammar.

65. A system as in claim 58, further comprising means for translating the recognition grammar into a form that can be processed by a speech recognition system.

66. A system as in claim 58, further comprising means for manually editing the recognition grammar.

58. A system for creating a recognition grammar for use with an interactive user interface that is responsive to spoken input, comprising:

means for formulating an expression of each of one or more anticipated spoken inputs to the interface, wherein each formulated expression can be constructed as one or more combinations of one or more phrases in a phrase thesaurus; and

means for using the phrase thesaurus to construct one or more equivalent expressions of one or more formulated expressions, wherein the collection of all of the expressions comprises the recognition grammar.

67. A method for determining the meaning of spoken input to an interface device, comprising the steps of:

converting the spoken input into a textual representation of the spoken input;

parsing the textual representation of the spoken input, using a phrase thesaurus, into one or more phrases, wherein an annotation is associated with at least one of the phrases; and

evaluating the annotation or annotations associated with the one or more phrases to determine the meaning of the spoken input.

68. A system for evaluating a first phrase to produce a second phrase having substantially the same meaning as the first phrase, comprising:

one or more data storage devices for storing a phrase thesaurus including classes of equivalent phrases, and for storing instructions for using the phrase thesaurus;

one or more user input devices for accepting input from a user specifying the first phrase and an instruction from the user to identify one or more phrases that are equivalent to the first phrase; and

a processing device for executing, in response to the user instruction, the instructions for using the phrase thesaurus, so that the second phrase is identified.

69. A computer readable storage medium encoded with instructions and/or data, comprising:

data representing a plurality of phrases;

instructions and/or data identifying classes of equivalent phrases having greater than a predetermined degree of similarity.