Диссертация (1137263), страница 12
Текст из файла (страница 12)
Всилу ограничения (9) и ранее введенных соглашений об индексации(1 ≤ ≤ ≤ ), нельзя так выбрать значения , чтобы ониобозначали ситуацию, в которой для некоторого -го запроса былорешено показывать рекламный блок, содержащий ровно объявлений,но в действительности в нем показывается большее число объявлений(это бы означало, что > , то есть показалось всего два объявления,однако существует 23 , а это невозможно). Но все еще возможнаситуация, которая заключается в том, что для некоторого -го запросарешено показывать ровно объявлений, но сумма значенийсоответствующих , то есть сумма показов,0 < ∑=1 ∑ < .меньшее :То есть, например, = 3, и объявление с89индексом 1 должно быть показано на 1-ой позиции (131 = 1),объявление с индексом 3 – на 3-ей позиции (333 = 1).
Но нет ниодного объявления, которое могло бы показаться на 2-ой позиции: несуществует такого индекса 2 , чтобы было выполнено 232 = 1.Введемусловие,котороесделаетподобныеситуацииневозможными:∀, : ∑=1 ∑ ∈ {0, }(11)3.2.3 Введение ограничений, связанных с показом рекламногоблока.Определим еще один набор бинарных переменных: = 1, если в ответ на -ый запрос показан рекламный блок,содержащее ровно рекламных объявлений ∑=1 ∑ = ; = 0 иначе.Ограничение состоит в том, что если для -го запроса решенопоказывать рекламный блок над результатами поиска, то числосодержащихся в нем объявлений должно быть однозначно определено.Необходимо исключить такие события, когда показывается ровно дваобъявления и в то же время ровно три объявления. Это ограничениеможно записать так:∀: ∑=1 ≤ 1(12)Таким образом, сумма ∑=1 = 1, если для -го запроса решенопоказать рекламный блок над результатами поиска, и ∑=1 = 0иначе.3.2.4 Ограничения из базовой задачи оптимизации в случае учётапозиционного эффекта.
Математическая постановка задачи.С учётом обозначений, введённых выше, ограничение напокрытие (3) примет вид:90∑ ∑=1 ≤ Если выполнены ограничения(13)(9) – (12), то значенияиндикаторов не противоречат друг другу. Целевая функция среднейкликабельности (1) запишется в следующем виде:̅̅̅̅̅̅() = ∑(,,,) ∙ /()(14)То есть просуммируем значения кликабельностей для всехпоказанных объявлений в зависимости от их позиций в рекламномблоке и разделим на суммарное количество показанных объявлений повсем запросам.Ожидаемый доход запишется в виде:() = ∑(,,,) ∙ ∙ (15)По условию изначальной оптимизационной задачи из п. 2.1 ожидаемыйдоход ()должен быть не меньше заданной неотрицательнойвеличины :() ≥ (16)Будем решать задачу максимизации средней кликабельности попеременным :̅̅̅̅̅̅() → max0 () = (17)при условиях (9) – (13), (16).3.3Решение задачи оптимизации с учётом позиционногоэффекта.3.3.1 Расширение области значений переменных .Как и в п.
2.2.1 позволим переменным принимать любыезначения из отрезка [0;1] , а не только крайние значения 0 и 1. Отсюдавытекает еще одно ограничение-неравенство:91∀, , , : 0 ≤ ≤ 1(18)Результаты будут такими же, как если бы мы решали задачу безрасширения области значений : окажется, что для максимизациикритерия (17) переменные все равно должны принимать толькокрайние значения 0 и 1.3.3.2 Перевод ограничения по суммарному доходу в критерийПрежде всего, переведем ограничение (16) в критерий припомощи множителя Лагранжа 1 ≥ 0 и будем искать максимумполучившегося критерия при оставшихся ограничениях (9) – (13).
Врезультате получаем новый критерий:̅̅̅̅̅̅ () − 1 ( − ())1 (, 1 ) = (19)3.3.3 Перевод ограничения по суммарным денежным средствам вкритерийКак и в п. 2.2 было бы удобно оптимизировать критерий 1 ,еслибыонпредставлялсобойсуммуслагаемых.Введемдополнительное ограничение-равенство:() = 0 , 0 > 0(20)Это ограничение переведем в критерий при помощи множителяЛагранжа 1 :̅̅̅̅̅̅() −2 (, 1 , 2 , 0 ) = 1 ( − ()) − 2 (() − 0 )(21)3.3.4 Декомпозиция задачиДля 2 мы уже можем провести декомпозицию: представитьего в виде суммы слагаемых, каждое из которых зависит только от92одной из переменных .
Преобразуем 2 , сгруппировавслагаемые, зависящие от :2 (, 1 , 2 , 0 ) =∑(,,,) ∙0− 1 ( −∑(,,,) ∙ ∙ ) − 2 (∑(,,,) − 0 ) =∑(,,,) (0+ 1 ∙ ∙ − 2 ) ∙ + (−1 ∙ −0 ) = ∑ ∑(,,) (1 , 2 , 0 ) ∙ + = ∑ (, 1 , 2 , 0 ) + В результате получилось представить 2 в виде суммыслагаемых, каждое из которых относится только к одному запросу, иконстанты, не зависящей от переменных . Для максимизациикритерия 2 (, 1 , 2 , 0 ) при фиксированных 1 , 0 и 2попеременным и при условиях (9) – (13), (16) мы будем отдельномаксимизировать по при условиях (9) – (13), (16) каждое изслагаемых (, 1 , 2 , 0 ) а затем отдельно учитывать ограничение(13) на покрытие.3.3.5 Максимизация с учётом ограничений.Переменные , соответствующим образом как и в п. 2.2.3,могут принимать значения только 0 и 1.
Все нужные значения и нам заданы и, зная 1 , 0 и 2 , можно вычислить: (1 , 2 , 0 ) =0+ 1 ∙ ∙ − 2 .Заметим, что если ≤ 0, то соответствующий множитель должен быть равен нулю (ненулевое может быть толькоположительным в силу (20), поэтому в противном случае слагаемое ∙ < 0 будет лишь уменьшать сумму = ∑(,,) ∙ ). Напротив, если > 0, то в целях максимизации это должно быть умножено на максимально значение , то есть наединицу. Так мы и будем поступать в дальнейшем.933.3.6 Подбор оптимального числа баннеров на показ.Ограничение (12) сводится к тому, что доля запросов, на которыеможно показывать рекламный блок над результатами поиска,ограничена, при этом нам хотелось бы, чтобы число показанныхрекламных объявлений, их состав и позиция в рекламном блоке былиоптимальны с точки зрения максимизации соответствующего ().Отдельно рассмотрим ситуации, когда показывается только однообъявление, два объявления, и так далее до .
Для каждой из этихситуаций найдём оптимальный набор объявлений – таким образомбудут найдены все оптимальные варианты показа рекламныхобъявлений в рекламном блоке по данному запросу. В итоге выберемтот вариант, который обеспечивает максимальное значение :max (, 1 , 2 , 0 ) = =1 (max(∑(,) (1 , 2 , 0 ) ∙ )|(9)−(13),(16) ) (22)Учитывая, что в рекламном блоке над результатами поиска допускаетсяодновременный показ не более трёх объявлений, объем такогоперебора мал. Результат максимизации можно представлять в видесписка из индексов рекламных объявлений. Если, допустим, этотсписок имеет вид (1 , 2 ), то по -му запросу оптимально показатьрекламный блок, в котором на первой позиции расположенообъявление с индексом 1 , на второй – объявление с индексом 2 .Вполне может оказаться, что при заданных 1 , 2 и 0 для некоторыхзначений (или даже для всех) вообще невыгодно показыватьрекламныйблокнадрезультатамипоиска,либозадача∑(,) (1 , 2 , 0 ) ∙ → max не решается при ограничениях(9) – (13) и (16), поэтому этот список может быть пустым.943.3.7 Отбор рекламных объявлений и их размещение призаданном числе показов.Итак, для того чтобы решить задачу максимизации намостается рассмотреть решение задачи вида ∑(,) (1 , 2 , 0 ) ∙ → max при ограничениях (9) – (13) и (16).
Расположимвеличины (при фиксированных и ) в прямоугольной матрицес строками и столбцами:11( ⋮1⋯ 1⋱⋮ )⋯ (23)Если некоторое (при данных фиксированных и ) положитьравным единице, то тем самым мы отберем из этой матрицы в сумму∑(,) ∙ соответствующий элемент .
Из-за ограничений(9) и (10) становится невозможным произвольное установлениезначения равным единице, если соответствующий элемент положителен, и нулю в противном случае.Заметим, что условие (10) означает, что в этой матрице из любойстроки можно выбрать не более одного элемента. Аналогично, условие(11) означает, что из любого столбца матрицы можно выбрать не болееодного элемента.
По условию задачи оптимизации необходимо, чтобысумма выбранных элементов была как можно больше. В такойпостановке мы получаем так называемую задачу о назначениях,которая решается венгерским алгоритмом [45].При помощи венгерского алгоритма мы выбираем из каждойстроки матрицы (23) по одному значению так, чтобы никаких двавыбранных значения не находились в одном столбце. При этом суммавыбранных значений максимальна среди всех возможных выборок,95удовлетворяющих условиям нахождения в разных строках и разныхстолбцах.Просмотрим выбранные значений : если все ониположительны, то положим соответствующие им значения равными единице, а все прочие (при фиксированных и ) –нулю, тогда условия (9) и (10) будут выполнены.
Также, очевидно, вэтом случае выполнится и условие (11). То есть мы нашли решение(распределениерекламныхобъявленийпопозициям)задачи∑(,) ∙ → max , удовлетворяющее всем ограничениям. Втом случае, если какое-то из выбранных значений неположительно, то придется его не рассматривать, и, следовательно,придется исключить из рассмотрения и остальные выбранныезначения, иначе не будет выполняться условие (11).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
