Каждый, кто делал покупки на Amazon, слушал музыку на Spotify или искал достойный просмотра сериал на Netflix, сталкивался с персонализированными рекомендациями. Компании используют рекомендательные системы для увеличения вовлеченности клиентов и роста доходов. Эти алгоритмы принимают на входе метаданные о пользователе, продукте и контексте и создают персонализированный динамический контент на выходе с помощью методов коллаборативной или фильтрации по содержанию.
Качество рекомендательной системы часто измеряется с помощью экспериментов A/B-тестирования. Однако A/B-тестирование традиционно используется для измерения коэффициентов конверсии в статичных вариантах пользовательского интерфейса (например, синяя ссылка в сравнении с зеленой). Именно это натолкнуло меня на мысль об исследовании многоруких бандитов в качестве альтернативы A/B-тестированию в области рекомендательных систем.
Для начала мы рассмотрим классический мысленный эксперимент "многорукий бандит". Затем последует дискуссия о контекстном многоруком бандите с помощью формального определения и примера. Наконец, мы проведем сравнение традиционных экспериментов A/B-тестирования с многоруким бандитом.
Проблема многорукого бандита
Решение задачи с использованием многорукого бандита — это пример обучения с подкреплением, взятый из классической Байесовской вероятности. Это гипотетический эксперимент, в котором азартный игрок получает игровой автомат с несколькими рычагами, каждый из которых имеет свое неизвестное распределение вероятности. Задача состоит в том, чтобы последовательно вытягивать рычаги один за другим, собирая информацию, для максимизации общей выплаты в долгосрочной перспективе.
Более формальное описание предполагает, что вознаграждение происходит из вероятностного распределения ƒa(y|θ), где a обозначает предпринятое действие (или сыгравшую руку [рычаг]), y — наблюдаемое вознаграждение, а θ — набор неизвестных параметров, которые должны быть изучены путем экспериментов [6]. Нетривиальность задачи о многоруком бандите заключается в том, что мы (агент) не можем получить доступ к истинным распределениям вероятностей бандита — все обучение осуществляется методом проб и ошибок и оценки значений [7]. Это известный компромисс между разведкой и эксплуатацией, т.е. зарабатывай, пока учишься.
Проблема контекстного бандита
Проблема контекстного бандита — это обобщение многорукого бандита, которое расширяет модель, ставя действия в зависимость от состояния окружающей среды [3]. В отличие от классического многорукого бандита, здесь рассматривается проблема определения наиболее подходящего контента в оптимальное время для отдельных пользователей [2]. Контекстная информация может быть использована для группировки пользователей по общим признакам с помощью методов классификации или кластеризации с предположением, что пользователи, принадлежащие к одному кластеру, имеют сходное поведение, в то время как пользователи, принадлежащие к разным кластерам, характеризуются существенно отличающимся поведением [1].
Ниже приводится формальное определение контекстных многоруких бандитов:
Источник: http://www.hongliangjie.com/2014/04/14/unbiased-offline-evaluation/
Формально, мы определяем через A = {1,2,•••, K}, множество действий, контекстный вектор xt ∊ X, вектор вознаграждения rt = (rt,1,•••, rt,k}, где каждый rt,a ∊ [0,1] и политика π : X -> A. Контекстный бандит снова и снова (цикл за циклом) описывает взаимодействие между обучающимся и окружающей средой. В каждом цикле t задача может быть разбита на
следующие шаги:
Окружение выбирает (xt, rt) из некоторого неизвестного распределения D. Обучающемуся сообщается только xt, а вознаграждение не сообщается.
После того, как обучаемый фиксирует xt, далее он использует некоторую политику π для выбора действия a ∊ A, и в результате получает соответствующее вознаграждение rt,a.
(Необязательно) Политика π пересматривается с учетом данных, собранных за этот цикл.
Здесь мы определяем, что π параметризуется неизвестным параметром θ. В идеале, мы хотели бы выбрать политику, максимизирующую ожидаемое вознаграждение: arg max π Ex,r~D[rπ(x;θ]
Распространенным примером контекстного бандита в реальном мире является система рекомендаций новостей. Учитывая набор представленных новостных статей, вознаграждение зависит от поведения пользователя при переходе по ссылке. Если пользователь кликает на статью, то он получает вознаграждение, равное 1, и 0 в противном случае [2]. Кликабельность (Click-through-rate, CRT) используется для определения выбора и размещения рекламы в приложении, рекомендующем новости.
Теперь предположим, что вознаграждение определяется по CTR в сочетании с метаданными о пользователе (например, возраст и пол), поэтому рекомендации могут быть еще более персонализированы. Возьмем, к примеру, 65-летнюю женщину и 18-летнего юношу, которые читают новостные статьи со своего мобильного устройства. Рекомендации для этих двух пользователей должны отражать их отличительные особенности. Не имеет смысла показывать 18-летнему мужчине рекламу пенсионных планов или магазинов одежды для зрелых женщин (например, Talbots [известный в США производитель женской одежды, обуви и аксессуаров]).
Контекстная информация может также включать географическое местоположение, время суток, день недели и время года. Предположим, метаданные о географическом местоположении 18-летнего юноши доступны через его мобильное устройство. Он находится в непосредственной близости от главного кампуса Техасского университета в Остине и проявил интерес к магазинам для скейтбордистов и серферов посредством своих кликов. Имея такую контекстную информацию о пользователе, приложение должно показывать рекламу магазинов скейтов и серфинга в пределах его текущего географического положения (например, Tyler's). Если это начало семестра, скажем, в сентябре или январе, этому пользователя должна быть сгенерирована реклама магазинов учебников для колледжей (например, University Coop), поскольку высока вероятность того, что он является студентом колледжа и покупает учебники.
A/B-тестирование и многорукие бандиты
В большинстве современных интернет-компаний везде, где есть метрика, которую можно измерить (например, время, проведенное на странице, количество кликов, конверсия в продаже), почти всегда за кулисами проводятся рандомизированные испытания, целью которых является определение альтернативного дизайна сайта, позволяющего улучшить его по сравнению со стандартным [8]. Этот процесс и методологию часто называют A/B-тестированием. A/B-тестирование — это форма статистической проверки гипотез с двумя заданными выборками A и B, первая из которых является контрольной, а вторая — вариантом. Учитывая конфигурацию по умолчанию и несколько альтернатив (например, цветовые схемы сайта), стандартная практика заключается в том, чтобы направить небольшое количество исследовательского потока на рандомизированное тестирование этих альтернатив и записать необходимую метрику для каждой из них [8].
Многорукий бандит — это альтернатива A/B-тестированию. Когда необходимо отыскать разницу, многорукий бандит значительно эффективнее находит наилучшую руку, чем традиционные статистические эксперименты, и его преимущество увеличивается по мере роста числа рук [6]. Интуитивно понятно, что нам нужно распределить больше трафика на новый контент, чтобы быстрее узнать его ценность, и меньше — для отслеживания временных изменений существующего [2]. Ниже приводится обсуждение преимуществ экспериментов с многоруким бандитом от Стивена Л. Скотта (Steven L. Scott), старшего экономического аналитика Google Analytics:
Эксперименты на основе многоруких бандитов обычно намного эффективнее, чем "классические" A-B эксперименты, основанные на проверке статистических гипотез. Они точно так же статистически достоверны, а в большинстве случаев могут давать ответы гораздо быстрее. Они более эффективны, потому что продвигаются к выигрышным вариациям поступательно, а не заставляют вас ждать "окончательного ответа" в конце эксперимента. Они работают быстрее, потому что пробы, которые могли бы отправиться к явно уступающим альтернативам, назначаются для потенциальных победителей. Дополнительные данные, собранные по высокоэффективным вариантам, помогают быстрее отделить "хорошие" руки от "лучших".
По сути, бандиты делают эксперименты более эффективными, так что вы можете опробовать большее их количество. Вы также можете выделить большую долю трафика на эксперименты, поскольку трафик будет автоматически направляться на страницы с лучшими показателями.
Теперь давайте непосредственно сравним эти конкурирующие методы тестирования:
Как видно из приведенного графика, A/B-тестирование никак не адаптируется на протяжении всех этапов эксперимента, поскольку фазы исследования и эксплуатации статичны и различны, в то время как многорукий бандит адаптируется за счет одновременного исследования и эксплуатации. Кроме этого, в многоруком бандите меньше времени и ресурсов выделяется на более слабые руки/фрагменты. Вместо этого трафик последовательно распределяется между наиболее оптимальными фрагментами в ходе всего эксперимента. Одним из важных преимуществ тестирования бандитами является то, что они сокращают "сожаление", являющееся по сути потерей конверсии, которую вы получаете, исследуя потенциально худший вариант в тесте [5].
Для получения дополнительной информации о многоруких бандитах см. следующие ссылки:
Эффективный алгоритм бандита для многовариантной оптимизации в реальном времени. Как Amazon адаптировал подход "многорукого бандита" с помощью выборки Томпсона, чтобы увеличить количество покупок на 21% за одну неделю.
Практический искусственный интеллект для бизнеса: Алгоритмы бандита. Фантастическая презентация Макса Пагельса (Max Pagels) об алгоритмах бандита и их практическом применении в бизнесе. Он представляет многоруких бандитов с помощью четких и лаконичных объяснений, которые легче усвоить, чем сложные аргументы, встречающиеся в научных трудах.
Интерактивная коллаборативная фильтрация в режиме онлайн с использованием многорукого бандита с зависимыми руками. Обсуждаются проблемы интерактивной коллаборативной фильтрации онлайн с учетом зависимостей между элементами.
Многорукие бандиты с изменяющимся во времени контекстом. Исследование проблемы контекстного многорукого бандита с изменяющимся во времени контекстом, когда функция отображения вознаграждения меняется со временем.
Ссылки
[1] Li, Karatzoglou, and Gentile. Коллаборативная фильтрация бандитов.
[2] Li, Langform, and Schapire. Метод контекстного бандита в персонализированной рекомендации новостных статей.
[3] Surmenok, Paul. Контекстные бандиты и обучение с подкреплением — с точки зрения науки о данных.
[4] Scott, Steven. Эксперименты с многорукими бандитами.
[5] Birkett, Alex. Основы A/B-тестирования: От новичка до профессионала в одной статье.
[6] Scott, Steven. Многорукие бандиты в экономике онлайн-услуг.
[7] Wong, Anson. Решение проблемы многорукого бандита.
[8] Yang, Ramdas, Jamieson, and Wainwright. Фреймворк для тестирования многорукого бандита, А/В (Multi-A(rmed)/B(andit)) с онлайн контролем FDR [False discovery rate. Ожидаемая доля ложных отклонений].
24 мая в OTUS пройдет открытый урок «Рекомендательная система: как рекомендовать визуально похожие товары». На этом занятии вы узнаете, как сделать векторное представление изображений. Также мы поработаем с нейросетями компьютерного зрения, поищем похожие по фото объекты — украшения, предметы одежды. Обсудим, как это технически организовать для целей рекомендательной системы.
В результате вы узнаете, как работать с глубокими нейросетями компьютерного зрения, как готовить изображения для обработки, как сделать рекомендательную систему на основе похожих изображений.