标签: beam-search

我使用Tensorflow tf.nn.ctc_beam_search_decoder()来解码RNN的输出,进行一些多对多映射(即每个网络单元的多个softmax输出).

网络输出的简化版本和Beam搜索解码器是:

import numpy as np
import tensorflow as tf

batch_size = 4
sequence_max_len = 5
num_classes = 3

y_pred = tf.placeholder(tf.float32, shape=(batch_size, sequence_max_len, num_classes))
y_pred_transposed = tf.transpose(y_pred,
                                 perm=[1, 0, 2])  # TF expects dimensions [max_time, batch_size, num_classes]
logits = tf.log(y_pred_transposed)
sequence_lengths = tf.to_int32(tf.fill([batch_size], sequence_max_len))
decoded, log_probabilities = tf.nn.ctc_beam_search_decoder(logits,
                                                           sequence_length=sequence_lengths,
                                                           beam_width=3,
                                                           merge_repeated=False, top_paths=1)

decoded = decoded[0]
decoded_paths = tf.sparse_tensor_to_dense(decoded)  # Shape: [batch_size, max_sequence_len]

with tf.Session() as session:
    tf.global_variables_initializer().run()

    softmax_outputs = np.array([[[0.1, 0.1, 0.8], [0.8, 0.1, 0.1], [0.8, 0.1, …

我对光束搜索算法有疑问.

让我们说n = 2(我们将从每个节点扩展的节点数).所以,在开始时,我们只有根,我们从它扩展了2个节点.现在,从这两个节点开始,我们再扩展两个节点.所以,目前,我们有4片叶子.我们将继续这样,直到找到答案.

这是梁搜索的工作原理吗？它是仅扩展n = 2每个节点,还是一直保留2个叶子节点？

我曾经认为这n = 2意味着我们每个节点最多应该有2个活动节点,而不是整个树的两个活动节点.

我知道他们两个都随机选择K,然后选择最好的K,因为我知道最好的K叫其他人找到目标,那么本地波束搜索和随机波束搜索之间的确切区别是什么？如果我错了,请帮助我并纠正我

根据我的理解（如果我错了，请纠正我），Beam Search 是 BFS，它只探索可能性的“图”向下b最可能的选项，其中b是光束大小。

为了计算/评分每个选项，特别是对于我正在做的 NLP 领域的工作，我们基本上通过计算一个标记的概率来计算可能性的分数，考虑到它之前的所有内容。

这在循环架构中是有意义的，在这种架构中，您只需通过最好的b 个第一个标记运行您使用解码器拥有的模型，以获得每个第一个标记的第二个标记的概率。最终，您会得到具有概率的序列，然后您只需选择概率最高的序列。

然而，在 Transformer 架构中，模型没有这种循环，输出是词汇表中每个单词的整个概率，序列中的每个位置（批量大小、最大序列长度、词汇大小）。我如何解释 Beam Search 的这个输出？我可以获得输入序列的编码，但由于没有重复使用前一个输出作为下一个标记解码的输入，我如何计算所有可能序列的概率，这些序列源自最佳b令牌？

我正在尝试在文本生成模型中实现波束搜索解码策略。这是我用来解码输出概率的函数。

def beam_search_decoder(data, k):
    sequences = [[list(), 0.0]]
    # walk over each step in sequence
    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 - torch.log(row[j])]
                all_candidates.append(candidate)
        # sort candidates by score
        ordered = sorted(all_candidates, key=lambda tup:tup[1])
        sequences = ordered[:k]
    return sequences

现在你可以看到这个函数是在batch_size 1的情况下实现的。添加另一个用于批量大小的循环将使该算法成为可能O(n^4)。就像现在一样缓慢。有什么办法可以提高这个功能的速度吗？我的模型输出的大小通常(32, 150, 9907)遵循格式(batch_size, max_len, vocab_size)

CRF ++允许我们获得每个标签的边际概率（每个输出标签的一种置信度）和一个可能的输出条件（整个输出的置信度）。

% crf_test -v2 -m model test.data
# 0.478113
Rockwell        NNP     B       B/0.992465      B/0.992465      I/0.00144946    O/0.00608594
International   NNP     I       I/0.979089      B/0.0105273     I/0.979089      O/0.0103833
Corp.           NNP     I       I/0.954883      B/0.00477976    I/0.954883      O/0.040337
's              POS     B       B/0.986396      B/0.986396      I/0.00655976    O/0.00704426
Tulsa           NNP     I       I/0.991966      B/0.00787494    I/0.991966      O/0.00015949
unit            NN      I       I/0.996169      B/0.00283111    I/0.996169      O/0.000999975
..

Tensorflow有自己的crf实现。训练完crf模型后，我们可以通过或y为每个测试输入序列获得最佳的标签序列及其标准化分数。xtf.contrib.crf.viterbi_decode()tf.contrib.crf.crf_decode()

但是，对于我来说，获得一个最佳顺序是不够的。目前，排名前k位的最佳序列及其对应的分数对我都很有用。我注意到，当前上述两个功能不提供这些信息。因此，我想知道在对tensorflow源代码进行少量修改后是否有可能获得前k个最佳候选者。

1. top-k标签序列及其对应的归一化分数。
2. 每个标签的边际概率（如CRF ++）

给定状态向量,我们可以通过连续生成每个输出以贪婪的方式递归地解码序列,其中每个预测以先前的输出为条件.我最近读了一篇论文,描述了在解码过程中使用光束搜索,光束大小为1(k = 1).如果我们只是在每一步保留最佳输出,这不是贪婪解码的同一个东西,并没有提供光束搜索通常提供的任何好处吗？