A Combinatorial-Bandit Algorithm for the Online Joint Bid / Budget Optimization of Pay-per-Click Advertising Campaigns |
||
МЕНЮ Искусственный интеллект Поиск Регистрация на сайте Помощь проекту ТЕМЫ Новости ИИ Искусственный интеллект Разработка ИИГолосовой помощник Городские сумасшедшие ИИ в медицине ИИ проекты Искусственные нейросети Слежка за людьми Угроза ИИ ИИ теория Внедрение ИИКомпьютерные науки Машинное обуч. (Ошибки) Машинное обучение Машинный перевод Нейронные сети начинающим Реализация ИИ Реализация нейросетей Создание беспилотных авто Трезво про ИИ Философия ИИ Big data Работа разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика
Генетические алгоритмы Капсульные нейросети Основы нейронных сетей Распознавание лиц Распознавание образов Распознавание речи Техническое зрение Чат-боты Авторизация |
2020-07-16 13:53
Какую задачу решают в статье?
Авторы статьи решают задачу оптимального распределения общего бюджета между объявлениями таким образом, чтобы максимизировать суммарную выгоду. Представьте, что рекламодатель создал два объявление и у него есть 100 рублей. Объявления разные и заранее сложно оценить, какое из них будет эффективнее для рекламодателя и принесет больше дешевых кликов, поэтому непонятно, какой дневной бюджет указать каждому из объявлений. Алгоритм должен заметить, что первое объявление работает гораздо круче, но и по второму по низкой ставке можно найти немного хороших кликов. Поэтому результатом алгоритма будет, например, что первое объявление потратило 80 рублей и заработало 16 кликов, а второе – 20 рублей и 4 клика. Чуть формальнее. Пусть есть кампания, состоящая из N объявлений, общим дневным бюджетом B и ожидаемой длительностью кампании в днях T. Для каждого объявления из кампании требуется найти оптимальную пару (бюджет, ставка) такую, чтобы суммарное число полученных кликов было максимально. В статье Zhang W. et al. 2013 года данную задачу решали с помощью последовательного квадратичного программирования. Авторы сформулировали задачу оптимизации и итеративно решают ее с помощью квадратичного программирования. В статье Xu J. et al. 2015 года было предложено жадное итеративное решение. Каждый день на основе показателей прошлого дня (потраченный бюджет, средний CTR, приоритета объявления, вероятности перехода от вставки к показу) обновляются пропорции бюджета между объявлениями. Основной принцип: чем выше CTR, тем выше приоритет объявления и вероятности перехода от вставки к показу у более приоритетных объявлений не может быть меньше, чем у менее приоритетных объявлений. Как решают? Задачу формулирует в терминах задачи оптимизации с ограничениями. Для каждого объявления найти такие оптимальные ставку и бюджет, чтобы максимизировать суммарное взвешенное число кликов всех объявлений. Данная задача есть не что иное, как задача о рюкзаке с мультивыбором (Multiple-choice Knapsack Problem) Есть N предметов, у каждого предмета есть стоимость и вес, каждый предмет принадлежит одному из M классов. Выбрать по одному предмету из каждого класса таким образом, чтобы стоимость была максимальна, а суммарный вес не превышал вес рюкзака. Проводя аналогию с рюкзаком, предметы это множество всевозможных пар (бюджет, ставка). Стоимость предмета это количество кликов, которые можно получить по заданной ставке и бюджету. Нужно выбрать подмножество пар (бюджет, ставка), где каждая пара принадлежит только одному из объявлений, так чтобы сумма кликов (стоимость предмета) была максимальна, а сумма бюджетов объявлений (вес предмета) меньше бюджета кампании. При этом в отличие от задачи о рюкзаке, задача динамична и в течение времени нужно заново выбирать предметы (оптимальные пары (бюджет, ставка)) из каждого класса. Предлагаемое решение состоит из трех этапов: обновление модели предсказания кликов и выбор оптимальных пар (бюджет, ставка) для каждого объявления. Сначала авторы описывают модель оценки максимального ожидаемого числа кликов и максимального потраченного бюджета по заданной ставке для конкретного объявления. С помощью оценки этих значений далее авторы рассчитывают ожидаемое число кликов по объявлению по заданной ставке и заданному бюджету с помощью линейной формулы. Ожидаемое число кликов моделируется с помощью Гауссовского процесса. В первый день задают средние значения, в последующие дни уточняю модель с помощью данных об открутке объявления в предыдущий день. Также в модели есть exploration стадия, которую авторы реализуют с помощью комбинаторных бандитов (combinatorial bandit). Выбор оптимальных пар (бюджет, ставка) для каждого объявления осуществляется с помощью динамического программирования, как в обычном ограниченном рюкзаке. То есть за O(кол-во объявлений * (кол-во вариантов бюджета для объявления)^2). Также авторы уточняют, что если второй параметр большой, то можно решать эту задачу с помощью приближенной схемы, которая ищет субоптимальное решение за полиномиальное время. Тестировали на датасете Yahoo! с помощью какого-то симулятора и в течение двух месяцев на реальной кампании в финансовой итальянской кампании. Преимущества подхода
Мое мнение
Другие статьи по этой задаче
Источник: m.vk.com Комментарии: |
|