Ускоритель статистики - когда, почему и как

Привет, читатели! Я Сэмми и один из инженеров по машинному обучению, которые создали Stats Accelerator, набор алгоритмов адаптивного распределения трафика. Это первая часть из двух частей, и я пишу эту часть, чтобы пролить свет на то, зачем мы создали Stats Accelerator, для каких бизнес-потребностей он был разработан, а также дать общее объяснение того, как работают эти алгоритмы и как они может применяться к потребностям вашего бизнеса. Этот пост содержит некоторые концепции бандитов. Не волнуйтесь, внизу сообщения есть глоссарий определений и ссылок.

Присоединяйтесь к моей команде! Мы нанимаем инженеров машинного обучения в Сан-Франциско и Остин.

Что такое Stats Accelerator и зачем его использовать?

Когда клиент настраивает A / B / n-тест с помощью Optimizely, он выбирает, какой процент посетителей (или образцов) будет подвергаться каждому из вариантов теста. Это распределение трафика для теста. Распределение трафика остается прежним, если только покупатель не изменит его вручную - например, чтобы перенаправить трафик на вариант, который кажется более эффективным, чем другие.

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

  1. Быстрое выявление статистически значимого отклонения. В этом сценарии клиент, выполняющий A / B / n-тест, хочет узнать, может ли изменение привести к полезному анализу. То есть отличается ли вариант от базовой линии по заданной метрике? Мы называем это различие подъемом или улучшением. Если отличается, как можно быстрее найдите тот, который наиболее удален от базового - при одновременном контроле частоты ложных обнаружений (FDR) ниже заданного порогового значения, чтобы они могли проинформировать их о том, как оптимизировать свой бизнес.
  2. Оптимизация вознаграждения на определенный период времени. В этом сценарии клиенты хотят максимизировать воздействие, например доход. Например, покупатель, участвующий в акции «Черная пятница», может захотеть поэкспериментировать с разными заголовками на своей целевой странице, чтобы максимизировать прибыль. Они не озабочены внедрением каких-либо постоянных изменений; они хотят направлять посетителей только к варианту, который дает самые высокие коэффициенты конверсии на данный момент, и удаляют варианты со своего веб-сайта после завершения рекламной акции.

Чтобы помочь клиентам достичь этих двух целей, мы запустили Stats Accelerator с двумя режимами: Accelerate Learning для первого сценария и Accelerate Impact для второго. Оба режима динамически изменяют распределение трафика теста, но их стратегии и цели сильно различаются.

Ускорение обучения

Мы сотрудничаем с Кевином Джеймисоном из факультета компьютерных наук и инженерии Вашингтонского университета, который разработал итерационный алгоритм, который выявляет существенные вариации как можно быстрее, направляя больше посетителей к вариантам, которые имеют больше шансов достижение статистической значимости. При этом приоритет отдается поиску вариации, величина эффекта которой, то есть наблюдаемая разница между ней и базовой линией, является наибольшей, при этом FDR остается ниже заданного порога. Мы внедрили его алгоритм и назвали его Ускоренное обучение.

Для простоты предположим, что все варианты имеют истинное среднее значение, превышающее базовое значение для остальной части этого раздела. Это означает, что со временем будет обнаружено, что все варианты имеют статистически значимые улучшения. Мы заинтересованы в том, чтобы сначала найти вариацию, наиболее удаленную от базовой линии, в как можно меньшем количестве выборок. Грубо говоря, этот алгоритм выделяет больше трафика для варианта с максимальной достоверностью на каждой итерации. Наивысшая доверительная граница - это верхняя конечная точка доверительного интервала, наиболее удаленная от нуля. На следующей итерации он наблюдает доверительные интервалы результирующих вариаций и эмпирические средние и принимает решения на основе этого. Как только изменение достигает статистической значимости, оно исключается из рассмотрения, и процесс повторяется, при этом алгоритм фокусируется на оставшихся безрезультатных вариантах, чтобы определить следующий лучший вариант.

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

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

В качестве примера предположим, что клиент запускает программу Accelerate Learning и ищет лучший вариант. В момент времени t = t0 результаты следующие:

Accelerate Learning выделяет больше трафика для Var1 по сравнению с Var2 и Var3, потому что похоже, что он может достичь статистической значимости с меньшим количеством выборок, чем другие. На это указывает его доверительный интервал, верхняя граница которого наиболее удалена от 0.

И в момент t = t0 + 1 - при следующем запуске алгоритма - наблюдаем результаты:

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

Ускорение воздействия

Чтобы оптимизировать метрику Бернулли, мы используем выборку Томпсона (объяснения этих терминов см. В Глоссарии ниже). Для каждого варианта мы используем текущее наблюдаемое в тесте количество уникальных конверсий и количество посетителей, чтобы охарактеризовать бета-распределение. Мы пробуем эти распределения несколько раз и распределяем трафик в соответствии с их коэффициентом выигрыша.

Например, предположим, что у нас есть следующие результаты по сравнению уникальных конверсий при обновлении распределения трафика:

Мы характеризуем бета-распределения, обозначенные как Beta (𝛼, 𝛽), на основе этих значений, где 𝛼 - количество уникальных конверсий, а 𝛽 - количество посетителей для каждого варианта. Например, оригинал будет характеризоваться Beta (189, 323).

Мы пробуем эти распределения N раз - скажем, 10 000 - записывая распределение, которое дает наибольшее значение в каждом раунде. Это имитирует то, что могло бы произойти, если бы у нас было 10 000 посетителей, выделенных для оригинала, 10 000 - для варианта № 1 и 10 000 - для варианта № 2. Отношение выигрышей каждого варианта определяет процент выделенных ему новых посетителей:

На следующей итерации мы снова запускаем Thompson Sampling с обновленными наблюдениями.

Вышеупомянутый алгоритм работает для двоичных показателей, но не для числовых показателей. Для числовых показателей, таких как доход или количество событий на пользователя, мы реализовали Epsilon-Greedy bandit (подробности см. В глоссарии ниже). Этот бандит равномерно распределяет небольшую (эпсилон) часть трафика между всеми вариациями для исследования, а затем выделяет большую (1-эпсилон) часть для вариации с наибольшим наблюдаемым средним значением для эксплуатации.

Дилемма разведки и эксплуатации

Причина, по которой должна быть часть трафика, предназначенная для исследовательских целей, заключается в том, что эмпирические средства могут не быть близкими к их истинным средствам. Как Epsilon-Greedy, так и Thompson Sampling in Accelerate Impact являются общими стратегиями, которые решают дилемму эксплуатации-разведки (определения эксплуатации и разведки см. В Глоссарии). Thompson Sampling способствует раннему исследованию из-за неопределенностей на ранних этапах тестирования, тогда как Epsilon-Greedy больше фокусируется на эксплуатации, направляя большую часть трафика на вариацию с наивысшим эмпирическим средним значением. Если покупатель будет использовать только ту информацию, которую он наблюдал, то он направит всех новых посетителей на вариант, имеющий наивысшее эмпирическое среднее значение. Но как они узнают, действительно ли эта вариация имеет наивысшее истинное среднее значение? Им потребуется больше образцов, чтобы уменьшить эту неопределенность. Вот где исследование становится важным, потому что оно дает больше свидетельств о лежащих в основе средствах. Следовательно, необходим баланс между ними.

Ускоренное обучение также имеет форму исследования и эксплуатации. Что касается эксплуатации, он использует верхние доверительные границы каждого варианта, выделяя больше трафика на верхнюю границу. И если его решение было неоптимальным, он узнает из обновленных результатов теста. В результате будут исследованы другие варианты.

Когда следует использовать Accelerate Impact вместо Accelerate Learning?

Accelerate Learning предоставляет клиентам полезную информацию, позволяющую быстро внедрить наиболее значимые изменения в их бизнес. Он фокусируется на статистической неопределенности вариаций, используя доверительные интервалы для обновления распределения теста, чтобы сократить время на поиск наиболее значимой вариации.

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

Из желания клиентов автоматизировать распределение трафика и различных бизнес-потребностей вытекают два разных алгоритма, каждый из которых ориентирован на свою цель.

Скоро: запись в блоге о том, как мы решили парадокс Симпсона

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

Вам это показалось интересным? Присоединяйтесь к моей команде! Мы нанимаем инженеров машинного обучения в Сан-Франциско и Остин.

Глоссарий

  • Рука: это бандитский жаргон. Рука - это синоним вариации.
  • Показатель Бернулли: измеримое действие, равное 0 или 1, например, совершил посетитель или нет.
  • Размер эффекта: в тесте A / B / n это наблюдаемая разница между исходным уровнем и вариацией.
  • Epsilon-Greedy Bandit: ознакомьтесь с Стратегией Epsilon-Greedy в разделе Bandit Strategies здесь.
  • Эксплуатация: бандитский жаргон. Принятие решения с учетом актуальной информации.
  • Исследование: бандитский жаргон. Сбор дополнительной информации.
  • Разведка-эксплуатация проблема: бандитский жаргон. Направляем ли мы весь трафик на наблюдаемую нами вариацию, имеющую наивысшее эмпирическое среднее значение (использование)? Если это не лучший вариант, то как нам направить некоторый трафик на другие варианты, чтобы найти вариант с самым высоким истинным средним значением (исследование)? Каков оптимальный компромисс между этими двумя состояниями?
  • Коэффициент ложного обнаружения: это среднее количество неверных отклонений нулевой гипотезы по всем открытиям, сделанным в наборе тестов A / B / n. Прочтите эту замечательную статью, в которой рассказывается, почему мы используем это в Stats Engine.
  • Многорукий бандит: тип проблемы, в которой стратегия заключается в оптимизации конкретной функции путем принятия решения о распределении ресурсов.
  • Числовая метрика: измеримое событие, не равное 0 или 1 (читай: не метрика Бернулли). Сюда входят такие показатели, как доход, количество кликов на посетителя и т. Д.
  • Образец: наблюдение. Если мы измеряем количество уникальных конверсий на посетителя, выборкой будет посетитель.
  • Статистическая значимость: вероятность того, что разница в коэффициентах конверсии между заданным вариантом и базовым уровнем не является случайной. Перейдите по этой ссылке, чтобы увидеть, как связаны доверительные интервалы и статистическая значимость.
  • Выборка Томпсона: эвристика для выбора способа распределения трафика при решении проблемы эксплуатации-разведки в сценарии многорукого бандита. Ознакомьтесь с этой ссылкой для более подробного ознакомления с этой темой.
  • Распределение трафика: распределение новых посетителей по вариантам теста.
  • Верхний предел достоверности: бандитский жаргон. Также известен как UCB. Верхнее значение доверительного интервала.