Page 87 -
P. 87
45 General form of Optimization Verification
test
You can apply the Optimization Verification test when, given some input x, you know how to
compute Score (y) that indicates how good a response y is to an input x. Furthermore, you
x
are using an approximate algorithm to try to find arg max Score (y), but suspect that the
y x
search algorithm is sometimes failing to find the maximum. In our previous speech
recognition example, x=A was an audio clip, and y=S was the output transcript.
Suppose y* is the “correct” output but the algorithm instead outputs y . Then the key test is
out
to measure whether Score (y*) > Score (y ). If this inequality holds, then we blame the
x x out
optimization algorithm for the mistake. Refer to the previous chapter to make sure you
understand the logic behind this. Otherwise, we blame the computation of Score (y).
x
Let’s look at one more example. Suppose you are building a Chinese-to-English machine
translation system. Your system works by inputting a Chinese sentence C, and computing
some Score (E) for each possible translation E. For example, you might use Score (E) =
C C
P(E|C), the probability of the translation being E given that the input sentence was C.
Your algorithm translates sentences by trying to compute:
However, the set of all possible English sentences E is too large, so you rely on a heuristic
search algorithm.
Suppose your algorithm outputs an incorrect translation E rather than some correct
out
translation E*. Then the Optimization Verification test would ask you to compute whether
Score (E*) > Score (E ). If this inequality holds, then the Score (.) correctly recognized E*
C C out C
as a superior output to E ; thus, you would attribute this error to the approximate search
out
algorithm. Otherwise, you attribute this error to the computation of Score (.).
C
It is a very common “design pattern” in AI to first learn an approximate scoring function
Score (.), then use an approximate maximization algorithm. If you are able to spot this
x
pattern, you will be able to use the Optimization Verification test to understand your source
of errors.
Page 87 Machine Learning Yearning-Draft Andrew Ng
