Е. Миркес - Учебное пособие по курсу «Нейроинформатика»

35. Ш1=Ш О1=О

36. Чиспо_парабол=Число_парабол+1

37. Если Число_парабоп<���Максимальное_Число_Парабол то переход к шагу 22

33. Установить_параметры В

39. Модификация_вектора Н, 1, Ш 2

40. Освободить_вектор В

Рис. 3. Алгоритм оптимизации шага

Если после первого пробного шага получилось О2 большее О1, то уменьшаем шаг до тех пор, пока не получим оценку, меньше чем О1. После этого производим квадратичную оптимизацию.

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

1. Создать_вектор Н

2. Число_Смен_Радиуса=1

3. Попытка=0

4. Радиус=1/Число_Смен_Радиуса

5. Случайный_вектор Н

6. Оптимизация шага Н Радиус

7. Попытка=Попытка+1

8. Если Радиус=0 то Попытка=0

9. Если Попытка<=Число_попыток то переход к шагу 4

10. Число_Смен_Радиуса= Число_Смен_Радиуса+1

11. Радиус=1/Число_Смен_Радиуса

12. Если Радиус>= Минимальный_радиус то переход к шагу 3

13. Освободить_вектор Н

Рис. 4. Алгоритм метода случайного поиска

Число_попыток — число неудачных пробных генераций вектора при одном радиусе.

Минимальный_радиус — минимальное значение радиуса, при котором продолжает работать алгоритм.

Идея этого метода состоит в следующем. Зададимся начальным состоянием вектора параметров. Новый вектор параметров будем искать как сумму начального и случайного, умноженного на радиус, векторов. Если после Число_попыток случайных генераций не произошло уменьшения оценки, то уменьшаем радиус. Если произошло уменьшение оценки, то полученный вектор объявляем начальным и продолжаем процедуру с тем же шагом. Важно, чтобы последовательность уменьшающихся радиусов образовывала расходящийся ряд. Примером такой последовательности может служить использованный в примере на рис. 4 ряд 1/n.

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

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

Изучению градиентных методов обучения нейронных сетей посвящено множество работ [47, 65, 90] (сослаться на все работы по этой теме не представляется возможным, поэтому дана ссылка на работы, где эта тема исследована наиболее детально). Кроме того, существует множество публикаций, посвященных градиентным методам поиска минимума функции [48, 104] (как и в предыдущем случае, ссылки даны только на две работы, которые показались наиболее удачными). Данный раздел не претендует на какую-либо полноту рассмотрения градиентных методов поиска минимума. В нем приведены только несколько методов, применявшихся в работе группой «НейроКомп». Все градиентные методы объединены использованием градиента как основы для вычисления направления спуска.

1. Вычислить_оценку О2

2. О1=О2

3. Вычислить_градиент

4. Оптимизация шага Пустой_указатель Шаг

5. Вычислить_оценку О2

6. Если О1-О2<���Точность то переход к шагу 2

Рис. 5. Метод наискорейшего спуска

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

Этот метод работает, как правило, на порядок быстрее методов случайного поиска. Он имеет два параметра — Точность, показывающий, что если изменение оценки за шаг метода меньше чем Точность, то обучение останавливается; Шаг — начальный шаг для оптимизации шага. Заметим, что шаг постоянно изменяется в ходе оптимизации шага.

а)

б)

в)

Рис. 6. Траектории спуска при различных конфигурациях окрестности минимума и разных методах оптимизации.

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

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