Cегодня хочу вам рассказать о популярном алгоритме который широко используется в рекомендательных системах - "Multi-armed bandits" или "Многорукие бандиты" на примере Spotify.
Его название произошло от названия игрального автомата, суть игры в который - дерганье за ручку. Только в нашем случае автоматов больше чем 1, у нас есть N попыток дернуть за ручку, а ручки это вовсе и не ручки, а конфигурации для предложения рекомендаций. Нужно за меньшее количество попыток исследовать ручки на прибыльность и получить эту самую максимальную прибыль.
В Spotify используется расширенная версия этого алгоритма - "Контекстуальные многорукие бандиты". Как следует из названия, они учитывают контекст - регион, последние понравившиеся треки, время суток и т.д. и так же дает предсказание в зависимости от контекста. Но прежде, давайте разберемся с основами😌
Существуют несколько видов стратегий игры Многоруких бандитов, например жадные, когда мы на каждом шаге дергаем за самую прибыльную ручку, вопрос лишь в том, как ее выбрать.
Для этого применяется epsilon-greedy стратегия, здесь мы выбираем случайную руку с вероятностью epsilon или лучшую руку с вероятностью 1-epsilon в зависимости от значения из распределения вероятностей. Лучшая ручка оказывается та, которая дает наибольший результат в среднем.
При таком подходе мы можем упустить ручки, которые на первых итерациях давали маленький выигрыш, но в перспективе имели бы больший выигрыш в среднем. На помощь нам приходит следующий алгоритм - Upper Confidence Bound (Алгоритм верхней границы доверительного интервала) который оптимистично полагает что неприбыльные ручки хороши в среднем, нужно лишь сделать нескольких попыток. Во время работы UCB мы считаем доверительный интервал - интервал, в котором лежит средняя награда для руки,после нескольких итераций и фокусируемся на той ручке, верхняя граница доверительного интервала которой больше остальных.
Но и выбирать по максимальному среднему вознаграждению тоже не всегда хорошая стратегия. Нам хотелось бы еще знать, а с какой вероятностью мы получим гарантированное вознаграждение от выбранной ручки? На помощь приходит семплирование Томпсона. В процессе работы этого алгоритма мы строим распределение вероятностей получить выигрыш от каждого автомата.
Интересно ли вам было заглядывать во внутренности работы алгоритмов, которые используют крупные компании? Делаем вторую часть с разбором статьи?😼
Статья от Spotify с математикой и описанием использования контекстуальных бандитов
Более подробно про семплирование Томпсона
Его название произошло от названия игрального автомата, суть игры в который - дерганье за ручку. Только в нашем случае автоматов больше чем 1, у нас есть N попыток дернуть за ручку, а ручки это вовсе и не ручки, а конфигурации для предложения рекомендаций. Нужно за меньшее количество попыток исследовать ручки на прибыльность и получить эту самую максимальную прибыль.
В Spotify используется расширенная версия этого алгоритма - "Контекстуальные многорукие бандиты". Как следует из названия, они учитывают контекст - регион, последние понравившиеся треки, время суток и т.д. и так же дает предсказание в зависимости от контекста. Но прежде, давайте разберемся с основами😌
Существуют несколько видов стратегий игры Многоруких бандитов, например жадные, когда мы на каждом шаге дергаем за самую прибыльную ручку, вопрос лишь в том, как ее выбрать.
Для этого применяется epsilon-greedy стратегия, здесь мы выбираем случайную руку с вероятностью epsilon или лучшую руку с вероятностью 1-epsilon в зависимости от значения из распределения вероятностей. Лучшая ручка оказывается та, которая дает наибольший результат в среднем.
При таком подходе мы можем упустить ручки, которые на первых итерациях давали маленький выигрыш, но в перспективе имели бы больший выигрыш в среднем. На помощь нам приходит следующий алгоритм - Upper Confidence Bound (Алгоритм верхней границы доверительного интервала) который оптимистично полагает что неприбыльные ручки хороши в среднем, нужно лишь сделать нескольких попыток. Во время работы UCB мы считаем доверительный интервал - интервал, в котором лежит средняя награда для руки,после нескольких итераций и фокусируемся на той ручке, верхняя граница доверительного интервала которой больше остальных.
Но и выбирать по максимальному среднему вознаграждению тоже не всегда хорошая стратегия. Нам хотелось бы еще знать, а с какой вероятностью мы получим гарантированное вознаграждение от выбранной ручки? На помощь приходит семплирование Томпсона. В процессе работы этого алгоритма мы строим распределение вероятностей получить выигрыш от каждого автомата.
Интересно ли вам было заглядывать во внутренности работы алгоритмов, которые используют крупные компании? Делаем вторую часть с разбором статьи?😼
Статья от Spotify с математикой и описанием использования контекстуальных бандитов
Более подробно про семплирование Томпсона