Введение

Теория грамматик для моделирования символьных строк берет начало в работах по вычислительной лингвистике, целью которых было понимание структуры естественных языков.

Связь с скрытыми моделями Маркова

Модели PCFG расширяют контекстно-свободные грамматики так же, как скрытые марковские модели расширяют регулярные грамматики. Алгоритм Inside-Outside является аналогом алгоритма Forward-Backward. Он вычисляет общую вероятность всех разборов, согласующихся с заданной последовательностью, на основе некоторой PCFG. Это эквивалентно вероятности генерации последовательности данной PCFG и интуитивно представляет собой меру соответствия последовательности заданной грамматике. Алгоритм Inside-Outside используется в параметризации модели для оценки априорных частот, наблюдаемых в обучающих последовательностях, в случае РНК. Варианты динамического программирования алгоритма CYK находят наиболее вероятный разбор (Viterbi-разбор) последовательности РНК для модели PCFG. Этот разбор является наиболее вероятным выводом последовательности данной PCFG.

Граматическая конструкция

Контекстно-свободные грамматики представляются как набор правил, вдохновлённых попытками моделирования естественных языков. (Или сумма) всех весов правил в дереве. Вес каждого правила учитывается столько раз, сколько раз правило используется в дереве. Особым случаем WCFG являются PCFG, где веса представляют собой (логарифмы) вероятностей. Расширенная версия алгоритма CYK может быть использована для поиска "наименее весомого" (минимального по весу) вывода строки для заданной WCFG. Когда вес дерева является произведением весов правил, WCFG и PCFG могут выражать один и тот же набор распределений вероятностей. Как следствие, большинство применений теории формальных языков к анализу белков в основном ограничивались созданием грамматик с меньшей выразительной силой для моделирования простых функциональных паттернов, основанных на локальных взаимодействиях. Поскольку белковые структуры обычно демонстрируют зависимости более высокого порядка, включая вложенные и перекрестные связи, они явно превосходят возможности любой контекстно-свободной грамматики.