Оригинал изInnovating Faster on Personalization Algorithms at Netflix Using Interleaving. Если вы обнаружите какие-либо нарушения, пожалуйста, свяжитесь со мной.
Опыт Netflix основан на серии алгоритмов ранжирования, каждый из которых оптимизирован для разных целей. Например, строка Top Picks на главной странице дает рекомендации на основе персонализированного рейтинга видео, а строка Trending Now также содержит последние тенденции. Эти алгоритмы, наряду со многими другими, используются для создания персонализированных домашних страниц для более чем 100 миллионов пользователей.
В Netflix мы стремимся постоянно улучшать нашу систему рекомендаций. Процесс разработки начинается с создания нового алгоритма ранжирования и оценки его эффективности в автономном режиме. Затем мы используем A/B-тестирование для онлайн-измерения основных метрик оценки, которые тесно связаны с нашей бизнес-целью максимального удовлетворения пользователей. К таким показателям относятся удержание ежемесячной подписки и время просмотра пользователями. Поскольку алгоритмы ранжирования и весь продукт Netflix оптимизированы, для значительного увеличения этих показателей требуются все большие и большие размеры выборки и более длительные эксперименты.
Чтобы ускорить темпы инноваций алгоритмов, мы разрабатываем двухэтапный процесс онлайн-экспериментирования. Первый этап — это быстрый шаг обрезки, когда мы определяем наиболее перспективные алгоритмы ранжирования из большого набора первоначальных идей. Второй этап — традиционное A/B-тестирование сокращенного набора алгоритмов для измерения их влияния на долгосрочное поведение пользователей. В этом сообщении блога мы сосредоточимся на нашем подходе к первой фазе: методе чередования, который позволяет нам более точно измерять предпочтения пользователей.
Faster algorithm innovation with interleaving
Быстро тестируя большое количество идей, мы можем увеличить скорость обучения и скорость инноваций алгоритмов. Мы расширяем количество новых алгоритмов, которые можно тестировать, вводя начальную фазу онлайн-экспериментов. Этот метод удовлетворяет следующим двум свойствам:
- Он очень чувствителен к качеству алгоритма ранжирования, т. е. надежно определяет лучший алгоритм, используя значительно меньший размер выборки по сравнению с традиционным A/B-тестированием.
- Он предсказывает успех второго этапа: метрики, измеренные на первом этапе, согласуются с нашими основными метриками оценки A/B.
Мы используем методы чередования (см.Chapelle et al.) достигает вышеуказанных целей, что значительно ускоряет наш экспериментальный процесс (см. рис. 2). Первый этап был завершен за несколько дней, и у нас остался небольшой выбор наиболее перспективных алгоритмов ранжирования. На втором этапе тестируются только эти выбранные алгоритмы, что позволяет нам назначать меньше участников для всего эксперимента и сокращать общую продолжительность эксперимента по сравнению с традиционным A/B-тестированием.
Using a repeated measures design to determine preferences
Чтобы построить интуитивное представление об увеличении чувствительности, которое обеспечивает чередование, давайте рассмотрим эксперимент, чтобы определить, что предпочитается в популяции: кока-кола или пепси. Если бы мы использовали традиционное A/B-тестирование, мы могли бы случайным образом разделить население на две группы и провести слепой обзор. Одна группа подавала только Coca-Cola, а вторая — только Pepsi (на обоих напитках не было идентифицируемых этикеток). В конце эксперимента мы можем определить, есть ли предпочтение Coca-Cola или Pepsi, измерив разницу в потреблении напитков между двумя группами и степень неопределенности в этом измерении, что может сказать нам, существует ли статистическая зависимость. значимое различие.
Хотя этот подход работает, все еще могут быть возможности для улучшения. Во-первых, существует основной источник неопределенности измерения: большие различия в привычках потребления газированных напитков среди населения, от тех, кто почти не употребляет газированные напитки, до тех, кто потребляет много. Во-вторых, потребители тяжелых газированных напитков могут составлять лишь небольшую часть населения, но их потребление может составлять большой процент от общего потребления газированных напитков. Таким образом, даже небольшой дисбаланс в количестве потребителей крепких газированных напитков между двумя группами может оказать непропорциональное влияние на наши выводы. При проведении онлайн-экспериментов потребительские интернет-продукты часто сталкиваются с аналогичными проблемами, связанными с их наиболее активными пользователями, будь то измерение изменений показателей, таких как время потоковой передачи на Netflix, отправленные сообщения или фотографии, которыми делятся в социальных приложениях.
В качестве альтернативы традиционному A/B-тестированию мы можем использовать схему повторных измерений для определения предпочтения Coca-Cola или Pepsi. В этом методе популяция не разбивается случайным образом. Вместо этого каждый может выбирать между Coca-Cola или Pepsi (ни один из брендов не имеет узнаваемых этикеток, но все же визуально различим). В конце эксперимента мы можем сравнить долю газированных напитков, потребляемых Coca-Cola или Pepsi, на уровне человека. В этом плане 1) мы устраняем неопределенность, вызванную привычками потребления газированных напитков на уровне населения, и 2) присваивая всем одинаковый вес, мы уменьшаем вероятность того, что на них сильно повлияет сильный дисбаланс газированных напитков.
Interleaving at Netflix
В Netflix мы используем чередование на первом этапе наших экспериментов, чтобы определить предпочтения членства между двумя алгоритмами ранжирования. На изображении ниже показана разница между A/B-тестированием и чередованием. В традиционном A/B-тестировании мы выбираем две группы подписчиков: одну, которая принимает алгоритм ранжирования A, и другую, которая принимает B. При чередовании мы выбираем набор подписчиков, подвергающихся воздействию алгоритмов чередующегося ранжирования A и B, сгенерированных путем смешивания ранжирования. Это позволяет нам одновременно предлагать пользователям выбор, определяющий их предпочтения в отношении алгоритма ранжирования. (Участники не могут сказать, по какому алгоритму было рекомендовано конкретное видео.) Мы рассчитываем относительное предпочтение алгоритма ранжирования, сравнивая количество часов, которое пользователи смотрят.
При генерации наборов видео в шахматном порядке с помощью двух алгоритмов ранжирования A и B подряд на главной странице Netflix мы должны учитывать наличие позиционной предвзятости: вероятность того, что участник воспроизведет видео, уменьшается по мере продвижения слева направо. Чтобы получить действительную меру чередования, мы должны гарантировать, что в любой заданной позиции в строке видео с равной вероятностью будет получено с помощью алгоритма сортировки A или B.
Чтобы решить эту проблему, мы использовали вариант чередования драфтов команд, который имитирует процесс выбора команды для товарищеских матчей. Во время этого процесса два капитана подбрасывают монету, чтобы определить, кто выбирает первым, а затем они поочередно выбирают членов команды. Каждый капитан выбирает игрока, который занимает первое место в списке предпочтений и все еще доступен. Этот процесс будет продолжаться до тех пор, пока не будет завершен выбор команды. Применяя эту аналогию к рекомендуемому Netflix процессу чередования, видео представляют доступных игроков, а алгоритмы ранжирования A и B представляют собой упорядоченные предпочтения двух капитанов команд. Мы случайным образом определили, какой алгоритм ранжирования предоставил первое видео для алгоритма чередующегося списка, а затем чередовали, при этом каждый алгоритм предоставлял видео с самым высоким рейтингом, которое у них все еще было доступным (см. рис. 4). Предпочтения пользователя в отношении алгоритма ранжирования A или B определяются путем измерения того, какой из алгоритмов обеспечивает большее количество часов просмотра в расположенном в шахматном порядке ряду.
Comparing the sensitivity of interleaving to traditional A/B testing
Наше первое требование к использованию чередования во время нашего двухэтапного онлайн-эксперимента заключается в том, что оно должно надежно идентифицировать лучшие алгоритмы сортировки с небольшими размерами выборки. Чтобы оценить, насколько хорошо чередование удовлетворяет этому требованию, мы обратимся к случаю, когда два алгоритма ранжирования A и B имеют известные относительные качества: ранг B лучше, чем ранг A. Затем мы используем эти два алгоритма, проводя эксперименты по чередованию параллельно с A/B. тестирование .
Чтобы сравнить чувствительность чередования по сравнению с A/B-тестированием, мы рассчитали предпочтение чередования и показатели A/B, используя разные размеры выборки. где образцы взяты из бутстрап-подвыборки. При выполнении бутстреп-анализа мы либо имитировали назначение N пользователей блоку чередования, либо назначение N/2 пользователей каждому блоку традиционного эксперимента A/B. Если мы случайным образом угадаем, какой ранкер лучше, вероятность того, что результат будет отличаться от истинного предпочтения, составит 50%. Когда эта вероятность составляет 5%, мы достигаем 95% уверенности в наших результатах обнаружения различий в качестве ранжирования. Таким образом, метрика, которая пересекает пороговое значение при меньшем количестве пользователей, является более чувствительной метрикой.
На рисунке ниже показаны результаты нашего анализа. Мы сравниваем предпочтение чередования с двумя метриками, обычно используемыми в настройках A/B: общей потоковой передачей и метрикой взаимодействия для конкретного алгоритма. Чувствительность метрик, используемых для оценки A/B-тестов, может сильно различаться. Мы обнаружили, что чередование является очень чувствительным: для достижения уровня достоверности 95% требовалось всего один процент пользователей по нашим наиболее чувствительным показателям A/B.
Correlation of interleaving metrics with A/B metrics
Наше второе требование заключалось в том, что метрики, измеренные на этапе чередования, должны были соответствовать нашим традиционным метрикам A/B-тестирования. Теперь мы оцениваем, может ли предпочтение чередования предсказать производительность ранжировщиков в последующих A/B-тестах.
На приведенном ниже графике показано изменение метрики предпочтения перемежения по сравнению с метрикой A/B по сравнению с контролем. Каждая точка данных представляет собой алгоритм ранжирования, который оценивался по сравнению с производственным ранжировщиком, который использовался в качестве контрольной группы. Мы обнаруживаем очень сильную корреляцию и согласованность между метрикой чередования и нашей наиболее чувствительной метрикой оценки A/B, что заставляет нас поверить, что предпочтение чередования может предсказать успех традиционных экспериментов A/B.
Conclusion
Чередование — это мощная технология, которая позволяет нам ускорить инновации в алгоритме ранжирования Netflix. Это позволяет нам точно измерять предпочтения участников для алгоритмов ранжирования и выявлять наиболее перспективных кандидатов в течение нескольких дней. Это позволяет нам быстро тестировать ряд новых алгоритмов, повышая скорость обучения.
Хотя чередование обеспечивает значительное повышение чувствительности и хорошо согласуется с показателями A/B, у него есть ограничения. Во-первых, реализовать структуру чередования довольно сложно, что является проблемой для инженерных возможностей. Наличие бизнес-логики может еще больше помешать всему процессу, что требует создания масштабируемых решений для проверки согласованности и автоматического обнаружения определенных проблем. Во-вторых, хотя чередование может быстро определить лучший алгоритм ранжирования, ограничение состоит в том, что оно является относительной мерой предпочтений пользователя в отношении алгоритмов ранжирования. То есть он не позволяет нам напрямую измерять изменения некоторых метрик.
Мы устраняем последнее ограничение, проводя эксперименты A/B на втором этапе, когда мы выбрали лучший набор кандидатов из первоначальных идей. Это позволило нам начать эксперименты, увеличив размер выборки, выделяемой каждым алгоритмом, что позволило нам тщательно измерить долгосрочное поведение пользователей. Решение этих проблем и разработка более эффективных способов измерения — это то, что мы постоянно изучаем.