Автореферат (1137262), страница 3
Текст из файла (страница 3)
В ходе решения был получен алгоритм подбора параметровправила показа. Теперь, когда мы получили вид правила, который однозначноопределяет, показывать объявление по запросу над результатами поиска или54.54CTR ∙ Bid3.53не отобралось2.52отобралось1.5отобралось но не показалось10.50-0.10.10.30.50.70.91.1CTRРис. 4. Отбор объявлений для показа по одному запросу.11нет, можно построить новую математическую модель рекламных показов. Этамодель учитывает ограничения системы рекламных показов и максимизируетпоказатель её эффективности (Рис.3.).В конце второй главы представлены результаты тестированиямодифицированного алгоритма на реальных данных, предоставленныхкомпанией «Яндекс».
Использовались данные показов рекламы на протяжениинедели за 25 – 31 января 2013 года, по ним выделялось случайно 105 запросов,для каждого из которых составлялся список соответствующих ему рекламныхобъявлений, для которых были известны их и .В работе продемонстрировано, как, согласно предложенному правилу,происходит отбор объявлений для показа на конкретный запрос (Рис.4.). Далеерассматривается процесс учета ограничения по суммарному доходу поисковойсистемы. После того как ограничение по доходу выполнено, алгоритмоптимизирует основной критерий: среднюю кликабельность всех рекламныхобъявлений, показавшихся над результатами поиска (Рис.5.).
Алгоритм находитмаксимум критерия и соответствующие ему параметры 1опт , 2опт и 3опт длядальнейшей работы с новыми запросами.В третьей главе диссертационного исследования говорится обобобщении разработанного метода получения правила показа напредсказанную вероятность клика, зависящую от позиции, на которую попадётрекламное объявление. Разница с базовым алгоритмом заключается в том, чтовероятность клика по объявлению зависит, помимо указанных выше факторов,от позиции, на которой оно показано: – оценка вероятности клика припоказе -ого объявления на -ой позиции рекламного блока в ответ на -ыйзапрос пользователя, при условии, что общее число объявлений, показанных врекламном блоке над результатами поиска, равно .
По аналогии с алгоритмомmax 0.1080.1060.104CTRavg0.1020.10.0980.0960.0940.0922опт0.09024681012141618202Рис. 5. Нахождение максимума средней кликабельности от параметра .12без позиционных эффектов вводятся бинарные переменные , выписываются ограничения из базовой задачи оптимизации и осуществляется самаматематическая постановка задачи.Решение оптимизационной задачи ведётся соответственно решениюбазовой задачи оптимизации, за исключением отбора рекламных объявлений напоказ для одного запроса.
Необходимо рассмотреть решение задачи вида:∑(,) ∙ → , где (1 , 2 , 0 ) = ⁄0 + 1 ∙ ∙ − 2 .Из-за ограничений, связанных с позиционностью, становится невозможным установление значения = 1, если > 0, и нулю иначе. Вматрице из любой строки и столбца можно выбрать не более одного элемента. По условию задачи оптимизации необходимо, чтобы сумма выбранныхэлементов была как можно больше. Эта задача решается стандартными методами, например с помощью Венгерского алгоритма.Был проведён численный эксперимент на модельных данных.№ эксперимента12345670.25 0.27 0.330.350.30.350.32(), %01263 1160 185227951195492814338_ ()1263 1145 185017955193672794320_ ()0̅̅̅̅̅̅0.49 0.37 0.300.180.170.460.45()̅̅̅̅̅̅ ()0.51 0.39 0.310.190.170.480.460̅̅̅̅̅̅ () − ̅̅̅̅̅̅()10.5 52.572.281.8535,273.1,%0̅̅̅̅̅̅()Табл.1.
Результаты вычислительных экспериментов.0̅̅̅̅̅̅ () – среднее значение при отборе базовым алгоритмом;̅̅̅̅̅̅ () – среднее значение по результатам алгоритма, учитывающего позиционные эффекты.0() и _ () – ожидаемый суммарный доход для базового и новогоалгоритмов соответственно. Алгоритм, учитывающий позиционные эффекты,практически всегда оказывается более эффективным на модельных данных посреднему позиционному , чем базовый алгоритм: в зависимости отхарактеристик модельных данных улучшение среднего позиционного составляет 2% – 10% (Табл. 1., Рис. 6.).В четвёртой главе приводятся результаты экспериментальноготестирования полученного правила показа и алгоритма получения егопараметров.
Была разработана и реализована схема оптимизации системыпоказов поисковой рекламы, рассмотрен каждый этап оптимизации отполучения данных для подбора оптимальных параметров до запускаэксперимента на реальных данных. Далее в работе представлены различныеварианты постановки задач оптимизации, которые могут быть решены с130.5100.460Среднийпозиционыый CTR0.4100.3600.3100.2600.210Алгоритм, учитывающийпозиционные эффектыАлгоритм без учетапозиционных эффектов0.160Номер эксперимента0.1100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30Рис. 6. Сравнение результатов работы базового и позиционного алгоритмов.использованием полученного в ходе диссертационного исследования видаправила показа рекламного объявления над результатами поиска.Как только вид задачи оптимизации определён, то необходимо подобратьпараметры правила показа: 1опт , 2опт и 3опт .
Система показов рекламныхобъявлений в интернет-системе «Яндекс» очень сложная, поэтому подборпараметров в режиме on-line на данном этапе и с учетом современныхтехнологических возможностей, мало возможен. В настоящее время алгоритмподбирает 1опт , 2опт и 3опт на наборе запросов, состоящим из 105 случайныхзапросов за неделю данных. Чтобы получить 1опт , 2опт и 3опт нужнопросмотреть весь набор запросов и соответствующих им объявленийкандидатов для показа над результатами поиска.В среднем на каждый запрос пользователя отбирается 50 объявленийкандидатов, для каждого из которых нужно вычислить = + 1опт ∙ ∙ − 2опт для применения правила показа.
Кликабельность объявления и его ставка уже известны. Таким образом, чтобы посчитать , нужно произвести всего лишь ряд элементарных математических операций.После того как весь рекламный блок для показа над результатами поискасформирован, для него считается суммарный критерий: = ∑ , которыйсравнивается с 3опт : если < 3опт , то рекламные объявления не показываются, иначе – показывается весь рекламный блок.Отметим, что для одного запроса отбор объявлений для показавыполняется за сотые доли секунды: это соответствует требованиямпроизводительности поисковой системы (необходим быстрый ответ на запроспользователя).14Для подбора значений 1опт , 2опт и 3опт был реализован комплекспрограмм, включающий в себя следующие компоненты:1.
QueryPool.py - выбор из набора показов рекламных объявлений случайногонабора запросов необходимого размера. На вход программе дается наборрекламных показов: временная последовательность запросов пользователей,на которые было показано хотя бы одно рекламное объявление.Пользовательские запросы нужны для того, чтобы собрать обучающийматериал для подбора параметров правила показа. За день в поисковуюсистему поступают миллионы запросов, это количество слишком великодля обучения, поэтому возникает необходимость выбрать 105 случайных изних за неделю данных, что и делает эта программа.2.
GetCandidatesForQuery.py – для каждого из запросов из базы данных рекламных объявлений выбираются соответствующие ему объявления. Длякаждого из запросов, которые были собраны программой QueryPool.py,производятся следующие действия: Из запроса выделяются ключевые слова – слова, несущие основнуюсмысловую нагрузку. Из ключевых слов (если их несколько) составляются ключевые фразы. По ключевым фразам из всего набора рекламных объявленийвыбираются именно те, которые поставили свои ставки для того чтобыпоказаться по этим ключевым фразам. Таким образом, для каждогозапроса отбираются соответствующие ему кандидаты для показа врекламном блоке над результатами поиска. Объявления-кандидаты определенным образом фильтруются (чтобы небыло повторяющихся объявлений, объявлений от одного рекламодателяи т.д.).В результате работы программы получается обучающий материал дляподбора параметров правил показа.3.
OptimalThresholdParameters.py – реализация алгоритма подбора значений параметров правила показа, в зависимости от поставленной оптимизационной задачи. В качестве входных данных выступают: Набор запросов с объявлениями-кандидатами, для каждого из которыхизвестны значения и , которые были получены предыдущейпрограммой GetCandidatesForQuery.py Максимизируемые показатели системы (например средняя кликабельность или суммарный доход). Ограничения поисковой системы (ими могут выступать средняякликабельность, суммарный доход поисковой системе, покрытиерекламой поисковых запросов, заполняемость рекламного блока назапрос пользователя, суммарное количество показов рекламныхобъявлений по набору запросов).15После того, как задана конкретная задача оптимизации с ограничениями,выполняется поиск соответствующих значений 1опт , 2опт и 3опт (Рис.2.).Полный цикл подбора параметров для набора запросов занимает от 6 до 9 часов(в зависимости от шага перебора 1 и 2 ).Реализация комплекса программ была выполнена на языке программирования Python.
Из-за больших объёмов данных (информации о показахрекламы, обучающего набора запросов и объявлений-кандидатов для показа назапрос) возникла необходимость использования распределённых вычисленийна MapReduce: вычисления параметров правила показа происходят на порядокбыстрее.Важно заметить, что данный комплекс программ позволяет подбиратьпараметры для правила показа для любой части поискового трафика(например, в конкретном географическом районе). Если возникнет задачаподбора параметров правила показа отдельно для регионов или для днейнедели, или ещё по каким-либо разделениям (по пользователям,рекламодателям, и т.п.), то это не представляется проблемой. Таким образом,программный комплекс является масштабируемым.После того, как значения параметров правила показа 1опт , 2опт и 3оптподобраны, необходимо запустить эксперимент на пользователяхпоисковой системы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
