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 思考
- 逆向 concat 得到 semantic 和 structure 的表示,真的合理吗?作者在实验部分写到,LSTM hidden size = 100, semantic = 75, structure = 25, 这。。
- 这个方法在句子里面使用,可以用句法树来解释;在文档里面使用,还真就只能说成 LSR 的 latent structure 了。。。顿时就失去了可解释性(但是还是很有道理的)不知道,篇章结构有没有什么类似句法分析的 parser 或者规范?让篇章的 structure 不 latent!
- 在看到 pooling 的时候,突然想到,pooling 怎么反传梯度?这里 搜到了答案
- 看实验结果的时候,突然想到,怎么统计参数量?也查到了 pytorch得到模型的计算量和参数量,没试
- 这篇文章表示 document 是一个 word – sentence – document 的 pipeline,因此很容易就想到,为什么不直接把每一句的句法树的根结点,按照 document structure 组合,让整个 document 形成一个直接由 word 作为结点的树呢?LSR 就是这样做的。当然,这里 pipeline 好还是 joint 好,也是说不准。说不定把 LSR 改回 pipeline,性能又提升了呢。
5 Ref
- Terry Koo, et al., “Structured Prediction Models via the Matrix-Tree Theorem”, EMNLP 2007 pdf slides
- 学习笔记 – Matrix-Tree矩阵树定理
- 机器学习基础(3)——广义线性模型 – soul的文章 – 知乎
- Yoon Kim, et al., “Structured Attntion Networks”, ICLR 2017 pdf
- CHAPTER 13 Dependency Parsing
- 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
- 2.4.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]
- 说是用 Chu-Liu-Edmonds 算法从 attn matrix 画出生成树,回来得看看这个算法,如果所有 attn score 都能画出一棵树,那这文章 motivation 就废了
- 看看怎么把句子分成 unit
豁然开朗,感谢博主。
不客气,多多交流