新手语音入门(一)：认识词错率WER与字错率CER ｜ 编辑距离 ｜ 莱文斯坦距离 ｜ 动态规划

词错率（Word Error Rate, WER）是一项用于评价ASR性能的重要指标，用来评价预测文本与标准文本之间错误率，因此词错率最大的特点是越小越好。像英语、阿拉伯语语音转文本或语音识别任务中研究者常用WER衡量ASR效果好坏。

因为英文语句中句子的最小单位是单词，而中文语句中的最小单位是汉字，因此在中文语音转文本任务或中文语音识别任务中使用字错率（Character Error Rate, CER）来衡量中文ASR效果好坏。

两者计算方式相同，为行文统一，下文统一使用WER表示该性能。

它们的计算公式是：

W E R = S + D + I N = S + D + I S + D + C WER = \frac{S + D + I}{N} = \frac{S+D+I}{S+D+C} WER=NS+D+I​=S+D+CS+D+I​

假设有一个参考例句Ref和一段ASR系统转写语音后生成的预测文本Hyp。带入上面公式，S表示将Hyp转化为Ref时发生的替换数量，D表示将Hyp转化为Ref时发生的替换数量，I代表将Hypo转化为Ref时发生的插入数量，N代表Ref句子中总的字数或者英文单词数。C代表Hyp句子中识别正确的字数。即原参考句子总字数N = S+ D + C。

再说一句，根据维基百科里面的说法，N就是原样例文本总的字数。

举例1:

标准文本为“你吃了吗”，转写结果为“你吃了么”，上例发生了一次错误替换，Hyp将“吗”替换成了么，即S=1,D=0, I =0, 参考文本字数N=4, 因此本次转写结果WER= 1/4 = 25%.

举例2:

预测文本为“你吃了”，相比标准文本错误删除1个“吗”，即S=0,D=1,I=0,N=4,因此本次转写结果WER = 1/4 = 25%。

举例3：

举例3中，Hyp文本相比标准文本错误插入了一个“啊”，即S=0，D=0，I =1，N=6，因此字错率WER= 1/6 = 16.7%。

在参考文本给出的情况下，N可以很轻易统计出来，而编辑数量 S + I + D S+I+D S+I+D的计算我们通过编辑距离的引入来计算。

编辑距离，由前苏联数学家弗拉基米尔·莱温斯坦在1965年提出，通过计算两个字符串互相转换所需要的最小编辑数来描述两个字符串的差异，编辑操作包括替换，删除，插入。编辑距离也叫莱温斯基距离，当前被广泛用于字错率计算，DNA序列比对，拼写检测等领域。

编辑距离就等同于上文所述的 S + D + I S+D+I S+D+I。

编辑距离的公式为：

l e v a , b ( i , j ) = { m a x ( i , j ) if min( i , j )=0 m i n   { l e v a , b ( i − 1 , j ) + 1 , l e v a , b ( i , j − 1 ) + 1 , l e v a , b ( i − 1 , j − 1 ) + w a i ≠ b j otherwise lev_{a,b}(i, j) = \begin{cases} max(i,j) & \text{if min($i$,$j$)=0}\\ min \ \begin{cases} lev_{a,b}(i-1,j) + 1, \\ lev_{a,b}(i,j-1) + 1, \\ lev_{a,b}(i-1, j-1) + w_{a_i \neq b_j}\\ \end{cases} & \text{otherwise} \end{cases} leva,b​(i,j)=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​max(i,j)min ⎩⎪⎪⎨⎪⎪⎧​leva,b​(i−1,j)+1,leva,b​(i,j−1)+1,leva,b​(i−1,j−1)+wai​=bj​​​​if min(i,j)=0otherwise​

其中 w w w为指示函数，当 a i ≠ b j a_{i} \neq b_{j} ai​=bj​时，其值为1；当 a i = a j a_i = a_j ai​=aj​时，其值为0。

作为一个新手，直接看这个公式，可能不明所以。但是如果可以用一个矩阵来表示这个公式，并自己在纸上推导一遍，回过头来再看这个公式就会相对比较容易理解。 可以参考2.2示例。

假设我们有两个词，horse和ros，需要计算他们俩的编辑距离。我们假设horse是参考例句Ref，而ros是预测文本Hyp, 现在计算ros转换为horse所需要的最少操作数，即它俩的编辑距离。

参考Leetcode问题#71

我们首先定义一个距离矩阵，并且命名为cache。矩阵的行数为ros字符长度+1， 矩阵的列数为horse字符长度+1，因此cache为一个4✖️6的矩阵。下文中用i表示行数，用j表示列数。

矩阵大概长这个样子：

多出来的一行和一列给了null。而矩阵中的每个元素将保存当前位置之前字符的互相转换所需要的操作数。例如cache[2][3]表示ro转换成为hor所需要的最小操作数。

如果可以得到最右下角的矩阵元素的值，那么就可以得到ros和horse之间互相转换所需要的编辑数。

因为我们可以较为容易的计算出来null转换为null或null转换为任何字符所需要的操作数，例如null转换成null的操作数为0,即cache[0][0]=0；null转换为h的操作数为1,即cache[0][1]=1，null转换为ho的操作数为2,即cache[0][2]=2。null转换为hor、hors、horse的操作数分别为3、4、5。

因此可以得到距离矩阵：

同时可以发现一种模式，当i=0, cache[i][j] = j,

同理，竖列r、ro、ros转换为null的操作数分别为1、2、3，即分别删除1、2、3个字符。

得到以下距离矩阵：

并发现，当j=0, cache[i][j] = i。

计算距离矩阵中剩余的部分，我们首先定义两个矩阵规则，

当 r ≠ c r \neq c r=c时，右下角的矩阵值为周边三个值最小值+1：

当 r = c r = c r=c时，右下角的矩阵值为左上角对角矩阵的值。

对于未填满的左上角第一个元素，r需要转换为h，根据上面第一种情况，周边三个值最小值+1，即0+1=1， 因此距离矩阵如下图：

按照上述两个规则我们可以填满距离矩阵：

得到右下角的值即ros转换成为horse的最小编辑数，即ros和horse的编辑距离为3。

这时，我们可以用公式语言描述上述两个规则：

当 r ≠ c r \neq c r=c时，右下角的矩阵值为周边三个值最小值+1：

c a c h e [ i ] [ j ] = 1 + m i n { c a c h e [ i ] [ j − 1 ] Insert c a c h e [ i − 1 ] [ j ] Remove c a c h e [ i − 1 ] [ j − 1 ] Replace cache[i][j] = 1 + min \begin{cases} cache[i][j-1] & \text{Insert}\\ cache[i-1][j] & \text{Remove}\\ cache[i-1][j-1] & \text{Replace}\\ \end{cases} cache[i][j]=1+min⎩⎪⎪⎨⎪⎪⎧​cache[i][j−1]cache[i−1][j]cache[i−1][j−1]​InsertRemoveReplace​

当 r = c r = c r=c时，右下角的矩阵值为左上角对角矩阵的值:

c a c h e [ i ] [ j ] = c a c h e [ i − 1 ] [ j − 1 ]                Do Nothing cache[i][j] = cache[i-1][j-1] \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{Do Nothing} cache[i][j]=cache[i−1][j−1]               Do Nothing

现在我们可以将上述计算过程再用合并一下：

c a c h e [ i ] [ j ] = { m a x ( i , j ) if min( i , j )=0 1 + m i n   { c a c h e [ i − 1 ] [ j ] ;  Remove c a c h e [ i ] [ j − 1 ] ;  Insert c a c h e [ i − 1 ] [ j − 1 ] ;  Replace  word1[i] ≠  word2[j] c a c h e [ i − 1 ] [ j − 1 ] word1[i] = word2[j] cache[i][j] = \begin{cases} max(i,j) & \text{if min($i$,$j$)=0}\\ 1+min \ \begin{cases} cache[i-1][j]; \ \text{Remove} \\ cache[i][j-1]; \ \text{Insert} \\ cache[i-1][j-1]; \ \text{Replace} \\ \end{cases} & \text{ word1[i]$\neq$ word2[j]} \\ cache[i-1][j-1] & \text{word1[i] = word2[j]} \end{cases} cache[i][j]=⎩⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎧​max(i,j)1+min ⎩⎪⎪⎨⎪⎪⎧​cache[i−1][j]; Removecache[i][j−1]; Insertcache[i−1][j−1]; Replace​cache[i−1][j−1]​if min(i,j)=0 word1[i]= word2[j]word1[i] = word2[j]​

不难发现这个公式就是来温斯坦公式，同时也是通过动态规划方法计算编辑距离的状态方程。

使用Python代码实现：

如果将上述字符换成汉字或是单词，再计算两句话的 S + D + I S+D+I S+D+I的值，就很容易计算WER了。