Проблема локальных минимумов

[yanchick]

Доброго времени суток всем. Решаю задачу обучения нейронной сети. При обучении столкнулся с проблемой локальных минимумов. Побывал следующие алгоритмы: обратное распространение, обратное распространение с моментом.Также побывал интерпретировать задачу обучения как задачу глобальной минимизации функции многих переменных с использованием модификации алгоритма Ньютона и алгоритмом Левенберга. При всём выше перечисленном сталкиваюсь с проблемой локальных минимумов. Я точно знаю что сеть можно обучить на более эффективную работу( по критерию среднеквадратичной ошибки). Сейчас на повестке дня стоит метод "имитации отжига". Но что-то мне подсказывает что есть другие, более продуктивные, методы. Подскажите, уважаемые форумчане, на что еще можно обратить свой взор. Заранее благодарен.

[PAV]

Чтобы выскочить из локального минимума, нужно что-то пошевелить. Можно взять найденные переметры и немного поменять их случайным образом (т.е. по сути - сделать шаг из минимума в случайном направлении). Можно взять подмножество обучающих примеров, либо же как более мягкий вариант - перевзвесить их. Например, можно целенаправленно понизить вес ровно тем примерам, которые мешают выскочить из данного минимума. После нескольких шагов, когда процедура достаточно от него отойдет, можно обратно вернуть их на место.

Можно также попробовать в принципе сделать задачу более гладкой. Например, оценивать качество не по значению в одной точке, а по среднему значению целевого функционала в некоторой окрестности точки.

[yanchick]

PAV в сообщении #343740 писал(а):

Чтобы выскочить из локального минимума, нужно что-то пошевелить. Можно взять найденные переметры и немного поменять их случайным образом (т.е. по сути - сделать шаг из минимума в случайном направлении).

Спасибо попробую.

PAV писал(а):

Можно также попробовать в принципе сделать задачу более гладкой. Например, оценивать качество не по значению в одной точке, а по среднему значению целевого функционала в некоторой окрестности точки.

Качество итак оценивается по всей выборке. Берется среднее значение по эпохе.

[PAV]

yanchick в сообщении #343772 писал(а):

Качество итак оценивается по всей выборке. Берется среднее значение по эпохе.

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

[Maslov]

yanchick в сообщении #343725 писал(а):

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

Ну так что ж тут удивительного? Эти методы ищут именно локальный экстремум.

Ещё можно пообучать из других начальных состояний, т.е. повыбирать разные начальные распределения весов. Но вообще, проблема поиска глобального оптимума в общем случае относится к разряду неразрешимых, и универсальных подходов здесь нет :)

yanchick в сообщении #343725 писал(а):

Я точно знаю что сеть можно обучить на более эффективную работу( по критерию среднеквадратичной ошибки).

Если не секрет, откуда у Вас такая информация? Есть "правильный" набор весов, обеспечивающий глобальный минимум?

[yanchick]

Maslov в сообщении #343798 писал(а):

Если не секрет, откуда у Вас такая информация? Есть "правильный" набор весов, обеспечивающий глобальный минимум?

С использованием MatLab я сеть с аналогичной структурой обучал на необходимую точность. Плюс используется почти азбучный пример, который рассматривается в многих источниках(интерполяция синус). В идеале я должен получить свой программный пакет для дальнейших исследований. До сегодняшнего дня использовал Neural Network Toolbox, но уткнулся в ряд его ограничений. Да и просто хочу написать свое.

-- Ср авг 11, 2010 21:14:55 --

Maslov в сообщении #343798 писал(а):

Ну так что ж тут удивительного? Эти методы ищут именно локальный экстремум.

Ещё можно пообучать из других начальных состояний, т.е. повыбирать разные начальные распределения весов. Но вообще, проблема поиска глобального оптимума в общем случае относится к разряду неразрешимых, и универсальных подходов здесь нет :)

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

[Maslov]

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

Синусу НС довольно хорошо должна обучаться, если, конечно, в реализации не напутали.

Кстати, кроме проблемы локальных оптимумов, при оптимизации довольно часто встречается проблема оврагов, т.е. идём по дну оврага в сторону экстремума, но очень-очень медленно. У Вас СКО совсем не уменьшается?

yanchick в сообщении #343832 писал(а):

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

А где у Вас тут квадратичная функция?

[alekcey]

yanchick в сообщении #343725 писал(а):

...Решаю задачу обучения нейронной сети. При обучении столкнулся с проблемой локальных минимумов. .. и алгоритма Ньютона и алгоритмом Левенберга...

Признаюсь, непонятно мне, что Вы обучаете и с какой целью. Реагирую только на слова о локальных минимумах, ну, и на алгоритмы Ньютона и Левенберга. Непонятно и какая проблема связана с минимумами. Имеются реализованные алгоритмы, например, в приложении к Мэпл13 на сайте предлагается бесплатный пакет Сергея Моисеева. Этот пакет решает практически весь спектр задач оптимизации и просто великолепно справляется с решением систем нелинейных уравнений. При этом он не использует ни первых, ни, тем более, вторых производных. Лично предлагал ему примеры, которые просто нереальны для последней версии любого матпакета. Не владею в достаточной мере Мэплом, а то бы протестировал на пакете и краевую задачу для ОДУ. (По логике, для него краевые задачи для ОДУ должны быть не сложнее, чем СНУ небольшой размерности.)
Если говорить о прохождении локальных экстремумов, то есть метод Драгилева, для которого требуются первые производные, но он не реагирует на обращение в о определителя Якоби, а потому спокойно проходит глобальные и локальные экстремумы. Затруднением для него являются только точки самопересечения, поскольку метод использует решение автономной системы, а для неё это особые точки. Но затруднением не фатальным при некоторых приёмах программирования…

[yanchick]

Maslov в сообщении #343842 писал(а):

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

На входе величина в диапазоне $x \subset [0; \pi ]$, ны выходе должен быть $sin(x)$. Сеть гарантированная рабочая. В пакете MatLab NeuralNetwork Toolbox она обучается на эту задачу.

Maslov в сообщении #343842 писал(а):

Кстати, кроме проблемы локальных оптимумов, при оптимизации довольно часто встречается проблема оврагов, т.е. идём по дну оврага в сторону экстремума, но очень-очень медленно. У Вас СКО совсем не уменьшается?

Оно в течении нескольких итераций(где то за 20-50) уменьшается, а потом прыгает вокруг определенного значения. Как я предполагаю это точка локального минимума.

Maslov в сообщении #343842 писал(а):

А где у Вас тут квадратичная функция?

Ну как же функция которую я минимизирую имеет вид $E=\frac{1}{N}\sum_1^{N}(y_i-d_i)^2$, где $y$- выход сети, $d$- цель из обучающей выборки.

[R.Deyanov]

по поводу выхода из точки локального минимума(т.л.м.) можете посмотреть здесь в разделах: программы, потенциал Морза, задача Томсона.
Если в двух словах: к т.л.м. подвешивается выпуклая ф-ия(типа чашки верх дном), далее решается нелинейное уравнение пересечения этой ф-ии и исходной - таким образом выходим из области притяжения т.л.м. Далее стартуем из найденного решения нелинейного уравнения любым методом поиска т.л.м.
Предложил алгоритм и реализовал его программно еще в начале 80-х. Могу сразу предупредить вопрос: решение нелинейного скалярного(не системы) уравнения(с сотнями неизвестных) не менее проблемно, но решаемо.
Если есть у кого интересные задачи(практические) по этому поводу пишите в личку.

С уважением, Рамиль.