知识挖掘

知识挖掘：实体链接、规则挖掘与知识表示学习

小象实战讲义 · 知识图谱

上一节解决了“从文本里抽出三元组实例”，本节解决另一半问题：抽出来的指称到底对应知识库哪个实体（实体消歧与链接）、能不能从已有三元组里把隐含的规则与公理归纳出来（关联规则挖掘、路径排序），以及能不能让实体和关系自己“长出”可计算的向量（知识表示学习 TransE）。学完本节，你会拿到三套可运行的现代 Python 最小实现，覆盖协同消歧、统计模式归纳、路径排序补全与翻译模型训练。

💡 核心导读

• 实体链接分两步：指称识别与候选实体生成（mention discovery + candidate entity generation，宁可多召回）与实体消歧（定到唯一实体或 NIL）；实体引用表用百科锚文本统计给出名字模型与先验流行度。
• 消歧两条主线：生成式实体-指称模型（联合概率 + 贝叶斯后验 + 阈值），以及基于图的协同消歧（标签传播、动态 PageRank、RWR；RDF2Vec 提供实体向量）。
• 知识规则挖掘抽取的是“规则”而不是“实例”：ARM 从事务表挖频繁项集与关联规则、再把规则转换为 OWL 子类公理；SRL 的代表 PRA 把图上路径当特征，负采样 + logistic 回归做知识图谱补全。
• 知识表示学习把三元组压进低维向量：TransE 用“h 经 r 翻译到 t”建模，配 max-margin 训练；TransH/TransR 与属性关系分治修补其一对多缺陷；路径、规则、多模态与图结构上下文是后续演进方向。
• 评测两条线：三元组分类看 accuracy，链接预测看 Hits@10；PRA 可解释但稀疏低效，TransE 高效但不可解释，两类方法互补。

1. 实体消歧与链接：把指称挂到知识库节点上

1.1 从 NER 到实体链接：任务边界

命名实体识别（NER）只回答“文本里哪一段是实体、它属于哪个粗类型”：人名（PER）、国家、组织机构（ORG，如 NBA 联盟、耐克公司）。它给出的类型粒度很粗，也不告诉你这个“乔丹”和知识库里哪条记录是同一个人。实体链接（entity linking）要做的，是把文本中的实体指称（mention）关联到给定知识库中的目标实体（entity）：同样是“乔丹”，体育报道里应链接到 id=0002 的 Michael Jeffrey Jordan（篮球之神），而不是加州大学伯克利分校（UC Berkeley）的机器学习学者 Michael I. Jordan；如果知识库里两个都不是，还要能输出 NIL。

完整流程在课件里画成三步（指称识别、候选实体生成、实体消歧），实际可以并成两步：先在文本中找出可能是实体指称的片段（mention discovery/detection），并为每个指称召回候选实体；再统一做消歧。

文本 ──① 指称识别 + 候选实体生成(mention discovery + candidate generation)
         （从 mention 到实体候选的高效查找，追求覆盖率/召回，不必准）
     ──② 实体消歧──────────────────────▶ 每个 mention 定到 1 个实体，或 NIL
         （追求准确：相似度计算、图协同推理）

注意两个术语的分工：mention discovery 负责“文本里哪一段是指称”，候选实体生成（candidate entity generation）负责“这个指称在知识库里可能对应哪些实体”，课件小结把后者定义为“从 Mention 到实体候选的查找”；本课按两步并一步的讲法，把二者合在第一步，关键是“别漏掉”：围绕别名、简称、同义词、缩写构建词典查询，把一个名字可能指向的实体全部召回；消歧阶段才负责精判。下面分别看消歧的两类主流方法。

1.2 实体引用表：锚文本统计出来的名字模型与流行度

候选生成依赖的核心数据结构叫实体引用表（entity reference table）：它为每个实体维护一张名字表（names），收录该实体的所有名字串 s（全称、简称、别名、锚文本写法）以及每个名字的出现概率。百科类知识库（典型如维基百科）页面里存在大量内部链接（internal link）与锚文本（anchor text），聚合这些统计可以得到两个方向完全不同的量：

• 名字模型 $P(s\mid e)=\mathrm{count}(s,e)/\mathrm{count}(e)$：实体 e 被称作名字串 s 的比例，即“这个实体通常怎么被称呼”。比如某球队实体的锚文本里全称占 2/3、简称占 1/3；
• 实体流行度 $P(e)=\mathrm{count}(e)/N$（popularity/活跃度）：实体 e 的锚文本占全部链接的比例，即“这个实体 overall 有多常被提到”。

此外再建一张反查索引 mention→候选实体集合用于召回：“乔丹”同时指向篮球之神与学者两个实体，前者占比压倒性更高，“迈克尔·乔丹”则几乎只指向篮球之神。工程上的主要工作量是把别名、简称、同义词、缩写收全，保证召回（coverage）。

1.3 生成式实体-指称模型

第一种消歧方法是生成概率模型（entity-mention model，韩先培团队 Han & Sun, ACL 2011 的工作），对长文本、短文本（如微博）都适用。思路是先算联合概率，再用贝叶斯公式转成后验条件概率。给定名字串 s 与上下文 c，联合概率拆成两块：

$$P(s,c \mid e)=P(s \mid e)\,P(c \mid e)$$

• $P(s \mid e)$：实体 e 生成名字串 s 的概率，即实体引用表名字表中的名字出现概率（由 count(s,e)/count(e) 估计）；
• $P(c \mid e)$：实体 e 生成上下文 c 的概率，做法类比机器翻译里的翻译概率——把上下文词“翻译”到实体的语义空间，统计词与实体的共现对齐；
• $P(e)$：实体自身的先验概率，即引用表统计出的流行度 popularity。

由贝叶斯公式，$P(e \mid s,c)\propto P(s\mid e)P(c\mid e)P(e)$，对候选实体取 argmax，并且最高分必须超过预设阈值才输出，否则判定知识库中没有对应实体（NIL）。下面用合成语料给出最小可运行实现（真实人名全部换成虚构 ID，避免任何真实指向）：

# -*- coding: utf-8 -*-
"""实体引用表（名字模型 P(s|e) + 实体流行度 P(e)）+ 生成模型实体消歧（合成中性语料）。"""
import math
from collections import defaultdict

# 1) 百科内部链接 + 锚文本统计：每条 = (锚文本 s, 指向实体 e)
anchor_links = [
    # “云岚”是多义名：多数指向篮球运动员，少数指向机器学习学者
    ("云岚", "E_ATHLETE_01"), ("云岚", "E_ATHLETE_01"), ("云岚", "E_ATHLETE_01"),
    ("云岚", "E_ATHLETE_01"), ("云岚", "E_SCHOLAR_01"),
    # 球队有全称与简称两种叫法，演示名字表 P(s|e) 的分数
    ("岚峰队", "E_TEAM_LANFENG"), ("岚峰队", "E_TEAM_LANFENG"), ("岚峰", "E_TEAM_LANFENG"),
    ("长河市", "E_CITY_CHANGHE"), ("长河市", "E_CITY_CHANGHE"),
    ("滨河大学", "E_UNIV_BINHE"),
]
TOTAL = len(anchor_links)

# 实体出现总次数 -> 实体流行度先验 P(e)（popularity/活跃度）
ent_total = defaultdict(int)
# (s,e) 共现次数
se_count = defaultdict(int)
# mention -> 候选实体集合（反查索引，用于候选召回）
mention_index = defaultdict(set)
for s, e in anchor_links:
    ent_total[e] += 1
    se_count[(s, e)] += 1
    mention_index[s].add(e)

prior_e = {e: c / TOTAL for e, c in ent_total.items()}
# 名字模型 P(s|e) = count(s,e)/count(e)：实体 e 的锚文本中名字串 s 占比
name_model = {e: {} for e in ent_total}
for (s, e), c in se_count.items():
    name_model[e][s] = c / ent_total[e]

print("=== 实体引用表：实体流行度先验 P(e) ===")
for e, p in sorted(prior_e.items(), key=lambda x: -x[1]):
    print(f"  {e:<16} P(e)={p:.2f}")
print("\n=== 实体引用表：名字模型 P(s|e)（每个实体的名字表）===")
for e in sorted(name_model):
    names = ", ".join(f"P({s!r}|e)={p:.2f}" for s, p in name_model[e].items())
    print(f"  {e:<16} {names}")

# 2) 上下文模型 P(c|e)：实体描述中上下文词的出现次数（合成），拉普拉斯平滑
entity_ctx = {
    "E_ATHLETE_01": {"篮球": 5, "冠军": 4, "联赛": 4, "球队": 3, "扣篮": 2, "赛季": 3},
    "E_SCHOLAR_01": {"机器学习": 5, "教授": 4, "论文": 4, "概率图": 2, "模型": 3, "大学": 2},
    "E_CITY_CHANGHE": {"港口": 3, "人口": 2, "省会": 3, "河流": 2},
    "E_TEAM_LANFENG": {"篮球": 4, "联赛": 3, "主场": 3, "教练": 2, "赛季": 2},
    "E_UNIV_BINHE": {"大学": 4, "学院": 3, "教授": 2, "招生": 2},
}
ctx_prob = {}
for e, words in entity_ctx.items():
    total = sum(words.values()) + len(words)
    ctx_prob[e] = {w: (c + 1) / total for w, c in words.items()}

def log_context_prob(context_words, entity):
    """P(c|e)：上下文词条件独立，对数概率求和；未登录词给极小概率。"""
    p = 0.0
    floor = 1.0 / (sum(entity_ctx[entity].values()) + len(entity_ctx[entity]) + 50)
    for w in context_words:
        p += math.log(ctx_prob[entity].get(w, floor))
    return p

# 3) 生成模型：log P(s,c|e) + log P(e) = log P(s|e) + log P(c|e) + log P(e)
#    再由贝叶斯归一化为后验 P(e|s,c)，argmax + 阈值，否则 NIL
THRESHOLD = 0.30

def disambiguate(mention, context_words):
    candidates = mention_index.get(mention, set())
    if not candidates:
        return None, 0.0, {}
    scores = {}
    for e in candidates:
        p_s_e = name_model[e].get(mention, 1e-6)          # P(s|e) 名字生成
        scores[e] = math.log(p_s_e) + log_context_prob(context_words, e) + math.log(prior_e[e])
    m = max(scores.values())
    exp_s = {e: math.exp(v - m) for e, v in scores.items()}
    z = sum(exp_s.values())
    posterior = {e: v / z for e, v in exp_s.items()}
    best = max(posterior, key=posterior.get)
    return (best if posterior[best] >= THRESHOLD else None), posterior[best], posterior

docs = [
    ("云岚", ["篮球", "联赛", "冠军", "球队", "赛季"], "体育报道"),
    ("云岚", ["机器学习", "教授", "论文", "概率图", "模型"], "学术报道"),
]
print("\n=== 生成模型消歧结果 ===")
for mention, ctx, tag in docs:
    best, prob, posterior = disambiguate(mention, ctx)
    dist = ", ".join(f"{e}:{p:.2f}" for e, p in sorted(posterior.items(), key=lambda x: -x[1]))
    print(f"[{tag}] mention={mention} 上下文={ctx}")
    print(f"   后验分布 {dist}")
    print(f"   -> 链接到 {best if best else 'NIL（知识库无对应实体）'}（最佳后验 {prob:.3f}）")

运行结果：两个候选实体的名字模型 $P(s\mid e)$ 都为 1（语料里都只被写作“云岚”），此时由流行度先验与上下文翻译概率共同决定归属，体育上下文把后验全部压给运动员实体，学术上下文全部压给学者实体。

=== 实体引用表：实体流行度先验 P(e) ===
  E_ATHLETE_01     P(e)=0.36
  E_TEAM_LANFENG   P(e)=0.27
  E_CITY_CHANGHE   P(e)=0.18
  E_SCHOLAR_01     P(e)=0.09
  E_UNIV_BINHE     P(e)=0.09

=== 实体引用表：名字模型 P(s|e)（每个实体的名字表）===
  E_ATHLETE_01     P('云岚'|e)=1.00
  E_CITY_CHANGHE   P('长河市'|e)=1.00
  E_SCHOLAR_01     P('云岚'|e)=1.00
  E_TEAM_LANFENG   P('岚峰队'|e)=0.67, P('岚峰'|e)=0.33
  E_UNIV_BINHE     P('滨河大学'|e)=1.00

=== 生成模型消歧结果 ===
[体育报道] mention=云岚 上下文=['篮球', '联赛', '冠军', '球队', '赛季']
   后验分布 E_ATHLETE_01:1.00, E_SCHOLAR_01:0.00
   -> 链接到 E_ATHLETE_01（最佳后验 1.000）
[学术报道] mention=云岚 上下文=['机器学习', '教授', '论文', '概率图', '模型']
   后验分布 E_SCHOLAR_01:1.00, E_ATHLETE_01:0.00
   -> 链接到 E_SCHOLAR_01（最佳后验 1.000）

1.4 基于图的协同消歧：候选实体关联图、顶点得分与边权

单-mention 独立消歧会浪费篇章内部的互相印证。一篇 NBA 报道里同时出现 New York、底特律、NBA、迈阿密等 mention：底特律的候选是{底特律活塞队，底特律城市}，New York 的候选是{纽约尼克斯队，纽约城市}，迈阿密只有{迈阿密热火}，NBA 只有{NBA 联盟}。如果迈阿密、NBA 这两个无歧义候选已经确定是“体育语境”，它们就应该把一票邻居也拉向球队一侧——这就是协同消歧（collective disambiguation，RPI 季恒（Heng Ji）团队与韩先培团队的图方法工作）。

课件示例二构建的是候选实体关联图（实体关联图），每个顶点是一个 mention-entity 对 $V_i=\langle m_i,e_i\rangle$，由三部分组成：

1. 顶点：mention 与其候选实体组成的顶点对（注意它不是数学意义上的二分图，边连在不同 mention 的候选顶点之间）；
2. 顶点得分：$m_i$ 的目标实体是 $e_i$ 的概率，初始化规则为——候选唯一则置 1；$P(e\mid m)\ge 0.95$ 也置 1；其余顶点取 $P(e\mid m)$；
3. 边权：两个候选实体之间的语义关联度，表明两个顶点的关联紧密程度。

边权从哪里来？课件给出的是一套深度语义关系模型，训练语料仍然是维基百科——它同时拥有结构化数据（infobox、类别）、非结构化文本，以及用 internal link 把两者连起来的关联，天然适合训练语义模型。具体做法是把实体（e）、关系（r）、实体类型（et）、词（d）各自拼成 one-hot 分量再拼接：约 400 万实体、3.2 万关系、1600 个实体类型、100 万个词，合起来是 500 多万维的超大稀疏向量；先通过 hashing 与降维压到约 10 万维，再经过多层非线性映射（tanh、sigmoid 等激活函数）得到实体的低维稠密向量，两个实体间用欧氏距离即可算出语义相似度，作为边权。

1.5 标签传播、动态 PageRank 与 RWR

在这张图上做协同推理有两种经典算法。

标签传播（Label Propagation） 是半监督学习的标准图算法（朱小金（Xiaojin Zhu）的半监督学习综述（Semi-Supervised Learning Literature Survey，2005）有系统介绍）：唯一候选的 mention 视为已标注样本，歧义 mention 视为未标注样本；先构造相似度矩阵，再在矩阵上做图正则化迭代，把确定标签的影响沿边权向外扩散，直到所有顶点的标签分布稳定，歧义 mention 就“沾”到了语境一致的标签上。

动态 PageRank 是课件示例三采用的路线。示例三的关联图显式包含两类节点：实体指称节点与候选实体节点，候选实体节点的初始顶点值在该 mention 的候选内均等，之后每轮更新为上一轮的 PageRank 得分，边权是两个候选实体间的转化概率（由语义相似度归一化得到）。语义相似度是无向的，但计算时要拆成两条有向边，并按各顶点的出度归一化转移概率——注意 A→B 与 B→A 归一化后的概率并不相等（两侧出边数量不同）。收缩节奏要特别注意：课件示例三每轮只在所有未消歧 mention 中选出全局最高得分的一个候选（如先确定 New York 应链接纽约尼克斯队，就删掉纽约城市顶点及相关边），更新边权后再算下一轮，逐 mention 推进，直到每个 mention 只剩一个候选。关于在线/离线：实体之间的边权可以离线全部算好，但 PageRank 的 rank 必须在线算——好在这张图本身很小（一篇文档只有若干 mention），可设最大迭代次数，而且图每轮都在收缩、歧义越来越少，收敛很快。如果不删节点，而是把 mention→entity 的证据也放进图里，则使用带重启的随机游走（Random Walk with Restart, RWR）：mention 节点的分值由证据权重（evidence weight）预先给定，每轮迭代后 reset 回证据权重，相当于让游走者不断从证据节点重新出发。

下面用合成的体育报道语料实现动态 PageRank 协同消歧。为便于最小实现，代码把示例三的“实体指称节点”折叠进候选顶点：每个顶点直接表示为 (mention, 候选实体) 对，指称证据通过候选内均等的初值带入，PageRank 转移与逐轮单 mention 收缩流程与示例三一致：

# -*- coding: utf-8 -*-
"""基于图的协同实体消歧：动态 PageRank（课件示例三流程：候选内均等初始化、
每轮只收缩全局最高分的一个未消歧 mention，逐轮更新图）。合成语料。"""

# mention -> 候选实体列表（单候选 mention 天然已消歧）
mentions = {
    "m_岚峰": ["E_TEAM_LANFENG"],
    "m_长河": ["E_CITY_CHANGHE", "E_TEAM_CHANGHE"],
    "m_滨河": ["E_CITY_BINHE", "E_TEAM_BINHE"],
    "m_联赛": ["E_LEAGUE_CBA"],
}

# 候选实体间语义关联度（对称，0~1；真实工程由百科链接/实体向量离线训练）
sem = {
    ("E_TEAM_LANFENG", "E_TEAM_CHANGHE"): 0.85,   # 球队-球队：同联赛对手
    ("E_TEAM_LANFENG", "E_LEAGUE_CBA"): 0.95,     # 球队-所属联赛
    ("E_TEAM_CHANGHE", "E_CITY_CHANGHE"): 0.50,   # 球队-其所在城市
    ("E_TEAM_BINHE", "E_CITY_BINHE"): 0.50,
    ("E_TEAM_CHANGHE", "E_LEAGUE_CBA"): 0.95,
    ("E_TEAM_BINHE", "E_LEAGUE_CBA"): 0.95,
    ("E_TEAM_CHANGHE", "E_TEAM_BINHE"): 0.85,
    ("E_CITY_CHANGHE", "E_CITY_BINHE"): 0.15,     # 城市-城市：弱关联
    ("E_CITY_CHANGHE", "E_TEAM_BINHE"): 0.10,     # 跨类型弱关联（客场地缘）
    ("E_CITY_BINHE", "E_TEAM_CHANGHE"): 0.10,
}
def sem_w(a, b):
    return sem.get((a, b), sem.get((b, a), 0.0))

def init_scores(active):
    """示例三初始化：候选实体顶点值在该 mention 的候选内均等（单候选自然为 1）。"""
    return {(m, e): 1.0 / len(cands) for m, cands in active.items() for e in cands}

def build_edges(active):
    """存活候选之间建边：同一 mention 的候选互斥不连边；无向边存两份。"""
    nodes = [(m, e) for m, cs in active.items() for e in cs]
    adj = {v: {} for v in nodes}
    for i, (m1, e1) in enumerate(nodes):
        for (m2, e2) in nodes[i + 1:]:
            if m1 == m2:
                continue
            w = sem_w(e1, e2)
            if w > 0:
                adj[(m1, e1)][(m2, e2)] = w
                adj[(m2, e2)][(m1, e1)] = w
    return nodes, adj

def pagerank_round(active, iters=50, damping=0.85):
    """一轮 PageRank：无向边拆两条有向边，按出度归一化转移。"""
    nodes, adj = build_edges(active)
    rank = init_scores(active)
    z = sum(rank.values())
    rank = {v: r / z for v, r in rank.items()}
    base = (1 - damping) / len(nodes)
    for _ in range(iters):
        nxt = {v: base for v in nodes}
        for v in nodes:
            out = adj[v]
            wsum = sum(out.values())
            if wsum > 0:
                for u, w in out.items():
                    nxt[u] += damping * rank[v] * (w / wsum)  # 按出度归一化
            else:
                nxt[v] += damping * rank[v]                  # 悬空点自留
        rank = nxt
    return rank

# 主循环（忠实课件示例三）：每轮只在“未消歧 mention”里选出全局最高得分候选，
# 固定该 mention、删除其败选候选及关联边，再进入下一轮。
active = {m: list(cands) for m, cands in mentions.items()}
rnd = 0
while any(len(cs) > 1 for cs in active.values()):
    rnd += 1
    rank = pagerank_round(active)
    unresolved = [m for m, cs in active.items() if len(cs) > 1]
    best_m, best_e = max(
        ((m, e) for m in unresolved for e in active[m]),
        key=lambda v: rank[v],
    )
    print(f"--- 第 {rnd} 轮 PageRank（{sum(len(v) for v in active.values())} 个候选顶点）---")
    for m in active:
        tag = "" if len(active[m]) > 1 else "（已消歧）"
        line = ", ".join(f"{e}={rank[(m, e)]:.3f}" for e in active[m])
        print(f"  {m}: {line}{tag}")
    dropped = [e for e in active[best_m] if e != best_e]
    print(f"  >> 本轮固定 {best_m} -> {best_e}，删除败选候选 {dropped} 及关联边")
    active[best_m] = [best_e]

print("\n=== 协同消歧结果 ===")
for m, cands in active.items():
    print(f"  {m} -> {cands[0]}")

--- 第 1 轮 PageRank（6 个候选顶点）---
  m_岚峰: E_TEAM_LANFENG=0.165（已消歧）
  m_长河: E_CITY_CHANGHE=0.068, E_TEAM_CHANGHE=0.258
  m_滨河: E_CITY_BINHE=0.068, E_TEAM_BINHE=0.188
  m_联赛: E_LEAGUE_CBA=0.254（已消歧）
  >> 本轮固定 m_长河 -> E_TEAM_CHANGHE，删除败选候选 ['E_CITY_CHANGHE'] 及关联边
--- 第 2 轮 PageRank（5 个候选顶点）---
  m_岚峰: E_TEAM_LANFENG=0.189（已消歧）
  m_长河: E_TEAM_CHANGHE=0.296（已消歧）
  m_滨河: E_CITY_BINHE=0.039, E_TEAM_BINHE=0.189
  m_联赛: E_LEAGUE_CBA=0.287（已消歧）
  >> 本轮固定 m_滨河 -> E_TEAM_BINHE，删除败选候选 ['E_CITY_BINHE'] 及关联边

=== 协同消歧结果 ===
  m_岚峰 -> E_TEAM_LANFENG
  m_长河 -> E_TEAM_CHANGHE
  m_滨河 -> E_TEAM_BINHE
  m_联赛 -> E_LEAGUE_CBA

第 1 轮全局最高分候选是 m_长河的球队顶点（0.258 对城市 0.068），先固定它；图收缩后第 2 轮 m_滨河 的球队候选优势进一步拉大（0.189 对 0.039），再固定——先验上平分秋色的候选，被篇章里确定的“球队、联赛”证据逐轮拉了过去。

1.6 RDF2Vec：把知识库当成语料来训练实体向量

当知识库以 RDF 三元组表示时，还可以仿照 word2vec 直接训练实体向量，即 RDF2Vec 思路：在 RDF 图上抽取实体周围的子图并做随机游走，把游走经过的实体序列当作“句子”，再用 skip-gram（中心实体预测上下文窗口中的实体）或 CBOW（上下文实体预测中心实体）训练，最终每个实体得到一个低维向量；两个实体在图上的子图越相似（结构越同构），向量就越接近。实体向量既可以替代上一节的深度语义模型去算边权（相似度可用余弦或欧氏距离），也可以直接作为其他挖掘任务的特征。

1.7 实体链接小结

• 知识库形态：从百科型知识库（维基百科类，覆盖面广）发展到特定领域知识库（行业库，精度优先）；
• 链接载体：从长文本到短文本（微博），再到列表与 Web 表格；
• 候选生成：围绕同义词、简称、各种缩写做足准备，追求从 mention 到候选的高效查找，保证覆盖率（coverage）；
• 实体消歧：把多种相似度计算做细化与聚合，并用基于图的协同消歧、篇章级协同推理做全局优化，而不是孤立判每个 mention。

2. 知识规则挖掘：从实例中归纳模式与公理

2.1 抽实例与挖规则：方法谱系

前面章节的知识抽取，产出的是一条条实例三元组；知识挖掘（knowledge mining）要问的是：能不能从已有的实例里，把隐含的规则、模式也抽出来？统计模式归纳（Statistical Schema Induction）主要有三条技术路线：

• 归纳逻辑编程（Inductive Logic Programming, ILP）：使用精化算子（refinement operators）在逻辑规则空间里搜索，本课不展开；
• 统计关系学习（Statistical Relational Learning, SRL）：主要是对贝叶斯网络等概率模型做关系扩展，代表算法是路径排序算法 PRA；
• 关联规则挖掘（Association Rule Mining, ARM）：流程为①构建事务表，②挖掘频繁项集与关联规则，③把规则转换为 OWL 公理，④构建本体。

2.2 ARM：从事务表到子类公理

本体里的许多公理是可以从数据里学出来的。以子类公理为例，OWL2 公理 $C\sqsubseteq D$（C 是 D 的子类）可以对应地写成关联规则 $C\Rightarrow D$ 的形式（注意这只是为了套用关联规则挖掘而做的形式对应，并非严格的逻辑等价——关联规则是统计模式，只有置信度接近 1 时才支撑该公理）：概念 C 的实例同时也属于概念 D；规则的置信度（confidence）越高，$C\sqsubseteq D$ 成立的可能性就越大。

课件示例是一个含 6 个实例、8 个概念的小型知识库（实例为 Hancock_Tower、JFK_Airport、Newark_Airport、Robin_Williams、Jerry_Seinfeld、Chris_Rock，概念为 Animal、Black_Bird、Building、Person、Airport、Comedian、Artist、Place），灰色边表示 rdf:type（方框是实体、圆角框是概念）：Building 下挂着多个实例，Airport 下有 JFK、纽瓦克两个机场实例。第一步是构建事务表（transaction table，可参考韩家炜老师的数据挖掘教材）：每行一个实例、每列一个概念，取值 0/1。框出 airport 与 building 两列：两者同时出现 2 次，airport 单独出现也是 2 次，于是：

$$\mathrm{support}(Airport,Building)=2,\quad \mathrm{support}(Airport)=2,\quad \mathrm{confidence}(Airport\Rightarrow Building)=\frac{2}{2}=1$$

玩具数据只有两条共现，不具备统计意义；真实工程要求样本量足够大、置信度超阈值才产出公理。除子类外，属性的 domain/range、属性包含等公理也可同样转写成关联规则。下面给出从事务表到公理候选的完整实现（概念与实例全部合成，样本量放大到百级以体现统计含义）：

# -*- coding: utf-8 -*-
"""ARM 统计模式归纳：事务表 -> 频繁项集 -> support/confidence -> rdfs:subClassOf 公理。"""
from itertools import combinations

# 0) 合成知识库的 rdf:type 边：实例 -> 所属概念（可多重继承）
type_edges = {
    **{f"airport_{i:02d}": {"Airport", "Building", "Place"} for i in range(1, 31)},   # 30 个机场
    **{f"school_{i:02d}": {"School", "Building", "Place"} for i in range(1, 41)},     # 40 所学校
    **{f"park_{i:02d}": {"Park", "Place"} for i in range(1, 26)},                     # 25 个公园
    **{f"library_{i:02d}": {"Library", "Building", "Place"} for i in range(1, 21)},   # 20 个图书馆
}
N = len(type_edges)
concepts = sorted({c for cs in type_edges.values() for c in cs})

# ① 事务表：行=实例，列=概念（打印前 5 行）
print("=== 事务表（前 5 行，1=实例属于该概念）===")
print("实例".ljust(14), "".join(c[:5].ljust(9) for c in concepts))
for inst, cs in list(type_edges.items())[:5]:
    print(inst.ljust(14), "".join(("1" if c in cs else "0").ljust(9) for c in concepts))
print(f"... 共 {N} 个实例（事务），{len(concepts)} 个概念（项）\n")

# ② 频繁项集（公理归纳只需 1~2 项集），按 support 过滤
MIN_SUP = 0.15

def support(itemset):
    """support(X) = 同时拥有 X 中全部概念的实例占比。"""
    return sum(1 for cs in type_edges.values() if set(itemset) <= cs) / N

freq = {}
for k in (1, 2):
    for itemset in combinations(concepts, k):
        sup = support(itemset)
        if sup >= MIN_SUP:
            freq[itemset] = sup
print(f"=== 频繁项集（min_support={MIN_SUP}）===")
for itemset, sup in sorted(freq.items(), key=lambda x: (-x[1], x[0])):
    print(f"  {set(itemset)!s:<32} support={sup:.3f}（{round(sup*N)} 个实例）")

# ③ 在频繁 2 项集上派生规则 C=>D，confidence(C=>D)=support(C∪D)/support(C)
MIN_CONF = 0.90
print(f"\n=== 关联规则与公理转写（min_confidence={MIN_CONF}）===")
axioms = []
for itemset, sup_ab in freq.items():
    if len(itemset) != 2:
        continue
    a, b = itemset
    for c, d in ((a, b), (b, a)):                       # 两个方向都算
        conf = sup_ab / freq[(c,)]
        flag = "✅ 采纳" if conf >= MIN_CONF else "  舍弃"
        print(f"  {c:<9} => {d:<9} support(C)={freq[(c,)]:.3f} "
              f"support(C∪D)={sup_ab:.3f} confidence={conf:.3f} {flag}")
        if conf >= MIN_CONF:
            axioms.append((c, d, conf))

# ④ 规则 -> 公理：C ⊑ D 即 C rdfs:subClassOf D
print("\n=== 归纳得到的子类公理（TBox 候选，需领域专家复核）===")
for c, d, conf in axioms:
    print(f"  {c} rdfs:subClassOf {d}   （置信度 {conf:.2f}）")

=== 关联规则与公理转写（min_confidence=0.9）===
  Airport   => Building  support(C)=0.261 support(C∪D)=0.261 confidence=1.000 ✅ 采纳
  Airport   => Place     support(C)=0.261 support(C∪D)=0.261 confidence=1.000 ✅ 采纳
  Library   => Building  support(C)=0.174 support(C∪D)=0.174 confidence=1.000 ✅ 采纳
  Building  => Place     support(C)=0.783 support(C∪D)=0.783 confidence=1.000 ✅ 采纳
  School    => Building  support(C)=0.348 support(C∪D)=0.348 confidence=1.000 ✅ 采纳
  Park      => Place     support(C)=0.217 support(C∪D)=0.217 confidence=1.000 ✅ 采纳
  Place     => Building  support(C)=1.000 support(C∪D)=0.783 confidence=0.783   舍弃
  Building  => Airport   support(C)=0.783 support(C∪D)=0.261 confidence=0.333   舍弃
  ...

输出精确复现了课件示例的方向性：Airport⇒Building 置信度为 1 被采纳为公理，其反向 Building⇒Airport 只有 0.333 被舍弃（Place⇒Building 也只有 0.783，同样不过阈值）——关联规则是有方向的，子类公理同样有方向。

2.3 SRL 与 PRA：把路径当特征做知识图谱补全

统计关系学习的输入是实体集合（所有 $e_i$）、关系集合（所有 $r_k$）与一批已知三元组 $\langle e_i,r_k,e_j\rangle$（也就是一张知识图谱）；目标是对任意实体对和给定关系，估计三元组成立的概率 $P(e_i,r_k,e_j)=1$，从而预测未知三元组、完成知识图谱补全（knowledge base completion）。

基于图的 SRL 方法的基本思想是：把连接两个实体的路径作为特征，来预测它们之间可能存在的关系。课件示例中，狄更斯（Charles Dickens）写了《双城记》（A Tale of Two Cities）且职业是作家；夏洛蒂·勃朗特（Charlotte Brontë）写了《简·爱》（Jane Eyre），她的父亲帕特里克·勃朗特（Patrick Brontë）职业是作家，而“夏洛蒂职业是作家”这条边在图中缺失。知识图谱的边是有向的，为了让路径能往回走，要给每条边补一条逆关系 $r^{-1}$（如 Wrote$^{-1}$、IsA$^{-1}$），于是从夏洛蒂到作家存在路径类型 $\langle\text{HasFather},\text{Profession}\rangle$，成为推断缺失边的证据。

通用关系学习框架（generic relational learning framework）可概括为：输入一张有向边标记图 $G$、一个目标关系 $r$、一个实体对 $(s,t)$，由关系学习算法（如 PRA）输出 $r(s,t)$ 是否成立及其概率。PRA（Path Ranking Algorithm，Lao 等，EMNLP 2011）的形式化要点：

• 图 $G=(N,E,R)$，$N$ 为节点（实例或概念），$E$ 为边，$R$ 为边类型（即知识表示里的 property type），$r^{-1}$ 表示边类型 $r$ 的逆；
• 路径类型（path type）$\pi=\langle r_1,r_2,\dots,r_n\rangle$，如 $\langle\text{HasFather},\text{Profession}\rangle$，并设最大路径长度 $n$；
• 对实体对 $(s,t)$ 枚举所有从 $s$ 出发、以 $t$ 收尾、长度不超过 $n$ 的路径类型，每条路径的取值是沿该路径从 $s$ 随机游走到达 $t$ 的概率：每一步在当前边类型的出边中均匀分流，概率可递归定义（走到中间节点 $c$，再要求 $c$ 经单跳到 $t$），用动态规划从单跳概率逐层算到整条路径；
• 路径权重离线训练得到：正例取已知成立的三元组，负例通过随机替换 subject 或 object 负采样生成；以各路径概率为特征训练 logistic 回归，系数即路径权重；
• 预测时把可达路径的概率按权重加权聚合（logistic 输出概率），高分缺失边即补全进知识库。

下面的最小实现完整复现这条链路（人物、作品、职业全部为合成 ID，结构对应课件的夏洛蒂示例）：

# -*- coding: utf-8 -*-
"""PRA 路径排序算法：逆关系建图 + DP 随机游走路径概率 + 负采样 + logistic 回归补全。"""
import math
import random
from itertools import product
random.seed(42)

# 1) 知识图谱三元组（合成语料，结构对应课件夏洛蒂示例）
triples = [
    # 直接声明的作家群，合著小说以形成“同作者”路径
    ("p3", "wrote", "novel2"), ("p15", "wrote", "novel2"),
    ("p4", "wrote", "novel3"), ("p15", "wrote", "novel3"),
    ("p6", "wrote", "novel4"), ("p15", "wrote", "novel4"),
    ("p2", "wrote", "novel5"),
    ("novel2", "IsA", "Novel"), ("novel3", "IsA", "Novel"),
    ("novel4", "IsA", "Novel"), ("novel5", "IsA", "Novel"),
    ("novel1", "IsA", "Novel"),
    ("p2", "profession", "Writer"), ("p3", "profession", "Writer"),
    ("p4", "profession", "Writer"), ("p6", "profession", "Writer"),
    ("p15", "profession", "Writer"),
    # “父亲是作家、本人也是作家”的正例群
    ("p12", "hasFather", "p6"), ("p12", "profession", "Writer"),
    ("p13", "hasFather", "p3"), ("p13", "profession", "Writer"),
    ("p14", "hasFather", "p4"), ("p14", "profession", "Writer"),
    # 每位父亲再添一个未标注职业的孩子，降低“原路弹回”路径的概率
    ("p16", "hasFather", "p6"), ("p17", "hasFather", "p3"), ("p18", "hasFather", "p4"),
    # 待补全实体 p1：写了 novel1（与作家 p15 合著）、父亲 p2 是作家；无 profession 边
    ("p1", "wrote", "novel1"), ("p15", "wrote", "novel1"),
    ("p1", "hasFather", "p2"),
    # 负向人群：教师 p7 及其子 p8（合著教材）、工程师 p10 及其女 p11
    ("p7", "profession", "Teacher"),
    ("p8", "hasFather", "p7"), ("p8", "wrote", "textbook1"),
    ("p7", "wrote", "textbook1"), ("textbook1", "IsA", "Textbook"),
    ("p10", "profession", "Engineer"),
    ("p11", "hasFather", "p10"),
]
RELATIONS = sorted({r for _, r, _ in triples})
NODES = sorted({n for s, _, o in triples for n in (s, o)})

# 邻接表，并登记逆关系 r^-1（后缀 _inv）
adj = {u: {r: [] for r in RELATIONS + [r + "_inv" for r in RELATIONS]} for u in NODES}
for s, r, o in triples:
    adj[s][r].append(o)
    adj[o][r + "_inv"].append(s)
EDGE_TYPES = RELATIONS + [r + "_inv" for r in RELATIONS]

# 2) 路径类型枚举（长度 2~3，末跳为目标关系，中间跳不得使用目标关系）
MIN_LEN, MAX_LEN, TARGET_R = 2, 3, "profession"

def base_type(et):
    return et[:-4] if et.endswith("_inv") else et

def valid_path(path):
    return path[-1] == TARGET_R and all(base_type(et) != TARGET_R for et in path[:-1])

def walk_prob(s, path, t):
    """从 s 沿路径类型 path 随机游走到 t 的概率（动态规划，按出度均分）。"""
    dist = {s: 1.0}
    for r in path:
        nxt = {}
        for u, p in dist.items():
            outs = adj[u][r]
            if outs:
                share = p / len(outs)
                for v in outs:
                    nxt[v] = nxt.get(v, 0.0) + share
        dist = nxt
        if not dist:
            return 0.0
    return dist.get(t, 0.0)

candidate_paths = [p for k in range(MIN_LEN, MAX_LEN + 1)
                   for p in product(EDGE_TYPES, repeat=k) if valid_path(p)]

# 3) 训练样本（正负例数量平衡）
TARGET_T = "Writer"
pos_s = [s for s, r, o in triples if r == TARGET_R and o == TARGET_T]
train = [(s, TARGET_T, 1) for s in pos_s]
for s in ["p7", "p10", "p8", "p11"]:                 # 非作家配 Writer
    train.append((s, TARGET_T, 0))
for s, t in [("p3", "Teacher"), ("p6", "Engineer"), ("p12", "Teacher")]:  # 作家配错职业
    train.append((s, t, 0))
random.shuffle(train)

feat_paths = [p for p in candidate_paths
              if any(walk_prob(s, p, t) > 0 for s, t, _ in train)]

def featurize(s, t):
    return [walk_prob(s, p, t) for p in feat_paths]

# 4) logistic 回归（纯标准库梯度下降）
def sigmoid(z):
    return 1.0 / (1.0 + math.exp(-z))

d, w, b = len(feat_paths), [0.0] * len(feat_paths), 0.0
LR, EPOCHS = 0.5, 600
Xy = [(featurize(s, t), y) for s, t, y in train]
for _ in range(EPOCHS):
    gw, gb = [0.0] * d, 0.0
    for x, y in Xy:
        err = sigmoid(sum(wi * xi for wi, xi in zip(w, x)) + b) - y
        for i in range(d):
            gw[i] += err * x[i]
        gb += err
    scale = LR / len(Xy)
    w = [wi - scale * g for wi, g in zip(w, gw)]
    b -= scale * gb

print("=== 学到的路径权重（离线训练结果）===")
for p, wi in sorted(zip(feat_paths, w), key=lambda x: -x[1]):
    print(f"  w={wi:+.3f}  <{', '.join(p)}>")
print(f"  偏置 b={b:.3f}")

def predict(s, t=TARGET_T):
    return sigmoid(sum(wi * xi for wi, xi in zip(w, featurize(s, t))) + b)

# 5) 补全：预测缺失边 profession(p1, Writer)
print("\n=== 知识图谱补全预测（目标关系 profession，客体 Writer）===")
for s in ["p1", "p2", "p3", "p12", "p13", "p14", "p7", "p8", "p10", "p11"]:
    prob = predict(s)
    known = "（已知）" if s in pos_s else ""
    mark = "  <-- 图中缺失，PRA 预测应补全" if s == "p1" else ""
    print(f"  P(profession({s}, Writer)=1) = {prob:.3f} {known}{mark}")

=== 学到的路径权重（离线训练结果）===
  w=+6.143  <wrote, wrote_inv, profession>
  w=+5.498  <hasFather, profession>
  w=+2.749  <hasFather, hasFather_inv, profession>
  w=+2.484  <hasFather_inv, hasFather, profession>
  w=+0.880  <hasFather_inv, profession>
  偏置 b=-3.281

=== 知识图谱补全预测（目标关系 profession，客体 Writer）===
  P(profession(p1, Writer)=1) = 0.995   <-- 图中缺失，PRA 预测应补全
  P(profession(p2, Writer)=1) = 0.995 （已知）
  P(profession(p3, Writer)=1) = 0.997 （已知）
  P(profession(p12, Writer)=1) = 0.973 （已知）
  P(profession(p7, Writer)=1) = 0.036
  P(profession(p8, Writer)=1) = 0.036
  P(profession(p10, Writer)=1) = 0.036
  P(profession(p11, Writer)=1) = 0.036

待补全实体 p1 只靠 $\langle\text{hasFather},\text{profession}\rangle$ 与合著路径两条间接证据，预测概率就达到 0.995；教师、工程师一线全部在 0.04 以下。注意代码对路径类型做了两条 PRA 约束：长度从 2 起步（排除长度 1 的平凡直达路径，否则模型只会依赖已知边，对补全无意义），且只有末跳允许是目标关系（中间跳使用目标关系等于标签泄漏）。

2.4 PRA 的长处与短板

PRA 的最大优点是可解释性强：一条关系为什么成立，可以直接用命中的路径来解释，路径本身就是从数据中挖出的推理规则（如“父亲的职业往往是子女的职业”）。短板也很明确：一是路径特征提取要在图上做遍历，效率比较低；二是难以处理稀疏关系——稀有关系的路径上下文特征不足，模型得不到充分训练。这两个短板恰好是表示学习方法的强项，构成了下一节两类方法互补的背景。

3. 知识表示学习：TransE 及其扩展

3.1 从 word2vec 到知识图谱嵌入

表示学习的意义在自然语言处理里已经被 word2vec 验证：one-hot 输入层经隐藏层投影到低维向量空间，用 CBOW 或 skip-gram 训练，词就获得了稠密向量；进一步还能学句向量、文档向量（document vector，短文本可以直接视为一个句向量）。低维向量带来两个好处：建立了统一的语义空间，并且语义变得可计算，经典例子是向量类比 $\vec{king}-\vec{queen}\approx\vec{man}-\vec{woman}$。

知识图谱上的表示学习服务两类任务：

• 实体预测：给定主体 $s$ 与谓词 $p$ 预测客体 $o$，又称链接预测（link prediction）；
• 关系预测：给定两个实体，预测它们之间的谓词 $p$。

这些能力可以直接外溢到应用。例如《卧虎藏龙》的观影人群，可以关联到章子怡的粉丝、武侠片的粉丝、周润发的粉丝；要判断《阿甘正传》是不是英语片，可以沿图上路径推断成立概率。推荐系统方向的代表工作是 Zhang 等（KDD 2016，微软亚洲研究院）：把结构化 embedding、文本 embedding、视觉 embedding 聚合成推荐物料（item）的综合向量，再与用户行为画像的隐向量联合学习，做协同推荐。

3.2 TransE：把三元组看成一次翻译

TransE（Bordes 等，2013）是翻译模型（translation-based model）的开山之作。对每个三元组 $\langle h,r,t\rangle$，把头实体 $h$ 经关系 $r$ “翻译”到尾实体 $t$，在低维向量空间里希望向量和 $\boldsymbol{h}+\boldsymbol{r}$ 接近 $\boldsymbol{t}$。能量函数（energy function）衡量翻译残差，取 L1 或 L2 范数：

$$f(h,r,t)=\lVert\boldsymbol{h}+\boldsymbol{r}-\boldsymbol{t}\rVert$$

真实三元组能量应当低：$f(\text{Beijing},\text{Capital-of},\text{China})<f(\text{Shanghai},\text{Capital-of},\text{China})$；并且由 $\boldsymbol h+\boldsymbol r\approx\boldsymbol t$ 可知同一关系的“尾减头”差向量近似相等，即 China−Beijing ≈ France−Paris ≈ Capital-of（课件原页写作 Beijing−China = Pairs−France，方向与定义式相反且 Pairs 为 Paris 笔误，本讲义统一按 $\boldsymbol t-\boldsymbol h\approx\boldsymbol r$ 表述）。训练目标是 max-margin 排序损失（合页损失）：让知识库中已有三元组的能量，比负采样得到的三元组能量至少低一个间隔 $\gamma$，从而最小化整体势能：

$$\mathcal{L}=\sum_{(h,r,t)}\sum_{(h',r,t')\in\text{Neg}}\max\bigl(0,\ \gamma+f(h,r,t)-f(h',r,t')\bigr)$$

下面是纯标准库的最小 TransE（5 维向量、L2 能量、负采样、SGD，实体向量每步归一化；语料为合成城市/国家）：

# -*- coding: utf-8 -*-
"""TransE 翻译模型最小实现：max-margin 合页损失 + 负采样 + SGD（合成城市/国家语料）。"""
import random
random.seed(42)

# 1) 合成知识图谱：4 个国家，每国 1 个首都 + 2 个普通城市
countries = ["country_W", "country_X", "country_Y", "country_Z"]
capitals = {"country_W": "city_w0", "country_X": "city_x0",
            "country_Y": "city_y0", "country_Z": "city_z0"}
cities = {c: [f"city_{c[-1].lower()}{i}" for i in (0, 1, 2)] for c in countries}

triples = []
for c in countries:
    triples.append((capitals[c], "capitalOf", c))   # 一对一关系
    for city in cities[c]:
        triples.append((city, "locatedIn", c))      # 多对一关系
entities = sorted({e for h, _, t in triples for e in (h, t)})
relations = sorted({r for _, r, _ in triples})

# 2) 参数初始化
DIM, MARGIN, LR, EPOCHS = 5, 1.0, 0.05, 500

def rand_vec():
    return [random.uniform(-1, 1) / DIM for _ in range(DIM)]

ent_vec = {e: rand_vec() for e in entities}
rel_vec = {r: rand_vec() for r in relations}
triple_set = set(triples)

def normalize(v):
    n = sum(x * x for x in v) ** 0.5
    return [x / n for x in v] if n > 0 else v

def add(a, b):
    return [x + y for x, y in zip(a, b)]

def sub(a, b):
    return [x - y for x, y in zip(a, b)]

def energy(h, r, t):
    d = sub(add(ent_vec[h], rel_vec[r]), ent_vec[t])   # h + r - t
    return sum(x * x for x in d) ** 0.5                # L2 范数

def corrupt(h, r, t):
    """负采样：随机替换主体或客体，生成不在知识库中的三元组。"""
    if random.random() < 0.5:
        h2 = random.choice(entities)
        while (h2, r, t) in triple_set:
            h2 = random.choice(entities)
        return h2, r, t
    t2 = random.choice(entities)
    while (h, r, t2) in triple_set:
        t2 = random.choice(entities)
    return h, r, t2

# 3) SGD：合页损失 max(0, margin + f(pos) - f(neg))
def grad_step(pos, neg):
    hp, rp, tp = pos
    hn, rn, tn = neg
    loss = max(0.0, MARGIN + energy(*pos) - energy(*neg))
    if loss == 0.0:
        return 0.0
    def unit(d):
        n = sum(x * x for x in d) ** 0.5
        return [x / n for x in d] if n > 1e-9 else [0.0] * len(d)
    gp = unit(sub(add(ent_vec[hp], rel_vec[rp]), ent_vec[tp]))
    gn = unit(sub(add(ent_vec[hn], rel_vec[rn]), ent_vec[tn]))
    ent_vec[hp] = sub(ent_vec[hp], [LR * x for x in gp])      # 正例：压低能量
    rel_vec[rp] = sub(rel_vec[rp], [LR * x for x in gp])
    ent_vec[tp] = add(ent_vec[tp], [LR * x for x in gp])
    ent_vec[hn] = add(ent_vec[hn], [LR * x for x in gn])      # 负例：抬高能量
    rel_vec[rn] = add(rel_vec[rn], [LR * x for x in gn])
    ent_vec[tn] = sub(ent_vec[tn], [LR * x for x in gn])
    for e in (hp, tp, hn, tn):
        ent_vec[e] = normalize(ent_vec[e])
    return loss

for ep in range(1, EPOCHS + 1):
    random.shuffle(triples)
    ep_loss = sum(grad_step(tr, corrupt(*tr)) for tr in triples)
    if ep % 100 == 0:
        print(f"epoch {ep:>3}  本轮合页损失合计 {ep_loss:.3f}")

# 4) 检验一：正例能量低、负例能量高
print("\n=== 能量对比（正例应显著低于负例）===")
for h, r, t in triples[:3]:
    neg = corrupt(h, r, t)
    print(f"  正例 ({h},{r},{t}) f={energy(h,r,t):.3f} | 负例 ({neg[0]},{neg[1]},{neg[2]}) f={energy(*neg):.3f}")

# 5) 检验二：链接预测——给定 (city_x0, capitalOf, ?)，给所有国家打分排序
print("\n=== 链接预测：(city_x0, capitalOf, ?) 候选国家排序 ===")
for rank, (sc, c) in enumerate(sorted((energy("city_x0", "capitalOf", c), c) for c in countries), 1):
    print(f"  rank{rank}  {c}  能量 {sc:.3f}" + ("   <- 正确答案" if c == "country_X" else ""))

# 6) 检验三：翻译等价性 t-h ≈ r
print("\n=== 关系向量等价性：country - capital ≈ 学到的 capitalOf 向量 ===")
for c in countries:
    cap = capitals[c]
    diff = sub(ent_vec[c], ent_vec[cap])
    print(f"  {c} - {cap} = [{diff[0]:+.3f}, {diff[1]:+.3f}, ...]")
print(f"  学到的 capitalOf 向量 r = [{rel_vec['capitalOf'][0]:+.3f}, {rel_vec['capitalOf'][1]:+.3f}, ...]")

# 7) 检验四：多对一关系的正例能量普遍高于一对一关系（TransE 的缺陷信号）
print("\n=== locatedIn（多对一）正例能量普遍高于 capitalOf（一对一）===")
cap_energy = [energy(capitals[c], "capitalOf", c) for c in countries]
loc_energy = [energy(city, "locatedIn", c) for c in countries for city in cities[c]]
print(f"  capitalOf 平均能量 {sum(cap_energy)/len(cap_energy):.3f}；locatedIn 平均能量 {sum(loc_energy)/len(loc_energy):.3f}")

=== 链接预测：(city_x0, capitalOf, ?) 候选国家排序 ===
  rank1  country_X  能量 0.165   <- 正确答案
  rank2  country_Y  能量 1.299
  rank3  country_Z  能量 1.328
  rank4  country_W  能量 1.328

=== 关系向量等价性：country - capital ≈ 学到的 capitalOf 向量 ===
  country_W - city_w0 = [-0.027, +0.840, ...]
  country_X - city_x0 = [-0.006, +0.868, ...]
  country_Y - city_y0 = [-0.011, +0.900, ...]
  country_Z - city_z0 = [-0.014, +0.842, ...]
  学到的 capitalOf 向量 r = [-0.027, +0.933, ...]

=== locatedIn（多对一）正例能量普遍高于 capitalOf（一对一）===
  capitalOf 平均能量 0.114；locatedIn 平均能量 0.235

训练后链接预测把正确国家排在第 1 位，四对“国家−首都”的差向量紧紧聚成一个方向、与学到的关系向量吻合；而多对一的 locatedIn 平均能量（0.235）明显高于一对一的 capitalOf（0.114），这正是下一节缺陷的量化信号。

3.3 TransE 的缺陷与 TransH/TransR/分而治之

TransE 模型简单、参数少、效率高，却有结构性短板：它无法很好地处理一对多、多对一和多对多关系。例如“莫言—作品”同时指向《春夜雨霏霏》《透明的红萝卜》等多部作品，一个 $\boldsymbol r$ 无法把同一个 $\boldsymbol h$ 翻译到多个不同的 $\boldsymbol t$；对称关系同样学不好，如“英达—兄弟—英壮”与“英壮—兄弟—英达”，翻译模型会被迫让两个实体向量趋同。课件给出的改进路线有三步：

• TransH（Wang 等，AAAI 2014）：为每个关系定义一个超平面（hyperplane），先把头、尾实体投影到该关系的超平面上，再在超平面内做翻译，使同一实体面对不同关系时有不同投影；
• TransR（Lin 等，AAAI 2015）：通过一个关系矩阵把头、尾实体从实体空间映射到“关系感知”的语义空间，让映射后的空间里关系尽量保持一对一，从而化解一对多、多对一、多对多；
• 属性与关系分而治之（Lin、Liu、Sun，IJCAI 2016）：知识图谱里既有对象属性（object property，实体间关系），又有数据类型属性（datatype property，实体到字面量），后者天然制造多对一（如性别，许多人都指向“男/女”），把属性学习与关系学习分开建模，属性侧的结果还能反过来提升关系侧的准确性。

3.4 路径、规则、多模态与图结构上下文

PRA 与 TransE 恰好互补（课件对比表）：PRA 可解释性强、能从数据中挖出推理规则，但难处理稀疏关系、路径特征提取效率不高；TransE 能捕捉数据中的潜在特征、参数少、计算效率高，但模型简单、处理不了复杂关系、可解释性不强。把两者揉合的方向包括：

• 路径的表示学习（课件 Page 94 标注 Gardner 等，EMNLP 2013）：TransE 孤立地学习每个事实三元组，而关系之间存在复杂的关系链（如 Steven Jobs 经 bornInCity → cityInState → stateInCountry 关联到 United States）。把 $\langle h,r_1,e_1,r_2,t\rangle$ 这样的关系链视为整体，用链上各关系 embedding 的聚合做复合翻译，等价于一次多跳翻译。文献说明：Gardner 等 2013 原题是用隐式句法线索改进大知识库的学习与推理，属“路径即特征”早期工作；关系链向量复合的代表作通常引 Guu 等 2015 与 Lin 等 2015（PTransE），课件将其统一归在本标题下。
• 加入规则的表示学习（Guo 等，EMNLP 2016）：如（Paris, Capital-of, France）与（Paris, Located-in, France）之间可定义连接节点，把规则推理也纳入向量学习，使规则的似然（likelihood）最大化。
• 多模态表示学习（Xu 等，IJCAI 2017，全称 Knowledge Graph Representation with Jointly Structural and Textual Encoding）：头/尾实体的表示分两块，一块来自知识图谱结构（TransE 式翻译），一块来自实体的文本描述——论文给出三种文本编码器：神经词袋 NBOW（词向量求和）、双向 LSTM（BLSTM，正反两个方向拼接）、带词级注意力的 Attentive LSTM（按当前关系对不同词加权，可按需挑选相关词）；再用门控机制把结构表示与文本表示融合为一个联合表示。对图中出现次数少的长尾实体、甚至从未出现的实体，也能做链接预测，助力 zero-shot 与长尾场景。

  注：基于文本描述增强表示的早期路线中，Xie 等 2016 的 DKRL（Description-Embedded Knowledge Representation Learning）用的是 CNN 编码描述 + TransE，与本篇的 NBOW/BLSTM/Attentive LSTM 编码器不同，注意区分。

• 基于图结构的表示学习：描述一个实体的数据有两类——实体周围的实体（neighbor context，一跳邻居，如北京经“首都”连到中国），以及从别的实体到该实体的联通路径（path context，如家庭关系图中经两条路径到达谢霆锋）。Triple Context = Triple + Path Context + Neighbor Context：假设各类上下文相互独立、各自描述三元组的一部分，把给定上下文时三元组 $(h,r,t)$ 成立的概率函数 $f$ 按条件独立分解为头实体（neighbor context）、尾实体（path context）、关系（原始 triple 约束）三部分条件概率的乘积，对全库三元组做极大似然。实验在 FB15k 的一对多、多对一、多对多设置上表现突出；工程细节还包括先聚类（cluster）再分簇训练、按头/尾度数设计的 bern 负采样（优于均匀采样 uniform），以及用 TransE 结果做初始化再提升一轮。

3.5 评测基准、工具与趋势

评测分两条线。三元组分类：给定一个 SPO 判断对错，指标看 accuracy，常用数据集为 WN11（11 种关系）、FB13（13 种关系）；方法家族除翻译模型外还有张量分解、神经网络等，TransE 是公认的强基线。链接预测：给定 S、P 预测 O，看返回的 top-10 结果中包含正确答案的比例（Hits@10），常用基准为 WN18、FB15k（后者含 1300 余种关系，即上文 Triple Context 实验所用）。评测协议区分 raw 与 filter（Bordes 等 2013 的标准设置）：对每个测试三元组，分别用知识库中的每个实体穷举替换头实体或尾实体生成候选并按能量排名，raw 直接在全部候选上排名；filter 则在排名前剔除训练/验证/测试集中已知为真的其他候选三元组，避免“另一个本来也正确的答案”把目标答案的名次挤低，因而更公平、也更贴近知识图谱补全“在已知图谱内为缺边找位置”的评测需要，融合路径信息的翻译模型在 filter 设置下表现最好。

工具方面，清华的 OpenKE 是基于 TensorFlow 的知识表示学习框架，已被 OpenKG 收录（openkg.cn/tool/openke），TransE/TransH/TransR 等模型都有参考实现。课件最后给出四个研究趋势：融合更多本体特征的表示学习算法；表示学习与本体推理之间的等价性分析；知识图谱 embedding 与网络表示学习（network embedding）的异同与取舍；以及融合规则、本体公理等符号计算的神经符号系统。

📝 动手练一练

练习 1（手算关联规则）：给定下面这张事务表（行是实例、列是概念，1 表示实例属于该概念），请计算 support(Airport)、support(Airport, Building) 与 confidence(Airport⇒Building)，并说明反向规则 Building⇒Airport 的置信度是多少、能否据此写出 Building rdfs:subClassOf Airport。

实例          Airport Building Place
airport_01      1        1       1
airport_02      1        1       1
school_01       0        1       1
park_01         0        0       1
library_01      0        1       1

练习 2（理解 TransE 的复杂关系缺陷）：运行本节代码块 5，观察输出中 capitalOf 与 locatedIn 两类关系的平均能量差异。然后思考：如果把“性别”（多个人对应同一个值“男”）作为关系加入 TransE，$\boldsymbol h+\boldsymbol r\approx\boldsymbol t$ 会迫使这些人的向量发生什么变化？TransH 与 TransR 分别用什么机制缓解这个问题？

本章小结

本节沿着“消歧—挖规则—学表示”三条线走完了知识挖掘的主体：实体链接先用实体引用表（百科锚文本统计出的名字模型 $P(s\mid e)$、实体流行度 $P(e)$ 与 mention 反查索引）保证候选召回，再用生成式实体-指称模型（$P(s\mid e)P(c\mid e)P(e)$ 联合概率、贝叶斯后验、argmax 加阈值）或图方法做消歧；图方法上，标签传播把唯一候选当已标注样本在相似度矩阵上做图正则化扩散，动态 PageRank 按出度归一化转移、逐轮删候选直到每 mention 唯一，RWR 不删节点而每轮把 mention 证据 reset 回证据权重，RDF2Vec 则仿 word2vec 用 RDF 子图游走序列训练实体向量。规则挖掘侧，知识抽取产出实例、知识挖掘产出规则：ARM 从事务表挖频繁项集与关联规则，再按 support/confidence 把 $C\Rightarrow D$ 这类规则归纳为 $C\sqsubseteq D$ 等 OWL 子类公理；SRL 的 PRA 给边补逆关系、枚举长度受限的路径类型、用动态规划算随机游走路径概率，负采样后以路径为特征训练 logistic 回归，输出缺失三元组的概率完成补全，其可解释性强但遍历效率低、怕稀疏关系。表示学习侧，TransE 以 $\boldsymbol h+\boldsymbol r\approx\boldsymbol t$ 的翻译思想配合 L1/L2 能量函数与 max-margin 训练，成为强基线；TransH（关系超平面）、TransR（关系空间矩阵映射）、属性/关系分治依次修补一对多、多对一、多对多与对称关系缺陷；路径表示学习、规则嵌入、多模态编码、Triple Context（neighbor + path + triple）持续把图结构与外部信息融入向量；评测看三元组分类 accuracy 与链接预测 Hits@10，工程实现可参考 OpenKE。

📋 行动清单

• 找一个你熟悉的领域知识库（或用本节合成数据），为 5 个多义 mention 手工构建实体引用表，统计先验 P(e|m)，并标注哪些 mention 满足“唯一候选/先验≥0.95 直接置 1”的图初始化条件。
• 运行代码块 3（ARM）与代码块 4（PRA），各改一处数据验证边界：在事务表里加入一个“是 Airport 但不是 Building”的反例观察 confidence 下降；在 PRA 图里删掉 p1 的 hasFather 边，观察缺失边预测概率如何变化。
• 运行代码块 5（TransE），把向量维度 DIM 从 5 改成 2 和 20 各训一次，记录链接预测 rank1 能量与两类关系平均能量的变化，直观体会维度对复杂关系建模的影响。

—— 小象教研组