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

你的名字 2023-01-10 11:47 263阅读 0赞

# 1. 引入 #

用Seq2Seq模型开发翻译系统时，假设输入一句法语，输出英文。在Decoder输出部分，选择不同的单词，输出（翻译）的结果也会不同。

这里用下图来举例说明：

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

一个法语句子，被Seq2Seq模型翻译为不同的4句英文，我们该选择哪个结果作为最终结果呢？

上图中，给了一个公式，式中的`x`表示法语句子，`y`表示各个单词组成的最终的英文句子，不同的y的组合表示不同的翻译，即y1~yn表示单词序列。

解决这个问题的关键，就在于找到合适的y值，使得图中的公式值最大化。

但是具体怎么做呢？

下面我们介绍一种方法：`Beam Search`。

# 2. 集束搜索算法：Beam Search #

之前我们介绍过`贪心算法`，它最简单：每次选择输出概率值最大的那个单词组成单词序列，如下图。

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

`集束搜索`和`贪心算法`类似，不同的地方在于，它选择每次输出概率值最大的N个单词序列，N指的是`集束宽度`（`Beam Width`）。下面举例说明，假设集束宽度N=2。

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

1.  第一步，在第一个输出中，选择2个概率值最高的单词。如图，这一步选择了A和C。
2.  第二步，依次以A,C作为LSTM的输入，得到各个单词的概率（两组输出），选择两组输出中概率值最大的2个单词。如图，这一步选择了B和E。
3.  第二步，依次以B和E作为LSTM的输入，得到各个单词的概率（两组输出），选择两组输出中概率值最大的2个单词。如图，这一步选择了D和D。
4.  最终输出，就是两个句子，ABD和CED。

可以看到，如果集束宽度N=1，则`集束搜索`就等效于`贪心算法`。

# 3. 算法优点 #

`集束搜索`得到的也不是最优解，但能在一定宽度下搜索出N个次优解。这样的算法，在没有唯一正确解的大型系统中用的比较多。比如语音识别，机器翻译，自动问答。这样的系统，算法复杂，数据量大，VC维很高。所以，系统的主要目标，并不是找到最优解，而是用最快的速度，找到最接近正确解作为输出。

# 参考 #

*  \[1\]. https://blog.csdn.net/weixin\_38937984/article/details/102492050
 *  \[2\]. Andrew Ng Sequence Models video
 *  \[3\]. https://d2l.ai/chapter\_recurrent-modern/beam-search.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3liZGVzaXJl_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/55c55dba1f8449869b7ede5efb5f6708.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3liZGVzaXJl_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221119/890f88463529427791b7d22dc60e7b5f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3liZGVzaXJl_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221119/428e0680a3ac4e8686748fb79ba3e15b.png