3.2. Изображения в виде абстрактной последовательности

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

Рис. 3.2.1.

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

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

оно также имеет внешние связи, хотя последние не всегда явно указываются.

В известном эксперименте, проведенном Шенноном (1949), выдавались цепочки вида

Эта цепочка имеет мало общего с естественным английским языком.

Если образующие имеют на рис. 3.2.1 вид (а), указывая переходы от одной буквы к другой при «равенство», то, как известно, простой случайный источник на задает меру марковской цепи Р на (см. разд. 2.10). В данном случае образующая имеет две связи, и значениями являются буквы.

Другие цепочки, полученные в шенноновском эксперименте, имеющие вид

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

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

и аналогично для марковской цепи первого порядка —

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

Рис. 3.2.2.

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

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

Таблица 9.2.1 (см. скан)

Таблица 3.2.2 (см. скан)

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

Моделирование автомата с псевдослучайным генератором чисел дает цепочки, приведенные в табл. 3.2.2, где они следуют в порядке формирования.

Оставляя этот пример, перейдем к конечно-автоматному языку общего вида, для которого конфигурации можно представить в виде где образующей является переход из состояния в состояние с записью терминального символа Тогда естественно использовать такое правило идентификации: если с — допустимая конфигурация, отличная от , с тем же числом образующих, с теми же внешними связями и той же терминальной цепочкой. Легко проверить, что имеет все свойства правила идентификации (см. определение 3.1.1).

Это означает, что лишь первое и последнее состояния конфигурации со всеми ее терминалами могут быть доступны наблюдателю. Другими словами, он не сможет идентифицировать-вывод, если грамматика не однозначна. Чтобы получить для данного изображения, пронумеруем синтаксические переменные числами и рассмотрим все правила

составляющие множество Обозначая соответствующие вероятности через получим

или в матрично-векторном обозначении

и

Мы также вводим вектор . Тогда (3.2.3) можно переписать в виде где вектор-столбец, все компонент которого равны 1.

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

от начального состояния до конечного состояния. Общий случай может быть рассмотрен точно таким же способом.

Имея терминальную цепочку сразу можно получить

Это можно записать в виде

Чтобы распределение вероятностей было корректным, будем считать, что конечное состояние может быть достигнуто из любого состояния. Пользуясь удобным матричным представлением вероятностей, можно вывести компактные выражения для многих величин, которые необходимо будет проанализировать в части III (см. приложение).

Какова вероятность получения цепочки вида

Просуммировав (3.2.6) по всем неопределенным терминальным символам, получим вероятность

Здесь мы воспользовались соотношением Частный случай соотношения (3.2.6) получается, когда мы интересуемся тем, что происходит, если все терминалы (скажем, штук) остаются неопределенными. Тогда из (3.2.8) получаем распределение предложений по длине

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

где

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

здесь и обозначает произвольную цепочку, возможно пустую, в то время как обозначает произвольную цепочку из терминальных символов. Используя (3.2.6), выразим (3.2.12) в виде

Итак, нами доказана

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

Ситуация, предсказываемая соотношением иллюстрируется табл. 3.2.3, в которой дано наблюдаемое распределение предложений по длине в упомянутом эксперименте моделирования.

Таблица 3.2.3 (см. скан)

Таблица 3.2.4 (см. скан)

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

В данном случае естественное правило идентификации — считать идентичными те конфигурации, выводы которых начинаются с одной и той же синтаксической переменной и которые

имеют одну и ту же последовательность символов в нижних узлах. При этом гарантируется совпадение их внешних структур. Можно проверить, что действительно данное правило идентификации соответствует определению 3.1.1.

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

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

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

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

сохраняя остальные неизменными. Были сгенерированы следующие двадцать терминальных цепочек:

Уже поверхностная проверка показывает, что наблюдается тенденция к удлинению цепочек и более частому вхождению в них символа Это объясняется тем, что правило с малым скобочным вложением встречается реже, чем правило Изменение стиля в этом примере легко наблюдаемо; в более сложном примере может потребоваться более систематический анализ, и мы вернемся к этому в частях III и IV.

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

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

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

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

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

Пусть детерминированный конечный автомат со словарем, включающим слова и переменными порождает предложения при помощи правил вывода

вероятности правил и терминальные правила вывода

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

задается интересным выражением

с матрицами

и векторами

и

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

каждая из которых положительна.

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

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

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

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

Ранговая функция является удобным средством при изучении поставленного вопроса, и мы сначала приведем некоторые предварительные результаты, с которыми можно ознакомиться более подробно в работе Бушара (1967).

Теорема 3.2.2. Ранговая функция имеет следующие свойства:

б) среднее значение формального типового отношения

, оно обладает выпуклым поведением, т.е.

в) нормализованное отношение сходится в среднем к 1.

Доказательство, а) Ранговая функция неотрицательна и интегрирование по частям дает

б) Имеем

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

По виду второй суммы в (3.2.26) также ясно, что при

где - переменная, указывающая на появление предложения Однако

Но ковариации не могут быть положительными, поскольку при

Следовательно, так что в среднем.

Ранговая функция имеет некоторые свойства плотности. Интересно посмотреть, чему равно среднее этой плотности. Мы имеем

так что среднее пропорционально коэффициенту повторения Юла.

В качестве иллюстрации рассмотрим формальное типовое отношение для закона Зипфа

так что,

и

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

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

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

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

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

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

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

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

Если велико при малых то велико (см. 3.2.24), и наоборот.

Рассмотрим переменную и приводящие к ней правила вывода

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

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

Рассматривая правила в (3.2.35), заметим, что цепочки в 2,- составлены из цепочек и т.д., вероятность каждой из которых получается умножением вероятностей для и т. д. на Это означает, что

поскольку благодаря свойству детерминированности системы никакого объединения вероятностей не происходит. Если одно из состояний в правой части (3.2.35) совпадает с начальным состоянием 1, то мы получаем дополнительный член для (3.2.36):

так как мы всегда отправляемся от состояния 1. Значением служит вероятность перехода из состояния 1 в состояние Если заключительное состояние, что соответствует терминальным правилам вывода, то имеем так что если нам удается решить систему (3.2.36) при , то мы получим требуемую

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

с отрицательными константами, и т. д.

Необходимо найти (верхние) границы для (функций) для этого положим равным минимуму всех вероятностей переходов, используемых при порождении правильных предложений. Тогда для произвольного (состояний )

Следовательно, ранговые функции имеют оценки

так что

В связи с тем что растет самое большее экспоненциально, ее преобразование Лапласа для достаточно больших имеет вид

Мы будем рассматривать только такие значения Известно, что преобразование Лапласа однозначно определяет преобразованную функцию, если она задана при Тогда система (3.2.38) преобразуется к виду

или, если начальное состояние входит в правую часть (3.2.35), включается дополнительный член

Поэтому при фиксированном на (3.2.43) можно смотреть как на неоднородную систему линейных уравнений, коэффициентами

которых служат экспоненциальные функции , а их постоянные члены имеют вид либо равны 0.

Общим элементом матрицы является

если пары соответствуют возможным переходам, и

Рис. 3.2.3.

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

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

где рациональные функции экспонент .

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

Рассмотрим сначала машину с двумя словами а и состоянием, с начальным состоянием 1 и заключительным состоянием , все вероятности переходов которой равны 1/2 (см. рис. 3.2.3,а). Тогда

где Следовательно,

так что

Поведение при таково:

так что по стандартной теореме Таубера (см. Феллер (1957), том 2, гл. 8)

и ранговая функция

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

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

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

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

где все вероятности переходов предполагаются равными 1/2. Следовательно,

и окончательно

Поведение зависит от значения положительного корня уравнения

где . Он близок к 1/2, если велико. Тогда окажется регулярной в той полуплоскости, в которой

Для близких к , поведение определяется

Это означает, что

и

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