2.2. Синтаксические деформации

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

автомат (здесь — заданный на нетерминалах) появляется в стандартной форме с детерминированным ветвлением.

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

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

а используемое множество сегментов состояний — как Два сегмента состояний пересекаются, если

и

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

Случай 2.2.1 (автоморфные синтаксические деформации). В заданном множестве непересекающихся сегментов состояний всякому соответствует случайное отображение в где — первый и последний элементы соответственно. Деформация заданного элемента осуществляется применением этих случайных отображений к каждому содержащемуся в нем сегменту состояния независимо.

Для того чтобы убедиться в осмысленности этой процедуры, допустим, что при Может оказаться, что не содержит ни одного сегмента состояния, принадлежащего — в таком случае I остается точно таким же, каким оно было.

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

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

Подобные деформации можно рассматривать как изменения в стиле. Человек, когда он говорит или пишет, может предпочитать те или иные стилистические механизмы, выражающиеся в виде цепочек синтаксических переменных. Это не идет вразрез с правилами грамматики но изменяет стилистические параметры (см. т. 1, с. 95).

Рассмотрим в качестве примера грамматику, представленную в табл. 3.2.1, т. 1. Пусть включает два сегмента (4,6) и (4,5,6) и отображения определены следующим образом:

Поверхностные изменения, вызванные этими деформациями будут заключаться в переходе цепочек (1) и (2, 2) друг в друга, однако изменения эти зависят от того, в какой части синтаксического вывода появляется соответствующая цепочка.

В случае 2.2.1 идеальное изображение, принадлежащее в целом при приложении изменениям не подвергается. Диффузный образ, однако, определенный синтаксически управляемыми вероятностями на вообще говоря, будет преобразован в другой диффузный образ. Более того, новый диффузный образ необязательно должен принадлежать классу синтаксически управляемых вероятностей, так как критическое допущение о статистической независимости ветвления может оказаться нарушенным. Автор полагает, хотя и не доказал этого, что если разрешить Добавлять новые состояния, то новый диффузный образ можно по-прежнему рассматривать как синтаксически управляемую вероятностную меру, заданную на расширенной слабо эквивалентной грамматике. Новая грамматика необязательно должна быть стандартной формы, как в разд. 2.6 т. 1.

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

Очевидно, этот случай — сугубо исключительный.

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

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

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

Хотя подобная процедура вполне разумна, в ней не используются по существу имеющиеся у нас сведения о Структурированному подходу, свойственному общей теории образов, более свойственно непосредственное сопоставление индуцированных вероятностных мер друг с другом (см. разд. 2.1).

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

Лемма 2.2.1. В основу алгоритма, позволяющего разделить (распознать) два диффузных образа, можно положить достаточную статистику чисел где произвольная цепочка, принадлежащая множеству

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

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

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

так что

Из уравнения (2.2.9) следует, что можно записать

Эта величина для определенного наблюдаемого изображения зависит только от числа появлений Проведя группировку множителей в правой части уравнения (2.2.9), получаем, что правдоподобие полного множества изображений является функцией числа появлений. Таким образом, утверждение леммы о достаточности статистик доказано. В примере (2.2.5) необходимо подсчитать лишь

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

при соответственно. Следовательно, для соответствующего отношения правдоподобия имеем

где

Итак, алгоритм, основанный на критерии Неймана—Пирсона, позволяет распознать идеальный диффузный образ если

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

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

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

В самом деле, справедлива следующая теорема.

Теорема 2.2.1. Математическое ожидание для указанного случая равно

Доказательство. Определим индикаторную функцию как

Число появлений цепочки в заданном предложении с состояниями равно

Математическое ожидание числа появлений цепочки в заданном предложении равно

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

Тогда имеет место следующая теорема: Теорема 2.2.2. Дисперсия равна:

Доказательство.

и

Поскольку, однако, математическое ожидание первой суммы в последнем выражении равно (см. уравнение (2.2.19)). С помощью этого же приема получаем также, что

Последнее выражение можно свести к следующему:

Используя это выражение и учитывая значение определенное предыдущей теоремой, приходим к утверждению доказываемой теоремы (2.2.21).

В частном случае, когда цепочка не содержит значения так что выражение (2.2.21) упрощается:

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