Как предсказать вероятность предложения?

Question

Как определить вероятность предложения "что такое кот"? с ассоциированным ПКФГ:

Rule , Probability
S -> NP VB
NN -> CAT , 1
DT -> what , 1
VB->is , .5
VB->be , .5

Как этот pcfg с предложением можно представить как скрытую марковскую модель?

Каждый узел в модели "что", "есть", "a", "кошка"? Как смоделировать вероятность соединения между узлами из ПКФГ?

Answer 1

PCFG определяет (i) распределение по деревьям разбора и (ii) распределение по предложениям.

Вероятность дерева разбора , заданного PCFG, равна:

где дерево разбора t описывается как мультимножество правил r (это мультимножество, поскольку правило можно использовать несколько раз для получения дерева).

Чтобы вычислить вероятность предложения , вы должны рассмотреть все возможные способы выведения предложения и суммировать их вероятности.

, где означает, что строка терминалов (доходность) t является предложением s .

В вашем примере вероятность "что такое кот" равна 0, потому что вы не можете сгенерировать ее с помощью своей грамматики. Вот еще один пример с игрушечной грамматикой:

Rule            Probability
S -> NP VP      1
NP -> they      0.5
NP -> fish      0.5
VP -> VBP NP    0.5
VP -> MD VB     0.5
VBP -> can      1
MD -> can       1
VB -> fish      1

Предложение "они могут ловить рыбу" имеет два возможных дерева разбора:

(S (NP they) (VP (MD can) (VB fish)))
(S (NP they) (VP (VBP can) (NP fish)))

с вероятностями:

S   NP    VP     MD   VB
1 * 0.5 * 0.5 *  1  * 1 = 1 / 4

и

S   NP    VP     VBP   NP
1 * 0.5 * 0.5 *  1  *  0.5  = 1 /8

поэтому его вероятность - это сумма или вероятности обоих деревьев разбора (3/8).

Оказывается, что в общем случае вычислительно слишком дорого перечислять каждое возможное дерево разбора для предложения. Тем не менее, существует алгоритм O (n ^ 3) для эффективного вычисления суммы: алгоритм изнутри-снаружи (см. Стр. 17-18), pdf от Michael Collins.

Редактировать: исправленные деревья.