Google

A search algorithm problem occurs when the scoring function assigns a higher score to the correct output, but the approximate search algorithm still selects the wrong output. This indicates that improving the search algorithm, such as increasing beam width in beam search, is the right focus.

Search Algorithm Problem in Inference

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)

When ScoreA(S*) > ScoreA(Sout) but the algorithm outputs Sout, what is the diagnosis?

True or False: Increasing beam width is a reasonable fix for a search algorithm problem.

A search algorithm problem occurs when the scoring function ranks the correct output higher, but the _____ still selects the wrong output.

Match each score comparison outcome to its diagnostic conclusion. for Search Algorithm Problem in Inference

Order the steps of diagnosing a search algorithm problem using the Optimization Verification test.

Question:
In your own words, explain why a system can still output Sout even when the scoring function ScoreA gives a higher score to S* than to Sout. What does this reveal about the roles of the scoring function versus the search algorithm?

Sample answer:
The scoring function ScoreA is only responsible for ranking possible outputs; it does not itself select the final output. The search algorithm (e.g., beam search) is an approximate method that searches over the space of possible outputs to find the one that maximizes ScoreA(S). Because it is approximate, it can fail to find the true maximum and instead settle on Sout, even though S* would have scored higher. This shows that a well-designed scoring function is not sufficient for correct behavior; the search procedure must also be capable of finding the output that the scoring function actually favors.

Key points:
- Scoring function ranks outputs but doesn't select the final one
- Search algorithm is approximate and can fail to find the true maximum
- ScoreA(S*) > ScoreA(Sout) rules out an objective/scoring problem
- The failure is attributed to the search procedure, not the scorer

Rubric:
Full credit: clearly distinguishes the role of the scoring function from the search algorithm and explains the failure as a search limitation, not a scoring limitation. Partial credit: mentions one of the two roles but not the distinction. No credit: does not address the two components or misattributes the failure to the scorer.

Explain why a higher scoring function value for S* does not guarantee the system will output S*.

Case context:
A machine translation team built a system with an RNN encoder-decoder producing ScoreA(S) and a beam search that outputs the sentence Sout. For a batch of mistranslated sentences, they computed ScoreA(S*) for the human-generated reference and ScoreA(Sout) for the system's output. In the majority of these error cases, ScoreA(S*) turned out to be greater than ScoreA(Sout).

Question:
Given this pattern across the error cases, what should the team conclude, and what should they try next to address the errors?

Sample answer:
Since ScoreA(S*) is greater than ScoreA(Sout) in most of the error cases, this indicates a search algorithm problem: the scoring function is correctly ranking the human translation higher, but beam search is failing to find the value of S that maximizes ScoreA(S). The team should focus their efforts on improving the search algorithm rather than the scoring function, for example by increasing the beam width used in beam search.

Key points:
- Pattern of ScoreA(S*) > ScoreA(Sout) indicates a search algorithm problem
- The scoring function is functioning correctly in this scenario
- Effort should be focused on the search algorithm, not the scorer
- Increasing beam width is a concrete suggested fix

Rubric:
Full credit: correctly identifies the pattern as a search algorithm problem and recommends improving search (e.g., wider beam width), not the scorer. Partial credit: identifies the correct diagnosis but omits the recommended action, or vice versa. No credit: misdiagnoses the issue as an objective/scoring function problem.

Diagnose the beam search failure in a translation system.

Question:
In one to three sentences, explain why the system can still output Sout as an error even when ScoreA correctly ranks S* above Sout.

Sample answer:
Because beam search is only an approximate search algorithm, it isn't guaranteed to find the output that truly maximizes ScoreA(S). Even though the scoring function correctly rates S* higher, the search process can settle on the lower-scoring Sout instead.

Key points:
- Beam search is an approximate algorithm
- It is not guaranteed to find the true maximum of ScoreA(S)
- The scoring function itself is not at fault in this case

Rubric:
Full credit: mentions that beam search/search algorithm is approximate and can fail to find the true maximizer despite correct scoring. Partial credit: vague reference to search failure without connecting it to approximation. No credit: blames the scoring function.

Learn Before

Related