Взвешенная выборка и выборка по хешу: когда элементы не равны

Если ты выберешь элемент с вероятностью, пропорциональной весу, за один проход, объяснишь ключ u^(1/w) и скажешь, чем выборка по хешу отличается от резервуарной, - листай до «Теперь сам».

Как думаешь, годится ли ключ «случайное число, умноженное на вес»

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

Ответь себе до чтения: даёт ли это нужные шансы? Для платежей в 100 и 200 рублей второй должен выигрывать в двух случаях из трёх. Он выигрывает в трёх из четырёх. Умножение завышает шансы тяжёлых; правильный ключ - не u · w, а u, возведённое в степень 1/w.

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

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

Выдавать тяжёлому элементу по билету на каждую единицу веса необязательно. Достаточно сразу выдать ему один номер, распределённый так же, как наибольший из его w билетов. Это и делает формула с корнем.

Механизм: два способа и один хеш

Способ первый: резервуар с весами. Для одного выбранного элемента правило резервуара обобщается напрямую. Ведём сумму весов W всех виденных элементов. Новый элемент с весом w сначала добавляет свой вес к W, а потом занимает место выбранного с вероятностью w / W.

P(элемент i выбран в конце) = wᵢ/Wᵢ · Wᵢ/Wᵢ₊₁ · Wᵢ₊₁/Wᵢ₊₂ · … · Wₙ₋₁/Wₙ = wᵢ / Wₙ

Wₘ здесь - сумма весов после m элементов. Уцелеть на шаге m - значит, что новый элемент не занял место: вероятность 1 − wₘ/Wₘ = Wₘ₋₁/Wₘ. Произведение сокращается так же, как у обычного резервуара; при всех весах, равных единице, получается он сам.

Способ второй: ключи. Веса - положительные числа. Каждому элементу независимо дают ключ u^(1/w), где u - случайное число от 0 до 1, и хранят k элементов с наибольшими ключами.

Почему степень 1/w. Возьмём w независимых случайных чисел от 0 до 1 и посмотрим на наибольшее из них. Оно не больше t, только если все w чисел не больше t: вероятность tʷ. Теперь посмотрим на u^(1/w). Оно не больше t, когда u ≤ tʷ: вероятность тоже tʷ. Распределения совпали: ключ u^(1/w) - это наибольший из w билетов, полученный одним броском. Элемент с весом w участвует в розыгрыше как w единичных элементов, и наибольший ключ достаётся ему с вероятностью w / W.

Для дробных весов рассуждение про билеты теряет буквальный смысл, а результат остаётся: вероятность «ключ не больше t» равна tʷ при любом положительном w, и из неё тем же счётом получается шанс w / W.

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

Объединение. Набор «k наибольших ключей» по всем данным - это k наибольших среди наборов по частям: ключ, не вошедший в лучшие у себя, не войдёт и в общие лучшие. Поэтому два сервера хранят свои k пар «ключ, элемент», а объединение - слить 2k пар и оставить k лучших. Счётчики виденных элементов, нужные обычному резервуару, здесь не требуются: вся нужная информация сидит в ключах.

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

Правило

Взвешенный выбор одного элемента за один проход: элемент с весом w заменяет выбранный с вероятностью w / W, где W - сумма весов, включая его. Взвешенная выборка k элементов: ключ u^(1/w), хранить k наибольших; объединение - k наибольших из слитых наборов. Выборка по хешу: оставлять элемент, если хеш его идентификатора меньше порога; она выбирает долю идентификаторов, а не долю событий, и согласована между машинами.

Разбор: веса 1, 2, 3 и 4

Восемь тысяч розыгрышей среди четырёх элементов. Доли должны быть 0,1, 0,2, 0,3 и 0,4.

import random

def vzveshennyj(vesa):
    luchshij = -1
    luchshij_klyuch = -1
    for i in range(len(vesa)):
        klyuch = random.random() ** (1 / vesa[i])
        if klyuch > luchshij_klyuch:
            luchshij_klyuch = klyuch
            luchshij = i
    return luchshij

random.seed(55)
vesa = [1, 2, 3, 4]
skolko = [0, 0, 0, 0]
opytov = 8000
for opyt in range(opytov):
    i = vzveshennyj(vesa)
    skolko[i] = skolko[i] + 1
doli = []
for s in skolko:
    doli.append(round(s / opytov, 3))
print(skolko, doli)

[772, 1618, 2370, 3240] [0.097, 0.202, 0.296, 0.405]

Доли 0,097, 0,202, 0,296 и 0,405 - в пределах полупроцента от заданных. Функция проходит по элементам один раз и помнит одного лучшего: сумму весов знать не нужно ни заранее, ни по ходу.

Теперь про ключ u · w из вопроса в начале. Для весов 1 и 2 второй элемент проигрывает, когда u₁ > 2 · u₂. При данном u₁ это случается с вероятностью u₁ / 2, а в среднем по u₁ - с вероятностью 1/4. Первый элемент выигрывает в четверти розыгрышей вместо трети. Ошибка небольшая на вид и систематическая: лёгкие элементы недополучают всегда.

Разбор: два сервера и то, кого на самом деле выбирает выборка

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

import random

def luchshie(pary, k):
    return sorted(pary)[len(pary) - k:]

random.seed(58)
k = 3
pary = []
for nomer in range(20):
    ves = random.randint(1, 9)
    klyuch = round(random.random() ** (1 / ves), 4)
    pary.append([klyuch, nomer])

pervyj_server = luchshie(pary[:12], k)
vtoroj_server = luchshie(pary[12:], k)
print(luchshie(pary, k))
print(luchshie(pervyj_server + vtoroj_server, k))

[[0.954, 12], [0.9576, 3], [0.9933, 4]]
[[0.954, 12], [0.9576, 3], [0.9933, 4]]

Строки совпали. В выборку вошли элементы 3 и 4 с первого сервера и элемент 12 со второго; координатор получил шесть пар вместо двадцати и принял то же решение, что принял бы, видя всё.

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

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

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

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

Ключ u · w. Перекос из разбора: тяжёлые выбираются чаще, чем должны.

Маленькое u в большой степени. При весе в одну миллионную ключ u^(1 000 000) превращается в ноль из-за пределов точности, и все лёгкие элементы становятся неразличимы. На практике сравнивают ln(u) / w: порядок тот же, а потери точности нет.

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

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

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

Деление пользователей на группы в эксперименте. Группа определяется хешем идентификатора: пользователь видит один и тот же вариант на всех устройствах и после перезапуска серверов, а состав групп никто не хранит.

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

Теперь сам

1. Два элемента с весами 2 и 6. С какой вероятностью взвешенный выбор вернёт первый?
2. По первому способу пришли элементы с весами 5, 3 и 2. С какой вероятностью третий заменит выбранного?
3. Элемент с весом 4 получил u = 0,5, элемент с весом 1 получил u = 0,8. Чей ключ больше? 0,5^(1/4) ≈ 0,84.
4. Событие оставляют, если хеш идентификатора пользователя при делении на 1000 даёт остаток меньше 5. Какая доля пользователей попадёт в выборку и какая доля событий пользователя, сделавшего 3000 запросов?
5. Три сервера прислали по пять лучших пар «ключ, элемент». Сколько пар получит координатор и как найдёт выборку из пяти элементов по всем данным?