NLP 自然语言处理集束搜索beam search和贪心搜索greedy search

末蓝、 2021-09-16 14:46 570阅读 0赞

在数学之美中曾介绍[维特比算法][Link 1]，其根据自然语言句子生成的特性，利用动态规划方法，找到生成的最大可能性句子。但其同样存在弊端，如如果字典的长度非常大的话，那么查找的状态将会非常多，影响效率。而在句子生成中还有些如下方法：

**贪心搜索(greedy search)：**

贪心搜索最为简单，直接选择每个输出的最大概率，直到出现终结符或最大句子长度。

![70][]

**集束搜索(beam search)：**

集束搜索可以认为是维特比算法的贪心形式，在维特比所有中由于利用动态规划导致当字典较大时效率低，而集束搜索使用beam size参数来限制在每一步保留下来的可能性词的数量。集束搜索是在测试阶段为了获得更好准确性而采取的一种策略，在训练阶段无需使用。

假设字典为\[a,b,c\]，beam size选择2，则如下图有：

1：在生成第1个词的时候，选择概率最大的2个词，那么当前序列就是a或b

2：生成第2个词的时候，我们将当前序列a或b，分别与字典中的所有词进行组合，得到新的6个序列aa ab ac ba bb bc,然后从其中选择2个概率最高的，作为当前序列，即ab或bb

3：不断重复这个过程，直到遇到结束符为止。最终输出2个概率最高的序列。

**![70 1][]**

显然集束搜索属于贪心算法，不能保证一定能够找到全局最优解，因为考虑到搜索空间太大，而采用一个相对的较优解。而维特比算法在字典大小较小时能够快速找到全局最优解。

而贪心搜索由于每次考虑当下词的概率，而通常英文中有些常用结构，如“is going”，出现概率较大，会导致模型最终生成的句子过于冗余。如“is visiting”和“is going to be visiting”。贪心搜索可以认为beam size为1时的集束搜索特例。

**维特比算法(Viterbi algorithm)：**

[维特比算法][Link 1]

[Link 1]: https://blog.csdn.net/qq_16234613/article/details/82835641
[70]: /images/20210520/75ef3dcc718e4a2b8dd0f51e25d0fbec.png
[70 1]: /images/20210520/e78487e7218f4f5a9ac9c60db645d46b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，570人围观）

还没有评论，来说两句吧...

相关阅读

相关 helm search搜索charts命令

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

╰半橙微兮°/ 2023年10月05日 03:13/ 0 赞/ 8 阅读

相关 Seq2Seq模型中的集束搜索(Beam Search)

1. 引入用Seq2Seq模型开发翻译系统时，假设输入一句法语，输出英文。在Decoder输出部分，选择不同的单词，输出（翻译）的结果也会不同。这里用下图来举例说明

你的名字/ 2023年01月10日 11:47/ 0 赞/ 264 阅读

相关 Elasticsearch 跨集群搜索 cross cluster search

Elasticsearch 通过cross cluster search实现跨集群搜索，需要在每个集群中添加一些动态配置，然后在搜索语句中就可以实现跨越集群进行搜索。启动

短命女/ 2023年01月01日 11:55/ 0 赞/ 119 阅读

相关 Seq2Seq模型中的贪心搜索(Greedy Search)

1. 引入用Seq2Seq模型开发翻译系统时，假设输入一句法语，输出英文。在Decoder输出部分，选择不同的单词，输出（翻译）的结果也会不同。这里用下图来举例说明

雨点打透心脏的1/2处/ 2022年12月27日 01:24/ 0 赞/ 180 阅读

相关 Word Search（C++单词搜索）

（1）回溯（2）返回时重置为未访问 class Solution { private: vector<vector<cha

淡淡的烟草味﹌/ 2022年10月11日 13:46/ 0 赞/ 139 阅读

相关深度学习：自然语言生成-集束/柱搜索beam search和随机搜索random search

http://[blog.csdn.net/pipisorry/article/details/78404964][blog.csdn.net_pipisorry_articl

迷南。/ 2022年06月06日 05:28/ 0 赞/ 221 阅读

相关随机搜索（Random Searching）算法

个人理解，随机搜索是一种在巨大数据规模下执行一个耗时上无法接受的程序的优化方法。它可以用以对一个搜索算法施展优化的前提是： > 1、数据规模大，精确的结果难以在一定时间

爱被打了一巴掌/ 2022年03月29日 10:21/ 0 赞/ 688 阅读

相关 NLP自然语言处理

<table> <tbody> <tr> <td><font> </font> <div> <h2>自然语言处理</h2>&nb

落日映苍穹つ/ 2021年11月30日 00:52/ 0 赞/ 457 阅读

相关 NLP 自然语言处理集束搜索beam search和贪心搜索greedy search

在数学之美中曾介绍[维特比算法][Link 1]，其根据自然语言句子生成的特性，利用动态规划方法，找到生成的最大可能性句子。但其同样存在弊端，如如果字典的长度非常大的话，那么查

末蓝、/ 2021年09月16日 14:46/ 0 赞/ 571 阅读

相关 HTML input search搜索域

将input元素的type属性值设置为"search"可以创建一个搜索域。搜索域是HTML5新增，IE9+和其他标准浏览器支持。从表面上看与普通文本框非常类似，且...

小灰灰/ 2020年05月15日 18:50/ 0 赞/ 845 阅读