Multi-objective optimization ⚖️

Представь, что ты обучил три версии одной и той же модели для мобильного приложения распознавания речи. Первая — большая трансформерная сеть с точностью 94%, но она весит 800 мегабайт и отвечает за 300 миллисекунд. Вторая — дистиллированная версия с точностью 91%, весом 150 мегабайт и временем отклика 80 миллисекунд. Третья — агрессивно квантованная модель с точностью 87%, весом 30 мегабайт и откликом 20 миллисекунд. Какая из них «лучшая»? На этот вопрос нет единственно верного ответа — всё зависит от того, где именно будет работать приложение: на флагманском смартфоне с быстрым интернетом или на бюджетном устройстве с ограниченной памятью и офлайн-режимом.

Ты только что столкнулся с сутью многокритериальной оптимизации (multi-objective optimization) — задачи одновременной оптимизации нескольких целей, которые конфликтуют между собой. Все двадцать четыре предыдущих урока этого блока — от условий Каруша–Куна–Таккера до байесовской оптимизации — работали с одной-единственной целевой функцией: минимизировать ошибку, минимизировать время выполнения, максимизировать прибыль. Реальные инженерные задачи почти никогда не устроены так просто. Точность модели, скорость инференса и размер на диске — это три отдельных числа, которые нельзя честно свернуть в одно без потери информации, потому что улучшение одного почти всегда означает ухудшение другого.

Именно поэтому в многокритериальных задачах обычно не существует единственного «оптимального» решения в привычном смысле. Вместо одной точки-победителя есть целое множество разумных компромиссов — решений, каждое из которых хорошо по-своему и не может быть однозначно признано хуже какого-то другого. Задача инженера смещается: не «найти оптимум», а сначала понять всю структуру доступных компромиссов, а затем осознанно выбрать среди них тот, что соответствует приоритетам конкретной ситуации.

В этом уроке — последнем в блоке «Оптимизация» — ты разберёшь, как формально устроена задача с конфликтующими целями, что такое доминирование по Парето и как оно позволяет сравнивать решения по нескольким критериям сразу, что такое фронт Парето и как его строить и визуализировать на простых числовых примерах, какими способами многокритериальную задачу можно свести к однокритериальной — через взвешенную сумму целей (скаляризацию) или лексикографический порядок приоритетов, — и как устроена идея NSGA-II, самого известного эволюционного алгоритма для многокритериальной оптимизации. Ты увидишь, как эти инструменты работают на сквозном примере выбора модели для развёртывания — задаче, с которой ML-инженер сталкивается практически при каждом релизе.

История

Имя, давшее название всей области, принадлежит Вильфредо Парето (Vilfredo Pareto), итальянскому инженеру, экономисту и социологу рубежа XIX–XX веков. Парето получил образование инженера в Туринском политехническом институте и много лет проработал в металлургии и на железной дороге, прежде чем в 1893 году занял кафедру политической экономии в Лозаннском университете, сменив на этом посту Леона Вальраса — одного из основателей математической экономики. Именно инженерная закалка отличала подход Парето от подхода большинства экономистов его времени: он последовательно переводил экономические рассуждения на язык функций, множеств и оптимизации, что было довольно необычно для гуманитарной по духу дисциплины конца XIX века.

Изучая распределение доходов в разных странах Европы, Парето обнаружил закономерность, которая сегодня известна как «правило 80/20»: примерно 80% богатства сосредоточено у примерно 20% населения, причём это соотношение с поразительным постоянством повторялось в самых разных экономиках и эпохах. Но по-настоящему важным для будущей теории оптимизации оказалось не само правило 80/20, а введённое Парето в его труде «Cours d'économie politique» (1896–1897) понятие оптимальности распределения ресурсов в обществе с несколькими участниками: состояние экономики называется оптимальным (в современных терминах — Парето-оптимальным), если невозможно улучшить положение хотя бы одного человека, не ухудшив положение кого-то другого. Это определение сформулировано без единой общей «функции полезности всего общества» — оно сравнивает состояния напрямую, по каждому участнику отдельно, и именно эта идея прямого попарного сравнения без свёртки в одно число почти сто лет спустя легла в основу формального доминирования по Парето в теории многокритериальной оптимизации.

Систематическое применение идей Парето к инженерной и вычислительной оптимизации развернулось во второй половине XX века, когда специалисты по исследованию операций и системному проектированию начали формализовать задачи с несколькими критериями — стоимостью, надёжностью, весом конструкции, временем выполнения. Настоящий взрыв интереса к вычислительным методам многокритериальной оптимизации пришёлся на 1980–1990-е годы, когда Дэвид Голдберг (David E. Goldberg) предложил использовать ранжирование по недоминированию внутри генетических алгоритмов, а в 2002 году Калиянмой Деб (Kalyanmoy Deb) с соавторами опубликовал алгоритм NSGA-II — с этого момента многокритериальная оптимизация окончательно оформилась как самостоятельный, практически применимый раздел вычислительной оптимизации, который сегодня встроен в инструменты автоматического подбора гиперпараметров и архитектур моделей машинного обучения.

Задача с конфликтующими целями

Интуиция

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

Формальное определение

Общая постановка многокритериальной задачи оптимизации. Дано пространство допустимых решений $X$ и $m \ge 2$ целевых функций $f_1(x), f_2(x), \dots, f_m(x)$, которые нужно одновременно минимизировать (максимизация цели $f_i$ сводится к минимизации $-f_i$). Формально задача записывается как

$$\min_{x \in X} \big(f_1(x),\ f_2(x),\ \dots,\ f_m(x)\big)$$

Принципиальная сложность этой записи в том, что «минимум вектора» в общем случае не определён однозначно: если целевые функции конфликтуют, не существует решения $x^*$, которое одновременно минимизировало бы каждую $f_i$ по отдельности — минимум $f_1$ и минимум $f_2$ достигаются, как правило, в разных точках $X$.

Примеры

Пример 1: выбор модели для мобильного приложения. Вернись к трём моделям распознавания речи из вступления. Формализуем задачу двумя целями: $f_1(x) = 100\% - \text{accuracy}(x)$ (ошибка, которую минимизируем) и $f_2(x) = \text{latency}(x)$ в миллисекундах. Модель A: $f_1 = 6,\ f_2 = 300$. Модель B: $f_1 = 9,\ f_2 = 80$. Модель C: $f_1 = 13,\ f_2 = 20$. Нет модели, которая одновременно минимизировала бы и ошибку, и задержку — минимум $f_1$ у модели A, минимум $f_2$ у модели C. Это и есть конфликт целей в чистом виде.

Пример 2: инвестиционный портфель. Классическая задача Марковица: инвестор одновременно хочет максимизировать ожидаемую доходность портфеля $R(x)$ и минимизировать его риск, обычно измеряемый дисперсией доходности $\sigma^2(x)$. Портфель, полностью состоящий из одной быстрорастущей, но волатильной акции, обычно даёт высокую ожидаемую доходность ценой высокого риска; портфель из государственных облигаций даёт низкий риск ценой низкой доходности. Между этими крайностями лежит целый спектр промежуточных портфелей — ни один из них не доминирует остальные по обоим критериям сразу.

Пример 3: проектирование крыла самолёта. Авиаинженеры одновременно минимизируют расход топлива на километр пути и вес конструкции крыла, а также максимизируют его прочность на излом. Более лёгкое крыло экономит топливо (меньше масса — меньше энергии на подъём), но облегчение конструкции обычно означает более тонкие элементы и, следовательно, меньший запас прочности. Здесь конфликтуют уже три цели одновременно, а не две, что типично для инженерных задач вне учебных примеров.

Почему это важно

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

Доминирование по Парето

Интуиция

Раз единой шкалы сравнения нет, нужен способ сравнивать два решения напрямую, «по-компонентно», не сворачивая их предварительно в одно число. Идея простая и интуитивно честная: решение $A$ однозначно лучше решения $B$, если оно не хуже $B$ по каждому отдельному критерию и строго лучше хотя бы по одному. Если же по одному критерию лучше $A$, а по другому лучше $B$, сравнение напрямую невозможно — оба решения представляют разные, несравнимые компромиссы.

Формальное определение

Доминирование по Парето. Пусть все цели минимизируются. Решение $x_A$ доминирует решение $x_B$ (обозначается $x_A \prec x_B$), если выполнены два условия одновременно:

1. $f_i(x_A) \le f_i(x_B)$ для всех $i = 1, \dots, m$ (решение $x_A$ не хуже $x_B$ по каждому критерию);
2. существует хотя бы один индекс $j$, для которого $f_j(x_A) < f_j(x_B)$ строго (решение $x_A$ строго лучше по хотя бы одному критерию).

Если ни одно из двух условий не нарушено — доминирование установлено. Если же по одному критерию лучше $x_A$, а по другому лучше $x_B$, решения называются несравнимыми (несопоставимыми): ни одно не доминирует другое.

Примеры

Пример 1: явное доминирование. Модель X имеет ошибку $f_1=5\%$ и задержку $f_2=100$ мс. Модель Y имеет ошибку $f_1=5\%$ и задержку $f_2=80$ мс. По первому критерию модели равны, по второму Y строго лучше — оба условия доминирования выполнены, значит Y доминирует X ($Y \prec X$). Модель X в этой паре можно смело исключить из рассмотрения: она не лучше Y ни по одному критерию и строго хуже по одному.

Пример 2: несравнимые решения. Модель P имеет ошибку $f_1=3\%$ и задержку $f_2=200$ мс. Модель Q имеет ошибку $f_1=6\%$ и задержку $f_2=50$ мс. По ошибке лучше P, по задержке лучше Q — ни одно условие доминирования не выполняется ни в одну, ни в другую сторону. P и Q несравнимы: выбор между ними — это уже не вопрос математики, а вопрос приоритетов конкретного проекта (важнее точность или скорость).

Пример 3: доминирование среди трёх моделей. Возьми модели A ($f_1=6,\ f_2=300$), B ($f_1=9,\ f_2=80$), C ($f_1=13,\ f_2=20$) из примера про распознавание речи и добавь четвёртую, D, с $f_1=10,\ f_2=150$. Сравни D с B: $f_1(B)=9 < f_1(D)=10$ и $f_2(B)=80 < f_2(D)=150$ — B лучше D по обоим критериям сразу, значит $B \prec D$, и D доминируется. А вот пары A–B, A–C и B–C попарно несравнимы (проверь самостоятельно по определению: в каждой паре один критерий лучше у одной модели, другой — у другой). Модель D можно смело исключить как заведомо худший вариант, а вот среди A, B и C выбор зависит от приоритетов.

Почему это важно

Доминирование по Парето даёт формальный, не зависящий от произвольно выбранных весов способ выбраковать заведомо плохие решения: если решение доминируется каким-то другим, его можно отбросить без каких-либо дополнительных предположений о приоритетах — любой разумный человек, желающий улучшения хотя бы по одному критерию без ухудшения остальных, предпочтёт доминирующее решение. Это первый и совершенно бесспорный шаг сужения множества кандидатов, который стоит делать всегда, ещё до того, как вступают в игру субъективные веса или приоритеты.

Фронт Парето и его визуализация

Интуиция

После того как все доминируемые решения отброшены, остаётся множество взаимно несравнимых решений — каждое из них хорошо по-своему, и ни одно не может быть улучшено по одному критерию без ухудшения по другому. Это множество и есть содержательный, «интересный» результат многокритериальной оптимизации: не одна точка, а вся карта разумных компромиссов, из которой уже человек (или дополнительный, более субъективный критерий) выбирает конкретное решение.

Формальное определение

Парето-оптимальность и фронт Парето. Решение $x^* \in X$ называется Парето-оптимальным (недоминируемым), если не существует другого допустимого решения $x \in X$, которое доминирует $x^*$. Множество всех Парето-оптимальных решений $X^* \subseteq X$ называется множеством Парето (Pareto set), а множество их образов в пространстве целевых функций

$$\mathcal{P} = \big\{ \big(f_1(x^*), \dots, f_m(x^*)\big) : x^* \in X^* \big\}$$

называется фронтом Парето (Pareto front). При двух целевых функциях фронт Парето обычно визуализируют как «лестницу», убывающую слева направо на плоскости $(f_1, f_2)$ (для задачи минимизации обеих целей): каждая последующая точка фронта справа налево улучшает $f_1$ за счёт ухудшения $f_2$.

Примеры

Пример 1: построение фронта Парето вручную по числовым парам. Пусть у тебя есть восемь кандидатов моделей с парами (ошибка в %, задержка в мс): $(2, 400)$, $(3, 250)$, $(4, 180)$, $(4, 300)$, $(6, 130)$, $(8, 130)$, $(9, 70)$, $(15, 50)$. Построить фронт Парето вручную удобно так: отсортируй точки по первому критерию по возрастанию, затем пройди по списку и отслеживай минимальное значение второго критерия, встреченное на данный момент. Точка попадает на фронт, только если её второй критерий строго меньше минимума, встреченного среди всех точек с не большей ошибкой. Отсортированный список: $(2,400), (3,250), (4,180), (4,300), (6,130), (8,130), (9,70), (15,50)$. Проходим: $(2,400)$ — на фронте (первая точка, минимум задержки пока $=400$). $(3,250)$ — $250<400$, на фронте, минимум обновляется до $250$. $(4,180)$ — $180<250$, на фронте, минимум $=180$. $(4,300)$ — $300>180$, доминируется точкой $(4,180)$ (равная ошибка, хуже задержка) — не на фронте. $(6,130)$ — $130<180$, на фронте, минимум $=130$. $(8,130)$ — $130$ не меньше текущего минимума $130$ строго — доминируется точкой $(6,130)$ (не хуже по задержке, строго лучше по ошибке) — не на фронте. $(9,70)$ — $70<130$, на фронте, минимум $=70$. $(15,50)$ — $50<70$, на фронте, минимум $=50$. Итоговый фронт Парето: $(2,400), (3,250), (4,180), (6,130), (9,70), (15,50)$ — шесть из восьми точек, две отброшены как доминируемые.

Пример 2: визуализация фронта на плоскости. Если отметить шесть точек фронта из примера 1 на графике с осью $x$ = ошибка, осью $y$ = задержка, получится убывающая ступенчатая линия: с ростом допустимой ошибки задержка падает. Форма этой линии содержательна: резкий обрыв задержки между $(2,400)$ и $(3,250)$ говорит о том, что небольшая уступка по точности даёт непропорционально большой выигрыш в скорости — типичная и очень практически ценная информация при выборе модели для развёртывания. Пологий участок фронта, наоборот, говорит о том, что дальнейшие уступки по одной цели почти не приносят выгоды по другой.

Пример 3: фронт при трёх целях. Когда целей три (например, ошибка, задержка и размер модели на диске), фронт Парето — уже не линия, а двумерная поверхность в трёхмерном пространстве критериев, и визуализировать её напрямую сложнее. На практике для трёх целей часто используют 3D-scatter график с возможностью вращения, а для четырёх и более целей — parallel coordinates plot (график параллельных координат), где каждая ось соответствует одной цели, а каждое Парето-оптимальное решение — это ломаная линия, пересекающая все оси. При большом числе целей (свыше пяти-шести) почти все решения в популяции становятся взаимно несравнимыми, и фронт Парето разрастается настолько, что теряет практическую пользу как инструмент для выбора, — это известное явление иногда называют «проклятием размерности» применительно к числу целевых функций, а не входных переменных.

Почему это важно

Фронт Парето — это не промежуточный технический артефакт, а самостоятельный, самоценный результат многокритериальной оптимизации: он превращает вопрос «какое решение лучшее?» в куда более полезный вопрос «какие компромиссы вообще доступны, и какой из них устраивает нас сейчас?». Визуализация фронта — особенно при двух-трёх целях — часто оказывается самым убедительным аргументом в разговоре с заказчиком или продакт-менеджером: наглядная кривая «точность против задержки» с явно отмеченными кандидатами моделей объясняет компромисс куда лучше, чем таблица чисел или единственное «рекомендованное» решение без объяснения альтернатив.

Скаляризация и лексикографический подход

Интуиция

Фронт Парето даёт полную картину, но рано или поздно нужно выбрать одно конкретное решение — задеплоить конкретную модель, купить конкретный портфель акций. Скаляризация решает эту задачу «в лоб»: она сводит несколько целей к одной взвешенной комбинации, превращая многокритериальную задачу обратно в однокритериальную, к которой применимы все методы предыдущих уроков блока — от градиентного спуска до байесовской оптимизации. Лексикографический подход решает ту же задачу иначе — не смешивая цели в одно число, а выстраивая их в строгий порядок приоритета и оптимизируя по очереди.

Формальное определение

Скаляризация методом взвешенной суммы. Задаются веса $w_1, \dots, w_m \ge 0$ с $\sum_{i=1}^m w_i = 1$, отражающие относительную важность целей, и решается однокритериальная задача

$$\min_{x \in X} \sum_{i=1}^m w_i \, f_i(x)$$

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

Лексикографический подход. Цели упорядочиваются по строгому приоритету $f_{(1)} \succ f_{(2)} \succ \dots \succ f_{(m)}$. Сначала находится множество решений $X_1 \subseteq X$, оптимальных по $f_{(1)}$; среди $X_1$ находится подмножество $X_2 \subseteq X_1$, оптимальных по $f_{(2)}$, и так далее, пока не останется единственное решение или не закончится список критериев.

Примеры

Пример 1: числовой расчёт взвешенной суммы. Возьми модели A ($f_1=6\%$ ошибка, $f_2=300$ мс), B ($f_1=9\%$, $f_2=80$ мс), C ($f_1=13\%$, $f_2=20$ мс). Нормализуем каждый критерий в диапазон $[0,1]$ делением на максимум по всем моделям: $f_1^{norm} = f_1/13$, $f_2^{norm} = f_2/300$. Получаем: A $= (0{,}462,\ 1{,}0)$, B $= (0{,}692,\ 0{,}267)$, C $= (1{,}0,\ 0{,}067)$. При весах $w_1=0{,}7$ (точность важнее) и $w_2=0{,}3$: скор A $=0{,}7\cdot0{,}462+0{,}3\cdot1{,}0=0{,}623$; скор B $=0{,}7\cdot0{,}692+0{,}3\cdot0{,}267=0{,}564$; скор C $=0{,}7\cdot1{,}0+0{,}3\cdot0{,}067=0{,}720$. Наименьший скор (мы минимизируем) у B — при таких весах побеждает модель B, компромиссный вариант.

Пример 2: как смена весов меняет выбор. Возьми те же нормализованные значения, но поменяй веса на $w_1=0{,}2$ (точность менее важна), $w_2=0{,}8$ (задержка критична, например для устройства реального времени): скор A $=0{,}2\cdot0{,}462+0{,}8\cdot1{,}0=0{,}892$; скор B $=0{,}2\cdot0{,}692+0{,}8\cdot0{,}267=0{,}352$; скор C $=0{,}2\cdot1{,}0+0{,}8\cdot0{,}067=0{,}254$. Теперь минимальный скор у C — при новых весах побеждает самая лёгкая и быстрая модель. Это ключевое практическое свойство скаляризации: разные веса, отражающие разные приоритеты проекта, приводят к разным точкам фронта Парето — и потому веса нужно осознанно обсуждать с заказчиком, а не «зашивать» произвольно в код.

Пример 3: лексикографический выбор для медицинской диагностической системы. Пусть система классифицирует снимки на предмет опасного заболевания, и приоритеты строго упорядочены: сначала минимизировать долю пропущенных положительных случаев (false negative rate) — цена ошибки здесь неприемлемо высока, — и только среди моделей с почти одинаковым, минимальным значением этого показателя выбирать по второму критерию — задержке инференса. Если модель D имеет false negative rate $=1{,}2\%$, модель E — $1{,}3\%$, а модель F — $4{,}0\%$, то F отбрасывается сразу же на первом шаге лексикографической процедуры, независимо от того, насколько она быстрее D и E, — а выбор между D и E будет сделан уже по задержке. Здесь лексикографический подход отражает реальный инженерный процесс лучше взвешенной суммы: не существует такого веса задержки, при котором стоило бы жертвовать безопасностью пациента.

Почему это важно

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

NSGA-II кратко

Интуиция

Скаляризация с разными весами позволяет нащупать отдельные точки фронта Парето, запуская однокритериальную оптимизацию заново для каждого набора весов, — но это дорого, если фронт нужен целиком. NSGA-II (Non-dominated Sorting Genetic Algorithm II, «генетический алгоритм с недоминируемой сортировкой», предложенный Кальянмоем Дебом с соавторами в 2002 году) решает эту проблему иначе: он строит целую популяцию решений одновременно и использует доминирование по Парето прямо в процедуре отбора, вместо того чтобы сначала сворачивать цели в одно число.

Формальное определение

Идея NSGA-II. Популяция решений разбивается на слои недоминирования (фронты): первый фронт $F_1$ — множество Парето-оптимальных решений внутри текущей популяции; второй фронт $F_2$ — решения, доминируемые только решениями из $F_1$ (то есть Парето-оптимальные, если временно убрать из популяции $F_1$); и так далее, пока не будет распределена вся популяция. Отбор особей для следующего поколения производится в первую очередь по номеру фронта (чем меньше номер, тем предпочтительнее особь), а среди особей одного фронта — по метрике crowding distance («плотность скученности»), которая тем больше, чем дальше особь расположена от своих ближайших соседей по фронту в пространстве целевых функций. Отбор по crowding distance намеренно предпочитает более редко населённые участки фронта, поддерживая разнообразие решений вдоль всего фронта Парето, а не скучивание в одной его части.

Примеры

Пример 1: недоминируемая сортировка вручную на маленькой популяции. Пусть популяция из шести решений (в координатах $f_1, f_2$, минимизация обеих): $P1=(1,5)$, $P2=(2,3)$, $P3=(3,2)$, $P4=(4,6)$, $P5=(5,1)$, $P6=(2,4)$. Проверка доминирования показывает: $P1$, $P2$, $P3$, $P5$ взаимно несравнимы и не доминируются никем — это фронт $F_1$. $P6=(2,4)$ доминируется $P2=(2,3)$ (равная ошибка $f_1$, лучше $f_2$) — значит $P6$ не в $F_1$; после временного удаления $F_1$ из рассмотрения $P6$ остаётся единственным и потому недоминируемым в оставшемся множестве — это фронт $F_2$. $P4=(4,6)$ доминируется и $P2$, и $P3$, и даже (после удаления $F_1$) не доминируется никем из оставшихся, кроме уже убранных, — тоже попадает во фронт $F_2$ вместе с $P6$ (либо в $F_3$, если сравнивать P4 и P6 между собой окажется, что ни одна не доминирует другую — проверка: $f_1(P6)=2<4=f_1(P4)$, но $f_2(P6)=4<6=f_2(P4)$, значит $P6$ доминирует $P4$, и итоговое распределение: $F_1=\{P1,P2,P3,P5\}$, $F_2=\{P6\}$, $F_3=\{P4\}$).

Пример 2: зачем нужна crowding distance. Представь, что фронт $F_1$ состоит из десяти точек, девять из которых скучены в одном небольшом участке кривой, а одна — на противоположном, малоизученном конце фронта. Если отбирать особей для следующего поколения только по номеру фронта, все десять точек одинаково хороши, и алгоритм рискует случайно выродить популяцию в узкий участок фронта, потеряв разнообразие компромиссов. Crowding distance присваивает изолированной десятой точке — и вообще крайним точкам фронта — намеренно завышенное (формально бесконечное) значение метрики, гарантируя, что такие точки сохранятся в популяции и фронт не «схлопнется» в одну область.

Пример 3: NSGA-II в подборе архитектур моделей. Современные инструменты автоматического машинного обучения (AutoML), такие как Optuna, включают NSGA-II как один из встроенных алгоритмов сэмплирования именно для многокритериальных задач: например, одновременного подбора архитектуры и гиперпараметров нейросети по двум критериям — точности на валидации и числу параметров модели. За один прогон такой оптимизации, в отличие от многократного повторения скаляризации с разными весами, инженер получает сразу приближение всего фронта Парето — набор кандидатов на разных уровнях компромисса «точность против размера», из которого можно выбрать финальную модель под конкретное устройство развёртывания.

Почему это важно

Ценность NSGA-II и подобных ему эволюционных многокритериальных алгоритмов в том, что они дают приближение всего фронта Парето за один прогон оптимизации, а не отдельную точку за один прогон, как это происходит при скаляризации. Это особенно важно на ранней стадии проекта, когда веса приоритетов ещё не согласованы с заказчиком или продакт-командой: вместо того чтобы гадать с весами заранее и переобучать модели заново при каждом их изменении, можно один раз построить приближённый фронт Парето и затем обсуждать выбор конкретной точки на нём уже на основе фактических данных о доступных компромиссах, а не абстрактных предположений.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Модель X имеет точность 90% (ошибка 10%) и задержку 50 мс. Модель Y имеет точность 92% (ошибка 8%) и задержку 40 мс. Определи, доминирует ли одна модель другую.

Задание 2: Модель M1 имеет ошибку 5% и размер 100 МБ. Модель M2 имеет ошибку 5% и размер 120 МБ. Определи отношение доминирования.

Задание 3: Модель P имеет ошибку 3% и задержку 200 мс. Модель Q имеет ошибку 6% и задержку 90 мс. Определи, есть ли доминирование.

Задание 4: Сформулируй своими словами (без формул) два условия, которые обязательно должны выполняться, чтобы решение A доминировало решение B.

Задание 5: Даны нормализованные значения модели K: $f_1=0{,}4$, $f_2=0{,}7$. Веса $w_1=0{,}6$, $w_2=0{,}4$. Вычисли взвешенную сумму.

Задание 6: Даны пять точек (ошибка, задержка): $(1,300)$, $(2,200)$, $(2,250)$, $(4,100)$, $(6,90)$. Найди, какие точки не входят во фронт Парето.

Задание 7: Опиши качественно (без вычислений), как выглядит фронт Парето на графике при минимизации двух целей одновременно.

Задание 8: Даны нормализованные значения трёх моделей: A $=(0{,}5, 0{,}9)$, B $=(0{,}7, 0{,}3)$, C $=(0{,}9, 0{,}1)$. При весах $w_1=0{,}5$, $w_2=0{,}5$ вычисли скор каждой и найди победителя.

Задание 9: В лексикографической процедуре приоритет отдан безопасности (первый критерий), затем задержке (второй). Кандидаты: D — безопасность-ошибка $1{,}2\%$, задержка $90$ мс; E — безопасность-ошибка $1{,}2\%$, задержка $60$ мс; F — безопасность-ошибка $2{,}0\%$, задержка $20$ мс. Кого выберет лексикографическая процедура?

Задание 10: Объясни своими словами, почему для двух целевых функций, которые полностью совпадают друг с другом (то есть $f_1(x)=f_2(x)$ для любого $x$), фронт Парето вырождается в единственную точку.

Продвинутые задания (11–20)

Задание 11: Докажи, что отношение доминирования по Парето не является полным (тотальным) порядком — то есть приведи общий аргумент, почему для двух произвольных решений $A$ и $B$ не всегда верно, что либо $A \prec B$, либо $B \prec A$.

Задание 12: Дан набор из шести точек (ошибка, размер в МБ): $(1,500)$, $(2,400)$, $(2,300)$, $(3,300)$, $(5,150)$, $(5,200)$. Найди полный фронт Парето алгоритмом сортировки и сметания.

Задание 13: Для трёх моделей A $=(0{,}3, 0{,}8)$, B $=(0{,}6, 0{,}4)$, C $=(0{,}9, 0{,}1)$ (нормализованные ошибка и задержка) найди победителя при весах $(0{,}8, 0{,}2)$ и отдельно при весах $(0{,}2, 0{,}8)$.

Задание 14: Придумай (или опиши качественно) набор из трёх точек фронта Парето, для которого никакой набор неотрицательных весов взвешенной суммы не выберет среднюю точку. Объясни, почему так происходит.

Задание 15: Объясни на числовом примере, почему отсутствие нормализации искажает результат взвешенной суммы. Возьми ошибку в диапазоне $[0,1]$ (доля) и задержку в диапазоне $[10, 500]$ (миллисекунды), веса $w_1=w_2=0{,}5$, для двух моделей: X — ошибка $0{,}10$, задержка $50$ мс; Y — ошибка $0{,}05$, задержка $400$ мс.

Задание 16: Опиши ситуацию, в которой лексикографический подход и взвешенная сумма дают разные результаты выбора для одного и того же набора кандидатов, и объясни, почему.

Задание 17: Проведи недоминируемую сортировку для популяции из пяти решений (минимизация обеих целей): $R1=(2,7)$, $R2=(4,4)$, $R3=(6,2)$, $R4=(3,8)$, $R5=(5,5)$. Определи фронты $F_1$, $F_2$ и т.д.

Задание 18: Объясни, почему крайним (граничным) точкам фронта Парето в NSGA-II присваивают намеренно завышенное (формально бесконечное) значение crowding distance, и к чему привело бы обратное решение — присвоить им обычное, конечное значение.

Задание 19: Даны четыре кандидата моделей (ошибка %, задержка мс, размер МБ): W $=(3, 200, 500)$, X $=(3, 150, 500)$, Y $=(5, 150, 200)$, Z $=(6, 300, 600)$. Определи, какие из них доминируются, используя доминирование по трём критериям одновременно.

Задание 20: Объясни связь между выпуклостью целевых функций (материал уроков про выпуклые множества и функции) и тем, насколько полно метод взвешенной суммы способен покрыть весь фронт Парето, меняя веса.

Задания-челленджи (21–30)

Задание 21: Докажи, что при выпуклых $f_1, \dots, f_m$ и выпуклом $X$ решение $x^*$, минимизирующее взвешенную сумму $\sum w_i f_i(x)$ с весами $w_i > 0$ для всех $i$, является Парето-оптимальным.

Задание 22: Спроектируй лексикографическую процедуру с допуском (эпсилон) для выбора модели, где строгое лексикографическое сравнение слишком жёстко отсеивает почти равнозначные варианты. Опиши, как именно вводится допуск и в чём риск его слишком большого значения.

Задание 23: Сравни, что нужно изменить в устройстве Simulated Annealing (урок 298) или генетического алгоритма (урок 296), изначально работающих с единственным скалярным значением приспособленности, чтобы превратить их в многокритериальный алгоритм наподобие NSGA-II.

Задание 24: Дан набор из восьми кандидатов моделей с тремя целями (ошибка %, задержка мс, размер МБ): $(2,300,600)$, $(3,250,500)$, $(3,300,400)$, $(4,200,450)$, $(5,150,300)$, $(6,180,250)$, $(7,100,200)$, $(9,90,150)$. Найди фронт Парето по трём критериям.

Задание 25: Опиши идею индикатора гиперобъёма (hypervolume indicator) как способа сравнить качество двух разных приближённых фронтов Парето, полученных, например, разными запусками NSGA-II.

Задание 26: Объясни, в каком практическом сценарии скаляризация с фиксированными весами предпочтительнее полноценного построения всего фронта Парето алгоритмом наподобие NSGA-II, несмотря на то, что NSGA-II даёт больше информации.

Задание 27: Опиши идею метода опорной точки (Чебышева, reference point method) как альтернативной скаляризации и объясни, почему он способен находить точки на невыпуклых участках фронта Парето, в отличие от взвешенной суммы.

Задание 28: Свяжи многокритериальную оптимизацию с условиями Каруша–Куна–Таккера (урок 279, KKT): опиши, как выглядит необходимое условие первого порядка для точки, минимизирующей взвешенную сумму целей со строго положительными весами, если задача не имеет ограничений.

Задание 29: Модель развёртывается на устройстве с жёстким бюджетом задержки не более 100 мс. Есть пять кандидатов с (ошибка %, задержка мс): $(2,250)$, $(4,120)$, $(6,95)$, $(8,60)$, $(12,30)$. Опиши, как жёсткое ограничение по задержке меняет процедуру выбора по сравнению с обычным построением полного фронта Парето.

Задание 30: Спроектируй практический двухэтапный пайплайн выбора модели для продакшена: сначала NSGA-II находит приближённый фронт Парето по нескольким целям, затем применяется лексикографическая фильтрация для финального выбора. Объясни, почему такая комбинация имеет смысл на практике.

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

Ошибка 1. Ищут «единственную лучшую модель» так, будто задача многокритериальна лишь по видимости, а на самом деле сводится к одному числу.

Как выглядит: «давайте просто возьмём модель с самой высокой точностью, остальное не так важно».

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

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

Ошибка 2. Путают «недоминируемое решение» с «одинаково хорошим по всем критериям решением».

Как выглядит: «раз обе модели на фронте Парето, значит они равноценны».

Почему возникает: недоминируемость — это отсутствие строгого превосходства одного решения над другим по всем критериям сразу, а не равенство значений критериев.

Как правильно: решения на фронте Парето могут сильно различаться между собой — на фронте могут одновременно быть модель с ошибкой 2% и задержкой 400 мс, и модель с ошибкой 15% и задержкой 20 мс, — они просто представляют разные, несравнимые компромиссы, а не эквивалентные варианты.

Ошибка 3. Применяют взвешенную сумму к ненормализованным критериям разного масштаба.

Как выглядит: складывают долю ошибки (порядка 0,01–0,2) с задержкой в миллисекундах (порядка 10–500) с формально равными весами.

Почему возникает: веса кажутся «равными приоритетами» без учёта того, что численные диапазоны критериев сами по себе очень разные.

Как правильно: прежде чем применять веса, привести все критерии к сопоставимому масштабу — например, нормализовать каждый в диапазон $[0,1]$ относительно его минимума и максимума среди кандидатов, как показано в разделе про скаляризацию.

Ошибка 4. Считают, что взвешенная сумма при переборе весов способна найти любую точку фронта Парето.

Как выглядит: «если фронт не устраивает, просто подберём другие веса и получим нужную точку».

Почему возникает: интуитивно кажется, что раз веса можно менять непрерывно, то и достижимые точки должны покрывать весь фронт непрерывно.

Как правильно: взвешенная сумма гарантированно достаёт только точки на выпуклой оболочке фронта Парето; для невыпуклых («вогнутых») участков фронта нужны другие методы скаляризации (например, метод Чебышева из задания 27) или прямые многокритериальные алгоритмы вроде NSGA-II.

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

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

Почему возникает: кажется, что учесть больше критериев — значит получить более полную и честную картину.

Как правильно: с ростом числа целей почти все решения становятся взаимно несравнимыми (см. задание 24), фронт Парето разрастается настолько, что теряет практическую пользу для выбора; лучше заранее превратить часть «второстепенных» критериев в жёсткие ограничения (как в задании 29) и оставить для настоящей многокритериальной оптимизации два-три по-настоящему конфликтующих и решающих критерия.

Ошибка 6. Игнорируют лексикографический подход там, где веса принципиально не могут отразить приоритет.

Как выглядит: пытаются подобрать веса для критерия безопасности так, чтобы он «почти всегда» побеждал, вместо явного лексикографического приоритета.

Почему возникает: привычка использовать один универсальный инструмент (взвешенную сумму) для всех случаев.

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

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

• Многокритериальная оптимизация (multi-objective optimization) одновременно оптимизирует несколько целевых функций $f_1, \dots, f_m$, которые, как правило, конфликтуют между собой — улучшение одной цели обычно ухудшает другую.

• Когда цели конфликтуют, единственного «оптимального» решения в привычном смысле не существует — вместо него есть целое множество взаимно несравнимых компромиссов.

• Решение $A$ доминирует решение $B$, если $A$ не хуже $B$ по каждому критерию и строго лучше хотя бы по одному; если по разным критериям лучше разные решения, они несравнимы.

• Множество всех недоминируемых решений называется множеством Парето, а его образ в пространстве целевых функций — фронтом Парето; при двух целях фронт визуализируется как убывающая ступенчатая линия.

• Скаляризация методом взвешенной суммы сводит несколько целей к одной линейной комбинации с весами, но требует предварительной нормализации критериев и достаёт только точки на выпуклой оболочке фронта.

• Лексикографический подход упорядочивает цели по строгому приоритету и оптимизирует по очереди — подходит там, где один критерий не подлежит компенсации другим, но требует аккуратного допуска (эпсилон) на «практическое равенство».

• NSGA-II строит недоминируемые фронты внутри популяции решений и использует метрику crowding distance для поддержания разнообразия — это позволяет получить приближение всего фронта Парето за один прогон оптимизации.

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

• Условие стационарности взвешенной суммы целей с неотрицательными весами — прямое обобщение условий оптимальности (KKT), с которых начинался весь блок «Оптимизация».

• Перевод жёстких требований (например, бюджет задержки) из статуса «цель» в статус «ограничение допустимого множества» часто упрощает многокритериальную задачу, не теряя её практическую суть.

Связь с темами курса

Что нужно было знать до этого урока

Этот урок опирается на весь материал блока «Оптимизация», а не только на непосредственно предыдущий урок о байесовской оптимизации. Понятие Парето-оптимальности как обобщения условия стационарности градиента напрямую связано с условиями Каруша–Куна–Таккера (урок 279), а свойства выпуклых множеств и функций (уроки 277–278) объясняют, почему взвешенная сумма достаёт не весь фронт Парето, а только его выпуклую часть. Идея NSGA-II прямо продолжает линию метаэвристик — эволюционных и генетических алгоритмов (уроки 295–296), — только вместо скалярной приспособленности особи используется послойное ранжирование по недоминированию.

Итог блока «Оптимизация» (276–300)

Этот урок завершает большой, двадцатипятиурочный блок «Оптимизация» — и стоит на секунду оглянуться на весь пройденный путь. Блок начался с фундамента: понятия выпуклых множеств и функций (уроки 277–278) и условий оптимальности Каруша–Куна–Таккера (урок 279), которые дают язык для описания того, что вообще значит «оптимальное решение» и когда его можно распознать по локальным условиям на градиент. Дальше блок перешёл к точным, структурным методам для задач специального вида: линейное программирование и симплекс-метод (уроки 280–281), двойственность (урок 282), квадратичное и целочисленное программирование (уроки 283–284) — классы задач, для которых существуют мощные точные или почти точные алгоритмы, опирающиеся на их особую структуру.

Следующая большая часть блока — это градиентные и околоградиентные методы численной оптимизации гладких (и не совсем гладких) функций: градиентный спуск и его стохастическая версия (уроки 285–286), метод Ньютона и квазиньютоновские методы (уроки 287–288), метод сопряжённых градиентов (урок 289), субградиентные и проксимальные методы для негладких задач (уроки 290–291), покоординатный спуск (урок 292) и адаптивные методы вроде Adam (урок 293) — это тот самый инструментарий, на котором в буквальном смысле обучается почти каждая современная нейросеть.

Дальше блок сместился туда, где градиента либо нет, либо он бесполезен: методы нулевого порядка (урок 294) и целое семейство метаэвристик — эволюционные и генетические алгоритмы (уроки 295–296), Particle Swarm Optimization (урок 297) и Simulated Annealing (урок 298) — каждый со своей метафорой (естественный отбор, рой частиц, остывающий металл), но общей идеей управляемого случайного поиска там, где градиентные методы неприменимы. Байесовская оптимизация (урок 299) добавила к этому арсеналу более «расчётливый» подход — осознанный выбор следующей точки на основе вероятностной модели уже накопленных наблюдений, особенно ценный, когда каждое вычисление целевой функции дорого.

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

Где это нужно в жизни

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

🏭 Инженерное проектирование. Авиастроение, автомобилестроение и микроэлектроника используют многокритериальную оптимизацию для поиска компромиссов между весом, прочностью, стоимостью и энергоэффективностью конструкций — область, где идеи фронта Парето применяются дольше и системнее всего.

💰 Финансы и управление портфелем. Задача Марковица — компромисс между ожидаемой доходностью и риском портфеля — классический пример двукритериальной оптимизации, лежащий в основе современной портфельной теории.

🤖 AutoML и подбор архитектур нейросетей. Современные инструменты вроде Optuna и Ax/BoTorch включают многокритериальные алгоритмы (в том числе NSGA-II и многокритериальные варианты байесовской оптимизации) именно для одновременного поиска по точности, числу параметров и вычислительной стоимости модели.

Интересные факты

• Знаменитое «правило 80/20», давшее имя всей области, изначально описывало распределение земельной собственности и доходов в Италии конца XIX века и не имело прямого отношения к вычислительной оптимизации — связь с многокритериальной оптимизацией возникла позже, через более общее понятие Парето-оптимальности в экономике благосостояния.

• Статья Деба, Пратапа, Агарвала и Мейяриван про NSGA-II 2002 года — одна из самых цитируемых работ в области эволюционных вычислений; несмотря на выход более новых алгоритмов (NSGA-III, MOEA/D и другие), NSGA-II по сей день остаётся стандартным baseline-алгоритмом почти в каждой библиотеке многокритериальной оптимизации, включая pymoo, DEAP и Optuna.

• Понятие «Парето-фронтир» (Pareto frontier) настолько прижилось за пределами исходной экономической и инженерной области, что его сегодня используют в дизайне продуктов, спортивной аналитике и даже в описании компромиссов между разными метриками качества текста у языковых моделей — например, между «фактологической точностью» и «креативностью» генерации.

• Инструменты автоматического машинного обучения, объединяющие идеи двух последних уроков этого блока — байесовской оптимизации и многокритериальной оптимизации, — называют многокритериальной байесовской оптимизацией (multi-objective Bayesian optimization); один из известных методов такого рода, expected hypervolume improvement (qEHVI), напрямую использует индикатор гиперобъёма из задания 25 этого урока как acquisition function.

Лайфхаки

• Прежде чем применять взвешенную сумму, всегда нормализуй все критерии к сопоставимому диапазону (например, делением на разброс значений среди кандидатов) — иначе критерий с большими абсолютными числами незаметно задавит остальные, даже если формальные веса кажутся сбалансированными.

• Визуализируй фронт Парето напрямую (2D scatter-график при двух целях, 3D-график или parallel coordinates при трёх и более) прежде чем обсуждать выбор конкретного решения с командой — наглядная картина компромисса убеждает лучше таблицы чисел и часто сама подсказывает, какая часть фронта заслуживает более пристального внимания.

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

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

• Для быстрого исследования пространства компромиссов на ранней стадии проекта запускай NSGA-II (или аналог) один раз, чтобы получить приближённый фронт Парето целиком, и уже после этого обсуждай с командой конкретную точку выбора — это избавляет от необходимости пересчитывать всё заново при каждом изменении приоритетов.

• Ограничивай число одновременно оптимизируемых целей двумя-тремя по-настоящему решающими критериями — остальные, менее значимые аспекты задачи лучше зафиксировать как ограничения или вовсе исключить из формальной постановки, иначе фронт Парето разрастётся до практически бесполезного размера.

На этом двадцатипятиурочный блок «Оптимизация» подходит к своему завершению — и это действительно большой пройденный путь: от строгого языка выпуклости и условий Каруша–Куна–Таккера, через точные методы линейного и квадратичного программирования, через всё семейство градиентных методов, на которых буквально обучается каждая современная нейросеть, через метаэвристики и байесовскую оптимизацию для задач без градиента — и вплоть до сегодняшнего снятия последнего упрощения: признания того, что реальные инженерные задачи почти никогда не сводятся к одной-единственной цели. Ты прошёл этот путь целиком, и теперь у тебя есть общий язык и рабочий набор инструментов для практически любой оптимизационной задачи, с которой ты столкнёшься в работе с данными и моделями. Дальше курс переходит от математического фундамента к его прямому практическому применению — в следующей главе ты начнёшь разбирать основы машинного обучения с самого первого, но принципиального вопроса: что такое машинное обучение и чем оно отличается от классического программирования.