Неградиентные методы обучения
Среди неградиентных методов рассмотрим следующие методы, каждый из которых является представителем целого семейства методов оптимизации:
1. Метод случайной стрельбы (представитель семейства методов Монте-Карло).
2. Метод покоординатного спуска (псевдоградиентный метод).
3. Метод случайного поиска (псевдоградиентный метод).
4. Метод Нелдера-Мида.
Метод случайной стрельбы
1. Создать_вектор В1
2. Создать_вектор В2
3. Вычислить_оценку О1
4. Сохранить_вктор В1
5. Установить_параметры В1
6. Случайный_вектор В2
7. Модификация_вектора В2, 0, 1
8. Вычислить_оценку О2
9. Если О2<О1 то переход к шагу 11
10. Переход к шагу 5
11. О1=О2
12. Переход к шагу 4
13. Установить_параметры В1
14. Освободить_вектор В1
15. Освободить_вектор В2
Рис. 1. Простейший алгоритм метода случайной стрельбы
Идея метода случайной стрельбы состоит в генерации большой последовательности случайных точек и вычисления оценки в каждой из них. При достаточной длине последовательности минимум будет найден. Запись этой процедуры на макроязыке приведена на рис. 1
Остановка данной процедуры производится по команде пользователя или при выполнении условия, что О1 стало меньше некоторой заданной величины. Существует огромное разнообразие модификаций этого метода. Наиболее простой является метод случайной стрельбы с уменьшением радиуса. Пример процедуры, реализующей этот метод, приведен на рис. 2. В этом методе есть два параметра, задаваемых пользователем:
Число_попыток — число неудачных пробных генераций вектора при одном радиусе.
Минимальный_радиус — минимальное значение радиуса, при котором продолжает работать алгоритм.
Идея этого метода состоит в следующем. Зададимся начальным состоянием вектора параметров. Новый вектор параметров будем искать как сумму начального и случайного, умноженного на радиус, векторов. Если после Число_попыток случайных генераций не произошло уменьшения оценки, то уменьшаем радиус. Если произошло уменьшение оценки, то полученный вектор объявляем начальным и продолжаем процедуру с тем же шагом. Важно, чтобы последовательность уменьшающихся радиусов образовывала расходящийся ряд. Примером такой последовательности может служить использованный в примере на рис. 2 ряд 1/n.
1. Создать_вектор В1
2. Создать_вектор В2
3. Вычислить_оценку O1
4. Число_Смен_Радиуса=1
5. Радиус=1/Число_Смен_Радиуса
6. Попытка=0
7. Сохранить_вектор В1
8. Установить_параметры В1
9. Случайный_вектор В2
10. Модификация_вектора В2, 1, Радиус
11. Вычислить_оценку О2
12. Попытка=Попытка+1
13. Если 02<01 то переход к шагу 16
14. Если Попытка<=Число_попыток то переход к шагу 8
15. Переход к шагу 18
16. О1=О2
17. Переход к шагу 6
18. Число_Смен_Радиуса= Число_Смен_Радиуса+1
19. Радиус=1/Число_Смен_Радиуса
20. Если радиус >= Минимапьный_радиус то переход к шагу 6
21. Установить_параметры В1
22. Освободить_вектор В1
23. Освободить_вектор В2
Рис. 2. Алгоритм метода случайной стрельбы с уменьшением радиуса
Отмечен ряд случаев, когда метод случайной стрельбы с уменьшением радиуса работает быстрее градиентных методов, но обычно это не так.
Метод покоординатного спуска
Идея этого метода состоит в том, что если в задаче сложно или долго вычислять градиент, то можно построить вектор, обладающий приблизительно теми же свойствами, что и градиент следующим путем. Даем малое положительное приращение первой координате вектора. Если оценка при этом увеличилась, то пробуем отрицательное приращение. Далее так же поступаем со всеми остальными координатами. В результате получаем вектор, в направлении которого оценка убывает. Для вычисления такого вектора потребуется, как минимум, столько вычислений функции оценки, сколько координат у вектора. В худшем случае потребуется в два раза большее число вычислений функции оценки. Время же необходимое для вычисления градиента в случае использования двойственных сетей можно оценить как 2–3 вычисления функции оценки. Таким образом, учитывая способность двойственных сетей быстро вычислять градиент, можно сделать вывод о нецелесообразности применения метода покоординатного спуска в обучении нейронных сетей.
Подбор оптимального шага
Данный раздел посвящен описанию макрокоманды Оптимизация_Шага. Эта макрокоманда часто используется в описании процедур обучения и не столь очевидна как другие макрокоманды. Поэтому ее текст приведен на рис. 3. Идея подбора оптимального шага состоит в том, что при наличии направления в котором производится спуск (изменение параметров) задача многомерной оптимизации в пространстве параметров сводится к одномерной оптимизации — подбору шага. Пусть заданы начальный шаг (Ш2) и направление спуска (антиградиент или случайное) (Н). Тогда вычислим величину О1 — оценку в текущей точке пространства параметров. Изменив параметры на вектор направления, умноженный на величину пробного шага, вычислим величину оценки в новой точке — О2. Если О2 оказалось меньше либо равно О1, то увеличиваем шаг и снова вычисляем оценку. Продолжаем эту процедуру до тех пор, пока не получится оценка, большая предыдущей. Зная три последних значения величины шага и оценки, используем квадратичную оптимизацию — по трем точкам построим параболу и следующий шаг сделаем в вершину параболы. После нескольких шагов квадратичной оптимизации получаем приближенное значение оптимального шага.
1. Создать_вектор В
2. Сохранить_вектор В
3. Вычислить_оценку О1
4. Ш1=0
5. Модификация_вектора Н, 1, Ш2
6. Вычислить_оценку О2
7. Если О1<О2 то переход к шагу 15
8. Ш3=Ш2*3
9. Установить_параметры В
10. Модификация_вектора Н, 1, Ш3
11. Вычислить_оценку О3
12. Если О3>О2 то переход к шагу 21
13. О1=О2 О2=О3 Ш1=Ш2 Ш2=ШЗ
14. Переход к шагу 3
15. ШЗ=Ш2 03=02
16. Ш2=ШЗ/3
17. Установить_параметры В
18. Модификация_вектора Н, 1, Ш2
19. Вычислить_оценку О3
20. Если О2>=О1 то переход к шагу 15
21. Число_парабол=0
22. Ш=((ШЗШЗ-Ш2Ш2)О1+(Ш1Ш1-ШЗШЗ)О2+(Ш2Ш2-Ш1Ш )О3)/(2((ШЗ-Ш2)О1+(Ш1-Ш3)О2 +(Ш2-Ш )О3))
23. Установить_параметры В
24. Модификация_вектора Н, 1, Ш
25. Вычислить_оценку О
26. Если Ш>Ш2 то переход к шагу 32
27. Если О>О2 то переход к шагу 30
28. ШЗ=Ш2 О3=О2 О2=О Ш2=Ш
29. Переход к шагу 36
30. Ш1=Ш О1=О
31. Переход к шагу 36
32. Если О>О2 то переход к шагу 35
33. ШЗ=Ш2 О3=О2 О2=О Ш2=Ш
34. Переход к шагу 36
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. Освободить_вектор Н
