小组作业：从稀疏、有噪的成对比较中恢复关系结构

形式：4–5 人小组 ｜ 周期：4 周 ｜ 建议投入：每人每周 6–8 小时

提交物（一份 zip + 一个仓库链接）

1. 技术报告（英文 LaTeX，正文 ≥ 8 页，不含参考文献）
2. 代码仓库（含 README 与一键复现脚本，他人可完整重跑全部图表）
3. 结果数据（严格按第 8 节的格式）
4. 15 分钟英文口头汇报（录像）

分工要求：报告首页给出 CRediT 格式贡献声明，每位成员至少主责一个模块。全组同分，贡献声明与答辩表现不一致者单独调分。

**⚠️ 报告须含一节「模块间一致性检查」（占报告分的 1/3）。**本作业的六个模块不是六份独立作业，它们相互咬合：

四条至少答三条。若某条检查的结果互相矛盾，如实写出矛盾并分析原因——发现并说清一处矛盾，比四条都"一致"更能拿分。这一节也是答辩必问的部分：如果四个人各做各的、从不对话，这一节写不出来。

0. 这份作业问的是一个问题

只学过相邻关系 A>B、B>C、C>D，人和动物却能判断从未学过的 A>D[1]。一个直觉的解释是联想强度（flat associative）：反复配对让 A 带上高分、D 带上低分，比较分数即可。另一类解释认为大脑构建了一张关系图，推理是在图上找路径[2,3]；这一视角把空间编码视为人类思维的通用底层[10]，并已有形式化的实现——把关系表示成「从此处出发会到达何处」的预测性结构[9]。海马–内嗅系统不仅编码物理空间[4]，也以同样方式组织抽象关系与社会关系[5,6,7,8]。

这两类模型在观测充分时都能答对，因此区分它们的地方在观测不充分处。本作业只问一个问题：

观测要多稀疏、多脏，一张关系图才推不动了？一维序和二维支配的门槛，是同一条吗？

这个问题看起来是工程问题，其实是理论问题：如果两种推理的可行域边界不同，那它们就不可能由同一个瓶颈决定；如果边界重合，则"二维更难"只是"二维平均距离更短"造成的假象。目前没有人系统地量过这条边界。

四个人的建议分工（4 人组可合并 C、F）：

**模块 D 是本作业的主线，其余模块都是为它服务的工具或对照。**如果时间不够，优先保证 A + D 的完整性。

1. 通用协议（所有模块共用，不得更改）

1. 真值结构：N 个个体，随机打乱得到一个真实全序；二维情形为两个正交的序（即每个个体有一对秩 (x, y)）。真值只用于评分，不得喂给模型。
2. 观测（前提）：从全部 C(N,2) 个配对中以概率 p 独立采样。被采样到的配对给出一条有向边"i > j"。
3. 噪声：每条被观测的边以概率 ε 方向反转。ε 是边错误率，不是试次错误率。
4. 提问：在未被观测的配对（held-out）上提问。二维情形只在可比配对（一项在两维上都不低于另一项且至少一维更高）上统计支配判断准确率。
5. 重复与种子——这是两件不同的事，两件都要做：
   • 重复（repetition）：在一个种子内，每个数据点 ≥ 200 次重新抽真值 + 重新抽观测；
   • 种子（seed）：整条流水线用 ≥ 3 个独立随机种子各跑一遍（建议 42 / 43 / 44）。 最终报告的形式是 mean ± s.d. over seeds，其中每个 seed 的值本身已是 200 次重复的均值。
6. 禁止调用现成的传递闭包库，闭包需自己实现（三重循环或 Floyd–Warshall 皆可）。

⚠️ 二维的组合方式必须写清楚：你是先对每一维各取闭包再组合，还是先组合再取闭包？两者不等价，结论也不同。报告中须明确说明并给出理由。

1.1 种子、报告与复现（全局硬性要求，适用于每一个模块）

这三条是本作业的红线，任何一条不满足，相关模块直接计 0 分。

(a) 每一个数字都必须来自 ≥ 3 个独立种子。

• 没有例外。不要因为"这个结果是确定性的"就只跑一次——确定性的算法不等于确定性的结果：真值次序是随机抽的，观测掩码是随机抽的，噪声是随机加的，网络初始化是随机的。只要流水线里还有一处随机，就必须多种子。
• 唯一豁免的是解析结果（模块 A.4 的闭式表达式）。豁免的部分请在报告中明确标注为 analytic。
• 种子必须显式设置并记录：random、numpy、torch（含 torch.manual_seed）、以及环境变量 PYTHONHASHSEED。种子作为命令行参数暴露出来，使任何一次运行都能被单独重放。

(b) 报告所有结果，不是最好的结果。

• 每张图、每个表格单元都写成 mean ± s.d.（n = 种子数），并在附录中逐种子列出原始数值。
• 禁止只报告"表现最好的那个种子/维度/超参"。若某个种子的行为与其他种子明显不同，把它写出来并讨论——这通常是最有价值的观察，不是需要藏起来的瑕疵。
• 若某项实验跑失败了、或没跑完，在报告中明确写出来，并说明缺口在哪。留白不扣分，掩盖要扣分。

(c) 每一个数字都必须可追溯到代码。

• 仓库中须有 README，说明从零开始如何复现每一张图、每一个表——具体到"运行哪个脚本、带什么参数、产出哪个文件"。
• 每个结果文件（.json / .csv）中须记录产生它的种子、参数、脚本名与 git commit。
• 报告中每张图的题注须注明它由哪个脚本、哪个数据文件生成。
• **助教会随机抽取至少两个结果重跑。**重跑不出来（或与提交值不一致，超出浮点末位差异）的，该模块计 0 分。

这三条看起来繁琐，但它们正是把"我跑出来了"变成"这个结果成立"的全部区别。本作业的很多结论是否定性的（某个方法不行、某条边界不存在），而否定性结论对上述要求最敏感——一个没记种子、没法重跑的否定结果，等于没有结果。

1.2 数据从哪来、需要装什么

模块 A、B、C、D、F 不使用任何外部数据集。全部数据由你按 §1 的协议自行生成——每一次"实验"就是：抽一个真值次序 → 按 p 抽观测 → 按 ε 加噪 → 在 held-out 上提问。不要去找现成的传递推理数据集，本作业不需要，也没有公认可用的。

这样设计不是图省事，有三条实在的理由：

1. **只有真值已知，准确率才有定义。**在真实数据上你根本不知道"正确答案"是什么，就无从判断闭包补出的关系对不对。
2. **只有能自由拧 N、p、ε 三个旋钮，模块 D 的相图才画得出来。**相图的横纵轴就是这些旋钮，外部数据集把它们钉死了。
3. **可复现。**数据由种子完全决定，助教重跑你的脚本能得到逐位相同的结果——这正是 §1.1(c) 要求的。

唯一用到外部数据的是模块 E（预训练词向量），下载与规格见 E.1。

环境：Python 3.9+、NumPy、Matplotlib、PyTorch（仅模块 B 需要，CPU 版即可）。不需要 GPU——所有实验在笔记本上可完成，模块 D 的机时开销来自格点数量而非单次计算（见第 10 节的估算与并行化建议）。仓库的 README 中请写明你实际使用的版本号。

2. 模块 A：基线模型与三条行为签名（15 分）

A.1（3 分）两个 agent

def flat_agent(observed_pairs, query):
    """查表：只对观测过的配对作答，其余随机猜。"""

def map_agent(observed_pairs, query):
    """关系图：先对观测边取传递闭包，再回答查询；仍不可推者随机猜。"""

A.2（4 分）符号距离效应

N = 7，p ∈ {0.2, 0.35, 0.5}，按秩距离 1…6 分组统计 held-out 准确率，两个 agent 各一条线，含误差棒。

报告要求：关系图 agent 是否出现准确率随距离上升？查表 agent 呢？给出机制解释，并说明这一效应为什么不能由联想强度产生。

A.3（4 分）端点锚定效应（end-anchor）

统计含端点（最高或最低项）的配对 vs 纯中间配对的准确率，画"准确率 vs 序位"曲线，检验是否呈两端高、中间低的弓形。

报告要求：解释弓形如何从闭包中自然出现（提示：端点参与了多少条可推链？）。并回答——若把结构从全序换成环（首尾相接），弓形还在吗？先给预测，再跑。

A.4（4 分）解析部分

对一维、无噪（ε = 0）情形，推导 held-out 配对（即该对本身未被观测）被闭包解出的概率 P_resolve(d; N, p)，其中 d 为两者的秩距离。

这一题有精确解，不要一上来就写模拟。

按以下顺序做，每一步都比上一步难一点：

1. 先想清楚谁能当中间站。闭包里的路径必须沿真值次序单调，所以能把 i 和 j 接起来的点，秩必须严格介于两者之间。请先回答：这样的点有几个？
2. **d = 1 的精确值。**由上一步直接得出，写出来并说明理由。
3. **一般 d 的精确表达式。**顺着"可达集逐个吸收中间点"的思路，写出一个可计算的递推（提示：新中间点能否被接上，只取决于当前已可达的点数）。这不是近似，是精确解。
4. **一个可以被证伪的推论。**你的表达式里出现 N 了吗？据此预测 P_resolve(d; N, p) 与 N 的关系，然后用 N = 7、12、20 的模拟去检验这条预测。先写预测，再跑。
5. 把理论曲线与模拟画在同一张图上，报告最大偏差，并说明该偏差是否在蒙特卡洛误差范围内。

若第 3 步实在做不出，可以给上下界并说明界在何处松，但必须完成第 4 步的预测–检验。 这一小题是模块 D 的理论锚点，D.3 会直接用到它的结论。

3. 模块 B：神经网络的可学习性边界（20 分）

前两个 agent 是符号模型。一个自然的问题是：一个从数据里学的连续模型，会不会自己长出同样的能力？

用 nn.Embedding（每个个体一个可学习向量）+ 两层 MLP（输入为两个个体向量的拼接），在观测到的边上以交叉熵训练，在 held-out 配对上测试。

B.1（5 分）一维

N = 7，相邻采样（只给 N−1 条相邻边）。画准确率 vs 秩距离。

• 网络是否自发出现符号距离效应？与 A.2 的闭包曲线对比。
• 把学到的嵌入向量降到 1 维可视化：它排成一条线吗？该一维投影与真实秩的相关有多高？
• ≥ 20 个随机结构 × ≥ 3 个种子，报告 mean ± s.d.（跨种子），并在附录逐种子列出。

B.2（8 分）二维与"不可比"

4×4 网格，三分类：a 支配 b / b 支配 a / 不可比。

关键设定：训练集只含单轴相邻对——因而训练集里一条"不可比"样本都没有。测试集包含全部 held-out 配对，其中相当一部分是不可比的。

• 嵌入维度取 1、2、4、8、32，每个维度 ≥ 6 个随机种子（此处种子数高于全局下限 3，因为网络初始化的方差更大）；
• 分别报告可比配对与不可比配对的判别准确率（不要只报总体准确率，它会掩盖问题）；
• 画出准确率 vs 嵌入维度。

B.3（7 分）诊断

若网络在"不可比"上失败，请判断失败来源属于以下哪一类，并给出能相互分离的对照实验：

至少必须做的对照：把"不可比"样本按比例 r 加入训练集，r 从 0 扫到 0.5，看准确率怎么动。

报告要求：只写"可能是因为……“不得分。必须给出每种解释各自预测什么、你的数据支持哪一个、又排除了哪一个。若你认为 (d) 成立，请把它写成一个关于表示的命题并给出论证——注意任意两个实数必有大小。

B.4（与模块 D 的接口，不单独计分，但缺失则 D 扣 5 分）

把训练好的网络当作第三个 agent，放到模块 D 相图的至少 6 个格点上评测（建议沿 p 与 ε 各取一条线），与 flat / 关系图两个 agent 画在同一张图里。

必答：网络的可行域边界落在另外两个 agent 的哪一侧？ 它更像查表，更像闭包，还是两者都不像？在噪声大的格点上，它是退化成"猜”，还是自信地答错？——这两种失败方式的后果完全不同。

4. 模块 C：固定观测预算下的分配问题（15 分）

现实中每一次比较都有成本（一场比赛、一次试验、一次标注）。给定总预算 B 次比较，你可以：

• 覆盖 B 个不同配对，每对只看 1 次（密但脏）；
• 或覆盖 B/k 个配对，每对看 k 次取多数（稀但干净）。

C.1（8 分）最优 k

固定 B，扫 k ∈ {1, 2, 3, 5, 7, 9}，在 ε ∈ {0.05, 0.1, 0.2, 0.3} 下分别找出使 held-out 准确率最高的 k*。

注意约束：覆盖的配对数 ⌊B/k⌋ 不能超过 C(N,2)。请选一个使 k = 1 时不会覆盖满全部配对的 B（否则 k = 1 那一档没有意义），并在报告中写明你取的 B 与对应的覆盖率。

• 画 “准确率 vs k”，每个 ε 一条线；
• 给出 k*(ε) 的关系，并解释它的形状。

C.2（4 分）它依赖什么

k* 随 N 变化吗？随 B/C(N,2) 的比值变化吗？至少扫两个 N。

C.3（3 分）一维 vs 二维

同一预算下，一维与二维的 k* 相同吗？ 若不同，方向是什么，为什么？

报告要求：给出一条可直接用于实验设计的建议——“在边错误率约为 ε 时，预算应当这样花”。 这条建议必须在模块 D 的相图上被检验：按你的建议分配预算，落点应当在可行域内；按等预算的 k = 1 分配，落点在哪？把两个落点标在 D.1 的图上。建议与检验不一致时，如实报告并分析原因——这比给一条没验过的建议有价值得多。

5. 模块 D：相图 —— 一维与二维的可行域（25 分）

本模块是主线。

D.1（8 分）扫描

对一维和二维分别扫描：

• 个体数 N：一维取 {9, 12, 16, 25, 36, 49}；二维取对应的矩形网格 3×3、3×4、4×4、5×5、6×6、7×7， 使两种结构在同一 N 下逐点可比（这是 D.2 能做比较的前提，不要各扫各的）
• 观测密度 p ∈ {0.2, 0.3, 0.4, 0.6, 0.8}
• 边错误率 ε ∈ {0, 0.1, 0.2, 0.3}

每个格点报告两个 agent 在 held-out 上的准确率：≥ 3 个种子 × 每种子 ≥ 200 次重复，报告跨种子的 mean ± s.d.

输出：每个 ε 一张 (N, p) 热力图，画 map 减 flat 的优势；在图上标出优势 = 5 个百分点的等值线（这条线就是"可行域边界”）。

必答：在固定 (p, ε) 下，优势随 N 单调吗？若不单调，峰值在哪、之后为什么会掉？把"更多个体"与"更多错边"这两个相反的作用分别量化，说明是哪一个在何处占上风。

D.2（6 分）两条边界是同一条吗

把一维与二维的等值线画在同一张图上。

• 在同一 (p, ε) 下，二维需要多少个体才能达到一维在 N = 12 时的优势水平？给出比值，并给出它随 ε 的变化。
• 若二维的边界系统性地更靠右（需要更多个体），请给出这个差距的来源。至少考虑三种候选：(i) 可比配对本身更少；(ii) 组合步骤额外损失了信息；(iii) 组合步骤的 AND 结构改变了出错的方式（把"答错"变成"答不出"）。设计能把这三者分开的对照，不要只做两分类。
• 若两条边界重合，那么"二维更难"的说法就需要重新表述——请给出你认为正确的表述。

D.3（6 分）有没有一个控制变量

定义可解对比例 R = 闭包能补出的 held-out 配对占全部 held-out 配对的比例（这是一个可以直接测量的量，不依赖准确率）。

关键检验：把 D.1 中所有格点的准确率对 R 作图。

• 不同的 (N, p, ε) 组合是否塌缩到同一条曲线上？
• 与 A.4 对照：把 A.4 的解析式按你的秩距离分布加权，算出 ε = 0 时 R 的理论值，与 D.1 实测的 R 比较。两者一致吗？若一致，那么相图在 ε = 0 这一层是可以预测的，不必扫；请说明这对 ε > 0 的那几层意味着什么。
• 若塌缩：你就找到了控制这件事的单一变量，请给出这条曲线的形式，并说明它对一维、二维是否是同一条。
• 若不塌缩：残差里还有什么？ 请找出至少一个额外的控制变量，并证明加上它之后塌缩变好（给出定量的拟合优度对比，不要只看图）。

这一小题是整份作业里最难、也最有价值的一题。允许得出否定结论——“不存在这样的单一变量”，只要证据扎实，同样满分。

D.4（5 分）噪声的结构，还是噪声的大小？

前面把噪声当作 iid：每条边以相同概率 ε 反转。但真实的成对观测通常不是这样——两个实力接近的个体比一次，结果接近抛硬币；实力悬殊的两个，几乎不会爆冷。也就是说，错误率依赖于两者的秩距离。

请实现第二种噪声模型：

P(反转 | 秩距离 d) = f(d)，且 f 单调递减，例如 f(d) = 0.5 * exp(-d / λ)

这里有一个陷阱，请务必想清楚再动手。“把两种噪声模型调成可比"有两种做法，它们不等价：

• 对齐噪声函数：一维和二维用同一个 f(d)（即同一套"实力差 → 胜负概率"的规律）；
• 对齐实测错误率：分别调 λ，使两种结构实际产生的边错误率相同。

两种对齐必须都做，并分别报告。 然后回答：

• 在对齐噪声函数时，一维与二维实测的边错误率相同吗？若不同，差多少、为什么？ （提示：把 N 个个体摆成二维网格后，每个轴上还剩几个等级？这些等级之间的秩距离典型是多大？）
• 在对齐实测错误率时，两种噪声模型的可行域边界还有差别吗？
• 综合两者：“二维更难"这件事，多大程度上来自结构本身，多大程度上来自二维改变了观测的噪声水平？ 这是本小题的核心结论，请用数字回答。

哪一种对齐才是"公平"的，取决于你要回答什么问题——请在报告中明确说明你的立场并给出理由。选错对齐方式会让你看不见真正的效应，这一点本身就是考点。

**这一小题可能会推翻 D.2 的结论。**如果发生这种情况，请在报告中明确写出来，并说明 D.2 的结论应当被限制在什么条件下——这比把两节结论强行调和更有价值。

6. 模块 E：真实概念空间上的复核（15 分）

前面全部用合成结构。合成结构的风险是：它可能比真实结构更好推（真值是随机全序，链条干净）。本模块检验结论在真实语义结构上是否还成立。

E.1（6 分）构建

数据来源（照此执行，以便跨组可比）：使用公开的 GloVe 6B / 300 维词向量，官方下载地址 https://nlp.stanford.edu/data/glove.6B.zip（约 820 MB，解压后取 glove.6B.300d.txt）。若下载不便，也可用 gensim.downloader.load("glove-wiki-gigaword-300") 获得同一份向量；用其他公开词向量亦可，但必须在报告中写明具体是哪一份。

规格：取 4 个语义类别（如 动物 / 工具 / 食物 / 交通工具），每类 9 个词，共 N = 36 个节点。选 36 正是为了对上模块 D 的 N = 36 那一列，E.3 可以直接比，不必补跑。词表请写进代码或单独一个文件并提交，不要只在报告里罗列。

复现提示：不要把 820 MB 的原始文件提交到仓库。写一个脚本，从原始文件中抽出你那 36 个词的向量存成一个小文件（几十 KB）并提交，同时在 README 里写明原始文件的来源与抽取脚本。这样助教无需下载 820 MB 也能重跑。

节点为词，边权为余弦相似度。在这个图上定义一个有序结构（例如沿某个语义方向的投影给出秩），并按 §1 的通用协议采样观测、加噪、推断。

报告要求：说明你如何定义秩、为什么这个定义是合理的、以及它对结论的敏感性（换一个定义，结论变吗？）。

E.2（6 分）碎片化

真实语义空间是高度连通的：即使不加任何额外结构，度量本身就能跨类别到达。因此闭包的优势可能在真实空间上被稀释。

以概率 q 删除跨类别的边，把 q 从 0 扫到 1，量化"闭包相对查表的优势"随 q 的变化。

报告要求：优势是随 q 单调上升吗？如果是，说明了什么？如果不是，转折在哪、为什么？

E.3（3 分）与合成结构对照

把 E.2 的曲线与模块 D 中同等 (N, p, ε) 的合成结果画在一起。注意先对齐 N：E.1 取了多少个词，就用 D 相图上同样 N 的那一列作对照；若词数不在 D 的 N 网格上，请补跑该 N 的合成格点，不要拿相邻的 N 硬比。

真实结构比合成结构更好推还是更难推？ 给出定量比较，并解释差异来源。

7. 模块 F：产出可证伪的人类预测（10 分）

前六个模块全是模型。本模块要求你把模型变成可以被人类数据推翻的东西。本模块不收集任何人类数据。

产出一张预测表，每行一条预测，含以下列：

至少 5 行，且其中至少 2 行必须是两个模型预测方向相反的（同向但幅度不同的预测区分力弱，只能算半行）。

加分（+3）：给出一条预测，是两个模型都无法解释的现象——即你认为人类会做出的、但你的任何模型都预测不出的行为。说明你的理由。

8. 结果汇交格式（不合格则模块 D 不计分）

所有小组的模块 D 结果将汇总比较，格式必须一致。提交 UTF-8 编码的 phase_diagram.csv：

代码仓库中须有一个脚本，从零重跑即可生成这张表，且与提交的表逐行一致（允许浮点末位差异）。助教会抽查复现。

9. 评分标准

扣分项：任一数字少于 3 个种子（该模块 0 分）；只报告最好的种子而不报全部（该模块 0 分）；图无坐标轴标签或图例（−3/图）；结论与自己的数据矛盾（−10）；未说明二维的组合次序（−5）；代码无法一键复现（该模块 0 分）；汇交表与重跑结果不一致（模块 D 0 分）。

关于否定结论：模块 B.3、D.2、D.3、D.4 与 E.2 允许并鼓励得出否定结论。“我做了，它不成立”，只要证据扎实（重复次数、误差棒、排除了平凡解释），与肯定结论同分。把不成立的结果修饰成成立的，按学术不端处理。

学术诚信：允许使用 AI 工具，但须在报告末尾说明用于哪一步、以及你如何核验其输出；未说明而被发现按学术不端处理。

10. 时间表（建议）

先估机时再动手。模块 D 是 6（N）× 5（p）× 4（ε）× 2（结构）= 240 个格点，每格 ≥ 3 个种子 × ≥ 200 次重复，即 ≥ 144,000 次单次运行；D.4 的两种对齐各需再来一套。请在第 1 周就测出单次运行耗时、乘出总量、并做并行化（multiprocessing 或作业数组均可），不要等到第 3 周才发现跑不完。

提示：闭包用布尔矩阵运算实现，比三重 Python 循环快两到三个数量级——这一步做不做，直接决定这个模块能不能完成。

参考文献

[1] Bryant, P. E., & Trabasso, T. (1971). Transitive inferences and memory in young children. Nature, 232(5311), 456–458.

[2] Tolman, E. C. (1948). Cognitive maps in rats and men. Psychological Review, 55(4), 189–208.

[3] Behrens, T. E. J., Muller, T. H., Whittington, J. C. R., Mark, S., Baram, A. B., Stachenfeld, K. L., & Kurth-Nelson, Z. (2018). What is a cognitive map? Organizing knowledge for flexible behavior. Neuron, 100(2), 490–509.

[4] O’Keefe, J., & Dostrovsky, J. (1971). The hippocampus as a spatial map: preliminary evidence from unit activity in the freely-moving rat. Brain Research, 34(1), 171–175.

[5] Constantinescu, A. O., O’Reilly, J. X., & Behrens, T. E. J. (2016). Organizing conceptual knowledge in humans with a gridlike code. Science, 352(6292), 1464–1468.

[6] Garvert, M. M., Dolan, R. J., & Behrens, T. E. J. (2017). A map of abstract relational knowledge in the human hippocampal–entorhinal cortex. eLife, 6, e17086.

[7] Park, S. A., Miller, D. S., Nili, H., Ranganath, C., & Boorman, E. D. (2021). Inferences on a multidimensional social hierarchy use a grid-like code. Nature Neuroscience, 24(9), 1292–1301.

[8] Kumaran, D., Banino, A., Blundell, C., Hassabis, D., & Dayan, P. (2016). Computations underlying social hierarchy learning: distinct neural mechanisms for updating and representing self-relevant information. Neuron, 92(5), 1135–1147.

[9] Stachenfeld, K. L., Botvinick, M. M., & Gershman, S. J. (2017). The hippocampus as a predictive map. Nature Neuroscience, 20(11), 1643–1653.

[10] Bellmund, J. L. S., Gärdenfors, P., Moser, E. I., & Doeller, C. F. (2018). Navigating cognition: spatial codes for human thinking. Science, 362(6415), eaat6766.