语言学的计算方法
对应：培养方案 专业选修课 · 三门课合并成一页
课程 学分 学期 内容 标记 计量语言学 2 4 用统计方法研究语言规律（词频分布、依存距离等） ↗ 与信科院共享 语言结构计算 2 4 把语言结构（句法/形态）形式化并计算 ↗ 与信科院共享 语言工程入门 2 3 最浅的一门，偏工具与流程 ↗ 与信科院共享 为什么合成一篇：这三门课的知识结构是同一条链。先把语言现象变成可计数的量
（计量语言学），再把语言结构变成可计算的符号系统（语言结构计算），最后把这两件事
接进一条能跑通的工程流水线（语言工程入门）。拆成三篇会重复三分之二的导论，
而且你看不出它们本来是一件事。合并之后反而多出一样东西：每个环节都能看到上一步
的产物是怎么被下一步消费掉的。前置：这页假设你已经读过同目录的《自然语言处理》和《深度学习原理与实践》，
但方向相反。那两页讲"机器怎么学会做事"，这页讲"怎么用计算去回答语言学问题"。
重叠的部分只有句法树和形式语言，其余不重复。这份笔记怎么用：所有代码都用
~/miniconda3/bin/python实际跑过，
只依赖numpy/scipy（加标准库），语料是你本机现成的 24 篇中文笔记，
不需要下载任何东西。搜索>>> 实跑输出能看到真实结果。
本页实验用的语料只有 28.8 万汉字，属于小样本演示，
每个结论旁边我都会写清楚"这个数字能支持到哪一步"。相关笔记：语言学概念对照
../专业课/教材/笔记-语言学概论.html（下称《语言学概论》）
与../专业课/教材/笔记-现代汉语.html（下称《现代汉语》）；
认知侧对照../专业课/教材/笔记-心理语言学核心.html（下称《心理语言学》）；
工程侧对照../编程/教材/笔记-科研计算.html。
1 导论：这门课在研究什么（先读这个）
1.1 这门课不是什么
误解一："这三门课就是 NLP 的简易版 / 预备课。"
这是本专业学生最容易犯的错，而且错得很自然，因为课名里都有"计算""语言"，
上课也都在敲代码。但两边的目标函数是反的：
- NLP 的目标是让机器做事：翻译、抽取、问答。判据是"下游指标涨没涨"。
语言学知识在 NLP 里只是可选的特征来源，BERT 之后就基本不用了。 - 这三门课的目标是用计算回答语言学问题："汉语的平均依存距离是不是比英语长？""词频
分布到底服从什么分布？""这句话有几个合法结构？"判据是"这个结论在统计上站得住吗"。
一个具体的例子：NLP 里分词是把词切成 token 喂给模型，切错了顶多掉点分；
计量语言学里分词是测量单位的选择，切错了整篇论文的结论都是假的（§1.3 会看到
汉字和字对给出的 Zipf 指数差了整整一倍）。这就是两边最本质的区别。
误解二："计量语言学就是数词频，没什么理论。"
数词频只是第一步。这门课真正的方法论核心是零模型（null model）：
你观察到一个数字，必须回答"如果语言是随机的，这个数字会是多少"。
本页 §3 整个"依存距离"一节的核心是基线怎么设计，那个距离公式反倒次要；
§1.5 我会亲手演示一条"看起来成立、一做零模型检验就塌掉"的著名定律。
不会做零模型的人，做的是数字占卜，不是计量语言学。
误解三："语言结构计算 = 编译原理 / 自动机理论。"
形式语言理论（乔姆斯基层级、自动机、CFG）确实是共用的工具，考试也考这些。
但方向不同：编译原理关心"给定文法，怎么最高效地分析程序"，
语言结构计算关心"给定语言，它的文法应该有多强"。
前者是工程师问题，后者是科学问题。§4 会看到，一个"英语是不是正则语言"的问题
引出了半世纪的语言学争论，而编译原理课根本不问这个。
误解四："语言工程 = 装软件、调 API。"
语言工程入门确实是三兄弟里最浅的一门，但它的深度在流程规范而不在算法：
语料怎么清洗、标注规范怎么定、标注一致性怎么算（不是准确率！）、
评测集怎么切才能不泄漏。这些东西没写好，后面所有模型都是在垃圾上训练。
本页 §6 会把整条流水线画出来，每一站的坑都标出来。
1.2 它在专业里的位置
认知科学与技术 · 专业选修
│
┌───────────────────────────┼───────────────────────────┐
│ │ │
它依赖谁 【本页·三门课】 它被谁依赖
──────────── ┌─────────────────────────┐ ──────────────
· 语言学概论 │ 计量语言学 (学期 4, 2分) │ · 自然语言处理
· 现代汉语 │ 统计 + 语料 -> 语言规律 │ （学期 5）
· 概率统计/数理统计 │ ↓ │ · 大语言模型
· Python / 科学计算栈 │ 语言结构计算 (学期 4, 2分) │ · 心理语言学
· 实验方法论 │ 形式语言 + 自动机 │ （surprisal 框架）
│ ↓ │ · 认知神经科学
│ 语言工程入门 (学期 3, 2分) │ （语言网络建模）
│ 语料 -> 标注 -> 评测 │
└─────────────────────────┘
│
▼
一句话：把"语言"变成"可计算的量"
和隔壁几门课的分工：
| 课程 | 它负责 | 和本页的分界 |
|---|---|---|
| 自然语言处理（学期 5） | 让机器完成语言任务 | 那门问"机器能不能做对"；本页问"用计算能不能证明语言的一条性质" |
| 深度学习原理与实践 | 神经网络的机制与推导 | 那门关心损失怎么降；本页一个神经元都不训练，全部用计数和动态规划 |
| 大语言模型 | 规模上去了发生什么 | 那门关心 10²³ 次浮点运算的世界；本页关心几百个词的小语料能得出什么 |
| 语言学概论 / 现代汉语 | 语言的结构事实 | 那两门告诉你"汉语有 X 现象"；本页告诉你"怎么把 X 变成一个可检验的数字" |
| 心理语言学 | 人怎么做语言加工 | 那门用反应时/眼动；本页用语料里的统计规律去侧面支持加工理论（§7） |
| 实验方法论核心 | 怎么设计实验 | 那门是行为实验的零模型；本页是语料统计的零模型，逻辑同源 |
这条线是专业选修板块里唯一一条把"语言学"当研究对象、把"计算"当工具的方向。
NLP 那条线最终通向就业，这条线最终通向研究，两条线共用同一套编程技能，
但问的问题完全不同。
1.3 真正要教你的能力
具体、可检验，一共四条：
-
能把一条"语言规律"写成可检验的定量假设，并配一个零模型。
给你一句话（比如"汉语倾向于把长成分放在后面"），你能说出：怎么度量、在什么语料上测、
什么样的随机基线算公平、以及结果差多少才算"有效应"。
检验方式：做 §8 第 3、5 题，动手做 §3.4 的代码。 -
能手算一个双对数拟合，并知道它什么时候在骗你。
给你一张名次-频次的表，你能算出 log-log 斜率和 Pearson $r$，能说出
"$r = -0.93$ 看起来不错，但这条直线在头部外推了 700 万次"。
检验方式：§1.2 的代码，把语料换成任意一段文本重跑。 -
能手工做依存句法标注，并算出平均依存距离。
给你 10 个汉语句子，你能标出每个词的支配词、算出 MDD、再算出随机语序下的 MDD。
这是计量语言学最标志性的一项技能，也是本页 §3 的全部内容。 -
能把一个歧义句交给算法，并读懂它的输出。
给你一套 CFG 和一句话，你能手工写出 CNF、手工填出 CYK 表格、
说出这句话有几种结构、每种结构在语言学上意味着什么。
检验方式：§5.5 的代码，把句子换成「咬死了猎人的狗」自己试着设计文法。
1.4 这份笔记的组织逻辑 / 怎么读
组织的原则是：先把语言变成可计数的量（§1-§2），再用这些量回答一个真问题（§3），
然后把语言结构本身形式化（§4），再让机器去算这些结构（§5），
最后接到工程流水线上（§6）。
导论 ▸ 坐标系：这三门课 vs NLP
│
▼
§1 词频分布三定律 ★★★ ▸ Zipf / Heaps / Menzerath-Altmann
│ 每个都用本机语料真实跑过
│ 含一条"实跑发现它不成立"的定律
▼
§2 搭配的统计度量 ★★ ▸ 2x2 列联表 -> MI / t-score / LLR
│ 两个可以自己推的恒等式
▼
§3 依存距离最小化 ★★★ ▸ 本页最重要的一节
│ 计量语言学最著名的发现 + 基线设计
▼
§4 语言结构的形式化 ★★ ▸ 乔姆斯基层级 / FST
│ 「自然语言不是正则语言」的严格证明
▼
§5 句法计算：CFG 与 CYK ★★★ ▸ 手写 CYK，看它吐出两棵句法树
│
▼
§6 语言工程入门 ▸ 语料 -> 清洗 -> 标注 -> 模型 -> 评测
│
▼
§7 和你专业的关系 -> §8 习题 -> §9 出处索引
阅读顺序建议：
- 第一遍（别停）：只读每节的"直觉"和代码后面的输出。跳过所有 $\sum$ 和 $\log$。
目标是建立"这门课在算什么、算出来的数字长什么样"的手感。 - 第二遍（拿纸笔）：死磕 §1.3（为什么字频的尾巴塌了）、§2.5（两个恒等式）、
§4.5（非正则性的证明）、§5.4（CYK 的表格怎么填）。这四处是本页的智力核心。 - 第三遍（动手改）：把 §1.2 的语料路径换成任意一个
.md文件重跑；
把 §3.4 的句子改一句你自己的汉语重新标注；把 §5.5 的文法改一条规则。
改一个数看输出怎么变，比读十遍公式有用。 - 考试前：只看 §8 习题、每节的"边界与批评"、和 §4.1 的层级表。
一页速查：
| 符号 | 读法 | 含义 | 本页典型值 |
|---|---|---|---|
| $N$ | token 数 | 语料一共多少个单位 | 288365（汉字） |
| $V$ | type 数 | 一共多少种不同的单位 | 2095（汉字） |
| $f(r)$ | 名次频次 | 第 $r$ 高频单位的出现次数 | 11028（"的"） |
| $\alpha$ | Zipf 指数 | 双对数直线的斜率绝对值 | ≈1（字对）/ ≈1.9（汉字） |
| $\beta$ | Heaps 指数 | 词表增长率 | 0.25（汉字）/ 0.70（字对） |
| $\mathrm{DD}$ | 依存距离 | $\lvert i-j\rvert$，支配词与从属词的位置差 | 1 ~ 7 词 |
| $\mathrm{MDD}$ | 平均依存距离 | 一句里所有 DD 的平均 | 1.69 词（本页小库） |
| $\mathrm{LLR}$ | 对数似然比 | 搭配显著性，可加、可比较 | 26.7 ~ 17976 |
2 词频分布：三条定律，和一条"跑不出来"的定律
这一节处理"语言里的量"。它要回答的是一个很朴素的问题：
一段自然语言里，各个单位出现的次数是怎么分布的？问出这个问题的那一刻，
语言学就变成了一门可以做定量研究的学科，因为分布是可以检验、可以证伪的东西。
2.1 Zipf 定律：名次 × 频次 ≈ 常数
它想解决什么：如果你把一段文本里所有词按出现次数从多到少排列，
第 1 名（"的"）、第 2 名、第 100 名、第 1000 名的频次之间有关系吗？
1949 年 Zipf 发现了一个规律：
$$f(r) \;\propto\; \frac{1}{r^{\alpha}}, \qquad \alpha \approx 1$$
逐项解释：
- $r$ 是名次（rank），从 1 开始，1 是最高频的那个单位；
- $f(r)$ 是名次为 $r$ 的单位的频次；
- $\alpha$ 是指数。$\alpha = 1$ 是最常被引用的形式，意思是"名次翻一倍，频次减一半"；
- $\propto$ 表示"成正比"，因为真实的常数取决于文本长度，不重要。
取对数之后，这条公式变成一条直线，这是它好用的原因：
$$\log f(r) = \underbrace{\log C}_{\text{截距}} \;-\; \alpha \underbrace{\log r}_{\text{自变量}}$$
所以检验 Zipf 定律的标准操作是：把 $(r, f(r))$ 画在双对数坐标里，
做一次最小二乘直线拟合，看斜率是不是 $-1$、看 Pearson 相关系数 $r$ 有多高。
$-1$ 这个数是理论预测，不是拟合出来的，这是它和"随便找个函数拟合数据"的根本区别。
为什么会有一条这样的定律（三个层次的解释，从浅到深）：
- 省力原则（Zipf 1949）：说话人想省力 → 常用词就反复用；听话人想省力 →
希望词和意义一一对应（也就是词表要大）。两个力平衡的结果就是"少数词用得多、
多数词用得少"。 - 随机打字模型（Miller 1957）：假设一只猴子在键盘上随机敲，把"空格"当成词边界，
敲出来的"词"的频次分布会自动服从 Zipf 定律。这一条很重要，它说明
观察到一个服从幂律的分布，本身不能证明语言有什么特殊设计，
因为无记忆的随机过程也能产生它。这个教训会在 §1.5 和 §3 反复出现。 - 信息论推导（Mandelbrot 1953）：在"每个词有代价、要最小化平均编码长度"的
假设下，最优编码给出的分布是 $f(r) = C/(r+b)^{\alpha}$，比纯幂律多了一个
位移参数 $b$。这个 $b$ 就是本页 §1.2 用来救场的那一项。
2.2 实跑：用本机 24 篇中文笔记验证 Zipf 定律
语料：/Users/mamingyu/Desktop/大一/专业课/教材/*.md，24 个文件，580532 个字符
（含标点、代码、公式），其中 288365 个汉字。
单位的选择：Zipf 定律的经典对象是词。
汉语书写没有空格，要得到"词"必须先分词，而本机没有 jieba。
所以我们做两级对照：
- 单位 A = 汉字（不需要分词，直接取所有 CJK 字符）；
- 单位 B = 句内相邻字对（同一句话里两个紧挨着的汉字，不跨标点）。
字对不是"词"，但它的 type 数（43704）和"词表"是同一个量级，
尾部足够长，可以拿来看幂律成不成立。
# 语料：本机现成的 24 篇中文笔记（纯文本，不需要下载任何东西）
import glob, re
from collections import Counter
import numpy as np
FILES = sorted(glob.glob('/Users/mamingyu/Desktop/大一/专业课/教材/*.md'))
text = "".join(open(f, encoding='utf-8').read() for f in FILES)
print("语料：%d 个文件，%d 个字符（含标点/代码）" % (len(FILES), len(text)))
def fit_zipf(freqs):
"""给出一个频次列表，返回 (频次数组, 名次数组, 双对数斜率, 截距, Pearson r)"""
f = np.array(sorted(freqs, reverse=True), dtype=float) # 频次降序
r = np.arange(1, len(f) + 1, dtype=float) # 名次 1,2,3,...
lr, lf = np.log10(r), np.log10(f)
b, a = np.polyfit(lr, lf, 1) # 最小二乘直线
return f, r, b, a, np.corrcoef(lr, lf)[0, 1]
# ---------- 单位 1：汉字 ----------
hanzi = re.findall(r'[一-鿿]', text)
f1, r1, b1, a1, rho1 = fit_zipf(Counter(hanzi).values())
print("\n【单位 A】汉字： %d 字次，%d 字种" % (len(hanzi), len(f1)))
print(" log10(f) = %.4f + (%.4f)·log10(r) Pearson r = %.4f，r² = %.4f"
% (a1, b1, rho1, rho1**2))
print(" 若是严格 Zipf，斜率应为 -1；最高频字的频次 = %d，故理想截距 = %.4f"
% (f1[0], np.log10(f1[0])))
print(" 最高频 10 字：%s" % "".join(c for c, _ in Counter(hanzi).most_common(10)))
print(" 分段看（每一段单独拟合，斜率差得非常远）：")
print(" 名次区间 字种数 斜率 b Pearson r")
for lo, hi in [(1, 10), (11, 100), (101, 500), (501, 1000), (1001, len(f1))]:
m = (r1 >= lo) & (r1 <= hi)
bb, aa = np.polyfit(np.log10(r1[m]), np.log10(f1[m]), 1)
print(" %5d - %5d %7d %8.4f %9.4f"
% (lo, hi, m.sum(), bb, np.corrcoef(np.log10(r1[m]), np.log10(f1[m]))[0, 1]))
# ---------- 单位 2：句内相邻字对 ----------
chunks = [s for s in re.split(r'[^一-鿿]+', text) if len(s) > 1]
bigram = Counter(s[i:i+2] for s in chunks for i in range(len(s) - 1))
f2, r2, b2, a2, rho2 = fit_zipf(bigram.values())
print("\n【单位 B】句内相邻字对： %d 个字对次，%d 个字对种" % (sum(bigram.values()), len(f2)))
print(" log10(f) = %.4f + (%.4f)·log10(r) Pearson r = %.4f，r² = %.4f"
% (a2, b2, rho2, rho2**2))
print(" 最高频 10 个字对：%s" % " ".join(c for c, _ in bigram.most_common(10)))
# ---------- Mandelbrot 三参数修正 ----------
from scipy.optimize import curve_fit
def mandelbrot(r, C, bb, aa): # f(r) = C / (r + b)^a
return C / (r + bb) ** aa
popt, _ = curve_fit(mandelbrot, r1, f1, p0=(f1[0], 1.0, 1.0), maxfev=20000)
pred_m = mandelbrot(r1, *popt)
pred_z = 10 ** (a1 + b1 * np.log10(r1))
ss = np.sum((f1 - f1.mean()) ** 2)
print("\n【Mandelbrot 修正】f(r) = C / (r + b)^a （在原始频次尺度上比较）")
print(" 纯 Zipf 直线 ： R² = %.4f" % (1 - np.sum((f1 - pred_z) ** 2) / ss))
print(" Mandelbrot 三参数： C = %.1f, b = %.4f, a = %.4f，R² = %.4f"
% (popt[0], popt[1], popt[2], 1 - np.sum((f1 - pred_m) ** 2) / ss))
print(" 最大频字：实际 %d，纯 Zipf 直线外推 %.0f，Mandelbrot %.0f"
% (f1[0], pred_z[0], pred_m[0]))
# ---------- 集中度 ----------
print("\n【集中度】")
for k in (10, 100, 1000):
print(" 前 %4d 高频字覆盖全部字次的 %5.1f%%" % (k, 100 * f1[:k].sum() / len(hanzi)))
print(" 只出现 1 次的字种 %d 个（占字种 %.1f%%），合计只占字次 %.2f%%"
% ((f1 == 1).sum(), 100 * (f1 == 1).mean(), 100 * f1[f1 == 1].sum() / len(hanzi)))
实跑输出
语料：24 个文件，580532 个字符（含标点/代码）
【单位 A】汉字： 288365 字次，2095 字种
log10(f) = 6.8568 + (-1.9398)·log10(r) Pearson r = -0.9267，r² = 0.8588
若是严格 Zipf，斜率应为 -1；最高频字的频次 = 11028，故理想截距 = 4.0425
最高频 10 字：的是一这个不学你么有
分段看（每一段单独拟合，斜率差得非常远）：
名次区间 字种数 斜率 b Pearson r
1 - 10 10 -0.6429 -0.9806
11 - 100 90 -0.5729 -0.9952
101 - 500 400 -1.2467 -0.9867
501 - 1000 500 -2.5623 -0.9991
1001 - 2095 1095 -4.2931 -0.9873
【单位 B】句内相邻字对： 234761 个字对次，43704 个字对种
log10(f) = 4.5111 + (-0.9983)·log10(r) Pearson r = -0.9828，r² = 0.9658
最高频 10 个字对：什么 一个 这个 不是 语言 就是 问题 教育 怎么 为什
【Mandelbrot 修正】f(r) = C / (r + b)^a （在原始频次尺度上比较）
纯 Zipf 直线 ： R² = -126960.9694
Mandelbrot 三参数： C = 19774.1, b = 1.1681, a = 0.7977，R² = 0.9745
最大频字：实际 11028，纯 Zipf 直线外推 7190707，Mandelbrot 10667
【集中度】
前 10 高频字覆盖全部字次的 17.5%
前 100 高频字覆盖全部字次的 51.6%
前 1000 高频字覆盖全部字次的 98.1%
只出现 1 次的字种 277 个（占字种 13.2%），合计只占字次 0.10%
（跑的时候你会看到一行 RuntimeWarning: invalid value encountered in power。
这是无害的：curve_fit 在搜索参数时会把 $b$ 试成负数，
此时 $(r+b)$ 可能为负、分数次幂在实数域无定义，于是 numpy 报一句警告。
最终收敛到的参数是合法的，结果不受影响。看到警告不要慌，但也别一律忽略，
判断标准永远是"最终结果对不对"，不是"有没有警告"。）
这张输出里有四个地方必须看懂。
2.3 为什么汉字的尾巴塌了（本节最值钱的一段）
第一，汉字全秩的斜率是 $-1.94$，不是 $-1$。但这个数字本身没有意义，
因为分段拟合显示斜率从 $-0.64$（头部）一路变到 $-4.29$（尾部）。
一条用五段不同斜率的折线拼起来的曲线，用一条直线去拟合，得到的斜率
是"平均"出来的假象。
第二，为什么汉字的尾部会陡到 $-4.29$？因为汉字的字表是有限的。
常用汉字只有几千个，我们的语料只出现了 2095 种。幂律的尾巴之所以能一直是直线，
靠的是"总能有更罕见的单位冒出来"，词可以有上百万种，字只有几千种。
到了名次 1000 之后，你能数到的字已经数完了，剩下的只是"这些字碰巧又出现了几次"，
于是分布被硬生生截断，曲线向下猛掉。
这不是语言的性质，是书写系统的性质。
第三，换成字对（单位 B），斜率立刻变成 $-0.9983$，$r = 0.983$，
几乎是教科书级别的 Zipf 分布。字对的"表"有 43704 种而且还在增长，
尾部够长，幂律就有空间成立。这两级的对比说明了一件事：
Zipf 定律不是语言的神秘属性，它是"符号表足够大、增长不受限"时幂律分布的自然结果
（回想 §1.1 的 Miller 1957 随机打字模型）。同时它也说明了另一件事：
"选哪个单位"不是细节，它决定你的结论。这正是 §6 语言工程里分词为什么重要的统计学理由。
第四，注意 Mandelbrot 那一行里那个吓人的 $R^2 = -126960$。
这是本页第一个"拟合优度会骗人"的例子，值得单独讲：
- 双对数坐标下的最小二乘，对每一个名次点的误差一视同仁。语料里尾部有 1000 多个点，
头部只有几十个点，所以直线被尾部"拽"着走。 - 结果就是：直线在 $r=1$ 处外推给出 7190707 次，而实际最高频的"的"只有 11028 次。
差了 650 倍。回到原始尺度一看，$R^2$ 直接变成负数（$R^2$ 为负表示
"比直接用平均值预测还差"）。 - 换成 Mandelbrot 的 $f(r) = C/(r+b)^{a}$，多了一个位移参数 $b$（来自 §1.1 的信息论推导），
$R^2$ 立刻回到 0.9745，头部预测 10667 次（实际 11028，误差 3%）。
教训：双对数坐标里的 $r = -0.93$ 看着挺像直线，实际上这条直线在头部完全失效。
永远要把拟合曲线画回原始尺度看一眼残差，不能只看 $r$。
2.4 Heaps 定律：词表随文本增长
它想解决什么：Zipf 定律描述的是一个静态的分布（语料已经收集完了，看频次怎么排）。
Heaps 定律描述的是动态过程：边读边数，读得越多，遇到的新词越多，但新词的增长越来越慢。
$$V(N) = K \cdot N^{\beta} \qquad\Longleftrightarrow\qquad \log V = \log K + \beta \log N$$
逐项解释：
- $N$ 是已经读过的 token 总数（读到第 $N$ 个位置）；
- $V(N)$ 是到那一刻为止见过的 type 数（不同单位的个数）；
- $K$ 是比例常数（取决于语料，没有理论意义）；
- $\beta$ 是 Heaps 指数，这是唯一有意义的参数。自然语言里常见 $0.4 < \beta < 0.6$。
$\beta = 1$ 意味着"每读到一个 token 都是新词"（没有词汇重复）；
$\beta = 0$ 意味着"读多少都是那几个词"（词表封顶）。
为什么它重要：$\beta$ 直接决定"要读多少数据才能覆盖语言"。
信息检索里估计索引大小、统计里估计"还要多少语料才够"，都靠这个数。
它和 Zipf 定律是一体两面：Zipf 的指数越大，Heaps 的指数越小（近似 $\beta = 1/\alpha$，
但这个关系只在纯幂律且 $\alpha > 1$ 时成立，本页的数据不满足，所以下面实测值对不上，
这本身是个可讨论的练习，见 §8 第 2 题 (d)）。
# 接着上面的语料。按文本自然顺序吃 token，每 2000 个记录一次 (N, V)
import glob, re
import numpy as np
text = "".join(open(f, encoding='utf-8').read()
for f in sorted(glob.glob('/Users/mamingyu/Desktop/大一/专业课/教材/*.md')))
def growth(tokens, step):
seen, out = set(), []
for i, t in enumerate(tokens, 1):
seen.add(t)
if i % step == 0:
out.append((i, len(seen)))
out.append((len(tokens), len(seen)))
return np.array(out, dtype=float)
def fit_heaps(tokens, step, tag):
a = growth(tokens, step)
N, V = a[:, 0], a[:, 1]
m = N >= 1000 # 丢掉最初那段（还没进入幂律区）
b, c = np.polyfit(np.log10(N[m]), np.log10(V[m]), 1)
print("%s N=%d, V=%d" % (tag, int(N[-1]), int(V[-1])))
print(" 拟合段 N>=1000：log10(V) = %.4f + %.4f·log10(N) r = %.4f"
% (c, b, np.corrcoef(np.log10(N[m]), np.log10(V[m]))[0, 1]))
print(" -> Heaps: beta = %.4f, K = %.3f" % (b, 10 ** c))
print(" 抽样点 (N,V)：", " ".join("(%d,%d)" % (n, v)
for n, v in a[::max(1, len(a) // 8)]))
hanzi = re.findall(r'[一-鿿]', text)
fit_heaps(hanzi, 2000, "\n【单位 A】汉字")
chunks = [s for s in re.split(r'[^一-鿿]+', text) if len(s) > 1]
fit_heaps([s[i:i+2] for s in chunks for i in range(len(s)-1)], 2000, "\n【单位 B】句内相邻字对")
实跑输出
【单位 A】汉字 N=288365, V=2095
拟合段 N>=1000：log10(V) = 1.9636 + 0.2505·log10(N) r = 0.9904
-> Heaps: beta = 0.2505, K = 91.962
抽样点 (N,V)： (2000,462) (38000,1342) (74000,1548) (110000,1674) (146000,1820) (182000,1890) (218000,1982) (254000,2051) (288365,2095)
【单位 B】句内相邻字对 N=234761, V=43704
拟合段 N>=1000：log10(V) = 0.8929 + 0.7006·log10(N) r = 0.9989
-> Heaps: beta = 0.7006, K = 7.814
抽样点 (N,V)： (2000,1293) (30000,11088) (58000,17333) (86000,22474) (114000,27453) (142000,31853) (170000,35853) (198000,39523) (226000,42889)
怎么读这两个 $\beta$：
- 汉字 $\beta = 0.2505$：远低于自然语言的常见区间 $0.4\sim0.6$。原因和 §1.3 完全一样，
字表封顶了。抽样点看得很清楚：读到 20 万汉字时已经有 1982 种，读到 28.8 万才 2095 种，
最后 7 万字只带来 44 个新字。曲线正在压平，$\beta$ 只是它压平过程中的一个瞬时斜率。 - 字对 $\beta = 0.7006$：比常见区间偏高，因为字对的"表"极大（43704 种且远未饱和），
新字对还在源源不断地冒出来。抽样点显示每读 2.8 万字还在新增 3000 多个 type。 - 更有意义的读法是"外推"：$\beta = 0.7$ 意味着语料翻 10 倍，type 数只翻
$10^{0.7} \approx 5$ 倍。想覆盖现在两倍的词汇量，要把语料扩大
$2^{1/0.7} \approx 2.7$ 倍。这就是"语料永远不够大"的定量表达。
2.5 Menzerath-Altmann 定律：一条实跑发现不成立的定律
它想解决什么：Zipf 和 Heaps 都是关于"词"的。Menzerath 定律往上走一层，
问的是结构层级之间的关系：语言是分层组织的（篇章 > 段落 > 句子 > 分句 > 词 > 音节）。
Menzerath 在 1954 年提出、Altmann 在 1980 年形式化了一个猜想：
一个构造（construct）包含的成分越多，这些成分本身就越小。
原型例子：一个句子里的分句越多，每个分句就越短。数学形式是
$$y = a \cdot x^{b} \cdot e^{-c\,x} \qquad \Longleftrightarrow \qquad \log y = \log a + b\log x - c\,x$$
逐项解释：$x$ 是上级单位的"组成成分个数"（比如一个句子有几个分句），
$y$ 是下级单位在上一级里的平均大小（比如平均分句长度）；$a, b, c$ 是拟合参数。
多出来的 $e^{-cx}$ 项是这个形式比纯幂律强的地方：它让曲线在 $x$ 很大时向下弯，
能刻画"越到后面，成分越短"的加速效应。$c = 0$ 时就退化成普通的幂律 $y = ax^b$。
这条定律为什么值得单独讲：因为它是本页唯一一条我们跑出来、结果不成立的定律。
而"跑不出来"这件事本身，是这门课最该学会的东西。
# 句子 -> 分句 这一层：中文里按 。！？ 切句，按 ，、；： 切分句
import glob, re
import numpy as np
text = "".join(open(f, encoding='utf-8').read()
for f in sorted(glob.glob('/Users/mamingyu/Desktop/大一/专业课/教材/*.md')))
FENCE = chr(96) * 3 # 三个反引号（不直接写，避免嵌套围栏）
body = re.sub(FENCE + '.*?' + FENCE, '', text, flags=re.S) # 先把代码块删掉
rows = []
for s in re.split(r'[。！？]', body):
s = re.sub(r'[^一-鿿，、；：]', '', s) # 只留汉字和句内标点
parts = [p for p in re.split(r'[，、；：]', s) if p]
if len(parts) < 2:
continue
rows.append((len(parts), float(np.mean([len(p) for p in parts])), len(s)))
d = np.array(rows)
print("有效句子（>=2 个分句）：%d 句，共 %d 个分句" % (len(d), int(d[:, 0].sum())))
print("\n[1] 相关性（句子的分句数 vs 它的平均分句长度）")
print(" Pearson r = %+.4f" % np.corrcoef(d[:, 0], d[:, 1])[0, 1])
lx, ly = np.log10(d[:, 0]), np.log10(d[:, 1])
b, a = np.polyfit(lx, ly, 1)
print(" 双对数: log10(平均分句长) = %.4f + (%+.4f)·log10(分句数), r = %+.4f"
% (a, b, np.corrcoef(lx, ly)[0, 1]))
print("\n[2] 分箱看（按分句数分组，组内求平均分句长度）")
print(" 分句数 n 句子数 平均分句长度(字) 平均整句长(字)")
for n in range(2, 16):
m = d[:, 0] == n
if m.sum() >= 5:
print(" %6d %8d %14.2f %14.1f"
% (n, m.sum(), d[m, 1].mean(), d[m, 2].mean()))
m = d[:, 0] >= 16
print(" %6s %8d %14.2f %14.1f"
% (">=16", m.sum(), d[m, 1].mean(), d[m, 2].mean()))
print("\n[3] 零模型：把所有分句从句子中拆散、随机重新组装成同样大小的句子，看 r 会是多少")
rng = np.random.default_rng(0)
pool = []
for s in re.split(r'[。！？]', body):
s = re.sub(r'[^一-鿿，、；：]', '', s)
pool += [len(p) for p in re.split(r'[，、；：]', s) if p]
pool = np.array(pool)
sizes = d[:, 0].astype(int)
rs = []
for _ in range(200):
p = rng.permutation(pool)
idx, xs, ys = 0, [], []
for n in sizes:
seg = p[idx:idx + n]; idx += n
if len(seg):
xs.append(len(seg)); ys.append(seg.mean())
rs.append(np.corrcoef(xs, ys)[0, 1])
rs = np.array(rs)
print(" 随机重排 200 次：r 的均值 %+.4f，标准差 %.4f，95%% 区间 [%+.4f, %+.4f]"
% (rs.mean(), rs.std(), np.percentile(rs, 2.5), np.percentile(rs, 97.5)))
print(" 实测 r = %+.4f" % np.corrcoef(d[:, 0], d[:, 1])[0, 1])
print("\n[4] 换一种切分方式，结论会不会变？（这是稳健性检查）")
for tag, seps in [("含顿号 ，、；：", "，、；："), ("不含顿号 ，；：", "，；："), ("只按逗号 ，", "，")]:
rr = []
for s in re.split(r'[。！？]', body):
s2 = re.sub(r'[^一-鿿' + seps + r']', '', s)
ps = [p for p in re.split(r'[' + seps + r']', s2) if p]
if len(ps) >= 2:
rr.append((len(ps), np.mean([len(p) for p in ps])))
rr = np.array(rr)
print(" %s：%d 句，r = %+.4f" % (tag, len(rr), np.corrcoef(rr[:, 0], rr[:, 1])[0, 1]))
实跑输出
有效句子（>=2 个分句）：6396 句，共 21564 个分句
[1] 相关性（句子的分句数 vs 它的平均分句长度）
Pearson r = -0.0065
双对数: log10(平均分句长) = 1.0358 + (-0.0082)·log10(分句数), r = -0.0084
[2] 分箱看（按分句数分组，组内求平均分句长度）
分句数 n 句子数 平均分句长度(字) 平均整句长(字)
2 2389 11.99 25.0
3 1823 11.41 36.3
4 1000 11.27 48.1
5 583 11.43 61.2
6 297 11.72 75.4
7 133 12.23 91.7
8 69 12.14 104.1
9 34 12.74 122.8
10 21 13.50 144.0
11 14 11.58 137.5
12 9 12.06 155.7
13 10 12.81 178.5
14 6 12.33 185.7
>=16 6 11.67 238.0
[3] 零模型：把所有分句从句子中拆散、随机重新组装成同样大小的句子，看 r 会是多少
随机重排 200 次：r 的均值 +0.0008，标准差 0.0103，95% 区间 [-0.0206, +0.0222]
实测 r = -0.0065
[4] 换一种切分方式，结论会不会变？（这是稳健性检查）
含顿号 ，、；：：6396 句，r = -0.0065
不含顿号 ，；：：6219 句，r = +0.0119
只按逗号 ，：5323 句，r = +0.0230
这张输出在说什么：Menzerath-Altmann 定律在这份语料、这个层级、这个测量方式下
完全没有出现。
- 相关系数 $r = -0.0065$，基本就是 0。
- 分箱表更直观：不管一个句子有 2 个分句还是 14 个分句，
平均分句长度都稳定在 11.3 ~ 13.5 字之间，几乎是常数。
（唯一的系统性变化是整句长度在稳定增长，但那是因为分句多了，不是因为分句变短了。） - 零模型告诉他这个 $-0.0065$ 一点都不意外：把 21564 个分句全部拆散、
随机重组成跟原来一样长度的句子，跑 200 次得到的 $r$ 分布是
$[+0.0008 \pm 0.0103]$。实测值老老实实待在这个分布的正中间。 - 稳健性检查更狠：换一种分句切分方式，$r$ 的符号直接翻正了
（$-0.0065 \to +0.0119 \to +0.0230$）。结论的符号取决于你怎么定义"分句"，
那这个结论就不该被当成定律。
怎么理解这个负面结果？有三种可能，必须分开说清楚：
- 测量方式的问题：原版 Menzerath 定律测量的是"音节/词"这类音系-形态单位，
我们用的是"字"。中文里"字"同时是音节和语素，用它当分句长度单位是一个偷懒的近似。
所以我不能说"Menzerath 定律是错的"，只能说"本页这个测量测不出来"。 - 语料的问题：这是 24 篇教学笔记，不是自然语言文本。笔记的句子偏短、
结构偏简单（大量的小标题、列表句），可能本来就缺乏长句。 - 定律本身的问题：这一条有真实的文献支持。Torre、Dębowski 和 Hernández-Fernández
2021 年在 PLoS ONE 上证明：一个"猴子打字"式的无记忆信源也能生成符合
Menzerath 定律形式的规律。也就是说，即使观察到这条定律，也不能推出
"语言有高效的设计"。同一方向还有 Benešová & Čech 2015 把 Menzerath-Altmann
定律和随机模型做对比的工作。
这一节的真正价值在于它演示了计量语言学的完整操作流程：
提出假设 → 度量 → 拟合 → 零模型 → 稳健性检查 → 如实报告。
其中第 5 步和第 3 步最关键：看到一条拟合直线就宣布"定律"，
是这门学科最容易犯的错误。这个教训在 §3 会再一次出现，而且那次我们要主动
用零模型来做结论。
2.6 边界与批评（词频分布）
- 小样本：28.8 万汉字，24 个文件，而且都是同一个人（AI 辅助）写的教学笔记，
不是自然语言语料。所有数字都是演示性质的，不能当作汉语的总体参数。 - 单位问题：汉语没有分词器时只能用字或字对近似，§1.3 已经看到这两者给出的
Zipf 指数差了近一倍。任何"汉语的词频统计"都必须先交代分词规范。 - Zipf 定律不是语言独有的：城市人口、姓氏分布、网页链接数、地震震级都服从幂律。
所以"语言服从 Zipf"这件事本身没有解释力，有解释力的是偏离幂律的那部分
（比如 §1.2 里头部斜率只有 $-0.6$，说明常用词的使用比纯幂律更集中）。 - 拟合方法本身有陷阱：双对数坐标 + 最小二乘（本页用的方法）在尾部噪声大时偏差严重。
更严谨的做法是 Clauset、Shalizi & Newman 2009 在 SIAM Review 上系统论述的
极大似然估计 + KS 距离检验。本页 §1.2 的alpha_MLE就是那个思路的简化版
（未展开，可作拓展阅读）。 - "定律"这个词要打折：Zipf 和 Heaps 是稳定的经验规律（在各种语言、各种语料上
反复出现），Menzerath-Altmann 是有争议的（§1.5）。同一个学科里，
三个"定律"的可信度完全不同，读文献时必须区分。
3 搭配的统计度量：MI、t-score、对数似然比
3.1 问题：什么算"搭配"
"搭配（collocation）"指的是习惯上总一起出现的词组合：汉语的"提出"、"进行"、"研究"，
英语的 strong tea 而不是 powerful tea。人类判断"这两个词是不是搭配"很准，
但要教给机器，必须先把它变成一个数。
朴素的想法是"数它们一起出现的次数"。这行不通，因为高频词之间天然会一起出现：
"的"和"是"在语料里挨着的次数一定很多，但它们不构成任何搭配。
所以真正要衡量的是：它们一起出现的次数，比"如果它们彼此无关，本该出现的次数"，高出多少？
这个"本该出现的次数"就是期望频次，它的计算公式由独立性假设给出，
这正是概率论里 $P(A \cap B) = P(A)P(B)$ 的直接应用。
3.2 2×2 列联表：所有搭配度量都长在它上面
对每一对候选 $(w_1, w_2)$，统计四格：
| $w_2$ 出现 | $w_2$ 没出现 | 合计 | |
|---|---|---|---|
| $w_1$ 出现 | $O_{11}$（观测的共现次数） | $O_{12} = R_1 - O_{11}$ | $R_1$（$w_1$ 的总次数） |
| $w_1$ 没出现 | $O_{21} = C_2 - O_{11}$ | $O_{22} = N - R_1 - C_2 + O_{11}$ | $N - R_1$ |
| 合计 | $C_2$（$w_2$ 的总次数） | $N - C_2$ | $N$（语料总 token 数） |
逐项解释：
- $N$：语料里一共有多少个可比的单位（本页是 234761 个字对 token）；
- $O_{11}$：$w_1$ 和 $w_2$ 实际紧挨着出现的次数（观测值）；
- $R_1$：$w_1$ 作为左元素出现的总次数（边缘和）；
- $C_2$：$w_2$ 作为右元素出现的总次数（边缘和）；
- $E_{11}$：期望频次，即"如果 $w_1$ 和 $w_2$ 完全没关系，它们本该共现多少次"：
$$E_{11} \;=\; \frac{R_1 \times C_2}{N}$$
这个公式为什么长这样：若两个事件独立，则 $P(w_1, w_2) = P(w_1)P(w_2)$。
两边乘 $N$ 就得到 $E_{11} = N \cdot \frac{R_1}{N} \cdot \frac{C_2}{N} = \frac{R_1 C_2}{N}$。
分子是"实际"，分母是"如果无关"，所有搭配度量都是在比较这两个数。
3.3 三种度量，三种"比较方式"
① 互信息（MI）：直接取比值，再取对数把尺度拉平。
$$\mathrm{MI}(w_1, w_2) = \log_2 \frac{O_{11}}{E_{11}}$$
读法是"实际是期望的多少倍"。$\mathrm{MI} = 3$ 表示"共现次数是随机预期的 $2^3 = 8$ 倍"。
取 $\log_2$ 是因为比值本身是指数级的，取对数后才能和别的对子放在一起比较。
（出处：Church & Hanks 1990，Computational Linguistics。）
② t 值（t-score）：不看比值，看绝对差值相对于噪声有多大。
$$t = \frac{O_{11} - E_{11}}{\sqrt{O_{11}}}$$
逐项解释：分子是"超出预期多少"，分母是"噪声的尺度"。
为什么分母是 $\sqrt{O_{11}}$？因为如果共现是泊松过程，$O_{11}$ 的方差近似等于它的均值，
所以标准差约为 $\sqrt{O_{11}}$。t 值就是"超出预期多少个标准差"，和统计里的 t 检验同源。
③ 对数似然比（LLR）：不只看第一格，而是把四格的偏差全加起来。
$$\mathrm{LLR} = 2\sum_{i,j \in \{1,2\}} O_{ij} \ln \frac{O_{ij}}{E_{ij}}, \qquad E_{ij} = \frac{(\text{第 } i \text{ 行和})(\text{第 } j \text{ 列和})}{N}$$
逐项解释：这是一次似然比检验（$H_0$：两词独立 vs $H_1$：不独立）。
每一项 $O_{ij}\ln(O_{ij}/E_{ij})$ 是"这一格贡献了多少证据"，
当 $O_{ij} > E_{ij}$ 时贡献为正、反之为负，$2$ 是使统计量渐近服从 $\chi^2_1$ 分布的常数。
约定 $O_{ij} = 0$ 时该项取 0（$0\ln 0 = 0$），这个约定很关键，代码里会专门处理。
（出处：Dunning 1993，Computational Linguistics，这篇论文就是为批评 MI 而写的。）
3.4 实跑：用 numpy 抽一遍搭配
# 仍然用 24 篇中文笔记；汉语没有空格，所以做「字对搭配」，公式和英文的词对完全一样
import glob, re
from collections import Counter
import numpy as np
FILES = sorted(glob.glob('/Users/mamingyu/Desktop/大一/专业课/教材/*.md'))
text = "".join(open(f, encoding='utf-8').read() for f in FILES)
chunks = [s for s in re.split(r'[^一-鿿]+', text) if len(s) > 1]
bigrams = [s[i:i+2] for s in chunks for i in range(len(s) - 1)]
print("语料：%d 个字对 token，%d 个不同的字对 type" % (len(bigrams), len(set(bigrams))))
# ---------- 1. 数出 2x2 列联表的四个格子 ----------
pair = Counter(bigrams) # O11
left = Counter(b[0] for b in bigrams) # 左元素的边缘频次
right = Counter(b[1] for b in bigrams) # 右元素的边缘频次
N = len(bigrams)
w1 = np.array([p[0] for p in pair]); w2 = np.array([p[1] for p in pair])
O11 = np.array([pair[p] for p in pair], dtype=float)
R1 = np.array([left[a] for a in w1], dtype=float)
C2 = np.array([right[b] for b in w2], dtype=float)
E11 = R1 * C2 / N # 独立假设下的期望频次
# ---------- 2. 三种度量 ----------
MI = np.log2(O11 / E11)
T = (O11 - E11) / np.sqrt(O11)
O12, O21 = R1 - O11, C2 - O11
O22 = N - R1 - C2 + O11
E12, E21 = R1 * (N - C2) / N, (N - R1) * C2 / N
E22 = (N - R1) * (N - C2) / N
def cell(o, e): # O=0 时该项按 0 计（0*ln0 的约定）
out = np.zeros_like(o)
m = o > 0
out[m] = o[m] * np.log(o[m] / e[m])
return out
LLR = 2 * (cell(O11, E11) + cell(O12, E12) + cell(O21, E21) + cell(O22, E22))
def show(name, score, k=14):
idx = np.argsort(-score)[:k]
print("\n【按 %s 排前 %d 名】" % (name, k))
print(" 字对 O11 R1 C2 E11 数值")
for i in idx:
print(" %s %5d %5d %5d %7.1f %8.3f"
% (w1[i] + w2[i], O11[i], R1[i], C2[i], E11[i], score[i]))
show("互信息 MI", MI)
show("t 值 t-score", T)
show("对数似然比 LLR", LLR)
# ---------- 3. 三种度量各自偏爱什么样的字对 ----------
print("\n【诊断】三种度量各自的前 100 名，都是些什么样的对子")
print(" 度量 前100名的平均 O11 其中 O11<=3 的有几个 排第一的 O11")
for name, sc in [("MI", MI), ("t-score", T), ("LLR", LLR)]:
idx = np.argsort(-sc)[:100]
print(" %-9s %15.1f %19d %15d"
% (name, O11[idx].mean(), int((O11[idx] <= 3).sum()), int(O11[idx[0]])))
# ---------- 4. 几个具体字对的三项数值对照 ----------
print("\n【对照实验】")
print(" 字对 O11 E11 MI t-score LLR")
for p in ['什么', '语言', '认知', '的的', '学语', '神经']:
i = list(pair).index(p)
print(" %s %5d %7.1f %7.3f %10.3f %8.1f"
% (p, O11[i], E11[i], MI[i], T[i], LLR[i]))
# ---------- 5. 手算核对 ----------
def xlogx(o, e):
return 0.0 if o == 0 else o * np.log(o / e)
print("\n【手算核对】取“什么”这一对，把 2x2 列联表摆出来")
p = '什么'; i = list(pair).index(p)
o11, r1, c2 = O11[i], R1[i], C2[i]
o12, o21, o22 = r1 - o11, c2 - o11, N - r1 - c2 + o11
e11, e12 = r1 * c2 / N, r1 * (N - c2) / N
e21, e22 = (N - r1) * c2 / N, (N - r1) * (N - c2) / N
print(" w2=%s w2=其他" % p[1])
print(" w1=%s %8.0f %8.0f R1 = %.0f" % (p[0], o11, o12, r1))
print(" w1=其他 %8.0f %8.0f" % (o21, o22))
print(" C2=%.0f N = %d" % (c2, N))
print(" 期望频次 E11 = R1*C2/N = %.0f*%.0f/%d = %.2f" % (r1, c2, N, e11))
print(" MI = log2(O11/E11) = log2(%.0f/%.2f) = %.4f" % (o11, e11, np.log2(o11 / e11)))
print(" t = (O11-E11)/sqrt(O11) = (%.0f-%.2f)/sqrt(%.0f) = %.4f"
% (o11, e11, o11, (o11 - e11) / np.sqrt(o11)))
terms = [xlogx(o11, e11), xlogx(o12, e12), xlogx(o21, e21), xlogx(o22, e22)]
print(" LLR = 2*[%.1f + %.1f + %.1f + %.1f] = %.1f"
% (terms[0], terms[1], terms[2], terms[3], 2 * sum(terms)))
print(" 注意第 2 项：格子值是 %.0f，期望是 %.1f，0*ln0 约定取 0" % (o12, e12))
实跑输出
语料：234761 个字对 token，43704 个不同的字对 type
【按 互信息 MI 排前 14 名】
字对 O11 R1 C2 E11 数值
咔嚓 1 1 1 0.0 17.841
盈眶 1 1 1 0.0 17.841
酝酿 1 1 1 0.0 17.841
氨酸 1 1 1 0.0 17.841
捕捉 1 1 1 0.0 17.841
罪魁 1 1 1 0.0 17.841
岳麓 1 1 1 0.0 17.841
丛林 1 1 1 0.0 17.841
谷氨 1 1 1 0.0 17.841
髓鞘 1 1 1 0.0 17.841
泪盈 1 1 1 0.0 17.841
葬礼 1 1 1 0.0 17.841
蚂蚁 1 1 1 0.0 17.841
枯燥 1 1 1 0.0 17.841
【按 t 值 t-score 排前 14 名】
字对 O11 R1 C2 E11 数值
什么 1824 1824 2689 20.9 42.219
一个 1781 5613 4716 112.8 39.530
这个 1222 5030 4716 101.0 32.067
不是 1140 4368 6698 124.6 30.073
语言 841 1774 878 6.6 28.771
问题 710 978 1190 5.0 26.460
教育 705 1407 731 4.4 26.387
就是 789 1765 6698 50.4 26.296
怎么 671 703 2689 8.1 25.593
为什 613 1384 1711 10.1 24.351
实验 558 1441 945 5.8 23.376
因为 554 745 1216 3.9 23.373
认知 528 686 956 2.8 22.857
门课 515 642 838 2.3 22.593
【按 对数似然比 LLR 排前 14 名】
字对 O11 R1 C2 E11 数值
什么 1824 1824 2689 20.9 17976.000
语言 841 1774 878 6.6 8390.583
一个 1781 5613 4716 112.8 7767.263
教育 705 1407 731 4.4 7422.431
问题 710 978 1190 5.0 6902.887
研究 484 488 485 1.0 6892.579
怎么 671 703 2689 8.1 5919.727
门课 515 642 838 2.3 5579.094
认知 528 686 956 2.8 5438.825
笔记 471 482 1008 2.1 5294.337
因为 554 745 1216 3.9 5285.956
自己 409 784 409 1.4 4928.341
实验 558 1441 945 5.8 4657.781
这个 1222 5030 4716 101.0 4430.035
【诊断】三种度量各自的前 100 名，都是些什么样的对子
度量 前100名的平均 O11 其中 O11<=3 的有几个 排第一的 O11
MI 1.6 94 1
t-score 362.7 0 1824
LLR 339.3 0 1824
【对照实验】
字对 O11 E11 MI t-score LLR
什么 1824 20.9 6.448 42.219 17976.0
语言 841 6.6 6.986 28.771 8390.6
认知 528 2.8 7.562 22.857 5438.8
的的 3 366.4 -6.932 -209.803 727.8
学语 12 16.6 -0.466 -1.322 1.4
神经 167 0.4 8.886 12.896 2061.4
【手算核对】取“什么”这一对，把 2x2 列联表摆出来
w2=么 w2=其他
w1=什 1824 0 R1 = 1824
w1=其他 865 232072
C2=2689 N = 234761
期望频次 E11 = R1*C2/N = 1824*2689/234761 = 20.89
MI = log2(O11/E11) = log2(1824/20.89) = 6.4480
t = (O11-E11)/sqrt(O11) = (1824-20.89)/sqrt(1824) = 42.2191
LLR = 2*[8152.2 + 0.0 + -974.3 + 1810.1] = 17976.0
注意第 2 项：格子值是 0，期望是 1803.1，0*ln0 约定取 0
3.5 这张输出里的三件事
第一：MI 的前 14 名全部并列，而且分数一模一样（17.841）。
这不是巧合。$\mathrm{MI} = \log_2(O_{11}/E_{11})$，当两个字的全语料频次都是 1、
又恰好挨在一起时（$O_{11} = R_1 = C_2 = 1$），有 $E_{11} = 1 \times 1 / N = 1/N$，于是
$$\mathrm{MI} = \log_2 \frac{1}{1/N} = \log_2 N = \log_2 234761 = 17.841$$
MI 在这里取到了它的上限，完全没有能力区分"髓鞘"（真词）和"泪盈"（跨词边界的偶然相邻）。
更糟的是，它连"这两个字是不是真的倾向一起出现"都判断不了，因为 $O_{11} = 1$，
你只有一次观测。诊断表里的数字很直白：MI 的前 100 名，平均 $O_{11}$ 只有 1.6，
其中 94 个的 $O_{11} \le 3$。MI 在用零证据给出满分。
第二：t-score 和 LLR 的前 100 名里，一个 $O_{11} \le 3$ 的都没有。
它们的平均 $O_{11}$ 分别是 362.7 和 339.3。这两个度量自带"样本量门槛"，
原因不在于它们设计了什么特殊规则，而在于公式里就有 $O_{11}$ 这个因子。
这一点在下一段会变成一条可以推导的恒等式。
第三：对照表里的"的的"是一个很好的反面教材。
"的的"共现 3 次，期望 366.4 次，$\mathrm{MI} = -6.93$（强烈负相关，因为两个"的"
几乎不可能相邻），t 值 $-209.8$（极大的负值），LLR 却是 727.8（正值）。
- 负的 MI 和负的 t 值说的是同一件事：这对字比随机更少共现；
- 正的 LLR 说的是另一件事：这种"比随机少"本身也超出了随机波动的范围。
LLR 检验的是"独立 vs 不独立"这个二选一，不区分正相关还是负相关，所以它永远是正的。
用 LLR 时这一点很关键：LLR 高只说明"有关系"，不说明"关系是正向的"。
工业上做搭配抽取时通常的做法是 LLR 排序 + MI/t 值过滤方向，两个一起看。
3.6 两个可以自己推的恒等式（本节的数学核心）
上面那些现象背后有两条精确的代数恒等式。把 MI 的定义代进 t 的公式：
$$t = \frac{O_{11} - E_{11}}{\sqrt{O_{11}}} = \sqrt{O_{11}}\left(\frac{O_{11}}{E_{11}} - 1\right)\cdot\frac{E_{11}}{O_{11}} = \sqrt{O_{11}}\left(1 - \frac{E_{11}}{O_{11}}\right) = \sqrt{O_{11}}\left(1 - 2^{-\mathrm{MI}}\right)$$
（最后一步用了 $E_{11}/O_{11} = 2^{-\mathrm{MI}}$，这是 MI 定义的直接改写。）
读法：$t = \underbrace{\sqrt{O_{11}}}{\text{证据量}} \times
\underbrace{(1 - 2^{-\mathrm{MI}})}{\text{强度，取值在 } 0\sim1 \text{ 之间}}$。
MI 单独用会被低频骗，是因为它只含"强度"不含"证据量"；t-score 把两者乘起来了，
所以 $O_{11} = 1$ 的对子必须靠极大的 MI 才能把 t 值顶上去（$1 - 2^{-17.84} \approx 0.99999$，
但前面只乘了 $\sqrt{1} = 1$）。
第二条是 LLR 与 MI 的关系。LLR 的四项里，第一项是
$$2\,O_{11}\ln\frac{O_{11}}{E_{11}} = 2\,O_{11}\cdot \mathrm{MI}\cdot \ln 2$$
读法：LLR 的核心就是"强度 × 证据量 × 常数"。剩下三项是其余三个格子的修正。
numpy 实算核对（对全部 43704 个字对逐一验证）：
# 接着上面的变量（O11/E11/MI/T/LLR/w1/w2/keys 都还在）
import numpy as np
print("恒等式 1： t-score = sqrt(O11) * (1 - 2^(-MI))")
lhs, rhs = T, np.sqrt(O11) * (1 - 2.0 ** (-MI))
print(" 在全部 %d 个字对上核对，最大绝对误差 = %.3e" % (len(w1), np.abs(lhs - rhs).max()))
print("\n恒等式 2： LLR 的第一项 = 2 * O11 * MI * ln2")
first = 2 * O11 * MI * np.log(2)
print(" 字对 O11 MI LLR第一项 LLR完整值 第一项占比")
for k in ['什么', '语言', '认知', '因为']:
i = list(pair).index(k)
print(" %s %5.0f %6.3f %11.1f %11.1f %7.1f%%"
% (k, O11[i], MI[i], first[i], LLR[i], 100 * first[i] / LLR[i]))
print(" （其余三个格子的修正项可正可负，所以占比在 100% 上下浮动）")
print("\n 最干净的情形：整份语料里只出现一次的字对（O11=1，另两格都是 0）")
for k in ['髓鞘', '酝酿', '咔嚓']:
i = list(pair).index(k)
print(" %s: O11=%d, MI=%.4f, LLR第一项=%.3f, LLR完整值=%.3f，差值恰好 %.3f"
% (k, O11[i], MI[i], first[i], LLR[i], LLR[i] - first[i]))
实跑输出
恒等式 1： t-score = sqrt(O11) * (1 - 2^(-MI))
在全部 43704 个字对上核对，最大绝对误差 = 2.842e-14
恒等式 2： LLR 的第一项 = 2 * O11 * MI * ln2
字对 O11 MI LLR第一项 LLR完整值 第一项占比
什么 1824 6.448 16304.4 17976.0 90.7%
语言 841 6.986 8144.7 8390.6 97.1%
认知 528 7.562 5535.3 5438.8 101.8%
因为 554 7.166 5503.2 5286.0 104.1%
（其余三个格子的修正项可正可负，所以占比在 100% 上下浮动）
最干净的情形：整份语料里只出现一次的字对（O11=1，另两格都是 0）
髓鞘: O11=1, MI=17.8408, LLR第一项=24.733, LLR完整值=26.733，差值恰好 2.000
酝酿: O11=1, MI=17.8408, LLR第一项=24.733, LLR完整值=26.733，差值恰好 2.000
咔嚓: O11=1, MI=17.8408, LLR第一项=24.733, LLR完整值=26.733，差值恰好 2.000
最大误差 $2.8\times10^{-14}$，这是浮点数的机器精度，说明恒等式是对的。
那个"差值恰好 2.000"也值得算一遍：当 $O_{11}=1$ 且 $O_{12}=O_{21}=0$ 时，
第四格 $O_{22} = N-1$，$E_{22} = (N-1)^2/N$，所以第四项贡献
$2(N-1)\ln\frac{N-1}{(N-1)^2/N} = 2(N-1)\ln\frac{N}{N-1} \approx 2\cdot\frac{N-1}{N} \to 2$。
这就是那个 2.000 的来源。
3.7 边界与批评（搭配度量）
- $O_{11}$ 的大小完全取决于语料规模。同一个搭配在 100 万字的语料里 LLR 会是
这里的两倍以上。LLR 只能在同一个语料内部比较，不能跨语料比大小
（t-score 同样有此问题，MI 相对最稳但又有低频偏差）。这组矛盾没有完美解，
实操中通常固定语料规模、并且只在规模相近的语料之间比较。 - MI 的低频偏差是结构性的，不是调参能修的。常见补救是 MI 的幂次修正
（$\mathrm{MI}^k$ 一类，不同文献给出的 $k$ 不同），具体出处本页未核实，标"出处待查"。 - 窗口大小与方向被本页忽略了。我们没有区分"左邻"和"右邻"，也没有用 ±5 词窗口。
真正的搭配研究里，"窗口多大""算不算跨标点"是必须先声明的操作化选择，
§1.5 已经演示过，换一个切分方式就能让结论翻符号。 - "搭配"不等于"固定短语"。统计显著性只回答"这两个单位是不是倾向于一起出现"，
不回答"它们是不是一个词"。汉语里"的的"这种负相关对也有高 LLR（§2.5），
而"什么"既是高频搭配也是疑问代词，统计度量和语言学分类是两个层面。
4 依存距离最小化 ⭐（本页最重要的一节）
4.1 一句话说清依存语法
它想解决什么：成分句法（§5 的 CFG）把句子切成一层层嵌套的短语，
像"盒子装盒子"。依存语法换了一个视角：不切盒子，而是指出词与词之间谁管谁。
每个句子有一个根（root）（通常是主要动词），其他每个词都依赖于另一个词。
这种"支配-从属"的连线就是依存弧。
依存视角的「语言学 的 学生 读 了 一 本 关于 语法 的 书」
语言学 ←── 学生 ←── 读 ──→ 了
↑ （根） │
的 └──→ 书 ──→ 本 ←── 一
│ └──→ 语法 ←── 关于
└──→ 的
（箭头从支配词指向从属词，标签在本页省略。这就是 CoNLL-U 格式里那十列的原因，
见 §6。）《语言学概论》里讲过的句法树，在依存视角下就是这张"连线图"。
4.2 依存距离：把"难不难懂"变成一个数
核心定义：一条依存弧连接位置 $i$ 的支配词和位置 $j$ 的从属词，它的
依存距离（dependency distance, DD）是
$$\mathrm{DD} = \lvert i - j \rvert$$
逐项解释：$i$ 和 $j$ 是词在句子里的线性位置（第几个词），
不是树上的层级深度。取绝对值是因为两个方向的远距离都同样费解。
一句话的平均依存距离（MDD）就是所有依存弧的 DD 取平均。
为什么这个量重要：它有一个非常干净的认知解释。人加工句子时，
支配词和从属词之间需要保持在内存里配对，它们隔得越远，中间要维持的
未完成依赖就越多。Gibson 1998 年在 Cognition 上提出的"依存局部性理论"
就是围绕这一点展开的。所以：
MDD 是"工作记忆负荷"在语料上留下的可测量指纹。
而计量语言学最著名的发现是：自然语言的语序不是随机的，它系统性地让 MDD 变短。
这叫依存距离最小化（dependency length minimization, DLM）。
文献线：
- Hudson (1995) 最早把依存距离当作句法难度的度量（未刊手稿，通行引用为
Measuring syntactic difficulty，正式出处待查）；
- Liu (2008)，Journal of Cognitive Science 9(2): 159–191，用 20 种语言的依存树库
系统测量，提出"MDD 倾向于被最小化、且多数语言不超过 3 个词"的假设；
- Temperley (2007)，Cognition 105(2): 300–333，在英语上做了同样的论证；
- Futrell, Mahowald & Gibson (2015)，PNAS 112(33): 10336–10341，
在 37 种语言、10 个语系上给出大规模证据。
4.3 为什么必须做基线（本节的方法论核心）
最容易犯的错：算出一个语言的 MDD 是 2.5，就说"这很小，所以语言在最小化距离"。
这个推理是无效的，因为 2.5 这个数字本身没有可比的参照：
- 句子越长，词越多，MDD 自然越大；
- 树的结构不同（比如全是短弧的链状树 vs 一根长弧的星形树），MDD 也自然不同；
- 甚至语序完全随机的语言，MDD 也不会是无穷大，它会是某个有限值。
所以正确的做法是：固定住一切不该变的因素，只让"语序"这一个变量变，
然后比较"真实语序"和"反事实语序"。这就是 Futrell et al. (2015) 的
自由语序基线（Free Word Order Baseline）：
保持每句话的依存树结构完全不变（哪些词管哪些词、谁是根，一字不改），
只随机打乱这些词在线性顺序上的排列，生成 100 个（本页做 2000 个）随机语序，
算它们的 MDD，取平均。这个平均值就是"如果这门语言的语序是随机的，
MDD 该有多大"。
再进一步，还有一个最优语序基线：
在所有可能的语序里，找出让 MDD 最小的那一个，看真实语序离这个理论下界有多远。
两个基线回答两个不同的问题：
"语言比随机好多少"（随机基线）和
"语言离理论最优还差多少"（最优基线）。
Futrell et al. 发现真实语序总是比随机基线短、但总是比最优基线长。
后一半同样重要：说明说话人并没有把距离压到底，一定还有别的力量在起作用
（比如"重要信息放前面"、或者"保持固定的词序类型"）。
4.4 实跑：12 句手工标注的汉语小句库
语料：本页手工标注的 12 个汉语句子，共 96 个词。标注约定：
heads[i] = 第 i 个词的支配词的下标，-1 表示它是整句的根。
（这就是 CoNLL-U 里 HEAD 那一列。）
import itertools, random
import numpy as np
# 句子；heads[i] = 第 i 个词的支配词下标，-1 表示它是整句的根
SENTS = [
("我 喜欢 语言学", [1, -1, 1]),
("他 昨天 看 了 电影", [2, 2, -1, 2, 2]),
("我 的 姐姐 在 学校 读 语言学", [2, 2, 5, 4, 5, -1, 5]),
("这 本 书 的 作者 是 一 位 语言学 家", [2, 2, 4, 2, 5, -1, 7, 9, 9, 5]),
("因为 下雨 他 没 去 学校", [1, 4, 4, 4, -1, 4]),
("他 把 书 放 在 桌子 上", [3, 2, 3, -1, 5, 3, 5]),
("那个 学生 认为 这 道 题 很 简单", [1, 2, -1, 4, 5, 7, 7, 2]),
("我 昨天 买 的 那 本 书 特别 好", [2, 2, 6, 2, 5, 6, 8, 8, -1]),
("虽然 天气 不 好 我们 还是 去 了 公园", [3, 3, 3, 6, 6, 6, -1, 6, 6]),
("老师 让 学生 读 一 篇 很 长 的 文章", [1, -1, 1, 1, 5, 9, 7, 9, 7, 3]),
("他 写 的 那 篇 关于 语言 的 论文 很 好", [1, 8, 1, 4, 8, 6, 8, 6, 10, 10, -1]),
("语言学 的 学生 读 了 一 本 关于 语法 的 书", [2, 0, 3, -1, 3, 6, 10, 8, 10, 8, 3]),
]
def arcs(heads):
return [(i, h) for i, h in enumerate(heads) if h >= 0]
def mdd(order, heads):
"""order = (位置 -> 词下标) 的一个排列；返回该语序下的平均依存距离"""
pos = {w: p for p, w in enumerate(order)}
a = arcs(heads)
return sum(abs(pos[i] - pos[h]) for i, h in a) / len(a)
def min_mdd(heads, restarts=400):
"""最优语序基线：n<=8 穷举全部排列；n>8 用随机重启 + 两两交换的局部搜索"""
n = len(heads)
if n <= 8:
return min(mdd(p, heads) for p in itertools.permutations(range(n)))
best = 1e9
for _ in range(restarts):
o = list(range(n)); random.shuffle(o)
cur = mdd(o, heads); improved = True
while improved:
improved = False
for i in range(n):
for j in range(i + 1, n):
o[i], o[j] = o[j], o[i]
v = mdd(o, heads)
if v < cur - 1e-12:
cur, improved = v, True
else:
o[i], o[j] = o[j], o[i]
best = min(best, cur)
return best
print("【手工标注的依存句法小库】共 %d 句，%d 个词"
% (len(SENTS), sum(len(h) for _, h in SENTS)))
print(" 约定：heads[i] = 第 i 个词的支配词下标，-1 = 根；依存距离 = |支配词位置 - 从属词位置|")
random.seed(7); np.random.seed(7)
rows = []
for sent, heads in SENTS:
ws = sent.split()
assert len(ws) == len(heads), sent
n = len(heads)
obs = mdd(range(n), heads) # 真实语序
rs = np.array([mdd(np.random.permutation(n), heads) for _ in range(2000)]) # 随机语序基线
opt = min_mdd(heads) # 最优语序基线
rows.append((n, obs, rs.mean(), rs.std(), opt))
print("\n【逐句结果】距离单位 = 词")
print(" 词数 实测MDD 随机语序MDD(均值±SD) 比随机短 最优MDD 离最优还差")
for n, obs, rm, rsd, opt in rows:
print(" %3d %7.3f %8.3f ± %.3f %6.1f%% %6.3f %5.1f%%"
% (n, obs, rm, rsd, 100*(rm-obs)/rm, opt, 100*(obs-opt)/(rm-opt)))
O = np.array([r[1] for r in rows]); R = np.array([r[2] for r in rows])
OP = np.array([r[4] for r in rows]); L = np.array([r[0] for r in rows])
print("\n【汇总】全部句子合在一起")
print(" 实测 MDD 总平均 = %.3f 词" % O.mean())
print(" 随机语序 MDD 总平均 = %.3f 词" % R.mean())
print(" 理论最优 MDD 总平均 = %.3f 词" % OP.mean())
print(" 实测比随机短 %.1f%%，离最优还差 %.1f%%"
% (100*(R.mean()-O.mean())/R.mean(), 100*(O.mean()-OP.mean())/(R.mean()-OP.mean())))
print("\n【按句长分组】——依存距离最小化的效果随句子变长而变大")
print(" 句长 句数 实测MDD 随机MDD 比随机短")
for lo, hi in [(3, 5), (6, 8), (9, 12)]:
m = (L >= lo) & (L <= hi)
print(" %2d-%2d词 %4d %7.3f %7.3f %5.1f%%"
% (lo, hi, m.sum(), O[m].mean(), R[m].mean(),
100*(R[m].mean()-O[m].mean())/R[m].mean()))
print("\n【单句示形】「语言学 的 学生 读 了 一 本 关于 语法 的 书」")
ws = SENTS[11][0].split(); hd = SENTS[11][1]
print(" 实测语序下每一条依存弧：")
for i, h in arcs(hd):
print(" %-4s <- %-4s 距离 %d" % (ws[i], ws[h], abs(i - h)))
print(" 该句：实测 MDD %.3f，随机语序约 %.3f，最优 %.3f"
% (mdd(range(len(ws)), hd),
np.mean([mdd(np.random.permutation(len(ws)), hd) for _ in range(2000)]),
min_mdd(hd)))
实跑输出
【手工标注的依存句法小库】共 12 句，96 个词
约定：heads[i] = 第 i 个词的支配词下标，-1 = 根；依存距离 = |支配词位置 - 从属词位置|
【逐句结果】距离单位 = 词
词数 实测MDD 随机语序MDD(均值±SD) 比随机短 最优MDD 离最优还差
3 1.000 1.338 ± 0.234 25.2% 1.000 0.0%
5 1.500 1.996 ± 0.416 24.8% 1.500 0.0%
7 1.500 2.670 ± 0.527 43.8% 1.333 12.5%
10 1.667 3.665 ± 0.656 54.5% 1.333 14.3%
6 1.600 2.329 ± 0.478 31.3% 1.400 21.5%
7 1.500 2.640 ± 0.515 43.2% 1.333 12.8%
8 1.714 2.981 ± 0.547 42.5% 1.143 31.1%
9 1.625 3.325 ± 0.622 51.1% 1.500 6.9%
9 1.875 3.320 ± 0.652 43.5% 1.750 8.0%
10 2.111 3.675 ± 0.658 42.5% 1.444 29.9%
11 2.100 3.994 ± 0.700 47.4% 1.600 20.9%
11 2.100 3.954 ± 0.683 46.9% 1.400 27.4%
【汇总】全部句子合在一起
实测 MDD 总平均 = 1.691 词
随机语序 MDD 总平均 = 2.990 词
理论最优 MDD 总平均 = 1.395 词
实测比随机短 43.5%，离最优还差 18.6%
【按句长分组】——依存距离最小化的效果随句子变长而变大
句长 句数 实测MDD 随机MDD 比随机短
3- 5词 2 1.250 1.667 25.0%
6- 8词 4 1.579 2.655 40.5%
9-12词 6 1.913 3.655 47.7%
【单句示形】「语言学 的 学生 读 了 一 本 关于 语法 的 书」
实测语序下每一条依存弧：
语言学 <- 学生 距离 2
的 <- 语言学 距离 1
学生 <- 读 距离 1
了 <- 读 距离 1
一 <- 本 距离 1
本 <- 书 距离 4
关于 <- 语法 距离 1
语法 <- 书 距离 2
的 <- 语法 距离 1
书 <- 读 距离 7
该句：实测 MDD 2.100，随机语序约 4.010，最优 1.400
4.5 这张输出里的四件事
第一：真实语序比随机语序短 43.5%，而且这个优势随句长单调上升
（25.0% → 40.5% → 47.7%）。这正是 Futrell et al. (2015) 在 37 种语言里看到的模式：
短句子里词少、本来就没多少可压缩的空间，效应小；句子越长，
随机语序制造长弧的机会越多，而真实语言系统性地避免长弧，差距就拉开了。
"效应随句长增加"这条模式，比"总体显著"这个结论本身更有说服力，
因为它说明这背后是一个随结构复杂度增强的机制，不是一次统计波动。
第二：真实语序离理论最优还差 18.6%，从来没有达到过最优。
这半句话同样重要。如果语言只是在"最小化距离"，为什么做不到极致？
文献里的标准解释是存在别的竞争性力量：语言还要标记"谁是主语/宾语"、
还要把已知信息放前面、还要保持语序类型的一致性（SVO 语言不许随便把动词挪到句尾）。
DLM 是一个倾向（preference），不是一个硬约束。
第三：单句示形里那条"书 ← 读 距离 7"值得盯住。这是全句最长的一条弧，
而且它恰恰是汉语里最典型的长距离依赖：宾语"书"被一个长长的定语
"一本关于语法的"推到了句子末尾，和动词"读"隔了 7 个词。
把它和随机基线一比就明白了，在随机语序里，这个 7 会被改成别的弧，
但总有某条弧要变长，因为树的形状是固定的。这就是为什么必须先固定树、只打乱语序：
只有这样才能把"树本来就这么长"和"语序让弧变长了"分开。
第四：MDD 的绝对数值很小（1.691），但不要拿它当"汉语的 MDD"。
本页句子只有 3~12 个词，而且是我为了演示挑的短句。真实的汉语依存树库里
MDD 会明显更高。这恰恰是汉语在跨语言比较里的一个特点：汉语倾向于
把修饰成分放在中心语前面（"的"字结构、介词短语都前置），这会产生很多向后的长弧。
Liu (2008) 报告的汉语 MDD 在所比较的语言里属于偏大的一端。
（具体数字请以原文表格为准，本页引的是二手转述，未逐表核对，标为待核。）
4.6 边界与批评（依存距离）
这一节的批评集中在方法论层面，而且很尖锐：
- 随机基线本身可能藏了偏见。Futrell et al. 的"自由语序基线"生成的是投射的
（projective，依存弧不交叉）线性化。Ferrer-i-Cancho 的批评是：
投射性本身可能就是 DLM 的产物，把它写进基线里等于把要证明的结论预先假设了。
一个真正"自由"的基线应该允许全部 $n!$ 种排列（包括弧交叉的那些）。
这场争论在 2015 年前后有多篇往返回应（Liu, Xu & Liang 2015 与
Ferrer-i-Cancho & Gómez-Rodríguez 2015 都对 Futrell et al. 提出过意见，
Futrell 等人有公开回应）。本页的基线同样是投射的（我们的随机排列不约束交叉），
实际上本页反而没有这个问题，我们打乱的是"词的位置"，交叉是允许出现的。
但你读文献时要注意作者用的是哪种基线。 - "DLM 有效应"和"DLM 是语言的设计目标"是两件事。观察到效应，
只能说明真实语序偏离随机。偏离的方向可以由很多机制产生
（比如"主语在前"这条独立规则就会顺带缩短主语的依存距离）。
把相关性读成设计意图，是这一支文献被批评最多的地方。 - 手工标注的小库不是树库。12 句、96 个词，而且标注是我一个人做的，
没有标注一致性检验（真实树库里这部分必须报告，见 §6.4）。
句子也是我挑的，挑句子这个动作本身就可能引入偏差。
真实研究必须用公开树库（如 Universal Dependencies 里的中文树库）。 - "词"的定义影响结果。汉语分词方式不同，MDD 会变。§1.3 已经证明
"选哪个单位"能改变结论的量级。 - MDD 丢掉了很多信息。两个句子的 DD 分布可以完全不同（"一堆 2 + 一条 10"
vs "均匀分布在 3 左右"）却有相同的 MDD。所以看 MDD 时应该同时看 DD 的分布形状，
真实语言里这个分布是右偏的（大部分弧很短，少数弧很长）。
5 语言结构的形式化：从正则语言到乔姆斯基层级
§1-§3 处理的是量（频次、距离）。从这一节开始处理结构：
怎么把"这句话合语法"这件事本身变成数学对象。
5.1 乔姆斯基层级：一张表定坐标
它想解决什么：1950 年代，Chomsky 想把"语法"这件事公理化。
他提出了一件事：语法规则的形式不同，能生成的语言的复杂度就不同，
于是语言可以按"描述它需要多强的规则"来分类。这就形成了乔姆斯基层级。
| 类型 | 名字 | 规则形式 | 识别机器 | 典型例子 |
|---|---|---|---|---|
| 3 型 | 正则语言 | $A \to aB$ 或 $A \to a$ | 有限状态自动机（无栈） | 英语 -ed 形态变化；电话号码 |
| 2 型 | 上下文无关语言 | $A \to \gamma$（$\gamma$ 任意） | 下推自动机（一条栈） | 编程语言的语法；$a^nb^n$ |
| 1 型 | 上下文相关语言 | $\alpha A \beta \to \alpha\gamma\beta$ | 线性有界自动机 | 瑞士德语的交叉依赖（有争议） |
| 0 型 | 无限制 | 任意重写规则 | 图灵机 | 一切可计算的东西 |
逐项解释：
- 规则左边必须是单个非终结符 $A$，这是 3 型和 2 型的共同点；
区别只在右边：3 型的右边必须是"一个终结符 + 最多一个非终结符"，
2 型没有这个限制。 - 3 型的那个限制意味着机器没有任何记忆。$A \to aB$ 说的是
"现在处于状态 $A$，读到一个 $a$，转到状态 $B$"，状态是有限的，
除了当前状态之外什么都不许记。 - 2 型多出来的能力来自"递归"：$A \to aAb$ 这种规则能让机器
一直往下改写，等效于"记在一条栈上"。栈有多深，就能数多少。
这张表的坐标意义：语言学的核心问题之一就是"自然语言在哪一层？"
如果只在 3 型，那整个自然语言的语法可以用有限状态机实现，
语言学就是查表；如果在 2 型或更高，就必须有递归结构。
§4.5 会给出这个问题的严格论证。
出处：Chomsky 1956 年在 IRE Transactions on Information Theory 2(3): 113–124
上发表的 "Three models for the description of language" 是这条线的起点；
层级的完整形式化在 Chomsky 1959，Information and Control 2(2): 137–167。
5.2 正则语言 vs 上下文无关语言：一句话的差别
正则语言：能用一个循环图（有限状态机）识别的字符串集合。
它的本质限制是"有限的记忆"，你的机器只有 $K$ 个状态，
就最多只能区分 $K$ 种不同的情况。
上下文无关语言：能用一套递归规则生成的字符串集合。
它的本质能力是"可以插叙"，写了一半的东西可以先搁着，
处理完里面的部分再回来接着写。
一个例子说明这个差别：
正则能做的： 匹配「任何以 ab 结尾的串」
机器只需要记住「上一个读到的是不是 a」—— 2 个状态
正则做不到的： 匹配「n 个 a 后面跟 n 个 b」（a^n b^n）
要判断配不配平，机器得数数，
而数到多少取决于 n —— 需要无限多个状态
上下文无关能做的： a^n b^n
规则：S -> a S b | a b
生成：S => aSb => aaSbb => aaaSbbb ...
（左半边的 a 数多少，右半边就补多少 b）
5.3 有限状态转换器（FST）：把"规则"变成"机器"
它想解决什么：语言里有一大类规律是"输入-输出"关系，
比如形态变化（cat → cats）、音变（in + possible → impossible）、
拼写规则（英语的 y → ies）。这些规律有共同点：它们是局部的、可以逐段处理的。
有限状态转换器（finite-state transducer, FST）就是正则语言的"两带"版本：
它的每一条转移读一个符号的同时写一个符号：
a:x b:y
( q0 ) ──────────> ( q1 ) ──────────> (( q2 ))
读 a 写 x 读 b 写 y q2 是接受状态
关键能力是"合成"（composition）：两台转换器 $T_1$（拼写规则）
和 $T_2$（音变规则）可以用 $T_1 \circ T_2$ 叠成一台新机器，
结果仍然是一台有限状态转换器。这意味着"给词加上前缀、再改音、
再处理重音"这一整串规则可以编译成一台机器一次跑完，
快、可逆、可证明等价。这就是 FST 在语音识别、拼写检查、
形态分析里被大量使用的原因（Mohri 1997，Computational Linguistics 23(2): 269–311；
这个"把规则编译成转换器"的方法论源头是 Kaplan & Kay 1994，
Computational Linguistics 20(3): 331–378）。
5.4 实跑：把一条音变规则编译成 FST
下面这台机器处理英语否定前缀 in- 的同化：$n$ 在 $p, b, m$ 前变成 $m$，
在 $l$ 前变成 $l$，在 $r$ 前变成 $r$，其余情况保持 $n$。
输入是底层形式（underlying form，语言学里的"字典里记的那个形式"），
输出是表层形式（surface form，实际说的那个形式）。
# 一台 4 状态的转换器。转移是 (输入符号 : 输出符号)，输出可以是空串或一整串
LETTERS = "abcdefghijklmnopqrstuvwxyz"
T = {}
# q0 起步：读到 i 就进入「可能遇到 in- 前缀」的状态；其他字母直接原样穿过
for c in LETTERS:
T[('q0', c)] = (c, 'q_body')
T[('q0', 'i')] = ('i', 'q_i')
# q_i 读到 n：先不输出（先延迟，等看到后文再决定）——这是 FST 处理「看后文」的标准手法
T[('q_i', 'n')] = ('', 'q_n')
# q_n 读到特定字母，才把那个 n 兑现成 m / l / r / 保持 n
for c, o in [('p', 'mp'), ('b', 'mb'), ('m', 'mm'), ('l', 'll'), ('r', 'rr')]:
T[('q_n', c)] = (o, 'q_body')
for c in LETTERS:
T.setdefault(('q_n', c), ('n' + c, 'q_body'))
# q_body：前缀处理完了，后面一律原样输出
for c in LETTERS:
T[('q_body', c)] = (c, 'q_body')
def run(word):
state, out = 'q0', ''
for ch in word:
if (state, ch) not in T:
return None
o, state = T[(state, ch)]
out += o
return out if state == 'q_body' else None
print("规则：底层形式「in-X」里的 n，在 p/b/m/l/r 前发生同化（n->m/l/r），否则保持 n")
print("这台机器一共有 %d 个状态\n" % 4)
print(" 底层形式（输入） 表层形式（机器输出） 实际英语")
REAL = {"inpossible": "impossible", "inlegal": "illegal", "inregular": "irregular",
"intolerant": "intolerant", "incorrect": "incorrect", "inmobile": "immobile",
"inbalance": "imbalance", "inmature": "immature", "inrelevant": "irrelevant",
"inlegible": "illegible", "inmodest": "immodest", "inrational": "irrational",
"innoble": "ignoble"}
for w in ["inpossible", "inlegal", "inregular", "intolerant", "incorrect", "inmobile",
"inbalance", "inmature", "inrelevant", "inlegible", "inmodest", "inrational",
"innoble"]:
got = run(w)
flag = " <- 对不上" if got != REAL[w] else ""
print(" %-14s -> %-24s %s%s" % (w, got, REAL[w], flag))
实跑输出
规则：底层形式「in-X」里的 n，在 p/b/m/l/r 前发生同化（n->m/l/r），否则保持 n
这台机器一共有 4 个状态
底层形式（输入） 表层形式（机器输出） 实际英语
inpossible -> impossible impossible
inlegal -> illegal illegal
inregular -> irregular irregular
intolerant -> intolerant intolerant
incorrect -> incorrect incorrect
inmobile -> immobile immobile
inbalance -> imbalance imbalance
inmature -> immature immature
inrelevant -> irrelevant irrelevant
inlegible -> illegible illegible
inmodest -> immodest immodest
inrational -> irrational irrational
innoble -> innoble ignoble <- 对不上
13 个里对了 12 个，错的这个恰恰是最有价值的一个。
ignoble 来自拉丁语 in- + nobilis，走的是另一条历史路径（同化成了 $g$）。
这台机器没错，是"规则"这个模型没错，是"英语只有一条规则"这个假设错了。
这就是 §4.6 要讲的那件事：纯规则系统会被例外吞掉，这是 NLP 从规则转向统计的直接原因。
另外注意那个 T[('q_i', 'n')] = ('', 'q_n')：输出空串。
这是因为"$n$ 变成什么"取决于后面一个字母，而有限状态的机器不能回头改已经写出去的东西，
所以标准手法是先延迟输出，等环境明确了再兑现。
这个"延迟"技巧是 FST 处理所有"看后文"规则的核心，也是它仍然属于正则范畴的原因：
它只是把决定推迟了几步，状态数并没有爆炸（这台机器只有 4 个状态）。
5.5 为什么自然语言不是正则语言（严格反证）
目标：证明自然语言（在标准的理想化下）不可能是正则语言。
要求是严格，不能只说"一般认为"。
第 1 步：先把"不是正则"这件事变成一个可以证明的数学命题。
$$\text{定理（泵引理）}：设 L 是正则语言，则存在常数 p \ge 1，使得
\forall w \in L，若 \lvert w\rvert \ge p，则 w 可以写成 w = xyz，满足$$
$$(i)\ \lvert xy\rvert \le p; \qquad (ii)\ \lvert y\rvert \ge 1; \qquad
(iii)\ \forall k \ge 0,\ xy^kz \in L$$
逐项解释（这是整个证明的关键，每一句都要读懂）：
- $p$ 是什么：$L$ 若是正则的，就有一台 $p$ 个状态的自动机识别它。
取 $p$ 等于状态数。 - $(i)$ 为什么能要求 $\lvert xy\rvert \le p$：一个长度 $\ge p$ 的串被机器读的时候，
读前 $p$ 个字符就已经走了 $p+1$ 个"状态+字符"的位置，
由鸽笼原理必然重复经过了某个状态。$y$ 就是那个重复走的环。 - $(ii)$：环当然至少要走一步。
- $(iii)$ 是结论：那个环可以走 0 次、1 次、2 次、任意次，
机器分不出来（因为走完环回到同一个状态），所以 $xy^kz$ 全都必须被接受。 - 直觉版：一个只有有限状态的机器，识别一个长串时必然"绕圈"，
而绕圈就意味着它丧失了对"绕了几次"的计数能力。
第 2 步：证明 $L = \{a^nb^n : n \ge 1\}$ 不是正则语言。
反证。设 $L$ 正则，泵引理给常数 $p$。取 $w = a^pb^p \in L$（长度 $2p \ge p$）。
按引理，$w = xyz$ 且 $\lvert xy\rvert \le p$。因为 $xy$ 只覆盖 $w$ 的前 $p$ 个字符，
而前 $p$ 个字符全是 $a$，所以 $y$ 只能是若干个 $a$，设 $\lvert y\rvert = m \ge 1$。
现在取 $k = 2$，得到 $xy^2z = a^{p+m}b^p$。但 $p + m \ne p$，
所以 $a^{p+m}b^p \notin L$，与引理的 $(iii)$ 矛盾。故 $L$ 不是正则语言。$\blacksquare$
第 3 步：把自然语言"翻译"进这个定理。
英语（以及汉语）允许关系从句的中心嵌套。看这一族句子：
深度 0： the cat slept
深度 1： the cat [that the cat slept] slept
深度 2： the cat [that the cat [that the cat slept] slept] slept
...
深度 n： (the cat)^(n+1) (slept)^(n+1)
每一层嵌套都恰好往中间插入一组"the cat ... slept"，
所以深度 $n$ 的句子的词序列正好是 $(the\ cat)^{n+1}(slept)^{n+1}$。
（这不是巧合，是中心嵌套的定义带来的：新的从句必须插在主句主语和谓语之间。）
现在构造归约：
- 设 $E$ 是所有合语法英语句子的集合。反设 $E$ 是正则的。
- 令 $R = L\big((\texttt{the cat})^+(\texttt{slept})^+\big)$。
$R$ 是正则语言（它是两个正则语言的连接）。 - 正则语言对交运算封闭，所以 $E \cap R$ 是正则的。
- 定义同态 $h$：$h(\texttt{cat}) = a$，$h(\texttt{slept}) = b$，$h(\texttt{the}) = \varepsilon$。
同态保持正则性，所以 $h(E \cap R)$ 是正则的。 - 由第 3 步的构造，$\{(the\ cat)^n(slept)^n\} \subseteq E \cap R$，
也就是说 $\{a^nb^n : n \ge 1\} \subseteq h(E \cap R)$。
而反过来，$m \ne n$ 的串 $(the\ cat)^m(slept)^n$ 不合语法，
所以 $h(E \cap R) = \{a^nb^n : n \ge 1\}$。 - 但第 2 步已经证明 $\{a^nb^n\}$ 不是正则语言。矛盾。
所以 $E$ 不是正则语言。$\blacksquare$
这个证明里必须点明一件事：哪些部分是纯数学，哪些部分是经验前提。
- 纯数学：第 1、2 步和"正则语言对交封闭""同态保持正则"都是定理，
一个字都不用怀疑。 - 经验前提（两条，都必须单独声明）：
- (P1) 任意深度的中心嵌套在英语里都是合语法的（即 $\{(the\ cat)^n(slept)^n\}$ 全在 $E$ 里）；
- (P2) 词数配不平的串（$(the\ cat)^m(slept)^n$，$m \ne n$）不合语法。
- 结论：只要 (P1) 和 (P2) 成立，英语就不是正则语言。
它是一个条件命题，不能只当"一般认为"。
如果你不接受 (P1)（下面 §4.6 会看到有人真的不接受），
那么整个论证的攻击点就在 (P1)，而不在数学部分。
第 4 步：把泵引理跑出来看。
泵引理是纯数学，但它可以变成一个看得见的现象：
"$K$ 个状态的机器最多只能数到 $K$"。
# 把泵引理跑出来：有限状态自动机数不了数，下推自动机能
def dfa_anbn(s, K):
"""一个有 K+2 个状态的 DFA：状态 i 表示「已经数到 i 个 a」，K+1 是死状态。
K 就是这台机器的记忆容量——它只有这么多状态可以区分。"""
q = 0
for ch in s:
if q == K + 1: # 进死状态，再也出不来
return False
if ch == 'a':
q = q + 1 if q < K else K + 1
else:
q = q - 1 if q > 0 else K + 1
return q == 0 # 只有正好配平才接受
def pda_anbn(s):
"""下推自动机：一条无限长的栈，数多少都行"""
stack = []
for ch in s:
if ch == 'a':
stack.append('a')
else:
if not stack:
return False
stack.pop()
return not stack
print("目标语言 L = { a^n b^n : n >= 1 }（n 个 a 后面跟 n 个 b）")
print("这正是「中心嵌套」的抽象形式：嵌套多少层，就要数到多少。\n")
print("【有限状态自动机】不同状态数下，能正确接受的 n 的范围")
for K in (1, 2, 5, 20):
ok = [n for n in range(1, 500) if dfa_anbn('a' * n + 'b' * n, K)]
bad = [n for n in range(1, 500) if not dfa_anbn('a' * n + 'b' * n, K)]
print(" K = %2d 个状态：接受 n <= %s，从 n = %d 起全部拒绝"
% (K, ok[-1] if ok else "无", bad[0] if bad else 999))
print(" -> 状态数 K 加多少都只能往前推一格，永远存在把它打败的 n。")
print(" 所以「对所有 n 都接受」需要无穷多个状态：不存在这样的 DFA。")
print("\n对照：换成下推自动机（带一条栈）")
for n in (1, 5, 50, 300):
print(" n = %3d : %s" % (n, pda_anbn('a' * n + 'b' * n)))
print(" -> 一条无限长的栈就够了。这就是正则语言 ⊊ 上下文无关语言的分界。")
print("\n【负例检查】确认 DFA 的失败不是因为实现写错，而是数不过来")
for s in ['aabb', 'aaabbb', 'aabbb', 'abab', 'aaab']:
print(" %-8s K=2 -> %-5s K=100 -> %-5s PDA -> %s"
% (s, dfa_anbn(s, 2), dfa_anbn(s, 100), pda_anbn(s)))
实跑输出
目标语言 L = { a^n b^n : n >= 1 }（n 个 a 后面跟 n 个 b）
这正是「中心嵌套」的抽象形式：嵌套多少层，就要数到多少。
【有限状态自动机】不同状态数下，能正确接受的 n 的范围
K = 1 个状态：接受 n <= 1，从 n = 2 起全部拒绝
K = 2 个状态：接受 n <= 2，从 n = 3 起全部拒绝
K = 5 个状态：接受 n <= 5，从 n = 6 起全部拒绝
K = 20 个状态：接受 n <= 20，从 n = 21 起全部拒绝
-> 状态数 K 加多少都只能往前推一格，永远存在把它打败的 n。
所以「对所有 n 都接受」需要无穷多个状态：不存在这样的 DFA。
对照：换成下推自动机（带一条栈）
n = 1 : True
n = 5 : True
n = 50 : True
n = 300 : True
-> 一条无限长的栈就够了。这就是正则语言 ⊊ 上下文无关语言的分界。
【负例检查】确认 DFA 的失败不是因为实现写错，而是数不过来
aabb K=2 -> True K=100 -> True PDA -> True
aaabbb K=2 -> False K=100 -> True PDA -> True
aabbb K=2 -> False K=100 -> False PDA -> False
abab K=2 -> True K=100 -> True PDA -> True
aaab K=2 -> False K=100 -> False PDA -> False
这张输出就是泵引理的可执行版本："$K$ 个状态接受 $n \le K$，$n = K+1$ 起全部拒绝"，
那个 $K+1$ 就是鸽笼原理说的"必然重复状态"的位置。
而且注意负例检查那几行：DFA 的失败不是 bug，它接受 aabb、abab
（这两个都在 $L$ 或恰好配平），拒绝 aabbb、aaab（确实不合 $L$），
它只是在 $n > K$ 时无能为力。"在有限范围内正确、在无限范围上失效"，
正是泵引理说的那件事。
5.6 边界与批评（非正则性论证）
上面那个证明在数学上是完整的，但它的两条经验前提都受到了严重挑战。
- 挑战一（最致命）：语言是有限的。
任何一个真实语料库都是有限的字符串集合，有限集合一定是正则语言。
所以严格来说，没有一种"实际存在的语言"不是正则的。
整个论证的前提是把语言理想化成"所有合语法句子的无穷集合"（这是 Chomsky
的"语言能力/语言表现"区分的核心，也是 Miller & Chomsky 1963 那篇
Finitary models of language users 讨论的起点）。
你必须接受这个理想化，论证才能启动。这是语言学里最根本的一个方法论选择，
不是技术细节。 - 挑战二：真实语言里的中心嵌套有硬上限。
Karlsson 2007 年在 Journal of Linguistics 43(2): 365–392 上，
从七种欧洲语言的真实语料里只找到 13 个三重中心嵌套和 104 个二重中心嵌套，
书面语的最大深度是 3，口语几乎完全不超过 2。
也就是说 (P1)（"任意深度都合语法"）在实际使用中是假的。
有意思的是 Karlsson 自己指出："多层中心嵌套有没有上限"这个问题，
恰好就是判断自然语言句法是 2 型还是 3 型的唯一关键，
有上限就是 3 型（正则），没上限就是 2 型。
他的语料支持"有上限"，但那只是使用上的限制，不是语法上的禁止。
（一个不会说深层嵌套的人，和一个语法禁止深层嵌套的语言，是两回事。） - 挑战三：往上走，2 型也不够。
如果自然语言不是正则的，那它是上下文无关的吗？
Pullum & Gazdar 1982（Linguistics and Philosophy 4(4): 471–504）
系统地检查了此前所有"证明自然语言不是上下文无关"的论证，
结论是它们的证明全都有问题（形式上或经验上），并明确说
"自然语言是不是上下文无关的仍是一个开放问题"。
三年后 Shieber 1985（Linguistics and Philosophy 8(3): 333–343）
用瑞士德语的交叉依赖（cross-serial dependencies）
给出了一个被广泛接受的不是上下文无关的论证。
Shieber 自己也很克制地指出：这不说明自然语言难以解析
（那些结构是可以用线性时间解析的），也不说明必须用到
上下文相关文法或更强的装置。这场"语言在哪一层"的争论至今没有定论。 - 工程上的教训：不管语言学结论如何，工业界的句法分析器一律用 CFG 或更弱的模型
（PCFG、依存文法、甚至有限状态的序列标注）。原因很实际：
复杂度可控、有高效算法、够用。"语言需要多强的形式装置"和"解析器该用什么模型"
是两个不同的问题，前者是科学问题，后者是工程问题。
6 句法计算：CFG 与 CYK 算法
从这一节开始我们站在机器那边：给定一套文法、一个句子，
怎么算出一个句子的所有结构？
6.1 CFG 的形式定义
上下文无关文法（context-free grammar, CFG）是一个四元组 $G = (N, \Sigma, R, S)$：
- $N$：非终结符集合（可以继续改写的符号，比如"名词短语 NP"、"动词短语 VP"）；
- $\Sigma$：终结符集合（不能再改写的符号，就是词表本身）；
- $R$：规则集合，每条规则形如 $A \to \gamma$，其中 $A \in N$，
$\gamma$ 是 $(N \cup \Sigma)^*$ 里的符号串； - $S \in N$：起始符号，整棵树的根。
逐项解释：
- "$(N \cup \Sigma)^*$"上的 $*$ 表示"任意长度（包括 0）的符号串"，
所以规则右边可以是任意长的符号串。这正是 CFG 比正则文法强的地方：
3 型要求右边是"一个终结符 + 最多一个非终结符"。 - "上下文无关"这个名字说的是：左边永远只是一个孤零零的 $A$，
规则的适用与 $A$ 周围有什么符号无关（不依赖上下文）。
这就是它和 1 型（上下文相关）的分界。 - 推导（derivation）：从 $S$ 开始，每一步把某个非终结符按一条规则改写成右边，
直到串里只剩下终结符。推导的过程记录成树，就是句法树。
6.2 推导、歧义、以及本节的靶子
文法片段： 句子：
S -> NP VP 三 个 学校 的 老师 来 了
VP -> V Part
NP -> NP DE NP 两棵不同的树：
NP -> NumP NP
NP -> 学校 | 老师 (1) 三个 [学校的老师]
NumP -> Num CL └─ 数量词修饰整个「学校的老师」
Num -> 三 CL -> 个 (2) [三个学校] 的老师
DE -> 的 └─ 「三个学校」是一个整体
V -> 来 Part -> 了
这就是《现代汉语》里讲的"数量词辖域歧义"。词和词性完全相同，
只有句法结构不同，而这两个结构对应两个不同的意义。
CFG 的"歧义"就是"同一个串有多于一个推导"。我们要算的就是：
给定文法，这个串到底有几种推导？
6.3 乔姆斯基范式（CNF）：CYK 的前置要求
CYK 算法只接受一种很窄的文法形式，也就是乔姆斯基范式（CNF）：
$$A \to B\,C \qquad\text{或}\qquad A \to a$$
右边的两种可能：要么是两个非终结符，要么是一个终结符。别的什么都不许有。
为什么需要这个：CYK 的核心操作是"把两个相邻的小跨度拼成一个大跨度"。
它需要每一棵子树恰好是二叉的。如果一条规则有三四个符号，
算法就不知道该从哪里切。所以先把长规则二值化：
$$A \to B\,C\,D \quad\Longrightarrow\quad A \to B\,X_1,\quad X_1 \to C\,D$$
（$X_1$ 是临时造的新非终结符，没有语言学意义，纯粹为了满足二叉要求。）
注意：$A \to B$ 这种"单产生式"和 $A \to \varepsilon$ 都要先消掉，
本节的文法里没有，所以省了这一步。
二值化不改变文法生成的语言（$L(G)$ 不变），也不改变树的结构，
只是插进去一批中间节点。这个"插入无名中间节点"的代价，就是 CYK 简单的原因。
6.4 CYK 算法
核心想法：动态规划。设 $T[i][j]$ 表示"从第 $i$ 个词到第 $j$ 个词这一段，
能由哪些非终结符推导出来"。
for 每个词 i: # 长度 1 的跨度
T[i][i] = { A : 有规则 A -> 第i个词 }
for span = 2 .. n: # 跨度从短到长
for i = 0 .. n-span: # 起点
j = i + span - 1 # 终点
for k = i .. j-1: # 枚举切分点
for 每条规则 A -> B C:
if B ∈ T[i][k] and C ∈ T[k+1][j]:
T[i][j].add(A, 来源=(k, B, C)) # 记下回溯指针
句子合语法 <=> S ∈ T[0][n-1]
逐项解释：
- 为什么从短跨度往长跨度填：因为 $T[i][j]$ 依赖 $T[i][k]$ 和 $T[k+1][j]$，
而这两个跨度都比 $[i,j]$ 短。这保证了填表时依赖的东西已经算好了。 - 为什么要记"来源"：如果只记"能不能推导出来"，你只知道句子合不合法。
要列出所有句法树，必须在每个格子里保留所有可能的 $k$ 和 $(B, C)$ 组合，
然后递归展开，这就是回溯指针（backpointer）。这也是 §5.5 里
"2 棵树"和"5 棵树"能被数出来的原因。 - 复杂度：三层循环（span、i、k）是 $O(n^3)$，内层遍历规则是常数 $|R|$，
所以总复杂度 $O(n^3 \lvert R\rvert)$。这个 $n^3$ 是"所有可能切分"的代价：
一个长度 $n$ 的句子有 $O(n^2)$ 个跨度，每个跨度有 $O(n)$ 个切分点。
6.5 实跑：手写 CYK，看它吐出两棵树
"""CYK 解析器：玩具文法 + 「三个学校的老师」的结构歧义。只用标准库。"""
# ---------- 1. 可读文法（A -> B C ... 或 A -> 词）----------
GRAMMAR = [
("S", ("NP", "VP")),
("VP", ("V", "Part")),
("NP", ("NP", "DE", "NP")), # 的-结构：X 的 Y
("NP", ("NumP", "NP")), # 数量词 + 名词短语
("NP", ("学校",)),
("NP", ("老师",)),
("NumP", ("Num", "CL")),
("Num", ("三",)),
("CL", ("个",)),
("DE", ("的",)),
("V", ("来",)),
("Part", ("了",)),
]
def binarize(rules):
"""把 A -> B C D 这种长规则右二值化成 A -> B X, X -> C D"""
out, k = [], 0
for lhs, rhs in rules:
cur = list(rhs)
while len(cur) > 2:
k += 1
new = "X%d" % k
out.append((new, (cur[-2], cur[-1])))
cur = cur[:-2] + [new]
out.append((lhs, tuple(cur)))
return out
CNF = binarize(GRAMMAR)
print("原文法 %d 条 -> CNF %d 条。新增的非终结符是二值化时临时造的：" % (len(GRAMMAR), len(CNF)))
for lhs, rhs in CNF:
if lhs.startswith("X"):
print(" %s -> %s" % (lhs, " ".join(rhs)))
# ---------- 2. CYK ----------
def cyk(words, rules):
n = len(words)
# table[i][j][A] = 该格子里 A 的所有推导方式（也就是全部回溯指针）
table = [[{} for _ in range(n)] for _ in range(n)]
for i, w in enumerate(words): # 长度 1 的跨度
for lhs, rhs in rules:
if len(rhs) == 1 and rhs[0] == w:
table[i][i].setdefault(lhs, []).append(("词", w))
for span in range(2, n + 1): # 跨度从小到大
for i in range(n - span + 1):
j = i + span - 1
for k in range(i, j): # 枚举切分点
for lhs, rhs in rules:
if len(rhs) != 2:
continue
B, C = rhs
if B in table[i][k] and C in table[k + 1][j]:
table[i][j].setdefault(lhs, []).append((k, B, C))
return table
def trees(table, i, j, sym):
"""递归展开回溯指针，列出这个格子里 sym 的全部句法树"""
out = []
for item in table[i][j][sym]:
if item[0] == "词":
out.append(sym + "(" + item[1] + ")")
else:
k, B, C = item
for lb in trees(table, i, k, B):
for rb in trees(table, k + 1, j, C):
out.append(sym + "(" + lb + " " + rb + ")")
return out
SENT = "三 个 学校 的 老师 来 了"
words = SENT.split()
T = cyk(words, CNF)
n = len(words)
print("\n句子：%s （%d 个词）" % (SENT, n))
print("注意：词和词性完全相同，只有结构不同。")
print("\n【DP 表格】每一格列出该跨度上能成立的非终结符（下三角）")
print(" " + "".join("%-22s" % ("%d:%s" % (j, words[j])) for j in range(n)))
for i in range(n):
row = " %d:%s " % (i, words[i])
for j in range(n):
row += "%-22s" % (",".join(sorted(T[i][j])) if j >= i else "·")
print(row)
print("\n【全部合法句法树】从 S 出发、覆盖 0~%d 的推导共 %d 棵"
% (n - 1, len(trees(T, 0, n - 1, "S"))))
for t in trees(T, 0, n - 1, "S"):
print(" " + t)
# 顺手看一眼：别的串能出几棵树
print("\n【对照】同一套文法解析别的串")
def count_parses(s):
w = s.split()
t = cyk(w, CNF)
return len(trees(t, 0, len(w) - 1, "S")) if "S" in t[0][len(w) - 1] else 0
for s in ["三 个 学校 来 了",
"三 个 学校 的 老师 来 了",
"三 个 学校 的 老师 的 学校 来 了"]:
print(" 「%s」 -> %d 棵树" % (s, count_parses(s)))
print(" 「三 个 个 来 了」 -> %d 棵树（不合语法，S 格子里什么都没有）"
% count_parses("三 个 个 来 了"))
实跑输出
原文法 12 条 -> CNF 13 条。新增的非终结符是二值化时临时造的：
X1 -> DE NP
句子：三 个 学校 的 老师 来 了 （7 个词）
注意：词和词性完全相同，只有结构不同。
【DP 表格】每一格列出该跨度上能成立的非终结符（下三角）
0:三 1:个 2:学校 3:的 4:老师 5:来 6:了
0:三 Num NumP NP NP S
1:个 · CL
2:学校 · · NP NP S
3:的 · · · DE X1
4:老师 · · · · NP S
5:来 · · · · · V VP
6:了 · · · · · · Part
【全部合法句法树】从 S 出发、覆盖 0~6 的推导共 2 棵
S(NP(NumP(Num(三) CL(个)) NP(NP(学校) X1(DE(的) NP(老师)))) VP(V(来) Part(了)))
S(NP(NP(NumP(Num(三) CL(个)) NP(学校)) X1(DE(的) NP(老师))) VP(V(来) Part(了)))
【对照】同一套文法解析别的串
「三 个 学校 来 了」 -> 1 棵树
「三 个 学校 的 老师 来 了」 -> 2 棵树
「三 个 学校 的 老师 的 学校 来 了」 -> 5 棵树
「三 个 个 来 了」 -> 0 棵树（不合语法，S 格子里什么都没有）
6.6 怎么读这张表和这两棵树
第一：两棵树的差别就是语言学上的差别。
(1) S(NP(NumP(三 个) NP(NP(学校) X1(的 老师))) VP(来 了))
= 三 个 [ 学校 的 老师 ]
数量词「三个」修饰整个「学校的老师」
→ 意义：这位老师有三份（比如在三个学校任教）
(2) S(NP(NP(NumP(三 个) NP(学校)) X1(的 老师)) VP(来 了))
= [ 三 个 学校 ] 的 老师
「三个学校」是一个整体，再被「的」接到「老师」上
→ 意义：来自三个学校的那位老师
算法没有"理解"这句话，它把两种可能都算出来了。
消解歧义是下一步的事（需要概率、语义或上下文），CFG 本身做不到。
这正是《自然语言处理》§5 里讲的：句法分析器的输出是"结构集合"，
不是"唯一正确的结构"。
第二：DP 表格的读法。看对角线往右上一格一格读：
T[0][0] = {Num}（"三"是数词），T[1][1] = {CL}（"个"是量词）；- 跨度 2 的
T[0][1] = {NumP}，因为规则NumP -> Num CL，
$B = \text{Num} \in T[0][0]$，$C = \text{CL} \in T[1][1]$，切分点 $k=0$； - 跨度 4 的
T[0][3]是空的（"三 个 学校 的"推不出任何非终结符），
空格子不是错误，是 CYK 在说"这一段不可能是一个成分"； - 跨度 5 的
T[0][4]出现NP，而且只有一种来源：
$k=1$ 时 $B = \text{NumP} \in T[0][1]$，$C = \text{NP} \in T[2][4]$。
另一种切分 $k=3$ 走不通，因为 $T[4][4]$ 是 NP 但 $T[0][3]$ 是空的。 - 跨度 7 的
T[0][6] = {S}：$k=4$ 时 $B = \text{NP} \in T[0][4]$，
$C = \text{VP} \in T[5][6]$。注意 $T[0][4]$ 那个 NP 格子里有两条来源，
这就是两棵树的来源。
第三：歧义的规模会爆炸。对照那一行很说明问题：
把句子加长成「三个学校的老师的学校来了」（9 个词），树的数量变成 5。
每多一层"的"，歧义就多翻几倍。这就是为什么真实长度的句子
（20+ 词）用无概率 CFG 解析会得到天文数字的树，
工业系统必须用 PCFG（概率 CFG）给每条规则配概率，
再取概率最大的那棵树（或者做 k-best 剪枝）。
6.7 边界与批评（CFG 与 CYK）
- $O(n^3)$ 只是渐近最优。CYK 是 1960 年代三个独立工作
（Cocke、Kasami、Younger）的产物，正式发表的是 Younger 1967，
Information and Control 10(2): 189–208；Cocke 和 Kasami 的贡献
以技术报告形式存在（确切出处待查）。
更好的算法是 Earley 1970（Communications of the ACM 13(2): 94–102），
它在"文法不大、句子不长"时快得多，而且不需要 CNF。
但 CYK 的结构最简单、最容易手写、最容易被证明正确，
本页用它就是为了这一点。 - CFG 表达不了自然语言的全部结构。§4.6 已经说了，
瑞士德语的交叉依赖被认为超出了 CFG。但工程上大家还是用 CFG，
因为那类结构极其罕见，为了它升级整套形式装置不划算。 - 无概率 CFG 没有偏好。它只会说"这 5 棵树都合法"，不会说"第 2 棵更可能"。
概率化的代价是需要标注树库来估参数，而树库的构建又回到 §3.6 讲的问题：
标注一致性、规范制定、人工成本。 - "合语法"不等于"能解析"。CYK 判定的"合语法"完全是相对于你给的那套文法。
文法写错了，算法不会告诉你，它会忠实地按错文法解析。
本页的文法是个玩具（12 条规则），"三 个 学校 的 老师 来 了" 恰好给出 2 棵树，
是因为我把文法写成了恰好产生 2 棵，这本身就是一种"人为控制变量"，
真实研究中必须先说明文法从哪来。
6.8 结构计算的一个真实应用：§4.4 的 FST 与 §5.5 的 CYK 是什么关系
这两样东西看起来在讲不同的事，其实是一回事的两端：
| FST（§4.4） | CYK（§5.5） | |
|---|---|---|
| 处理的对象 | 词的内部（形态、音系） | 词的外部（句法结构） |
| 形式装置的强度 | 正则（有限状态） | 上下文无关（有栈） |
| 算法复杂度 | $O(n)$ 线性 | $O(n^3)$ |
| 为什么它能用更低复杂度 | 形态规律是局部的 | 句法要处理递归嵌套 |
这就是"语言分层"的工程含义：越往上层（词法 → 句法 → 语义），
依赖越非局部，需要的形式装置越强、算法越慢。
《现代汉语》里讲的"语素-词-短语-句子"层级，在计算这边对应的是
复杂度的阶梯。
7 语言工程入门：从语料到可评测系统
§1-§5 都是"分析"。这一节是"建造"：怎样把前面那些度量和方法，
做成一条别人能复现、结果能比较的流水线。这是三门课里最浅的一门，
但它教的东西最不容易自学，因为它的难点全在"规范"上，而规范是靠踩坑攒出来的。
7.1 完整流程
┌──────────────┐
│ 1. 任务定义 │ 先说清楚"要做什么、怎么算做对了"
└──────┬───────┘ ← 90% 的项目死在这一步没做清楚
▼
┌──────────────┐
│ 2. 语料获取 │ 现有语料库 / 爬取 / 合作方给 / 自己造
└──────┬───────┘ 坑：版权、隐私、领域偏差
▼
┌──────────────┐
│ 3. 清洗 │ 去重、去模板、编码统一（UTF-8 NFKC）、
└──────┬───────┘ 去 HTML/公式/代码、全半角统一
▼ 坑：清洗过度 -> 把有用的信号也洗掉了
┌──────────────┐
│ 4. 切分+标注 │ 分词 / 词性 / 依存 / 语义标签
└──────┬───────┘ 坑：规范歧义 -> 一致性低 -> 数据报废
▼
┌──────────────┐
│ 5. 划分 │ 训练 / 开发 / 测试，按"文档"或"说话人"切
└──────┬───────┘ 坑：泄漏（同一个句子出现在两个集合里）
▼
┌──────────────┐
│ 6. 建模 │ 统计方法（本页 §1-§3）或神经方法（隔壁两页）
└──────┬───────┘
▼
┌──────────────┐
│ 7. 评测 │ 指标 + 显著性 + 误差分析 + 人工抽检
└──────┬───────┘ 坑：只报一个数字，不做误差分析
▼
┌──────────────┐
│ 8. 发布 │ 模型/数据/代码/版本，别人能复现
└──────────────┘
这个流程图是一条反馈回路：
第 7 步的误差分析经常会把你打回第 3 步（数据脏）、第 4 步（标注规范有歧义）
甚至第 1 步（任务定义本身有问题）。新手最容易犯的错是把 1-5 步当成
"准备工作"草草做完，然后花 90% 的时间调第 6 步的模型。
7.2 每一站的坑，逐条说
第 2 站·语料获取：
- 现成语料库优先。中文方面，做计量语言学的常用资源包括
各类报刊/文学语料库、以及依存树库，真实研究必须用公开树库而不是
自己标 12 句（§3.6）。国际上最通用的一套是
Universal Dependencies（UD），它把几十种语言的依存标注统一到一套标签体系下，
这正是 Futrell et al. (2015) 能跨 37 种语言比较的前提。
- 版权和隐私是硬约束，不是形式主义。用别人的语料要看许可协议；
涉及个人信息的数据必须脱敏。
第 3 站·清洗：
- 编码统一是最容易被忽略的坑。全角/半角、繁简、异体字、
Unicode 正规化（NFKC）不统一，会导致"同一个词被统计成两种"，
直接污染 §1 的所有频次统计。
- 清洗过度是反向的坑：把标点全删了，§1.5 的分句切分就没法做了；
把重复的模板句全删了，某些真实分布特征也被删了。
第 4 站·切分与标注（这一站最贵）：
- 分词：汉语特有。同一个串可以有多种切法（§1.3 已经证明切分单位
能改变统计结论）。所以分词规范必须先写下来再动手，
而不是"大家凭感觉切"。
- 标注规范：什么算一个命名实体？"北京大学"是一个还是两个？
"的"字结构的中心语怎么定？规范必须先写、先试标、先算一致性、
再大规模标。跳过试标的项目，标到一半会发现前面全白标了。
第 5 站·划分：
- 数据泄漏是评测里最严重的错误。如果测试集里的句子在训练集里出现过
（哪怕是近似重复），指标会虚高得离谱。正确做法是按文档/按说话人/按时间切，
而不是随机切句子。
- 测试集要冻结。一旦开始用它调参，它就不再是测试集了（变成第二个开发集）。
第 7 站·评测：见 §6.4。
7.3 常见工具链（只讲用途，本页不要求安装）
| 环节 | 常见工具 | 它做什么 | 本页替代方案 |
|---|---|---|---|
| 中文分词 | jieba、HanLP、THULAC、LTP | 把连续汉字切成词 | 本页用"字"和"字对"绕过（§1.3 已说明代价） |
| 词性/依存标注 | spaCy、Stanza、UDPipe、HanLP | 给词标词性、依存弧 | 本页 §3.4 手工标注 96 个词 |
| 树库格式 | CoNLL-U | 依存标注的标准文本格式 | 本页用 heads 列表（就是它的 HEAD 列） |
| 有限状态工具 | OpenFST、Foma、HFST | 编译/合成/求逆转换器 | 本页 §4.4 手写 4 状态 FST |
| 统计计算 | numpy / scipy / pandas | 频次、拟合、检验 | 本页全部计算 |
| 神经模型 | PyTorch、HuggingFace transformers | 训练/微调大模型 | 见《深度学习》与《自然语言处理》 |
关于 CoNLL-U：它是十列制表符分隔的纯文本，每一行一个词，
关键三列是 ID（位置）、FORM（词形）、HEAD（支配词的下标）。
本页 §3.4 的 heads 列表就是 HEAD 列。知道这个格式，
你就能直接读任何公开树库。
关于"要不要学工具"：先懂原理，再用工具。
本页故意让你手算 MDD、手写 CYK、手写 FST，就是为了让工具变成"省力装置"
而不是"黑箱"。反过来，如果你只用 jieba 而不知道分词规范是怎么回事，
你连它切错了都发现不了。
7.4 评测：四个必须区分的东西
① 准确率（accuracy）vs 精确率/召回率/F1
$$P = \frac{TP}{TP+FP}, \qquad R = \frac{TP}{TP+FN}, \qquad F_1 = \frac{2PR}{P+R}$$
逐项解释：$P$ 回答"我报出来的有多少是对的"，
$R$ 回答"该报的里面我漏了多少"，$F_1$ 是两者的调和平均
（用调和平均而不是算术平均，是为了惩罚偏科：
$P = 1, R = 0$ 时算术平均是 0.5，调和平均是 0，更符合实际）。
类别不平衡时准确率会骗人：99% 的样本是负类时，全猜负类准确率就有 99%。
② 标注一致性（inter-annotator agreement）≠ 准确率
这是语料库语言学特有的一个指标，也是最常被混淆的一个。
它衡量的是"两个标注者有多一致"，通常用 Cohen's $\kappa$：
$$\kappa = \frac{P_o - P_e}{1 - P_e}$$
逐项解释：$P_o$ 是观察到的实际一致率，$P_e$ 是"两个人都随机猜"时
按类别频率算出的期望一致率。减去 $P_e$ 再除以 $1 - P_e$，
是为了扣除"碰巧一致"：如果 90% 的标签都是同一个类别，
两个人即使都在瞎猜也有一致率。$\kappa$ 校正了这一点，这是它存在的全部理由。
为什么必须报告它：因为一个标注者标错了的语料，会让所有下游结论一起错。
一致性太低（通常 $\kappa < 0.6$）说明规范有歧义，
此时正确的动作是回去改规范，不是"接着标"。
③ 显著性检验：§2 的 LLR、§1.5 的零模型都是这个层面的工具。
报一个指标提升必须同时报它在什么条件下显著，
「B 模型比 A 模型高 0.3 分」这句话在没有置信区间时没有信息量。
④ 误差分析（error analysis）：把人分成"随机抽 100 个错误样本、
逐条看它错在哪、归类"。这是整个流程里最有信息量的一步，
而且几乎没有替代品，它经常直接指出"你的训练数据里缺某一类"。
7.5 边界与批评（语言工程）
- "工程"和"科学"的目标冲突。工业界只要能上线的系统，
不在乎它是否反映了语言的真结构；计量语言学在乎结构，
不在乎能不能上线。这两拨人在同一门课里，很容易互相看不上。
理解对方的约束条件，是这门课真正要教的态度。 - 可复现性危机。NLP 领域近年反复出现"复现不出来"的问题，
原因通常在第 3-5 步没写清楚（数据版本、清洗脚本、划分随机种子）。
本页所有代码都在注释里说明了数据来源和版本，就是为了示范这个习惯。 - 工具会过时，规范不会。jieba 可能在五年后被取代，
但"必须先定分词规范""必须切分训练测试集""必须算一致性"这几条不会。
这门课的价值在规范，不在工具。
8 和你专业的关系：语言作为复杂系统
8.1 这门课给认知科学提供了什么
计量语言学是"语言是一个复杂系统"这个说法的证据来源。
"复杂系统"在别的学科里常被当成一个模糊的修辞。但在这条线上，它是有具体内容的：
| 复杂系统的特征 | 在本页的对应 | 证据位置 |
|---|---|---|
| 幂律分布（无标度） | Zipf 定律 | §1.2 实跑：字对斜率 -0.998 |
| 增长的路径依赖 | Heaps 定律 | §1.4 实跑：β=0.70 |
| 多层级自相似 | Menzerath-Altmann | §1.5 实跑：没测到 |
| 局部优化的痕迹 | 依存距离最小化 | §3.3 实跑：比随机短 43.5% |
| 系统在约束下运行 | 离最优还差 18.6% | §3.5 实跑 |
最后两行是配套的：只有同时看到"比随机好"和"没到最优"，
才能说"系统在多个约束下做权衡"，这是复杂系统研究的标准论证结构。
只报前半句，就成了过度解读。
8.2 和《心理语言学》的接缝（这条最直接）
§3 讲的依存距离有一个认知机制假设：距离越长，工作记忆负荷越大。
这条假设把纯语料的统计和人的行为接了起来。相关的两条文献线：
- Gibson (1998)，Cognition 68(1): 1–76，提出"依存局部性理论"（DLT），
用"未完成的依存"的数量预测加工难度； - surprisal 框架（Hale 2001；Levy 2008，Cognition 106(3): 1126–1177）
从概率角度预测难度：一个词在上下文中越出人意料，读起来越慢。
这两个框架是可以对上的：长依存往往意味着更难预测，所以 DLM 效应
和 surprisal 效应在很多实验里部分重叠。这是《心理语言学》和本页的天然接口，
语料侧的规律（本页）和读者侧的反应（那门课）互为解释。
但也有一个必须警惕的鸿沟：语料的统计规律 ≠ 说话人的心理机制。
"汉语的 MDD 偏大"是一个关于语料的事实；
"汉语使用者工作记忆负荷更大"是一个关于人的假设，
后者需要反应时/眼动/脑电实验才能支持。从前者跳到后者，是这一支文献最常见的过度推论。
8.3 汉语的独特性（你最该关心的部分）
作为汉语母语者、又在做认知科学，你在这个方向上有几个现成的切入点：
- 汉语的依存距离在跨语言比较里偏大。原因是汉语的修饰语基本前置
（"的"字结构、介词短语、"把"字句的处置成分），
这会产生大量向后的长弧（§3.5 那条"书 ← 读 距离 7"就是典型）。
这和其他语言"往中心语靠"的策略很不一样，是一个真实且未完全解释的跨语言差异。 - 汉语的统计单位天然是两级的（字/词），这在 §1.3 和 §1.4 里直接产生了
两组完全不同的指数。"汉语的 Zipf 指数是多少"这个问题，
不先说清是字还是词，就是没有答案的。 - 汉语没有形态变化，所以 §4.4 那种"输入-输出"式形态规则很少，
汉语的 FST 更多用在拼音转汉字、注音、简繁转换这类任务上。
这决定了汉语计算的工具链和英语从一开始就不一样。
8.4 一个真实的哲学分歧（值得你知道它存在）
统计规律是"语言的规律"还是"用语言的人的规律"？
- 一种立场：Zipf、Heaps、DLM 是语言这个符号系统本身的性质，
和说话人是谁无关（所以可以跨语言、跨语料重复观察到）。 - 另一种立场：这些规律全是人的认知约束的副产品
（省力、工作记忆有限、偏好平滑的信息流），
所以它们是认知科学的发现，不是语言学的发现。
§1.5 那个"没测到 Menzerath 定律"的结果，正好是这场争论的样本：
如果你在一个语料里测到了幂律，而猴子打字也能产生幂律
（Miller 1957；Torre et al. 2021），那么"测到幂律"这件事
对两种立场都兼容，因此不构成对任何一方的证据。
怎么在这条线上做得站得住：永远问"这个规律相对于什么零模型成立"，
而不是"这个规律存不存在"。这就是本页从 §1.5 到 §3.6 反复在做的事。
这条方法论在整个认知科学里都通用
（对照《实验方法论核心》里的随机基线、以及《心理语言学》里对惊喜效应的控制条件）。
升学提示：这条路线在海外硕士里通常归入
quantitative linguistics / corpus linguistics / computational linguistics
三个方向，前两个偏本页，第三个偏《自然语言处理》。做这个方向的组
通常要求你能独立写语料处理脚本 + 会基础统计 + 会读依存树库，
本页的四条能力（见导论 ③）刚好对应。
9 习题（带答案）
做题约定：能用纸笔算的就别开电脑；要开电脑时用 ~/miniconda3/bin/python。
每道题的答案后面标了它在正文里的位置。
9.1 第 1 题：Zipf 手算，以及 $r$ 的陷阱（§1.2-§1.3）
某语料的单位频次如下（已按频次降序）：
| 名次 $r$ | 1 | 2 | 4 | 8 | 16 |
|---|---|---|---|---|---|
| 频次 $f(r)$ | 100 | 55 | 30 | 16 | 9 |
(a) 用 $r=1$ 和 $r=16$ 两个点，手算双对数直线的斜率。
(b) 用上全部五个点做最小二乘，得到的斜率是 $-0.8729$，$r = -0.9999$。
这个 $r$ 说明什么？这个斜率说明什么？
(c) 有人看到 $r = -0.9999$，宣布"完美验证了 Zipf 定律"。
他错在哪？
答案
(a) $\log_{10}100 = 2.000$，$\log_{10}9 = 0.9542$；
$\log_{10}1 = 0$，$\log_{10}16 = 1.2041$。
$$\text{斜率} = \frac{0.9542 - 2.000}{1.2041 - 0} = \frac{-1.0458}{1.2041} = -0.8685$$
(b) $r = -0.9999$ 说明这五个点在双对数坐标里几乎完美地落在一条直线上，
即"幂律"这个函数形式很适合描述这组数据。
但斜率 $-0.8729$ 不等于 $-1$，也就是说这不是 Zipf 定律的经典形式，
而是一条更平缓的幂律（名次翻 16 倍，频次降到原来的 $16^{-0.87} \approx 8.9\%$，
而不是 $\frac{1}{16} = 6.25\%$）。
$r$ 衡量的是"像不像直线"，斜率衡量的是"是哪一条直线"。两件事必须分开看。
(c) 三个错误：
1. 把"拟合得好"当成"理论被验证"。Zipf 定律是一个有具体参数的预测
（$\alpha = 1$），不是"随便一条幂律都算"。斜率 $-0.87$ 是不符合的。
2. 只看 $r$ 不看残差结构。五个点太少了，无法判断有没有系统性偏差。
§1.2 的教训是：必须分段拟合 + 回到原始尺度看 $R^2$。
3. 没有对照零模型。§1.5 已经证明，一条"漂亮的拟合"可能完全是随机过程的产物。
9.2 第 2 题：Heaps 定律的外推（§1.4）
本页字对语料的 Heaps 拟合结果是 $\beta = 0.7006$、$K = 7.814$，
在 $N = 234761$ 时 $V = 43704$。
(a) 语料规模翻 4 倍（$N = 939044$），$V$ 预计是多少？
(b) 想让 $V$ 翻倍到 87408，语料要变成原来的几倍？
(c) 为什么这个外推必须加"仅在幂律区间内有效"的限定？
(d) 理论上，如果类型频率严格服从指数为 $\alpha$ 的幂律，
Heaps 指数满足 $\beta = 1/\alpha$（这是"频率分布"和"词表增长"是同一枚硬币两面的数学表达）。
本页汉字 $\alpha = 1.94 \Rightarrow 1/\alpha = 0.515$，实测 $\beta = 0.2505$；
字对 $\alpha = 0.998 \Rightarrow 1/\alpha \approx 1.002$，实测 $\beta = 0.7006$。
两组都对不上。这说明什么？
答案
(a) $V \propto N^{\beta}$，所以 $\frac{V_2}{V_1} = 4^{0.7006} = 2.6412$，
$V_2 \approx 43704 \times 2.6412 \approx \mathbf{115432}$。
(b) 要 $\frac{V_2}{V_1} = 2$，需 $N_2/N_1 = 2^{1/0.7006} = 2^{1.4273} = 2.6895$，
即语料要变成 2.69 倍（约 63 万字对）。
这就是"词汇量翻倍要靠语料翻近三倍"的定量表达。
(c) 因为幂律只是一段区间上的近似。§1.3 已经看到：
字对的表虽然大，但并非无限，读到一定程度后新 type 的增长必然会放缓，
$\beta$ 会掉下来（汉字那组 $\beta$ 只有 0.25 就是饱和后的样子）。
任何幂律外推到数据范围之外都是不可靠的，这句限定不是客套话。
(d) 不是公式错了，是前提没满足。$\beta = 1/\alpha$ 的推导需要三条前提：
（i）分布是纯幂律（不是 Mandelbrot 形式）；
（ii）$\alpha > 1$；（iii）语料是从该分布里独立随机抽样得到的。逐条检查：
- 汉字：$\alpha = 1.94 > 1$ 满足（ii），但 §1.3 已经证明它的分布严重偏离纯幂律
（分段斜率从 $-0.64$ 一路变到 $-4.29$），(i) 不满足；而且字表封顶，
抽样的"独立性"也被破坏（能出现的字就那两千多个）。 - 字对：$\alpha = 0.998 < 1$，直接卡在 (ii) 的边界外，
指数小于 1 的幂律期望是无穷的，理论关系根本不适用。
更有价值的读法：这说明"分布"和"增长"是两个独立的经验事实，
谁也不能从谁直接推出来。要同时解释两者，需要一个更强的生成模型，
§1.1 的随机打字模型（Miller 1957）就是这样一个模型，它能同时给出 Zipf 形式的分布
和 Heaps 形式的增长。方法论教训：从公式推出来的关系，用之前必须逐条核对前提。
这是本页第四次出现同一个教训了（§1.3 的 $R^2$、§1.5 的零模型、§3.3 的基线，这里）。
9.3 第 3 题：零模型设计（§1.5、§3.3）
有人说："汉语的『的』字平均每 6 个字就出现一次，使用频率极高，
说明汉语的定语标记系统非常发达。"
(a) 这个论证缺了什么？
(b) 设计一个零模型来检验"极高"这个说法。
(c) 为什么这一题和 §3 的随机语序基线是同一件事？
答案
(a) 缺参照系。"极高"是一个比较级，必须有比较对象才成立。
"每 6 个字出现一次"这个数字，在任何语言的高频虚词上都能观察到
（英语的 the、of 同理），它既不能支持"汉语定语标记发达"，
也不能反驳。没有零模型的频率数字不构成证据。
(b) 至少三种可行的零模型：
1. 句内乱序：保持每个句子的长度和整篇语料的字频分布不变，
把每个句子内部的字序随机打乱（不打乱跨句），重算"的"的出现率。
如果打乱后频率差不多，说明这个频率只是字频分布的副产品，和语序无关。
2. 跨语料对照：拿一份体裁完全不同的汉语语料（小说、口语转写）做同样的统计，
看差异有多大。如果同一语言内部差异就很大，那"汉语如何如何"这种说法要打折。
3. 跨语言对照：拿同规模的英语语料，统计英语定冠词/介词的比例。
这是 §3 里 Futrell et al. 那种跨语言比较的思路。
(c) 因为是同一个逻辑："这个数是大还是小"必须相对于一个"如果机制不存在时
该是多少"的基线才能判断。§3 里我们固定树、打乱语序，正是为了
把"句子长度/树形状"这些不该变的因素控住，只留下"语序"这一个变量。
这一题里固定"字频分布"、打乱"字序"是完全同构的操作。
零模型思维是这一整页的方法论主线。
9.4 第 4 题：解释一个负面结果（§1.5）
§1.5 的 Menzerath-Altmann 检验结果：实测 $r = -0.0065$，
零模型 95% 区间 $[-0.0206, +0.0222]$；换切分方式后 $r$ 变成 $+0.0119$、$+0.0230$。
(a) 列出三种可能的原因。
(b) 为每一种设计一个能把它和其他两种区分开的后续实验。
(c) 你不能从这次结果里推出什么结论？
答案
(a)
1. 测量单位不当：原始文献测量"音节/词"，本页用"字"近似；
2. 语料不适配：24 篇教学笔记，句子偏短、结构偏简单，不是自然语言文本；
3. 定律本身是统计假象：无记忆随机过程也能产生 MAL 形式的规律
（Torre, Dębowski & Hernández-Fernández 2021，PLoS ONE 16(8): e0256133）。
(b)
1. 手工分词：挑 200 个句子人工分词，用"词"代替"字"重算。
如果效应出现 → 支持原因 1。
2. 换语料：用一份小说或新闻语料（体裁完全不同）重跑同样的代码。
如果效应出现 → 支持原因 2；如果仍然没有 → 排除原因 2。
3. 猴子打字对照：写一个无记忆的随机文本生成器（随机抽字组成"句子"，
控制句长分布与真实语料相同），对生成文本跑同样的分析。
如果生成文本也出现负相关 → 支持原因 3（即使真实语料有效应，
这个效应也缺乏解释力）。
(c) 不能说"Menzerath-Altmann 定律是错的"，也不能说"语言不服从这条定律"。
只能说："在这份语料、这个层级、这个测量方式下，本页没有观察到它。"
这是负面结果的标准表述方式，也是 §1.6 反复强调的"结论要带作用域"。
9.5 第 5 题：手算依存距离（§3）
句子：他 昨天 读 了 那 本 新 书（8 个词，下标从 0 开始）
依存标注：heads = [2, 2, -1, 2, 5, 7, 7, 2]
(a) 把每一条依存弧写出来，算出这个句子的 MDD。
(b) 哪条弧最长？它在语言学上对应什么现象？
(c) 如果把这句话的词序完全随机打乱（树结构不变），
你预计 MDD 会变大还是变小？为什么不能只凭直觉下结论？
答案
(a) 逐条：
| 从属词 | 支配词 | 距离 |
|---|---|---|
| 他(0) | 读(2) | 2 |
| 昨天(1) | 读(2) | 1 |
| 了(3) | 读(2) | 1 |
| 那(4) | 本(5) | 1 |
| 本(5) | 书(7) | 2 |
| 新(6) | 书(7) | 1 |
| 书(7) | 读(2) | 5 |
共 7 条弧，总距离 $2+1+1+1+2+1+5 = 13$。
$$\mathrm{MDD} = \frac{13}{7} \approx 1.857$$
(b) 最长的是 书 ← 读，距离 5。对应的是汉语的"定语前置"现象：
宾语"书"被定语"那本新的"推到了句子末尾，和动词"读"之间隔了 3 个词。
这就是 §3.5 单句示形里"书 ← 读 距离 7"的同型现象。
(c) 预计变大。因为真实语序下大部分弧是 1~2，只有一条长弧；
随机语序会把"哪两个词相邻"重新洗牌，长弧会变多（两个需要配对的词
被随机放远的概率很高）。§3.4 的实跑证实了这一点：
12 句的平均 MDD 从 1.691（实测）涨到 2.990（随机），差了 43.5%。
但不能凭直觉下结论，因为：
1. 直觉说不出大多少，是 5% 还是 50%？
2. 更关键的是，短句子里随机化几乎不产生差别（§3.4 里 3 词句子只差 25%），
而长句子里差别很大（47.7%）。不做基线就分不清"这个语言的语序好"
和"我的句子都太短"。
9.6 第 6 题：搭配三度量手算（§2）
语料 $N = 100000$。对某对单位，$O_{11} = 40$，$R_1 = 100$，$C_2 = 200$。
(a) 算出 $E_{11}$、MI、t-score。
(b) 把四个格子填全，算出 LLR。
(c) 假设另一个对子的 $O_{11} = R_1 = C_2 = 2$。算出它的 MI 和 t 值。
这两个数字矛盾吗？该信哪个？
答案
(a) $E_{11} = \frac{100 \times 200}{100000} = \mathbf{0.2}$
$$\mathrm{MI} = \log_2\frac{40}{0.2} = \log_2 200 = \mathbf{7.6439}$$
$$t = \frac{40 - 0.2}{\sqrt{40}} = \frac{39.8}{6.3246} = \mathbf{6.2929}$$
(b) 四个格子与期望：
| $w_2$ 出现 | $w_2$ 没出现 | 合计 | |
|---|---|---|---|
| $w_1$ 出现 | $O_{11}=40$，$E_{11}=0.2$ | $O_{12}=60$，$E_{12}=99.8$ | 100 |
| $w_1$ 没出现 | $O_{21}=160$，$E_{21}=199.8$ | $O_{22}=99740$，$E_{22}=99700.2$ | 99900 |
| 合计 | 200 | 99800 | 100000 |
$$\mathrm{LLR} = 2\left[40\ln\frac{40}{0.2} + 60\ln\frac{60}{99.8} + 160\ln\frac{160}{199.8} + 99740\ln\frac{99740}{99700.2}\right] \approx \mathbf{371.34}$$
（作为参照：$\chi^2_1$ 在 $p=0.001$ 时的临界值是 10.83，371 远远超过它。）
(c) $E_{11} = \frac{2\times 2}{100000} = 0.00004$。
$$\mathrm{MI} = \log_2\frac{2}{0.00004} = \log_2 50000 = \mathbf{15.6096}, \qquad t = \frac{2 - 0.00004}{\sqrt{2}} = \mathbf{1.4142}$$
不矛盾，两个数字在回答不同的问题：
MI 说"这个共现比随机预期强 5 万倍"，听起来惊人，
但它的证据只有 2 次观测；t 值说"这个超出量只有 1.4 个标准差"，
在统计上和 0 没有区别。
该信 t 值（和 LLR）。§2.6 的恒等式给出了原因：
$t = \sqrt{O_{11}}\,(1 - 2^{-\mathrm{MI}})$。
这个对子的 $1 - 2^{-15.61} \approx 0.99998$ 已经接近 1 了，
但前面的 $\sqrt{2} = 1.414$ 太小，乘起来还是上不去。
MI 只测"强度"不测"证据量"，这就是它最大的缺陷。
9.7 第 7 题：CYK 表格手填（§5）
用 §5.5 的那套文法（12 条规则，见正文），解析句子：
三 个 老师 来 了（5 个词）
(a) 填出 DP 表格（只填下三角，标出每格的非终结符）。
(b) 一共几棵树？写出来。
(c) 对比「三 个 学校 的 老师 来 了」（2 棵树），说明歧义的来源是什么。
答案
(a) 长度 1 的格子：$T[0][0] = \{\text{Num}\}$、$T[1][1] = \{\text{CL}\}$、
$T[2][2] = \{\text{NP}\}$、$T[3][3] = \{\text{V}\}$、$T[4][4] = \{\text{Part}\}$。
按跨度从小到大：
| 跨度 | 格子 | 内容 | 依据 |
|---|---|---|---|
| 2 | $T[0][1]$ | $\{\text{NumP}\}$ | $\text{NumP} \to \text{Num CL}$，$k=0$ |
| 2 | $T[1][2]$ | $\varnothing$ | 没有规则能把 CL 和 NP 拼起来 |
| 2 | $T[2][3]$ | $\varnothing$ | NP 和 V 拼不起来 |
| 2 | $T[3][4]$ | $\{\text{VP}\}$ | $\text{VP} \to \text{V Part}$，$k=3$ |
| 3 | $T[1][3]$ | $\varnothing$ | $T[1][2]$ 空，怎么切都不行 |
| 3 | $T[2][4]$ | $\varnothing$ | 同理 |
| 3 | $T[0][2]$ | $\{\text{NP}\}$ | $\text{NP} \to \text{NumP NP}$，$k=1$ |
| 4 | $T[0][3]$ | $\varnothing$ | $T[0][k]$ 与 $T[k+1][3]$ 没有能配上的 |
| 4 | $T[1][4]$ | $\varnothing$ | 同理 |
| 5 | $T[0][4]$ | $\{\text{S}\}$ | $\text{S} \to \text{NP VP}$，$k=2$ |
(b) 1 棵树：
S( NP( NumP( Num(三) CL(个) ) NP(老师) ) VP( V(来) Part(了) ) )
即"三 个 老师"只能读成 [三个 老师]，没有歧义。
(c) 歧义的来源是 NP -> NP DE NP（的-结构）和 NP -> NumP NP（数量词结构）
这两条规则可以互相嵌套：
- 「三个学校的老师」里，"三个"既可以修饰"学校"（→ [三个学校] 的 老师），
也可以修饰"学校的老师"（→ 三个 [学校的老师]）。两条路径都通，所以两棵树。 - 「三个老师来了」里没有"的"，
NP -> NP DE NP这条规则用不上，
嵌套无从发生，所以只有一条路径、一棵树。
一般化的结论：歧义的数量来自"有几条规则可以竞争同一个跨度"，
而不是来自"句子有多长"。§5.5 的对照里，加一层"的"就从 2 棵变成 5 棵，
正是因为每加一层就多出一次嵌套选择的机会。
9.8 第 8 题：判断乔姆斯基层级（§4）
判断下列每个语言属于哪一层，并说明理由（能给出文法或自动机的就给出）：
(a) $L_1 = \{$ 所有由 $a,b$ 组成、以 $b$ 结尾的串 $\}$
(b) $L_2 = \{a^nb^nc^m : n \ge 1, m \ge 1\}$
(c) $L_3 = \{ww : w \in \{a,b\}^+\}$（把任意串原样重复一遍）
(d) 汉语（在"任意深度中心嵌套都合语法"的理想化下）
答案
(a) 正则语言（3 型）。理由：只需要记住"上一个读到的是不是 $b$"，
2 个状态就够：$q_0 \xrightarrow{a,b} q_0$，$q_0 \xrightarrow{b} q_1$，
$q_1 \xrightarrow{a,b} q_0$，$q_1 \xrightarrow{b} q_1$，$q_1$ 是接受状态。
它不需要数数，所以有限状态足够。
(b) 上下文无关语言（2 型）。文法：
$$S \to AB, \qquad A \to aAb \mid ab, \qquad B \to cB \mid c$$
理由：$a$ 和 $b$ 必须配平（数数 → 需要栈），
但 $c$ 的个数和 $n$ 无关，可以独立处理。用泵引理可以证明它不是正则的
（证明与 §4.5 里 $\{a^nb^n\}$ 的证明同构：取 $w = a^pbc$，
$y$ 只能是 $a$，泵一下 $a$ 的个数就配不平了）。
(c) 上下文相关语言（1 型），不是上下文无关的。
这是著名的"复制语言"。直觉理由：CFG 的规则是"局部改写"的，
它没有一个机制能把前面生成的一整段原样复制到后面。
形式证明要用 CFG 的泵引理（或 Ogden 引理），
本页未展开，属于拓展内容，但结论是标准的：
$ww$ 超出 CFG 的能力，需要上下文相关文法（或等价的装置）。
(d) 不是正则语言。见 §4.5 的完整证明：
在 (P1) 任意深度中心嵌套合语法、(P2) 配不平的串不合语法这两条经验前提下，
$E \cap R$ 经过同态映射得到 $\{a^nb^n\}$，而后者不是正则语言，矛盾。
注意这个结论的作用域：它是条件命题，两条前提必须一起接受才成立。
"是不是上下文无关"则是另一个问题，Pullum & Gazdar (1982) 说明这个问题开放，
Shieber (1985) 用瑞士德语交叉依赖给出了"至少有些自然语言不是 CFG"的论证。
9.9 第 9 题：把语言现象翻译成计算任务（§6、§7，综合题）
现象陈述："汉语的『把』字句（如'他把书放在桌子上'）里，
『把』后面的宾语必须是有定的（definite）。"
(a) 本页的哪些工具能检验它？哪些不能？
(b) 如果要用语料统计来检验，写出完整的方案：
需要什么数据、用什么度量、做什么零模型、结论该怎么表述。
答案
(a)
- CYK / CFG（§5）不能直接检验。因为"有定"是一个语义-语用特征，
不是句法结构特征。CYK 只能告诉你"这个串有几种结构"，
它对"书"和"这本书"之间在句法上的差别（都是 NP）无法区分。
- FST（§4.4）也不能。"有定"不是局部可判定的音变/形态规则。
- 能检验的是 §2 的搭配统计度量：把"有定"变成一个可操作的标签，
然后比较它在不同位置上的分布。这是把语言学假设变成可检验命题的标准手法。
(b) 完整方案：
- 数据：需要带句法标注的汉语语料（至少要有依存关系，
能识别出"'把'的宾语"这个位置）。规模要够，本页那种 12 句小库
只能做演示，不能做结论。 - 操作化定义：把"有定"定义成可以标注的东西，比如
"以'这/那/我/你/他'等限定词开头，或专有名词"记为有定。
必须写下来，并且报告标注一致性 $\kappa$（§6.4）。
如果两个标注者对"有定"的判断只有 $\kappa = 0.5$，
那后面所有统计都是在测噪声。 - 度量：造一个 2×2 列联表，
行 = "处于'把'后的宾语位置 / 其他宾语位置"，
列 = "有定 / 无定"。算 LLR 和 MI：
- MI 给"关联强度"（有定和'把'位置的关联有多强）；
- LLR 给"显著性"（这个关联有多可信）。
两个都要报（§2.5 的教训：LLR 不区分正负，MI 不管证据量）。 - 零模型：打乱"把"的位置。保持每个句子的词序不变，
但把"把"随机挪到句子里其他可能的位置（或者把"有定"标签随机重新分配给
句中的名词短语），重算 MI 和 LLR。如果打乱后也能得到同样高的值，
说明观察到的关联只是名词短语分布的自然结果，不是"把"字句的特殊要求。 - 结论的表述（这一条最重要）：不能说"证明了汉语'把'的宾语必须有定"。
只能说："在语料 X 上，用操作性定义 Y，观察到'把'后宾语有定的比例
显著高于其他宾语位置（LLR = …, MI = …, 零模型 p < …）。"
然后把作用域、定义、数据来源全部写清楚。
"必须"是一个语法学强度很强的断言，语料统计支持不了"必须"，
只能支持"强烈倾向"。要谈"必须"，需要的是可接受性判断实验，
那是《实验方法论核心》和《心理语言学》的地盘。
10 出处索引
本页引用到的文献（能核实到卷期页码的都给了；核不到的明确标注）：
词频分布
- Zipf, G. K. (1949). Human Behavior and the Principle of Least Effort. Addison-Wesley.
省力原则与 Zipf 定律的源头。
- Miller, G. A. (1957). Some effects of intermittent silence.
The American Journal of Psychology, 70(2), 311–314. DOI: 10.2307/1419346.
随机打字模型。原文推出的形式是 $p(w) \approx 0.11\,[r(w)+0.54]^{-1.06}$，
并明确说明"最大化假设可以换成随机间隔假设"，这是本页 §1.1 第 2 条的依据。
- Mandelbrot, B. (1953). An informational theory of the statistical structure
of language. In W. Jackson (Ed.), Communication Theory (pp. 486–502).
Butterworths, London. $f(r) = C/(r+b)^{\alpha}$ 的信息论推导。
- Heaps, H. S. (1978). Information Retrieval: Computational and Theoretical
Aspects. Academic Press. Heaps 定律。
- Clauset, A., Shalizi, C. R., & Newman, M. E. J. (2009). Power-law distributions
in empirical data. SIAM Review, 51(4), 661–703.
幂律拟合的严谨做法（极大似然 + KS 检验），本页 §1.2 的 alpha_MLE 用的是它的估计式。
Menzerath-Altmann 定律
- Menzerath, P. (1954). Die Architektonik des deutschen Wortschatzes.
Dümmler, Bonn. 定律的原始观察（德文）。
- Altmann, G. (1980). Prolegomena to Menzerath's law.
In R. Grotjahn (Ed.), Glottometrika 2 (pp. 1–10). Brockmeyer, Bochum.
三参数形式化 $y = ax^be^{-cx}$ 的出处。
- Torre, I. G., Dębowski, Ł., & Hernández-Fernández, A. (2021).
Can Menzerath's law be a criterion of complexity in communication?
PLoS ONE, 16(8), e0256133. 证明无记忆信源也能产生 MAL 形式的规律，
即"观察到 MAL"不构成语言的复杂性证据。
- Benešová, M., & Čech, R. (2015). Menzerath-Altmann law versus random model.
把 MAL 与随机模型对比的工作。具体出版信息待查。
搭配与统计度量
- Church, K. W., & Hanks, P. (1990). Word association norms, mutual information,
and lexicography. Computational Linguistics, 16(1), 22–29. MI 用于搭配。
- Dunning, T. (1993). Accurate methods for the statistics of surprise and
coincidence. Computational Linguistics, 19(1), 61–74. LLR，为批评 MI 而写。
- Evert, S. (2008). Corpora and collocations. In A. Lüdeling & M. Kytö (Eds.),
Corpus Linguistics: An International Handbook (Vol. 2, pp. 1212–1248).
Mouton de Gruyter. MI / t-score / LLR 的系统比较。页码待核。
- Rayson, P., & Garside, R. (2000). Comparing corpora using frequency profiling.
Proceedings of the ACL Workshop on Comparing Corpora, 1–6. LLR 用于语料对比。
依存距离最小化
- Hudson, R. (1995). Measuring syntactic difficulty. 未刊手稿，
通行引用即此形式，正式出版信息待查。
- Gibson, E. (1998). Linguistic complexity: Locality of syntactic dependencies.
Cognition, 68(1), 1–76. 依存局部性理论（DLT）。
- Temperley, D. (2007). Minimization of dependency length in written English.
Cognition, 105(2), 300–333.
- Liu, H. (2008). Dependency distance as a metric of language comprehension
difficulty. Journal of Cognitive Science, 9(2), 159–191.
DOI: 10.17791/jcs.2008.9.2.159. 20 种语言的依存距离测量；
"MDD 阈值 < 3 词"的假设。本页 §3.5 引用的汉语 MDD 数值属于二手转述，
未逐表核对原文，标为待核。
- Gildea, D., & Temperley, D. (2010). Do grammars minimize dependency length?
PNAS, 107(7), 2865–2870.
- Futrell, R., Mahowald, K., & Gibson, E. (2015). Large-scale evidence of
dependency length minimization in 37 languages. PNAS, 112(33), 10336–10341.
DOI: 10.1073/pnas.1502134112. 本页 §3.3 的基线设计直接照搬其
"Free Word Order Baseline"（固定依存树、随机化词序、取 100 次）
和"optimal baseline"（投射线性化下的最小依存长度）。
该文的方法论争议（Ferrer-i-Cancho 关于投射性是否应写进基线的批评）
见其对 Liu, Xu & Liang (2015) 与 Ferrer-i-Cancho & Gómez-Rodríguez (2015)
的公开回应。
形式语言与乔姆斯基层级
- Chomsky, N. (1956). Three models for the description of language.
IRE Transactions on Information Theory, 2(3), 113–124.
- Chomsky, N. (1959). On certain formal properties of grammars.
Information and Control, 2(2), 137–167. 层级的完整形式化。
- Miller, G. A., & Chomsky, N. (1963). Finitary models of language users.
In R. D. Luce, R. R. Bush, & E. Galanter (Eds.),
Handbook of Mathematical Psychology (Vol. II, pp. 419–491). Wiley.
§4.6 "语言是有限的"这条挑战的出处。
- Karlsson, F. (2007). Constraints on multiple center-embedding of clauses.
Journal of Linguistics, 43(2), 365–392. DOI: 10.1017/S0022226707004616.
真实语料里中心嵌套最大深度为 3；并明确指出
"多层中心嵌套有没有上限"是判断句法是 2 型还是 3 型的关键。
- Pullum, G. K., & Gazdar, G. (1982). Natural languages and context-free
languages. Linguistics and Philosophy, 4(4), 471–504.
DOI: 10.1007/BF00360802. 系统批评了此前所有"自然语言非上下文无关"的论证，
并把问题定性为开放。
- Shieber, S. M. (1985). Evidence against the context-freeness of natural
language. Linguistics and Philosophy, 8(3), 333–343. DOI: 10.1007/BF00630917.
瑞士德语交叉依赖。
- Kaplan, R. M., & Kay, M. (1994). Regular models of phonological rule systems.
Computational Linguistics, 20(3), 331–378. 把规则编译成 FST 的方法论源头。
- Mohri, M. (1997). Finite-state transducers in language and speech processing.
Computational Linguistics, 23(2), 269–311. FST 的语言学应用综述。
句法分析
- Younger, D. H. (1967). Recognition and parsing of context-free languages
in time $n^3$. Information and Control, 10(2), 189–208.
CYK 里"Y"的正式发表。Cocke 与 Kasami 的贡献分别以技术报告形式存在，
确切出处待查（通行引用为 Cocke 1969、Kasami 1965）。
- Earley, J. (1970). An efficient context-free parsing algorithm.
Communications of the ACM, 13(2), 94–102.
其他被本页提到但没有展开的
- Hale, J. (2001). A probabilistic Earley parser as a psycholinguistic model.
NAACL 2001. surprisal 框架的起点。
- Levy, R. (2008). Expectation-based syntactic comprehension.
Cognition, 106(3), 1126–1177. surprisal 框架的完整论述。
- Universal Dependencies（UD）：跨语言依存标注的统一规范，
是 §3 那类跨语言比较的基础设施。具体版本与主页地址随年份变动，用时自查。
11 附：本页所有代码的运行环境
# 本页全部代码块的运行环境（实际跑过的版本）
import sys, numpy, scipy
print(sys.version)
print("numpy", numpy.__version__, "| scipy", scipy.__version__)
实跑输出
3.14.7 | packaged by Anaconda, Inc. | (main, Aug 14 2026, 10:13:42) [Clang 20.1.8 ]
numpy 2.5.3 | scipy 1.18.1
- 解释器：
~/miniconda3/bin/python - 依赖：
numpy（§1-§3 的全部计算）、scipy.optimize.curve_fit（§1.2 的 Mandelbrot 拟合）。
§4.4、§4.5、§5.5 只用标准库。 - 语料：
/Users/mamingyu/Desktop/大一/专业课/教材/*.md（24 个文件，本机现成）。
换成任意.md文件都能跑，把FILES的 glob 改掉即可。 - 本页没有用到任何需要额外安装的包（无 jieba、无 nltk、无 torch）。