Attributing Errors in MT Search

Exhaustive vs. Heuristic Search in MT

Relying on _____ Search

MT Optimization Verification Outcomes

Steps of the MT Verification Test

Question:
Explain why the Optimization Verification test is necessary in machine translation. Describe the two main components of the system that the test evaluates and how it distinguishes between their failures.

Sample answer:
In machine translation, the set of all possible English sentences is too large to score exhaustively, so systems use both a scoring function to evaluate translations and a heuristic search algorithm to find high-scoring sentences. When the system outputs an incorrect translation, the Optimization Verification test is necessary to pinpoint which component failed. It does this by comparing the score of the correct translation to the score of the incorrect output. If the correct translation has a higher score, the scoring function worked, but the search algorithm failed to find it. If the incorrect output has a higher or equal score, the scoring function is at fault for ranking the bad translation higher.

Key points:
- Identifies the scoring function and heuristic search algorithm.
- Explains that heuristic search is needed due to the massive set of possible translations.
- Describes the condition where the search algorithm is blamed (Score(E*) > Score(Eout)).
- Describes the condition where the scoring function is blamed (Score(E*) <= Score(Eout)).

Rubric:
The essay should identify the two main components (scoring function and heuristic search), explain why heuristic search is used (large search space), and detail the logic of comparing the scores of the correct and incorrect translations.

Analyzing MT Optimization Verification

Case context:
You are building a Chinese-to-English machine translation system. Your system outputs an incorrect translation Eout instead of the correct translation E*. You run the Optimization Verification test and find that the score computed for E* is actually lower than the score computed for Eout.

Question:
Based on this finding, what component of your machine translation system should you diagnose and improve, and what is the underlying reasoning?

Sample answer:
I should diagnose and improve the score computation component. Because the score for the correct translation E* was lower than the incorrect translation Eout, the scoring function failed to recognize E* as the superior output. The search algorithm cannot be blamed because even if it had found E*, the scoring function would still have preferred Eout.

Key points:
- Identifies the score computation as the component to fix.
- Explains that the scoring function ranked the incorrect translation higher.
- Exonerates the search algorithm since it relies on the flawed scoring function.

Rubric:
The response must correctly identify the score computation as the source of the error and provide the reasoning that the scoring function incorrectly ranked the bad output above the true translation.

Diagnosing a Translation Scoring Error

Question:
In a machine translation system using heuristic search, what is the purpose of computing a score, such as Score_C(E), for a possible translation?

Sample answer:
The purpose of computing a score is to evaluate and rank different possible English translations given the Chinese input sentence, helping the system identify which translation is the most likely or optimal.

Key points:
- Evaluates possible translations.
- Ranks or estimates the probability of the translation given the input.

Rubric:
The answer should mention that the score evaluates, ranks, or estimates the probability/quality of possible translations.

Purpose of Score Computation

Identifying the Source of Scoring Errors

Search Algorithm Blame Condition

For machine translation, compute a score for possible translations and use heuristic search because the set of possible English sentences is too large. If the correct translation scores above the system translation, attribute the error to approximate search; otherwise, attribute it to the score computation.

Google

The Optimization Verification test compares the score of a known correct output with the score of the system output. If the correct output scores higher, blame the optimization or search algorithm; otherwise, blame the scoring function computation.

Optimization Verification Test

Machine Learning Yearning, a free ebook from Andrew Ng, teaches you how to structure Machine Learning projects.
https://www.deeplearning.ai/machine-learning-yearning/

Note: The content of the book is aligned with the Coursera Deeplearning.ai specialization.  https://www.deeplearning.ai/deep-learning-specialization/ 

Machine Learning Yearning (Deeplearning.ai)

In practice, apply the Optimization Verification test across errors in the dev set. Each error where the correct output scores higher is marked as an optimization-algorithm error; each error where it does not is counted as a scoring-function error.

Applying Optimization Verification Across Dev Set Errors

A common AI design pattern is to first learn an approximate scoring function and then use an approximate maximization algorithm. Recognizing this pattern lets one use Optimization Verification to understand the source of errors.

Approximate Scoring Function Plus Approximate Maximization Pattern

Optimization Verification for Machine Translation

For a reinforcement learning system whose trajectory is worse than a human pilot trajectory, compare the reward assigned to the human trajectory with the reward assigned to the algorithm trajectory. If the human trajectory scores higher, improving the reinforcement learning algorithm is worthwhile; if it does not, improve the reward function.

Optimization Verification for Reinforcement Learning Reward Functions

Optimization Verification does not require a truly optimal output. If a superior output is available, such as a human pilot trajectory that is better than the current learning algorithm output, the test can still indicate whether improving the optimization algorithm or the scoring function is more promising.

Learn Before

Related

Learn After