Statistical translation system with features based on phrases or groups of words

• US 5,991,710 A
• Filed: 05/20/1997
• Issued: 11/23/1999
• Est. Priority Date: 05/20/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ward, Robert Todd, Papineni, Kishore Ananda, Roukos, Salim Estephan
• Primary Examiner(s): Isen, Forester W.
• Assistant Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US08/859,586
• Time in Patent Office: 917 Days
• Field of Search: 704/2-7, 704/9
• US Class Current: 704/2
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models

Abstract

A system for translating a first word set in a source language into a second word set in a target language, the system comprising: input means for inputting the first word set into the system; tagging means for tagging the first word set input to the system so as to at least substantially reduce non-essential variability in the first word set; translation means including a single a posteriori conditional probability model and a target candidate store for storing target language candidate word sets, wherein the translation means employs the single model to evaluate the target language candidate word sets in order to select the target language candidate word set having a best score with respect to the first word set; and output means for outputting the best scoring target language candidate word set as the second word set in the target language.

Claims

1. A system for translating a first word set in a source language into a second word set in a target language, the system comprising:

input means for inputting the first word set into the system;

tagging means for tagging the first word set input to the system so as to at least substantially reduce non-essential variability in the first word set;

translation means including a single a posteriori conditional probability model and a target candidate store for storing target language candidate word sets, wherein the translation means employs the single model to evaluate the target language candidate word sets in order to select the target language candidate word set having a best score with respect to the first word set;

wherein the single model includes a prior model, a plurality of feature functions and a plurality of weighting factors respectively corresponding to the plurality of feature functions, wherein the translation means receives the first word set and, in accordance with the single model, iteratively proceeds through the target language candidate store and each of the candidate word sets and finds the feature functions which are true with respect to the first word set and the second word set, and then multiplies the prior model by the weighting factors corresponding to the feature functions thereby providing resulting scores, the translation means then choosing the best matching target language candidate word set in accordance with the resulting scores; and

output means for out putting the best scoring target language candidate word set as the second word set in the target language.

2. The system of claim 1, wherein the prior model is one of a stochastic probabilistic model, a uniform model and a decision network based model.

3. The system of claim 1, wherein the plurality of feature functions includes a phrase feature function and wherein the phrase feature function is true when the first word set has a first phrase therein and at least one of the target language candidate word sets has a second phrase therein.

4. The system of claim 1, wherein the plurality of feature functions includes a word-set feature function and wherein the word-set feature function is true when the first word set has a first subset of unordered words therein and at least one of the target language candidate word sets has a second set of unordered words therein.

5. The system of claim 1, wherein the plurality of feature functions includes a long distance bigram feature function and wherein the bigram feature function is true when the first word set has a first word and a subsequent second word therein which are separated by no more than a predetermined number of words and at least one of the target language candidate word sets has a third word therein.

6. The system of claim 1, wherein the plurality of feature functions includes a language model feature function and wherein the language model feature function is true when at least one of the target language candidate word sets has at least one of a phrase, a set of unordered words, and a first word and a subsequent second word which are separated by no more than a predetermined number of words.

7. The system of claim 1, wherein the plurality of feature functions includes a spurious target-insertion feature function and wherein the spurious target-insertion feature function is true when the target language candidate word set has at least one word which has no correspondingly related word in the first word set.

8. The system of claim 1, wherein the plurality of feature functions includes a spurious target-deletion feature function and wherein the spurious target-deletion feature function is true when the first word set has at least one word which has no correspondingly related word in the target language candidate word set.

9. The system of claim 1, wherein the plurality of feature functions includes a feature function based on an analysis of the first word set and the target language candidate word set.

10. The system of claim 1, wherein the analysis performed by the feature function is a statistical parsing analysis.

11. The system of claim 1, wherein the plurality of weighting factors respectively corresponding to the plurality of feature functions are selected such that:

##EQU12## where D₁ (λ

) is an objective function, λ

represents the plurality of weighting factors, φ

represents the plurality of feature functions, s_i represents the first word set, T_i represents the second word set, and ^T i is defined such that, ##EQU13## wherein λ

is chosen to maximize D₁ (λ

).

12. The system of claim 1, wherein the plurality of weighting factors respectively corresponding to the plurality of feature functions are selected such that:

##EQU14## where D₂ (λ

) is an objective function, λ

represents the plurality of weighting factors, φ

represents the plurality of feature functions, s_i represents the first word set, T_i represents the second word set, and I_i is defined such that ##EQU15## wherein λ

is chosen to maximize D₂ (λ

).

13. The system of claim 1, wherein the plurality of weighting factors respectively corresponding to the plurality of feature functions are selected such that the plurality of weighting factors maximizes a conditional maximum entropy of the single a posteriori conditional probabilistic model.

14. The system of claim 1, wherein the input means includes means for receiving a spoken word set in the source language and converting the spoken word set into the first word set.

15. The system of claim 1, wherein the input means includes means for receiving a handwritten word set in the source language and converting the handwritten word set into the first word set.

16. The system of claim 1, wherein the input means includes means for receiving a typed word set in the source language and utilizing the typed word set as the first word set.

17. The system of claim 1, wherein the tagging means includes one of a Hidden Markov Model tagger and a decision tree based tagger.

18. The system of claim 1, wherein the source language is a natural language.

19. The system of claim 18, wherein the natural language is English.

20. The system of claim 1, wherein the target language is an artificial language.

21. The system of claim 1, wherein the target language is a natural language which is substantially domain-restricted.

22. The system of claim 20, wherein the artificial language is a computer database query language.

23. The system of claim 22, wherein the computer database query language is adapted to an air travel information system domain.

24. The system according to claim 1, further including parsing means responsive to the tagging means for parsing the tagged first word set so as to at least extract structural information from the tagged first word set, the structural information being employed by the translation means.

25. The system of claim 15, wherein the parsing means includes one of a statistical decision tree based parser and a maximum entropy parser.

26. A method for translating a first word set in a source language into a second word set in a target language, the method comprising the steps of:

(a) storing target language candidate word sets;

(b) forming a single a posteriori conditional probability model which includes a prior model, a plurality of feature functions and a plurality of weighting factors respectively corresponding to the plurality of feature functions;

(c) inputting the first word set;

(d) tagging the input first word set so as to at least substantially reduce non-essential variability in the first word set;

(e) determining which features fire regarding the target language candidate word sets and if at least one of the feature functions fires, multiplying the prior model by the weighting factor corresponding to the feature function to provide a resulting score, and if no feature function fires than multiplying the prior model by one;

(f) evaluating a next target language candidate word set, if available, as in step (e); and

(g) determining a best score from among the resulting scores such that the target language candidate word set having the best score is chosen as the second word set in the target language.

27. A translation model utilized in a translation system for translating a first word set in a source language into a second word set in a target language, the translation model comprising a prior model, a plurality of feature functions and a plurality of weighting factors respectively corresponding to the plurality of feature functions, wherein the translation model is responsive to the first word set and iteratively proceeds through a target language candidate store of candidate word sets and each of the candidate word sets and finds the feature functions which are true with respect to the first word set and the second word set, and then multiplies the prior model by the weighting factors corresponding to the feature functions thereby providing resulting scores, the translation model then providing the best scoring target language candidate word set in accordance with the resulting scores.