Главная > Распознавание образов > Лекции по теории образов: Регулярные структуры
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

7.4. Система в равновесии

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

Теорема 7.4 1. Для регулярной конфигурации плотность равновесного распределения на имеет вид

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

(при другом значении ) — это плотность равновесного распределения. Вспомним, что равновесное решение для динамической системы определяется однозначно. Уравнения равновесия имеют вид

где сумма берется по всем с, так что и

Согласно (7.3.1), выражено через и мы можем записать

где сумма берется по

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

где штрих у произведений означает, что они не включают и где присутствие объясняется тем, что

, а — членом в (7.4.5), поскольку, согласно , связь замкнута.

Однако в правой части (7.4.3) мы будем иметь некоторую Благодаря этому появится член

где множитель объясняется тем, что замкнута согласно появляется благодаря связи, раскрываемой, чтобы получить с. Но (7.4.6) и (7.4.7) совпадают.

Аналогичным образом можно рассуждать, когда так что для получения с из с нужно замкнуть связь. В обоих случаях мы встречаем те же члены в обеих частях (7.4.3), так что равенство выполняется.

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

Удобно записать (7.4.1) в виде

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

Замечание. Если ввести энергию взаимодействия

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

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

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

Возвращаясь к (7.4.8), заметим, что могут принимать только определенные значения. Обозначим их через

пользуемся следующими частотами связей:

Тогда имеем

Эта форма окажется очень полезной в разд. 7.6.

Рассмотрим теперь усредненную по времени величину поведение которой в ходе моделирующего эксперимента показано на рис. 7.3.9,

Поскольку представляет собой (по крайней мере асимптотически) стационарный эргодический процесс, то, согласно индивидуальной эргодической теореме (7.4.14), он сходится, почти наверное, к пределу

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

Следует отметить, что предел (7.4.15) является также энтропией динамической системы.

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

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

Теорема 7.4.2. Меры на и соответственно имеют плотности такие, что

Доказательство. Из выражения (7.4.1) немедленно получаем

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

и в силу (7.4.1) между вероятностями устанавливается следующее отношение:

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

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

в противном случае — нет.

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

Лемма 7.4.1. Подобные конфигурации равновероятны.

Доказательство. Если подобны, то существует перестановка такая,

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

так как Следовательно, показатели сродства двух конфигураций совпадают и из (7.4.10), (7.4.11) получаем что и требовалось доказать.

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

Лемма 7.4.2. Нестабильность с описывается выражением

Доказательство непосредственно следует из (7.3.2).

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

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

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

где если соединяется с в противном случае. Соединитель а содержит все соединения в , которые не участвовали в предыдущих произведениях. Чтобы убедиться в этом, рассмотрим произвольную пару связей открытых или нет в а. Если то может появиться в качестве множителя в (7.4.8) только, когда Тогда этот множитель принадлежит в (7.4.23). С другой стороны, если не принадлежит никакому то либо открыта, так что не появляется в (7.4.8), либо не является элементом никакого Отсюда мы получаем разложение в (7.4.23). Однако тогда связность связей описывается множителем и мультипликативная форма (7.4.23) устанавливает условную независимость.

Замечание 1. Связи, конечно, не являются стохастически независимыми при (7.4.8). Это можно легко продемонстрировать на простых примерах. Лемма 7.4.3 дает нам более слабую (условную) независимость. Нам не известно, является ли условная независимость, описанная в лемме, также достаточным условием для выполнения (7.4.8).

Замечание 2. По-видимому, было бы соблазнительно считать, что маргинальная вероятность замкнутости пары связей равна

Это не так. Однако мы полагаем, без доказательства, что (7.4.24) выполняется асимптотически при малых

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

Другими словами, мы выберем моду в качестве типичного представителя. Согласно (7.4.10) и (7.4.11), мы должны решить

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

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

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

Рис. 7.4.1

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

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

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

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

Читатель, знакомый со статистической механикой, и в частности с моделями Бозе—Эйнштейна и Ферми—Дирака, заметит сходство с этим подходом к выбору представителя.

<< Предыдущий параграф Следующий параграф >>
Оглавление