文本处理与经典 NLP

文本处理将原始字符转换为模型可以消费的结构化表示。本文件涵盖分词（词级、子词、BPE、WordPiece）、文本规范化、编辑距离、TF-IDF、n-元语言模型、词性标注、命名实体识别和情感分析——这些经典 NLP 流程仍然支撑着现代系统。

• 原始文本是杂乱无章的。在任何 NLP 模型能够处理语言之前，必须对文本进行清洗、规范化并转换为结构化表示。本文件涵盖从原始字符到模型可消费特征的整个流程，以及深度学习主导之前流行的经典 NLP 算法。

• 文本规范化将原始文本转换为规范形式。目标是减少无关的变化，使得 “Hello”、“hello”、“HELLO” 和 “héllo” 能够得到恰当的处理。

• 大小写折叠将文本转换为小写。这会把 “The” 和 “the” 合并成一个标记。这对大多数任务有帮助，但在某些情况下会丢失有用信息：“US”（国家）与 “us”（代词），或者 “Apple”（公司）与 “apple”（水果）。

• Unicode 规范化处理同一个字符有多种编码方式的事实。字符 “é” 可以是一个单一码位（U+00E9），也可以是一个基本 “e” 加上一个组合重音（U+0065 + U+0301）。NFC 规范化将它们组合成一个码位；NFD 则分解它们。如果没有规范化，两个看起来相同的字符串可能无法匹配。

• 编辑距离衡量两个字符串的差异程度。莱文斯坦距离统计将一个字符串转换为另一个字符串所需的最小单字符插入、删除和替换次数。“kitten” → “sitting” 的编辑距离为 3（k→s，e→i，插入 g）。

• 编辑距离使用动态规划计算。定义 \(D[i][j]\) 为字符串 \(s\) 的前 \(i\) 个字符与字符串 \(t\) 的前 \(j\) 个字符之间的距离：

\[ D[i][j] = \begin{cases} j & \text{若 } i = 0 \\ i & \text{若 } j = 0 \\ D[i{-}1][j{-}1] & \text{若 } s[i] = t[j] \\ 1 + \min(D[i{-}1][j], \; D[i][j{-}1], \; D[i{-}1][j{-}1]) & \text{否则} \end{cases} \]

• 编辑距离是拼写纠正、模糊匹配和 DNA 序列比对的基础。在 NLP 中，它用于处理拼写错误和查找相似词。

• 分词将文本切分为离散的单元（标记），供模型处理。这是第一个，也可以说是最重要的预处理步骤。分词策略的选择深刻影响模型的行为。

• 空白分词按空格切分。简单但天真：“New York” 变成两个标记，“don't” 是一个标记（或根据切分器分成 “don” 和 “'t”），而像汉语和日语这样的语言根本没有空格分隔单词。

• 基于规则的分词使用手工构建的模式（正则表达式）来处理缩写、标点符号和特殊情况。“I'm” → “I” + “'m”，“U.S.A.” 保持为一个标记。每种语言都需要自己的规则，这很耗费人力。

• 子词分词是现代解决方案。它不是按单词边界切分，而是从数据中学习常见的子词单元词汇表。这可以优雅地处理未知词：如果 “unhappiness” 不在词汇表中，它可能会被切分为 “un” + “happi” + “ness”，保留了形态结构。

• 字节对编码（BPE） 从单个字符作为词汇表开始。它反复寻找最频繁的相邻对，并将它们合并为一个新标记。经过足够多次合并后，常见词成为单个标记，稀有词被切分为频繁的子词片段。

• BPE 算法：

  1. 用训练语料中的所有单个字符初始化词汇表
  2. 统计每对相邻标记的频率
  3. 将最频繁的对合并为一个新标记
  4. 重复步骤 2-3，直到达到所需的合并次数（即词汇表大小）

• 例如，从 “l o w”（5 次）、“l o w e r”（2 次）、“n e w e s t”（6 次）开始：最频繁的对可能是 “e s” → 合并为 “es”。然后 “es t” → “est”。然后 “n e w” → “new”。最终的词汇表同时包含完整单词和子词片段。

• WordPiece（BERT 使用）与 BPE 类似，但基于似然而非频率选择合并。它合并那些能够最大化训练数据语言模型似然的词对。非词首的子词标记会加上 “##” 前缀（例如，“playing” → “play” + “##ing”）。

• Unigram（SentencePiece 使用之一）采取相反的方法：从一个大的词汇表开始，迭代地移除那些移除后对训练数据似然伤害最小的标记。最终的词汇表是能够最好地解释语料的子词单元集合。

• SentencePiece 是一个语言无关的分词库，它将输入视为原始字节流（不预先在空格上切分）。这使得它适用于任何语言，包括那些没有空格的语言。它同时实现了 BPE 和 Unigram 算法。

• 词汇表大小是一个关键的超参数。典型选择范围从 30,000 到 100,000 个标记。较大的词汇表意味着每个序列的标记更少（更高效），但嵌入表更大。较小的词汇表意味着更多的子词切分和更长的序列。

• 这两种技术都将单词还原为基本形式，但方法不同。

• 词干提取使用粗略的规则切掉后缀。Porter 词干提取器将 “running” 还原为 “run”，“happiness” 还原为 “happi”，“studies” 还原为 “studi”。它速度快但不精确：“university” 和 “universe” 都被提取为 “univers”，尽管它们不相关。

• 词形还原使用词汇表和形态分析找到真正的词典形式（词元）。“Running” → “run”，“better” → “good”，“mice” → “mouse”。它需要知道词性：“saw” 作为动词词形还原为 “see”，但作为名词则保持 “saw”。

• 现代子词分词在很大程度上已经取代了神经 NLP 中的词干提取和词形还原，但它们在信息检索以及处理较小模型或有限数据时仍然有用。

• 词性标注为每个单词分配一个语法类别：名词、动词、形容词、限定词等。这是最古老的 NLP 任务之一，是句法分析的基础。

• Penn Treebank 标记集是英语中最常见的，有 36 个标记（NN 表示单数名词，NNS 表示复数名词，VB 表示动词原形，VBD 表示过去式，JJ 表示形容词等）。

• 词性标注很棘手，因为许多单词有歧义。“Book” 可以是名词（“the book”）或动词（“book a flight”）。“Run” 有几十种跨词性的义项。上下文至关重要。

• 早期的标注器使用第 05 章中的隐马尔可夫模型。隐藏状态是词性标记，观测值是单词。转移概率捕捉标记序列（限定词后面很可能跟着名词或形容词），发射概率捕捉哪些单词与哪些标记一起出现。维特比算法找到最可能的标记序列。

• 用于词性标注的 HMM 模型：

\[\hat{t}_{1:n} = \arg\max_{t_{1:n}} \prod_{i=1}^{n} P(w_i \mid t_i) \cdot P(t_i \mid t_{i-1})\]

• 现代词性标注器使用神经网络（双向 LSTM 或 Transformer），在英语上准确率超过 97%，接近人类水平。

• 命名实体识别（NER） 识别并对专有名词和其他特定实体进行分类：人物、组织、地点、日期、金额等。

• 在 “Apple CEO Tim Cook announced the event in Cupertino on Monday” 中，NER 系统应识别出：Apple（组织）、Tim Cook（人物）、Cupertino（地点）、Monday（日期）。

• NER 通常被构建为序列标注任务，使用 BIO 标记（也称 IOB 标记）。每个标记获得一个标签：

  • B-TYPE：某个 TYPE 类型实体的开始
  • I-TYPE：某个 TYPE 类型实体的内部（延续）
  • O：实体外部

• “Tim Cook visited New York” 变成：Tim/B-PER Cook/I-PER visited/O New/B-LOC York/I-LOC。B 标记标记新实体的开始，这在两个相同类型的实体相邻时很重要。

• 经典 NER 使用第 05 章中的条件随机场（CRF），它建模给定输入下整个标签序列的条件概率。与 HMM 是生成式（\(P(x, y)\)）不同，CRF 是判别式的，直接建模 \(P(y \mid x)\)。线性链 CRF 定义为：

\[P(y_{1:n} \mid x_{1:n}) = \frac{1}{Z(x)} \exp\!\left(\sum_{i=1}^{n} \left[\sum_k \lambda_k f_k(y_i, x, i) + \sum_j \mu_j g_j(y_i, y_{i-1}, x, i)\right]\right)\]

• 其中 \(f_k\) 是发射特征（给定位置 \(i\) 的输入时，标签 \(y_i\) 的可能性），\(g_j\) 是转移特征（给定前一个标签 \(y_{i-1}\) 时，标签 \(y_i\) 的可能性）。

• 配分函数 \(Z(x) = \sum_{y'} \exp(\ldots)\) 对所有可能的标签序列求和以归一化分布。训练最大化条件对数似然，这需要利用前向算法高效计算 \(Z(x)\)（第 05 章）。

• 与独立分类每个标记相比，CRF 的关键优势在于其转移特征强制结构约束（例如，I-PER 应该只跟在 B-PER 或 I-PER 后面，永远不能出现在 O 之后）。

• 现代 NER 在神经编码器之上堆叠一个 CRF（BiLSTM-CRF 或 BERT-CRF），其中神经网络产生发射分数，CRF 层学习转移结构。

• 句法分析将句子转换为其句法结构，可以是成分树或依存树（二者均来自文件 01）。

• CYK 算法使用动态规划解析上下文无关文法中的句子。

• 它要求文法为乔姆斯基范式（每条规则的右侧要么有两个非终结符，要么有一个终结符）。它自底向上填充一个三角形表格：单元格表示句子的跨度，每个单元格存储可以生成该跨度的非终结符。

• CYK 的时间复杂度为 \(O(n^3 \cdot |G|)\)，其中 \(n\) 是句子长度，\(|G|\) 是文法规模。对于大型语法，这种方法是精确的但速度较慢。

• 移进-归约解析从左到右处理句子，维护一个栈。在每一步，它要么移进（将下一个单词压入栈），要么归约（从栈中弹出元素并用一个短语替换它们）。一个训练好的分类器决定每一步的动作。时间复杂度为 \(O(n)\)，比 CYK 快得多。

• 依存解析在实践中比成分解析更常见。基于转移的依存解析器（如移进-归约）和基于图的解析器（对所有可能的边打分并找到最大生成树）是两种主要方法。使用 BiLSTM 或 Transformer 的神经依存解析器达到了最先进的结果。

• 在词嵌入出现之前，NLP 使用简单的计数方法将文档表示为向量。

• 词袋模型将文档表示为单词计数的向量，完全忽略词序。如果词汇表有 \(V\) 个单词，每个文档就是 \(\mathbb{R}^V\) 中的一个向量（联系回第 01 章的向量空间）。单词 \(w\) 对应的条目是 \(w\) 在文档中出现的次数。

• BoW 简单但对于文档分类和垃圾邮件过滤等任务出奇地有效。它的主要弱点是对每个单词一视同仁：“the” 和 “revolutionary” 获得相同的权重。

• TF-IDF（词频-逆文档频率）通过基于单词的信息量来加权解决了这个问题。在一个文档中出现频率高但在整个语料库中出现频率低的单词很可能对该文档很重要。

\[\text{TF-IDF}(t, d) = \text{TF}(t, d) \times \text{IDF}(t)\]

• 词频 \(\text{TF}(t, d)\) 通常是词 \(t\) 在文档 \(d\) 中的原始计数（或其对数：\(1 + \log(\text{count})\)）。

• 逆文档频率 \(\text{IDF}(t) = \log\frac{N}{|\{d : t \in d\}|}\)，其中 \(N\) 是文档总数。出现在每个文档中的单词（如 “the”）的 IDF 接近于 0。稀有词的 IDF 高。

• TF-IDF 向量可以使用余弦相似度（来自第 01 章）进行比较，以衡量文档相似度。这是经典信息检索和搜索引擎的基础。

• 语言模型给一个单词序列赋予概率。它回答：这个句子的可能性有多大？语言模型是机器翻译、语音识别、拼写纠正和文本生成的核心。

• 根据概率的链式法则（第 05 章），句子 \(w_1, w_2, \ldots, w_n\) 的概率为：

\[P(w_1, w_2, \ldots, w_n) = \prod_{i=1}^{n} P(w_i \mid w_1, \ldots, w_{i-1})\]

• 这是精确的但不实用：你需要为每一种可能的历史存储概率。马尔可夫假设（第 05 章）将历史截断到最后 \(k-1\) 个单词，得到 n-元模型（其中 \(n = k\)）。

• 二元模型（\(n = 2\)）只依赖前一个单词：

\[P(w_i \mid w_1, \ldots, w_{i-1}) \approx P(w_i \mid w_{i-1})\]

• 三元模型（\(n = 3\)）依赖前两个单词。n-元概率通过在语料库中计数来估计：

\[P(w_i \mid w_{i-1}) = \frac{\text{count}(w_{i-1}, w_i)}{\text{count}(w_{i-1})}\]

• 困惑度衡量语言模型在测试集上的预测效果。它是测试集概率的倒数，按单词数归一化：

\[\text{PPL} = P(w_1, \ldots, w_N)^{-1/N} = \exp\!\left(-\frac{1}{N} \sum_{i=1}^{N} \log P(w_i \mid w_{<i})\right)\]

• 困惑度越低，模型对测试数据的“惊讶”程度越低，因此模型越好。在 10,000 词词汇表上均匀分配概率的模型困惑度为 10,000。一个良好的二元模型可能达到约 200 的困惑度。现代神经语言模型的困惑度低于 20。

• 注意，困惑度是指数化的交叉熵（来自第 05 章的信息论）。训练中最小化交叉熵损失直接最小化困惑度。

• 平滑处理零概率问题：如果一个 n-元从未在训练中出现，模型会赋予它 0 概率，这会使整个句子概率为 0。拉普拉斯平滑（add-1）为每个 n-元增加一个小的计数：

\[P_{\text{Laplace}}(w_i \mid w_{i-1}) = \frac{\text{count}(w_{i-1}, w_i) + 1}{\text{count}(w_{i-1}) + V}\]

• 对于大词汇表，这过于激进（从已观察到的 n-元中窃取了太多概率）。Kneser-Ney 平滑是 n-元模型的金标准。它结合了两个思想：绝对折扣和用于回退的延续概率。

• 首先，绝对折扣从每个观察计数中减去一个固定折扣 \(d\)（通常 \(d \approx 0.75\)），而不是添加伪计数。释放出的概率质量被重新分配给未见的 n-元。插值形式为：

\[P_{\text{KN}}(w_i \mid w_{i-1}) = \frac{\max(\text{count}(w_{i-1}, w_i) - d, \; 0)}{\text{count}(w_{i-1})} + \lambda(w_{i-1}) \cdot P_{\text{cont}}(w_i)\]

• 其中 \(\lambda(w_{i-1})\) 是归一化常数，用于分配折扣后的质量。关键创新是延续概率 \(P_{\text{cont}}(w_i)\)，它衡量 \(w_i\) 出现在多少个不同的上下文中，而不是它出现的总次数：

\[P_{\text{cont}}(w_i) = \frac{|\{w' : \text{count}(w', w_i) > 0\}|}{|\{(w', w'') : \text{count}(w', w'') > 0\}|}\]

• 分子统计有多少个不同的单词在语料库中出现在 \(w_i\) 之前。像 “Francisco” 这样的词出现在很少的上下文中（几乎总是在 “San” 之后），所以即使 “San Francisco” 非常频繁，“Francisco” 的延续概率也很低，不会在其他上下文中被错误地预测。

• 相反，像 “the” 这样的常见词出现在许多不同的单词之后，从而获得较高的延续概率。这抓住了这样一个直觉：在回退估计中，一个词的通用性比其原始频率更重要。

• n-元模型多年来一直是 state of the art。它们速度快、可解释，且无需训练（只需计数）。但它们难以处理长距离依赖（“The keys that I left on the table are missing” 需要知道主语 “keys” 是复数，这离动词很远）。从 RNN 开始到 Transformer 达到顶峰的神经语言模型解决了这一局限。

编码任务（使用 CoLab 或 notebook）

1. 使用动态规划实现莱文斯坦编辑距离。在单词对上进行测试，并将其用于简单的拼写纠正。

   import jax.numpy as jnp
   
   def edit_distance(s, t):
       """使用动态规划计算莱文斯坦编辑距离。"""
       m, n = len(s), len(t)
       D = [[0] * (n + 1) for _ in range(m + 1)]
   
       for i in range(m + 1):
           D[i][0] = i
       for j in range(n + 1):
           D[0][j] = j
   
       for i in range(1, m + 1):
           for j in range(1, n + 1):
               if s[i-1] == t[j-1]:
                   D[i][j] = D[i-1][j-1]
               else:
                   D[i][j] = 1 + min(D[i-1][j], D[i][j-1], D[i-1][j-1])
   
       return D[m][n]
   
   # 测试
   pairs = [("kitten", "sitting"), ("sunday", "saturday"), ("hello", "hallo")]
   for s, t in pairs:
       print(f"d('{s}', '{t}') = {edit_distance(s, t)}")
   
   # 简单的拼写纠正
   dictionary = ["the", "their", "there", "then", "than", "this", "that", "these", "those"]
   misspelled = "thier"
   corrections = sorted(dictionary, key=lambda w: edit_distance(misspelled, w))
   print(f"\n与 '{misspelled}' 最接近的词: {corrections[:3]}")
   

2. 从头实现 BPE 分词。从字符级标记开始，迭代地合并最频繁的对。

   from collections import Counter
   
   def get_pairs(corpus):
       """统计所有单词中相邻标记对的数量。"""
       pairs = Counter()
       for word, freq in corpus.items():
           symbols = word.split()
           for i in range(len(symbols) - 1):
               pairs[(symbols[i], symbols[i+1])] += freq
       return pairs
   
   def merge_pair(pair, corpus):
       """在语料库中合并所有出现的对。"""
       new_corpus = {}
       bigram = ' '.join(pair)
       replacement = ''.join(pair)
       for word, freq in corpus.items():
           new_word = word.replace(bigram, replacement)
           new_corpus[new_word] = freq
       return new_corpus
   
   # 带词频的训练语料
   text = "low low low low low lower lower newest newest newest newest newest newest"
   word_freqs = Counter(text.split())
   # 初始化：将每个单词切分为字符，并添加词尾标记
   corpus = {' '.join(word) + ' _': freq for word, freq in word_freqs.items()}
   
   print("初始语料：")
   for word, freq in corpus.items():
       print(f"  {word}: {freq}")
   
   # 运行 BPE 进行 10 次合并
   for i in range(10):
       pairs = get_pairs(corpus)
       if not pairs:
           break
       best_pair = max(pairs, key=pairs.get)
       corpus = merge_pair(best_pair, corpus)
       print(f"\n合并 {i+1}: {best_pair} (频率={pairs[best_pair]})")
       for word, freq in corpus.items():
           print(f"  {word}: {freq}")
   

3. 构建一个二元语言模型，并计算测试句子的困惑度。使用拉普拉斯平滑进行实验。

   from collections import Counter, defaultdict
   import math
   
   # 训练语料
   train = """the cat sat on the mat . the dog chased the cat .
   the cat ran from the dog . a dog sat on a mat .""".split()
   
   # 统计二元组和一元组
   bigrams = Counter(zip(train[:-1], train[1:]))
   unigrams = Counter(train)
   vocab_size = len(set(train))
   
   def bigram_prob(w2, w1, alpha=0):
       """P(w2 | w1) 带有可选的拉普拉斯平滑。"""
       return (bigrams[(w1, w2)] + alpha) / (unigrams[w1] + alpha * vocab_size)
   
   # 计算困惑度
   test = "the cat sat on a mat .".split()
   
   for alpha in [0, 1, 0.1]:
       log_prob = 0
       for w1, w2 in zip(test[:-1], test[1:]):
           p = bigram_prob(w2, w1, alpha=alpha)
           if p > 0:
               log_prob += math.log(p)
           else:
               log_prob += float('-inf')
   
       ppl = math.exp(-log_prob / (len(test) - 1)) if log_prob > float('-inf') else float('inf')
       print(f"平滑 α={alpha}: 困惑度 = {ppl:.2f}")
   

4. 从头实现 TF-IDF，并使用余弦相似度找到与查询最相似的文档。

   import jax.numpy as jnp
   import math
   from collections import Counter
   
   documents = [
       "the cat sat on the mat",
       "the dog chased the cat around the park",
       "a mat was placed on the floor by the door",
       "the quick brown fox jumped over the lazy dog",
   ]
   
   # 构建词汇表
   vocab = sorted(set(word for doc in documents for word in doc.split()))
   word_to_idx = {w: i for i, w in enumerate(vocab)}
   V = len(vocab)
   N = len(documents)
   
   # 计算文档频率
   doc_freq = Counter()
   for doc in documents:
       for word in set(doc.split()):
           doc_freq[word] += 1
   
   # 计算 TF-IDF 矩阵
   tfidf_matrix = jnp.zeros((N, V))
   for i, doc in enumerate(documents):
       word_counts = Counter(doc.split())
       for word, count in word_counts.items():
           tf = 1 + math.log(count)
           idf = math.log(N / doc_freq[word])
           j = word_to_idx[word]
           tfidf_matrix = tfidf_matrix.at[i, j].set(tf * idf)
   
   # 查询
   query = "cat on the mat"
   query_vec = jnp.zeros(V)
   query_counts = Counter(query.split())
   for word, count in query_counts.items():
       if word in word_to_idx:
           tf = 1 + math.log(count)
           idf = math.log(N / doc_freq.get(word, 1))
           query_vec = query_vec.at[word_to_idx[word]].set(tf * idf)
   
   # 余弦相似度（来自第 01 章）
   def cosine_sim(a, b):
       return jnp.dot(a, b) / (jnp.linalg.norm(a) * jnp.linalg.norm(b) + 1e-8)
   
   print(f"查询: '{query}'\n")
   for i, doc in enumerate(documents):
       sim = cosine_sim(query_vec, tfidf_matrix[i])
       print(f"  文档 {i} (相似度={sim:.3f}): '{doc}'")