06 / 树表示学习经典算法：RNTN / Tree-LSTM / TBCNN / ASTNN

01RNTN2013

EMNLP 2013 · Socher, Perelygin, Wu, Chuang, Manning, Ng, Potts

让两个孩子的每一维，两两相乘

RNTN 的树表示学习过程 —— 只看「一棵句法树怎么被递归地合成一个向量」

递归网络的组合函数通常是 h = tanh(W[h_l;h_r] + b)：加权、求和、弯曲。 RNTN 在它前面多加了一项 uᵀVu（u = 左右孩子拼起来的 2d 维向量，V 是 2d×2d×d 的三阶张量）。这一项把任意两个输入维度两两相乘，于是「not × good」「very × 好」这类乘性修饰第一次能被表达。其余部分没变：叶子是词向量，自底向上，根的 h 就是整句的表示。

1.1

为什么"加权求和"不够用

RNTN 存在的唯一理由

假设已经有两个孩子的向量 h_l、h_r。要合成父亲，最直接的做法是拼起来做一次线性变换。问题在于：线性变换只会"按比例混合"，不会"让一个词改变另一个词的作用方式"。

1

线性组合

只能加，不能"翻转"

h = tanh(W[h_l;h_r] + b)。对「not good」，它能学到的是"not 的向量 + good 的向量指向某个方向"，但学不到"not 把 good 的极性反号"——那是一个条件性的、乘性的效果。

2

乘性交互

交叉项才表达"修饰"

就像多项式回归里的 x_i·x_j。张量项 uᵀVu 把 2d 维里所有 (i, j) 组合都乘一遍，权重由 V 学出来：某一维活跃时，另一维的贡献可以被放大、压低甚至反号。

3

代价

参数涨一个量级

V 有 (2d)²·d = 4d³ 个参数。d=25 时约 6.2 万，而线性项 W 只有 2d² ≈ 1250。这是 RNTN 比普通递归网络强、也更容易过拟合的直接原因。

论文里的三类典型错误正好对应这一点：否定正向（not good）、否定负向（not bad）、「X 但是 Y」（前负后正时整体为正）。它们都不是"把两个向量加权平均"能解决的，而都需要一个词改变另一个词的作用。

1.2

树从哪来，叶子是什么

和普通递归网络一样的前半段

1

结构

二叉成分树

用成分句法分析器得到二叉树（论文里是二值化的 PTB 树）。每个内部节点就是一个待合成的短语。

2

输入

叶子 = 词向量

只有叶子有输入，就是词向量（论文用 d=25）。内部节点没有自己的 token，它的向量完全由孩子合成出来。

3

顺序

后序遍历，自底向上

孩子全算完父亲才能算。每个内部节点的 h 都是它那棵子树的表示；算到根，根的 h 就是整句的表示。

1.3

主舞台：一个节点内部到底在算什么

4×4 张量切片 · 真实数值

为了把张量看清楚，这里用 d = 2：每个孩子的向量只有 2 维，拼起来 u 是 4 维，于是每个输出维度对应一个 4×4 的矩阵（张量的一个切片）。点「播放」看向量自底向上流动；也可以直接点任意节点，单独看它的张量运算。

the movie was not good

二叉成分树 · 9 个节点 · 点节点可单独查看

速度

1.4

公式：只多了一项

把 03 节的动画翻译成式子

组合函数论文式 (3)

(3)

h = tanh( u^T V u + W u + b ), u = [ h_l ; h_r ]

先算二次型，再加线性项，最后 tanh。注意两项都作用在同一个 u 上，不是两个分支

逐维

h_k = tanh( Σ_i,j u_i V_k,i,j u_j + Σ_i W_k,i u_i + b_k )

V 的第 k 个切片是一个 2d×2d 矩阵，每个输出维度都有自己的一个切片

V ∈ ℝ^2d×2d×d、W ∈ ℝ^d×2d、b ∈ ℝ^d。u^TVu 是一个标量：把 u 的所有维度两两相乘，权重就是 V 里对应的那个数。

退化与对照同一套记号下看差别

(2)

h = tanh( W u + b )

普通递归网络：去掉张量项。表达能力只到"加权混合 + 弯曲"

(1)

p = softmax( W^s h )

每个节点都接一个分类器（论文里是 5 档情感）。监督信号遍布全树，每个短语的 h 都被要求"可分类"

这一点对"树怎么被嵌入"很关键：不只是根有监督，所有中间节点都有标签，所以中间层的 h 不会退化成只为根服务的中间量。

1.5

张量到底学到了什么

示意图，非论文原图

把 V 的某个切片画成矩阵，行和列都是 u 的维度（前半是左孩子，后半是右孩子）。两个交叉块就是「左孩子的某一维 × 右孩子的某一维」——乘性交互全在这里。

行 = u 的维度，列 = u 的维度。左上块是「左 × 左」，右下块是「右 × 右」，中间两块才是「左 × 右」的交互项。

在这页的随机权重下也能看到一点影子：good 的第一维是 +0.80，与 not 合成后 ADJP 的第一维变成 −0.42 —— 张量项确实让这一维反了号。这当然只是随机初始化，不能当语言学结论；但一个训练过的 V 会把这种交互放大成真正的「否定翻转」。

否定

not × good

V 可以在「否定词那一维」与「正向情感那一维」之间学到一个大负值：当 not 活跃时，good 的贡献被反号。

程度

very × 好

同理，程度副词与形容词之间学到一个放大系数：不是加一点，而是把对方的强度乘上去。

转折

X but Y

「but」让后半段的权重压过前半段。这也是线性组合最难学的一种：它需要根据一侧的内容去调节另一侧。

1.6

要点、误解，和它的性质

01

只有组合函数变了。树结构、叶子向量、自底向上的顺序、根即表示 —— 这些和普通递归网络完全一样，唯一的增量是 uᵀVu。

02

张量不是"多层"，而是"双线性"。它不增加网络的深度，而是增加每个节点的交互阶数：从一阶（线性）升到二阶（二次型）。

03

每个输出维度一个切片。h 有 d 维，就有 d 个 2d×2d 矩阵；它们不是同一张矩阵重复用，而是各学各的。

04

参数量是它的软肋。4d³ 随 d 立方增长，d 一大就吃不消 —— 这也是后来 Tree-LSTM 一类模型用门控替代张量的动机之一。

05

训练时每个节点都有监督。所以中间层的 h 不只是"为了算根"的中间量，它本身就被训练成有意义的短语表示。

06

结构是外部给的。模型只学 V/W/b 和词向量，不学怎么断句；换一棵树，同一句话的表示就变了。

性质	RNTN 的表现
组合阶数	二阶（双线性），能表达乘性修饰
可学习参数	V: 4d³ ≈ 6.2 万（d=25），W: 2d²，另有词向量
计算顺序	后序遍历，深度 = 树高
表示在哪	根的 h = 整句；每个内部节点的 h = 对应短语
保留的信息	两个孩子之间的两两交互（这是关键）
代价	参数多、深层树上仍有梯度衰减

容易想错的三处

「张量项是另一个隐藏层」 —— 不是。它是一个标量二次型 uᵀVu，和线性项相加后才过 tanh，没有额外的非线性层。

「V 是一个矩阵」 —— 不是。V 是三阶张量 2d×2d×d，每个输出维度对应其中一张 2d×2d 的切片。

「只有根节点被训练」 —— 不是。论文的树库里每个短语都有情感标签，所有节点都参与监督。

02Tree-LSTM2015

ACL 2015 · Tai, Socher & Manning

一棵树，是怎么被嵌入成向量的

Tree-LSTM 的树表示学习过程 —— 只谈「树 → 向量」这一步，不谈它后来去做了什么任务

核心命题：树不是先被展平成序列再编码的。每个节点就是一个 LSTM 单元，它把标准 LSTM 里的「上一时刻的 h」换成 孩子的 h 之和，把「一个遗忘门」换成 每个孩子一个遗忘门。叶子从词向量出发，沿树自底向上递归，根节点的 h 就是整棵树的表示，每个内部节点的 h 就是它那棵子树的表示。

2.1

树表示学习其实只做三件事

先建立骨架，再看细节

1

Encode

叶子：词 → 向量

每个叶子节点拿到自己的词向量 x_j，经过一个 LSTM 单元得到 h_j。注意：成分树里只有叶子有 x，内部节点没有词输入。

2

Compose

内部：孩子 → 汇聚 → 门控

把所有孩子的 h_k 汇聚成 h̃_j，连同自己的 x_j 一起送进四个门，算出新的记忆 c_j 和输出 h_j。

3

Represent

根：整棵树的向量

递归到根，h_root 就是这句话（这棵树）的定长表示。中间每个节点的 h 也都"顺便"成了子短语的表示。

为什么非要用一个 LSTM 单元来做「组合」？因为一个合格的组合函数要同时满足三件事：① 输出维度固定——不管这棵子树有多大，都要压成同一个 d 维向量；② 组合方式可学习——保留什么、丢掉什么由数据决定，而不是人定的规则；③ 能吃任意分支和任意深度。求和 / 平均满足 ①③，但学不到「哪个孩子更重要」；拼接不满足 ①（维度会随分支数膨胀）；固定窗口的卷积不满足 ③。带门的递归单元把这三条同时满足了 —— 这就是 Tree-LSTM 存在的全部理由。

计算顺序不是从左到右读句子，而是按树的后序遍历（拓扑序）：孩子全算完，父亲才能算。

2.2

主舞台：一次真实的、自底向上的计算

右侧数字是真算出来的，不是占位符

下面用 4 维向量（方便看）把 The movie was really good 这棵二叉成分树完整算一遍。点「播放」，看向量如何沿着边向上流动；也可以单步、或点时间轴跳到任意一步。

The movie was really good

二叉化成分树 · 后序遍历

速度

2.3

把公式拆开：每个节点内部到底在算什么

与上方动画同步高亮

和标准 LSTM 相比，改动只有两处：输入从「上一个 h」变成「孩子的 h 汇聚」，遗忘门从「一个」变成「每个孩子一个」。其余门控逻辑完全一致。

Child-Sum Tree-LSTM 任意分支、子节点无序

(2)

h̃_j = Σ_k∈C(j) h_k

把所有孩子的 h 直接相加 —— 这一步是置换不变的，加完就分不清谁左谁右

(3)

i_j = σ( W⁽ⁱ⁾x_j + U⁽ⁱ⁾h̃_j + b⁽ⁱ⁾ )

输入门：这一层要往记忆里写多少新信息

(4)

f_jk = σ( W^(f)x_j + U^(f)h_k + b^(f) )

注意下标 jk：第 k 个孩子有自己专属的遗忘门，只由「父亲 + 这个孩子」决定

(5)

o_j = σ( W^(o)x_j + U^(o)h̃_j + b^(o) )

输出门：记忆里有多少要暴露成 h_j

(6)

u_j = tanh( W^(u)x_j + U^(u)h̃_j + b^(u) )

候选记忆：本节点想写进去的新内容

(7)

c_j = i_j ⊙ u_j + Σ_k∈C(j) f_jk ⊙ c_k

记忆更新：新内容 + 每个孩子的记忆各按自己的门打折后相加

(8)

h_j = o_j ⊙ tanh( c_j )

输出：这就是以 j 为根的子树的向量表示，会继续往上递

N-ary / Binary Tree-LSTM 固定分支数 N、子节点有序

(9)

i_j = σ( W⁽ⁱ⁾x_j + Σ_ℓ=1^N U⁽ⁱ⁾_ℓ h_jℓ + b⁽ⁱ⁾ )

每个槽位 ℓ 有自己的矩阵 U_ℓ，先分槽加权再相加 —— 有序信息在这里被保留

(10)

f_jk = σ( W^(f)x_j + Σ_ℓ=1^N U^(f)_kℓ h_jℓ + b^(f) )

双重下标 kℓ：第 k 个遗忘门会看所有孩子的 h，因此它能表达「因为左孩子是 not，所以右孩子要打折」

(11)

o_j = σ( W^(o)x_j + Σ_ℓ=1^N U^(o)_ℓ h_jℓ + b^(o) )

同上，按槽位分开

(12)

u_j = tanh( W^(u)x_j + Σ_ℓ=1^N U^(u)_ℓ h_jℓ + b^(u) )

候选记忆

(13)

c_j = i_j ⊙ u_j + Σ_ℓ=1^N f_jℓ ⊙ c_jℓ

记忆更新的形式和 Child-Sum 一模一样

(14)

h_j = o_j ⊙ tanh( c_j )

输出同样不变

Binary Tree-LSTM 就是 N=2 的特例，用在二叉化成分树上（左右孩子天然有序）。论文里 Constituency Tree-LSTM 用的就是它。

2.4

两种树 LSTM 的差别，只在一张「连线图」上

汇聚方式 × 遗忘门怎么接

Child-Sum 无序 · 任意分支

先求和，再过共享的 U —— 置换不变

汇聚：Σ h_k，对称、置换不变，天生适合依存树（孩子数不固定）
参数最省：U 只有 4 个 d×d 矩阵（i/f/o/u 各一）
代价：丢失孩子的顺序，谁左谁右无所谓

Binary / N-ary 有序 · 固定槽位

分槽加权，再过每个槽位自己的 U_ℓ

汇聚：Σ_ℓ U_ℓh_jℓ，槽位有身份，天然适合二叉成分树
参数更多：U 有 10 个 d×d 矩阵（i/o/u 各 2 个 + f 的 4 块）
好处：能对语序和句法角色敏感，表达能力更强

对比项	Child-Sum	N-ary / Binary
适用树	依存树，孩子数量任意	成分树，孩子数 ≤ N（通常 N=2）
汇聚 h̃	Σ h_k（无序）	Σ_ℓ U_ℓ h_jℓ（有序）
遗忘门 f_jk 依赖	只看第 k 个孩子的 h_k	看全部孩子的 h_j1…h_jN
词向量输入 x_j	每个节点都有（该节点中心词）	成分树里只有叶子有
U 矩阵数量（d×d）	4（i/f/o/u 各一）	10（N=2 时）

2.5

它和链式 LSTM 的关系：树退化成一条链

一个检验你理解没理解的判据

把树压成一条链（每个节点只有一个孩子），上面那套公式会自动退化成标准 LSTM：h̃_j = h_k 变成「上一个时刻的 h」，唯一的 f_jk 变成那个遗忘门，c_k 变成 c_t−1。

所以 Tree-LSTM 不是另一套模型，而是把 LSTM 的"时间轴"换成了"树结构"：

时间步的定义

链式：由位置决定

第 t 步依赖第 t−1 步，信息只能沿一条线单向流动，两个远距离词之间必须穿过中间所有词。

时间步的定义

树式：由句法决定

节点只依赖它的孩子，信息沿着句法边流动。两个词的交互距离 = 它们在树上的路径长度，通常远短于序列距离。

共同点

都是同一套门控 + BPTT

参数全树共享；训练时误差从根往下沿树反向传播，梯度在每个节点按「孩子数」分叉。

2.6

要点，以及三个常见的误解

01

树表示 = 根的 h。不是把所有节点向量拼接或平均；整棵树的表示就是递归到顶后根节点那一个定长向量。

02

嵌入和组合是同一件事。叶子编码词，内部节点编码短语，两者用的是同一个 LSTM 单元、同一组参数。

03

关键改造只有两处：用「孩子 h 的汇聚」替代「上一时刻 h」；用「每个孩子一个遗忘门 + 一份 c」替代「一个遗忘门 + 一份 c」。

04

计算顺序是后序遍历。孩子全算完父亲才算，所以任意深度都能递归，且每层都是并行可算的。

05

树结构是外部给的。模型只学 W/U/b 这些参数，不学「怎么断句」；结构换了，同一句话的表示就变了。

06

每个孩子一个遗忘门，是它能"选择性记忆"的关键。父亲可以保留一个孩子的记忆、丢掉另一个，这是简单地把孩子 h 拼接/相加做不到的。

容易想错的三处

「Tree-LSTM 自己学会了句法树」 —— 不对。树由外部解析器给出（依存用 Stanford 神经依存分析器，成分用 Stanford PCFG 分析器并二叉化）。

「根的向量是各词向量的加权和」 —— 不对。中间隔着 sigmoid / tanh 的非线性递归，是逐层复合出来的，不是线性组合。

「内部节点也有自己的词向量输入」 —— 看树而定。依存树里每个节点就是一个词，都有 x；成分树里只有叶子有 x，内部节点靠孩子汇聚。

03TBCNN2015

Mou et al. · Tree-Based Convolution

一棵树，是怎么被卷积成向量的

TBCNN 的树表示学习过程 —— 只看「一棵树怎么变成一个定长向量」

核心命题：TBCNN 不递归、不逐层合成、节点之间也不传递状态。它给每个节点配一个向量，在每个节点上开一个固定形状的窗口（父 + 左孩子 + 右孩子）算出一个特征，再把整棵树所有窗口的结果逐维取最大，压成一个定长向量。树在这里只决定了一件事：窗口开在哪、盖住谁；其余部分和一维卷积没有区别。

3.1

TBCNN 只做三件事

向量 → 窗口 → 池化

整棵树只被「看」一遍：先给每个节点配一个向量，再在每个节点上开一个窗口算一次，最后把所有窗口的结果压成一个向量。三步之间没有递归、没有先后依赖。

1

Step 1 · Input

每个节点 = 一个向量

每个节点都要有一个 d 维向量当输入。叶子直接用词向量；内部节点不是词，没有现成向量，得先「造」出来 —— 下一节细说。

2

Step 2 · Convolve

每个节点开一个窗口

窗口固定为「父 + 左孩子 + 右孩子」。三个位置各一套权重，在所有节点上复用，所以树再大参数量不变。

3

Step 3 · Pool

所有窗口压成一个向量

对每一维，在全部窗口里取最大值。输出维度 = 特征图数量，与树的形状、大小、节点数都无关。

这个设计的好处很直接：所有窗口互相独立，可以一次并行算完，不需要等孩子先算好；输出层到任意特征检测器之间只隔一次池化加几层全连接，传播路径很短。代价是节点之间的组合关系没有被建模 —— 池化只记得「某个局部结构出现过」，不记得「它和谁拼在一起」。

3.2

第 1 步的细节：节点向量从哪来

决定了窗口能「卷」到什么

卷积需要每个位置都有输入向量。但树的内部节点不是词，没有现成的词向量——这是 TBCNN 必须回答的第一个问题。

1

Constituency · 叶子

叶子 = 词向量

成分树的叶子就是词，直接用预训练词向量（论文用 word2vec，300 维）。这一步和普通 CNN 一样。

2

Constituency · 内部节点

先用 RNN 预训练，然后冻结

非叶节点没有词向量。论文的做法：先用递归 RNN（Socher 2011 式）把树跑一遍得到每个节点的向量，之后固定不动，再交给卷积去用。

3

Dependency

每个节点就是一个词

依存树的节点与句中词一一对应，天然每个节点都有词向量，不需要额外预训练——但孩子数量变得不固定。

注意这一步的含义：在 c-TBCNN 里，内部节点的向量不是由卷积学出来的，而是从另一套递归模型搬过来的"冻结特征"。所以 TBCNN 的「树表示」其实分两层：节点向量（预训练得到） + 结构特征（卷积 + 池化学到）。

3.3

主舞台：窗口滑一遍，再池化

真实数值计算，非示意

句子 the cake was quite sweet 的二叉成分树。点「播放」：虚线三角窗口会依次停在每个节点上，算出一个 4 维特征，填进下面的特征矩阵；最后一步逐维取最大值，得到句子向量。

the cake was quite sweet

深度 2 窗口 · 层序扫描（顺序不影响池化）

特征矩阵每个窗口一行 · 4 个特征图

速度

3.4

公式：整个模型只有四行

与上方动画同步高亮

TBCNN 之所以好讲，是因为它的"树"只出现在窗口的形状里，公式本身平凡得像普通 CNN。

通用树卷积式 (2)

(2)

y = f( Σ_i=1^t W_i · x_i + b )

窗口里有 t 个节点，每个位置 i 配一个权重矩阵 W_i，加权求和后过非线性

—

y = f( W_p·p + W_l·c_l + W_r·c_r + b )

c-TBCNN：深度 2 的窗口 = 父 + 左孩子 + 右孩子。叶子节点的 c_l、c_r 置 0

—

y = f( W_p·p + Σ_i=1ⁿ W_{r[c_i]}·c_i + b )

d-TBCNN：权重按依存关系类型分配，而不是按位置 —— 这样孩子数量可变也能算

同一组 W 在所有节点上共享，所以参数量与树的大小无关；窗口深度取 2，深度每加 1，窗口覆盖的节点数指数增长。

池化与输出无编号，原文为文字定义

—

g_k = max_v∈V y_v,k

对每一维 k，在所有窗口 v 上取最大值。得到的 g 就是定长句子向量

—

ŷ = softmax( W₂ · relu(W₁ g + b₁) + b₂ )

之后接全连接层做分类（这部分与本页主题无关，仅补全链路）

为什么用 max 而不是平均？max 相当于"只要这个结构特征在树里任何地方出现过，就把它记下来"，对树的形状、节点数量、窗口出现的位置都不敏感 —— 这正好符合「判别式」任务的需要（有没有某种句法模式）。

3.5

依存树怎么办：孩子数量不固定

TBCNN 最巧妙的一处改动

成分树二叉化后每个窗口固定三个位置，直接套 W_p/W_l/W_r 就行。但依存树里一个词可能有 0 个、1 个、5 个孩子，"按位置分配权重"立刻失效。

改法：按依存类型赋权

位置 → 语法角色

W_nsubj、W_acomp、W_det… 每个依存类型一个矩阵（保留 15 种高频类型，其余共享一个矩阵）。孩子数变了，求和项数变，权重含义不变。

池化也要按位置分槽

k-slot pooling：先分槽，再槽内取 max

纯 max 会把位置信息全丢掉。d-TBCNN 按词在句中的位置把特征分到 k 个槽（情感任务 k=2），槽内再取 max，作为折中。

3.6

要点、误解，和它的性质

性质	TBCNN 的表现
可学习参数	W_p、W_l、W_r 三个 d×d 矩阵 + 偏置（d-TBCNN 换成按依存类型的一组矩阵）
与树规模的关系	参数量与节点数无关；计算量与节点数成正比
并行性	所有窗口互相独立，可一次算完，没有「孩子先算」的依赖
输出维度	固定为特征图数量 n_c，与树的形状、大小无关
窗口深度	论文实验统一取 2；深度每加 1，窗口覆盖节点数指数增长
保留的信息	「某种局部句法结构出现过、强度多大」
丢掉的信息	特征来自哪个节点、与谁相邻、在句子哪个位置（k-slot 只补回一点）

01

树只出现在窗口形状里。公式和普通一维 CNN 几乎一样，区别只是"窗口内的邻居"由句法树定义，而不是"左右各 k 个词"。

02

没有根向量。任何单个节点都不代表整棵树；表示是池化出来的全局向量，这正是它与递归模型的根本差别。

03

参数共享到极致。同一组 W_p/W_l/W_r 在所有节点复用，所以树再大参数量不变，且每个窗口都能并行算。

04

c-TBCNN 的内部节点向量是预训练冻结的。这意味着"结构特征"和"节点语义"是两套东西拼起来的，理解它的表达力边界时必须记住这一点。

05

传播路径短是它的设计动机。输出层到任意特征检测器只隔一次池化 + 几层全连接，不像深递归网络那样要穿过整棵树。

06

池化是置换不变的。所以扫描顺序、节点顺序都不影响结果 —— 这也解释了为什么它天然适合「判别式」任务而不适合生成。

容易想错的三处

「TBCNN 也是从叶子递归算到根」 —— 不是。它没有递归合成，每个窗口独立计算，彼此不传递状态。

「窗口越大效果越好」 —— 不一定。论文实验用深度 2；深度每加 1，窗口覆盖节点数指数增长，而收益并不对等。

「池化后的向量还能还原树结构」 —— 不能。max pooling 丢掉了"特征来自哪个节点、和谁相邻"，只剩下"出现过什么"。

04ASTNN2019

ICSE 2019 · Zhang, Wang, Zhang, Sun, Wang, Liu

把语法树切成句子，再逐句编码

ASTNN 的树表示学习过程 —— 只看「一棵 AST 怎么变成一个定长向量」

核心动作是下刀：沿语句边界把一棵巨大的 AST 切成若干棵小语句树（外加 { } 标记），每棵小树用递归网络编成一个向量，于是得到一串「语句向量」；再把这串向量交给 Bi-GRU。所以它的树表示分两级：语句树向量（一棵小树 → 一个向量）和 代码片段向量（一串向量 → 一个向量）。

4.1

为什么非要把树切开

ASTNN 的出发点

1

Problem

AST 又大又深

一个普通方法解析出来常有上千个节点、二三十层。递归网络的计算深度等于树高，信息从叶子传到根要走很远，梯度容易消失，长距离依赖学不到。

2

Problem

二叉化会破坏结构

为了套用「左孩子 + 右孩子」的递归单元，常见做法是把 AST 强行转成二叉树。这既改变原有语法形状，又把树压得更深。

3

Idea

语句是天然的切点

代码本身就是由一条条语句组成的。在语句边界切开，每棵小树只有 2–4 层，递归编码不再有深度问题，而且不用二叉化，原树形状保留。

代价是：切开之后，语句之间的顺序和嵌套关系就不在树里了 —— 所以要靠后面的 Bi-GRU 把它们重新串起来。这正是 ASTNN 两级表示的分工。

4.2

第一刀：在哪切、切完长什么样

点「开始切分」

规则只有四条，但很关键：切的是语句体，不是语句本身。语句节点自己留下来当小树的根，它的身体被切走，成为后面独立的树。

int sum(int n) { int s = 0; for (int i = 0; i < n; i++) s += i; return s; }

C 代码 · pycparser 风格的 AST

切分后的顺序 = 源码顺序 + 花括号标记

规则 1

控制语句处下刀

遇到 FuncDef / If / For / While / DoWhile，以它为根开一棵新树，但不含语句体；语句体单独成树。

规则 2

For 特殊处理

For 只切走循环体，初始化、条件、步进留在自己的树里 —— 因为这三段决定了循环的语义。

规则 3

花括号变成标记

每个 {...} 块插入一个 { 和 } 节点。这样虽然树被切碎了，嵌套层级依然保留在序列里。

4.3

第二刀：一棵语句树怎么变成一个向量

真实数值 · 可单步

拿 for (i = 0; i < n; i++) 这棵语句树做例子。自底向上递归：每个节点把自己的 token 和孩子的向量拼起来，过一个大矩阵，再 tanh。最后不是取根，而是对整棵树的节点向量做逐维 max pooling。

for (i = 0; i < n; i++)

9 个节点 · 后序遍历

速度

4.4

第三刀：一串语句向量怎么变成一个代码向量

Bi-GRU + 时间维池化

切分后得到一个按源码顺序排列的语句向量序列。它已经丢掉了树结构，只保留了"第几条语句、是什么"。Bi-GRU 负责把顺序和上下文补回来：前向读一遍、后向读一遍，每个位置拿到两份上下文，最后在时间维上取最大。

s₁ … sₙ → 代码片段向量

双向各扫一遍，逐维取最大

为什么双向

语句的语义看上下文

一条 return s; 的含义取决于前面怎么算 s；一个循环体的作用取决于它后面的语句。单向 RNN 只能看一半。

为什么再池化

代码长度不固定

方法有 5 行也有 500 行。时间维 max pooling 把任意长度的序列压成固定维度，同时保留"某个位置出现过的最强信号"。

两次池化的区别

一次在树内，一次在时间上

语句树内池化得到一个语句的向量；时间维池化得到整段代码的向量。这是 ASTNN 里两个不同层级的 max。

4.5

公式与实现注记

四行公式串起整条链路

语句树编码（RvNN）

(1)

h_v = tanh( W · [ x_v ; h_c₁ ; … ; h_{c_n} ] + b )

把「自己的 token 向量」和「所有孩子的向量」拼起来，乘一个大矩阵再 tanh。叶子没有孩子，只用 x_v

(2)

s = max_{v ∈ tree} h_v

语句向量 = 树内所有节点表示的逐维最大值 —— 不是根的 h

同一棵树里所有节点共享同一组 W、b；不同分支数用不同形状的 W（0 个孩子、1 个、2 个…各一套），这样既不用二叉化，也不用给每个位置配一套权重。

序列编码与池化

(3)

h_t = [ GRU_→(s_t, h_t−1) ; GRU_←(s_t, h_t+1) ]

Bi-GRU：每个位置的表示由「左边看过来的上下文」和「右边看过来的上下文」拼接而成

(4)

g = max_t=1…n h_t

时间维逐维取最大，得到与代码长度无关的定长向量 g

之后的分类/检测头（全连接 + softmax 或孪生网络）与本页主题无关，略。

实现注记（值得知道）：官方开源仓库里，RvNN 那一层被简化过 —— W_l / W_r 定义了却没有参与计算， tanh 被注释掉了，实际等价于 h = W_c·e(v) + Σ h_c（线性累加）。如果照抄这份代码去复现论文，编码器会退化成「token 向量的加权求和」。以论文的式 (1) 为准。

4.6

要点、误解，和它的性质

01

树被切碎了，但没被丢掉。语句边界切开后，靠 { } 标记和序列顺序把结构找回来。这是「分而治之 + 序列重连」的组合。

02

语句向量不是根的 h。根只是一个语法类别（比如 For），取根会丢掉细节；max pooling 保留「这条语句里最显著的特征」。

03

不用二叉化。按孩子数量选用不同形状的 W，n 个孩子就拼成 n 份，天然支持任意分支。

04

两个层级的池化，解决两个不同的问题。树内池化解决「一棵树 → 一个向量」，时间维池化解决「长度不固定」。

05

深度被切没了。切开后每棵树只有 2–4 层，梯度路径短，这是它相对整树递归模型最实际的优势。

06

顺序信息是后补的。切分本身打乱了树的层级，顺序与嵌套全靠 Bi-GRU 重新建模 —— 所以序列编码器不是可选项。

性质	ASTNN 的表现
输入	原始 AST（不二叉化），切成语义单元后的小树序列
可学习参数	RvNN 按孩子数共享的几套 W + Bi-GRU 参数，与代码长度无关
计算深度	= 单棵语句树的深度（2–4 层），与整个方法的大小无关
输出维度	固定（Bi-GRU 隐层维度 ×2），与语句条数、代码长度无关
保留的信息	语句内部的词法 + 语法结构，语句之间的顺序与嵌套
丢掉的信息	跨语句的精确树路径（比如某个变量在几条语句间的数据流）

容易想错的三处

「ASTNN 是把整棵 AST 递归编码」 —— 不是。它先切成小树，每棵独立编码，树与树之间不传递状态。

「切分后结构就丢了」 —— 没丢。{ } 标记 + 源码顺序 + Bi-GRU，把嵌套和先后都编码进了序列。

「语句向量就是语句树根节点的向量」 —— 不是。是对全树节点做 max pooling，根只是其中一个候选。

为什么"加权求和"不够用

只能加，不能"翻转"

交叉项才表达"修饰"

参数涨一个量级

树从哪来，叶子是什么

二叉成分树

叶子 = 词向量

后序遍历，自底向上

主舞台：一个节点内部到底在算什么

公式：只多了一项

张量到底学到了什么

not × good

very × 好

X but Y

要点、误解，和它的性质

容易想错的三处

树表示学习其实只做三件事

叶子：词 → 向量

内部：孩子 → 汇聚 → 门控

根：整棵树的向量

主舞台：一次真实的、自底向上的计算

把公式拆开：每个节点内部到底在算什么

两种树 LSTM 的差别，只在一张「连线图」上

Child-Sum 无序 · 任意分支

Binary / N-ary 有序 · 固定槽位

它和链式 LSTM 的关系：树退化成一条链

链式：由位置决定

树式：由句法决定

都是同一套门控 + BPTT

要点，以及三个常见的误解

容易想错的三处

TBCNN 只做三件事

每个节点 = 一个向量

每个节点开一个窗口

所有窗口压成一个向量

第 1 步的细节：节点向量从哪来

叶子 = 词向量

先用 RNN 预训练，然后冻结

每个节点就是一个词

主舞台：窗口滑一遍，再池化

公式：整个模型只有四行

依存树怎么办：孩子数量不固定

改法：按依存类型赋权

池化也要按位置分槽

要点、误解，和它的性质

容易想错的三处

为什么非要把树切开

AST 又大又深

二叉化会破坏结构

语句是天然的切点

第一刀：在哪切、切完长什么样

控制语句处下刀

For 特殊处理

花括号变成标记

第二刀：一棵语句树怎么变成一个向量

第三刀：一串语句向量怎么变成一个代码向量

语句的语义看上下文

代码长度不固定

一次在树内，一次在时间上

公式与实现注记

要点、误解，和它的性质

容易想错的三处

论文整理工作流

微风工坊首页