TRANSLATION SYSTEM COMBINING HIERARCHICAL AND PHRASE-BASED MODELS

• US 20120041753A1
• Filed: 08/12/2010
• Published: 02/16/2012
• Est. Priority Date: 08/12/2010
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Dymetman, Marc
• Granted Patent: US 8,543,374 B2
• Time in Patent Office: Days
• US Class Current: 704/4
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models

Abstract

A method comprises: receiving or generating bi-content including source content in a source language or format and corresponding target content in a target language or format, wherein the target language or format is different from the source language or format; generating a source weighted finite state automaton representing the source content of the bi-content; generating a target weighted finite state automaton representing the target content of the bi-content; and computing a bilateral intersection between (i) the source weighted finite state automaton, (ii) a synchronous weighted context-free grammar comprising synchronized grammars for the source language or format and the target language or format, and (iii) the target weighted finite state automaton to generate an enriched synchronous weighted context free grammar.

Claims

1. A method comprising:

receiving or generating bi-content including source content in a source language or format and corresponding target content in a target language or format, wherein the target language or format is different from the source language or format;

generating a source weighted finite state automaton representing the source content of the bi-content;

generating a target weighted finite state automaton representing the target content of the bi-content; and

computing a bilateral intersection between (i) the source weighted finite state automaton, (ii) a synchronous weighted context-free grammar comprising synchronized grammars for the source language or format and the target language or format, and (iii) the target weighted finite state automaton to generate an enriched synchronous weighted context-free grammar;

wherein the generating of the source and target weighted finite state automata and the computing of the bilateral intersection are performed by a digital processor.

2. The method as set forth in claim 1, wherein:

the bi-content includes source natural language content in a first natural language and corresponding target natural language content in a second natural language different from the first natural language, and

the synchronous weighted context-free grammar comprises synchronized grammars for the source natural language and the target natural language.

3. The method as set forth in claim 2, wherein:

the target natural language content comprises a plurality of candidate target natural language translations of the source natural language content, and

the target weighted finite state automaton represents a plurality of candidate target natural language translations as paths of the weighted finite state automaton having path weights indicative of the target natural language translation likelihoods.

4. The method as set forth in claim 3, wherein the receiving or generating of the bi-content comprises:

generating the target natural language content by applying a phrase-based translation model to the source natural language content wherein the phrase-based translation model references a database of bi-phrases each comprising a phrase in the source natural language and its translation in the target natural language.

5. The method as set forth in claim 4, wherein the target weighted finite state automaton comprises a σ

-automaton having edges decorated with;

tokens of the target natural language content generated by applying the phrase-based translation model to the source natural language content, and

tokens of a powerset of tokens of the source language content.

6. The method as set forth in claim 4, further comprising:

performing a hierarchical translation of the source language content using the enriched synchronous weighted context-free grammar;

wherein the performing of the hierarchical translation is also performed by the digital processor.

7. The method as set forth in claim 3, wherein the target weighted finite state automaton comprises a σ

-automaton having edges decorated with;

tokens of the target natural language content, and

tokens of a powerset of tokens of the source language content.

8. The method as set forth in claim 3, wherein the computing comprises:

omitting from the bilateral intersection any term associating first and second tokens of the source natural language content with first and second tokens in the target weighted finite state automaton for which a symmetric difference between the target weighted finite state automaton and the set of tokens between the first and second tokens in the source natural language content has cardinality larger than a selected threshold value.

9. The method as set forth in claim 3, further comprising:

performing a hierarchical translation of the source language content using the enriched synchronous weighted context-free grammar to generate at least one proposed translation for the source language content; and

displaying the at least one proposed translation for the source language content.

10. The method as set forth in claim 1, wherein:

the computing does not include computing a unilateral intersection between the source weighted finite state automaton and the synchronous weighted context-free grammar, and

the computing does not include computing a unilateral intersection between the synchronous weighted context-free grammar and the target weighted finite state automaton.

11. The method as set forth in claim 1, wherein the computing comprises computing the bilateral intersection using a bottom-up process comprising:

initializing the bilateral intersection as an empty set of grammar rules; and

adding grammar rules to the bilateral intersection that satisfy the source weighted finite state automaton, the synchronous weighted context-free grammar, and the target weighted finite state automaton, and that further are productive grammar rules capable of producing bi-content including terminal elements in both the source language or format and the target language or format.

12. An apparatus comprising:

a digital processor configured to perform a method operating on bi-content including source content in a source language or format and corresponding target content in a target language or format different from the source language or format, the method including;

generating a source weighted finite state automaton representing the source content of the bi-content,

generating a target weighted finite state automaton representing the target content of the bi-content, and

generating an enriched synchronous weighted context-free grammar by computing a bilateral intersection between (i) the source weighted finite state automaton, (ii) a synchronous weighted context-free grammar comprising synchronized grammars for the source language or format and the target language or format, and (iii) the target weighted finite state automaton.

13. The apparatus as set forth in claim 12, wherein the bi-content includes source natural language content in a first natural language and corresponding target natural language content in a second natural language different from the first natural language, the synchronous weighted context-free grammar comprises synchronized grammars for the source natural language and the target natural language, and the method performed by the digital processor further comprises:

generating the target natural language content by applying a phrase-based translation model to the source natural language content wherein the phrase-based translation model references a database of bi-phrases each comprising a phrase in the source natural language and its translation in the target natural language;

wherein the generating of the target weighted finite state automaton includes representing the plurality of target natural language translations as paths of the target weighted finite state automaton having path weights indicative of the target natural language translation likelihoods.

14. The apparatus as set forth in claim 13, wherein the generating of the target weighted finite state automaton comprises:

generating the target weighted finite state automaton as a σ

-automaton having edges decorated with;

tokens of the target natural language content generated by applying the phrase-based translation model to the source natural language content, and

tokens of a powerset of tokens of the source language content.

15. The apparatus as set forth in claim 13, wherein the apparatus comprises a natural language translation apparatus and the method performed by the digital processor further comprises:

performing a hierarchical translation of the source language content using the enriched synchronous weighted context-free grammar.

16. The apparatus as set forth in claim 13, wherein the computing of the bilateral intersection comprises:

omitting from the bilateral intersection any term associating first and second tokens of the source natural language content with first and second tokens in the target weighted finite state automaton for which a symmetric difference between the target weighted finite state automaton and the set of tokens between the first and second tokens in the source natural language content has cardinality larger than a selected threshold value.

17. The apparatus as set forth in claim 12, wherein:

the computing of the bilateral intersection does not include computing a unilateral intersection between the source weighted finite state automaton and the synchronous weighted context-free grammar, and

the computing of the bilateral intersection does not include computing a unilateral intersection between the synchronous weighted context-free grammar and the target weighted finite state automaton.

18. A storage medium storing instructions executable by a digital processor to perform a method operating on bi-content including source content in a source language or format and corresponding target content in a target language or format different from the source language or format, the method including generating a source weighted finite state automaton representing the source content of the bi-content, generating a target weighted finite state automaton representing the target content of the bi-content, and enriching a synchronous weighted context-free grammar comprising synchronized grammars for the source language or format and the target language or format by computing a bilateral intersection between the source weighted finite state automaton, the synchronous weighted context-free grammar, and the target weighted finite state automaton.

19. The storage medium as set forth in claim 18, wherein the instructions are executable by a digital processor to perform a method operating on bi-content including source content in a source natural language and corresponding target content in a target natural language different from the source natural language, the method including generating a source weighted finite state automaton representing the source content of the bi-content, generating a target weighted finite state automaton representing the target content of the bi-content, and enriching a synchronous weighted context-free grammar comprising synchronized grammars for the source natural language and the target natural language by computing a bilateral intersection between the source weighted finite state automaton, the synchronous weighted context-free grammar, and the target weighted finite state automaton.

20. The storage medium as set forth in claim 19, wherein the instructions are further executable by the digital processor to generate the target natural language content by applying a phrase-based translation model to the source natural language content wherein the phrase-based translation model references a database of bi-phrases each comprising a phrase in the source natural language and its translation in the target natural language.

21. The storage medium as set forth in claim 20, wherein the instructions are executable by the digital processor to generate the target weighted finite state automaton comprising a σ

-automaton having edges decorated with both tokens of the target natural language content generated by applying the phrase-based translation model to the source natural language content and tokens of a powerset of tokens of the source language content.