Компьютерная Графика и Мультимедиа Сетевой журнал

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

1. Введение

Природе удалось создать такой удивительный механизм - живое существо. Его нервная система умеет многое. Именно поэтому наибольшие надежды ответить на вопрос <как это у нее получается?> связаны с изучением моделей нервной системы живых существ - искусственных нейронных сетей.

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

2. Нейронная сеть

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

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

Математическая запись:

Где: w - веса связей, x - компоненты выходного вектора (входного сигнала), f - функция активности, y - значение функции активности нейрона (активность), b - значение смещения (bias).

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

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

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

2.1. Структура сети

В зависимости от функций, выполняемых нейронами в сети выделяются три их класса:

• Входные нейроны (на которые подается векторы, кодирующий входное воздействие)
• Выходные нейроны (выходные значения которых представляют выходы нейронной сети)
• Промежуточные нейроны

С точки зрения топологии сети обычно разделяются на следующие типы:

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

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

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

2.2. Обучение нейронной сети

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

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

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

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

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

2.3. Построение нейронной сети

Разработчикам решения на основе нейронной сети требуется следующее:

• Выбрать соответствующую модель структуры сети
• Определить структуру сети - Указать параметры обучения
• Обучить нейронную сеть

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

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

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

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

2.4. Переход к эволюционным методам

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

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

3. Эволюционные методы

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

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

Обычно все эволюционные методы разделяют на 4 группы:

• Генетические алгоритмы
• Генетическое программирование
• Эволюционное программирование
• Эволюционные стратегии

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

Генетическое Программирование ставит своей основной задачей автоматическое программирование, т.е. каждый индивид является некоторой программой. Размер программы ограничен, но не постоянен. Также используются помимо строчного (линейного) представления деревья и графы. В общем, во всем остальном ГП очень похоже на ГА.

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

3.1. Основные механизмы генетических методов

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

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

Для описания процесса работы ГА необходимо определить еще несколько операций. Скрещивание - это операция построения нового генотипа (потомка) по генотипам двух родителей. Мутация - случайное изменение генотипа. Отбор - это выбор из популяции объектов-кандидатов для последующего скрещивания или перехода в новую популяцию (выживание особи и ее переход в новую эпоху).

Каждая эпоха согласно ГА состоит из следующих шагов:

1. Вычисление приспособленности каждого индивида из популяции
2. Отбор индивидов для скрещивания
3. Скрещивание отобранных индивидов и добавление потомков в популяцию
4. Мутация некоторых особей из популяции
5. Вычисление приспособленности всех новых особей
6. Отбор особей и составление из них новой популяции

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

3.2. Стандартные реализации механизмов

Для ГА стандартным представлением объекта является строка из символов некоторого языка (в машинном представлении - строка из битов). Алгоритм кодирования/декодирования уже выбирается в зависимости от задачи. Обычно, каждому числовому параметру фенотипа (по которому производится оптимизация), соответствует один или несколько символов в строке, называемых геном.

В качестве оператора мутации чаще всего применяется так называемая побитовая мутация (bit-flip или uniform). При применении такого оператора мутации каждый бит в гене меняет свое значение на противоположенное с некоторой заданной вероятностью. Т.к. и старшие и младшие биты двоичного представления чисел меняются с одинаковой вероятностью, то наряду с небольшими изменениями в значениях могут случаться и очень значительные. Поэтому наряду с побитовой мутацией часто применяется Гауссова мутация. Оператор гауссовой мутации работает только с генами из вещественных переменных. К значению каждой переменной в гене прибавляется некоторое случайное число, полученное с помощью нормального распределения с заданными параметрами. Параметры мутации могут задаваться как таким образом, чтобы мутация была незначительным изменением гена, так и для совершения больших скачков по пространству поиска. Приводятся доводы в пользу обоих вариантов, поэтому обычно для каждой задачи и тип оператора мутации и его конкретные параметры задаются отдельно.

Оператор скрещивания (более точное название, взятое из биологии - перекрест) обеспечивает обмен отдельными сегментами гена в процессе размножения. Чаще всего применяется одноточечный перекрест. Случайным образом выбирается точка на гене, по которой геном <разрезается>. Ген - потомок получает сегмент гена до точки разреза от одного родителя, а после точки разреза - от другого родителя. Аналогично вводятся двухточечный перекрест по двум точкам разреза и т.д.

Рис.2. Схема одно- и двухточечного перекреста

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

4. Эволюционное построение нейронной сети

Для применения генетических методов при построении структуры нейронных сетей (Evolutionary design of neural architectures - EDNA) вначале необходимо определить фенотип и генотип нейронной сети. Чаще всего под ее фенотипом понимают только структуру нейронной сети - т.е. структуру связей между нейронами. Такие параметры как вид и параметры функции активации обычно считаются заданными (хотя они также могут быть закодированы в генотипе). Весовые коэффициенты связей для построенной сети чаще всего задаются случайным образом, после чего корректируются в процессе обучения нейронной сети по одному из методов. Однако многие исследователи применяют генетические методы и для корректировки весов связей.

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

Рис.3 Взаимодействие между НС и ее записью в Гене

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

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

1. Каждый индивид из популяции декодируется в соответствующую нейронную сеть со всеми необходимыми параметрами
2. Все построенные нейронные сети обучаются по заранее определенному методу. Начальные значения параметров (весов) задаются обычно случайным образом.
3. Рассчитывается приспособленность каждого индивида по результатам тестирования сети
4. По правилам отбора определяются кандидаты на скрещивание, которые порождают новые генотипы
5. Некоторые индивиды из популяции и новых генотипов подвергаются мутации
6. Из индивидов старой популяции и новых генотипов составляется новая популяция

5. Обучение нейронной сети эволюционными методами

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

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

6. Свойства генетических представлений

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

Они предлагают следующий набор свойств:

1. Полнота (Completeness). Представление R полно, если любая принципиально возможная архитектура сети может быть сконструирована в системе.
2. Замкнутость (Closure). Представление R полностью замкнуто, если каждый генотип может быть декодирован в допустимый фенотип. Если представление незамкнуто, то его можно преобразовать в замкнутое введением специальных ограничений на процесс декодирования. Также, если генетические операторы сконструированы с учетом условия замкнутости, то система будет ограничена замкнутой. В этом случае не все генотипы будут соответствовать допустимым фенотипам, но система никогда не сгенерирует недопустимый генотип.
3. Компактность (Compactness). Пусть генотипы G1 и G2 декодируются в один и тот же фенотип. Тогда G1 компактнее G2, если он занимает меньше места в памяти.
4. Масштабируемость (Scalability). Различают масштабируемость по времени и по размеру. Масштабируемость по времени оценивает зависимость времени декодирования генотипа от его размера. По размеру оценивает зависимость размера генотипа от размеров соответствующего ему фенотипа.
5. Множественность (Multiplicity). Говорят, что представление обладает генотипической множественностью, если несколько различных геномов могут декодироваться в один фенотип. Аналогично, фенотипическая множественность возникает тогда, когда несколько фенотипов соответствуют одному генотипу.
6. Онтогенетическая приспосабливаемость (ontogenetic plasticity). Представление обладает этим свойством, когда декодирование фенотипа по генотипу зависит от внешней среды. (Многие представления нейронных сетей частично обладают этим свойством, т.к. процесс декодирования заканчивается обучением нейронной сети, а он зависит от подаваемых исходных данных.)
7. Модульность (Modularity). Пусть в сети несколько раз встречается подсеть SN. Тогда представление будет обладать свойством модульности, если в генотип информация о структуре подсети SN будет записана только один раз.
8. Избыточность (Redundancy). Избыточность может быть генетическая или фенотипическая. Если в геноме информация о некоторых генах записывается более одного раза, то возникает генетическая избыточность. Аналогично фенотипическая избыточность.
9. Сложность (Complexity). В этой свойство включаются такие понятия как структурная сложность (генотипа), сложность декодирования, вычислительная сложность отдельных компонентов системы построения.

7. Прямое кодирование

В 1989 году Миллер предложил кодировать структуру нейронной сети с помощью матрицы смежности (аналогично матрице смежности для графов). Он использовал ее для записи только многослойных нейронных сетей без обратных связей. Каждой возможной прямой связи нейрона i и не входного нейрона j соответствует элемент матрицы с координатами (i,j). Если значение этого элемента равно 1, связь есть; если 0 - связи нет. Для смещений каждого нейрона выделен отдельный столбец. Таким образом, нейронной сети из N нейронов соответствует матрица размерности N * (N+1).

Рис.4 Кодирование НС в матрице смежности

Геном нейронной сети по методу прямого кодирования составляется путем конкатенации двоичных строк матрицы смежности нейронной сети.

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

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

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

8. Параметрическое (непрямое) кодирование

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

Существует несколько подходов к реализации идеи параметрического кодирования. Первый из них был предложен Харпом, Самадом и Гуха в 1989 году. Они использовали <чертеж> для задания нейронной сети. Чертеж представлял собой последовательность сегментов, каждый из которых описывал одну группу нейронов (например, слоя в многослойной сети без обратных связей). Сегмент состоял из двух частей. Первая была фиксированного размера и содержала информацию о количестве нейронов в группе, их организации, а также адрес. Вторая часть содержала одно или более поле описания проекции (Projection specification field PSF), задающего связь данной группы нейронов с другими. В каждом поле записывались плотность связей, адрес группы, к которому они ведут и информацию об их организации. Первая и последняя группа описывала входные и выходные нейроны. Такое описание было намного более компактно и гораздо лучше масштабировалось.

Однако, такое представление не обеспечивало корректность закодированных сетей. Некоторые авторы исследовали варианты подобных представлений, например, Мандишер предложил представление для кодирования многослойных сетей, которое обеспечивало корректность. Геном состоял из последовательности описаний слоев. Описание слоя состояло из трех полей. Первое поле - размер слоя (количество нейронов).

Рис.5 Кодирование по Мандишеру

Второе и третье поле задавало связи данного слоя с другими. Второе поле описывало проективные связи, т.е. направленные от данного слоя к следующему. Третье поле описывало рецептивные связи, т.е. направленные от одного из предыдущих слоев к данному, соответственно третье поле состояло из произвольного количества описаний связей. Проективные связи задавались двумя параметрами - радиусом связей и плотностью связей. Размер радиуса зоны присоединения связей задавался в процентах относительно размера следующего слоя. Второй параметр задавал процент нейронов в зоне присоединения связей, с которыми реально устанавливалась связь.

Рис.6 Кодирование промежуточного слоя

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

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

9. Комбинированное представление

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

Рис.7 Шаблоны связей комбинированного кодирования

10. Грамматическое представление

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

Самый известный подход к реализации этой идеи базируется на Системах Линдемайра, или L-системах. Этот формализм был изначально грамматическим подходом к моделированию морфогенеза растений. Грамматика L-системы состоит из набора правил, использовавшихся для генерации строки-описания структуры. Процесс применения правил называется переписыванием строк (string-rewriting). К начальному символу S последовательно применяются правила переписывания строк, пока мы не получим строчку только из терминальных символов.

В 1990 году Китано разработал грамматику генерации графов (Graph Generation Grammar -GGG). Все правила имеют вид:

Алфавит этой грамматики содержит символы трех типов: нетерминальных N={A,B,:,Z}, предтерминальных P={a,b,:,p} и терминальных T={0,1}. Грамматика состоит из двух частей: переменной и постоянной. Переменная часть записывается в геном и состоит из последовательности описаний правил грамматики. Все символы из левой части правил должны быть нетерминальными, а из правой часть - из множества N?P. Постоянная часть грамматики содержит 16 правил для каждого предтерминального символа слева, и матрицы 2*2 из {0,1} справа. Для терминальных символов также задаются грамматические правила. Ноль раскрывается в матрицу 2*2 из нулей, а единичка - в матрицу и единиц.

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

Рис.9 Процесс декодирования грамматического представления

Процесс декодирования состоит из последовательных применений правил из генома к начальному символу S. Количество применений правил задается в начале. Полученная матрица интерпретируется следующим образом: если на диагонали элемент (i,i)=1, то ему соответствует нейрон. Все элементы (i,j) обозначают связь нейрона i с нейроном j, если они оба существуют. Все обратные связи удаляются.

11. Пространство из ячеек

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

Рис.10 Построение сети в пространстве из ячеек

В начале процесса декодирования все нейроны помещаются на плоскости в точках, заданных их координатами. Затем они индексируются. Индекс скрытых нейронов определяется их координатой х. Если у двух нейронов их х-овые координаты совпадают, то больший номер получает тот нейрон, который был считан из генома позже (д.е. закодирован дальше, чем другой). Индексы всех входных и выходных нейронов рассчитываются иначе. Каждому нейрону в генотипе также соответствует параметр тип. Для входных нейронов индекс равен I = type mod N(input), а для выходных нейронов он рассчитывается по формуле j = N - N(output) + type mod N(output). Где N(input) - количество входов в нейронную сеть, N(output) - количество выходов из нейронной сети. Очевидно, что некоторые входные и выходные нейроны будут иметь один и тот же индекс. Поэтому, при декодировании к нейронной сети добавляется N(input) входных и N(output) выходных реальных нейронов, к которым присоединены входы и выходы сети. Каждый такой дополнительный нейрон связывается со всеми нейронами с соответствующим индексом.

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

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

12. Порождающее пространство из ячеек

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

Этот подход был разработан Кангелоси, Париси и Нолфи. Вместо того, чтобы кодировать каждый нейрон напрямую, они записывают набор правил для разделения и смещения нейронов. Поэтому метод получил название порождающего пространства из ячеек (Generative cell space GCS).

Процесс онтогенеза начинается с одной клетки - <яйца> специального типа. Эта клетка затем разделяется (<переписывается>) в две дочерние клетки, причем параметры разделения задаются в правиле. Каждая из клеток-потомков могут быть размещены в одной из 8-и соседних с родительской клетках. Процесс повторяется заданное число раз, после чего все построенные клетки <взрослеют> и превращаются в нейроны. Они разделяются на входные, выходные и скрытые по тому же принципу, что и в предыдущем методе.

13. Результаты применения эволюционных методов

Подробнее всего описываются результаты применения эволюционных методов построения структуры нейронных сетей для исследовательских <тестовых> задач. Часто эти подходы используются для построения сетей распознавания свойств. Например, для определения углов и ребер на образцах, распознавания рукописных буквы.

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

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

14. Заключение

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

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

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

15. Ссылки

1. X. Yao "Evolving artificial neural networks", Proc. Of the IEEE, 1999
2. Marco Gronroos "A comparison of some methods for evolving neural networks" 1998
3. Karthik Balakrishnan, Vasant Honavar "Properties of genetic representations of neural architectures" 1995
4. Wolfram Schiffmann "Encoding feedforward networks for topology optimization by simulated evolution" 1999
5. A.A. Siddiqi, S.M.Lucas "A comparison of matrix rewriting versus direct encoding for evolving neural networks" IEEE Press, 1998
6. D.Dasgupta, D.McGregor, "Designing application specific neural networks using structured genetic algorithm", Proc. COGANN-92, 1992
7. M.Mandischer, "Representation and evolution of neural networks", 1993
8. Роберт Каллан <Основные концепции нейронных сетей> М.2001
9. В.В.Круглов, В.В.Борисов, <Искусственные нейронные сети> М. 2001

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

Ссылка: 

Антон Конушин. Эволюционные нейросетевые модели с незаданным заранее числом связей. Компьютерная графика и мультимедиа. Выпуск №1(2)/2003. http://cgm.computergraphics.ru/content/view/25

Выпуск: 

Выпуск №1(2)/2003