Machine translation apparatus and machine translation computer program

• US 20050049851A1
• Filed: 08/13/2004
• Published: 03/03/2005
• Est. Priority Date: 09/01/2003
• Status: Active Grant

• Current Assignee: Advanced Telecommunications Research Institute International
• Original Assignee: Advanced Telecommunications Research Institute International
• Inventors: Sumita, Eiichiro, Watanabe, Taro
• Granted Patent: US 7,925,493 B2
• Time in Patent Office: Days
• US Class Current: 704/2
• CPC Class Codes: G06F 40/45 Example-based machine translation; Alignment

Abstract

A method of machine translation, using a bilingual corpus containing translation pairs each consisting of a sentence of a first language and a sentence of a second language, for translating an input sentence of the first language to the second language, including the steps of: receiving the input sentence of the first language and extracting, from the bilingual corpus, a sentence of the second language forming a pair with a sentence of the first language with highest similarity to the input sentence; applying an arbitrary modification among a plurality of predetermined modifications to the extracted sentence of the second language, and computing likelihood of sentences resulting from the modification; selecting a prescribed number of sentences having high likelihood from among the sentences resulting from the modification; repeating, on each of the sentences selected in the step of selecting, the steps of extracting, computing and selecting, until the likelihood no longer improves; and outputting, as a translation of the input sentence, a sentence having the highest likelihood among the sentences of the second language left at the end of the step of repeating.

Claims

1. A method of machine translation, using a bilingual corpus containing a plurality of translation pairs each consisting of a sentence of a first language and a sentence of a second language, for translating an input sentence of said first language to said second language, comprising the steps of:

receiving the input sentence of said first language and extracting, from said bilingual corpus, a sentence of said second language forming a pair with a sentence of said first language satisfying a prescribed relation with said input sentence;

applying an arbitrary modification among a plurality of predetermined modifications to said extracted sentence of said second language, and computing likelihood of sentences resulting from the modification;

selecting sentences having the likelihood satisfying a prescribed condition from among the sentences resulting from the modification;

repeating, on each of the sentences selected in said step of selecting, said steps of extracting, computing and selecting, until a predetermined termination condition is satisfied; and

outputting, as a translation of said input sentence, a sentence having the likelihood satisfying a predetermined selection condition among the sentences of said second language left at the end of said step of repeating.

2. The method of machine translation according to claim 1, wherein

said extracting step includes the step of receiving the input sentence of said first language, and reading a sentence of said second language forming a pair with a sentence of said first language having a prescribed score representing similarity to said input sentence satisfying a predetermined condition, from said bilingual corpus.

3. The method of machine translation according to claim 2, wherein

said reading step includes

the step of receiving the input sentence of said first language, and computing said score between said input sentence and each sentence of said first language contained in said bilingual corpus,

identifying one or a plurality of sentences of said first language having the highest score computed in said step of computing the score, and

reading, from said bilingual corpus, one or a plurality of sentences of said second language each forming a pair with each of said one or a plurality of sentences of said first language identified in said step of identifying.

4. The method of machine translation according to claim 3, wherein

said step of computing the score includes the steps of

computing a prescribed measure of similarity, using document frequency defined on said input sentence regarding a sentence of said first language contained in said bilingual corpus as a document, between said input sentence and each of the sentences of said first language contained in said bilingual corpus,

computing edit distance between said input sentence and each of the sentences of said first language contained in said bilingual corpus, and

computing said score based on the measure of similarity computed in said step of computing similarity and on the edit distance computed in said step of computing edit distance.

5. The method of machine translation according to claim 4, wherein

said step of computing similarity includes the step of computing a tf/idf criteria P_tf/idf in accordance with the following equation, between each sentence of said first language contained in said bilingual corpus and said input sentence:

$P_{\mathrm{tf}/\mathrm{idf}}<br><br>\left(J_k,J_0\right)=\underset{i;<br><br>J_{0,i}\in <br><br>\text{\hspace{1em}<br><br>}<br><br>J_k}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\frac{\log <br><br>\left(N/d<br><br>f<br><br>\left(J_{0,i}\right)\right)/\log <br><br>\text{\hspace{1em}<br><br>}<br><br>N}{<br><br>J_0<br><br>}$

where J₀ is the input sentence, J_0,i is the i-th word of input sentence J₀, df(J_0,i) is the document frequency for the word J_0,i, J_k is a k-th sentence of said first language (1≦

k≦

N) and N is the total number of translation pairs in the bilingual corpus.

6. The method of machine translation according to claim 5, wherein

said step of computing edit distance includes the step of computing the edit distance dis(J_k, J₀) by performing DP (Dynamic Programming) matching between the input sentence J₀ and a sentence J_k of said first language, and the edit distance dis(J_k, J₀) is determined by the following equation

dis(J_k,J₀)=I(J_k,J₀)+D(J_k,J₀)+S(J_k,J₀)

where k is an integer satisfying 1≦

k≦

N, and I(J_k, J₀), D(J_k, J₀) and S(J_k, J₀) are the number of insertions, deletions and substitutions respectively, necessary for modifying the sentence J₀ to sentence J_k.

7. The method of machine translation according to claim 6, wherein

said step of computing the score of a sentence J_k of the first language in accordance with the equation below, based on the tf/idf criteria P_tf/idf computed in the step of computing said similarity measure and on the edit distance computed in the step of computing edit distance

$\mathrm{score}=\{\begin{array}{c}(1.0-\alpha \end{array}$

)⁢

(1.0-dis⁡

(Jk,J0)

J0

)+α

⁢

 

⁢

Ptf/idf⁡

(Jk,J0)(if⁢

 

⁢

dis⁡

(Jk,J0)>

0)1.0(otherwise)

where α

is a tuning parameter, and

selecting, as said initial candidate, a predetermined number of translations in order from one having the highest score computed in said step of computing the score.

8. The method of machine translation according to claim 7, further comprising the steps of:

determining whether a sentence having said score of 1 exists among the sentences of said first language read in said step of reading; and

in response to a determination in said step of determining that a sentence having the score of 1 exists, outputting said sentence of said first language having the score of 1 as a translation of said input sentence.

9. The method of machine translation according to claim 8, further comprising the step of

in response to a determination in said step of determining that a sentence of the first language having the score of 1 exists, stopping execution of said step of repeating said steps of extracting, computing and selecting on each of the sentences selected in said step of selecting and execution of said step of outputting.

10. The method of machine translation according to claim 1, wherein

said step of selecting includes the step of selecting a prescribed number of sentences having highest likelihood, from among the sentences resulting from said modification.

11. The method of machine translation according to claim 1, wherein

said step of repeating includes the step of repeating, on each of the sentences selected in said step of selecting, said steps of extracting, computing and selecting, until likelihood of the sentence selected in said step of selecting no longer improves.

12. The method of machine translation according to claim 1, wherein

said step of outputting includes the step of

outputting as a translation of said input sentence, a sentence having the highest likelihood among the sentences of the second language left at the end of said step of repeating.

13. The method of machine translation according to claim 1, used in conjunction with a language model of said second language and a translation model from said first language to said second language;

wherein

said step of computing likelihood includes the step of applying an arbitrary modification among a plurality of predetermined modifications to said extracted sentence of said second language, and computing likelihood of sentences resulting from the modification, using said language model and said translation model.

14. A recording medium recording a machine translation computer program causing, when executed by a computer, the computer to perform a method of machine translation using a bilingual corpus containing a plurality of translation pairs each consisting of a sentence of a first language and a sentence of a second language, for translating an input sentence of said first language to said second language, said method including the steps of:

receiving the input sentence of said first language and extracting, from said bilingual corpus, a sentence of said second language forming a pair with a sentence of said first language satisfying a prescribed relation with said input sentence;

applying an arbitrary modification among a plurality of predetermined modifications to said extracted sentence of said second language, and computing likelihood of sentences resulting from the modification;

selecting sentences having the likelihood satisfying a prescribed condition from among the sentences resulting from the modification;

repeating, on each of the sentences selected in said step of selecting, said steps of extracting, computing and selecting, until a predetermined termination condition is satisfied; and

outputting, as a translation of said input sentence, a sentence having the likelihood satisfying a predetermined selection condition among the sentences of said second language left at the end of said step of repeating.

15. The recording medium according to claim 14, wherein

said extracting step includes the step of receiving the input sentence of said first language, and reading a sentence of said second language forming a pair with a sentence of said first language having a prescribed score representing similarity to said input sentence satisfying a predetermined condition, from said bilingual corpus.

16. The recording medium according to claim 15, wherein

said reading step includes

the step of receiving the input sentence of said first language, and computing said score between said input sentence and each sentence of said first language contained in said bilingual corpus,

identifying one or a plurality of sentences of said first language having the highest score computed in said step of computing the score, and

reading, from said bilingual corpus, one or a plurality of sentences of said second language each forming a pair with each of said one or a plurality of sentences of said first language identified in said step of identifying.

17. The recording medium according to claim 16, wherein

said step of computing the score includes the steps of

computing a prescribed measure of similarity, using document frequency defined on said input sentence regarding a sentence of said first language contained in said bilingual corpus as a document, between said input sentence and each of the sentences of said first language contained in said bilingual corpus,

computing edit distance between said input sentence and each of the sentences of said first language contained in said bilingual corpus, and

computing said score based on the measure of similarity computed in said step of computing similarity and on the edit distance computed in said step of computing edit distance.

18. The recording medium according to claim 17, wherein

said step of computing similarity includes the step of computing a tf/idf criteria P_tf/idf in accordance with the following equation, between each sentence of said first language contained in said bilingual corpus and said input sentence:

$P_{\mathrm{tf}/\mathrm{idf}}<br><br>\left(J_k,J_0\right)=\underset{i;<br><br>J_{0,i}\in <br><br>J_k}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\frac{\log <br><br>\left(N/\mathrm{df}<br><br>\left(J_{0,i}\right)\right)/\log <br><br>\text{\hspace{1em}<br><br>}<br><br>N}{<br><br>J_0<br><br>}$

where J₀ is the input sentence, J_0,i is the i-th word of input sentence J₀, df(J_0,i) is the document frequency for the word J_0,i, J_k is a k-th sentence of said first language (1≦

k≦

N) and N is the total number of translation pairs in the bilingual corpus.

19. The recording medium according to claim 18, wherein

said step of computing edit distance includes the step of computing the edit distance dis(J_k, J₀) by performing DP (Dynamic Programming) matching between the input sentence J₀ and a sentence J_k of said first language, and the edit distance dis(J_k, J₀) is determined by the following equation

dis(J_k,J₀)=I(J_k,J₀)+D(J_k,J₀)+S(J_k,J₀)

where k is an integer satisfying 1≦

k≦

N, and I(J_k, J₀), D(J_k, J₀) and S(J_k, J₀) are the number of insertions, deletions and substitutions respectively, necessary for modifying the sentence J₀ to sentence J_k.

20. The recording medium according to claim 19, wherein

said step of computing the score of a sentence J_k of the first language in accordance with the equation below, based on the tf/idf criteria P_tf/idf computed in the step of computing said similarity measure and on the edit distance computed by in the step of computing edit distance

$\mathrm{score}=\{\begin{array}{c}(1.0-\alpha \end{array}$

)⁢

(1.0-dis⁡

(Jk,J0)

J0

)+α

⁢

 

⁢

Ptf/idf⁡

(Jk,J0)(if⁢

 

⁢

dis⁡

(Jk,J0)>

0)1.0(otherwise)

where α

is a tuning parameter, and

selecting, as said initial candidate, a predetermined number of translations in order from one having the highest score computed in said step of computing the score.

21. The recording medium according to claim 20, wherein said method further includes the steps of:

determining whether a sentence having said score of 1 exists among the sentences of said first language read in said step of reading; and

in response to a determination in said step of determining that a sentence having the score of 1 exists, outputting said sentence of said first language having the score of 1 as a translation of said input sentence.

22. The recording medium according to claim 21, wherein said method further includes the step of

in response to a determination in said step of determining that a sentence of the first language having the score of 1 exists, stopping execution of said step of repeating said steps of extracting, computing and selecting on each of the sentences selected in said step of selecting and execution of said step of outputting.

23. The recording medium according to claim 14, wherein

said step of selecting includes the step of selecting a prescribed number of sentences having highest likelihood, from among the sentences resulting from said modification.

24. The recording medium according to claim 14, wherein

said step of repeating includes the step of repeating, on each of the sentences selected in said step of selecting, said steps of extracting, computing and selecting, until likelihood of the sentence selected in said step of selecting no longer improves.

25. The recording medium according to claim 14, wherein

said step of outputting includes the step of

outputting as a translation of said input sentence, a sentence having the highest likelihood among the sentences of the second language left at the end of said step of repeating.

26. The recording medium according to claim 14, wherein

said method is used in conjunction with a language model of said second language and a translation model from said first language to said second language;

and

said step of computing likelihood includes the step of applying an arbitrary modification among a plurality of predetermined modifications to said extracted sentence of said second language, and computing likelihood of sentences resulting from the modification, using said language model and said translation model.