BoBolilla's site

Appearance

N-gram哈希函数 ​

N-gram哈希函数在自然语言处理（NLP）中主要用于高效提取局部词序特征，尤其在FastText等模型中起到关键作用。以下是其核心用途和原理的详细解释：

1. 什么是N-gram哈希函数？ ​

N-gram哈希函数通过数学运算将连续的N个单词（或字符）映射到一个固定范围的整数值（哈希桶）。例如：

  • 二元语法（Bigram）："apple banana" → 哈希值
  • 三元语法（Trigram）："apple banana orange" → 哈希值

代码中的实现：

python

python

复制

python
def biGramHash(sequence, t, buckets):
    t1 = sequence[t - 1] if t - 1 >= 0 else 0  # 前一个词（不存在则用0）
    return (t1 * 14918087) % buckets  # 通过大质数计算哈希

def triGramHash(sequence, t, buckets):
    t1 = sequence[t - 1] if t - 1 >= 0 else 0
    t2 = sequence[t - 2] if t - 2 >= 0 else 0  # 前两个词
    return (t2 * 14918087 * 18408749 + t1 * 14918087) % buckets

2. 核心作用 ​

（1）捕捉局部词序信息 ​

  • 问题：传统词袋模型（Bag-of-Words）忽略单词顺序，无法区分 "cat eats fish" 和 "fish eats cat"。
  • 解决：N-gram哈希保留连续的N个词的组合信息，增强模型对局部语序的理解。

（2）减少内存消耗 ​

  • 传统方法：显式存储所有可能的N-gram组合（例如5万词汇的Bigram需要存储约25亿种组合）。
  • 哈希技巧：通过哈希函数将N-gram映射到固定数量的桶（如buckets=100万），内存占用从指数级降至线性级。

（3）处理未知N-gram ​

  • 即使测试集中出现训练时未见的N-gram，哈希函数也能将其映射到某个桶，避免OOV（Out-of-Vocabulary）问题。

3. 在FastText中的应用 ​

FastText模型通过以下方式利用N-gram哈希：

输入扩展

：将每个词的N-gram哈希值作为附加特征输入模型。

  • 例如，单词 "apple" 的Bigram可能包括 "ap", "pp", "pl", "le" 的哈希值。

子词嵌入

：N-gram哈希允许模型学习

子词（subword）

的语义，提升对罕见词或拼写错误的鲁棒性。

  • 例如，即使 "apple" 未出现在训练集中，其子词 "app" 和 "ple" 可能已被学习。

4. 代码中的具体实现 ​

在给定的 load_dataset 函数中：

python

python

复制

python
bigram = [biGramHash(words_line, i, buckets) for i in range(pad_size)]
trigram = [triGramHash(words_line, i, buckets) for i in range(pad_size)]

  • 输入：单词ID序列（如 [1, 2, 3] 对应 ["apple", "banana", "orange"]）。

  • 输出：每个位置的Bigram/Trigram哈希值序列（长度与输入一致，不足补零）。

示例

：

  • 若

    words_line = [1, 2, 3]

    （对应

    ["apple", "banana", "orange"]

    ），则：

    • Bigram哈希可能计算 (apple, banana) 和 (banana, orange) 的组合。
    • Trigram哈希可能计算 (apple, banana, orange) 的组合。

5. 为什么使用大质数？ ​

哈希函数中的大质数（如 14918087）用于：

  • 减少冲突：质数的乘积特性使哈希值分布更均匀，降低不同N-gram映射到同一桶的概率。
  • 数学性质：质数模运算能更好地分散输入模式，避免规律性导致的哈希聚集。

6. 与其他方法的对比 ​

方法优点缺点
显式N-gram存储精确保留所有组合内存爆炸（词汇量大时不可行）
N-gram哈希内存高效，兼容未知N-gram可能有哈希冲突（但实际影响小）
神经网络自学习自动捕捉词序（如CNN/RNN）需要更多数据和计算资源

7. 适用场景 ​

  • 文本分类：通过N-gram哈希捕捉短语特征（如负面评论中的 "not good"）。
  • 多语言任务：对形态丰富的语言（如德语、土耳其语），子词N-gram能更好地处理复合词。
  • 短文本建模：局部词序信息对短文本（如推特）的分类至关重要。

总结 ​

N-gram哈希函数通过空间换时间的策略，在保证模型性能的同时大幅降低计算成本，是FastText等轻量级模型的核心技术之一。它的设计平衡了语义捕捉能力和资源效率，尤其适合大规模文本处理任务。