- PVSM.RU - https://www.pvsm.ru -

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

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

Суть заключается в использовании жадного алгоритма для решения задачи о многоруком бандите [2]. Другими словами, при выборе между вариантами 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/… и т.д.
  • Мгновенный результат в виде повышения эффективности интерфейса.

Автор: alizar


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/testirovanie/8680

Ссылки в тексте:

[1] простом способе повысить эффективность A/B-тестирования: http://stevehanov.ca/blog/index.php?id=132

[2] задачи о многоруком бандите: http://en.wikipedia.org/wiki/Multi-armed_bandit