Поведенческие факторы. Часть 6: От экспериментов с BrowseRank Plus и MobileRank к алгоритму Fresh BrowseRank

Результаты экспериментов

Чтобы подтвердить эффективность предложенного общего фреймворка, мы провели несколько опытов для проверки производительности алгоритмов BrowseRank Plus и MobileRank по двум направлениям: поиск важных веб-сайтов и фильтрация спама/низкокачественного материала. В эксперименте использовались два набора данных: один описывал поведение пользователей, а второй являлся данными о мобильном вебе.

Ранжирование по графу сёрфинга пользователей

Набор данных и задача

Мы использовали набор данных о поведении из коммерческой поисковой системы для наших экспериментов. Всевозможные личные данные были исключены из образцов. В целом было получено более 3 млрд записей и 950 млн уникальных URL.

Сперва мы создали граф сёрфинга пользователей на уровне веб-сайта, как описывается у [1] посредством объединения страниц одного и того же сайта и игнорирования переходов между страницами в пределах этого сайта, а так же собирая переходы со (или к) страниц в том же сайте. Данный граф сёрфинга пользователей состоял из 5.6 млн вершин и 53 млн рёбер. Затем на граф применялись BrowseRank Plus и BrowseRank. Так же мы создали ссылочный граф с 5.6 млн веб-сайтов, а затем рассчитали PageRank и TrustRank.

Для PageRank использовался uniform teleport vector. Для TrustRank сначала на ссылочный граф применялся инверсированный PageRank и полученный топ из 2000 вебсайтов затем рассматривался как исходная выборка. Затем мы вручную проверили эти 2000 сайтов, исключили спам, зеркала (дубликаты сайтов) и сайты со взрослой тематикой, что уменьшило исходную выборку до 1700 надёжных вебсайтов. TrustRank рассчитывался путём передачи оценки доверия с данной выборки. BrowseRank работал по тем же настройкам, как в [1].

Топ-20 вебсайтов

Таблица 10 показывает топ-20 вебсайтов, ранжированных различными алгоритмами. Для краткости обозначим PageRank, TrustRank, BrowseRank и BrowseRank Plus как PR, TR, BR и BR+, соответственно. Из таблицы можно заключить следующее:

• BR+ высоко ранжирует сайты Web 2.0 (помечены жирным), такие как myspace.com, youtube.com и facebook.com, но низко ранжирует сайты с большим числом входящих ссылок и малым количеством посещений. Поэтому по сравнению с TR и PR, BR+ более объективно отражает предпочтения пользователей.
• BR+ пессимизирует вебсайты с большим числом локальных переходов точнее, чем BR. К примеру, googl.co.th является таким вебсайтом: он высоко ранжируется BR по причине высокого числа кликов и продолжительности визитов в данных о поведении пользователей. Дальнейшее изучение данных о поведении показывает, что большинство переходов совершаются с локальных сайтов в Тайланде, а малая часть приходится на внешний мир. Таким образом в расчёте BR мы получаем высокое значение средней продолжительности визита для google.co.th, так как алгоритм BR не определяет тип перехода. Однако BR+ будет по-разному оценивать переходы с разных сайтов, а эффективная нормализация вебсайтов в (18) сможет уменьшить влияние большого количества переходов с того же сайта. Таким образом ранжирование google.co.th будет адекватно и результат BR+ является более приемлемым, чем BR.

Таблица 10. Топ-20 сайтов по версии разных алгоритмов.

Фильтрация спама

Из 5.6 млн вебсайтов, мы случайным образом отобрали 10000 экземпляров и попросили экспертов провести ручную разметку на вопрос спама. В процессе маркировки страницы, являющиеся целиком рекламными и не несущие никакой полезной информации, так же считались спамом. 2714 сайтов были помечены как спам, а оставшиеся 7286 оказались нормальными.

Для сравнения производительности алгоритмов, мы изобразили распределение блоков спама способом, похожим на [1] [17] [6]. Для каждого алгоритма 5.6 млн веб-сайтов были отсортированы в убывающем порядке в соответствии с оценками, выданными алгоритмом. Затем сайты были разбиты на 15 блоков. Статистика распределения спама приводится в Таблице 11.

Таблица 11. Количество спам-сайтов в блоках.

Из эксперимента были получены следующие наблюдения: TR работает лучше, чем PR, так как рассчитывает оценку доверия на основе человеческой разметки и ссылочного графа. Среди всех алгоритмов BR+ пессимизирует наибольшее количество спам-сайтов. И хотя BR поместил немного больше спамовых вебсайтов в последний блок, чем BR+, BR+ превосходит его работу в целом по блокам 6, 5, 4, 3, 2. К примеру, lastlotteryresults.com ранжируется BR очень высоко, но BR+ ранжирует его очень низко. Анализ данных показал, что 26% переходов на этот вебсайт совершались с сайта, на котором расположено объявление latest-lotteryresults.com на главной странице. Судя по данным, вебмастер сайта намеренно кликал по объявлению. При помощи нормализации BR+ может эффективно пессимизировать подобное кликовое мошенничество.

Ранжирование на мобильном веб-графе

Набор данных и задача

Мобильный веб-граф, который мы использовали в экспериментах, был предоставлен китайской мобильной поисковой системой. Сканирование графа проводилось в октябре 2008. В графе около 80% китайских веб-страниц (816 млн) и 20% некитайских (158 млн). В нашем статистическом анализе основные свойства графа были схожи с (Jindal и др. [18]). Мы рассчитали PageRank и MobileRank по данному графу.

Топ-10 вебсайтов

В таблице 12 приводится топ-10 веб-сайтов, отранжированных алгоритмами. Мы провели пользовательское исследование и обнаружили, что MobileRank работает лучше PageRank. Например, wap.cnscu.cn по PageRank ранжирован на втором месте, а MR не включил его даже в десятку. После анализа данных, мы обнаружили, что на главную страницу сайта есть 78331 ссылка с 829 других вебсайтов. Топ-5 веб-сайтов генерируют 8720, 5688, 3764 и 2920 входящих ссылок, соответственно. Таким образом, топ-5 вебсайтов создают 31,5% входящих ссылок. По MR эффект возможных бизнес-отношений между wap.cnsci.cn и топ-5 генераторов будет снижен. Другим примером является wap.motuu.com, который ранжируется на 11 место по PR и 474 по MR. На главную страницу сайта ведёт 12357 входящих ссылок с 79 вебсайтов. Топ-5 ссылающихся сайтов генерируют 3350, 2540, 1662, 1541 и 1144 ссылок, соответственно, занимая 82.3% от 12327 ссылок. MR успешно пессимизирует эффект такой ссылочной массы и понижает ранг.

Таблица 12. Топ-10 сайтов по различным алгоритмам.

Фильтрация мусора

Мы случайным образом выбрали 1500 страниц из мобильного веб-графа и вручную разметили их как «мусорные» или нормальные. 441 страница была расценена как бесполезная, какие зачастую создают недобросовестными оптимизаторами при продвижении сайтов.

Аналогично фильтрации спама в разделе «Фильтрация спама», мы используем распределение по блокам для сравнения производительности алгоритмов. Мы отсортировали 158 млн страниц в убывающем порядке соответственно их оценке и распределили на 10 блоков. В таблице 13 показана сводка по наличию бесполезных страниц в блоках.

Таблица 13. Мусорные страницы в блоках.

Видно, что MR работает лучше PR в пессимизации мусорных страниц в последние блоки. Например, в наших данных мусорная страница (рекламная страница) обладает большим числом входящих ссылок. Судя по всему, ссылки были добавлены роботом на несколько форумов. Это хорошо подпадает под типичный паттерн поведения спамеров. По MR (см. формулу 24) при фиксированном числе сайтов, чем больше входящих ссылок с сайта, тем больше штраф на среднюю продолжительность визита. Поэтому MR лучше пессимизирует мусорные страницы, чем PR.

Обсуждение

Ранее было предложено несколько обобщённых фреймворков для ссылочного анализа. Ding и др. [19] скомбинировал принципы PageRank и HITS в единый фреймворк с точки зрения расчёта матриц. Chen и др. [21] расширили HITS для анализа и гиперссылок на странице и взаимодействия пользователей с веб-страницей. Они учитывали два фактора в общем фреймворке и провели ссылочный анализ данных графа. Poblete и др. [20] скомбинировали ссылочный граф и кликовый граф в гиперссылочно-кликовый граф, а затем провели на нём случайное блуждание. Для получение более надёжного случайного блуждания было проведено слияние нескольких типов данных. Работы, описанные выше очень отличаются от предложенного нами алгоритма. Некоторые из них (Ding и др. [19]) стремятся к расчёту матриц, другие ([19][20]) нацелены на слияние сигналов. Предложенный общий фреймворк Маркова основан на процессах Маркова и объясняет факторы расчёт авторитетности страницы. Так же он охватывает [20] в качестве своего частного случая.

Заключение и дальнейшая работа

В данной части работы мы подвели итог общему фреймворку Маркова, необходимого для расчёта авторитетности страницы. В данном фреймворке для моделирования случайного блуждания используется Сетевой Скелетный Процесс Маркова. Авторитетность страницs составляется из двух факторов: доступность страницы и полезность страницы. Эти два фактора могут рассчитываться как вероятности переходов между страницами и среднее время пребывания на странице в Сетевом Скелетном Процессе Маркова. Предложенный фреймворк охватывает многие существующие алгоритмы и помогает в разработке новых. Мы показываем его преимущество путём разработки Зеркального Полумарковского Процесса и применяя его в двух задачах: борьбе со спамом в обычном вебе и расчёте авторитетности страниц в мобильном. Наши эксперименты показали, что фреймворк позволяет мделировать авторитетность по различным определениям, на основе которых мы получаем различные списки ранжирования. Однако потребуется более сложный эксперимент для понимания практической пользы фреймворка в информационном поиске.

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

От фреймворка Маркова к Fresh BrowseRank

В последние несколько лет много внимания уделялось вопросу оценки авторитетности веб-страницы на основе пользовательского поведения. Однако предложенные методы имели ряд недостатков. В частности, предложенные техники работали на единственном снимке графа сёрфинга, игнорируя его природную динамику с непрерывно изменяющейся пользовательской активностью, что приводит актуальность использования метода к нулю. В данной работе предлагается новый метод расчёта важности веб-страницы под названием Fresh BrowseRank. Оценка страницы нашим алгоритмом соответствует её весу в стационарном распределении гибкой модели случайного блуждания, которая управляется чувствительными к обновлениям весами вершин и рёбер. Наш метод обобщает некоторые ранние подходы, обладает расширенными возможностями для захвата динамики Веба и пользовательского поведения и преодолевает стандартные ограничения BrowseRank. Результаты эксперимента показывают, что наш подход способен генерировать более релевантные и более свежие результаты ранжирования по сравнению с классическим BrowseRank.

Введение в Fresh BrowseRank

Оценка авторитетности веб-страницы является одной из самых важных характеристик, используемых алгоритмами ранжирования. Существует множество способов расчёт важности веб-страниц, среди которых есть такие алгоритмы, которые анализируют историю посещений пользователя. В частности, алгоритм BrowseRank [1] измеряет важность веб-страницы посредством расчёта её вероятности в стационарном распределении непрерывного процесса Маркова на графе сёрфинга пользователей. Несмотря на неоспоримые преимущества BrowseRank и его модификаций (см. раздел 2), эти алгоритмы не учитывают временные характеристики Сети. Более новые страницы, вероятно, более релевантны запросам, чувствительным к новизне, чем старые страницы и, как следствие, временная характеристика релевантности документа позволяет провести более чёткое разграничение между релевантными и нерелевантными документами. Учитывая существование регулярно обновляемых ресурсов, посвящённых новостям, политическим вопросам, спортивным обзорам или конференциям, пользователь, скорее всего, ищет информацию, относящуюся к самому последнему событию. По этой причине вопрос создания чувствительного к новизне (свежести, fresh) BrowseRank должен быть весьма актуален для поисковых систем.

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

Широко применяемым методом оценки важности веб-страниц является анализ Веба в виде графа веб-страниц, соединённого гиперссылками. Наиболее известным представителем алгоритмов ссылочного анализа является PageRank (Page и др. [2]). Согласно алгоритму оценка страницы p равна её весу в стационарном распределении дискретного процесса Маркова, который моделирует случайное блуждание пользователя по гиперссылочному графу. Однако подобный метод оценки обладает рядом уязвимостей. В частности, значительная доля страниц и ссылок является ненадёжной и не используется реальными людьми. Прочие варианты используют качественно иной вид данных. Как следствие, моделирование случайного блуждания на плоском гиперссылочном графе не реалистично. В 2008 Liu и др. [1] предложили алгоритм BrowseRank, который рассчитывает важность веб-страницы, используя данные о поведении пользователей. Граф сёрфинга содержит множество информации, такой как время пребывания пользователей на странице, число переходов между веб-страницами и т.д. В отличие от PageRank, основанного на дискретной случайной работе, BrowseRank использует непрерывный процесс Маркова на основе статистики сёрфинга пользователей. Такая модель является более реалистичным подходом к оценке важности веб-страниц. Однако подходящий алгоритм ранжирования должен обладать некоторыми свойствами, которых нет у BrowseRank. Liu и др. в [3], [4] предложили разнообразные модификации алгоритма, которые позволяют устранить некоторые недостатки. В [3] показаны новые способы оценки распределения времени пребывания. В [4] используется Скелетные Процессы Маркова для моделирования случайного блуждания веб-сёрфера. Они показывают, что этот фреймворк охватывает множество существующих алгоритмов (среди которых PageRank, Usage-based PageRank [5], TrustRank [6], BrowseRank Plus, MobileRank [7] и их модификации). Параметры этих алгоритмов могут выбираться таким образом, что они будут работать аналогично классическому BrowseRank. Существуют и другие подходы к вычислению важности веб-страницы с использованием данных о пользовательском поведении, которые не применяют модель случайного блуждания (например, [8]).

Важной проблемой, которая не решена ни одним из упомянутых алгоритмов, является проблема ранжирования новизны. Как показано в [9], граф сёрфинга существенно меняется каждый день. Поэтому страницы, имевшие высокий BrowseRank несколько дней назад, могут не быть авторитетными в настоящий момент.

Yu и др. [10] были первопроходцами в изучении алгоритмов ссылочного анализа, чувствительных к временным характеристикам Сети. Авторы модифицировали PageRank посредством взвешивания каждой гиперссылки в соответствии с её возрастом. Прочие алгоритмы ссылочного ранжирования, чувствительного к новизне, изучались Amitay и др. в [11], Berberich и др. в [12] и [13], Yang и др. в [14], Dai и Davison в [15]. Алгоритм T-Fresh из последней работы обобщает идеи из всех остальных вышеупомянутых публикаций. Однако T-Fresh обладает несколькими недостатками, которых нет в алгоритме APR за авторством Жуковского и др. в [16]. Оба метода основаны на взвешивании графа, которое собирает информацию о свежести страниц и гиперссылок. Dai и Davison вывели два новых фактора важности страницы, которые зависят от свежести самой станиц и свежести ссылок. В отличие от T-Fresh, оценка свежести APR зависит от скомбинированного поведения страниц и ссылок. Такой подход позволяет контролировать влияние обоих типов характеристик на назначаемую оценку. Следуя схожему принципу мы предлагаем методику решения проблемы нечувствительности BrowseRank к новизне.

Фреймворк и пояснения

Популярные поисковые системы постоянно предлагаю пользователям установить в их браузер свои тулбары, которые, помимо полезных возможностей отслеживают сессии пользователей, чтобы использовать собранную информацию для улучшения качества поиска. Анонимная информация, описывающая пользовательское поведение (посещённые страницы, количество посещений, поданные запросы и т.д.) сохраняется в логе браузера. Мы определяем сессии и граф сёрфинга пользователей аналогично Liu и др [1]. Пусть S — это сессия пользователя. Страницами сессии будут p₁(S),p₂(S),…,p_k(s)(S). Для каждого i ∈ {1,2,…,k(S) — 1} тулбар делает запись p_i(S) → p_i+1(S). Мы называем страницы p_i(S), p_i+1(S) соседними элементами сессии S.

Для каждой страницы p из лога браузинга мы определяем число сессий, начатых с этой страницы как s(p). Для каждой пары соседних элементов {p_i,p_i+1} в сессии мы определяем число сессий, содержащих такую пару как I(p_i,p_i+1).

Мы определяем граф сёрфинга пользователя G = (V,E) таким образом: ряд вершин V состоит из всех веб-страниц, упомянутых в логе, а так же из дополнительной вершины x. Набор ориентированных рёбер E содержит все упорядоченные пары соседних элементов {p₁,p₂}. Так же он содержит дополнительные рёбра от последних страниц всех сессий к вершине x. Пусть σ(x) = 0. Для каждой страницы p при условии p → x ∈ E определим число сессий, завершившихся на p как I(p,x).

Освежим в памяти определение BrowseRank. Вероятность сброса σ(p) — это вероятность выбора страницы p при старте новой сессии. Она пропорциональна числу сессий s(p), начинающихся со страницы p. Поэтому σ(x) = 0. Вероятность перехода w(p₁ → p₂) — это вероятность клика гиперссылки p₁→p₂. Она равна I(p₁,p₂)/(∑_{pi → p ∈ E}).

Оцениваемое время пребывания Q(p) страницы p определено в [1]. BrowseRank p равен Q(p)π(p), где

(последние уравнения работают и при p = x), α^_(p) = α(1 — π(x)) + π(x).

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

Fresh BrowseRank

Определим меру новизны страницы. Мы используем фреймворк из работы [16]. Рассмотрим два момента времени τ, Т, τ < Т. Мы разделяем интервал [τ,Т] на К частей: [t_i-1,t_i], i ∈ {1,2,…,K}, t₀ = τ, t_i-t_i-1 = (T — τ)/k. Для каждой страницы p из V определим через t(p) дату создания. Мы считаем, что вершина x была создана в момент времени τ.

Пусть i ∈ {1,2,…,K}. Пусть p ∈ V — это вершина, созданная до t_i. Мы определяем оценку новизны F_i(p) p в i-ом интервале времени следующим образом:

1) Мы определяем начальное значение F_i⁰(p) забирая новизну страницы p и её ссылок как (27):

где a⁰, b⁰ — неотрицательные параметры; n_i(p) = 1 если вершина p создана в i-ом периоде, иначе n_i(p) = 0; m_i(p) — это число посещений страницы в i-ом периоде. Устанавливаем F_i⁰(x) = 0.

2) Начальная оценка F_i⁰(o) распределяется по вершинам через исходящие рёбра (28):

где μ ∈ [0,1], W_i(p) — это оценка, назначенная «локальной» мерой новизны вершине p в i-ом периоде времени. Эта мера определяется таким же образом, как начальная мера F_i⁰ (значения параметров могут отличаться от параметров в уравнении (27)) (29),

Мы хотим «распространить меру новизны» по исходящим со страницы ссылкам, даже если среди них нет свежих ссылок. Поэтому мы увеличиваем вес страницы на 1 (последнее слагаемое в формуле 29), если она была создана до времени t_i. Система, описанная в уравнении 28 иллюстрирует влияние соседей на меру новизны страницы.

3) Наконец, мера новизны F_i определяется как F_i(p) = ΒF_i-1(p) + ΔF_i(p). Мера экспоненциально уменьшается со временем, если нет никакой активности у вершины p (параметр Β из (0, 1)). В действительности F_i(p) = Β_iΔF₀(p) если не было активности за период [τ, t_i].

В уравнении 28 все рассматриваемые вершины и рёбра созданы до момента времени t_i.

Пусть мера новизны назначит странице p в графе G оценку F_k(p). Мы освежаем вероятность перехода путём замены I(p₁,p₂) на I(p₁,p₂)F_k(p₂). Другими словами вероятность свежего перехода w_f(p₁→p₂) ребра p₁→p₂ равно I(p₁,p₂)F_k(p₂)/(∑_p:p1→p∈EI(p₁,p)F_K(p)) и Fresh BrowseRank p равен Q(p)πF(p), где

В таблице 14 представлено описание всех параметров алгоритма.

Таблица 14. Параметры Fresh BrowseRank.

Обучение

Пусть f_q(p) — значение нашей характеристики страницы p и запроса q. Сделаем её запросо-зависимой путём линейной комбинации Fresh BrowseRank с запросо-зависимой характеристикой.

Обучающая выборка содержит коллекцию запросов и наборы страниц V_q¹, V_q²,…,V_q^k для каждого запроса q, которые отсортированы от наиболее релевантных (свежих) к нерелевантным страницам. Другими словами V_q¹ — это набор всех страниц с самой высокой оценкой. Для любых двух страниц p₁ ∈ V_qⁱ, p₂ ∈ V_q^j пусть h(i,j,f_q(p₂) — f_q(p₁)) будет значением пенальти, если позиция страницы p₁ в соответствии с нашим алгоритмом ранжирования выше, чем позиция страницы p₂ но i < j. Функция h — это функция потери (loss function). Мы рассматриваем потери с границами b_ij > 0, где 1 ≤ i < j ≤ k: h(i,j,x) = max {x + b_ij, 0}². Пусть w — это вектор параметров Fresh BrowseRank.

Минимизируем вектор методом градиентной оптимизации. Алгоритм ранжирования новизны требует частой настройки параметров. Простой выбор значений параметров из крупной выборки отнимает много времени. Поэтому применение простой оценки существенно снизит качество поисковой выдачи. Покажем, как мы нашли производную дπ_F/дw_i. Насколько нам известно, мы первые получившие производные от стационарного распределения процесса Маркова когда его вероятности перехода — это функции стационарного распределения другого процесса Маркова (вложенные процессы Маркова широко применяются, см. [15], [16]). Легко найти производные дπ_Fresh/д_α через решение следующей системы линейных уравнений (30), (31).

получаем производную д_w/д_Β(q→p) через нахождение дF_k/д_Β(p) из уравнения:

Представим системы линейных уравнений с решениями дπ_F/д_μ, дπ_F/дα⁰, дπ_F/дα¹ (производные дπ_F/дb⁰, дπ_F/дb⁰ — решения тех же уравнений). Первые уравнения системы аналогичны уравнениям из (5). Нам только требуется выбрать рассматриваемый параметр вместо Β. Остаётся найти дΔF_i/дμ, дΔF_i/дα⁰, дΔF_i/дα¹ (32), (33):

параметры τ, Т, К выбираются из небольшого числа вариантов. Мы рассматриваем интервал времени [τ,Т] длиной в 1 неделю. Параметр К выбирается таким образом, чтобы длина одного периода [t_i-1,t_i] были либо 1 день, либо 6 часов, 3 часа и 1 час.

Результаты эксперимента

Все эксперименты проводились на страницах и ссылках сканированных в декабре 2012 популярной коммерческой поисковой системой. Мы использовали все данные с тулбаров с 10 декабря по 16 декабря 2012. В выборке было 113 млн. страниц и 478 млн. переходов. Для оценки ранжирования мы выбрали ряд запросов, поданных реальными пользователями за период с 14 по 17 декабря. Запрос — это пара «текст запроса, время запроса». Каждый запрос был оценён экспертами, нанятыми поисковой системой. Когда ассессор оценивал пару «запрос, URL», он назначал оценку и новизне страницы в соответствии с временем запроса и оценивал тематическую релевантность страницы запросу. Из-за специфики задания мы рассматривали только чувствительные к новизне запросы, на которые и нацелен наш алгоритм. Чтобы иметь должную релевантность для таких запросов, документы должны были быть и новыми и отвечающими тематике одновременно. Ассессоры были проинструктированы оценивать документы как новые, если тулбар делал запись не раньше 3 дней до момента оценки. Наконец, вышеописанные процедуры вылились в 200 оцененных запросов по новизне и 3000 пар запрос-URL.

Оценка релевантности проводилась по пятибалльной шкале: Идеально, Отлично, Хорошо, Неплохо, Плохо. Мы разделили данные на две части. На первой части (75% данных) мы обучали параметры, а на второй тестировали работу алгоритма. Мы сравнили Fresh BrowseRank с классическим BrowseRank так же, как это делали Dai и Davison [15] и Жуковский [16]. Алгоритмы были линейно скомбинированы по рангам при помощи BM25. Затем параметры Fresh BrowseRank выбирались путём максимизации функции потери. Параметр линейной комбинации BM25 выбирался через максимизацию метрики NDCG. Мы получили следующие параметры:

Параметр K выбирался из набора {7, 28, 56, 168}. В этих случаях длины интервалов [t_i-1,t_i] равнялись 1 дню, 6 часам, 3 часам и 1 часу, соответственно.

Таблица 15 демонстрирует производительность алгоритмов по метрикам NDCG@5 и NDCG@10.

Таблица 15. Производительность.

Заключение

Мы представили Fresh BrowseRank, следующий алгоритм анализа пользовательского поведения, чувствительный к новизне. Мы сравнили его с классическим BrowseRank. Наш алгоритм был протестирован на крупном объёме данных и продемонстрировал превосходство над BrowseRank. Кроме непосредственного интереса наших результатов, они так же могут быть полезны коммерческим поисковым системам, желающим улучшить качество своей выдачи. Естественно, стоит предлагать и другие алгоритмы анализа пользовательского поведения, чувствительные к новизне, на основе нашего фреймворка. По этой причине мы считаем, что наш подход будет фундаментом исследований в данной области. Было бы интересно изучить прочие аспекты пользовательского поведения, однако нам не хватает алгоритмов. Например, стоит представить слой узлов запросов в виде графа. Так же мы представили методику обучения параметров вложенных процессов Маркова. Было бы интересно использовать эти алгоритмы для других алгоритмов, основанных на схожих процессах.