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

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

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

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

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

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

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

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

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

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

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

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

Генетические алгоритмы имитируют процессы наследования свойств живыми организмами и генерируют последовательности новых векторов $$w$$, содержащие оптимизированные переменные: $$w = [w_1,w_2, \ldots, w_n]^T$$. При этом выполняются операции трех видов: селекция, скрещивание и мутация.

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим один из вариантов алгоритма виртуальных частиц. Пусть требуется найти минимум функции $$H_{pg}(w)$$.Параметры сети разбиваются на группы структурно эквивалентных. Для каждой группы задается свой интервал случайных сдвигов. Определяется число виртуальных частиц $$n$$ и генерируется $$n-1$$ случайных векторов $$r_1,r_2, \ldots, r_{n-1}$$. Их координаты независимо и равномерно распределены в заданных интервалах.

Начальное положение основной частицы - $$w^0$$. Начальное положение $$i$$ -ой виртуальной частицы $$w^0 + r_i, i=1, \ldots, n-1$$. Случайный вектор для $$n$$ -й виртуальной частицы строится так:

и её положение задается вектором $$w^0 + r_n$$. Всем частицам, кроме $$n$$ -й, присваивается вес $$W$$, $$0 < W < 1$$, $$n$$ -я получает вес $$W_n=W/n^{1/2}$$. Далее минимизируется функция

Алгоритм локальной оптимизации может быть выбран любой - от наискорейшего спуска и партан-методов до метода сопряженных градиентов. Выбор $$r_n$$ в виде $$(1)$$ и $$W_n=W/n^{1/2}$$ определяется двумя обстоятельствами:

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

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

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

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

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

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

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

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

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

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

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

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