Диссертация (1137263), страница 9
Текст из файла (страница 9)
Иначе показать все объявления изусеченного списка.После проведения операций 1)-7) , будет совершенно ясно показыватьли по новому поступившему запросу объявления, если да, то какиеконкретно из всех объявлений-кандидатов на показ.Таким образом, представлена математическая постановка задачиоптимизации показов объявлений над результатами поиска, а такжерешение этой оптимизационной задачи при помощи теории КунаТаккера. В итоге представлен алгоритм отбора рекламных объявленийдля показа, а также обработка нового пользовательского запросапоступившего в поисковую систему.582.5Модификация алгоритмаПредлагается модификация базового алгоритма, позволяющаясущественноускоритьегоработу.Общаясхемаалгоритмапредставлена на Рис. 3.Внешний цикл реализует перебор по переменной 2 , в ходекоторого ищется значение 2опт , доставляющее максимум нашемуосновному критерию:0 () = ∑ ∙ /(,)вложенный цикл осуществляет перебор по переменной 1 , где ищется(при фиксированном значении 2 ) значение 1 , обеспечивающееравенство () = .Замена неравенства () ≥ на равенство объясняетсяследующим: если бы было справедливо () > , то по теорииКуна-Таккера должно быть справедливо 1 = 0, но тогда ограничениена суммарные денежные средства вообще не учитывается, и максимумсреднего значения будет достигнут, если показать толькообъявления с максимальным значением .
Но таковых будет одинили совсем немного, а тогда (в практически интересных случаях)денежных средств заведомо не хватит.59Перебор значений 2 с цельюмаксимизации критерия0 () = ∑ ∙ /(,)Перебор значений 1(при фиксированном 2 )до достижения равенства() = Решение задачи оптимизации критерия1 () = ∑ ∙ ( + 1 ∙ ∙ − 2 )(,)при фиксированных значениях 1 и 2 .Получение оптимальных значений матрицы и соответствующих значений и 3Оптимальные значения1 , 2 и 3Рис. 3. Общая схема алгоритма подбора порогов.Можно показать, что оптимальная величина () (прификсированном значении 2 ) не убывает с ростом 1 , и поэтому длянахождения корня () = можно использовать бинарныйпоиск.Центральная часть алгоритма осуществляет выбор оптимальныхзначений переменных , доставляющих максимум критерию:1 () = ∑ ∙ ( + 1 ∙ ∙ − 2 )(,)при фиксированных значениях 1 и 2 .
Оптимизация идет тем жепутем, который описан для начального алгоритма.602.5.1 Формальное описание алгоритмаТеперь запишем общий алгоритм подбора параметров критерияпоказа объявлений над результатами поиска. Обозначения принятытакими же, как и в формальном описании начального алгоритма (п. 2.3).Алгоритм можно записать в виде:Цикл по Величина 2 доставляет максимум основному критерию 0 ().Цикл по Вырученные денежные средства с ростом 1 не убывают,то есть можно сказать что 1 - параметр, регулирующийпоступление денежных средств от рекламодателей.Перебор по 1 идёт до достижения () = Цикл по запросам По всем баннерам-кандидатам для запроса :Составить «список для показа», вычисляя длякаждого рекламного объявления: (1 , 2 , 0 ) = + 1 ∙ ∙ − 2Не включая в список те , для которых неположительно,иоставивобъявленийснаибольшим значением .Вычислить вклад в суммарный критерий объявлений,вошедших в список для показа: = ∑ (по объявлениямвошедшим в список)Конец цикла по запросам Упорядочить списки для запросов в порядке убывания .61Оставить только первые из них (выполнениеограничения по покрытию), остальные обнулить (это в томслучае, если списков с рекламой хватает, в противномслучае оставить все списки).Запомнить = min Положить:1, = {0,если пара (, ) оставлена для показа,в противном случаеМенять 1 , пока не будет достигнуто() = следующим образом:Если () < , то уменьшить 1Если () > , то увеличить 1Положить опт = 1 .Запомнить 3 , 1 опт , списки (то есть объявления,отобранные для показа)Конец цикла по .Менять 2 чтобы достигнуть максимума0 () = ∑(,) ∙ /Положить опт то значение 2 , при котором достигнут max 0 ().Конец цикла по В конце работы алгоритма мы получаем значения трёх параметров1 опт , 2 опт и 3 опт , которые будут использоваться для работы сновыми запросами.2.5.2 Доказательство эквивалентности двух алгоритмовДопустим, что максимум функционала:0 () = ∑ ∙ /(,)62достигается в опт и величина оптсоответствует этомузначению опт , где = 0 означает, что рекламное объявление назапрос не показывалось, а при = 1 – показывалось, и =∑(,) , при ограничениях:() ≥ ∀ ∑ ≤ () = ∑ {∑()() > 0} ≤ 0 ≤ ≤ 1В дальнейшем предположим, что в точке максимума ограничение насуммарные денежные средства достигается, т.е.(опт ) = (7)По «старому» алгоритму опт достигается при следующих условиях:Критерий2 () = ∑ ∙ ( /0 + 1 ∙ ∙ − 2 ) + (,)достигает максимума по при ограничениях:∀ ∑ ≤ () = ∑() {∑() > 0} ≤ 0 ≤ ≤ 1а коэффициенты 1 , 2 и 0 подбираются так, чтобы = ∑ = 0(,)630 опт = arg max 1 (, 1 , 0 ) == arg max [∑ ∙ − 1 ( − ())]0(опт ) = ,Следовательно0 = опт .Обозначим также подобранные значения 1 и 2 как 1опт и 2опт .Умножим 2 () на постоянную величину опт и обозначимэту функцию 2∗ ():2∗ () = ∑ ∙ ( + (1 ∙ опт ) ∙ ∙ − (2(,)∙ опт )) + Замечание 1.Обозначим 1∗ = 1 ∙ опт , ∗2 = 2 ∙ опт , и заметим,чтоопт , доставляющее максимум критерию, не меняется приумножении на константу.Перейдем теперь к «новому алгоритму».
По этому алгоритму мысначала максимизируем критерий ∑(,) ∙ ( + 1 ∙ ∙ − 2 ) при фиксированных значениях 1 и 2 . При этом вкачестве оптимальных значений получим (1 , 2 ) и соответствующиезначения (1 , 2 ), 0 ((1 , 2 )) и ((1 , 2 )). Затем длякаждого значения 1 величина 2 опт (1 ) подбирается так, чтобы(1 , 2 ) = Далеезначение 2 = 2 опт подбирается так, чтобы величина0 ((1 , 2 )) достигла максимума при 2 = 2 опт (1 ).Теперь видим, что значения 1∗ и ∗2 могут претендовать нарезультат «нового» алгоритма. Действительно, в силу Замечания 1значение (1∗ , ∗2 ) = опт , и, значит, доставляет максимум критерию64∑(,) опт ∙ ( + 1 ∙ ∙ − 2 )прификсированныхзначениях 1∗ и ∗2 .
В то же время в силу (1):(1∗ , ∗2 ) = Таким образом, при переборе 1 в качестве нужного значенияпри 1 = 1∗ будет по новому алгоритму выбрано 2 = ∗2 . Наконец, поновому алгоритму значение1 опт выбирается так, чтобы былдостигнут максимум величины 0 ((1 , 2 )).
Но при 1 = 1∗ и 2 =∗2 эта величина по построению достигает максимума. Значит, либо1 опт = 1∗ , либо при равенстве максимумов0 ((1∗ , ∗2 )) = 0 ((1 опт , 2 опт )).И, значит, новый алгоритм дает результат равносильный старому.Таким образом, модифицированный алгоритм решает ту жеоптимизационную задачу, однако количество затрачиваемого объёмапроизводимых операций уменьшается на порядок (так как былупразднён один из переборов по внешнему параметру).2.6Новая модель показа рекламных объявлений.Теперь, когда получен новый вид критерия показа рекламногообъявления в рекламном блоке над результатами поиска, можноописать новую модель показа.Входные данные модели остаются такими же: набор запросовпользователей (1 ≤ ≤ ).
Для каждого из запросов составляетсясписок рекламных объявлений (1 ≤ ≤ ) для которых известно:предсказание вероятности клика и ставка .Процесс моделирования. Имеется набор запросов и наборрекламных объявлений и необходимо решить какие конкретно изобъявлений следует показать. Был выявлен вид критерия показа + 1 ∙ ∙ − 2 > 0 с помощью которого модель65определяет показывать ли объявление по запросу . Для каждого иззапросов и соответствующим им объявлениям необходимо выполнить:1) Вычислить значение = + 1 опт ∙ ∙ − 2 оптдля всех объявлений.2) Составить список кандидатов на показ над результатами поиска. Вэтот список поместить только те объявления, для которых > 0.Если список пуст, то над результатами поиска не будет показано ниодного рекламного объявления.3) Если число кандидатов больше , то сократить список, оставив внем только объявлений с наибольшим значением .4) Подсчитать значение = ∑() , где сумма берется по всемобъявлениям из усеченного списка.5) Если эта величина меньше 3 опт , то обнулить список, и дляданногозапросанепоказыватьникакихобъявленийнадрезультатами поиска и положить соответствующие = 0.
Иначепоказать все объявления из усеченного списка и положить = 1.Таким образом заполняется матрица показов по всему наборузапросов и множеству рекламных объявлений .Выходные характеристики системы. После того как матрица определена и известно какие объявления покажутся по каждому иззапросов считаются суммарные характеристики системы: суммарныйдоход(), средняя кликабельность по всему набору запросов () и количество запросов с показанным по ним рекламнымблоком ().
Теперь, они соответствуют следующим правилам: () → max() ≥ () ≤ ∀ : ≤ 66То есть мы отбираем объявления для показа таким образом чтобымаксимизироватьсреднююкликабельностьвсехпоказанныхобъявлений по набору запросов с ограничениями на суммарный доходи покрытие.Достоинством данной модели (Рис. 4.) является то, что дляуправления выходными характеристиками системы показов рекламныхобъявлений используется три параметра критерия показа 1 , 2 и 3 . Спомощью этих параметров мы можем регулировать основныепоказатели системы.Критерий показа= + 1 ∙ ∙ − 2ПоказрекламныхОбъявлений = { }∀ , :max ≥ ≤ ∀ : ≤ Параметры управления показами:1 , 2 и 3Рис. 4. Новая модель показов рекламы над результатами поиска.2.7Результаты экспериментального тестирования алгоритмаТестирование на реальных данных будет проводиться только дляулучшенного алгоритма по следующим причинам:во-первых, модифицированный алгоритм эквивалентен изначальнопредложенному (п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
