Реферат Бакалаврская работа, 34 с., 17 рис., 6 табл., 15 ист., 1 прил



Скачать 12.52 Mb.
страница1/3
Дата03.05.2016
Размер12.52 Mb.
ТипРеферат
  1   2   3
МИНОБРНАУКИ РОССИИ

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Факультет информатики

Кафедра теоретических основ информатики (ТОИ)


УДК 004.89

ДОПУСТИТЬ К ЗАЩИТЕ В ГАК

Зав. каф. ТОИ

к.т.н., доцент

___________ А. Л. Фукс

«_____»__________2013 г.


БАКАЛАВРСКАЯ РАБОТА
ОПТИМИЗАЦИЯ ТОПОЛОГИИ НЕЙРОННОЙ СЕТИ, ИСПОЛЬЗУЕМОЙ ДЛЯ ПРЕДСКАЗАНИЯ ОЦЕНКИ ФИЛЬМА ПОЛЬЗОВАТЕЛЕМ, С ПРИМЕНЕНИЕМ ГЕНЕТИЧЕСКОГО ПРОГРАММИРОВАНИЯ
по основной образовательной программе подготовки бакалавров

010400 – Информационные технологии


Криммель Герман Константинович
Руководитель ВКР

ассистент

____________В. В. Разин

подпись

«_____»__________2013 г.


Автор работы

студент группы №________

_____________Г. К. Криммель

подпись
Электронная версия бакалаврской работы Администратор электронной помещена в электронную библиотеку. библиотеки факультета

_____________ Е.Н.Якунина

подпись
Томск 2013

Реферат

Бакалаврская работа, 34 с., 17 рис., 6 табл., 15 ист., 1 прил.

ГЕНЕТИЧЕСКИЙ АЛГОРИТМ, ПОПУЛЯЦИИ, МУТАЦИИ, СЕЛЕКЦИОННЫЙ ОТБОР, ГЕНЕТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ, НЕЙРОННЫЕ СЕТИ, ОПТИМИЗАЦИЯ, АНАЛИЗ ДАННЫХ, ПРОГНОЗИРОВАНИЕ, РЕКОМЕНДАТЕЛЬНАЯ СИСТЕМА, ДИНАМИЧЕСКАЯ ТОПОЛОГИЯ, ИСКУСТВЕННЫЙ ИНТЕЛЛЕКТ

Объект исследования – нейронные сети и генетические алгоритмы.

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

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

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

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



Содержание
Введение 4

1 Постановка задачи 6

2 Обзор литературы 8

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

2.1 Генетические алгоритмы 12

2.2 Нейроэволюционные алгоритмы 13

2.2.1 Достоинства и недостатки нейроэволюционных алгоритмов 13

2.2.2 Особенности применения генетического

программирования для построения нейронных сетей 14

2.2.3 Обзор существующих алгоритмов 19

3 Программная реализация 21

4 Результаты экспериментов 26

Заключение 29

Список использованной литературы 31

Приложение 1 Руководство программиста 33

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

Причинами этого успеха стали следующие особенности нейронных сетей:



  • Широкий спектр решаемых задач;

  • Простота применения для конкретных задач.

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

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

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

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

Для достижения поставленной цели в работе поставлены следующие задачи:


  1. Провести обзор существующих решений;

  2. Подобрать параметры реализации генетического алгоритма;

  3. Спроектировать систему предсказания оценки фильма пользователем, на основе нейронной сети;

  4. Реализовать систему оптимизировать спроектировать систему с применением концепции генетического программирования.

Объектом исследования являются генетические алгоритмы и нейронные сети.

Предмет изучения – генетические алгоритмы используемые для оптимизации нейронной сети.

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

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


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

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

Более формально эту проблему можно выразить следующим образом:

, где U - набор пользователей, I - набор существующих объектов, r - некоторая функция, которая представляет полезность объекта i для пользователя, а V - вполне упорядоченное множество.

Таким образом для системы рекомендаций данная задача состоит в поиске для каждого i*:

, где


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

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

Для реализации задачи были выделены следующие подзадачи:


  • Проектирование нейронной сети для анализа оценок пользователей и прогнозирования их предпочтений

  • Генерация нейронной сети и оптимизация её топологии при помощи генетического алгоритма

  • Реализация подсчета и демонстрации метрик для анализа точности и эффективности работы системы предсказаний рейтингов

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

Методы генетического программирования для получения нейронных сетей были выбраны по следующим соображениям:

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

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

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

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

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

2 Обзор литературы

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

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

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

Человеку и высшим животным буквально на каждом шагу приходится распознавать, принимать решения и обучаться. Без этого невозможно было бы успешное существование в постоянно изменяющейся среде, а значит и выживание конкретного организма в частности и вида в общем случае. Таким образом можно сказать, что в ходе эволюционного процесса природа создала пусть и не идеальный, но крайне успешный механизм, способный находить пути достижения вышеупомянутых целей. Нейросетевой подход возник из стремления понять, каким образом естественные нейронные системы решают столь сложные задачи, и реализовать эти принципы в искусственных устройствах, предназначенных для решения практических задач[5]. В настоящее время искусственные нейронные сети зачастую являются лишь крайне упрощёнными моделями естественных нейронных сетей. Нервные системы животных и тем более человека гораздо сложнее тех устройств, которые могут быть созданы либо исследованы с помощью современных технологий[6]. Однако для успешного решения многих практических задач оказалось вполне достаточно «подсмотреть» лишь общие принципы функционирования нервной системы, а так же эмулировать отдельные их свойства и характеристики.

Рассмотрим в общих чертах устройство и принципы работы нервной клетки естественного нейрона. Клетка имеет множество разветвлённых отростков, называемых дендритами, и одно длинное тонкое волокно — аксон, на конце которого находятся синапсы, примыкающие к дендритам других нервных клеток. Каждый нейрон может находиться в одном из двух состояний: обычном и возбуждённом. В обычном состоянии нейрон слушает своих соседей – ожидает импульсы, которые достигая определённого порога переводят его в возбуждённое состояние. В возбуждённом состоянии клетка сама генерирует электрический импульс, который проходит по аксону до синапсов. Синапс при приходе импульса выделяет вещество, способствующее проникновению положительных зарядов внутрь соседней клетки. Синапсы имеют разную способность концентрировать это вещество. Поскольку каждый нейрон связан с большим количеством других нервных клеток, то та структура, которую они образуют, способна крайне эффективно распараллеливать ход нахождения решения задачи, что позволяет, к примеру, человеческому мозгу решать сложные задачи распознавания за считаные доли секунды. Кроме того, это обеспечивает высокую степень взаимозаменяемости нервных клеток и, как следствие, надежность нервной системы в целом[5].

Для моделирования работы естественного нейрона может быть использована следующая модель:





Рис. 2.1.1.1 Математическая модель искусственного нейрона

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

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



Рис. 2.1.1.2 Нейронная сеть с прямым распространением сигнала

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

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



Рис. 2.1.1.3 Двухслойная нейронная сеть

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

Самые же распространённые на данный момент искусственные нейронные сети – однослойные. В них есть лишь один внутренний слой, что не позволяет им решать некоторые сложные задачи, однако для большинства задач их возможностей вполне хватает. Поэтому в данной работе в качестве начального приближения (представителей начальной популяции) используются именно нейронные сети с однослойной топологией. Что, однако, не исключает того, что в результате эволюционного процесса могут быть получены многослойные нейронные сети.

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

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

Обучение – это процесс, в котором свободные параметры нейронной сети настраиваются посредством моделирования среды, в которую эта сеть встроена. Тип обучения определяется способом подстройки этих параметров[7].

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


  1. В нейронную сеть поступают стимулы из внешней среды.

  2. В результате первого пункта изменяются свободные параметры нейронной сети.

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

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

Существуют два концептуальных подхода к обучению нейронных сетей:

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

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


2.2 Генетические алгоритмы

Основателем современной теории генетических алгоритмов считается Джон Холланд (J. Holland), чья работа «Adaptation in Natural and Artificial Systems», стала классикой в этой области. Именно в ней Холланд впервые ввел термин «генетический алгоритм» [9]. Сейчас описанный в данной работе алгоритм принято называть «классическим генетическим алгоритмом», а само же понятие «генетического алгоритма» стало крайне широким.

Генетические алгоритмы работают по аналогии с системами существующими в живой природе. Они оперируют с совокупностью «особей» (называемой популяцией), представляющих собой закодированные решения задачи, подобно тому, как генетический код кодирует фенотипические свойства организмов. Приспособленность особи оценивается с помощью специальной функции, называемой фитнес-функцией[1]. Наиболее приспособленные получают шанс скрещиваться и давать потомство. Таким образом, приспособленность нового поколения в среднем выше предыдущего[14].

Главным отличием генетического программирования от генетических алгоритмов является в то, что каждая особь в популяции теперь кодирует не числовые характеристики, которые обеспечивают задаче оптимальность, а некоторую "программу", которая решает поставленную проблему. Под словом "программа" здесь понимается не реальная программа на каком-либо конкретном языке программирования. Чаще всего, такая программа - это конфигурация дерева функции, нейронной сети, автомата или же правила их построения[3].

Алгоритм работает по всем законам генетических алгоритмов, лишь при оценке новой особи происходит "исполнение" программы, а затем оценка её деятельности. Например, в задаче оптимизации нейронных сетей хромосома кодирует некоторую сложную структуру, поскольку нейронная сеть может содержать множество нейронов и связей. Уменьшая отклонение от целевого значения, алгоритм находит оптимальную топологию искусственной нейронной сети, для данного набора значений. Стоит отметить, что идея использования генетического программирования не является новой [13], однако чаще всего в литературе встречаются лишь теоритические предположения.

На данный момент самыми распространёнными и перспективными направлениями в применении генетического программирования являются:



  • Деревья поколений.

  • Нейронные сети.

  • Автоматы

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

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


2.3 Нейроэволюционные алгоритмы

2.3.1 Достоинства и недостатки генетического программирования

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



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

  2. Генетические алгоритмы плохо масштабируемы под сложность решаемой проблемы.

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

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

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

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

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



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

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

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

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

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

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

Каталог: sites -> default -> files
files -> Рабочая программа дисциплины Лечебная физическая культура и массаж Направление подготовки 050100 Педагогическое образование
files -> Хроническая сердечная недостаточность и депрессия у лиц пожилого возраста
files -> Ирвин Ялом Лечение от любви и другие психотерапевтические новеллы
files -> Оценка элементного статуса в определении нутриентной обеспеченности организма. Значение нарушений элементного статуса при различной патологии
files -> Проблема безопасности продуктов питания
files -> Примерная программа профессионального модуля
files -> Бета-адреноблокаторы в терапии артериальной гипертензии// Лечащий врач. 2015. № С. 12-14
files -> Тамбовское областное государственное бюджетное учреждение «научная медицинская библиотека»


Поделитесь с Вашими друзьями:
  1   2   3


База данных защищена авторским правом ©zodorov.ru 2017
обратиться к администрации

    Главная страница