Off-policy оценка

Есть лог показов, собранный старой моделью (logging policy \(\pi_0\)), и новая модель \(\pi\). Нужно оценить её метрику, не выкатывая. Эта страница — вывод того, что считают ranklens.offpolicy.ips и ranklens.offpolicy.snips, и границы, где им можно верить.

Модель: осмотр по позиции (PBM)

Документ \(d\) на позиции \(r\) пользователь осматривает с вероятностью \(p_r\), не зависящей от документа, и, осмотрев, реагирует с вероятностью \(a(d)\) — привлекательность. Наблюдаем только реакцию:

\[ P(c = 1 \mid d \text{ на позиции } r) = p_r \cdot a(d). \]

С наградой вместо клика (шкала «клик < корзина < покупка») всё так же: \(\mathbb E[c \mid r, d] = p_r \cdot a(d)\), где \(a(d)\) — ожидаемая награда осмотренного документа. Наивное среднее по кликам меряет \(p_r \cdot a(d)\) — то есть старую модель вместе с её позициями, а не новую.

Что оцениваем

Для новой политики \(\pi\) и дисконта \(\lambda\) (какую метрику считаем):

\[ V(\pi) = \mathbb E_q \sum_{d} \lambda\bigl(\operatorname{rank}_\pi(d)\bigr)\, a(d), \qquad \lambda_{\text{DCG@}k}(r) = \frac{\mathbb 1[r \le k]}{\log_2(r+1)}. \]

Это ожидаемые дисконтированные клики, если бы каждая позиция осматривалась, — DCG@k с привлекательностью в роли gain. Дисконт берётся от позиции у новой политики: индикатор «\(\pi\) ставит документ в top-k» — частный случай \(\lambda(r) = \mathbb 1[r \le k]\), он оценивает число кликов в top-k, а не DCG.

IPS

Каждая реакция делится на вероятность, что её позицию осмотрели:

\[ \hat V_{\text{IPS}}(\pi) = \frac1n \sum_{i=1}^{n} \sum_{d \in S_i} \frac{c_i(d)\; \lambda\bigl(\operatorname{rank}_\pi(d)\bigr)}{p_{r_i(d)}}, \]

где \(S_i\) — документы, показанные в \(i\)-м показе, \(r_i(d)\) — их позиция у старой модели.

Несмещённость. \(\mathbb E[c_i(d) / p_{r_i(d)}] = p_r\, a(d) / p_r = a(d)\), поэтому

\[ \mathbb E\,\hat V_{\text{IPS}} = \mathbb E_q \sum_{d \in S(q)} \lambda\bigl(\operatorname{rank}_\pi(d)\bigr)\, a(d) = V(\pi) - \underbrace{\mathbb E_q \sum_{d \notin S(q)} \lambda\bigl(\operatorname{rank}_\pi(d)\bigr)\, a(d)}_{\text{смещение}}. \]

Два условия: \(p_r > 0\) для всех позиций лога (поэтому Propensity запрещает ноль) и новая политика ставит в метрику только показанные документы. Документ, который старая модель ни разу не показала, оценщик не видит, и никакая коррекция весов этого не исправит — отсюда смещение вниз, когда новая модель поднимает в top-k «новые» документы.

Дисперсия растёт как \(1/p\): клик на позиции 20 при \(p_r = 1/r\) получает вес 20.

SNIPS: отношение

Классический SNIPS (Swaminathan & Joachims, 2015) делит на сумму весов \(\sum w_i\): там \(w = \pi(a)/\pi_0(a)\) и \(\mathbb E[w] = 1\), так что знаменатель — контрольная величина с известным средним. У нас веса \(1/p\) — поправка на осмотр, а не отношение политик, и \(\mathbb E[\sum_d c/p] = \sum_{d \in S} a(d)\) неизвестно. Прямого аналога нет, поэтому SNIPS здесь — отношение с другой целью оценки:

\[ \hat R(\pi) = \frac{\sum_i \sum_{d \in S_i} c_i(d)\, \lambda(\operatorname{rank}_\pi(d)) / p_{r_i(d)}} {\sum_i \sum_{d \in S_i} c_i(d) / p_{r_i(d)}} \;\longrightarrow\; R(\pi) = \frac{\mathbb E_q \sum_{d \in S(q)} \lambda(\operatorname{rank}_\pi(d))\, a(d)}{\mathbb E_q \sum_{d \in S(q)} a(d)}. \]

\(R\) — какую долю привлекательности показанного \(\pi\) собирает с учётом дисконта. Числитель и знаменатель — средние по показам, отношение сходится по закону больших чисел; смещение порядка \(1/n\).

Сравнение политик не меняется. На одном логе знаменатель общий:

\[ R(\pi_1) - R(\pi_2) = \frac{V(\pi_1) - V(\pi_2)}{\mathbb E_q \sum_{d \in S(q)} a(d)}, \]

знак и порядок политик — те же, что у IPS; величина в других единицах.

Дисперсия меньше: числитель и знаменатель скоррелированы, общий шум показа («в этом показе кликали много») сокращается.

Клиппинг весов

\(w = \min(1/p_r, \tau)\) ограничивает вклад редких глубоких позиций. Цена — смещение: \(\mathbb E[c \cdot \min(1/p, \tau)] = a \cdot \min(1, p\tau) \le a\), то есть IPS с клиппингом занижает оценку. У отношения урезаются и числитель, и знаменатель, поэтому направление смещения заранее не определено. Число обрезанных весов сообщается вместе с оценкой.

Когда весам нельзя верить: ESS

Оценка — среднее наград, умноженных на веса \(w = 1/p\). Если несколько наград с глубоких позиций несут огромные веса, они и решают результат, а интервал занижает неопределённость: нормальное приближение не видит, что «данных» на самом деле мало. Эффективный размер выборки

\[ \mathrm{ESS} = \frac{\bigl(\sum_j w_j\bigr)^2}{\sum_j w_j^2} \]

по весам награждённых документов равен их числу \(m\), когда веса одинаковы, и падает до единиц, когда доминирует несколько весов. При \(\mathrm{ESS} < 0.1\,m\) оценщики предупреждают (DegenerateWeightsWarning); weight_diagnostics показывает распределение весов — максимум, 99-й перцентиль и долю массы в верхнем 1%.

На симуляторе (50 позиций, 3000 показов): при \(\eta = 1\) ESS — 35% от числа весов, максимальный вес 49; при \(\eta = 2\) — 5%, максимальный вес 729 и 35% всей массы весов у верхнего 1%: предупреждение срабатывает, клиппинг возвращает ESS выше порога.

Проверка на симуляторе

ClickWorld: 100 запросов по 10 документов, старая модель — релевантность плюс шум σ = 1.5, новая — σ = 0.3; показываются все 10 позиций, \(p_r = 1/r\), метрика DCG@5. 200 повторов по 3000 показов:

оценщик	среднее	истина	относительный разброс
IPS	0.9277	V = 0.9284	2.4%
отношение (SNIPS)	0.7353	R = 0.7356	1.1%
IPS, τ = 5	0.9002	V = 0.9284	2.3%
отношение, τ = 5	0.7469	R = 0.7356	1.0%
IPS, τ = 2	0.7454	V = 0.9284	2.0%
отношение, τ = 2	0.7803	R = 0.7356	0.7%

IPS несмещён, отношение сходится к своей цели с вдвое меньшим разбросом; клиппинг снижает разброс ценой смещения — у IPS вниз, у отношения здесь вверх.

То же через API — один лог, истина считается симулятором:

from ranklens.offpolicy import ClickWorld, Propensity, dcg_discount, ips, snips

world = ClickWorld.random(n_queries=100, docs_per_query=10, seed=1)
logging, new = world.policy(noise=1.5, seed=2), world.policy(noise=0.3, seed=3)
pbm, dcg5 = Propensity.power(depth=10, eta=1.0), dcg_discount(5)
log = world.simulate(logging, pbm, n_impressions=5_000, seed=4)

print(f"истина V(new) = {world.value(new, dcg5):.4f}")
for estimate in (ips(log, new, pbm, dcg5), ips(log, new, pbm, dcg5, clip=2.0)):
    print(
        f"{estimate.estimator:5} clip={estimate.clip}: {estimate.value:.4f} "
        f"[{estimate.ci_low:.4f}, {estimate.ci_high:.4f}], обрезано весов: {estimate.n_clipped}"
    )
print(f"snips: {snips(log, new, pbm, dcg5).value:.4f} (доля, а не клики)")

истина V(new) = 0.9284
ips   clip=None: 0.9377 [0.9025, 0.9729], обрезано весов: 0
ips   clip=2.0: 0.7543 [0.7308, 0.7778], обрезано весов: 688
snips: 0.7329 (доля, а не клики)

Интервал с клиппингом уже, но истину не содержит: он описывает разброс вокруг смещённого значения, а не ошибку относительно истины. Узкий интервал — не аргумент в пользу клиппинга, пока смещение не оценено.

Интервалы

Показы независимы, \(n\) в логах велико — нормальное приближение. Для IPS — среднее \(x_i\) (вклад показа) и \(\hat\sigma/\sqrt n\). Для отношения — дельта-метод: с \(u_i\) (числитель показа) и \(v_i\) (знаменатель)

\[ \widehat{\operatorname{Var}}(\hat R) \approx \frac{1}{n\,\bar v^{2}}\; \widehat{\operatorname{Var}}\bigl(u_i - \hat R\, v_i\bigr). \]

Оба считаются одним проходом по логу по накопленным суммам — память не растёт с размером лога.

Покрытие 95%-х интервалов на симуляторе (1000 логов на каждый размер):

показов в логе	IPS	SNIPS
1000	0.946	0.944
2000	0.952	0.957

На совсем малых логах интервал отношения бывает чуть уже нужного: смещение отношения порядка \(1/n\), а дельта-метод — первое приближение.

Ограничения

• Propensity фиксированы; если \(p_r\) заданы неверно, IPS смещён пропорционально ошибке.
• Документы вне лога не оцениваются (см. смещение выше).
• PBM не учитывает, что осмотр зависит от выше стоящих документов (каскадная модель).