A / B-тестирование - стандартный шаг в маркетинговом процессе многих компаний, занимающихся электронной коммерцией. С помощью хорошо разработанных A / B-тестов маркетологи могут получить представление о том, где и как максимизировать свои маркетинговые усилия и провести успешную кампанию. Однако с практической точки зрения стандартные A / B-тесты оставляют деньги на столе по сравнению с более продвинутыми подходами к машинному обучению.

В этом посте мы обсудим текущее состояние A / B-тестирования, определим несколько распространенных алгоритмов машинного обучения (Multi-Armed Bandits), используемых для оптимизации A / B-тестов, и, наконец, опишем производительность этих алгоритмов в нескольких типичных примерах. маркетинговые варианты использования.

A / B-тестирование: как это работает?

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

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

В данном эксперименте мы измеряем средний коэффициент конверсии для каждого варианта, но мы знаем, что это среднее значение является лишь оценкой «истинного» коэффициента конверсии. В зависимости от количества имеющихся у нас наблюдений мы можем быть более или менее уверены в значении оценки, и мы можем представить эту уверенность с помощью интервала, в котором может быть найдено истинное значение. Например, если мы говорим, что коэффициент конверсии составляет 0,032 +/- 0,002 при доверительной вероятности 95%, мы на 95% уверены, что реальный коэффициент конверсии находится в пределах 0,030–0,034. Таким образом, на практике мы будем искать доверительные интервалы, которые не пересекаются, так что вероятность того, что истинные коэффициенты конверсии различны, превышает 95%.

Однако ожидание разделения интервалов может занять много времени. В практическом случае для типичного коэффициента кликов 0,03, чтобы обнаружить 10% -ный рост числа кликов (0,03 * 0,1 = 0,003) со стандартными уровнями статистической мощности и значимости, нам потребуется минимальный размер выборки, составляющий всего 106 000 контактов. (53 000 контактов на вариант). В зависимости от трафика, накопление такого количества данных может занять от нескольких дней до нескольких месяцев, и если бы у нас было больше вариантов, более низкий коэффициент конверсии или меньший размер эффекта, период сбора мог бы быть намного больше.

Алгоритмы многоруких бандитов: исследование + эксплуатация

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

A / B-тестирование - это чисто исследовательский подход. Поскольку контакты случайным образом назначаются каждому варианту с равной вероятностью в тестовом эксперименте A / B, общий достижимый выигрыш равен среднему выигрышу всех вариантов и должен быть ниже, чем у выигравшего варианта. Как показано в приведенном выше примере, типичный A / B-тест обычно требует сотен тысяч контактов для достижения соответствующей статистической мощности. Использование алгоритма случайного распределения фиксированного размера для проведения экспериментов этого типа может привести к значительным потерям в общих выплатах - тесты A / B могут вызывать очень сильное сожаление.

Алгоритмы Многорукий бандит (MAB) можно рассматривать как альтернативу A / B-тестированию, которые уравновешивают использование и исследование в процессе обучения. Решение MAB использует существующие результаты эксперимента, чтобы выделить больше контактов для вариантов, которые работают хорошо, и при этом распределять меньше трафика для вариантов, которые неэффективны. Теоретически алгоритмы многорукого бандита должны давать более высокий общий выигрыш (и уменьшать сожаление), в то же время позволяя собирать данные о том, как пользователи взаимодействуют с различными вариантами кампании.

Существует несколько алгоритмов MAB, каждый из которых в разной степени предпочитает эксплуатацию разведке. Три самых популярных - это Epsilon Greedy, Thompson Sampling и Upper Confidence Bound 1 (UCB-1). В этом блоге мы обсудим каждый из этих алгоритмов MAB по отдельности, а затем сравним их поведение друг с другом и с настройкой A / B-теста в различных экспериментальных условиях.

Особенности алгоритма

(В этом разделе мы демонстрируем поведение алгоритма, используя одну из более простых схем моделирования, более подробно описанную ниже: двухвариантное моделирование с малой разницей.)

Эпсилон Жадный:

Epsilon Greedy, как следует из названия, является самым жадным из трех алгоритмов МАБ. В экспериментах Epsilon Greedy константа ε (от 0 до 1) выбирается пользователем перед началом эксперимента. При распределении контактов по разным вариантам кампании выбирается случайно выбранный вариант ε раз. В остальное время выбирается вариант с наибольшим известным выигрышем. Чем выше ε, тем больше этот алгоритм способствует исследованию. Для всех наших примеров ε установлено равным 0,1.

Результаты моделирования представлены на рис. 1. Более тонкие кривые получены из 10 случайно выбранных имитаций, а более толстая линия - это средний результат из 1000 симуляций. Левая панель показывает распределение контактов между двумя вариантами, а правая показывает фактический коэффициент конверсии для каждого варианта во время моделирования.

Интересно, что хотя в среднем алгоритм распределяет больше контактов для победившего варианта, для отдельных симуляций результат распределения может сильно отличаться от среднего поведения. Из-за небольших различий между двумя вариантами и небольшого количества контактов, которые мы выделили изначально, проигрышный вариант иногда показывает более высокий коэффициент конверсии в начале эксперимента. Поскольку алгоритм настолько «жадный», изначально «проигрышный» вариант не изучен в достаточной степени, чтобы алгоритм собрал достаточно данных, чтобы узнать реальный коэффициент конверсии для любого варианта во время эксперимента. Это также проявляется в зашумленности графика коэффициента конверсии для отдельных симуляций, которые не полностью сходятся к истинному среднему даже после 40 000 точек данных (контакты назначены).

Выборка Томпсона

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

По умолчанию параметры (𝛂 и 𝛃) каждого бета-распределения инициализируются равными 1 и 1, что приводит к одинаковым широким бета-распределениям для всех вариантов, что означает отсутствие предвзятости (поскольку у нас нет доказательств, позволяющих предположить, какой вариант может быть выигрышным). . По мере того, как мы собираем больше данных, распределение обновляется с учетом последних результатов (с преобразованием 𝛂 = n и без преобразования 𝛃 = n), и плотность вероятности начнет собираться вокруг среднего выигрыша. Чем больше количество точек данных, тем уже функция плотности вероятности (см. Рис. 2). Если есть твердые априорные убеждения относительно того, как должен вести себя каждый вариант, мы можем изменить 𝛂 и 𝛃, чтобы представить это априорное распределение до начала эксперимента.

Ниже (рис. 3) приведен средний результат нашего двухвариантного моделирования для выборки Томпсона. Как и в случае с Epsilon Greedy (рис. 1), отдельные модели сэмплирования Томпсона довольно сильно отклоняются от среднего поведения в начале эксперимента. Однако на более поздних этапах эксперимента поведение отдельных симуляторов становится более последовательным и сходным со средними результатами.

Чтобы получить больше информации об этом поведении, мы построили графики распределения средней плотности вероятности (PDF) для двух случайно выбранных имитаций на разных этапах эксперимента (рис. 2) вместе с распределением контактов для каждого моделирования (вставные панели). В обоих случаях PDF-файлы с начала эксперимента начали широко и сильно перекрываться, а с дополнительными точками данных в конечном итоге стали довольно хорошо разделенными к концу эксперимента. Как и ожидалось, мы можем отследить, как распределяются контакты на каждом этапе эксперимента, посмотрев, насколько PDF двух плеч перекрываются, и какое из них имеет более высокий средний коэффициент конверсии (пик PDF).

UCB-1:

Для каждого варианта кампании мы определим верхнюю границу достоверности (UCB), которая представляет собой наше наивысшее предположение о возможном выигрыше для этого варианта. Алгоритм назначит контакты варианту с наивысшим UCB.

UCB для каждого варианта рассчитывается как на основе среднего выигрыша варианта, так и количества контактов, назначенных для варианта, с помощью уравнения:

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

Ниже (рис. 4) снова представлены результаты двухвариантного моделирования (коэффициент конверсии 0,024 против 0,023) с использованием UCB-1. UCB-1 работает очень похоже на пропорциональное распределение (рис. 3) и намного более консервативно по сравнению с Epsilon Greedy (рис. 1). На начальном этапе эксперимента (первые 30 000 точек данных) алгоритм в основном представляет собой чистое исследование с распределением почти равного количества контактов между двумя руками. Как и пропорциональное распределение, результаты UCB-1 из отдельных симуляций довольно стабильны и напоминают средний результат. Это снова демонстрирует тот факт, что алгоритм способен сбалансировать исследование и эксплуатацию в рамках одного эксперимента, оптимизируя распределение контактов, чтобы выявить реальный выигрышный вариант и затем воспользоваться им.

Настройка моделирования

Теперь, когда у нас есть представление о том, как ведет себя каждый из алгоритмов, мы можем сравнить их поведение с исходной настройкой A / B-теста. Мы делаем это, настраивая следующие 5 симуляций.

Первые 3 моделирования содержат 5 вариантов, каждый со стационарным коэффициентом конверсии, перечисленным ниже. Чтобы оценить, как эти алгоритмы работают в реальных ситуациях, мы устанавливаем истинные коэффициенты конверсии для вариантов в каждой модели, чтобы они соответствовали тем, которые встречаются в типичных сценариях использования маркетинговой кампании по электронной почте. Кроме того, мы запустили 2 дополнительные двухвариантные версии моделирования коэффициента конверсии. Все коэффициенты конверсии, использованные при моделировании, перечислены в таблице 1.

Для всех симуляций мы делаем начальный шаг распределения с 200 контактами, одинаково распределенными для всех 5 вариантов (поскольку предыдущих результатов нет). После этого для каждого шага распределения мы добавляем в эксперимент 200 дополнительных контактов, выделяемых на основе определенного алгоритма MAB. Для моделирования с двумя вариантами, моделирования скорости открытия и моделирования конверсии с высокой разницей мы выполнили в общей сложности 400 шагов, повторенных 1000 раз. Для моделирования преобразования с малой разницей мы выполнили 1000 шагов и 2000 повторов, чтобы лучше оценить поведение алгоритмов. Во всех случаях мы определяем выплату как двоичную конверсию, а то, что мы сравниваем между вариантами, - это коэффициенты конверсии. Результаты существенно не изменятся, если мы будем использовать другие определения выплаты, такие как доход. Для всех симуляций Epsilon Greedy параметр ε установлен на 0,10.

Для каждого шага распределения мы отслеживаем распределение контактов, общую производительность и статистическую значимость (p-значение 2-процентного z-критерия для 2 вариантов и критерий непредвиденных обстоятельств хи-квадрат для более чем 3+ вариантов).

Результаты моделирования:

  • Назначение контактов:

Для симуляций с небольшими различиями в выплатах (Рис. 5, Рис. 6) UCB-1 распределяет контакты наиболее консервативно (наиболее похоже на равное распределение), поскольку различия в производительности вариантов настолько малы. Thompson Sampling и Epsilon Greedy намного жаднее, выделяя в два раза больше контактов для победившего варианта по сравнению с UCB-1. Для моделирования с 5 вариантами с низким уровнем конверсии выборка Томпсона была немного более консервативной, чем Epsilon Greedy в первой трети эксперимента, но в конечном итоге догнала.

Для моделирования нормального коэффициента открытия (Рис. 7) и высокой разницы (Рис. 8, 9) коэффициента конверсии UCB-1 остается наиболее консервативным алгоритмом, а Thompson Sampling - наиболее жадным. Интересно, что выборка Томпсона в этих симуляциях вела себя гораздо более жадно, чем в симуляциях с малой разницей. Это демонстрирует способность Thompson Sampling балансировать между разведкой и разработкой, отдавая предпочтение последнему в сценариях с четкими и легко обнаруживаемыми различиями в выплатах между вариантами. В одном из трех примеров Thompson Sampling выделил почти вдвое больше контактов победившему варианту, чем UCB-1 в конце моделирования.

  • Общая выплата:

Как и ожидалось, во всех симуляциях все три алгоритма дают более высокие общие выплаты, чем настройки A / B-теста, при этом более жадные алгоритмы показывают лучшую производительность. С нашим предопределенным ε, равным 0,1, Epsilon Greedy превосходит другие алгоритмы в наиболее сложном случае (5-вариант с низким коэффициентом преобразования). Во всех остальных четырех сценариях Epsilon Greedy получал более высокие выплаты на ранней стадии эксперимента, но Thompson Sampling последовательно обгоняет Epsilon Greedy, становясь более жадным по мере сбора большего количества точек данных (как видно из результатов распределения) и получает более высокий конечный результат. общая выплата. Это еще раз демонстрирует, как Thompson Sampling поддерживает исследования перед лицом неопределенности на ранней стадии эксперимента, сохраняя при этом возможность переключиться на использование в более поздней фазе эксперимента.

  • Статистическая значимость:

Для всех симуляций UCB-1 смог достичь статистической значимости (p

Для моделирования с большой разницей все алгоритмы достигли статистической значимости в течение экспериментов. Подобно результатам, приведенным выше, тесты UCB-1 и A / B достигли p

Вывод:

С помощью результатов этого моделирования мы продемонстрировали, что, когда необходим рандомизированный контролируемый эксперимент, алгоритмы MAB всегда будут более выгодной альтернативой A / B-тестированию. Конкретный выбор алгоритма зависит от того, хочет ли пользователь определить приоритетность прибыли или сбора данных, а также от предполагаемого размера и продолжительности эксперимента.

В редких случаях, когда известно, что разница в выплатах между тестируемыми вариантами довольно велика, все алгоритмы смогут показать статистически значимые различия между вариантами в пределах нескольких точек данных. Выборка Томпсона, или жадный алгоритм Epsilon Greedy, в этом случае становится безоговорочным победителем для максимизации выплаты.

И Thompson Sampling, и UCB-1 смогли оптимизировать общую выплату во всех случаях, не жертвуя при этом исследованием всех вариантов и обнаружением статистических различий между ними. UCB-1 будет производить распределения, более похожие на A / B-тест, в то время как Thompson более оптимизирован для максимизации долгосрочной общей отдачи. UCB-1 также ведет себя более последовательно в каждом отдельном эксперименте по сравнению с Thompson Sampling, который испытывает больше шума из-за шага случайной выборки в алгоритме. С небольшими различиями в производительности вариантов, что типично для результатов A / B-тестов, которые мы видели в прошлом, UCB-1 имеет тенденцию быть довольно консервативным по сравнению с Thompson Sampling и Epsilon Greedy (при ε = 0,1). Когда ε установлено слишком низким, Epsilon Greedy может захватить наибольшее значение в лучшем случае, но поведение алгоритма также становится довольно нестабильным, легко подавляемым шумом в наблюдаемых преобразованиях.

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