Beam Search：为什么这个「折中」算法统治了序列生成三十年

这个策略看起来很直观——既然模型认为这个词概率最高，选它不就对了吗？问题在于，贪婪搜索只看到了眼前的利益，完全忽略了全局最优的可能性。

让我们用一个具体的例子来说明。假设词汇表只有三个词$\{A, B, C\}$，我们要生成一个长度为3的序列。模型输出的概率如下：

flowchart TD
    subgraph 第一步["第一步：选择第一个词"]
        A1["P(A) = 0.6"] --> B1["P(B) = 0.3"]
        A1 --> C1["P(C) = 0.1"]
    end
    
    subgraph 第二步["第二步：假设选了A"]
        A2["P(A|A) = 0.2"]
        B2["P(B|A) = 0.3"]
        C2["P(C|A) = 0.5"]
    end
    
    subgraph 第三步["第三步：假设选了AC"]
        A3["P(A|AC) = 0.3"]
        B3["P(B|AC) = 0.4"]
        C3["P(C|AC) = 0.3"]
    end
    
    第一步 -->|"贪婪选A"| 第二步
    第二步 -->|"贪婪选C"| 第三步
    第三步 -->|"贪婪选B"| 结果["序列ACB<br/>概率=0.6×0.5×0.4=0.12"]

贪婪搜索会按照以下路径生成：

1. 第一步选A（概率0.6，最高）
2. 第二步选C（在A的条件下概率0.5，最高）
3. 第三步选B（在AC的条件下概率0.4，最高）

最终得到的序列是"ACB"，概率为$0.6 \times 0.5 \times 0.4 = 0.12$。

但是，如果我们查看所有可能的序列，可能会发现：

“ABC"序列的概率（0.144）实际上比"ACB”（0.120）更高！贪婪搜索因为在第二步选择了局部最优的C，错过了全局最优的序列。

这就是贪婪搜索的核心问题：局部最优不等于全局最优。一个看似次优的选择可能打开通往更好结果的大门。

搜索空间的残酷现实

你可能会问：为什么不直接遍历所有可能的序列，选择概率最高的那个？

理论上这是最优解。设词汇表大小为$|V|$，序列最大长度为$T'$，穷举搜索需要评估的序列数量为：

对于一个典型的语言模型，$|V| \approx 50000$，$T' \approx 20-50$。这意味着搜索空间大小在$50000^{20}$到$50000^{50}$之间，这比可观测宇宙中的原子数量还要多得多。

相比之下，贪婪搜索的时间复杂度仅为：

它只需要$T'$步，每步遍历词汇表一次。但代价是可能错过最优解。

这就是序列生成面临的核心困境：我们既没有计算资源穷举，又不愿意接受贪婪搜索的短视。

Beam Search：折中的艺术

Beam Search的核心思想很简单：与其只保留一个候选（贪婪搜索），不如同时保留$k$个最有希望的候选。

这个$k$被称为Beam Width或Beam Size。所有被保留的候选序列组成的集合称为Beam。

算法流程

flowchart TB
    Start["初始化：Beam = [空序列]"] --> Step1["时间步 t = 1"]
    
    Step1 --> Expand["扩展阶段：<br/>对Beam中每个序列<br/>尝试所有可能的下一个词"]
    
    Expand --> Candidates["生成 k × |V| 个候选序列"]
    
    Candidates --> Score["计算每个候选的累积对数概率"]
    
    Score --> Select["选择阶段：<br/>保留top-k个候选"]
    
    Select --> Check{"所有候选都<br/>生成了结束符？"}
    
    Check -->|"否"| Step2["时间步 t = t + 1"]
    Step2 --> Expand
    
    Check -->|"是"| Output["输出：返回概率最高的序列"]
    
    style Start fill:#e1f5fe
    style Output fill:#c8e6c9
    style Select fill:#fff3e0

具体来说，Beam Search的每一步包含两个阶段：

扩展阶段：对于Beam中的每个序列，尝试添加词汇表中的每一个词，生成新的候选序列。如果当前Beam有$k$个序列，词汇表大小为$|V|$，则生成$k \times |V|$个候选。

选择阶段：计算所有候选序列的累积对数概率，保留top-$k$个：

flowchart TD
    subgraph t0["t=0: 初始化"]
        S0["Beam: [空序列]"]
    end
    
    subgraph t1["t=1: 第一步扩展"]
        S1A["A (0.6)"]
        S1B["B (0.3)"]
        S1C["C (0.1)"]
    end
    
    subgraph t2["t=1: 选择top-2"]
        B1["Beam: [A, B]<br/>概率: 0.6, 0.3"]
    end
    
    subgraph t3["t=2: 第二步扩展"]
        E1["AA (0.6×0.2=0.12)"]
        E2["AB (0.6×0.3=0.18)"]
        E3["AC (0.6×0.5=0.30)"]
        E4["BA (0.3×0.4=0.12)"]
        E5["BB (0.3×0.1=0.03)"]
        E6["BC (0.3×0.5=0.15)"]
    end
    
    subgraph t4["t=2: 选择top-2"]
        B2["Beam: [AC, AB]<br/>概率: 0.30, 0.18"]
    end
    
    t0 --> t1 --> t2 --> t3 --> t4

graph LR
    A["k=1<br/>贪婪搜索<br/>质量较低"] --> B["k=2-5<br/>最佳区间<br/>质量峰值"]
    B --> C["k>5<br/>质量下降"]
    C --> D["k→∞<br/>趋近穷举<br/>但质量不如人意"]
    
    style B fill:#c8e6c9
    style C fill:#ffcdd2
    style D fill:#ffcdd2

flowchart LR
    subgraph 优化技术
        LP["长度惩罚<br/>平衡长短序列"]
        NB["N-gram Blocking<br/>防止重复"]
        CP["Coverage Penalty<br/>防止遗漏"]
    end
    
    subgraph 效果
        E1["翻译更完整"]
        E2["文本更流畅"]
        E3["生成更多样"]
    end
    
    LP --> E1
    NB --> E2
    CP --> E1

flowchart TD
    A["输入约束: ['iPhone', '苹果']"] --> B["初始化约束状态"]
    B --> C["正常Beam Search扩展"]
    C --> D{"约束词可被满足？"}
    D -->|"是"| E["更新约束状态<br/>优先扩展该候选"]
    D -->|"否"| F["继续正常扩展"]
    E --> G{"所有约束已满足？"}
    F --> G
    G -->|"否"| C
    G -->|"是"| H["输出包含所有约束的序列"]

graph TB
    subgraph 概率分布对比
        A["Beam Search<br/>偏好高概率词<br/>结果：重复、可预测"]
        B["人类文本<br/>包含中低概率词<br/>结果：多样、意外"]
        C["采样方法<br/>允许低概率词<br/>结果：更有创意"]
    end
    
    A -->|"问题"| D["文本退化<br/>重复模式"]
    B -->|"启发"| C
    C -->|"可能"| E["生成质量不稳定"]

# 典型配置
beam_size = 4
length_penalty = 0.6
coverage_penalty = 0.2
early_stopping = True  # 当所有候选都生成<eos>时停止

# 典型配置
beam_size = 6
length_penalty = 2.0  # 更强的长度惩罚
max_length = 142
min_length = 56
no_repeat_ngram_size = 3

# 典型配置（使用采样而非Beam Search）
do_sample = True
top_p = 0.92
temperature = 0.7
no_repeat_ngram_size = 3