Извлечение вероятностей и наиболее вероятного разбора дерева из Cyk - PullRequest
Новая
       56

Извлечение вероятностей и наиболее вероятного разбора дерева из Cyk

0 голосов
/ 11 мая 2018

Чтобы понять алгоритм cyk, я работал с примером: https://www.youtube.com/watch?v=VTH1k-xiswM&feature=youtu.be.

Результат которого:

enter image description here

Как извлечь вероятности, связанные с каждым анализом, и извлечь дерево наиболее вероятного анализа

1 Ответ

0 голосов
/ 15 мая 2018

Это две различные проблемы для PCFG:

  • распознавание : относится ли предложение к языку, сгенерированному CFG?(вывод: да или нет)
  • синтаксический анализ : какое дерево наивысшего балла для этого предложения?(вывод: дерево разбора)

Видеоролик об алгоритме CKY, связанный с вопросом, имеет дело только с проблемой распознавания.Чтобы выполнить задачу синтаксического анализа одновременно, нам нужно (i) поддерживать оценку каждого элемента синтаксического анализа и (ii) отслеживать иерархические отношения (например, если мы используем правило S -> NP VP: мы должны отслеживать, какой NPи какой VP используется для прогнозирования S).

Обозначения:

  • A элемент синтаксического анализа [X, i, j]: s означает, что существует узел, помеченный X охватывающим токеном *С 1021 * 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)

    Gloss: если есть 2 парсингаэлементы [X, i, k] и [Y, k, j] на графике и правило Z -> X Y на грамматике, тогда мы можем добавить [Z, i, j] к графику.

Цель взвешенного анализазаключается в выводе элемента синтаксического анализа [S, 0, n]:s (S: аксиома, n: длина предложения) с наивысшей оценкой s.

Псевдокод для всего алгоритма 

# 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 |это размер грамматики.
  • Алгоритм предполагает, что грамматика находится в Нормальной форме Хомского
...