,
Научно-исследовательский институт системных исследований РАН, Москва
*****@***ru, *****@***ru
об одном методе построения нейронной
сети с большой памятью
Для нейронных сетей типа модели Хопифлда в качестве памяти сети обычно рассматривают ее основное состояние – множество конфигураций, доставляющих глобальный минимум энергетическому функционалу. Мы изучаем матрицу связи, с помощью которой можно в значительной мере управлять основным состоянием. Удается создавать сети, у которых вырожденность основного состояния m превосходит (или даже – значительно превосходит) размерность задачи p: m >> p. Иными словами, память сети может намного превосходить размерность задачи. Обсуждаются возникающие при этом возможности.
Ключевые слова: сеть Хопфилда, мультипликативная матрица связи
Введение
Будем изучать ассоциативную нейронную сеть Хопфилдова типа с мультипликативной матрицей связи
. (1)
Верхний диагональный блок матрицы имеет размеры 
, нижний диагональный блок (состоящий из единиц) – размеры 
; размерность матрицы равна 
; положительные вещественные числа 
и 
– свободные параметры системы; 
можно считать упорядоченными по возрастанию, а 
-мерный вектор 
нормировать на :
. (2)
Матрица (1) обобщает матрицу связи, рассматривавшуюся в работе [1].
Нейронная сеть с матрицей связи (1) определена на множестве 
-мерных конфигурационных векторов 
, где 
. Легко показать, что неподвижными точками сети (а именно они нас интересуют) могут быть только такие конфигурации, у которых последние 
координат равны друг другу; например, неподвижным точкам можно придать вид 
. Варьируемая часть этих конфигураций, которую нам и предстоит определить, является -мерным вектором: 
. Все дальнейшие рассмотрения будем вести на языке -мерных векторов 
, 
и т. д., памятуя, что полученные результаты в конечном итоге должны переводиться на -мерный язык с помощью соотвествия: 
. И последнее, о чем необходимо условиться: удобнее изучать не минимумы энергетического функционала 
, каковыми являются все неподвижные точки сети, а максимумы обратной энергии 
. Используя физическую терминологию, будем называть основным состоянием -конфигурации, доставляющие функционалу 
глобальный максимум.
1. Основное состояние сети
Легко видеть, что с точностью до несущественных членов выполняется
.
Значение при фиксированном определяется только скалярным произведением и . Чтобы придать полученному выражению обозримый вид, введем косинус угла между р-мерными векторами и :
, где 
.
Тогда
.
Распределим все 
-конфигураций по классам 
, объединив в каждый класс те конфигурации, скалярные произведения которых с вектором одинаковы. Будем называть такие классы эквидистантными, поскольку конфигурации из класса отстоят от вектора на одно и то же расстояние. На всех 
значение 
одинаково.
Состав классов и их число определяются исключительно симметрией вектора . Например, в [1] изучался случай, когда все координаты вектора одинаковы: 
. В этом случае класс состоит из -конфигураций, у которых в точности 
координат равны «-1»: для всех таких конфигураций 
. Число конфигураций в классе равно 
, а число различных классов равно 
(
).
Удобно пронумеровать классы в порядке убывания отвечающих им значений косинуса, начав нумерацию с 0:
, (3)
. (4)
Легко сообразить, что для любого 
справедливо
, 
.
В случае, когда число различных классов четно (
), значения косинусов монотонно убывают до своего наименьшего положительного значения 
, после чего косинусы становятся отрицательными:
.
Ни один из косинусов этой последовательности не равен 0. Напротив, в случае четного 
одно из значений косинуса в (3) равно 0, а сама последовательность (3) принимает вид:
.
В этом случае конфигурации класса 
ортогональны вектору .
Итак, при фиксированном имеется 
различных значений функционала:
. (5)
Чтобы отыскать глобальный максимум F-функционала, необходимо определить наибольшую из величин 
(5). Оказывается, это можно сделать в общем виде, воспользовавшись тем, что как функции параметра величины (5) представляют собой семейство прямых линий – анализировать семейство прямых линий несложно. Поскольку нас интересует максимум F-функционала, необходимо разобраться в том, какая из прямых при данном значении проходит выше всех остальных прямых. Детальный анализ семейства прямых линий (5) позволяет сформулировать следующий результат.
Теорема. Когда монотонно возрастает от 0 до бесконечности, основное состояние 
-функционала последовательно совпадает с эквидистантыми классами 
(4):
.
Перестройка основного состояния 
происходит в точке
. (6)
Если 
, то по этой схеме одна за другой произойдут все 
перестроек основного состояния – в этом случае 
. Если же 
, перестройки основного состояния прекратятся в тот момент, когда знаменатель в (6) станет отрицательным – когда выполнится 
.
Сделаем несколько замечаний.
Первая точка перестройки основного состояния гарантированно больше ½: 
. Пока 
, основное состояние функционала принадлежит классу 
(в предположениях (2) класс состоит всего из одной конфигурации: 
). Когда переваливает через критическое значение 
, основное состояние перескакивает в класс 
(который может состоять как из одной конфигурации - если все различны, - так и из нескольких). И так далее: слева от критической точки 
основным состоянием является класс 
, а справа от точки - класс . Заметим, что когда равен критическому значению , основное состояние состоит из объединения классов и .
С помощью параметра 
регулируется число перестроек основного состояния, которые могут произойти при неограниченном увеличении . Если выбрать достаточно большим, чтобы , то произойдут все перестроек основного состояния. Если же мы хотим, чтобы произошло только 
перестроек, необходимо взять таким, чтобы выполнялось: 
. Легко сообразить, что в любом случае выполняются неравенства: 
, и 
.
Большая часть изложенных результатов была анонсирована еще в [1]. Рассмотрим, как их можно использовать для создания сети с большой памятью.
2. Нейронная сеть с заданной памятью
В качестве памяти сети обычно рассматривают ее основное состояние. Это связано с тем, что чем глубже минимум, тем из больших искажений данную конфигурацию можно восстановить – тем выше ее помехоустойчивость. И для Хеббовской матрицы связи [2], и для проекционной матрицы [3], в качестве памяти сети выступает именно основное состояние системы. Мы тоже будем придерживаться этого правила.
Пусть 
– набор р-мерных конфигураций, которые мы хотим сделать основным состоянием сети. Будем называть эти исходные конфигурации паттернами. Результаты предыдущего раздела позволяют сформулировать следующий рецепт.
Необходимо:
а) отыскать р-мерный вектор , равноудаленный от всех паттернов 
, превратив набор паттернов в эквидистантный класс вида (4);
б) определить номер 
этого класса в упорядоченной последовательности (3) и выбрать внутреннюю точку интервала 
, где вычисляются по формуле (6) при фиксированном значении ;
в) построить с найденными значениями , 
и матрицу 
вида (1). Ее основным состоянием будут 
-мерных конфигураций, у которых последние координат равны 1, а -части, образованные первыми координатами, совпадают с исходными паттернами.
Программу, изложенную в A)-C), легко осуществить, когда паттерны линейно независимы. Сначала мы рассмотрим этот случай, а затем обсудим возможности, возникающие для линейно зависимых паттернов.
1. Линейно независимые паттерны. В этом случае в качестве вектора можно использовать сумму -мерных векторов базиса 
, двойственного к 
:
; (7)
здесь 
есть символ Кронекера, а сумму векторов 
следует должным образом отнормировать. Построение базиса , двойственного к – хорошо формализованная процедура, легко выполняемая с помощью псевдообратной матрицы [3], [4]. Очевидно, что вектор (7) имеет одинаковые скалярные произведения со всеми паттернами 
- что и требуется в п. A). (Эти скалярные произведения положительны.)
Для выполнения п. B), вообще говоря, необходимо проделать очень большую вычислительную работу. Сначала придется вычислить скалярные произведения всех конфигураций с вектором , затем эти числа необходимо упорядочить, и отыскать в полученной числовой последовательности кусочно-постоянные интервалы. Каждый такой интервал отвечает определенному эквидистантному классу (4). Необходимо определить порядковый номер того класса , с которым совпадает набор исходных паттернов . Теперь, зная 
и 
, можно по формуле (6) вычислить граничные точки интервала , внутри которого следует выбирать точку . Только после этого можно будет построить искомую матрицу 
.
Ясно, что из-за объема вычислений эту программу просто невозможно реализовать на компьютере уже для 
. Можно, однако, не заниматься отысканием номера класса , составленного из исходных паттернов, а воспользоваться известным нам значением косинуса угла между паттернами и вектором : 
. Очевидно, что точка
будет внутренней точкой интервала 
: 
. Зная эту точку, можно выполнить предписания п. С). Поскольку, по построению значение положительно, для создания матрицы можно обойтись минимальным значением параметра : 
.
Итак, с помощью мультипликативной матрицы связи (1) любой наперед заданный набор линейно независимых паттернов можно превратить в основное состояние сети. Естественно, число паттернов не может превышать их размерности р. Получается, что для линейно независимых паттернов рассматриваемый подход не уступает нейронной сети с проекционной матрицей связи (в этом случае тоже паттерны должны быть линейно независимыми, и их должно быть не больше р). Однако, это не совсем так: две эти матрицы демонстрируют одинаковые результаты, только когда число паттернов равно (или приблизительно равно) размерности р: 
. Компьютерные эксперименты показывают, что когда 
проекционная матрица дает лучшие результаты. Поясним, что имеется в виду.
Для мультипликативной и проекционной матриц связи в компьютерном эксперименте исследовались области притяжения паттернов. Оказалось, что при максимально возможном числе паттернов 
, размеры областей притяжения для обеих матриц практически совпадают. (Добавим, что области притяжения в этом случае сравнительно малы, и заметно меньше областей притяжения, когда используется Хеббовская матрица связи.) Если мы станем уменьшать число паттернов, то для мультипликативной матрицы ничего не изменится – для нее размер областей притяжения почти не зависит от 
. А для проекционной матрицы связи уменьшение числа паттернов сопровождается улучшением качества распознавания: области притяжения паттернов при этом заметно увеличиваются. Конечно, наибольший интерес представляет случай максимально возможного числа паттернов , и здесь обе матрицы эквивалентны. Зато мультипликативная матрица позволяет продвинуться в область 
, где подход, основанный на проекционной матрице связи, бессилен. Поясним, что имеется в виду.
2. Случай m > p. Теперь паттерны будут линейно зависимыми и применение алгоритма A)-C) невозможно. Однако и в такой ситуации нередко можно указать вектор , равноудаленный от исходного набора паттернов. Например, в упоминавшемся выше примере из работы [1], равноудаленными от вектора 
являются те -конфигурации, у которых в точности координат равны «-1». Число конфигураций в таком классе 
, и для 
подобное во много раз превосходит .
Этот пример указывает нам общий подход к исследованию того, какие именно наборы конфигураций могут быть объединены в эквидистантные классы, и от какого вектора они будут равноудалены. Рассмотрим стандартный р-мерный гиперкуб с ребром длины 2, центр которого совмещен с началом координат. Радиус-векторы, проведенные в вершины гиперкуба, являются р-мерными -конфигурациями. В качестве вектора необходимо рассмотреть все возможные симметричные направления в этом гиперкубе, и для каждого исследовать – как именно р-мерные -конфигурации распределяются по эквидистантным классам. Это исследование даст нам полный список эквидистантных классов , возможных для размерности р.
Таким образом, вопрос о распределении конфигураций по эквидистантным классам тесно связан со свойствами симметрии -мерного гиперкуба. Большую роль в исследовании симметрии гиперкуба играет теория групп (см. в [5] о точечных группах). Мы рассчитываем использовать методы теории групп для отыскания всех эквидистантных классов для произвольной размерности р.
Чтобы составить себе представление о том, много ли существует больших по размеру эквидистантных классов? – мы проделали следующий компьютерный эксперимент. Для данной размерности р выбирали случайный симметричный вектор , а затем все р-мерные -конфигурации распределяли по классам, равноудаленным относительно . Всякий раз при этом подсчитывалось:
– общее число эквидистантных классов ;
– средняя длина класса , приведенная к размерности задачи;
– общее число «больших» классов , размер которых больше размерности , а также общее число 
конфигураций, попавших в «большие» классы;
– средняя длина «большого» класса , приведенная к размерности задачи.
Для каждой размерности эти характеристики усреднялись по 5000 случайных испытаний. Интересно было определить максимально возможное значение 
– каков наибольший размер эквидистантного класса? Поэтому, для каждой размерности определяли еще и
– наибольший размер эквидистантного класса. По понятным причинам размерность могла быть не очень большой: 
. Полученные графики показаны на рис.1.
Рис. 1. Результаты компьютерного эксперимента по определению числа
эквидистантных классов и их размеров (см. текст)
Левая верхняя панель рисунка свидетельствует о том, что с ростом растет и общее число эквидистантных классов (штриховая линия), и число «больших» классов , размер которых больше размерности задачи (сплошная линия). На левой нижней панели показано отношение 
. Видно, что для больших не меньше половины эквидистантных классов являются «большими».
Правая верхняя панель показывает, как от размерности зависит приведенный средний размер эквидистантного класса 
(штриховая линия), и приведенный средний размер «большого» класса (сплошная линия). Нас больше всего интересует именно . Мы видим, что для размерностей 
приведенный средний размер ведет себя как р: 
. Следовательно, средний размер «большого» эквидистантного класса по порядку величины равен 
. Любой такой класс с помощью мультипликативной матрицы может быть сделан основным состоянием сети. Наконец, график на правой нижней панели свидетельствует о том, что для больших значений р максимальный размер эквидистантного класса может на порядки превосходить размерность задачи.
выводы
Результаты эксперимента свидетельствуют о том, что с помощью мультипликативной матрицы (1) можно конструировать сети с очень большой памятью. Конечно, трудно рассчитывать на то, что подобным простым приемом удастся превращать в основное состояние любой набор конфигураций. Тем не менее, представляется полезным выяснить границы применимости всего подхода.
Работа выполнялась при финансовой поддержке программы Президиума РАН (проект 2.15) и Российского Фонда Фундаментальных Исследований (грант ).
Список литературы
1. . Высокосимметричные нейронные сети Хопфилдова типа. Теоретическая и математическая физика, 1999. Т.118(1). С. 133-158.
2. J. Hertz, A. Krogh, R. Palmer. Introduction to the Theory of Neural Computation. Massachusetts: Addison-Wesley, 1991.
3. L. Perzonnas, I. Guyon, G. Dreyfus. Collective computational properties of neural networks: new learning mechanisms.// Phys. Re., 1986. A34. Р..
4. Т. Кохонен. Ассоциативная память. М.: Мир, 1980.
5. . Теория групп и ее применение в физике. М.: ГИТТЛ, 1957.
