Главная arrow книги arrow Копия Глава 23. arrow Вероятностные контекстно-свободные грамматики
Вероятностные контекстно-свободные грамматики

В моделях n-элементных сочетаний используются статистические данные о совместном появлении элементов в текстовой совокупности, но эти модели не позволяют учитывать грамматические связи на расстояниях, превышающих п. В качестве альтернативной языковой модели может служить вероятностная контекстно-свободная грамматика, или PCFG1 (Probabilistic Context-Free Grammar), которая представляет собой такую грамматику CFG, где каждое правило подстановки имеет связанную с ним вероятность. Сумма вероятностей по всем правилам с одной и той же левой частью равна 1. Грамматика PCFG для части грамматики языкаприведена в листинге 23.2.

Листинг 23.2. Вероятностная контекстно-свободная грамматика (PCFG) и словарь для части грамматики языка. Числа в квадратных скобках показывают вероятность того, что вместо символа в левой части правила будет выполнена подстановка правой части соответствующего правила

В модели PCFG вероятность строки, Ρ (words), представляет собой сумму вероятностей деревьев синтаксического анализа этой строки. А вероятность данного конкретного дерева представляет собой произведение вероятностей всех правил, на основании которых сформированы узлы этого дерева. На рис. 23.1 показано, как вычислить вероятность некоторого предложения. Такую вероятность можно вычислить, применяя синтаксический анализатор диаграмм CFG для перечисления возможных вариантов синтаксического анализа, а затем складывая полученные вероятности. Но если нас интересует только наиболее вероятный вариант синтаксического анализа, то перебор всех маловероятных вариантов представляет собой бесполезную трату времени. Для эффективного поиска наиболее вероятного варианта синтаксического анализа может использоваться одна из разновидностей алгоритма Витерби или же какой-то метод поиска по первому наилучшему совпадению (такой как А*).