早期博文含有大量错误,见谅。关于最大生成树句法分析器,请参考 Non-projective Dependency Parsing using Spanning Tree Algorithms
生成式句法分析指的是,生成一系列依存句法树,从它们中用特定算法挑出概率最大那一棵。句法分析中,生成模型的构建主要使用三类信息:词性信息、词汇信息和结构信息。前二类很好理解,而结构信息需要特殊语法标记,不做考虑。
本文主要利用了词汇+词性生成联合概率模型,使用最大生成树Prim算法搜索最终结果,得到了一个简单的汉语依存句法分析器。
开源项目
本文代码已集成到HanLP中开源:http://www.hankcs.com/nlp/hanlp.html
基本思路
统计词语WordA与词语WordB构成依存关系DrC的频次,词语WordA与词性TagB构成依存关系DrD的频次,词性TagA与词语WordB构成依存关系DrE的频次,词性TagA与词词性TagB构成依存关系DrF的频次。为句子中词语i与词语j生成多条依存句法边,其权值为上述四种频次的综合(主要利用词-词频次,其余的作平滑处理用)。取边的权值最大的作为唯一的边,加入有向图中。
在有向图上使用Prim最大生成树算法,计算出最大生成树,格式化输出。
模型训练
简单地统计一下清华大学语义依存网络语料,得到如下结果:
找@ 频次 54 找@##核心## 核心成分 16 找@<d> 结果事件 1 找@<f> 目的 1 找@<n> 限定 3 找@<root> 核心成分 16 找@<v> 内容 2 结果事件 2 目的 1 找@<vf> 目的 1 找@也有 结果事件 1 找@仪器 限定 1 找@前来 目的 1 找@去 目的 1 找@合作 内容 1 找@引导 结果事件 1 找@让 结果事件 1 找@进入 目的 1 找@队伍 限定 1 找@需 内容 1 找@项目 限定 1
@符号连接起两个词汇或词性,用<>括起来的表示词性,否则是词汇。如果@后面没有内容,则表示频次,否则表示一些依存关系与其出现的频次。
依存句法分析
分词标注
以“我吃米饭”为例,先进行分词与词性标注,结果:
[我/rr, 吃/v, 米饭/nf]
生成有向图
由于依存句法树中有虚根的存在,所以为其加入一个虚节点,这样一共有四个节点:
[##核心##/root,我/rr,吃/v,米饭/n]
每个节点都与另外三个构成一条有向边,一共4 * 3 = 12 条:
##核心##/root 到 我/rr : 未知 10000.0 ##核心##/root 到 吃/v : 未知 10000.0 ##核心##/root 到 米饭/n : 未知 10000.0 我/rr 到 ##核心##/root : 核心成分 6.410175 我/rr 到 吃/v : 施事 21.061098 经验者 28.54827 目标 33.656525 受事 37.021248 限定 43.307335 相伴体 48.00737 关系主体 53.115623 内容 53.115623 来源 64.101746 我/rr 到 米饭/n : 限定 22.2052 施事 48.00737 受事 57.170277 目标 57.170277 经验者 64.101746 连接依存 64.101746 吃/v 到 ##核心##/root : 核心成分 1.7917595 吃/v 到 我/rr : 连接依存 96.688614 介词依存 107.67474 施事 107.67474 吃/v 到 米饭/n : 限定 24.849068 米饭/n 到 ##核心##/root : 核心成分 37.077995 米饭/n 到 我/rr : 连接依存 113.2556 米饭/n 到 吃/v : 受事 0.6931472
其中“未知”表示边不存在,“受事”“施事”表示依存关系,后面的小数表示权值。我对概率取了负对数,所以接下来用加法求最小生成树即可。
最小生成树
关于最小生成树的Prim算法请参考《最小生成树算法初步》,这里必须有所改动,由于虚根有且只能有一个孩子,所以虚根必须单独计算:
// 找虚根的唯一孩子 float minCostToRoot = Float.MAX_VALUE; Edge firstEdge = null; Edge[] edgeResult = new Edge[termList.size() - 1]; for (Edge edge : edges[0]) { if (edge == null) continue; if (minCostToRoot > edge.cost) { firstEdge = edge; minCostToRoot = edge.cost; } }
然后就是中规中矩的Prim算法:
while (!que.isEmpty()) { State p = que.poll(); int v = p.id; if (used[v] || p.cost > mincost[v]) continue; used[v] = true; if (p.edge != null) { edgeResult[p.edge.from - 1] = p.edge; } for (Edge e : edges[v]) { if (e == null) continue; if (mincost[e.from] > e.cost) { mincost[e.from] = e.cost; que.add(new State(mincost[e.from], e.from, e)); } } }
得出最小生成树:
2 0核心成分 3 2受事 1 2施事
格式化输出
将其转为CoNLL格式输出:
1 我 我 rr rr _ 2 施事 _ _ 2 吃 吃 v v _ 0 核心成分 _ _ 3 米饭 米饭 n n _ 2 受事 _ _
可视化
使用可视化工具展现出来:
结果评测
我没有进行严格的测试,这只是一个玩具级别的汉语依存句法分析器。先来看几个good case与bad case——
坚决惩治贪污贿赂等经济犯罪
我每天都在写程序
hankcs每天都在写程序
挖掘机技术哪家强
咬死猎人的狗
效果比较马虎,为何这么说,这是因为分词的训练语料和句法分析语料不同,且我自知此方法严重依赖词汇共现,主要是这种二元词汇生成模型无法充分利用上下文。
短一点的搜索语句可能还是有微量的利用价值。
TODO
应当采用判别式模型,导入SVM或最大熵作为权值的计算工具,然后使用最大生成树算法获取全局最优解。
您好,请问模型的训练代码是不是没有开源?没找到。如果不能开源,您是否可以提供一下参考资料,谢谢
宗成庆老师的《统计自然语言处理》里面显示最大树是属于判别式依存分析方法,每条边算的是条件概率,不是联合概率,我也觉得应该是判别式。
你好,请教一个问题,根据这个可以提取句子中的key和value吗,我没有头绪
prim算法会产生交叉弧,最小熵算法需要改进。
这些知识可以用在情感分析上面么,有做情感分析的意图么。
情感分析用文本分类模型居多
每个依存关系的概率怎么算的?
看代码吧
感谢,看了代码明白了:-log(词1到词2依存关系数/总数) 没有的话取 -log(词到词性依存关系数/总数) *10 没有的话取 -log(词性到词依存关系数/总数) *10 没有的话取 -log(词性到词性依存关系数/总数) *100
不客气,这个比例是自己拍脑袋决定的,毕竟这只是个玩具,大致反映了约束的优先级就行了
你好 怎么保证依存关系的箭头不交叉
你好,暂时没考虑,这个得在最小生成树的生成过程中做判断。或者改用Shift-Reduce Algorithm等算法,我倾向于后者。
你可以把你做的依存树库标注工具发我一份吗,整个项目。
你指的这个?http://www.hankcs.com/nlp/corpus/chinese-treebank.html#h2-8
差不多 我自己有做 做的很糟,你有做吗
这个倒没有
没有成型的工具还是蛮可惜的
我没有仔细找过,我猜这个肯定有开源的实现,至少Java平台下套用一个矢量库做这么一个GUI并不难
那个南大的不开源的,你做了很多前期工作,有个成品稍微好点感觉
前期工作指的是依存句法分析吗?那么后期工作指的是可视化和人工调整的GUI?斯坦福parser里面自带了一个GUI,对可视化感兴趣的话可以去看看