Книга: Учебное пособие по курсу «Нейроинформатика»

Ортогональные сети

Ортогональные сети

Для обеспечения правильного воспроизведения эталонов вне зависимости от степени их коррелированности достаточно потребовать, чтобы первое преобразование в (5) было таким, что xⁱ = Pxⁱ [67]. Очевидно, что если проектор является ортогональным, то это требование выполняется, поскольку x = Px при x ?L({xⁱ}), а x^j ?L({xⁱ}) по определению множества L({xⁱ}).

Для обеспечения ортогональности проектора воспользуемся дуальным множеством векторов. Множество векторов V({xⁱ}) называется дуальным к множеству векторов {xⁱ}, если все векторы этого множества v^j удовлетворяют следующим требованиям:

1. (xⁱ, vⁱ) = ?_ij; ?_ij = 0, при i ? j; ?_ij = 1 при i = j;

2. v^j ?L({xⁱ}).

Преобразование

является ортогональным проектором на линейное пространство L({xⁱ}).

Ортогональная сеть ассоциативной памяти преобразует образы по формуле

Дуальное множество векторов существует тогда и только тогда, когда множество векторов {xⁱ} линейно независимо. Если множество эталонов {xⁱ} линейно зависимо, то исключим из него линейно зависимые образы и будем рассматривать полученное усеченное множество эталонов как основу для построения дуального множества и преобразования (6). Образы, исключенные из исходного множества эталонов, будут по-прежнему сохраняться сетью в исходном виде (преобразовываться в самих себя). Действительно, пусть эталон x является линейно зависимым от остальных m эталонов. Тогда его можно представить в виде

Подставив полученное выражение в преобразование (6) и учитывая свойства дуального множества получим:

Рассмотрим свойства сети (6) [67]. Во-первых, количество запоминаемых и точно воспроизводимых эталонов не зависит от степени их коррелированности. Во-вторых, формально сеть способна работать без искажений при любом возможном числе эталонов (всего их может быть до 2n). Однако, если число линейно независимых эталонов (т. е. ранг множества эталонов) равно n, сеть становится прозрачной — какой бы образ не предъявили на ее вход, на выходе окажется тот же образ. Действительно, как было показано в (7), все образы, линейно зависимые от эталонов, преобразуются проективной частью преобразования (6) сами в себя. Значит, если в множестве эталонов есть n линейно независимых, то любой образ можно представить в виде линейной комбинации эталонов (точнее n линейно независимых эталонов), а проективная часть преобразования (6) в силу формулы (7) переводит любую линейную комбинацию эталонов в саму себя.

Если число линейно независимых эталонов меньше n, то сеть преобразует поступающий образ, отфильтровывая помехи, ортогональные всем эталонам.

Отметим, что результаты работы сетей (3) и (6) эквивалентны, если все эталоны попарно ортогональны.

Остановимся несколько подробнее на алгоритме вычисления дуального множества векторов. Обозначим через ?({xⁱ}) матрицу Грама множества векторов {xⁱ}.

Элементы матрицы Грама имеют вид ?_ij = (xⁱ, x^j) (ij-ый элемент матрицы Грама равен скалярному произведению i-го эталона на j-ый). Известно, что векторы дуального множества можно записать в следующем виде:

где ?_ij^-1 — элемент матрицы ?^-1({xⁱ}). Поскольку определитель матрицы Грама равен нулю, если множество векторов линейно зависимо, то матрица, обратная к матрице Грама, а следовательно и дуальное множество векторов существует только тогда, когда множество эталонов линейно независимо.

Для работ сети (6) необходимо хранить эталоны и матрицу ?^-1({xⁱ}).

Рассмотрим процедуру добавления нового эталона к сети (6). Эта операция часто называется дообучением сети. Важным критерием оценки алгоритма формирования сети является соотношение вычислительных затрат на обучение и дообучение. Затраты на дообучение не должны зависеть от числа освоенных ранее эталонов.

Для сетей Хопфилда это, очевидно, выполняется — добавление еще одного эталона сводится к прибавлению к функции H одного слагаемого (x, x^m+1)?, а модификация связей в сети — состоит в прибавлении к весу ij-й связи числа x_i^m+1x_j^m+1 — всего n? операций.

Для рассматриваемых сетей с ортогональным проектированием также возможно простое дообучение. На первый взгляд, это может показаться странным — если добавляемый эталон линейно независим от старых эталонов, то, вообще говоря, необходимо пересчитать матрицу Грама и обратить ее. Однако симметричность матрицы Грама позволяет не производить заново процедуру обращения всей матрицы. Действительно, обозначим через G_m — матрицу Грама для множества из m векторов; через E_m — единичную матрицу размерности m?m. При обращении матриц методом Гаусса используется следующая процедура:

1 .Запишем матрицу размерности m?2m следующего вида: (G_m|E_m).

2. Используя операции сложения строк и умножения строки на ненулевое число преобразуем левую квадратную подматрицу к единичной. В результате получим (E_m|G_m^-1). Пусть известна G_m^-1 — обратная к матрице Грама для множества из m векторов xⁱ. Добавим к этому множеству вектор x^m+1. Тогда матрица для обращения матрицы G_m+1 методом Гауса будет иметь вид:

После приведения к единичной матрице главного минора ранга m получится следующая матрица:

где b_i — неизвестные величины, полученные в ходе приведения главного минора к единичной матрице. Для завершения обращения матрицы G_m+1 необходимо привести к нулевому виду первые m элементов последней строки и (m +1)-го столбца. Для обращения в ноль i-го элемента последней строки необходимо умножить i-ю строку на (x, x^m+1) и вычесть из последней строки. После проведения этого преобразования получим

где

b₀ = 0 только если новый эталон является линейной комбинацией первых m эталонов. Следовательно b₀ ? 0. Для завершения обращения необходимо разделить последнюю строку на b₀ и затем вычесть из всех предыдущих строк последнюю, умноженную на соответствующее номеру строки b_i. В результате получим следующую матрицу

где F_ij = G_mij^-1-b_ic_j/b₀. Поскольку матрица, обратная к симметричной, всегда симметрична получаем c_i/b₀ = -b_i/b₀ при всех i. Так как b₀ ? 0 следовательно b_i = -c_i.

Обозначим через d вектор ((x¹, x^m+1), …, (x^m, x^m+1)), через b — вектор (b₁, …, b_m). Используя эти обозначения можно записать b = G_m^-1d, b₀ = (x^m+1,x^m+1)-(d,b), b₀ = (x^m+1,x^m+1)-(d,b). Матрица G_m+1^-1 записывается в виде

Таким образом, при добавлении нового эталона требуется произвести следующие операции:

1. Вычислить вектор d (m скалярных произведений — mn операций, mn?n?).

2. Вычислить вектор b (умножение вектора на матрицу — m? операций).

3. Вычислить b⁰ (два скалярных произведения — m+n операций).

4. Умножить матрицу на число и добавить тензорное произведение вектора b на себя (2m? операций).

5. Записать G_m+1^-1.

Таким образом эта процедура требует m+n+mn+3m? операций. Тогда как стандартная схема полного пересчета потребует:

1. Вычислить всю матрицу Грама (nm(m+1)/2 операций).

2. Методом Гаусса привести левую квадратную матрицу к единичному виду (2m?+m?-m операций).

3. Записать G_m+1^-1.

Всего 2m?+m?–m+nm(m+1)/2 операций, что в m раз больше.

Используя ортогональную сеть (6), удалось добиться независимости способности сети к запоминанию и точному воспроизведению эталонов от степени коррелированности эталонов. Так, например, ортогональная сеть смогла правильно воспроизвести все буквы латинского алфавита в написании, приведенном на рис. 1.

Основным ограничением сети (6) является малое число эталонов — число линейно независимых эталонов должно быть меньше размерности системы n.

Оглавление книги