Иерархический каскад: три уровня поиска, делящих один бюджет
Статья про настройку поиска заканчивается практичным советом: настраивайте, если есть репрезентативный набор задач, иначе берите дефолты. Совет этот опирается на негласное допущение, которое в тексте почти не видно, — что у мета-уровня свой бюджет. Гонки конфигураций тратят прогоны поиска, но эти прогоны никто не отнял у самого поиска: они оплачены отдельной статьёй расходов, обычно ночью в CI.
Уберём допущение. Пусть бюджет один, общий, и всё, что съел верхний уровень, недополучил нижний. Вопрос сразу меняет форму. Было: «помогает ли настройка?» Стало: «окупается ли настройка ровно теми оценками фитнеса, которые она отняла у поиска?» Это другой вопрос, и ответ на него, как выяснится, другой.
Заодно появляется третий уровень, которого в схеме «настройка над поиском» нет вовсе: тот, кто решает, сколько бюджета отдать каждой задаче и когда остановиться. Получается иерархия из трёх уровней — управление временем, настройка параметров, поиск решения, — и такая иерархия имеет название и проработанную постановку.
Постановка каскада GA0 → GA1 → GA2, из которой сделана эта статья, взята из диссертационного
исследования М. Ф. Зимнурова по специальности 2.3.1 «Системный анализ, управление и обработка
информации, статистика». Работа непубличная, поэтому здесь нет ни одной цитаты — только постановки,
изложенные своими словами, с явной пометкой, что адаптировано. Результаты автора получены на
другой задаче — планирование и перепланирование задач разработки ПО, — и на нашу задачу как
данность не переносятся; где его числа, там сказано, что они его.
Наша задача — та же, что в предыдущей статье: по парам «вход → выход» синтезировать спецификацию, фитнес считает компилятор. Эксперимент ниже — 100 прогонов, 800 наблюдений, 19 360 000 обращений к фитнесу. Все числа в тексте измерены; ни одно не приведено по памяти.
Статья предполагает знакомство с механикой ГА (Генетические алгоритмы), с настройкой параметров как задачей мета-уровня (Настройка самого поиска) и с планированием бюджета оценок (Дорогой фитнес). Ничего из этого здесь не пересказывается.
Сама схема
GA0 → GA1 → GA2разобрана как архитектурное решение в статье про каскад — что делает каждый уровень и зачем их вообще разделять. Здесь та же схема измеряется: уровни делят один бюджет, и вопрос ставится не «как устроено», а «окупается ли».
Три уровня и одно разделение ролей
Идея каскада — не «настройка над поиском», а явное распределение обязанностей между тремя уровнями, каждый из которых распоряжается своим ресурсом.
решает: сколько бюджета
дать задаче и когда остановиться"] GA1["GA1 — параметры поиска
решает: с какими θ
работает нижний уровень"] GA2["GA2 — решение
ищет саму спецификацию"] FIT["фитнес: компилятор,
типы, примеры, инварианты"] GA0 -->|"бюджет ступени t_k, порог c_min"| GA1 GA1 -->|"вектор параметров θ*"| GA2 GA2 -->|"обращения к фитнесу"| FIT GA2 -.->|"чёткость c(X): доля пройденных примеров"| GA0 GA2 -.->|"качество θ и её стоимость"| GA1
Пунктир — обратные связи, и они здесь важнее сплошных стрелок. Вниз идут ресурс и настройки, вверх — одна-единственная величина на каждом канале: наверх GA0 уходит достигнутая чёткость, наверх GA1 — качество конфигурации вместе с её вычислительной стоимостью. Всё остальное уровни друг о друге не знают.
| Уровень | Чем распоряжается | Что кодирует | Критерий | Когда останавливается |
|---|---|---|---|---|
| GA0 | бюджетом | ступени бюджета $t_k$ | минимально достаточное $t$ | первое $c(X) \ge c_{\min}$ |
| GA1 | параметрами | вектор $\theta$ из 18 генов | $\mathbb{E}J(\theta) + \mu C(\theta)$ | исчерпание своей доли бюджета |
| GA2 | решением | дерево правил спецификации | вектор из четырёх целей | бюджет ступени либо порог |
Формально уровень GA0 ищет минимально достаточное время:
$$t_k^{}=\min{,t\in[0,t_{\max}] ;\mid; c(X^{}(\theta^{*},t),t)\ge c_{\min},}$$
где $c$ — коэффициент чёткости решения, а $c_{\min}$ — требуемый порог. Смысл этой формулы стоит проговорить отдельно, потому что он управленческий, а не алгоритмический. Обычный поисковый цикл останавливается по исчерпании бюджета и отдаёт лучшее, что успел. Здесь наоборот: как только качество достигло заявленного порога, всё оставшееся время объявляется лишним. Ресурс — не то, что надо израсходовать, а то, что надо не потратить.
Уровень GA1 ставится как задача мета-оптимизации:
$$\theta^{}=\arg\min_{\theta\in\Theta}\bigl[,\mathbb{E}J(X^{}(\theta,t_k),t_k;\theta)+\mu C(\theta),\bigr]$$
где $C(\theta)$ — вычислительная стоимость конфигурации, а $\mu$ — цена этой стоимости в единицах качества. Второе слагаемое — то самое место, где схема отличается от гонок конфигураций из тринадцатой статьи: конфигурация оценивается не только тем, насколько она хороша, но и тем, во сколько обходится.
Что пришлось поменять при переносе
Постановка написана под другую задачу, и часть её на нашей не работает буквально. Изменения ниже перечислены полностью — не потому что их много, а потому что молчаливая подмена постановки и есть самый частый способ получить красивый результат.
Время → обращения к фитнесу. Секунды на общей машине с чужой нагрузкой несопоставимы между прогонами. Головной метрикой объявлено число обращений к фитнес-функции. Это же решение принял и сам автор постановки во второй серии своих экспериментов.
Коэффициент чёткости. У автора $c$ определён накоплением приращений штрафного функционала: $c = 1-e^{-\lambda I}$, где $I$ копит убывание штрафа по поколениям. Конструкция опирается на скаляризацию — свёртку критериев весами. У нас свёртки нет намеренно (почему — в статье про многокритериальность и в предыдущей главе), поэтому $c$ задан прямо: доля обучающих примеров, пройденных выбранным ответом. Величина ограничена единицей, не убывает по ходу поиска, и в формуле остановки играет ту же роль. Это замена, а не пересказ: сравнивать наши значения $c$ с авторскими нельзя, у них общее только имя.
Многокритериальность. Автор сводит четыре критерия скаляризацией $J=\sum_k \omega_k \hat f_k$, причём веса $\omega$ подбирает как раз GA1. Логика у него последовательная: претензия к литературе формулируется не как «скаляризация плоха», а как «курс обмена между критериями назначается молча», и лечится это тем, что веса перестают быть константами и становятся предметом настройки на среднем уровне. Мы контролируем тот же компромисс иначе — фронтом вместо весов. Это осознанное расхождение с источником, а не упущение.
Бюджет между задачами. У автора GA0 распоряжается временем внутри одного запроса. У нас восемь задач и общий бюджет, и ранняя остановка на лёгкой задаче высвобождает ресурс, который можно отдать трудной. Это расширение постановки — и, как окажется, единственный уровень каскада, от которого на нашем ландшафте вообще был толк.
Стоимость GA1 списывается с общего бюджета. У автора она в бюджет явно не входит.
И одна оговорка, которую опускать нельзя: у автора GA0 не является генетическим алгоритмом. Ни популяции, ни операторов на нулевом уровне в его тексте нет — это монотонная лестница по $t$ с проверкой порога. Слово «каскад генетических алгоритмов» относится к уровню в иерархии, а не к методу на нём. Здесь сохранено ровно это, без домысливания.
Валюта: чем именно меряется бюджет
Скучный раздел, который решает исход всего эксперимента.
Кандидат оценивается вызовом функции фитнеса. Результаты мемоизированы: повторно встреченная особь берётся из кэша и компилятор не вызывается. Значит, есть две разные величины — обращений к фитнесу и вызовов компилятора, — и выбор между ними в качестве валюты бюджета определяет, кто победит.
Если считать бюджет вызовами компилятора, то сошедшаяся популяция перестаёт тратить бюджет: все её особи уже в кэше. Одноуровневый прогон может тогда крутиться сколь угодно долго, ничего не находя и ничего не тратя, и «равный бюджет» начнёт сравнивать неравные вещи.
Поэтому валюта — обращение к фитнесу, включая попадание в кэш. Их ровно popSize на поколение,
и это делает пересчёт очевидным: бюджет 24 200 обращений на задачу — те же
самые 200 особей на 121 поколение, с которыми работал одноуровневый прогон из предыдущей статьи.
Вызовы компилятора считаются отдельно и идут в отчёт как стоимость, а не как бюджет.
Если два алгоритма делят один ресурс, сначала назовите единицу этого ресурса — и проверьте, может ли один из них потреблять её нулевыми порциями. Если может, единица выбрана неправильно.
Разница между валютами при этом измерена и велика: у одноуровневой руки вызовом компилятора кончается 65,4 % обращений, у каскада — 70,0 %, а у руки, которой настройка досталась бесплатно, — 86,5 %. Верхний уровень порождает больше разных кандидатов и потому стоит дороже при том же числе обращений. Именно эту величину и берёт на себя слагаемое $\mu C(\theta)$.
Пять рук при одном бюджете
Прошлый эксперимент этого проекта расширял пространство поиска одновременно с ростом бюджета и не смог потом разделить эффекты; автор назвал это дыркой в измерении, а не результатом. Чтобы не повторить, руки разведены заранее.
| Рука | Что это | Какой вопрос закрывает |
|---|---|---|
single |
одноуровневый ГА, дефолтные параметры, весь бюджет задачи в одном прогоне | базовая линия |
cascade |
GA0 → GA1 → GA2, стоимость всех уровней списывается | основная гипотеза |
ga0 |
GA0 → GA2 без среднего уровня | что даёт лестница перезапусков и перераспределение бюджета сама по себе |
cascade-free-ga1 |
каскад, но настройка бесплатна | помогает ли настройка вообще, отдельно от вопроса «окупается ли» |
antagonist |
GA0 → root(A⁺, A⁻) → GA2 | другой средний уровень при тех же накладных расходах — следующая статья |
Две средние руки — не украшение. ga0 отделяет «перезапуски и перераспределение» от «настройки
параметров»: это два разных механизма, и слитый результат ничего бы не сказал о том, какой из них
сработал. cascade-free-ga1 разводит два вопроса, которые звучат одинаково, но требуют разных
ответов. Тот же приём применил и автор постановки, отдельно приводя результат с амортизированной
калибровкой.
Парность строгая: одни и те же восемь задач, то же разбиение обучающие/отложенные, те же 20 зёрен, и на каждом зерне каждая рука получает ровно 193 600 обращений. Одноуровневая рука не останавливается по достижении порога — она тратит бюджет до конца, и это делает базовую линию сильнее, а не слабее.
Сам замер прогонялся дважды, двумя независимыми запусками драйвера. Одноуровневая рука совпала на 100,0 % пар «задача × зерно» из 160: поиск детерминирован по зерну, и это проверено, а не заявлено.
Что получилось
Машина: AMD Ryzen 7 9700X 8-Core Processor, 16 потоков, 249 ГБ памяти. Машина общая — рядом считают чужие процессы, — поэтому загрузка записана в отчёт: 13,2 до запуска и 15,3 после. Стена 6,8 мин, сумма собственного времени прогонов 103,7 мин: разница между этими двумя числами и есть всё, что дала параллельность.
| Рука | решено задач из 8 | разрыв train/holdout | сумма размахов по зёрнам | обращений до решения | доля бюджета верхнему уровню |
|---|---|---|---|---|---|
single |
4,0 | 30,0 п.п. | 1,875 | 4 400 | 0,0 % |
cascade |
4,0 | 26,6 п.п. | 1,375 | 11 726 | 26,0 % |
ga0 |
4,0 | 22,9 п.п. | 1,125 | 5 200 | 0,0 % |
cascade-free-ga1 |
4,0 | 28,0 п.п. | 1,250 | 7 512 | 21,1 % |
antagonist |
4,0 | 30,0 п.п. | 1,625 | 7 807 | 26,5 % |
Первый столбец одинаков у всех пяти рук. Это и есть главный результат, и он отрицательный.
Парные знаковые тесты — по каждой паре «задача × зерно» против одноуровневого прогона на том же зерне, двусторонние, по ненулевым парам:
| Рука | чёткость $c$ | разрыв train/holdout | различных точек на фронте |
|---|---|---|---|
cascade |
+19 / −43, $p$ = 0,0032 | +79 / −49, $p$ = 0,0101 | +39 / −37, $p$ = 0,9088 |
ga0 |
+21 / −34, $p$ = 0,1048 | +67 / −49, $p$ = 0,1141 | +43 / −28, $p$ = 0,0959 |
cascade-free-ga1 |
+25 / −31, $p$ = 0,5044 | +71 / −54, $p$ = 0,1521 | +45 / −27, $p$ = 0,0444 |
Читать это надо так. Полный каскад значимо хуже одноуровневого поиска по чёткости. Абляция без среднего уровня — уже не значимо хуже. Каскад, которому настройка досталась даром, — не хуже вовсе. Разница между тремя строками одна: сколько стоил средний уровень. Отсюда и вывод: проигрывает не иерархия, проигрывает цена среднего уровня.
Проверка первая: три задачи, которые не решались никогда
В одноуровневом прогоне предыдущей статьи три задачи из восьми не решались точной целью ни при каком зерне: insurance-premium, logistics-shipping, telecom-bill. Ландшафт там описан как «плато с иглами» — точное совпадение даёт награду только при полном сходстве до последнего рубля, и поиску не за что зацепиться. Именно такие задачи каскад и должен был лечить: если параметры по умолчанию не годятся, их подберут; если бюджета мало, его перераспределят.
| Задача | single |
cascade |
ga0 |
cascade-free-ga1 |
|---|---|---|---|---|
insurance-premium |
1/20 | 0/20 | 0/20 | 0/20 |
logistics-shipping |
1/20 | 0/20 | 0/20 | 0/20 |
telecom-bill |
0/20 | 0/20 | 0/20 | 0/20 |
Ответ: нет. На трёх трудных задачах каскад решил 0/60 наблюдений, одноуровневый поиск — 2/60. Разницу между двумя такими числами отличить от случайности нельзя, и утверждать «каскад отнял решения» было бы натяжкой. Правильная формулировка скромнее и всё равно достаточна: на трудных задачах иерархия не дала ничего, а цену за себя взяла.
Заодно всплыла деталь, которой в прошлом замере не было видно, потому что зёрен было пять, а не двадцать: на двух из трёх задач одноуровневый поиск всё-таки решает — примерно раз на двадцать прогонов. Утверждение «не решается ни при каком зерне» было верно для пяти зёрен и оказалось слишком сильным для двадцати. Лучшая достигнутая чёткость на трудных задачах: 1,000 у одноуровневого против 0,875 у каскада.
Проверка вторая: разброс по зёрнам
Уменьшить разброс — это ровно то, ради чего параметры настраивают: если алгоритм на одной и той же задаче даёт то решение, то ничего, виноваты либо параметры, либо ландшафт.
Медиана размаха $c$ по зёрнам у каскада — 0,188 — совпала с одноуровневой (0,188). Медиана здесь плохой инструмент: восемь задач, из них две с нулевым размахом всегда. Сумма размахов по восьми задачам различает руки лучше:
| Рука | сумма размахов | задач, где зерно вообще меняет исход |
|---|---|---|
single |
1,875 | 7/8 |
cascade |
1,375 | 6/8 |
ga0 |
1,125 | 5/8 |
cascade-free-ga1 |
1,250 | 6/8 |
Разброс действительно падает — и больше всего у руки, в которой настройки параметров нет вообще. Устойчивость даёт не GA1, а лестница перезапусков: три независимых старта с растущим бюджетом вместо одного длинного прогона усредняют невезение с начальной популяцией. Ровно тот же механизм, что даёт рестарт в портфелях из тринадцатой статьи, — и он не требует ни одного уровня иерархии сверху.
Проверка третья: съедает ли верхний уровень бюджет впустую
Съедает. Средний уровень взял 26,0 % всего потраченного, то есть 6 252 обращений на задачу в среднем. Обращений до первого решения у каскада 11 726 против 4 400 у одноуровневого — почти втрое дороже за тот же ответ.
Прямая проверка — прогнать каскад при разных долях бюджета $\rho$, отданных верхнему уровню:
| $\rho$ | решено задач из 8 | медиана $c$ | разрыв train/holdout | ушло на верхний уровень |
|---|---|---|---|---|
| 0,05 | 4,0 | 0,938 | 21,8 п.п. | 80 134 |
| 0,15 | 4,0 | 0,938 | 26,0 п.п. | 228 825 |
| 0,25 | 3,5 | 0,875 | 22,9 п.п. | 402 158 |
| 0,40 | 3,0 | 0,875 | 28,1 п.п. | 631 531 |
Кривая монотонная и смотрит вниз: чем больше отдать верхнему уровню, тем хуже итог. Оптимум по $\rho$ лежит на левом краю проверенного диапазона, то есть настолько близко к нулю, насколько позволяет сетка. Это и есть количественный ответ на вопрос из заголовка раздела.
Почему GA1 ничего не нашёл
Отрицательный результат полезен ровно настолько, насколько понятен его механизм. Здесь он понятен и измерен.
Хромосома $\theta$ — 18 генов: размер популяции, вероятности скрещивания и мутации, размер турнира, число мутаций подряд, доля свежих случайных особей, доля одноточечного скрещивания, глубина инициализации и вектор весов по десяти операторам мутации. Вот что GA1 из этого выбрал:
| Ген | дефолт | медиана выбранного | размах выбранного |
|---|---|---|---|
| размер популяции | 200 | 200 | 40 – 390 |
| вероятность скрещивания | 0,850 | 0,836 | 0,305 – 0,997 |
| вероятность мутации | 0,900 | 0,721 | 0,308 – 0,981 |
| размер турнира | 2,0 | 3,0 | 2,0 – 6,0 |
| доля свежих особей | 0,000 | 0,036 | 0,000 – 0,298 |
| доля одноточечного скрещивания | 0,750 | 0,732 | 0,221 – 0,990 |
Медианы почти совпадают с дефолтами, размахи занимают почти всё пространство $\Theta$. Это подпись шума, а не настройки: GA1 возвращает случайную точку, центрированную на значении по умолчанию.
Причина в первом столбце соседней таблицы. При равном бюджете GA1 успевает попробовать медиану 2,0 конфигурации на ступень, максимум 4. Гонка конфигураций на двух участниках — это не гонка. И в 43,5 % случаев из 485 лучшей оказывалась та самая конфигурация по умолчанию, с которой начинали, — то есть уровень тратил бюджет и возвращал ровно то, что ему дали на входе.
Арифметика тут неумолимая, и её стоит проделать до запуска, а не после. Одна честная оценка конфигурации — это целый прогон поиска, да ещё на нескольких зёрнах, иначе меряется удача. У нас зонд стоит 600 обращений на 2 зёрнах. При бюджете задачи 24 200 и доле $\rho$ = 0,25 верхнему уровню достаётся меньше десятка зондов на всю задачу. Настройка параметров при общем бюджете становится осмысленной начиная с той величины бюджета, при которой мета-уровню хватает на десятки прогонов, — а до неё она гарантированно шум.
И это же объясняет, почему схема работает в литературе и не работает здесь. Гонки конфигураций предполагают набор похожих инстансов, по которым конфигурация переносится. У нас восемь задач, каждая со своим ландшафтом, и настройка идёт под одну задачу — то есть в терминах тринадцатой статьи это чистое переобучение мета-уровня, только без второй половины сделки: перенести настройку не на что.
Отдельно стоит сказать, что автор постановки получил на своей задаче — планирование и перепланирование задач разработки ПО — такой же по знаку результат: в его серии экспериментов конфигурация, выбранная средним уровнем, не показала преимущества над фиксированной, а с учётом амортизированной стоимости калибровки число оценок целевой функции заметно выросло. Совпадение знака на двух разных задачах и двух разных ландшафтах весит больше, чем любой из двух замеров по отдельности.
Числовые таблицы автора здесь не приводятся: работа непубличная, а эта её часть на момент письма не прошла рецензирование. Ссылаться на неопубликованные числа в учебном тексте нельзя — поэтому от неё взят только знак результата, и он помечен как чужой. Все числа в таблицах выше — наши.
Единственное, что каскад улучшил
По одному показателю каскад базовую линию обошёл, и показатель этот не тот, ради которого его строили: разрыв между обучающими и отложенными примерами. Медиана падает с 30,0 п.п. у одноуровневого до 26,6 п.п. у каскада и до 22,9 п.п. у руки без среднего уровня; знаковый тест для каскада даёт $p$ = 0,0101.
Объяснение неприятное, но простое, и оно уже сформулировано в предыдущей главе: более сильный оптимизатор переобучается сильнее. Каскад слабее — он дробит бюджет на три перезапуска и часть тратит наверху, — и поэтому находит менее подогнанные под обучающую выборку ответы. Это улучшение в чистом виде куплено ослаблением поиска, а не пониманием задачи, и выдавать его за успех иерархии было бы подтасовкой.
Мощность парето-фронта иерархия не изменила: медиана различных векторов на фронте у всех рук
3,0, и единственная строка со значимым различием —
cascade-free-ga1 ($p$ = 0,0444), где эффект держится на границе
и на единственной руке. Фронт вырождается по причине, к иерархии отношения не имеющей: цели
дискретны и грубы, ничьих очень много.
Композиция этапов: что даёт формализация типами
В исходной постановке рядом с каскадом стоит категориальное описание вычислительного контура: цепочка обработки данных задаётся как композиция этапов, а требование согласованности формулируется как условие на типы — выход каждого этапа корректно типизирован как вход следующего. Автор сам относит этот блок к методологической иллюстрации, а не к доказательной части, и в защищаемую версию работы он не входит. Здесь он полезен ровно одним: у нас есть место, где этот инвариант измерен, и видно, что он покупает и чего не покупает.
Наша цепочка — четыре этапа: геном (дерево правил) → принтер → грамматика → компилятор. Инвариант композиции держится на том, что принтер обратен распознавателю грамматики. Следствие проверяемое: любая мутация и любое скрещивание дают документ, который грамматика принимает. И это подтвердилось — в прошлом прогоне на 1 865 472 оценок ошибок разбора не было ни одной.
А дальше начинается то, ради чего этот раздел здесь. Типы гарантируются не все. Та же мутация свободно порождает «процент от логического признака»: документ разбирается, но не типизируется, и такие особи составили заметную долю популяции. Инвариант композиции проходит ровно по границе между «форма» и «смысл», и всё, что он даёт, — гарантия формы.
Практический вывод из этого один и он не про теорию категорий: формализуйте стык этапов там, где несогласованность типов иначе проявится как загадочное ухудшение метрики. Если после этапа что-то молча обрезается, следующий этап получит объект вне своей области определения, а вы увидите скачок штрафа при неизменном входе и пойдёте искать ошибку в оптимизаторе. Проверять стыки дешевле. Записывать эту проверку языком категорий — вопрос вкуса; она от этого не становится сильнее, и собственного измерения у неё нет.
Когда иерархия всё-таки оправдана
Отрицательный результат ограничен ландшафтом, на котором получен, и границу стоит назвать явно.
| Признак задачи | иерархия окупится | иерархия съест бюджет |
|---|---|---|
| Фитнес | непрерывный, информативный | ступенчатый, плато с иглами |
| Бюджет мета-уровня | десятки прогонов поиска | единицы |
| Набор инстансов | много похожих, настройка переносится | каждая задача своя |
| Разброс параметров | оптимум далеко от дефолта | дефолт уже разумен |
| Стоимость времени | время дороже качества, нужна ранняя остановка | нужен максимум качества |
Верхняя строка — главная. Средний уровень оценивает конфигурацию по результату прогона, и если результат прогона на плато почти всегда один и тот же, сигнала для настройки просто нет. Это не дефект схемы: каскад корректно передаёт наверх то, что есть внизу, а внизу нет ничего.
Зато нижний уровень иерархии — тот, что распоряжается бюджетом, — окупается и здесь. Ранняя остановка на решённой задаче с возвратом остатка в общий котёл ничего не стоит и заметно снижает разброс. Если из трёх уровней внедрять один, это он.
Как воспроизвести
Инструмент лежит рядом с одноуровневым и переиспользует его целиком: отбор, фитнес и геном не переписаны, уровень GA2 — это подкласс острова из соседнего проекта, переопределяющий два метода.
node --test test/cascade.test.mjs # 20 тестов
node src/run.mjs paired --seeds 20 --workers 16 --budget 24200
node src/run.mjs rho --seeds 8 --workers 16 --rhos 0.05,0.15,0.25,0.40
node src/run.mjs parallel --counts 1,2,4,8,16 --seeds 2 --budget 6000
node src/report.mjs
Три места, где легко ошибиться, и как они закрыты.
Задачи не пересобираются. Читается тот же файл собранных задач, на котором сделан одноуровневый прогон, — иначе разбиение обучающие/отложенные не совпало бы и сравнение перестало бы быть парным.
Веса операторов мутации. Настройка состава операторов требует перевзвесить выбор, зашитый константами в чужом файле. Он сделан подменой первого обращения к ГПСЧ, а связь с чужим файлом объявлена тестом: тест читает исходник, сверяет таблицу весов с копией и падает при расхождении. Молчаливой рассинхронизации быть не может.
Бюджет. Счётчик вложенный: дочерний уровень не может выдать больше, чем осталось у родителя, а расход переносится наверх при закрытии. Отдельный флаг отключает перенос — на нём и держится рука «настройка бесплатна».
Замер параллельности сделан на общей машине с чужой нагрузкой, поэтому загрузка записана в каждый отчёт: 4,11 × на 16 потоков при фактической загрузке машины 9,7. Без второго числа первое ничего не значит.
Типичные ошибки
- Не назвать единицу общего ресурса. Пока не сказано, что именно делят уровни, «равный бюджет» — фигура речи. Проверьте, может ли один из сравниваемых алгоритмов потреблять эту единицу нулевыми порциями; если может, единица выбрана неправильно.
- Не списывать стоимость мета-уровня. Настройка, оплаченная из отдельного кармана, почти всегда выглядит полезной. Списанная с бюджета поиска — далеко не всегда.
- Менять два механизма сразу. Иерархия приносит перезапуски, перераспределение бюджета и настройку параметров одним пакетом. Без абляции по каждому механизму результат нечитаем: тут выяснилось, что работает ровно один из трёх.
- Настраивать под одну задачу. Настройка без набора инстансов, на которые её переносить, — это переобучение мета-уровня, только без второй половины сделки.
- Считать медиану там, где половина значений нулевая. Медиана размаха по восьми задачам не различила руки; сумма размахов различила. Смотрите на распределение, прежде чем выбирать сводку.
- Радоваться упавшему разрыву train/holdout. Разрыв падает и от того, что оптимизатор стал слабее. Это надо проверять, а не праздновать.
- Переносить постановку вместе с выводами. Постановка переносится, выводы — нет: они получены на другом ландшафте. Каждый перенесённый вывод обязан быть перемерен.
- Молча подменять определения при переносе. Если формула источника опирается на конструкцию, которой у вас нет, замену надо назвать заменой — иначе одинаковое имя величины создаст впечатление сравнимости там, где её нет.
Мини-итог
- Каскад из трёх уровней при равном бюджете проиграл одноуровневому поиску по чёткости статистически значимо, и ни одной из трёх ранее нерешаемых задач не решил.
- Проигрывает не иерархия, а цена среднего уровня: та же схема с бесплатной настройкой уже не проигрывает, а без среднего уровня — тем более.
- Настройка параметров при общем бюджете упирается в арифметику. Меньше десятка проб на задачу — это шум; медианы выбранных параметров совпали с дефолтами, а почти в половине случаев лучшим оказывался сам дефолт.
- Разброс по зёрнам снижают перезапуски, а не настройка. Лучший результат по устойчивости — у руки, где настройки нет вовсе.
- Уровень управления бюджетом окупается даже там, где остальная иерархия нет: ранняя остановка и возврат остатка стоят почти ничего.
- На плато с иглами мета-уровню нечего наблюдать. Каскад корректно передаёт наверх сигнал, которого внизу нет.
- Тот же по знаку отрицательный результат по среднему уровню получен автором исходной постановки на его собственной задаче — совпадение знака на двух разных задачах весит больше одиночного замера.
Источники
- Зимнуров М. Ф. «Оптимизация итеративных методов управления разработкой программного обеспечения с использованием генетических алгоритмов», диссертация на соискание учёной степени кандидата технических наук, специальность 2.3.1, 2025. Источник постановки каскада GA0 → GA1 → GA2, категориального описания вычислительного контура и антагонистического режима. Работа непубличная.
- Arcuri, Fraser. «Parameter tuning or default values? An empirical investigation in search-based software engineering», EMSE 2013 — почему настройка плохо переносится между инстансами.
- Eiben, Hinterding, Michalewicz. «Parameter control in evolutionary algorithms», IEEE TEC 1999 — классификация «настройка против управления», в которой каскад занимает место между двумя классами.
- Birattari, Stützle, Paquete, Varrentrapp. «A racing algorithm for configuring metaheuristics», GECCO 2002 — гонки конфигураций, с которыми средний уровень каскада сравнивается по назначению.
- Deb, Pratap, Agarwal, Meyarivan. «A fast and elitist multiobjective genetic algorithm: NSGA-II», IEEE TEC 2002 — отбор и constrained domination на уровне GA2.
- Hutter, Hoos, Leyton-Brown. «Sequential model-based optimization for general algorithm configuration», LION 2011 — SMAC; что делают, когда бюджет мета-уровня всё-таки есть.
Смежные статьи трека: настройка поиска, дорогой фитнес, многокритериальная оптимизация, исполняемая спецификация как фитнес.
Что дальше
Средний уровень каскада можно занять не настройкой параметров, а чем-то другим — и вопрос «на что лучше потратить те же накладные расходы» становится осмысленным ровно после того, как выяснилось, что настройка их не отрабатывает. В исходной постановке на это место претендует конструкция, у которой другая логика: не подбирать параметры, а явным решением расширять или сужать саму рабочую область поиска, причём решение принимает арбитр по формуле со штрафом за вычислительную стоимость.
Антагонистический режим: два подагента и явное управление областью поиска