Учебное пособие по курсу «Нейроинформатика»
Шрифт:
Среди неградиентных методов рассмотрим следующие методы, каждый из которых является представителем целого семейства методов оптимизации:
1. Метод случайной стрельбы (представитель семейства методов Монте-Карло).
2. Метод покоординатного спуска (псевдоградиентный метод).
3. Метод случайного поиска (псевдоградиентный метод).
4. Метод Нелдера-Мида.
Рис. 1. Простейший алгоритм метода случайной стрельбы
Идея метода случайной стрельбы состоит в генерации большой последовательности случайных точек и вычисления оценки в каждой из них. При достаточной длине последовательности минимум будет найден. Запись этой процедуры на макроязыке приведена на рис. 1
Остановка данной процедуры производится по команде пользователя или при выполнении условия, что О1 стало меньше некоторой заданной величины. Существует огромное разнообразие модификаций этого метода. Наиболее простой является метод случайной стрельбы с уменьшением радиуса. Пример процедуры, реализующей этот метод, приведен на рис. 2. В этом методе есть два параметра, задаваемых пользователем:
Число_попыток — число неудачных пробных генераций вектора при одном радиусе.
Минимальный_радиус — минимальное значение радиуса, при котором продолжает работать алгоритм.
Идея этого метода состоит в следующем. Зададимся начальным состоянием вектора параметров. Новый вектор параметров будем искать как сумму начального и случайного, умноженного на радиус, векторов. Если после Число_попыток случайных генераций не произошло уменьшения оценки, то уменьшаем радиус. Если произошло уменьшение оценки, то полученный вектор объявляем начальным и продолжаем процедуру с тем же шагом. Важно, чтобы последовательность уменьшающихся радиусов образовывала расходящийся ряд. Примером такой последовательности может служить использованный в примере на рис. 2 ряд 1/n.
Рис. 2. Алгоритм метода случайной стрельбы с уменьшением радиуса
Отмечен ряд случаев, когда метод случайной стрельбы с уменьшением радиуса работает быстрее градиентных методов, но обычно это не так.
Идея этого метода состоит в том,
что если в задаче сложно или долго вычислять градиент, то можно построить вектор, обладающий приблизительно теми же свойствами, что и градиент следующим путем. Даем малое положительное приращение первой координате вектора. Если оценка при этом увеличилась, то пробуем отрицательное приращение. Далее так же поступаем со всеми остальными координатами. В результате получаем вектор, в направлении которого оценка убывает. Для вычисления такого вектора потребуется, как минимум, столько вычислений функции оценки, сколько координат у вектора. В худшем случае потребуется в два раза большее число вычислений функции оценки. Время же необходимое для вычисления градиента в случае использования двойственных сетей можно оценить как 2–3 вычисления функции оценки. Таким образом, учитывая способность двойственных сетей быстро вычислять градиент, можно сделать вывод о нецелесообразности применения метода покоординатного спуска в обучении нейронных сетей.Данный раздел посвящен описанию макрокоманды Оптимизация_Шага. Эта макрокоманда часто используется в описании процедур обучения и не столь очевидна как другие макрокоманды. Поэтому ее текст приведен на рис. 3. Идея подбора оптимального шага состоит в том, что при наличии направления в котором производится спуск (изменение параметров) задача многомерной оптимизации в пространстве параметров сводится к одномерной оптимизации — подбору шага. Пусть заданы начальный шаг (Ш2) и направление спуска (антиградиент или случайное) (Н). Тогда вычислим величину О1 — оценку в текущей точке пространства параметров. Изменив параметры на вектор направления, умноженный на величину пробного шага, вычислим величину оценки в новой точке — О2. Если О2 оказалось меньше либо равно О1, то увеличиваем шаг и снова вычисляем оценку. Продолжаем эту процедуру до тех пор, пока не получится оценка, большая предыдущей. Зная три последних значения величины шага и оценки, используем квадратичную оптимизацию — по трем точкам построим параболу и следующий шаг сделаем в вершину параболы. После нескольких шагов квадратичной оптимизации получаем приближенное значение оптимального шага.