Перевод вот этой статьи от Жёлтого Веба 

Такая хреново работающая штука, как A/B тестирование, используется слишком часто. Она дефективна по определению: разделите пользователей на две группы. Покажите группе А старый-проверенный сайт. Покажите группе В новый охеренный дизайн с большими кнопками и слегка отредактированным текстом. Через какое-то время чекните стату и посмотрите, какая группа чаще нажимала на кнопку «Заказать». Звучит вроде неплохо, да? Но проблема прямо перед вами. Это та же дилемма, что и у разработчиков новых лекарств. Во время тестов вы даёте только половине пациентов спасительное средство. Вторые же получают плацебо. Даже если ваше чудо-средство работает, то пациентов из группы В вы всё равно потеряли. Эта жертва приносится ради того, чтобы получить данные. Но можно всё сделать по-другому!

В последние годы сотни лучших умов во всю трудились, но не для того, чтобы вылечить рак. Вместо этого они оттачивали алгоритмы, которые заставляют вас чаще кликать по рекламным баннерам. И это работает. И Гугл и Майкрософт фокусируются на использовании большего кол-ва информации о пользователях, чтобы предугадать, что им показывать. Странно, но в мейнстримовых сервисах сейчас (прим. перев.: на 2012 год) нет ничего лучше А/В тестов, но я надеюсь исправить эту ситуацию путём повышения осведомлённости о более эффективных техниках.

Используя 20 строк простого кода, которые вы можете написать прямо сегодня, вы всегда сможете получать результаты лучше, чем при обычном А/В тестировании, иногда в 2-3 раза лучше! У этого метода есть несколько преимуществ:

• Вы можете тестировать больше двух вариантов сразу же. A, B, C, D, E, F, G и т.д.
• Новые варианты могут быть добавлены или убраны в любое время.

А одна из наиболее привлекательных штук — это то, что вы можете настроить всё один раз и забыть об этом! Если вам дорого ваше время, то вам тупо некогда заходить и смотреть, как там ведёт себя тот или иной вариант, и выбирать лучший. Просто позвольте алгоритму работать. Эти 20 строк кода быстро и автоматически находят лучший вариант и используют его до тех пор, пока он не перестанет быть лучшим.

Задача о многоруких бандитах

Картинка от Microsoft Research

Терминология задачи о многоруких бандитах пришла к нам из казино. Перед вами куча игровых автоматов, у каждого свой рычаг. Вы подозреваете, что у каких-то автоматов процент выигрыша больше, чем у других. Как определить, какой автомат лучше всех и получить наибольшее кол-во бабла за наименьшее кол-во попыток?

Как и во многих других техниках машинного обучения: самые простые стратегии трудно улучшить. Нет, более сложные техники нужно иметь в виду, но обычно они позволяют дополнительно выжать всего несколько сотых процента. Одна из стратегий, которая хорошо себя показала в практических задачах, — это эпсилон-жадный алгоритм. Суть в следующем: мы всегда следим за тем, сколько раз мы дёрнули рычаг и сколько профита от него получили. В 10% случаев мы выбираем рычаг рандомно, оставшиеся 90% раз мы выбираем рычаг с наибольшей вероятностью выигрыша.

def choose():

    if math.random() < 0.1:

        # исследуем!

        # выбираем рандомный рычаг в 10% случаев

    else:

        # эксплуатируем!

        # для каждого рычага, 

            # считаем вероятность выигрыша. 

            # =кол-ву выигрышей делённому на кол-во попыток

            # т.е. на кол-во раз, которое мы "дёргали рычаг".

        # выбираем рычаг с наибольшим шансом выигрыша

    # увеличиваем число, отвечающее за то, сколько раз мы дёргали данный рычаг

    # сохраняем данные где-нибудь типа Redis

def reward(choice, amount):

    # добавляем награду к общему кол-ву награды для выбранного рычага

Почему это работает?

Допустим, мы выбираем цвет для кнопки «Купить сейчас». В наличии оранжевый, зелёный или белый. Изначально мы задаём всем трём вариантам одинаковый шанс выигрыша: один выигрыш из одной попытки, то есть 100%. Это не так важно, какие начальные значения мы зададим, алгоритм адаптируется. Итак, когда мы начинаем, наши стартовые данные выглядят так:

Затем к нам на сайт заходит пользователь, и мы должны показать ему нашу кнопку. Мы выбираем первую, с наибольшей вероятностью выигрыша. Алгоритм видит, что сейчас все они одинаковые, поэтому берёт первую: оранжевую. Но… пользователь не кликает на кнопку.

Затем приходит второй пользователь. Мы однозначно не покажем ему оранжевую кнопку, потому что у неё теперь только 50% вероятности сработать. Поэтому мы выбираем зелёную. Всё то же самое происходит ещё для нескольких визитов, и мы просто перебираем варианты, каждый раз обновляя наши данные.

Но вдруг кто-то кликает на оранжевую кнопку! Браузер отправляет Ajax запрос, и мы обновляем результирующую табличку:

Когда наш дизайнер видит это, он в задумчивости чешет голову: какого хуя??! Оранжевая кнопка — это же полный отстой! У неё маленький размер шрифта, зелёная же очевидно лучше! Всё пропало! «Жадный» алгоритм теперь всегда будет выбирать оранжевую!

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

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

А что насчёт рандомизации?

Мы не обсудили ту часть, которая касается рандомизации. Рандомный выбор рычага в 10% случаев заставляет алгоритм исследовать имеющиеся варианты. Это компромисс между поиском чего-то нового в надежде, что это новое сработает лучше, и использованием того, что уже работает хорошо. Есть несколько вариантов эпсилон-жадного алгоритма. В одном из них в начале алгоритм 100% времени занимается исследованием вариантов, и только после того, как у него накапливается достаточно данных, он переключается на эксплуатацию. В другом алгоритме вы можете постепенно снижать процент исследований с течением времени. Но эпсилон-жадный алгоритм, который я описал — это хороший баланс между простотой и производительностью. Исследование других алгоритмов таких как UCB, сэмплирование Томпсона и тех, что принимают во внимание контекст — это охуенно, но опционально, если вам нужно что-то, что просто работает.

Подожди-ка, так а почему же все это не используют?

Многим людям сложна для понимания статистика. Люди не доверяют тем вещам, которые они не понимают, особенно они не доверяют алгоритмам машинного обучения, даже если они простые. Мейнстримовые сервисы и инструменты не поддерживают эти алгоритмы потому что тогда им бы пришлось обучать ими пользоваться, обучать статистике — а это сложно! Также может быть несколько типовых возражений:

1. Показывая разные варианты с разной частотой, вы исказите результаты! (Нет, не исказите. У вас всегда есть рассчитанный CTR для каждого варианта).
2. Нет адаптации к изменениям! (Ваши посетители скорее всего не изменяются. Но если вы хотите запилить такую адаптацию, просто измените функцию reward и умножайте старое значение награды на какой-нибудь коэффициент (forgetting factor)).
3. Эта штука не вывезет изменения нескольких вещей, зависящих друг от друга, за раз! (Верно, но и А/В тесты тоже такую херню не вывезут).

От переводчика

Даже учитывая вышеприведённый абзац, я совершенно не понимаю, почему в профессиональных инструментах для арбитража трафика (в частности в трекерах) до сих пор не реализована возможность использовать подобные алгоритмы в работе. Ведь большая часть из них проста в написании и использовании, а выгода от внедрения очевидна и будет весьма ощутима в денежном эквиваленте как для соло-арбитражника, так и для команд любого масштаба.

Для интересующихся темой есть отличная книжка издательства O’Reilly, где с примерами разобрано несколько алгоритмов многоруких бандитов, вот её русскоязычный обзор.

Источник