Название работы	Кол-во страниц	Размер
Модификация ранцевой криптосистемы на основе искусственных нейронных...	1	30.2kb.
Перечень вопросов к экзамену	1	34.28kb.
Метод обучения персептрона	1	56.01kb.
С. Короткий. Нейронные сети: основные положения	1	119.79kb.
Автоматическая обработка естественного языка с помощью искусственных...	1	59.09kb.
Распараллеливание самоконфигурируемого алгоритма генетического программирования...	1	35.09kb.
«Обучение персептрона с использованием нормированной функции настройки»	1	212.45kb.
Астрофизика Начало в 15. 15 в конф зале гаиш предс проф. Постнов...	2	488.56kb.
Шифрование методом скремблеров	1	51.68kb.
Изучить блочные алгоритмы шифрования: алгоритм перестановки, алгоритм...	1	82.65kb.
Нейросетевое моделирование когнитивных функций мозга: обзор основных...	2	524.06kb.
Динамическое предсказание переходов с использованием расширенной...	1	145.11kb.
Викторина для любознательных: «Занимательная биология»	1	9.92kb.

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

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

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

Нейронные сети в биологической перспективе

Нейронные сети (Neural network) представляют собой упрощенную модель че­ловеческого мозга. Мозг состоит из нейронов, которые являются индивидуальны­ми процессорами. Нейроны соединяются друг с другом с помощью нервных окон­чаний двух типов: синапсов, через которые в ядро поступают сигналы, и аксонов, через которые нейрон передает сигнал далее. Человеческий мозг состоит пример­но из 10^й нейронов. Каждый нейрон связан примерно с 1000 других нейронов (это не относится к коре головного мозга, где плотность нейронных связей намного выше). Структура мозга высокоциклична, но ее можно рассматривать и как мно­гослойную (рис. 5.1). В очень упрощенном виде работу мозга можно представить так: внешний слой сети передает импульсы от сенсоров из внешней среды, сред­ний слой (или кора головного мозга) обрабатывает импульсы, а «выходной» слой выдает результат (действие) обратно во внешнюю среду.

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

Однослойные перцептроны
Однослойный перцептпрон (Single layer perceptron - SLP) представляет собой концептуальную модель, которая состоит из одного процессора. Каждое соедине­ние от входа к ядру включает коэффициент, который показывает фактор веса, и обозначается с помощью веса который определяет влияние ячейки u_i на дру­гую ячейку. Положительные веса показывают усиление, а отрицательные - за­прещение. Совместно с входами в ячейку они определяют поведение сети. Схема однослойного перцептрона представлена на рис. 5.2.

Ячейка на рис. 5.2 включает три входа (и₍, и₂ и и₃). Кроме этого, есть вход сме­щения (w_Q), о котором будет рассказано позже. Каждое входное соединение имеет вес (wj, w₂ и w₃). Наконец, существует единый выход, О. Состояние нейрона обо­значено как у и определяется уравнением 5.1.

(5.1)



Рис. 5.2. Однослойный перцептрон
Выражение, показанное в уравнении 5.1, является функцией, которая сумми-рует сигналы на всех входах с учетом веса, а затем добавляет смещение. Затем ре-зультат передается в активационную функцию, которая может быть определена так,как показано в уравнении 5.2 (в данном случае функция является пороговой).

(5.2)
Если значение состояния больше нуля, то выходное значение будет равно 1. Иначе оно составит -1.
Моделирование булевых выражений с помощью SLP
Хотя однослойный перцептрон является очень простой моделью, ее возмож­ности весьма велики. Например, можно легко сконструировать базовые логичес­кие функции, как показано на рис. 5.3.

Ключ И Ключ ИЛИ Ключ НЕ

Рис. 5.3. Логические функции, построенные с помощью однослойных перцептронов
Вспомните, что функция И имеет значение 1, если оба входа равны 1, в про­тивном случае функция возвращает значение 0. Поэтому если заданы оба входа I (вектор и = (1,1)), то, используя активационную функцию из уравнения 5.2 в ка­честве порога, получим следующий результат:

Как показывают оба примера, модель простого перцептрона правильно реали­зует логическую функцию И (а также функции ИЛИ и НЕ). Однако однослойный

перцептрон не может смоделировать такую логическую функцию, как исключаю­щее ИЛИ (XOR). Эта неспособность к моделированию функции XOR известна как проблема отделимости. Из-за нее Марвин Мински и Сеймур Паперт в 1960-е гг. уничтожили результаты своих разработок в области связей и стали заниматься стандартными подходами к изучению ИИ.

Проблема отделимости была легко решена путем добавления одного или не­скольких слоев между входами и выходами нейронной сети (см. рис. 5.4). Это при­вело к созданию модели, известной как многослойные перцептроны (Multiple layer perceptron - MLP).

Многослойные сети

Многослойные сети позволяют создавать более сложные, нелинейные связи между входными данными и результатами на выходе. На рис. 5.4 многослойная сеть состоит из входного, промежуточного (или скрытого) и выходного слоев. Входной слой представляет входы в сеть и не состоит из ячеек (нейронов) в тра­диционном смысле слова. В этом примере для каждой ячейки задан идентифика­тор u_n. Две входные ячейки называются (u₁, u₂), две скрытые ячейки (u₃, u₄), а вы­ходная ячейка - (u₅). Обозначение соединений в сети стандартизовано в форме w₁₃ и отображает связь с учетом веса между и₃ и и_г

Рис. 5.4. Многослойные перцептроны

В то время как входные ячейки (u, и u₂) просто задают входное значение для сети, скрытые и выходные ячейки представляют собой функцию (уравнение 5.1). Результат суммирования дополнительно обрабатывается функцией сжатия (обычно сигмоид), результат которой выдается на выходе из ячейки. Функция сигмоида показана на рис. 5.5.

Теперь изучим полную картину ячейки в нейронной сети. На рис. 5.6 изобра­жена выходная ячейка для сети, показанной на рис. 5.4. Выходная ячейка u₅ полу­чает результат от двух скрытых ячеек (u₃и u₄) через веса w₅₃ и w₅₄ соответственно.

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

Функция сжатия (сигмоид)



Рис. 5.5. Функция сигмоида, использующаяся для активации



Рис. 5.6. Скрытый и выходной слои в нейронной сети

проиллюстрировать только обработку выходного слоя. Уравнение на рис. 5.6 показывает сумму результатов входов скрытого слоя с весами соединений. Функция f(x) представляет сигмоид, примененный к результату.

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

Обучение с помощью алгоритма обратного распространения

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

Алгоритм обратного распространения

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

1. Берется пример входного сигнала Е с соответствующим правильным значе­нием выхода С.

2. Рассчитывается прямое распространение Е через сеть (определяются весо­вые суммы S₍ и активаторы и. для каждой ячейки).

3. Начиная с выходов, выполняется обратное движение через ячейки выход­ного и промежуточного слоя, при этом программа рассчитывает значения ошибок (уравнения 5.3 и 5.4):

(5.3)

(5.4)


(Обратите внимание, что m обозначает все ячейки, связанные со скрытым узлом, w - заданный вектор веса, а и - активация). 4. Наконец, веса в сети обновляются следующим образом (уравнение 5.5 и 5.6):
(5.5)
(5.6)
Здесь р представляет коэффициент обучения (или размер шага). Это неболь­шое значение ограничивает изменение, которое может произойти при каждом шаге.

Совет

Параметр р можно определить таким образом, чтобы он указы­вал скорость продвижения алгоритма обратного распространения к решению. Лучше начать тестирование с небольшого значения (0,1) и затем постепенно его повышать.

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

Рассмотрим пример функционирования сети в процессе обучения.

Пример алгоритма обратного распространения

Изучим работу алгоритма обратного распространения, взяв в качестве приме­ра сеть, показанную на рис. 5.7.

Рис. 5.7. Пример алгоритма обратного распространения
Развитие вперед

Сначала выполняется расчет движения входного сигнала по сети. Рассмотрим значения для скрытого слоя:

Вспомните, что f(x) является активационной функцией, то есть функцией сиг-моида (уравнение 5.7):

(5.7)

Теперь сигнал дошел до скрытого слоя. Конечный шаг заключается в том, что­бы переместить сигнал из скрытого слоя в выходной слой и рассчитать значения на выходе из сети:

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

Для коррекции весовых коэффициентов в сети обычно используется средне­квадратичная ошибка. Для одного узла ошибка определяется в уравнении 5.8:

(5.8)

Поэтому ошибка составляет:

Алгоритм обратного распространения для ошибки

Теперь применим обратное распространение, начиная с определения ошибки в выходном и скрытых узлах. Используя уравнение 5.1, рассчитаем ошибку в вы­ходном узле:

Теперь следует рассчитать ошибку для двух скрытых узлов. Для этого исполь­зуется производная функция сигмоида (уравнение 5.5), которая показана в виде уравнения 5.9:

(5.9)

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

Изменения весов соединений

Теперь, когда рассчитаны значения ошибок для выходного и скрытого слоев, можно с помощью уравнений 5.3 и 5.4 изменить веса. Используем коэффициент обучения (р), равный 0,5. Сначала следует обновить веса для соединений между выходным и скрытым слоями:

Теперь нужно обновить смещение для выходной ячейки:

Для w_5.4 вес уменьшен, а для w_5.3 - увеличен. Смещение было обновлено для повышения возбуждения. Теперь нужно показать изменение весов для скрытого слоя (для входа к скрытым ячейкам):

Последний шаг - это обновление смещений для ячеек:

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

Вспомните, что начальная ошибка была равна 0,023895. Текущая ошибка со­ставляет 0,022, а это значит, что одна итерация алгоритма обратного распростра­нения позволила уменьшить среднюю ошибку на 0,001895.

Расчет поведения ИИ для компьютерных игр

Алгоритм обратного распространения применяется при создании нейроконтрол-леров для персонажей компьютерных игр. Нейроконтроллерами (Neurocontroller) обычно называются нейронные сети, которые используются при управлении. В этом приложении мы задействуем нейронную сеть, чтобы выбрать действие из доступного списка на основании того, в какой окружающей среде находится персонаж. Термины «персонаж» и «агент» далее употребляются как синонимы.

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

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

Как показано на рис. 5.8, окружающая среда предоставляет для персонажа оп­ределенную информацию, которая затем передается агенту. Процесс «восприятия» окружающей среды называется предчувствием. Нейроконтроллер обеспечивает возможность выбора действия, посредством которого персонаж взаимодействует с окружающей средой. Окружающая среда при этом изменяется, персонаж вновь обращается к восприятию, и цикл возобновляется.



Рис. 5.8. Пример нейроконтроллера в окружающей среде

Архитектура нейроконтроллера

В предыдущем примере описывалась нейронная сеть с одним выходом. В ком­пьютерных играх используется несколько иная архитектура - сеть, построенная по принципу «победитель получает все». Такие архитектуры полезны в том слу­чае, если выходы должны быть разделены на несколько классов (рис. 5.9).

Группа ячеек по принципу «победитель получает все»

Входной слой Скрытый слой Выходной слой

Рис. 5.9. Группа «победитель получает все»
В сети, созданной по принципу «победитель получает все», выходная ячейка с большей суммой весов является «победителем» группы и допускается к дей­ствию. В рассматриваемом приложении каждая ячейка представляет определенное поведение, которое доступно для персонажа в игре. В качестве примеров поведения можно назвать такие действия, как выстрелить из оружия, убежать, уклониться и др. Срабатывание ячейки в группе по принципу «победитель получает все» при­водит к тому, что агент выполняет определенное действие. Когда агенту вновь позволяется оценить окружающую среду, процесс повторяется.

На рис. 5.10 представлена сеть, которая использовалась для тестирования ар­хитектуры и метода выбора действия. Четыре входа обозначают «здоровье персо­нажа» (0 - плохое, 2 - хорошее), «имеет нож» (1, если персонаж имеет нож, 0 -в противном случае), «имеет пистолет» (1, если персонаж имеет пистолет, 0 -в противном случае) и «присутствует враг» (количество врагов в поле зрения).

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

Группа ячеек по принципу «победитель получает все»

Входной слой Скрытый слой Выходной слой

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

Примечание Выбранная здесь архитектура (три скрытые ячейки) была опре­делена способом проб и ошибок. Три скрытые ячейки могут быть обучены для всех представленных примеров со 100% точностью. Уменьшение количества ячеек до двух или одной приводит к созда­нию сети, которая не может правильно классифицировать все при­меры.
Обучение нейроконтроллера

Нейроконтроллер в игровой среде представляет собой постоянный элемент персонажа. Дальше мы обсудим обучение нейроконтроллера в режиме реального времени.

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

Данные для тестирования

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

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

Здоровье	Имеет нож	Имеет пистолет	Враги	Поведение
2	0	0	0	Уворачиваться
2	0	0	1	Уворачиваться
2	0	1	1	Атаковать
2	0	1	2	Атаковать
2	1	0	2	Прятаться
2	1	0	1	Атаковать
1	0	0	0	Уворачиваться
1	0	0	1	Прятаться
1	0	1	1	Атаковать
1	0	1	2	Прятаться
1	1	0	2	Прятаться
1	1	0	1	Прятаться
0	0	0	0	Уворачиваться
0	0	0	1	Прятаться
0	0	1	1	Прятаться
0	0	1	2	Бежать
0	1	0	2	Бежать
0	1	0	1	Прятаться

Данные, приведенные в табл. 5.1, были переданы сети в произвольном поряд­ке во время обучения с помощью алгоритма обратного распространения. График снижения средней ошибки показан на рис. 5.11.

В большинстве случаев сеть успешно проходит обучение на всех представ­ленных примерах. При некоторых запусках один или два примера приводят



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

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

Если предложить нейроконтроллеру сценарий, в котором персонаж полнос­тью здоров, владеет оружием двух видов и видит двух врагов (то есть 2:1:1:1), ней­роконтроллер выберет действие «атаковать». Это разумная реакция на данную си­туацию. Теперь рассмотрим сценарий, в котором персонаж полностью здоров, владеет ножом и видит трех врагов (то есть 2:1:0:3). Нейроконтроллер выбирает действие «спрятаться», вполне разумный выбор в данной ситуации. Другие при­меры показаны в табл. 5.2.

Таблица 5.2. Примеры, иллюстрирующие правильную генерацию действий

Здоровье	Имеет нож	Имеет пистолет	Враги	Поведение
Хорошее (2)	Да	Да	1	Атаковать
ОК(1)	Да	Да	2	Прятаться
Плохое (0)	Нет	Нет	0	Уворачиваться
Плохое (0)	Да	Да	1	Прятаться
Хорошее (2)	Нет	Да	3	Прятаться
Хорошее (2)	Да	Нет	3	Прятаться
Плохое (0)	Да	Нет	3	Бежать

Таким образом, нейроконтроллер правильно генерирует действие из заданно­го набора в ответ на новую обстановку (табл. 5.2). Хотя его не обучали конкретно для этих примеров, он способен правильно на них реагировать.

Совет Исходный код алгоритма обратного распространения вы можете

найти в архиве с примерами на сайте издательства «ДМК Пресс» www.dmk.ru.

Обсуждение исходного кода

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

Листинг 5.1. Гповальные константы и переменные для нейронной сети и алгоритма обратного распространения

#define INPUT_NEURONS 4

#define HIDDEN_NEURONS 3

#de-fine OUTPUT_NEURONS 4

I* Веса */

/* Вход скрытых ячеек (со смещением) */ double wih[INPUT_NEURONS+l][HIDDEN_NEURONS];

/* Вход выходных ячеек (со смещением) */ double who[HIDDEN_NEURONS+l][OUTPuT_NEURONS];

/* Активаторы */ double inputs[INPUT_NEURONS]; double hidden[HIDDEN_NEURONS]; double target[OUTPUT_NEURONS]; double actual[OUTPUT_NEURONS];

/* Ошибки */

double erro[OUTPUT_NEURONS]; double errh[HIDDEN_NEURONS];

Веса определяются как веса соединений между входным и скрытым (wih), а также между скрытым и выходным слоями (who). Вес соединения между и₅ и и, (рис. 5.10) является весом входа в скрытый слой, представленный wih[0] [0] (так как и, - это первая входная ячейка, а и₅ - первая скрытая ячейка, начиная с нуля). Данный вес обозначается как w_5.1. Вес w_11.7 (соединение между ячейкой и„ выходного слоя и и₇ скрытого слоя) равен who [ 2 ] [ 3 ]. Веса смещения занима­ют последнюю строку в каждой таблице и идентифицируются с помощью значе­ния +1 в массивах wih и who.

Значения сигналов хранятся в четырех массивах. Массив inputs определяет значение входных ячеек, массив hidden содержит выход для скрытых ячеек, мас­сив target предоставляет желаемое значение сети для заданных входов, а мас­сив actual отображает реальный результат работы сети.

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

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

Листинг 5.2. Макросы и символьные константы для алгоритма обратного распространения

#define LEARN_RATE 0.2 /* Коэффициент обучения */

#define RAND_WEIGHT ( ((float)rand() / (float)RAND_MAX) - 0.5)

#define getSRandO ((float)rand() / (float)RAND_MAX)

#define getRand(x) (int)((x) * getSRandO)

#define sqr(x) ((x)*(x))

Веса произвольно выбираются в диапазоне (от -0,5 до 0,5). Коэффициент обу­чения задается как 0,2. Диапазон весов и коэффициент обучения могут быть из­менены в зависимости от проблемы и требуемой точности решения.

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

Листинг 5.3. Вспомогательные функции для алгоритма обратного распространения

void assignRandomWeights( void ) {

int hid, inp, out;

for (inp = 0 ; inp

}

} . *

for (hid = 0 ; hid OUt++) { who[hid][out] = RAND_WEIGHT;

}

} -

double sigmoid( double val ) {

return (1.0 / (1.0 + exp(-val)));

}

double sigmoidDerivative( double val ) {

return ( val * (1.0 - val) );

}

Функция assignRandomWeights произвольно задает вес для всех соеди­нений сети (включая все смещения). Функция sigmoid определяет значение функции сжатия (сигмоида), которая используется при прямом вычислении (уравнение 5.5). Функция sigmoidDerivative устанавливает значение про­изводной функции sigmoid и используется при обратном распространении ошибки.

Следующая функция реализует фазу прямого вычисления алгоритма (лис­тинг 5.4).

' Листинг 5.4. Алгоритм прямого распространения

void feedForward( ) {

int inp, hid, out; double sum;

/* Вычислить вход в скрытый слой */

for (hid = 0 ; hid

sum = 0.0;

for (inp = 0 ; inp
}

/* Добавить смещение */

sum += wih[INPUT_NEURONS][hid];

hidden[hid] = sigmoid( sum );

}

/* Вычислить вход в выходной слой */

for (out = 0 ; out

sum =0.0;

for (hid = 0 ; hid
}

/* Добавить смещение */

sum += who№IDDEN_NEURONS] [out] ;

actual[out] = sigmoid( sum );

}

}

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

Алгоритм обратного распространения показан в листинге 5.5.

Листинг 5.5. Алгоритм обратного распространения

void backPropagate( void ) {

int inp, hid, out;

/* Вычислить ошибку выходного слоя (шаг 3 для выходных ячеек) */ for (out = 0 ; out OUt++) { errofout] = (target[out]-actual[out])*

sigmoidDerivative( actual[out]);

}

/* Вычислить ошибку скрытого слоя (шаг 3 для скрытого слоя) */ for (hid = 0 ; hid

errh[hid] = 0.0;

for (out = 0 ; out

}

errhfhid] *= sigmoidDerivative( hidden[hid] );

}

/* Обновить веса для выходного слоя (шаг 4 для выходных ячеек) */ for (out = 0 ; out

who[hid][out] += (LEARN_RATE * erro[out] * hidden[hid]);

}

/* Обновить смещение */

who[HIDDEN_NEURONS][out] += (LEARN_RATE * erro[out]);

}

/* Обновить веса для скрытого слоя (шаг 4 для скрытого слоя) */

for (hid = 0 ; hid

wih[inp][hid] += (LEARN_RATE * errh[hid] * inputs[inp]);

}

/* Обновить смещение */

wih[INPUT_NEURONS][hid] += (LEARN_RATE * errh[hid]);

}

}

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

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

В листинге 5.6 приведена структура, задачей которой является отображение примеров для обучения. Структура задает входы (здоровье, нож, пистолет, враг), атакже значение желаемого результата (массив out). Листинг 5.6 также включа­ет инициализированные данные для обучения сети.

Листинг 5.6. Отображение данных для обучения нейроконтроллера

typedef struct {

double health;

double knife;

double gun;

double enemy;'

double out[OUTPUT_NEURONS]; } ELEMENT;

#define MAX_SAMPLES 18

/* Н К G Е A R W Н */

ELEMENT samples[MAX_SAMPLES] = {

{ 2.0, 0.0, 0.0, 0.0, {0.0, 0.0, 1.0, 0.0} },

{ 2.0, 0.0, 0.0, 1.0, {0.0, 0.0, 1.0, 0.0} },

{ 2.0, 0.0, 1.0, 1.0, {1.0, 0.0, 0.0, 0.0} },

{ 2.0, 0.0, 1.0, 2.0, {1.0, 0.0, 0.0, 0.0} },

{ 2.0, 1.0, 0.0, 2.0, {0.0, 0.0, 0.0, 1.0} },

{ 2.0, 1.0, 0.0, 1.0, {1.0, 0.0, 0.0, 0.0} },

{ 1.0, 0.0, 0.0, 0.0, {0.0, 0.0, 1.0, 0.0} },

{ 1.0, 0.0, 0.0, 1.0, {0.0, 0.0, 0.0, 1.0} },

{ 1.0, 0.0, 1.0, 1.0, {1.0, 0.0, 0.0, 0.0} },

{ 1.0, 0.0, 1.0, 2.0, {0.0, 0.0, 0.0, 1.0} },

{ 1.0, 1.0, 0.0, 2.0, {0.0, 0.0, 0.0, 1.0} },

{ 1.0, 1.0, 0.0, 1.0, {0.0, 0.0, 0.0, 1.0} },

{ 0.0, 0.0, 0.0, 0.0, {0.0, 0.0, 1.0, 0.0} },

{ 0.0, 0.0, 0.0, 1.0, {0.0, 0.0, 0.0, 1.0} },

{ 0.0, 0.0, 1.0, 1.0, {0.0, 0.0, 0.0, 1.0} }, { 0.0, 0.0, 1.0, 2.0, {0.0, 1.0, 0.0, 0.0} }, { 0.0, 1.0, 0.0, 2.0, {0.0, 1.0, 0.0, 0.0} }, { 0.0, 1.0, 0.0, 1.0, {0.0, 0.0, 0.0, 1.0} }

};

Вспомните, что вход «здоровье» может иметь три значения (2 - здоров, 1 - не полностью здоров и 0 - нездоров). Входы «нож» и «пистолет» являются булевы­ми (1 - если предмет есть, 0 - если его нет), а вход «враг» показывает количество врагов в пределах видимости. Действия также являются булевыми, где ненулевое значение показывает выбранное действие.

Поскольку сеть построена по принципу «победитель получает все», следует за­кодировать простую функцию, которая будет определять выходную ячейку с самой большой суммой весов. Она выполняет поиск по вектору максимального значения и возвращает строку, которая отображает нужное действие (листинг 5.7). Возвра­щенное значение затем может использоваться в качестве индекса в массиве строк strings и позволяет вывести текст, показывающий реакцию.

Листинг 5.7. Функция для сети «победитель получает все»

char *strings[4]={"Attack", "Run", "Wander", "Hide"};

int action( double *vector ) {

int index, sel; double max;

sel = 0;

max = vector[sel]; ;

for (index = 1 ; index max) {

max = vector[index]; sel = index;

}

}

return( sel ) ;

}

Наконец, в листинге 5.8 показана функция main, которая выполняет обуче­ние и тестирование нейроконтроллера.

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

int main() {

double err;

int i, sample=0, iterations=0; int sum = 0;

out = fopen("stats.txt", "w");

/* Инициализировать генератор случайных чисел */ srand( time(NULL) ) ; assignRandomWeights();

/* Обучить сеть */ while (1) {

if (++sample == MAX_SAMPLES) sample = 0;

inputs[0] = samples[sample].health;

inputs[l] = samples[sample].knife;

inputs[2] = samples[sample].gun;

inputs[3] = samples[sample].enemy;

target[0] = samples[sample].out[0]

target[1] = samples[sample].out[1]

target[2] = samples[sample].out[2]

target[3] = samples[sample].out[3]

feedForward();

err = 0.0;

for (i = 0 ; i

err += sqr( (samples[sample].out[i] - actual[i]) );

}

err = 0.5 * err;

fprintf(out, "%g\n", err); printf("mse = %g\n", err);

if (iterations++ > 100000) break;

backPropagate();

}

/* Проверить сеть */

for i=0 ; i

inputs[0] = samples[i].health; inputs[l] = samples[i].knife;

inputs[2] = samples[i].gun;

inputs[3] = samples[i].enemy;

target[0] = samples[i].out[0];

target[1] = samples[i].out[1];

target[2] = samples[i].out[2];

target[3] = samples[i].out[3];

feedForward();

if (action(actual)!= action(target)) {

printf("%2.1g:%2.1g:%2.1g:%2.1g %s (%s)\n",

inputs[0], inputs[1], inputs[2], inputs[3], strings[action(actual)], strings[action(target)]);

} else { sum++;

}

}

printf("Network is %g%% correct\n",

((float)sum / (float)MAX_SAMPLES) * 100.0);

/* Выполнение тестов */

/* Здоровье Нож Пистолет Враг*/

inputs[0] = 2.0; inputs[1] = 1.0; dnputs[2] = 1.0; inputs[3] = 1.0; feedForward();

printf("2111 Action %s\n", strings[action(actual)]);

inputs[0] = 1.0; inputs[l] = 1.0; inputs[2] = 1.0; inputs[3] = 2.0; feedForward();

printf("1112 Action %s\n", strings[action(actual)]);

inputs[0] = 0.0; inputs[l] = 0.0; inputs[2] = 0.0; inputs[3] = 0.0; feedForward();

printf("0000 Action %s\n", strings[action(actual)]) ;

inputs[0] = 0.0; inputs[l] = 1.0; inputs[2] = 1.0; inputs[3] = 1.0; feedForward();

printf("0111 Action %s\n", strings[action(actual)]) ;

inputs[0] = 2.0; inputs[l] = 0.0; inputs[2] = 1.0; inputs[3] = 3.0; feedForward();

printf("2013 Action %s\n", strings[action(actual)]);

inputs[0] = 2.0; inputs[1] = 1.0; inputs[2] = 0.0; inputs[3] = 3.0; feedForward();

printf("2103 Action %s\n", strings[action(actual)]);

inputstO] = 0.0; inputs[1] = 1.0; inputs[2] = 0.0; inputs[3] = 3.0; feedForward();

printf("0103 Action %s\n", strings[action(actual)]); fclose(out); return 0;

}

После инициализации генератора случайных чисел с помощью функции srand будут произвольно сгенерированы веса соединений сети. Затем для обучения сети выполняется цикл while. Примеры рассматриваются последовательно, а не в произвольном порядке. Выполняется расчет реакции сети на входной вектор, а затем - проверка средней ошибки. Наконец, запускается алгоритм обратного распространения, чтобы изменить веса соединений сети. После вы­полнения ряда итераций программа выходит из цикла, и сеть тестируется на точность на основе значений, заданных для обучения. После стандартного тес­тирования выполняется тестирование сети с примерами, которые не входили в начальную группу при обучении.

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

Обучение нейроконтроллера

Когда нейроконтроллер встраивается в игру, его обучение считается завер­шенным и не может продолжаться дальше. Чтобы дать персонажу возможность обучаться, вы можете добавить в игру элементы алгоритма обратного распрост­ранения. Это позволит изменять веса в зависимости от ситуаций игрового про­цесса.

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

Далее все ИИ-персонажи игры могут получать одни и те же знания, пользу­ясь тем, что называется «эволюцией Ламарка», при которой дети учатся на ошиб­ках своих родителей. Пройдя несколько игр, персонажи постепенно будут стре­миться избегать отрицательных результатов.

Память нейроконтроллера

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

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

Другие области применения

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

□ общее распознавание моделей;

□ диагностика ошибок;

□ мониторинг состояния пациентов врача;

□ распознавание персонажей;

□ фильтрация данных;

□ анализ запахов и ароматов;

□ распознавание фальшивых банкнот и документов.

Итоги

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

Литература и ресурсы

1. Ваггонер Б., Спир Б. Жан-Баптист Ламарк (1744-1829) (Waggoner В., Speer В. Jean-Baptiste Lamarck (1744-1829)). Доступно по адресу http:// www.ucmp.berkeley.edu/history/lamarck.html).

2. Галлант С. Обучение в нейронных сетях и экспертные системы (Gallant S. L., Neutral Network Learning and Expert Systems. - Cambridge, Mass.: MIT Press, 1994).

3. Мински M., Паперт С. Перцептроны: введение в компьютерную геометрию (Minsky М., Papert S. Perceptrons: An Introduction to Computational Geometry. - Cambridge, Mass.: MIT Press, 1969).