Разработка и реализация параллельного алгоритма для построения моделей нейронных сетей Ваттса-Строгаца

ВВЕДЕНИЕ 5
1.ОБЗОР СУЩЕСТВУЮЩИХ РЕШЕНИЙ 10
2. ПОСЛЕДОВАТЕЛЬНЫЕ АЛГОРИТМЫ 12
2.1. Алгоритм построения модели нейронной сети Ваттса-Строгаца . 12
2.2. Алгоритм расчета длины кратчайшего пути в среднем 15
2.3. Расчет коэффициента кластеризации 17
2.4. Матрицы смежности, инцидентности и запаздывающих
взаимодействий 18
3. РЕАЛИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ 21
3.1. Архитектура сопроцессора Intel Xeon Phi. Параллельные
алгоритмы для сопроцессора Intel Xeon Phi 21
3.2. Параллельный алгоритм построения нейронной сети 22
3.3. Параллельный алгоритм расчета длины кратчайшего пути в
среднем 22
3.4. Параллельный алгоритм расчета коэффициента кластеризации . 22
4. ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ 24
ЗАКЛЮЧЕНИЕ 31
ЛИТЕРАТУРА 32
Купить

Изучение нейронных сетей является активно развивающейся в настоящее время областью прикладной математики. Искусственная нейронная сеть - математическая модель, построенная по принципу организации и функционирования сетей нервных клеток живых организмов. В качестве нейронной сети можно рассматривать любую модель, содержащую узлы и связи между ними. Нейронные сети находят применение во многих областях: социологии, экономике, биохимии, технических науках.
Топология связей в сетях обычно бывает либо полностью регулярной, либо полностью произвольной. Но, поскольку многие реальные сети находятся между двумя этими крайностями, была выделена группа сетей, обладающая высокой степенью кластеризации, как сети с решетчатой топологией, и имеющая малую среднюю длину пути, как сети со случайной (произвольной) топологией. Такие сети носят название «small-world» и были описаны Дунканом Ваттсом и Стивеном Строгацем в 1998 году [15]. «Small-world» определяется как сеть, в которой расстояние L между двумя произвольно выбранными вершинами растет пропорционально логарифму от числа вершин N в сети, то есть L х log2 N. За этой работой по следовало множество других исследований проявлений свойств «small world» [1, 5, 9, 10, 13]. Сети «small world» описывают различные объекты, в том числе, различные отделы головного мозга [7, 11], а в сфере информационных технологий они проявляют себя в файлообменных сервисах [8], пиринговых сетях.
Такие сети имеют много вершин с редкими связями, но не настолько редкими, чтобы граф мог оказаться несвязным, поэтому принимаем N >> к >> lnN >> 1, где к >> ln N гарантирует связность графа [3]. Также «small-world» сети имеют тенденцию содержать в себе клики (термин пришел из работы [6]), это следует из определения такого свойства сети, как коэффициент кластеризации - степень, с которой вершины склонны группироваться вместе.
Алгоритм построения сетей «small-world» (описанный далее в разделе 2.1) позволяет «настроить» граф на промежуток между регулярностью и произвольностью и исследовать область 0 < р < 1. В работе [15] показано, что есть большой интервал р, на котором длина пути L(p) почти также мала как в произвольном графе Lrandom при коэффициенте кластеризации много большем, чем в произвольном графе, С (р) >> Crandom (см. рис. 1). Данные собирались для графов с числом вершин N = 1000 и соседей к = 10 и были нормированы с помощью значений L(0) и С(0) для регулярного графа. Логарифмическая горизонтальная шкала использована, чтобы показать быстрое падение длины пути L(p), что соответствует «small-world». При этом коэффициент кластеризации С(р) почти не изменяет своего значения, соответствующего регулярному графу. Это значит, что переход сети к виду «small-world» почти невозможно заметить на локальном уровне.

Рис. 1. Расчет коэффициента кластеризации для узла

Проверка с использованием разработанного продукта показала аналогичное распределение значений (см. рис. 2).

Рис. 2. Расчет коэффициента кластеризации для узла

Согласно графикам, сеть типа «small-world» получается при значении вероятности от 0.01 до 0.1. То есть, чтобы отнести моделируемую сеть к типу «small-world», нужно проанализировать полученные значения длины кратчайшего пути в среднем и коэффициента кластеризации. Но для исследования областей устойчивости нейронных сетей будет интересна любая сеть, моделируемая со значением вероятности из области 0 < р < 1, упомянутой в оригинальной работе [15].
Одним из предметов исследования в работе [17] является важное свойство - устойчивость нейронной сети. Устойчивость - способность продолжать стабильно функционировать при возникновении колебаний при передаче сигналов между нейронами, например, вследствие запаздывания. Достаточно разработана тема устойчивости непрерывных моделей нейронных сетей стандартных конфигураций (кольцевой и линейной) [21]. Особенностью данной работы является то, что модель нейронной сети дискретна, то есть для изучения проблемы ее устойчивости необходимо применение теории разностных матричных уравнений с за-
паздываниями [16]. В работе [17] рассматривается уравнение вида эд ^xs—m + Bxs—^, s 1,2,...
где: у - коэффициент демпфирования нейронной сети; В матрица взаимодействий нейронов в сети; к запаздывание во взаимодействии различных нейронов; т - запаздывание в демпфировании собственных колебаний нейрона.
Эта проблема разработана гораздо меньше, чем аналогичная для непрерывных моделей. В работе [17] был разработан метод анализа устойчивости дискретных моделей нейронных сетей - метод конусов устойчивости, для которого был реализован программный продукт [18] в программной среде MATLAB.
Цель и задачи исследования
Целью данной работы является разработка и реализация параллельных алгоритмов для построения моделей нейронных сетей Ваттса-Строга- ца, расчета их параметров, генерации входных данных для программного продукта [18], осуществляющего анализ устойчивости нейронных сетей.
Для достижения поставленной цели нужно выполнить следующие задачи:
1) рассмотреть существующие варианты последовательного алгоритма по строения моделей нейронных сетей Ваттса-Строгаца и его реализации, а также алгоритмов для расчета его свойств;
2) изучить методы разработки параллельных алгоритмов для сопроцессора Intel Xeon Phi;
3) на основе существующих последовательных алгоритмов спроектировать и реализовать параллельные алгоритмы;
4) провести эксперименты по оценке эффективности разработанных алгоритмов.
Структура и объем работы
Работа состоит из введения, 4 основных разделов, заключения и библиографии. Объем работы составляет 34 страницы, объем библиографии - 21 наименование.
Содержание работы
В первом разделе проведен обзор существующих алгоритмов и их реализаций для построения модели нейронной сети Ваттса-Строгаца и расчета ее коэффициентов.
Во втором разделе приведены описания последовательных алгоритмов.
Третий раздел содержит описание параллельных алгоритмов на основе технологии OpenMP, а также приведено краткое описание архитектуры сопроцессора Intel Xeon Phi и методов разработки для этого сопро- цесора.
В четвертом разделе представлены результаты экспериментов и анализ эффективности разработанных алгоритмов.
В заключении подведены итоги проделанной работы.
Купить