2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Понимание conjugate gradients в контексте обучения MLP
Сообщение05.12.2014, 10:08 


05/12/14
12
Здравствуйте.
У меня реализован алгоритм 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. В наивной реализации мы просто вычитаем накопившуюся ошибку из веса и переходим к следующей итерации. А тут как поступить?

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

 Профиль  
                  
 
 Re: Понимание conjugate gradients в контексте обучения MLP
Сообщение05.12.2014, 13:27 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Понимание conjugate gradients в контексте обучения MLP
Сообщение05.12.2014, 14:08 


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

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

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

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

 Профиль  
                  
 
 Re: Понимание conjugate gradients в контексте обучения MLP
Сообщение05.12.2014, 16:56 
Заслуженный участник


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

-- 06.12.2014, 01:07 --

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

 Профиль  
                  
 
 Re: Понимание conjugate gradients в контексте обучения MLP
Сообщение05.12.2014, 17:45 


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

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

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


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

 Профиль  
                  
 
 Re: Понимание conjugate gradients в контексте обучения MLP
Сообщение05.12.2014, 18:38 
Заслуженный участник


16/02/13
4105
Владивосток
lsoft в сообщении #940760 писал(а):
почему Вы решили, что "теперь уже функции одной переменной"
Именно одной — $\alpha$. Смотрите, мы фиксировали точку и направление. Теперь все переменные, а значит и функция, определяются этой самой $\alpha$.
Задача называется численный поиск экстремума функции одной переменной. Гугл находит 52 тысячи результатов :wink: Вот первый. Возможно, дальше есть получше.

 Профиль  
                  
 
 Re: Понимание conjugate gradients в контексте обучения MLP
Сообщение05.12.2014, 18:56 


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

спасибо!

 Профиль  
                  
 
 Re: Понимание conjugate gradients в контексте обучения MLP
Сообщение05.12.2014, 19:43 
Заслуженный участник


16/02/13
4105
Владивосток
Удачи!

 Профиль  
                  
 
 Re: Понимание conjugate gradients в контексте обучения MLP
Сообщение09.12.2014, 14:40 


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group