Нейрокомпьютерные системы

этого устройст­ва с усилителями, выполняющими роль искусственных ней­ронов. Сопротивления, выполняющие роль весов, соединяют выход каждого нейрона с входами всех остальных. Чтобы удовлетворить условию устойчивости, выход нейрона не соединялся сопротивлением с его собственным входом, а веса брались симметричными, т.е. сопротивление от выхо­да нейрона i к входу нейрона j имело ту же величину, что и сопротивление от выхода нейрона j к входу нейрона i. Заметим, что усилители имеют прямой и инвертиро­ванный выходы. Это позволяет с помощью обычных положи­тельных сопротивлений реализовывать и те случаи, когда веса должны быть отрицательными. На рис. 6.4 показаны все возможные сопротивления, при этом никогда не возни­кает необходимости присоединять как прямой, так и ин­вертированный выходы нейрона к входу другого нейрона. В реальной системе каждый усилитель обладает ко­нечным входным сопротивлением и входной емкостью, что должно учитываться при расчете динамической характерис­тики. Для устойчивости сети не требуется равенства этих параметров для всех усилителей и их симметричности. Так как эти параметры влияют лишь на время получения реше­ния, а не на само решение, для упрощения анализа они исключены. Предполагается, что используется пороговая функция (предел сигмоидальной функции при X, стремящемся к бесконечности). Далее, все выходы изменяются в начале дискретных интервалов времени, называемых эпохами. В начале каждой эпохи исследуется сумма входов каждого нейрона. Если она больше порога, выход принимает единичное значение, если меньше - нулевое. На протяжении эпохи выходы нейронов не изменяются.

Рис. 6.4. Четырехбитовый аналого-цифровой преобразователь, использующий сеть Хопфилда.

Целью является такой выбор сопротивлений (весов), что непрерывно растущее напряжение X, приложенное к одновходовому терминалу, порождает множество из четы­рех выходов, представляющих двоичную запись числа, величина которого приближенно равна входному напряжению (рис. 6.5). Определим сначала функцию энергии следующим образом:

(6.7)

где Х - входное напряжение. Когда Е минимизировано, то получаются нужные выхо­ды. Первое выражение в скобках минимизируется, когда двоичное число, образованное выходами, наиболее близко (в среднеквадратичном смысле) к аналоговой величине входа X. Второе выражение в скобках обращается в нуль, когда все выходы равны 1 или 0, тем самым накладывая ограничение, что выходы принимают только двоичные зна­чения. Если уравнение (6.7) перегруппировать и сравнить с уравнением (6.2), то получим следующее выражение для весов:

wij=-2i+j, yi=2i

где wij - проводимость (величина, обратная сопротивле­нию) от выхода нейрона i к входу нейрона j (равная также проводимости от выхода нейрона j к входу нейрона 0); ij. - проводимость от входа Х к входу нейрона i. Чтобы получить схему с приемлемыми значениями сопротивлений и потребляемой мощности, все веса должны быть промасштабированы.

Идеальная выходная характеристика, изображенная на рис. 6.5, будет реализована лишь в том случае, если входы устанавливаются в нуль перед выполнением преобра­зования. Если этого не делать, сеть может попасть в локальный минимум энергии и дать неверный выход.

Задача коммивояжера

Задача коммивояжера является оптимизационной зада­чей, часто возникающей на практике. Она может быть сформулирована следующим образом: для некоторой группы городов с заданными расстояниями между ними требуется найти кратчайший маршрут с посещением каждого города один раз и с возвращением в исходную точку. Было дока­зано, что эта задача принадлежит большому множеству задач, называемых «NP-полными» (недетерминистски поли­номиальными) [3]. Для NP-полных задач не известно луч­шего метода решения, чем полный перебор всех возможных вариантов, и, по мнению большинства математиков, мало­вероятно, чтобы лучший метод был когда либо найден. Так как такой полный поиск практически неосуществим для большого числа городов, то эвристические методы исполь­зуются для нахождения приемлемых, хотя и неоптимальных решений. Описанное в работе [8] решение, основанное на сетях с обратными связями, является типичным в этом отношении. Все же ответ получается так быстро, что в определенных случаях метод может оказаться полезным. Допустим, что города, которые необходимо посетить, помечены буквами А, В, С и D, а расстояния между парами городов есть dab, dbc и т.д. Решением является упорядоченное множество из n городов. Задача состоит в отображении его в вычисли­тельную сеть с использованием нейронов в режиме с боль­шой крутизной характеристики ( приближается к бесконе­чности). Каждый город представлен строкой из n нейро­нов. Выход одного и только одного нейрона из них равен единице (все остальные равны нулю). Этот равный единице выход нейрона показывает порядковый номер, в котором данный город посещается при обходе. На рис. 6.6 показан случай, когда город С посещается первым, город А - вторым, город D - третьим и город В - четвертым. Для такого представления требуется n2 нейронов - число, которое быстро растет с увеличением числа городов. Длина такого маршрута была бы равна dca + dad + ddb + dbc. Так как каждый город посещается только один раз и в каждый момент посещается лишь один город, то в каждой строке и в каждом столбце имеется по одной единице. Для задачи с п городами всего имеется п! различных маршрутов обхода. Если п = 60, то имеется 69 34155 х 1078 возможных маршрутов. Если принять во внимание, что в нашей галактике (Млечном Пути) имеете) лишь 1011 звезд, то станет ясным, что полный перебор всех возможных маршрутов для 1000 городов даже и. самом быстром в мире компьютере займет время, сравнимо с геологической эпохой. Продемонстрируем теперь, как сконструировать сет: для решения этой NP-полной проблемы. Каждый нейрон снабжен двумя индексами, которые соответствуют городу порядковому номеру его посещения в маршруте. Например OUTxj = 1 показывает, что город х был j-ым по порядку j - ым городом маршрута.

функция энергии должна удовлетворять двум требованиям: во-первых, должна быть малой только для тех решений, которые имеют по одной единице в каждой строке и каждом столбце; во-вторых, должна оказывать предпочтение решениям с короткой длиной маршрута. Первое требование удовлетворяется введением следующей, состоящей из трех сумм, функции энергии:

(6.9)


где А, В и С- некоторые константы. Этим достигается выполнение следующих условий:

  1. Первая тройная сумма равна нулю в том и только в том случае, если каждая строка (город) содержит не более одной единицы.

2. Вторая тройная сумма равна нулю в том и только в том случае, если каждый столбец (порядковый номер посещения) содержит не более одной единицы.

3. Третья сумма равна нулю в том и только в том случае, если матрица содержит ровно п единиц.

Второе требование - предпочтение коротким маршру­там - удовлетворяется с помощью добавления следующего члена к функции энергии:

(6.10)


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

Получаем

Wxi,yi = -Axy (1-ij) - Bij (1- xy ) - C - Dxy(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 допустимых маршрутов. Сообщалось, что сходимость решений, полученных по методу Хопфилда для задачи коммивояжера, в сильной степени зависит от коэффициентов, и не имеется система­тического метода определения их значений [II]. В этой работе предложена другая функция энергии с единственным коэффициентом, значение которого легко определяется. В дополнение предложен новый сходящийся алгоритм. Можно ожидать, что новые более совершенные методы будут раз­рабатываться, так как полностью удовлетворительное решение нашло бы массу применений.

ОБСУЖДЕНИЕ

Локальные минимумы

Сеть, выполняющая аналого-цифровое преобразование, всегда находит единственное оптимальное решение. Это обусловлено простой природой поверхности энергии в этой задаче. В задаче коммивояжера поверхность энергии силь­но изрезана, изобилует склонами, долинами и локальными минимумами и нет гарантии, что будет найдено глобальное оптимальное решение и что полученное решение будет допустимым. При этом возникают серьезные вопросы относи­тельно надежности сети и доверия к ее решениям. Эти недостатки сети смягчаются тем обстоятельством, что нахождение глобальных минимумов для NP-полных задач является очень трудной задачей, которая не может быть решена в приемлемое время никаким другим методом. Дру­гие методы значительно более медленны и дают не лучшие результаты.

Скорость

Способность сети быстро производить вычисления является ее главным достоинством. Она обусловлена высо­кой степенью распараллеливания вычислительного процес­са. Если сеть реализована на аналоговой электронике, то решение редко занимает промежуток времени, больший не­скольких постоянных времени сети. Более того, время сходимости слабо зависит от размерности задачи. Это резко контрастирует с более чем экспоненциальным ростом времени решения при использовании обычных подходов. Моделирование с помощью однопроцессорных систем не позволяет использовать преимущества параллельной архите­ктуры, но современные мультипроцессорные системы типа Connection Machine (65536 процессоров!) весьма много­обещающи для решения трудных задач.

Функция энергии

Определение функции энергии сети в зависимости от . задачи не является тривиальным. Существующие решения были получены с помощью изобретательности, математичес­кого опыта и таланта, которые не разбросаны в изобилии. Для некоторых задач существуют систематические методы нахождения весов сети. Эти методы излагаются в гл. 7.

Емкость сети

Актуальным предметом исследований является макси­мальное количество запоминаемой информации, которое может храниться в сети Хопфилда. Так как сеть из N двоичных нейронов может иметь 2n состояний, то исследо­ватели были удивлены, обнаружив, что максимальная ем­кость памяти оказалась значительно меньшей. Если бы могло запоминаться большое количество информационных единиц, то сеть не стабилизировалась бы на некоторых из них. Более того, она могла бы помнить то, чему ее не учили, т.е. могла стабилизироваться на решении, не являющемся требуемым вектором. Эти свойства ставили в тупик первых исследователей, которые не имели математических методов для предварительной оценки емко­сти памяти сети. Последние исследования пролили свет на эту пробле­му. Например, предполагалось, что максимальное коли­чество запоминаемой информации, которое может хранить­ся в сети из N нейронов и безошибочно извлекаться, меньше чем cN2, где с - положительная константа, боль­шая единицы. Хотя этот предел и достигается в некоторых случаях, в общем случае он оказался слишком оптимисти­ческим. В работе [4] было экспериментально показано, что в общем случае предельное значение емкости ближе к 0,15N. В работе [1] было показано, что число таких состояний не может превышать N, что согласуется с на­блюдениями над реальными системами и является наилучшей на сегодняшний день оценкой.

ВЫВОДЫ

Сети с обратными связями являются перспективным объектом для дальнейших исследований. Их динамическое поведение открывает новые интересные возможности и ставит специфические проблемы. Как отмечается в гл. 9, эти возможности и проблемы сохраняются при реализации нейронных сетей в виде оптических систем.


Глава 7 Двунаправленная ассоциативная память

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: