【NLP】13. NLP推理方法详解 --- 穷举和贪心搜索

NLP推理方法详解 — 穷举和贪心搜索

在自然语言处理（NLP）任务中，推理（Inference）是指在给定模型的情况下，找到最可能的输出序列。由于模型通常是神经网络，它会为每个可能的输出分配一个概率，我们需要设计算法来找到最佳输出。

穷举搜索（Exhaustive Search）

方法介绍

穷举搜索是一种最直观的搜索方法，它会遍历所有可能的输出序列，计算每个序列的分数，并选择得分最高的那个。

优势

✅ 全局最优：可以找到得分最高的输出序列，因为它考虑了所有可能性。
✅ 结构完整：可以保证输出的整体一致性，而不会因为局部最优选择导致全局不佳。

问题

❌ 计算量巨大：如果有 n 个单词，每个单词有 m 种可能的标签，搜索空间大小为 $m^n$ ，即 指数级增长。
❌ 不可扩展：当句子变长或者词汇量增加时，穷举搜索变得不可行。

*例子

假设我们要翻译 “I love NLP”：

假设每个单词有 5 个可能的翻译，那么可能的翻译组合有 $5^3 = 125$ 种。
穷举搜索需要计算所有 125 种组合的分数，选择最优的。

贪心方法（Greedy Method）

方法介绍

贪心方法是指 一步步选择当前概率最高的选项，而不考虑未来可能的更优解。

计算复杂度

O(n⋅m)

相比穷举搜索，贪心方法的计算量小了很多，因为它不考虑所有可能的组合，而是 每一步只选择最优的一个。

例子

假设模型计算出以下翻译概率：

I	-> ["我" (0.7), "咱" (0.2), "俺" (0.1)]
love -> ["爱" (0.6), "喜欢" (0.3), "热爱" (0.1)]
NLP -> ["自然语言处理" (0.8), "语言学" (0.2)]

贪心方法选择每一步最高概率的词，最终得到：“我爱自然语言处理”。

问题

可能错过全局最优解。例如：
- “我喜欢自然语言处理” 可能更自然，但贪心算法无法回头修改之前的选择。
依赖局部信息，而非整体上下文。

贪心推理的不同变体

1. Top-1 方法

📌 方法：每一步选择 最高概率的选项（argmax）。
📌 特点：

计算最快，适用于高确定性的任务（如翻译）。
容易陷入局部最优，可能导致不自然的句子。

📌 例子

输入：I love NLP
模型输出概率：
I -> ["我" (0.7), "咱" (0.2), "俺" (0.1)]
love -> ["爱" (0.6), "喜欢" (0.3), "热爱" (0.1)]
NLP -> ["自然语言处理" (0.8), "语言学" (0.2)]

Top-1 选择：“我爱自然语言处理”。

2. 随机采样（Random Sampling）

📌 方法：每一步按照概率分布 随机选择一个词。
📌 特点：

适用于文本生成任务（如对话系统），增加句子多样性。
可能选择低概率的词，导致句子不连贯。

📌 例子假设 love 有以下翻译：

爱 (0.6)
喜欢 (0.3)
热爱 (0.1)

随机采样可能选择：

“我爱自然语言处理”
“我喜欢自然语言处理”
“我热爱语言学”

3. Top-K 采样

📌 方法：每一步只考虑概率最高的 K 个选项，然后 随机采样。
📌 特点：

保持了一定的多样性，但不会选择过于罕见的词。
需要 重新缩放（rescale） 选择的 K 个词的概率，使它们的和为 1。

📌 例子假设 K=3：

love -> ["爱" (0.6), "喜欢" (0.3), "热爱" (0.1)]

只会在 “爱”、“喜欢”、“热爱” 之间随机选择，而不会选到 “崇拜” 这种低概率的词。

4. Top-P 采样（Nucleus Sampling）

📌 方法：每一步只考虑 累积概率超过 P% 的选项，然后 随机采样。
📌 特点：

适应性更强，避免了固定 K 的局限性。
当某个单词的概率很高时，减少随机性。
当多个单词概率接近时，增加多样性。
需要 重新缩放（rescale） 选中的单词概率，使它们的和为 1。

📌 例子假设我们设定 P=80%：

love -> ["爱" (0.6), "喜欢" (0.3), "热爱" (0.1), "崇拜" (0.05), "迷恋" (0.05)]

前 80% 概率的词是 “爱” 和 “喜欢”，所以只在这两个中随机选择。

5. 对比采样（Contrastive Sampling）

📌 方法：

在选择时 调整得分，根据之前生成的内容降低重复度，提高句子的多样性。

📌 特点：

适合长文本生成，减少重复句子。
结合其他方法使用，如 Top-K、Top-P 采样。

📌 例子

输入："I love NLP because NLP is fun"
如果直接使用 Top-1 方法，可能会生成：
"我 爱 自然语言处理，因为 自然语言处理 很 有趣"
对比采样会调整得分，避免重复 "自然语言处理"，可能生成：
"我 爱 自然语言处理，因为 这 门 学科 很 有趣"

方法对比

方法	计算量	生成质量	适用场景
Top-1 (argmax)	最低	单一、确定性强	适用于翻译、分类
随机采样	低	多样性强，但可能不自然	适用于对话系统、文本生成
Top-K 采样	中等	保持一定多样性，避免极端情况	适用于诗歌、创意写作
Top-P 采样	中等	兼顾确定性和多样性	适用于自由文本生成
对比采样	最高	控制重复，提高连贯性	适用于长文本、摘要