Дорогой фитнес: кэш, суррогатные модели и байесовская оптимизация

Две предыдущие статьи закончились одинаково. Поиск последовательности рефакторингов упёрся в «одна оценка = сборка плюс тесты». Оптимизация конфигурации упёрлась в «одна оценка = развернуть стенд и померить». А весь предыдущий материал трека — генетические алгоритмы, отжиг, рой — молчаливо предполагал, что оценок можно позволить себе десятки тысяч.

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

Арифметика бюджета

Всё планирование поиска сводится к одной формуле:

$$N_{eval} = \frac{T_{wall} \cdot P}{C_{eval}}$$

где $T_{wall}$ — время, которое вы готовы ждать, $P$ — степень параллелизма, $C_{eval}$ — стоимость одной оценки. Подставим цифры.

Правая колонка определяет, какой алгоритм вообще имеет смысл. Генетический алгоритм с популяцией 100 за 200 оценок успеет сделать два поколения — то есть не успеет ничего: это будет случайный поиск с лишними накладными расходами. Отсюда практическое правило:

До 10⁴ оценок — работают любые метаэвристики из первых глав трека. От 10² до 10³ — нужны суррогаты и байесовская оптимизация. Меньше 10² — поиск заканчивается, начинается планирование эксперимента: вы выбираете 30 точек руками, и цена ошибки в выборе точек выше цены выбора алгоритма.

Дальше — четыре уровня борьбы за бюджет, от обязательной гигиены до тяжёлой артиллерии.

Уровень 0: не считать то, что уже посчитано

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

Кэш с канонизацией

Популяционные алгоритмы порождают дубликаты постоянно: элитизм переносит особей без изменений, кроссовер одинаковых родителей даёт их же, мутация иногда возвращает решение в прежнее состояние. На поздних поколениях, когда популяция сошлась, доля повторов измеряется десятками процентов.

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

"""Кэширующая обёртка над дорогой фитнес-функцией."""
from __future__ import annotations

import hashlib
import json
import time
from dataclasses import dataclass, field
from typing import Callable, Hashable


def canonical_key(solution) -> str:
    """Каноническая форма решения -> стабильный ключ кэша.

    Порядок элементов в множестве, порядок ключей в словаре и порядок независимых
    операций в последовательности не меняют смысла решения. Всё это надо
    отсортировать ДО хеширования, иначе кэш будет промахиваться на эквивалентах.
    """
    payload = json.dumps(solution, sort_keys=True, ensure_ascii=False, default=sorted)
    return hashlib.blake2b(payload.encode("utf-8"), digest_size=16).hexdigest()


@dataclass
class CachedFitness:
    """Кэш + статистика + бюджет. Бюджет здесь, а не в алгоритме: так его нельзя обойти."""
    fn: Callable[[Hashable], float]
    budget: int
    _cache: dict[str, float] = field(default_factory=dict)
    hits: int = 0
    misses: int = 0
    seconds: float = 0.0

    def __call__(self, solution) -> float:
        key = canonical_key(solution)
        if key in self._cache:
            self.hits += 1
            return self._cache[key]
        if self.misses >= self.budget:
            raise RuntimeError("бюджет оценок исчерпан")
        started = time.perf_counter()
        value = self.fn(solution)
        self.seconds += time.perf_counter() - started
        self.misses += 1
        self._cache[key] = value
        return value

    @property
    def hit_rate(self) -> float:
        total = self.hits + self.misses
        return self.hits / total if total else 0.0

Два инженерных замечания. Первое: бюджет живёт в оценщике, а не в цикле алгоритма — тогда его невозможно случайно обойти вложенным вызовом. Второе: кэш имеет смысл делать общим для всех запусков (файл, Redis, S3), потому что 30 независимых запусков для статистики по протоколу Arcuri–Briand пересекаются по решениям сильнее, чем кажется.

Инкрементальный пересчёт

Уже дважды встречался в треке: MQ после переноса класса считается за $O(\deg v)$ вместо $O(E)$, покрытие пар после замены значения — за $O(k)$ вместо $O(N k^2)$. Общее правило: если оператор меняет малую часть решения, фитнес обязан уметь пересчитываться по дельте. Это самая выгодная оптимизация в SBSE и почти всегда возможна.

Ранний выход

Если фитнес — сумма неотрицательных вкладов, а вам нужно только «лучше текущего лучшего», считать до конца не нужно:

def suite_runtime(tests, run_one, best_so_far: float) -> float:
    """Суммарное время прогона набора с отсечением.

    Как только частичная сумма превысила лучший известный результат, продолжать
    бессмысленно: полный ответ уже не понадобится. На наборах в тысячи тестов
    отсечение экономит порядка половины работы.
    """
    total = 0.0
    for test in tests:
        total += run_one(test)
        if total >= best_so_far:
            return float("inf")      # заведомо не лучше — дальше не считаем
    return total

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

Параллелизм и его предел

Оценки независимы, поэтому параллелятся почти линейно — но только внутри поколения. Синхронный генетический алгоритм ждёт самую медленную особь: если 99 кандидатов считаются секунду, а один зависает на таймаут в 60 секунд, поколение стоит 60 секунд. Лечения два: steady-state / асинхронная схема (освободился воркер — выдали ему нового кандидата, не дожидаясь остальных) и жёсткие таймауты с назначением худшего фитнеса.

Уровень 1: дешёвые приближения и правильное распределение бюджета

Почти у любой дорогой оценки есть дешёвый суррогат «в лоб»:

Прежде чем строить на приближении поиск, проверьте главное: сохраняет ли оно порядок. Нам не нужна точность, нам нужно, чтобы «лучше по приближению» означало «лучше по-настоящему». Измеряется это ранговой корреляцией на выборке из 30–50 точек, оценённых обоими способами. Ориентир: $\rho > 0.8$ — приближение годится как основной фильтр, $0.5$–$0.8$ — только как предварительный отсев, ниже $0.5$ — приближение врёт, оно хуже, чем ничего, потому что уводит поиск уверенно и в неправильную сторону.

Successive halving и Hyperband

Дальше вопрос: как распределить бюджет между кандидатами, если у оценки есть регулируемая «глубина» (число тестов, длительность замера, число эпох)? Наивно — дать всем поровну. Умно — дать всем понемногу, отсеять половину, оставшимся удвоить.

def successive_halving(configs, evaluate, budget_unit: int, factor: int = 3):
    """Отсев с наращиванием бюджета: дёшево смотрим всех, дорого — только выживших.

    evaluate(config, budget) -> оценка (меньше лучше), budget — «глубина» оценки.
    На каждом раунде выживает 1/factor кандидатов, их бюджет умножается на factor.
    """
    alive = list(configs)
    budget = budget_unit
    history = []
    while len(alive) > 1:
        scored = sorted((evaluate(c, budget), c) for c in alive)
        history.append((len(alive), budget, scored[0][0]))
        keep = max(1, len(alive) // factor)
        alive = [c for _, c in scored[:keep]]
        budget *= factor
    return alive[0], history

Арифметика, ради которой всё затевалось. Пусть 27 кандидатов и единица бюджета — «один прогон». Равномерно каждому по 27 единиц — это 729 единиц. Через successive halving:

В 6.75 раза дешевле при том же качестве оценки победителя. Риск известен и называется «сгоревшие поздние цветы»: кандидат, который плох на коротком бюджете, но выигрывает на длинном (типично для медленно прогревающихся систем), будет отсеян. Именно поэтому Hyperband (Li и соавторы, JMLR 2018) запускает несколько «скобок» с разным начальным бюджетом — от «много кандидатов, мало бюджета» до «мало кандидатов, много бюджета» — и берёт лучшее по всем скобкам.

Уровень 2: суррогатная модель внутри эволюции

Идея surrogate-assisted evolutionary algorithms проста: пусть модель, обученная на уже сделанных оценках, предсказывает фитнес; порождаем много кандидатов, реально считаем только тех, кому модель пророчит успех. Обзор направления — Jin, «Surrogate-assisted evolutionary computation: Recent advances and future challenges», Swarm and Evolutionary Computation, 2011.

Три правила, без которых схема разваливается:

1. Всегда оценивать честно долю случайных кандидатов (обычно 10–20 %). Иначе модель обучается только на области, куда сама же и привела, — классический замкнутый цикл, где поиск оптимизирует ошибку модели, а не задачу.
2. Следить за ошибкой предсказания на честно оценённых точках. Растущая ошибка — сигнал переобучить модель или увеличить долю реальных оценок.
3. Хранить архив всех честных оценок. Он же датасет для модели, он же кэш, он же материал для отчёта «что вообще пробовали».

Уровень 3: байесовская оптимизация

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

Обратите внимание на форму синей полосы: рядом с уже сделанными замерами неуверенность стягивается в точку, между ними — раздувается. Максимум EI никогда не приходится на уже измеренную точку: повторять известное бессмысленно.

Классическая работа, с которой всё началось, — Jones, Schonlau, Welch, «Efficient Global Optimization of Expensive Black-Box Functions», Journal of Global Optimization, 1998; современный обзор — Shahriari и соавторы, «Taking the Human Out of the Loop: A Review of Bayesian Optimization», Proceedings of the IEEE, 2016.

Гауссовский процесс и EI на чистом Python

Ниже — минимальная, но настоящая реализация: ядро RBF, разложение Холецкого, предсказание среднего и дисперсии, критерий Expected Improvement для минимизации.

"""Байесовская оптимизация: GP + EI, без внешних библиотек."""
import math
import random


def rbf(a: list[float], b: list[float], ell: float) -> float:
    """Ядро: насколько две точки «похожи». ell — характерный масштаб изменений функции."""
    d2 = sum((ai - bi) ** 2 for ai, bi in zip(a, b))
    return math.exp(-0.5 * d2 / (ell * ell))


def cholesky(m: list[list[float]]) -> list[list[float]]:
    """Разложение Холецкого: O(n^3), но n — это число уже сделанных замеров, то есть десятки."""
    n = len(m)
    L = [[0.0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1):
            s = sum(L[i][k] * L[j][k] for k in range(j))
            L[i][j] = math.sqrt(max(m[i][i] - s, 1e-12)) if i == j else (m[i][j] - s) / L[j][j]
    return L


def solve_lower(L, b):
    y = [0.0] * len(b)
    for i in range(len(b)):
        y[i] = (b[i] - sum(L[i][k] * y[k] for k in range(i))) / L[i][i]
    return y


def solve_upper(L, b):
    x = [0.0] * len(b)
    for i in reversed(range(len(b))):
        x[i] = (b[i] - sum(L[k][i] * x[k] for k in range(i + 1, len(b)))) / L[i][i]
    return x


class GP:
    """Гауссовский процесс: предсказывает и значение, и собственную неуверенность."""

    def __init__(self, xs, ys, ell=0.25, noise=0.05):
        self.xs, self.ell, self.noise = xs, ell, noise
        self.mean = sum(ys) / len(ys)                     # нормировка: GP ждёт нулевое среднее
        var = sum((y - self.mean) ** 2 for y in ys) / max(len(ys) - 1, 1)
        self.std = var ** 0.5 or 1.0
        y = [(v - self.mean) / self.std for v in ys]
        n = len(xs)
        K = [[rbf(xs[i], xs[j], ell) + (noise if i == j else 0.0) for j in range(n)] for i in range(n)]
        self.L = cholesky(K)                              # noise на диагонали = шум измерений
        self.alpha = solve_upper(self.L, solve_lower(self.L, y))

    def predict(self, x) -> tuple[float, float]:
        k = [rbf(x, xi, self.ell) for xi in self.xs]
        mu = sum(ki * ai for ki, ai in zip(k, self.alpha))
        v = solve_lower(self.L, k)
        var = max(1.0 + self.noise - sum(vi * vi for vi in v), 1e-9)
        return mu * self.std + self.mean, math.sqrt(var) * self.std


def expected_improvement(mu: float, sigma: float, best: float, xi: float = 0.01) -> float:
    """EI для минимизации: средний выигрыш относительно лучшего известного значения.

    Первое слагаемое — эксплуатация (там, где предсказано хорошо),
    второе — исследование (там, где модель не уверена). xi слегка смещает баланс к исследованию.
    """
    if sigma < 1e-9:
        return 0.0
    z = (best - xi - mu) / sigma
    cdf = 0.5 * (1.0 + math.erf(z / math.sqrt(2.0)))
    pdf = math.exp(-0.5 * z * z) / math.sqrt(2.0 * math.pi)
    return (best - xi - mu) * cdf + sigma * pdf


def bayes_opt(objective, dim: int, budget: int, seed: int, n_init: int = 5):
    """objective(x) -> измеренное значение (минимизируем). budget считается в ЗАМЕРАХ."""
    rnd = random.Random(seed)
    xs = [[rnd.random() for _ in range(dim)] for _ in range(n_init)]
    ys = [objective(x) for x in xs]
    while len(ys) < budget:
        gp = GP(xs, ys)
        best = min(ys)
        # максимизацию EI решаем грубо — случайными кандидатами: она дешёвая,
        # и точность здесь не важна, важна только дороговизна настоящего замера
        candidates = [[rnd.random() for _ in range(dim)] for _ in range(600)]
        nxt = max(candidates, key=lambda c: expected_improvement(*gp.predict(c), best))
        xs.append(nxt)
        ys.append(objective(nxt))
    return min(ys), xs[ys.index(min(ys))]

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

бюджет  15 оценок | random search: медиана 129.3 мс | BO: медиана 120.3 мс
бюджет  30 оценок | random search: медиана 125.6 мс | BO: медиана 119.7 мс
бюджет  60 оценок | random search: медиана 123.5 мс | BO: медиана 119.4 мс
бюджет 300 оценок | random search: медиана 120.9 мс

Читать это надо так: байесовская оптимизация за 15 замеров даёт то же, что случайный поиск за 300. Если один замер — шесть минут, это разница между полутора часами и полутора сутками. Размер эффекта на 30 запусках при бюджете 30: $\hat{A}_ {12} = 1.0$ — ни один запуск случайного поиска не обошёл ни одного запуска BO. Накладные расходы самого алгоритма — 0.47 секунды на 30 итераций, то есть примерно ноль по сравнению со стоимостью замеров.

Когда BO, а когда эволюция

Про варианты, снимающие ограничения GP, стоит знать три:

• TPE (tree-structured Parzen estimator, Bergstra и соавторы, NeurIPS 2011) моделирует не $p(y \mid x)$, а $p(x \mid y)$ двумя плотностями — «хорошие» и «плохие» точки. Прекрасно работает с категориальными и условными параметрами; это движок по умолчанию в Optuna.
• SMAC (Hutter, Hoos, Leyton-Brown, LION 2011) вместо GP использует случайный лес — он не боится категориальных переменных, условных зависимостей и большой размерности. Про это будет отдельный разговор в следующей статье, потому что SMAC создавался ровно для настройки алгоритмов.
• Батч-BO: если у вас 16 воркеров, выбирать точки по одной — расточительство. Батч-варианты (constant liar, локальные штрафы) выдают сразу $k$ разнесённых точек.

Шум: главный способ обмануть самого себя

Всё, что дорого измеряется, измеряется шумно. Три правила выживания.

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

Сравнивайте статистически, а не по числу. Кандидат A с 118 мс и кандидат B с 120 мс при шуме в 3 мс неразличимы. Механизм «продолжать замерять, пока разница не станет значимой, и отсеивать проигравших» называется racing и подробно разбирается в следующей статье.

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

Как это выглядит в проде

Общая черта всех пяти: суррогат и настоящая оценка живут вместе. Ни одна из этих систем не доверяет модели окончательное решение — модель только распределяет дорогие замеры.

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

Типичные ошибки

1. Оптимизировать алгоритм вместо оценщика. Ускорение фитнеса вдвое эквивалентно удвоению бюджета поиска и почти всегда достигается проще, чем выигрыш от смены алгоритма.
2. Кэш без канонизации. Промахи на эквивалентных решениях сводят выгоду к нулю; хуже того, создают иллюзию, что кэш есть.
3. Приближение без проверки корреляции. Прокси с рангом хуже 0.5 не экономит бюджет, а уверенно уводит поиск не туда.
4. Суррогат без честных случайных оценок. Модель замыкается на собственных ошибках, поиск сходится к «оптимуму модели», которого в реальности нет.
5. BO на неподходящей задаче. Гауссовский процесс на 500-мерном комбинаторном пространстве — потраченное время: там нужен эволюционный поиск.
6. Игнорирование $O(n^3)$ у GP. После нескольких тысяч замеров сам алгоритм начинает стоить дороже оценок; переходите на леса (SMAC) или разреженные GP.
7. Один замер на кандидата в шумной задаче. Вы оптимизируете удачу; финальный результат развалится на перепроверке.
8. Отсутствие финальной валидации. Топ-кандидатов надо перемерять заново — из-за регрессии к среднему победитель поиска почти всегда слабее, чем показался.

Мини-итог

• Планирование поиска начинается с арифметики: сколько оценок влезает в доступное время при доступном параллелизме.
• Уровень 0 (кэш с канонизацией, инкрементальный пересчёт, ранний выход, таймауты, асинхронный параллелизм) даёт больше всех и стоит дешевле всех.
• Дешёвые приближения работают, если сохраняют порядок кандидатов; проверяется ранговой корреляцией на 30–50 точках.
• Successive halving и Hyperband распределяют бюджет неравномерно и экономят кратно: 27 кандидатов обходятся в 108 единиц вместо 729.
• Суррогатная модель внутри эволюции отсеивает бесперспективных кандидатов, но требует доли честных случайных оценок, иначе поиск начнёт оптимизировать ошибку модели.
• Байесовская оптимизация — метод выбора при бюджете в десятки-сотни оценок и размерности до ~20; в примере статьи 15 замеров BO эквивалентны 300 замерам случайного поиска.
• Шум лечится повторами, статистическим сравнением и обязательной перепроверкой финалистов.

Источники

• Jones, Schonlau, Welch. «Efficient Global Optimization of Expensive Black-Box Functions», J. Global Optimization 1998.
• Shahriari, Swersky, Wang, Adams, de Freitas. «Taking the Human Out of the Loop», Proc. IEEE 2016.
• Bergstra, Bengio. «Random Search for Hyper-Parameter Optimization», JMLR 2012 — почему случайный поиск сильнее сетки.
• Li, Jamieson, DeSalvo, Rostamizadeh, Talwalkar. «Hyperband», JMLR 2018.
• Jin. «Surrogate-assisted evolutionary computation», Swarm and Evolutionary Computation 2011.
• Golovin et al. «Google Vizier: A Service for Black-Box Optimization», KDD 2017.
• Van Aken, Pavlo, Gordon, Zhang. «Automatic Database Management System Tuning Through Large-scale Machine Learning», SIGMOD 2017.
• Akiba, Sano, Yanase, Ohta, Koyama. «Optuna», KDD 2019.

Что дальше

Мы научились экономить оценки. Остался вопрос, который висел с третьей статьи трека и который задают чаще всех остальных: какие ставить параметры? Размер популяции, вероятность мутации, расписание охлаждения, длину списка табу — и, шире, какой вообще алгоритм брать под конкретную задачу. Ответ неожиданный и приятный: это тоже задача поиска, и решается она теми же средствами, включая racing и суррогаты из этой статьи.

Настройка самого поиска: параметры, гиперэвристики и выбор алгоритма