автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Оптимизация показов рекламных объявлений в поисковых интернет-системах

На правах рукописи

Сорокина Анна Николаевна

ОПТИМИЗАЦИЯ ПОКАЗОВ РЕКЛАМНЫХ ОБЪЯВЛЕНИЙ В ПОИСКОВЫХ ИНТЕРНЕТ-СИСТЕМАХ: РАЗРАБОТКА МЕТОДОЛОГИИ ПОДБОРА ПОРОГОВ ВХОДА В РЕКЛАМНЫЙ ПОКАЗ

Специальность 05.13.18 -«Математическое моделирование, численные методы и комплексы программ»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва-2015

ь АБГ 2015

005571317

Работа выполнена в Федеральном государственном автономном образовательном учреждении высшего профессионального образования Национальном Исследовательском Университете «Высшая Школа Экономики».

Научный руководитель: Цитович Иван Иванович,

доктор физико-математических наук, профессор базовой кафедры Яндекс НИУ ВШЭ.

Официальные оппоненты: Степанов Сергей Николаевич,

доктор технических наук,

профессор кафедры Сети связи и системы

коммутации ФГОБУ ВПО МТУСИ.

Гайдамака Юлия Васильевна,

кандидат физико-математических наук, доцент кафедры прикладной информатики и теории вероятностей ФГАО ВО РУДН.

Ведущая организация: Федеральное государственное учреждение

«Федеральный исследовательский центр "Информатика и управление" Российской академии наук» (ФИЦ ИУ РАН). Защита состоится 28 сентября 2015 г. в 14 часов на заседании Диссертационного совета Д 002.226.01 при Федеральном государственном бюджетном учреждении науки Институте проблем управления им. В. А. Трапезникова РАН, по адресу: 117997, Москва, ул. Профсоюзная, д. 65.

С диссертацией можно ознакомиться в библиотеке ИПУ РАН и на официальном сайте http://vvww.ipu.ru/.

Автореферат разослан «_»_2015 г.

Ученый секретарь ф-ОЪе^и*— Кочетков С. А.

диссертационного совета Д 002.226.01 г

доктор технических наук

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования. Сегодня огромная аудитория пользуется интернетом для поиска информации. Как правило, интернет-пользователь задает поисковый запрос, на который он хочет получить ответ, и задача поисковых систем — отвечать на эти запросы наиболее полно и точно. Чтобы иметь доход от предоставления информации пользователям в ответ на их запросы, поисковая система использует рекламные объявления от рекламодателей, которые показываются на странице результатов поиска. Рекламные объявления могут размещаться в различных местах страницы поисковых результатов. В диссертационном исследовании рассматривается блок рекламных объявлений, который визуально располагается над результатами поиска на интернет-странице. Клик пользователя по рекламному объявлению, расположенному в этом рекламном блоке, приносит поисковой интернет-системе доход. Оптимальный отбор рекламных объявлений для показа пользователю - важная практическая задача для современных поисковых интернет-систем. Решение данной задачи в интересах и других сторон. Рекламодатели нуждаются в привлечении клиентов, а пользователи заинтересованы в соответствующей их запросу информации, даже если она получена из рекламных объявлений.

В научной литературе проблематика определения наилучшего правила показа рекламного объявления (иными словами, правила отбора объявлений для показа пользователю в ответ на его поисковый запрос) стала активно изучаться последние 10-15 лет. Над проблемой работали многие учёные: Choul W. L., Agarwal D. К., Broder A. Z., Ciaramita M., Lacerda A., Ghose A., Zhang W. V., Schroedl S., Lahaie S., Radlinski F., Chakrabarti D„ Dembczynski K., Regelson M., Richardson M., Feng J., Joachims T., Granka L., Herbrich R., Liu T. Y., Zhu Y. Graepel T., Sheth А. и др. Большинство авторов при рассмотрении данной проблемы фокусируется на задаче определения и обоснования такого правила показа, которое демонстрировало бы наибольшую эффектив-

ность в конкретных случаях, не предлагая глубокого концептуального и математического обоснования того или иного правила.

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

Цель работы: разработка, программная реализация и внедрение нового правила показа рекламных объявлений в поисковой интернет-системе. Задачи диссертационного исследования:

1. Исследовать систему показов рекламных объявлений на странице результатов поиска в современных поисковых интернет-системах, провести анализ существующих подходов к отбору объявлений для показа, их ограничений и недостатков.

2. Разработать новую модель отбора рекламных объявлений для показа над результатами поиска на странице результатов в поисковой интернет-системе,

а также на основе разработанной модели поставить соответствующую математическую задачу оптимизации.

3. На основе решения математической задачи оптимизации получить новое правило показа рекламных объявлений над результатами поиска, а также алгоритм подбора параметров правила показа.

4. Разработать программные средства для реализации полученного алгоритма отбора рекламных объявлений для показа.

5. Провести экспериментальное тестирование полученного алгоритма на базе современной поисковой интернет-системы «Яндекс», оценить эффективность выработанной методики, и полученного на её основе правила показа, а также выделить наиболее перспективные направления её дальнейшей доработки и усовершенствования.

Теоретико-методологическую основу исследования составляют теория оптимизации, теория алгоритмов, теория вероятностей и математическая статистика.

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

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

2. На основе разработанной математической модели автором предложена новая формулировка математической задачи оптимизации рекламных показов и предложено ее оригинальное решение, которое основывается на

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

результатов в поисковой интернет-системе в ответ на запрос пользователя. Теоретическая значимость исследования: Теоретически обоснована и построена математическая модель показов рекламы и осуществлена постановка задачи оптимизации показов рекламных объявлений, а также предложен алгоритм отбора объявлений в рекламный показ, соответствующий решению задачи оптимизации. Разработан и описан новый вид правила показа рекламных объявлений над результатами поиска. В ходе исследования выработан алгоритм отбора, который в дальнейшем применялся для работы с новыми запросами пользователей. Предложены теоретические основания для расширения разработанного алгоритма отбора рекламных объявлений в целях учета позиционного эффекта внутри рекламного блока, показываемого на странице результатов в поисковой интернет-системе в ответ на запрос пользователя. Практическая значимость состоит в том, что на основе проведенного исследования разработан алгоритм подбора параметров правила показа рекламных объявлений над результатами поиска в поисковых интернет-системах (на примере системы «Яндекс»). Реализация данного подхода позволила на практике повысить эффективность работы системы при заданных ограничениях. Разработанные теоретические положения и методики могут быть использованы и для других постановок задач оптимизации, а также для других видов ограничений применительно к различным практическим задачам.

Внедрение результатов диссертационного исследования в учебный процесс в рамках курсов лекций и практических занятий по дисциплинам «Современные методы анализа данных» и «Научный семинар «Анализ интер-нет-данных»» позволило повысить теоретический и практический уровень знаний

студентов в области методов анализа иитернет-данных на примере изучения

принципов и механизмов показа рекламы в поисковых интернет-системах.

Положения, выносимые на защиту:

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

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

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

4. Построен алгоритм нахождения параметров правила показа для выбранной задачи оптимизации рекламных показов.

5. Применение нового вида правила показа привело к повышению эффективности и производительности системы рекламных показов по итогам апробации в поисковой системе «Яндекс».

Апробация и внедрение результатов исследования. Основные результаты

работы представлялись и получили одобрение на:

- Международной конференции International World Wide Web Conferences 2013 (13-17 мая 2013, Рио-Де-Жанейро, Бразилия) с постером «Optimization of ads allocation in sponsored search».

- Международной конференции ACM SIGKDD 2012 (12-16 августа 2012, Пекин, Китай) с докладом «Using boosted trees for click-through rate prediction for sponsored search».

- Научных семинарах базовой кафедры Яндекс НИУ ВШЭ.

По теме диссертационной работы опубликовано шесть научных работ, включая три статьи в изданиях из списка изданий, рекомендованных ВАК РФ.

Разработанный в диссертации алгоритм отбора для показа рекламных объявлений был реализован в онлайн-системе показов рекламы компании «Яндекс». Структура диссертации. Основной текст диссертации изложен на 137 страницах, состоит из введения, четырёх глав, заключения, списка использованной литературы, состоящего из 74 наименований, и приложения, включающего в себя акты о внедрении.

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

В первой главе строится математическая модель системы показов рекламы в интернет-системах и на основе анализа научной литературы обосновывается необходимость выработки нового правила показа рекламных объявлений, которое будет учитывать ограничения системы показов рекламы, а также максимизировать показатель эффективности рекламных показов.

Для решения этой задачи необходимо определить основные показатели системы показов рекламных объявлений над результатами поиска. Рекламное объявление характеризуется двумя основными характеристиками. Первая - это вероятность того, что пользователь кликнет на предъявленное объявление (кликабельность - CTR, Click — Through — Rate). Можно сказать, что это -степень «эффективности» показа объявления, характеристика его привлекательности для пользователя. Вторая характеристика - это ставка(ВШ), назначенная рекламодателем за клик по его рекламному объявлению.

В работе были выделены следующие основные характеристики системыпоказов рекламных объявлений над результатами поиска в ответ на запрос пользователя:

• Средняя кликабелыюсть - показатель, описывающий, насколько часто в среднем пользователь кликает на рекламные объявления. Можно сказать, что этот показатель определяет «удовлетворённость» пользователя. Если эта величина мала, то пользователь либо перестанет кликать по рекламе, либо будет искать другие способы поиска информации в интернете. Ни один из этих вариантов поведения пользователя не удовлетворяет потребностям поисковой системы.

• Суммарный доход - суммарные денежные средства, списываемые со счетов рекламодателей (суммарный доход поисковой интернет-системы от показов рекламы на страницах поисковой выдачи).

• Покрытие - количество запросов, в отношении которых страница поисковых результатов содержит хотя бы одно рекламное объявление над результатами поиска.

• Заполняемость - максимальное количество рекламных объявлений, одновременно показанных в рекламном блоке над результатами поиска.

В диссертационном исследовании при построении новой модели рекламных показов ставится задача максимизации средней кликабельности (СТК), и вводятся ограничение снизу на суммарный доход поисковой системы и ограничения сверху на покрытие и на заполняемость.

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

Для постановки задачи оптимизации обозначим: (2 — множество запросов, А — множество объявлений, ^ - индекс запроса в множестве (1 < q < |(?|),

9

а - индекс рекламного объявления в множестве А (1 < а < \А |), Bida > 0 - ставка объявления a, CTRaq - оценка вероятности клика по а-у объявлению, показанному над результатами поиска на q-ый запрос. Величины Bida и CTRaq считаем заданными.

taq - бинарная переменная, обозначающая что а-е объявление показано над результатом поиска на q-ый запрос.

Поиск оптимальных значений taq является центральным предметом рассмотрения в диссертационной работе. Обозначим все искомые переменные taq как матрицу Т. Events = 2¡(a,g) taq - общее количество показов рекламных объявлений по данной выборке запросов над результатами поиска, а

CTRavg(T) = ~Z(a,q) CTRaq • taq/Y,(a,q) ¿aq (1)

- среднее значение CTR по показанным объявлениям. Задача состоит в том, чтобы максимизировать эту величину при заданных ограничениях. Ограничение па суммарный доход. Ожидаемый доход от показа объявления а по запросу q будет равен Bida • CTRaq, тогда ограничение на суммарный доход поисковой системы можно записать в виде:

М{Т) = Zca,q) Bida ■ CTRaq ■ taq > Mmin. (2)

Ограничение на покрытие. Напомним, что «покрытием» называется количество запросов, по которым в рекламном блоке над результатами поиска показано хотя бы одно рекламное объявление. Для каждого запроса выражение l{S(a) faq > о} равно 1, если над результатом поиска показано хотя бы одно объявление, и 0 иначе. П - индикаторная функция. Тогда ограничение на покрытие примет вид:

HitsiT) = £(,)№(«) ta, > 0}) < Hitmax. (3)

Ограничение на наполняемость - число объявлений, размещаемых над каждым результатом поиска, оно не должно превышать к:

V<7 2(a) t-aq < к. (4)

Рис. 1. Математическая модель показов рекламных объявлений. Описание задачи оптимизации. Задача оптимизации ставится следующим образом: максимизировать по бинарным переменным taq функцию

(Т) = Z(a,q) CTRaq ' ^aq/^a.q) taq (5)

при ограничениях:

^ Bida ■ CTRaq ■ taq > Mmin, (a,q)

Zc^^Zfa)^4 > 0j - HitmaX'

taq ^ k.

¿-J (a)

Теперь приступим к решению задачи оптимизации.

Решение задачи оптимизации.

Для решения задачи оптимизации были предприняты следующие действия:

1. Релаксация переменных taq на непрерывные: 0 < taq < 1.

2. Применение метода множителей Лагранжа: переведем в критерий (1) (с помощью множителя Лагранжа Л1 > 0) ограничение (2), которое запишем в виде Mmln — М(Т) < 0. Получим Лагранжиан:

Х(Г) = £(°' fTRfaq - h{Mmin - М(Г)).

2.(a,q) Laq

3. Чтобы добиться декомпозиции £(7*)на сумму слагаемых, зафиксируем знаменатель Events — S(a,<7) taq дополнительным ограничением Events = Е0,

где Е0 - некоторая положительная константа. Переведем с помощью множителя Лагранжа и новое дополнительное ограничение в критерий:

£,(т) = Z(a.4)CTRaq-taq _ ^ I ^ _ ^ ctr^ . Сач j _ д2. | ^ taq - £„ ]. (6)

° V (a.«) J \ia.q) J

4. Произведём декомпозицию: объединяя члены суммы, зависящие от taq, и вынося за скобки taq, получим:

Z/CTRaa \

taq ■ (—Y3- + Я1 • Bida " CTRaq ~ ¿2 1 + COUSt. (a,q) °

Видим, что полученный критерий, действительно, представляет собой сумму функций, каждая из которых линейно зависит только от переменной taq. Это значит, что правило показа для каждого объявления не зависит от других объявлений.

Теперь найдем максимум критерия (6) по переменным taq с учетом только ограничения 0 < taq < 1. Обозначим Faq(A1,A2,E0') коэффициент при taq- Faq(A1,A2,E0') = CTRaq/E0 + • Bida ■ CTRaq — Я2. Тогда кандидатами на показ будут те объявления, для которых Faq > 0. Таким образом, линейная функция Faq(A1,A2,E0) является новым правилом показа рекламного объявления над результатами поиска.

Теперь учтем ограничение на количество объявлений в рекламном блоке (4): оставляем к кандидатов с максимальным значением Faq(A1,A2,E0). Остается ограничение на покрытие (3). Обозначим Rq(A1,A2,E0) вклад в критерий (6) для каждого запроса от объявлений, отобранных для показа Rq(A1,A2,E0) = Z(a) ("J"" + Аг •Bida • CTRaq — Я2). Максимум критерия (6)

будет достигнут, если мы оставим Hitmax запросов с наибольшим значением Rq(A1,A2,E0). Обозначим А3 = minHitmaxRq(A1,A2~), тогда условием показа рекламы по запросу q будет Rq(A1,A2) > А3.

Таким образом, был получен новый вид правила показа рекламного объявления над результатами поиска.

В работе построен алгоритм подбора параметров правила показа А1 опт, опт» опт н Е0 опт (Рис. 2.).

Подобранные параметры будут использоваться для работы с новыми запросами. Эта работа осуществляется согласно следующему алгоритму:

1) Вычислить значение Faq = CTRaq/E0om + Л1опт • Bida ■ CTRaq - А2от для всех объявлений-кандидатов для показа по запросу q.Отобрать кандидатов для показа на запрос пользователя для которых Faq > 0.

2) Сократить кандидатов до к с наибольшими значениями Faq. Эти объявления

будут составлять список для показа.

Рис. 2. Алгоритм подбора параметров правила показа.

Рис. 3. Новая модель показов рекламы над результатами поиска. 3) Подсчитать Rq = £(а) для всех объявлений из списка для показа.

4) Если Rq < Л3 опт, то для данного запроса не показывать объявлений над результатами поиска. В противном случае показать все объявления из списка для показа.

Алгоритм отбора определяет: показывать ли по запросу объявления? Если да, то какие конкретно объявления следует показывать из всех объявлений-кандидатов для показа?

Далее в работе представлена модификация базового алгоритма, позволяющая ускорить его работу с помощью устранения перебора по Е0. В работе представлено формальное описание модифицированного алгоритма, а также доказательство эквивалентности между ним и базовым алгоритмом.

Таким образом, описана математическая постановка задачи оптимизации рекламных показов, приведено её решение, а также выявлен вид правила показа Faq = CTRac¡ + Л1 ■ Bida ■ CTRaq — Л2 . В ходе решения задачи оптимизации был получен алгоритм подбора параметров правила показа. Теперь, когда мы получили вид правила, который однозначно определяет, показывать объявление по запросу над результатами поиска или нет, можно построить новую математическую модель рекламных показов. Эта модель учитывает

5

4.5 ■

4

3.5 ■о 3 со к2-5 ■ ♦ не отобралось

Ь 2 ■ _ отобралось

1.5 ▲ отобралось но не показалось

1 А.

0.5 ♦ ♦ ♦

0

•0.1 0.1 0.3 0.5 0.7 ста 0.9 1.1

Рис. 4. Отбор объявлений для показа по одному запросу, ограничения системы рекламных показов и максимизирует показатель её

эффективности (Рис.3.).

В конце второй главы представлены результаты тестирования нового вида правила показа рекламных объявлений, а также модифицированного алгоритма на реальных данных, предоставленных компанией «Яндекс». Использовались данные показов рекламы на протяжении недели за 25 - 31 января 2013 года, по ним выделялось случайно 105 запросов, для каждого из которых составлялся список соответствующих ему рекламных объявлений, для которых были известны их СТ11ас1 и ЕИс1а.

В работе продемонстрировано, как, согласно предложенному правилу, происходит отбор объявлений для показа на конкретный запрос (Рис.4.). Далее рассматривается процесс учета ограничения на суммарный доход поисковой системы. После того как ограничение по доходу выполнено, алгоритм оптимизирует основной критерий: среднюю кликабельность всех рекламных объявлений, показавшихся над результатами поиска (Рис.5.). Алгоритм находит максимум средней кликабельности и соответствующие ему параметры А1опт, Я2оПт и А-зопт Для дальнейшей работы с новыми запросами.

гпах СТЯ^д

♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦♦

Л-20ПТ

О 2 4 6 8 10 12 14 16 18 20

Л2

Рис. 5. Нахождение максимума средней кликабельности от параметра Я2.

В третьей главе диссертационного исследования говорится об обобщении разработанного метода получения правила показа на предсказанную вероятность клика, зависящую от позиции, на которую попадёт рекламное объявление. Разница с базовым алгоритмом заключается в том, что вероятность клика по объявлению зависит, помимо указанных выше факторов, от позиции, на которой оно показано: СТЯачрк - оценка вероятности клика при показе а-ого объявления на к-ой позиции рекламного блока в ответ на q-ъm запрос пользователя, при условии, что общее число объявлений, показанных в рекламном блоке над результатами поиска, равно р. По аналогии с алгоритмом без позиционных эффектов вводятся бинарные переменные taqpk, выписываются ограничения из базовой задачи оптимизации и осуществляется сама математическая постановка задачи.

Решение оптимизационной задачи ведётся соответственно решению базовой задачи оптимизации, за исключением отбора рекламных объявлений для показа по одному запросу. Необходимо рассмотреть решение задачи вида: Е(а.Ч) раЧРк ■ £аарк *т , где Е0 ) = СТЯацрк/Е0 + Л1 ■ ЕИс1а ■ СТЯачрк — Л2.

Из-за ограничений, связанных с позиционностью, становится невозможным установление значения = 1, если Радрк > 0, и нулю иначе. В матрице Т из любой строки и столбца можно выбрать не более одного элемента. По условию задачи оптимизации необходимо, чтобы сумма выбранных элементов была как можно больше. Эта задача решается стандартными методами, например с помощью Венгерского алгоритма.

Был проведён численный эксперимент на модельных данных.

№ эксперимента 1 2 3 4 5 6 7

//¿^(Г), % 0.25 0.27 0.33 0.35 0.3 0.35 0.32

1263 1160 18522 7951 19549 281 4338

1263 1145 18501 7955 19367 279 4320

С77?£0Х(Г) 0.49 0.37 0.30 0.18 0.17 0.46 0.45

СТЯров{Т) 0.51 0.39 0.31 0.19 0.17 0.48 0.46

10.5 5 2.57 2.28 1.853 5,27 3.1

Табл.1. Результаты вычислительных экспериментов.

СГДр05(7') — среднее значение СТЙа(1рк при отборе базовым алгоритмом; СГЙр05(Т) - среднее значение СТЯачрк по результатам алгоритма, учитывающего позиционные эффекты.

М°оро5(Т) и Мпоро5(Т) - ожидаемый суммарный доход для базового и нового алгоритмов соответственно. Алгоритм, учитывающий позиционные эффекты, практически всегда оказывается более эффективным на модельных данных по среднему позиционному СТИ, чем базовый алгоритм: в зависимости от характеристик модельных данных улучшение среднего позиционного СТЯ составляет 2% - 10% (Табл. 1., Рис. 6.).

В четвёртой главе приводятся результаты экспериментального тестирования полученного правила показа и алгоритма получения его параметров. Была разработана и реализована схема оптимизации системы

0.510 0.460 0.410 0.360 0.310 0.260 0.210 0.160 0.110

Средний »

позиционыый СТ1? .\

Г^ \

гГ^ \

< Алгоритм, учитывающий \

позиционные эффекты \

Алгоритм без учета \

позиционных эффектов

Номер эксперимента

О 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опт и Л-зопт- Система показов рекламных объявлений в интернет-системе «Яндекс» очень сложная, поэтому подбор параметров в режиме on-line мало возможен. В настоящее время алгоритм подбирает Я1опт, Я2опт и Я3опт на наборе запросов, состоящим из 105 случайных запросов за неделю данных. Чтобы получить Я1опт, Я2опт и Я3опт нужно просмотреть весь набор запросов и соответствующих им объявлений-кандидатов для показа над результатами поиска.

В среднем на каждый запрос пользователя отбирается 50 объявлений-кандидатов, для каждого из которых нужно вычислить Faq — CTRaq + Я1опт ■ Bida ■ CTRaq ~ А-2опт Для применения правила показа. Кликабельность объявления CTRaq и его ставка Bida уже известны. Таким образом, чтобы посчитать

Рщ, нужно произвести всего лишь ряд элементарных математических операций. После того как весь рекламный блок для показа над результатами поиска сформирован, для него считается суммарный критерий: = £ , который сравнивается с Азопт: если <^зопт> т0 рекламные объявления не показываются, иначе - показывается весь рекламный блок.

Отметим, что для одного запроса отбор объявлений для показа выполняется за сотые доли секунды: это соответствует требованиям производительности поисковой системы (необходим быстрый ответ на запрос пользователя).

Для подбора значении Я^опт, А20ПТ '' ^зопт был реализован комплекс программ, включающий в себя следующие компоненты:

1. (ЗиегуРооЬру - выбор из набора показов рекламных объявлений случайного набора запросов необходимого размера. На вход программе дается набор рекламных показов: временная последовательность запросов пользователей, на которые было показано хотя бы одно рекламное объявление. Пользовательские запросы нужны для того, чтобы собрать обучающий материал для подбора параметров правила показа. За день в поисковую систему поступают миллионы запросов, это количество слишком велико для обучения, поэтому возникает необходимость выбрать 105 случайных из них за неделю данных, что и делает эта программа.

2. Се1СапсНс1а1е8рог(Зиегу.ру — для каждого из запросов из базы данных рекламных объявлений выбираются соответствующие ему объявления. Для каждого из запросов, которые были собраны программой (2иегуРоо1.ру, производятся следующие действия:

- Из запроса выделяются ключевые слова - слова, несущие основную смысловую нагрузку.

- Из ключевых слов (если их несколько) составляются ключевые фразы.

- По ключевым фразам из всего набора рекламных объявлений выбираются именно те, которые поставили свои ставки для того чтобы

показаться по этим ключевым фразам. Таким образом, для каждого запроса отбираются соответствующие ему кандидаты для показа в рекламном блоке над результатами поиска.

- Объявления-кандидаты определенным образом фильтруются (чтобы не было повторяющихся объявлений, объявлений одного рекламодателя).

В результате работы программы получается обучающий материал для подбора параметров правил показа.

3. OptimalThresholdParameters.py - реализация алгоритма подбора значений параметров правила показа, в зависимости от поставленной оптимизационной задачи. В качестве входных данных выступают:

- Набор запросов с объявлениями-кандидатами, для каждого из которых известны значения Bid и CTR, которые были получены предыдущей программой GetCandidatesForQuery.py

- Максимизируемые показатели системы (например средняя кликабель-ность или суммарный доход).

- Ограничения поисковой системы (ими могут выступать средняя кликабельность, суммарный доход поисковой системе, покрытие рекламой поисковых запросов, заполняемость рекламного блока на запрос пользователя, суммарное количество показов рекламных объявлений по набору запросов).

После того, как задана конкретная задача оптимизации с ограничениями, выполняется поиск соответствующих значений Л1опт, Я2опт и Я3опт (Рис.2.). Полный цикл подбора параметров для набора запросов занимает от 6 до 9 часов (в зависимости от шага перебора Ях и Я2).

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

на МарКсс1исе: вычисления параметров правила показа происходят на порядок быстрее.

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

После того, как значения параметров правила показа Л1опт, Я2опт и /13оПт подобраны, необходимо запустить эксперимент па пользователях поисковой системы. В данном случае решалась задача максимизации средней кликабельности при ограничении на доход поисковой системы и количества запросов с рекламой над результатами поиска. Он-лайн эксперимент проводился 10 дней на 2% пользователей, результаты изменения средней кликабельности относительно эталонного эксперимента (также на 2% трафика) составили в среднем 8% (Табл.2). Эксперимент проводился по методике АВ-тестирования.

После проведения он-лайн эксперимента, было решено внедрить данное правило показа для всей системы показов рекламы компании «Яндекс». После внедрения проводился обратный эксперимент со старой формулой. По результатам сравнения новой формулы и обратного эксперимента по средней кликабельности прирост в процентах составил 8.1% (Табл.2.).

Данный вид правила показа рекламных объявлений в рекламном блоке над результатами поиска используется па данный момент в системе показов рекламных объявлений компании «Яндекс».

№ дня 1 2 3 4 5 6 7 8 9 10 Среднее

эксперимент 7.9% 8.1% 8.2% 7.8% 8.3% 7.7% 7.6% 7.8% 8.5% 8.2% 8%

внедрение 7.9% 8.8% 7.7% 8.1% 8.7% 7.5% 7.5% 8.1% 8.4% 8.3% 8.1%

Табл. 2. Дневная динамика изменения средней кликабельности.

II. ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

Основные результаты, полученные лично соискателем, и их научная новизна

заключаются в том, что:

1. На основе проведённого анализа существующих подходов и методов разработана новая модель показов рекламных объявлений в поисковых системах, а также представлено её математическое описание.

2. В соответствии с выделенным критерием эффективности показов рекламных объявлений над результатами поиска на запрос пользователей и ограничений системы показов рекламы, была поставлена математическая задача оптимизации рекламных показов.

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

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

5. Написан комплекс программ, основной частью которого является алгоритм подбора параметров правила показа. Алгоритм показал высокую эффективность, масштабируемость и быстродействие. По результатам тестирования нового вида правила показа на он-лайн эксперименте было решено использовать предложенный вид правила показа для всего потока запросов поисковой системы «Яндекс».

III. ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Работы, опубликованные автором в перечне ведущих рецензируемых

научных журналов н изданий, рекомендованных ВАК:

1. Корнетова Л. II. (Сорокина A.II.) Оптимизация показов рекламы в поисковых системах // Проблемы управления, 2013.- №. 1. - С. 40-49. — 1 п.л. (в соавт. с Червоненкисом А. Я.; авт. вклад 0.5 п.л.).

2. Сорокина А. Н., Усовершенствованный алгоритм оптимизации показов рекламы в поисковых системах и результаты экспериментов. // Проблемы управления, 2014. - № 3 - С. 57-63. - 1 п.л. (в соавт. с Червоненкисом А. Я.; авт. вклад 0.5 п.л.).

3. Корнетова А.Н. (Сорокина А.Н.) Оптимизация прогноза вероятности клика по контекстной рекламе на поисковой системе «Яндекса» // Научно-Техническая Информация. Серия 2. Информационные процессы и системы, 2013 - №. 4,- С. 1-8. - 0.5 п.л. (в соавт. с Бауманом К.Е., Топинским В.А., Хакимовой Д.А.; авт. вклад 0.15 п.л.).

В других изданиях:

4. Kometova A. (Sorokina A.) Using boosted trees for click-through rate prediction for sponsored search // Proceedings of the Sixth International Workshop on Data Mining for Online Advertising and Internet Economy, 2012. - C. 2. - 0.1 п.л. (в соав. с Trofimov I., Topinskiy V.; авт. вкл. 0.03 п.л.).

5. Sorokina A. (Kometova A.) Optimization of ads allocation in sponsored search // Proceedings of the 22nd international conference on World Wide Web companion. - International World Wide Web Conferences Steering Committee, 2013. - C. 121-122. - 0.1 п.л. (в соавт. с Chervonenkis А., Topinskiy V.A.; авт. вклад 0.03 п.л.).

6. Сорокина А. Н Алгоритм размещения рекламных объявлений над результатами поиска, максимизирующий доход поисковой системы // Информационные процессы, 2014-Т. 14- №. 1.-С. 108-116.-0,5 п.л.

Все результаты, составляющие основное содержание диссертации, получены автором самостоятельно. В работах, опубликованных в соавторстве, личный вклад диссертанта состоит в следующем.

В работе [1], [5] автором разработана модель показов рекламных объявлений в поисковых интернет-системах, а также получена математическая задача оптимизации в соответствии с характеристиками построенной модели.

В работе [2] автором построен усовершенствованный алгоритм подбора параметров правила показа рекламного объявления над результатами поиска на запрос пользователя. Автором получены и проанализированы результаты экспериментов, использующих полученное правило показа.

В работах [3] - [4] автором предложены правила подбора параметров правила показа в зависимости от изменения оптимизационной задачи размещения рекламных объявлений и проведены соответствующие эксперименты.

Подписано в печать 22.07.2015 г. Формат А5 Бумага офсетная. Печать цифровая. Тираж 100 Экз. Заказ № 31932-15-КЦ Типография ООО "Ай-клуб" (Печатный салон МДМ) 119146, г. Москва, Комсомольский пр-кт, д.28 Тел. 8-495-782-88-39