我对光束搜索算法有疑问。
假设是n = 2（我们将从每个节点扩展的节点数）。所以，一开始，我们只有根，我们从它扩展 2 个节点。现在，从这两个节点，我们再扩展两个。所以，目前，我们有 4 片叶子。我们将继续这样，直到找到答案。
这是光束搜索的工作原理吗？它是仅扩展n = 2每个节点，还是始终保留 2 个叶节点？
我曾经认为这n = 2意味着每个节点最多应该有 2 个活动节点，而不是整个树的两个。
问问题
20396 次
2 回答
15
在“标准”波束搜索算法中，在每一步中，您当前“了解”的节点总数是有限的 - 而不是您将从每个节点遵循的节点数。
具体来说，如果n = 2，则意味着“梁”的大小在任何时候都最多为 2。因此，最初，您从一个节点开始，然后发现所有可从该节点到达的节点，但丢弃除两个以外的所有节点，并以 2 个节点完成步骤 1。在第 2 步，您有两个节点，您将展开这两个节点，并再次丢弃所有节点，除了正好 2 个节点（总计，不是每个节点！）。在接下来的步骤中，类似地，您将在每一步之后保留 2 个节点。
选择保留哪个节点通常由一些启发式函数完成，该函数评估哪个节点最接近目标。
请注意，波束搜索算法不是完整的（即，如果存在解决方案，它可能找不到解决方案）也不是最优的（即，它可能找不到最佳解决方案）。看到这一点的最好方法是见证当 时n = 1，它基本上简化为最佳优先搜索。
于 2014-03-08T18:36:41.930 回答
-1
在波束搜索中，我们不是在每个时间步选择最好的令牌生成，而是在每个步骤保留 k 个可能的令牌。这个固定大小的内存占用 k 称为光束宽度，比喻手电筒光束可以参数化为更宽或更窄。
因此，在解码的第一步，我们在整个词汇表上计算一个 softmax，为每个单词分配一个概率。然后我们从这个 softmax 输出中选择 k-best 选项。这些初始的 k 个输出是搜索边界，这 k 个初始词称为假设。假设是一个输出序列，一个翻译到目前为止，连同它的概率。
在随后的步骤中，k 个最佳假设中的每一个都通过传递给不同的解码器来增量扩展，每个解码器都会在整个词汇表上生成一个 softmax，以将假设扩展到每个可能的下一个标记。这些 k∗V 假设中的每一个都由 P(yi|x,y<i) 评分：当前单词选择的概率乘以通向它的路径的概率的乘积。然后我们将 k∗V 假设修剪为 k 个最佳假设，因此在搜索的前沿永远不会超过 k 个假设，并且永远不会超过 k 个解码器。
光束尺寸（或光束宽度）是前面提到的 k。
于 2018-05-16T02:21:42.647 回答