Онлайн-алгоритм с прогнозом: доверять, но с гарантией

Если ты знаешь, что такое согласованность и устойчивость, как устроена аренда лыж с прогнозом и почему между ними неизбежен размен, листай до «Теперь сам».

Как думаешь, стоит ли слушать прогноз

Аренда лыж с подсказкой: модель, обученная на прошлых сезонах, говорит «в этом году - 30 дней». Покупка стоит 10 дней проката. Если прогноз верен, нужно купить в первый же день и заплатить 10 - отношение 1. Правило без подсказки заплатило бы 19.

Ответь себе до чтения: что, если поверить прогнозу целиком, а он ошибся и сезон - один день? Заплатишь 10 вместо 1: отношение 10, хуже любого правила без подсказки. Полное доверие делает алгоритм беспомощным перед плохой моделью, полное недоверие - выбрасывает полезную информацию. Нужна ручка посередине - и обещание на оба случая.

На что это похоже

Навигатор с прогнозом пробок. Хороший водитель едет по совету навигатора, но не сворачивает на просёлок в пятьдесят километров ради выигрыша в две минуты: если прогноз ошибся, он не должен потерять полдня. Степень доверия - это сколько риска ты готов принять ради выигрыша при верном прогнозе.

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

Механизм: две гарантии и ручка между ними

Согласованность - худшее отношение к оптимуму при точном прогнозе. Устойчивость - худшее отношение при любом прогнозе. Классический онлайн-алгоритм - частный случай: у него обе равны его конкурентному отношению.

Правило для аренды лыж с параметром λ ∈ (0, 1]:

прогноз «сезон >= B дней»:  купить в день ⌈λ · B⌉     (раньше обычного)
прогноз «сезон < B дней»:   купить в день ⌈B / λ⌉     (позже обычного)

Почему 1 + λ при верном прогнозе. Сезон и правда длинный: заплачено не больше λB + B при оптимуме B. Сезон и правда короткий (меньше B): покупка в день B/λ ≥ B не наступит, заплачено ровно столько, сколько дней, - как оптимум.

Почему 1 + 1/λ при любом прогнозе. Худшее, что может сделать неверный прогноз: «длинный» при сезоне ровно λB дней - заплачено λB − 1 + B против λB, отношение около 1 + 1/λ; или «короткий» при сезоне B/λ - заплачено B/λ − 1 + B против B, отношение около 1 + 1/λ.

Размен неизбежен. Сделать λ маленьким - почти идеально при верном прогнозе (1 + λ → 1), но катастрофично при неверном (1 + 1/λ → ∞). λ = 1 - игнорировать прогноз: обе гарантии 2. Доказано (Вэй, Чжан, 2020), что лучшего размена у детерминированных правил нет.

Правило

Онлайн-алгоритм с прогнозом описывают двумя числами: согласованность - отношение при верном прогнозе, устойчивость - при любом. Аренда лыж с доверием λ: при прогнозе «длинный» купить в день λB, иначе в день B/λ; согласованность 1 + λ, устойчивость 1 + 1/λ. Между ними размен, и параметр доверия - это выбор точки на нём.

Разбор: три уровня доверия

den_pokupki - правило с прогнозом. Для каждого λ считаются два худших отношения: когда прогноз совпал с длиной сезона и когда прогноз любой. B = 10, сезоны от 1 до 59 дней.

import math

def den_pokupki(prognoz, B, lam):
    if prognoz >= B:
        return math.ceil(lam * B)
    return math.ceil(B / lam)

def zatraty(kupit_v_den, dnej, B):
    if dnej < kupit_v_den:
        return dnej
    return (kupit_v_den - 1) + B

B = 10
for lam in [1, 0.5, 0.2]:
    vernyj = 0
    lyuboj = 0
    for dnej in range(1, 6 * B):
        opt = min(dnej, B)
        r = zatraty(den_pokupki(dnej, B, lam), dnej, B) / opt
        vernyj = max(vernyj, r)
        for prognoz in range(1, 6 * B):
            k = den_pokupki(prognoz, B, lam)
            lyuboj = max(lyuboj, zatraty(k, dnej, B) / opt)
    print(lam, round(vernyj, 2), round(lyuboj, 2),
          round(1 + lam, 2), round(1 + 1 / lam, 2))

1 1.9 1.9 2 2.0
0.5 1.4 2.9 1.5 3.0
0.2 1.1 5.9 1.2 6.0

Столбцы: λ, худшее отношение при верном прогнозе, при любом, формулы 1 + λ и 1 + 1/λ. λ = 1: прогноз проигнорирован, обе цифры 1,9 - классическое правило. λ = 0,5: при верном прогнозе 1,4, при любом не хуже 2,9. λ = 0,2: почти оптимум при верном (1,1), но 5,9 при плохом. На дискретных днях цифры чуть лучше формул: округление дня покупки работает в пользу правила.

Выбор λ - деловое решение, а не математическое. Модель надёжная и ошибки дороги умеренно - λ = 0,2. Модель новая, а переплата впятеро недопустима - λ = 0,5 или выше.

Разбор: насколько плох неточный прогноз

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

import math

def den_pokupki(prognoz, B, lam):
    if prognoz >= B:
        return math.ceil(lam * B)
    return math.ceil(B / lam)

def zatraty(kupit_v_den, dnej, B):
    if dnej < kupit_v_den:
        return dnej
    return (kupit_v_den - 1) + B

B = 10
lam = 0.5
for oshibka in [0, 2, 5, 10, 30]:
    hud = 0
    for dnej in range(1, 6 * B):
        for prognoz in range(max(1, dnej - oshibka), dnej + oshibka + 1):
            k = den_pokupki(prognoz, B, lam)
            hud = max(hud, zatraty(k, dnej, B) / min(dnej, B))
    print(oshibka, round(hud, 2))

0 1.4
2 1.75
5 2.8
10 2.8
30 2.9

Точный прогноз - 1,4. Ошибка в два дня - 1,75. Пять дней - 2,8, и дальше почти не растёт: устойчивость держит потолок 2,9 при любой ошибке. Деградация резкая там, где ошибка перебрасывает прогноз через порог B: сезон в 8 дней, предсказанный как 10, заставляет купить на пятый день - 14 против 8, те самые 1,75. Именно поэтому современные варианты правила смотрят не только на «длинный или короткий», но и на величину прогноза и на уверенность модели.

Что ломается без этого

Слепо доверяют модели. Покупка в первый день по прогнозу «30 дней» при реальном одном дне - отношение 10. Без устойчивости алгоритм с прогнозом хуже классического.

Игнорируют модель. Классическое правило платит 1,9 там, где верный прогноз позволил бы 1,1.

Не задают λ явно. Доверие зашито в код неявно («если модель сказала - делаем»), и никто не знает, какова потеря при её ошибке. Явный параметр - это явно названный риск.

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

Зачем это в работе

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

Теперь сам

1. λ = 0,25. Каковы согласованность и устойчивость правила аренды лыж?
2. B = 20, λ = 0,5, прогноз - 40 дней. В какой день правило купит лыжи? А при прогнозе 5 дней?
3. Почему правило не может быть одновременно 1-согласованным и 2-устойчивым?