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

в 13:18, , рубрики: Алгоритмы, задача о многоруком бандите, интерфейсы, статистика, тестирование

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

Суть заключается в использовании жадного алгоритма для решения задачи о многоруком бандите. Другими словами, при выборе между вариантами 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


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js