问题标签 [beam-search]

我使用爬山和光束搜索算法在 Prolog 中为 nqueens 拼图制作了两个程序。

不幸的是，我没有检查程序是否正确的经验，我陷入了死胡同。

如果有人可以帮助我，我将不胜感激。不幸的是，爬山的程序不正确。:( 束搜索中的程序是：

我需要生成 4 个随机数，每个随机数在 [-45 +45] 度之间。如果 rand%2 = 0 那么我想要结果（生成的随机数等于 -angle）。一旦生成了 4 个随机数，就需要扫描这些角度并找到一个锁（角度相交的点）。if 语句中循环中的 -3,-2,-1,... +3 表示锁定发生在 6 度波束宽度内。代码有效。但是可以简化吗？目标也是通过扫描两个点的仰角和方位角在两个点之间建立锁定。

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

假设是n = 2（我们将从每个节点扩展的节点数）。所以，一开始，我们只有根，我们从它扩展 2 个节点。现在，从这两个节点，我们再扩展两个。所以，目前，我们有 4 片叶子。我们将继续这样，直到找到答案。

这是光束搜索的工作原理吗？它是仅扩展n = 2每个节点，还是始终保留 2 个叶节点？

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

我知道他们都随机选择 K，然后选择最好的 K，据我所知，最好的 K 调用其他人来找到目标，那么 Local beam search 和 Stochastic beam search 之间的确切区别是什么？如果我错了，请帮助我并纠正我

如果我们认为只有 1 个光束的光束搜索将类似于爬山，还是有其他区别？根据波束搜索的定义，它在爬山算法中跟踪 k 个最佳状态。所以如果 k = 1，我们应该有一个常规的爬山者。

但是我在测试中被问到它们的区别，所以我很困惑。

虽然我对光束搜索有很好的理解，但我对光束搜索有疑问。当我们选择n 条最佳路径时，我们应该对它们进行排序还是简单地保持它们存在的顺序并丢弃其他昂贵的节点？

我对此进行了很多搜索，但它说的每一个地方都保持最佳状态。我们应该对它们进行排序吗？

我认为我们应该对它们进行排序，因为通过应用排序，我们将很快到达目标节点。但是我想确认我的排序想法，直到现在我才找到它。

如果您能帮助我改进我的概念，我将不胜感激。

我正在开发一种带有回溯的光束搜索算法，当我测试算法时，我得到了针对不同光束长度的不同数量的解决方案。所以我只是想确保在这个算法中这是可能的，或者对于任何光束长度，解决方案的数量应该保持不变？所以，我可以确保算法是正确的或需要更新！

给定一个状态向量，我们可以通过连续生成每个输出以贪婪的方式递归解码序列，其中每个预测都以前一个输出为条件。我最近阅读了一篇论文，该论文描述了在解码过程中使用波束搜索，波束大小为 1 (k=1)。如果我们只在每一步都保留最好的输出，这不就和贪心解码一样，并且没有提供波束搜索通常提供的好处吗？

在原始Google 的 SmartReply 论文中：

我们的搜索如下进行。首先，将 R 的元素（所有可能响应的集合）组织成一个 trie。然后，我们进行从左到右的波束搜索，但只保留出现在 trie 中的假设。对于光束大小 b 和最大响应长度 l，此搜索过程具有复杂性 O(bl)。b 和 l 通常都在 10-30 的范围内，因此这种方法大大减少了寻找最佳响应的时间，并且是使该系统可部署的关键因素。

我想实现类似的东西。一些问题：

1. 如何在 TF 中的 trie 数据结构中表示所有可能响应（R）的集合？
2. 如何修改当前的波束搜索以仅保留 R 中可用的假设？

我一直在尝试理解波束搜索算法在解码部分的自动语音识别中使用的逻辑。我尝试关注的论文是First-Pass Large Vocabulary Continuous Speech Recognition using Bi-Directional Recurrent DNNs、Lexicon-Free Conversational Speech Recognition with Neural Networks和Towards End-to-End Speech Recognition with Recurrent Neural Networks。问题是该算法背后的想法并不那么容易理解，并且论文中提供的伪代码中有很多错别字。此外，第二篇论文中的这个实现令人难以置信的难以理解，而上一篇论文中提到的这个实现不包括语言模型。

这是我在 Python 中的实现，由于缺少一些概率而失败：

任何帮助将不胜感激。