Диссертация (1137263), страница 7
Текст из файла (страница 7)
Все ставки неотрицательны, т.е. ≥ 0. – оценка вероятности клика при размещении –огорекламного объявления над результатами поиска на –ый запрос.Величины и считаем заданными.Введем далее бинарную переменную , такую что = 1означает, что –ое рекламное объявлений размещено над результатомпоиска на –ый запрос,и = 0в противном случае. Именнооптимальные значения ищутся в диссертационной работе,обозначим все искомые переменные как матрицу .Тогда: = ∑ (,)будет означать суммарное количество показов рекламных объявленийпо данной выборке запросов в рекламном блоке над результатамипоиска, а () = ∑(,) ∙ /(1)– среднюю кликабельность (среднее значение по по этимрекламнымобъявлениям).Именноэтувеличинумыхотиммаксимизировать при заданных ограничениях.2.1.2 Ограничения.Ограничение по суммарному доходу.
Математическое ожиданиеденежных средств, списываемых со счета рекламодателя, равновероятности клика на данное рекламное объявление по заданномузапросу, умноженной на ставку рекламодателя выставленную для этогообъявления, в случае его показа в рекламном блоке над результатамипоиска. Если же оно не показано, то вероятность клика по объявлению41равна нулю, а, поэтому, и денежных средств оно принести не может. Заоценку вероятности клика мы принимаем заданное значение .Таким образом величина денежных средств, которые поисковаясистема может получить от показа рекламного объявления, принимаетзначение ∙ ∙ , где – номер баннера, а – номер запросаизнашейвыборки.Тогдаобщаясуммаденежныхсредств,списываемых с рекламодателей по нашей выборке запросов будетравна:() = ∑(,) ∙ ∙ требуется, чтобы эта сумма была не меньше заданного значения .Таким образом, ограничение принимает вид:() ≥ Ограничениенапокрытие.(2)Напомним,чтопокрытиемназывается доля запросов, по которым в рекламном блоке надрезультатами поиска показано хотя бы одно рекламное объявлениесреди всех результатов поиска, по которым была показана реклама.Выражение {∑() > 0} = 1, если над результатом поиска размещенхоть один баннер, и 0 в противном случае.
Тогда ограничение напокрытие примет вид:() = ∑()({∑() > }) ≤ (3)Ограничение на число рекламных объявлений, размещаемых врекламном блоке над каждым результатом поиска. Считается, что эточисло не должно превышать . Тогда это ограничение запишется как:∀ ∑() ≤ Впоисковыхсистемахколичестворекламных(4)объявлений,размещаемых над результатами поиска, исторически было ограничено42[54], причём максимально допустимым считается четыре рекламныхобъявления над поисковой выдачей.
Мы же ограничимся = 3 (этотпараметр задаётся критериями релевантности поисковой выдачи посравнению с рекламной выдачей).2.1.2 Математическая модель показов рекламных объявлений.Теперь, когда приведены все математические обозначения,можноописатьматематическуюмодельпоказоврекламныхобъявлений в рекламном блоке над результатами поиска.Входные данные. Имеется набор случайных запросов из логовзапросов пользователей (1 ≤ ≤ ). Для каждого из запросовсоставляется список рекламных объявлений (1 ≤ ≤ ) длякоторых известно: предсказание вероятности клика и ставка назначенная рекламодателем за попадание в рекламный блок надрезультатами поиска.Процесс моделирования. Теперь, когда имеется набор запросови набор рекламных объявлений, необходимо решить какие конкретноиз объявлений следует показать на запросы.
Существует некоторыйкритерий показа. В базовой модели показов рекламы он одинаковыйдля всех рекламных объявлений и запросов, то есть ∙ > .Если это условие выполнено, то индикатор показа равен 1 и 0 иначе.Таким образом заполняется матрица показов по всему наборузапросов и множеству рекламных объявлений .Выходные характеристики системы. После того как матрица определена и известно какие объявления покажутся по каждому иззапросов, можно посчитать суммарные характеристики системы:суммарныйдоходкликабельностьпо() = ∑(,) ∙ ∙ ,всемунабору43запросовсреднюю () =∑(,) ∙ / и количество запросов с показанным по нимрекламным блоком () (3).Недостатком данной математической модели показов рекламы(Рис.
2.) является то, что параметр, с помощью которого можноуправлять основными характеристиками всей системы, только один. Спомощью всего одного параметра не представляется возможнымвыбирать объявления для показа на запрос таким образом, чтобыоптимизировать какую-либо из характеристик системы.Критерий показа ∙ > Показрекламныхобъявлений = { }∀ , :Рис. 2. Математическая модель показов рекламных объявлений.2.1.3 Формальное описание задачи оптимизации.Чтобы получить новую математическую модель показов рекламыпоставим следующую задачу оптимизации: максимизировать побинарным переменным функцию () = ∑(,) ∙ /при ограничениях:∑(,)∑() ∙ ∙ ≥ {∑() > 0} ≤ ∀ ∑() ≤ 44(5)Это задача дискретного программирования.2.2Решение задачи оптимизации.
Алгоритм подбораоптимальных параметров.2.2.1 Переход от дискретной задачи к непрерывной.Сформулированная постановка задачи относится к классу задачдискретной оптимизации. Решать такие задачи трудно, обычно ихрешение требует комбинаторного перебора. Но, если такую задачупогрузить в непрерывное пространство, то часто для ее решенияудаетсявоспользоватьсяхорошоразработаннымиметодамиоптимизации в непрерывном пространстве искомых переменных. Мытакже воспользуемся этим приемом и заменим бинарные переменныенанепрерывные ,подчиненныедополнительномуограничению: 0 ≤ ≤ 1.
Эта замена корректна, потому, что, как мыувидим, при максимизации нашего критерия переменные все равнопринимают крайние значения 0 или 1. Поэтому решение непрерывнойзадачи совпадет с решением дискретной [3], [4].2.2.2 Общий принцип – метод множителей Лагранжа.Согласно методу множителей Лагранжа, если требуется найтимаксимум некоторой функции () при ограничениях () = 0, томожно эту задачу заменить на задачу поиска безусловного максимумафункции ∗ () = () − ∑ (),причемкоэффициентыподбираются так, чтобы в точке максимума ∗ () все ограничения () = 0 выполнились точно.Если же ограничения имеют вид неравенств () ≤ 0, тосогласно теории Куна-Таккера [3], метод множителей Лагранжамодифицируетсяследующимобразом:45по-прежнему,ищетсябезусловныймаксимумфункции ∗ () = () − ∑ (),акоэффициенты подбираются так, чтобы выполнились три условия:- точка максимума функции ∗ () должна удовлетворятьограничениям () ≤ 0,- коэффициенты должны быть неотрицательны ( ≥ 0),- коэффициент должен быть равен нулю, если в точкемаксимума ∗ () соответствующее ограничение не достигаетпредельного значения, т.е.
() < 0.На самом деле можно не все ограничения заменять слагаемыми вкритерии, а часть из них оставить как ограничения [4]. То есть искатьусловный максимум функции ∗ () = () − ∑ (),(=1,)при ограничениях () ≤ 0 ( = + 1, ).Требования к подбору коэффициентов остаются теми же, чтоперечислены выше.Именно этим приемом, когда часть ограничений переводится вкритерий (с последующим удовлетворением ограничений путемвыбора соответствующих множителей Лагранжа), а часть сохраняется,мы и будем пользоваться в дальнейшем.2.2.3 Применение метода множителей Лагранжа к задачеоптимизации.Добавление в критерий ограничения по деньгам.Итак, требуется найти максимум по функции 0 () =∑ ∙ / при ограничениях (2), (3), (4) и 0 ≤ ≤ 1.Сначала переведем в критерий (с помощью множителя Лагранжа 1 ≥0) только ограничение (2). Запишем его в виде () ≤ 0: − () ≤ 0,46Получим новый критерий1 () =∑ ∙∑ − 1 ( − ()),и будем искать его максимум с учетом остальных ограничений.Дополнительное ограничение.Если бы наш критерий представлял собой сумму функций, каждаяиз которых зависит только от одной переменной , то можно было быоптимизировать каждую из этих функций по отдельности – провестидекомпозицию задачи.
Но в нашем случае это не так, посколькузнаменатель = ∑(,) в слагаемых∑ ∙∑ зависит сразуот всех переменных. Для того чтобы все же добиться декомпозиции,предлагается следующее:а) Сначала зафиксировать знаменатель дополнительнымтребованием: = 0 ,где 0 – некоторая назначенная положительная константа, и найтимаксимум 1 () с учетом этого дополнительного ограничения.Этот максимум будет зависеть от назначенного значения 0 .Теперь наш критерий приобретает вид:1 () =∑ ∙ − 1 ( − ∑ ∙ ∙ ),0(,)и действительно становится суммой функций, зависящих только отодной переменной .Решая задачу, найдем значения переменных , доставляющиеусловный максимум критерия 1 () при заданных 1 и 0 .б)Перебором по 0 найти то значение 0(опт) , при которомдостигается максимум критерия1 (). Переведем с помощью47множителя Лагранжа и новое дополнительное ограничение в критерий.Получим:2 () =∑ ∙ − 1 ∙ ( − ∑ ∙ ∙ ) −0(,)−2 ∙ ( ∑ − 0 )(,)при ограничениях:0 ≤ ≤ 1,∀ ∑ ≤ () = ∑() {∑() > 0} ≤ Оптимизация критерия 2 () при оставшихся ограничениях.Итак, на данном шаге мы должны максимизировать критерий 2 ()считаявеличины 1 , 2 и 0 фиксированными.
Объединяя членысуммы, зависящие от , и вынося за скобки , получим:2 () = ∑ ∙ ( /0 + 1 ∙ ∙ − 2 ) + (,)где величина от переменных не зависит. Видим, что нашкритерий действительно представляет собой сумму функций, каждаяиз которых линейно зависит только от одной переменной .Шаг 1.Теперь найдем максимум критерия 2 () по переменным с учетом только одного ограничения: 0 ≤ ≤ 1.Ясно, что при этом переменная должна принять значение 0,если коэффициент при ней отрицателен. Действительно, в этом случае48вклад в критерий 2 () от члена суммы ∙ ( /0 + 1 ∙ ∙ − 2 ) будет отрицательным при любом положительномзначении , а при = 0 этот вклад будет нулевым.Если же этот коэффициент положителен, то без учета остальныхограниченийпеременнаядолжнапринятьзначение1.Действительно в этом случае вклад в критерий будет максимальным (иположительным) при = 1.В случае же, когда этот коэффициент в точности равен нулю принекоторых значениях пары (, ), мы получаем, что 2 () независит от .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
