讨论 2020-01-13
=
###### tags: `tutorials` `Fudan` `2020`
# 文本中的结构 (三)

大量参照 http://www.cs.umd.edu/class/fall2017/cmsc723/slides/slides_13.pdf ，对于文本结构的研究和教程数不胜数，本文只起抛砖引玉之用。

## Non-Projective 解法
没有了 Projective假设，没法做子问题拆解（不满足区间划分的要求），所以就不再适用上次讲的动态规划算法了。
退回到在一个全连接有向图上找生成树的问题，有向图的最小生成树有相应的解法，朱刘算法

## 朱刘算法

- 为每个点找最小入边
- 如果最小入边不成环，就是最小生成树
- 如果成环，缩点，重复流程
- 求解出一个缩点后的最小生成树，可以逐层展开，对于一个环，只去掉和整个环的入边相矛盾的一条边即可

## Non-Projective的困境
虽然我们给出了一些 Non-Projective的例子，并且在一些语言中更为频繁，但语言本身还是比较简单的，当做一个图论问题来解过于宽松，容易出现一些过于复杂的例子，并且对误差敏感。如果语法树和文字语序对应关系很差，实际上是不利于人们理解的，所以在Non-Projective和Projective之间应该有合理的假设（或者说不同语言有各自的合理假设）。

## Transition-Based
转移式/传递式的句法分析从另一个角度考虑问题，既然目标是一棵树，并且在Projective假设下，是一个语序和原句一致的括号表达式，那么就直接按照括号表达式的处理方式来做即可。换言之，我们可以把问题看做是如何在一个序列中加括号，只不过是有顺序，贪心的。其实用上次讲的动态规划思想解括号问题更自然，但是在Context-free Grammar中有一种简化的解法就是 Shift-Reduce 算法(用栈解表达式求值)。 Transition-Based的工作大部分受Shift-Reduce的影响，虽然处理的目标不是CFG了，仍然近似的使用这种算法。所以Transition-Based从本质是贪心的，局部最优的，换言之Transition-Based一开始就放弃了求最优解，但因此他的速度也很快（在NN中相反，因为要考虑历史信息）。

Shift-Reduce

a+b*(c+d*e)+f
|a
|a+
|a+b
|a+b*
|a+b*(
|a+b*(c
|a+b*(c+
|a+b*(c+d
|a+b*(c+d*
|a+b*(c+d*e    	A=d*e
|a+b*(c+A
|a+b*(c+A)	        B=(c+A)
|a+b*B         	C=b*B
|a+C
|a+C+
|a+C+f <eos>	        D=C+f
|a+D <eos> 	        E=a+D
|E <eos>

Arc-Standard
Arc-Eager

# 句法分析的合理性
其实Graph-Based和Transition-Based都不能完整的表达句法分析问题。

Graph的中的边应该是互相无关的，很少有图论算法会考虑求解子图结果时会影响边权，比如求一个最短路，加入一条边，另一条边权值就会改变。当然，在网络流中有一些例子，但权值影响都很简单。

Transition-Based把问题拆解成有后效性的局部贪心问题，显然就是有瑕疵的，另一方面，他也不是个MDP问题，并且从左到右不一定是后效性最小的顺序。

所以说，句法分析问题抽象化之后的模型就已经是一个很复杂的模型了，目前还没有很好的解答。