Диссертация (1137263), страница 13

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

Текст из файла (страница 13)

В этом случае мыполагаем все равными нулю.3.3.8 Учёт ограничения на покрытие.Итак, мы выполнили максимизацию по переменным критерия2 при ограничениях (9) – (13), (16) и данных фиксированныхзначениях 1 , 2 и 0 , пользуясь тем, что 2 разбивается на суммунезависимых величин (, 1 , 2 , 0 ), каждая из которыхсоответствует одному из запросов. На данный момент для каждогозапроса найден список рекламных объявлений, который представляетсобой оптимальный набор для показа в рекламном блоке надрезультатами поиска в ответ на этот запрос.

Некоторые списки могутбыть пустыми: это значит, что при данных 1 , 2 и 0 по этому запросуненашлосьобъявлений,удовлетворяющимусловиямоптимизационной задачи, и рекламный блок показывать не стоит.Чтобы учесть ограничение (13) на покрытие для данного наборазапросов, мы должны показывать рекламный блок в ответ на не более96чем запросов из этого набора. Если число запросов с непустымсписком меньше, чем , то ограничение уже автоматическивыполнено. В противном случае упорядочим списки по убываниюсоответствующих им значений , и оставим только первые списков.

Тогда значение 2 будет равно сумме значений пооставленным спискам. Тем самым будет удовлетворено ограничение напокрытие, и 2 принимает максимально возможное при этомзначение. Кроме того, необходимо вычислить еще одну величину: 3 ,которая равна минимальному значению по оставленным (непустым)спискам. Эта величина зависит от 1 , 2 и 0 : 3 = 3 (1 , 2 , 0 ). Мыперебором находим оптимальные 1 опт , 2 опт и 0 опт , при которыхдостигается максимум по значения критерия 2 (, 1 , 2 , 0 ) ипри этом выполняются ограничения. Оптимальное значение 3 опт =3 (1 опт , 2 опт , 0 опт )надозапомнить,таккаконобудетиспользоваться при работе с новыми запросами для учета ограниченияна покрытие.3.3.9 Общая схема оптимизации.Общая схема оптимизации будет иметь следующий вид:Алгоритм можно записать в виде:Цикл по Величина 2 доставляет максимум нашему основному критерию0 ().Цикл по Вырученные деньги с ростом 1 не убывают, то естьможно сказать что 1 – это параметр, регулирующийпоступление денег от рекламодателей.Перебор по 1 идёт до достижения равенства() = 97Цикл по запросам По всем объявлениям-кандидатам для запроса :Составить «список для показа», вычисляя длякаждого объявления: (1 , 2 , 0 ) =0+ 1 ∙ ∙ − 2 .С помощью венгерского алгоритма решаем задачумаксимизации:∑(,) ∙ → max , в список для показапопадают соответствующие .

Таким образом: = arg max(2 (, 1 , 2 )|(9)−(13),(16) )Вычислить вклад в суммарный критерий объявлений,вошедших в список для показа в рекламный блок надрезультатами поиска: = ∑(,) ∙ Конец цикла по запросам Упорядочить списки для запросов в порядке убывания .Оставить только первые из них (выполнениеограничения по покрытию), остальные обнулить.Запомнить = min Положить:1, = {0,если пара (, ) оставлена для показа,в противном случаеМенять 1 , пока не будет достигнутоследующим образом:Если () < , то уменьшить 1Если () > , то увеличить 1Положить опт = 1 .98() = Запомнить 3 , 1 опт , списки (то есть рекламныеобъявления, отобранные для показа)Конец цикла по .Менятьчтобы2достигнутьмаксимума0 () = ∑(,,,) ∙ /()Положитьопттозначение2 ,прикоторомдостигнутmax 0 ()Конец цикла по В конце работы алгоритма мы получаем величины 1 опт , 2 опт и 3 опт ,которые будут использоваться для работы с новыми запросами.3.3.10 Схема работы с новыми запросами.В результате работы алгоритма на обучающем наборе запросовполучаются значения параметров 1 опт , 2 опт и 3 опт .

Будемиспользовать эти значения при работе с новыми запросами. Считаем,что для новых запросов и соответствующих им рекламных объявленийизвестны величины и , либо их можно каким-то образомполучить. Тогда алгоритм обработки новых запросов выглядитследующим образом (для -го нового запроса):Итак, получив новый запрос нужно:1) Отобрать объявления-кандидаты для возможных показов (пофразам запроса).2) Для каждого из этих объявлений известно значение ставки ипрогноз кликабельности , где – индекс запроса, –индекс баннера, – индекс позиции объявления средипоказанных, – общее количество рекламных объявлений врекламном блоке.3) для каждого возможного размера p рекламного блока:993.1.

вычислить значения = + 1 опт ∙ ∙ − 2 опт3.2. решить задачу ∑(,) ∙ → max при ограничениях(9) – (12)3.3. выбрать наилучший вариант по с точки зрениямаксимизации: = ∑(,,) ∙ 4) Если величина меньше 3 опт , то обнулить список, и дляданного запроса не показывать рекламный блок над результатамипоиска.

Иначе показать в рекламном блоке все объявления,которые отобрались для показа в процессе п. 3.2.После проведения операций 1) - 4), будет совершенно яснопоказывать ли по новому поступившему запросу объявления, если да,то какое количество рекламных объявлений показывать, конкретнокакиеизвсехобъявлений-кандидатовнапоказивкакойпоследовательности.3.4Численный эксперимент на модельных данных.3.4.1 Создание модельных данных.Для отладки описанного алгоритма отбора объявлений с учетомпозиционных эффектов, его тестирования и сравнения с аналогичнымалгоритмом,неучитывающимпозиционныеэффекты,будемиспользовать модельные данные, из которых и будет состоятьобучающий набор запросов.В статье Пина [51] предполагалось моделировать ставкилогнормальным распределение с параметрами = 1 и = 0.1.

Мыбудем пользоваться этим предположением при генерации модельных100данных, за исключением того, что параметры могут несколькоотличаться от указанных там = 1 и = 0.1.Для генерации значений считаем, что значения имеютбета-распределение с некоторыми параметрами. Предположение о том,что значения кликабельности имеют бета-распределение, являетсячасто используемым [63], и оно хорошо подтверждается на практике.Когдавышеутверждалось,чтозначенияможнопредставлять как реализацию некоторой случайной величины,имеющей бета-распределение, имелись в виду значения без учетапозиционных эффектов: (запрос, объявление). Далее такиекликабельности будем также обозначать как :оценкавероятности клика на -ое объявление в случае, если оно показываетсяна странице результатов поиска в ответ на -ый запрос.

Для того чтобыперейти от вероятностей кликов без учета позиционныхэффектов к вероятностям кликов , зависящим от позиционныхэффектов, используем предположение, в котором вероятность клика представляется в виде произведения: = ∙ Множитель зависит только от объявления и запроса, амножитель вводится для учета позиционных эффектов. Такоепредположение рассматривается во многих работах [68], [31], [47]. Внашем случае множитель представляется в виде = ∙−1 . Множитель учитывает тот факт, что любое объявление врекламном блоке может быть показано одно, либо иметь одного, либодвух соседей (напомним, что всего в рекламном блоке допускаетсяодновременный показ не более трёх рекламных объявлений).

То естьесли в ответ на -ый запрос в рекламном блоке над результатамипоиска показываются два объявления, в число которых входит -ое, то101для учета этого факта в оценке вероятности клика для -го объявленияпроизводится умножением на  2 . Значения для 1 , 2 и 3выбираются из следующих предположений. Когда объявлениепоказывается в одиночку, вероятность клика на него гораздо больше,чем когда он показывается совместно с одним или более рекламныхобъявлений.Фактическизначение(объявлениепоказываетсявкликабельностиодиночестве),должно11немногопревосходить значение кликабельности (итоговое усредненноезначение без позиционных эффектов), поэтому будем полагать 1 ≈ 1,1 > 1. Далее, когда объявление показывается в компании ровноодного соседа, то вероятность того, что пользователь кликнет на него,больше, чем когда это же объявление показывается в компании ровнодвух соседей. Поэтому будем полагать, что 1 ≥ 2 > 3 .

Например, внескольких вычислительных экспериментах использовались значения1 = 1.065, 2 = 0.92 и 3 = 0.83, а в нескольких других 1 = 1.045,2 = 0.72 и 3 = 0.902.Теперь рассмотрим множитель −1 (величина ,возведенная в степень − 1). В работе Фенга [31] предлагалось ввестиэкспоненциальное затухание для того, чтобы учесть позициюобъявления. Допустим, что в ответ на -ый запрос показываетсярекламный блок над результатами поиска, и в нем показано ровно триобъявления, причем интересующее нас -ое объявление находится на-ой сверху позиции (1 ≤ ≤ 3).

Тогда учет этого эффектапроизводится умножением кликабельности на −1 .Значениямножителяможновзятьизнепрерывногораспределения на отрезке [0; 1] – например, из бета-распределения спараметрами и .Схема, по которой генерируются модельные данные, такова:1021. Задаемся: параметрами ≥ 0и ≥ 0длялогнормальногораспределения ставок; параметрами > 0 и > 0 для бета-распределения независящих от позиционных эффектов кликабельностей ; параметрами > 0 и > 0 для бета-распределениякоэффициентов затухания, которые используются для учетапозиции , на которой находится данное объявление; положительными множителями 1 , 2 и 3 , используемыми дляучета числа объявлений, показываемых одновременно врекламном блоке; – размер модельного набора запросов; – общее число различных объявлений; минимальным (_) и максимальным (_) числомрекламных объявлений, которые могут быть кандидатами дляпоказа в рекламном блоке по одному запросу.2. Будем различать запросы по идентификатору , объявления – поиндексу/идентификатору .

То есть на данный момент у нас есть запросов, индексируемых при помощи , и рекламныхобъявлений, индексируемых при помощи . Пока что это пустыесущности: не составлены списки объявлений, соответствующихзапросам, не сгенерированы ставки для запросов и т.д.3. Для каждого запроса сгенерируем ставку , являющуюсяреализацией случайной величины из логнормального распределенияс параметрами и .4. Для каждого запроса сгенерируем коэффициент затухания из бета-распределения с параметрами и .5. Для каждого запроса :1035.1. Определяем,сколькообъявленийемусоответствует(равномерная случайная целая величина между и ) – назовем это число __ .5.2. Делаем случайную выборку размера __ измножества идентификаторов .

Объявления с выбраннымиидентификаторами теперь соответствуют запросу .5.3. Для текущего запроса и каждого объявления изсоответствующих ему объявлений генерируем значения .5.4. Для каждого возможного числа баннеров , показываемых врекламном блоке над результатами поиска определяем как = ∙ ∙ −1 .−1 моделирует .104Произведение ∙b)a)c)Рис.

22. Гистограммы распределений и плотности для (a), коэффициентовзатухания (b) и ставок (с).Примеры гистограмм и функций плотности распределения дляпозиционно-независимых , коэффициентов затухания иставок приведены на Рис.

Характеристики

Список файлов диссертации