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

Главная

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

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


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


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

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Глава 1. Задача логического вывода в нейронных сетях
Глава 2. Построение логической нейронной сети для задачи логического следования
2.1 Реализация конструктора сети и подстановки значений
2.2 Возможности параллелизации использованных алгоритмов
Глава 3. Применение технологии CUDA для параллельной реализации логической нейронной сети
3.1 История и структура технологии CUDA
3.3 Реализация параллельного алгоритма
Начиная с появления первых людей, человечество генерирует различную информацию, и с каждым днём, скорость и объёмы создаваемой информации только увеличиваются. На сегодняшний день информационная сфера является неотъемлемой части жизни практически любого человека. Однако, количество существующей сегодня информации, и информации, действительно нужной человеку, сильно различается, то есть из общего количества всей доступной информации человеку необходимо вычленить именно то, что ему нужно. Обычный человеческий мозг не способен обработать и малой доли всего, что существует сегодня, отсюда мы получаем первую проблему - проблему получения, выбора, анализа информации.
Чтобы попытаться решить данную проблему, человечество изобретало различные устройства, приспособления, позволяющие облегчить нагрузку на человека. Венцом данных изобретений стали ЭВМ, позволяющие хранить и обрабатывать огромные объёмы различной информации. Однако, сама информация не столь важна, как понять, что делать, обладая данной информацией. Нужны системы анализа данных и принятия решений на их основе. Данная концепция систем принятия решений позволяет работать с большим количеством данных, анализируя входящую информацию и выдающая в качестве результата определённое действие или порядок действий, необходимых человеку. Эти системы получили огромное распространение в различных сферах, в которых необходимо оперативное получение конечных данных, например в экономике, медицине, в сферах моделирования различных систем и процессов, а так же в системах контроля работы предприятий и системах безопасности.
Помимо получения необходимого результата, системы принятия решений могут предоставлять пользователю различные прогнозы, а так же, в случаях некорректных, или не полностью соответствующих данных, выдавать примерные данные, более всего подходящие для сложившейся ситуации. Так человек получает возможность оценить полученные результаты и принять оптимальное решение.
На сегодняшний день, к сожалению, не все задачи возможно точно формализовать, и создать алгоритм для конкретной задачи, поскольку зачастую задачу нельзя алгоритмизировать, либо же выполнение расчётов для получения точного значения займут намного больше времени, чем необходимо. В ситуациях такого типа, вместо точного решения, правильнее будет оценить наиболее важные критерии, выделить ключевые значения и присвоить им наиболее подходящие примерные значения, в зависимости от состояния всей системы. При этом стоит отметить, что показатели состояния системы необходимы не только для данного момента, но и прошлые состояния, чтобы путём анализа, понять, как система пришла в данное состояние, какие были для этого предпосылки, а так же «запомнить» следствия, чтобы использовать данную конфигурацию значений в дальнейшем. Для любой системы можно попытаться выделить цикличность состояний, благодаря чему последующий анализ будет проходить проще и быстрее.
Однако, не смотря на столь широкий охват выполняемых задач, системы принятия решений по своей специфике не являются автономными и не могут работать без участия человека. Всё равно необходимо вмешательство человека. Для создания полностью автономной системы необходим аппарат, математическая модель, позволяющая анализировать информацию и принимать решения, с учётом обучаемости данной системы. Таким критериям соответствуют нейронные сети. Созданные как компьютерная симуляция работы мозга, благодаря возможности обучения, нейронные сети могут адаптироваться к новым данным и различным изменениям, принимая при этом верные решения при полной автономии. Таким образом, нейронные сети позволяют добиться высокой точности получаемых результатов при различных, изменяющихся конфигурациях входных данных.
Создание нейронной сети происходит в 2 этапа, это создание нейронов и связей между ними, а затем, процесс обучения сети, однако наиболее важен именно процесс обучения. Нейронные сети по способу обучения делятся на 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. Задача логического вывода в нейронных сетях
Впервые нейронные сети были упомянуты в работе Уоррена Мак-Каллока и Уолтера Питтса «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 Схема работы искусственного нейрона
Таким образом, нейрон вычисляет входное значение базисной функцией
где значения j - значения входных векторов, а щ ij - соответствующие синаптические веса.
Базисные функции, отвечающие за вычисление выходного значения, могут очень сильно различаться, однако среди общего множества можно выделить несколько, используемых наиболее часто:
а) Линейная: функция выполняет операцию сложения типа:
б) Радиальная: значение вычисляется по формуле расстояния от входного значения до некоторого «шаблонного»:
В целом, ограничений на выбор базисной функции нет. Подбор функции происходит в зависимости от задачи, для получения адекватной модели.
После выполнения преобразования величины входного сигнала, нейрон посылает данное значение на выход. Выходное значение подлежит анализу активационной функцией, являющейся своего рода фильтром. Активационная функция оценивает полученное значение, и в случае удовлетворения определённым условиям, значение будет передано далее. Основными активационными функциями являются:
где net - текущее значение, min и max - некоторые выбранные пороговые значения.
б) Пороговые функции типа «скачок»:
F(net) = , в данном случае значение порога выбрано равным 0, однако можно выставить данное значение равным любому, подходящему под реализуемую модель. Одна из распространённых функций такого типа -
где «k» - коэффициент наклона функции. Обычно принято брать k = 1. При выборе бесконечно большого значения k, функция вырождается в пороговую.
где S = ||x - c|| - «расстояние» между значениями входного вектора, и некоторого заданного шаблона; R - параметр, отвечающий за сдвиг функции по оси абсцисс; - параметр, определяющий скорость изменения значения функции, при отдалении от центра.
Графически, перечисленные виды функций, отображены на рисунках 1.2(А-Г)
Рис. 1.2 А) Линейная Б) Пороговая
Рис. 1.2 В) Сигмоидальная Г) Гауссова
Помимо приведённых активационных функций, существует множество их модификаций и функций других видов. В некоторых сетях активационная функция не используется, и выходное значение вычисляется как F(net) = net.
Для реализации структуры сети, необходимо ввести связи между нейронами. Основные виды связей, используемых в нейронных сетях, следующие:
Процесс передачи выходного сигнала происходит последовательно, с выхода одного слоя, на вход следующего.
Выходные сигналы передаются на вход предыдущего слоя, что позволяет производить рекуррентные операции на нейронных сетях.
Выходные сигналы передаются внутри слоя от нейрона к нейрону.
Прежде чем начать создавать нейронную сеть, проводится долгий анализ задачи, в процессе которого определяются топология и размеры сети, передаточные и активационные функции и прочие параметры. Завершив данный этап формализации и переноса поставленной задачи на модель нейронной сети, необходимо начать процесс обучения.
Обучение является ключевым этапом во время создания нейронной сети, и представляет собой процесс настройки параметров, например выбор весов синаптических связей и порогов в активационных функциях. Принято различать 3 вида способов обучения:
в) Обучение по алгоритму с фиксированными весами.
Процесс обучения с учителем заключается в том, что нейронной сети передаются входные данные, и набор заранее вычисленных выходных значений. Таким образом, из полученных значений составляются обучающие пары, а выходная функция производит корректировки, чтобы с максимальной точностью приблизить реальный результат к ожидаемому выходному значению. Система будет продолжать обучение до тех пор, пока результаты не достигнут определённой точности. Основным алгоритмом метода обучения с учителем является метод обратного распространения ошибки, позволяющий рекуррентно корректировать параметры сети.
Для алгоритма обучения без учителя, характерна передача только входных данных. Алгоритм является итеративным, а процесс корректировки заканчивается в случае, если одинаковые входы соответствуют одинаковым выходам. Примером нейронной сети, обучающейся без учителя, служат самоорганизующиеся карты.
При обучении нейронной сети алгоритмом с фиксированными весами, сеть определяет веса по заранее заданным методам расчёта, вычисляя их по входным векторам.
В целом, если кратко сравнить алгоритмы, то результаты, получаемые путём обучения без учителя, являются более реалистичными, поскольку в этих процессах не идёт сравнения с заданным результатом.
Обучение нейронной сети затрачивает много времени, и чем сложнее структура, тем дольше будет проходить обучение. Для ускорения данного процесса существует лишь одно решение - улучшение самого алгоритма обучения. Наиболее эффективной, с точки зрения временных затрат модификацией для процессов обучения является распараллеливание алгоритма.
После завершения стадии обучения, структура нейронной сети фиксируется, то есть дальнейших изменений весов и связей не происходит, сеть переходит в рабочий режим.
Первым шагом для создания нейронной сети является анализ выбранной задачи, которую данная сеть будет выполнять, то есть по установленным требованиям выбирается некоторый стандартный набор функций. В зависимости от поставленных целей, принято классифицировать нейронные сети. Для систем анализа изображений, задач автоматизации управления, экономической сферы, существуют типовые нейронные сети, которые далее модифицируются под конкретно поставленную задачу. В данной работе будет рассмотрен класс логических нейронных сетей.
Для того чтобы определить, в чём заключается суть логических нейронных сетей, рассмотрим пример задачи, стоящей перед данной системой. Допустим, что у нас имеется некоторое множество высказываний, по которому путём неарифметических преобразований должен быть получен результат. Для работы с подобными множествами, необходимо их формализовать, представив все высказывания в виде предикатов. Так получаем возможность обработки предикатов при помощи операций алгебры логики. Решение в данной задаче зависит от истинности или ложности высказываний входного множества. Исходя из этого, логическую нейронную сеть можно охарактеризовать как нейронную сеть, базисом для которой является булева алгебра.
Продолжим рассмотрение поставленной задачи для определения функционала и вида сети. Если взять совокупность всех событий, и выделить среди них те высказывания, которые полностью покрывают смысловой диапазон, получим новое множество. В том случае, если каждая допустимая ситуация характеризуется тем, что истинное значение принимает только одно высказывание этой совокупности, полученное множество будет называться исчерпывающим множеством событий. На основе полученного множества, введя некоторую иерархию, будем строить логические цепочки, позволяющие однозначно получить результат. Систему из таких логических путей, в случае её непротиворечивости и полноты, можно рассматривать как систему принятий решений. Однако, прежде чем перейти к построению нейронной сети из СПР, необходим ещё один шаг в формализации задачи - определение величины входных сигналов.
Поскольку в сети, нейроны представлены в некотором стандартном виде, то величины возбуждения, синапсические связи, пороги и функции должны быть одинаковы, ну или лежать в общем диапазоне значений для всей сети.
После этого шага, можно приступить к выбору параметров сети.
Возьмём передаточную функцию некоторого нейрона:
Vj - величина сигнала, поступающего на j-й вход нейрона.
В модели логической нейронной сети рассматриваются 2 типа нейронов, реализующих логические функции. Это нейрон-конъюнктор и нейрон-дизъюнктор.(рис 1.3А, 1.3Б)
Рисунок 1.3А) Модель нейрона-конъюнктора
Рисунок 1.3Б) Модель нейрона-дизъюнктора
Для реализации модели нейрона-конъюнктора используется высокое значение порога. Значение «д» - поправка, необходимая для того, чтобы для преодоления порога, сигнал поступал по всем входам.
Модель нейрона-дизъюнктора выполняется при низком значении порога, но при высоком значении весов. Это условие обеспечивает получение выходного значения при хотя бы одном входном сигнале, но в таком случае необходимо дополнительное условие, ограничивающее выходное значение, то есть Vi 1. Во время процесса обучения дизъюнктора, предполагается получение точных входных и выходных данных, а следовательно логическая функция «ИЛИ» превращается в «исключающее ИЛИ», поскольку в данном случае предполагается возбуждение всего на одном входе.
Главным отличием логических нейронных сетей от сетей других видов является то, что не существует одного шаблона для реализации всего класса логических нейронных сетей. Каждая такая сеть строится под задачу, путём объединения в сети конъюнкторов и дизъюнкторов. Только путём анализа конкретной задачи может быть создана логическая нейронная сеть. Таким образом целью данной работы будет разработка конструктора, позволяющего создать логическую нейронную сеть.
Проанализировав входное множество, необходимо выделить все используемые переменные, подаваемые на вход, после чего надо построить структуру, а затем обучить её. Первая часть обучения происходит методом трассировки, когда по предъявляемому сети эталону выстраивается путь от входных значений к выходному. При предъявлении нескольких эталонов нейронная сеть строит пути последовательно, выбирая ещё не задействованные нейроны и вводя необходимые связи. Данный алгоритм повторяется до тех пор, пока не будет достигнута полная определённость для всех входных эталонов, предъявляемых сети. Для алгоритма трассировки нейронной сети используется понятие матрицы следования - матрицы, в которой строки и столбцы - нейроны, а значения, стоящие на их пересечении отвечают за наличие или отсутствие связи. Алгоритм позволяет выстроить связи, цепочки следования из входного слоя к выходному через скрытые слои. Таким образом, мы получаем готовую структуру логической нейронной сети. Следующим шагом обучения является приведение нейронной сети после трассировки, то есть коррекция весов и порогов для достижения необходимых результатов. Также, для получения более точных результатов, можно использовать коэффициент приведения, который будет рассчитываться для каждого нейрона. Коэффициент «K» будет вычисляться по следующей формуле:
нейронный сеть логический параллельный алгоритм
где в качестве значения Uj будет выбрано, например, максимальное значение возбуждения нейрона, или некоторая удовлетворяющая задаче оценка.
В итоге, полученная логическая нейронная сеть способна на основе формализованных входных данных, выдать значение путём логических операций. Таким образом, логическая нейронная сеть, по сути, является автоматизированной системой логического вывода. Сферой применения таких сетей являются системы управления, банковская сфера, различные системы анализа, а также система автоматического доказательства теорем, основывающаяся на методе логического вывода.
Математическая логика, как наука, содержит в себе множество подразделов. Один из таких подразделов, называемый теорией доказательств, рассматривает возможность представления доказательств, как формальных математических объектов, путём их анализа математическими методами. Теория доказательств является синтаксическим методом, и получила своё развитие благодаря работам многих учёных, таких как Г. Фреге, Дж. Пеано. Однако считается, что более современная теория доказательств начинается с работ Д. Гильберта, К. Геделя и Яна Лукашевича. В итоге теория доказательств была сведена к методам дедукции и естественного вывода. Так в 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».
Основным недостатком метода резолюции является порождение большого количества новых резольвент, которые зачастую оказываются лишними, не приводящими к искомому результату.
Несмотря на универсальность, значимость и применимость метода резолюции, сформулированного Робинсоном, он был недостаточно эффективен в плане временных затрат. Полный перебор всего множества дизъюнктов и порождаемых дополнительно резольвент, приводили к тому, что даже на максимально мощных ЭВМ того времени, выполнение алгоритма происходило слишком долго.
С конца 1970-х - начала 1980-х годов, идеология в сфере компьютерной индустрии устремилась в новое русло - создание мощного суперкомпьютера с функциями искусственного интеллекта. Данный проект получил наибольший приоритет в Японии, поскольку тогда была составлена правительственная программа, то есть данные разработки являлись стратегией развития технологий для всей страны. Поскольку суперкомпьютер должен был обладать искусственным разумом, в него необходимо было заложить основы работы с логикой, методики обработки данных и логического вывода.
Параллельная реализация логических нейронных сетей дипломная работа. Программирование, компьютеры и кибернетика.
История Компьютерных Игр Реферат
Сочинение На Тему Мой Брат 4 Класс
Реферат: Возвращение карельской пестрой норки
Реферат: Статус депутата парламента
О Вкусах Не Спорят Эссе
Сочинение Госпожа Простакова Хорошая Мать Или Нет
Обломов Сочинение Егэ По Литературе
Сочинение: Тема любви в романе И. А. Гончарова Обломов 2
Отчёт по практике: Oтчёт по практике на OAO «Татнефтепроводстрой». Скачать бесплатно и без регистрации
Эссе По Философии Софисты
Реферат: Перспективы развития международных корпораций в России. Скачать бесплатно и без регистрации
Майская Ночь Сочинение
Реферат: Венчание на царство
Курсовая работа: Воображение и креативная функция мышления
Реферат по теме Роль цитат в романе Жозе Сарамаго 'Год смерти Рикарду Рейша'.
Курсовая работа: Взаимодействие органов ФСБ и МВД
Итоговая Контрольная Работа По Алгебре 7 Класс
Сочинение На Тему Зима В Лесу
Реферат: My Last Duchess Essay Research Paper My
Дипломная работа по теме Фабрика в составе двух бумагоделательных машин производительностью 300 т/сут газетной бумаги марки В ГОСТ 6445-74
Патология стекловидного тела - Медицина презентация
Февральская революция 1917 г. Свержение самодержавной власти - История и исторические личности реферат
Методы измерения эффективности ведомственной медиаорганизации - Журналистика, издательское дело и СМИ курсовая работа