讨论 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的例子，其括号表达式总是和原句语序不符。

大家可以尝试一下

### 动态规划
今天介绍的三种方法(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（下次讲）