Диссертация (1137263), страница 10
Текст из файла (страница 10)
2.5.2);во-вторых, уменьшено машинное время работы алгоритма, поэтомуприменять его к большим объёмам данных более целесообразно;67в-третьих, при варьировании меньшего количества параметров,гораздо проще проводить интерпретацию работы алгоритма;и, наконец, в-четвёртых более «прозрачная» схема работы позволяетлучше понять по каким критериям происходит отбор объявлений дляпоказа в рекламном блоке над результатами поиска.2.7.1 Данные для тестированияЭкспериментальное тестирование описанного выше алгоритмабудет проводиться следующим образом: последовательно рассмотримкаждый из этапов выбора значений параметров 1 , 2 и 3 и убедимся,что алгоритм отбирает объявления нужным нам способом.Данные для тестирования выбирались следующим образом:1) Бралась неделя логов показов рекламы на поисковой страницекомпании «Яндекс» за 25 – 31 января 2013 г.2) Из данных по поисковому логу выделялись запросы, которыепользователи задавали за соответствующую неделю.3) Для тестирования алгоритма отбиралось 100 000 запросов(случайно, то есть выборка запросов получилась несмещённая ирепрезентативная).4) Иззапросавыделяетсяключеваяфразаспомощьюморфологического инструментария.
Фраза, точно (с точностью дословоформы и предлогов/союзов), совпадающая с запросомназывается точным совпадением. Также существует большоеколичество способов подбора дополнительных фраз [37]. Такимобразом, каждому запросу ставится в соответствие набор фраз.5) Каждой фразе запроса соответствует множество рекламныхобъявлений, которые торгуются за попадание в рекламный показ (ив том числе за позицию при показе) по этой фразе.
Для запроса68составляется список рекламных объявлений как объединение ихмножеств по каждой из фраз, соответствующих запросу.6) Для каждого объявления известно: – предсказание вероятности клика для пары объявлениефраза. – ставка для данного баннера и соответствующей фразы.2.7.2 Этапы проведения экспериментального тестирования.Экспериментальное тестирование алгоритма будет состоять изследующих этапов:Этап 1.
Рассмотрим один запрос.Рассмотрим ту часть алгоритма, которая на схеме (Рис. 2.) обозначается(Рис. 5.).Решение задачи оптимизации критерия1 () = ∑ ∙ ( + 1 ∙ ∙ − 2 )(,)при фиксированных значениях 1 и 2 .Получение оптимальных значений матрицы и соответствующих значений и 3Рис. 5.
Работа с отдельными запросами.Сначала возьмём один запрос и, перебирая 1 , зафиксируем какпоследовательно отбираются объявления на показ в рекламный блокнад результатами поиска. Рассматриваются те характеристики, которыезадействованы в задаче оптимизации (5).Этап 2. Подбор для фиксированного .69Перебор значений 1(при фиксированном 2 )до достижения равенства() = Рис. 6. Подбор значения параметра при фиксированном длявсего набора запросов.Возьмём полный набор запросов с объявлениями – кандидатами.Для заданного 2варьируем 1 до достижения равенства попрогнозируемым денежным средствам (Рис. 6.)Для пары параметров и уже становится возможным подсчётсуммарных характеристик для всего набора запросов (то естьсчитаются уже характеристики всей системы). Сам параметр 1отвечает за вклад предсказанного дохода от показа рекламногообъявления, тем самым мы регулируем и суммарный ожидаемый доход,который входит в (5) как ограничение.
Нас интересует зависимость от1 таких величин как: , ∙ , / , 3 .Этап 3. Максимизация основного критерия.Внешний цикл алгоритма отвечает за оптимизацию основногокритерия оптимизационной задачи – среднего по всему наборузапросов (Рис. 7.).Перебор значений 2 с цельюмаксимизации критерия0 () = ∑ ∙ /(,)Рис. 7. Максимизация основного критерия.Будем варьировать 2 , получать для него соотвествующееоптимальное 1 (которое выводит систему на ограничение поожидаемому доходу), и получать для пары (1 , 2 ) набор различныхвеличин , ∙ , 0 .702.7.3 Отбор объявлений на показ для одного запроса.Было взято фиксированное значение 2 = 7.46, 1 варьировалосьс шагом 0.1. Зафиксировав 2 , и варьируя 1 (последовательноувеличивая) мы начинаем «пускать» объявления для показа врекламном блоке над результатами поиска.
Рассмотрим на примере какэто происходит. Допустим, в качестве кандидатов на показ у насотобрались объявления со следующими характеристиками (Табл.1.)IDCTR Bid CPM10.0452 100 4.5220.0271 122 3.3030.0952 100.9540.0284 661.8750.0534 110.5960.0627 30.1970.0254 180.46Табл. 1.
Набор характеристик для объявлений-кандидатов для показапо конкретному запросу.Для первой пары (1 , 2 ) = (1,7.46) получаются следующие значения1 (Табл.2.).ID1-1.832-3.493-4.164-4.895-5.566-5.737-6.38Табл. 2. Значение критерия для объявлений-кандидатов.Из таблицы видно, что для всех объявлений значение 1отрицательно, и ни одно объявление не будет претендентом на показ.Теперь, последовательно увеличивая 1 , можно найти такое 1 ,чтобы показать только одно объявление, это 1 = 1.5.
Будем искатьследующее значение 1 такое, что в список кандидатов на показ в71рекламном блоке добавляется ещё одно дополнительное объявление.Получены соответствующие значения 1 и 1 для объявленийкандидатов (Табл. 3.).1111(1 = 1.5)(1 = 2.1)(1 = 3.7)(1 = 5.4)10.433.1410.3618.042-1.840.145.4211.033-3.95-2.830.163.354-3.69-3.12-1.590.035-5.26-4.91-3.97-2.976-5.63-5.52-5.14-4.367-6.15-5.87-5.22-4.90Табл. 3.
Значение критерия для разных значений .Красным цветом отмечены положительные значения критерия,то есть когда объявление становится кандидатом на показ. По таблице(Табл. 3.) видно, что в последней колонке уже становится четырекандидата на показ, однако покажется всего три (из-за ограничения наколичество показываемых объявлений в рекламном блоке сверхурезультатов поиска на запрос пользователя). Покажем более нагляднодинамику выбора алгоритмом объявлений (Рис.
8. – Рис. 12).72(1,2)=(1,7.46)54,54CTR*Bid3,532,52не отобралось1,510,5000,020,040,060,080,1CTRРис. 8. Ни одного объявление для показа не отобралось.(1,2)=(1.5,7.46)54,54CTR*Bid3,532,5не отобралось2отобралось1,510,5000,020,040,060,080,1CTRРис. 9. Отобралось одно объявление на рекламный показ.73(1,2)=(2.1,7.46)54,54CTR*Bid3,532,5не отобралось2отобралось1,510,5000,020,040,060,080,1CTRРис. 10. Отобралось два объявления для показа.(1,2)=(3.7,7.46)54,54CTR*Bid3,532,5не отобралось2отобралось1,510,5000,020,040,060,080,1CTRРис.
11. Отобралось три объявления (максимально возможноезначение)74(1,2)=(5.4,7.46)54,54CTR*Bid3,53не отобралось2,52отобралось1,5отобралось но не показалось10,5000,020,040,060,080,1CTRРис. 12. По критерию отобралось четыре объявления, но будетпоказано всего три.Таким образом, получено представление о том, как алгоритмотбирает из всего множества объявлений-кандидатов претендентов напоказ в рекламном блоке для одного запроса.2.7.4 Подбор параметра при фиксированном значении навсём пуле запросов.Теперь будем варьировать 1 и 2 для всего набора запросов(одновременно) и посчитаем следующие величины: , ∙ 1 .
Рассмотрим зависимости основных показателей системы отпараметра 1 . Этот параметр входит в критерий показа следующимобразом: + 1 ∙ ∙ − 2То есть он присутствует перед ∙ – вероятностью списанияставки с рекламодателя. Рассмотрим поведение и ∙ отизменения параметра 1 :1) .75Получен график зависимости среднего от 1 (Рис. 13.).CTR, %0,1020,10,098CTR, %0,0960,0940,0920,090,0880,086012345671Рис. 13. Зависимость изменения среднего от параметра .Из графика (Рис. 13.) видно, что, действительно, при увеличении 1такая характеристика объявления как его начинает учитыватьсяпри отборе объявления для показа всё меньше и меньше и средний по всему набору запросов так же падает.2) ∙ .Рассмотрим поведение ∙ в зависимости от измененияпараметра 1 (Рис.
14).Опишем процедуру выбора 1опт при фиксированом значении 2 .Последовательно перебирая значения параметра 1 , алгоритм получаетсуммарное значение ∑ ∙ , которое в нашем случае мыпринимаемкакаппроксимациюсуммарногодохода().Ограничение оптимизационной задачи имеет вид: () ≥ . Кактолькодостигается,соотвествующеезначение1дляфиксированного 2 принимается за оптимальное и запоминается как1опт (2 ).76Рис. 14. Динамика изменения () в зависимости от .На графике (Рис.
14) показана вся кривая варьирования 1 и () ,алгоритм перейдёт к следующей итерации по 2 , как только будетдостигнуто для пары (1 , 2 ) ограничение () ≥ .Построим график процентного изменения суммарного () отограничения (чтобы понять порядком каких процентныхизменений мы располагаем) (Рис. 15.).Так как параметр 1 отвечает в критерии как раз за ∙ объявления, то и суммарный доход () по системе увеличивается сувеличением 1 (Рис.
15). Однако, важно заметить, что суммарный() растёт сильнее при варьировании 1 от 1.5 до 2.7, дальше же,видимо, происходит некоторое «насыщение», то есть объявлений сбольшими ∙ уже не остаётся среди кандидатов на показ,поэтому мы начинаем добирать всё более дешёвые объявления исуммарный () начинает расти медленнее.77M(T), %65M(T), %4321001234561Рис. 15. Динамика изменения () в зависимости от 1 .3) ().Величины и () рассчитываются следующим образом: = ∑ ∙ /(,)() = ∑ ∙ ∙ (,)787CTR vs M(T), %65M(T), %43210-12-10-8-6-4-202CTR, %Рис.
16. () при изменении при фиксированном .По построению оптимизационной задачи важно посмотреть назависимость суммарного показателя прогноза заработанных денежныхсредств от средней кликабельности (Рис. 16.).Тут просматривается вполне логичная ситуация: при увеличениипроцента отличия в , () уменьшается, то есть происходитзамещениепроцентов одной характеристики системы на другой.Также на кривой можно выделить несколько областей: процентразницы меняется от -11 до -4%: на данном участе происходитдостаточно резкое увеличение и совсем небольшое уменьшениепроцента () : тут размен /() достаточно большой. Далееследует отрезок изменения процентов разницы от -4 до +1.4% гдеразмен 2:1.4) = / в зависимости от 1 .Общее количество показов рекламы в рекламном блоке надрезультатами поиска вычисляется следующим образом:79 = ∑ (,)Общее количество запросов с рекламой может быть получено последующей формуле: = ∑ {∑()() > 0}Так как количество запросов с рекламой над результатами поискаограничено, то величина показывает заполняемостьпоказами одного рекламного блока, то есть, сколько в среднемобъявлений показалось на запрос над результатами поиска (Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
