用于解码RNN输出的Beam-search算法

Question

我一直在尝试理解自动语音识别中使用的波束搜索算法的逻辑。我尝试了以下论文：使用双向循环DNN进行大词汇连续语音识别的第一遍通行证，使用神经网络进行无词典会话式语音识别和使用递归神经网络实现端到端语音识别。问题在于算法背后的思想并不容易理解，并且提供的伪代码中存在许多错别字。此外，第二篇论文中的此实现难以理解，最后一篇论文中的此实现不包括语言模型。

这是我的Python实现，由于缺少某些概率而失败：

class BeamSearch(object):
"""
Decoder for audio to text.

From: https://arxiv.org/pdf/1408.2873.pdf (hardcoded)
"""
def __init__(self, alphabet='" abcdefghijklmnopqrstuvwxyz'):
    # blank symbol plus alphabet
    self.alphabet = '-' + alphabet
    # index of each char
    self.char_to_index = {c: i for i, c in enumerate(self.alphabet)}

def decode(self, probs, k=100):
    """
    Decoder.

    :param probs: matrix of size Windows X AlphaLength
    :param k: beam size
    :returns: most probable prefix in A_prev
    """
    # List of prefixs, initialized with empty char
    A_prev = ['']
    # Probability of a prefix at windows time t to ending in blank
    p_b = {('', 0): 1.0}
    # Probability of a prefix at windows time t to not ending in blank
    p_nb = {('', 0): 0.0}

    # for each time window t
    for t in range(1, probs.shape[0] + 1):
        A_new = []
        # for each prefix
        for s in Z:
            for c in self.alphabet:
                if c == '-':
                    p_b[(s, t)] = probs[t-1][self.char_to_index[self.blank]] *\
                                    (p_b[(s, t-1)] +\
                                        p_nb[(s, t-1)])
                    A_new.append(s)
                else:
                    s_new = s + c
                    # repeated chars
                    if len(s) > 0 and c == s[-1]:
                        p_nb[(s_new, t)] = probs[t-1][self.char_to_index[c]] *\
                                            p_b[(s, t-1)]
                        p_nb[(s, t)] = probs[t-1][self.char_to_index[c]] *\
                                            p_b[(s, t-1)]
                    # spaces
                    elif c == ' ':
                        p_nb[(s_new, t)] = probs[t-1][self.char_to_index[c]] *\
                                           (p_b[(s, t-1)] +\
                                            p_nb[(s, t-1)])
                    else:
                        p_nb[(s_new, t)] = probs[t-1][self.char_to_index[c]] *\
                                            (p_b[(s, t-1)] +\
                                                p_nb[(s, t-1)])
                        p_nb[(s, t)] = probs[t-1][self.char_to_index[c]] *\
                                            (p_b[(s, t-1)] +\
                                                p_nb[(s, t-1)])
                    if s_new not in A_prev:
                        p_b[(s_new, t)] = probs[t-1][self.char_to_index[self.blank]] *\
                                            (p_b[(s, t-1)] +\
                                                p_nb[(s, t-1)])
                        p_nb[(s_new, t)]  = probs[t-1][self.char_to_index[c]] *\
                                                p_nb[(s, t-1)]
                    A_new.append(s_new)
        A = A_new
        s_probs = map(lambda x: (x, (p_b[(x, t)] + p_nb[(x, t)])*len(x)), A_new)
        xs = sorted(s_probs, key=lambda x: x[1], reverse=True)[:k]
        Z, best_probs = zip(*xs)
    return Z[0], best_probs[0]

任何帮助都将不胜感激。

- Giovanni Rescia

---

{btsdaf} - Harry

Answer 1

我使用-inf初始化实现了束搜索，并且遵循了来自论文http://proceedings.mlr.press/v32/graves14.pdf的ctc_beam_search算法...它与此几乎相似，除了字符的p_b更新...算法正常运行...即使存在初始化，这个算法也可以工作。

A_prev = ['']
p_b[('',0)] = 1
p_nb[('',0)] = 0
for alphabet in alphabets:
    p_b[(alphabet,0)] = -float("inf")
    p_nb[(alphabet,0)] = -float("inf")
for t in range(1,probs.shape[0] +1):
    A_new = []
    for s in A_prev:
        if s!='':
            try:                
                p_nb[(s,t)] = p_nb[(s,t-1)]*probs[t-1][char_map[s[-1:]]]
            except:
                p_nb[(s,t)] = p_nb[(s,t-1)]*probs[t-1][char_map['<SPACE>']]*pW(s)
            if s[:-1] in A_prev:
                p_nb[(s,t)] = p_nb[(s,t)]+pr(probs[t-1],s[-1:],s[:-1],t)
        p_b[(s,t)] = (p_nb[(s,t-1)]+p_b[(s,t-1)])*probs[t-1][0]
        if s=='':
            p_nb[(s,t)] = 0
        if s not in A_new:
            A_new.append(s)
        for c in alphabets:
            s_new = s+c
            p_b[(s_new,t)] = 0
            p_nb[(s_new,t)] = pr(probs[t-1],c,s,t)
            #print s_new,' ',p_nb[(s_new,t)]
            if s_new not in A_new:
                A_new.append(s_new)
    s_probs = map(lambda x: (x,(p_b[(x, t)]+ p_nb[(x, t)])), A_new)

- Suparna Ghanvatkar

---

假设“ab”和“a”包含在B_hat集合中。当y =“a”和k =“b”时，y + k =“ab”。但是，“ab”的条目已经存在，因此旧的概率Pr +被覆盖。你怎么看？也在这里讨论：https://stats.stackexchange.com/questions/273548/multiple-paths-leading-to-same-label-during-ctc-beam-search/ - Harry

Answer 2

问题在于带有 s_new 的块不在 A_prev 中，这会涉及到新生成的字符串不存在的概率。对于新字符串的前一个时间步长即 s_new,t-1，应使用 -float("inf") 进行初始化。您可以放置一个 try catch 块，如果 p[(s_new,t-1)] 不存在，则将其使用 -infinity。

- Suparna Ghanvatkar