Santi

  • 5

    获得赞
  • 2

    发布的文章
  • 0

    答辩的项目

Beam Search Decoder 解码器

CNN

最后更新 2020-05-11 10:49 阅读 72

最后更新 2020-05-11 10:49

阅读 72

CNN

简介

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

image.png如对上图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,因此上述的贪婪搜索结果如下图,为:--。

image.png

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

Beam Search Decoder

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

image.png

首先,我们计算所有路径的各自概率,当然下述算法不是最高效,其没有跳过概率为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大,于是为此算法的解。


本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可,转载请附上原文出处链接和本声明。
本文链接地址:https://www.flyai.com/article/450
讨论
500字
表情
每日参与讨论奖励 20FAI
发送
每日参与讨论奖励 20FAI
删除确认
是否删除该条评论?
取消 删除