Ортогональные сети
Для обеспечения правильного воспроизведения эталонов достаточно потребовать, чтобы первое преобразование в (5) было таким, что
Очевидно, что если проектор является ортогональным, то это требование выполняется, поскольку
при
а
по определению множества
Для обеспечения ортогональности проектора воспользуемся дуальным множеством векторов. Множество векторов
называется дуальным к множеству векторов
если все вектора этого множества
удовлетворяют следующим требованиям:
- при при
Преобразование
является ортогональным проектором на линейное пространство
Ортогональная сеть ассоциативной памяти преобразует образы по формуле
Дуальное множество векторов существует тогда и только тогда, когда множество векторов
линейно независимо. Если множество эталонов
линейно зависимо, то исключим из него линейно зависимые образы и будем рассматривать полученное усеченное множество эталонов как основу для построения дуального множества и преобразования (6). Образы, исключенные из исходного множества эталонов, будут по-прежнему сохраняться сетью в исходном виде (преобразовываться в самих себя). Действительно, пусть эталон
является линейно зависимым от остальных
эталонов. Тогда его можно представить в виде
Подставив полученное выражение в преобразование (6) и учитывая свойства дуального множества получим:
Рассмотрим свойства сети (6) [8.2]. Во-первых, количество запоминаемых и точно воспроизводимых эталонов не зависит от степени их скоррелированности. Во-вторых, формально сеть способна работать без искажений при любом возможном числе эталонов (всего их может быть до
). Однако, если число линейно независимых эталонов (т.е. ранг множества эталонов) равно
сеть становится прозрачной - какой бы образ не предъявили на ее вход, на выходе окажется тот же образ. Действительно, как было показано в (7), все образы, линейно зависимые от эталонов, преобразуются проективной частью преобразования (6) сами в себя. Значит, если в множестве эталонов есть
линейно независимых, то любой образ можно представить в виде линейной комбинации эталонов (точнее
линейно независимых эталонов), а проективная часть преобразования (6) в силу формулы (7) переводит любую линейную комбинацию эталонов в саму себя.
Если число линейно независимых эталонов меньше n , то сеть преобразует поступающий образ, отфильтровывая помехи, ортогональные всем эталонам.
Отметим, что результаты работы сетей (3) и (6) эквивалентны, если все эталоны попарно ортогональны.
Остановимся несколько подробнее на алгоритме вычисления дуального множества векторов. Обозначим через
матрицу Грамма множества векторов
Элементы матрицы Грамма имеют вид
(
-ый элемент матрицы Грамма равен скалярному произведению
-го эталона на
-ый). Известно, что векторы дуального множества можно записать в следующем виде:
где
- элемент матрицы
Поскольку определитель матрицы Грамма равен нулю, если множество векторов линейно зависимо, то матрица, обратная к матрице Грамма, а следовательно и дуальное множество векторов существует только тогда, когда множество эталонов линейно независимо.
Для работы сети (6) необходимо хранить эталоны и матрицу
Рассмотрим процедуру добавления нового эталона к сети (6). Эта операция часто называется дообучением сети. Важным критерием оценки алгоритма формирования сети является соотношение вычислительных затрат на обучение и дообучение. Затраты на дообучение не должны зависеть от числа освоенных ранее эталонов.
Для сетей Хопфилда это, очевидно, выполняется - добавление еще одного эталона сводится к прибавлению к функции H одного слагаемого
а модификация связей в сети - состоит в прибавлении к весу ij-й связи числа
- всего
операций.
В результате получим
Пусть известна
- обратная к матрице Грамма для множества из m векторов
Добавим к этому множеству вектор
Тогда матрица для обращения матрицы
методом Гаусса будет иметь вид:
После приведения к единичной матрице главного минора ранга m получится следующая матрица:
где
- неизвестные величины, полученные в ходе приведения главного минора к единичной матрице. Для завершения обращения матрицы
необходимо привести к нулевому виду первые m элементов последней строки и
-о столбца. Для обращения в ноль i-о элемента последней строки необходимо умножить i-ю строку на
и вычесть из последней строки. После проведения этого преобразования получим
где
только если новый эталон является линейной комбинацией первых m эталонов. Следовательно
Для завершения обращения необходимо разделить последнюю строку на
и затем вычесть из всех предыдущих строк последнюю, умноженную на соответствующее номеру строки
В результате получим следующую матрицу
где
Поскольку матрица, обратная к симметричной, всегда симметрична получаем
при всех i. Так как
следовательно
Обозначим через
вектор
через
- вектор
Используя эти обозначения можно записать
Матрица
записывается в виде
Таким образом, при добавлении нового эталона требуется произвести следующие операции:
- Вычислить вектор ( скалярных произведений - операций, ).
- Вычислить вектор (умножение вектора на матрицу - операций).
- Вычислить (два скалярных произведения - операций).
- Умножить матрицу на число и добавить тензорное произведение вектора на себя ( операций).
- Записать
Таким образом, эта процедура требует
операций. Тогда как стандартная схема полного пересчета потребует:
- Вычислить всю матрицу Грамма ( операций).
- Методом Гаусса привести левую квадратную матрицу к единичному виду ( операций).
- Записать
Всего
операций, что в
раз больше.
Используя ортогональную сеть (6), удалось добиться независимости способности сети к запоминанию и точному воспроизведению эталонов от степени скоррелированности эталонов. Так, например, ортогональная сеть смогла правильно воспроизвести все буквы латинского алфавита в написании, приведенном на рис. 8.1.
У сети (6) можно выделить два основных недостатка:
- Число линейно независимых эталонов должно быть меньше размерности системы
- Неинвариантностью - если два визуальных образа отличаются только своим положением в рамке, то в большинстве задач желательно объединять их в один эталон.
Оба этих недостатка можно устранить, изменив выбор весовых коэффициентов в (2).
Содержание раздела
при
).
