深度学习 – 基础的Greedy Search和Beam Search算法的Python实现

假设当前词汇表中总共有5个词汇，现在有一个概率矩阵需要解码为词序列，词序列中包含10个词，以下通过Greedy Search Decoder和Beam Search Decoder对该词序列分别进行解码。

1 Greedy Search

import numpy as np

# greedy decoder
def greedy_decoder(data):
    # 每行最多的概率值索引
    return [np.argmax(s) for s in data]


if __name__ == '__main__':
    data = [[0.1, 0.2, 0.3, 0.4, 0.5],
            [0.5, 0.4, 0.3, 0.2, 0.1],
            [0.1, 0.2, 0.3, 0.4, 0.5],
            [0.5, 0.4, 0.3, 0.2, 0.1],
            [0.1, 0.2, 0.3, 0.4, 0.5],
            [0.5, 0.4, 0.3, 0.2, 0.1],
            [0.1, 0.2, 0.3, 0.4, 0.5],
            [0.5, 0.4, 0.3, 0.2, 0.1],
            [0.1, 0.2, 0.3, 0.4, 0.5],
            [0.5, 0.4, 0.3, 0.2, 0.1]]

    data = np.array(data)

    result = greedy_decoder(data)

    print(result)

输出

[4, 0, 4, 0, 4, 0, 4, 0, 4, 0]

2 Beam Search

from math import log
import numpy as np

# beam search
def beam_search_decoder(data, beam_size):
    sequences = [[list(), 0.0]]
    # 遍历每一个序列
    for row in data:
        all_candidates = list()
        # 在下一个序列中找到候选者
        for i in range(len(sequences)):
            seq, score = sequences[i]
            for j in range(len(row)):
                candidate = [seq + [j], score - log(row[j])]
                all_candidates.append(candidate)
        # 根据分数排序所有的候选者
        ordered = sorted(all_candidates, key=lambda tup:tup[1])
        # 选择beam_size个最大的
        sequences = ordered[:beam_size]
    return sequences

if __name__ == '__main__':
    data = [[0.1, 0.2, 0.3, 0.4, 0.5],
            [0.5, 0.4, 0.3, 0.2, 0.1],
            [0.1, 0.2, 0.3, 0.4, 0.5],
            [0.5, 0.4, 0.3, 0.2, 0.1],
            [0.1, 0.2, 0.3, 0.4, 0.5],
            [0.5, 0.4, 0.3, 0.2, 0.1],
            [0.1, 0.2, 0.3, 0.4, 0.5],
            [0.5, 0.4, 0.3, 0.2, 0.1],
            [0.1, 0.2, 0.3, 0.4, 0.5],
            [0.5, 0.4, 0.3, 0.2, 0.1]]

    data = np.array(data)

    result = beam_search_decoder(data,3)

    for seq in result:
        print(seq)

输出

[[4, 0, 4, 0, 4, 0, 4, 0, 4, 0], 6.931471805599453]
[[4, 0, 4, 0, 4, 0, 4, 0, 4, 1], 7.154615356913663]
[[4, 0, 4, 0, 4, 0, 4, 0, 3, 0], 7.154615356913663]