智客公社

标题: 语音辨认算法(ASR)目的评价之编辑间隔下WER计算图解 [打印本页]
作者: ivyshek    时间: 2020-9-20 18:57
标题: 语音辨认算法(ASR)目的评价之编辑间隔下WER计算图解
编辑间隔

字符串的编辑间隔，又称为 Levenshtein间隔，由俄罗斯的数学家Vladimir Levenshtein在1965年提出。是指经过字符间的操作，把字符串A转换成字符串B所需求的最少操作步骤数，普通来说，两个字符串的编辑间隔越小，则它们越相似。其中，字符操作包括：
例如：
Levenshtein 给出了编辑间隔的普通求法，就是经典动态规划成绩。这里给出Levenshtein间隔的性质，设d(x,y)表示字符串x到y的Levenshtein间隔，那么显然：
在自然言语处理中，编辑间隔是一个概念非常重要，例如在词典小程序中：假如用户不小心输错了单词，则可以列出字典里与它的Levenshtein间隔小于某个数N的单词，让用户选择正确的那一个，N通常取到 2或3。
求解编辑间隔

这里需求运用动态规划的思想，动态规划算法通常基于一个递推公式及一个或多个初始形状。 当前子成绩的解将由上一次子成绩的解推出。所以我们首要目的是找到某个形状和一个递推公式。
假设我们可以运用d[ x, y ]个步骤（运用二维数组描画，数组中每个值表示到目前为止两个子字符串的转换需求的操作数），表示将字符串 hyp[1...i] 转换为字符串 ref[ 1…j ] 所需最少步骤数。
为方便了解，我们先假如在最简单的状况下，即在 i=0 时，也就是说字符串hyp 为空，那么要转为对应的 d[0, j] ，hyp需求添加 j 个字符，即需求 j 步，使得hyp转化为ref；异样在 j 等于0时，即字符串ref为空，那么对应的 d[i, 0] 就是hyp删除 i个字符，即需求i步，使得hyp转化为ref。
再进一步，假如我们想要将 hyp[1...i] 经过最少次数的插入、删除、编辑操作转换为 ref[1...j]，存在以下三种状况：
这三种状况是在前一个形状可以以最少次数的添加，删除或者编辑操作，使得如今字符串hyp 和 字符串ref 只需求再停止一次操作或者不停止任何操作就可以完成hyp[1..i]到 ref[1..j]的转换。最后，我们为了保证所需的步骤最少，我们需求从下面三种状况中选择步骤最少的一种作为将 hyp[1..i]转换为 ref[1..j] 所需的最少步骤数—— 即 min(M+1，N+1，Q+temp)，其中 hyp==ref[j]时，temp=0，否则 temp=1。
这样我们就得出递推公式：

levenST[ i ][ j ] = min( levenST[ i-1 ][ j ] + 1, levenST[ i ][ j-1 ] + 1, levenST [i-1 ][ j-1 ] + temp);
递推公式需求三个初始形状，即levenST[i-1][j]， levenST[j-1]和levenST[i-1][j-1]，所以我们需求对数组 levenST[][]事行停止初始化，先求出最简单的形状下的levenshtein间隔。
最后，我们将两个字符串中一切字符都遍历对比完成之后，将hyp转换为ref所需最少步骤数就是d[m][n]。其中m为字符串hyp的长度，n为字符串ref的长度。
图解栗子

ref（reference）表示标注文本序列，hyp（hypothesis）表示预测文本序列，则可以计算 编辑间隔为 3，其中1次交换错误（S），1次删除错误（D），1次插入错误（I）。

[attach]449847[/attach]


1.构造初始化二维数组levenST[6][6]，横轴为ref（标注序列），纵轴为hyp（预测序列）。

[attach]449848[/attach]


2.从字符串HYP的第一个字末尾，依次与REF中的字母（y[1...j]）停止比较，然后得出相应地位levenST[1,j]上的最少转换步骤数，即编辑间隔，假如两个字母相等，则在从此地位的左（i ,j-1）+1，上（i -1,j）+1，左上（i -1,j-1）+0 三个数中获取最小的值写入（因左、上的值不能够低于左上的值，所以可以直接去左上的值）；若不等，则在从此地位的左（i ,j-1），上（i -1,j），左上（i -1,j-1）三个地位中获取最小的值再加上1。如下图，首先对比字符串HYP中第1个汉字"五"和字符串REF中第1个汉字"五"，发现两个汉字相等，所以对比[j]的左、上、左上三个地位的值，取出最小值0存入levenST[1][1]

[attach]449849[/attach]


也就是说当前地位的levenST[1,j]只与相邻的后面三个地位有关，而三个有色方块代表的物理意义如下：
    左上表示交换错误 S 右上表示插入错误 I 左下表示删除错误 D

[attach]449850[/attach]


不断迭代下去，直到矩阵中一切的值都被计算出来之后，整个levenST矩阵右下角的为的值就是你要的编辑间隔了，图中编辑间隔为3。
此外，我们还想知道 I、D、S 到底各占多少，对齐的文本到底是什么样子的，这是我们要从右下角（6，6）回溯。对于右下角的“3”，它的前三个值最小为3，阐明没有发生错误。接上去（5，5）地位，前三个值为4、3、2，最小值为2，选择上方的方格，并记录一次插入错误，再如（2，3），前三个值为1、1、2，最小值为1，阐明发生了错误，这时按照 substitution > insert > delete 的优先级，选择左上方的方格。以此类推，直到遍历到左上角为止。如下图所示，我们就得到了一切的错误类型。

[attach]449851[/attach]


当然，优先级不同，回溯方法也不一样，假如优先级为：insert > delete > substitution，则结果如下：

[attach]449852[/attach]


下面看一个特殊状况，即句子扫尾有插入或者删除错误。

[attach]449853[/attach]


这时假如我们回溯整个矩阵发现，hyp先结束了，而ref还没有结束，为了得到一切的操作，我们必需要遍历的左上角才行，所以，强行从遍历结束的地位移动到左上角。那么，假如是hyp先结束，则一切移动都是删除错误（D），假如是ref先结束，那么一切错误都是插入错误（I）。

[attach]449854[/attach]


Python完成

WER(word error rate) 常常作为语音辨认义务的功能评测目的，WER的计算公式，如下：

[attach]449855[/attach]


如何经过计算编辑间隔，获取到WER计算的分子与分母呢？我们可以从较为简单的状况停止分析。
    当两个字符串都为空串，那么编辑间隔为0； 当其中一个字符串为空串时，那么编辑间隔为另一个非空字符串的长度； 当两个字符串均为非空时(长度分别为 i 和 j )，取以下三种状况最小值即可： 1、长度分别为 i-1 和 j 的字符串的编辑间隔已知，那么加1即可； 2、长度分别为 i 和 j-1 的字符串的编辑间隔已知，那么加1即可； 3、长度分别为 i-1 和 j-1 的字符串的编辑间隔已知，此时思索两种状况，若第i个字符和第j个字符不同，那么加1即可；假如不同，那么不需求加1。
例如，求长度为ref和hyp的字符串的编辑间隔，首先定义函数——edit(i, j)，它表示第一个长度为i的字符串与第二个长度为j的字符串之间的编辑间隔。动态规划表达式可以写为：
    if i == 0 且 j == 0，edit(i, j) = 0 if （i == 0 且 j > 0 ）或者 （i > 0 且j == 0），edit(i, j) = i + j if i ≥ 1 且 j ≥ 1 ，edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + d(i, j) }，当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，d(i, j) = 1；否则，d(i, j) = 0。
实古代码

Python 实古代码篇幅较大，此处不贴了，需求的可私聊。
输入结果数据结构

{                # 标注文本    "ref": "五六七八九十",      # 预测文本    "hyp": "五七捌九玖十",    "result_detail": {        # 一切对的字列表        "C": [            { "ref_value": "五", # ref的值              "hyp_value": "五", # hyp的值              "ref_index": 0,    # 该值在ref的索引地位              "hyp_index": 0,    # 该值在hyp的索引地位              "ref_syllable": "wu", # ref中该值的音节              "hyp_syllable": "wu", # hyp中该值的音节              "ref_tones": "3", # ref中该值的音调              "hyp_tones": "3"  # hyp中该值的音调             },{……}  ],        # 一切编辑的字列表        "S": [{……}, ],        # 一切删除的字列表        "D": [{……}, ],        # 所欲插入的字列表        "I": [{……}, ]    },    # 字句的目的     "result_indicator": {        # 字错率wer目的        "wer": 0.500,        # 句错率ser目的        "ser": 1    },    # 编辑间隔计算出的各项值    "result_count": {        # 全部的数量 N = S + I + D + C        "N": 6,        # 正确的的数量        "C": 4,        # 错误的的数量 W = S + I + D        "W": 3,        # 插入的数量        "I": 1,        # 删除的数量        "D": 1,        # 编辑的数量        "S": 1    },    # 将 ref 与 hpy 建立相对索引对齐后的字典，方便展现输入    "relative_index_value": {        # 索引 1        "1": {            "ref_value": "五",        # ref的值            "ref_index": 0,           # 该值在ref的索引地位             "hyp_value": "五",        # hyp的值            "hyp_index": 0,           # 该值在hyp的索引地位            "syllable_type": "C",     # 音节比对结果，C=正确 S=错误            "hyp_syllable": "wu",     # hyp中该值的音节            "ref_syllable": "wu",     # ref中该值的音节             "tones_type": "C",        # 音调比对结果，C=正确 S=错误            "hyp_tones": "3",         # hyp中该值的音调            "ref_tones": "3",         # ref中该值的音调            "type": "C"               # 字符比对结果，C=正确 S=编辑 I=插入 D=删除        },        # 索引二        "2": {{……},}    }}实践输入JSON如下：
{    "ref": "五六七八九十",    "hyp": "五七捌九玖十",    "result_detail": {        "C": [            {                "ref_value": "五",                "hyp_value": "五",                "ref_index": 0,                "hyp_index": 0,                "ref_syllable": "wu",                "hyp_syllable": "wu",                "ref_tones": "3",                "hyp_tones": "3"            },            {                "ref_value": "七",                "hyp_value": "七",                "ref_index": 2,                "hyp_index": 1,                "ref_syllable": "qi",                "hyp_syllable": "qi",                "ref_tones": "1",                "hyp_tones": "1"            },            {                "ref_value": "九",                "hyp_value": "九",                "ref_index": 4,                "hyp_index": 3,                "ref_syllable": "jiu",                "hyp_syllable": "jiu",                "ref_tones": "3",                "hyp_tones": "3"            },            {                "ref_value": "十",                "hyp_value": "十",                "ref_index": 5,                "hyp_index": 5,                "ref_syllable": "shi",                "hyp_syllable": "shi",                "ref_tones": "2",                "hyp_tones": "2"            }        ],        "S": [            {                "ref_value": "八",                "hyp_value": "捌",                "ref_index": 3,                "hyp_index": 2,                "ref_syllable": "ba",                "hyp_syllable": "ba",                "syllable_type": "C",                "ref_tones": "1",                "hyp_tones": "1",                "tones_type": "C"            }        ],        "D": [            {                "ref_value": "六",                "hyp_value": null,                "ref_index": 1,                "hyp_index": 1,                "ref_syllable": "liu",                "hyp_syllable": null,                "ref_tones": "4",                "hyp_tones": null            }        ],        "I": [            {                "ref_value": null,                "hyp_value": "玖",                "ref_index": 5,                "hyp_index": 4,                "ref_syllable": null,                "hyp_syllable": "jiu",                "ref_tones": null,                "hyp_tones": "3"            }        ]    },    "result_indicator": {        "wer": "0.500",        "ser": 1    },    "result_count": {        "N": 6,        "C": 4,        "W": 3,        "I": 1,        "D": 1,        "S": 1    },    "relative_index_value": {        "1": {            "ref_value": "五",            "ref_index": 0,            "hyp_value": "五",            "hyp_index": 0,            "syllable_type": "C",            "hyp_syllable": "wu",            "ref_syllable": "wu",            "tones_type": "C",            "hyp_tones": "3",            "ref_tones": "3",            "type": "C"        },        "2": {            "ref_value": "六",            "ref_index": 1,            "hyp_value": null,            "hyp_index": null,            "syllable_type": "S",            "hyp_syllable": null,            "ref_syllable": "liu",            "tones_type": "S",            "hyp_tones": null,            "ref_tones": "4",            "type": "D"        },        "3": {            "ref_value": "七",            "ref_index": 2,            "hyp_value": "七",            "hyp_index": 1,            "syllable_type": "C",            "hyp_syllable": "qi",            "ref_syllable": "qi",            "tones_type": "C",            "hyp_tones": "1",            "ref_tones": "1",            "type": "C"        },        "4": {            "ref_value": "八",            "ref_index": 3,            "hyp_value": "捌",            "hyp_index": 2,            "syllable_type": "C",            "hyp_syllable": "ba",            "ref_syllable": "ba",            "tones_type": "C",            "hyp_tones": "1",            "ref_tones": "1",            "type": "S"        },        "5": {            "ref_value": "九",            "ref_index": 4,            "hyp_value": "九",            "hyp_index": 3,            "syllable_type": "C",            "hyp_syllable": "jiu",            "ref_syllable": "jiu",            "tones_type": "C",            "hyp_tones": "3",            "ref_tones": "3",            "type": "C"        },        "6": {            "ref_value": null,            "ref_index": null,            "hyp_value": "玖",            "hyp_index": 4,            "syllable_type": "S",            "hyp_syllable": "jiu",            "ref_syllable": null,            "tones_type": "S",            "hyp_tones": "3",            "ref_tones": null,            "type": "I"        },        "7": {            "ref_value": "十",            "ref_index": 5,            "hyp_value": "十",            "hyp_index": 5,            "syllable_type": "C",            "hyp_syllable": "shi",            "ref_syllable": "shi",            "tones_type": "C",            "hyp_tones": "2",            "ref_tones": "2",            "type": "C"        }    }}

作者: 52013141314    时间: 2020-9-21 07:12
我是个凑数的。。。
作者: 红魔砍切尔斯基    时间: 2020-9-21 21:17
不太懂？有没有详细介绍？
作者: 780548597    时间: 2020-9-22 19:50
前排，哇咔咔



欢迎光临 智客公社 (http://bbs.cnaiplus.com/) Powered by Discuz! X3.4