Автореферат (1137262), страница 2

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

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

Разработана методология математической постановки задачи оптимизациипоказов рекламных объявлений, которая позволяет эффективно учитыватьсовокупность ключевых факторов, влияющих на основные показатели ихарактеристики системы показов рекламных объявлений.53. Предложено решение задачи оптимизации, которое позволило получитьновый вид правила показа рекламных объявлений над результатами поиска,характерной особенностью которого является независимость от другихобъявлений.4.

Построен алгоритм нахождения параметров правила показа для выбраннойзадачи оптимизации рекламных показов.5. Применение нового вида правила показа привело к повышениюэффективности и производительности системы рекламных показов поитогам апробации в поисковой системе «Яндекс».Апробация и внедрение результатов исследования. Основные результатыработы представлялись и получили одобрение на: Международной конференции International World Wide Web Conferences2013 (13-17 мая 2013, Рио-Де-Жанейро, Бразилия) с постером «Optimizationof ads allocation in sponsored search». Международной конференции ACM SIGKDD 2012 (12-16 августа 2012,Пекин, Китай) с докладом «Using boosted trees for click-through rate predictionfor sponsored search». Научных семинарах базовой кафедры Яндекс НИУ ВШЭ.По теме диссертационной работы опубликовано шесть научных работ,включая три статьи в изданиях из списка изданий, рекомендованных ВАК РФ.Разработанный в диссертации алгоритм был реализован в онлайн-системепоказов рекламы компании «Яндекс».Структура диссертации.

Основной текст диссертации изложен на 137страницах, состоит из введения, четырёх глав, заключения, спискаиспользованной литературы, состоящего из 74 наименований, и приложения,включающего в себя акты о внедрении.I. ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫВо введении обоснована актуальность темы диссертационногоисследования, сформулированы цели и задачи работы, определены еетеоретическая и практическая значимость, приведены сведения обэкспериментальном тестировании и внедрении его результатов, о структуредиссертации и о публикациях по теме диссертации.В первой главе строится математическая модель системы показов рекламыв интернет-системах и на основе анализа научной литературы обосновываетсянеобходимость выработки нового правила отбора рекламных объявлений,которое будет учитывать ограничения системы показов рекламы, а такжемаксимизировать показатель эффективности рекламных показов.Для решения этой задачи необходимо определить основные показателисистемы показов рекламных объявлений над результатами поиска.

Рекламноеобъявление характеризуется двумя основными параметрами. Первый – этовероятность того, что пользователь кликнет на предъявленное объявление(кликабельность – , − − ). Можно сказать, что это –6степень «эффективности» показа объявления, характеристика его привлекательности для пользователя. Второй параметр – это ставка(), назначеннаярекламодателем за клик по его рекламному объявлению.В работе были выделены следующие основные характеристики показоврекламных объявлений над результатами поиска в ответ на запроспользователя: Средняя кликабельность – показатель, описывающий, насколько часто всреднем пользователь кликает на рекламные объявления.

Можно сказать,что этот показатель определяет «удовлетворённость» пользователя. Если этавеличина мала, то пользователь либо перестанет кликать по рекламе, либобудет искать другие способы поиска информации в интернете. Ни один изэтих вариантов поведения пользователя не удовлетворяет потребностямпоисковой системы. Суммарный доход – суммарные денежные средства, списываемые со счетов рекламодателей (суммарный доход поисковой интернет-системы отпоказов рекламы на страницах поисковой выдачи). Покрытие – количество запросов, в отношении которых страница поисковых результатов содержит хотя бы одно рекламное объявление надрезультатами поиска. Заполняемость – максимальное количество рекламных объявлений, одновременно показанных в рекламном блоке над результатами поиска.В диссертационном исследовании при построении новой модели рекламныхпоказов ставится задача максимизации средней кликабельности (), ивводятся ограничение снизу на суммарный доход поисковой системы иограничения сверху на покрытие и на заполняемость.Во второй главе приводится математическое описание модели показоврекламы (Рис.1.).

Далее ставится задача оптимизации и приводится её решение,а также осуществляется построение нового правила показа рекламных объявлений над результатами поиска.Для постановки задачи оптимизации обозначим: − множество запросов, − множество объявлений, – индекс запроса в множестве (1 ≤ ≤ ||), – индекс рекламного объявления в множестве (1 ≤ ≤ | |), ≥ 0 – ставка объявления , – оценка вероятности клика по –у объявлению, показанному надрезультатами поиска на –ый запрос.Величины и считаем заданными.

– бинарная переменная, обозначающая что –е объявление показано надрезультатом поиска на –ый запрос.Поиск оптимальных значений является центральным предметом рассмотрения в диссертационной работе. Обозначим все искомые переменные 7как матрицу . = ∑(,) – общее количество показов рекламныхобъявлений по данной выборке запросов над результатами поиска, а () = ∑(,) ∙ / ∑(,) (1)– среднее значение по этим объявлениям.

Задача состоит в том, чтобымаксимизировать эту величину при заданных ограничениях.Ограничение на суммарный доход. Ожидаемый доход от показа объявления по запросу будет равен ∙ , тогда суммарный доход поисковойсистемы можно записать в виде:() = ∑(,) ∙ ∙ ≥ .(2)Ограничение на покрытие. Напомним, что «покрытием» называетсяколичество запросов, по которым в рекламном блоке над результатами поискапоказано хотя бы одно рекламное объявление.

Выражение {∑() > 0} равно1, если над результатом поиска размещено хотя бы одно объявление, и 0 иначе. – индикаторная функция. Тогда ограничение на покрытие примет вид:() = ∑()({∑() > 0}) ≤ .(3)Ограничение на заполняемость – число объявлений, размещаемых надкаждым результатом поиска, оно не должно превышать :∀ ∑() ≤ .(4)Описание задачи оптимизации.Задача ставится следующим образом: максимизировать по бинарнымпеременным функцию () = ∑(,) ∙ / ∑(,) (5)при ограничениях:∑ ∙ ≥ ,(,)∑() {∑(): ∑ > 0} ≤ ,() ≤ .Теперь приступим к решению задачи оптимизации.Правило показа∀ , :Показрекламныхобъявлений = { }∀ : Рис. 1. Математическая модель показов рекламных объявлений.8Решение задачи оптимизации.Для решения задачи оптимизации были предприняты следующие действия:1. Релаксация переменных на непрерывные: 0 ≤ ≤ 1.2.

Применение метода множителей Лагранжа: переведем в критерий (1) (спомощью множителя Лагранжа 1 ≥ 0) ограничение (2), которое запишем ввиде − () ≤ 0. Получим Лагранжиан:() =∑(,) ∙∑(,) − 1 ( − ()).3. Чтобы добиться декомпозиции () на сумму слагаемых, зафиксируемзнаменатель = ∑(,) дополнительным ограничением =0 , где 0 – некоторая положительная константа. Переведем с помощьюмножителя Лагранжа и новое дополнительное ограничение в критерий.Получим:∗ () =∑(,) ∙ 0− 1 ∙ ( − ∑ ∙ ) − 2 ∙ ( ∑ − 0 ). (6)(,)(,)4. Произведём декомпозицию: объединяя члены суммы, зависящие от , ивынося за скобки , получим:∗ () = ∑ ∙ (+ 1 ∙ ∙ − 2 ) + .0(,)Видим, что полученный критерий, действительно, представляет собой суммуфункций, каждая из которых линейно зависит только от переменной .

Этозначит, что правило показа для каждого объявления не зависит от другихобъявлений.Теперь найдем максимум критерия (6) по переменным с учетомтолько ограничения 0 ≤ ≤ 1. Обозначим (1 , 2 , 0 ) коэффициент при : (1 , 2 , 0 ) = /0 + 1 ∙ ∙ − 2 . Тогда кандидатамина показ будут те объявления, для которых > 0. Таким образом, линейнаяфункция (1 , 2 , 0 ) является новым правилом показа рекламногообъявления над результатами поиска.Теперь учтем ограничение на количество объявлений в рекламномблоке (4): оставляем кандидатов с максимальным значением (1 , 2 , 0 ).Остается ограничение на покрытие (3). Обозначим (1 , 2 , 0 ) вклад вкритерий (6) для каждого запроса от объявлений, отобранных для показа (1 , 2 , 0 ) = ∑() (+ 1 ∙ ∙ − 2 ) .

Максимум критерия (6)0будет достигнут, если мы оставим запросов с наибольшим значением (1 , 2 , 0 ). Обозначим = min (1 , 2 ), тогда условием показарекламы по запросу будет (1 , 2 ) ≥ 3 .Таким образом, был получен новый вид правила показа рекламногообъявления над результатами поиска.9В работе построен алгоритм подбора параметров правила показа 1 опт ,2 опт , 3 опт и 0 опт (Рис. 2.).Подобранные параметры будут использоваться для работы с новымизапросами. Эта работа осуществляется согласно следующему алгоритму:1) Вычислить значение = /0 опт + 1 опт ∙ ∙ − 2 опт длявсех объявлений-кандидатов на показ по запросу .Отобрать кандидатовдля показа на запрос пользователя для которых > 0.2) Сократить кандидатов до с наибольшими значениями .

Эти объявлениябудут составлять список для показа.3) Подсчитать = ∑() , для всех объявлений из списка для показа.4) Если < 3 опт , то для данного запроса не показывать объявлений надрезультатами поиска. В противном случае показать все объявления изсписка для показа.Перебор значений 1 до достижения равенства() = Перебор значений 0 (при фиксированном 1 )с целью максимизации критерия:() = ∑ ∙ (− 1 ∙ ( − () )0(,)Перебор значений 2 (при фиксированном 1 и 0 )до достижения равенства: = ∑ = 0(,)Решение задачи оптимизации критерия∗ () = ∑ ∙ ( /0 + 1 ∙ ∙ − 2 )(,)при фиксированных значениях 1 , 2 и 0Получение значений матрицы и соответствующих значений и 31 опт , 2 опт , 3 опт и 0 оптРис.

2. Алгоритм подбора параметров правила показа.10Правило показа= + 1 ∙ ∙ − 2max Показрекламныхобъявлений = { }∀ , : ≥ ≤ ∀ : ≤ Параметры управления показами:1 , 2 и 3Рис. 3. Новая модель показов рекламы над результатами поиска.Алгоритм отбора определяет: показывать ли по новому запросу объявления?Если да, то какие конкретно объявления следует показывать из всех объявлений-кандидатов на показ?Далее в работе представлена модификация базового алгоритма,позволяющая ускорить его работу с помощью устранения перебора по 0 . Вработе представлено формальное описание модифицированного алгоритма, атакже доказательство эквивалентности между ним и базовым алгоритмом.Таким образом, описана математическая постановка задачи оптимизации,приведено её решение, а также выявлен вид правила показа = + 1 ∙ ∙ − 2 .

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

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