从cyk中提取概率和最有可能的解析树

Question

为了理解cyk算法，我已经完成了示例：https://www.youtube.com/watch?v=VTH1k-xiswM&feature=youtu.be。

其结果是：

​

​

如何提取与每个解析关联的概率并提取最有可能的解析树？

Answer 1

这是PCFG的两个截然不同的问题：

• recognition：句子是否属于CFG生成的语言？(产出:是或否)
• 解析：这句话的最高得分树是什么？(输出:解析树)

问题中链接的CKY算法视频只处理识别问题。为了同时执行解析问题，我们需要(i)保持每个解析项的得分，(ii)跟踪层次关系(例如，如果我们使用S -> NP VP规则:我们必须跟踪哪个NP和哪个VP用于预测S)。

符号：

• 解析项 [X, i, j]: s表示有一个节点标记为X生成令牌I(包括)到j(排除)，其得分为根植于X的子树的日志概率。
• 这个句子是一个单词w_1 w_2 ... w_n的序列。

在抽象层次上，PCFG解析可以表述为一组演绎规则：

1. 扫描规则(读取令牌) ____________________________{前提:X -> w_i是语法规则X，i，i+1: log p(X -> w_i) 光泽:如果语法中有一个规则X -> w_i，那么我们可以在图表中添加项[X, i, i+1]。
2. 完整规则(创建一个新的自下而上的成分) X，i，k: s1 Y，k，j: s2 Z -> X是语法规则Z，i，j: s1 + s2 + log p(Z -> X，Y) 光泽:如果图表中有两个解析项[X, i, k]和[Y, k, j]，语法中有一个规则Z -> X Y，那么我们可以将[Z, i, j]添加到图表中。

加权分析的目的是推导出得分最高的句法分析项目[S, 0, n]:s (S：axiom，n：句子长度)。

全算法伪码

# The chart stores parsing items and their scores
chart[beginning(int)][end(int)][NonTerminal][score(float)]

# the backtrack table is used to recover the parse tree at the end
backtrack[beginning][end][NonTerminal][item_left, item_right]

# insert a new item in the chart
# for a given span (i, j) and nonterminal X, we only need to
# keep the single best scoring item.
def insert(X, i, j, score, Y, Z, k):
    if X not in chart[i][j] or chart[i][j][X] < score             
        chart[i][j][X] <- score
        backtrack[i][j][X] <- (Y, i, k), (Z, k, j)

n <- length of sentence

for i in range(0, n):
    # apply scan rule
    insert(X, i, i+1, log p(X -> w_i)) for each grammar rule X -> w_i

for span_length in range(2, n):
    for beginning in range(0, n - span_length):
        end <- beginning + span_length

        for k in range(beginning+1, end -1):
            # apply completion rules
            for each grammar rule X -> Y Z such that 
                * Y is in chart[beginning][k]
                * Z is in chart[k][end]

                score_left <- chart[beginning][k][Y]
                score_right <- chart[k][end][Z]

                insert(X, beginning, end, log p(X -> Y Z) + score_left + score_right)

if there is S (axiom) in chart[0][n], then parsing is successful
    the score (log probability) of the best tree is chart[0][n][S]
    the best tree can be recovered recursively by following pointers from backtrack[0][n][S]
else:
    parsing failure, the sentence does not belong to the language
    generated by the grammar

一些注意事项：

• 时间复杂度为O(n^3⋅x~+)，其中\G_x是文法的大小。
• 该算法假定语法在乔姆斯基范式中。