#bayesian #optimization #python #gaussianprocess

https://medium.com/@okanyenigun/step-by-step-guide-to-bayesian-optimization-a-python-based-approach-3558985c6818

#scipy #global #optimization #diogenes

Продолжаю работать над отборщиком признаков Диоген.

Столкнулcя с плохой работой методов глобальной оптимизации.

Кто работал с численной оптимизацией в сайпай, подскажите, что не так делаю. Пока кажется, что глобальная оптимизация из scipy не способна найти экстремум даже относительно простой гладкой функции 1 переменного. Хотелось бы что-то для поиска экстремума функции с очень высокой стоимостью оценки, в идеале когда можно задать бюджет поиска.

Попробую, наверное, запилить универсальный модуль с 3 опциями: гауссов процесс, бустинг с квантильной регрессей, и случайный поиск. Для первых двух будет какой-то начальный эквидистантный сэмплинг, чтоб было на чём учиться. Ну и плюс варианты выбора следующего кандидата, конечно же: expected improvement, ucb, etc.

Просто очень странно, что такого пакета ещё нет готовенького.

https://github.com/scipy/scipy/issues/19467

#global #optimization #benchmarks

Дали ссылку на такое вот иллюстрированное сравнение численных оптимизаторов

https://infinity77.net/go_2021/thebenchmarks.html

#optuna #dask #optimization #global

Разные способы заюзать Даск из Оптуны.

https://www.youtube.com/watch?v=euT6_h7iIBA

#skopt #optuna #global #optimization

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

The total number of evaluations, n_calls, are performed like the following. If x0 is provided but not y0, then the elements of x0 are first evaluated, followed by n_initial_points evaluations. Finally, n_calls - len(x0) - n_initial_points evaluations are made guided by the surrogate model. If x0 and y0 are both provided then n_initial_points evaluations are first made then n_calls - n_initial_points subsequent evaluations are made guided by the surrogate model.

initial_point_generatorstr, InitialPointGenerator instance, default: ‘random’
Sets a initial points generator. Can be either

"random" for uniform random numbers,
"sobol" for a Sobol sequence,
"halton" for a Halton sequence,
"hammersly" for a Hammersly sequence,
"lhs" for a latin hypercube sequence

Интересно будет увидеть её в сравнении. Ещё из интересных находок авторов: по умолчанию у них acquisition function не просто одна из известных EI, PI UCB/LCB, а т.н. gp_hedge, которая на каждом шаге сэмплит одну из указанных, по идее предлагая лучшее из 3 миров )

#gaussianprocess #optimization #global

Честно говоря, пока что кажется, что толку от "байесовости" гауссовых процессов в задаче глобальной оптимизации не так уж много. Да, рассчитывается неопределённость в каждой точке, ну так она:

1) зачастую крайне слабо отражает реальное положение относительно искомой функции
2) пропорциональна расстоянию до ближайших исследованных точек, так что её можно оценить и для "классических" ml алгосов.

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

#featureselection #hpo #hpt #global #optimization #optuna #scipy

Начинаю бенчить алгоритмы глобальной оптимизации на задаче определения лучшего количества фичей в машинном обучении. Для развитых современных сред это лишь частная подзадача: одномерная однокритериальная оптимизация в целочисленном домене без допограничений.

Мне надо знать, чем лучше всего искать лучшее количество фичей, хорошо ли с этим справляются существующие библиотеки, какие для них лучше использовать настройки, и надо ли пилить своё решение.

Общий сетап: есть 8 кривых зависимости CV метрики качества от nfeatures: выдуманные, синтетические по связям, синтетические по данным и связям, с шумом (как есть) и сглаженные. Количество фичей там посчитано от 150 до 570.

Замеряю вкупе по всем 8 задачам (в среднем):
1) найденный максимум на истинный максимум
2) среднее по верхнему 25% перцентилю найденных значений на истинный максимум
3) факт нахождения истинного максимум
4) итерацию нахождения истинного максимум к общему числу попыток
5) время поиска

С Оптуной уже есть интересные результаты. Почти всё богатство настроек там в т.н. сэмплерах, я насчитал 7, от случайного до генетиков и парценовского. У некоторых настроек просто тонна. Так как большинство сэмплеров в сравнении будут model-based (smbo), у них (в Оптуне) есть параметр n_startup_trials, т.е., сколько брать случайных точек для инициализации модели. Тут интуитивно не хочется отдавать случаю слишком много ценных попыток, кажется, пусть уж лучше ищет с умом.

Для 100 повторов с n_trials 50 (n_trials - это разрешённое число оценок целевой функции) выяснилось, к примеру, что уменьшение n_startup_trials с 10 до 5 увеличивает долю нахождения истинного максимума с 66.7% до 68%. А вот дальнейшее снижение до n_startup_trials=2 уже снижает долю до 66.87%. А ведь у оптуны этот параметр по дефолту 10! Так что не полагайтесь на дефолты, тестируйте.

Ясно, что 100 повторов для каждого конфига мало, надо тысяч 10 минимум, а лучше 100. Но даже для 1 парценовского сэмплера кол-во комбинаций конфигов под сотню. Придётся, видно, писать распредёлённый бенч под Dask (

А, и уже видно, что TPE сэмплер заруливает случайный: доля найденных истинных максимумов составляет 68% против 18%. Цена принятия решения вполне оправдана: вместо 0.01 секунды тратится 0.28, что несущественно по сравнению с переобучением даже одной терабайтной модели.

UPD. С дефолтными параметрами все сэмплеры Оптуны, кроме TPE, на моем тесте не могут обогнать RandomSampler, поэтому их тонкие настройки тестить даже не буду.

#featureselection #hpo #hpt #global #optimization #optuna

Ну вот, уже не зря делал исследование. Не все настройки парценовского сэмплера Оптуны одинаково полезны. Выходит, в задаче FS хитрейт можно легко поднять с 68% до 76%!

#pandas #optimization #bollocks

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

Набрёл на дискуссию, где человек приводит аргументы, что копирование излишне и вызывает пенальти к производительности. А 2 мудака-разраба пандас ему затирают про premature optimizaion. Cмотрю, у одного мудака знакомый ник. jreback. И вспоминаю, что это же существо из ядерных разрабов панадаса и мне когда-то давно писало про premature optimization, когда я спрашивал, почему какая-то операция была реализована без inplace (у меня была забита вся память и операция присваиванием просто не проходила).

Отсюда 2 вопроса:
1) кто знает техническое решение, напишите
2) почему подобные мудаки идут разрабатывать библиотеки для работы с данными, в том числе, большими данными? и потом херят все разумные начинания. так вот почему пандас такой сука медленный. вовсе не потому, что высокий уровень абстракции, гибкость. Просто разрабы - мудаки, которые под предлогом no premature optimization делают no optimization at all.

#pandas #optimization #joblib #numpy #memmap

Хорошие новости! после экспериментов выяснилось, что в последних версиях joblib умеет дампить в общую память не просто отдельные массивы numpy, а (что не указано в доке) и целиком фреймы пандас!

И даже не обязательно прописывать операции вручную. Достаточно просто передать фрейм в конструктор Parallel joblib-a как параметр, и, если он больше max_nbytes, joblib его автоматически сдампит и правильно загрузит уже в рабочих процессах! Советую в качестве temp_folder указывать быстрый NVME SSD диск, типа Parallel(n_jobs=32,max_nbytes=0, temp_folder=r'R:\Temp' ). В моих тестах отработали по сути все базовые типы столбцов: int, float, datetime, categorical.

Единственное - проблема со сложными типами, вроде массива массивов numpy (итоговый тип object), такое не работает и включается обычная сериализация. Но этого желать было бы уж слишком нереалистично, я и так не могу себе представить, как удалось победить нерадивых программистов пандас, ведь раньше даже просто инитнуть фрейм с разнородными типами столбцов было невозможно без копирования.

Вывод: если у Вас не экзотические типы данных и есть nvme, большие фреймы в свежих версиях библиотек можно спокойно передавать как параметры, и они не буду побайтово сериализоваться, более того, RAM будет расходоваться в десятки раз экономнее.

#optimization #global #benchmarks #python #cuckolds

Набрёл на вот какое классное питоновское сравнение оптимизаторов! Оказывается, не гипероптом и оптуной едиными! )
Открылись питоновские оптимизаторы, о которых никогда раньше не слышал: Facebook Ax, PySOT, PyMoo, Platypus, pattern.

Автор бенчмарка тоже не в восторге от поведения функций глобальной оптимизации scipy, но он себя успокаивает, что там по-другому, наверное, просто нельзя было сделать:
Evaluating "naughty" optimizers. In this discussion, a naughty optimizer is one that does not limit function evaluations to precisely what the user might desire. As an aside, this isn't a critique. Often the optimizers cycle through parameters, or perform some other subroutine that involves multiple function evaluations - so they only stop periodically to see whether the user-supplied maximum has been exceeded. It may not be sensible to do otherwise, depending on the details of the algorithm.

Я же ответственно вам заявляю, что можно было. Даже если у тебя внутри вложенные процедуры, никаких проблем передать в них максимальное и текущее количество оценок и выйти по условию НЕТ, в процедуре более высокого уровня можно проверку повторить. Это просто мудаки-разработчки. Если параметр у тебя называется max_evals, будь добр, обеспечь, чтобы это количество не превышалось, иначе ты мудак. Хм, или куколд? ) На твои параметры можно только смотреть, они все равно ни хрена не делают )

Кстати, странно, что автор не нашёл идеи нормализовать результаты на реальное количество оценок функции, он же вместо этого для куколдовских алгоритмов scipy итеративно подбирал max_evals так, чтобы реальное max_evals примерно подходило. Также большой недостаток, что у оптуны и гиперопта не проверялись разные сэмплеры и параметры (как их назвать-то? метапараметры?), видимо, всё взяли по дефолту. И шакала оценок совершенно непонятная, если честно, в таблицах не найденные экстремумы, как я думал, а какие-то странные скоры с привязкой ко времени поиска. А, или в основной таблице скоры, а в куколдовских средние найденные экстремумы...

Но ближе к делу, факт в том, что очень хорошо себя показали pysot, pattern из pymoo и shgo+powell из scipy. А значит, их надо затестить тоже.

https://www.microprediction.com/blog/optimize

#optimization #global #benchmarks #python #humpday

Продолжение оптимизационного банкета от того же автора. Он подготовил единый интерфейс для сравнения работы алгосов из доброго десятка оптимизационных пакетов. Я даже не имел понятия, что их СТОЛЬКО, реально под полсотни.

Ну и я посмотрел, что он в итоге советует. В топ-10 автора вошли optuna-cmaes и skopt-gp_minimize, которые на моей одномерной задаче сработали вообще хуже всего... Неужели они так раскрываются с повышением мерности?

https://www.microprediction.com/blog/humpday

#optimization #global #nevergrad

Оказывается, в 2020 фэйсбук проводили даже конкурс на улучшение своего "безградиентного" оптимизатора неверград. Надо тоже попробовать будет. И попробую пульнуть Питеру идею с добавлением метрик, метапараметров оптимизаторов, и включением своих одномерных задач FS в его бенчмарк.

Интересный человек, кстати:

"Dr. Peter Cotton, a career quant, entrepreneur and leading authority on crowdsourcing, is the creator of microprediction.com and founder of Micropredictions, a division of Intech Investments. Dr. Cotton is Intech's former Chief Data Scientist and is the developer of multiple financial modeling patents.

Before joining Intech®, Dr. Cotton spent six years at JPMorgan, where he served as executive director of data science. He created ROAR, a collective intelligence platform with over 1,000 contributing data scientists within JPMorgan; also initiating the privacy preserving computation research, and the use of optimal control in trading. Previously, he was the founder of Benchmark Solutions, a company that pioneered large-scale financial data assimilation and was later sold to Bloomberg. Peter began his career at Morgan Stanley where he was one of several independent inventors of closed-form synthetic CDO pricing.

Dr. Cotton earned an undergraduate degree in physics and mathematics from the University of New South Wales and a PhD in mathematics from Stanford University."

https://github.com/facebookresearch/nevergrad/blob/main/docs/opencompetition2020.md

#featureselection #hpo #hpt #global #optimization #mbho

Недавно я начал тестирование библиотек глобальной оптимизации для одномерной задачи отбора признаков.
Сформировал датасет, проверил самые известные в ds тусовке optuna, skopt, hyperopt (см. по тэгу #featureselection).
Ну и, наконец, представляю своей алгоритм. Назван он Model-based heuristic optimization (MBHO), и по сути похож на байесовскую оптимизацию гауссовым процессом.

Только гауссов процесс я заменил на более универсальный бустинг (опционально с квантилями), а поиск кандидатов ведётся вместо Expected Improvement, Probability of improvement, Upper Confidence Bound такими достаточно простыми эвристиками:

1) на каждом шаге с опр. вероятностью выбирается режим, exploration или exploitation
2) в exploration мы рекомендуем проверить самые неисследованные точки - лежащие дальше всего от уже проверенных, + имеющие самую высокую неопределённость в случае использования квантилей
3) в exploitation режиме мы строим для всей области поиска прогноз, и исследуем точку с самым высоким прогнозом. если такая уже проверена, дополнительно учитываем расстояния от уже проверенных точек и неопределённости.
4) есть ещё несколько мелких опций

Почему гауссов процесс меня не устроил? Да он тупо зачастую плохо приближает данные, и качество решения, как следствие, отвратительное (пример будет в комментах). + долго работает.
Какие есть ещё фишки:

1) закодил 4 метода определения "затравочных" кандидатов, Random, Equidistant, Fibonacci, ReversedFibonacci. В какой-то мере это аналоги soblo/lhe и прочего из skopt.
2) есть возможность строить визуализацию поиска. видно, какие точки уже проверены, как к ним фиттится модель и какие даёт прогнозы, как рассчиталась перспективность каждого кандидата в зависимости от настроек, и какой кандидат в итоге выбран.

К результатам. В бенче я в основном смотрел на процент случаев, когда оптимизатор нашёл истинный максимум.
Для 20 итераций лидером была - optuna/tpe с 69%, для 50 - hyperopt/atpe с 81%. skopt этих показателей не смог превысить.

Показатели моего MBHO: 20 итераций - 70%, 50 итераций - 100%. По времени медленнее оптуны, но быстрее hyperopt/skopt. То есть моё решение победило 3 известные либы оптимизации в одномерном случае.

Да, можно возразить, что я заточил алгоритм под свои конкретные задачи, или вообще старался выставить оппонентов в невыгодном свете, но
1) старался возможности конкурентов исследовать по-полной
2) у них же тоже было тестирование на профильных задачах, им никто не мешал тоже тестироваться на одномерном случае
3) у моего алгоритма достаточно много параметров, и он как раз-таки остаётся недоисследованным. все вычисления я провёл навскидку с просто "разумными" значениями, наверняка можно натюнить лучшее время работы и точность.

Ну и моя основная мотивация, зачем я всё это начинал: в предварительном тестировании встроенные важности признаков бустингов себя хорошо показали, FS по таким важностям разумно делать только с RFECV, но в sklearn RFECV делает полный перебор (да и не работает с категориями), а на практике у меня десятки тысяч признаков и большие датасеты.
Получается, благодаря новому MBHO оптимизатору я смогу просчитывать лишь небольшой % от признаков и при этом находить глобально оптимальные сочетания.

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

Реализация MBHO заняла ~700 строк кода, поддерживается максимизация и минимизация (в отличие от hyperopt, где надо извращаться с негацией функции). Правда, нет асинхронности и многопоточности.

#simulation #optimization

Интересная идея о том, как ускорять симуляции с помощью ML и тем самым помогать быстрой оптимизации. Действительно, почему бы и и нет! Сначала собираем входные параметры системы +итоги симуляций, а дальше симуляцию пробуем заменять быстрой ML моделью.

https://www.youtube.com/watch?v=ohGeGfUCV_A

#optimization #guroby #gurobipy_pandas #guroby_ml

Что примечательно, в качестве ограничений оптимизационной модели можно использовать ... регрессоры!

https://www.youtube.com/watch?v=-xXUVM2UJlg

#trading #backtesting #optimization #sigopt

https://youtu.be/gFPZLpyv774?si=f1bfC2WacedM6O83

#inference #optimization #blackwell

https://developer.nvidia.com/blog/blackwell-breaks-the-1000-tps-user-barrier-with-metas-llama-4-maverick/

#optimization #linearprogramming #operationsresearch

Where to Place the Cameras: Solving a Museum Security Problem with Linear Programming https://allaboutalgorithms.com/where-to-place-the-cameras-solving-a-museum-security-problem-with-linear-programming-9ba958641097