автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Применение дискретизации для решения задач бинарной оптимизации с помощью нейронной сети Хопфилда

005012986

Мальсагов Магомед Юсупович

На правах рукописи

ПРИМЕНЕНИЕ ДИСКРЕТИЗАЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧ БИНАРНОЙ ОПТИМИЗАЦИИ С ПОМОЩЬЮ НЕЙРОННОЙ СЕТИ

ХОПФИЛДА

05.13.01 - Системный анализ, управление и обработка информации (по математическим отраслям и информатике)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

2 3 '.:;,? ГЛ

Москва-2012

005012986

Работа выполнена в Федеральном государственном бюджетном учреждении пауки Научно-исследовательском институте системных исследований РАН.

Научный руководитель: кандидат физико-математических наук

Крыжановский Михаил Владимирович

Официальные оппоненты: Литвинов Олег Станиславович,

доктор физико-математических наук, профессор, МГТУ им. Н.Э. Баумана

Защита состоится «25» апреля 2012 года в 16 часов на заседании диссертационного совета Д 002.265.01 при НИИСИ РАН по адресу 117218, Москва, Нахимовский проспект, д. 36, корп. 1, конференц-зал.

С диссертацией можно ознакомиться в библиотеке НИИСИ РАН (комн. 13-21а)

Автореферат разослан «23» марта 2012 года

Доленко Сергей Анатольевич, кандидат физико-математических наук, старший научный сотрудник, НИИЯФ МГУ

Ведущая организация: Национальный исследовательский ядерный

университет «МИФИ»

Ученый секретарь диссертационного совета, кандидат физико-математических наук, доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Задачи дискретной оптимизации широко распространены и встречаются практически во всех сферах человеческой деятельности. Многочисленные проблемы в математике, статистике, технике, науке, медицине и экономике могут рассматриваться как проблемы оптимизации. Задачей оптимизации является нахождение решения, которое удовлетворяет системе ограничений и максимизирует или минимизирует целевую функцию. Наиболее известными задачами дискретной оптимизации являются задача о рюкзаке, задача о коммивояжере, задача планирования вычислений для многопроцессорной системы, выбор оптимальной структуры автоматизированной системы управления и т.д. Решение этих задач связано с рядом трудностей. Например, полный перебор возможных решений, как правило, невозможен из-за большого объема вычислений.

Основными методами дискретной оптимизации являются метод ветвей и границ, динамическое программирование, метод отсечений, генетические алгоритмы, нейросетевые алгоритмы. Потребность в большой оперативной памяти и вычислительная сложность остаются слабыми местами всех известных оптимизационных алгоритмов. Так, например, метод ветвей и границ позволяет решать только задачи малой размерности < 100). Поэтому остается актуальной задача построения и модификации алгоритмов с целью увеличения их производительности и снижения требований на вычислительные ресурсы. Очень удобными для решения этих задач оказались искусственные нейронные сети.

Искусственные нейронные сети — математические модели, а также их программные или аппаратные реализации, построенные по принципу организации и функционирования биологических нейронных сетей — сетей нервных клеток живого организма. Это понятие возникло при изучении процессов, протекающих в мозге, и при попытке смоделировать эти процессы. Нейронные сети позволяют быстро находить приближенные решения задач дискретной оптимизации больших размерностей (N>1000). Однако здесь тоже возникают проблемы с оперативной памятью и вычислительной сложностью.

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

Цель диссертационной работы. Основная цель диссертационной работы состояла в разработке быстрого метода решения задач комбинаторной оптимизации на базе нейронных сетей.

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

2. Теоретически и экспериментально получены оценки для вероятности несовпадения направлений градиентов и эффективности минимизации.

3. На основе процедуры дискретизации разработаны и исследованы алгоритмы минимизации квадратичного функционала. Исследовано увеличение быстродействия новых алгоритмов и их эффективность по сравнению со стандартной моделью Хопфилда.

Основные положения, выносимые на защиту:

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

2. Алгоритмы поиска минимумов квадратичного функционала в пространстве бинарных переменных с использованием процедуры дискретизации. Методы исследований. Для решения поставленных задач в работе были

использованы методы вычислительной математики, теории вероятностей и

математической статистики, а также методы прикладного программирования. Научная новизна. В диссертационной работе

1. Предложена и исследована процедура дискретизации.

2. Создан алгоритм, позволяющий увеличить скорость решения оптимизационных задач и получать при существенно меньших вычислительных затратах заметно лучшее решение, чем при использовании стандартной модели Хопфилда.

3. Применение дискретизации снижает требования к оперативной памяти, что позволяет решать задачи недоступные стандартной модели Хопфилда.

4. Получены выражения, позволяющие аналитически оценить качество решения при использовании минимизационного алгоритма. Практическая ценность. Практическая ценность результатов работы

состоит в следующем:

1. На основе процедуры дискретизации создан алгоритм, позволяющий уменьшить время решения оптимизационных задач и получать при существенно меньших вычислительных затратах лучшее решение, чем при использовании стандартного подхода, основанного на модели Хопфилда;

2. Получены выражения, позволяющие априори аналитически оценить качество решения, которое может быть получено в результате минимизации. Разработанные алгоритмы и методы дискретизации найдут свое применение

в прикладных системах на основе нейронных сетей Хопфилда.

Апробация работы и публикации. По материалам диссертации

опубликовано 11 работ, из них 5 - в российских и зарубежных журналах [1-5]

(все из перечня ВАК), 6 - в трудах конференций [5-11].

Основные положения работы докладывались на следующих конференциях:

1. XI Всероссийская научно-техническая конференция «Нейроинформатика-2009», Москва, 2009.

2. Международная Научно-Техническая конференция «Искусственный Интеллект. Интеллектуальные Системы - 2009», ИИ - 2009, Украина, 2009.

3. XII Всероссийская научно-техническая конференция «Нейроинформатика-2010», Москва, 2010.

4. The fourth International Conference on Neural Networks and Artificial

Intelligence, ICNNAI - 2010, респ. Белоруссия, Брест, 2010.

5. XIII Всероссийская научно-техническая конференция «Нсйроинформатика-

2011», Москва, 2011.

6. Международная Научно-Тсхническая конференция «Искусственный

Интеллект. Интеллектуальные Системы - 2011», ИИ - 2011, Украина, 2011.

Структура н объем диссертации. Работа состоит из четырех глав,

заключения, списка литературы и двух приложений. Общий объем диссертации составляет 133 страницы. Список литературы содержит 121 наименование.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

В первой главе представлен обзор работ посвященных исследованию нейронной сети Хопфилда и ее применению к решению задач дискретной оптимизации. Сформулированы цели диссертационной работы, обоснована ее актуальность и научная новизна.

Модель Хопфилда принято описывать как систему взаимосвязанных нейронов (рис.1). Состояние сети описывается N- мерным вектором S, компоненты которого, бинарные переменные, принимают значения ±1. Связи между нейронами задаются с помощью симметричной матрицы связей А с нулевыми диагональными элементами. Каждый нейрон связан со всеми остальными.

Пусть в начальный момент времени сеть находится в состоянии S0. На каждый нейрон со стороны остальных нейронов действует локальное поле II

Н = -В + А. • S. (1)

Под влиянием этого поля компоненты состояния S(/) меняются по правилу:

*Ы)=и<!\ {2)

Состояние нейрона не меняется, если ориентация этого нейрона и локального поля одинаковы, и меняется на противоположное в противном случае. Вектор В задает пороги нейронов, т.е. границу, при превышении которой нейрон меняет свое состояние.

Состояние сети характеризуется функцией энергии Е

£ = -i(s,Äs)+(B,S). (3)

В процессе эволюции сети энергия состояния неуклонно понижается. Постепенно система приходит в состояние покоя.

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

Возможность использования нейронных сетей для задач оптимизации была впервые продемонстрирована Хопфилдом в его совместных работах с Танком.

Успешное применение нейронной сети к задаче коммивояжера инициировало исследование нейросетевых подходов к решению задач оптимизации.

Наличие большого количества локальных минимумов, которыми 5 *

обладает нейронная сеть большой размерности, затрудняет решение задач дискретной оптимизации, поскольку нахождение приемлемого

субоптимального состояния требует большого объема вычислений. Например, сеть Хопфилда размерности 100 имеет более 50 ООО локальных минимумов, и

нахождение субоптималыюго решения , ,, .. _ ,

_ , г Рис.1. Нейронная сеть Хопфилда.

требует ~ 1 часа машинного времени. В

случае размерности сети 1000 вероятность нахождения наиболее глубокого

минимума составляет ~ 10~б и требует ~ 500 часов работы алгоритма.

С целью увеличения быстродействия нейронных сетей, в 2006 году Магомедов Б.М. предложил метод снижения размерности сети, путем объединения нейронов в группы (домены). В этом подходе одновременно меняют состояние всей группы нейронов. Однако, при этом глубина находимых локальных минимумов недостаточна. Дальнейшие исследования в этом направлении прекращены.

Других работ, посвященных увеличению быстродействия нейронных сетей, нет.

В данной работе исследуется возможность применения целочисленной арифметики для решения задач бинарной оптимизации с помощью нейронной сети Хопфилда . с целью увеличения быстродействия вычислительных алгоритмов.

Во второй главе описывается процедура дискретизации, заключающаяся в замене действительных элементов матрицы межсвязей нейронной сети целыми числами.

Решение задач дискретной оптимизации нейронными сетями сводится к минимизации квадратичного функционала (3).

Дискретизация заключается в замене матрицы А некоторой матрицей С. Элементами матрицы С являются целые числа в диапазоне [-<?;#], где ц -число градаций, свободный параметр, задаваемый пользователем. Матрица С формируется следующим образом: разбиваем область распределения элементов центрированного остатка А'у = Ау - А0 на (2<у +1) отрезка. Здесь А0 - среднее

значение матричного элемента. Формируем матрицу С по правилу

Су = к-sign{A'¡j), когда хк<| < хк, к = 0,1,..., д. (4)

Здесь хк - правая граница к -ого отрезка.

Длины отрезков выбираются так, чтобы средние значения на отрезках были кратны величине т, где т> 0 - наименьшее положительное среднее

значение (среднее на А-ом отрезке равно кт, к- 0,±],...,±д). Заметим, что длины всех отрезков однозначно определяются длиной /0 отрезка с нулевым средним, которая является свободным параметром для последующей оптимизации. Более того, введение отрезка с нулевым средним является ключевым^ моментом, позволяющим наилучшим образом аппроксимировать

матрицу А матрицей С и существенно повысить эффективность алгоритма минимизации.

Адаптация алгоритма минимизации. Адаптируем алгоритм минимизации к работе с матрицей С. Для этого сделаем в (3) замены Ац -> С0 + Сц и В, 6,. Здесь С0 и 6,- - свободные параметры, оптимальные значения которых будут определены ниже. Тогда, расчет локального поля и обновление компонент конфигурационного вектора будет производиться в соответствии с выражениями:

Решающее правило (5) соответствует спуску по поверхности, описываемой дискретизированным функционалом

*=~Мс0+с»+М). (6)

Заменить решающее правило (2) его дискретизированным аналогом (5) можно только в том случае, когда знаки локальных полей Яи А, совпадают в любой точке N -мерного пространства с достаточно большой вероятностью (амплитуды полей Н1 и /г, не играют роли). Иными словами, использовать модифицированное правило (5) для минимизации исходного функционала (3) можно, если свести до минимума величину ошибки - вероятность несовпадения направлений локальных полей в случайной точке пространства:

Р = Рг{#, > 0п/г, < 0} + Рг{//(. < Оп/г, > О}, (7)

Для минимизации ошибки надо найти наилучшее представление матрицы А' матрицей С и найти оптимальные значения величин С0 и , / = Т^}.

Выражение для ошибки приведено в диссертационной работе. Оптимальные значения величин С0 и Ь, определяются из условий ВР/дЬ, = 0 и дР/дС0 = 0:

Анализ полученных выражений показал, что вероятность ошибки Р не зависит от знаков величин А0 и В(. С ростом абсолютных значений |Л0| и |5,| вероятность ошибки Р быстро уменьшается (рис. 2).

Наихудшие условия для дискретизации имеют место, когда А0= 0 и = 0. В этом случае величина ошибки максимальна и описывается выражением:

р 1 1 ■ (С'Л, тах = - — акат ртт, рт{п = ---Л.. (9)

2 ж сгсаА

Рис.2. Вероятность несовпадения направлений локальных полей в случайной точке конфигурационного пространства. Матрицы с равномерным распределением элементов.

Отметим, что все выражения получены в самом общем виде, без привязки к конкретному распределению матричных элементов Л,у и типу выбранного

метода дискретизации. Поэтому можно сделать общий вывод: наилучшее представление матрицы А' матрицей С сводится к такому подбору метода дискретизации, при котором величина рт{п максимальна: согласно (9) вероятность ошибки Ртях при этом минимальна. В этом смысле выбранный нами метод дискретизации, направленный на максимальное ускорение алгоритма минимизации, как правило, не является наилучшим.

Выражение (9) следует оптимизировать по длине отрезка с нулевым средним, находя /0 из условия

ЭР п

а/Г0" <10)

В диссертационной работе рассматривались матрицы с равномерным и нормальным распределениями матричных элементов. Для матриц с равномерным распределением при <7 = 1 получаем Ртах а 0.11. С ростом числа градаций до q = 16 вероятность ошибки снижается до /5ти я 0.01. Для матриц с нормальным распределением для тех же значений параметра д ошибка меняется от значения 0.16 до Ртзх ~ 0.06. Несмотря на то, что тип

распределения влияет на эффективность дискретизации, ошибка все равно остается достаточно малой величиной.

Минимум функционала. Процесс минимизации функционала (3) начинается с некоторой случайной конфигурации в. Подчиняясь решающему правилу (5)

нейронная сеть приходит в некоторое устойчивое состояние Бо, являющееся минимумом дискретизированного функционала (6). Если из этой точки продолжить спуск с решающим правилом (2), то сеть придет в состояние 80,

соответствующее минимуму функционала (3). На всем пути в -»80 значение ошибки только уменьшается. В диссертационной работе анализируется так же величина ошибки в точке - минимуме исходного функционала (3).

Определив вероятность ошибки с помощью выражения (9), можно сразу же оценить и расстояние (как по Хэммингу с1, так и по энергии с1Е) между

8

¿Е = стАРМл

найденным минимумом дискретизированного функционала 80 и истинным минимумом 50, до которого сеть не добралась. Обладая такой информацией

можно принять решение: продолжать ли спуск дальше из точки 50, или же остановиться (в зависимости от требований поставленной задачи):

й - РЫ,

¡Л[ (П>

12л '

Проведенный анализ показал, что расстояние между минимумами достаточно мало: для матриц с равномерным распределением не превышает а? = 0.1Ш при q = \ и снижается до значения (1 = 0.02Л' при <7 = 16. Эффективность йЕ дискретизированного алгоритма достаточно велика: разница в энергиях составляет всего лишь 7% при д = 1 и меньше 0.2% при = 16.

В третьей главе рассматриваются особенности программной реализации процедуры дискретизации. На основе идеи дискретизации разработаны и исследованы алгоритмы минимизации квадратичного функционала. Исследовано быстродействие и эффективность новых алгоритмов по сравнению со стандартной моделью Хопфилда.

При дискретизации исходная матрица А заменяется ее дискретизированным аналогом С, элементы которой являются целыми числами

-<7<CV<<7, (12)

где ц - целое число градаций. Например, при <7 = 1 - Су = -1; 0; +1. В этом

случае нахождение состояний определяется минимизацией функционала е , описываемого выражением (6). Динамика системы описывается выражением (5).

На рисунке 3 показы плотности распределений по энергии исходного функционала Е (3) в локальных минимумах дискретизированного функционала для нескольких значений числа градаций: ц = 1,2,16. Видно, что с

увеличением числа градаций пик плотности распределения смешается влево, в сторону более глубоких минимумов. То есть вероятность отыскания более глубоких минимумов увеличивается. Большая часть пути (около 95%) при минимизации проходится при использовании дискретизированного функционала (рис. 4). На графиках все кривые нормированы на модуль среднего значения энергии минимумов сети Хопфилда. Таким образом, начальные состояния (кривая 1) распределены около нуля, а минимумы сети Хопфилда (кривая 3) распределены около -1.

9

■■.....;------

-.....\4ffir

.. шДЦ..----

........

«'.2 -и -1 -О.» -0.1 -0.' £,

Рис.З. Плотность локальных минимумов.

распределения

Минимумы дискретизированного функционала (кривая 2) по энергии отстоят от начальных состояний на 0.95.

Если использовать дискретизированные минимумы как стартовые точки исходной сети, то с большей вероятностью найдем более глубокие минимумы (кривая 4), чем при стандартной процедуре минимизации.

При оптимизации количество итераций для дискретизированной матрицы примерно равно числу итераций исходной матрицы (рис. 5). Таким образом, путь, проходимый при оптимизации по энергии примерно равен пути проходимому на исходной матрице, а объем вычислений при такой замене тот же. Однако применение целых чисел малой разрядности в процедуре дискретизации дает возможность для более экономного хранения этих чисел и увеличивает скорость работы алгоритма. В случае 9 = 15 в 4 байта можно записать одновременно 4 целых числа. При этом время работы сократится в 4 раза. А при ? = 1 в 4 байта можно записать сразу 8 чисел, и время работы сократится до 8 раз. Экономия происходит за счет операций процессор-память, т.к. при использовании чисел малой разрядности можно оперировать сразу несколькими числами.

На рисунке 6 показано увеличение скорости алгоритма при использовании дискретизации (д = 1, в 4 байта записывалось 8 чисел) по сравнению с алгоритмом Хопфилда. С увеличением размерности сети скорость алгоритма увеличивается и достигает своего предельного значения 7.3.

На основе описанных выше преимуществ, предлагается два алгоритма поиска: одноэтапный и двухэтапный.

Рис.4. Плотность распределения состояний по энергии: кривая 1 -стартовые конфигурации в; кривая 2 -локальные минимумы в*

дискретизированного функционала (<7 = 1); кривая 3 - локальные минимумы, полученные без использования дискретизации; кривая 4 - окончательные локальные минимумы в,,.

Рис.5. Количество итераций при замене вещественной матрицы на

целочисленную (я=1).

Рис.6. Ускорение алгоритма при использовании упаковки чисел малой разрядности.

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

функционала £ = соответствует более глубокая энергия исходного

/ Л *

функционала Е = I, где 80 - минимум дискретизированного функционала.

Сказанное выше показано на рисунке 7. По оси абсцисс отложено расстояние по энергии, на котором расположен локальный минимум относительно

наименьшего значения функционала £ = По оси ординат отложено

расстояние тех же конфигураций, но по энергии исходного функционала

Оценить стандартное отклонение ас и среднее значение энергии минимумов дискретизированного функционала можно по формулам

. ^ „ та

4л/оТШ' * 4

Видно, что практически на всем диапазоне зависимость линейная. Однако на расстоянии менее 0.05 от наименьшего значения (около 1.5ае от среднего значения энергии минимумов) эта зависимость нарушается. Поэтому нельзя утверждать, что, отыскав самый глубокий дискретизированный минимум, мы наилучшим образом минимизировали исходный функционал.

С учетом сказанного, одноэтапный алгоритм можно сформулировать следующим образом: после дискретизации матрицы определяются минимумы дискретизированного функционала, лежащие глубже 1.5<те от среднего значения £. Затем, в зависимости от цели задачи, можно либо ограничиться самым глубоким минимумом дискретизированного функционала, либо вычислить соответствующие им энергии исходного функционала и выбрать

самое глубокое состояние из них. Второй способ более медленный, так как вычисление энергии исходного

7

функционала требует ~ 2Ы операций. Вычисление энергии

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

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

*

= (14)

где Е0 - самый глубокий минимум, найденный в результате стартов со всех

состояний во, Е* - самый глубокий минимум, найденный в результате стартов из заданной области.

!

______:

:

о.ч о.1э о.х о.м 0.1

Рис.7. Соотношение энергий минимумов одноэтапного алгоритма на исходном функционале и

дискретизированном функционале.

Рис.8. Зависимость эффективного Рис.9. Количество изменений состояний

расстояния от размера стартовой нейронов на каждой итерации,

области. Размерность пейросети N = 4000, Т -

номер итерации.

На рисунке 8 показано, как меняется эффективность минимизации при уменьшении числа минимумов дискретизированного функционала, используемых на втором этапе. По оси абсцисс отложена верхняя граница минимумов дискретизированного функционала, которые используются как стартовые конфигурации на втором этапе. По оси ординат отложена эффективность минимизации <5Е. Видно, что если сдвинуть границу на я 2ае относительно среднего значения энергии минимумов дискретизированного функционала, то эффективность алгоритма снизится приблизительно на 1%. При этом число состояний, подлежащих коррекции на втором этапе, составит

порядка 0.05 от общего числа состояний 80, найденных на первом этапе. Так же можно отметить, что с ростом размерности эта граница отодвигается влево, уменьшая необходимое число стартов на втором этапе.

Модификация динамики. С увеличением числа итераций, число нейронов, которые изменяют свое направление, неуклонно уменьшается (рис. 9). Это означает, что направления компонент локального поля Н также реже изменяется уже после 4-ой итерации (менее 5%). Поэтому вычисление на каждом шаге компоненты вектора Н не эффективно. В настоящее время

Рис.10, (а) - Полное число изменений состояний нейронов при увеличении размерности нейронной сети N ; (Ь) - Изменение числа итераций в зависимости от размерности сети.

используется другой метод расчета. В исходном состоянии в вычисляются все компоненты Н . Па каждом шаге процедуры при изменении состояния нейрона вектор II модифицируется по правилу Н = Н±2(а),, если направление спина

положительно/отрицательно, (а), - г -ый вектор-столбец матрицы а.

При перевороте каждого спина производится N операций. Число изменений состояний нейронов не превышает N (рис. 10а), поэтому вычислительная сложность такого

алгоритма ~(1 + а)у2, а 0.5 <«<1.

Программная реализация стандартной модели Хопфилда требует порядка

2

Ор к 2ТМ операций. Отношение

объемов вычислений исходного метода

к методу с обновлениями составляет

величину порядка числа итераций ~Т,{Г» 1) (рис.ЮЬ). Поэтому в дальнейшем использовался алгоритм с обновлениями.

Увеличение быстродействия одноэтапного алгоритма при использовании дискретизации в динамике с обновлениями для различной размерности показано на рисунке 11. Установлено, что достигаемое ускорение при упаковке

8 чисел в 4 байта (д = 1, р = 8) равно в « 5.3. При упаковке 4 чисел (р = 4) в исходный формат ускорение составляет в »3.8 (?<1б). Таким образом, с помощью дискретизации можно добиться 8-кратного увеличения скорости работы алгоритма при использовании чисел малой разрядности {-1:0; +1}.

Объем вычислений двухэтапного алгоритма складывается из объема вычислений на первом и втором этапах. Согласно рис. 5 число итераций на первом этапе равно числу итераций обычного алгоритма Он, однако, за счет дискретизации эти операции выполняются в б1 раз быстрее. Таким образом, объем вычислений на первом этапе по сравнению с алгоритмом Хопфилда

Рис.11. Ускорение, получаемое при упаковке чисел (р = 8) по сравнению с обычным методом.

составит

О,

О,

(15)

На втором этапе производится лишь часть пусков, произведенных на первом этапе. В среднем доля пусков составляет 0.05 от общего числа стартов. При этом на втором этапе (коррекции) производится лишь 0.3 от числа итераций стандартного алгоритма Хопфилда (рис.5, нижняя кривая). Поэтому объем вычислений на втором этапе составит

02 - 0.05 • О.ЗОн. (1б)

Тогда ускорение двухэтапного алгоритма составит

0 =_о*_7.

0.05-0.3 Он+°"0 (,7)

В случае ¡7 = 1, /> = 8- 0 = 5,а при д = 1, р = 16 - 0 = 7.14.

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

В четвертой главе представлены схемы алгоритмов и анализ их быстродействия. Рассматриваются изменения в сети Хопфилда, связанные с применением дискретизации. Приводится описание программной реализации сети Хопфилда с дискретизировашюй матрицей.

Основным результатом четвертой главы является оценка соотношения числа операций алгоритма с упаковкой данных по сравнению с обычной сетью Хопфилда. Рассмотрим случай, когда под элемент исходной матрицы выделяется 4 байта. В зависимости от числа градаций под дискретизированный элемент можно выбирать различное число бит, желательно, с запасом, чтобы переполнение не происходило достаточно часто. Например, можно выделять г = 4 бита, когда ц £ {1; 2} и упаковывать р = 8 дискретизированных чисел в 4 байта или г = 8 бит, когда ^е[3;1б] и упаковывать р- 4 дискретизированных числа в 4 байта. Тогда можно будет просуммировать V чисел разрядности г, прежде чем произойдет переполнение.

(18)

Op=4NT + N

(.N + rot). (19)

Я

Здесь [jrJ - наибольшее целое, меньшее или равное х.

С учетом сказанного выше можно оценить число операций, которое затратит нейронная сеть с упакованными данными на спуск из случайного состояния в минимум

_р 2v

Стандартная сеть Хопфилда производит спуск из стартового состояния в минимум за число операций равное

Он = 2N2 + NT + N -rot. (20)

В результате многочисленных экспериментов была установлена зависимости между числом итераций Г, числом изменений нейронами своего состояния rot и размерностью задачи N:

Т к 0.29jV°'62, rot я 0.32^(1 + 0.2I«(iV)). (21)

С учетом приведенных выше выражений можно оценить выигрыш по числу операций. На рисунке 12 представлено отношение числа операций алгоритма Хопфилда и алгоритма с упаковкой дискретизированных чисел. Видно, что за счет упаковки данных (матрицы и состояния) экономия операций составляет около 4.5 раз. С увеличением числа градаций скорость снизится, так как в 4-х байтную переменную удастся упаковать меньше дискретизированных

15

элементов (например, <? = 16 и р = 4). Восьмикратное ускорение не достигается

в связи с тем, что при работе с упакованными данными периодически приходится их в переменные большего формата.

Чтобы получить полное ускорение алгоритма необходимо также учесть время, затрачиваемое на передачу данных между памятью и процессором. Так как при упаковке передаются сразу несколько чисел, то число обращений процессора к памяти будет примерно в р раз меньше, чем при обычном алгоритме. Общее время работы алгоритмов можно оценить как

ЕОЮ «ООО 1ІКИ Л^

Рис.12. Отношенне числа операций стандартной модели Хопфилда к алгоритму с упаковкой в 4 байта для разного числа градаций.

Н

О у, ■ + г.

ар

'пер ' °Н

(22)

, _ ,, - , , , > I 1 -- 1 п

р р ар ПСР

Здесь гар - время выполнения арифметической операции, /пер - время передачи

данных между процессором и памятью. Время передачи данных обычно много больше времени выполнения арифметических операций. Можно рассмотреть 2 граничных случая.

'.А,-

л/

Рис.13. Полное ускорение алгоритма с упаковкой по сравнению с сетью Хопфилда, когда время выполнения арифметических операций равно времени передачи данных между процессором и памятью.

ИМ ЮОО 10000 ЛГ

Рис.14. Полное ускорение алгоритма с упаковкой по сравнению с сетью Хопфилда, когда время выполнения арифметических операций в 10 раз меньше времени передачи данных между процессором и памятью.

1. /пер =/ар (см. рис. 13): в этом случае, если вычислить отношение времен

•ар

работы алгоритмов получим, что при д = 1 алгоритм с упаковкой данных работает приблизительно в 5.5 раз быстрее, чем сеть Хопфилда. При ц = 16 ускорение составит более 3 раз.

2. * »/ (см. рис. 14): например, I = Шар. В этом случае получим, что при ¿7 = 1 алгоритм с упаковкой данных работает почти в 7.5 раз быстрее, чем сеть Хопфилда. А при д - 16 ускорение приближается к 4 раз.

Таким образом, ускорение алгоритма с упаковкой данных в зависимости от архитектуры вычислительной машины позволяет достичь ускорения от 5.5 до 7.5 раз.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В диссертационной работе получены следующие результаты.'

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

2. Определены оптимальные параметры дискретизации, при которых ошибка в направлениях локальных полей составляет менее 10% в любой точке конфигурационного пространства. Показано, что расстояние по Хеммингу и по энергии между минимумом дискретизированного функционала и минимумом исходного функционала, в который пришла бы исходная сеть из дискретизированного минимума, прямо пропорционально вероятности несовпадения направлений локальных полей в случайной точке. Хеммингово расстояние менее 12%, а по энергии меньше 7% для любого числа градаций.

3. На основе процедуры дискретизации разработаны алгоритмы минимизации квадратичного функционала: одноэтапный и двухэтапный. Исследовано быстродействие предложенных алгоритмов, а также их эффективность по сравнению со стандартной моделью Хопфилда.

4. Применение одноэтапного алгоритма при использовании упакованных чисел позволяет достичь 7-кратного увеличения скорости. При этом глубина полученных минимумов по энергии на 7% меньше, чем при стандартной модели Хопфилда. При этом требуется в 8 раз меньше оперативной памяти, чем при стандартной модели Хопфилда. Таким образом, с помощью одноэтапного алгоритма можно решать задачи недоступные стандартным алгоритмам.

5. Для отыскания более глубоких минимумов предлагается двухэтапный алгоритм. Он позволяет отыскивать те же минимумы, что и стандартная модель, но с вероятностью более 50% находятся более глубокие. Использование только самых глубоких дискретизированпых минимумов на втором этапе позволило сохранить скорость алгоритма, достигаемую за счет дискретизации.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Kryzhanovsky M.V., Malsagov M.U. Clipping procedure in optimization problems and its generalization // Optical Memory and Neural Networks (Information Optics).-2009- Vol. 18,№3.-pp. 181-187.

2. Крыжановский Б.В., Крыжановский M.B., Мальсагов М.Ю. Дискретизация матрицы в задаче бинарной минимизации квадратичного функционала // Доклады Академии Наук,- 2011.— Т.438, №3- сс. 312-317.

3. Мальсагов М.Ю. Понижение разрядности элементов матрицы для ускорения алгоритма дискретной оптимизации // Нейрокомпьютеры: разработка и применение - 2011.- №4.- сс. 22-31.

4. Kryzhanovsky M.V., Malsagov M.Yu. Modification of Binary Optimization Algorithm and Use Small Digit Capacity Numbers // Optical Memory and Neural Networks (Information Optics).- 2011.- Vol. 20, №3 - pp. 194-200.

5. Крыжановский M.B., Мальсагов М.Ю. Применение чисел малой разрядности в задаче бинарной оптимизации // Программные продукты и системы.-2011.-№4.-сс. 40-44.

6. Крыжановский М.В., Мальсагов М.Ю. Обобщение процедуры клиппирования в задачах оптимизации в дискретном пространстве // Искусственный интеллект.- 2009 - №3- сс. 496-503.

7. Крыжановский М.В., Мальсагов М.Ю. Особенности применения дискретизации в задачах поиска глобального минимума // Искусственный интеллект,- 2011- №3 - сс. 497-505.

8. Крыжановский М.В., Мальсагов М.Ю. Применение процедуры клипгшрования и ее обобщение в задачах поиска глобального минимума // Сборник трудов XI Всероссийской научно-технической конференции «Нейроинформатика-2009».- М.: МИФИ, 2009 - ч.2.~ сс. 61-68.

9. Крыжановский М.В., Мальсагов М.Ю. Ускорение модифицированной процедуры клиппирования // Сборник трудов XII Всероссийской научно-технической конференции «Нейроинформатика-2010»,- М.: МИФИ, 2010.—

4.2.- сс. 45-54.

10.Kryzhanovsky M.V., Malsagov M.U. Small digit capacity arithmetic for problems of discrete optimization // Proc. of the IV International Conference on Neural Networks and Artificial Intelligence «ICNNAI-2010».- Brest - Belarus.- pp. 101106.

11 .Крыжановский M.B., Мальсагов М.Ю. Дискретизация матрицы в задаче бинарной оптимизации // Сборник трудов XIII Всероссийской научно-технической конференции «Нейроинформатика-2011»,- М.: МИФИ, 2011-

4.3.-сс. 152-160.

Подписало в печать: 20.03.2012

Заказ № 6846 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.aatoreferat.ru

61 12-1/759

Федеральное государственное бюджетное учреждение науки Научно-исследовательский институт системных исследований РАН

На правах рукописи

Мальсагов Магомед Юсупович

ПРИМЕНЕНИЕ ДИСКРЕТИЗАЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧ БИНАРНОЙ ОПТИМИЗАЦИИ С ПОМОЩЬЮ НЕЙРОННОЙ

СЕТИ ХОПФИЛДА

05.13.01 - «Системный анализ, управление и обработка информации» (по математическим отраслям и информатике)

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель: кандидат физико-математических наук Крыжановский Михаил Владимирович

Москва —2012

СОДЕРЖАНИЕ

СОДЕРЖАНИЕ_2

ГЛАВА 1. ВВЕДЕНИЕ_3

§1.1. Актуальность темы...........................................................................................................................3

§1.2. Нейронные сети и модель Хопфилда..........................................................................................7

§1.3. Исследования и применения нейронной сети Хопфилда.................................................13

§1.4. Цели и задачи диссертационной работы.................................................................................26

§1.5. Основные положения, выносимые на защиту......................................................................27

§1.6. Методы исследования...................................................................................................................28

§1.7. Научная новизна..............................................................................................................................29

§1.8. Практическая ценность.................................................................................................................30

§1.9. Апробация работы и публикации...............................................................................................31

§1.10. Структура и объем диссертации...............................................................................................33

ГЛАВА 2. ПРОЦЕДУРА ДИСКРЕТИЗАЦИИ_34

§2.1. Процедура дискретизации.............................................................................................................35

§2.2. Матрицы с равномерным распределением элементов.......................................................43

§2.3. Матрицы с нормальным распределением элементов........................................................48

§2.4. Расстояние между минимумами...............................................................................................53

§2.5. Выводы.................................................................................................................................................59

ГЛАВА 3. АЛГОРИТМЫ ПОИСКА МИНИМУМОВ_62

§3.1. Одноэтапный алгоритм.................................................................................................................62

§3.2. двухэтапный алгоритм..................................................................................................................72

§3.3. Быстродействие алгоритмов.......................................................................................................77

§3.4. Выводы.................................................................................................................................................83

ГЛАВА 4. СХЕМЫ АЛГОРИТМОВ ПОИСКА_86

§4.1. Схема одноэтапного алгоритма................................................................................................86

§4.2. Схема двухэтапного алгоритма.................................................................................................88

§4.3. Нейронная сеть Хопфилда с дискретизированной матрицей..........................................90

§4.4. Описание программной реализации.........................................................................................97

§4.5. выводы...............................................................................................................................................103

ЗАКЛЮЧЕНИЕ_104

ПРИЛОЖЕНИЕ___106

СПИСОК ЛИТЕРАТУРЫ_123

ГЛАВА 1. ВВЕДЕНИЕ

§1.1. Актуальность темы

Задачи дискретной оптимизации [1-8] широко распространены и встречаются практически во всех сферах человеческой деятельности. Многочисленные проблемы в математике, статистике, технике, науке, медицине и экономике могут рассматриваться как проблемы оптимизации. Задачей оптимизации является нахождение решения, которое удовлетворяет системе ограничений и максимизирует или минимизирует целевую функцию. Наиболее известными задачами дискретной оптимизации являются задача о рюкзаке, задача о коммивояжере, задача планирования вычислений для многопроцессорной системы, выбор оптимальной структуры автоматизированной системы управления и т.д. Решение этих задач связано с рядом трудностей. Например, полный перебор возможных решений, как правило, невозможен из-за большого объема вычислений. Из-за дискретности пространства решений неприменимы многие приемы, разработанные в математическом программировании, например, движение по направлению градиента, переход из одной точки допустимых решений в другую и т.д. Однако для большинства прикладных задач достаточно получить хорошее приближенное решение. За счет отказа от поиска точного решения часто удается построить простые алгоритмы для сложных задач. Поэтому на практике часто используются приближенные методы как альтернатива полному перебору [9-14].

Большое значение имеют вопросы эффективности алгоритмов решения задач дискретной оптимизации [1, 15]. Для дискретных задач не всегда пригодны критерии оценки эффективности алгоритмов оптимизации, используемые для непрерывных задач. Состояние теории в настоящее время не позволяет указать универсальные количественные, и даже качественные оценки эффективности вычислительных алгоритмов. Такие оценки дает лишь вычислительная практика.

При решении задач дискретной оптимизации характерным приемом является разбиение задачи на подзадачи или ветвление. Полученные подзадачи либо решают, либо, в свою очередь, применяют к ним процедуру ветвления. Решение всей задачи получается в результате анализа всех подзадач наиболее низкого уровня ветвления.

Основными методами дискретной оптимизации являются метод ветвей и границ, динамическое программирование, метод отсечений, генетические алгоритмы, нейросетевые алгоритмы.

В методе ветвей и границ [16] из рассматриваемой задачи получаются две подзадачи путем специального разбиения пространства решений и отбрасывания областей, заведомо не содержащих решения исходной задачи. В случае, когда целочисленные переменные являются булевыми, обычно используется аддитивный алгоритм (метод Балаша [17]). Метод ветвей и границ позволяет получать хорошие результаты, но только при малых размерностях задачи (N=50-60) [18-21].

Метод динамического программирования [22-25] применяется для решения динамических, т.е. меняющихся во времени, или многошаговых оптимизационных задачах. Метод строится на основе принципа оптимальности: оптимальное поведение в многошаговом процессе обладает тем свойством, что, какими бы ни были решение, принятое на последнем шаге, и состояние процесса перед последним шагом, предыдущие решения должны составлять оптимальное относительно этого состояния поведение. Таким образом, метод динамического программирования можно представить в виде трех этапов:

1. Исходная задача разбивается на подзадачи меньшего размера.

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

3. Используются решения подзадач для формирования решения исходной задачи.

Важным достоинством метода динамического программирования является его предсказуемость, т.е. возможность теоретически оценить объем вычислительной работы и объем занимаемой памяти. К недостаткам метода относится потребность в большом объеме памяти, а также сложность его катастрофически возрастает с увеличением размерности задачи.

Исходной задачей методов отсечений [26-29], используемых для решения линейных целочисленных задач, является задача с ослабленными ограничениями, которая возникает в результате исключения требования целочисленности переменных. По мере введения специальных дополнительных ограничений, учитывающих требование целочисленности, область допустимых решений ослабленной задачи постепенно изменяется до тех пор, пока координаты оптимального решения не станут целочисленными. Вводимые дополнительные ограничения отсекают некоторые области допустимых решений, в которых отсутствуют точки с целочисленными координатами. Примером метода отсечений является метод Гомори [17], основным недостатком которого является его достаточно медленная сходимость.

В основе генетических алгоритмов [30] лежит принцип естественного отбора (выживания сильнейшего или наиболее приспособленного). Вкратце, стандартный генетический алгоритм можно описать следующим образом:

1. Формируется начальная популяция решений задачи (некоторый набор векторов).

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

3. К векторам применяется операция скрещивания, в результате которой, получается новый вектор.

4. К полученному вектору применяется операция мутации, т.е., над вектором производятся небольшие случайные модификации.

5. Решение добавляется в популяцию, при этом из нее удаляется решение, соответствующее худшему минимуму.

6. Шаги с 1-го по 5-й выполняются до тех пор, пока популяция не будет состоять из векторов доставляющих самые оптимальные решения, согласно определенным заранее критериям.

Существует большое число [31-38], всевозможных модификаций описанного выше генетического алгоритма. Все они в той или иной мере справляются с задачей комбинаторной оптимизации. Однако у этих алгоритмов есть существенный недостаток — время работы.

Искусственные нейронные сети [39-43] — математические модели, а также их программные или аппаратные реализации, построенные по принципу организации и функционирования биологических нейронных сетей — сетей нервных клеток живого организма. Это понятие возникло при изучении процессов, протекающих в мозге, и при попытке смоделировать эти процессы. ИНС позволяют быстро находить приближенные решения задач дискретной оптимизации больших размерностей (N>1000). Однако нейросети также критичны к требованиям оперативной памяти и вычислительной сложности.

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

§1.2. Нейронные сети и модель Хопфилда

Теория искусственных нейронных сетей - одна из областей математики, существующая уже более полувека и активно развивающаяся по настоящее время. Создание искусственных нейронных сетей было вызвано попытками понять принципы работы человеческого мозга. Однако, в сравнении с человеческим мозгом, искусственные нейронные сети сегодня представляют собой весьма упрощенные абстракции. Основные результаты в этой области связаны с именами У. Маккалоха (W. McCulloch) [44], У. Питтса (W. Pitts) [44], Д. Хебба (D. Hebb) [45], Ф. Розенблатта (F. Rosenblatt) [46], М. Минского (М. Minsky) [47] и Дж. Хопфилда (J. Hopfield) [48]. Область применения нейронных сетей довольно обширна. С их помощью можно успешно решать такие задачи как распознавание образов, классификация, идентификация, прогнозирование, аппроксимация функций, оптимизация, управление сложными объектами и др.

Нейронные сети не программируются в привычном смысле этого слова, они обучаются. Возможность обучения — одно из главных преимуществ нейронных сетей перед традиционными алгоритмами. Технически обучение заключается в нахождении коэффициентов связей между нейронами. В процессе обучения нейронная сеть способна выявлять сложные зависимости между входными данными и выходными, а также выполнять обобщение. Это значит, что в случае успешного обучения сеть сможет вернуть верный результат на основании данных, которые отсутствовали в обучающей выборке, а также неполных и/или «зашумленных», частично искаженных данных.

Одной из известнейших моделей искусственной нейронной сети является модель Хопфилда, предложенная в 1982 году американским ученым - специалистом в области физики твердого тела, Джоном Хопфилдом.

На создание данной модели Хопфилда подтолкнули его исследования в области спиновых стекол [49-52]. В кристаллической решетке атомы, обладающие магнитными моментами - спинами, могут различным образом

взаимодействовать друг с другом. Если взаимодействие между спинами таково, что оно стремится сориентировать их параллельно, то в основном состоянии (когда температура вещества Т = 0°К) все атомы в решетке ориентируют свои спины параллельно. Такие вещества называются ферромагнетиками. Для других веществ - антиферромагнетиков, каждому положительному направлению спина атома соответствует атом с противоположным направлением спина. Однако существуют такие вещества, в которых характер взаимодействия между магнитными моментами приводит к тому, что в основном состоянии направления спинов хаотичны. Такие вещества носят название спиновых стекол. Для спиновых стекол такое поведение магнитных моментов означает вырождение основного состояния. Спиновое стекло может «замерзнуть» в любом из возможных состояний системы.

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

Для модели Хопфилда была измерена емкость памяти, величина которой составила менее 15% от размерности сети N. Впервые было введено понятие энергии нейронной сети, которая в процессе работы нейронной сети монотонно понижается. Хопфилд показал, что эта энергия ограниченна и в силу монотонности ее понижения процесс распознавания конечен, а

эталонные векторы, записываемые в нейронную сеть по правилу Хебба, являются локальными минимумами введенного им энергетического функционала.

В период 1985-1987 гг. Амит, Гудфренд и Шомполинский [53] на основе статфизических методов развивают подход, позволяющий получить аналитические оценки емкости памяти и вероятности ошибки

распознавания модели Хопфилда.

Исследования, начатые Гарднер и проводимые с 1965 по 1993 годы, показали, что максимальная емкость памяти модели Хопфилда [54-58] при оптимальном правиле обучения (не хеббовском) не превышает 2Ы.

51 в2

Рис. 1.1. Схема нейронной сети Хопфилда размерностью N = 5 .

Модель Хопфилда принято описывать как систему взаимосвязанных нейронов (рис. 1.1). Состояние сети описывается N -мерным вектором 8, компоненты которого, бинарные переменные, принимают значения ± 1. Связи между нейронами задаются с помощью симметричной матрицы связей

л

А с нулевыми диагональными элементами. Каждый нейрон связан со всеми остальными.

Пусть в начальный момент времени сеть находится в состоянии 80. На каждый нейрон со стороны остальных нейронов действует локальное поле Н

Н = -В + А • 8. (1.1)

Под влиянием этого поля компоненты состояния $(/) меняются по правилу:

Состояние нейрона не меняется, если ориентация этого нейрона и локального поля одинаковы, и меняется на противоположное в противном случае. Вектор В задает пороги нейронов, т.е. границу, при превышении которой нейрон меняет свое состояние.

Состояние сети характеризуется функцией энергии Е

Я = 4(8,А8)+(В,в), (13)

В процессе эволюции сети энергия состояния неуклонно понижается. Постепенно система приходит в состояние покоя.

Правило обучения для сети Хопфилда опирается на исследования Дональда Хебба [45], который предположил, что синаптическая связь, соединяющая два нейрона, будет усиливаться, если в процессе обучения оба нейрона согласованно испытывают возбуждение либо торможение. Простой алгоритм, реализующий такой механизм обучения, получил название правила Хебба. Итак, требуется построить процесс получения матрицы связей А, такой, что соответствующая нейронная сеть будет иметь в качестве стационарных состояний образы обучающей выборки (значения порогов нейронов В обычно полагаются равными нулю). Математически правило

Хебба можно записать следующим образом

м

А = (1.4)

Здесь М - число эталонных образов, записываемых в нейронную сеть; -/л - ый эталон. Ряд исследований показывает, что нейронная сеть, обученная по правилу Хебба, может в среднем, при больших размерах сети N, хранить не более чем М = 0.138А^ различных образов.

Довольно часто используется обобщенное правило Хебба, т.е. каждый эталон записывается в сеть с некоторым весовым коэффициентом

м м

А = Ег^в; , где =1. (15)

При использовании обобщенного правила становится возможным сделать некоторые эталоны глубже других (чем больше г' , тем глубже минимум). В

работах [59, 60] исследуются различные способы выбора весовых коэффициентов г■ , например, как числовой ряд или геометрическую

прогрессию. При этом как коэффициент�