Вычислительный центр СО РАН в г. Красноярске
Рассматриваются нейронные сети ассоциативной памяти, восстанавливающие по искаженному и/или зашумленному образу ближайший к нему эталонный. Исследована информационная емкость сетей и предложено несколько путей ее повышения, в том числе - ортогональные тензорные (многочастичные) сети. Построены способы предобработки, позволяющие конструировать нейронные сети ассоциативной памяти для обработки образов, инвариантной относительно групп преобразований. Описан численный эксперимент по использованию нейронных сетей для декодирования различных кодов.
Прежде чем заниматься конструированием сетей ассоциативной памяти необходимо ответить на следующие два вопроса: "Как устроена ассоциативная память?" и "Какие задачи она решает?". Когда мы задаем эти вопросы, имеется в виду не устройство отделов мозга, отвечающих за
Принято говорить, что у человека возникла ассоциация, если при получении некоторой неполной информации он может подробно описать объект, к которому по его мнению относится эта информация. Достаточно хорошим примером может служить описание малознакомого человека. К примеру, при высказывании: "Слушай, а что за парень, с которым ты вчера разговаривал на вечеринке, такой высокий блондин?"- у собеседника возникает образ вчерашнего собеседника, не ограничивающийся ростом и цветом волос. В ответ на заданный вопрос он может рассказать об этом человеке довольно много. При этом следует заметить, что содержащейся в вопросе информации явно недостаточно для точной идентификации собеседника. Более того, если вчерашний собеседник был случайным, то без дополнительной информации его и не вспомнят.
В качестве другого примера можно рассмотреть ситуацию, когда ваша однокурсница появляется в институте с совершенно новой прической и в незнакомой вам одежде. При этом вы, тем не менее, чаще всего ее узнаете и сможете определить чем ее новый образ отличается от привычного. Можно предположить, что это происходит следующим образом. При виде ее нового облика в вашей памяти возникает ассоциация с привычным для вас. А далее сравнивая эти два облика вы можете определить отличия.
Исходя из рассмотренных примеров можно сказать, что ассоциативная память позволяет по неполной и даже частично недостоверной информации восстановить достаточно полное описание знакомого объекта. Слово знакомого является очень важным, поскольку невозможно вызвать ассоциации с незнакомыми объектами. При этом объект должен быть знаком тому, у кого возникают ассоциации.
Одновременно рассмотренные примеры позволяют сформулировать решаемые ассоциативной памятью задачи:
Очевидно, что под точным описанием объекта следует понимать всю информацию, которая доступна ассоциативной памяти. Вторая задача решается не поэтапно, а одновременно происходит соотнесение полученной информации с известными образцами и отсев недостоверной информации.
Пусть задан набор из $$m$$ эталонов - $$n$$ -мерных векторов $$\left\{ {x^i } \right\}$$. Требуется построить сеть, которая при предъявлении на вход произвольного образа - вектора x - давала бы на выходе "наиболее похожий" эталон.
Всюду далее образы и, в том числе, эталоны - $$n$$ -мерные векторы с координатами $$\pm 1$$. Эталон, "наиболее похожий" на x - ближайший к x вектор $$x^i$$. Легко заметить, что это требование эквивалентно требованию максимальности
$$\left\| {x - x^i } \right\| = \left\| x \right\|^2 + \left\| {x^i } \right\|^2 - 2\left( {x,x^i } \right) .$$
Первые два слагаемых в правой части совпадают для любых образов $$x$$ и $$x^i$$, так как длины всех векторов-образов равны $$\sqrt n$$. Таким образом, задача поиска ближайшего образа сводится к поиску образа, скалярное произведение с которым максимально. Этот простой факт приводит к тому, что сравнивать придется линейные функции от образов, тогда как расстояние является квадратичной функцией.
Наиболее известной сетью ассоциативной памяти является H (функции Ляпунова). Точки равновесия такой системы находятся в точках минимума энергии. Функцию энергии будем строить из следующих соображений:
Функция
$$$H = - {\frac{1}{2}} \sum\limits_{i = 1}^m {\left( {x,x^i } \right)^2 } + \alpha \sum\limits_{j = 1}^n {\left( {x_j^2 - 1} \right)^2 }$$$
не удовлетворяет этим требованиям строго, но можно предполагать, что первое слагаемое обеспечит притяжение к эталонам (для вектора x фиксированной длины максимум квадрата скалярного произведения $$\left( {x,x^i } \right)^2 $$ достигается при x=xi ), а второе слагаемое $$\sum\limits_{j = 1}^n {\left( {x_j^2 - 1} \right)^2 } $$ - приблизит к единице абсолютные величины всех координат точки минимума. Величина $$\alpha $$ характеризует соотношение между этими двумя требованиями и может меняться со временем.
Используя выражение для энергии, можно записать систему уравнений, описывающих функционирование
$$\dot x_j = - \partial H/\partial x_j = \sum\limits_{i = 1}^m {\left( {x,x^i } \right)x_j^i } - 4\alpha \left( {x_j^2 - 1} \right)x_j$$
Построим
$$x' = Sign\left( {\sum\limits_{i = 1}^m {w_i x^i } } \right) ,$$
где $$w_i $$ - вес $$i$$ -го эталона, характеризующий его близость к вектору $$x$$, $$Sign $$ - нелинейный оператор, переводящий вектор с координатами $$y_i $$ в вектор с координатами $$sign y_i.$$
Функционирование сети. Сеть работает следующим образом:
Таким образом, ответ всегда является неподвижной точкой преобразования сети (2) и именно это условие (неизменность при обработке образа сетью) и является условием остановки.
Пусть $$i^* $$ - номер эталона, ближайшего к образу $$x$$. Тогда, если выбрать веса пропорционально близости эталонов к исходному образу $$x$$, то следует ожидать, что образ $$x'$$ будет ближе к эталону $$x^{i^* }$$, чем $$x$$, а после нескольких итераций он станет совпадать с эталоном $$x^{i^* }$$.
Наиболее простой сетью вида (2) является дискретный вариант
$$x' = Sign\left( {\sum\limits_{i = 1}^m {\left( {x,x^i } \right)x^i } } \right) .$$
О сетях Хопфилда известно, что они способны запомнить и точно воспроизвести "порядка $$0.14n$$ слабо скоррелированных образов". В этом высказывании содержится два ограничения:
(рис 8.1) а, б, с – эталоны, г – ответ сети на предъявление любого эталонаНаиболее существенным является второе ограничение, поскольку образы, которые сеть должна обрабатывать, часто очень похожи. Примером могут служить буквы латинского алфавита. При обучении
В связи с такими примерами первый вопрос о качестве работы сети ассоциативной памяти звучит тривиально: будет ли сеть правильно обрабатывать сами эталонные образы (т.е. не искажает их)?
Зависимость работы
$$\begin{array}{l} \left( {x^1 ,x^2 } \right) + \left( {x^1 ,x^3 } \right) > n, \\ \left( {x^1 ,x^2 } \right) + \left( {x^2 ,x^3 } \right) > n, \\ \left( {x^1 ,x^3 } \right) + \left( {x^2 ,x^3 } \right) > n, \\ \left( {x^i ,x^j } \right) > 0{\rm{ (}}\forall i,j). \\ \end{array}$$
Для любой координаты существует одна из четырех возможностей:
$$\begin{array}{l} 1){\rm{ }}x_l^i = x_l^j {\rm{ = }}1{\rm{ (}}\forall i,j){\rm{, }} \\ {\rm{2)}}x_l^i = - x_l^j {\rm{ = }}x_l^k {\rm{ = }}1{\rm{ }}{\rm{,}} \\ {\rm{3)}}x_l^i = - x_l^j {\rm{ = }}x_l^k {\rm{ = - }}1{\rm{ }}{\rm{, }} \\ 4){\rm{ }}x_l^i = x_l^j {\rm{ = - }}1{\rm{ (}}\forall i,j){\rm{ }}{\rm{.}} \\ \end{array}$$
В первом случае при предъявлении сети $$q$$ -го эталона в силу формулы (3) получаем $$x'_l = Sign\left( {\sum\limits_{i = 1}^3 {\left( {x^q ,x^i } \right) \times 1} } \right) = 1$$, так как все скалярные произведения положительны по условию (4). Аналогично получаем в четвертом случае $$x'_j = - 1$$.
Во втором случае рассмотрим отдельно три варианта
$$\begin{array}{*{20}c} {x = x^i ,{\rm{ }}x'_j = Sign\left( { - \left( {x^i ,x^i } \right) + \left( {x^i ,x^j } \right) + \left( {x^i ,x^k } \right)} \right) = 1} \\ {x = x^j ,{\rm{ }}x'_l = Sign\left( { - \left( {x^j ,x^i } \right) + \left( {x^j ,x^j } \right) + \left( {x^j ,x^k } \right)} \right) = 1} \\ {x = x^k ,{\rm{ }}x'_l = Sign\left( { - \left( {x^k ,x^i } \right) + \left( {x^k ,x^j } \right) + \left( {x^k ,x^k } \right)} \right) = 1} \\ \end{array}$$
так как скалярный квадрат любого образа равен $$n$$, а сумма двух любых скалярных произведений эталонов больше $$n$$, по условию (4). Таким образом, независимо от предъявленного эталона получаем $$x'_j = 1$$. Аналогично в третьем случае получаем $$x'_j = - 1$$.
Окончательный вывод таков: если эталоны удовлетворяют условиям (4), то при предъявлении любого эталона на выходе всегда будет один образ. Этот образ может быть эталоном или "химерой", составленной, чаще всего, из узнаваемых фрагментов различных эталонов (примером "химеры" может служить образ, приведенный на рис. 8.1 г). Рассмотренный ранее пример с буквами детально иллюстрирует такую ситуацию.
Приведенные выше соображения позволяют сформулировать требование, детализирующие понятие "слабо скоррелированных образов". Для правильного распознавания всех эталонов достаточно (но не необходимо) потребовать, чтобы выполнялось следующее неравенство $$\sum\limits_{\scriptstyle i = 1 \hfill \atop \scriptstyle i \ne j \hfill}^m {\left| {\left( {x^i ,x^j } \right)} \right|} < n,\forall j$$. Более простое и наглядное, хотя и более сильное условие можно записать в виде $$\left| {\left( {x^i ,x^j } \right)} \right| < \frac{n}{m},\forall i \ne j$$. Из этих условий видно, что чем больше задано эталонов, тем более жесткие требования предъявляются к степени их скоррелированности, тем ближе они должны быть к ортогональным.
Рассмотрим преобразование (3) как суперпозицию двух преобразований:
$$Px = \sum\limits_{i = 1}^m {\left( {x,x^i } \right)x^i } ,{\rm{ }}x' = Sign\left( {Px} \right).$$
Обозначим через $$L\left( {\left\{ {x^i } \right\}} \right) = \left\{ {\left. {x} \right| x = \sum\limits_{i = 1}^m {\alpha_i x^i }{\rm{; }}\alpha_i \in {\bf{R}}} \right\}$$ - линейное пространство, натянутое на множество эталонов. Тогда первое преобразование в (5) переводит векторы из $${\bf{R}}^n $$ в $$L\left( {\left\{ {x^i } \right\}} \right)$$. Второе преобразование в (5) переводит результат первого преобразования $$Px$$ в одну из вершин
$$\begin{array}{l} \left\| {b - Px} \right\| = \sum\limits_{i = 1}^n {\left( {b_i - \left( {Px} \right)_i } \right)^2 } = \sum\limits_{i \in I}{\left( {b_i - \left( {Px} \right)_i } \right)^2 } + \sum\limits_{i \notin I}{\left( {b_i - \left( {Px} \right)_i } \right)^2 } < \\ \sum\limits_{i \in I}{\left( {1 + \left| {\left( {Px} \right)_i } \right|} \right)^2 } + \sum\limits_{i \notin I}{\left( {a_i - \left( {Px} \right)_i } \right)^2 } = \sum\limits_{i = 1}^n {\left( {a_i - \left( {Px} \right)_i } \right)^2 } = \left\| {a - Px} \right\|. \\ \end{array}$$
Полученное неравенство $$\left\| {b - Px} \right\| < \left\| {a - Px} \right\|$$ противоречит тому, что $$a$$ - ближайшая к $$Px$$. Таким образом доказано, что второе преобразование в (5) переводит точку $$Px$$ в ближайшую вершину
Для обеспечения правильного воспроизведения эталонов достаточно потребовать, чтобы первое преобразование в (5) было таким, что $$x^i = Px^i$$. Очевидно, что если проектор является ортогональным, то это требование выполняется, поскольку $$x = Px$$ при $$x \in L\left( {\left\{ {x^i } \right\}} \right)$$, а $$x^j \in L\left( {\left\{ {x^i } \right\}} \right)$$ по определению множества $$L\left( {\left\{ {x^i } \right\}} \right)$$.
Для обеспечения ортогональности проектора воспользуемся дуальным множеством векторов. Множество векторов $$V\left( {\left\{ {x^i } \right\}} \right)$$ называется дуальным к множеству векторов $$\left\{ {x^i } \right\}$$ если все вектора этого множества $$v^j $$ удовлетворяют следующим требованиям:
Преобразование $$Px = \sum\limits_{i = 1}^m {\left( {x,v^i } \right)x^i } ,{\rm{ }}v^i \in V\left( {\left\{ {x^i } \right\}} \right)$$ является ортогональным проектором на линейное пространство $$L\left( {\left\{ {x^i } \right\}} \right)$$.
Ортогональная сеть ассоциативной памяти преобразует образы по формуле
$$x' = Sign\left( {\sum\limits_{i = 1}^m {\left( {x,v^i } \right)x^i } } \right) .$$
Дуальное множество векторов существует тогда и только тогда, когда множество векторов $$\left\{ {x^i } \right\}$$ линейно независимо. Если множество эталонов $$\left\{ {x^i } \right\}$$ линейно зависимо, то исключим из него линейно зависимые образы и будем рассматривать полученное усеченное множество эталонов как основу для построения дуального множества и преобразования (6). Образы, исключенные из исходного множества эталонов, будут по-прежнему сохраняться сетью в исходном виде (преобразовываться в самих себя). Действительно, пусть эталон $$x$$ является линейно зависимым от остальных $$m$$ эталонов. Тогда его можно представить в виде$$x = \sum\limits_{i = 1}^m {\alpha_i x^i } .$$ Подставив полученное выражение в преобразование (6) и учитывая свойства дуального множества получим:
$$\begin{array}{l} x' = Sign\left( {\sum\limits_{i = 1}^m {\left( {x,v^i } \right)x^i } } \right) = Sign\left( {\sum\limits_{i = 1}^m {\left( {\sum\limits_{j = 1}^m {\alpha_j x^j } ,v^i } \right)x^i } } \right) = \\ = Sign\left( {\sum\limits_{i,j = 1}^m {\alpha_j \left( {x^j ,v^i } \right)x^i } } \right) = Sign\left( {\sum\limits_{j = 1}^m {\alpha_j x^j } } \right) = Sign\left( x \right) = x \\ \end{array}$$
Рассмотрим свойства сети (6) [8.2]. Во-первых, количество запоминаемых и точно воспроизводимых эталонов не зависит от степени их скоррелированности. Во-вторых, формально сеть способна работать без искажений при любом возможном числе эталонов (всего их может быть до $$2^n $$ ). Однако, если число линейно независимых эталонов (т.е. ранг множества эталонов) равно $$n$$, сеть становится прозрачной - какой бы образ не предъявили на ее вход, на выходе окажется тот же образ. Действительно, как было показано в (7), все образы, линейно зависимые от эталонов, преобразуются проективной частью преобразования (6) сами в себя. Значит, если в множестве эталонов есть $$n$$ линейно независимых, то любой образ можно представить в виде линейной комбинации эталонов (точнее $$n$$ линейно независимых эталонов), а проективная часть преобразования (6) в силу формулы (7) переводит любую линейную комбинацию эталонов в саму себя.
Если число линейно независимых эталонов меньше n , то сеть преобразует поступающий образ, отфильтровывая помехи, ортогональные всем эталонам.
Отметим, что результаты работы сетей (3) и (6) эквивалентны, если все эталоны попарно ортогональны.
Остановимся несколько подробнее на алгоритме вычисления дуального множества векторов. Обозначим через $$\Gamma \left( {\left\{ {x^i } \right\}} \right)$$ матрицу Грамма множества векторов $$\left\{ {x^i } \right\}$$. Элементы матрицы Грамма имеют вид $$\gamma_{ij} = \left( {x^i ,x^j } \right)$$ ( $$ij$$ -ый элемент матрицы Грамма равен скалярному произведению $$i$$ -го эталона на $$j$$ -ый). Известно, что векторы дуального множества можно записать в следующем виде:
$$v^i = \sum\limits_{j = 1}^m {\gamma_{ij}^{ - 1} x^j } ,$$
где $$\gamma {ij}^{ - 1} $$ - элемент матрицы $$\Gamma^{ - 1} \left( {\left\{ {x^i } \right\}} \right)$$. Поскольку
Для работы сети (6) необходимо хранить эталоны и матрицу $$\Gamma^{ - 1} \left( {\left\{ {x^i } \right\}} \right)$$.
Рассмотрим процедуру добавления нового эталона к сети (6). Эта операция часто называется дообучением сети. Важным критерием оценки алгоритма формирования сети является соотношение вычислительных затрат на обучение и дообучение. Затраты на дообучение не должны зависеть от числа освоенных ранее эталонов.
Для H одного слагаемого $$\left( {x,x^{m + 1} } \right)^2$$, а модификация связей в сети - состоит в прибавлении к весу ij -й связи числа $$x_i^{m + 1} x_j^{m + 1} $$ - всего $$n^2 $$ операций.
Для рассматриваемых сетей с ортогональным проектированием также возможно простое дообучение. На первый взгляд, это может показаться странным - если добавляемый эталон линейно независим от старых эталонов, то вообще говоря необходимо пересчитать матрицу Грамма и обратить ее. Однако симметричность матрицы Грамма позволяет не производить заново процедуру обращения всей матрицы. Действительно, обозначим через $${\bf{G}}_m $$ - матрицу Грамма для множества из $$m$$ векторов $$x^i $$ ; через $${\bf{E}}_m $$ - единичную матрицу размерности $$m \times m$$. При обращении матриц методом Гаусса используется следующая процедура:
Пусть известна $${\bf{G}}_m^{ - 1} $$ - обратная к матрице Грамма для множества из m векторов $$x^i$$. Добавим к этому множеству вектор $$x^{m + 1}$$. Тогда матрица для обращения матрицы $${\bf{G}}_{m + 1} $$ методом Гаусса будет иметь вид:
$$\left( {\left. {\begin{array}{*{20}c} {\left( {x^1 ,x^{m + 1} } \right)} \\ {{\bf{G}}_m } \vdots \\ {\left( {x^m ,x^{m + 1} } \right)} \\ {\left( {x^1 ,x^{m + 1} } \right)} \cdots {\left( {x^m ,x^{m + 1} } \right)} {\left( {x^{m + 1} ,x^{m + 1} } \right)} \\ \end{array}} \right|{\bf{E}}_{m + 1} } \right) .$$
После приведения к единичной матрице главного минора ранга m получится следующая матрица:
$$\left( {\left. {\begin{array}{*{20}c} {b_1 } \\ {{\bf{E}}_m } \vdots \\ {b_m } \\ {\left( {x^1 ,x^{m + 1} } \right)} \cdots {\left( {x^m ,x^{m + 1} } \right)} {\left( {x^{m + 1} ,x^{m + 1} } \right)} \\ \end{array}} \right|\begin{array}{*{20}c} 0 \\ {{\bf{G}}_m^{ - 1} } \vdots \\ 0 \\ 0 \cdots 0 1 \\ \end{array}} \right) ,$$
где $$b_i $$ - неизвестные величины, полученные в ходе приведения главного минора к единичной матрице. Для завершения обращения матрицы $${\bf{G}}_{m + 1} $$ необходимо привести к нулевому виду первые m элементов последней строки и $$\left( {m + 1} \right)$$ -о столбца. Для обращения в ноль i -о элемента последней строки необходимо умножить i -ю строку на $$\left( {x^i ,x^{m + 1} } \right)$$ и вычесть из последней строки. После проведения этого преобразования получим
$$\left( {\left. {\begin{array}{*{20}c} {b_1 } \\ {{\bf{E}}_m } \vdots \\ {b_m } \\ 0 \cdots 0 {b_0 } \\ \end{array}} \right|\begin{array}{*{20}c} 0 \\ {{\bf{G}}_m^{ - 1} } \vdots \\ 0 \\ {c_1 } \cdots {c_m } 1 \\ \end{array}} \right) ,$$
где$$b_0 = \left( {x^{m + 1} , x^{m + 1} } \right) - \sum\limits_{i = 1}^m {\left( {x^i ,x^{m + 1} } \right)b_i } ,$$
$$c_i = - \sum\limits_{j = 1}^m {\left( {x^j ,x^{m + 1} } \right){\bf{G}}_{m,ji}^{ - 1} } .$$
$$b_0 = 0$$ только если новый эталон является линейной комбинацией первых m эталонов. Следовательно $$b_0 \ne 0$$. Для завершения обращения необходимо разделить последнюю строку на $$b_0 $$ и затем вычесть из всех предыдущих строк последнюю, умноженную на соответствующее номеру строки $$b_i$$. В результате получим следующую матрицу
$$\left( {\left. {\begin{array}{*{20}c} 0 \\ {{\bf{E}}_m } \vdots \\ 0 \\ 0 \cdots 0 1 \\ \end{array}} \right|\begin{array}{*{20}c} { - {{b_1 } \mathord{\left/ {\vphantom {{b_1 }{b_0 }}} \right. \kern-\nulldelimiterspace}{b_0 }}} \\ {\bf{F}} \vdots \\ { - {{b_m } \mathord{\left/ {\vphantom {{b_m }{b_0 }}} \right. \kern-\nulldelimiterspace}{b_0 }}} \\ {{{c_1 } \mathord{\left/ {\vphantom {{c_1 }{b_0 }}} \right. \kern-\nulldelimiterspace}{b_0 }}} \cdots {{{c_m } \mathord{\left/ {\vphantom {{c_m }{b_0 }}} \right. \kern-\nulldelimiterspace}{b_0 }}} {{1 \mathord{\left/ {\vphantom {1 {b_0 }}} \right. \kern-\nulldelimiterspace}{b_0 }}} \\ \end{array}} \right) ,$$
где $${\bf{F}}_{ij} = {\bf{G}}_{m,ij}^{ - 1} - {{b_i c_j }{\left/ {b_0 } \right }}$$. Поскольку i. Так как $$b_0 \ne 0$$ следовательно $$b_i = - c_i$$.
Обозначим через $${\bf{d}}$$ вектор$$\left( {\left( {x^1 ,x^{m + 1} } \right), \ldots ,\left( {x^m ,x^{m + 1} } \right)} \right),$$ через $${\bf{b}}$$ - вектор $$\left( {b_1 , \ldots ,b_m } \right)$$. Используя эти обозначения можно записать$${\bf{b}} = {\bf{G}}_m^{ - 1}{\bf{d}},{\rm{ }}b_0 = \left( {x^{m + 1} ,x^{m + 1} } \right) - \left( {{\bf{d}},{\bf{b}}} \right).$$ Матрица $${\bf{G}}_{m + 1}^{ - 1} $$ записывается в виде
$${\bf{G}}_{m + 1}^{ - 1} = \frac{1}{{b_0 }}\left( {\begin{array}{*{20}c} {b_0 {\bf{G}}_m^{ - 1} + {\bf{b}} \otimes {\bf{b}}} { - {\bf{b}}} \\ { - {\bf{b}}} {\bf{1}} \\ \end{array}} \right) .$$
Таким образом, при добавлении нового эталона требуется произвести следующие операции:
Таким образом, эта процедура требует $$m + n + mn + 3m^2 $$ операций. Тогда как стандартная схема полного пересчета потребует:
Всего $${{2m^3 + nm\left( {m + 1} \right)} \mathord{\left/ {\vphantom {{2m^3 + nm\left( {m + 1} \right)} 2}} \right. \kern-\nulldelimiterspace} 2}$$ операций, что в $$m $$ раз больше.
Используя ортогональную сеть (6), удалось добиться независимости способности сети к запоминанию и точному воспроизведению эталонов от степени скоррелированности эталонов. Так, например, ортогональная сеть смогла правильно воспроизвести все буквы латинского алфавита в написании, приведенном на рис. 8.1.
У сети (6) можно выделить два основных недостатка:
Оба этих недостатка можно устранить, изменив выбор весовых коэффициентов в (2).
Для увеличения числа линейно независимых эталонов, не приводящих к прозрачности сети, используется прием перехода к тензорным или многочастичным сетям [8.3, 8.4, 8.5, 8.6, 8.7].
Тензорным произведением $$k$$ $$n$$ -мерных векторов $$y^1 , \cdots ,y^k $$ называется $$k$$ -индексная величина $$b_{i_1 \cdots i_k }$$, у которой все индексы независимо пробегают весь набор значений от единицы до $$n$$, а $$b_{i_1 \cdots i_k } = y_{i_1 }^1 y_{i_2 }^2 \cdots y_{i_k }^k$$. $$k$$ -ой тензорной степенью вектора $$x$$ будем называть вектор $$x^{ \otimes k}$$, полученный как тензорное произведение $$k$$ векторов $$x$$. Вектор $$x^{ \otimes k} $$ является $$n^k $$ -мерным вектором. Однако пространство $$L\left( {\left\{ {x^{i^{ \otimes k}}} \right\}} \right)$$ имеет размерность, не превышающую величину $$r_{n,k} = \sum\limits_{i = 0}^k {{\bf{C}}_{n - 1}^i }$$, где $${\bf{C}}_p^q = \frac{{p!}}{{q!\left( {p - q} \right)!}} $$ - число сочетаний из $$p$$ по $$q$$.
Теорема. При k < n в ранг $$r_{n,k} $$ множества $$\left\{ {x^{ \otimes k} } \right\}$$ равен: $$r_{n,k} = \sum\limits_{i = 0}^k {{\bf{C}}_{n - 1}^i }$$.
(рис 8.2) "Тензорный" треугольник Паскаля Небольшая модернизация
n=2 в множестве X всего два неколлинеарных вектора.| n | k | nk | Ck - 1n + k - 1 | rn,k |
|---|---|---|---|---|
| 5 | 2 | 25 | 15 | 11 |
| 3 | 125 | 35 | 15 | |
| 10 | 3 | 1 000 | 220 | 130 |
| 6 | 1 000 000 | 5005 | 466 | |
| 8 | 100 000 000 | 24310 | 511 |
В таблица 8.1 приведено сравнение трех оценок информационной емкости тензорных сетей для некоторых значений n и k. Первая оценка - $$n^k $$ - заведомо завышена, вторая - $${\bf{C}}_{n + k - 1}^{k - 1}
$$ - дается формулой Эйлера для размерности пространства симметричных тензоров и третья - точное значение $$r_{n,k} $$
Как легко видеть из таблицы таблица 8.1, уточнение при переходе к оценке $$r_{nk} $$ является весьма существенным. С другой стороны, предельная информационная емкость тензорной сети (число правильно воспроизводимых образов) может существенно превышать число нейронов, например, для 10 нейронов тензорная сеть валентности 8 имеет предельную информационную емкость 511.
Легко показать, что если множество векторов $$\left\{ {x^i } \right\}$$ не содержит взаимно обратных, то размерность пространства $$L\left( {\left\{ {x^{i^{ \otimes n}} } \right\}} \right)$$ равна числу векторов в множестве $$\left\{ {x^i } \right\}$$. Сеть (2) для случая тензорных сетей имеет вид
$$x' = Sign\left( {\sum\limits_{i = 1}^m {\left( {x^{ \otimes k} ,x^{i^{ \otimes k}} } \right)x^i } } \right) = Sign\left( {\sum\limits_{i = 1}^m {\left( {x,x^i } \right)^k x^i } } \right) ,$$
а ортогональная тензорная сеть
$$x' = Sign\left( {\sum\limits_{i = 1}^m {\left( {x^{ \otimes k} ,v^i } \right)x^i } } \right) = Sign\left( {\sum\limits_{i = 1}^m {\sum\limits_{j = 1}^m {\gamma_{ij}^{ - 1} } \left( {x,x^j } \right)^k x^i } } \right) ,$$
где $$\gamma_{ij}^{-1} $$ - элемент матрицы$$\Gamma^{ - 1} \left( {\left\{ {x^{i^{ \otimes k}} } \right\}} \right).$$ Сеть (9) хорошо работает на слабо скоррелированных эталонах, а сеть (10) не чувствительна к степени скоррелированности эталонов.
Для того, чтобы при обработке переводить визуальные образов, отличающиеся только положением в рамке изображения, в один эталон, применяется следующий прием [8.7]. Преобразуем исходное изображение в некоторый вектор величин, не изменяющихся при сдвиге (вектор инвариантов). Простейший набор инвариантов дают автокорреляторы - скалярные произведения образа на сдвинутый образ, рассматриваемые как функции вектора сдвига.
В качестве примера рассмотрим вычисление сдвигового автокоррелятора для черно-белых изображений. Пусть дан двумерный образ $$S$$ размером $$p \times q = n$$. Обозначим точки образа как $$s_{ij}$$. Элементами автокоррелятора $$Ac\left( S \right)$$ будут величины$$a_{kl} = \sum\limits_{i = 1}^p {\sum\limits_{j = 1}^q {s_{ij} s_{i + k,j + l} } } ,$$ где $$s_{ij = 0} $$ при выполнении любого из неравенств $$i < 1,i > p,j < 1,j > q$$. Легко проверить, что автокорреляторы любых двух образов, отличающихся только расположением в рамке, совпадают. Отметим, что $$a_{ij} = a_{ - i, - j} $$ при всех $$i,j$$, и $$a_{ij} = 0$$ при выполнении любого из неравенств $$i < 1 - p,i > p - 1,j < 1 - q,j > q - 1$$. Таким образом, можно считать, что размер автокоррелятора равен $$p \times \left( {2q + 1} \right)$$.
Автокорреляторная сеть имеет вид
$$x' = Sign\left( {\sum\limits_{i = 1}^m {\left( {Ac\left( x \right),Ac\left( {x^i } \right)} \right)x^i } } \right) .$$
Сеть (11) позволяет обрабатывать различные визуальные образы, отличающиеся только положением в рамке, как один образ.
Подводя итоги, можно сказать, что все сети ассоциативной памяти типа (2) можно получить, комбинируя следующие преобразования:
Наиболее сложная сеть будет иметь вид:
$$x' = Sign\left( {\sum\limits_{i = 1}^m {\sum\limits_{j = 1}^m {\gamma_{ij}^{ - 1} } \left( {F\left( x \right),F\left( {x^j } \right)} \right)^k x^i } } \right) ,$$
где $$\gamma_{ij}^{ - 1} $$ - элементы матрицы, обратной матрице Грамма системы векторов$$\Gamma^{ - 1} \left( {\left\{ {F\left( {x^{i^{ \otimes k}} } \right)} \right\}} \right),$$ $$F\left( x \right)$$ - произвольное преобразование.
Работа ортогональных тензорных сетей при наличии помех сравнивалась с возможностями линейных кодов, исправляющих ошибки. Линейным кодом, исправляющим k ошибок, называется линейное подпространство в n -мерном пространстве над GF2, все вектора которого удалены друг от друга не менее чем на 2k+1 (см., например, [8.8]). Линейный код называется совершенным, если для любого вектора n -мерного пространства существует кодовый вектор, удаленный от данного не более, чем на k. Тензорной сети в качестве эталонов подавались все кодовые
векторы избранного для сравнения кода. Численные эксперименты с совершенными кодами показали, что тензорная сеть минимально необходимой валентности правильно декодирует все векторы. Для несовершенных кодов картина оказалась хуже - среди устойчивых образов тензорной сети появились "химеры" - векторы, не принадлежащие множеству эталонов.
В случае n=10, k=1 (см. табл. 8.1 2 и 3, строка 1) при валентностях 3 и 5 тензорная сеть работала как единичный оператор - все входные вектора передавались на выход сети без изменений. Однако уже при валентности 7 число химер резко сократилось и сеть правильно декодировала более 60% сигналов. При этом были правильно декодированы все векторы, удаленные от ближайшего эталона на расстояние 2, а часть векторов, удаленных от ближайшего эталона на расстояние 1, остались химерами. В случае n=10, k=2 (см. табл. 8.1 2 и 3,
строки 3, 4, 5) наблюдалось уменьшение числа химер с ростом валентности, однако часть химер, удаленных от ближайшего эталона на расстояние 2 сохранялась. Сеть правильно декодировала более 50% сигналов. Таким образом при малых размерностях и кодах, далеких от совершенных, тензорная сеть работает довольно плохо. Однако, уже при n=15, k=3 и валентности, большей 3 (см. табл. 8.1 2 и 3, строки 6, 7), сеть правильно декодировала все сигналы с тремя ошибками. В большинстве экспериментов число эталонов было больше числа нейронов.
Подводя итог, можно сказать, что качество работы сети возрастает с ростом размерности пространства и валентности и по эффективности устранения ошибок сеть приближается к коду, гарантированно исправляющему ошибки.
Работа выполнена при поддержке Красноярского краевого фонда науки, грант 6F0124.
Вычислительный центр СО РАН в г. Красноярске
Рассматриваются нейронные сети ассоциативной памяти, восстанавливающие по искаженному и/или зашумленному образу ближайший к нему эталонный. Исследована информационная емкость сетей и предложено несколько путей ее повышения, в том числе - ортогональные тензорные (многочастичные) сети. Построены способы предобработки, позволяющие конструировать нейронные сети ассоциативной памяти для обработки образов, инвариантной относительно групп преобразований. Описан численный эксперимент по использованию нейронных сетей для декодирования различных кодов.
Прежде чем заниматься конструированием сетей ассоциативной памяти необходимо ответить на следующие два вопроса: "Как устроена ассоциативная память?" и "Какие задачи она решает?". Когда мы задаем эти вопросы, имеется в виду не устройство отделов мозга, отвечающих за
Принято говорить, что у человека возникла ассоциация, если при получении некоторой неполной информации он может подробно описать объект, к которому по его мнению относится эта информация. Достаточно хорошим примером может служить описание малознакомого человека. К примеру, при высказывании: "Слушай, а что за парень, с которым ты вчера разговаривал на вечеринке, такой высокий блондин?"- у собеседника возникает образ вчерашнего собеседника, не ограничивающийся ростом и цветом волос. В ответ на заданный вопрос он может рассказать об этом человеке довольно много. При этом следует заметить, что содержащейся в вопросе информации явно недостаточно для точной идентификации собеседника. Более того, если вчерашний собеседник был случайным, то без дополнительной информации его и не вспомнят.
В качестве другого примера можно рассмотреть ситуацию, когда ваша однокурсница появляется в институте с совершенно новой прической и в незнакомой вам одежде. При этом вы, тем не менее, чаще всего ее узнаете и сможете определить чем ее новый образ отличается от привычного. Можно предположить, что это происходит следующим образом. При виде ее нового облика в вашей памяти возникает ассоциация с привычным для вас. А далее сравнивая эти два облика вы можете определить отличия.
Исходя из рассмотренных примеров можно сказать, что ассоциативная память позволяет по неполной и даже частично недостоверной информации восстановить достаточно полное описание знакомого объекта. Слово знакомого является очень важным, поскольку невозможно вызвать ассоциации с незнакомыми объектами. При этом объект должен быть знаком тому, у кого возникают ассоциации.
Одновременно рассмотренные примеры позволяют сформулировать решаемые ассоциативной памятью задачи:
Очевидно, что под точным описанием объекта следует понимать всю информацию, которая доступна ассоциативной памяти. Вторая задача решается не поэтапно, а одновременно происходит соотнесение полученной информации с известными образцами и отсев недостоверной информации.
Пусть задан набор из $$m$$ эталонов - $$n$$ -мерных векторов $$\left\{ {x^i } \right\}$$. Требуется построить сеть, которая при предъявлении на вход произвольного образа - вектора x - давала бы на выходе "наиболее похожий" эталон.
Всюду далее образы и, в том числе, эталоны - $$n$$ -мерные векторы с координатами $$\pm 1$$. Эталон, "наиболее похожий" на x - ближайший к x вектор $$x^i$$. Легко заметить, что это требование эквивалентно требованию максимальности
$$\left\| {x - x^i } \right\| = \left\| x \right\|^2 + \left\| {x^i } \right\|^2 - 2\left( {x,x^i } \right) .$$
Первые два слагаемых в правой части совпадают для любых образов $$x$$ и $$x^i$$, так как длины всех векторов-образов равны $$\sqrt n$$. Таким образом, задача поиска ближайшего образа сводится к поиску образа, скалярное произведение с которым максимально. Этот простой факт приводит к тому, что сравнивать придется линейные функции от образов, тогда как расстояние является квадратичной функцией.
Наиболее известной сетью ассоциативной памяти является H (функции Ляпунова). Точки равновесия такой системы находятся в точках минимума энергии. Функцию энергии будем строить из следующих соображений:
Функция
$$$H = - {\frac{1}{2}} \sum\limits_{i = 1}^m {\left( {x,x^i } \right)^2 } + \alpha \sum\limits_{j = 1}^n {\left( {x_j^2 - 1} \right)^2 }$$$
не удовлетворяет этим требованиям строго, но можно предполагать, что первое слагаемое обеспечит притяжение к эталонам (для вектора x фиксированной длины максимум квадрата скалярного произведения $$\left( {x,x^i } \right)^2 $$ достигается при x=xi ), а второе слагаемое $$\sum\limits_{j = 1}^n {\left( {x_j^2 - 1} \right)^2 } $$ - приблизит к единице абсолютные величины всех координат точки минимума. Величина $$\alpha $$ характеризует соотношение между этими двумя требованиями и может меняться со временем.
Используя выражение для энергии, можно записать систему уравнений, описывающих функционирование
$$\dot x_j = - \partial H/\partial x_j = \sum\limits_{i = 1}^m {\left( {x,x^i } \right)x_j^i } - 4\alpha \left( {x_j^2 - 1} \right)x_j$$
Построим
$$x' = Sign\left( {\sum\limits_{i = 1}^m {w_i x^i } } \right) ,$$
где $$w_i $$ - вес $$i$$ -го эталона, характеризующий его близость к вектору $$x$$, $$Sign $$ - нелинейный оператор, переводящий вектор с координатами $$y_i $$ в вектор с координатами $$sign y_i.$$
Функционирование сети. Сеть работает следующим образом:
Таким образом, ответ всегда является неподвижной точкой преобразования сети (2) и именно это условие (неизменность при обработке образа сетью) и является условием остановки.
Пусть $$i^* $$ - номер эталона, ближайшего к образу $$x$$. Тогда, если выбрать веса пропорционально близости эталонов к исходному образу $$x$$, то следует ожидать, что образ $$x'$$ будет ближе к эталону $$x^{i^* }$$, чем $$x$$, а после нескольких итераций он станет совпадать с эталоном $$x^{i^* }$$.
Наиболее простой сетью вида (2) является дискретный вариант
$$x' = Sign\left( {\sum\limits_{i = 1}^m {\left( {x,x^i } \right)x^i } } \right) .$$
О сетях Хопфилда известно, что они способны запомнить и точно воспроизвести "порядка $$0.14n$$ слабо скоррелированных образов". В этом высказывании содержится два ограничения:
(рис 8.1) а, б, с – эталоны, г – ответ сети на предъявление любого эталонаНаиболее существенным является второе ограничение, поскольку образы, которые сеть должна обрабатывать, часто очень похожи. Примером могут служить буквы латинского алфавита. При обучении
В связи с такими примерами первый вопрос о качестве работы сети ассоциативной памяти звучит тривиально: будет ли сеть правильно обрабатывать сами эталонные образы (т.е. не искажает их)?
Зависимость работы
$$\begin{array}{l} \left( {x^1 ,x^2 } \right) + \left( {x^1 ,x^3 } \right) > n, \\ \left( {x^1 ,x^2 } \right) + \left( {x^2 ,x^3 } \right) > n, \\ \left( {x^1 ,x^3 } \right) + \left( {x^2 ,x^3 } \right) > n, \\ \left( {x^i ,x^j } \right) > 0{\rm{ (}}\forall i,j). \\ \end{array}$$
Для любой координаты существует одна из четырех возможностей:
$$\begin{array}{l} 1){\rm{ }}x_l^i = x_l^j {\rm{ = }}1{\rm{ (}}\forall i,j){\rm{, }} \\ {\rm{2)}}x_l^i = - x_l^j {\rm{ = }}x_l^k {\rm{ = }}1{\rm{ }}{\rm{,}} \\ {\rm{3)}}x_l^i = - x_l^j {\rm{ = }}x_l^k {\rm{ = - }}1{\rm{ }}{\rm{, }} \\ 4){\rm{ }}x_l^i = x_l^j {\rm{ = - }}1{\rm{ (}}\forall i,j){\rm{ }}{\rm{.}} \\ \end{array}$$
В первом случае при предъявлении сети $$q$$ -го эталона в силу формулы (3) получаем $$x'_l = Sign\left( {\sum\limits_{i = 1}^3 {\left( {x^q ,x^i } \right) \times 1} } \right) = 1$$, так как все скалярные произведения положительны по условию (4). Аналогично получаем в четвертом случае $$x'_j = - 1$$.
Во втором случае рассмотрим отдельно три варианта
$$\begin{array}{*{20}c} {x = x^i ,{\rm{ }}x'_j = Sign\left( { - \left( {x^i ,x^i } \right) + \left( {x^i ,x^j } \right) + \left( {x^i ,x^k } \right)} \right) = 1} \\ {x = x^j ,{\rm{ }}x'_l = Sign\left( { - \left( {x^j ,x^i } \right) + \left( {x^j ,x^j } \right) + \left( {x^j ,x^k } \right)} \right) = 1} \\ {x = x^k ,{\rm{ }}x'_l = Sign\left( { - \left( {x^k ,x^i } \right) + \left( {x^k ,x^j } \right) + \left( {x^k ,x^k } \right)} \right) = 1} \\ \end{array}$$
так как скалярный квадрат любого образа равен $$n$$, а сумма двух любых скалярных произведений эталонов больше $$n$$, по условию (4). Таким образом, независимо от предъявленного эталона получаем $$x'_j = 1$$. Аналогично в третьем случае получаем $$x'_j = - 1$$.
Окончательный вывод таков: если эталоны удовлетворяют условиям (4), то при предъявлении любого эталона на выходе всегда будет один образ. Этот образ может быть эталоном или "химерой", составленной, чаще всего, из узнаваемых фрагментов различных эталонов (примером "химеры" может служить образ, приведенный на рис. 8.1 г). Рассмотренный ранее пример с буквами детально иллюстрирует такую ситуацию.
Приведенные выше соображения позволяют сформулировать требование, детализирующие понятие "слабо скоррелированных образов". Для правильного распознавания всех эталонов достаточно (но не необходимо) потребовать, чтобы выполнялось следующее неравенство $$\sum\limits_{\scriptstyle i = 1 \hfill \atop \scriptstyle i \ne j \hfill}^m {\left| {\left( {x^i ,x^j } \right)} \right|} < n,\forall j$$. Более простое и наглядное, хотя и более сильное условие можно записать в виде $$\left| {\left( {x^i ,x^j } \right)} \right| < \frac{n}{m},\forall i \ne j$$. Из этих условий видно, что чем больше задано эталонов, тем более жесткие требования предъявляются к степени их скоррелированности, тем ближе они должны быть к ортогональным.
Рассмотрим преобразование (3) как суперпозицию двух преобразований:
$$Px = \sum\limits_{i = 1}^m {\left( {x,x^i } \right)x^i } ,{\rm{ }}x' = Sign\left( {Px} \right).$$
Обозначим через $$L\left( {\left\{ {x^i } \right\}} \right) = \left\{ {\left. {x} \right| x = \sum\limits_{i = 1}^m {\alpha_i x^i }{\rm{; }}\alpha_i \in {\bf{R}}} \right\}$$ - линейное пространство, натянутое на множество эталонов. Тогда первое преобразование в (5) переводит векторы из $${\bf{R}}^n $$ в $$L\left( {\left\{ {x^i } \right\}} \right)$$. Второе преобразование в (5) переводит результат первого преобразования $$Px$$ в одну из вершин
$$\begin{array}{l} \left\| {b - Px} \right\| = \sum\limits_{i = 1}^n {\left( {b_i - \left( {Px} \right)_i } \right)^2 } = \sum\limits_{i \in I}{\left( {b_i - \left( {Px} \right)_i } \right)^2 } + \sum\limits_{i \notin I}{\left( {b_i - \left( {Px} \right)_i } \right)^2 } < \\ \sum\limits_{i \in I}{\left( {1 + \left| {\left( {Px} \right)_i } \right|} \right)^2 } + \sum\limits_{i \notin I}{\left( {a_i - \left( {Px} \right)_i } \right)^2 } = \sum\limits_{i = 1}^n {\left( {a_i - \left( {Px} \right)_i } \right)^2 } = \left\| {a - Px} \right\|. \\ \end{array}$$
Полученное неравенство $$\left\| {b - Px} \right\| < \left\| {a - Px} \right\|$$ противоречит тому, что $$a$$ - ближайшая к $$Px$$. Таким образом доказано, что второе преобразование в (5) переводит точку $$Px$$ в ближайшую вершину
Для обеспечения правильного воспроизведения эталонов достаточно потребовать, чтобы первое преобразование в (5) было таким, что $$x^i = Px^i$$. Очевидно, что если проектор является ортогональным, то это требование выполняется, поскольку $$x = Px$$ при $$x \in L\left( {\left\{ {x^i } \right\}} \right)$$, а $$x^j \in L\left( {\left\{ {x^i } \right\}} \right)$$ по определению множества $$L\left( {\left\{ {x^i } \right\}} \right)$$.
Для обеспечения ортогональности проектора воспользуемся дуальным множеством векторов. Множество векторов $$V\left( {\left\{ {x^i } \right\}} \right)$$ называется дуальным к множеству векторов $$\left\{ {x^i } \right\}$$ если все вектора этого множества $$v^j $$ удовлетворяют следующим требованиям:
Преобразование $$Px = \sum\limits_{i = 1}^m {\left( {x,v^i } \right)x^i } ,{\rm{ }}v^i \in V\left( {\left\{ {x^i } \right\}} \right)$$ является ортогональным проектором на линейное пространство $$L\left( {\left\{ {x^i } \right\}} \right)$$.
Ортогональная сеть ассоциативной памяти преобразует образы по формуле
$$x' = Sign\left( {\sum\limits_{i = 1}^m {\left( {x,v^i } \right)x^i } } \right) .$$
Дуальное множество векторов существует тогда и только тогда, когда множество векторов $$\left\{ {x^i } \right\}$$ линейно независимо. Если множество эталонов $$\left\{ {x^i } \right\}$$ линейно зависимо, то исключим из него линейно зависимые образы и будем рассматривать полученное усеченное множество эталонов как основу для построения дуального множества и преобразования (6). Образы, исключенные из исходного множества эталонов, будут по-прежнему сохраняться сетью в исходном виде (преобразовываться в самих себя). Действительно, пусть эталон $$x$$ является линейно зависимым от остальных $$m$$ эталонов. Тогда его можно представить в виде$$x = \sum\limits_{i = 1}^m {\alpha_i x^i } .$$ Подставив полученное выражение в преобразование (6) и учитывая свойства дуального множества получим:
$$\begin{array}{l} x' = Sign\left( {\sum\limits_{i = 1}^m {\left( {x,v^i } \right)x^i } } \right) = Sign\left( {\sum\limits_{i = 1}^m {\left( {\sum\limits_{j = 1}^m {\alpha_j x^j } ,v^i } \right)x^i } } \right) = \\ = Sign\left( {\sum\limits_{i,j = 1}^m {\alpha_j \left( {x^j ,v^i } \right)x^i } } \right) = Sign\left( {\sum\limits_{j = 1}^m {\alpha_j x^j } } \right) = Sign\left( x \right) = x \\ \end{array}$$
Рассмотрим свойства сети (6) [8.2]. Во-первых, количество запоминаемых и точно воспроизводимых эталонов не зависит от степени их скоррелированности. Во-вторых, формально сеть способна работать без искажений при любом возможном числе эталонов (всего их может быть до $$2^n $$ ). Однако, если число линейно независимых эталонов (т.е. ранг множества эталонов) равно $$n$$, сеть становится прозрачной - какой бы образ не предъявили на ее вход, на выходе окажется тот же образ. Действительно, как было показано в (7), все образы, линейно зависимые от эталонов, преобразуются проективной частью преобразования (6) сами в себя. Значит, если в множестве эталонов есть $$n$$ линейно независимых, то любой образ можно представить в виде линейной комбинации эталонов (точнее $$n$$ линейно независимых эталонов), а проективная часть преобразования (6) в силу формулы (7) переводит любую линейную комбинацию эталонов в саму себя.
Если число линейно независимых эталонов меньше n , то сеть преобразует поступающий образ, отфильтровывая помехи, ортогональные всем эталонам.
Отметим, что результаты работы сетей (3) и (6) эквивалентны, если все эталоны попарно ортогональны.
Остановимся несколько подробнее на алгоритме вычисления дуального множества векторов. Обозначим через $$\Gamma \left( {\left\{ {x^i } \right\}} \right)$$ матрицу Грамма множества векторов $$\left\{ {x^i } \right\}$$. Элементы матрицы Грамма имеют вид $$\gamma_{ij} = \left( {x^i ,x^j } \right)$$ ( $$ij$$ -ый элемент матрицы Грамма равен скалярному произведению $$i$$ -го эталона на $$j$$ -ый). Известно, что векторы дуального множества можно записать в следующем виде:
$$v^i = \sum\limits_{j = 1}^m {\gamma_{ij}^{ - 1} x^j } ,$$
где $$\gamma {ij}^{ - 1} $$ - элемент матрицы $$\Gamma^{ - 1} \left( {\left\{ {x^i } \right\}} \right)$$. Поскольку
Для работы сети (6) необходимо хранить эталоны и матрицу $$\Gamma^{ - 1} \left( {\left\{ {x^i } \right\}} \right)$$.
Рассмотрим процедуру добавления нового эталона к сети (6). Эта операция часто называется дообучением сети. Важным критерием оценки алгоритма формирования сети является соотношение вычислительных затрат на обучение и дообучение. Затраты на дообучение не должны зависеть от числа освоенных ранее эталонов.
Для H одного слагаемого $$\left( {x,x^{m + 1} } \right)^2$$, а модификация связей в сети - состоит в прибавлении к весу ij -й связи числа $$x_i^{m + 1} x_j^{m + 1} $$ - всего $$n^2 $$ операций.
Для рассматриваемых сетей с ортогональным проектированием также возможно простое дообучение. На первый взгляд, это может показаться странным - если добавляемый эталон линейно независим от старых эталонов, то вообще говоря необходимо пересчитать матрицу Грамма и обратить ее. Однако симметричность матрицы Грамма позволяет не производить заново процедуру обращения всей матрицы. Действительно, обозначим через $${\bf{G}}_m $$ - матрицу Грамма для множества из $$m$$ векторов $$x^i $$ ; через $${\bf{E}}_m $$ - единичную матрицу размерности $$m \times m$$. При обращении матриц методом Гаусса используется следующая процедура:
Пусть известна $${\bf{G}}_m^{ - 1} $$ - обратная к матрице Грамма для множества из m векторов $$x^i$$. Добавим к этому множеству вектор $$x^{m + 1}$$. Тогда матрица для обращения матрицы $${\bf{G}}_{m + 1} $$ методом Гаусса будет иметь вид:
$$\left( {\left. {\begin{array}{*{20}c} {\left( {x^1 ,x^{m + 1} } \right)} \\ {{\bf{G}}_m } \vdots \\ {\left( {x^m ,x^{m + 1} } \right)} \\ {\left( {x^1 ,x^{m + 1} } \right)} \cdots {\left( {x^m ,x^{m + 1} } \right)} {\left( {x^{m + 1} ,x^{m + 1} } \right)} \\ \end{array}} \right|{\bf{E}}_{m + 1} } \right) .$$
После приведения к единичной матрице главного минора ранга m получится следующая матрица:
$$\left( {\left. {\begin{array}{*{20}c} {b_1 } \\ {{\bf{E}}_m } \vdots \\ {b_m } \\ {\left( {x^1 ,x^{m + 1} } \right)} \cdots {\left( {x^m ,x^{m + 1} } \right)} {\left( {x^{m + 1} ,x^{m + 1} } \right)} \\ \end{array}} \right|\begin{array}{*{20}c} 0 \\ {{\bf{G}}_m^{ - 1} } \vdots \\ 0 \\ 0 \cdots 0 1 \\ \end{array}} \right) ,$$
где $$b_i $$ - неизвестные величины, полученные в ходе приведения главного минора к единичной матрице. Для завершения обращения матрицы $${\bf{G}}_{m + 1} $$ необходимо привести к нулевому виду первые m элементов последней строки и $$\left( {m + 1} \right)$$ -о столбца. Для обращения в ноль i -о элемента последней строки необходимо умножить i -ю строку на $$\left( {x^i ,x^{m + 1} } \right)$$ и вычесть из последней строки. После проведения этого преобразования получим
$$\left( {\left. {\begin{array}{*{20}c} {b_1 } \\ {{\bf{E}}_m } \vdots \\ {b_m } \\ 0 \cdots 0 {b_0 } \\ \end{array}} \right|\begin{array}{*{20}c} 0 \\ {{\bf{G}}_m^{ - 1} } \vdots \\ 0 \\ {c_1 } \cdots {c_m } 1 \\ \end{array}} \right) ,$$
где$$b_0 = \left( {x^{m + 1} , x^{m + 1} } \right) - \sum\limits_{i = 1}^m {\left( {x^i ,x^{m + 1} } \right)b_i } ,$$
$$c_i = - \sum\limits_{j = 1}^m {\left( {x^j ,x^{m + 1} } \right){\bf{G}}_{m,ji}^{ - 1} } .$$
$$b_0 = 0$$ только если новый эталон является линейной комбинацией первых m эталонов. Следовательно $$b_0 \ne 0$$. Для завершения обращения необходимо разделить последнюю строку на $$b_0 $$ и затем вычесть из всех предыдущих строк последнюю, умноженную на соответствующее номеру строки $$b_i$$. В результате получим следующую матрицу
$$\left( {\left. {\begin{array}{*{20}c} 0 \\ {{\bf{E}}_m } \vdots \\ 0 \\ 0 \cdots 0 1 \\ \end{array}} \right|\begin{array}{*{20}c} { - {{b_1 } \mathord{\left/ {\vphantom {{b_1 }{b_0 }}} \right. \kern-\nulldelimiterspace}{b_0 }}} \\ {\bf{F}} \vdots \\ { - {{b_m } \mathord{\left/ {\vphantom {{b_m }{b_0 }}} \right. \kern-\nulldelimiterspace}{b_0 }}} \\ {{{c_1 } \mathord{\left/ {\vphantom {{c_1 }{b_0 }}} \right. \kern-\nulldelimiterspace}{b_0 }}} \cdots {{{c_m } \mathord{\left/ {\vphantom {{c_m }{b_0 }}} \right. \kern-\nulldelimiterspace}{b_0 }}} {{1 \mathord{\left/ {\vphantom {1 {b_0 }}} \right. \kern-\nulldelimiterspace}{b_0 }}} \\ \end{array}} \right) ,$$
где $${\bf{F}}_{ij} = {\bf{G}}_{m,ij}^{ - 1} - {{b_i c_j }{\left/ {b_0 } \right }}$$. Поскольку i. Так как $$b_0 \ne 0$$ следовательно $$b_i = - c_i$$.
Обозначим через $${\bf{d}}$$ вектор$$\left( {\left( {x^1 ,x^{m + 1} } \right), \ldots ,\left( {x^m ,x^{m + 1} } \right)} \right),$$ через $${\bf{b}}$$ - вектор $$\left( {b_1 , \ldots ,b_m } \right)$$. Используя эти обозначения можно записать$${\bf{b}} = {\bf{G}}_m^{ - 1}{\bf{d}},{\rm{ }}b_0 = \left( {x^{m + 1} ,x^{m + 1} } \right) - \left( {{\bf{d}},{\bf{b}}} \right).$$ Матрица $${\bf{G}}_{m + 1}^{ - 1} $$ записывается в виде
$${\bf{G}}_{m + 1}^{ - 1} = \frac{1}{{b_0 }}\left( {\begin{array}{*{20}c} {b_0 {\bf{G}}_m^{ - 1} + {\bf{b}} \otimes {\bf{b}}} { - {\bf{b}}} \\ { - {\bf{b}}} {\bf{1}} \\ \end{array}} \right) .$$
Таким образом, при добавлении нового эталона требуется произвести следующие операции:
Таким образом, эта процедура требует $$m + n + mn + 3m^2 $$ операций. Тогда как стандартная схема полного пересчета потребует:
Всего $${{2m^3 + nm\left( {m + 1} \right)} \mathord{\left/ {\vphantom {{2m^3 + nm\left( {m + 1} \right)} 2}} \right. \kern-\nulldelimiterspace} 2}$$ операций, что в $$m $$ раз больше.
Используя ортогональную сеть (6), удалось добиться независимости способности сети к запоминанию и точному воспроизведению эталонов от степени скоррелированности эталонов. Так, например, ортогональная сеть смогла правильно воспроизвести все буквы латинского алфавита в написании, приведенном на рис. 8.1.
У сети (6) можно выделить два основных недостатка:
Оба этих недостатка можно устранить, изменив выбор весовых коэффициентов в (2).
Для увеличения числа линейно независимых эталонов, не приводящих к прозрачности сети, используется прием перехода к тензорным или многочастичным сетям [8.3, 8.4, 8.5, 8.6, 8.7].
Тензорным произведением $$k$$ $$n$$ -мерных векторов $$y^1 , \cdots ,y^k $$ называется $$k$$ -индексная величина $$b_{i_1 \cdots i_k }$$, у которой все индексы независимо пробегают весь набор значений от единицы до $$n$$, а $$b_{i_1 \cdots i_k } = y_{i_1 }^1 y_{i_2 }^2 \cdots y_{i_k }^k$$. $$k$$ -ой тензорной степенью вектора $$x$$ будем называть вектор $$x^{ \otimes k}$$, полученный как тензорное произведение $$k$$ векторов $$x$$. Вектор $$x^{ \otimes k} $$ является $$n^k $$ -мерным вектором. Однако пространство $$L\left( {\left\{ {x^{i^{ \otimes k}}} \right\}} \right)$$ имеет размерность, не превышающую величину $$r_{n,k} = \sum\limits_{i = 0}^k {{\bf{C}}_{n - 1}^i }$$, где $${\bf{C}}_p^q = \frac{{p!}}{{q!\left( {p - q} \right)!}} $$ - число сочетаний из $$p$$ по $$q$$.
Теорема. При k < n в ранг $$r_{n,k} $$ множества $$\left\{ {x^{ \otimes k} } \right\}$$ равен: $$r_{n,k} = \sum\limits_{i = 0}^k {{\bf{C}}_{n - 1}^i }$$.
(рис 8.2) "Тензорный" треугольник Паскаля Небольшая модернизация
n=2 в множестве X всего два неколлинеарных вектора.| n | k | nk | Ck - 1n + k - 1 | rn,k |
|---|---|---|---|---|
| 5 | 2 | 25 | 15 | 11 |
| 3 | 125 | 35 | 15 | |
| 10 | 3 | 1 000 | 220 | 130 |
| 6 | 1 000 000 | 5005 | 466 | |
| 8 | 100 000 000 | 24310 | 511 |
В таблица 8.1 приведено сравнение трех оценок информационной емкости тензорных сетей для некоторых значений n и k. Первая оценка - $$n^k $$ - заведомо завышена, вторая - $${\bf{C}}_{n + k - 1}^{k - 1}
$$ - дается формулой Эйлера для размерности пространства симметричных тензоров и третья - точное значение $$r_{n,k} $$
Как легко видеть из таблицы таблица 8.1, уточнение при переходе к оценке $$r_{nk} $$ является весьма существенным. С другой стороны, предельная информационная емкость тензорной сети (число правильно воспроизводимых образов) может существенно превышать число нейронов, например, для 10 нейронов тензорная сеть валентности 8 имеет предельную информационную емкость 511.
Легко показать, что если множество векторов $$\left\{ {x^i } \right\}$$ не содержит взаимно обратных, то размерность пространства $$L\left( {\left\{ {x^{i^{ \otimes n}} } \right\}} \right)$$ равна числу векторов в множестве $$\left\{ {x^i } \right\}$$. Сеть (2) для случая тензорных сетей имеет вид
$$x' = Sign\left( {\sum\limits_{i = 1}^m {\left( {x^{ \otimes k} ,x^{i^{ \otimes k}} } \right)x^i } } \right) = Sign\left( {\sum\limits_{i = 1}^m {\left( {x,x^i } \right)^k x^i } } \right) ,$$
а ортогональная тензорная сеть
$$x' = Sign\left( {\sum\limits_{i = 1}^m {\left( {x^{ \otimes k} ,v^i } \right)x^i } } \right) = Sign\left( {\sum\limits_{i = 1}^m {\sum\limits_{j = 1}^m {\gamma_{ij}^{ - 1} } \left( {x,x^j } \right)^k x^i } } \right) ,$$
где $$\gamma_{ij}^{-1} $$ - элемент матрицы$$\Gamma^{ - 1} \left( {\left\{ {x^{i^{ \otimes k}} } \right\}} \right).$$ Сеть (9) хорошо работает на слабо скоррелированных эталонах, а сеть (10) не чувствительна к степени скоррелированности эталонов.
Для того, чтобы при обработке переводить визуальные образов, отличающиеся только положением в рамке изображения, в один эталон, применяется следующий прием [8.7]. Преобразуем исходное изображение в некоторый вектор величин, не изменяющихся при сдвиге (вектор инвариантов). Простейший набор инвариантов дают автокорреляторы - скалярные произведения образа на сдвинутый образ, рассматриваемые как функции вектора сдвига.
В качестве примера рассмотрим вычисление сдвигового автокоррелятора для черно-белых изображений. Пусть дан двумерный образ $$S$$ размером $$p \times q = n$$. Обозначим точки образа как $$s_{ij}$$. Элементами автокоррелятора $$Ac\left( S \right)$$ будут величины$$a_{kl} = \sum\limits_{i = 1}^p {\sum\limits_{j = 1}^q {s_{ij} s_{i + k,j + l} } } ,$$ где $$s_{ij = 0} $$ при выполнении любого из неравенств $$i < 1,i > p,j < 1,j > q$$. Легко проверить, что автокорреляторы любых двух образов, отличающихся только расположением в рамке, совпадают. Отметим, что $$a_{ij} = a_{ - i, - j} $$ при всех $$i,j$$, и $$a_{ij} = 0$$ при выполнении любого из неравенств $$i < 1 - p,i > p - 1,j < 1 - q,j > q - 1$$. Таким образом, можно считать, что размер автокоррелятора равен $$p \times \left( {2q + 1} \right)$$.
Автокорреляторная сеть имеет вид
$$x' = Sign\left( {\sum\limits_{i = 1}^m {\left( {Ac\left( x \right),Ac\left( {x^i } \right)} \right)x^i } } \right) .$$
Сеть (11) позволяет обрабатывать различные визуальные образы, отличающиеся только положением в рамке, как один образ.
Подводя итоги, можно сказать, что все сети ассоциативной памяти типа (2) можно получить, комбинируя следующие преобразования:
Наиболее сложная сеть будет иметь вид:
$$x' = Sign\left( {\sum\limits_{i = 1}^m {\sum\limits_{j = 1}^m {\gamma_{ij}^{ - 1} } \left( {F\left( x \right),F\left( {x^j } \right)} \right)^k x^i } } \right) ,$$
где $$\gamma_{ij}^{ - 1} $$ - элементы матрицы, обратной матрице Грамма системы векторов$$\Gamma^{ - 1} \left( {\left\{ {F\left( {x^{i^{ \otimes k}} } \right)} \right\}} \right),$$ $$F\left( x \right)$$ - произвольное преобразование.
Работа ортогональных тензорных сетей при наличии помех сравнивалась с возможностями линейных кодов, исправляющих ошибки. Линейным кодом, исправляющим k ошибок, называется линейное подпространство в n -мерном пространстве над GF2, все вектора которого удалены друг от друга не менее чем на 2k+1 (см., например, [8.8]). Линейный код называется совершенным, если для любого вектора n -мерного пространства существует кодовый вектор, удаленный от данного не более, чем на k. Тензорной сети в качестве эталонов подавались все кодовые
векторы избранного для сравнения кода. Численные эксперименты с совершенными кодами показали, что тензорная сеть минимально необходимой валентности правильно декодирует все векторы. Для несовершенных кодов картина оказалась хуже - среди устойчивых образов тензорной сети появились "химеры" - векторы, не принадлежащие множеству эталонов.
В случае n=10, k=1 (см. табл. 8.1 2 и 3, строка 1) при валентностях 3 и 5 тензорная сеть работала как единичный оператор - все входные вектора передавались на выход сети без изменений. Однако уже при валентности 7 число химер резко сократилось и сеть правильно декодировала более 60% сигналов. При этом были правильно декодированы все векторы, удаленные от ближайшего эталона на расстояние 2, а часть векторов, удаленных от ближайшего эталона на расстояние 1, остались химерами. В случае n=10, k=2 (см. табл. 8.1 2 и 3,
строки 3, 4, 5) наблюдалось уменьшение числа химер с ростом валентности, однако часть химер, удаленных от ближайшего эталона на расстояние 2 сохранялась. Сеть правильно декодировала более 50% сигналов. Таким образом при малых размерностях и кодах, далеких от совершенных, тензорная сеть работает довольно плохо. Однако, уже при n=15, k=3 и валентности, большей 3 (см. табл. 8.1 2 и 3, строки 6, 7), сеть правильно декодировала все сигналы с тремя ошибками. В большинстве экспериментов число эталонов было больше числа нейронов.
Подводя итог, можно сказать, что качество работы сети возрастает с ростом размерности пространства и валентности и по эффективности устранения ошибок сеть приближается к коду, гарантированно исправляющему ошибки.
Работа выполнена при поддержке Красноярского краевого фонда науки, грант 6F0124.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.