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

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

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

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

Например, мы тестируем три варианта кнопок для сайта. Для начала каждой из них присваивается результат 1 выбор из 1 попытки.

Приходит посетитель и система делает выбор, какую кнопку показывать. При одинаковом результате можно показывать просто первую по списку. Показывают оранжевую, он по ней не кликает.

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

Потом неожиданно какой-то посетитель вдруг кликает по оранжевой кнопке, таблица сразу же обновляется через $.ajax(url:"/reward?testname=buy-button");

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

Но если это действительно плохой вариант, то очень быстро ситуация исправится.

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

На практике такую систему можно реализовать всего в 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