Ротация размещений

В первой части были описаны общие принципы по вычислению ёмкостей рекламных мест. На каком-то этапе мы получили оценку ёмкости по любым комбинациям переменных таргетирования. Для построения финального прогноза этих данных недостаточно. Ведь на одном рекламном месте может происходить ротация нескольких размещений. Таким образом, чтобы рассчитать прогноз какого-то размещения, нужно знать все размещения, которые в будущем будут конкурировать с ним на данном рекламном месте. Более того, добавление нового размещения в систему влияет на прогноз всех остальных пересекающихся с ним размещений (понятно, что вновь добавленное размещение «отнимет» у остальных часть трафика).

Достаточно сложно обозначить какую-то общую схему, по которой мы можем произвести расчет. Проблема в том, что правила ротации в разных баннерных системах сильно различаются. Зачастую эти правила диктуются особенностями бизнеса (например, наличие приоритетных размещений, способных полностью «захватить» трафик). Задача прогноза ротации нескольких размещений в большинстве случаев сводится к линейному программированию. Полная схема расчета достаточно сложна для понимания. Можно рассмотреть пример с достаточно простыми правилами ротации, а именно:

  • На рекламное место можно назначить сколько угодно размещений
  • Каждое размещение имеет вес (целое число); чем больше вес размещения, тем больше трафика оно получит
  • Есть ограничение на число показов в сутки по каждому размещению.

Для простоты можно рассчитать пример прогноза ротации на одном рекламном месте в течение суток. Пусть изначально нам известны ёмкости для различных условий таргетирования:

Firefox & Москва 1000
Firefox & Windows 1000
Firefox & Москва & Windows 300

Есть 2 размещения:

  • Размещение A1 с условиями таргетирования Firefox & Москва, весом 1
  • Размещение A2 с условиями таргетирования Firefox & Windows, весом 2
  • Размещение A2 имеет ограничение на число показов в сутки, равное 450.

Попробуем определить, как эти два размещения будут откручиваться. В тех областях, где размещения не пересекаются, им будет доступна максимальная ёмкость, и она составит 1000 — 300 = 700 показов:

Там, где имеется пересечение по условиям таргетирования (Firefox & Москва & Windows), оба размещения будут откручиваться в соответствии со своими весами: размещение A1, имеющее вес 1, получит 1/3 трафика (100 показов), размещение A2 — 2/3 трафика (200 показов). Теперь мы можем вычислить окончательный прогноз — A1: 700 + 100 = 800 показов, A2: 700 + 200 = 900 показов.

Этот прогноз, однако, не учитывает, что A2 имеет ограничение на число показов — 450, что явно меньше максимального прогноза — 900. Примем гипотезу, что трафик по размещению A2 будет распределен пропорционально максимальному прогнозу. Тогда по условиям таргетирования Firefox & Windows получим скорректированный прогноз 350, а для Firefox & Москва & Windows — 100. Поскольку при этом «освобождается» часть ёмкости рекламного места, нужно понять, кому достанется остаточный трафик. В области пересечения A1 и A2 остаточный трафик перейдет размещению A1 (которое в данной области получит уже не 100, а 200 показов). В тех областях, где размещение A2 не накладывается на другие размещения, трафик останется «невостребованным».

Как видим, даже для двух размещений расчет прогноза превращается в нетривиальную процедуру. Чем сложнее логика ротации и чем больше ограничений разного рода она содержит, тем более сложным и трудоёмким становится алгоритм расчета.

Кстати, выше мы провели расчёт всего лишь за одни сутки. Реально же нам нужен прогноз на всё время открутки размещения. Период открутки размещения может регулироваться несколькими правилами:

  • Общее ограничение по числу показов/кликов для данного размещения
  • Ограничение по числу показов/кликов для данного размещения в течение суток
  • Жесткое ограничение по временному периоду (ситуация, когда нужно показывать рекламу четко в определенные дни)

Все эти правила могут применяться одновременно, образуя довольно сложную картину:

Ротация по времени

На диаграмме изображен прогноз по размещениям и временная шкала в днях (это могут быть не обязательно дни, а любая другая подходящая единица планирования — час, неделя). Прогноз вычисляется слева направо, начиная от текущей даты. Когда мы делаем прогноз по показам для размещений внутри одного дня, мы должны учитывать уже вычисленный прогноз за предыдущие дни, т.к. это влияет на достижение лимитов размещений. С другой стороны, некоторые размещения уже начали откручиваться, и нам необходимо учитывать реальную статистику событий в нашем прогнозе. Что самое неприятное, статистика может приходить с опозданием. Все это создает дополнительные сложности и в целом большую вычислительную нагрузку.

Важным моментом является то, что вычисленный прогноз остается актуальным довольно ограниченное время. Как только на данном рекламном месте добавляется новое размещение или снимается существующее, прогноз нужно вычислять заново. Когда прогноз показывается пользователю (а обычно это в момент создания размещения), необходимо особо разъяснять, что прогноз является одномоментным и может измениться в результате появления других конкурирующих размещений.

Формальные методы расчета

Выше мы описали «умозрительный» способ построения прогноза, применимый только к частному случаю. В нашем примере не было конфликтных ситуаций, когда неясно, какому именно размещению достанется избыточный трафик. Тем, кто хочет понять, как в общем случае можно рассчитать прогноз по размещениям при наличии множества различных условий и лимитов, предлагается более углубленная модель, которая будет описана ниже.

Начнем с уже известного нам примера, размещения A1 и A2. Попробуем сформулировать граничные условия открутки в терминах системы уравнений. Неизвестными в этих уравнений будут доли трафика размещений A1 и A2. Назовем их соответственно X1 и X2. Учитывая, что внутри одного размещения трафик делится в соответствии с условиями таргетирования, мы дополнительно делим неизвестные X1 и X2 по условиям таргетирования, вот так:

X1 = X1(FF,Москва,не_Win) + X1(FF,Москва,Win)
X2 = X2(FF,не_Москва,Win) + X2(FF,Москва,Win)

Далее, каждая из этих неизвестных ограничена соответствующими ёмкостями, поэтому дополняем нашу систему ограничениями вида:

X1(FF,Москва,Win) + X2(FF,Москва,Win) ≤ Capacity(FF,Москва,Win)
X1(FF,Москва,не_Win) ≤ Capacity(FF,Москва,не_Win)
X2(FF,не_Москва,Win) ≤ Capacity(FF,не_Москва,Win)

Здесь значения ёмкости вида Capacity(FF,Москва,не_Win) означают остаточную ёмкость (всё, что FF и Москва, но не Windows). Фактически Capacity(FF,Москва,не_Win) = Capacity(FF,Москва) - Capacity(FF,Москва,Win).

Мы также знаем, что размещения имеют пересечение трафика в области FF,Москва,Win. Как будет распределен этот трафик? Если бы размещения могли откручиваться неограниченно, мы бы, памятуя, что размещение A2 имеет вес 2, просто добавили условие:


X1(FF,Москва,Win) = 2⋅X2(FF,Москва,Win)

Но мир жесток, и нужно ещё как-то учесть лимиты размещений:

X1(FF,Москва,Win) = 2⋅X2(FF,Москва,Win), если X2(FF,Москва,Win)≤Limit(A2)

Это условное неравенство, означающее, что распределение трафика как 1:2 будет действовать только при соблюдении лимитов. А что будет, если лимит будет превышен? Тут есть простор для гипотез, ведь всё сильно зависит от того, как рекламная система отслеживает лимиты и насколько равномерно откручиваются размещения. При условии равномерного откручивания, если лимит A2 будет достигнут, у размещения A1 будут шансы «подобрать» оставшийся трафик. Однако откручивание может быть неравномерным и иметь «всплески», тогда результат непредсказуем (в том числе возможна ситуация, что размещение A1 не успеет получить положенный ему трафик).

Если рассматривать это неравенство отдельно в пространстве двух переменных, то его решение будет выглядеть так:

Распределение трафика между размещениями

В области, где лимит A2 не достигается, решением является часть прямой. В области, где лимит превышен, ограничение трафика уже никак не работает и решением является вся заштрихованная полуплоскость.

Если записать все имеющиеся у нас ограничения, получим такую систему:

X1(FF,Москва,Win) + X2(FF,Москва,Win) ≤ 300
X1(FF,Москва,не_Win) ≤ 700
X2(FF,не_Москва,Win) ≤ 700
X1(FF,Москва,Win) = 2⋅X2(FF,Москва,Win), если X2(FF,Москва,Win)≤450

Изобразить графически это будет сложнее, т.к. всё происходит уже в четырехмерном пространстве. При этом неявно предполагаем, что все Xi ≥ 0; то, что переменные у нас строго целочисленные, можно для простоты проигнорировать.

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

Эти рассуждения приводят нас к задаче линейного программирования. Поскольку это задача оптимизации функции, давайте подумаем, какую функцию мы оптимизируем. Для начала можно выбрать просто функцию суммарного трафика:

ƒ(...) = X1(FF,Москва,Win) + X2(FF,Москва,Win) + X1(FF,Москва,не_Win) + X2(FF,не_Москва,Win)

В этой функции трафик всех размещений равноценен для нас. Максимизируя эту функцию, мы максимизируем трафик, при этом неважно, за счет каких размещений.

Заключение

Мы рассмотрели проблему прогнозирования в комплексе. Как видим, прогнозирование требует решения ряда сложных задач; причем сложных как алгоритмически, так и с вычислительной точки зрения. Мы поделили формирование прогноза на две стадии:

  • Статическая часть — расчет ёмкостей рекламных мест с учётом таргетирования
  • Динамическая часть — расчет финального прогноза по размещению с учётом ротации на данном рекламном месте.

Мы определили, что прогноз по ротации для всех размещений должен вычисляться последовательно слева направо, начиная от текущей даты. Одним из важных моментов, требующих упоминания, является малое время актуальности прогноза по размещению: запуск, остановка других размещений и даже изменения в их настройках требуют уточнения прогноза.

  • Sharing

    Facebooktwittergoogle_plusredditpinterestlinkedinmailby feather