Parsing and translating natural language sentences automatically

• US 5,930,746 A
• Filed: 08/09/1996
• Issued: 07/27/1999
• Est. Priority Date: 03/20/1996
• Status: Expired due to Fees

• Current Assignee: Government of Singapore
• Original Assignee: Government of Singapore
• Inventors: Ting, Hian Ann
• Primary Examiner(s): Isen, Forester W.
• Assistant Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US08/694,697
• Time in Patent Office: 1,082 Days
• Field of Search: 704/1, 704/9, 704/2, 704/4, 704/7, 707/530, 707/531, 707/536
• US Class Current: 704/9
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models
• CPC Class Codes: G06F 40/49 using very large corpora, e.g. the web
• CPC Class Codes: G06F 40/55 Rule-based translation

Abstract

A sentence of a natural language is automatically parsed by: defining a set of coded tags each corresponding to a respective part-of-speech of a word in a sentence of the language; building a small corpus of sentence dependency structures by annotating with the corresponding coded tags the words in each sentence of a set of sentences having respective exemplary dependency structures to obtain a set of sequences of coded tags representing the dependency structures; determining the statistical parameters of a corpus-based statistical tool, such as a hidden Markov model, from the corpus of sentence dependency structures; tagging the words of an input sentence to be parsed with the corresponding coded tags to obtain a sequence of coded tags to derive therefrom the most probable dependency structure for the input sentence; and generating a dependency parse tree of the sentence from the derived dependency structure and the words of the input sentence. The invention finds particular application in the automatic translation of a first natural language into a second language.

Claims

1. A method of automatically parsing a sentence of a natural language, comprising:

defining a set of coded tags each corresponding to a respective part-of-speech of a word in a sentence of the language;

building a corpus of sentence dependency structures by annotating with the corresponding coded tags the words in each sentence of a set of sentences having respective exemplary dependency structures to obtain a set of sequences of coded tags representing the dependency structures;

determining the statistical parameters of a corpus-based statistical tool from the corpus of sentence dependency structures;

tagging the words of an input sentence to be parsed with the corresponding coded tags to obtain a sequence of coded tags representing the input sentence;

applying the corpus-based statistical tool to the sequence of coded tags to derive therefrom the most probable dependency structure for the input sentence; and

generating a dependency parse tree of the sentence from the derived dependency structure and the words of the input sentence.

2. The method according to claim 1, comprising:

rendering electrical signals representing input text in the language into paragraphs and sentences; and

tokenising the sentences into strings of words.

3. The method according to claim 1, comprising:

storing a part-of-speech corpus consisting of words in the language associates with their corresponding coded tags; and

tagging the words of the input sentence to be parsed using the part-of-speech corpus and the statistical tagger.

4. The method according to claim 3, wherein the statistical tagger is based on a first-order hidden Markov model.

5. The method according to claim 3, comprising using a dynamic context algorithm to assign a most probable coded tag to an unknown word not contained in the part-of-speech corpus.

6. The method according to claim 1, comprising determining the most probable dependency structure using a first-order double layer hidden Markov model.

7. The method according to claim 6, comprising:

using a dynamic context algorithm to nominate candidate governors and generate a parse forest of dependency parse trees;

pruning away invalid candidate governors; and

selecting the most probable dependency structure from the remaining dependency trees.

8. The method according to claim 7, comprising pruning away the invalid governors using a first group of language-independent axioms of dependency structure.

9. The method according to claim 8, wherein the first group of axioms comprises a first axiom that each word depends on one and only one word in the same sentence and a second axiom that a word used as a conjunction or preposition cannot be a leaf of a dependency tree.

10. The method according to claim 8, comprising selecting a plurality of most likely dependency trees from the pruned forest of dependency trees using an enhanced Viterbi algorithm.

11. The method according to claim 10, comprising selecting as the most probable dependency structure that dependency tree which satisfies a second group of language independent axioms of dependency structure.

12. The method according to claim 11, wherein the second group of axioms comprises a third axiom that dependency structure is non-cyclic, a fourth axiom that dependency structure is non-crossing and a fifth axiom that a sentence can have at most one main verb.

13. The method according to claim 7, comprising extracting noun phrases from the input sentence after tagging of the input sentence and prior to generating the parse forest.

14. A machine for parsing a sentence of a natural language, comprising:

a coder defining a set of coded tags each corresponding to a respective part-of-speech of a word in a sentence of the language;

a corpus-based statistical tool having statistical parameters determined from a corpus of sentence dependency structures formed by annotating with the corresponding coded tags the words in each sentence of a set of sentences having respective exemplary dependency structures;

a tagger for tagging the words of a sentence to be parsed with the corresponding coded tags to obtain a sequence of coded tags representing the input sentence;

a processor for applying the corpus-based statistical tool to the sequence of coded tags to derive therefrom the most probable dependency structure for the input sentence and to generate a dependency parse tree of the sentence from the derived dependency structure and the words of the input sentence.

15. The machine according to claim 14, comprising an analyzer for rendering electrical signals representing input text in the language into paragraphs and sentences and for tokenising the sentences into strings of words.

16. The machine according to claim 14, comprising a first corpus memory storing a part-of-speech corpus consisting of words in the language associated with their corresponding coded tags;

and a statistical tagger for tagging the words of the input sentence using the part-of-speech corpus.

17. The machine according to claim 16, wherein the statistical tagger is based on a first-order hidden Markov model.

18. The machine according to claim 16, comprising a dynamic context algorithm for assigning a most probable coded tag to an unknown word not contained in the part-of-speech corpus.

19. The machine according to claim 14, wherein the corpus-based statistical tool for determining the most probable dependency structure includes a first-order double layer hidden Markov model.

20. The machine according to claim 19, wherein a dynamic context algorithm is used to nominate candidate governors and generate a parse forest of dependency parse trees from which invalid candidate governors are pruned away, the most probable dependency structure being selected from the remaining dependency trees.

21. The machine according to claim 20, wherein the invalid governors are pruned away using a first group of language-independent axioms of dependency structure.

22. The machine according to claim 21, wherein the first group of axioms comprises a first axiom that each word depends on one and only one word in the same sentence and a second axiom that a word used as a conjunction or preposition cannot be a leaf of a dependency tree.

23. The machine according to claim 21, wherein a plurality of most likely dependency trees are selected from the pruned forest of dependency trees using an enhanced Viterbi algorithm.

24. The machine according to claim 23, wherein the most probable dependency structure is selected from the plurality of most likely dependency trees as being that dependency tree which satisfies a second group of language-independent axioms of dependency structure.

25. The machine according to claim 24, wherein the second group of axioms comprises a third axiom that dependency structure is non-cyclic, a fourth axiom that dependency structure is non-crossing and a fifth axiom that a sentence can have at most the main verb.

26. The machine according to claim 20, wherein noun phrases are extracted from the input sentence after tagging of the input sentence and prior to generating the parse forest.

27. A method of automatically translating a first natural language into a second language, comprising the steps of:

converting a spoken or written text in the first language into electrical signals representing the spoken or written words;

rendering the text into sentences;

processing each sentence by an automatic parsing method to generate a dependency parse tree for the sentence by defining a set of coded tags each corresponding to a respective part-of-speech of a word in a sentence of the language;

building a corpus of sentence dependency structures by annotating with the corresponding coded tags the words in each sentence of a set of sentences having respective exemplary dependency structures to obtain a set of sequences of coded tags representing the dependency structures;

determining the statistical parameters of a corpus-based statistical tool from the corpus of sentence dependency structures;

tagging the words of an input sentence to be parsed with the corresponding coded tags to obtain a sequence of coded tags representing the input sequence;

applying the corpus-based statistical tool to the sequence of coded tags to derive therefrom the most probable dependency structure for the input sentence; and

generating a dependency parse tree of the sentence from the derived dependency structure and the words of the input sentence;

synthesizing a sentence in a second language based on the words and the derived dependency tree of the sentence in the first language; and

audibly or visually reproducing a synthesized sentence in the second language.

28. The method according to claim 27, comprising rendering electrical signals representing input text in the language into paragraphs and sentences;

and

tokenising the sentences into strings of words.

29. The method according to claim 27, comprising storing a part-of-speech corpus consisting of words in the language associates with their corresponding coded tags;

and

tagging the words of the input sentence to be parsed using the part-of-speech corpus and the statistical tagger.

30. The method according to claim 29, wherein the statistical tagger is based on a first-order hidden Markov model.

31. The method according to claim 29, comprising using a dynamic context algorithm to assign a most probable coded tag to an unknown word not contained in the part-of-speech corpus.

32. The method according to claim 27, comprising determining the most probable dependency structure using a first-order double layer hidden Markov model.

33. The method according to claim 32, comprising using a dynamic context algorithm to nominate candidate governors and generate a parse forest of dependency parse trees;

pruning away invalid candidate governors; and

selecting the most probable dependency structure from the remaining dependency trees.

34. The method according to claim 33, comprising pruning away the invalid governors using a first group of language-dependent axioms of dependency structure.

35. The method according to claim 34, wherein the first group of axioms comprises a first axiom that each word depends on one and only one word in the same sentence and a second axiom that a word used as a conjunction or preposition cannot be a leaf of a dependency tree.

36. The method according to claim 34, comprising selecting a plurality of most likely dependency trees from the pruned forest of dependency trees using an enhanced Viterbi algorithm.

37. The method according to claim 36, comprising selecting as the most probable dependency structure that dependency tree which satisfies a second group of language independent axioms of dependency structure.

38. The method according to claim 37, wherein the second group of axioms comprises a third axiom that dependency structure is non-cyclic, a fourth axiom that dependency structure is non-crossing and a fifth axiom that a sentence can have at most one main verb.

39. The method according to claim 33 comprising extracting noun phrases from the input sentence after tagging of the input sentence prior to generating the parse forest.

40. An apparatus for automatically translating a first natural language into a second language, comprising:

a converter for converting a spoken or written text in the first language into electrical signals representing the spoken or written words;

a means for rendering the text into sentences;

an automatic parsing machine for processing each sentence to generate a dependency parse tree for the sentence comprising a coder defining a set of coded tags each corresponding to a respective part-of-speech of a word in a sentence of the language;

a corpus-based statistical tool having statistical parameters determined from a corpus of sentence dependency structures formed by annotating with the corresponding coded tags the words in each sentence of a set of sentences having respective exemplary dependency structures;

a tagger for tagging the words of a sentence to be parsed with the corresponding coded tags to obtain a sequence of coded tags representing the input sentence;

a processor for applying the corpus-based statistical tool to the sequence of coded tags to derive therefrom the most probable dependency structure for the input sentence and to generate a dependency parse tree of the sentence from the derived dependency structure and the words of the input sentence;

a synthesizer for synthesizing a sentence in the second language based on the words and the derived dependency tree of the sentence in the first language; and

a reproduction device for audibly or visually reproducing the synthesized sentence in the second language.

41. The machine according to claim 40, comprising an analyzer for rendering electric signals representing input text in the language into paragraphs and sentences and for tokenising the sentences into strings of words.

42. The machine according to claim 40, comprising a first corpus memory storing a part-of-speech corpus consisting of words in the language associated with a corresponding coded tags;

and

a statistical tagger for tagging the words of the input sentence using the part-of-speech corpus.

43. The machine according to claim 42, wherein the statistical tagger is based on a first-order hidden Markov model.

44. The machine according to claim 42, comprising a dynamic context algorithm for assigning a most probable coded tag to an unknown word not contained in the part-of-speech corpus.

45. The machine according to claim 40, wherein the corpus-based statistical tool for determining the most probable dependency structure includes a first-order double layer hidden Markov model.

46. The machine according to claim 45, wherein a dynamic context algorithm is used to nominate candidate governors and generate a parse forest of dependency parse trees from which invalid candidate governors are pruned away, the most probable dependency structure being selected from the remaining dependency trees.

47. The machine according to claim 46, wherein the invalid governors are pruned away using a first group of language-independent axioms of dependency structure.

48. The machine according to claim 47, wherein the first group of axioms comprises a first axiom that each word depends on one and only one word in the same sentence and a second axiom that a word used as a conjunction or preposition cannot be a leaf of a dependency tree.

49. The machine according to claim 47, wherein a plurality of most likely dependency trees are selected from the pruned forest of dependency trees using an enhanced Viterbi algorithm.

50. The machine according to claim 49, wherein the most probable dependency structure is selected from the plurality of most likely dependency trees as being that dependency tree which satisfies a second group of language-independent axioms of dependency structure.

51. The machine according to claim 50, wherein the second group of axioms comprises a third axiom that dependency structure is non-cyclic, a fourth axiom that dependency structure is non-crossing and a fifth axiom that a sentence can have at most the main verb.

52. The machine according to claim 46, wherein noun phrases are extracted from the input sentence after tagging of the input sentence and prior to generating the parse forest.