📈Глобальная оптимизация

Давно я ничего не писал – всё не видел достойных поводов для постов, однако сейчас такой появился.

Я сделаю небольшую серию публикаций на тему глобальной оптимизации:

1️⃣ Что это за задача
2️⃣ Семейства алгоритмов оптимизации и их представители
3️⃣ Библиотека Ray
4️⃣ Опыт собственной реализации алгоритма на основе статьи

Пример

Представьте, что у вас есть какая-то бизнес- или математическая задача. Например — купить мясо и напитки к столу на фиксированный бюджет. Цель — потратить минимум времени. Зададим переменные и ограничим их диапазон, чтобы совсем с ума не сходить:

x1: Сколько людей мы отправим: от 1 до 4
x2: Каких именно людей мы отправим: пускай будет выборка из 6 человек.
x3: День недели: пятница или суббота
x4: В какое время суток отправлять: с 8 до 16 часов
x5: На какой рынок отправиться: пускай будет 3 варианта наиболее удачных рынков в городе.

Давайте попробуем решить эту задачу, опираясь на жизненный опыт. Я опишу свои мысли, а вы можете прикинуть сами и потом читать дальше.

x1 — количество людей: оптимально – двое. Один может быстро закупиться, но вдвоем есть дополнительная пара рук как для тяжестей, так и для иных задач. Если 3 или 4 человека, то вместо одного канала коммуникаций у нас будет уже 3 и 6 каналов. Если по-русски — много времени начнет уходить на обсуждения.
х2 — кого отправим: здесь нужны люди пунктуальные и желательно с большим опытом в организации таких мероприятий.
х3 — день недели: лучше в пятницу, чем в субботу, очевидно.
х4 — время суток: я бы выбрал 10 утра, потому что в это время уже все, кому надо, на работе, и отправленные на рынок люди уже проснулись и бодрствуют, тормозить не будут.
х5 — рынок: здесь не буду предполагать, но можно учесть местоположение людей, которых отправляем, и взять тот рынок, который по среднему расстоянию будет ближе всего.

Разумеется, это достаточно простая жизненная задача, однако к 20-25 годам у нас уже есть набор знаний и опыта, который позволяет оценить поведение этой функции в зависимости от переменных, и выбрать некоторую субоптимальную комбинацию параметров. Но как, очутившись в мире, где есть только люди, рынки и мясо для шашлыка, такой опыт можно получить и каким образом достичь цели быстрее всего? Перепробовать все комбинации — точно сработает, но долго. Попробовать случайные 5-6 — а достаточно ли это хороший подход?

Задача

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

Оптимизация гиперпараметров

С помощью примера выше мы показали, что в жизни таких задач очень много — практически каждый процесс можно сформулировать как задачу оптимизации, в том числе и эволюционный (это важное замечание). И раз уж я не владелец кафе а-ля Шашлычный Мир, а CV/ML-инженер, расскажу про реальную задачу, где нам нужна глобальная оптимизация.

Обучаем мы нейросеть, задаем различные гиперпараметры, начиная с оптимизатора, learning rate и batch size, заканчивая аугментациями и регуляризациями и смотрим на точность после обучения. Важно отметить, что в силу невозможности продифференцировать такую функцию, мы имеем более общую задачу и медленную сходимость. Как будем подбирать самую хорошую комбинацию? Жизненный опыт — это хорошо, но его долго получать, нет гарантий, что он верный и сработает как нам надо, а также его не так легко обосновать.

Люди, которые касались этой задачи, сразу же вспомнят про GridSearch – поиск по сетке, где мы задаем для каждого параметра набор значений, которые нужно перебрать каждый с каждым. Однако есть высокая вероятность не попасть даже в хороший локальный максимум. Ну и вспомним RandomSearch – поиск по случайным наборам параметров. Любопытно, что у него даже теоретически доказанная сходимость заметно лучше, чем у поиска по сетке, но он тоже не вызывает чувство спокойствия по поводу обоснованности сделанного выбора.

Как раз о таких методах, которые помогут спать спокойно, в следующих постах и пойдет речь.

#learn #hard #cases