Компания
97,55
рейтинг
7 февраля 2013 в 13:57

Разработка → Многорукие бандиты: введение и алгоритм UCB1 tutorial

Это первый пост из блога Surfingbird, который я выношу в общие хабы алгоритмов и искусственного интеллекта; честно говоря, раньше просто не догадался. Если интересно, заходите к нам, чтобы прочесть предыдущие тексты, – я не знаю, что произойдёт, если просто добавить новые хабы к постам несколькомесячной давности.

Краткое содержание предыдущих серий о рекомендательных системах:

В этот раз начинаем новую тему – о многоруких бандитах. Бандиты – это самая простая, но от этого только более важная постановка задачи в так называемом обучении с подкреплением



Мы всё время говорим, что то, что мы делаем, – это машинное обучение (machine learning). Однако задумайтесь: как вы на самом деле обучаетесь? Неужели мы с вами строим регрессию движения пальцев на основе наблюдений за машинистками для того, чтобы научиться слепой печати? Неужели ребёнок, чтобы научиться ходить, сначала собирает и обобщает коллекцию примеров прямохождения родителей? На самом деле, конечно, нет: в таких случаях мы просто пробуем что-нибудь сделать, смотрим, получилось ли, а затем пытаемся (обычно бессознательно) скорректировать своё поведение на основе полученного результата.

Такая постановка задачи называется обучением с подкреплением: есть агент, который действует в какой-то среде; агент пытается что-то делать, а среда в ответ на его действия выдаёт агенту плюшки или, наоборот, бьёт током. Агент старается получить плюшек побольше, а током – пореже. В общем, типичная мышка в лабиринте.

Сегодня, однако, мы поговорим о мышке, которая попала даже не в лабиринт, а в самый обычный skinner box – давайте предположим, что состояние среды/агента от действия к действию не изменяется. Иначе говоря, у агента есть некоторый набор возможных действий, агент выбирает одно из них, получает за это некоторое вознаграждение (которое является случайной величиной), а затем снова может выбирать из тех же действий. В машинном обучении такая постановка задачи получила название многоруких бандитов (multiarmed bandits): вы сидите в комнате перед несколькими игровыми автоматами и должны постараться выиграть как можно больше.


(картинка с сайта Microsoft Research)

Зачем это нужно в реальной жизни? К примеру, представьте себе, что вы – Yahoo! или, скажем, mail.ru. У вас есть домашняя страница, на которой бывают миллионы людей каждый день. Вы хотите размещать на ней ссылки так, чтобы на них кликали как можно чаще. Как выбрать те ссылки, которые дают максимальный CTR (click-through ratio)? Здесь каждый показ ссылки пользователю соответствует «дёрганию за ручку»; каждый клик – успех, положительное подкрепление от среды; не-клик – неудача. Задача алгоритма будет в том, чтобы как можно быстрее понять, что та или иная новость «горяча», и начать её показывать (да, это чуть модифицированная задача, в которой бандиты время от времени умирают и рождаются вновь).

Другой пример: представьте себе, что вы хотите протестировать какой-то набор изменений в интерфейсе своего сайта. Обычно это делается при помощи так называемого A/B testing – вы должны выбрать группу для эксперимента (по каждому изменению в отдельности), контрольную группу, для которой ничего не изменится, затем собрать статистику и оценить, значимо ли улучшение. Однако такая схема сама по себе не отвечает на главный вопрос – как долго надо собирать статистику? Здесь бандиты тоже могут придти на помощь, постановка задачи ведь в точности бандитская: показ того или иного варианта соответствует дёрганию за ручку, а действия пользователя определяют ответ окружающей среды (см., например, вот этот пост).

Однако вернёмся к постановке задачи. На первый взгляд кажется, что задача выбрать оптимальную ручку очень простая: нужно дёрнуть за каждую ручку по тысяче раз, а потом выбрать ручку с наибольшим средним. И действительно, такой алгоритм, скорее всего, сделает правильный выбор – но сколько он потеряет «денег» на субоптимальных ручках! Многих из этих потерь можно было бы избежать. Вообще, лучшая метрика для оценки качества «бандитского» алгоритма – это его потери (regret) по сравнению с оптимальным алгоритмом, т.е. ожидание разности дохода от стратегии «всегда дёргать за оптимальную ручку» и рассматриваемой стратегии.

В качестве примера я сразу приведу алгоритм с одними из самых лучших гарантий на эту самую меру потерь на обучение. Это алгоритм UCB1; сам алгоритм очень простой, доказательство его оптимальности, конечно, не такое простое, но в это мы углубляться не будем, а интересующихся я отсылаю к статье [Auer et al., 2002]; там же можно найти и более «продвинутую» версию с улучшенными константами.

  • Инициализация: дёрнуть за каждую ручку один раз.
  • Пока продолжается работа:
    • дёрнуть за ручку j, для которой максимальна величина
      image,
      где image – средний доход от ручки j, nj – то, сколько раз мы дёрнули за ручку j, а n – то, сколько раз мы дёргали за все ручки.


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

Реализация этого алгоритма на вашем любимом языке, понятное дело, никаких трудностей не представляет – нужно просто запоминать, сколько раз дёргали за каждую ручку. Главный пафос здесь в том, что хорошо работает такая простая эвристика: можно просто выбирать ручку с максимальным приоритетом и больше ни на что не обращать внимания. Это связано с так называемой теоремой Гиттинса: оказывается, что в достаточно общих предположениях выбор оптимальной стратегии в задаче о многоруких бандитах сводится к подсчёту независимых приоритетов для каждой ручки в отдельности. Правда, теорема Гиттинса сама по себе даёт только крайне сложный и медленный алгоритм вычисления этих приоритетов (так называемых индексов Гиттинса), и алгоритм UCB – это не просто частный случай общей теоремы, а отдельный результат.

В следующей серии мы продолжим рассматривать «бандитские» задачи и обобщим их до задач следования за трендами, когда доходы разных «ручек» могут изменяться во времени, и наша задача – быстро понимать, что и где изменилось.
Автор: @snikolenko
Surfingbird
рейтинг 97,55

Комментарии (13)

  • +1
    Я по названию статьи и картинке решил, что расскажите о алгоритме работы именно игровых автоматов…
    • +1
      А я подумал, что расскажут, как в них выигрывать =(
      • +2
        Выиграть в них можно только приобретя и выставив для игры. И не забыть подкручивать вероятность выпадения выигрыша — то вперед, то назад, чтобы взбадривать и завлекать бонвиванов.

        За статью автору спасибо, хоть что-то расширяющее примитивное A/B тестирование, тема нигде не раскрыта, дал толчок для дальнейшего чтения.
        • 0
          В цивилизованных странах это называется tampering и ведет к потере лицензии. Нельзя просто взять и поменять процент выплаты.
  • –1
    Жду статью, где распишут принцип работы и «намахивания» игроков
  • 0
    А когда следует остановиться в UCB1?
    • 0
      Так не надо останавливаться. :) Идёт поток, и пусть идёт. Со временем, естественно, наступит сходимость и выбор ручки будет меняться всё реже и реже.
      • 0
        Ну так-то да. Тогда переформулирую. Пусть дано n автоматов. В «тривиальной» стратегии мы на очередной итерации дёргаем каждый автомат по одному разу, и при некотором m1 таких кругов из дёрганий наступает сходимость. Теперь в UCB1 делаем некоторое количество шагов m2, при которых также наблюдается примерно того же порядка сходимость. Как соотносятся m1 и m2, можно ли сказать?
        • 0
          Можно, но это зависит от соотношений между ручками. Собственно, теорема Auer et al. заключается в том, что regret получится логарифмический, причём порядок величины там \sum_{неоптимальные ручки} ln(n) / Delta_i, где Delta_i — разница в ожиданиях выигрышей между i-й ручкой и оптимальной. Простыми словами это значит довольно естественную вещь: чем сильнее оптимальная ручка выделяется на фоне остальных, тем меньше будет regret (тем быстрее мы найдём оптимальную), причём зависимость будет буквально обратно пропорциональная.
        • 0
          Т.е., отвечая совсем конкретно на ваш вопрос, если все ручки примерно одинаковые, то большой разницы между m1 и m2 не будет. А если одна ручка заметно лучше других, то m2 будет заметно меньше m1.
          • 0
            Да, понятно, спасибо!
      • 0
        Верно ли, что алгоритм находит оптимальные ручки в случае, если «оптимальность» ручек не меняется со временем?

        Алгоритм не сможет быстро перестроится, если всегда в тренде зелёные ручки, но под новый год — красные?
        Инерция зелёных ручек не даст снять новогодние сливки с красных?
        • 0
          Да. Не сможет. Для меняющихся со временем бандитов – другие алгоритмы, чуть посложнее, я про них расскажу в следующей серии или через раз.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка