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

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

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

Например, в [57] критерий показа надрезультатами поиска имеет вид: ∙ ∙ ∙ ≥ , гдедобавляется мультипликативный множитель – персональныйпризнак, обозначающий на сколько данный пользователь расположенкликатьнарекламувданныймоментпосравнениюсосреднестатистическим пользователем.Шестым в качестве критерия показа объявления в рекламныйблок рассматривались критерии вида ∙ . Данный вид критериядаёт достаточно большую степень свободы при отборе объявлений.Однако, ограниченность данного метода заключается в том, что ставкаи предсказанная кликабельность берутся именно в произведении однона другое. То есть ∙ при любых и – некоторая вероятностьсписания ставки за клик по объявлению, мы можем только усиливатьзависимость критерия показа либо от ставки данного объявления, либоот предсказанного объявления.Как видно из представленного обзора, тема критерия показарекламных объявлений над результатами поиска актуальна и широкоисследуется научным сообществом.

Также важно заметить, чтонекоторые авторы ставят оптимизационные задачи, однако врассмотренных работах есть некоторые ограничения и алгоритмыбольше эвристические и подходят только лишь к конкретнымпостановкам задачи оптимизации.Ни в одной из представленных в литературе работ не встречаетсяразработка модели показов рекламных объявлений, её математическое12описание и соответствующая математическая постановка задачиоптимизации рекламных показов и её решение.Цель и задачи исследованияЦель работы – математическая постановка задачи оптимизации иразработка алгоритма её решения.Задачи диссертационного исследования:1. Исследовать модель показов рекламных объявлений, провестианализ существующих подходов к отбору объявлений для показа,их ограничений и недостатков.2.

Разработать новую методику решения проблемы размещениярекламных объявлений над результатами поиска, а также наоснове разработанной методики поставить соответствующуюматематическую задачу оптимизации.3. Решить задачу оптимизации и получить алгоритм отбораобъявлений в рекламный показ. С помощью критериев,полученных с помощью алгоритма, научиться работать с новымипоисковыми запросами.4. Разработать программные средства для реализации полученногоалгоритма отбора и подбора его параметров.5. Провестиэкспериментальноетестированиеполученногоалгоритма на базе поисковой интернет-системы «Яндекс»,сделать выводы об эффективности выработанной методики, иполученного на её основе алгоритма, а также о наиболееперспективных направлениях её дальнейшей доработки иусовершенствования.Предмет и объект исследованияОбъект исследования: система показов рекламных объявлений настранице поисковой выдачи.13Предмет исследования: критерий показа рекламных объявлений вответ на поисковый запрос пользователя в сети ИнтернетНаучная новизна и практическая ценность.Научная новизна диссертационного исследования заключается вследующем: Разработана новая математическая модель показов рекламныхобъявлений над результатами поиска. Новая математическая модель учитывает дополнительныеограничения системы показов рекламных объявлений, а такжемаксимизирует выявленный показатель эффективности показов. По-новомусформулированнойматематическойзадачеоптимизации с помощью релаксации предложено решение спомощьюметодамножителейЛагранжа,особенностью которого являетсяхарактернойдекомпозиция целевойфункции. Получен новый критерий показа объявлений в рекламном блокенад результатами поиска.Положения, выдвигаемые на защиту.1.

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

Построен алгоритм нахождения параметров показа для выбраннойзадачи оптимизации рекламных показов.5. Применениеновоговидакритерияпоказалоповышениеэффективности и производительности системы рекламных показовпо итогам апробации в поисковой системе «Яндекс».Практическая ценность состоит в том, что на основе проведенныхисследований разработан алгоритм подбора параметров критерияпоказа рекламных объявлений над результатами поиска в современнойпоисковой интернет-системе (на примере системы Яндекс.Директ).Реализация данного подхода позволила повысить эффективностьработысистемыпризаданныхограничениях.Разработанныетеоретические положения и методики могут быть использованы и длядругих постановок задач оптимизации и других видах ограничений, втом числе позволяет использовать при отборе дополнительнуюинформацию про объявления, например такую как релевантностьзапросу или конверсионность (действие пользователя на сайтерекламодателя).Внедрение результатов диссертационного исследования в учебныйпроцесс в рамках курсов лекций и практических занятий подисциплинам «Современные методы анализа данных» и «Научныйсеминар«Анализинтернет-данных»позволилоповыситьтеоретический и практический уровень знаний студентов в областиметодов анализа интернет-данных на примере изучения механизмовпоказа рекламы в поисковых интернет-системах.Апробация и внедрение результатов исследования.15Основные результаты работы представлялись и получили одобрениена: Международной конференции International World Wide WebConferences 2013 (13-17 мая 2013, Рио-Де-Жанейро, Бразилия) спостером «Optimization of ads allocation in sponsored search». Конференции ACM SIGKDD 2012 (12-16 августа 2012, Пекин,Китай) с докладом на семинаре The Sixth International Workshop onData Mining for Online Advertising and Internet Economy на тему«Using boosted trees for click-through rate prediction for sponsoredsearch». Научных семинарах базовой кафедры Яндекс НИУ ВШЭ.По теме диссертационной работы опубликовано пять научныхработ [1], [2], [5], [19], [61], включая две статьи в изданиях из спискаизданий, рекомендованных ВАК РФ [1], [2].

В опубликованных статьяхотражено основное содержание диссертационной работы.Разработанный в диссертации алгоритм был реализован в онлайнсистемепоказоврекламыкомпании«Яндекс».Дляподбораоптимальных значений параметров критерия показа был реализованкомплекс программ, включающий в себя следующие компоненты:1) QueryPool.py – выбор из лога показов рекламных объявленийслучайного набора запросов необходимого размера. На входпрограммедаютсялогирекламныхпоказов:временнаяпоследовательность запросов пользователей, на которые былопоказано хотя бы одно рекламное объявление.

Пользовательскиезапросы нужны для того, чтобы собрать обучающий материал дляподбора оптимальных параметров.2) GetCandidatesForQuery.py – для каждого из запросов из базыданных рекламных объявлений выбираются соответствующие16ему объявления. Для каждого из запросов, которые были собраныпрограммой QueryPool.py , производятся следующие действия: Из запроса выделяются ключевые слова – слова, несущиеосновную смысловую нагрузку. Из ключевых слов (если их несколько) составляются ключевыефразы. По ключевым фразам из всего набора рекламных объявленийвыбираютсяименноте,которыеторгуютсяпосоответствующим фразам из запроса. Таким образом, длякаждого запроса отбираются соответствующие ему кандидатына показ в рекламном блоке над результатами поиска. Для каждого объявления-кандидата известна его ставка Bid ивычисляется предсказание вероятности клика CTR.В результате работы программы получается обучающий материалдля подбора оптимальных значений параметров порогов.3) OptimalThresholdParameters.py – реализация алгоритма подбораоптимальныхзначенийпараметровфункциипорогавзависимости от поставленной оптимизационной задачи.

На входпрограмма получает:a. Набор запросов с баннерами-кандидатами, для каждого изкоторых известны значения Bid и CTR, которые были полученыпредыдущей программой GetCandidatesForQuery.pyb. Критерий, который необходимо максимизироватьc. Ограничения поисковой системы.После того, как задана конкретная задача оптимизации сограничениями, выполняется поиск соответствующих значенийпараметров.Реализация комплекса программ была выполнена на языкепрограммирования Python.

Из-за больших объёмов данных (логов17показов рекламы, обучающего набора запросов и баннеров-кандидатовна показ) возникла необходимость использования распределённыхвычислений на MapReduce: вычисления оптимальных параметровпроисходят на порядок быстрее.Структура диссертационного исследования.Основной текст диссертации изложен на 138 страницах, состоитиз введения, четырёх глав, заключения, списка использованнойлитературы, состоящего из 74 наименований, и приложения,включающего в себя акты о внедрении.В первой главе строится математическая модель показов рекламыинаосновеанализанаучнойлитературыобосновываетсянеобходимость выработки новой модели, которая будет учитыватьограничения системы показов рекламы, а так же максимизироватьпоказатель эффективности рекламных показов.Также рассматривается структура рекламного блока и порядокего функционирования. В этой главе также говорится о развитииинтернет-рекламы,выделениипроблемыеёпоказовпередрезультатами поиска. В конце главы приводятся обзор научных трудовна данную тематику, и вытекающая постановка задачи исследования.Вторая глава посвящена математическому описанию моделипоказоврекламы,атакжеметодологическомуобоснованиюпостановки задачи оптимизации и построению нового алгоритмаподбора параметров критерия показа рекламных объявлений надрезультатам поиска.

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

Далее во второй главе представлена модификация исходного(базового) алгоритма, которая значительно упрощает его работу иинтерпретацию результатов его работы. В конце второй главыпредставлены результаты тестирования улучшенного алгоритма длякаждого из его этапов.Втретьейглаведиссертационногоисследованиярассматривается обобщение алгоритма подбора параметров критерияпоказа на предсказанную вероятность клика, зависящую от позиции, накоторую попадёт рекламное объявление.

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

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