АБЗАЦ: Нейрокомпьютерная техника: Теория и практика / Уоссермен Ф. / Учеба / 8 сторінка

Жанр: Учеба

Нейрокомпьютерная техника: Теория и практика

сторінка №8

...з n городов. Задача состоит в
отображении его в вычислительную сеть с использованием нейронов в режиме с
большой крутизной характеристики (( приближается к бесконечности). Каждый
город представлен строкой из n нейронов. Выход одного и только одного
нейрона из них равен единице (все остальные равны нулю). Этот равный единице
выход нейрона показывает порядковый номер, в котором данный город посещается
при обходе. На рис. 6.6 показан случай, когда город C посещается первым,
город A - вторым, город D - третьим и город B - четвертым. Для такого
представления требуется п2 нейронов - число, которое быстро растет с
увеличением числа городов. Длина такого маршрута была бы равна dca + dad +
ddb + dbc. Так как каждый город посещается только один раз и в каждый момент
посещается лишь один город, то в каждой строке и в каждом столбце имеется по
одной единице. Для задачи с п городами всего имеется п! различных маршрутов
обхода. Если п = 60, то имеется 6934155х1078 возможных маршрутов. Если
принять во внимание, что в нашей галактике (Млечном Пути) имеется лишь 1011
звезд, то станет ясным, что полный перебор всех возможных маршрутов для 1000
городов даже на самом быстром в мире компьютере займет время, сравнимое с
геологической эпохой.
Продемонстрируем теперь, как сконструировать сеть для решения этой
NP-полной проблемы. Каждый нейрон снабжен двумя индексами, которые
соответствуют городу и порядковому номеру его посещения в маршруте.
Например, OUTxj = 1 показывает, что город х был j-ым по порядку городом
маршрута.
Функция энергии должна удовлетворять двум требованиям: во-первых, должна
быть малой только для тех решений, которые имеют по одной единице в каждой
строке и в каждом столбце; во-вторых, должна оказывать предпочтение решениям
с короткой длиной маршрута.
Первое требование удовлетворяется введением следующей, состоящей из трех
сумм, функции энергии:
, (6.9)
где A, B и C - некоторые константы. Этим достигается выполнение следующих
условий:
1. Первая тройная сумма равна нулю в том и только в том случае, если
каждая строка (город) содержит не более одной единицы.
2. Вторая тройная сумма равна нулю в том и только в том случае, если
каждый столбец (порядковый номер посещения) содержит не более одной единицы.
3. Третья сумма равна нулю в том и только в том случае, если матрица
содержит ровно п единиц.
город
Порядок следования

1

2

3

4

0

1

0

1

0

1

0

Рис. 6.6. Маршрут коммивояжера
Второе требование - предпочтение коротким маршрутам - удовлетворяется с
помощью добавления следующего члена к функции энергии: , (6.10)
Заметим, что этот член представляет собой длину любого допустимого
маршрута. Для удобства индексы определяются по модулю n, т. е. OUTn+j =
OUTj, a D - некоторая константа.
При достаточно больших значениях A, B и C низкоэнергетические состояния
будут представлять допустимые маршруты, а большие значения D гарантируют,
что будет найден короткий маршрут.
Теперь зададим значения весов, т. е. установим соответствие между членами
в функции энергии и членами общей формы (см. уравнение 6.2)).

Получаем
wxi,yi = -A?xy(1 - ?ij) (не допускает более одной единицы в строке)
-B?ij(1 - ?xy) (не допускает более одной единицы в столбце) -С (глобальное
ограничение) -Ddxy(?j,i+1 + ?j,i-1) (член, отвечающий за длину цикла),
где ?ij = 1, если i = j, в противном случае ?ij = 0. Кроме того, каждый
нейрон имеет смещающий вес хi, соединенный с +1 и равный Сп.
В работе [8] сообщается об эксперименте, в котором задача коммивояжера
была решена для 10 городов. В этом случае возбуждающая функция была равна
OUT = 1/2 [1 + th(NET/U0)].
Как показали результаты, 16 из 20 прогонов сошлись к допустимому маршруту
и около 50% решений оказались кратчайшими маршрутами, как это было
установлено с помощью полного перебора. Этот результат станет более
впечатляющим, если осознать, что имеется 181440 допустимых маршрутов.
Сообщалось, что сходимость решений, полученных по методу Хопфилда для
задачи коммивояжера, в сильной степени зависит от коэффициентов, и не
имеется систематического метода определения их значений [11]. В этой работе
предложена другая функция энергии с единственным коэффициентом, значение
которого легко определяется. В дополнение предложен новый сходящийся
алгоритм. Можно ожидать, что новые более совершенные методы будут
разрабатываться, так как полностью удовлетворительное решение нашло бы массу
применений. ОБСУЖДЕНИЕ Локальные минимумы
Сеть, выполняющая аналого-цифровое преобразование, всегда находит
единственное оптимальное решение. Это обусловлено простой природой
поверхности энергии в этой задаче. В задаче коммивояжера поверхность энергии
сильно изрезана, изобилует склонами, долинами и локальными минимумами и нет
гарантии, что будет найдено глобальное оптимальное решение и что полученное
решение будет допустимым. При этом воникают серьезные вопросы относительно
надежности сети и доверия к ее решениям. Эти недостатки сети смягчаются тем
обстоятельством, что нахождение глобальных минимумов для NP-полных задач
является очень трудной задачей, которая не может быть решена в приемлемое
время никаким другим методом. Другие методы значительно более медленны и
дают не лучшие результаты. Скорость
Способность сети быстро производить вычисления является ее главным
достоинством. Она обусловлена высокой степенью распараллеливания
вычислительного процесса. Если сеть реализована на аналоговой электронике,
то решение редко занимает промежуток времени, больший нескольких постоянных
времени сети. Более того, время сходимости слабо зависит от размерности
задачи. Это резко контрастирует с более чем экспоненциальным ростом времени
решения при использовании обычных подходов. Моделирование с помощью
однопроцессорных систем не позволяет использовать преимущества параллельной
архитектуры, но современные мультипроцессорные системы типа Connection
Machine (65536 процессоров!) весьма многообещающи для решения трудных задач.
Функция энергии
Определение функции энергии сети в зависимости от задачи не является
тривиальным. Существующие решения были получены с помощью изобретательности,
математического опыта и таланта, которые не разбросаны в изобилии. Для
некоторых задач существуют систематические методы нахождения весов сети. Эти
методы излагаются в гл. 7. Емкость сети
Актуальным предметом исследований является максимальное количество
запоминаемой информации, которое может храниться в сети Хопфилда. Так как
сеть из n двоичных нейронов может иметь 2n состояний, то исследователи были
удивлены, обнаружив, что максимальная емкость памяти оказалась значительно
меньшей.
Если бы могло запоминаться большое количество информационных единиц, то
сеть не стабилизировалась бы на некоторых из них. Более того, она могла бы
помнить то, чему ее не учили, т. е. могла стабилизироваться на решении, не
являющемся требуемым вектором. Эти свойства ставили в тупик первых
исследователей, которые не имели математических методов для предварительной
оценки емкости памяти сети.
Последние исследования пролили свет на эту проблему. Например,
предполагалось, что максимальное количество запоминаемой информации, которое
может храниться в сети из N нейронов и безошибочно извлекаться, меньше чем
cN2, где c - положительная константа, большая единицы. Хотя этот предел и
достигается в некоторых случаях, в общем случае он оказался слишком
оптимистическим. В работе [4] было экспериментально показано, что в общем
случае предельное значение емкости ближе к 0,15N. В работе [1] было
показано, что число таких состояний не может превышать N, что согласуется с
наблюдениями над реальными системами и является наилучшей на сегодняшний
день оценкой. ВЫВОДЫ
Сети с обратными связями являются перспективным объектом для дальнейших
исследований. Их динамическое поведение открывает новые интересные
возможности и ставит специфические проблемы. Как отмечается в гл. 9, эти
возможности и проблемы сохраняются при реализации нейронных сетей в виде
оптических систем. Литература
1. Abu-Mostafa Y. S., St. Jacques, J. 1985. Information capacity of the
Hopfield model. IEEE Transactions on Information Theory 31(4):461-64.

2. Cohen M. A., Grossberg S. G. 1983. Absolute stability of global
pattern formation and parallel memory storage by compatitive neural
networks. IEEE Transactions on Systems, Man and Cybernetics 13:815-26.
3. Qarey M. R., Johnson D. S. 1979. Computers and intrac-tality. New
York: W.H. Freeman.
4. Grossberg S. 1987. The adapptive brain, vol. 1 and 2. Amsterdam:
North-Holland.
5. Hinton G. E., Sejnowski T. J. 1986. Learning and relearning in
Boltzmann machines. In Parallel distributed processing, vol. 1, pp. 282-317.
Cambridge, MA: MIT Press.
6. Horfield J. J. 1982. Neural networks and physical systems with
emergent collective computational abilities. Proceedings of the National
Academy of Science 79:2554-58.
7. Horfield J. J. 1984. Neural with graded response have collective
computational properties like those of two-state neurons. Proceedings of the
National Academy of Science 81:3088-92.
8. Horfield J. J., Tank D. W. 1985. Neural computation of decisions in
optimization problems. Biological Cybernetics 52:141-52.
9. Horfield J. J., Tank D. W. 1986. Computing with neural circuits: A
model.Science 233:625-33.
10. Tank D. W., Horfield J. J. 1986. Simple "neural" optimization
networks: An A/D converter, signal decision circuit, and a linear
programming circuit. Circuits and Systems IEEE Transactions on
CAS-33(5):533-41.
11. Van den Bout D. E. and Miller Т. К. 1988. A traveling salesman
objective function that works. Proceedings of the IEEE International
Conference on Neural Networks, vol. 2, pp. 299-304. San Diego, CA: SOS
Printing.

Глава 7.

Двунаправленная ассоциативная память
Память человека часто является ассоциативной; один предмет напоминает нам
о другом, а этот другой о третьем. Если позволить нашим мыслям, они будут
перемещаться от предмета к предмету по цепочке умственных ассоциаций. Кроме
того, возможно использование способности к ассоциациям для восстановления
забытых образов. Если мы забыли, где оставили свои очки, то пытаемся
вспомнить, где видели их , в последний раз, с кем разговаривали и что
делали. Посредством этого устанавливается конец цепочки ассоциаций, что
позволяет нашей памяти соединять ассоциации для получения требуемого образа.
Ассоциативная память, рассмотренная в гл. 6, является, строго говоря,
автоассоциативной, это означает, что образ может быть завершен или
исправлен, но не может быть ассоциирован с другим образом. Данный факт
является результатом одноуровневой структуры ассоциативной памяти, в которой
вектор появляется на выходе тех же нейронов, на которые поступает входной
вектор.
Двунаправленная ассоциативная память (ДАП) является гетероассоциативной;
входной вектор поступает на один набор нейронов, а соответствующий выходной
вектор вырабатывается на другом наборе нейронов. Как и сеть Хопфилда, ДАП
способна к обобщению, вырабатывая правильные реакции, несмотря на искаженные
входы. Кроме того, могут быть реализованы адаптивные версии ДАП, выделяющие
эталонный образ из зашумленных экземпляров. Эти возможности сильно
напоминают процесс мышления человека и позволяют искусственным нейронным
сетям сделать шаг в направлении моделирования мозга.
В последних публикациях [9,12] представлено несколько форм реализации
двунаправленной ассоциативной памяти. Как большинство важных идей,
изложенные в этих работах идеи имеют глубокие корни; например, в работе
Гроссберга [6] представлены некоторые важные для ДАП концепции. В данной
работе ссылки приводятся не с целью разрешения вопроса о приоритете
исследовательских работ, а исключительно для освещения их вклада в
исследовательскую тематику. СТРУКТУРА ДАП

Рис. 7.1. Конфигурация двунаправленной ассоциативной памяти
На рис. 7.1 приведена базовая конфигурация ДАП. Эта конфигурация
существенно отличается от используемой в работе [9]. Она выбрана таким
образом, чтобы подчеркнуть сходство с сетями Хопфилда и предусмотреть
увеличения количества слоев. На рис. 7.1 входной вектор А обрабатывается
матрицей весов W сети, в результате чего вырабатывается вектор выходных
сигналов нейронов В. Вектор В затем обрабатывается транспонированной
матрицей Wt весов сети, которая вырабатывает новые выходные сигналы,
представляющие собой новый входной вектор А. Этот процесс повторяется до тех
пор, пока сеть не достигнет стабильного состояния, в котором ни вектор А, ни
вектор В не изменяются. Заметим, что нейроны в слоях 1 и 2 функционируют,
как и в других парадигмах, вычисляя сумму взвешенных входов и вычисляя по
ней значение функции активации F. Этот процесс может быть выражен следующим
образом: (7.1)
или в векторной форме: В = F(AW), (7.2)
где В - вектор выходных сигналов нейронов слоя 2, А - вектор выходных
сигналов нейронов слоя 1, W - матрица весов связей между слоями 1 и 2, F -
функция активации.

Аналогично A = F(BWt) (7.3)
где Wt является транспозицией матрицы W.
Как отмечено в гл. 1, Гроссберг показал преимущества использования
сигмоидальной (логистической) функции активации (7.3)
где OUTi - выход нейрона i, NETi - взвешенная сумма входных сигналов
нейрона i, ( - константа, определяющая степень кривизны.
В простейших версиях ДАП значение константы ( выбирается большим, в
результате чего функция активации приближается к простой пороговой функции.
В дальнейших рассуждениях будем предполагать, что используется пороговая
функция активации.
Примем также, что существует память внутри каждого нейрона в слоях 1 и 2
и что выходные сигналы нейронов изменяются одновременно с каждым тактом
синхронизации, оставаясь постоянными между этими тактами. Таким образом,
поведение нейронов может быть описано следующими правилами:
OUTi(n+1) = 1, если NETi(n)>0,
OUTi(n+l) = 0, если NETi(n)<0,
OUTi(n+l) = OUT(n), если NETi(n) = 0,
где OUTi(n) представляет собой величину выходного сигнала нейрона i в
момент времени п.
Заметим, что как и в описанных ранее сетях слой 0 не производит
вычислений и не имеет памяти; он является только средством распределения
выходных сигналов слоя 2 к элементам матрицы Wt. ВОССТАНОВЛЕНИЕ ЗАПОМНЕННЫХ
АССОЦИАЦИЙ
Долговременная память (или ассоциации) реализуется в весовых массивах W и
Wt. Каждый образ состоит из двух векторов: вектора A, являющегося выходом
слоя 1, и вектора B, ассоциированного образа, являющегося выходом слоя 2.
Для восстановления ассоциированного образа вектор A или его часть
кратковременно устанавливаются на выходах слоя 1. Затем вектор A удаляется и
сеть приводится в стабильное состояние, вырабатывая ассоциированный вектор B
на выходе слоя 2. Затем вектор B воздействует через транспонированную
матрицу Wt, воспроизводя воздействие исходного входного вектора A на выходе
слоя 1. Каждый такой цикл вызывает уточнение выходных векторов слоя 1 и 2 до
тех пор, пока не будет достигнута точка стабильности в сети. Эта точка может
быть рассмотрена как резонансная, так как вектор передается обратно и вперед
между слоями сети, всегда обрабатывая текущие выходные сигналы, но больше не
изменяя их. Состояние нейронов представляет собой кратковременную память
(КП), так как оно может быстро изменяться при появлении другого входного
вектора. Значения коэффициентов весовой матрицы образуют долговременную
память и могут изменяться только на более длительном отрезке времени,
используя представленные ниже в данном разделе методы.
В работе [9] показано, что сеть функционирует в направлении минимизации
функции энергии Ляпунова в основном таким же образом, как и сети Хопфилда в
процессе сходимости (см. гл. 6). Таким образом, каждый цикл модифицирует
систему в направлении энергетического минимума, расположение которого
определяется значениями весов.

Рис. 7.2. Энергетическая поверхность двунаправленной ассоциативной памяти
Этот процесс может быть визуально представлен в форме направленного
движения мяча по резиновой ленте, вытянутой над столом, причем каждому
запомненному образу соответствует точка, "вдавленная" в направлении
поверхности стола. Рис. 7.2 иллюстрирует данную аналогию с одним запомненным
образом. Данный процесс формирует минимум гравитационной энергии в каждой
точке, соответствующей запомненному образу, с соответствующим искривлением
поля притяжения в направлении к данной точке. Свободно движущийся мяч
попадает в поле притяжения и в результате будет двигаться в направлении
энергетического минимума, где и остановится. КОДИРОВАНИЕ АССОЦИАЦИЙ
Обычно сеть обучается распознаванию множества образов. Обучение
производится с использованием обучающего набора, состоящего из пар векторов
A и B. Процесс обучения реализуется в форме вычислений; это означает, что
весовая матрица вычисляется как сумма произведении всех векторных пар
обучающего набора. B символьной форме

Предположим, что все запомненные образы представляют собой двоичные
векторы. Это ограничение покажется менее строгим, если вспомнить, что все
содержимое Библиотеки Конгресса может быть закодировано в один очень длинный
двоичный вектор. В работе [11] показана возможность достижения более высокой
производительности при использовании биполярных векторов. При этом векторная
компонента, большая чем 0, становится +1, а компонента, меньшая или равная
0, становится -1.
Предположим, что требуется обучить сеть с целью запоминания трех пар
двоичных векторов, причем векторы Ai имеют размерность такую же, как и
векторы Вi. Надо отметить, что это не является необходимым условием для
работы алгоритма; ассоциации могут быть сформированы и между векторами
различной размерности.
Исходный вектор
Ассоциированный вектор
Бинарная версия
A1 = (1,0,0)
B1 = (0,0,1)
A'1 = (1,-1,-1)
B'1 = (-1,-1,1)
A2 = (0,1,0)
B2 = (0,1,0)
A'1 = (-1,1,-1)
B'1 = (-1,1,-1)
A3 = (0,0,1)
B3 = (1,0,0)
A'1 = (-1,-1,1)
B'1 = (1,-1,-1)

Вычисляем весовую матрицу W = A'1t B'1 + A'2t B'2 + A'3t B'3
-1
-1

1

-1

1

+
-1

1

=
-1
-1

3

-1
-1

что дает значение (1,0,0) после применения пороговой функции, образуя
величину вектора A1.
Этот пример показывает, как входной вектор A с использованием матрицы W
производит выходной вектор B. В свою очередь вектор B с использованием
матрицы Wt производит вектор A, таким образом в системе формируется
устойчивое состояние и резонанс.
ДАП обладает способностью к обобщению. Например, если незавершенный или
частично искаженный вектор подается в качестве A, сеть имеет тенденцию к
выработке запомненного вектора B, который в свою очередь стремится исправить
ошибки в A. Возможно, для этого потребуется несколько проходов, но сеть
сходится к воспроизведению ближайшего запомненного образа.
Системы с обратной связью могут иметь тенденцию к колебаниям; это
означает, что они могут переходить от состояния к состоянию, никогда не
достигая стабильности. В [9] доказано, что все ДАП безусловно стабильны при
любых значениях весов сети. Это важное свойство возникает из отношения
транспонирования между двумя весовыми матрицами и означает, что любой набор
ассоциаций может быть изучен без риска возникновения нестабильности.
Существует взаимосвязь между ДАП и рассмотренными в гл. 6 сетями
Хопфилда. Если весовая матрица W является квадратной и симметричной, то
W=Wt. В этом случае, если слои 1 и 2 являются одним и тем же набором
нейронов, ДАП превращается в автоассоциативную сеть Хопфилда. ЕМКОСТЬ ПАМЯТИ
Как и сети Хопфилда, ДАП имеет ограничения на максимальное количество
ассоциаций, которые она может точно воспроизвести. Если этот лимит превышен,
сеть может выработать неверный выходной сигнал, воспроизводя ассоциации,
которым не обучена.
В работе [9] приведены оценки, в соответствии с которыми количество
запомненных ассоциаций не может превышать количества нейронов в меньшем
слое. При этом предполагается, что емкость памяти максимизирована
посредством специального кодирования, при котором количество компонент со
значениями +1 равно количеству компонент со значениями -1 в каждом
биполярном векторе. Эта оценка оказалась слишком оптимистичной. Работа [13]
по оценке емкости сетей Хопфилда может быть легко расширена для ДАП. Можно
показать, что если L векторов выбраны случайно и представлены в указанной
выше форме, и если L меньше чем n/(2 1og2 п), где п - количество нейронов в
наименьшем слое, тогда все запомненные образы, за исключением "малой части",
могут быть восстановлены. Например, если п = 1024, тогда L должно быть
меньше 51. Если все образы должны восстанавливаться, L должно быть меньше
re/(4 1og2 п), то есть меньше 25. Эти, скорее озадачивающие, результаты
показывают, что большие системы могут запоминать только умеренное количество
ассоциаций.
В работе [7] показано, что ДАП может иметь до 2n стабильных состояний,
если пороговое значение Т выбирается для каждого нейрона. Такая
конфигурация, которую авторы назвали негомогенной ДАП, является расширением
исходной гомогенной ДАП, в которой все пороги были нулевыми.
Модифицированная передаточная функция нейрона принимает в этом случае
следующий вид: OUTi(n+l) = l, если NETi(n) > Ti, OUTi(n+l) = l, если NETi(n)
< Ti, OUTi(n+l) = OUTi(n), если NETi(n) = Ti,
где OUTi(t) - выход нейрона i в момент времени t.
Посредством выбора соответствующего порога для каждого нейрона количество
стабильных состояний может быть сделано любым в диапазоне от 1 до 2, где п
есть количество нейронов в меньшем слое. К сожалению, эти состояния не могут
быть выбраны случайно; они определяются жесткой геометрической процедурой.
Если пользователь выбирает L состояний случайным образом, причем L меньше
(0,68)n2/{[log2(п)] + 4}2, и если каждый вектор имеет 4 + log2n компонент,
равных +1, и остальные, равные -1, то можно сконструировать негомогенную
ДАП, имеющую 98% этих векторов в качестве стабильных состояний. Например,
если п = 1024, L должно быть меньше 3637, что является существенным
улучшением по сравнению с гомогенными ДАП, но это намного меньше 21024
возможных состояний.
Ограничение количества единиц во входных векторах представляет серьезную
проблему, тем более, что теория, которая позволяет перекодировать
произвольный набор векторов в такой "разреженный" набор, отсутствует.
Возможно, однако, что еще более серьезной является проблема некорректной
сходимости. Суть этой проблемы заключается в том, что сеть может не
производить точных ассоциаций вследствие природы поля притяжения; об ее
форме известно очень немногое. Это означает, что ДАП не является
ассоциатором по отношению к ближайшему соседнему образу. В действительности
она может производить ассоциации, имеющие слабое отношение ко входному
вектору. Как и в случае гомогенных ДАП, могут встречаться ложные стабильные
состояния и немногое известно об их количестве и природе.

Несмотря на эти проблемы, ДАП остается объектом интенсивных исследований.
Основная привлекательность ДАП заключается в ее простоте. Кроме того, она
может быть реализована в виде СБИС (либо аналоговых, либо цифровых), что
делает ее потенциально недорогой. Так как наши знания постоянно растут,
ограничения ДАП могут быть сняты. В этом случае как в экспериментальных, так
и в практических приложениях ДАП будет являться весьма перспективным и
полезным классом искусственных нейронных сетей. НЕПРЕРЫВНАЯ ДАП
В предшествующем обсуждении нейроны в слоях 1 и 2 рассматривались как
синхронные, каждый нейрон обладает памятью, причем все нейроны изменяют
состояния одновременно под воздействием импульса от центральных часов. В
асинхронной системе любой нейрон свободен изменять состояние в любое время,
когда его вход предписывает это сделать.
Кроме того, при определении фу...

Подання

Література

Періодика

Чтиво

Вивчення

Нейрокомпьютерная техника: Теория и практика

1

Посмотри в окно!

Поділитися у соцмережах