Комментарии 15
в миллионы раз менее подверженная застреванию в локальном оптимуме, чем существующие
Это сильное заявление, хотелось бы какое-нибудь обоснование (более серьёзное, чем десять примеров).
В 10 запусках из 10 был получен глобальный минимум
Что были за функции? Какая у них размерность? И какие результаты показывать обычный градиентный спуск? А что будет если мы увеличим размерность на порядок? А вы пробовали обучать нейросети из той статьи, которая вам так не понравилась?
At first I was like:
модификация алгоритма градиентного спуска, в миллионы раз менее подверженная застреванию в локальном оптимуме, чем существующие
But then,
В 10 запусках из 10…
Не требует доказательств, что ...
Похоже что вы таки решили проблему поиска глобального минимума и знатно подняли качество современных публикаций на тему проблем машинного обучения, это достойно уважения!
Рекомендую вам слать статью на NeurlIPS, дедлайн подачи в мае месяце.
Мб прогнать хотя бы на этом: https://pypi.org/project/OptimizationTestFunctions/ и сравнить с популярными решениями?
Хабр увы не позволяет редактировать статьи.
Это сильное заявление
Очень сильное, учитывая что
print(objective_function([10,10])==objective_function([100,100]))
True
Или, функция имеющая нулевой градиент при 99.9925% значениях параметров :)
Да, я специально взял "простейший пример", с нулевым градиентом. И потом добавил 360000 локальных минимумов :)
Или примерно 2000*2000*9/(10*10) = 40000*9=360000
локальных минимумов в диапазоне [[-1000;1000],[-1000;1000]]
z = -(4*np.exp(-(vector[0]-4)**2 - (vector[1]-4)**2)+2*np.exp(-(vector[0]-2)**2 - (vector[1]-2)**2))+4+0.2*np.sin(vector[0])+0.2*np.cos(vector[1])
Cost function calls for initialization:
1000001
Minimum error:
-0.009953628971875753
Result point:
[3.855589965005124, 4.428819432720052]
Initial points:
1000000
Total steps:
6778543
Maximum steps:
100000000
Cost function calls:
28113741
Local minimums queue len:
6778111
Raw results:
Как видим, у нас получилось гигантское количество локальных минимумов, но это не из-за ошибок в скрипте. Видимо, начальные точки по нескольку раз приводили в один и тот же локальный минимум
Даже с локальными минимумами 5 из 5 запусков окончились в Глобальном минимуме.
ну и ответы:
в 99.9925% обычный градиентный спуск не покажет вообще никаких результатов. (100 запусков из 100 закончились ничем, и я использовал в 20 раз больше вызовов ObjectiveFunction) (Плато или тысячи\миллионы локальных минимумов)
С функциями с большей размерностью будет то же самое, только в большем пространстве
Нейросети? Нет, зачем? Есть какая-то разница? ) Поменяются определения оптимальности? ) Градиентный спуск применяется не только в обучении нейронных сетей, но и для различных видов регрессии, и даже в системах машинного зрения
слишком сложный сарказм. Есть же PhD vacancies )
Да, добавление момента это здорово, но не оптимально.
К сожалению представленный бенчмарк гораздо проще, чем имеющаяся тестовая функция.
в миллионы раз менее подверженная застреванию в локальном оптимуме, чем существующие
Держать в памяти миллион точек — не очень-то практично. Для сложных нейронных сетей и пара точек не всегда в памяти помещается. :)
Насколько я вижу, идея метода — это запуск градиентного спуска для разных начальных точек (то есть, это multistart optimization), а очередь нужна только для оптимизации вычислений.
https://arxiv.org/abs/1401.3894 — вот, кстати, пример метода с multi-start, в котором есть множество алгоритмов локального поиска и делается выбор, каким искать.
Насчёт эвристики с выбором лучшего. Вот тут как раз не факт, что это как-то ускоряет поиск. Всё зависит от ландшафта функции. Может там всё усеяно седловыми точками. Тогда градиентный спуск будет всегда застревать и нужно взять что-то другое.
Мб прогнать хотя бы на этом: https://pypi.org/project/OptimizationTestFunctions/ и сравнить с популярными решениями?
Еще раз посмотрите на тестовые функции в этом репозитарии и тестовую функцию в статье
https://www.google.ru/search?q=z+%3D+-(4exp%28-%28x-4%29%5E2+-+%28y-4%29%5E2%29%2B2exp%28-%28x-2%29%5E2+-+%28y-2%29%5E2%29%29%2B4%2B0.2sin%28x%29%2B0.2cos%28y%29&newwindow=1&sxsrf=AJOqlzWlG-mGPnc4Mw7clYhca4XRAHNkhw%3A1678092860366&source=hp&ei=PKoFZKjIE4PprgSCwJaIAw&iflsig=AK50M_UAAAAAZAW4TFjsO9mdlcBJdARHrvUAkbCPrmcE&oq=z&gs_lcp=Cgdnd3Mtd2l6EAEYATIECCMQJzIECCMQJzIECCMQJzIICAAQgAQQsQMyCAgAEIAEELEDMggIABCABBCxAzIICC4QgAQQ1AIyCAgAEIAEELEDMggIABCABBCxAzIICAAQgAQQsQNQAFgAYJ4XaABwAHgAgAGCAYgBggGSAQMwLjGYAQCgAQE&sclient=gws-wiz
Не забудьте выставить диапазоны x,y -100;100
Похоже что вы таки решили проблему поиска глобального минимума и знатно подняли качество современных публикаций на тему проблем машинного обучения, это достойно уважения!
Увы, не смог оценить сарказм,
Насчёт эвристики с выбором лучшего. Вот тут как раз не факт, что это как-то ускоряет поиск.
Факт. Эвристики и оптимальный поиск. Просто никто не думает о эвристиках в разрезе простых алгоритмов (вроде градиентного спуска).
вот, кстати, пример метода с multi-start, в котором есть множество алгоритмов локального поиска и делается выбор, каким искать.
Ну, multi-start и global search скорее всего где-то между 100 запусками градиентного спуска и перезапуском при достижении минимума. Ничто не мешает добавить и настройку размера шагов, и прочие полезные вещи. Только с учетом что они тоже должны быть оптимальны.
Это сильное заявление, хотелось бы какое-нибудь обоснование (более серьёзное, чем десять примеров).
В статье же объяснено почему я отказался от свистелок и перделок в виде обучения с моментом, чтобы получить оптимальные градиентные спуски (пусть даже в некоторой области с локальным минимумом).
Так же добавил результаты 300 запусков, сведенные в таблицу.
На телефоне эта монструозная ссылка бесполезна. :) Сэкономлю немного времени другим читателям и добавлю картинки.
Еще раз посмотрите на тестовые функции в этом репозитарии и тестовую функцию в статье
Ну хорошо, а в чём сложность функции-то? Ярко выраженные локальные экстремумы, градиент везде хороший. Если попал в окрестность — гарантированно попадёшь в локальный оптимум. Извилистых оврагов нет, седловых точек мало.
А вот в том бенчмарке каждая функция в чём-то особенная. Например, функция Розенброка считается трудной для поиска глобального минимума из-за плоского извилистого оврага.
Если сравнивать методы оптимизации, то на каком-то бенчмарке, а не на единственной функции. Ну и раз уж у вас метод глобальной оптимизации, то и сравнивать стоит с методами глобальной оптимизации.
Факт. Эвристики и оптимальный поиск.
Ну хорошо, а чем очередь с приоритетами помогает? Всё равно нужно для каждой точки довести градиентный спуск до конца. Какая разница, в каком порядке это делать? А других эвристик (вернее, оптимизаций) по сравнению с multistart тут и нет.
Просто никто не думает о эвристиках в разрезе простых алгоритмов (вроде градиентного спуска).
Ну как же не задумывается, если для методов вроде вашего целое название придумали? Вы просто не интересовались, наверное.
Вот кусочек из статьи 1985 года:
A.H.G. Rinnooy Ran et al. A STOCHASTIC APPROACH TO GLOBAL OPTIMIZATION
Похоже, правда? Есть много статей — и старых, и новых. Просто погуглите.
Не требует доказательств, что шанс застрять в локальном оптимуме меньше в N раз, где N - количество начальных точек.
Не очень понятно, как вы это посчитали.
Пусть вероятность застрять в локальном оптимуме равна 2/3.
Тогда если мы делаем N=2 независимые попытки, получаем, что вероятность застрять в обеих равна 2/3 × 2/3 = 4/9. Это меньше, чем исходная вероятность, но не в N раз (иначе была бы 1/3=3/9).
Ну хорошо, а в чём сложность функции-то? Ярко выраженные локальные экстремумы, градиент везде хороший. Если попал в окрестность — гарантированно попадёшь в локальный оптимум. Извилистых оврагов нет, седловых точек мало.
Я проверяю эффективность поиска глобального оптимума, а не настройки размера шага. 1200 локальных минимумов против 1 глобального в интервале [[-100;100],[-100;100]]
Ну хорошо, а чем очередь с приоритетами помогает? Всё равно нужно для каждой точки довести градиентный спуск до конца. Какая разница, в каком порядке это делать? А других эвристик (вернее, оптимизаций) по сравнению с multistart тут и нет.
Ну, если без определения оптимальности - при нормальном распределении размеров ошибки случайно выбранных точек, если мы возьмем точки с наименьшим отклонением от искомого минимума, то сможем проверить большее количество локальных минимумов и быстрее найдем минимум глобальный
Ну как же не задумывается, если для методов вроде вашего целое название придумали? Вы просто не интересовались, наверное.
Погуглил и глобальную оптимизацию, и мультистарт, и стохаотическую глобальную оптимизацию - ничего не нашел ).
Я проверяю эффективность поиска глобального оптимума, а не настройки размера шага.
Посмотрите, пожалуйста, бенчмарк. Там почти половина функций мультимодальные. Если открыть репозиторий на GitHub, то там есть графики.
То, что вы подобрали функцию, на которой ваш конкретный алгоритм работает лучше какого-то другого алгоритма (из другого класса), называется в науке cherrypicking. Бенчмарк существует для того, чтобы можно было сравнивать методы оптимизации. Каждая функция там сложна в чём-то своём. Что толку от алгоритма, если на вашей функции он хорошо сходится, а на остальных нет?
Мы так долго спорим, что вы уже запустили бы давно. :)
1200 локальных минимумов против 1 глобального в интервале [[-100;100],[-100;100]]
Какая разница, сколько их? Главное — особенности ландшафта. Например, на функции Stairs из бенчмарка ваш алгоритм найдёт единственный минимум только если точка сразу в него попадёт, так как градиент почти всюду нулевой.
Ну, если без определения оптимальности - при нормальном распределении размеров ошибки случайно выбранных точек, если мы возьмем точки с наименьшим отклонением от искомого минимума, то сможем проверить большее количество локальных минимумов и быстрее найдем минимум глобальный
А очередь как помогает? Вы всё равно должны каждую точку довести до конца, чтоб убедиться, что это не глобальный минимум.
Погуглил и глобальную оптимизацию, и мультистарт, и стохаотическую глобальную оптимизацию - ничего не нашел ).
Я только в этих комментариях две статьи скинул. Второй 38 лет в этом году будет и она описывает ваш метод, который в то время был хорошо известен.
У нас какой-то разный гугл. Я просто пишу "multistart global optimization" и мне вываливает кучу статей. Это я даже в Google Scholar и arXiv не предлагал ещё. :)
Вот, первая попавшаяся же статья рассказывает, что ещё в 1970 году предложили модификацию вашего алгоритма. Почему нужно кидать много точек? Чтоб попасть в бассейны разных минимумов. И вот предложили сперва кидать равномерно, а потом смотреть, какие точки собираются в кучку после нескольких шагов. Если они собираются в кластер, то можно только одну точку рассматривать, а остальным назначить низкий приоритет. Этот метод был очень популярен в 70-х.
Вы безусловно молодец, что придумали multistart, но если вы почитаете какие-то обзоры, а лучше учебник по методам оптимизации, то это поможет вам не повторять то, что уже было изобретено.
Ну и насчёт машинного обучения. Multistart не используется не потому, что никто не додумался, а потому что это нерационально. Слишком много вычислительных ресурсов ради сомнительного улучшения. Методы второго порядка вот практически не используются для обучения нейронных сетей. Тут с Adam бы обучить.
Вы безусловно молодец, что придумали multistart
а потом смотреть, какие точки собираются в кучку после нескольких шагов
Вот в двух словах вы и определили, чем отличается мой алгоритм. Правильно, это оптимальный поиск.
Без момента, "бассейнов" и прочего.
Почему? потому что с точки зрения анализа алгоритмов и функций по N точкам нет никаких
особенности ландшафта
Определяя эти бассейны, мы не можем сказать, что ДА, МЫ ВЗЯЛИ 10 ТОЧЕК, и ВРОДЕ ОНИ СТЯГИВАЮТСЯ, И ЭТО БАССЕЙН. И ВСЕ ТОЧКИ ТУТ - БЕСПОЛЕЗНЫ.
То же самое с моментом и остальными оптимизациями.
(Кстати, multistart matlab-a находит глобальный минимум предложенной функции 0% раз )
Спасибо за то, что привели правильное название - глобальная оптимизация.
Кстати, мой алгоритм чуть ли не в 1% лучших (я могу решить Damavandi за 2000 измерений ошибки в 76% случаев)
https://infinity77.net/global_optimization/test_functions.html#test-functions-index
https://infinity77.net/global_optimization/test_functions_nd_D.html
Кстати, представленная тестовая функция похожа на смесь самых плохо решаемых
А очередь как помогает?
Уже приводил пример, даже понятную аналогию давал
при нормальном распределении размеров ошибки случайно выбранных точек, если мы возьмем точки с наименьшим отклонением от искомого минимума, то сможем проверить большее количество локальных минимумов и быстрее найдем минимум глобальный
Без момента, "бассейнов" и прочего.
Про момент я ничего не говорил, но бассейн у вас очень даже есть. :)
Бассейн локального минимума (attraction basin) — это такая область, что при выборе начальной точки из него, градиентный спуск попадёт именно в этот локальный минимум. Вы же не будете отрицать, что его нет. :)
Определяя эти бассейны, мы не можем сказать, что ДА, МЫ ВЗЯЛИ 10 ТОЧЕК, и ВРОДЕ ОНИ СТЯГИВАЮТСЯ, И ЭТО БАССЕЙН. И ВСЕ ТОЧКИ ТУТ - БЕСПОЛЕЗНЫ.
Прочитайте, пожалуйста, внимательно моё сообщение (а лучше исходную статью). Я нигде не говорил, что эти точки бесполезны, я говорил, что можно выбрать приоритеты. Можно рассматривать одну, если не позволяют вычислительные ресурсы.
Или, если позволяют, можно использовать эту информацию, чтобы выбрать другие точки. Равномерное распределение — это некоторое априорная оценка. Используя апостериорную информацию, можно улучшить оценку и добавить точки из других бассейнов.
Кстати, мой алгоритм чуть ли не в 1% лучших
Среди каких алгоритмов? :)
Если вы запустили его на бенчмарке, то приведите, пожалуйста, таблицу с параметрами запуска (область поиска и число точек), указанием количества вычислений функции и полученного значения. Тогда можно будет сравнить с другими методами оптимизациями.
А пока что это просто слова. Наука так не делается.
Кстати, multistart matlab-a находит глобальный минимум предложенной функции 0% раз
А для какого числа точек и какой области поиска вы запускали? :) Это точно было честное сравнение? А то если вы использовали 100 точек для своего алгоритма и 10 для матлаба, то сравнение некорректное.
А какие ещё методы глобальной оптимизации вы пробовали запускать?
Уже приводил пример, даже понятную аналогию давал
Похоже, вы не поняли вопрос. Попробую объяснить ещё раз.
У вас в алгоритме каждая точка обрабатывается до тех пор, пока не выполнится одно из условий:
Очередь пуста. Это значит, что все точки обработаны. А раз они все обработаны, то очередь не нужна, так как она влияет только на порядок обработки. То есть, это обычный multistart, хорошо известный метод.
Закончилось число итераций. А вот тут очередь помогает, так как хоть вы и не нашли минимум (иначе бы у вас была ситуация 1), но у вас будет лучшая на данный момент оценка. Но тут возникает риск, что если у вас много точек, то вы можете не дойти даже до локального минимума.
Если вы думаете, что никто не использует очередь с приоритетами при оптимизации, то вы ошибаетесь. Например, метод ветвей и границ основан на этом, да и другие методы оптимизации. Это не какое-то откровение. Часто очередь просто не упоминают, так как это просто деталь реализации.
(Кстати, вместо случайных начальных точек лучше использовать последовательности с низким расхождением. Например, последовательность Соболя.)
В байесовской оптимизации пошли ещё дальше и назначают приоритеты вообще всем точкам из области поиска. :)
Без обид, но давайте вы всё же что-то прочитаете. Потому что пересказывать всё очень утомительно. У вас очень выгодная позиция: вы можете говорить всё, что в голову придёт, а мне приходится подробно объяснять. Доказательствами вы, как я понимаю, себя не утруждаете, несмотря на то, что, например, с уменьшением шансов в N раз ошиблись.
Не знаю, насколько мне хватит мотивации. Честно говоря, для меня не очень важно, правы вы или нет. Если хотите, то можете считать свой алгоритм лучшим в мире, а меня частью заговора учёных, я не против. Если же хотите действительно разобраться, то попробуйте следовать научному подходу: подкреплять утверждения доказательствами или результатами воспроизводимых экспериментов.
У вас очень выгодная позиция: вы можете говорить всё, что в голову придёт, а мне приходится подробно объяснять.
Именно. Я могу просто добавить операцию обновления очереди и получить начальные точки такие же или лучше, и улучшить результат еще на десять процентов.
Не прибегая к предположениям о бассейнах и их позициях, о том что точки в каком-то месте неизвестной (все еще) функции лучше\хуже остальных.
Достаточно предположений:
Что градиентный спуск точки с меньшей ошибкой приводят к еще меньшей ошибке.
Считать изменение положения точки на плато\в локальном минимуме смысла нет.
Хотя результат уже довольно интересен, особенно если сравнить с Mutistart (100 точек по 20000 шагов).
Конечно, я могу добавить к своему получившемуся алгоритму все о чем вы говорите - и байесовскую оптимизацию гиперпараметров, и какие-то иные предположения "о бассейнах".
Но это не строгие предположения, и я могу просто "отсечь" части с глобальным оптимумом. Благодаря "очевидному ландшафту функции с известными особенностями", как вы говорили. И не получить решения в принципе.
Поэтому и не рекомендуется применять подобные техники. Но мне ничто не запрещает прикрутить все это к имеющемуся алгоритму. И быстро и эффектно делать вид оптимального поиска глобального минимума :).
У вас в алгоритме каждая точка обрабатывается до тех пор, пока не выполнится одно из условий:
Где это написано? Очередь всегда есть, с некоторым количеством точек.
Градиентный спуск, который мы заслужили