Case context: A machine learning engineer is deploying a model and using beam search as an approximate search algorithm to optimize a scoring function, Score_A(S). The algorithm is configured to keep only the top K candidates during the search process. During evaluation, the engineer observes that the system sometimes outputs a candidate that fails to maximize the scoring function.

Question: Based on the properties of approximate search algorithms, explain why the output candidate did not maximize the score, and identify the specific parameter in this search configuration that limits the candidates considered.

Sample answer: The output candidate did not maximize Score_A(S) because beam search is an approximate search algorithm, and such algorithms are not guaranteed to find the value of S that maximizes the scoring function. The parameter limiting the candidates is K, as the algorithm only keeps the top K candidates during the search process, potentially discarding the path to the optimal candidate.

Key points:

• Approximate search algorithms like beam search are not guaranteed to find the output that maximizes Score_A(S).
• Beam search limits the search space by keeping only the top K candidates during the search process.

Rubric: The student must state: 1) Beam search is an approximate search algorithm and is not guaranteed to find the output that maximizes the scoring function. 2) The algorithm limits its search by keeping only the top K candidates.