У вас очень выгодная позиция: вы можете говорить всё, что в голову придёт, а мне приходится подробно объяснять.
Именно. Я могу просто добавить операцию обновления очереди и получить начальные точки такие же или лучше, и улучшить результат еще на десять процентов. Не прибегая к предположениям о бассейнах и их позициях, о том что точки в каком-то месте неизвестной (все еще) функции лучше\хуже остальных. Достаточно предположений:
Что градиентный спуск точки с меньшей ошибкой приводят к еще меньшей ошибке.
Считать изменение положения точки на плато\в локальном минимуме смысла нет.
Хотя результат уже довольно интересен, особенно если сравнить с Mutistart (100 точек по 20000 шагов).
Конечно, я могу добавить к своему получившемуся алгоритму все о чем вы говорите - и байесовскую оптимизацию гиперпараметров, и какие-то иные предположения "о бассейнах". Но это не строгие предположения, и я могу просто "отсечь" части с глобальным оптимумом. Благодаря "очевидному ландшафту функции с известными особенностями", как вы говорили. И не получить решения в принципе.
Поэтому и не рекомендуется применять подобные техники. Но мне ничто не запрещает прикрутить все это к имеющемуся алгоритму. И быстро и эффектно делать вид оптимального поиска глобального минимума :).
У вас в алгоритме каждая точка обрабатывается до тех пор, пока не выполнится одно из условий:
Где это написано? Очередь всегда есть, с некоторым количеством точек.
а потом смотреть, какие точки собираются в кучку после нескольких шагов
Вот в двух словах вы и определили, чем отличается мой алгоритм. Правильно, это оптимальный поиск. Без момента, "бассейнов" и прочего. Почему? потому что с точки зрения анализа алгоритмов и функций по N точкам нет никаких
особенности ландшафта
Определяя эти бассейны, мы не можем сказать, что ДА, МЫ ВЗЯЛИ 10 ТОЧЕК, и ВРОДЕ ОНИ СТЯГИВАЮТСЯ, И ЭТО БАССЕЙН. И ВСЕ ТОЧКИ ТУТ - БЕСПОЛЕЗНЫ. То же самое с моментом и остальными оптимизациями.
(Кстати, multistart matlab-a находит глобальный минимум предложенной функции 0% раз )
Спасибо за то, что привели правильное название - глобальная оптимизация.
Кстати, мой алгоритм чуть ли не в 1% лучших (я могу решить Damavandi за 2000 измерений ошибки в 76% случаев)
Кстати, представленная тестовая функция похожа на смесь самых плохо решаемых
А очередь как помогает?
Уже приводил пример, даже понятную аналогию давал
при нормальном распределении размеров ошибки случайно выбранных точек, если мы возьмем точки с наименьшим отклонением от искомого минимума, то сможем проверить большее количество локальных минимумов и быстрее найдем минимум глобальный
Ну хорошо, а в чём сложность функции-то? Ярко выраженные локальные экстремумы, градиент везде хороший. Если попал в окрестность — гарантированно попадёшь в локальный оптимум. Извилистых оврагов нет, седловых точек мало.
Я проверяю эффективность поиска глобального оптимума, а не настройки размера шага. 1200 локальных минимумов против 1 глобального в интервале [[-100;100],[-100;100]]
Ну хорошо, а чем очередь с приоритетами помогает? Всё равно нужно для каждой точки довести градиентный спуск до конца. Какая разница, в каком порядке это делать? А других эвристик (вернее, оптимизаций) по сравнению с multistart тут и нет.
Ну, если без определения оптимальности - при нормальном распределении размеров ошибки случайно выбранных точек, если мы возьмем точки с наименьшим отклонением от искомого минимума, то сможем проверить большее количество локальных минимумов и быстрее найдем минимум глобальный
Ну как же не задумывается, если для методов вроде вашего целое название придумали? Вы просто не интересовались, наверное.
Погуглил и глобальную оптимизацию, и мультистарт, и стохаотическую глобальную оптимизацию - ничего не нашел ).
Еще раз посмотрите на тестовые функции в этом репозитарии и тестовую функцию в статье 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 запусков, сведенные в таблицу.
Или, функция имеющая нулевой градиент при 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 )
Да, добавление момента это здорово, но не оптимально. К сожалению представленный бенчмарк гораздо проще, чем имеющаяся тестовая функция.
Спасибо за статью, сейчас как раз пишу то же самое, только в виде генератора ). Смущает получившаяся у вас скорость, всего 30 тысяч запросов в секунду. Это следствие следствие сложной обработки запроса сервером?
А до 2030 мы будем печатать новости об этом каждый день.
Так а смысл в этом какой? Они планируют напечатать больше, чем Китай? Или на открывать фирм с превосходством по технологиям? (давайте не будем возвращаться к сравнениям intel/arm/risc-v)
Или шахматы и эти, ИИ, много очень процессоров потребляют? В эпоху наступающей сингулярности? )
что AI-системы на самом деле не могут «думать», они выдают только то, чему их учили, поэтому часто делают вещи, которые кажутся людям невероятно глупыми.
Только планирование, планирование и оценка. При помощи триллионов синапсов.
а потом такое ощущение, что мне даже немного делают одолжение. Один очень сильный по резюме кандидат написал — «…я попозже, когда будет время, рассмотрю ваше предложение и отвечу…».
и что в этом не так? Вы затмеваете IBM, Google и Microsoft вместе взятые? Или правите XPath сервисов для парсинга? )
Неудовлетворительные обновления градиента политики. Например, очень малые шаги, когда зависают в локальном оптимуме, или большие шаги, из-за которых упускают наибольшее вознаграждение.
Беда, правда, проще использовать N градиентных спусков с различными начальными точками, чем пытаться как-то и делать небольшие шаги, и не ждать целую вечность. Например, А* с миллионом начальных точек и градиентным спуском только по наиболее полезным. Эдакий аналог дождя для трехмерной поверхности (правда, работающий и для N-мерных функций). Это вполне по силам даже SIMD, не говоря уже про GPU ).
Алгоритмы, основанные на аппроксимации функции полезности, систематически выбирают действия с завышенной полезностью.
Зачем пытаться превратить эвристики, оптимальные для А* в неоптимальные дабы решить проблему "лишних миллионов шагов". Потеря оптимальности для поиска с эвристикой может вылиться в крайне субоптимальные решения.
Будет время, напишу статью и покажу что получается в таком случае. Благо, подобный алгоритм будет примерно в 10^6 раз менее подвержен застреванию в локальном, а не глобальном оптимуме, а с точки зрения количества вычислений может быть примерно сопоставим с классическим градиентным спуском (спасибо эвристикам).
Ну формат статьи такой. Группа СуперКриптографов собирается в чате и бесплатно клепает сайтики для Ужасного Darknet-а, чтобы противостоять еще более ужасным госструктурам.
Эм, повторю вопрос - эмуляция квантового отжига на GPU и взлом RSA у CAS. Что за Цикада-то?
как раз в 2014 году АНБ и ВМФ США стали публиковать криптографические задачи в сети по образцу «Цикады» для поиска потенциальных сотрудников в области криптографии
О боже, это у которых президент скатился по трапу?
И зачем нужны криптоаналитики, если есть DreamCoder и пара экзафлопс?
Ого, подозрительно напоминает работу Китайской академии наук, вышедшую год-два назад. Которая видимо поспевает за Топ Технологиями фирмы DeepMind xD.
Здорово, жалко разделить на:
1) Описательную часть (Что на изображении)
2) Текст в онтологии (с coreference и прочим), Q&A по карточкам
3) цикл с дополнением информацией о свойствах и их изменении на основе известных онтологий.
Ну и наконец Cause-and-effect или Q&A по получившемуся дереву или любое другое преобразование). (Abstraction And Reasoning в стиле DreamCoder-a)
Так как делают сейчас - трансформеры получаются слишком уж избыточными )
Ого, он наверное какие-нибудь функции будет выполнять? И с контекстом? ))
Ладно, тем более это не очередной идиот, а настоящий Король ИИ, видимо.
Хотя, с учетом того, что даже со Сферой Миколова гении ИИ так и не научились читать (кроме одного Китайца в Швейцарии, конечно)
Интересно, а DreamCoder может перебирать примитивы обработки текста и последовательностей эффективней чем очередная мечта вечнурного капитализма? )
Именно. Я могу просто добавить операцию обновления очереди и получить начальные точки такие же или лучше, и улучшить результат еще на десять процентов.
Не прибегая к предположениям о бассейнах и их позициях, о том что точки в каком-то месте неизвестной (все еще) функции лучше\хуже остальных.
Достаточно предположений:
Что градиентный спуск точки с меньшей ошибкой приводят к еще меньшей ошибке.
Считать изменение положения точки на плато\в локальном минимуме смысла нет.
Хотя результат уже довольно интересен, особенно если сравнить с Mutistart (100 точек по 20000 шагов).
Конечно, я могу добавить к своему получившемуся алгоритму все о чем вы говорите - и байесовскую оптимизацию гиперпараметров, и какие-то иные предположения "о бассейнах".
Но это не строгие предположения, и я могу просто "отсечь" части с глобальным оптимумом. Благодаря "очевидному ландшафту функции с известными особенностями", как вы говорили. И не получить решения в принципе.
Поэтому и не рекомендуется применять подобные техники. Но мне ничто не запрещает прикрутить все это к имеющемуся алгоритму. И быстро и эффектно делать вид оптимального поиска глобального минимума :).
Где это написано? Очередь всегда есть, с некоторым количеством точек.
Вот в двух словах вы и определили, чем отличается мой алгоритм. Правильно, это оптимальный поиск.
Без момента, "бассейнов" и прочего.
Почему? потому что с точки зрения анализа алгоритмов и функций по 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
Кстати, представленная тестовая функция похожа на смесь самых плохо решаемых
Уже приводил пример, даже понятную аналогию давал
при нормальном распределении размеров ошибки случайно выбранных точек, если мы возьмем точки с наименьшим отклонением от искомого минимума, то сможем проверить большее количество локальных минимумов и быстрее найдем минимум глобальный
Я проверяю эффективность поиска глобального оптимума, а не настройки размера шага. 1200 локальных минимумов против 1 глобального в интервале [[-100;100],[-100;100]]
Ну, если без определения оптимальности - при нормальном распределении размеров ошибки случайно выбранных точек, если мы возьмем точки с наименьшим отклонением от искомого минимума, то сможем проверить большее количество локальных минимумов и быстрее найдем минимум глобальный
Погуглил и глобальную оптимизацию, и мультистарт, и стохаотическую глобальную оптимизацию - ничего не нашел ).
Еще раз посмотрите на тестовые функции в этом репозитарии и тестовую функцию в статье
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 и global search скорее всего где-то между 100 запусками градиентного спуска и перезапуском при достижении минимума. Ничто не мешает добавить и настройку размера шагов, и прочие полезные вещи. Только с учетом что они тоже должны быть оптимальны.
В статье же объяснено почему я отказался от свистелок и перделок в виде обучения с моментом, чтобы получить оптимальные градиентные спуски (пусть даже в некоторой области с локальным минимумом).
Так же добавил результаты 300 запусков, сведенные в таблицу.
Хабр увы не позволяет редактировать статьи.
Очень сильное, учитывая что
Или, функция имеющая нулевой градиент при 99.9925% значениях параметров :)
Да, я специально взял "простейший пример", с нулевым градиентом. И потом добавил 360000 локальных минимумов :)
Или примерно
2000*2000*9/(10*10) = 40000*9=360000локальных минимумов в диапазоне [[-1000;1000],[-1000;1000]]
Как видим, у нас получилось гигантское количество локальных минимумов, но это не из-за ошибок в скрипте. Видимо, начальные точки по нескольку раз приводили в один и тот же локальный минимум
Даже с локальными минимумами 5 из 5 запусков окончились в Глобальном минимуме.
ну и ответы:
в 99.9925% обычный градиентный спуск не покажет вообще никаких результатов. (100 запусков из 100 закончились ничем, и я использовал в 20 раз больше вызовов ObjectiveFunction) (Плато или тысячи\миллионы локальных минимумов)
С функциями с большей размерностью будет то же самое, только в большем пространстве
Нейросети? Нет, зачем? Есть какая-то разница? ) Поменяются определения оптимальности? ) Градиентный спуск применяется не только в обучении нейронных сетей, но и для различных видов регрессии, и даже в системах машинного зрения
слишком сложный сарказм. Есть же PhD vacancies )
Да, добавление момента это здорово, но не оптимально.
К сожалению представленный бенчмарк гораздо проще, чем имеющаяся тестовая функция.
Ну а зачем, если можно получать гранты в ЕС или Китае, те же суммы только в долларах? (Даже условия похожи - работа в институте или частная фирма).
Тем более инновации обычно очень дорого ).
Вот и все, поэтому неосознанно большинство читателей рассматривают подобные публикации как Газлайтинг(Gaslighting).
Принеси нам, холоп, инноваций, да подешевле.
Спасибо за статью, сейчас как раз пишу то же самое, только в виде генератора ).
Смущает получившаяся у вас скорость, всего 30 тысяч запросов в секунду.
Это следствие следствие сложной обработки запроса сервером?
AI ЛОЛ
А до 2030 мы будем печатать новости об этом каждый день.
Так а смысл в этом какой?
Они планируют напечатать больше, чем Китай?
Или на открывать фирм с превосходством по технологиям? (давайте не будем возвращаться к сравнениям intel/arm/risc-v)
Или шахматы и эти, ИИ, много очень процессоров потребляют? В эпоху наступающей сингулярности? )
Только планирование, планирование и оценка. При помощи триллионов синапсов.
и что в этом не так? Вы затмеваете IBM, Google и Microsoft вместе взятые? Или правите XPath сервисов для парсинга? )
Беда, правда, проще использовать N градиентных спусков с различными начальными точками, чем пытаться как-то и делать небольшие шаги, и не ждать целую вечность. Например, А* с миллионом начальных точек и градиентным спуском только по наиболее полезным. Эдакий аналог дождя для трехмерной поверхности (правда, работающий и для N-мерных функций). Это вполне по силам даже SIMD, не говоря уже про GPU ).
Зачем пытаться превратить эвристики, оптимальные для А* в неоптимальные дабы решить проблему "лишних миллионов шагов". Потеря оптимальности для поиска с эвристикой может вылиться в крайне субоптимальные решения.
Будет время, напишу статью и покажу что получается в таком случае.
Благо, подобный алгоритм будет примерно в 10^6 раз менее подвержен застреванию в локальном, а не глобальном оптимуме, а с точки зрения количества вычислений может быть примерно сопоставим с классическим градиентным спуском (спасибо эвристикам).
Вот так за пару лет вы пришли к тому, что называется
ChatGPTМарусяGPT? )При экономии в
Вообще странно, что они лепят в кучу и компьютерное зрение на IBM PC, и технологические процессы.
Ненависть зашкаливает. После вузов из топ-500 тяжело проходить курсы? )
Ну формат статьи такой.
Группа СуперКриптографов собирается в чате и бесплатно клепает сайтики для Ужасного Darknet-а, чтобы противостоять еще более ужасным госструктурам.
Бесплатно.
А почему вы минусуете-то?
Эм, повторю вопрос - эмуляция квантового отжига на GPU и взлом RSA у CAS.
Что за Цикада-то?
О боже, это у которых президент скатился по трапу?
И зачем нужны криптоаналитики, если есть DreamCoder и пара экзафлопс?