Е. Миркес - Учебное пособие по курсу «Нейроинформатика»

1. ( x i, v i ) = ς ij ; ς ij = 0, при i ≠ j ; ς ij= 1 при i = j;

2. v j ∈ L ({ x i }).

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

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

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

(6)

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

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

(7)

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

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

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

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

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

(8)

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

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

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

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

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

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

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

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

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

где , .

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

где F ij = G mij -1- b ic j / b 0. Поскольку матрица, обратная к симметричной, всегда симметрична получаем c i / b 0= - b i / b 0при всех i . Так как b 0≠ 0 следовательно b i= -c i .

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

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

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

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

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

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