neironne_seti_i_neirokompjuter (1085713), страница 13
Текст из файла (страница 13)
процессобучения исключается. Если этот образ характеризуется n-мерным векторомX = (x1, …, xn)T, то веса соединений определяются по формулам:ì xi x j , для i ¹ jwij = í, для i = jî0.(2.50)В этом случае сеть Хопфилда, характеризуемая матрицей W ипорогами Ti = 0, i=1, 2, …, n, запоминает предъявленный образ.Для доказательства определим( ((å x )x )) = (x ) = Xf(WX) = ( f å wij x j ) = ( f å xi x j x j ) = f2jii.Веса wij можно умножить на некоторый положительный коэффициент(например, 1/n).Использование такого коэффициента особенно целесообразно в техслучаях, когда запоминаемые образы характеризуются большим числомпризнаков (например, видеоизображение отображается большим числомпикселей).67PDF created with pdfFactory trial version www.pdffactory.comПример 2.1.
Воспроизведение корректного изображенияс помощью сети ХопфилдаИмеется изображение из четырех пикселей:+1-1-1+1Соответствующий вектор (образ) имеет вид: X = (1,-1,-1,1)T.Стационарная сеть Хопфилда содержит при этом 4 элемента (нейрона).Ее весовая матрица рассчитывается на основе (2.50) и принимает видæ 0 -1 -1 1 ö÷ç1 - 1÷ç-1 0W= ç.-1 10 - 1÷÷çç 1 -1 -1 0 ÷øèПри этом легко можно убедиться в справедливости равенстваX = f(WX).Подадим на входы сети искаженный образ:11-11Можно легко установить, что нейронной сети потребуется лишь однаитерация, чтобы выдать корректное изображение.2.5.3.
Распознавание образов сетями ХопфилдаОбычно сети Хопфилда разрабатываются для запоминания ипоследующего распознавания большого количества образов (изображений).Обозначим через X1, …, XK эти образы, причем:Xj = (xj1, …, xjn)T,j = 1, 2, …, k,где xji (j = 1, 2, …, k; i = 1, 2, …, n) – i-я составляющая j-го образа.Подобно (2.50) введем матрицу Ws для s–го образа с весами68PDF created with pdfFactory trial version www.pdffactory.com(2.51)ìï x si x sj , s = 1, k , i ¹ jwijs = íïî0 , s = 1, k , i = j.(2.52)Из этих матриц можно образовать результирующую матрицу сети:W = (W1+ … +Wk)/n ,(2.53)где n – размерность векторов (например, число пикселей в представленииизображения).Если имеется немного изображений (т.е.
k мало), то нейронная сеть сматрицей (2.52) запоминает k образов, естественно, что изображения несильно коррелированны. Если же число k велико, то матрица (2.53)оказывается недостаточной для запоминания всех k изображений. С ростом kуменьшается вероятность воспроизведения образа.
Приведем утверждениеотносительно числа k запоминаемых образов при использовании сетиХопфилда из n нейронов.Пусть k – число образов, n – число признаков (пикселей), а образы,подлежащие запоминанию – некоррелированы, т.е. для двух изображений j иs суммаå x ji xsi.(2.54)iмала. При этом при подаче на вход сети с весовой матрицей (2.53) одногообраза каждый пиксель корректно воспроизводится с вероятностью p @ 0,99при выполнении условия:k £ 0,15n(n ® ¥ ) .(2.55)Пример 2.2.
Запоминание и корректное воспроизведениемножества образов с помощью сети ХопфилдаОбраз характеризуется тысячью признаками (n = 1000). В этом случаебинарная сеть Хопфилда в состоянии запомнить и корректно воспроизвестидо 150 образов (например, видеоизображений).В работе сети Хопфилда можно выделить следующие три стадии.1. Инициализация сети: на этой стадии рассчитываются все веса сетидля некоторого множества образов. Эти веса не определяются наоснове рекуррентной процедуры, используемой во многихалгоритмах обучения с поощрением.2. Ввод нового образа: нейроны сети устанавливаются всоответствующее начальное состояние по алгоритму (2.43) – (2.48).69PDF created with pdfFactory trial version www.pdffactory.com3.
Затухающий колебательный процесс: путем использованияитеративной процедуры рассчитывается последовательностьсостояний сети до тех пор, пока не будет достигнуто стабильноесостояние, т.е.oj(t+1) = oj(t) ,j = 1, 2, …, n(2.56)или в качестве выходов сети используются значения (2.56), прикоторых сеть находится в динамическом равновесии:O = f(WO) ,(2.57)где O – выходной вектор сети.Выход бинарной сети Хопфилда, содержащей n нейронов, может бытьотображен бинарным вектором O состояния сети. Общее число такихсостояний – 2n (вершины n-мерного гиперкуба).
При вводе нового входноговектора состояние сети изменяется от одной вершины к другой додостижения сетью устойчивого состояния.Из теории систем с обратными связями известно: для обеспеченияустойчивости системы ее изменения с течением времени должныуменьшатся. В противном случае возникают незатухающие колебания.Для таких сетей Коуэном (Cohen) и Гроссбергом (Grossberg) (1983)доказана теорема, формулирующая достаточные условия устойчивости сетейс обратными связями.Рекуррентные сети устойчивы, если весовая матрица W = (wij)симметрична, а на ее главной диагонали – нули:1) wij = wji2) wii = 0для всех i ¹ j ;для всех i .(2.58)Обратим внимание, что условия данной теоремы достаточны, но ненеобходимы. Для рекуррентных сетей отсюда следует, что возможныустойчивые сети, не удовлетворяющие приведенному критерию.Для доказательства теоремы Коуэна и Гроссберга используемэнергетическую функцию E (функцию Гамильтона), принимающую лишьположительные значения.
При достижении сетью одного из своихустойчивых состояний эта функция принимает соответствующееминимальное значение (локальный минимум) для бинарных образов врезультате конечного числа итераций:Ε=-1åå wij xi x j + å xiTi ,2 i j ¹ii(2.59)70PDF created with pdfFactory trial version www.pdffactory.comгде xi – вход i-го нейрона, Ti – порог i-го нейрона.Для каждого образа, вводимого в сеть, можно определить энергию E.Определив значение функции E для всех образов, можно получитьповерхность энергии с максимумами (вершинами) и минимумами(низинами), причем минимумы соответствуют образам, запомненным сетью.Для сетей Хопфилда справедливо утверждение: минимумы энергетическойфункции соответствуют образам, запомненным сетью.
В результатеитераций сеть Хопфилда в соответствии с (2.43) – (2.48) сходится кзапомненному образу.Для запоминания каждого следующего образа в поверхность энергии,описываемой энергетической функцией E, необходимо ввести новую«низину». Однако при таком введении уже существующие «низины» недолжны быть искажены.Для некоторого образа X=(x1, x2, … , xn)T следует минимизировать обесоставляющие функции E (2.59). Для того чтобы второе слагаемоеå xiTiiбыло отрицательным, необходимо обеспечить различие знаков входов xi ипорогов Ti.
При фиксированных порогах это невыполнимо, поэтому выберемпороги равными нулю. При этом второе слагаемое в (2.59) исключается, аостается лишь первое:Ε=-1åå wij xi x j .2 i j ¹i(2.60)Из общего числа k образов выделим некоторый образ с номером s.Тогда энергетическую функцию E (2.60) можно представить следующимобразом:Ε=-11wij' xi x j - åå wijs x si x sj ,åå2 i j ¹i2 i j ¹i(2.61)где wsij – составляющая весового коэффициента wij, вызванная s-м образом,w’ij – составляющая весового коэффициента wij, вызванная остальнымиобразами, запомненными сетью, xsi – значение i-го входа для s-го образа.Выделенный образ с номером s определяет лишь второе слагаемое в(2.59):71PDF created with pdfFactory trial version www.pdffactory.com1åå wijs xsi xsj .2 i j ¹iΕs = -Задачавыраженияминимизацииå å wijs xsi xsj(2.62)величиныEsэквивалентнамаксимизации.(2.63)i j ¹iВходы сети xsi принимают значения из множества {-1, 1}, поэтому (xsi)2всегда положительны.
Следовательно, путем разумного выбора весовыхкоэффициентов wsij можно максимизировать выражение (2.63):å å wijs xsi xsj = å å ( xsi ) 2 ( xsj ) 2i j ¹i,(2.64)i j ¹iгде wsij = xsixsjМинимум энергетической функции E (2.60) достигается при выборевесового коэффициентаwijs = xsi x sj .(2.65)Это справедливо для s-го образа, подлежащего запоминанию сетьюХопфилда. Для всех k образов, запоминаемых нейронной сетью, получаемравенствоwij = å wijs = å xsi x sj .s(2.66)sПример 2.3. Определение выходного вектора за три шагас помощью сети ХопфилдаДана сеть из трех нейронов и весами, равными 1 (рис. 2.11):111Рис. 2.11.
Пример сети Хопфилда72PDF created with pdfFactory trial version www.pdffactory.comСоответствующая весовая матрица имеет вид:æ0 1 1ö÷çW = ç1 0 1÷ .ç1 1 0÷øèВ качестве функции активации или выхода нейронов выберемзнаковую функцию (sign) с нулевыми порогами. Пусть на вход такой сетиподается вектор X=(1,-1,1)T.Рассчитаем для него выходной вектор сети. При этом в соответствии с(2.43) – (2.48) получим:O(1) = f(WX) = (-1,1,-1)T ;O(2) = f(WO(1)) = (-1,-1,-1)T ;O(3) = f(WO(2)) = (-1,-1,-1)T .Так как O(3)=O(2), то после 3-го шага выходы сети не изменятся, т.е.выходной вектор определяется сетью после 3-го шага.Основная область применения сетей Хопфилда – распознаваниеобразов. Например, каждое черно-белое изображение, представляемоепикселями, можно отобразить вектором X=(x1, …, xn)T, где xi для i-го пикселяравен 1, если он черный, и xi=–1, если – белый.
При подаче на входыобученной сети Хопфилда искаженного изображения сеть после некоторогочисла итераций выдает на выходы корректное изображение. На рис. 2.12 априведены корректные образы, запомненные сетью, а на рис. 2.12 б –последовательность состояний сети Хопфилда при вводе искаженногообраза (старт). После четвертой итерации нейронная сеть выдает корректныйобраз.2.5.4. Непрерывные сетиВ соответствии с предложением Хопфилда активация, функцияактивации и выходы сети Хопфилда могут быть непрерывными.Для этого может быть использована, например, сигмоидальнаялогистическая функция с параметром l :f ( z j = net j ) = 1(1 + e- lz j).(2.67)Чем больше значения l , тем лучше приближение сигмоидальнойфункции к бинарной пороговой функции.73PDF created with pdfFactory trial version www.pdffactory.comаСтарт1234бРис.
2.12. Последовательность состояний сети Хопфилдаа – корректные образы, запомненные сетьюб – искаженные образы (старт)Для непрерывных сетей Хопфилда справедлива модификация теоремыКоуэна и Гроссберга:Сеть устойчива при выполнении следующих условий:весовая матрица W симметрична: wij = wji для i ¹ j;главная диагональ содержит нули: wii = 0 для всех i.2.5.5. Применение сетей Хопфилда для оптимизацииОдной из известных «трудных» проблем оптимизации является задачао коммивояжере (Traveling Salesman Problem, TSP). Она состоит вопределении кратчайшего пути, соединяющего некоторое множествогородов, причем каждый город должен учитываться лишь один раз. Этопример NP – полной задачи.Хопфилд и Танк показали подход к ее приближенному решению наоснове сетей Хопфилда. Рассмотрим вкратце этот подход. Для описаниявозможных маршрутов авторы предложили специальный тип матрицы.
В74PDF created with pdfFactory trial version www.pdffactory.comней города образуют строки, а столбцы отображают последовательностьгородов в маршруте. В позиции (x, i) матрицы стоит 1 в том случае, когдагород x занимает i-е место в маршруте.В табл. 2.1 отображен маршрут, в котором пять городов A, B, C, D, Eпосещаются в следующей последовательности: D è B è E è A è C.В случае n городов существуетn!различных маршрутов, среди2nкоторых необходимо найти кратчайший. Для получения решения задачаотображается сетью Хопфилда.Таблица 2.1. Маршрут посещения пяти городов в заданной последовательности(задача о коммивояжере)ГородПоследовательность12345A00010B01000C00001D10000E00100В ней каждый нейрон обозначается двумя индексами x и i, причем xотражает город, а i-ю позицию в маршруте, т.е. oxi – это выход нейрона, вкотором город x размещен на i-й позиции маршрута.К энергетической функции E сети Хопфилда предъявляютсяследующие условия:§ должна быть минимальна только для допустимых решений, которыесодержат одну единицу в каждой строке и в каждом столбце матрицыописания маршрутов;§ для решений с более короткими маршрутами должна приниматьменьшие значения.Энергетическая функция, удовлетворяющая этим условиям, можетиметь вид:75PDF created with pdfFactory trial version www.pdffactory.com2ö öABC ææE = åå å o xi o xj + åå å o yi o xi + ç çç åå o xi ÷÷ - n ÷ +÷2 x i j¹i2 x i y¹ x2 çè è x iø øD+ ååå dist xy o xi o y , i +1 + o y , i -12 x i y().(2.68)При ее выборе учтены следующие соображения:§ первое слагаемое равно нулю только в тех случаях, когда каждаястрока матрицы описания маршрутов содержит лишь одну единицу;§ второе слагаемое равно нулю только тогда, когда каждый столбецматрицы содержит лишь одну единицу;§ третье слагаемое равно нулю лишь в тех случаях, когда в матрицеописания маршрутов имеется n единиц, что означает: каждый городпосещается лишь один раз;§ четвертое слагаемое отражает длину маршрута.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
