Кубические модели нейронов

Вектор

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

вектора

существует

возможных адресов.

Можно рассматривать ячейки памяти, как вершины

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

Двоичный вход

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

через

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

Модель нейрона Хебба

Структурная схема нейрона Хебба соответствует стандартной форме модели нейрона (рис.1). Д.Хебб предложил формальное правило, в котором вес

нейрона изменяется пропорционально произведению его входного и выходного сигналов

где

- коэффициент обучения.

При обучении с учителем вместо выходного сигнала

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

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

:

В результате применения правила Хебба веса нейрона могут принимать произвольно большие значения. Один из способов стабилизации процесса обучения по правилу Хебба состоит в учете последнего значения

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

Значение

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

Нейрон с квадратичным сумматором

Квадратичный сумматор может вычислять произвольный полином второго порядка от вектора входных сигналов

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

если

то объект принадлежит первому классу;

если

то объект принадлежит второму классу (при условии правильного выбора коэффициентов Q(x)).

Квадратичная ошибка здесь определяется как

Коэффициенты квадратичного сумматора уточняются по формулам

Недостаток такого классификатора - большое число настраиваемых параметров.

Нейрон типа "адалайн"

В нейроне типа "адалайн" (ADAptive LInear Neuron - адаптивный линейный нейрон) адаптивный подбор весовых коэффициентов осуществляется в процессе минимизации квадратичной ошибки, определяемой как

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

Нейроны типа WTA

Нейроны типа WTA (Winner Takes All — "Победитель получает все") имеют входной модуль в виде адаптивного сумматора. Выходной сигнал

-го сумматора определяется по формуле

По результатам сравнения сигналов

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

оказался наибольшим. Нейрон-победитель вырабатывает на своем выходе состояние 1, а остальные (проигравшие) нейроны переходят в состояние 0.

Для обучения нейронов WTA учитель не требуется. На начальном этапе случайным образом выбираются весовые коэффициенты

каждого нейрона, нормализуемые относительно 1 по формуле

После подачи входного вектора

, компоненты которого нормализованы по формуле

определяется победитель этапа. Победитель переходит в состояние 1, что позволяет произвести уточнение весов его входных линий

по правилу

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

Выходной сигнал

-го нейрона может быть описан векторным отношением

Поскольку

, значение

определяется углом между векторами

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

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

Обучение кубических нейронов

Кубические нейроны обучаются путем изменения содержимого ячейки их памяти. Обозначим через `+' операцию инкремента-установки содержимого ячейки в +1, через `-' операцию декремента-установки в -1.

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

Паде-нейрон

Паде-нейрон вычисляет произвольную дробно-линейную функцию вектора

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

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

В случае Паде-нейрона квадратичная ошибка определяется как

и значения весовых коэффициентов уточняются по следующим формулам

Персептрон

Простой персептрон — это нейрон МакКаллока-Питса (рис.1). Весовые коэффициенты входов сумматора, на которые подаются входные сигналы

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

персептрона является ступенчатой, вследствие чего выходной сигнал нейрона может принимать только два значения — 0 и 1 в соответствии с правилом

(1)

или -1 и 1 в соответствии с правилом

(2)

где

обозначает выходной сигнал сумматора

(3)

В формуле (3) предполагается

.

Рис. 1.  Нейрон МакКаллока-Питтса

Обучение персептрона состоит в таком подборе весов

, чтобы выходной сигнал совпадал с заданным значением или .

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

и . Заранее известно, что , относятся к первому классу, а , - ко второму. Требуется построить решающее правило, т.е. определить такую функцию , что при вектор относится к первому классу, а при - ко второму.

Сигма-Пи нейроны

Выше были рассмотрены нейроны с линейной и квадратичной функциями активации. Сигма-пи нейроны являются их обобщением на случай представления функции активации u полиномом степени

, - число входов нейрона:

где

- множество индексов, содержащее одну из возможных

комбинаций первых

целых чисел,

Сигмоидальный нейрон

Нейрон сигмоидального типа имеет структуру, подобную модели МакКаллока-Питса, с той разницей, что функция активации является непрерывной и может быть выражена в виде сигмоидальной униполярной или биполярной функции. Униполярная функция, как правило, представляется формулой (рис.2)

Рис. 2.  Униполярная функция (? =1)

тогда как биполярная функция задается в виде (рис.3)

Рис. 3.  Биполярная функция (?=1)

Параметр

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

Важным свойством сигмоидальной функции является ее дифференцируемость. Для униполярной функции имеем

тогда как для биполярной функции

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

проводится в направлении отрицательного градиента целевой функции

, где

Компонента градиента имеет вид

где

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

Значения весовых коэффициентов уточняются по формуле

где

.

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

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

выбирается из интервала (0,1).

Стохастическая модель нейрона

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

В стохастической модели нейрона выходной сигнал

принимает значения с вероятностью

где

обозначает взвешенную сумму входных сигналов нейрона, а

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

1) расчет взвешенной суммы

для каждого нейрона сети.

2) расчет вероятности

того, что принимает значение .

3) генерация значения случайной переменной

и формирование выходного сигнала , если , или в противном случае.

При обучении с учителем по правилу Видроу-Хоффа адаптация весов проводится по формуле

Запись активации в замкнутой форме

Рассмотрим двухвходовый кубический модуль. Существует 4 значения активации

. Выражение для активации будет иметь следующий вид:

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

В случае

- входового модуля получим

Алгоритм обучения персептрона по отдельным примерам

1. При изначально заданных значениях весов

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

2. Если

, то не изменяются.

3. Если

, а , то значения весов уточняются по формуле

где

— коэффициент обучения, — номер предыдущего цикла.

4. Если

, а , то значения весов уточняются по формуле

В обобщенной форме обучение персептрона на векторе

выражается формулой

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

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

Геометрическая интерпретация линейного разделения классов

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

В {

}-мерном пространстве (пространстве входных сигналов) разделяющая гиперплоскость перпендикулярна вектору . Вектор входных сигналов дает выход , если его проекция

на вектор

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

Пример

В двухмерном пространстве входных сигналов уравнение гиперплоскости имеет вид

При

и получаем уравнение

гиперплоскости, которая представлена на рис.1 пунктирной линией, пересекающей оси координат в точках (1.5, 0) и (0, 1.5) соответственно. Здесь:

— нормаль к разделяющей гиперплоскости; — вектор, относящийся к первому классу, поскольку проекция вектора на нормаль

больше

; — вектор, относящийся ко второму классу, поскольку .

Рис. 1. 

Линейное разделение классов

состоит в построении линейного решающего правила, т.е. такого вектора

, где

— порог, что при

вектор относится к первому классу, а при

— ко второму.

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

где

, относятся к первому классу, а - ко второму.

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

Настройка весового вектора

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

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

Пусть для некоторого

выполняется , но выход сети

где

при , и при , т.е. (угол

на рис.2 между векторами

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

Предположим теперь, что

, а (угол на рис.2 между векторами и меньше ). Теперь нужно увеличить угол между и , что получается путем вычитания части

из

:

увеличить изображение
Рис. 2.  Настройка вектора весов

Результирующая запись имеет вид:

Параметр

называется скоростью обучения.

Алгоритм обучения нейрона (персептрона) будет иметь вид:

repeat for

begin y = h[(W,V)];

end until

Обучение по всему задачнику

Построим обучающую выборку

В обучающей выборке выделяются все

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

модифицируется только после проверки всей обучающей выборки:

Не требуется хранить все множество Err - достаточно накапливать сумму тех

, на которых персептрон ошибается:

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

Промежуточный вариант: обучение по страницам

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

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

Метод максимума правдоподобия

Рассмотрим задачу разделения двух классов, с каждым из которых связано вероятностное распределение в пространстве векторов

значений признаков. Будем обозначать плотности этих распределений - событие, состоящее в том, что объект принадлежит {}-му классу. Нас интересует апостериорная вероятность: — вероятность принадлежности объекта к {}-му классу при условии, что он характеризуется вектором признаков . Известная из теории вероятности формула Байеса дает

" width="352" height="47">

где

— вероятность появления объектов {}-го класса. Для нормальных -мерных распределений

где

— математическое ожидание в {}-м классе, {} — ковариационная матрица для {}-го класса. В результате обработки данных находят статистические оценки {} и : пусть для {}-го класса имеются векторы , тогда полагаем

Минимизация в формуле Байеса дает простое решающее правило:

принадлежит

-му классу, если

для всех

, т.е выбирается такой класс, для которого вероятность максимальна. Поскольку в формуле Байеса для всех

знаменатель общий, то решающее правило приобретает следующий вид: выбираем то

, для которого максимально. Для нормального распределения удобно прологарифмировать эту величину. Окончательно получаем:

принадлежит -му классу, если среди величин

величина

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

Нейрофизиологическая аналогия

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

-го нейрона, в величину веса -го сигнала -го нейрона. Снабдив такое произведение весом — "коэффициентом индукции", получим рассматриваемую архитектуру

где

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

Реализация булевых функций нейронными сетями

Простой персептрон (нейрон МакКаллока-Питса) с весовым вектором

реализует гиперплоскость

и булеву функцию ИЛИ от двух аргументов

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

и булеву функцию И. Однако, персептрон не может воспроизвести даже такую простую функцию как ИСКЛЮЧАЮЩЕЕ ИЛИ. Она принимает значение единицы, когда один из аргументов равен единице (но не оба) (табл.1).

Таблица 1. Булева функция ИСКЛЮЧАЮЩЕЕ ИЛИ

0	0	0
0	1	1
1	0	1
1	1	0

Эту функцию реализует двухслойная нейронная сеть, представленная на рис.1 (сигнал

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

а вторая - уравнением

Соответствующие векторы весов имеют вид

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

Рис. 1.  Двухслойная сеть, реализующая функцию ИСКЛЮЧАЮЩЕЕ ИЛИ

Рис. 2.  Гиперплоскости, реализующие функцию ИСКЛЮЧАЮЩЕЕ ИЛИ

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

Выделение невыпуклых областей

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

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

На рис.5 приведен пример выделения невыпуклой области, представленной в виде объединения двух треугольных областей. Пять нейронов первого слоя реализуют разделяющие гиперплоскости, два нейрона второго слоя реализуют трехвходовые функции И, нейрон третьего слоя реализует функцию ИЛИ. Весовые векторы, описывающие соответствующие гиперплоскости, имеют вид:

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

Выделение выпуклых областей

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

Выше приведен пример выделения выпуклой области двумя гиперплоскостями (реализация функции ИСКЛЮЧАЮЩЕЕ ИЛИ). Аналогично в первом слое может быть использовано 3 нейрона с дальнейшим разбиением плоскости и созданием области треугольной формы (на рис. 3, 4,

, входы с нулевыми весами не указаны).

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

Рис. 3.  Гиперплоскости, выделяющие на плоскости выпуклую (треугольную) область

Рис. 4.  Нейронная сеть, выделяющая на плоскости выпуклую (треугольную) область

Функционирование сетей

Сети периодического функционирования. Простейшие представления об этих сетях таковы.

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

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

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

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

Интерпретация ответов сети

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

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

(или ). Если нам нужно получить сигнал в интервале , то нужно преобразовать выходной сигнал :

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

Знаковая интерпретация требует только

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

Порядковая интерпретация является еще более емкой, чем знаковая. В ней с помощью

нейронов можно описать принадлежность к

классам (а не

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

- наибольшему). Перестановку

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

Константа Липшица сигмоидальной сети

Рассмотрим слоистую сигмоидальную сеть (сеть с сигмоидальными нейронами) со следующими свойствами:

Число входных сигналов -

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

В этом случае оценка константы Липшица сети равна:

(2)

Формула (2) подтверждает экспериментально установленный факт, что, чем круче характеристическая функция нейрона (т.е. чем больше

), тем более сложные функции (функции с большей константой Липшица) может аппроксимировать сеть с такими нейронами.

Настройка нейронных сетей для решения задач

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

Какие сигналы сеть будет получать?Как мы будем интерпретировать сигналы, поступающие от сети?Как мы будем оценивать работу сети, если сеть обучается путем минимизации ошибок (т.е. что такое вектор ошибок и как вычисляется целевая функция — оценка функционирования сети)?

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

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

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

Оценка способности сети решить задачу

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

.

Нейронная сеть вычисляет некоторую вектор-функцию

от входных сигналов. Эта функция зависит от параметров сети. Обучение сети состоит в подборе такого набора параметров сети, чтобы величина

была минимальной (в идеале равна нулю), здесь

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

на

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

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

Сложность аппроксимации таблично заданной функции

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

(1)

Оценка (1) является оценкой константы Липшица аппроксимируемой функции снизу.

Константа Липшица сети вычисляется по следующей формуле:

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

сеть принципиально не способна решить задачу аппроксимации функции . Однако из еще не следует утверждение о способности сети аппроксимировать функцию

Предобработка данных

Нормировка и центрирование данных (предобработка) используются почти всегда (кроме тех случаев, когда данные представляют собой бинарные векторы с координатами 0,1 или

, либо символьные последовательности). Цель этих преобразований - сделать так, чтобы каждая компонента вектора данных лежала в отрезке (или ) или, по крайней мере, не слишком далеко выходила из этого отрезка, и её характерный разброс тоже был бы единичным.

Стандартные преобразования исходной выборки

:

или , где - -я компонента вектора ,

- выборочная оценка математического ожидания ;

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

Виды сетей

В многослойных (слоистых) сетях (рис.1) нейроны первого слоя получают входные сигналы, преобразуют их и передают нейронам второго слоя. Далее срабатывает второй слой и т.д., до

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

увеличить изображение
Рис. 1.  Многослойная (слоистая) сеть

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

к блоку ведут только возбуждающие связи, то это означает, что любой выходной сигнал блока

является монотонной неубывающей функцией любого выходного сигнала блока

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

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

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

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

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

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

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

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

Цель обучения состоит в подборе таких значений весов

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

Рис. 1.  Пример двухслойной нейронной сети

В выходном слое

-й нейрон вырабатывает выходной сигнал

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

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

примеров, целевая функция имеет вид

Минимизация целевой функции достигается уточнением вектора весов (обучением) по формуле

где

(1)

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

(2)

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

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

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



и



и затем сложить эти произведения и результат умножить на

и .

Таким образом, получим

Методы инициализации весов

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

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

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

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

Одномерная оптимизация

Все пошаговые методы оптимизации состоят из двух важнейших частей:

выбора направления, выбора шага в данном направлении (подбор коэффициента обучения).

Методы одномерной оптимизации дают эффективный способ для выбора шага.

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

где

обозначает количество входов -го нейрона в слое.

Более эффективный метод основан на адаптивном подборе коэффициента

с учетом фактической динамики величины целевой функции. Стратегия изменения значения определяется путем сравнения суммарной погрешности на -й итерации с ее предыдущим значением, причем рассчитывается по формуле

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

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

Если погрешности на

-1-й и -й итерациях обозначить соответственно и , а коэффициенты обучения на этих же итерациях — и , то значение следует рассчитывать по формуле

где

- коэффициент допустимого прироста погрешности, - коэффициент уменьшения

- коэффициент увеличения

.

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

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

Поиск минимума основан на полиномиальной аппроксимации целевой функции. Выберем для аппроксимации многочлен второго порядка

где

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

Соответствующие этим точкам значения целевой функции

обозначим как

(5)

Коэффициенты

, и

рассчитываются в соответствии с решением системы уравнений (5).
Для определения минимума многочлена

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

Одношаговый квазиньютоновский метод и сопряженные градиенты

В тех случаях, когда является положительно определенной матрица

вторых производных оценки

, наилучшим считается ньютоновское направление

С использованием этой формулы квадратичные формы минимизируются за один шаг, однако, применять эту формулу трудно по следующим причинам:

Время. Поиск всех вторых производных функции

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

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

Простейший и весьма эффективный метод основан на

формуле (Брайден-Флетчер-Гольдфард-Шанно) и использует результаты предыдущего шага. Обозначим:

- направление спуска на -шаге;

- величина шага (-й шаг - сдвиг на );

- градиент функции оценки в начальной точке -го шага;

- изменение градиента в результате -го шага.

- формула для направления спуска на -м шаге имеет вид:

где

- скалярное произведение векторов и .

Если одномерную оптимизацию в поиске шага проводить достаточно точно, то новый градиент

будет практически ортогонален предыдущему направлению спуска, т.е. . При этом формула для упрощается:

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

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

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

Особенности задачи оптимизации, возникающей при обучении нейронных сетей

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

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

Ограничение по памяти. Пусть

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

Партан-методы

Для исправления недостатков наискорейшего спуска разработаны итерационный и модифицированный партан-методы.

Итерационный партан-метод (

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

раз. После

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

Модифицированный партан-метод требует запоминания дополнительных параметров. Он строится следующим образом. Из

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

Учет ограничений при обучении

Для параметров сети возможны ограничения простейшего вида:

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

Учесть ограничения можно, например, методом штрафных функций либо методом проекций:

Использование метода штрафных функций означает, что в оценку

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

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

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

Универсальный путь обучения

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

задана обучающая выборка, состоящая из векторов входных сигналов

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

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

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

Выбор направления минимизации

Пусть задано начальное значение вектора параметров

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

Наиболее очевидный выбор направления

для одномерной оптимизации - направление антиградиента :

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

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

Другой способ - случайный выбор направления

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

Алгоритмы имитации отжига

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

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

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

Запустить процесс из начальной точки

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

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

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

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

Четыре типа устойчивости

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

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

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

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

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

Для выработки устойчивости 1-го типа примеры предъявляются сети не все сразу, а по одному, и сеть учится каждому из них до предела. Для выработки важнейшей устойчивости 4-го типа такая периодически производимая "порча" процесса обучения может быть полезной. Опыт показывает, что обучение позволяет выработать устойчивость к весьма сильным возмущением. Так, в задачах распознавания визуальных образов уровень шума на выходе мог в несколько раз превосходить общую интенсивность сигнала, случайный сдвиг параметров - достигать 0.5-0.7 их предельного значения, разрушение - 30-50\% элементов. И, тем не менее, обученная сеть делает не более 10\% ошибок!

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

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

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

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

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

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

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

, где

- ее целевая функция.

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

Рис. 1.  Процесс скрещивания

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

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

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

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

Элементы глобальной оптимизации

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

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

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

Метод виртуальных частиц

Метод виртуальных (случайных) частиц может надстраиваться почти над любым методом оптимизации. Он создан для:

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

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

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

Рассмотрим один из вариантов алгоритма виртуальных частиц. Пусть требуется найти минимум функции

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

Начальное положение основной частицы -

. Начальное положение -ой виртуальной частицы . Случайный вектор для -й виртуальной частицы строится так:

(1)

и её положение задается вектором

. Всем частицам, кроме -й, присваивается вес , , -я получает вес . Далее минимизируется функция

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

в виде и определяется двумя обстоятельствами:

для каждой координаты вектора

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

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

Есть три варианта:

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

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

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

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

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

---

---