HW5-补充1：深入理解 Beam Search——原理, 示例与代码实现

目录

0 前言

1 Beam Search的工作原理

2 生成示例

2.1 初始化

2.2 扩展 A 和 B

2.3 仅扩展 AC

2.4 后续步骤

3 怎么处理?

4 处理示例图（k=3）

5 进一步深入Beam Search

5.1 使用对数概率

5.2 参数解释

6 代码演示

7 数学描述

7.1 序列概率

7.2 评分函数

7.3 Beam Search的更新步骤

7.4 最终选择

8 实际应用

8.1 代码示例

8.2 对比不同束宽的输出

9 Beam Search Visualizer示例

10 推荐阅读

0 前言

本文为李宏毅学习笔记——2024春《GENERATIVE AI》篇——作业笔记HW5的补充内容1。

如果你还没获取到LLM API，请查看我的另一篇笔记：

HW1~2：LLM API获取步骤及LLM API使用演示：环境配置与多轮对话演示-CSDN博客

完整内容参见：

李宏毅学习笔记——2024春《GENERATIVE AI》篇

从示例到代码演示，讲解 Beam Search 的数学原理，这应该能解决一些之前阅读的困惑，最终提供一个简单的使用 Hugging Face Transformers 库的示例（如果跳过了之前的文章的话可以尝试它）。

Beam Search 是生成任务中常用的一种方法。在之前的文章中，我们都曾经用到过与它相关的参数，而对于早就有着实操经验的同学们，想必见到的更多。这篇文章将从示例到数学原理和代码带你进行理解。

Beam Search 对应的中文翻译为“集束搜索”或“束搜索”。你可以将其当作是贪心算法的拓展，其实是很简单的概念：贪心算法每次只选择最好的，而 Beam Search 会在多个候选中进行选择。通过这篇文章，你将了解到：

  • Beam Width（束宽） 的实际作用，常对应于参数名 num_beams。
  • 所有候选序列生成结束标记的含义，常对应于参数名 early_stopping。
  • Beam Search 的基本原理和工作机制。

强烈建议访问：Beam Search Visualizer，这是一个非常 Amazing 的交互式项目。

我之前也吴恩达老师的深度学习课程“第五课：序列模型”章节也简单了解过集束搜索Beam Search，链接如下：

第五课：序列模型-CSDN博客

1 Beam Search的工作原理

Beam Search 是一种宽度优先搜索算法，通过保留多个候选序列来探索可能的输出空间，这与贪心算法每次只选择一个当前最优序列不同，可以将贪心算法当成 1 个候选序列下的 Beam Search。

具体来讲，每一步生成时，Beam Search 会保留束宽 k 个最有可能的候选序列（k=1 即贪心），并为每个候选序列计算它们的累积概率或对数概率。在每一步搜索时，Beam Search 会生成所有可能的下一个词汇，并从中选择得分最高的 k 个序列继续下一步。所以，束宽越大，搜索空间越广，计算成本越高。

以下是 Beam Search 的基本步骤：

  1. 初始化：从一个初始序列（通常为空或特殊起始标记）开始，设定束宽 k，初始化候选序列集 B0=start。
  2. 迭代生成：对于当前所有候选序列 Bt−1，扩展一个新的词汇或符号，生成所有可能的下一个词汇组合，并计算每个序列的概率。
  3. 选择顶束：从所有扩展的候选序列中，选择得分最高的 k 个序列，作为下一步的候选序列 Bt。
  4. 终止条件：当所有候选序列都生成了结束标记（如 ）或达到设定的最大长度 T 时，停止生成。
  5. 选择最终序列：从最终的候选序列集中，选择得分最高的序列作为输出。

注：以 GPT 为例，扩展实际对应于去获取 tokens 的概率。

2 生成示例

为了清晰，这里使用累积概率进行得分的计算。

2.1 初始化

  • 束宽 (k): 2

  • 当前候选集 (B0): （空）

  • 词汇表 A,B,C,

  • 扩展（生成所有可能的下一个词汇）：

扩展结果概率
A0.4
B0.3
C0.2
0.1

  • 选择顶束 (k=2):

    • A (0.4)
    • B (0.3)

  • 新的候选集 (B1): A(0.4),B(0.3)

2.2 扩展 A 和 B

  • 扩展 A：

    • 生成概率: A:0.3,B:0.1,C:0.4,:0.2
扩展结果概率计算概率
AA0.4×0.30.12
AB0.4×0.10.04
AC0.4×0.40.16
A0.4×0.20.08

扩展 B：

  • 生成概率: A:0.1,B:0.1,C:0.3,:0.5
扩展结果概率计算概率
BA0.3×0.10.03
BB0.3×0.10.03
BC0.3×0.30.09
B0.3×0.50.15

所有扩展序列及其概率：

序列概率
AC0.16
AA0.12
B0.15
BC0.09
A0.08
AB0.04
BA0.03
BB0.03

  • 选择顶束 (k=2):

    • AC (0.16)
    • B (0.15)

  • 新的候选集 (B2): AC(0.16)

  • 完成集合: B (0.15)

2.3 仅扩展 AC

  • 生成概率: A:0.1,B:0.2,C:0.5,:0.2
扩展结果概率计算概率
ACA0.16×0.10.016
ACB0.16×0.20.032
ACC0.16×0.50.080
AC0.16×0.20.032
  • 由于 B 已完成，我们选择扩展结果中的顶束：
    • ACC (0.080)
    • 以某种规则选择 ACB 或 AC (0.032)
  • 新的候选集 (B3): ACC(0.080),ACB(0.032)
  • 完成集合: B(0.15)

现在是你访问它的最好时机：Beam Search Visualizer 

2.4 后续步骤

  • 继续扩展：重复上述过程，直到所有候选序列都生成了  或达到设定的最大长度。

3 怎么处理?

在每一步生成过程中，如果某个序列生成了 ，则将其标记为完成，不再进行扩展。以下是处理  的举例：

  • 假设在某一步，序列 ACB 扩展出 ACB (0.032×1=0.032)，则：
    • ACB 保留在最终候选集，并不再扩展。
    • Beam Search 继续扩展其他未完成的序列，直到所有序列完成或达到最大长度。

问题：如果有一个序列被标记为完成（生成了 ），在下一个扩展步骤中，Beam Search 应该扩展多少个候选序列？

答：束宽 (k) 个，如果被标记完成的序列还保留在候选集中不移出，就是 k−1 个。

4 处理示例图（k=3）

你可以在下图中看到，即便有一个序列生成了 ，下一个扩展步骤中还是会扩展 k=3 个候选序列。

5 进一步深入Beam Search

5.1 使用对数概率

在实际应用中，尤其是在处理长序列时，直接相乘概率会导致数值下溢问题。为了避免这种情况，通常会使用对数概率来累加评分。

示例说明：

假设使用对数概率，序列的评分计算如下：

  • 序列 A 的概率为 0.4，其对数概率为 log⁡(0.4)≈−0.916。
  • 序列 AC 的概率为 0.16，其对数概率为 log⁡(0.16)≈−1.833。

在 Beam Search 中，我们会选择对数概率较高（即绝对值较小）的序列作为顶束。

5.2 参数解释

除了 num_beams 和 early_stopping，Beam Search 通常还涉及其他参数，以下是常见参数的简要解释：

  • max_length（最大生成长度）：限制生成序列的最大长度。
  • length_penalty（长度惩罚）：用于调整生成序列的长度偏好，通常用于平衡生成序列的长度与概率评分。值大于 1 时，会惩罚过长的序列，值小于 1 时，会鼓励生成较长的序列。
  • no_repeat_ngram_size：防止生成序列中出现重复的 n-gram，提高生成内容的多样性。
  • num_return_sequences：指定生成的序列数量，允许一次生成多个不同的候选序列，<= num_beams。

6 代码演示

下面是一个 beam search 演示代码，结果完全对应于之前讨论的示例。为了简单起见，我们进一步假设在序列 ACB 和 ACC 之后一定是 

  1. import math
  2.  
  3. def beam_search(initial_sequence, beam_width, max_length, vocab, get_next_probs):
  4.     beam = [(initial_sequence, 0.0)]  # (sequence, log_prob)
  5.     completed = []
  6.  
  7.     for step in range(max_length):
  8.         print(f"\n第 {step + 1} 步:")
  9.         all_candidates = []
  10.         for seq, score in beam:
  11.             if seq.endswith(''):
  12.                 completed.append((seq, score))
  13.                 print(f"已完成序列: {seq}，得分为 {score}")
  14.                 continue
  15.             next_probs = get_next_probs(seq)
  16.             print(f"扩展序列: {seq}，当前得分为 {score}")
  17.             for token, prob in next_probs.items():
  18.                 new_seq = seq + token
  19.                 new_score = score + math.log(prob)
  20.                 all_candidates.append((new_seq, new_score))
  21.                 print(f"  候选序列: {new_seq}，得分为 {new_score}")
  22.         
  23.         # 对所有候选序列按得分降序排列，选择得分最高的 beam_width 个序列
  24.         all_candidates.sort(key=lambda x: x[1], reverse=True)
  25.         beam = all_candidates[:beam_width]
  26.  
  27.         # 打印选出的顶束序列
  28.         print(f"\n选择的 {beam_width} 个顶束序列:")
  29.         for seq, score in beam:
  30.             print(f"  {seq}，得分为 {score}")
  31.         
  32.         # 如果没有更多序列可以扩展，则退出循环
  33.         if not beam:
  34.             break
  35.  
  36.     # 将当前 beam 中剩下的序列加入完成序列中
  37.     completed += beam
  38.  
  39.     # 对完成的序列按得分降序排列，选择得分最高的序列
  40.     completed.sort(key=lambda x: x[1], reverse=True)
  41.     
  42.     print("\n已完成的所有序列:")
  43.     for seq, score in completed:
  44.         print(f"  {seq}，得分为 {score}")
  45.     
  46.     return completed[0][0]
  47.  
  48. # 我们之前示例中设置的概率
  49. def get_next_probs(seq):
  50.     probs = {
  51.         "": {"A": 0.4, "B": 0.3, "C": 0.2, "": 0.1},
  52.         "A": {"A": 0.3, "B": 0.1, "C": 0.4, "": 0.2},
  53.         "B": {"A": 0.1, "B": 0.1, "C": 0.3, "": 0.5},
  54.         "AC": {"A": 0.1, "B": 0.2, "C": 0.5, "": 0.2},
  55.     }
  56.     return probs.get(seq, {"": 1.0})
  57.  
  58. initial_sequence = ""
  59. beam_width = 3 # 你可以修改这个参数来感受区别
  60. max_length = 5
  61. vocab = {"A", "B", "C", ""}
  62.  
  63. best_sequence = beam_search(initial_sequence, beam_width, max_length, vocab, get_next_probs)
  64. print("\n最佳序列:", best_sequence)

输出：

  1. 第 1 步:
  2. 扩展序列: ，当前得分为 0.0
  3.   候选序列: A，得分为 -0.916290731874155
  4.   候选序列: B，得分为 -1.2039728043259361
  5.   候选序列: C，得分为 -1.6094379124341003
  6.   候选序列: ，得分为 -2.3025850929940455
  7.  
  8. 选择的 2 个顶束序列:
  9.   A，得分为 -0.916290731874155
  10.   B，得分为 -1.2039728043259361
  11.  
  12. 第 2 步:
  13. 扩展序列: A，当前得分为 -0.916290731874155
  14.   候选序列: AA，得分为 -2.120263536200091
  15.   候选序列: AB，得分为 -3.2188758248682006
  16.   候选序列: AC，得分为 -1.83258146374831
  17.   候选序列: A，得分为 -2.525728644308255
  18. 扩展序列: B，当前得分为 -1.2039728043259361
  19.   候选序列: BA，得分为 -3.506557897319982
  20.   候选序列: BB，得分为 -3.506557897319982
  21.   候选序列: BC，得分为 -2.4079456086518722
  22.   候选序列: B，得分为 -1.8971199848858813
  23.  
  24. 选择的 2 个顶束序列:
  25.   AC，得分为 -1.83258146374831
  26.   B，得分为 -1.8971199848858813
  27.  
  28. 第 3 步:
  29. 扩展序列: AC，当前得分为 -1.83258146374831
  30.   候选序列: ACA，得分为 -4.135166556742355
  31.   候选序列: ACB，得分为 -3.4420193761824103
  32.   候选序列: ACC，得分为 -2.525728644308255
  33.   候选序列: AC，得分为 -3.4420193761824103
  34. 已完成序列: B，得分为 -1.8971199848858813
  35.  
  36. 选择的 2 个顶束序列:
  37.   ACC，得分为 -2.525728644308255
  38.   ACB，得分为 -3.4420193761824103
  39.  
  40. 第 4 步:
  41. 扩展序列: ACC，当前得分为 -2.525728644308255
  42.   候选序列: ACC，得分为 -2.525728644308255
  43. 扩展序列: ACB，当前得分为 -3.4420193761824103
  44.   候选序列: ACB，得分为 -3.4420193761824103
  45.  
  46. 选择的 2 个顶束序列:
  47.   ACC，得分为 -2.525728644308255
  48.   ACB，得分为 -3.4420193761824103
  49.  
  50. 第 5 步:
  51. 已完成序列: ACC，得分为 -2.525728644308255
  52. 已完成序列: ACB，得分为 -3.4420193761824103
  53.  
  54. 选择的 2 个顶束序列:
  55.  
  56. 已完成的所有序列:
  57.   B，得分为 -1.8971199848858813
  58.   ACC，得分为 -2.525728644308255
  59.   ACB，得分为 -3.4420193761824103
  60.  
  61. 最佳序列: B

7 数学描述

7.1 序列概率

假设我们要生成一个长度为 T 的序列 Y=(y1,y2,…,yT)，该序列的生成是逐步进行的，即每个词汇 yt 的生成依赖于前面已经生成的词汇 y1,y2,…,yt−1。因此，序列 Y 的联合概率为：

7.2 评分函数

由于直接计算概率乘积在处理长序列时容易导致数值下溢问题，所以通过取对数来稳定数值并简化计算。取对数后的评分函数（log likelihood）为：

模型的目标是最大化序列的概率：

 

7.3 Beam Search的更新步骤

7.4 最终选择

当生成过程结束时，从最终的候选集 B_T 中，选择得分最高的序列作为最终输出:

8 实际应用

先安装一些演示用到的库：

  1. pip install transformers
  2. #pip install torch torchvision torchaudio --index-url https://download.pytorch.org/whl/cu118

8.1 代码示例

使用 Hugging Face Transformers 库的简单示例：

  1. from transformers import AutoTokenizer, AutoModelForCausalLM
  2. import torch
  3.  
  4. # 指定模型名称
  5. model_name = "distilgpt2"
  6.  
  7. # 加载分词器和模型
  8. tokenizer = AutoTokenizer.from_pretrained(model_name)
  9. model = AutoModelForCausalLM.from_pretrained(model_name)
  10.  
  11. # 设置 pad_token 为 eos_token
  12. tokenizer.pad_token = tokenizer.eos_token
  13.  
  14. # 移动模型到设备
  15. device = torch.device("cuda" if torch.cuda.is_available() else "cpu")
  16. model.to(device)
  17.  
  18. # 设置模型为评估模式
  19. model.eval()
  20.  
  21. # 输入文本
  22. input_text = "Hello GPT"
  23.  
  24. # 编码输入文本，同时返回 attention_mask
  25. inputs = tokenizer.encode_plus(input_text, return_tensors="pt", padding=True).to(device)
  26.  
  27. # 生成文本，使用 Beam Search
  28. beam_width = 5
  29. with torch.no_grad():
  30.     outputs = model.generate(
  31.         inputs["input_ids"],
  32.         attention_mask=inputs["attention_mask"],
  33.         max_length=50,
  34.         num_beams=beam_width,  # 你可以看到 beam_width 对应的参数名为 num_beams
  35.         no_repeat_ngram_size=2,
  36.         early_stopping=True,  # 当所有候选序列生成停止
  37.         pad_token_id=tokenizer.eos_token_id
  38.     )
  39.  
  40. # 解码生成的文本
  41. generated_text = tokenizer.decode(outputs[0], skip_special_tokens=True)
  42. print("生成的文本：")
  43. print(generated_text)

输出：

  1. 生成的文本：
  2. Hello GPT.
  3.  
  4. This article was originally published on The Conversation. Read the original article.

8.2 对比不同束宽的输出

  1. # 输入文本
  2. input_text = "Hello GPT"
  3.  
  4. # 编码输入文本，同时返回 attention_mask
  5. inputs = tokenizer.encode_plus(input_text, return_tensors="pt", padding=True).to(device)
  6.  
  7. # 设置束宽不同的生成策略
  8. beam_widths = [1, 3, 5]  # 使用不同的束宽
  9.  
  10. # 生成并打印结果
  11. for beam_width in beam_widths:
  12.     with torch.no_grad():
  13.         outputs = model.generate(
  14.             inputs["input_ids"],
  15.             attention_mask=inputs["attention_mask"],
  16.             max_length=50,
  17.             num_beams=beam_width,
  18.             no_repeat_ngram_size=2,
  19.             early_stopping=True,
  20.             pad_token_id=tokenizer.eos_token_id
  21.         )
  22.     generated_text = tokenizer.decode(outputs[0], skip_special_tokens=True)
  23.     print(f"束宽 {beam_width} 的生成结果：")
  24.     print(generated_text)
  25.     print('-' * 50)
  1. 束宽 1 的生成结果：
  2. Hello GPT is a free and open source software project that aims to provide a platform for developers to build and use GPGP-based GPSP based GPCs. GPP is an open-source software development platform that is designed to
  3. --------------------------------------------------
  4. 束宽 3 的生成结果：
  5. Hello GPT.
  6.  
  7. This article is part of a series of articles on the topic, and will be updated as more information becomes available.
  8. --------------------------------------------------
  9. 束宽 5 的生成结果：
  10. Hello GPT.
  11.  
  12. This article was originally published on The Conversation. Read the original article.
  13. --------------------------------------------------

9 Beam Search Visualizer示例

Beam Search Visualizer是一个用GPT2进行集束搜索然后可视化的工具。

现在我们设置一下下面的参数：

  • 解码所需的输入（inputs）：传递给解码器的输入序列。
  • 生成步骤数（max_new_tokens）：要生成的最大 token 数量。
  • 搜索宽度（num_beams）：用于生成的 beam search 的宽度，即 beam 的数量。
  • 长度惩罚系数（length_penalty）：对输出序列应用的长度惩罚。length_penalty > 0.0 会倾向于生成较长的序列，而 length_penalty < 0.0 会鼓励生成较短的序列。此参数不会影响 beam search 的路径搜索，但会在最终选择序列时根据长度偏好进行调整。
  • 返回序列数量（num_return_sequences）：最终生成的序列数量。此值应小于或等于 num_beams。

得到的结果如下图所示： 

结论性序列是以<| endftext |>标记结尾或以生成结束结尾的序列。

它们根据分数进行排名，如公式score = cumulative_score / (output_length ** length_penalty)所示。

只返回最上面的num_beams评分序列：在树中它们以蓝色突出显示。未选择的序列也显示在树中，用黄色突出显示。

输出的序列为：

  • Score -1.14: Conclusion: thanks a lot. That's all for today.\n\nAdvertisements<|endoftext|>
  • Score -1.30: Conclusion: thanks a lot. That's all for today. I hope you enjoyed
  • Score -1.33: Conclusion: thanks a lot. That's all for today. I'll be back

10 推荐阅读

注：本文转载自blog.csdn.net的笨笨sg的文章"https://blog.csdn.net/a131529/article/details/144192103"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！