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

7.3. Динамика конфигураций

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

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

Марковское условие означает, что развитие событий в момент t (теперь мы считаем t непрерывным) зависит только от состояния в настоящем времени и не зависит от прошлого.

Динамика: Будем считать, что в интервале времени справедливо следующее:

В 3а) мы имеем переход к положительной окрестности а в 3б) — переход к отрицательной окрестности . Функции выборки этого стохастического процесса (или, скорее, его сепарабельной версии) будут кусочно-постоянными, и скачки, как говорилось в предыдущем разделе, будут «маленькими».

Логическая непротиворечивость требует, чтобы

где

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

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

Начиная от исходной регулярной конфигурации при описанная выше динамика приводит к вероятностной мере на Что происходит при стремлении к бесконечности? Ответ дает следующая теорема.

Теорема 7.3.1. При вероятностная мера стремится к пределу Р, который является единственной равновесной мерой на

Доказательство. Поскольку конечно, мы

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

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

если или равна

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

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

Программа моделирования, написаная на языке приведена в приложении в конце главы. Функция генерирует число, иравый аргумент, образующих. Арности хранятся в -матрице, первая колонка содержит входные арности, вторая — выходные. Арности выбираются случайно (при равномерном распределении) в диапазоне от 1 до и соответственно. Значения х-признакам присваиваются при вызове функции (см. ниже). Пустая матрица отводится для того, чтобы позже поместить туда замкнутую связь в показатели выходных и входных связей хранятся соответственно в матрицах из строк и столбцов и из строк и столбцов. Эти показатели вычисляются, как и было описано в разд. 7.2.

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

от 0 до 20. Эта форма была выбрана произвольно, и, если нужно, ее можно легко изменить. То же самое касается (7.3.7) и (7.3.8).

У функции правый аргумент и левый аргумент Она вычисляет

Функция вычисляет

Функция дает

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

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

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

Эта функция должна быть выполнена до выполнения правый аргумент которой является результатом Функция вычисляет соединенные компоненты с использованием алгоритма поиска в глубину, см. , а также Примечания А).

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

Рис. 7.3.1 (см. скан)


и однородной стратегии по отношению к связям, как в (7.2.9.). Получается состав показанный на рис. 7.3.1. Численные значения округлены.

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

Результатом является конфигурация, представленная на рис. 7.3.2. Были установлены только 3 связи, две из них — от образующих с выходной арностью, равной 1. Это естественно, поскольку большие значения выходных арностей приводят к меньшим показателям выходных связей (при однородной стратегии)

Рис. 7.3.2 (см. скан)

Рис. 7.3.3 (см. скан)


и меньшая мощность идет на доминирование над остальными образующими

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

компоненты (1, 4), (2, 6, 10), (7, 8, 9). Остальные образующие изолированы. Неизолированные управляющие — это 4, 10, 8, После еще 30 итераций мы получаем с (50) на рис. 7.3.4. Было установлено еще одно соединение, а именно в паре связей (3,1) —? (5,1). Раскрылось соединение (8,1) — (7,1).

Рис. 6.4.2 (см. скан)

Рис. 7.3.5 (см. скан)

После выполнения еще 80 итераций мы получаем с (130) на рис. 7.3.5. Два соединения раскрылись, а именно в парах связей и . С другой стороны, замкнулись пары связей Теперь у

нас только три компоненты: (1, 3, 4, 5) с управляющей 4, (2, 6, 7, 10) с управляющей 10 и (8,9) с управляющей 8. Изолированных образующих не осталось. Заметим, что вторая компонента имеет древовидное соединение. Наблюдаемое состояние


Рис. 7.3.6 (см. скан)

Рис. 7.3.7 (см. скан)


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

После выполнения еще 100 итераций мы получаем с представленную на рис. 7.3.6. Раскрылись пары связей а замкнулись (7,1) — (5,1) и Теперь у нас четыре компоненты, а именно (1,3) с управляющей 1, (2, 6, 10) с управляющей 10, (4,8,9) с управляющей 4 и (5,7) с управляющей 7.

На рис. 7.3.7 — 7.3.9 мы привели некоторые статистические показатели конфигурации как функции времени. На рис. 7.3.7 показано число соединенных связей, на рис. 7.3.8 — число компонент,

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

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

Рис. 7.3.8 (см. скан)

Рис. 7.3.9 (см. скан)

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

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

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