# Semantic Features Based N-Best Rescoring Methods for Automatic Speech Recognition
## 4 N-Best Rescoring with Coordination Scores
### Fallibility of Word for ASR Hypothesis  
The n-best hypothesis of ASR result has a trait that given any two hypothesis for the same utterance, the mass of the hypothesis pairs have only a few words that are different, which can be instantiated by the example in the introduction.  
To rerank the hypothesis of the ASR result, we tend to focus on the different words in the hypotheses and ignore the words that exists in every hypothesis. Motivated by this, we introduce the notion of fallibility of word to the rescoring progress to magnify the influence of the words that exists less in similar places in the hypothesis list.  
We first align all the hypothesis pairs for each utterance. For each word in a hypothesis, we collect all the words that correspond to the required word in the aligning results in a set. (Each time the required word aligned with blank, we regard blank as a unique word.) The fallibility of a word in a hypothesis is defined by the number of unique words (namely number of types) for the words that are different from the required word in the set. For example, the fallibility weight for the word \"surged\" in hypothesis 446c040q-2 (presented in the introduction) is 2 as word \"search\" and \"sir\" both correspond to and different from \"surged\". Figure 2 is an example to show how to compute the fallibility.  
The aligning operation can be implemented by the minimum edit distance algorithm [25]. We use \(F(m,n)\) to denote the minimum edit distance for the first \(m\) words and first \(n\) words for the two sentences, \(S_{1}\) and \(S_{2}\). \(F(m,n)\) is computed by \(F(m-1,n)\), \(F(m,n-1)\) or \(F(m-1,n-1)\), each of which represent a way of tagging the present word \(S_{1}(m)\) and word \(S_{2}(n)\):  
\[F(m,n)=min\begin{cases}F(m-1,n)+1\\ F(m,n-1)+1\\ F(m-1,n-1)+\begin{cases}0,ifS_{1}(m)=S_{2}(n)\\ 1,ifS_{1}(m)\
eq S_{2}(n)\end{cases},F(0,n)=n,F(m,0)=m.\end{cases} \tag{17}\]  
\(F(|S1|,|S2|)\) is the final minimum edit distance of the two sentences. We can keep the path by which \(F\) item \(F(m,n)\) is computed and tag each word to distinguish the word to be correct or error.  
Figure 3 is an example of the minimum edit distance algorithm. In this example we align the word \"monkey\" and the word \"money\" by character. The left table is the \(F\) matrix and the bottom right element is the final edit distance for the two words. The right matrix stores the path. For the \((i,j)\)-th element, \"0\", \"1\" and \"2\" mean that \(F(i,j)\) is assigned by \(F(m-1,n)+1\), \(F(m,n-1)+1\) and \(F(m-1,n-1)+0/1\) respectively. From the path matrix, we can label words in hypotheses with \"correct\", \"substitute\" and \"insert\" tags. For example, if the vertical words refer to the reference and the horizontal words refer to hypothesis, \"1\" means that the corresponding word in hypothesis is of \"insert\" tag, and \"2\" means that the word is of \"correct\" tag or \"substitute\" tag, which depends on whether the corresponding words are different. We could not give a word \"delete\" tag in hypothesis, because the \"deleted\" word is not in the hypothesis.  
To emphasize the fallible words, we multiply the word score with the word fallibility score when computing the sentence score.  
Figure 3: An example of the minimum edit distance algorithm. The left sub-figure show the F matrix, which is the minimum edit distance for the sub-sentences. The right sub-figure shows the path matrix, from which we can get the alignment.  
Figure 2: An example of the fallibility.