首先需要了解贪心算法：
贪心算法，又名贪婪法，是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好/最优的解。{看着这个名字，贪心，贪婪这两字的内在含义最为关键。这就好像一个贪婪的人，他事事都想要眼前看到最好的那个，看不到长远的东西，也不为最终的结果和将来着想，贪图眼前局部的利益最大化，有点走一步看一步的感觉。}
小白带你学---贪心算法（Greedy Algorithm) - 知乎
应用：
Beam Search（集束搜索）多用在一些大型系统中，比如机器翻译系统，语音识别系统等，因为这些系统中的数据集可能非常大，而且结果也没有唯一正确的解，系统用最快的方式找到最接近正确的解才是系统的目标。例如解码Decoder是seq2seq模型的常见问题，常用方法有贪心搜索（Greedy Search）集束搜索（Beam Search）根据概率等等来确定decoder出什么样的语句。【我原来一直以为它是为了采样一个latent code周围的latent code方法，其实在NLP中，它是为了确定decoder出的语句是什么】
1、贪心搜索(greedy search)/采样(Sampling)
贪心搜索最为简单，直接选择每个输出的最大概率，直到出现终结符或最大句子长度。
贪心算法在翻译每个字的时候，直接选择条件概率最大的候选值作为当前最优。如下图所以，
- 第1个时间步长：首先翻译"我"，发现候选"I"的条件概率最大为0.6，所以第一个步长直接翻译成了"I"。
- 第2个时间步长：翻译"我恨"，发现II概率0.2，IH概率0.7，IU概率0.1，所以选择IH作为当前步长最优翻译结果。
- 第3个时间步长：翻译"我恨你"，发现IHI概率0.05，IHH概率0.05，IHU概率0.9，所以选择IHU作为最终的翻译结果。
PS：图中的概率如何得来的？不同的模型有不同的算法，我自己随便填的。
贪心算法每一步选择中都采取在当前状态下最好或最优的选择，通过这种局部最优策略期望产生全局最优解。但是期望是好的，能不能实现是另外一回事了。贪心算法本质上没有从整体最优上加以考虑，并不能保证最终的结果一定是全局最优的。但是相对穷举搜索，搜索效率大大提升。
2、beam search（束搜索）
beam search是对greedy search的一个改进算法。相对greedy search扩大了搜索空间，但远远不及穷举搜索指数级的搜索空间，是二者的一个折中方案。
beam search有一个超参数beam size（束宽），设为 k 。第一个时间步长，选取当前条件概率最大的 k个词，当做候选输出序列的第一个词。之后的每个时间步长，基于上个步长的输出序列，挑选出所有组合中条件概率最大的 k 个，作为该时间步长下的候选输出序列。始终保持 k 个候选。最后从 k 个候选中挑出最优的。
还是以上面的任务为例，假设 k=2 ，我们走一遍这个搜索流程。
- 第一个时间步长：如下图所示，I和H的概率是top2，所以第一个时间步长的输出的候选是I和H，将I和H加入到候选输出序列中。
- 第2个时间步长：如下图所示，以I开头有三种候选{II, IH, IU}，以H开头有三种候选{HI, HH, HU}。从这6个候选中挑出条件概率最大的2个，即IH和HI，作为候选输出序列。
- 第3个时间步长：同理，以IH开头有三种候选{IHI, IHH, IHU}，以HI开头有三种候选{HII, HIH, HIU}。从这6个候选中挑出条件概率最大的2个，即IHH和HIU，作为候选输出序列。因为3个步长就结束了，直接从IHH和IHU中挑选出最优值IHU作为最终的输出序列。
3、随机采样
贪心搜索（greedy search）、集束搜索（beam search）、随机采样（random sample）_jiangchao98的博客-CSDN博客
总结
beam search不保证全局最优，但是比greedy search搜索空间更大，一般结果比greedy search要好。
greedy search 可以看做是 beam size = 1时的 beam search。文章来源：https://www.toymoban.com/news/detail-556290.html
如何通俗的理解beam search？ - 知乎文章来源地址https://www.toymoban.com/news/detail-556290.html
到了这里，关于贪心算法、贪心搜索/采样（greedy search/sampling）、集束搜索（beam search）、随机采样（random sample）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
