3.4. Ускорение сходимости алгоритмов обучения нейронных сетей. Алгоритм сопряженных градиентов.

Как показано выше алгоритм обучения сетей типа “back propagation” – это реализация классического метода наискорейшего спуска. Этот алгоритм обучения относительно прост в реализации и применении, что и объясняет его широкое использование в области нейросетей. Однако у него имеется 2 слабых места:

  1. он медленно сходится;
  2. метод эффективен только при поиске точек локального минимума.

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

Метод сопряженных градиентов

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

(11)
где - множество обучающих образцов.

Для трехслойной сети с N входными узлами, включая пороговый узел, J скрытыми узлами и M выходными узлами вектор весов W содержит NJ+MJ компонент. В формуле (11) M - число выходных узлов; - желаемый выход для обучающего образца t, а - реакция (выходной сигнал сети) на образец t.

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

Сопряженные направления.

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

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

Возникает вопрос: каким образом алгоритм СГ достигает сходимости за конечное число шагов и на каких задачах? Допустим, что нам необходимо минимизировать функцию

(13)
где b и (W-D)-мерные векторы, а матрица определена выше. Итак, мы имеем квадратичную функцию. Допустим, что мы ищем итерационно оптимальный вектор , который минимизирует , и начинаем поиск с начальной точки . Выбираем ненулевой вектор , который служит направлением поиска на следующей итерации, при этом не важно, каким образом были выбраны и . Зададим как следующий вектор:
, (14)
где скаляр выбирается так, чтобы минимизировать . Сейчас мы подходим к главному пункту. Оптимальное направление, в котором необходимо двигаться на следующей итерации – это направление, в котором требуется только один шаг прямо в точку оптимального решения и оно должно образовывать A-сопряженную пару свектором .

Оптимальное направление – это поэтому условие, что есть А-сопряженное направление, эквивалентно утверждению, что должно выполняться условие

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

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

Алгоритм сопряженных направлений систематически конструирует множество А-сопряженных векторов. Спустя максимум D шагов алгоритм найдет оптимальное направление, и сходимость будет обеспечена.

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

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

Заметим, что в уравнении (13) AW есть множитель, пропорциональный градиенту функции E(W).

Для таких проблем общего вида конечная сходимость более не гарантируется.

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

Описание алгоритма.

  1. Полагаем . Инициализировать весовой вектор и вычислить градиент . Положить вектор начального направления .
  2. Найти скаляр >, который минимизирует , для чего можно использовать метод Фибоначчи или золотого сечения.
    (15)
  3. Если , где - допустимая точность нахождения минимума, то STOP. Иначе - вычислить новое направление:
  4. Если modD(K+1), где D - размерность пространства весов W, то новый вектор направления

    иначе положить (16)
    и вычислить новый вектор направления
  5. Заменить на и на . Переход к шагу 1 следующей итерации.