A Combinatorial-Bandit Algorithm for the Online Joint Bid / Budget Optimization of Pay-per-Click Advertising Campaigns

МЕНЮ


Искусственный интеллект
Поиск
Регистрация на сайте
Помощь проекту

ТЕМЫ


Новости ИИРазработка ИИВнедрение ИИРабота разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика

Авторизация



RSS


RSS новости


Какую задачу решают в статье?

Авторы статьи решают задачу оптимального распределения общего бюджета между объявлениями таким образом, чтобы максимизировать суммарную выгоду.

Представьте, что рекламодатель создал два объявление и у него есть 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! с помощью какого-то симулятора и в течение двух месяцев на реальной кампании в финансовой итальянской кампании.

Преимущества подхода

  • За счет наличия exploration стадии не требует в большого числа данных для обучения модели предсказания кликов в отличие от ранее предложенных подходов

Мое мнение

  • Круто, что подняли и сформулировали задачу оптимизации бюджета кампании, до них нашла только две статьи 2012 и 2015 года. Предлагаемое решение достаточно простое, поэтому думаю, что есть большой потенциал исследования и экспериментов в этой теме
  • Нет сравнения с другими алгоритмами. Говорят, что будет нечестное сравнение, потому что другим алгоритмам требуется большой датасет для обучения
  • Тестирование на нескольких кампаниях и без сравнения выглядит неубедительно

Другие статьи по этой задаче

  • Smart Pacing for Effective Online Ad Campaign Optimization, KDD 2015
  • Joint Optimization of Bid and Budget Allocation in Sponsored Search, KDD 2012

Источник: m.vk.com

Комментарии: