Методы нулевого порядка в оптимизации

🎯 Зачем это нужно?

Представь: ты настраиваешь нейросеть для генерации мемов 🤖. У тебя есть 20 гиперпараметров, и ты понятия не имеешь, как функция потерь зависит от каждого из них. Градиент? Какой градиент - у тебя черный ящик!

Или другой сценарий: SpaceX оптимизирует траекторию ракеты. Каждый “эксперимент” стоит миллионы долларов, а формула зависимости топливо→успех неизвестна. Как найти оптимум?

Вот тут и нужны методы нулевого порядка - они находят минимум, используя только значения функции (без производных)!

📚 История вопроса

В 1965 году Джон Нелдер и Роджер Мид придумали свой знаменитый алгоритм, наблюдая за… амёбой! 🦠 Они заметили, что амёба ползёт к еде, “щупая” среду и меняя форму. Так появился метод деформируемого многогранника.

А генетические алгоритмы в 1970-х вдохновились эволюцией: “Если природа за миллионы лет оптимизировала жирафа, почему бы не оптимизировать нейросеть?”

💡 Интуиция

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

🎯 Случайно тыкать (Random Search) - “а что если я пойду… сюда?” 🔍 Методично обходить (Grid Search) - “проверю каждый угол”
🧬 Эволюционировать (Genetic Algorithm) - “скрещу лучшие решения” 📐 Деформировать фигуру (Nelder-Mead) - “сожму треугольник к оптимуму”

[МЕДИА: image_01] Описание: Визуализация разных методов нулевого порядка на холмистом ландшафте функции Промпт: “3D landscape showing optimization methods, random search points scattered, grid search regular pattern, genetic algorithm population clusters, Nelder-Mead simplex triangle moving toward minimum, colorful educational visualization”

📐 Основные методы

1. Random Search (Случайный поиск)

Идея: Генерируем случайные точки и выбираем лучшую.

# Псевдокод
best_params = None
best_score = ∞
for i in range(n_iterations):
    params = random_sample()  # Случайные параметры
    score = black_box(params)  # Оценка функции
    if score < best_score:
        best_params = params
        best_score = score

2. Grid Search (Поиск по сетке)

Идея: Систематически проверяем все комбинации параметров.

Если у нас параметры α ∈ [0.01, 0.1, 1.0] и β ∈ [10, 100, 1000], то проверяем все 9 комбинаций.

3. Nelder-Mead (Метод деформируемого многогранника)

Идея: Ведём n+1 точек в n-мерном пространстве, деформируя многогранник.

Операции: отражение, растяжение, сжатие, редукция.

4. Генетический алгоритм

Идея: Популяция “особей” эволюционирует к оптимуму.

1. Селекция: выбираем лучших “родителей”
2. Скрещивание: комбинируем их параметры
3. Мутация: случайно меняем некоторые гены
4. Повторяем несколько поколений

[МЕДИА: image_02] Описание: Схема работы генетического алгоритма с популяцией, селекцией и скрещиванием Промпт: “genetic algorithm flowchart, population of solutions, selection process, crossover operation, mutation step, evolution across generations, clean technical illustration”

🔍 Примеры с разбором

Пример 1: Настройка гиперпараметров CNN

У нас есть свёрточная сеть для классификации изображений. Нужно найти:

• learning_rate ∈ [0.0001, 0.01]
• batch_size ∈ [16, 32, 64, 128]
• dropout ∈ [0.1, 0.5]

Grid Search: 4×4×2 = 32 комбинации Random Search: 32 случайные точки из области

Исследования показывают: Random Search часто работает лучше! Почему? Потому что важных параметров обычно мало, а Grid Search “тратит” попытки на неважные.

Пример 2: Оптимизация портфеля

Функция: f(w₁, w₂, w₃) = риск портфеля из 3 активов Ограничения: w₁ + w₂ + w₃ = 1, wᵢ ≥ 0

Генетический алгоритм:

• Особь = [0.3, 0.5, 0.2] (веса активов)
• Скрещивание: [0.3, 0.5, 0.2] + [0.4, 0.3, 0.3] → [0.35, 0.4, 0.25]
• Мутация: случайно меняем один вес с перенормировкой

🎮 Практика

Базовый уровень 🟢

Задача 1: У тебя функция f(x) = (x-3)² + шум. Сравни Random Search и Grid Search для поиска минимума на [-10, 10]. Сколько вычислений нужно каждому методу?

Задача 2: Объясни, почему Grid Search плохо масштабируется. Сколько точек нужно проверить для 10 параметров по 5 значений каждый?

Задача 3: В чём преимущество Random Search перед Grid Search для высокоразмерных задач?

Продвинутый уровень 🟡

Задача 4: Реализуй простейший генетический алгоритм для оптимизации функции f(x₁, x₂) = x₁² + x₂². Популяция = 10, поколений = 20.

Задача 5: В Nelder-Mead для функции двух переменных сколько точек в симплексе? Опиши операцию отражения.

Задача 6: Hyperband - улучшение Random Search. В чём идея: тратить больше времени на обучение хороших конфигураций?

Челлендж 🔴

Задача 7: Байесовская оптимизация использует Gaussian Process для моделирования функции. В чём её преимущество перед чисто случайными методами?

Задача 8: Evolutionary Strategy (ES) недавно обыграл backpropagation в некоторых задачах RL. Исследуй почему: что даёт шум в градиентах?

⚠️ Частые ошибки

❌ Ошибка: “Методы нулевого порядка всегда хуже градиентных” ✅ Правильно: При зашумленных градиентах или дискретных параметрах они могут быть лучше 💡 Почему: OpenAI ES показал конкурентные результаты в Atari играх

❌ Ошибка: “Grid Search всегда лучше Random Search”
✅ Правильно: Random Search эффективнее в высоких размерностях 💡 Почему: Проклятие размерности - Grid Search экспоненциально растёт

❌ Ошибка: “Генетические алгоритмы гарантируют глобальный оптимум” ✅ Правильно: Они эвристические и могут застрять в локальных минимумах
💡 Почему: Нет математических гарантий сходимости, только вероятностные

🎓 Главное запомнить

✅ Методы нулевого порядка = оптимизация без производных, только по значениям функции ✅ Random Search > Grid Search в высоких размерностях при фиксированном бюджете ✅ Применения: гиперпараметры ML, инженерный дизайн, финансы, игры

🔗 Связь с другими темами

Эти методы - основа для автоматического машинного обучения (AutoML). В следующих уроках изучим байесовскую оптимизацию и multi-armed bandits - более умные способы исследования пространства параметров без градиентов.