这篇博客中,我通过学习hankcs的Java版本,自己试着做一个简单的Python版本,用于学习和理清思路。
思路
所谓生成式句法解析是指生成一些列依存句法树,挑出概率最大的一棵。
这里的实现考虑了词性信息+词汇信息,使用最大生成树Prim算法搜索最终结果,实现一个简单的汉语依存句法分析器。
具体:
- 训练:
- 统计词语$WordA$和词语$WordB$构成依存关系$DrC$的频次。
- 统计词语$WordA$和词性$TagB$构成依存关系$DrD$的频次。
- 统计词性$TagA$和词语$WordB$构成依存关系$DrE$的频次。
- 统计词性$TagA$和词性$TagB$构成依存关系$DrF$的频次。
- 解析:
- 为句子中的词语$i$和词语$j$生成多条依存句法边,权值是上面4中频次的综合。
- 取边的权值最大的作为唯一的边,加入有向图。
- 使用Prim最大生成树算法,计算出最大生成树,格式化输出。
数据
使用第二届自然语言处理与中文计算会议(NLP&CC 2013)清华大学的数据。
下载地址:http://tcci.ccf.org.cn/conference/2013/dldoc/evsam05.zip
这些树库语料都是CoNLL格式的,CoNLL格式的语料以.conll结尾:
1 | CONLL标注格式包含10列,分别为: |
模型训练
这里所谓的模型训练即统计之前说的四种词频。
1 | from collections import namedtuple |
1 | list(c_dict.items())[:10] |
1 | [(('坚决', '惩治'), {'方式': 1}), |
1 | count |
1 | 165534 |
1 | def calc_dict_size(one_dict): |
1 | 165534 165534 165534 165534 |
构建图
进来一句句子,首先要做分词和词性判断。
然后在句首加入root,对一句有$n$个词的句子,两两之间可能有$(n+1)×n-n$条有向边。
这里的箭头是指向被依赖的HEAD。
有向边的权值计算方法:
$$log(词1到词2依存关系数/总数)$$
$$没有的话取\;\; log(词到词性依存关系数/总数) *10$$
$$没有的话取\;\; log(词性到词依存关系数/总数) *10$$
$$没有的话取\;\;log(词性到词性依存关系数/总数) *100$$
解释:第一种情况的权值要最大,第二第三种稍小,第四种最小。注意这里log计算后是负数。
1 | import jieba |
1 | [pair('我', 'r'), pair('写', 'v'), pair('代码', 'n')] |
1 | def get_max_from_dict(one_dict, k): |
1 | [Edge(name='施事', weight=-11.323784710206265, from_id=1, to_id=2), |
1 | root_edges = [] |
1 | [Edge(name='Root', weight=-12.016931890766211, from_id=0, to_id=0), |
Prim算法
Prim核心思路:任意挑一个顶点,添加权值最大边,直至所有顶点都在树中,得到一棵最大生成树。
1 | tree_edges = [] |
1 | [Edge(name='Root', weight=-4.318902720493405, from_id=2, to_id=0)] |
1 | nodes = set([tree_edges[0].from_id]) |
1 | {2} |
1 | # Prim |
1 | tree_edges |
1 | [Edge(name='Root', weight=-4.318902720493405, from_id=2, to_id=0), |
注意到这里的实现是从DEP指向HEAD,所以和一般常用的箭头方向正好相反,下面的函数中将顺序反过来,并输出标准的CONLL格式
1 | def edges2conll(edges, seg_list): |
1 | edges2conll(tree_edges, seg_list) |
1 | 1 我 我 r r _ 3 限定 _ _ |
使用这个在线可视化工具:http://spyysalo.github.io/conllu.js/ ,输入conll格式的数据可视化一下:
果然还是个Toy,三个错了一个。
总结
这只是我学习Hank写的一个小demo,主要目的是学习简单的依存解析器的实现原理。
缺点:prim算法会产生交叉弧,prim本身的实现也不是最优的,还有很多地方需要改进,也没有进行测评。