Pull to refresh

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

Reading time 2 min
Views 7.2K
Канадский разработчик Стив Ханов (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/… и т.д.
  • Мгновенный результат в виде повышения эффективности интерфейса.
Tags:
Hubs:
+28
Comments 14
Comments Comments 14

Articles