Понимание conjugate gradients в контексте обучения MLP

[lsoft]

Здравствуйте.
У меня реализован алгоритм backpropagation для обучения многослойного нейронной сети (MLP).
В нем используется steepest descent, градиентный спуск.
Я хотел бы поэкспериментировать с другим видом спуска - сопряженные градиенты (conjugate gradients).
Признаться, институт закончил давно и очень много забыл уже с тех пор. Нашел прекрасный документ painless-conjugate-gradient.pdf в котором метод объясняется понятно (даже мне! :) ).
Реализовал его _линейную_ версию, которая применяется для решения систем линейных уравнений. Работает, понятно.

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

Собственно вопросы.
Технический вопрос: в нелинейном алгоритме (стр 42 документа painless-conjugate-gradient.pdf) требуется найти "ALPHAi that minimizes f(Xi + ALPHAi*Di)". Непонятно как... Гессиан вычислять нереально долго в задачах обучения MLP, это не подойдет.
Алгоритмический вопрос: Собственно, мне непонятно, как CG вообще встроить в backpropagation. Насколько я могу понять, каждое изменение весов в backpropagation - должна быть одной итерация приближения по методу CG. В наивной реализации мы просто вычитаем накопившуюся ошибку из веса и переходим к следующей итерации. А тут как поступить?

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

[iifat]

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

[lsoft]

Честно говоря, не знаю как ответить конкретно на Ваш вопрос.
Сопряженные градиенты (СГ) у меня получились в линейном случае. В нелинейном случае есть проблема с определением коэффициент ALPHAi (не знаю как он называется на матем. языке). Общий способ - через гессиан - не подходит, других не знаю. Подскажите простой алгоритм :)
Вторая трудность она алгоритмическая. Я пока с трудом представляю как СГ интегрировать в backpropagation. Но я предлагаю вторую трудность _пока_ не обсуждать. До нее еще дойдет дело.

По поводу первой трудности, я посмотрел исходники матем. библиотеки Accord.NET там есть реализованные СГ. Там используется какой-то архисложный алгоритм для "line search" видимо как раз для определения ALPHAi. Можно его использовать конечно, не погружаясь в мощную математику, но мне его потребуется переложить на OpenCL, что весьма сложно.

Итого. Гессиан - не подходит по скорости. Алгоритм из accord.net в принципе подходит, но весьма сложен для адаптации. Поэтому хочется какой-то простой алгоритм поиска ALPHAi.

Надеюсь ответил на Ваш вопрос.

[iifat]

Чуть-чуть почитал Википедию. Когда-то читал учебники, но было это очень давно и мог чего забыть.
Метод градиентного спуска состоит в том, что на каждом шаге проводим через очередную точку прямую в направлени градиента, ищем на этой прямой точку минимума функции и берём её за очередную.
Метод сопряжённых градиентов аналогичен предыдущему, за исключением единственной малости: направление, начиная со второй точки, берётся не вдоль градиента, а вдоль градиента с некоторой поправкой, рассчитываемой по двум последним точкам по достаточно простой формуле.
То бишь, источник каких-то принципиальных трудностей мне совершенно неясен.
И почему вы говорите о линейном случае? Для поиска экстремума линейной функции применяются совершенно другие методы. Оба метода градиентов применяются в нелинейном программировании.

-- 06.12.2014, 01:07 --

Посмотрел страницу 42. Ну да, разумеется, методы нелинейного программироования можно применять для линейного. С выбором шага вы, как понимаю, не сталкивались именно потому, что решали задачи линейного программирования, я правильно понял?
Ну что ж, для поиска минимума — теперь уже функции одной переменной — нужно либо решать каждый раз уравнение, зависящее от вида минимизируемой функции, либо численно, поинтересуйтесь соответствующими методами. И да, скорость при этом ощутимо падает, будьте к этому готовы.

[lsoft]

Да, на данный момент, чтобы просто адаптировать мою (оч простую) реализацию СГ для линейного случая на нелинейный случай, мне надо выбирать размер шага (alphai в документе, на который я ссылаюсь).
Я всегда готов почитать литературу насчет выбора шага, только проблема в том, что я даже не могу составить запрос в гугле, потому что не разбираюсь в этой области. Прошу порекомендовать какой-либо простой алгоритм, но при этом сложнее "возьмите любую константу и используйте ее" :)

Также я не понял, почему Вы решили, что "теперь уже функции одной переменной". Вовсе нет, переменных все еще осталось много, просто функция нелинейная z=f(x,y,a,b,c,d...)

(спасибо что уделяете мне время)


(в линейном случае шаг определяется однозначно, поэтому произвола нет, в нелинейном случае - это магия, или по научному эвристика :) )

[iifat]

lsoft в сообщении #940760 писал(а):

почему Вы решили, что "теперь уже функции одной переменной"

Именно одной — $\alpha$. Смотрите, мы фиксировали точку и направление. Теперь все переменные, а значит и функция, определяются этой самой $\alpha$.
Задача называется численный поиск экстремума функции одной переменной. Гугл находит 52 тысячи результатов Вот первый. Возможно, дальше есть получше.

[lsoft]

мысль понял... поизучаю тему...

спасибо!

[iifat]

Удачи!

[lsoft]

Итак, вроде сделал нелинейный CG. На паре тестовых функций работает нормально.
Понятно, что там еще сидят баги на тему numerical stability, и другие, но надо попробовать двигаться дальше.

теперь встает в полный рост актуальный вопрос - как CG внедряется в backpropagation. Если рассмотреть Online BP (то есть веса MLP изменяются на каждом обучающем примере), то получается вот что: проход в прямом направлении, прогон результатов сети через функцию ошибки (logloss, rmse, half squared euclidian distance), полученную ошибку гоним в обратном направлении и для каждого веса каждого нейрона получаем delta-W.
я так понимаю, это как раз градиент. а оптимизируемая функция - это функция от (обучающего примера, конфигурации сети, функции активации нейрона, и функции ошибки).
как внедрить CG в эту конструкцию мне непонятно. интересно есть ли люди, которые делали что-то подобное...