Алгоритм NEAT. Эволюционирующие нейронные сети возрастающих топологий.

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

Поэтому возникла задача, чтобы сеть могла не только обучаться, но и сама настраивать свою топологию, создавать/удалять узлы и связи. Одним из таких алгоритмов является алгоритм NEAT. Именно с помощью этого алгоритма была создана и обучена нейронная сеть  Mar/IO, играющая в Супер Марио на видео ниже:

Документ, описывающий алгоритм NEAT 

Алгоритм

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

Ген

Наборы (векторы) нейронов и связей являют собой "Ген", которым оперируют генетический алгоритм.

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

Исторические маркеры

Каждая связь обладает своим уникальным маркером (innovation number). Новый маркер может быть создан только при мутации. Это по сути ID связи, но кроме всего прочего он позволяет отследить как "возраст" самой сети, так и происходивших с ней мутаций. Кроме того это позволяет значительно упростить скрещивание.

Мутация

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

NEAT Новая связь №7 (3 → 5)

При втором типе мутации создается новый нейрон, на месте уже существующей связи между двумя нейронами. При этом старая связь становится неактивной, и создаются две новые:

NEAT Новый нейрон №6.
Две новые связи созданы №8(3→6) и №9(6→4).
Связь №3(3→4) стала неактивна.

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

Скрещивание

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

NEAT Скрещивание генов двух родителей.

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

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

Однослойный персептрон, где x(1..n) - входы,  y(1..m) - выходы

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

Эта фитнес функция ранжирует всю популяцию (например по тому, как далеко Марио продвинулся в игре, или насколько далеко смог пройти человечек из видео выше). Те, особи, которые оказались лучше других будут иметь большие вероятности на "продолжение рода", но даже худшие имеют небольшой статистический шанс. Это помогает избежать скатыванию популяции в локальный минимум/максимум.

Далее алгоритм отбирает особей с учетом полученных вероятностей и происходит "скрещивание". Именно тут алгоритм NEAT хорош, ибо имеет простые правила "двуполого" скрещивания генов. Чаще всего именно скрещивание - самая сложная часть генетических алгоритмов.

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

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

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

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

NEAT - это только один из алгоритмов, для построения растущих нейронных сетей. Другими широко известными алгоритмами являются HyperNEAT(вариация этого-же алгоритма)  и SOINN.