Применение локального поиска в нейронных сетях Хопфилда - Локальный поиск

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

Задача

В этом разделе рассматривается задача поиска устойчивых конфигураций в нейронных сетях Хопфилда — простой модели ассоциативной памяти, в которой большое количество элементов объединяется в сеть, а соседние элементы пытаются согласовывать свои состояния. Конкретно сеть Хопфилда может рассматриваться как ненаправленный граф G = (V, E) с целочисленным весом для каждого ребра е; каждый вес может быть как положительным, так и отрицательным. Конфигурация сети S определяется как присваивание значения -1 или +1 каждому узлу u; это значение будет называться состоянием s_u узла u. Смысл конфигурации заключается в том, что каждый узел, представляющий элемент нейронной сети, пытается выбрать одно из двух возможных состояний (“да” или “нет”; “истина” или “ложь”), и этот выбор зависит от состояния соседей. Каждое ребро сети устанавливает требование к своим конечным точкам: если и соединяется с v ребром отрицательного веса, то u и v находятся в одинаковом состоянии, а если и соединяется с v ребром положительного веса, то u и v стремятся находиться в противоположных состояниях. Абсолютное значение |w_e| обозначает силу требования; мы будем называть |w| абсолютным весом ребра е.

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

С учетом этого обстоятельства мы немного снизим уровень требований. В отношении заданной конфигурации ребро e = (u, v) называется хорошим, если устанавливаемое им требование соблюдается состояниями его конечных точек: либо w_e < 0 и s_u = s_v, либо w_e > 0 и s_u ≠ s_v. В противном случае ребро e называется плохим. Заметим, что условие “ребро e является хорошим” очень компактно выражается в следующем виде: w_es_us_v < 0. Узел u в заданной конфигурации называется реализованным, если общий абсолютный вес всех хороших ребер, инцидентных и, по крайней мере не меньше общего абсолютного веса всех плохих ребер, инцидентных u. Это определение можно записать в виде

Наконец, конфигурация называется устойчивой, если все узлы в ней реализованы.

Почему такие конфигурации называются “устойчивыми”? Термин происходит из рассмотрения сети с точки зрения отдельного узла u. Сам по себе узел u имеет выбор только между состояниями -1 и +1; как и все узлы, он хочет учесть как можно больше требований ребер (в соответствии с метрикой абсолютного веса). Допустим, узел u спрашивает: следует ли мне перейти в противоположное состояние? Мы видим, что если u изменяет состояние (при сохранении состояний всех остальных узлов), то все хорошие ребра, инцидентные u, становятся плохими, а все плохие ребра, инцидентные u, становятся хорошими. Итак, чтобы максимизировать вес хороших ребер, находящихся под его прямым управлением, узел u должен перейти в обратное состояние в том, и только в том случае, если он не реализован. Другими словами, устойчивой конфигурацией является та, в которой нет отдельных узлов, для которых были бы причины перейти в противоположное состояние.

А теперь мы приходим к основному вопросу: всегда ли в сети Хопфилда существует устойчивая конфигурация, и если да, то как ее найти?

Разработка алгоритма

Алгоритм, который будет разработан в этом разделе, доказывает следующий результат.

(12.3) У каждой сети Хопфилда имеется устойчивая конфигурация, которая может быть найдена за время, полиномиальное по n и

Вы увидите, что устойчивые конфигурации крайне естественно встречаются в качестве локальных оптимумов определенных процедур локального поиска в сетях Хопфилда. Чтобы убедиться в том, что утверждение (12.3) не так уж тривиально, стоит заметить, что оно перестает быть истинным при некоторых естественных модификациях модели. Например, представьте, что мы определяем направленную сеть Хопфилда точно так, как описано выше, но с одним исключением — каждое ребро является направленным, а каждый узел определяет, является он реализованным или нет, проверяя только те ребра, для которых он является начальным. В этом случае сеть может и не иметь устойчивой конфигурации. Для примера возьмем направленную версию сети из трех узлов, упоминавшуюся ранее: имеются три узла a, b, c, соединенные направленными ребрами (a, b), (b, c), (c, a), все ребра имеют вес 1. Если все узлы находятся в одном состоянии, все они будут нереализованными; а если состояние одного узла отличается от состояния двух других, то узел, находящийся непосредственно перед ним, будет нереализованным. Следовательно, в этой направленной сети не существует конфигурации, в которой все узлы были бы реализованы.

Очевидно, доказательство (12.3) должно где-то зависеть от ненаправленной природы сети.

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

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

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

(Состояние узлов обозначается черным или белым цветом)

Анализ алгоритма

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

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

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

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

Очевидно, для любой конфигурации S выполняется Ф(S) ≥ 0 (так как Ф(S) — сумма положительных целых чисел) и (так как в крайнем случае каждое ребро является хорошим).

Теперь предположим, что в неустойчивой конфигурации S мы выбираем узел u, который является нереализованным, и изменяем его состояние, получая конфигурацию S'. Что можно сказать об отношениях между Ф(S') и Ф(S)? Вспомним, что при переключении состояния u все хорошие ребра, инцидентные u, становятся плохими; все плохие ребра, инцидентные u, становятся хорошими; а все ребра, для которых u не является конечной точкой, остаются без изменений. Если обозначить g_u и b_u общий абсолютный вес соответственно хороших и плохих ребер, инцидентных u, то имеем

Но так как узел u был нереализованным в S, мы также знаем, что b_u > g_u; а поскольку и b_u, и g_u являются целыми числами, имеем b_u ≥ g_u + 1. Следовательно,

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

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

Затем мы изучили поведение простого итеративного алгоритма локального поиска (“перевернутую” форму градиентного спуска, так как в данном случае используется задача максимизации); при этом было обнаружено следующее:

(12.4) Любой локальный максимум в алгоритме переключения состояния, максимизирующий Ф, является устойчивой конфигурацией.

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

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