Байесовское АВ-тестирование. Часть 1

Дилемма исследования и использования

Здравствуйте и вновь добро пожаловать на занятия по теме «Байесовское машинное обучение на языке Python, часть 1».

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

Мы не будем сразу переходить к байесовским методам, а сначала обсудим недостатки использования традиционного А/В-тестирования.

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

Дляиллюстрации этого момента мы воспользуемся более привычным для посвящённойбайесовскому А/В-тестированию литературе примером, который называется задачей многорукогобандита. Суть её в следующем. Мы находимся в казино и играем в игровые автоматы– отсюда и термина «рука», а «бандитами» они называются потому, что они воруютнаши деньги. Не все игровые автоматы одинаковы – один может дать вам выигрыш в30% случаев, второй – в 20% случаев, третий – в 10% случаев. Эта проблемааналогична показателям кликабельности и перехода: мы запускаем А/В-тестированиеи в конце эксперимента узнаем, является ли одна «рука» значимо лучше других.

Воттолько возникает вопрос: применимо ли это в реальной жизни? Даже после такоймалой выборки, как три игры на каждом автомате, если одна «рука» даёт выигрыш втрёх случаях из трёх, а вторая рука даёт нуль выигрышей из трёх, мы, надополагать, захотим просто чаще играть с первой «рукой». Другими словами, мызахотим приспособиться к уже собранным данным. Имейте в виду, что трёх игр,вероятно, недостаточно для получения статистической значимости, и всё же мычувствуем необходимость верить в то, что первая «рука» лучше.

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

Эта задача имеет своё название – дилемма исследования и использования. Вопрос состоит в следующем: если мы получили три выигрыша из трёх у первого бандита и нуль выигрышей из трёх у второго, то что следует делать? Следует ли использовать первого бандита или же следует продолжить исследование, чтобы собрать больше данных и быть более уверенным в показателе выигрышей для каждого из бандитов? В следующих лекциях мы рассмотрим несколько решений этой задачи. Хотя все они адаптивные, но не все из них байесовские. Байесовский метод мы рассмотрим последним, и это поможет вам понять и оценить элегантность решения.

Эпсилон-жадное решение

Рассмотри один из методов решения дилеммы исследования и использования, называемый эпсилон-жадным алгоритмом. Кстати, этот алгоритм также применим и в обучении с подкреплением.
Работает он следующим образом. Пусть у нас есть система, показывающая два рекламных объявления. Вряд ли мы будем запускать полное А/В-тестирование, слепо показывая каждое из объявлений равное количество раз. Скорее мы попробуем приспособиться к уже собранным данным, и если реклама А работает лучше, просто будем показывать её чаще.
Заметьте, что даже с такой адаптивной системой мы всё равно после этого можем провести традиционное А/В-тестирование. Напомню, что таблица сопряжённости, создаваемая для критерия хи-квадрат, не требует одинакового размера каждой из групп, а потому неважно, если реклама А будет показываться чаще рекламы В или наоборот. Единственное, что тут меняется, – это алгоритм, показывающий объявления. В традиционном А/В-тестировании он не является адаптивным, а просто показывает каждое из объявлений заранее определённым образом. Эпсилон-жадный же алгоритм приспосабливается в зависимости от эффективности рекламных объявлений А и В.
Итак, как же он работает? Сам алгоритм проще, чем его название. Мы выбираем небольшое число ε между 0 и 1 и считаем его вероятностью исследования. Псевдокод алгоритма будет примерно таким:

eps = 0.1
while True:
r = rand()
if r < eps:
# исследование
показать случайную рекламу
else:
# использование
показать лучшую рекламу (определяется как число кликов / число показов)

В теле цикла мы генерируем случайное число, и если оно меньше ε, то мы исследуем, в противном случае используем, показывая лучшую рекламу, определённую по текущему показателю кликабельности.
Как видите, всё довольно просто. Но давайте немного проанализируем этот алгоритм. Одна из проблем заключается в том, что он всегда делает одно и то же. Даже если реклама А значимо лучше рекламы В, он всё равно будет иногда выбирать В независимо от того, насколько существенно различие. Предположим, у нас есть только два рекламных объявления А и В и мы уже точно выяснили, что А лучше В, какое вознаграждение мы получим? Пусть клик равен единице, а отсутствие клика – нулю. Тогда после N показов ожидаемое вознаграждение будет равно N(1 – ε/2). Другими словами, если ε = 0,1, то мы получим 0,95N вместо N. В следующих лекциях мы увидим, как можно улучшить алгоритм, но помните, что даже он всё равно лучше, чем проведение традиционного А/В-тестирования без какой-либо адаптации.

UCB1

Выше мы рассмотрели простой и интуитивно понятный метод нахождения баланса в дилемме исследования и использования. Напомню, мы выбираем небольшое число, представляющее вероятность исследования, при котором выбирается случайное рекламное объявление (или случайный игровой автомат). В противном случае мы выбираем то, что считаем на данный момент лучшим, будь то реклама или игровой автомат. В долговременной перспективе ожидаемая отдача составит 95% от максимальной, если вероятность исследования составляет 10%. В этой лекции мы посмотрим, можно ли его улучшить.

Напомню наше обсуждение доверительных интервалов. Они позволяют нам определить верхнюю и нижнюю границы, где, по нашему мнению, находится действительное значение. В этой лекции мы рассмотрим похожую идею, но будем использовать не границы доверительных интервалов, как ранее, а более жёсткую так называемую границу Чернова-Хоффдинга. Она гласит, что для любого ε > 0 (так что можно выбирать какое угодно ε) справедливо следующее неравенство вероятностей:

Оно симметрично, поэтому если мы пойдём в другом направлении, то получим такое же истинное неравенство:

Оно симметрично, поэтому если мы пойдём в другом направлении, то получим такое же истинное неравенство:

Обратитевнимание, что эта граница несколько отличается от рассмотренных нами ранеедоверительных интервалов. В частности, ранее имевшийся доверительный интервалдаёт нам конкретные числа, или, другими словами, ранее доверительный интервалуказывал на то, что вероятность того, что истинное значение параметра лежит внекотором диапазоне, равна 95%. Нынешнее же выражение утверждает, чтовероятность того, что истинное значение параметра лежит в этом диапазоне,больше некоторой функции от N. Чтобы получить знак «больше», достаточнообъединить и переставить два вышеуказанных выражения:

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

Возникает вопрос: и как это нам может помочь? Интуитивно понятно, что если у нас более жёсткая верхняя граница, то мы можем быть более уверены в максимально возможном показателе выигрышей любого из бандитов. Вновь-таки, пропуская множество математических выкладок, можно утверждать, что для любой «руки» j мы, по сути, выбираем ε согласно формуле

где N – общее количество сыгранных игр, а Nj – количествоигр, сыгранных с бандитом j.

Таким образом, алгоритм работает примерно так. Мы инициируем начальные значения N и Nj равными нулю для всех бандитов j, а затем в цикле находим argmax для оценки среднего значения плюс ε, формула которого наведена выше. Затем выбираем бандита с наивысшей верхней границей, играем с соответствующей «рукой» и обновляем оценку среднего значения этой «руки». После этого увеличиваем N и Nj на единицу:

где N – общее количество сыгранных игр, а Nj – количествоигр, сыгранных с бандитом j.

Таким образом, алгоритм работает примерно так. Мы инициируем начальные значения N и Nj равными нулю для всех бандитов j, а затем в цикле находим argmax для оценки среднего значения плюс ε, формула которого наведена выше. Затем выбираем бандита с наивысшей верхней границей, играем с соответствующей «рукой» и обновляем оценку среднего значения этой «руки». После этого увеличиваем N и Nj на единицу:

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

Инаконец, рассмотрим асимптотическое поведение величины ln(N)/N. Поскольку логарифм отN растёт медленнее, чемсамо N, эта величина вконечном итоге будет стремиться к нулю. Следовательно, в конце концовиспользоваться будет только оценка средних значений, когда N станет достаточновелико.

Как видите, с точки зрения кода этот алгоритм не более сложный, чем эпсилон-жадный. Тут возникает справедливый вопрос: а какими будут ожидаемые потери от данного алгоритма? Опять же, пропуская более сложные математические выкладки, можно показать, что потери пропорциональны ln(N). Сравните это с эпсилон-жадным алгоритмом, где потери пропорциональны N. Следовательно, в долгосрочной перспективе данный алгоритм будет работать намного лучше, нежели эпсилон-жадный, ещё и с тем преимуществом, что он такой же лёгкий в написании, хотя его теоретические основы чуть сложнее.

Априорное сопряжение

Сейчас давайте создадим математический фундамент для подготовки к байесовскому А/В-тестированию.

Ещёв предыдущей части я говорил о байесовской парадигме. Я утверждал, чточастотная парадигма – это когда при измерении параметров вроде среднегозначения или показателя кликабельности мы делаем точечные оценки. Мы суммируемвсе результаты, делим на N и получаем оценку. В этом уже заключалась проблема,поскольку не учитывалось, насколько мы уверены в таких оценках. Впрочем, было ирешение – мы могли использовать центральную предельную теорему, чтобы показать,что доверительные интервалы имеют приблизительно гауссово распределение, изчего можно было получить верхнюю и нижнюю границы 95-процентного доверительногоинтервала. Таким образом, при частотной парадигме вычисляется правдоподобие имаксимизируется относительно рассматриваемого параметра, в результате чего мыполучаем оценку максимального правдоподобия этого параметра:

Вбайесовской статистике мы также рассматриваем параметр как случайнуюпеременную, которая, следовательно, имеет своё распределение, а формараспределения показывает нам, насколько можно быть уверенным при любом значенииэтого параметра. Для этого, в частности, применяется теорема Байеса. Так,распределение параметра с учётом данных равен вероятности данных с учётомпараметра, умноженной на априорную вероятность параметра и делённой навероятность данных. Напомню, что знаменатель при этом рассматривается какконстанта нормализации, поскольку он не зависит от параметра θ:

Вбайесовской статистике мы также рассматриваем параметр как случайнуюпеременную, которая, следовательно, имеет своё распределение, а формараспределения показывает нам, насколько можно быть уверенным при любом значенииэтого параметра. Для этого, в частности, применяется теорема Байеса. Так,распределение параметра с учётом данных равен вероятности данных с учётомпараметра, умноженной на априорную вероятность параметра и делённой навероятность данных. Напомню, что знаменатель при этом рассматривается какконстанта нормализации, поскольку он не зависит от параметра θ:

где Z – константа нормализации.

Напомнютакже, что три ключевых элемента байесовского уравнения имеют свои имена:апостериорная вероятность P(θ|X), показывающая наши новые представленияо параметре после сбора данных, априорная вероятность P(θ), отражающая наши старые представления опараметре, и правдоподобие P(X|θ), которое показывает, насколько вероятнополучить собранные нами данные, исходя из старых представлений о параметре.

Выможете решить, что всё это очень просто – тут лишь умножение и деление. Но неспешите. Тут не умножаются и делятся числа – это всё распределениявероятностей. Напомню, в частности, что член внизу – это интеграл члена вверхупо всем значениям параметра. В общем случае этот интеграл найти либо оченьсложно, либо невозможно. Одним из решений тут может быть использование методоввзятия выборок вроде MCMC, но мы не будемрассматривать их в этом курсе, поскольку собираемся достичь куда болееэлегантного решения.

Ответомна нашу задачу является априорное сопряжение. Что это такое? Дело в том, чтодля определённых распределений правдоподобия и определённых распределенийаприорной вероятности решение уравнения Байеса показывает, что апостериорноераспределение будет иметь тот же тип распределения, что и априорное.

Рассмотримпример, чтобы проиллюстрировать это утверждение. Мы знаем, что нашеправдоподобие для показателя кликабельности подчиняется распределению Бернулли:

Мытакже знаем, что θ должна бытьпараметром в диапазоне от 0 до 1, поскольку это вероятность клика. Просмотревсписок распределений вероятностей, которые могут варьироваться в диапазоне от 0до 1, можно наткнуться на бета-распределение. В частности, плотностьраспределения вероятностей при этом равна

Мытакже знаем, что θ должна бытьпараметром в диапазоне от 0 до 1, поскольку это вероятность клика. Просмотревсписок распределений вероятностей, которые могут варьироваться в диапазоне от 0до 1, можно наткнуться на бета-распределение. В частности, плотностьраспределения вероятностей при этом равна

где B(a,b) – бета-функция,которая может быть определена через гамма-функцию:

Гамма-функцияже, в свою очередь, является обобщённой формой функции факториала, ноработающей с любыми действительными числами:

Гамма-функцияже, в свою очередь, является обобщённой формой функции факториала, ноработающей с любыми действительными числами:

Теперьобъединим правдоподобие и априорную вероятность, используя теорему Байеса ипосмотрим, получится ли решить уравнение для апостериорной вероятности:

Тутмы используем знак пропорциональности, поскольку не учитываем константунормализации.

Далеемы объединяем подобные члены, и оказывается, что получается та же форма, что ипри бета-распределении:

Напомню,что константа нормализации тут не играет никакой роли, поскольку не зависит от θ.

Кромепрочего, можем видеть, что P(θ|X) также имеет бета-распределение, толькос параметрами a и b, которые могут быть определены с точкизрения собранных нами значений x:

Или,в понятиях нашей задачи о показателе кликабельности,

Любопытнойособенностью бета-распределения является то обстоятельство, что его среднеезначение равно

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

Другоелюбопытное обстоятельство возникает при анализе дисперсии бета-распределения:

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

Другоелюбопытное обстоятельство возникает при анализе дисперсии бета-распределения:

Итак,что здесь любопытного? Известно, что чем больше мы будет собирать данных, тем большими будут становиться А и В.Следовательно, по мере увеличения А и В дисперсия становится меньше. Из этогоавтоматически следует то же поведение, которое мы наблюдали в случаеприближённых доверительных интервалов, – дисперсия уменьшается по мереувеличения количества данных.

Возникаетвопрос: как выбрать исходные a и b? Получается, что если выбрать значения a = 1 и b = 1, тобета-распределение превращается равномерное. Это понятно, ведь если мы ничегоне знаем об априорной вероятности нашего показателя кликабельности, то всевозможные значения этого показателя равновероятны. Это называетсянеинформативной априорной вероятностью.

Важноеобстоятельство: по мере сбора всё большего количества данных влияние априорнойвероятности параметров становится пренебрежимо малой.

Итак, подведём итог изученному. Прежде всего мы резюмировали, что значит частотная парадигма, а что – байесовская, когда рассматривали измеряемый параметр в качестве случайной переменной и присваивали ему распределение вероятностей. Мы определили набор распределений вероятностей (Бернулли и бета) так, что, объединив их и использовав теорему Байеса, получили, что априорная и апостериорная вероятности имеют один и тот же тип распределения вероятностей, назвав это априорным сопряжением. Если вам интересно, то в Википедии есть статья об априорном сопряжении, в которой перечислены все пары правдоподобие — априорная вероятность, встречающиеся вместе. Я обнаружил, что это очень полезная ссылка при занятиях байесовской статистикой. И наконец, мы показали, что бета-распределение имеет то же среднее значение, что и максимальное правдоподобие показателя кликабельности, и что дисперсия автоматически уменьшается по мере увеличения собранных данных, как и в случае частотного доверительного интервала.

Байесовское А/В-тестирование

В завершение мы наконец-то рассмотрим алгоритм байесовского А/В-тестирования.

Впредыдущей лекции мы узнали, как получить распределение вероятностей нашегопоказателя кликабельности с учётом данных. Теперь перед нами возникает двавопроса: 1) как использовать эти распределения для решения дилеммы исследованияи использования, и 2) как это сделать лучше, чем эпсилон-жадный алгоритм и UCB1?

Ответомявляется выборка. Всякий раз, когда мы генерируем случайные числа, мы должнызадаться вопросом: «Из какого распределения я делаю выборку?» Как правило,большинство языков программирования даёт нам функцию rand(),которая возвращает равномерное распределённое число между 0 и 1. Библиотека Numpy также предоставляет функцию randn(), позволяющую сделать выборку из гауссовогораспределения со средним значением 0 и дисперсией 1. Неудивительно, что Scipy позволяет делать выборку из всех имеющихся в этойбиблиотеке распределений, и бета-распределение – одно из них. Поэтому вопростеперь звучит так: «Как выборка из бета-распределения может нам помочь?»

Рассмотримнесколько ситуаций. Первая из них – это когда мы уже потратили много времени наисследование, а потому имеем довольно ярко выраженные оценки наших показателейкликабельности с малой дисперсией. Тогда если мы будем выбирать по числу изобоих наших бета-распределений, то с большой вероятностью будем ожидать, чтораспределение с более высоким показателем кликабельность даст нам большееслучайное число. С точки зрения байесовской задачи о бандитах мы должны игратьс бандитом, который даст нам большее случайное число. Обратите внимание, чтохудший бандит всё ещё может дать нам большее случайное число, но по мере того,как дисперсии будут становиться всё тоньше и тоньше, это будет становиться всёболее маловероятным.

Теперьрассмотрим вторую ситуацию. Пусть один из бандитов использовался очень часто, апотому мы весьма уверены в его показателе кликабельности, тогда как в отношениивторого бандита мы собрали куда меньше данных. Выборка и выбор максимумапомогут нам и тут, поскольку в этой ситуации бандит с более «толстой»дисперсией имеет куда большие шансыдать нам большее случайное число. Как видите, сами распределения показываютнам, сколько исследовать и сколько использовать. Большее количество данных даётнам меньшую дисперсию, которая, в свою очередь, даёт нам меньше исследования, аменьшее количество данных даёт нам большуюдисперсию, которая даёт нам большее исследование.

Ещёраз рассмотрим эту же ситуацию. Заметьте, что резко выраженный показателькликабельности весьма высок. Если разделить более «толстое» распределение полинии более высокого показателя кликабельности, то можно видеть, что болеевероятно выбрать меньшее число, нежели большее. Что это значит? Это значит, чтовыраженный показатель кликабельности бандита уже достаточно хорош, поэтомуследует потратить больше времени на его использование и меньше времени – наисследование.

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

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

Ну,а теперь соберём всё вместе при помощи псевдокода. В теле цикла мы делаемслучайную выборку из всех бандитов, выбираем того из них, кто даёт наммаксимум, играем с ним и обновляем его a и b:

while True:

    сделать случайную выборку из всех бандитовпри текущем Beta(aj, bj)

    j* = бандит,дающий нам максимум

    x =  игра с бандитом j*

    aj* = aj* + x

    bj* = bj* + 1 – x

Обратите внимание, что алгоритм полностью независим от количества бандитов, – это то, что нуждалось в коррекции при частотном А/В-тестировании. Далее мы посмотрим, как это можно сделать в коде и понаблюдаем за развитием бета-распределений с течением времени.

Продолжим изучение байесовского АВ-тестирования в следующей статье.

Понравилась статья? Поделить с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: