Резервуарное сэмплирование — это методика выбора справедливого случайного образца, когда неизвестен размер множества, из которого выполняется выборка. К концу этой статьи вы будете знать:
Когда может потребоваться резервуарное сэмплирование.
Математика его работы на основании лишь базовых операций: вычитания, умножения, умножения и деления. Никаких сложных математических формул, обещаю.
Простой способ реализации резервуарного сэмплирования на случай, если вам оно понадобится.
Сэмплирование, когда размер известен
Перед вами десять игральных карт. Я прошу выбрать случайным образом три из них. Как вы это сделаете?
Первым делом можно вспомнить способ из детства — замешать их всех в колоду. Затем разложить на столе и взять первые три. Это показано в примере ниже. [Прим. пер.: в оригинале статьи все примеры интерактивны.]
При каждом нажатии на «Shuffle» показанный ниже график показывает, какими были первые три карты.
Поначалу вы будете замечать, что некоторые карты выбираются чаще других, но чем дольше вы будете это делать, тем более ровным будет становиться график. Все карты имеют одинаковую вероятность выбора. Поэтому такое сэмплирование «справедливое».
Можно нажимать на «Shuffle 100 times» («Перемешать 100 раз»), пока график не выровняется. Если захотите начать заново, то можно нажать на «Reset».
Такой способ хорош, когда у вас десять карт, но что, если их миллион? Перемешивать их будет непросто. Вместо этого можно при помощи генератора случайных чисел выбрать три индекса. Это будут три наши выбранные карты.
Нам больше не приходится перетасовывать все карты, а если понажимать на кнопку «Select» достаточное количество раз, то мы увидим, что этот способ столь же справедлив, как и способ с перемешиванием.
Здесь я использовал довольно натянутую аналогию. Нам сложно было бы посчитать колоду, допустим, до индекса 436234. Но когда это массив в памяти, то компьютер без проблем найдёт элемент по его индексу.
А теперь я задам хитрый вопрос: что, если я бы показывал вам по одной карте за раз, а вам нужно было бы выбрать одну случайным образом?
Сколько карт вы мне покажете?
В том-то и хитрость: вы не знаете.
Могу ли я придерживать все карты, которые вы мне даёте, а затем выбрать одну, когда вы остановитесь?
Нет, вы можете держать только одну карту за раз. Вы можете заменять её на самую новую каждый раз, когда я показываю вам карту, но хранить вы можете только одну и не можете возвращаться к карте, которую уже видели.
Это невозможно! Да и зачем вообще мне нужно было бы такое делать?
Можете мне не верить, но это реальная задача, имеющая реальное изящное решение.
Например, мы создаём сервис сбора логов. Этот сервис получает сообщения логов от других сервисов и сохраняет их, чтобы можно было с лёгкостью выполнять поиск по ним.
При создании подобного сервиса следует задуматься в том числе и о том, как поступать, если другой сервис начинает отправлять слишком много логов. Допустим, мы выпустили релиз с ошибкой или одно из ваших видео стало виральным. Какой бы ни была причина, это потенциально может перегрузить ваш сервис сбора логов.
Давайте симулируем это. Ниже показан поток логов, в котором периодически возникают всплески. Горизонтальная линия обозначает пороговое значение количества логов в секунду, с которым может справиться сервис; в этом примере — пять логов в секунду.
Как видите, время от времени количество логов превышает пороговое значение. Один из способов решения этой проблемы заключается в «сэмплировании», то есть в передаче сервису сбора логов только их части. Давайте будем отправлять 10% логов.
Ниже показана та же симуляция, но на этот раз логи, которые не передаются в сервис сбора логов, выделены серым. На графике есть две линии: чёрная отслеживает количество отправленных в сервис логов, серая — общее количество логов.
Частота отправляемых логов никогда не превышает порогового значения, поэтому мы не перегружаем сервис. Однако в периоды пониженной нагрузки мы отбрасываем 90% логов, хотя это и необязательно!
На самом деле нам нужно отправлять не более пяти логов в секунду. Это будет означать, что в периоды низкой нагрузки мы будем получать все логи, а во время всплесков будем отклонять логи, чтобы защитить сервис.
Проще всего было бы отправлять первые пять логов, которые мы встречаем в каждую секунду, но это будет несправедливо. Мы не даём всем логам одинакового шанса быть выбранными.
Сэмплирование, когда размер неизвестен
Итак, мы хотим брать справедливую выборку логов, получаемых каждую секунду. Проблема заключается в том, что мы не знаем, сколько их будет. Именно эту проблему и решает резервуарное сэмплирование.
1 секунда — это не так уж долго, разве нельзя просто хранить все полученные сообщения, а затем выбирать уже из них?
Конечно, можно, но зачем мириться с этой неопределённостью? Нам придётся хранить в памяти неизвестное количество логов. Достаточно сильный всплеск может вызвать проблемы. Резервуарное сэмплирование решает эту проблему, потребляя при этом не больше памяти, чем вы ему выделите.
Давайте вернёмся к нашему хитрому вопросу о показе только одной карты за раз. Вот его краткие правила:
Я по одной тяну карты из колоды.
Каждый раз, когда я показываю карту, вы должны или забрать её, или отказаться от неё.
Если вы уже держите карту, то вы должны отказаться от неё прежде, чем замените её новой.
Я в любой момент могу перестать тянуть карты, и та карта, которую вы держите, будет считаться выбранной вами.
Как играть в эту игру так, чтобы у любой карты был равный шанс на выбор, когда я решу остановиться?
Может, бросать для каждой новой карты монетку? Если выпал орёл, то мы оставляем карту, которая у нас в руках. Если решка, то берём вместо неё новую карту.
Вы на верном пути. Давайте посмотрим, как эта идея с бросками монеты поведёт себя на практике. Ниже показана колода карт. При нажатии на «Deal» из колоды берётся карта и с вероятностью 50% она идёт в сброс, а в 50% случаев она остаётся в центре, а предыдущая удерживаемая карта сбрасывается.
Проблема здесь в том, что хотя количество оставленных и сброшенных карт приблизительно одинаково, когда я остановлюсь, последующие карты имеют гораздо большую вероятность быть оставленными, чем предыдущие. После вытягивания десятой карты первой вытянутой карте нужно выиграть в десяти бросках монеты. Последней карте достаточно лишь одной победы.
Передвижение ползунка соответствует вытягиванию большего количества карт. Посмотрите, как меняются вероятности. Каждый столбец обозначает карту в колоде, а высота столбца обозначает вероятность того, что вы будете держать эту карту, когда я остановлюсь. Под ползунком показаны сравнение вероятностей того, что мы сохраним первую карту и того, что сохранится последняя вытянутая карта.
Карты, пережившие 15 вытягиваний, имеют шанс остаться после остановки, равный всего 0,01%.
Но вы сказали, что я на верном пути! Как это может быть верным путём, если у меня больше шансов выиграть в лотерею, чем оставить в руках карту, которую я получил 24 вытягиваний назад?
Потому что, верьте или нет, для превращения этой идеи в справедливую достаточно внести одно небольшое изменение.
Вместо того, чтобы бросать монетку для принятия решения, мы присваиваем каждой карте вероятность оставления 1/n, где n — это количество уже встреченных нами карт.
И это всё? В чём же тут справедливость?
Да! Чтобы сэмплирование было справедливым, каждая карта должна иметь равный шанс быть выбранной. То есть в случае второй карты мы хотим, чтобы обе карты имели вероятность 1/2. Для третьей карты мы хотим, чтобы все три карты имели вероятность 1/3. Для четвёртой — вероятность 1/4 для всех четырёх карт и так далее. Поэтому если использовать 1/n для каждой новой карты, то можно хотя бы сказать, что новая карта имеет справедливый шанс.
Давайте посмотрим на вероятности при вытягивании карт в этой новой методике.
Я понимаю, что каждая новая карта получает справедливый шанс быть выбранной, но как это делает справедливыми старые карты?
Пока мы рассматривали только вероятность выбора новой карты, но нам нужно учесть и вероятность того, что карта останется в руке. Давайте пройдёмся по числам.
Карта 1
С первой картой всё просто: в руках у нас ничего нет, так что мы всегда решаем выбрать первую карту. Вероятность того, что мы возьмём эту карту в руку, равна 1/1, или 100%.
Карта 2
Теперь у нас уже есть реальный выбор. Мы можем продолжить держать карту на руках или заменить её на новую. Выше говорилось, что мы сделаем это с вероятностью 1/n, где n — количество встреченных пока карт. Так что вероятность замены первой карты равна 1/2, или 50%, а вероятность оставления на руках первой карты равна вероятности её выбора в прошлый раз, умноженной на вероятность того, что её не заменят, то есть 100% * 1/2, что тоже равно 50%.
Карта 3
Карта, которую мы держим, имеет вероятность 50% остаться на руках. Это истинно вне зависимости от того, что происходило до этого момента. Держим ли мы карту 1 или карту 2, она всё равно равна 50%.
Новая карта имеет вероятность 1/3 быть выбранной, поэтому карта в руках имеет вероятность 1/3 быть заменённой. Это значит, что карта в руках имеет вероятность 2/3 остаться в руках. То есть её шансы «пережить» этот раунд равны 50% * 2/3.
Карта N
Этот паттерн повторяется для любого количества вытягиваемых карт. Мы можем выразить оба варианта в виде формул. Перемещение ползунка заменяет n реальными числами и позволяет увидеть, что две формулы всегда равны.
Если 1/n — это вероятность выбора новой карты, то 1/(n-1) — вероятность выбора новой карты из предыдущего вытягивания. Вероятность не выбрать новую карту — это дополнение 1/n, то есть 1-(1/n).
Ниже снова показаны карты, только теперь мы используем вместо броска монеты 1/n. Понаблюдаем за вытягиванием карт до конца колоды. Кажется ли оно вам справедливым?
Есть высокая вероятность того, что во второй половине колоды выбранная карта ни разу не будет заменена. Это кажется нечестным (мне, по крайней мере), но, как мы видели выше, числа говорят, что это абсолютно справедливо.
Выбор нескольких карт
Теперь, когда мы знаем, как выбрать одну карту, можно расширить эту систему для выбора нескольких карт. Для этого необходимо внести два изменения:
Теперь новые карты будут иметь вероятность выбора не
1/n, аk/n, гдеk— это количество карт, которое мы хотим выбрать.Когда мы выбираем заменить карту с руки, то выбираем одну из
kслучайным образом.
То есть теперь формула выбора карт имеет вид k/(n-1), потому что мы держим k карт. Тогда вероятность того, что одна из карт на руке будет заменена, равна 1-(1/n).
Давайте посмотрим, как это будет работать с реальными числами.
Справедливость по-прежнему сохраняется и будет сохраняться для любой пары k и n. Причина этого в том, что все карты на руке имеют одинаковую вероятность быть заменёнными, из-за чего они имеют равную вероятность остаться на руке при каждом вытягивании.
Это удобно реализовать при помощи массива размера k. Для каждой новой карты мы будем генерировать случайное число от 0 до n. Если случайное число меньше k, то мы заменяем карту по этому индексу новой картой. В противном случае новая карта отправляется в сброс.
Вот так и работает резервуарное сэмплирование!
Применяем эту систему к сбору логов
Давайте возьмём всё то, что у же знаем о резервуарном сэмплировании, и применим это в нашем сервисе сбора логов. Присвоим k=5, чтобы одновременно мы «держали» максимум пять сообщений логов, и каждую секунду отправляли выбранные логи в сервис. Сделав это, мы очищаем массив из пяти элементов и начинаем заново.
Это создаёт «бугристый» паттерн графика, подчёркивающий компромисс, на который мы идём при использовании резервуарного сэмплирования. Теперь это не поток логов в реальном времени, а интервально отправляемые блоки логов. Однако количество отправляемых логов никогда не превышает пороговое значение, и в спокойные периоды две линии почти полностью совпадают.
В спокойные периоды не теряется ни один лог, а во время всплесков в секунду бывает не больше логов, чем пороговое значение. Мы взяли лучшее от двух систем. Кроме того, хранится не более k=5 логов, так что объём занимаемой памяти предсказуем.
Дополнительное чтение
В процессе чтения поста вы могли подумать, что некоторые логи могут быть ценнее других. Например, вам, скорее всего, захочется сохранять все логи ошибок.
Для подобного сценария существует взвешенный вариант резервуарного сэмплирования. Мне не удалось найти более простого объяснения, поэтому ссылка ведёт на статью Википедии, которая мне показалась довольно сложной. Но самое главное, что этот вариант существует, и при необходимости его можно использовать.
Заключение
Резервуарное сэмплирование — один из любимых моих алгоритмов, я уже несколько лет мечтал написать статью о нём. Он изящным и эффективным образом позволяет решить проблему, которая поначалу кажется нерешаемой.
