Диссертация (1137263), страница 8
Текст из файла (страница 8)
При естественных значениях входных параметров,точное равенство коэффициента нулю может случиться только ввырожденных случаях. Но при подборе значений коэффициентовЛагранжа может оказаться необходимым выбрать дробное значение . Однако на практике такое может случиться только для оченьмалого числа пар (, ). Действительно, мы подбираем совсемнебольшое число неопределенных коэффициентов, и обеспечитьточное равенство коэффициента нулю можно тоже в очень маломколичестве случаев.
Учитывая, что в нашем пуле содержатся тысячиэлементов, замена значения на 0 или 1 в этих случаях практическине влияет на значение критерия.Ноостальныеограничениямогутсделатьпоказ–огообъявления на –тый запрос все же недопустимым, т.е. придетсяположить = 0.Обозначим (1 , 2 , 0 ) коэффициент при : (1 , 2 , 0 ) = /0 + 1 ∙ ∙ − 2Тогда кандидатами на показ в рекламном блоке над результатамипоиска будут те объявления, для которых > 0. Таким образом (1 , 2 , 0 ) является критерием показа рекламного объявления.49Составим теперь для каждого (–ого) запроса список кандидатовна показ в рекламном блоке над результатами поиска, упорядочив их впорядке убывания величин (1 , 2 ). Некоторые из списков могутоказаться пустыми, если для всех окажется, что (1 , 2 ) ≤ 0.Шаг 2.Теперьучтемограничениенаколичествобаннеров,размещаемых сверху от результатов поиска:∀ ∑ ≤ ()Если количество рекламных объявлений в списке кандидатов длязапроса–огоменьше,тоэтоограничениевыполнитсяавтоматически.
Иначе, для максимизации нашего критерия 2 ()следует оставить в каждом списке ровно кандидатов с максимальнымзначением (1 , 2 ), т.е. первые элементов списка. Для остальныхэлементов положить = 0. Назовем этот укороченный список«список для показа».Шаг 3.Остается ограничение на покрытие:() = ∑() {∑() > 0} ≤ то есть реклама над результатами поиска должна присутствовать неболее чем в результатах поиска. Если и так количество запросовс не пустым усеченным списком меньше чем , то ограничениевыполнится автоматически. В противном случае часть списков следуетобнулить.Обозначим (1 , 2 ) вклад в критерий для каждого запроса отрекламных объявлений, вошедших в усеченный список: (1 , 2 ) = ∑ ( /0 + 1 ∙ ∙ − 2 ),()50где сумма для каждого запроса берется только по рекламнымобъявлениям, вошедшим в список для показа.Ясно, что максимум критерия будет достигнут, если мы оставимтолько списков с наибольшим значением (1 , 2 ).
Инымисловами, если мы упорядочим списки в порядке убывания (1 , 2 ),то следует оставить только первых списков (если, конечно иххватит, иначе оставляем все). Обозначим 3 опт минимальное значение (1 , 2 ) по всем оставшимся спискам. Тогда будут оставлены толькоте списки, для которых (1 , 2 ) ≥ 3 . Разумеется, величина 3 будетзависеть от принятых значений 1 , 2 и 0 .Теперь можно зафиксировать оптимальные значения : = 1, если – е объявление в списке для показа для – ого запроса{ = 0,в противном случаеЭтот результат мы получили для заданных значений 1 , 2 и 0 .Обозначим через опт (1 , 2 , 0 ) вектор, составленный из значений этого решения.Выбор необходимого значения .Теперь мы должны найти то значение коэффициента 2 , прикотором действительно выполнится наше дополнительное ограничение = 0 .Заметим, что, зная значения , мы можем подсчитать величину = ∑(,) , причем значение (как и значения ) будетзависеть от зафиксированных значений 1 , 2 и 0 .
Но нас сейчас будетинтересовать только зависимость от Лагранжева коэффициента2 , считая по–прежнему значения 1 и 0 фиксированными. Перебираявсе значения 2 , мы можем попытаться добиться равенства(2 ) = 0 . Конечно, может случиться, что ни при какомзначении 2 это равенство не выполнится (в силу цело-численности 051или по иной причине, но такие значения объявим не допустимыми).Найденное значение 2 опт (1 , 0 ) (абсолютного порога) будет зависетьот 1 и 0 .
Ему будет соответствовать решение опт (1 , 2 опт (1 , 0 ),0 ).Выбор оптимального значения путем максимизациикритерия ().Теперь нам нужно избавиться от дополнительного ограничения = 0 , поскольку оно не входит в число ограничений исходнойпостановки задачи. Сделать это можно с помощью максимизациикритерия:1 (, 1 , 2 , 0 ) =∑ ∙ − 1 ( − ())0путем перебора по всем допустимым значениям 0 при фиксированномзначении 1 . При этомнайденныеприв качестве должны браться значения,2 = 2 опт (1 ,0 ).Этообеспечивает равенство (1 , 2 , 0 ) = 0значениезаведомов силу операции,описанной в предыдущем разделе.Обозначим 0 опт (1 ) то значение 0 , при котором достигаетсямаксимум критерия 1 .
Оно будет зависеть от значения 1 . Емубудут соответствовать значения 2 опт (1 , 0 ), 3 и решение опт (1 ,2 опт (1 , 0 опт (1 ) ), 0 опт (1 ) ).Оптимизация критерия () : выбор значения .Найденные значения 0 опт , 2 опт , 3 опт и опт будут зависеть отпараметра 1 . Согласно теории Куна-Таккера, для максимизациинашего основного критерия 0 () остается выбрать правильноезначение параметра 1 ≥ 0 . Этот параметр нужно выбрать так, чтобывыполнилось ограничение () ≥ . При том этот параметр можетбыть отличен от нуля только если неравенство по суммарнымденежным средствам переходит в равенство:52() = (6)При 1 = 0 в критерии 1 () денежные средства вообще неучитываются, и если при этом вырученных денежных средств хватает,то неравенство по деньгам выполнится автоматически. Если жеденежных средств не хватает, то следует увеличивать 1 , пока невыполнится равенство (6).
Вырученные денежные средства с ростом1 , во всяком случае, не убывают, так как величина () входит вкритерий 1 () все с большим весом. Если же при сколь угоднобольшом значении 1 денежных средств все равно не хватает, то задачавообще неразрешима. В нормальном случае перебором по 1 найдем тозначение 1 опт , при котором выполнится равенство (6). Соответственноопределятся значения 0 опт (1 опт ), 2 опт (1 опт , 0 опт ) и решениеопт (1 опт , 2 опт , 0 опт ), и задача будет решена полностью.Заметим, что если уже выбраны параметры 1 опт , 0 опт , 2 опт , и3 опт , то для заданного (–го) запроса определить, какие рекламныеобъявления должны показаться над результатами поиска по этомузапросу (определить опт ), можно не обращая внимания на другиезапросы. Для этого нужно:1) Вычислить значение = /0 опт + 1 опт ∙ ∙ − 2 оптдля всех рекламных объявлений (–ых), совместимых с даннымзапросом.2) Составить список кандидатов для показа.
В этот список поместитьтолько те рекламные объявления, для которых /0 опт + 1 опт ∙ ∙ > 2 опт .Этот список может быть и пустым.3) Если число кандидатов больше , то сократить список, оставив в немтолько объявлений с наибольшим значением .534) Подсчитать значение (1 опт , 2 опт ) = ∑( /0 опт + 1 опт ∙ ∙ − 2 опт ),()где сумма берется по рекламным объявлениям из списка кандидатов.5) Если эта величина меньше 3 опт , то обнулить список, и для данногозапроса не показывать рекламный блок над результатами поиска.Иначе показать все рекламные объявления из усеченного списка, т.е.положить опт = 1.
Остальные значения обнулить.В этой возможности определить опт , не обращая внимания надругие запросы, и есть смысл декомпозиции.2.3Формальное описание алгоритма подбора параметровкритерия показа.Теперь запишем общий алгоритм подбора параметров критерия показарекламных объявлений над результатами поиска.Обозначения в алгоритме: – общее число запросов; – общее количество рекламных объявлений-кандидатов на показ надрезультатами поиска; – максимальное допустимое покрытие, – минимальные денежные средства, которые должны бытьвыручены от показа рекламных объявлений над результатами поискапо нашей выборке запросов.Для каждого запроса и объявления-кандидата дано: – прогноз вероятности клика по рекламному объявлению – ставка рекламодателя по –тому рекламному объявлению.Цикл по (например от 0 вверх)54Вырученные денежные средства с ростом 1 не убывают, то есть можносказать что 1 – параметр, регулирующий поступление денежныхсредств от рекламодателей.Цикл по – общее количество показов рекламы над результатами поискапо всей выборке запросов.Цикл по Величина 2 регулирует количество показов в рекламномблоке по одному запросу.Цикл по запросам По всем объявлениям-кандидатам для запроса :Вычислить: = /0 + 1 ∙ ∙ − 2Если > , то включить пару (, ) в -ый список:Если в -ом списке объектов меньше чем , товключить объявление в список, иначепопытатьсявытеснитьхудшеепо ивставить -ое, а если текущее объявление хужевсех по критерию , то не включать его.Вычислить вклад в суммарный критерий объявлений,вошедших в список для показа: = ∑(по объявлениям,вошедших в список)Конец цикла по запросам .Упорядочить списки для запросов в порядке убывания .Оставить только первые из них (выполнениеограничения по покрытию), остальные обнулить (это в том55случае, если списков с рекламой хватает, в противномслучае оставить все списки).Запомнить = min ()Положить:1, = {0,если пара (, ) включена в список для показа,в противном случаеВычислить = ∑(,) , при этом величина будет зависеть от параметров (1 , 2 , 0 ).Менять , пока не будет достигнуто = 0 ± .Положить 2 опт = 2 .Запомнить 3 , 2 опт , списки (то есть объявления,отобранные для показа)Конец цикла по Вычислить1 (1 , 2 опт , 0 ) = ∑ ∙ (− 1 ∙ ( − ()))0(,)Менять , чтобы достигнуть max 10Положить 0 опт то значение 0,при котором достигнутmax 1 .0Запомнить 3 , 2 опт , 0 опт , ()Конец цикла по Менять пока () < Конец цикла по В конце работы алгоритма мы получаем четыре величины 1 опт , 0 опт ,2 опт и 3 опт , которые будут использоваться для работы с новымизапросами.562.4Работа с новыми запросами.Рассмотрим то, каким образом мы будем использовать полученныес помощью нашего алгоритма параметры 1 опт , 0 опт , 2 опт дляобработки нового запроса, поступившего от пользователя в системупоказов рекламных объявлений.Ранее было отмечено, что если данные параметры критерия показауже получены, то для каждого запроса из выборки запросов можноопределить, какие рекламные объявления должны быть показаны врекламном блоке над результатами поиска, не обращая внимания надругие запросы.
Мы рассчитываем на то, что используемая выборказапросов достаточно велика для того чтобы результат подборапараметров критерия показа мог быть применим в тех же условиях, вкоторых собиралась эта выборка. Тогда, в силу закона больших чисел,если мы будем применять те же правила к новым запросам, тоинтегральныекритерии–среднеезначениекликабельности,суммарные денежные средства и покрытие будут достаточно близки ктому, что было получено по выборке запросов. В то же времяпараметры были подобраны так, чтобы наш главный критерий –среднее значение по рекламным показам над результатами поискадостиг максимума при заданных ограничениях на суммарный доход ипокрытие. Поэтому и на новых данных с достаточной точностью всреднем критерий будет достигать максимума, а ограничениявыполняться.Итак, получив новый запрос нужно:1) Отобрать объявления-кандидаты для возможных показов (пофразам запроса).2) Для каждого из отобранных объявлений известно значениеставки и прогноз вероятности клика по объявлению ,где – индекс баннера, а – индекс запроса.573) Вычислитьзначение = /0 опт + 1 опт ∙ ∙ − 2 опт для всех полученных объявлений.4) Составить список кандидатов на показ над результатами поиска.В этот список для показа поместить только те объявления, длякоторых /0 опт + 1 опт ∙ ∙ > 2 опт .Этотсписок может быть и пустым (в этом случае над результатамипоиска не будет показано ни одного рекламного объявления).5) Если число кандидатов больше , то сократить список, оставив внем только объявлений с наибольшим значением .6) Подсчитать значение = ∑()( /0 опт + 1 опт ∙ ∙ − 2 опт ), где сумма берется по всем объявлениям изусеченного списка.7) Если эта величина меньше 3 опт , то обнулить список, и дляданного запроса не показывать никаких объявлений надрезультатами поиска.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
