论文笔记 – Learning Structured Text Representations

Yang Liu and Mirella Lapata, “Learning Structured Text Representations”, TACL 2018, pdf

1 简介

这篇文章的目的是获得 document 的表示。主要创新就在于使用 [1] 中基于 Matrix-Tree Theorem 的方法计算 attn score，这样出来的 attn matrix 就能表示文本的 non-projective tree 的结构（non-projective[5] 就是句法树的边可以有交叉）。

从另一方面来说，本文其实是 [4] 的改进：[4] 是使用 inside-outside algorithm 计算 attn score，使得到的 attn matrix 表示文本的 projective tree 结构。

为什么不用句法树工具得到句法树，然后直接用这个显式的来 guide attn？作者觉得这样就变成 pipeline，会有 error propagation。

本文的实验部分我就不说了，因为都是基础任务，对我的工作意义不大。下面就详细介绍一下它的方法。

2 方法

2.1 baseline

先描述一下这个任务，前人有一个基本框架：为了得到 document 的表示，就先用 word 的表示 做 attention aggregation（以下简称 attn agg）得到 sentence 表示，然后再用类似的结构，给 sentence 表示做 attn agg，得到 document 的表示。

具体来讲，attn agg 的过程如下：对于长度为 n 个词的句子 $[u_1, u_2, …, u_n]$，对于一对 token pair $<u_i,u_j>$，attn score $a_{ij}$ 的计算如下（公式 tag 我都是按照文中写的，所以不连续）：$$f_{ij} = F(u_i,u_j)\tag{1}$$ $$a_{ij} = \frac{\exp(f_{ij})}{\sum_{k=1}^n\exp(f_{ij})}\tag{2}$$

然后就可以得到每个 token context-aware 表示 $r_i$：$$r_i = \sum_{j=1}^na_{ij}u_j\tag{3}$$

最后进行 aggregation，即将所有 $u$ 过一层池化。但是这有一个严重的问题，就是他没有把句子的结构信息、文档的结构信息引入。[4] 这篇文章 empower neural networks with a structural bias（不太好翻译，下一段会解释），它的方法是将 (2) 式改成：$$a = inside-outsude(f)\tag{4}$$

They take into account the dependency structure of a sentence by viewing the attention mechanism as a graphical model over latent variables. They first calculate unnormalized pairwise attention scores for all tokens in a sentence(就是 $f$) and then use the inside-outside algorithm to normalize the scores with the marginal probabilities of a dependency tree.

这里的 marginal probility of a dependency tree 就是 attn matrix 作为邻接矩阵，从这个矩阵里找生成树作为句子的句法树的概率，后面会在讲方法的时候具体说。

但是这个做法还有两个问题：① inside-outside algorithm 只能生成 projective tree ② inside-outside algorithm 需要 DP，太慢。

本文方法基于 Matrix-Tree Theorem，可生成 non-projective tree，全程可微分、可端到端学习，可并行计算

下面就以 sentence 的表示这一步为例，详细介绍本文的方法。

2.2 sentence model

这部分模型如图所示，先用 Bi-LSTM 得到每个 token 的 embedding $[h_1,h_2,…,h_n]$，然后对于每一个 embedding，都拆成两部分：$$[e_t,d_t] = h_t\tag{7}$$

这里的拆，真的就是逆向 concat，得到 semantic vector $e_t$ 和 structure vector $d_t$。作者通过 structured attention mechanism，从 $d_t$ 得到与句子结构的表示 $p_t, c_t$，再和 $e_t$ 拼接、linear，就得到 token 的 context-aware 表示 $r_t$。

2.3 structured attention mechanism

那 $p_t, c_t$ 分别代表什么，以及 structured attention mechanism 是个啥呢？

我要详细阐述一下作者的 motivation：我们原先的 attention，只是一个信息的聚合，这并不能表明什么“模型注意到”云云。而在 NLP 领域，句法分析树是一个非常好的东西，他可以表示句子每个 token 之间的信息的传递，且对于长距离的 token 不方便找关系的问题（可是，attn 不已经解决了吗？），在句法树上也能轻易解决（句法树上距离就短多了，最多不就是层数 * 2 嘛）。

再具体一点，建立一个句法树，实际上就是找一组隐变量 $z_{ij} (i\ne j)$，表示 token i 是 j 的父亲结点。再加上一些限制，就能用它表示有根节点的树。[1] 通过求句法树上边的概率 $P(z_{ij} = 1)$ 来求解这一组隐变量。作者就想，如果用这个概率来替换 attn score，那么这所代表的 attn 的信息，不就是让句子中的词语信息，只按照句法树的上的边的流向来走嘛！

首先，用 (7) 得到的 structure vector 计算 unnormalized attention scores $f_{ij}$ 和 root score $f_i^r$：$$t_p = \text{tanh}(W_pd_i)$$ $$t_c = \text{tanh}(W_cd_j)$$ $$f_{ij} = t_p^TW_at_c$$ $$f_i^r = W_rd_i$$

其中，右下角标的 p, c, r 分别代表 parent, child, root，$W_c, W_p$ 是专门给父节点和子节点设立的 weight。计算 $f_{ij}$ 是两个 structure vector 分别过 linear，然后 bilinear；计算 $f_i^{r}$ 是直接一个 linear 得到。

作者说，这里的 $f_{ij}$ 可以被看做一个带权重的邻接矩阵，$f_i^r$ 是这个词是句法树根结点的概率。

下面，就通过计算每个边的概率 $P(z_{ij} = 1)$ 来找到句法树的边：

先定义邻接矩阵:$$A_{ij} = \begin{cases} 0 & \text{if } i = j \\ \exp(f_{ij}) & \text{otherwise} \end{cases}$$

这个很好理解，$f_{ij}$ 就是边权嘛。

然后定义拉普拉斯矩阵：（先说一句，拉普拉斯矩阵的定义，$L = D-A$，度矩阵 – 邻接矩阵）

$$L_{ij} = \begin{cases} \sum_{i’=1}^n A_{i’j} & \text{if } i= j \\ -A_{ij} & \text{otherwise} \end{cases}$$

这里也很好理解，就是把一个节点的边权相加，作为这个节点的度了嘛。

下面就开始进入 Matrix-Tree Theorem 和 [1] 的知识范围了，我在本节先只简单介绍和感性地解释，先把他的方法说清楚，我在 2.4 再来进行推导和证明。

然后定义变异的拉普拉斯矩阵（$\bar{L}$ is a variant of $L$ that takes the root node into consideration）$$\bar{L}_{ij} = \begin{cases} \exp(f_i^r) & i= 1 \\ L_{ij} & i > 1 \end{cases}$$

为什么要定义 $\bar{L}$ 呢？为了让现在讲方法更紧凑，我挪到后面说，详见 2.4.1

然后就可以计算句法树每个边的概率 $P(z_{ij} = 1)$ 和节点是根节点的概率 $P(root(i))$：$$P(z_{ij} = 1) = (1-\delta_{1,j}) A_{ij}[\bar{L}^{-1}]_{jj} – (1-\delta_{i,1}) A_{ij}[\bar{L}^{-1}]_{ji}$$ $$P(root(i)) = \exp(f_i^r)[\bar{L}^{-1}]_{i1}$$

这部分的解释详见 2.4.2

算出来的概率就可以当做 attn score，下面把 $P(z_{ij} = 1)$ 改写成 $a_{ij}$，$P(root(i))$ 写成 $a_i^r$，然后就可以通过 attn agg 得到 token i 作为父节点的表示 $p_i$ 和作为子节点的表示 $c_i$：$$p_i = \sum_{k=1}^na_{ki}e_k + a_i^r e_{root}$$ $$c_i = \sum_{k=1}^na_{ik}e_i$$

其中 $e$ 是式子 (7) 得到的 semantic vector，式子也很符合直觉，$p_i$ 就从可能的 parents 来 garther，$c_i$ 就从可能的 children 来 garther。最后将三者拼起来 + linear，得到 context-aware 表示 $r_i$：$$r_i = \text{tanh}(W_r[e_i;p_i;c_i])$$

2.4 一些解释

2.4.1 $\bar{L}$

$$\bar{L}_{ij} = \begin{cases} \exp(f_i^r) & i= 1 \\ L_{ij} & i > 1 \end{cases}$$

为什么要把第一行换成 root 的分数呢？（其实把任意一行换成 root 的分数都可以）这是因为在 [1] 中计算一棵树的 logit 分数时，实际上是下面这个式子的形式（我简化了）：$$\psi = r_{root} \prod A_{ij}$$

很简单，就是这棵树根结点的分数乘以所有边的分数。那么在计算这个句子属于这棵树的概率时，就是：$$p = \frac{\psi}{\sum\psi}$$

因此，这里的分母 $z = \sum \big(r_{root} \prod A_{ij}\big)$。根据 Matrix-Tree Theorem，拉普拉斯矩阵的 minor $L^{(m,m)}$（就是矩阵的余子式的行列式）就等于以点 m 为根结点的所有生成树的权重之和，因此上面这个分母 $z$ 可以用拉普拉斯矩阵表示：$$z = \sum \big(r_{root} L^{(m,m)}\big)$$

那这个式子不就是把 $\text{det}(\bar{L})$ 按照第一行展开嘛！所以搞一个 $\bar{L}$ 其实就是为了算 $z$ 方便。

2.4.2 $P(z_{ij} = 1), P(root(i))$

$$P(z_{ij} = 1) = (1-\delta_{1,j}) A_{ij}[\bar{L}^{-1}]_{jj} – (1-\delta_{i,1}) A_{ij}[\bar{L}^{-1}]_{ji}$$ $$P(root(i)) = \exp(f_i^r)[\bar{L}^{-1}]_{i1}$$

这两个式子的推导是同一个流程，我就用第一个来讲。在 2.4.1 说了，树的概率 $p = \frac{\psi}{\sum\psi}$，然后作者讲这个式子做了一个变形，原文 ([1] 3.2) 如下，我看不懂。

然后把这个微分求出来，就得到结果了。唉，我数学太差了。

3 实验

不说具体实验，只说一点有意思的：这个算法生成的句法树，要比用 parser 标注的层数更浅，且这两个之间有 37% 的边是相同的。这让人很 exciting！生成的树里面，projective 和 non-projective 大约是五五开。

但是，文档结构生成的树就差得远了，作者说，our trees cannot be directly compared with the output of a discourse parser which typically involves a segmentation pro- cess splitting sentences into smaller units. 因为没有把文章中的句子分成一个个 unit。【#TODO4】

4 思考

1. 逆向 concat 得到 semantic 和 structure 的表示，真的合理吗？作者在实验部分写到，LSTM hidden size = 100, semantic = 75, structure = 25, 这。。
2. 这个方法在句子里面使用，可以用句法树来解释；在文档里面使用，还真就只能说成 LSR 的 latent structure 了。。。顿时就失去了可解释性（但是还是很有道理的）不知道，篇章结构有没有什么类似句法分析的 parser 或者规范？让篇章的 structure 不 latent！
3. 在看到 pooling 的时候，突然想到，pooling 怎么反传梯度？这里 搜到了答案
4. 看实验结果的时候，突然想到，怎么统计参数量？也查到了 pytorch得到模型的计算量和参数量，没试
5. 这篇文章表示 document 是一个 word – sentence – document 的 pipeline，因此很容易就想到，为什么不直接把每一句的句法树的根结点，按照 document structure 组合，让整个 document 形成一个直接由 word 作为结点的树呢？LSR 就是这样做的。当然，这里 pipeline 好还是 joint 好，也是说不准。说不定把 LSR 改回 pipeline，性能又提升了呢。

5 Ref

1. Terry Koo, et al., “Structured Prediction Models via the Matrix-Tree Theorem”, EMNLP 2007 pdf slides
2. 学习笔记 – Matrix-Tree矩阵树定理
3. 机器学习基础(3)——广义线性模型 – soul的文章 – 知乎
4. Yoon Kim, et al., “Structured Attntion Networks”, ICLR 2017 pdf
5. CHAPTER 13 Dependency Parsing
6. Michał Daniluk, Tim Rockta ̈schel, Johannes Welbl, and Sebastian Riedel. 2017. Frustratingly short attention spans in neural language modeling. Pro- ceedings of the ICLR Conference .

6 TODO

1. 2.4.2 不懂（那个函数叫对数分割函数，但我愣是搜不出来他和条件概率有什么相关的定理）
2. 文中 3.1 说 the conventional way of using LSTM output vectors for calculating both attention and encoding word semantics is overloaded and likely to cause performance deficiencies，很有意思，我要看看引用的文章 [7]
3. 说是用 Chu-Liu-Edmonds 算法从 attn matrix 画出生成树，回来得看看这个算法，如果所有 attn score 都能画出一棵树，那这文章 motivation 就废了
4. 看看怎么把句子分成 unit