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

Question

为了理解 cyk 算法，我研究了以下示例： https ://www.youtube.com/watch?v=VTH1k-xiswM&feature=youtu.be 。

结果是：

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

Answer 1

这是 PCFG 的两个明显问题：

• 识别：句子是否属于CFG生成的语言？（输出：是或否）
• 解析：这句话得分最高的树是什么？（输出：解析树）

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

注释：

• 解析项 [X, i, j]: s意味着有一个标记为 X 的节点跨越令牌i （包含）到j（排除），分数为s。分数是以 为根的子树的对数概率X。
• 句子是一个单词序列w_1 w_2 ... w_n。

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

1. 扫描规则（读取令牌）

   ____________________________{precondition: X -> w_i is a grammar rule
   [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
   _____________________________________{precondition: Z -> X Y is a grammar rule
   [Z, i, j]: s1 + s2 + log p(Z -> X, Y)
   

   光泽度：如果图表中有2个解析项[X, i, k]和[Y, k, j]，并且语法中有一条规则Z -> X Y，那么我们可以添加[Z, i, j]到图表中。

加权解析的目标是推导出得分最高的解析项[S, 0, n]:s（S：公理， ：句子长度） 。ns

整个算法的伪代码

# 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 ⋅ |G|) 其中 |G| 是语法的大小。
• 该算法假设语法是乔姆斯基范式