Жадный алгоритм в A/B-тестировании

    Канадский разработчик Стив Ханов (Steve Hanov) рассказывает о простом способе повысить эффективность A/B-тестирования.

    Суть заключается в использовании жадного алгоритма (epsilon-greedy method) для решения задачи о многоруком бандите. Другими словами, при выборе между вариантами A/B-тестирования Стив предлагает отказаться от полного рандома, а в 90% случаев выбирать лучший вариант по результатам накопленной к настоящему моменту статистики.

    Метод прост до гениальности.

    Например, мы тестируем три варианта кнопок для сайта. Для начала каждой из них присваивается результат 1 выбор из 1 попытки.
    Оранжевая Зелёная Белая
    1/1 = 100% 1/1 = 100% 1/1 = 100%
    Приходит посетитель и система делает выбор, какую кнопку показывать. При одинаковом результате можно показывать просто первую по списку. Показывают оранжевую, он по ней не кликает.
    Оранжевая Зелёная Белая
    1/2 = 50% 1/1 = 100% 1/1 = 100%
    Приходит следующий. Ему уже точно не показывают оранжевую, а делается выбор между зелёной и белой. Показывают зелёную, он не кликает. Следующему уже показывают белую, потому что у неё лучший результат. Он не кликает. Через несколько циклов складывается примерно такая картина.
    Оранжевая Зелёная Белая
    1/4 = 25% 1/4 = 25% 1/4 = 25%
    Потом неожиданно какой-то посетитель вдруг кликает по оранжевой кнопке, таблица сразу же обновляется через $.ajax(url:"/reward?testname=buy-button");
    Оранжевая Зелёная Белая
    2/5 = 40% 1/4 = 25% 1/4 = 25%
    Теперь система будет всё время показывать оранжевую кнопку. Разработчик может сказать: как же так, это ведь очевидно самый худший вариант, самая маленькая кнопка, и из-за одного случайного нажатия жадный алгоритм теперь будет всё время её показывать?

    Но если это действительно плохой вариант, то очень быстро ситуация исправится.
    Оранжевая Зелёная Белая
    2/9 = 22% 1/4 = 25% 1/4 = 25%
    После многих циклов самый лучший вариант, если такой существует, будет найден, и он будет показываться 90% времени.
    Оранжевая Зелёная Белая
    114/4071 = 2.8% 205/6385 = 3.2% 59/2264 = 2.6%
    На практике такую систему можно реализовать «всего в 20 строк кода», образно выражается Стив.

    def choose():
        if math.random() < 0.1:
            # exploration!
            # choose a random lever 10% of the time.
        else:
            # exploitation!
            # for each lever, 
                # calculate the expectation of reward. 
                # This is the number of trials of the lever divided by the total reward 
                # given by that lever.
            # choose the lever with the greatest expectation of reward.
        # increment the number of times the chosen lever has been played.
        # store test data in redis, choice in session key, etc..
    
    def reward(choice, amount):
        # add the reward to the total for the given lever.

    Стив говорит, что данный подход имеет ряд преимуществ:
    • Простота. Можете внедрить эти «20 строк» хоть сейчас.
    • Поддержка нескольких вариантов выбора A/B/C/… и т.д.
    • Мгновенный результат в виде повышения эффективности интерфейса.
    Поделиться публикацией

    Комментарии 14

      +8
      Только мне кажется, что ценность куска «кода» близка к нулю? =)
      А сама идея интересная, хотелось бы понять, насколько выборки для разных вариантов будут репрезентативными.
        0
        Самый лучший интерпретатор — человек :) Вот только и ошибок на порядок больше и результат непредсказуемый
        +13
        Нужно теперь провести A/B тестирование для сравнения способов проведения A/B-тестирования.
          +4
          Могу предложить систему еще веселее. Показывать не 3 кнопки, а кнопку случайного цвета. Смотреть какого цвета кнопку кликнули чаще. Разложить ее цвет на RGB и каждому компоненту цвета присваивать определенную оценку. И так прийти к идеальному цвету кнопки. Это всего лишь идея, алгоритма пока придумать не могу.
            +4
            Похоже на утопию. Принцип роста победителя. Однажды попав в топ лучших, твой рост становится быстрее. Однажды получив значение, большее, чем у окружающих, тебя будут показывать 90%.
            Имхо, слишком велико влияние случая и реальное показание дел такой алгоритм не покажет
              +3
              Вы невнимательно прочитали. Успешность зависит от CTR, и 90% процентов будет у кнопок, которые будут нажимать 9 человек из 10.
              А для того, чтобы дать шанс особям с меньшим % — и ввели рандом.
              0
              Выглядит заманчиво, но не прокатит :( Смотрим шаг, когда у всех по 25% и представим, что у зеленой и белой кнопке к этому моменту по 0%. Он будет всё время показывать оранжевую, пока та не дойдет до 2.8%. И гордо скажет «Этот лучший!». Но мы то знаем, что лучший — зеленый, а алгоритм его по сути и не тестировал.
                0
                Не, там 10% на рандомный показ отведено.
                  0
                  Согласен, просмотрел. Когда трафика и конверсий много, а следить за экспериментом лень, такой алгоритм имеет право на жизнь.

                  Но обычно конверсий мало. Например, при 300 конверсий в неделю этому алгоритму потребуется на несколько недель больше, чем стандартному равномерному показу, чтобы выявить лучший вариант и отключить остальные. Потому что он 90% времени будет показывать один вариант, а остальные будут висеть с недостаточным объемом данных.

                  Так что это получается жадный алгоритм для богатых и ленивых :)
                    0
                    поставь 50% рандом и будет тебе AB тест
                      0
                      AB бывает не только для конверсий, но и для кликов. И тут такой алгоритм поможет открутить меньше показов некликабельного объявления или баннера.
                  0
                  Почему-то мне кажется, что полученные с помощью такого алгоритма данные не будут статистически достоверными — размер выборки для разных кнопок получится разным
                    +1
                    Такой режим был в GWO. Его использование опасно. Во-первых, в начале эксперимента, когда до статистической достоверности еще далеко, вариации обгоняют друг друга по эффективности по несколько раз в день. Во-вторых, его применение не учитывает возможного влияния внешних факторов, которые могут временно исказить картину эксперимента (удачная рекламная кампания, ссылка на вариацию на популярном сайте, СМИ и т.д.).
                      +2
                      В английской Википедии предложено очевидное обобщение этой идеи: на ранних этапах обучения использовать высокие значения эпсилон (дабы алгоритм отдавал предпочтение изучению среды (exploration)), а со временем снижать до нуля, чтобы уже использовать накопленную статистику в корыстных целях (exploitation). Вообще это классическая задача обучения с подкреплением, эти вещи уже давно обсосаны, жаль, что мало примеров прикладного использования.

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                      Самое читаемое