Automatic construction of conditional exponential models from elementary features

• US 6,304,841 B1
• Filed: 07/29/1997
• Issued: 10/16/2001
• Est. Priority Date: 10/28/1993
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mercer, Robert Leroy, Della Pietra, Vincent Joseph, Della Pietra, Stephen Andrew, Berger, Adam Lee, Brown, Peter Fitzhugh, Lafferty, John David
• Primary Examiner(s): Poinvil, Frantzy
• Application Number:
  US08/902,177
• Time in Patent Office: 1,540 Days
• Field of Search: 705/1-10, 705/257, 704/2, 704/9
• US Class Current: 704/2
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models

Abstract

An apparatus for translating a series of source words in a first language to a series of target words in a second language. For an input series of source words, at least two target hypotheses, each comprising a series of target words, are generated. Each target word has a context comprising at least one other word in the target hypothesis. For each target hypothesis, a language model match score comprises an estimate of the probability of occurrence of the series of words in the target hypothesis. At least one alignment connecting each source word with at least one target word in the target hypothesis is identified. For each source word and each target hypothesis, a word match score comprises an estimate of the conditional probability of occurrence of the source word, given the target word in the target hypothesis which is connected to the source word and given the context in the target hypothesis of the target word which is connected to the source word. For each target hypothesis, a translation match score comprises a combination of the word match scores for the target hypothesis and the source words in the input series of source words.

Claims

1. A computer-implemented method for translating source words using a language translation process, the language translation process using an adjustable model, the method comprising the steps of:

choosing an initial model for the language translation process;

generating, responsive to the source words, an output corresponding to at least one target hypothesis using the language translation process and the initial model;

adjusting the initial model to generate an adjusted model, including the following steps (a)-(j);

(a) providing a set of candidate features exhibited in the output of the language translation process;

(b) providing a sample of data representing the output of the language translation process being modeled;

(c) generating an intermediate model from the initial model of the language translation process;

(d) initializing an active set S of features contained in the intermediate model;

(e) computing scores representing the benefit of adding features to the intermediate model;

(f) selecting one or more features having scores higher than a first given value;

(g) if none of the scores is higher than a second given value, stop;

(h) adding selected features to the set S of active features;

(i) computing a model Ps containing the features in S to be the intermediate model; and

(j) repeating steps (e)-(i) until the stop condition of step (g) is satisfied to determine from the intermediate model an adjusted model; and

translating the source words with the language translation process operating using the adjusted model.

2. The method of claim 1, further comprising:

after step (i), pruning the selected features to a smaller set to eliminate unhelpful features.

3. The method of claim 1, wherein the step of computing the score comprises:

for each candidate feature f, compute the best model containing the features in S and also the feature f; and

computing the exact score of the feature the score representing how useful it would be to add this feature to S.

4. The method of claim 1, wherein the step of computing the score comprises computing for each feature (sequentially) an approximate score of the feature.

5. The method of claim 1, wherein approximate scores for all features are calculated in parallel.

6. The method of claim 1, wherein the step of computing Ps comprises:

initializing λ

_f=0 for all active features S;

repeating until all λ

_f have converged;

compute Λ

λ

_f; and

update λ

_f by Λ

λ

_f.

7. A computer-implemented method for translating source words using a language translation process by constructing and adjusting a model for ordering a string of words in a source language prior to translation to a target language to make the ordering of the words in the source language consistent with conventional word ordering of the target language, comprising the steps of:

choosing an initial model for the language translation and reordering process;

generating, responsive to the source words, an output corresponding to at least one target hypothesis using the language translation and reordering process and the initial model;

adjusting the initial model to generate an adjusted model, including the following steps (a)-(j);

a) providing a set of candidate features exhibited in sample word reorderings of strings of words in the source language;

b) providing a sample of word reorderings of the strings of words in the source language;

c) generating an intermediate model from the initial model of the language translation and reordering process;

d) initializing the active set S of features contained in the intermediate model;

e) computing scores representing the benefit of adding features to the intermediate model;

f) selecting one or more features having scores higher than a first given value;

g) if none of the scores is higher than a second given value, stop;

h) adding selected features to the set S of active features;

i) computing a model Ps containing the features in S to be the intemediate model; and

j) repeating steps (e)-(i) until the stop condition of step (g) is satisfied to determine from the intermediate model an adjusted model; and

translating the source words with the language translation process operating using the adjusted model.

8. The method according to claim 7, further comprising the step of inputting a string of words in the source language;

identifying groups of words that require reordering; and

obtaining a score indicating whether reordering should be performed.

9. An apparatus for translating a series of source words in a first language to a series of target words in a second language different from the first language, said apparatus comprising:

means for inputting said series of source words;

means for generating at least two target hypotheses using a translation process model, each target hypothesis comprising said series of target words selected from a vocabulary of words in the second language, each target word having a context comprising at least one other word in the target hypothesis;

means for generating, for each target hypothesis, a language model match score associated with the translation process model comprising an estimate of the probability of occurrence of the series of words in the target hypothesis;

means for identifying at least one alignment between the input series of source words and each target hypothesis, the alignment connecting each source word with at least one target word in the target hypothesis;

means for generating, for each source word and each target hypothesis, a word match score comprising an estimate of the conditional probability of occurrence of the source word, given the target word in the target hypothesis which is connected to the source word and given the context of the target word in the target hypothesis which is connected to the source word;

means for generating, for each target hypothesis, a translation match score comprising a combination of the word match scores for the target hypothesis and the source words in the input series of source words;

means for generating a target hypothesis match score for each target hypothesis, each target hypothesis match score comprising a combination of the language model match score for the target hypothesis and the translation match score for the target hypothesis;

means for adjusting the translation process model; and

means for outputting the target hypothesis having the best target hypothesis match score.

10. The apparatus of claim 9 wherein the means for adjusting the translation process model iteratively adjusts the translation process model by computing a score representing the benefit of adding at least one of a set of features to the translation process model and by generating an adjusted model having a highest score.