简介

Beam Search Decoder是解码神经网络输出常用的一种方法，常应用在OCR、文本翻译、语音识别等算法应用中。 其目的是从神经网络生成的一个二维矩阵中计算概率最大的路径，此路径上的内容（字符）即网络要生成的目标。

如对上图ab字符串的文字识别任务。 通过对图片纵向切成3片t1, t2，随后通过神经网络计算，输出如下概率矩阵。每一列分别表示其可能是[a, b, -]3个的概率。（-表示占位的空字符，一般叫做blank）。

   t1    t2 
a  0.2   0.4
b  0.0   0.0
-  0.8   0.6

我们先从速度快、准确率低的Greedy Search Decoder讲起，再叙述速度慢、但准确率高的Beam Search Decoder。

Greedy Search Decoder

贪婪搜索算法，即快速搜索算法，此算法从名字上就可以看出其偷懒所以快。 其只取每个列的最大值作为其路径结点：0.8 x 0.6，因此上述的贪婪搜索结果如下图，为：--。

def greedy_decoder(mat):
	# index for largest probability each row
	return [argmax(s) for s in mat]

Beam Search Decoder

上述的贪婪搜索虽然快，但经常不准确，如上，其搜索结果为：--，有时误差比较大。 Beam Search搜索就是解决此问题。其不止搜索一条概率最大路径，而是保存搜索的多条路径，最后再合并路径，去除占位符(blank)，以达到最优解。

首先，我们计算所有路径的各自概率，当然下述算法不是最高效，其没有跳过概率为0的路径，以及其它优化：

from math import log
from numpy import array
from numpy import argmax
 
# beam search
def beam_search_decoder(data):
	sequences = [[list(), 1.0]]
	# walk over each step in sequence
	for row in data:
		all_candidates = list()
		# expand each current candidate
		for i in range(len(sequences)):
			seq, score = sequences[i]
			for j in range(len(row)):
				candidate = [seq + [j], score * row[j]]
				all_candidates.append(candidate)
		# order all candidates by score
		ordered = sorted(all_candidates, key=lambda tup:tup[1], reverse=True)
		# select k best
		sequences = ordered
	return sequences
 
# define a sequence of 10 words over a vocab of 5 words
data = [[0.2, 0.0, 0.8],
        [0.4, 0.0, 0.6]]
data = array(data)
# decode sequence
result = beam_search_decoder(data)
# print result
for seq in result:
	print(seq)

输出计算的概率：

--: 0.8 x 0.6 = 0.48
aa: 0.2 x 0.4 = 0.08
a-: 0.2 x 0.6 = 0.12
-a: 0.8 x 0.4 = 0.32

随后，我们合并路径。

aa、a-、-a这3条去除点位符、合并重复字符，最后都为：a。因此它们3个可以合并计算概率为：0.08+0.12+0.32=0.52，概率比--的0.48大，于是为此算法的解。