Параллельная реализация логических нейронных сетей

Размещено на http://www.allbest.ru/

19

Размещено на http://www.allbest.ru/

Содержание

Введение

Глава 1. Задача логического вывода в нейронных сетях

1.1 Искусственные нейронные сети

1.2 Логические нейронные сети

1.3 Логический вывод

1.3.1 Принцип резолюции Робинсона

1.3.2 Параллельный метод резолюции

1.4 Выводы

Глава 2. Построение логической нейронной сети для задачи логического следования

2.1 Реализация конструктора сети и подстановки значений

2.2 Возможности параллелизации использованных алгоритмов

2.3 Выводы

Глава 3. Применение технологии CUDA для параллельной реализации логической нейронной сети

3.1 История и структура технологии CUDA

3.2 Применение технологии

3.3 Реализация параллельного алгоритма

Заключение

Список литературы

Приложения



Введение

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

Чтобы попытаться решить данную проблему, человечество изобретало различные устройства, приспособления, позволяющие облегчить нагрузку на человека. Венцом данных изобретений стали ЭВМ, позволяющие хранить и обрабатывать огромные объёмы различной информации. Однако, сама информация не столь важна, как понять, что делать, обладая данной информацией. Нужны системы анализа данных и принятия решений на их основе. Данная концепция систем принятия решений позволяет работать с большим количеством данных, анализируя входящую информацию и выдающая в качестве результата определённое действие или порядок действий, необходимых человеку. Эти системы получили огромное распространение в различных сферах, в которых необходимо оперативное получение конечных данных, например в экономике, медицине, в сферах моделирования различных систем и процессов, а так же в системах контроля работы предприятий и системах безопасности.

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

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

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

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

1)Обучающиеся с учителем;

2)Обучающиеся без учителя.

Также, нейронные сети можно классифицировать в зависимости от поставленных задач, например по типу вводимых данных, или по виду выходной информации. Так одни из самых распространённых сетей - сети, анализирующие изображения, или, например, системы распознавания рукописного текста. В данной работе будут рассмотрены логические нейронные сети. Базисом для таких сетей является алгебра логики. Предложенный Жаком Эрбраном и разработанный Джоном Робинсоном, алгоритм предполагает доказательство теоремы методом «от противного», через поиск противоречия во входной информации. Первоначально метод был реализован перебором множества входных данных до тех пор, пока не находилось искомое противоречие, или цикл не останавливался. Однако, в 1980-е годы, когда Япония объявила о старте проекта «ЭВМ пятого поколения», для реализации логических систем был переделан метод резолюции для параллельной реализации. Данный метод воплотил Ehud Shapiro( Ехуд Шапиро) в проекте «Flat Concurrent PROLOG», параллельной реализации логического языка программирования «PROLOG». Распараллеливание данного метода позволяет произвести резолюцию сразу над всем входным множеством за 1 раз. Таким образом, системы логического вывода получили своё параллельное воплощение, в том числе в виде логических нейронных сетей.

Нейронная сеть является параллельной структурой, состоящей, в минимальной конфигурации, из входного и выходного слоя. Обучение и работа нейронной сети происходит по схеме SIMD(Single Instruction - Multiple Data), что означает выполнение одной функции(инструкции) на некотором наборе различных входных данных. Таким образом, работа нейронной сети напрямую зависит от используемых алгоритмов работы, и естественно, при реализации параллельных алгоритмов обучения и работы, скорость выполнения поставленных задач будет намного больше.

Для реализации любого параллельного алгоритма, любых параллельных процессов, необходима подходящая архитектура ЭВМ, позволяющая одновременное выполнение задач. Подходящими конфигурациями для реализации параллельной работы являются многоядерные, многопроцессорные вычислительные машины и комплексы, а так же архитектуры, позволяющие использовать графическую карту для вычислений, такие как CUDA(Nvidia), C++ AMP(Microsoft), OpenCL, OpenACC и AMD FireStream. Использование процессора графической карты для вычислений отличается от использования нескольких ядер центрального процессора лишь тем, что графические карты имеют в разы большее количество ядер, а значит, имеют больше возможностей для параллелизма выполняемых задач. Однако стоит отметить тот факт, что при большом количестве ядер у графической карты, каждое ядро само по себе довольно слабое, поэтому выполнять на графических картах стоит только процессы, которые не нуждаются в мощной производительности.

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

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

а)Рассмотреть модели нейронных сетей, их реализации и основные идеи.

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

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

д)Установить зависимость между логическим следованием и логическим выводом.

е)Проанализировать полученную информацию, и на её основе изложить идеи параллельной реализации логической нейронной сети и метода логического следования.

ж)Реализовать логическую нейронную сеть для задачи логического следования.

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

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

Данная бакалаврская дипломная работа содержит введение, три главы, посвящённые каждому аспекту работы в отдельности, заключение, список литературы и приложения, содержащие конечную реализацию программы на C++.

Введение кратко характеризует область проводимой работы, её основные подразделы, описывает поставленные задачи и конечную цель.

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

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

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

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



Глава 1. Задача логического вывода в нейронных сетях

1.1 Искусственные нейронные сети

Впервые нейронные сети были упомянуты в работе Уоррена Мак-Каллока и Уолтера Питтса «Logical calculas of the ideas immanent in nervous activity» (рус. «Логическое исчисление идей, относящихся к нервной активности») в 1943 году. В статье было формализовано понятие нейронной сети и описана работа нейронов формулами математики и алгебры логики, исходя знаний об устройстве нервной системы. Было отмечено, что искусственный нейрон является простейшим логическим устройством, однако без обучения, не способен выполнять никаких функций. Алгоритм обучения был предложен в 1949 году Дональдом Хеббом в книге «Организация поведения: нейропсихологическая теория» и предполагал, что при частой стимуляции нервной системы образуются нейронные структуры.

Первый однослойный персептрон появился в 1958 году, благодаря Фрэнку Розенблатту и имел возможность выполнять задачи классификации, из-за чего обрел популярность в различных сферах. После публикации книги «Перцептроны» Марвином Минским и Сеймуром Папертом в 1969 году, в которой подробно приводилось доказательство невозможности обучения универсального перцептрона, и описывались классы задач, которые перцептрон не мог разрешить, интерес к нейронным сетям практически исчез.

Исследования в данной сфере продолжились, и в 1972 году Теуво Кохонен и Джеймс Андерсон независимо предлагают новый тип нейронных сетей. Так, до 1982 года, нейросетевые технологии были в упадке. Однако, модель сети с обратными связями, созданная Джоном Хопфилдом, показала новые возможности применения нейронных сетей. В это же время Теуво Кохонен предоставил модели нейронной сети, с возможностью обучения без учителя. 4 года спустя, двумя независимыми группами учёных, состоящих из Дэвида Румельхарта с Джеффри Хинтоном и Рональдом Вильямсом, и С.И. Барцева с В.А Охониным, был заново изучен и существенно развит метод обратного распространения ошибки. С этого момента в научной сфере вновь появился интерес к развитию технологий нейронных сетей, а благодаря широкому распространению персональных компьютеров, исследования в этой области крайне ускорились.

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

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

Исходя из этого, архитектуру нейронной сети можно характеризовать схемой SIMD(Single Instruction - Multiple Data), то есть выполнение одной функции для множества данных. По такой схеме реализуется вычислительный процесс на графических картах, а следовательно, архитектура графической карты полностью подходит для реализации на ней нейронных сетей. Однако прежде чем перейти к реализации, следует рассмотреть её устройство и алгоритмы её работы.

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

Рисунок 1.1 Схема работы искусственного нейрона

Таким образом, нейрон вычисляет входное значение базисной функцией

Neti (щ ij, j ),

где значения j - значения входных векторов, а щ ij - соответствующие синаптические веса.

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

а) Линейная: функция выполняет операцию сложения типа:

Neti (щ ij, j ) =

б) Радиальная: значение вычисляется по формуле расстояния от входного значения до некоторого «шаблонного»:

Neti (щ ij, j ) =

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

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

а) Линейные:

F(net) = ,

где net - текущее значение, min и max - некоторые выбранные пороговые значения.

б) Пороговые функции типа «скачок»:

F(net) = , в данном случае значение порога выбрано равным 0, однако можно выставить данное значение равным любому, подходящему под реализуемую модель. Одна из распространённых функций такого типа -

F(net) = sign(net), sign(net) =

в) Сигмоидальные функции:

F(net) = ,

где «k» - коэффициент наклона функции. Обычно принято брать k = 1. При выборе бесконечно большого значения k, функция вырождается в пороговую.

д) Функция Гаусса:

F(net) = ,

где S = ||x - c|| - «расстояние» между значениями входного вектора, и некоторого заданного шаблона; R - параметр, отвечающий за сдвиг функции по оси абсцисс; - параметр, определяющий скорость изменения значения функции, при отдалении от центра.

Графически, перечисленные виды функций, отображены на рисунках 1.2(А-Г)



Рис. 1.2 А) Линейная Б) Пороговая

Рис. 1.2 В) Сигмоидальная Г) Гауссова

Помимо приведённых активационных функций, существует множество их модификаций и функций других видов. В некоторых сетях активационная функция не используется, и выходное значение вычисляется как F(net) = net.

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

а) Прямая связь:

Процесс передачи выходного сигнала происходит последовательно, с выхода одного слоя, на вход следующего.

б) Обратная связь:

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

в) Боковая связь:

Выходные сигналы передаются внутри слоя от нейрона к нейрону.

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

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

а) Обучение с учителем;

б) Обучение без учителя;

в) Обучение по алгоритму с фиксированными весами.

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

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

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

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

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

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

1.2 Логические нейронные сети

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

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

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

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

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

Возьмём передаточную функцию некоторого нейрона:

V = ,

где ;

Vj - величина сигнала, поступающего на j-й вход нейрона.

В модели логической нейронной сети рассматриваются 2 типа нейронов, реализующих логические функции. Это нейрон-конъюнктор и нейрон-дизъюнктор.(рис 1.3А, 1.3Б)

Рисунок 1.3А) Модель нейрона-конъюнктора

Рисунок 1.3Б) Модель нейрона-дизъюнктора

Для реализации модели нейрона-конъюнктора используется высокое значение порога. Значение «д» - поправка, необходимая для того, чтобы для преодоления порога, сигнал поступал по всем входам.

Модель нейрона-дизъюнктора выполняется при низком значении порога, но при высоком значении весов. Это условие обеспечивает получение выходного значения при хотя бы одном входном сигнале, но в таком случае необходимо дополнительное условие, ограничивающее выходное значение, то есть Vi 1. Во время процесса обучения дизъюнктора, предполагается получение точных входных и выходных данных, а следовательно логическая функция «ИЛИ» превращается в «исключающее ИЛИ», поскольку в данном случае предполагается возбуждение всего на одном входе.

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

Проанализировав входное множество, необходимо выделить все используемые переменные, подаваемые на вход, после чего надо построить структуру, а затем обучить её. Первая часть обучения происходит методом трассировки, когда по предъявляемому сети эталону выстраивается путь от входных значений к выходному. При предъявлении нескольких эталонов нейронная сеть строит пути последовательно, выбирая ещё не задействованные нейроны и вводя необходимые связи. Данный алгоритм повторяется до тех пор, пока не будет достигнута полная определённость для всех входных эталонов, предъявляемых сети. Для алгоритма трассировки нейронной сети используется понятие матрицы следования - матрицы, в которой строки и столбцы - нейроны, а значения, стоящие на их пересечении отвечают за наличие или отсутствие связи. Алгоритм позволяет выстроить связи, цепочки следования из входного слоя к выходному через скрытые слои. Таким образом, мы получаем готовую структуру логической нейронной сети. Следующим шагом обучения является приведение нейронной сети после трассировки, то есть коррекция весов и порогов для достижения необходимых результатов. Также, для получения более точных результатов, можно использовать коэффициент приведения, который будет рассчитываться для каждого нейрона. Коэффициент «K» будет вычисляться по следующей формуле:

Кj = ,

нейронный сеть логический параллельный алгоритм



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

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

1.3 Логический вывод

1.3.1 Принцип резолюции Робинсона

Математическая логика, как наука, содержит в себе множество подразделов. Один из таких подразделов, называемый теорией доказательств, рассматривает возможность представления доказательств, как формальных математических объектов, путём их анализа математическими методами. Теория доказательств является синтаксическим методом, и получила своё развитие благодаря работам многих учёных, таких как Г. Фреге, Дж. Пеано. Однако считается, что более современная теория доказательств начинается с работ Д. Гильберта, К. Геделя и Яна Лукашевича. В итоге теория доказательств была сведена к методам дедукции и естественного вывода. Так в 1930 году в докторской диссертации Жака Эрбрана впервые появилось понятие правила резолюций - основного механизма для логического вывода.

Формулировка правила была следующей:

Имея логическую формулу А, из которой выводится логическая формула В, то доказуема операция импликации (логического следования) А=>В.

Данное правило позволяло аналитическим путём установить существование выводов и доказательств, не использую их построения.

Дальнейшую разработку данного правила, используемую по сегодняшний день, провёл Джон Алан Робинсон. В 1965 году Робинсон опубликовал работу «Машинно-ориентированная логика, основанная на принципе резолюции», в которой метод резолюции рассматривался более подробно, а также было описание методов построения логических систем на основе этого метода. В дальнейшем своём развитии, работы Робинсона стали основой для создания логических систем, в частности языка логического программирования PROLOG.

Суть метода резолюции заключалась в следующем: имея 2 высказывания, называемых резольвируемыми, необходимо получить из них новое выражение, которое будет содержать все литералы изначальных высказываний, за исключением взаимно обратных литералов. То есть, имея в качестве исходных данных выражения типа A1 = P v B'1 и A2 = !P v B'2 , необходимо получить резольвенту B'1 v B'2 . Знак «!» означает логическое отрицание. Правило вывода данного выражения называется правилом резолюций. Данное правило применяется для доказательства теорем. Происходит это по следующему алгоритму:

а) Формулировка:

Пусть некоторая формула H - гипотеза теоремы, является логическим следствием некоторого множества формул F1,…,Fk. Или иными словами, «если F1,…,Fk - истинны, то истинна H».

б)Применение метода:

1) Создадим новое множество формул {F1,…,Fk, !H}

2) Приводим каждую формулу к КНФ, убираем знаки конъюнкции, получаем множество дизъюнктов S.

3) Ищется вывод пустого дизъюнкта, попарным применением правила резолюций, то есть путём исключения взаимно обратных литералов.

в) Результат метода:

Если после применения метода к множеству S, был получен пустой дизъюнкт, то формула Н является логическим следствием из множества формул F1,…,Fk. В противном случае, если пустой дизъюнкт не был получен, то Н не является следствием из формул F1,…,Fk.

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

На основе метода резолюций базируется огромное множество логических систем и средств логического вывода. В логическом программировании данный метод применяется в совокупности с одним из методов рассуждения - прямым или обратным, правилами «modus ponens» и «modus tollens».

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

1.3.2 Параллельный метод резолюции

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

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

Для реализации параллельной системы логического вывода, Ехуд Шапиро во второй половине 1980-х годов разработал новый вид языка логического программирования PROLOG, названный «Flat Concurrent PROLOG», в котором вместо последовательной обработки логической информации, использовался параллельный подход. Распараллеливание алгоритмов логического вывода позволило добиться существенного сокращения временных затрат. Если прежние, последовательные версии, для функции времени от количества данных выдавали значения, пропорциональные О(log n), то нововведённые параллельные методы позволили добиться зависимости вида О(n/(log n)2), что означало существенный прорыв в данной технологии.

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

Алгоритм в своей сути не отличался от последовательного. Разница была в параллельном выборе и обработке дизъюнктов. Рассмотрим сам параллельный алгоритм:

а) Формулировка осталась такой же, как и при последовательном случае, то есть «если формулы F1,…,Fk - истинны, то истинна гипотеза H».

б)Применение метода:

1) Также происходило объединение множества формул {F1,…,Fk, !H}

2) Приводим каждую формулу к КНФ, убираем знаки конъюнкции, получаем множество дизъюнктов S.

3) Ищется вывод пустого дизъюнкта, попарным применением правила резолюций. Каждая пара обрабатывается параллельно следующим образом: для всех индексов i и j, где i, j?[1,n], i ?j, создавались пары (Fi ,Fj), к которым применялось правило резолюции.

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

в) Результат метода:

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

1.4 Выводы

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

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

Логические нейронные сети не имеют общего шаблона, и каждая такая сеть строится в зависимости от поставленной задачи. Путём анализа входных данных, используемых формул и поставленной цели, логическая нейронная сеть создаётся в виде структуры из конъюнкторов и дизъюнкторов, объединённых связями, полученными из условий задачи. Опираясь на булеву алгебру, логические нейронные сети покрывают широкий спектр задач, а также осуществлять логический вывод типа «причина-следствие», что применяется для различных систем управления, а также для систем автоматического доказательства теорем.

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

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

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

Целями данной работы являются:

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

б) Реализуемая модель логической нейронной сети должна выполнять проверку логического следования на истинность или ложность.

в) Для всего множества различных входных переменных должна быть реализована проверка на всех комбинациях входных переменных. Поскольку такая проверка порождает 2n различных наборов, n - количество переменных, необходима оптимизация в виде распараллеливания данного алгоритма подстановки значений.

д) Рассмотреть возможности параллелизации алгоритмов в процессе создания и работы нейронной сети

е) Используя технологию CUDA, написать программу, реализующую поставленные цели.



Глава 2. Построение логической нейронной сети для задачи логического следования

2.1 Реализация конструктора сети и подстановки значений

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

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

Рассмотрим реализуемый алгоритм:

1)Вводится множество формул.

2)Проводится посимвольный анализ для получения размера входного вектора

3)Также посимвольным анализом, устанавливаются зависимости между используемыми переменными и их композициями во ведёных формулах

Формулы вводятся вручную, после чего вычисляется общее количество различных переменных, используемых во всём введённом множестве, а так же наличие обратных переменных, к которым применён оператор отрицания. Далее оценивается общее количество используемых формул и для каждой из введённых формул рассматривается используемое множество переменных. Строится динамический двумерный массив, размерности которого - количество переменных и использованных формул.

Первично в массив заносятся значения 1,0 и -1, для обозначения использования переменной, отсутствия переменной и использование обратного значения переменной соответственно. Данная структура изображена на рисунках 2.1А и Б, где 1-й столбец массива - пустой, используемый в дальнейшем для помещения в него входных значений. 2-й столбец отвечает за использование обратных значений. Столбцы, начиная с 3-го, отвечают за введённые функции. Под матрицей отображён массив, содержащий информацию о количестве используемых переменных для каждой формулы.

Рисунок 2.1 А Рисунок 2.1Б

Таким образом, реализованный алгоритм позволил построить первоначальную структуру сети. Массив является динамическим, то есть позволяет создавать структуру сети для любого количества формул и переменных, что показано на рисунках 2.1А, Б.

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



Как было сказано ранее, первый столбец остаётся пустым, а затем в него записываются значения наборов переменных. Набор значений переменных представляет собой множества нулей из единиц. Пример изображён на рисунке 2.2

Рисунок 2.2 Пример входных значений

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

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



2.2 Возможности параллелизации использованных алгоритмов

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

Первым применением параллельных вычислений будет занесение значений переменных в массив. Вместо поочерёдной передачи каждого нуля или единицы, может быть реализована передача всего столбца, что сокращает количество операций в «n» раз. Однако, более эффективным будет рассмотрение параллельной передачи всех входных значений. Тогда количество передач будет ограничено только количеством ядер.

Главной задачей в этом разделе является параллельный способ вычисления введённых функций. Поскольку для «n» переменных мы получим 2n различных наборов входных значений, максимально затратным является именно обработка всего этого множества. Поскольку ограничение количества операций заключается только в мощности устройства, на котором будет реализована работа данной сети, возможно получить уменьшение количества операций благодаря параллельной организации вычислений, вплоть до одного шага.

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

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

Способ параллельной передачи входных данных изображён на рисунке 2.3, параллельная передача значений в каждую функцию изображена на рисунке 2.4.

Рисунок 2.3 Параллельная передача значений

Рисунок 2.4 Параллельное выполнение каждой функции для одного набора



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

Рисунок 2.5 Полная параллелизация задачи

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

В таком случае, графическое представление будет следующим.

Рисунок 2.6 Разбиение параллельных операций

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

2.4 Выводы

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

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

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

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



Глава 3. Применение технологии CUDA для параллельной реализации логической нейронной сети

3.1 История, структура

Технологии обработки информации постоянно развиваются, для достижения большей эффективности на новых архитектурах. Так в 2003 году было предложено использовать процессор графической карты для параллелизации алгоритма вычислений, путём передачи обрабатываемых данных с центрального процессора на процессор видеокарты. 3 года спустя, одна из передовых компаний, производящих графические карты воплотило новую архитектуру построения процессора графической карты, позволяющую задействовать её в качестве сопроцессора. Технология была названа CUDA, что являлось аббревиатурой от «Сompute Unified Device Architecture». Впервые данная архитектура была воплощена в графических картах серии Nvidia GeForce 8800 gtx. В картах этой модели использовался чип восьмого поколения G80, который в дальнейшем присутствовал во всех последующих графических картах.

Технология CUDA представляет собой не только новую архитектуру устройства графической карты. В это понятие также входит набор программ и надстроек, позволяющих создавать свои приложения на различных языках программирования, используя параллелизм графической карты. Языками, поддерживающими данную технологию являются Fortran и C/C++. Для того, чтобы начать работу с данной технологией, необходимо скачать с официального сайта компании Nvidia подходящий пакет программ, названный CUDA Toolkit, и установить его.

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

Архитектура CUDA использует модель памяти «Grid>Block>Thread», позволяющая независимый параллельный доступ к памяти видеокарты. Данная структура изображена на рисунке 3.1.

Рисунок 3.1 Структура памяти в графической карте

На этой иллюстрации присутствуют следующие понятия:

1)Host - центральный процессор используемой ЭВМ.

2)Kernel - ядро ЦП.

3)Device - графическая карта

4)Grid - размеченная сетка, массив из блоков памяти.

5)Block - блок памяти, массив, объединяющий некоторое количество нитей

6)Thread - нить, указатель на конкретное место в памяти графической карты.

Каждому блоку соответствует одно ядро графической карты, что позволяет добиться высокого параллелизма при использовании вычислений на графической карте. В современных графических картах Nvidia Tesla количество таких ядер насчитывает порядка пяти тысяч, что означает возможность использования до 5 тысяч параллельных операций. Благодаря синхронизируемой барьерной памяти, не существует проблем с использованием одного участка разными процессами, а следовательно позволяет избежать множества ошибок. В целом, систему памяти в CUDA можно изобразить, как на рисунке 3.2

Рисунок 3.2 Организация памяти в CUDA



3.2 Применение

Технология CUDA получила широкое распространение на сегодняшний день. Поскольку в большинстве сфер не требуется сложных, затратных с точки зрения производительности ЭВМ, операций, то выгоднее провести выполнение таких простых процессов не на центральном процессоре, тем самым освободив его, и предоставив возможность обработки более сложный операций. Таким образом, выгодно использовать графические карты для подобных простых вычислений, особенно при необходимости реализации схемы SIMD, для одновременной обработки большого количества однотипных данных.

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

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

Для реализации логической нейронной сети также возможно применение параллельной архитектуры CUDA для обучения, и для последующей работы. Если рассматривать реализацию логической нейронной сети, как средства логического вывода и автоматического доказательства теорем, то для применения параллельного метода резолюции Шапиро, необходима параллельная структура, которая позволит одновременно обрабатывать всё входное множество дизъюнктов. Таким образом технология CUDA по всем характеристикам подходит для данной реализации.

3.3 Реализация параллельного алгоритма

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