Использование бандитской политики для эффективного обучения на ходу
Принятие правильных решений требует информации о ваших возможностях. В отсутствие информации люди обычно понимают, когда вы делаете ошибки - в конце концов, ошибки - отличный способ собрать данные о ваших вариантах. По этой причине люди говорят такие вещи, как «не сдавайся, пока не попробуешь». Но люди также теряют к вам симпатию, когда вы повторяете одни и те же ошибки снова и снова - «одурачите меня один раз» и все такое. Это отражает интуицию о том, что должен быть баланс между попыткой нового для сбора информации и использованием информации, которую мы получаем в ходе наших испытаний. В машинном обучении это иногда называют дилеммой «исследовать или использовать».
В Red Ventures мы запускаем множество веб-сайтов - примерно 50 сайтов, обслуживающих около 115 миллионов сеансов в месяц. На каждом сайте, который мы запускаем, всегда есть варианты того, какие продукты мы должны показывать, какие специальные предложения, какой дизайн - даже такие вещи, как цвета и изображения, могут иметь значение, от того, на что вы не хотите смотреть. По этой причине нам нужны системы для эффективного тестирования различного опыта. В этой статье будут представлены некоторые из этих методов и приведен пример кода, чтобы вы могли провести собственное исследование.
Вариант 1 - A / B-тестирование - нестандартный подход
Если вы впервые думаете о тестировании, у вас может возникнуть желание попробовать каждый вариант несколько раз, а затем использовать тот, который лучше всего подходит. Главный нюанс этого подхода заключается в количественном определении того, сколько раз «пачка», и в интерпретации результатов вашего испытания. Есть несколько способов обдумать это, но вот самый простой из известных мне.
Предположим, мы нашли монету и задаемся вопросом о вероятности θ того, что она выпадет орлом (я буду называть это число "ставкой орла" для монеты). Допустим, мы перевернули его 10 раз, и он дважды выпал орлом. Мы могли бы закодировать это как кортеж:
D = (T, T, T, H, T, T, H, T, T, T)
Что было бы хорошей моделью для оценки голов? Если вы думаете, что ставка орла для этой монеты составляет θ = 1/5, спросите себя, насколько вы в этом уверены. Может, это и правда честная монета? Функция плотности вероятности может описать наши убеждения относительно истинной ставки орла для монеты. Итак, как должна выглядеть эта плотность?
Кто-то может сказать, что форма этого распределения должна зависеть не только от имеющихся у нас свидетельств (10 подбрасываний монеты с двумя орлами), но и от наших прежних представлений о монете. Например, наша интерпретация 10 бросков, вероятно, была бы другой, если бы монета представляла собой четверть доллара США прямо с Монетного двора, а не галеон, подаренный нам Гарри Поттером. Правило Байеса дает нам возможность рассуждать об этих двух силах: (1) наши прежние убеждения и (2) данные, которыми мы располагаем.
Функция правдоподобия и априорное распределение.
Мы хотим закодировать собранные данные. Один из способов сделать это - рассмотреть вероятность просмотра этих данных при наличии заданной скорости нападающих θ. В этом случае вероятность определяется как:
Это называется «функцией правдоподобия», где a - количество орлов, а b - количество наблюдаемых хвостов. Обычно мы будем думать об этом как о функции интересующего нас параметра θ. Что мы действительно хотели бы знать, так это P (θ | D) - распределение для θ с учетом данных, которые мы видели, которое мы называем апостериорной вероятностью. Связь между нашей известной функцией правдоподобия и этой апостериорной оценкой дается правилом Байеса (которое непосредственно следует из определения условной вероятности):
D для нас является фиксированным, поэтому имеет смысл думать о P (D) как о константе c - независимо от θ - , чтобы правильно нормализовать заднюю часть. Мы также можем - на данный момент - взять для P (θ) равномерное распределение, где P (θ) = 1 для всех θ между 0 и 1. С этими сокращениями и заменой в нашу рассчитанную вероятность мы получаем, что:
Более того, мы можем вычислить значение c, зная, что наша апостериорная оценка должна интегрироваться более θ до значения 1. Итак, имеем:
Это известно как бета-распределение - и это кажется нам естественным выбором. Он определяется двумя параметрами, которые мы можем рассматривать как количество успехов и неудач. По соглашению это должно быть написано как
где c - соответствующая константа. Более того, бета-распределение обладает прекрасным свойством: когда мы выбираем это распределение для априорного или апостериорного, оно обеспечивает (по правилу Байеса) распределение для другого. Это часто резюмируют, говоря, что бета-распределение является сопряженным априорным значением для функции правдоподобия Бернулли.
Оценка ставки орла для нашей загадочной монеты
Давайте посмотрим на нашу историю с монетами, чтобы увидеть пример этого. У нас были данные, состоящие из 10 флипов с 2 орлами и 8 решками. Это дает нам вероятность
Выбор предшествующего должен закодировать наше мнение о ситуации, прежде чем рассматривать эти данные. Предположим, что наше априорное значение дается распределением Бета (5,5), то есть мы думаем, что это честная монета, но имеем очень широкий доверительный интервал при этом предположении. Затем апостериор можно вычислить как:
Используя ту же логику, мы можем видеть, что если бы мы вместо этого выбрали бета (1,1) (то есть неинформативный) априор, то мы пришли бы к апостериорному бета (3,9). Таким образом, существует очевидный механизм, с помощью которого предварительные убеждения и эмпирические данные смешиваются, чтобы прийти к апостериорному. Ниже приведены графики различных обсуждаемых бета-дистрибутивов (созданных с использованием R со следующим кодом).
theta = seq(0,1, length=1000)
plot(theta, dbeta(theta, 7, 13), type =”l”, col=4)
lines(theta, dbeta(theta, 3, 9), type =”l”, col=3)
lines(theta, dbeta(theta, 5, 5), col=2)
lines(theta, dbeta(theta, 1, 1), col=1)
legend(“topright”,
c(“Beta(7,13)”,”Beta(3,9)”,”Beta(5,5)”, “Beta(1,1)”) ,
lty=c(1,1,1,1),
col=c(4,3,2,1)
Теперь, когда у нас есть распределения, которые описывают апостериорную вероятность ставки орла нашей монеты при различных априорных значениях, мы можем рассуждать о том, какого типа поведения мы можем разумно ожидать от монеты. Например, мы можем использовать связанные функции совокупной плотности для оценки вероятности того, что ставка орла для рассматриваемой монеты превышает 50%:
В R это может быть выполнено с помощью:
> 1 — pbeta(0.5, 3, 9) [1] 0.03271484 > 1 — pbeta(0.5, 7, 13) [1] 0.08353424
для апостериорной, заданной неинформативной априорной и бета-версией (5,5) соответственно.
Связь с тестированием
До сих пор наше обсуждение вращалось вокруг понимания ставки орла для отдельной монеты на основе данных, полученных в результате испытаний (или подбрасываний) этой монеты. Более интересная ситуация, когда у нас есть несколько монет на выбор, и мы хотим определить монету с наибольшей ставкой орлов. Эта ситуация часто возникает в Red Ventures. В частности, у нас может быть три разных предложения, которые могут отображаться на веб-сайте - каждое со своим коэффициентом конверсии. Мы хотели бы понять эти коэффициенты конверсии, чтобы знать, какие предложения больше всего находят отклик у пользователей и какие предложения приведут к наибольшему количеству конверсий.
В этом случае мы можем выбрать априорные значения для предложений, случайным образом обслуживать предложения для посетителей для сбора данных, а затем рассчитывать апостериорные значения для различных коэффициентов конверсии, как описано выше. Затем мы можем использовать эти апостериорные распределения, чтобы обсудить наши варианты и решить, как двигаться дальше.
Хотя эта стратегия удовлетворительна с точки зрения сбора знаний, она оставляет желать лучшего с точки зрения эффективности. Чтобы убедиться в этом, предположим, что мы тестируем три предложения. После дня случайного показа предложений у нас есть следующие данные о конверсиях:
Вариант 1: 100 просмотров, 6 конверсий
Вариант 2: 100 просмотров, 12 конверсий
Вариант 3: 100 просмотров, 15 конверсий
С неинформативными (Beta (1,1)) априорными значениями эти данные дают нам следующие апостериорные данные:
Глядя на эти последующие данные, у вас может возникнуть ощущение, что тестирование должно продолжиться завтра, но также что мы теряем конверсии, показывая предложение 1. Может быть, предложения 2 и 3 должны получить большую часть завтрашнего трафика, чтобы помочь уменьшить некоторые из этих потерь?
Тестирование идей пропорционально их производительности - это основная концепция, лежащая в основе идеи под названием Thompson Sampling, которая уравновешивает исследование (или получение информации о ваших вариантах) и использование (максимизацию конверсий с течением времени за счет использования информации, которую вы получаете в процессе). На следующем занятии мы углубимся в эту идею и попытаемся количественно оценить, насколько она может быть более эффективной.
Дубль 2 - Бандитский подход
Я склонен думать о подходе к оптимизации решений, основанном на тестировании, с точки зрения «ориентированности на знания». То есть я сосредоточен на понимании каждого варианта и количественной оценке этого понимания с очень маленькими полосами погрешностей. Когда у нас есть это понимание, часть оптимизации становится результатом знаний. Если мы можем количественно оценить, насколько хорошо выполняется каждое действие, то мы знаем, как действовать. Что, если вместо этого мы сделаем приоритетом не знания, а производительность в течение определенного периода времени? Это, по сути, проблема бандитов.
Бандитская проблема
Исходная формулировка задачи о бандите такова: представьте себе три игровых автомата перед вами. Каждую минуту вы можете дергать за ручку одного игрового автомата и получать «вознаграждение» - скажем, это вознаграждение 0 или 1. Ваша цель - максимизировать сумму всех полученных вознаграждений.
Оказывается, существует много разновидностей этой проблемы, но мы предполагаем, что награда для слота i (для каждого i) определяется i.i.d. из статического неизвестного распределения ν (i) (это предположение приводит нас к так называемой «проблеме стохастического многорукого бандита» и исключает ситуации, когда награды тщательно выбираются каким-то неизвестным противником).
У вас может возникнуть вопрос: «Почему это называется« проблемой бандитов »?» Здесь Bandit - это сокращение от «многорукий бандит». В какой-то момент игровые автоматы были известны как «однорукие бандиты», потому что у них одна рука и они часто крадут ваши деньги.
Эта проблема аналогична нашей проблеме выбора предложения: для каждого посетителя мы выбираем предложение 1, 2 или 3, чтобы показать их, а затем получаем (в качестве вознаграждения) либо конверсию, либо отсутствие конверсии. Наша цель - получить как можно больше конверсий (или продаж, или кликов, или подписок).
Сэмплинг Томпсона
Есть много подходов к этой проблеме, но метод, который выделяется своей теоретической и эмпирической эффективностью, также является довольно старым и простым. Предложенная в 1933 году методика Thompson Sampling работает путем построения для каждого варианта (обычно называемого на бандитском языке оружием) апостериорное распределение для неизвестной степени вознаграждения этой руки. Когда приходит время выбрать вариант для пользователя, мы производим выборку из каждой апостериорной точки и выбираем вариант с самой высокой выборкой. После получения награды соответствующая апостериорная информация может быть обновлена.
Более формально проблема сформулирована так:
И предлагаемое решение можно записать как:
Давайте подумаем, как Thompson Sampling будет вести себя в случае наших трех предложений сверху. На тот момент у нас есть:
Вариант 1: 100 просмотров, 6 конверсий
Вариант 2: 100 просмотров, 12 конверсий
Вариант 3: 100 просмотров, 15 конверсий
и поэтому мы ожидаем, что алгоритм выборки Томпсона будет рекомендовать все варианты, но не в равной степени. Мы ожидаем, что варианты 3 и 2 будут получать наибольшее количество сеансов, а вариант 1 - гораздо меньше сеансов. Чтобы понять это поведение, мы можем взять 10 000 выборок из каждого из этих распределений и посчитать, как часто будет выбираться каждая рука. В R это можно сделать с помощью:
> numSamples <- 10000 > offer1Samples <- rbeta(numSamples, 6,94) > offer2Samples <- rbeta(numSamples, 12, 88) > offer3Samples <- rbeta(numSamples, 15, 85) > > sum(offer1Samples > offer2Samples & offer1Samples > offer3Samples) [1] 72 > sum(offer2Samples > offer1Samples & offer2Samples > offer3Samples) [1] 2655 > sum(offer3Samples > offer1Samples & offer3Samples > offer2Samples) [1] 7273
Итак, мы видим, что на данный момент алгоритм выборки Томпсона будет выбирать вариант 1 менее чем в 1% случаев, вариант 2 - примерно в 27% случаев и вариант 3 - примерно в 73% случаев.
Эмпирические результаты
Здесь важно помнить, что преимущество Thompson Sampling заключается не в том, что он открывает больше знаний, чем A / B-тест, а в том, что он позволяет учиться более эффективно. Чтобы попытаться определить это количественно, давайте проведем эксперимент. Предположим, у меня есть три разных предложения, которые могут отображаться на веб-странице, и что я выделил 10 000 сеансов для тестирования этих предложений. Допустим, реальные коэффициенты конверсии для трех предложений:
Предложение 1: коэффициент конверсии 12%
Предложение 2: коэффициент конверсии 5%
Предложение 3: коэффициент конверсии 9%
Один из полезных способов оценить эффективность теста - это рассмотреть количество потерянных конверсий по сравнению с показом лучшего варианта в любое время. Эта концепция известна как сожаление. Сожаление (или ожидаемое количество потерянных конверсий) о распределении трафика поровну между тремя вариантами можно затем рассчитать как:
> .12*10000 — .12*(10000/3) — .05*(10000/3) — .09*(10000/3) [1] 333.3333
Таким образом, при проведении традиционного сплит-теста на этих сессиях мы платим 333 конверсии за все полученные знания. В чем же тогда сожаление, вызванное использованием Thompson Sampling? Мы можем ответить на этот вопрос с помощью простой симуляции (здесь написано на R).
set.seed(7)
#simulation parameters
rate1 <- .12
rate2 <- .05
rate3 <- .09
numSessions <- 10000
numArms <- 3
modelParams <- list()
rates <- c(rate1, rate2, rate3)
bestRate <- max(rates)
for (i in 1:numArms) {
modelParams[[i]] <- c(1,1)
}
rewardHistory <- c()
armHistory <- c()
#helper functions
flip <- function(p) {rbinom(1,1,p)}
sampleBeta <- function(params) {rbeta(1,params[1],params[2])}
vSampleBeta <- function(lparams) {simplify2array(lapply(X = lparams, FUN = sampleBeta))}
sampleArm <- function(lparams) {which.max(vSampleBeta(lparams))}
#simulation
for (i in 1:numSessions) {
arm <- sampleArm(modelParams) #choose arm (an integer)
reward <- flip(rates[[arm]])
if (reward == 1) { #update modelParams
modelParams[[arm]][1] <- modelParams[[arm]][1] + 1
} else if (reward == 0) {
modelParams[[arm]][2] <- modelParams[[arm]][2] + 1
}
rewardHistory[i] <- reward
armHistory[i] <- arm
}
Этот код конструирует наивные априорные значения для каждого варианта, а затем рекомендует предложения на основе апостериорных распределений - обновляя апостериорные значения по мере поступления новых данных в соответствии с правилом Байеса.
Затем мы можем посмотреть историю рекомендованных вооружений.
> table(armHistory) armHistory 1 2 3 9275 195 530
чтобы увидеть, что эта бандитская политика быстро отбрасывает вариант 2 и тратит немного больше времени на изучение варианта 3, но в конечном итоге рекомендует вариант 1 (оптимальный выбор) примерно в 93% случаев на протяжении всего эксперимента. (Обратите внимание, что, поскольку это случайный процесс, ваш результат может выглядеть иначе).
Затем количество конверсий в соответствии с этой политикой можно подсчитать и сравнить с количеством конверсий, ожидаемых, когда отображается только лучшая рука:
> bestRate*numSessions — sum(rewardHistory) [1] 33
Итак, мы видим, что в данном случае мы платим всего 33 преобразования за наши знания. По сравнению с традиционным сплит-тестом, выбирая эту методику, мы получаем дополнительно 300 конверсий.
Давайте посмотрим на бета-версии, полученные в рамках этих двух правил. В рамках сплит-теста мы имеем:
а при выборке Томпсона мы получаем:
Эти изображения помогают проиллюстрировать тот факт, что в традиционном сплит-тесте мы ищем информацию одинаково среди всех вариантов. В результате каждое распределение дает относительно точную оценку истинного коэффициента конверсии. В отличие от этого, с помощью выборки Томпсона мы узнаем достаточно о менее оптимальных вариантах, чтобы знать, что они не лучше, чем лучший вариант. Об этом свидетельствует более широкая степень неопределенности для предложений 2 и 3. Короче говоря, мы не заботимся о тщательной количественной оценке коэффициентов конверсии наших неэффективных активов - мы просто хотим знать, что они неэффективны.
Что дальше?
Мы считаем, что Red Ventures имеет много улучшений в вышеуказанной стратегии. Хотя обсуждение того, как это можно реализовать, придется отложить до следующей публикации, вот некоторые проблемы, которые стоит решить с помощью дополнительной методологии. Хотите узнать больше о конкретной теме? Дай мне знать в комментариях!
Небинарные структуры вознаграждения
В общем, нам может потребоваться оптимизация для небинарного события, такого как доход за сеанс.
Динамические структуры вознаграждения
Подобно тому, как модные предпочтения меняются со временем, мы можем ожидать, что предпочтения пользователей будут динамичными. Возможно, вы захотите, чтобы информация со временем терялась, чтобы не разрабатывать политику, которая устаревает.
Контекстные решения
В действительности маловероятно, что все ваши пользователи лучше всего отреагируют на одно лечение. В идеале ваша политика должна уметь различать разных пользователей и учиться принимать индивидуальные решения. Эта проблема называется проблемой c контекстного многорукого бандита. Внутри компании мы видим - в среднем - дополнительный 9% рост коэффициента конверсии за счет контекстной оптимизации.
Абстрагирование вашего пространства действия
Возможно, имеет смысл подумать о вашем сайте в виде модулей, чтобы опыт работы с перекрывающимся контентом мог поделиться знаниями. Учет этого совпадения может помочь ускорить обучение и создать значимую аналитическую обратную связь для ваших творческих групп.
Обработка отложенной обратной связи
На практике вознаграждения доступны не сразу, и мы должны подождать некоторое время, чтобы пользователи могли предоставить обратную связь (не говоря уже о задержке в конвейере данных). Понимание того, как эта задержка влияет на эффективность алгоритма, может помочь вам в разработке эффективных экспериментов.
