PCFG构造语法结构树相关问题思考
【目录】
- 如何从语料库提取PCFG(概率上下文无关)规则?
- 提取的规则存在什么数据结构中更好?
- 提取的规则为什么要转化为Chomsky Norm Form(CNF)?
- 提取的PCFG规则如何转化为CNF?
- 任意PCFG规则真的能像CFG一样转换为CNF吗?
- 如何根据符合CNF的规则生成新句子的结构树?
关于这些问题,如果大家知道有已经成熟的结论和推导过程,希望能留言告诉作者,帮助作者,谢谢啦~
【1. 如何从语料库提取PCFG(概率上下文无关)规则?】
我至今只做过从宾州中文树库CBT语料库中提取规则。归纳下来就是:了解语料库数据格式—>代码解析数据格式—>统计各种规则在语料库中的出现概率。这部分工作下一阶段方向:
【2. 提取的规则存在什么数据结构中更好?】
选择哪种数据结构更好,我基于两个方面考虑:
一:提取的规则在后续用来做什么工作?数据结构要让后续工作开发高效or工作效率高效。
二:数据结构能更好地表达提取的规则的自然含义?便于理解与传播,也便于开发
关于规则后续用来做什么工作,我现阶段只知道:形式的转化(转化到CNF或以后其他形式);根据规则生成句法结构树。
如果是在原规则基础上做形式转化,高频操作有:合并节点,新增节点,删除节点
如果是遍历原规则后,建立新建形式的规则,高频操作有:遍历。
关于是否能自然的表达规则,我认为“树”最贴近人本身对于规则的理解。例如wiki举例的如下规则,用以S0为根的树表示就很容易理解:
最初我没考虑这些,用的python里面字典结构表示学习的规则(以上图表示的规则为例),形式如下:
{S0:{“AbB”:p1,“C”:p2}, B:{“AA”:p3,“AC”:p4}, C:{“b”:p5,“c”:p6}, A:{“a”:p7,“sigma”:p8}}
好处是可以快速索引。下面我会继续使用这个结构存储学习到的规则,看看会有哪些好处和不便
【3.提取的规则为什么要转化为Chomsky Norm Form(CNF)?】
https://www.cnblogs.com/zhouksh/p/3732264.html
因为:使用原始形式(多叉树)时使用brute force遍历所有可能性,以找到一个句子最优的结构,计算量随句子长度的指数增长;
使用CKY算法以动态规划的方式解,计算量降低到多项式量级,但是要求从语料库中提取的规则满足CNF要求,因此需要将原始形式的规则转化为CNF形式
【4.提取的PCFG规则如何转化为CNF?】
{4.1}任意PCFG规则真的能像CFG一样转换为CNF吗?——下一步工作:深入理解PCFG概念,看是不是我有地方理解错误
PCFG就是将CFG中的每一条规则与一个概率联系起来。在CFG转换为CNF的“去除UNIT rule”一步中,需要将A->B和B->A(也即强连通分量中的节点)都替换为A。
当某个PCFG规则中存在某个强连通分量{D,E,F,G},现在要将这4个节点都要G表示:
我的疑问在于:如果p1*p2不等于p3*p4,那么D用G来代替的概率应该取p1*p2还是p3*p4呢?
【参考材料】
https://en.wikipedia.org/wiki/Chomsky_normal_form