Проектная работа на тему "Графы и нейронные сети"
Вложение | Размер |
---|---|
markova.docx | 56.44 КБ |
markova_mariya.ppt | 1.67 МБ |
Полное название темы работы | Графы и нейронные сети |
Тип работы | исследовательский реферат |
Фамилия имя автора | Маркова Мария |
Класс | 10Б |
Научный руководитель | Санина Марина Сергеевна, учитель |
Аннотация
Маркова Мария
г. Москва, ГБОУ школа №1362, 10 Б
«Графы и нейронные сети»
Научный руководитель: Санина Марина Сергеевна, учитель информатики.
Объект исследования — нейронная сеть.
Предмет исследования – нейропакеты.
Методы проведенных исследований: поисковый метод, теоретическое обобщение, сравнение, анализ.
В связи с вышесказанным была поставлена цель: изучить нейропакеты, имитирующие работу нейронной сети. Для достижения цели были поставлены следующие задачи:
Основным результатом научного исследования является выделение достоинств и недостатков нейропакетов.
Введение
Искусственные нейронные сети прочно вошли в нашу жизнь и в настоящее время широко используются при решении самых разных задач и активно применяются там, где обычные алгоритмические решения оказываются неэффективными или вовсе невозможными. В числе задач, решение которых доверяют искусственным нейронным сетям, можно назвать следующие: распознавание текстов, игра на бирже, контекстная реклама в Интернете, фильтрация спама, проверка проведения подозрительных операций по банковским картам, системы безопасности и видеонаблюдения — и это далеко не все.
Искусственные нейронные сети, подобно биологическим, являются вычислительной системой с огромным числом параллельно функционирующих простых процессоров с множеством связей. Несмотря на то, что при построении таких сетей обычно делается ряд допущений и значительных упрощений, отличающих их от биологических аналогов, искусственные нейронные сети демонстрируют удивительное число свойств, присущих мозгу, — это обучение на основе опыта, обобщение, извлечение существенных данных из избыточной информации.
Нейронные сети могут менять свое поведение в зависимости от состояния окружающей их среды. После анализа входных сигналов (возможно, вместе с требуемыми выходными сигналами) они самонастраиваются и обучаются, чтобы обеспечить правильную реакцию. Обученная сеть может быть устойчивой к некоторым отклонениям входных данных, что позволяет ей правильно «видеть» образ, содержащий различные помехи и искажения.
Основные понятия теории графов
Граф это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. Вершины, прилегающие к одному и тому же ребру, называются смежными.
Если ребра ориентированны, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом.
Если ребра не имеют ориентации, граф называется неориентированным.
Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра - линиями, соединяющими точки.
Графы, в которых не построены все возможные ребра, называются неполными графами, а тот граф, в котором соединены все вершины всеми возможными способами, называется полным графом. Часто связи между объектами характеризуются вполне определенной ориентацией. Например, на некоторых улицах допускается только одностороннее автомобильное движение, отношения между людьми могут определяться подчиненностью или старшинством. Ориентированные связи характеризуют переход системы из одного состояния в другое, результаты встреч между командами в спортивных состязаниях, отношения между числами (неравенство, делимость). Для указания направления связи между вершинами графа соответствующее ребро отмечается стрелкой. Ориентированное таким образом ребро называют дугой, а граф с ориентированными ребрами – ориентированным графом.
Описание связей между объектами с помощью графов состоит в приписывании ребрам некоторых количественных значений, качественных признаков или характерных свойств, называемых весами. В простейших случаях это может быть порядковая нумерация ребер, указывающая на очередность их рассмотрения (приоритет или иерархия). Вес ребра может означать длину (пути сообщения), пропускную способность (линии связи), напряжение или ток (электрические цепи), количество набранных очков (турниры), валентность связей (химические формулы), количество рядов движения (автомобильные дороги), цвет проводника (монтажные схемы электронного устройства), характер отношения между людьми (сын, отец, подчиненный, учитель) и т. п.
Вес можно приписывать не только ребрам, но и вершинам. Например, вершины, соответствующие населенным пунктам, могут характеризоваться количеством мест в гостиницах, пропускной способностью станций техобслуживания. Вообще, вес вершины означает любую характеристику соответствующего ей объекта – атомный вес элемента в структурной формуле, цвет изображаемого вершиной предмета, возраст человека и т. п.
Определение. Графы, вершинам и (или) ребрам которых приписаны некоторые веса, называют взвешенными графами. Графы, вершины которых пронумерованы, еще называют помеченными графами.
Особое значение для моделирования физических систем приобрели взвешенные ориентированные графы, называемые графами потоков сигналов или сигнальными графами. Вершины сигнального графа отождествляются с некоторыми переменными, описывающими состояние системы, а вес каждой вершины означает функцию времени или некоторой величины, характеризующую соответствующую переменную (сигнал вершины). Дуги отображают связи между переменными, и вес каждой дуги представляет собой численное или функциональное отношение, задающее передачу сигнала от одной вершины к другой (передача дуги). Сигнальные графы находят широкое применение в теории цепей и систем, а также во многих других областях науки и техники.
Нейронные сети
Идея нейронных сетей родилась в рамках теории искусственного интеллекта, в результате попыток имитировать способность биологических нервных систем обучаться и исправлять ошибки.
Нейронные сети (Neural Networks) - это модели биологических нейронных сетей мозга, в которых нейроны имитируются относительно простыми, часто однотипными, элементами (искусственными нейронами).
Нейронная сеть может быть представлена направленным графом с взвешенными связями, в котором искусственные нейроны являются вершинами, а синаптические связи - дугами.
Нейронные сети широко используются для решения разнообразных задач.
Среди областей применения нейронных сетей - автоматизация процессов распознавания образов, прогнозирование, адаптивное управление, создание экспертных систем, организация ассоциативной памяти, обработка аналоговых и цифровых сигналов, синтез и идентификация электронных цепей и систем.
С помощью нейронных сетей можно, например, предсказывать объемы продаж изделий, показатели биржевого рынка, выполнять распознавание сигналов, конструировать самообучающиеся системы.
Модели нейронных сетей могут быть программного и аппаратного исполнения. Мы будем рассматривать сети первого типа.
Если говорить простым языком, слоистая нейронная сеть представляет собой совокупность нейронов, которые составляют слои. В каждом слое нейроны между собой никак не связаны, но связаны с нейронами предыдущего и следующего слоев. Информация поступает с первого на второй слой, со второго - на третий и т.д.
Среди задач Data Mining( интеллектуальный анализ данных) , решаемых с помощью нейронных сетей, будем рассматривать такие:
Классификация (обучение с учителем). Примеры задач классификации: распознавание текста, распознавание речи, идентификация личности.
Прогнозирование. Для нейронной сети задача прогнозирования может быть поставлена таким образом: найти наилучшее приближение функции, заданной конечным набором входных значений (обучающих примеров). Например, нейронные сети позволяют решать задачу восстановления пропущенных значений.
Кластеризация (обучение без учителя). Примером задачи кластеризации может быть задача сжатия информации путем уменьшения размерности данных. Задачи кластеризации решаются, например, самоорганизующимися картами Кохонена.
Рассмотрим три примера задач, для решения которых возможно применение нейронных сетей.
Медицинская диагностика. В ходе наблюдения за различными показателями состояния пациентов накоплена база данных. Риск наступления осложнений может соответствовать сложной нелинейной комбинации наблюдаемых переменных, которая обнаруживается с помощью нейросетевого моделирования.
Прогнозирование показателей деятельности фирмы (объемы продаж). На основе ретроспективной информации о деятельности организации возможно определение объемов продаж на будущие периоды.
Предоставление кредита. Используя базу данных о клиентах банка, применяя нейронные сети, можно установить группу клиентов, которые относятся к группе потенциальных "неплательщиков".
Элементы нейронных сетей
Искусственный нейрон (формальный нейрон) - элемент искусственных нейронных сетей, моделирующий некоторые функции биологического нейрона.
Главная функция искусственного нейрона - формировать выходной сигнал в зависимости от сигналов, поступающих на его входы.
В самой распространенной конфигурации входные сигналы обрабатываются адаптивным сумматором, затем выходной сигнал сумматора поступает в нелинейный преобразователь, где преобразуется функцией активации, и результат подается на выход (в точку ветвления).
Общий вид искусственного нейрона.
Нейрон характеризуется текущим состоянием и обладает группой синапсов - однонаправленных входных связей, соединенных с выходами других нейронов.
Нейрон имеет аксон - выходную связь данного нейрона, с которой сигнал (возбуждения или торможения) поступает на синапсы следующих нейронов.
Каждый синапс характеризуется величиной синаптической связи (ее весом wi).
Текущее состояние нейрона определяется как взвешенная сумма его входов:
Выход нейрона есть функция его состояния: y = f(s).
Активационная функция, которую также называют характеристической функцией, - это нелинейная функция, вычисляющая выходной сигнал формального нейрона.
Часто используемые активационные функции:
Выбор активационной функции определяется спецификой поставленной задачи либо ограничениями, накладываемыми некоторыми алгоритмами обучения.
Нелинейный преобразователь - это элемент искусственного нейрона, преобразующий текущее состояние нейрона (выходной сигнал адаптивного сумматора) в выходной сигнал нейрона по некоторому нелинейному закону (активационной функции).
Точка ветвления (выход) - это элемент формального нейрона, посылающий его выходной сигнал по нескольким адресам и имеющий один вход и несколько выходов.
На вход точки ветвления обычно подается выходной сигнал нелинейного преобразователя, который затем посылается на входы других нейронов.
Архитектура нейронных сетей
Нейронные сети могут быть синхронные и асинхронные.
В синхронных нейронных сетях в каждый момент времени свое состояние меняет лишь один нейрон. В асинхронных - состояние меняется сразу у целой группы нейронов, как правило, у всего слоя. Можно выделить две базовые архитектуры - слоистые и полносвязные сети. Ключевым в слоистых сетях является понятие слоя.
Слой - один или несколько нейронов, на входы которых подается один и тот же общий сигнал. Слоистые нейронные сети - нейронные сети, в которых нейроны разбиты на отдельные группы (слои) так, что обработка информации осуществляется послойно.
В слоистых сетях нейроны i-го слоя получают входные сигналы, преобразуют их и через точки ветвления передают нейронам (i+1) слоя. И так до k-го слоя, который выдает выходные сигналы для интерпретатора и пользователя. Число нейронов в каждом слое не связано с количеством нейронов в других слоях, может быть произвольным.
В рамках одного слоя данные обрабатываются параллельно, а в масштабах всей сети обработка ведется последовательно - от слоя к слою. К слоистым нейронным сетям относятся, например, многослойные персептроны, сети радиальных базисных функций, когнитрон, некогнитрон, сети ассоциативной памяти.
Однако сигнал не всегда подается на все нейроны слоя. В когнитроне, например, каждый нейрон текущего слоя получает сигналы только от близких ему нейронов предыдущего слоя. Слоистые сети, в свою очередь, могут быть однослойными и многослойными [46].
Однослойная сеть - сеть, состоящая из одного слоя.
Многослойная сеть - сеть, имеющая несколько слоев. В многослойной сети первый слой называется входным, последующие - внутренними или скрытыми, последний слой - выходным. Таким образом, промежуточные слои - это все слои в многослойной нейронной сети, кроме входного и выходного.
Входной слой сети реализует связь с входными данными, выходной - с выходными.
Таким образом, нейроны могут быть входными, выходными и скрытыми.
Входной слой организован из входных нейронов (input neuron), которые получают данные и распространяют их на входы нейронов скрытого слоя сети.
Скрытый нейрон (hidden neuron) - это нейрон, находящийся в скрытом слое нейронной сети.
Выходные нейроны (output neuron), из которых организован выходной слой сети, выдает результаты работы нейронной сети.
В полносвязных сетях каждый нейрон передает свой выходной сигнал остальным нейронам, включая самого себя. Выходными сигналами сети могут быть все или некоторые выходные сигналы нейронов после нескольких тактов функционирования сети. Все входные сигналы подаются всем нейронам.
Обучение нейронных сетей
Перед использованием нейронной сети ее необходимо обучить. Процесс обучения нейронной сети заключается в подстройке ее внутренних параметров под конкретную задачу. Алгоритм работы нейронной сети является итеративным, его шаги называют эпохами или циклами. Эпоха - одна итерация в процессе обучения, включающая предъявление всех примеров из обучающего множества и, возможно, проверку качества обучения на контрольном множестве. Процесс обучения осуществляется на обучающей выборке. Обучающая выборка включает входные значения и соответствующие им выходные значения набора данных. В ходе обучения нейронная сеть находит некие зависимости выходных полей от входных.
Таким образом, перед нами ставится вопрос - какие входные поля (признаки) нам необходимо использовать. Первоначально выбор осуществляется эвристически, далее количество входов может быть изменено. Сложность может вызвать вопрос о количестве наблюдений в наборе данных. И хотя существуют некие правила, описывающие связь между необходимым количеством наблюдений и размером сети, их верность не доказана.
Количество необходимых наблюдений зависит от сложности решаемой задачи. При увеличении количества признаков количество наблюдений возрастает нелинейно, эта проблема носит название "проклятие размерности". При недостаточном количестве данных рекомендуется использовать линейную модель.
Аналитик должен определить количество слоев в сети и количество нейронов в каждом слое. Далее необходимо назначить такие значения весов и смещений, которые смогут минимизировать ошибку решения. Веса и смещения автоматически настраиваются таким образом, чтобы минимизировать разность между желаемым и полученным на выходе сигналами, которая называется ошибка обучения.
Ошибка обучения для построенной нейронной сети вычисляется путем сравнения выходных и целевых (желаемых) значений. Из полученных разностей формируется функция ошибок. Функция ошибок - это целевая функция, требующая минимизации в процессе управляемого обучения нейронной сети. С помощью функции ошибок можно оценить качество работы нейронной сети во время обучения. Например, часто используется сумма квадратов ошибок.
От качества обучения нейронной сети зависит ее способность решать поставленные перед ней задачи.
Переобучение нейронной сети
При обучении нейронных сетей часто возникает серьезная трудность, называемая проблемой переобучения (overfitting).
Переобучение, или чрезмерно близкая подгонка - излишне точное соответствие нейронной сети конкретному набору обучающих примеров, при котором сеть теряет способность к обобщению. Переобучение возникает в случае слишком долгого обучения, недостаточного числа обучающих примеров или переусложненной структуры нейронной сети. Переобучение связано с тем, что выбор обучающего (тренировочного) множества является случайным. С первых шагов обучения происходит уменьшение ошибки. На последующих шагах с целью уменьшения ошибки (целевой функции) параметры подстраиваются под особенности обучающего множества. Однако при этом происходит "подстройка" не под общие закономерности ряда, а под особенности его части - обучающего подмножества. При этом точность прогноза уменьшается.
Один из вариантов борьбы с переобучением сети - деление обучающей выборки на два множества (обучающее и тестовое). На обучающем множестве происходит обучение нейронной сети. На тестовом множестве осуществляется проверка построенной модели. Эти множества не должны пересекаться. С каждым шагом параметры модели изменяются, однако постоянное уменьшение значения целевой функции происходит именно на обучающем множестве. При разбиении множества на два мы можем наблюдать изменение ошибки прогноза на тестовом множестве параллельно с наблюдениями над обучающим множеством. Какое-то количество шагов ошибки прогноза уменьшается на обоих множествах. Однако на определенном шаге ошибка на тестовом множестве начинает возрастать, при этом ошибка на обучающем множестве продолжает уменьшаться. Этот момент считается концом реального или настоящего обучения, с него и начинается переобучение.
На первом шаге ошибки прогноза для обучающего и тестового множества одинаковы. На последующих шагах значения обеих ошибок уменьшаются, однако с семидесятого шага ошибка на тестовом множестве начинает возрастать, т.е. начинается процесс переобучения сети. Прогноз на тестовом множестве является проверкой работоспособности построенной модели. Ошибка на тестовом множестве может являться ошибкой прогноза, если тестовое множество максимально приближено к текущему моменту.
Программное обеспечение для работы с нейронными сетями
Программное обеспечение, имитирующее работу нейронной сети, называют нейросимулятором либо нейропакетом. Большинство нейропакетов включают следующую последовательность действий:
Существует огромное разнообразие нейропакетов, возможность использования нейросетей включена также практически во все известные статистические пакеты.
Среди специализированных нейропакетов можно назвать такие: BrainMaker, NeuroOffice, NeuroPro, и др..
Критерии сравнения нейропакетов: простота применения, наглядность представляемой информации, возможность использовать различные структуры, скорость работы, наличие документации. Выбор определяется квалификацией и требованиями пользователя.
Сравнение нейропакетов
Нейропакет работает под Windows и крайне нетребователен к вычислительным ресурсам. Хотя программа декларируется как нейропакет, на самом деле она не создает нейронную сеть в обычном понимании и не использует известные алгоритмы обучения.
В нейропакет встроен мощный нейроконструктор, позволяющий создавать любые нейронные структуры.
NeuroSolutions фирмы NeuroDimension Inc. - нейропакет с широкими средствами визуализации, для конструирования НС с произвольной топологией и процедурами обучения. Универсальный нейропакет NeuroSolutions фирмы NeuroDimension Inc предназначен для моделирования широкого круга искусственных нейронных сетей. По оценкам специалистов он является лучшим нейросетевым пакетом. Основное достоинство описываемого нейропакета состоит в его гибкости: помимо традиционно используемых нейросетевых парадигм (типа полносвязных многослойных нейронных сетей или самоорганизующихся полей Кохонена) нейропакет включает в себя мощнейший редактор ви- зуального проектирования нейронной сети, позволяющий создавать практически любые собственные нейронные структуры. Нейропакет NeuroSolutions снабжен мощными и хорошо продуманными средствами визуализации: отображать в каком угодно виде и визуально контролировать можно все, начиная от структуры нейронной сети и кончая процессом и результатом обучения. Наличие мощных средств визуализации выводит данный нейропакет на уровень CAD-систем (систем автоматизи- рованного проектирования), т.е. NeuroSolutions можно считать системой проектирования и моделирования нейронной сети. Помимо грамотно орга- низованных средств взаимодействия с операционной системой (поддерживается OLE2) нейропакет снабжен также генератором исходного кода и средствами, позволяющими использовать внешние модули при проектиро- вании и обучении нейронной сети. Серебренников А. Л. Сравнительный анализ нейросетевых пакетов 195 Нейропакет NeuroSolutions имеет также достаточно мощные средства для организации обучающих выборок. Встроенные конверторы данных поддерживают графические изображения в формате BMP, обычные текстовые файлы с числовыми или символьными данными, а также функции не- прерывного аргумента (например, времени), заданные в аналитическом виде или в виде выборки значений. Нейропакет позволяет использовать любые внешние конверторы данных, определяемые пользователем. Для тех, кто использует только традиционные нейронные парадигмы и не пользуется средствами собственного проектирования нейронной сети, нейро- пакет NeuroSolutions содержит генератор стандартных архитектур (Neural Wizard). С помощью этого генератора можно быстро задать архитектуру ней- ронной сети, подобрать обучающую выборку, критерии и методы обучения. Поддерживаются наиболее известные нейросетевые парадигмы: многослойные сети, сети Кохонена, самоорганизующиеся структуры и др. К недостаткам нейропакета NeuroSolutions можно отнести то, что в пакет включено недостаточное количество критериев обучения, если же требуется применять нестандартные критерии обучения, пользователь сталки- вается с тем, что ему необходимо создавать внешние модули с последую- щим подключением к пакету. В пакете реализовано мало методов обучения: алгоритм обратного распространения, сети Кохонена, самоорганизующиеся структуры. Это наиболее популярные методы, но их явно недостаточно. Для использования других методов обучения пользователю потребуется создать их самому. В итоге можно сделать вывод, что нейропакет NeuroSolutions имеет множество плюсов и некоторые недостатки и обладает гибкостью и универсальностью.
Этому пакету досталось тяжелое наследство предыдущих версий: командно-строковый интерфейс, украшенный «виндовым» обрамлением. Запомнить все функции и их параметры - все равно что выучить от корки до корки новый язык, правда, по мере терпеливого освоения «языка» его достоинства видишь все лучше.
Набор типов нейросетей стандартен. В версии 3.0 появилась возможность гибкого конструирования НС, а также были добавлены вероятностные и регрессионные нейросети. Несколько веселее с алгоритмами обучения: современный джентльменский набор и алгоритм обучения Levenberg-Marquardt собственной персоной. Предусмотрен демонстрационный режим, воспользовавшись которым, оценим работу пресловутой НС с обратными связями (Elman). Здесь нейросеть должна предсказать периодические прямоугольные импульсы. На первый взгляд задачка никчемная, но служит хорошей проверкой на работоспособность НС подобной архитектуры. Не меняя настроек, загружаю готовый матлабовский файл, и обучение начинается. За изменением ошибки можно наблюдать в отдельном окне прямо по ходу обучения. Согласно замыслу авторов демонстрашки, ошибка должна достичь величины 0,01. После предусмотренных пяти сотен повторов ошибка опустилась лишь до 1,00, начиная обучение заново, желаемого результата не последовало. Взамен программа предлагала попытаться продолжить обучение или добавить спрятанных нейронов. Настораживает заявление фирмы, что максимальное количество нейронов и весовых коэффициентов не ограничено, и это при 16 Мбайт минимально требуемой памяти, если верить описанию! Сколько на самом деле понадобится памяти, чтобы компьютер не впадал в прострацию, MathWorks скромно умалчивает. Но запавшим на матлабовские прелести и желающим не ограничиваться школьными задачками советую запастись памятью, ибо даже 128 Мбайт для этого симулятора - семечки.
Заключение
Итак, было выявлено, что самым оптимальным для решения задач является нейропакет QwikNet32, так как он и предназначен для работы в среде Windows и особых требований к вычислительным ресурсам не предъявляет. Нейропакет ориентирован на широкий круг задач - от создания прогностических приложений до организации систем распознавания образов и нейросетевой памяти. Следует отметить, что организация внутреннего представления нейросетевых моделей является прозрачной и легко доступной для программного наращивания. В целом пакет может быть легко интегрирован в программный комплекс целевого использования.
Литература:
Девчата
Сочные помидорки
Стеклянный Человечек
Почта
Цветущая сакура