Reservoir Sampling

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

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

Reservoir Sampling — это способ поддерживать случайную выборку постоянного размера за один проход по данным, количество которых заранее неизвестно. После каждого очередного сообщения память, называемая здесь резервуаром, содержит честную случайную выборку из всего, что пришло до этого момента. Простейшую версию, Algorithm R, описывает Vitter, Random Sampling with a Reservoir, §2, приписывая её Alan Waterman.

Рецепт в два шага

1. Первые четыре сообщения попадают в память без жребия.
2. Сообщение номер $t$ (пятое, шестое и каждое следующее) попадает в память с шансом $4/t$. Если попало, оно заменяет одно из четырёх сохранённых, выбранное случайно.

Пятое сообщение, таким образом, входит с шансом 4/5, сотое — с шансом 4/100. У новых сообщений шанс войти всё меньше, но старые уже много раз рисковали быть выброшенными, и эти два эффекта в точности уравновешиваются. Проверим это после пятого сообщения. Оно входит с шансом 4/5. Первое сообщение выпадает только тогда, когда пятое вошло (4/5) и попало как раз на его место (1/4), то есть с шансом 1/5. Оно остаётся с шансом 4/5: таким же, как у пятого. После $t$ сообщений каждое из них находится в памяти с шансом $4/t$.

Равный шанс — не гарантия

В эксперименте поток состоит из 20 сообщений. Восемнадцать касаются доставки, а два, девятое и пятнадцатое, — возвратов. Каждый запуск пропускает такой поток 2000 раз и считает, как часто данная позиция оставалась в памяти в конце. Случайный выбор настоящий, поэтому результаты каждый раз отличаются на долю процента.

При Reservoir Sampling каждый столбик составляет около 20%, то есть 4/20. При этом в большинстве прогонов ни один из двух возвратов не остаётся в памяти. Точное значение — 3060/4845, то есть около 63%: столько из всех четвёрок, выбранных из 20 сообщений, состоит исключительно из восемнадцати сообщений о доставке. Метод честен по отношению к отдельным сообщениям, но не следит за тем, чтобы у каждой категории был представитель.

Где это важно

В обучении с повторением Reservoir Sampling служит способом записи в буфер: не нужно знать ни длину потока, ни границы между задачами. Chaudhry et al., Continual Learning with Tiny Episodic Memories, §2, алгоритм 2 используют его именно так. В их экспериментах на задачах с изображениями он работал хорошо, за исключением очень маленькой памяти, когда из буфера исчезали более ранние классы; лучше тогда показывали себя стратегии, заботящиеся о равном представительстве классов (§4.4). Это результат для классификации изображений, а не для LLM.

Сам алгоритм не относится к машинному обучению. Работа Vitter 1985 года описывает случайный выбор записей с магнитной ленты неизвестной длины и предлагает более быстрые варианты, которые, вместо того чтобы бросать жребий на каждой записи, вычисляют, сколько записей пропустить. Сообщения клиентов и поток из 20 позиций — собственный пример.

• Experience Replay нуждается в буфере со старыми примерами; Reservoir Sampling — один из способов решать, что в него попадает.
• Continual Learning предполагает обучение на потоке данных при ограниченной памяти, то есть ситуацию, когда сохранить всё невозможно.
• Catastrophic Forgetting [Polski] может усилиться, когда из маленькой памяти выпадут все примеры старой категории.

Текст и иллюстрация подготовлены с помощью ИИ. Поток сообщений и демонстрация — собственный упрощённый учебный пример; иллюстрация — метафора, а не схема алгоритма.