8.6. СТАТИСТИЧЕСКИЙ АНАЛИЗ

Для определения и описания переменных, представляющих случайную среду, должны быть привлечены статистические понятия и методология. В распознавании образов случайность появляется в основном в результате воздействия двух принципиальных факторов: шума, возникающего при измерении характеристик объекта, и неполноты информации о характеристиках

классов образов. В этом разделе внимание сосредотачивается на обобщении основной модели формальной грамматики распространением ее на ситуации статистического характера. Полученная в результате стохастическая модель грамматики затем может быть использована в качестве статистического аппарата в процессе распознавания.

8.6.1. Стохастические грамматики и языки

Для придания статистического характера нашим моделям грамматик весьма целесообразно воспользоваться следующим приемом — считать недетерминированными правила подстановки и ставить в соответствие каждому из них некоторую вероятностную меру. Основываясь на этом приеме, мы определяем стохастическую грамматику следующим образом:

где как и прежде, — множества нетерминалов, терминалов, правил подстановки и начальный символ соответственно, множество вероятностных мер, заданных на множестве правил подстановки Р. Основные определения неограниченной грамматики, грамматики непосредственно составляющих, бесконтекстной и регулярной грамматик остаются в силе также и для стохастических грамматик. Как и прежде, тип грамматики зависит от типа допустимых правил подстановки из множества Р.

Рассмотрим следующий процесс порождения терминальной цепочки начинающийся с

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

где — условная вероятность, поставленная в соответствие правилу при предварительном применении правил

Если распределение вероятностей, поставленных в соответствие правилу называется неограниченным; множество неограниченно, если все составляющие его распределения вероятностей неограниченны. Стохастическую грамматику называют неоднозначной, если существует

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

Множество совместно, если

Стохастический язык — это язык, порожденный стохастической грамматикой . Каждая терминальная цепочка языка должна обладать вероятностью порождения данной цепочки. Стохастический язык, порожденный стохастической грамматикой формально можно определить так:

где — множество всех терминальных цепочек, исключая пустую, порожденных грамматикой обозначение используется для обозначения выводимости цепочки из начального символа посредством соответствующего применения правил подстановки из множества Р. Короче говоря, выражение (8.6.6) означает, что стохастический язык — это множество всех терминальных цепочек, каждой из которых поставлена в соответствие вероятность ее порождения, причем все цепочки выводимы из начального символа . Вероятность порождения задается суммированием вероятностей всех различных способов порождения цепочки Заметим, однако, что при стохастический язык становится неоднозначным. Рассмотренные выше понятия иллюстрируются следующим примером.

Пример. Рассмотрим стохастическую бесконтекстную грамматику

где

Заметим, что каждому правилу подстановки поставлена в соответствие вероятность его применения. В данном случае

первое правило применяется с вероятностью в то время как второе — с вероятностью

Дважды применив первое правило, а затем один раз второе, получим последовательность

Обозначив терминальную цепочку через и используя (8.6.3), имеем

Язык, порожденный грамматикой задается в данном случае следующим образом:

Каждая цепочка имеет, как мы видим, связанную с ней вероятность . Отметим также, что эта стохастическая грамматика не является неоднозначной, так как существует всего одна последовательность правил подстановки, ведущая к каждой терминальной цепочке. В качестве упражнения в конце этой главы предлагается доказать, что множество в данном случае совместно.

В стохастических языках используются те же методы грамматического разбора, что были рассмотрены в предыдущем параграфе. Однако для облегчения процесса разбора могут привлекаться знания о вероятности применения правил подстановки. Предположим, например, что на определенном шаге процедуры восходящего грамматического разбора имеется несколько правил-кандидатов, одно из которых следует выбрать и применить. Очевидно, что правилом, имеющим наибольшую вероятность успешного применения, будет правило с наибольшей вероятностью применения для порождения анализируемой терминальной цепочки. В общем случае вероятности применения грамматических правил должны использоваться в грамматическом разборе для увеличения скорости распознавания стохастических систем.