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

6.3. Исходная сеть

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

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

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

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

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

Рассмотрим некоторую сеть, состоящую из двух множеств узлов: входов с нумерацией и выходов с нумерацией Эти узлы являются ячейками сети — нейронами. Между некоторыми из -узлов и -узлов установлены синаптические связи. Связи между -узлами, так же как и связи между -узлами, отсутствуют.

Рис. 6.3.1.

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

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

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

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

Тогда средняя связность определяется как

и мы будем считать, что с увеличением Если соединено с то будем считать, что прочность этого соединения равна +1 или —1 с вероятностью 1/2 для каждого значения. Все ситуации выбора разрешаются независимо друг от друга.

Рис. 6.3.2.

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

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

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

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

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

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

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

Результат нашего анализа можно представить в виде отдельного предложения.

Предложение 6.3.1. Допустим, что при Пусть при заданном

Тогда для каждого последовательность сходится по вероятности к спектральной мере

которая зависит только от

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

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

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

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

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

где и связи между определяются начальными условиями. Отметим, что суммирование проводится не по всем значениям поскольку, например, не может равняться Рассмотрим в качестве примера случай, когда Тогда (6.3.6) принимает вид

Отметим, что некоторые группировки неосуществимы. Так, например, нельзя объединить с и оставлять в другой группе, поскольку будет равна в результате чего Один из допустимых способов группировки заключается в том, чтобы принять Обозначив индексы первой группы через и второй — через переписываем выражение (6.3.7) в следующем виде:

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

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

Лемма 6.3.1. Для каждой группировки т.е. обеспечивает точный подбор пар

Доказательство. Можно ограничить (3.6.3), удалив в первую очередь все пары в которых либо либо не связаны (отметим, что для каждого либо а, либо должны повторяться в другом множителе). Каждый раз, когда удаляются одиночные элементы, можно ограничить величину (6.3.7), исключая вместе с индексами и умножая полученную в результате сумму на С. После того как это сделано, выбираем любой и проводим по нему суммирование. Если имеется множителей

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

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

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

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

Лемма 6.3.2. Для каждой величина (6.3.7) и, следовательно, числу элементов в при

Доказательство. При заданной либо какой-то либо какой-то свободны. Пусть свободен конечно, не свободен). Тогда

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

и поскольку

то мы получаем, что

Очевидно, что такую операцию можно осуществить на каждом шаге. Следовательно, (6.3.7) .

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

Рис. 6.3.4.

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

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

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

Лемма 6.3.3. где — множество всех соединений (при заданном ), причем циферблатное представление характеризуется точным объединением в пары и отсутствием пересечений.

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

Лемма 6.3.4.

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

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

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

Случай 2. или 2. Тогда одной парой является а на остальной части циферблата, представляющей некоторую

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

Лемма 6.3.5. При мы имеем

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

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

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

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

Лемма 6.3.6. Величина сходится вероятности к

Доказательство. При заданном получаем, что

На основании неравенства Чебышева получаем следующее:

Поскольку оба члена стремятся к нулю при доказательство закончено.

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

Как и прежде, соединения будут циклическими. Напомним, что теперь Для заданной строки, суммируя вероятнности в столбцах, получаем С. Для заданного столбца сумма вероятностей по строкам дает (см. рис. 6.3.2). Будем действовать тем же способом, что и в случае . Связи, налагаемые на индексы при оценивании те же самые, за исключением того, что показатель каждой связи не будет равен 1. При каждом исключении некоторого мы получаем С, если исключение основано на суммировании по если суммирование проводится по за исключением случая, когда мы доходим до конца, поскольку Пусть

Случай произвольного трактуется так же. Подробности доказательства можно найти в отчете Гренандера и Силверстайна (1974); здесь мы приведем только результат: при справедлива следующая лемма.

Лемма 6.3.7.

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

Лемма 6.2.8. Производящая функция задаваемая как

является полностью определенной и аналитической в окрестности О на комплексной плоскости.

Доказательство. Вспомогательная функция

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

и, следовательно, лемма 6.3.8 справедлива.

Нетрудно найти в окрестности начала координат. Пусть — функция свертки с ней же, - производящая функция Тогда

и

так что

и

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

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

Определим функцию

воспользовавшись следующей теоремой (Титчмарш (1939)). Если обе аналитические в некоторой рестности 0, то

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

где контур окружает начало координат, и в нем а аналитические: При имеем

При

где определяются

Нетрудно убедиться в том, что

Следовательно, при

При мы получаем

В первую очередь рассмотрим случай можно записать как

Рис. 6.3.5.

где представлены на рис. 6.3.5. Причина присутствия в показательной функции состоит в том, что квадратный корень должен быть положителен на оси действительных чисел слева от при Из элементарной тригонометрии известно, что при Из (6.3.32) следует, что при при всех 0.

Рис. 6.3.6.

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

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

Положив получаем, что

где

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

Рис. 6.3.7.

Поскольку равномерно по 0 при то приходим к следующему:

Объединяя эти два результата, получаем

Элементарный интеграл

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

Поскольку аналитическая функция в окрестности 0, то единственное распределение, обладающее моментами

и, следовательно, определенная в предложении, однозначно задана своими моментами.

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

Нам известно, что

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

для всех Поскольку непрерывна, то при всех К

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

по вероятности.

На этом доказательство предложения заканчивается. На рис. 6.3.8 представлены графики при d = 1, 5, 10, 20. Их следует сопоставить с графиками, приведенными на рис. 6.3.3.

Рис. 6.3.8.

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

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

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