Bi-phrase filtering for statistical machine translation

• US 8,326,599 B2
• Filed: 04/21/2009
• Issued: 12/04/2012
• Est. Priority Date: 04/21/2009
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Cancedda, Nicola, Dymetman, Marc, Tomeh, Nadi
• Primary Examiner(s): Desir, Pierre-Louis
• Assistant Examiner(s): Sharma, Neeraj
• Application Number:
  US12/427,149
• Publication Number:
  US 20100268527A1
• Time in Patent Office: 1,323 Days
• Field of Search: 704/2, 704/10
• US Class Current: 704/4
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models

Abstract

A computer-implemented system and a method for pruning a library of bi-phrases, suitable for use in a machine translation system are provided. The method includes partitioning a bi-phrase library into a set of sub-libraries. The sub-libraries may be of different complexity such that, when pruning bi-phrases from the plurality of sub-libraries is based on a common noise threshold, a complexity of bi-phrases is taken into account in pruning the bi-phrases.

Claims

1. A method for pruning a library of bi-phrases, comprising:

partitioning a bi-phrase library for use in a machine translation system into a set of sub-libraries, the bi-phrase library including, bi-phrases, each bi-phrase including a source phrase in a source language and a target phrase in a target language which is predicted to be a translation of the source phrase;

for each of at least a plurality of the sub-libraries and for each of a plurality of association score thresholds, with a computer processor, computing values of noise as a function of expected counts and observed counts, where observed counts corresponds to a number of the bi-phrases in the sub-library having an association score above the association score threshold, and expected counts corresponds to a number of bi-phrases in the sub-library having an association score above the association score threshold under an independence hypothesis;

wherein the association score of a bi-phrase represents a statistical dependency between source and target phrases of the bi-phrase and is computed as −

log(p-value) of a contingency table for the bi-phrase, the contingency table including elements which represent a partition of N corpus bi-sentences into bi-sentences that contain both S and T, contain S but not T, contain T but not S, and contain neither S nor T, where N represent a number of bi-sentences in a parallel corpus from which the bi-phrases are extracted, S represents a source phrase of the bi-phrase, T represents a target phrase of the bi-phrase and wherein the p-value is computed from the contingency table using Fisher'"'"'s exact test; and

pruning the plurality of sub-libraries based on a common noise threshold on the noise values, including, for each sub-library, determining an association score pruning threshold corresponding to the common noise threshold, and pruning bi-phrases from the sub-library having an association score which exceeds the association score pruning threshold.

2. The method of claim 1, wherein the association scores under the independence hypothesis are computed by generating a virtual corpus, including randomly associating source and target sentences in a parallel corpus from which the bi-phrase library is extracted.

3. The method of claim 1, wherein the partitioning of the library into sub-libraries includes partitioning based on a measure of complexity of the bi-phrases.

4. The method of claim 3, wherein the complexity is based on at least one of:

a number of words in a bi-phrase;

a number of cepts in a bi-phrase; and

a number of gaps in a bi-phrase as a result of the bi-phrase including at least one non-contiguous phrase.

5. The method of claim 1, wherein the noise is computed for each association score threshold for each of the plurality of sub-libraries as a ratio of expected counts to observed counts.

6. The method of claim 1, wherein the plurality of association score thresholds comprises at least 3 association score thresholds.

7. The method of claim 1, wherein the plurality of sub-libraries comprises at least 3 sub-libraries.

8. The method of claim 1, further comprising, determining the common noise threshold by pruning a plurality of sub-libraries with a plurality of noise thresholds and selecting one of the plurality of noise thresholds as the common noise threshold based on at least one of:

a) a number of bi-phrases remaining in the bi-phrase library after pruning, and

b) a translation quality score computed on translations produced with a machine translation system which employs the bi-phrase library.

9. The method of claim 1, wherein the common noise threshold results in pruning bi-phrases from a first of the sub-libraries which exceed a first association score pruning threshold and pruning bi-phrases from a second of the sub-libraries which exceed a second association score pruning threshold which is higher than the first association score pruning threshold.

10. The method of claim 8, wherein the second sub-library includes bi-phrases of a higher complexity than the first sub-library.

11. A computer program product comprising a non-transitory computer-readable recording medium encoding instructions, which when executed on a computer causes the computer to perform the method of claim 1.

12. An apparatus for pruning bi-phrases comprising memory which stores instructions for performing the method of claim 1 and a processor, in communication with the memory, which executes the instructions.

13. The method of claim 1, wherein the set of sub-libraries comprises between 2-100 sub-libraries.

14. The method of claim 1, wherein the plurality of sub-libraries comprises up to 10 sub-libraries.

15. The method of claim 1, wherein the determining of the association score pruning threshold corresponding to the common noise threshold comprises generating a set of plots relating the noise level to the association score, one plot for each sub-library, and applying the common noise threshold to each plot, each association score pruning threshold corresponding to the common noise threshold.

16. The method of claim 13, wherein the set of sub-libraries comprises up to 10 sub-libraries.