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

Question

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

结果是：

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

Answer 1

PCFG 有两个截然不同的问题：

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

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

符号：

一个parsing item [X, i, j]: s表示有一个节点标记为X spanning token i（包含）到j（排除）得分s。得分是以X.
句子是单词序列 w_1 w_2 ... w_n。

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

扫描规则（读取令牌）
```
____________________________{precondition: X -> w_i is a grammar rule
[X, i, i+1]: log p(X -> w_i)
```
注解：如果语法中有规则X -> w_i，那么我们可以在图表中添加[X, i, i+1]项。
完成规则（自下而上创建新成分）
```
[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)
```
Gloss：如果图表中有2个解析项[X, i, k]和[Y, k, j]，语法中有一条规则Z -> X Y，那么我们可以添加[Z, i, j]图表。

加权解析的目标是推导出得分最高s的解析项[S, 0, n]:s（S：公理，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 ⋅ |G|) 其中 |G|是语法的大小。
算法假设文法在Chomsky Normal Form

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

Extract probabilities and most likely parse tree from cyk

nlp

probability

context-free-grammar

hidden-markov-models

cyk