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

7.6. Большие конфигурации — аналитические результаты

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

множестве состав имеющих показатель К-Аналогично показатели входных связей могут принимать только значения и через мы будем обозначать (в этом разделе не обозначает образующей!) количество входных связей с показателем

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

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

описанная в разд. 7.4 и обсуждавшаяся в связи с (7.5.1).

Когда размер выборки стремится к бесконечности, величины возрастают пропорционально:

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

Вдобавок к (абсолютным) частотам связей мы будем пользоваться относительными частотами связей (показателей)

и маргинальными частотами связей (показателей)

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

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

Покажем теперь, что топология больших конфигураций в должны удовлетворять (7.6.2), обладает

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

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

Доказательство. Сначала покажем, что система (7.6.7) имеет по крайней мере одно решение. Будем предполагать, что строго положительны, что возможно для некоторых регулярностей. Отметим, что — выпуклое и компактное множество. Это пригодится нам в дальнейшем.

Очевидно, что все функции

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

Если является решением, то мы можем записать его в «мультипликативной форме»

так что

Отметим, что в силу (7.6.6). Следовательно,

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

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

Рассмотрим функцию с аргументом

и значениями в виде вектора с компонентами

при

для следующих аргументов. Построим матрицу Якоби в блочной форме

так что

Аналогично при

а также при

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

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

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

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

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

Здесь Начнем с некоторого значения в указанной области и последуем вдоль траектории (7.6.23). Положив

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

или

так что

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

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

имеем

что в свою очередь означает, что

и мы показали, что система уравнений (7.6.7) имеет решение. Позже мы покажем, что это решение единственное.

Если конфигурация с имеет (абсолютные) частоты связей то ее вероятность равна

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

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

где изменилась так, чтобы включить факториалы из числителей (7.6.30).

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

(кликните для просмотра скана)

и аналогично для Объединяя все эти множители вместе, мы получаем для множителя в

так что -множители взаимно уничтожаются. Теперь рассмотрим

обращаясь к пяти произведениям в правой части (7.6.32). Мы уже видели по (7.6.42), что Например, при

Внутренняя сумма стремится к

Аналогичным образом для мы получаем внутреннюю сумму

Для мы не получили минуса, который присутствует в выражении для однако, сравнивая (7.6.45) и (7.6.46), мы видим, что оба выражения имеют одну и ту же аналитическую форму при обоих знаках

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

выражению:

Если ввести обозначение то этот результат можно несколько упростить.

Пусть для таких, что сумма

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

мы получаем

Полагая в (7.6.50), мы имеем

Теперь выберем такими, чтобы они удовлетворяли

стеме уравнений (7.6.7), что, как нам известно, возможно. Тогда

выражение в квадратных скобках (7.6.51) сводится к

так что

С другой стороны, дифференцируя еще раз и воспользовавшись соотношением в (7.6.49), мы получаем

После некоторых упрощений мы приводим это выражение к

где равенство имеет место только при

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

так что

Здесь соответствует решению некоторой точке Если и и оба являются решениями системы уравнений (7.6.7), то мы можем выбрать в качестве и в качестве или в качестве и в качестве Но тогда если не равно то (7.6.57) приводит к противоречию; решение системы (7.6.7) должно быть единственным.

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

Полное число -точек ограничено величиной

С другой стороны, если так что для некоторых будет выполнено

то предельное отношение (7.6.57) показывает, что

и с использованием оценки (7.6.59) мы получаем

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

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

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

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

Замечание 2. Возможно ли доказать справедливость закона больших чисел для статистической топологии в более «подробном»

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

Замечание 3. Доказательство устанавливает справедливость утверждения, но не объясняет причины наблюдающегося предельного поведения. Хотелось бы достичь лучшею интуитивного понимания этой своеобразной предельной теоремы.

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