--- # System prepended metadata title: 讨论 2020-01-06 tags: [Fudan, tutorials, '2020'] --- 讨论 2020-01-06 = ###### tags: `tutorials` `Fudan` `2020` # 文本中的结构 (二) 大量参照 https://cl.lingfil.uu.se/~sara/kurser/5LN455-2014/lectures/5LN455-F7.pdf, http://ivan-titov.org/teaching/nlp1-15/nlp1-l9.pdf ，对于文本结构的研究和教程数不胜数，本文只起抛砖引玉之用。 ### 生成树问题 首先，句法树是一棵树，而我们的要通过某种方法来构建这个树，一种很自然的方法是从两个节点的关系，也就是一条边入手，假如我们对任意两个节点之间都有一个权重，那么构造树的问题就是属于生成树问题。 给定一个图G(V,E),目标是选出一些边构成子图G'，且G'包含所有V中节点，G'是一棵树。假如我们要求边权最小，那就是最小生成树。在句法树中，我们求解的还是有向图。 ### Projective 假如一棵树的节点可以通过一种固定的访问方式（称为遍历不准确）和原句的语序一样，那就是projective，否则就是non-projective。当然很多现有文献主要讨论了交叉边问题，实际是等价的，没有交叉边一定有固定访问方式，有的话一定没有。更为直观的做法（熟悉的可以略过这个牵强的解释）是观察一棵树的括号表达式，树总能表达成一个括号表达式（树的集合定义）。上述的固定访问方式在成分树中是中序遍历只取叶节点，而依存树是中序遍历。 下面是一个non-projective的例子，其括号表达式总是和原句语序不符。 ![](https://i.imgur.com/4LV7QlA.png) 大家可以尝试一下 ### 动态规划 今天介绍的三种方法(CYK算铺垫)都是动态规划算法，也都是在Projective假设下的。 简断截说，动态规划总有一个状态表，一个转移方程（带边界条件）。其结果是总能把一个问题分成其他的问题再求解（一个状态可以从其他状态转移而来）。 ### CYK Algorithm 这里只讲最原始的CYK，用来检测一个输入字符串是否符合一段给定的CNF（标准的上下文无关文法，见上次讲义）。 一个长度为n的字符串输入，non-terminal数量为r的语法，其状态表为(n,n,r)，前两维表示一段连续区间，r表示是哪种non-terminal。 \begin{gather} D[i,j,k] = \cup_{q,A,B} (D[i,q,A]\cap D[q,j,B]\cap k\rightarrow AB \in Grammar) \end{gather} 初值为non-terminal到terminal对应表，如果最后D[0,n-1]中有一个元素为真，那么输入字符串就是符合相应语法的。 ### Collins Algorithm 假如我们有任意两个元素依存关系的权重$r_{ij}$，其中$r_{ij}$表示$i \rightarrow j$，$r_{ji}$表示 $j \rightarrow i$。 Collins算法定义的状态表为(n,n,n)，其含义为(start,end,head)，即一段区间（st,ed）的head是h的情况。显然，转移方程如下 \begin{gather} D[st,ed,hl] = \max_{q,hr} (D[st,q,hl]+D[q,ed,hr]+r_{hl,hr}) \\ D[st,ed,hr] = \max_{q,hl}(D[st,q,hl]+D[q,ed,hr]+r_{hr,hl}) \end{gather} 见板书 ### Eisner Algorithm Eisner算法和Collins目标一致，但使用了更好的状态设计，所以复杂度更低,状态表为(n,n,2,2)，即（start,end, is start a head or end a head, end at interval or boundary），Eisner规定head节点一定是区间的左端点或右端点，第三维就是表示这个信息的，同时带来的问题是head确定在了端点，但另一边仍不确定，即head指向的是不是另一个端点，用第四维表示。 \begin{gather} D[st,ed,\rightarrow,true] = \max_{q}(D[st,q,\rightarrow,false]+D[q+1,ed,\leftarrow,false])+r_{st,ed} \\ D[st,ed,\leftarrow,true] = \max_{q}(D[st,q,\rightarrow,false]+D[q+1,ed,\leftarrow,false])+r_{ed,st} \\ D[st,ed,\rightarrow,false] = \max_{q}(D[st,q,\rightarrow,false]+D[q,ed,\rightarrow,true]) \\ D[st,ed,\leftarrow,false] = \max_{q}(D[st,q,\leftarrow,true]+D[q,ed,\leftarrow,false]) \\ \end{gather} ### 一些问题 - Non-Projective 怎么解？ - 上述所有$r_{ij}$都是独立的，如果$r$内部有联系怎么办 ### 朱刘算法（下次讲） ### Transition-Based（下次讲）