Google

A scored inference system may compute a score for each possible output but still need an approximate search algorithm to find a high-scoring output, because exhaustive enumeration can be far too large. These approximate algorithms are not guaranteed to find the output that maximizes the score.

Approximate Search in Scored 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)

Beam search is an example of an approximate search algorithm that keeps only the top K candidates during the search process. Because it is approximate, it is not guaranteed to find the output that maximizes the score.

Beam Search as Approximate Inference Search

Why can't a scored inference system exhaustively enumerate all possible output sentences to find the highest-scoring one?

True or False: Approximate search algorithms used in scored inference are guaranteed to find the output that maximizes the score function.

Because exhaustively enumerating all possible outputs is infeasible, a scored inference system must apply a(n) _____ algorithm to find a high-scoring output.

Why must a scored inference system use approximate search rather than exhaustively enumerating all possible output sentences?

Approximate search algorithms used in scored inference are guaranteed to find the output S that maximizes Score_A(S).

In a scored inference system, the formal search objective is to compute the _____ of Score_A(S) over all possible output sentences S.

Match each term to its role in a scored inference system for speech recognition.

Order the steps a scored inference system follows to produce a transcription from an audio clip.

What does the quantity P(S|A) represent when used as Score_A(S) in a scored speech recognition system?

For a vocabulary of 50,000 words, there are (50,000)^N possible output sentences of exactly length N.

Approximate search algorithms are _____ to find the output that maximizes the score function, yet they make search computationally tractable.

Match each challenge in scored inference to the concept that best characterizes it.

Order the reasoning steps that build the argument for why approximate search is necessary in scored inference.

Question:
In a scored inference system, such as a speech recognition system that scores possible output sentences S given an audio input A, we must find the sentence S that maximizes ScoreA(S). Explain why exhaustive enumeration of all possible sentences is computationally impractical, and analyze the consequence of using an approximate search algorithm instead.

Sample answer:
Exhaustive enumeration is computationally impractical because the number of possible output sentences grows exponentially with sentence length. For example, with a vocabulary of 50,000 words, there are (50,000)^N possible sentences of length N, which is far too large to evaluate. To make this tractable, we must use an approximate search algorithm to search for the output S that optimizes ScoreA(S). The major limitation of this approach is that approximate search algorithms are not guaranteed to find the actual value of S that maximizes the score function.

Key points:
- Exhaustive search is infeasible due to the exponential growth of the sentence search space (e.g., 50,000^N).
- Approximate search is required to make finding high-scoring outputs computationally tractable.
- Approximate search algorithms do not guarantee finding the output S that maximizes ScoreA(S).

Rubric:
The answer should address two parts: 1) the exponential growth of the search space (e.g., vocabulary size raised to the power of N) that makes exhaustive search infeasible, and 2) the fact that approximate search algorithms are necessary for computational tractability but do not guarantee finding the score-maximizing output.

Explain the computational challenge and theoretical limitation of search in a scored inference system.

Case context:
You build a speech recognition system that inputs audio clip A and computes ScoreA(S) = P(S|A). Because exhaustively enumerating all (50,000)^N sentences of length N is impossible, you implement an approximate search algorithm to find the arg max of ScoreA(S). During an evaluation, the system outputs transcription S_approx. However, a manual check reveals that a different English transcription, S_better, has a higher computed score (ScoreA(S_better) > ScoreA(S_approx)).

Question:
Diagnose why the system returned S_approx instead of S_better. What does this reveal about the approximate search algorithm's guarantees?

Sample answer:
The system returned S_approx instead of S_better because the approximate search algorithm failed to find the sentence that maximizes ScoreA(S). This reveals that the approximate search algorithm is not guaranteed to find the true score-maximizing output, even when a higher-scoring output exists in the search space.

Key points:
- The approximate search algorithm failed to find the score-maximizing transcription.
- Approximate search algorithms are not guaranteed to find the output that maximizes ScoreA(S).
- The higher-scoring transcription S_better was missed due to search approximation rather than scoring error.

Rubric:
The response must explain that: 1. The approximate search algorithm failed to identify the optimal output S_better despite it having a higher score. 2. This behavior is due to the inherent limitation of approximate search algorithms, which do not guarantee finding the absolute maximum of the score function.

Diagnose search suboptimality in a scored speech recognition system using approximate search.

Question:
What is the primary trade-off we make when we apply an approximate search algorithm rather than exhaustive enumeration to optimize ScoreA(S)?

Sample answer:
We trade the mathematical guarantee of finding the absolute maximum of ScoreA(S) for computational tractability, allowing us to process large search spaces that are otherwise too large to exhaustively enumerate.

Key points:
- Loss of the guarantee to find the output that maximizes ScoreA(S).
- Gain of computational tractability/feasibility in large output spaces.

Rubric:
The student's answer must identify that we sacrifice the guarantee of finding the optimal output (the value of S that maximizes the score) in order to achieve computational tractability.

Learn Before

Related