Method and apparatus for natural language parsing using multiple passes and tags

• US 6,631,346 B1
• Filed: 04/07/1999
• Issued: 10/07/2003
• Est. Priority Date: 04/07/1999
• Status: Expired due to Term

• Current Assignee: Sovereign Peak Ventures, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Karaorman, Murat, Junqua, Jean-claude
• Primary Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US09/287,810
• Time in Patent Office: 1,644 Days
• Field of Search: 704/1, 704/8, 704/9, 704/10, 704/270, 704/275, 707/530, 707/531
• US Class Current: 704/9
• CPC Class Codes: G10L 15/1822 Parsing for meaning understanding

Abstract

A computer-implemented speech parsing method and apparatus for processing an input phrase. The method and apparatus include providing a plurality of grammars that are indicative of predetermined topics. A plurality of parse forests are generated using the grammars. Tags are associated with words preferably according to a scoring scheme utilizing the generated parse forests while parsing the input phrase. The tags that are associated with the words are used as a parsed representation of the input phrase.

Claims

1. A computer-implemented speech parsing method for processing an input phrase, comprising the steps of:

(a) providing a plurality of grammars indicative of predetermined topics;

(b) generating a plurality of parse forests related to said input phrase using said grammars;

(c) associating tags with words in said input phrase using said generated parse forests;

(d) using said tags associated with said words as a parsed representation of said input phrase;

(e) generating scores for said tags based upon attributes of said parse forest, said attributes comprising a plurality of score based factors selected from the group consisting of number of terminals, gap size, depth, number of non-terminals and combinations thereof;

(f) selecting said tags for use in said parsed representation based upon said generated scores; and

(g) extracting overall semantics of the input phrase by using task related topics of the parsed representation to recognize a goal-oriented task with certain constraints.

2. The speech parsing method of claim 1 further comprising the step of:

weighting at least two of said factors differently.

3. The speech parsing method of claim 2 further comprising the step of:

using context information to weigh at least two of said factors differently.

4. The speech parsing method of claim 3 further comprising the steps of:

generating a word confidence vector for said input phrase substantially during speech recognition of said input phrase; and

weighting at least two of said factors differently based upon said generated word confidence vector.

5. The speech parsing method of claim 4 further comprising the steps of:

generating a request for information related to a predetermined topic;

generating dialogue context weights based upon said generated request for information; and

weighting at least two of said factors differently based upon said generated dialogue context weights.

6. The speech parsing method of claim 3 further comprising the steps of:

generating a request for information related to a predetermined topic;

generating dialogue context weights based upon said generated request for information; and

weighting at least two of said factors differently based upon said generated dialogue context weights.

7. The speech parsing method of claim 3 further comprising the steps of:

using said context information substantially in parallel to performing said step (b).

8. A computer-implemented speech parsing apparatus for processing an input phrase, comprising:

a plurality of grammars indicative of predetermined topics;

a parse forest generator for generating a plurality of parse forests related to said input phrase using said grammars;

a tag generator for associating tags with words in said input phrase using said parse forests, wherein said tags associated with said words are used as a parsed representation of said input phrase;

a tag score generator for generating scores for said tags;

a global parser for extracting overall semantics of the input phrase by using task related topics of the parsed representation to recognize a goal-oriented task with certain constraints;

a tag selector for selecting tags for use in said parsed representation based upon said generated scores; and

said tag score generator generates scores for said tags based upon attributes of said parse forests;

said attributes comprising score based factors selected from the group consisting of number of terminals, gap size, depth, number of non-terminals; and

combinations thereof.

9. The speech parsing apparatus of claim 8 wherein said tag score generator weights at least two of said factors differently.

10. The speech parsing apparatus of claim 9 wherein said tag score generator uses context information to weight at least two of said factors differently.

11. The speech parsing apparatus of claim 10 further comprising:

a speech recognition module for performing speech recognition of said input phrase and for generating a word confidence vector for said input phrase substantially,

said tag score generator weighting at least two of said factors differently based upon said generated word confidence vector.

12. The speech parsing apparatus of claim 11 further comprising:

a dialogue manager for generating a request for information related to a predetermined topic, said dialogue manager generating dialogue context weights based upon said generated request for information,

said tag score generator weighting at least two of said factors differently based upon said generated dialogue context weights.

13. The speech parsing apparatus of claim 10 further comprising:

a dialogue manager for generating a request for information related to a predetermined topic, said dialogue manager generating dialogue context weights based upon said generated request for information,

said tag score generator weighting at least two of said factors differently based upon said generated dialogue context weights.

14. A computer-implemented speech parsing method for processing an input phrase, comprising the steps of:

(a) providing a plurality of grammars indicative of predetermined topics;

(b) generating a plurality of parse forests related to said input phrase using said grammars in cooperation with at least one global parser and at least one local parser;

(c) associating tags with words in said input phrase using said generated parse forests; and

(d) using said tags associated with said words as a parsed representation of said input phrase, said local parser identifying a plurality of predetermined relevant task-related fragments.

15. The speech parsing method of claim 14 wherein said local parser utilizing said grammars in a plurality of iterations in association with a scoring mechanism.

16. The speech parsing method of claim 15 wherein said grammars are relatively small in size.

17. The speech parsing method of claim 14 further comprising the step of:

performing said step (b) a plurality of iterations so that each iteration produces alternate parse forests.

18. The speech parsing method of claim 14 wherein said step (b) is performed substantially concurrently for each of said grammars.

19. The speech parsing method of claim 18 further comprising the step of:

performing said step (b) a plurality of iterations wherein each iteration produces alternate parse forests with respect to each of said grammars.

20. The speech parsing method of claim 14 further comprising the steps of:

generating scores for said tags; and

selecting tags for use in said parsed representation based upon said generated scores.

21. The speech parsing method of claim 20 further comprising the step of:

generating scores for said tags based upon attributes of said parse forests.

22. The speech parsing method of claim 21 further comprising the step of:

generating scores for said tags based upon score based factors selected from the group consisting of number of terminals, gap size, depth, number of non-terminals, and combinations thereof.

23. The speech parsing method of claim 22 further comprising the step of:

weighting at least two of said factors differently.

24. The speech parsing method of claim 23 further comprising the step of:

using context information to weigh at least two of said factors differently.

25. The speech parsing method of claim 24 further comprising the steps of:

generating a word confidence vector for said input phrase substantially during speech recognition of said input phrase; and

weighting at least two of said factors differently based upon said generated word confidence vector.

26. The speech parsing method of claim 25 further comprising the steps of:

generating a request for information related to a predetermined topic;

generating dialogue context weights based upon said generated request for information; and

weighting at least two of said factors differently based upon said generated dialogue context weights.

27. The speech parsing method of claim 24 further comprising the steps of:

generating a request for information related to a predetermined topic;

generating dialogue context weights based upon said generated request for information; and

weighting at least two of said factors differently based upon said generated dialogue context weights.

28. The speech parsing method of claim 24 further comprising the steps of:

using said context information substantially in parallel to performing said step (b).

29. The speech parsing method of claim 14 further comprising the steps of:

generating scores for said tags; and

selecting N-best tags for use in said parsed representation based upon said generated scores.

30. The speech parsing method of claim 29 further comprising the steps of:

performing said steps (b) and (c) a plurality of iterations; and

using said selected N-best tags of a first iteration as input related to processing said steps (b) and (c) of a second iteration.

31. The speech parsing method of claim 14 wherein said tags are indicative of said topics of said grammars.

32. The speech parsing method of claim 14 wherein said input phrase is grammatically incorrect with respect to at least a portion of said input phrase, said method further comprising the steps of:

generating a plurality of parse forests related to said grammatically incorrect input phrase using said grammars;

associating tags with words in said grammatically incorrect input phrase using said generated parse forests; and

using said tags associated with said words as a parsed representation of said grammatically incorrect input phrase.

33. The speech parsing method of claim 14 wherein said grammars are based upon left-right context-sensitive grammars.

34. The speech parsing method of claim 14 wherein said grammars are based upon left-right context-sensitive grammars and contain ambiguities.

35. The speech parsing method of claim 14 further comprising the steps of:

filtering said input phrase via lexical filters; and

generating said plurality of parse forests based upon said filtered input phrase.

36. The speech parsing method of claim 14 further comprising the step of:

extracting semantic components of said input phrase based upon said tags that are associated with said words.

37. The speech parsing method of claim 14 further comprising the step of:

providing said global parser for extracting said semantic components from said input phrase based upon said tags that are associated with said words.

38. The speech parsing method of claim 14 further comprising the step of:

managing based upon said extracted semantic components the exchange of dialogue between a speech recognizer device and a user.

39. The speech parsing method of claim 37 further comprising the step of:

managing based upon said extracted semantic components the exchange of dialogue between two users who speak different languages.

40. A computer-implemented speech parsing apparatus for processing an input phrase, comprising:

a plurality of grammars indicative of predetermined topics;

a parse forest generator for generating a plurality of parse forests related to said input phrase using said grammars in cooperation with at least one global parser and at least one local parser;

a tag generator for associating tags with words in said input phrase using said generated parse forests, wherein said tags associated with said words are used as a parsed representation of said input phrase; and

said local parser utilizing said grammars in a plurality of iterations in association with a scoring mechanism.

41. The speech parsing apparatus of claim 40 wherein said parse forest generator is executed a plurality of iterations such that each iteration produces alternate parse forests.

42. The speech parsing apparatus of claim 40 wherein said parse forest generator is executed a plurality of iterations such that each iteration produces alternate parse forests with respect to each of said grammars.

43. The speech parsing apparatus of claim 40 further comprising:

a tag score generator for generating scores for said tags; and

a tag selector for selecting tags for use in said parsed representation based upon said generated scores.

44. The speech parsing apparatus of claim 43 wherein said tag score generator generates scores for said tags based upon attributes of said parse forests.

45. The speech parsing apparatus of claim 44 wherein said tag score generator generates scores for said tags based upon score based factors selected from the group consisting of number of terminals, gap size, depth, number of non-terminals, and combinations thereof.

46. The speech parsing apparatus of claim 45 wherein said tag score generator weights at least two of said factors differently.

47. The speech parsing apparatus of claim 46 wherein said tag score generator uses context information to weight at least two of said factors differently.

48. The speech parsing apparatus of claim 47 further comprising:

a speech recognition module for performing speech recognition of said input phrase and for generating a word confidence vector for said input phrase substantially,

said tag score generator weighting at least two of said factors differently based upon said generated word confidence vector.

49. The speech parsing apparatus of claim 48 further comprising:

a dialogue manager for generating a request for information related to a predetermined topic, said dialogue manager generating dialogue context weights based upon said generated request for information,

said tag score generator weighting at least two of said factors differently based upon said generated dialogue context weights.

50. The speech parsing apparatus of claim 47 further comprising:

a dialogue manager for generating a request for information related to a predetermined topic, said dialogue manager generating dialogue context weights based upon said generated request for information,

said tag score generator weighting at least two of said factors differently based upon said generated dialogue context weights.

51. The speech parsing apparatus of claim 40 further comprising:

a tag score generator for generating scores for said tags; and

a tag selector for selecting N-best tags for use in said parsed representation based upon said generated scores.

52. The speech parsing apparatus of claim 51 wherein said parse forest generator and said tag generator are executed a plurality of iterations, said selected N-best tags of a first iteration are used as input to said parse forest generator and said tag generator during a second iteration.

53. The speech parsing apparatus of claim 40 wherein said tags are indicative of said topics of said grammars.

54. The speech parsing apparatus of claim 40 wherein said input phrase is grammatically incorrect with respect to at least a portion of said input phrase, said parse forest generators generating a plurality of parse forests related to said grammatically incorrect input phrase using said grammars, said tag generator associating tags with words in said grammatically incorrect input phrase using said generated parse forests, said tags being associated with said words as a parsed representation of said grammatically incorrect input phrase.

55. The speech parsing apparatus of claim 40 wherein said grammars are based upon left-right context-sensitive grammars.

56. The speech parsing apparatus of claim 40 wherein said grammars are based upon left-right context-sensitive grammars and contain ambiguities.

57. The speech parsing apparatus of claim 40 further comprising:

a lexical filter for filtering said input phrase, said parse forest generator generating said plurality of parse forests based upon said filtered input phrase.

58. The speech parsing apparatus of claim 40 further comprising:

a semantic extractor for extracting semantic components of said input phrase based upon said tags that are associated with said words.

59. The speech parsing apparatus of claim 48 further comprising:

said global parser extracting said semantic components from said input phrase based upon said tags that are associated with said words.

60. The speech parsing apparatus of claim 59 further comprising:

a dialogue manager for managing based upon said extracted semantic components the exchange of dialogue between a speech recognizer device and a user.

61. The speech parsing apparatus of claim 59 further comprising:

a dialogue manager for managing based upon said extracted semantic components the exchange of dialogue between two users who speak different languages.