Оптимизация

Многокритериальная оптимизация

Как Google выбирает архитектуру мобильного ML-чипа: нужны точность, скорость И энергопотребление одновременно. Нельзя максимизировать всё - нужны компромиссы. Фронт Парето показывает ВСЕ оптимальные компромиссы, позволяя инженерам осознанно выбрать позицию.

**NAS в Google/Meta:** EfficientNet найден через многокритериальный NAS - NSGA-II ищет accuracy-vs-FLOPs фронт Парето
**ML Systems design:** latency vs accuracy trade-off при выборе модели для production - MOBO в Ax (Meta) автоматизирует этот процесс
**Safe RL:** reward vs constraint violation (безопасность) - задача двухкритериальной оптимизации для автопилотов

Предварительные знания

Bayesian Optimization

Фронт Парето и доминирование

В **многокритериальной оптимизации** нет единственного оптимума - есть **фронт Парето**: множество решений, для каждого из которых нельзя улучшить один критерий без ухудшения другого. Решение x доминирует y (x ≻ y) если x не хуже по всем критериям и лучше хотя бы по одному.

**Гиперобъём (Hypervolume indicator):** скалярная мера качества фронта Парето - объём пространства, заключённого между фронтом и опорной точкой (worst case). Чем больше hypervolume, тем лучше покрытие фронта. Используется как objective для многокритериального BO.

Модель A: accuracy=0.85, latency=30ms. Модель B: accuracy=0.82, latency=35ms. Какая доминирует?

Скаляризация и ε-constraint

Две классических стратегии получить одно решение из многокритериальной задачи: **взвешенная сумма** min Σwᵢfᵢ(x) и **ε-constraint** min f₁(x) s.t. f₂(x) ≤ ε. Взвешенная сумма проста, но покрывает только выпуклые части фронта. ε-constraint находит любую точку фронта, включая невыпуклые.

Взвешенная сумма не работает для невыпуклых фронтов Парето: некоторые точки не являются минимумами ни при каком выборе весов. Для невыпуклых задач - ε-constraint или NSGA-II.

Взвешенная сумма с весами w=(0.5, 0.5) нашла точку P₁. При w=(0.8, 0.2) нашла P₂. Между P₁ и P₂ на фронте Парето есть точка P₃. Почему weighted sum её не нашла?

NSGA-II: генетический алгоритм для МОО

**NSGA-II** (Non-dominated Sorting Genetic Algorithm II, Deb 2002) - наиболее популярный многокритериальный эволюционный алгоритм. Ключевые идеи: 1. сортировка по рангам (fronts) 2. crowding distance - поощряем разнообразие на фронте.

**Crowding distance** в NSGA-II: мера «разрежённости» - сумма нормализованных расстояний до соседних решений на каждой оси. Решения с большой crowding distance поощряются при равном ранге доминирования. Это обеспечивает равномерное покрытие фронта.

NSGA-II использует crowding distance при выборе решений с одинаковым рангом доминирования. Зачем?

Hypervolume и практика МОО

**Hypervolume** - скалярная метрика качества фронта Парето: объём пространства, доминируемого фронтом относительно опорной точки r (worst-case). Позволяет сравнивать алгоритмы и измерять прогресс. Вычисление - O(n^(k-1)) для k критериев.

**Multi-objective BO (MOBO):** комбинация NSGA-II и BO. На каждом шаге: GP surrogates для каждой цели + acquisition function на основе EHVI (Expected Hypervolume Improvement). Используется в Ax (Meta) для оптимизации accuracy-latency trade-off в production ML.

В задаче с несколькими целями нужно взвешивать их и сводить к одной - только так можно оптимизировать

Взвешенная сумма - лишь один из подходов, теряющий невыпуклые части фронта. NSGA-II, MOBO и ε-constraint находят весь фронт без заранее заданных весов. Выбор точки на фронте - отдельная задача decision-making.

Взвешенная сумма корректна только когда пользователь заранее знает веса и фронт выпуклый. В реальности предпочтения часто неизвестны заранее (нужно увидеть trade-offs) и фронты невыпуклые. Multi-objective optimization сначала строит весь фронт, а потом позволяет выбрать точку. Это даёт принципиально больше информации.

Алгоритм A дал фронт Парето с HV=0.8, алгоритм B - с HV=0.75 (опорная точка та же). Что можно заключить?

Ключевые идеи

**Фронт Парето:** множество недоминируемых решений; x ≻ y если x лучше по всем критериям хотя бы в одном
**Взвешенная сумма vs ε-constraint:** взвешенная сумма проста, но теряет невыпуклые части; ε-constraint полный
**NSGA-II:** non-dominated sorting + crowding distance; стандарт для многокритериальной эволюции
**Hypervolume:** скалярная мера качества фронта; MOBO максимизирует expected HV improvement

Связанные темы

МОО объединяет комбинаторику и эволюцию:

Bayesian Optimization — MOBO (EHVI) расширяет BO для нескольких целей - Ax (Meta), BoTorch поддерживают
Метаэвристики — NSGA-II - многокритериальная версия GA; MOEA/D, SMS-EMOA - другие варианты
Distributed Optimization — Distributed NSGA-II для задач с дорогими evaluations - параллельная оценка popular в NAS

Вопросы для размышления

Бизнес хочет 'наилучшую' ML-модель: максимальная точность при минимальной задержке. Почему корректный ответ - 'покажите фронт Парето', а не 'вот одна лучшая модель'?
Взвешенная сумма с весами w=(0.7, 0.3) нашла решение A. Теперь стейкхолдер говорит, что хочет чуть лучшую задержку. Нужно ли перезапускать оптимизацию или можно использовать фронт Парето?
NSGA-II обеспечивает diversity через crowding distance. Почему diversity на фронте важна для практики, а не только для полноты математики?

Связанные уроки

opt-12 — Эволюционные алгоритмы часто применяют для многокритериальной оптимизации
opt-15 — ML-оптимизация требует понимания компромиссов точность/скорость
ml-05-evaluation — Precision/recall tradeoff - частный случай многокритериальной задачи
prob-07-expectation — Скаляризация через взвешенное матожидание критериев
alg-01-big-o — Сложность алгоритмов как один из критериев в Парето-фронте
calc-01-sequences