基于互信息的中文新词发现算法详解
1. 算法题目描述
基于互信息的中文新词发现算法是一种从大规模无标注文本中自动识别新词语（即未收录在现有词典中的词语）的无监督方法。其核心思想是：一个真正的词语，其内部的字与字之间在文本中共同出现的紧密程度（统计关联性）应该远高于随机组合。该算法不依赖预先构建的词典，通过统计分析字串的凝固度（如互信息）和自由度，从语料中自动挖掘出高频、稳定出现的候选新词，例如网络新词、领域术语等。
2. 核心概念与背景
在自然语言处理中，词典是许多任务（如分词、检索）的基础。但语言是动态发展的，新词不断涌现，固定词典难以覆盖。因此，需要一种能自动从海量文本中发现新词的技术。该算法基于一个基本假设：真正的词语，其内部的结合强度高，同时与外部语境的结合又比较灵活。这引出了两个关键指标：
- 凝固度：衡量字串内部字与字之间的结合强度。例如，“咖啡”作为一个词，“咖”和“啡”一起出现的概率应远高于它们随机组合的概率。
- 自由度：衡量字串在文本中出现环境的多样性，即其左右邻接字的丰富程度。一个真正的词应该能灵活地出现在多种语境中，而不是固定搭配的一部分。
3. 算法步骤详解
我们以一个具体例子（从语料中发现“咖啡”这个词）来逐步说明。
步骤1：文本预处理与N-gram候选生成
首先，对原始文本进行最基础的分字处理（即将文本拆分成单个字符序列）。然后，设定一个最大词长（如5个字），滑动窗口遍历字符序列，生成所有可能的子串（N-gram）。
- 例如，句子“我喝了一杯咖啡。”，处理后为字符序列【我， 喝， 了， 一， 杯， 咖， 啡， 。】。
- 滑动窗口（假设最大长度为3）会生成：“我喝”、“喝了”、“了一”、“一杯”、“杯咖”、“咖啡”、“啡。”，以及“我喝了”、“喝了一”等所有可能的2-gram和3-gram。
- 我们将这些子串都作为候选字符串，并统计它们在整个语料库中出现的总频率。
步骤2：计算凝固度（以点式互信息为例）
凝固度最常用的计算方法是点式互信息。对于候选字符串 \(s = c_1c_2...c_n\)（由n个字符组成），其PMI值定义为：
\[PMI(s) = \log_2 \frac{P(s)}{P(c_1)P(c_2)...P(c_n)} \]
其中：
- \(P(s)\) 是字符串 \(s\) 在语料中出现的概率（即频率除以语料总字符数或总子串数）。
- \(P(c_i)\) 是字符 \(c_i\) 在语料中出现的概率。
这个公式的直观理解是：比较字符串实际出现的概率与假设其各个字符独立随机出现时“碰巧”组成该字符串的概率的比值。比值越大（PMI值越高），说明这些字符组合在一起不是偶然，内部结合越紧密。
- 计算示例：假设在亿级规模的语料库中统计得到：
- \(P(咖) = 0.0001\)， \(P(啡) = 0.00005\)
- \(P(咖啡) = 0.00003\)
- 则 \(PMI(咖啡) = \log_2 \frac{0.00003}{0.0001 \times 0.00005} = \log_2 6000 \approx 12.55\)
- 这个值非常高，说明“咖”和“啡”的共现不是偶然。相反，像“了一”这样的组合，虽然频率可能高，但“了”和“一”各自独立出现的概率也很高，计算出的PMI值就会低很多。
对于长度大于2的词，通常计算所有可能二元切分下的最小PMI，以确保词内部各处都足够“凝固”。例如“蛋白质”，计算min(PMI(蛋, 白质)， PMI(蛋白, 质))。
步骤3：计算自由度（左右熵）
仅有高凝固度还不够。例如“茅台酒”中的“台酒”凝固度可能很高，但“台”几乎只出现在“茅”右边，“酒”几乎只出现在“台”左边，自由度低，它不是一个独立的词。自由度通常用信息熵来度量，分为左邻字熵和右邻字熵。
- 左熵：计算候选字符串 \(s\) 的所有左邻字集合的不确定性。
\[ H_{left}(s) = -\sum_{c \in LeftChars} P(c|s) \log_2 P(c|s) \]
其中，$ P(c|s) $ 是字符 $ c $ 出现在 $ s $ 左边的概率（基于语料统计）。
- 右熵：同理，计算所有右邻字集合的熵。
\[ H_{right}(s) = -\sum_{c \in RightChars} P(c|s) \log_2 P(c|s) \]
- 取左右熵中的较小值作为最终的自由度得分：\(Freedom(s) = \min(H_{left}(s), H_{right}(s))\)。
熵值越高，说明邻接字越多样、越随机，候选串作为一个独立单元使用的可能性越大。
- 计算示例：“咖啡”的左邻字可能有“喝”、“买”、“煮”、“冲”等，分布较均匀，左熵高；右邻字可能有“店”、“因”、“杯”、“糖”等，右熵也高。而“台酒”的左邻字可能几乎只有“茅”，左熵极低。
步骤4：综合筛选与排序
现在，对于每个候选子串，我们拥有三个关键指标：频率、凝固度(PMI)、自由度(左右熵最小值)。
设定阈值进行多轮筛选：
- 频率过滤：首先过滤掉出现次数过少的子串（如频率 < 5），以减少计算量并避免噪音。
- 凝固度过滤：保留PMI高于阈值 \(T_{pmi}\) 的候选串。这确保了剩下的都是内部结合紧密的字串。
- 自由度过滤：保留自由度（左右熵最小值）高于阈值 \(T_{entropy}\) 的候选串。这确保了剩下的字串使用语境不僵化。
- 综合排序：对通过过滤的候选串，可以采用加权公式（如
Score = \log(Freq) * PMI * Freedom）进行综合打分，并按分数从高到低排序。排名最前的就是最可能的新词。
步骤5：后处理
- 去冗余：由于算法会生成所有N-gram，结果中可能包含重叠的词语，如“咖啡”和“咖啡店”。需要根据规则（如：如果长词包含短词，且短词分数足够高，则保留短词；或者利用“边界熵”差异）进行去重。
- 人工审核或领域过滤：最终输出的列表通常需要人工校验，或结合特定领域的黑名单/白名单进行二次过滤，以得到最终的新词词典。
4. 算法特点与应用
- 优点：
- 完全无监督：不依赖于任何标注数据或现有词典。
- 可发现任意长度新词：通过设置N-gram最大长度即可。
- 原理直观：基于信息论，可解释性强。
- 局限性：
- 依赖大量高质量文本：统计结果在小型语料上不可靠。
- 无法处理低频新词：频率是基础，低频但重要的术语可能被遗漏。
- 参数敏感：凝固度和自由度的阈值需要根据语料调优。
- 应用场景：
- 扩充分词词典，提升分词系统对未登录词的识别能力。
- 网络舆情监控，自动发现新兴热点词汇。
- 特定领域（如生物医学、金融）的术语自动抽取。
通过以上循序渐进的分析，我们可以理解，基于互信息的新词发现算法本质上是一个在大规模文本中，利用统计信号（高频、高内聚、高灵活）来“大海捞针”的自动化过程，是构建动态语言知识库的重要基础工具。