В 2014 году был опубликован доклад Яндекс, раскрывающий детали и выводы эксперимента, посвященного влиянию поведения пользователей на метрики оценки эффективности выдачи. Перевод осуществлён при поддержке Исследовательского отдела компании ALTWeb Group, который занимается изучением влияния поведенческих факторов на порядок и методы ранжирования. Результаты собственных исследований ALTWeb Group использует для разработки и внедрения современных решений в области цифровой коммерции. Публикации из открытых источников используются в научных целях.
Приводимый доклад Яндекс раскрывает одну из сторон влияния поведенческих факторов на формирование подхода к построению страниц поисковой выдачи. Текст исследования приводится целиком и в ознакомительных целях.
Аннотация
Современные поисковые системы показывают пользователям неоднородную информацию, происходящую из источников различного типа, также именуемых «вертикали». Оценка данного типа систем — важная и сложная задача, решение которой ещё только предстоит найти. В данном докладе мы рассматриваем гипотезу о том, что использование моделей, запечатлевающих данные о поведении пользователей в поиске по отношению к неоднородным страницам выдачи, позволяет улучшить качество офлайновых метрик. Мы предлагаем две метрики для оценки вертикальных источников информации, которые основываются на пользовательской модели кликов для параллельного поиска, и даём им оценку на основе логов пользовательских запросов, собранных поисковой системой Яндекс. В своей работе мы показываем, что в зависимости от типа вертикали, предложенные метрики более тесно коррелируют с поведением пользователя онлайн, нежели чем другие новейшие техники.
Категория и предметная область
H 3.3 [Хранение и доступ к данным]: Поиск и выдача данных.
Ключевые слова
Кликовая модель, оценка, параллельный поиск.
1. Введение
При оценке системы поиска в сети, принято считать, что пользователи получают страницу результата с десятью сниппетами, также известными как «десять синих ссылок», и то, что эти сниппеты просматриваются пользователем сверху вниз. Тем не менее, существующие поисковые системы идут дальше парадигмы «десяти синих ссылок» и показывают пользователю неоднородную информацию из различных поисковых алгоритмов, также известных как вертикали (например: изображения, новости, карты и т. д.). В этом случае поведение пользователей значительно отличается от такового на стандартной странице выдачи [3, 10]. Хотя изменения в поведении пользователей должны приниматься во внимание при составлении неоднородных страниц выдачи, тем не менее, в данном направлении проведено пока что мало исследований [12].
Качество страницы выдачи может быть оценено двумя способами: онлайн или офлайн. Онлайновая оценка, такая как сплит-тестирование собирает обратную связь непосредственно от пользователей. Как правило, данные обратной связи включают в себя клики, время на странице, движения мышкой и другие показатели. Оценка качества системы строится на этих сигналах. Также, качество поиска может быть оценено офлайн вручную на основе всей страницы выдачи (SERP) и\или её частей. Подобная оценка может быть сделана как с непосредственним применением так и без офлайновых метрик эффективности. Не так давно был предложен смешанный метод оценки где офлайновые метрики строятся на основе моделей поведения пользователей, параметры которых берутся из логов поисковых запросов [4]. Таким образом, оценка производится офлайн и даёт реузльтаты незамедлительно. Тем не менее, в ходе подобной оценки используются данные обратной связи, поступающие от пользователей (в форме кликов), что даёт возможность принять во внимание предпочтения реальных пользователей.
В данной статье мы рассматриваем проблему оценки неоднородных поисковых алгоритмов исходя из изложенных выше фактов. В частности, мы разрабатываем модель метрик эффективности для неоднородных страниц выдачи, основанную на кликовой модели.
Основной вопрос нашего исследования состоит в следующем: возможно ли улучшить качество офлайновых метрик эффективности для веб-поиска при помощи данных о поведении пользователей в ситуации выдачи различных вертикальных результатов?
Практическая польза от данного исследования следующая. Во-первых, мы разрабатываем две метрики эффективности для вертикальных результатов выдачи на основе кликовой модели для комбинированного поиска [3, 10]. Во-вторых, мы даём оценку эффективности предлагаемых метрик на основе широкой выборки поисковых логов, на основе поисковых сессий с различными видами вертикальных результатов выдачи, а именно: изображения, видео, карты и новости.
2. Метрики на основе пользовательской кликовой модели
Метрики эффективности поиска по Интернету должны отражать то, как пользователи воспринимают качество предлагаемой выдачи. Соответственно, данные метрики всё в большей степени опираются на данные поведения пользователей. Традиционные метрики, такие как различные методы оценки точности, предполагают что пользователи заинтересованы в релевантных документах, а следовательно, фокусируются на параметре релевантности. В дополнение к релевантности, более продвинутые метрики, такие как nDCG [7] и RBP [8] предполагают, что пользователи просматривают результаты сверху вниз и соответственно ранжируют документы по релевантности на странице выдачи.
Однако в последнее время ряд метрик для оценки выдачи были предложено базировать на пользовательской кликовой модели. Такого рода модель оценивает возможность клика по каждому документу, предоставляемому пользователю в выдаче. Метрики, основанные на модели пользовательского поведения, в свою очередь, используют эти вероятностные возможности для того, чтобы измерить качество выдаваемых поиском результатов. Метрика Expected Reciprocal Rank metric (ERR) [2] (Ранжирование, используемое Yahoo — прим. перев.) использует упрощённую версию кликовой модели DBN [1] где пользователь просматривает результаты страницы выдачи сверху вниз до тех пор, пока не найдёт релевантный документ и не покинет поиск. Expected Browsing Utility (EBU) [11] (Метод, преложенный Microsoft — прим. перев.) также основан на упрощённой модели DBN но, в отличие от ERR, использующего предопределённые значения параметров, EBU определяет параметры непосредственно из кликовых логов.
Чуклин и соавторы [4] предложили общий способ конвертации кликовых моделей в метрики оценки эффективности построения страницы выдачи. Они применили эту идею к существующим моделям поиска, таким как DBN [1], DCM [6] и UBM [5]. Как результат, были предложены ряд метрик, основаyных на показателях полезности и затраченных усилий. Все они дали более высокие показатели точности по сравнению со стандартными методами, не учитывающими кликовые модели.
3. Метрики для вертикальных источников данных
Упомянутые выше метрики показали свою эффективность при стандартном пользовательском сценарии. Тем не менее, существующие офлайновые методы оценки для интернет-поиска не учитывают наличие вертикальных результатов на странице выдачи. Последние исследования в данной области показали что поведение пользователей значительно отклоняется от стандартного сценария в данном случае. [1, 10].
Были предложены следующие кликовые модели, которые отражают данные отклонения: Объединённая Кликовая Модель (FCM) [3], Кликовая модель для вертикальных поисков (VCM) [10]. Данные модели показали большую приближённость к реальным результатам и меньшую степень погрешности по сравнению с кликовыми моделями для стандартного поиска. Тем не менее, соответствующие метрики оценки эффективности выдачи разработаны не были. Мы попытаемся заполнить этот пробел путём конвертации FCM и VCM моделей в соответствующие офлайновые метрики оценки на основе кликовых моделей.
Мы считаем, что данные метрики лучше коррелируют с данными онлайн экспериментов по сравнению с существующими офлайновыми метриками в том случае, когда на странице поисковой выдачи присутствуют данные из различных (вертикальных) источников.
КАК FCM так и VCM дополняют tility Browsing Model (UBM) для интернет-поиска [5] (хотя использование DCM и DBN также допустимо).
Следовательно [4], UBM может быть использовано для создания метрики, основанной на полезности поиска — и мы сосредосточим наше внимание на подобных способах оценки в данном документе.
Метрика, основанная на эффективности (UBM) может быть определена следующим образом:
где N обозначает количество документов на странице выдачи, P (Ck = 1) означает вероятность того, что на k-ный по счету документ придётся клик, а rk обозначает релевантность k-ного по счету документа на странице выдачи.
В выражении (1) релевантность, выраженная rk, является офлайновым параметров, в то время как вероятность клика P ( Ck = 1) рассчитывается на основе пользовательской модели кликов. Мы используем принятое в работе по ERR [2] определение релевантности r на основе релевантности степени R как то: r = (2R 1)=2Rmax.
Согласно кликовой модели UBM, на документ приходится клик только в том случае, если он замечен и обладает привлекательностью для пользователя:
где E и А являются произвольными переменными, регистрирующим наступление событий того, что документ замечен и обладает привлекательностью. В модели UBM привлекательность зависит от документа и запроса q, а факт того, что документ замечен вероятно зависит от его расположения и удалённости от места последнего клика.
Во время офлайновой оценки веб-поиска, клики недоступны, поэтому расстояние d от места последнего клика на документ — недоступно. Следовательно, это расстояние должно не учитываться для того, чтобы посчитать конечные вероятности кликов. Согласно [4], PUBM (C = 1) может быть определено следующей формулой:
где для простоты будет принято, что
.Метрика на основе FCM
Исследование поведения пользователей на объединённом поиске показывают, что наличие вертикальных результатов влияет на вероятность открытия остальных документов на странице выдачи [3, 10]. Для того, чтобы построить модель, демонстрирующие это отличие от стандартного поиска, FCM вводит дополнительную скрытую переменную F, которая показывает, меняется ли поведение пользователей при наличии вертикальных результатов в выдаче. В данной работе мы будем называть это «вертикальной привлекательностью». Вероятность того, что документ будет рассмотрен, по модели FCM будет представлять собой следующее уравнение:
где t представляет тип вертикального результата поиска, v представляет его позицию, а l — это расстояние между вертикальным результатам и остальными результатами поисковой выдачи, которые могут быть как положительными, так и отрицательными. Таким образом, вероятность рассмотрения документа в модели FCM может быть рассчитана следующим образом:
Для того, чтобы получить вероятность клика PFCM (C = 1), нужно подставить вероятность рассмотрения PFCM (E = 1) в уравнение (2) вместо PFCM (E = 1) = γkd. В этом случае метрика uFCM может быть представлена путём добавления PFCM (C = 1) в уравнение (1).
Метрика на основе VCM
Подобно FCM, VCM предполагает что вероятность рассмотрения документа меняется когда привлекательный вертикальный результат поиска присутствует на странице выдачи (F = 1). Также, VCM предполагает, что в данном случае пользователь рассматривает вертикальный результат первым и только затем подолжает рассматривать другие результаты в направлении сверху-вниз. Это контролируется скрытой переменной B. Таким образом, VCM моделирует вероятность рассмотрения следующим образом:
Таким образом уравнения описывают три вероятных сценария пути рассмотрения для страницы выдачи:
(i) начиная с верха документа вниз (F = 0),
(ii) начиная с вертикали, затем вновь кликая на верх страницы выдачи (F = 1; B = 1), и
(iii) начиная с вертикали и до конца страницы выдачи (F = 1; B = 0).
Общая вероятность рассмотрения в VCM рассчитывается как среднее значение вероятностей рассмотрения этих трёх путей:
где d, d' и d'' обозначают расстояния между последними прокликанными документами согласно каждому из путей.
Общая вероятность клика в модели VCM не может быть подставлена напрямую в выражение (2) потому, что использует различные расстояния для различных путей пользовательского поведения. Поэтому нужно выделить вероятность клика для каждого пути и таким образом убрать каждую из дистанций из уравнения. Тогда общая вероятность клика для модели VCM может быть представлена в следующем виде:
где Pi обозначает вероятность рассмотрения в i-ном по счету пути. Метрика uVCM вычисляется путём подстановки PVCM (C = 1) в выражение (1).
4. Оценка
4.1 Условия эксперимента
Для того, чтобы оценить эффективность предлагаемых метрик для поиска, включающего вертикальную выдачу, мы собрали пользовательские поисковые сессии из кликовых логов на базе крупной коммерческой поисковой системы Яндекс. Как и в [3, 10], мы использовали вертикальные результаты трёх типов: изображения и видео как мультимедийные вертикали, новости как текстовая вертикаль, и карты как смешанная смешанная по составу вертикаль, содержащая текстовые и визуальные данные. Мы выделили образцы сессий, содержащих один из данных вертикальных результатов в ноябре 2013 года. Первые 10 документов в выдаче в каждой сесси были оценены пользователями по стандартной пятиступенчатой шкале (идеально, отлично, хорошо, неплохо, плохо). Собранные сессии были отсортированы по ID пользователей и скомпонованы в пакеты для тренинга и тестирования (см. таблицу 1). Неравномерное распределение числа сессий объясняется частотой появления вертикальных результатов в выбранных из кликовых логов образцах сессий.
Таблица 1
Согласно [2, 4], мы дали оценку качеству предлагаемых метрик, основываясь на их соответствии с онлайн метриками, такими как UCTR и Max/Mean/MinRR. UCTR представляет собой бинарную переменную, показывающую, был ли клик в течение сессии или нет (ситуация, противоположная ситуации выхода из сессии). MeanRR представляет собой средний обратно пропорциональный ранк кликов в сессии. MaxRR представляет собой обратно пропорциональный ранк последнего клика. Для этих онлайн метрик рассматриваются только клики в поисковой выдаче.
Принимая во внимание, что для одного и того же запроса страница поисковой выдачи может различаться в зависимости от пользователя, его местоположения и других подобных пользовательских факторов, мы сосредоточили наше внимание на структурах [2], представляющих собой запрос с фиксированной страницей выдачи (см. статистику в таблице 1). Офлайновые метрики дают те же значения для одних и тех же структур, в то время как онлайновые метрики дают среднее значение для всех сессий с одной и той же структурой. Измеримое соотношение между офлайновыми и онлайновыми метриками рассчитывается на основе всех стркуктур, как это показано в [2]:
Где N представляет собой общее количество конфигураций, nc представляет собой число различных конфигураций с, mi представляет собой значение метрики mi для конфигурации с, а
представляет собой числовое значение переменной mi.Мы сравниваем наши метрики для выдачи с вертикальными результатами с двумя типами исходных данных:
(i) статические офлайновые метрики где параметры являются неизменными (DCG и ERR), и
(ii) метриками на основе кликовой модели для веб-поиска, где параметры берутся из кликовых логов (EBU, uDCM, uDBN and uUBM). Рассматривая эти параметры модели, вероятность привлекательности для пользователя P(A=1) (и вероятность удовлетворённости P(S=1) для DBN) считается зависимой только на степени релевантности документа данному запросу как в [4].
4.2 Выводы и обсуждение
Измеримое соотношение между офлайновыми и онлайновыми метриками для различных типов вертикальных результатов поиска показано в таблицах 2-5, где лучшие значения выделены жирным шрифтом.
Таблицы 2 и 3
Таблица 2 представляет результаты для новостной вертикали. Новостные снипеты содержат в основном текстовые данные и, следовательно, аналогичны стандартным веб-сниппетам. Как следствие, большинство офлайновых метрик (за исключением DCG) имеют соответствующую корреляцию с онлайновыми метриками. В то же время, предложенные метрики для выдачи с учетом вертикальных результатов такие как uFCM и uVCM несколько превосходят другие метрики.
В таблицах 3 и 4 представлены результаты для мультимедийной вертикали, а именно для результатов поиска по изображениям и видео. В обоих случаях uFCM показывает более высокие значения корреляции со всеми онлайновыми метриками по сравнению с исходными данными. Данный результат является интуитивным, учитывая что поведение пользователей, согласно логам, значительно меняется когда в вертикальном результате присутствуют визуальные раздражители (например, изображение) [3, 10]. Модель FCM регистрирует данные изменения, которые, в свою очередь, являются результатом более высокой корреляции значений между uFCM и онлайновыми метриками.
Метрика uVCM занимает второе место по степени успешности в плане корреляции значений со значениями онлайн экспериментов. Однако она не коррелирует с uFCM. Это может быть объяснено следующим образом. Кликовые модели FCM и VCM используют параметр вертикальной привлекательности документа для пользователя
, который показывает насколько поведение пользователей отличается от стандартного сценария веб-поиска когда вертикальный результат типа t присутствует в ранке v. Чем ниже значение , тем ближе вертикальная модель к соответствующей модели UBM. После использования FCM и VCM на вертикалях изображений и видео, мы наблюдали что ожидаемое значение оказывается относительно высоким, что в свою очередь означает, что FCM в значительной степени является производной от UBM. В противоположность этому, значение для VCM оказалось весьма низким, гораздо более приближённым к UBM. Действительно, таблицы 3 и 4 показывают что корреляция uVCM с онлайновыми метриками близко к подобной корреляции uUBM.
Таблицы 4 и 5
Таблица 5 представляет результаты для вертикали поиска по картам, дающего данные в текстовом и визуальном форматах. DCG имеет наиболее высокую корреляцию с онлайновыми метриками, основанными на RR, следом идёт uDCM (у которой наблюдается наиболее высокая корреляция с UCTR) и EBU. Мы использовали A\B тестирование для того, чтобы наблюдать эту корреляцию. Тестирование проводилось на реальных пользователях в рамках используемой поисковой системы, где вертикаль карт была отключена на недельный период.
Данный эксперимент показал, что уровень выхода из поиска (когда вертикальный результат показан в поиске) был гораздо выше по сравнению с уровнем продолжения поиска (вертикальный результат не выдаётся пользователю). Мы видим две причины, объясняющих это явление: (i) пользователи удовлетворены информацией, представленной в выдаче (адрес, телефон, часы работы и т. д.) и выходят из поиска без клика, что рассматривается как положительный результат выхода из поиска. (ii) некоторые пользователи считают вышеприведённый результят для вертикали карт баннером (особенно если выдача по вертикали занимает верхнюю строку поиска) и пропускают данный результат, что рассматривается как вариант баннерной слепоты.
Для запросов маршрутов это даёт отсутствие кликов по выдаче. В обоих случаях. Онлайновые метрики, такие как MeanRR и UCTR не дают оценки полной картины пользовательского поведения. Таким образом, низкая корреляция офлайновых метрик, наблюдаемая на результатах из таблицы 5 не может быть интерпретирована как негативный результат. Другие средства оценки качества офлайновых метрик должны применяться в данном случае (например, классификация выходов из поиска на «положительные» и «отрицательные» как в [9] и подсчет показателей корреляции только для последнего типа выхода), что в будущем будет являться темой нашей следующей работы.
Как результат нашей работы, мы обнаружили несколько важных тенденций. Во-первых, они подтверждают результаты исследований предыдущих работ, посвященных поведению пользователей в параллельном поиске, а именно: поведение пользователей зависит от типа вертикального результата, включённого в страницу выдачи, где визуально привлекательные вертикали, такие как видео, влияют на поведение пользователя больше, чем текстовые вертикали, такие как новости. Вертикали, представляющие смешанный контент, такие как карты, провоцируют более сложное поведение пользователей, требующее дальнейшего исследования.
Во-вторых, в ответ на исследовательский вопрос, сформулированный в Секции 1 данной работы, мы показали, что в зависимости от типа вертикали, предлагаемая метрика для параллельного поиска, основанная на кликовой модели обладает более высокое значение корреляции с поведением пользователя онлайн по сравнению с офлайновыми метриками для веб-поиска. В частности, uFCM обладает наиболее высокой корреляцией в случае с включенными в страницу выдачи визуально привлекательными вертикалями, такими как изображения и видео. Метрика uVCM, напротив, более консервативна и ближе к соответствующей UBM модели.
5. Выводы и дальнейшие исследования
В данной работе мы рассмотрели проблему офлайновой оценки неоднородной среды поисковой выдачи, где стандартные результаты поиска соперничают с результатами вертикальных поисков. Мы исследовали вопрос как данные о поведении пользователей на примере такого рода смешанных страниц выдачи могут помочь улучшить качество офлайновых метрик. С этой точки зрения мы рассмотрели существующие кликовые модели для параллельного поиска, а именно FCM и VCM, и конвертировали их в метрики эффективности выдачи на основе кликовых моделей. Результаты эксперимента показали, что в зависимости от типа вертикали, предлагаемые метрики обладают более высокими показателями корреляции с онлайновыми метриками, особенно если визуально привлекательные результаты вертикали, такие как изображения и видео показаны в выдаче.
В нашей будущей работе мы планируем углубить предлагаемые метрики для оценки не только веб-результатов, но и страниц выдачи в целом, включая вертикальные результаты, спонсорский поиск и другие компоненты. Мы также планируем более детально исследовать поведение пользователей в случае отображения результатов вертикали карт на странице выдачи. В первую очередь, нам хотелось бы понять причину высоких показателей выхода из поиска, которые мы наблюдали в этом случае, после чего мы планируем разработать методы отделения положительных и отрицательных выходов для более точной оценки качества офлайновых метрик.
Выражаем благодарность. Авторы исследования хотели бы поблагодарить Евгения Крохлева и Сергея Протасова за обсуждения, в которых мы нашли вдохновение для создания нашей работы и поддержку с технической стороны. Это исследование было частично финансировано грантом P2T1P2_152269 Швейцарского научного фонда <далее перечисляются организации, гранты и программы, причастные к созданию работы, см. оригинальный текст — прим. Перев.>
Список литературы
[1] O. Chapelle and Y. Zhang. A dynamic bayesian network click model for web search ranking. In WWW ’09, pages 1–10, 2009.
[2] O. Chapelle, D. Metzler, Y. Zhang, and P. Grinspan. Expected recip-rocal rank for graded relevance. In CIKM ’09, pages 621–630, 2009.
[3] D. Chen, W. Chen, H. Wang, Z. Chen, and Q. Yang. Beyond ten blue links: enabling user click modeling in federated web search. In WSDM ’12, pages 463–472, 2012.
[4] A. Chuklin, P. Serdyukov, and M. de Rijke. Click model-based infor-mation retrieval metrics. In SIGIR ’13, pages 493–502, 2013.
[5] G. E. Dupret and B. Piwowarski. A user browsing model to predict search engine click data from past observations. In SIGIR ’08, pages 331–338, 2008.
[6] F. Guo, C. Liu, and Y. M. Wang. Efficient multiple-click models in web search. In WSDM ’09, pages 124–131, 2009.
[7] K. Järvelin and J. Kekäläinen. Cumulated gain-based evaluation of IR techniques. ACM Trans. Information Systems, 20(4):422–446, 2002.
[8] A. Moffat and J. Zobel. Rank-biased precision for measurement of retrieval effectiveness. ACM Trans. Information Systems, 27(1):2:1– 2:27, 2008.
[9] Y. Song, X. Shi, R. W. White, and A. Hassan. Context-aware web search abandonment prediction. In SIGIR ’14, 2014.
[10] C. Wang, Y. Liu, M. Zhang, S. Ma, M. Zheng, J. Qian, and K. Zhang. Incorporating vertical results into search click models. In SIGIR ’13, pages 503–512, 2013.
[11 ]E. Yilmaz, M. Shokouhi, N. Craswell, and S. Robertson. Expected browsing utility for web search evaluation. In CIKM ’10, pages 1561– 1564, 2010.
[12] K. Zhou, T. Sakai, M. Lalmas, Z. Dou, and J. M. Jose. Evaluating heterogeneous information access. In Proc. MUBE workshop, 2013.
