Supervised Nested PageRank

Основные определения: алгоритмы, экспериментальное исследование.

Ключевые слова: вес страницы, PageRank, случайные блуждания, новизна, свойства контента, интернет поиск, обучение

 

1. ВВЕДЕНИЕ

В настоящее время различные графы, такие, как веб-граф, граф переходов пользователя, граф «запрос-выдача», социальные сети и другие множества со значительным объемом информации на узлах, доступны для больших информационных систем. В некоторых из них, например, поисковых системах или социальных сетевых сервисах, ранжирование на базе графов всегда было одной из ключевых технологий. Наиболее распространенные из методов основаны на моделях случайного блуждания: PageRank [17], HITS [11], и различные их разновидности (см. [9, 18]). Например, алгоритм PageRank оценивает вес узла p как его стационарную вероятность в распределении марковского процесса, который моделирует случайное блуждание по графу (первоначально алгоритм использовался на веб-графах). Случайное блуждание может быть определено в виде совокупности начальных вероятностей и вероятностей переходов. В исходном алгоритме PageRank начальные вероятности для всех узлов равны, так же, как и равны все вероятности перехода для конечных узлов. А в более свежих модификациях алгоритма эти вероятности могут существенно зависеть от свойств узлов и ребер между ними. Например, если узлы — это документы веб-графа [17] или графа переходов пользователя [14], его вершины и ребра могут содержать некоторые метаданные, включающие статистику о взаимодействиях пользователей со страницами (число или средняя продолжительность посещений страницы пользователями или число переходов между ними), их языковые модели или истории их изменений. Такая информация определяет свойства узлов и ребер и может использоваться для более точного «взвешивания» страниц по сравнению с методами, основанными исключительно на геометрической структуре графа.

Существует множество работ, посвященных задаче выбора вышеупомянутых свойств узлов и ребер для ранжирования графа. Модели, описанные в ранних исследованиях [5, 13, 18], используют свойства вершин и ребер «жестким» способом, не допуская их настройку для частных вариантов использования. Авторы поздних работ [5, 6, 8, 9] предлагают более гибкие системы ранжирования, которые могут использовать одни и те же свойства различными способами в рамках некоторой параметрической модели. Другими словами, веса страниц (соответствующие начальным вероятностям) и веса ребер (соответствующие вероятностям переходов) определяются в виде параметрических функций от их свойств, с учетом их значимости, управляя, таким образом, характером случайного блуждания.

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

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

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

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

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

Система ранжирования на базе SNP зависит от вектора параметров. Мы разработали новый градиентный метод оптимизации для настройки параметров модели. Он основан на вычислении производных стационарных вероятностей модели относительно ее параметров. Наш метод оптимизации довольно эффективен: его вычислительная сложность равна количеству шагов градиентного спуска, умноженному на сложность алгоритма PageRank. Метод может использоваться для более широкого класса задач оптимизации с гладкими функциями стационарных вероятностей. Насколько нам известно, мы первые, кто представляет алгоритм формирования оптимальных параметров для вложенных процессов, используемых для ранжирования документов.

Основные тезисы данной статьи следующие:

— Представлен новый алгоритм SNP, основанный на случайном блуждании, определяемом весами узлов и ребер, которые в свою очередь определяются случайными блужданиями на базе их свойств. Этот алгоритм позволяет избавиться от некоторых ограничений подходов на базе линейных моделей ранжирования (PageRank) и позволяет максимизировать качество «взвешивания» страниц.

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

— Произведена оценка нашего алгоритма на базе ссылочного графа с двумя различными наборами свойств узлов и ребер и показано, что наш подход дает более высокое качество, чем передовой метод SSP [7]. Также проведены эксперименты, показывающие, что SNP более устойчив к разреженности значений свойств узлов и ребер по сравнению с SSP.

Нижеследующая часть статьи организована следующим образом.

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

В Разделе 3 описывается алгоритм Supervised Nest PageRank.

В Разделе 4 представлен метод оптимизации, который используется для настройки параметров нашего алгоритма.

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

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

В Разделе 7 подводятся итоги наших исследований, обсуждается их возможное использование и направления будущих работ.

 

2. ОБЗОР АНАЛОГИЧНЫХ ПОДХОДОВ

Основанные на графе методы ранжирования, такие, как PageRank, могут быть параметризированы различными способами. Проблема взвешивания узлов и ребер для лучшего ранжирования страниц возникает на всем множестве вариантов использования графов: ранжирование веб-страниц [5, 7, 9, 13, 17, 18], поиск научных статей и идентификация сущностей [12], поиск по образцу [15], предсказание связей в социальных сетях [1]. Для каждой из указанных прикладных областей существует некоторая информация об узлах или ребрах, которая не учитывается в исходном алгоритме PageRank [17].

Было разработано несколько методов, которые расширяют базовую модель PageRank [7, 9, 18, 21]. В этих работах авторы определяют параметрические модели, где выбор пользователя о переходе к странице непосредственно или через ссылку зависит от их (страницы и ссылки) весов. Однако авторы первой из подобных моделей (например, [9, 18]) не вводят теоретического обоснования метода оптимизации параметров таких случайных блужданий. В [1] Бэкстрем и др. разработали модификацию PageRank под названием Управляемое Случайное Блуждание для задачи предсказания связей. В этой работе только веса ребер зависят от метаданных. Гао и др. [7] обобщили вышеуказанные методы, введя структуру под названием Semi-Supervised PageRank (SSP). Стоит отметить, что множество классических методов ранжирования на базе графа (кроме уже перечисленных), LiftHITS [4], NetRank [3], Laplacian [22]), можно представить в виде частных случаев SSP.

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

Частный случай модели вложенного PageRank, которая рассмотрена в данной статье, был ранее описан Дэем и др. [5] и позже был расширен в [26]. Эти публикации были посвящены проблеме чувствительности алгоритма ранжирования веб-графа к возрасту его вершин. Для ее решения авторы разработали случайные блуждания, определяемые весами, которые по сути являются «свежестью» узлов в веб-графе. В этих подходах вес узла зависит от его собственных свойств, а также от свойств его соседей. Однако данные модели не обеспечены методами оптимизации для настройки их многочисленных параметров. Также в посвященных им статьях не были оценены преимущества, которые дает их сложная структура. Наше же исследование представляет собой попытку обобщить вложенные модели, изучить их преимущества перед более простым, но все же эффективным подходом SSP, и «усилить» их методом оптимизации основных параметров случайных блужданий.

BrowseRank [13] – эффективный метод ранжирования страниц, который использует граф пользовательских просмотров. Основанный на непрерывных марковских процессах, BrowseRank может быть представлен как частный случай SSP со всеми его недостатками (если мы сводим его к дискретному случаю, как предложено в статье). В [27], авторы описывают Fresh BrowseRank, использующий вложенные процессы на графе просмотров с учетом информации о новизне узлов. К сожалению, в этой короткой статье не описывается общая модель, которую можно использовать для широкого класса подобных задач, и не дается теоретического обоснования их собственной модели. При этом SNP, предложенный в настоящей статье, является общей и теоретически обоснованной моделью, которая может быть также использована для непрерывных марковских процессов. Кроме того, авторы [27], не представили какого-либо метода оптимизации параметров, которая сделала бы их модель практически реализуемой (т.е. не был представлен алгоритм вычисления производных), в то время как данный метод является одним из самых значимых преимуществ нашей технологии.

 

3. СУТЬ МЕТОДА

В этом разделе вводится метод ранжирования узлов графа. Пусть R – множество задач ранжирования, и для каждой задачи q {1,2,…R} мы должны определить ранги всех узлов. Например, если мы рассматриваем задачу запросного ранжирования веб-страниц, тогда запрос пользователя можно считать задачей как таковой. Алгоритм ранжирования на основе случайного блуждания использует в качестве входных данных свойства узлов и ребер, которые могут зависеть от условий задачи. Кроме них на выход алгоритма влияют также и его параметры, которые используются для его настройки и, при этом, не зависят от задачи. Ниже представлен алгоритм, определяющий значения параметров вложенных случайных блужданий, которые оптимизируют граф для всех задач в среднем.

3.1 Semi-supervised PageRank 

Пусть q {1…, R} — задачи ранжирования. Определим граф как кортеж , где V — множество n узлов, E — множество ребер,   множество векторов — свойств узлов (V_i^q — вектор свойств узла i размерностью l),   множество векторов — свойств ребер (E^q_ij —  вектор свойств ребра i→j размерностью h). Полагаем, что E_ij = 0, если i→j не существует. Например, для информационного поиска: если ссылка является внешней, то это может быть значимым свойством соответствующего ребра. Аналогично вес страницы, который определяется ее релевантностью, может быть значимым свойством соответствующего узла.

Пусть X, Y — наборы параметров и , : положительные вещественные функции, которые определяют веса в рамках задачи q следующим образом. Для фиксированных значений параметров , веса узла i из V и ребра i→j из E определяются как  и  соответственно. При этом значения функции f (и функции g) зависят от свойств узлов и ребер, а также V^q, E^q. Кроме того, значения функции f (или функции g) для узла i (ребра i→j) может зависеть не только от i-го элемента V^q (от элемента E^q для ребра i→j).

Semi-Supervised PageRank (SSP, [7]) определяется стационарным распределением, полученным на основе случайного блуждания по вершинам графа, которое определено для рассматриваемой задачи q следующим образом. Пользователь переходит от одного узла к другому за один шаг. Находясь в узле i, он решает перейти к любому другому узлу с вероятностью α или исходящему ребру с вероятностью 1-α. Если пользователь идет по ребру, то именно i→j выбирается с вероятностью перехода

(1)

Если пользователь выбирает случайный узел, то j выбирается с начальной вероятностью

(2)

N-мерный вектор  — это стационарное распределение марковского процесса (см. [16]). Таким образом, данное распределение представляет собой решение следующей системы уравнений:

 (3)

Отметим, что это выражение определяет стационарное распределение, при условии, что узлы с суммарным количеством исходящих ребер, равным нулю, отсутствуют (см. [8]). Если данное условие не выполняется, необходимо добавить в граф G дополнительный (виртуальный) узел, смежный со всеми другими узлами графа, как это было предположено в [6]. Значения вероятностей стационарного распределения можно рассмотреть как оценки узлов G, которые являются решением задачи q (см., например, [17, 7]). Предположим, что для каждой задачи q {1…, R} имеется -размерный вектор оценок, выставленных асессорами некоторым  узлам в соответствии с их релевантностью задаче q. Совокупность этих векторов формирует репрезентативное подмножество . В частности, если узлы графа — веб-страницы, то R можно рассматривать как множество запросов. Пусть  — функция невязки двух векторов  и  (например, ранговое расстояние или оценка качества поиска, если эти векторы представляют собой субъективное и идеальное ранжирование соответственно). Рассмотрим среднюю невязку

 (4)

как объект минимизации так, как это было сделано в [15]. Задача оптимизации

может быть решена при помощи градиентных методов (см. Раздел 5.1).

Тип задач q зависит от природы рассматриваемого графа и задачи ранжирования. Например, частная задача предсказания наличия связи [1] состоит в том, чтобы оценить вероятность, с которой некоторые узлы будут связаны с данным в будущем. В такой постановке свойство, определяемое задачей, это бинарная функция, которая идентифицирует узел q. Задачей в ранжировании документов является пользовательский запрос, а свойство узла — оценка релевантности на основе BM25. Когда результат алгоритма не зависит от задачи q, линейную комбинацию с зависимым ранжированием b^q можно представить в виде [7, 26, 27] (см. Раздел 5.1):

(5)

Т.к. метод SSP [7] использует только свойства отдельных узлов и ребер, чтобы определить вероятности перехода через них, то их веса не зависят от «контекста» задачи. Поэтому во внимание не принимается тот факт, что свойства объектов могут в некоторой степени определяться свойствами смежных с ними узлов и ребер. В следующем разделе будет описано, как использовать данное обстоятельство при настройке модели случайного блуждания, используемой для ранжирования.

3.2 Взвешивание узлов и ребер

Здесь мы обсудим возможные методы представления весов , используемых в Уравнениях 1, 2, которые определяют начальные вероятности и вероятности переходов соответственно. Для начала продолжим рассмотрение метода SSP [1, 2, 9] и затем введем наш новый метод, который является его улучшением.

В SSP множества параметров  соответствуют множествам свойств вершин и ребер. Другими словами, веса определяются уравнениями:

 (6)

Эти уравнения, таким образом, определяют в узком смысле линейную зависимость веса узла (ребра) от его вектора свойств. Также стоит отметить, что вес, определенный таким образом, зависит только от свойств рассматриваемого узла (ребра). Данный подход можно обобщить, как это было сделано в [1], рассматривая веса

где — некоторые монотонные функции (в частном случае мы получаем Уравнение 6).

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

Частные случаи таких вложенных процессов Маркова недавно описывались в [5, 26, 27]. В данной статье представлены общие положения для таких процессов и их приложений.

В частности мы предлагаем определять веса вершин и ребер, которые представлены в Уравнении 3, для получения стационарного распределения π уравнениями:

 (7)

где — стационарные распределения  случайных марковских процессов, которые определяют начальные веса вершин (ребер). Отметим, что второе уравнение выражает зависимость только от конечного узла ребра i→j. Это соответствует распространенному методу взвешивания ребер значениями весов их конечных вершин. В рамках нашей работы можно использовать, скажем, линейную комбинацию . Рассмотрим случай  по следующим двум причинам. Во-первых, этот случай — обобщение моделей из [5, 18, 26, 27], означающий, что случайный пользователь двигается в направлении более «тяжелых» узлов так, что вес ребер может быть оценен значимостью их конечных вершин. Во-вторых, не стоит увеличивать сложность алгоритма в отсутствии потребности в дополнительных параметрах.

Стационарное распределение  определяется уравнением, аналогичным Уравнению 3. На этот раз мы предлагаем использовать алгоритм взвешивания, предложенный в SSP, где вершины и ребра оцениваются на основе Уравнения 6. Однако назначения G¹ и G² отличаются, так как они определяют веса f и g, которые играют различные роли в Уравнениях 3, 7. Поэтому оптимальные значения параметров  могут отличаться, поскольку мы используем их для определения G¹ и G². Отметим, что нахождение оптимальных значений данных параметров является нетривиальной задачей: они определяют случайные блуждания, стационарные распределения которых влияют на веса f, g, которые в свою очередь определяют первичный марковский процесс, и его стационарное распределение, которое должно минимизировать функцию F. Каждый из вложенных марковских процессов описывается уравнением:

(8)

где  являются коэффициентами затухания случайных блужданий, а  — начальные веса вершин и ребер соответственно. Это означает, что начальные вероятности этих марковских процессов пропорциональны, а вероятности переходов пропорциональны . Как говорилось ранее, веса  определяются уравнениями, аналогичными Уравнению 6:

 (9)

В отличие от SSP, мы, таким образом, ввели f и g, которые зависят и от свойств вершин, и от свойств ребер согласно Уравнениям 7–9, что является целесообразным, так как эти веса — результат процесса случайного блуждания и, следовательно, могут быть определены полным набором его параметров. Таким образом, в нашем методе взвешивания вектор параметров  (вектор ), который определяет весовую функцию f (функцию g), состоит из двух частей  размерностью l и h, где первая часть соответствует свойствам узлов, а вторая — ребер, и включает дополнительные параметры (коэффициенты затухания):

Подчеркнем, что компоненты этих векторов и компоненты векторов   должны быть неотрицательными для того, чтобы получить неотрицательные веса , определяющие вероятности переходов и начальные вероятности марковских случайных процессов. В Разделе 4 будет рассмотрен метод обучения параметров ω  и φ. Предположим, что для каждого узла сумма  положительна. Тогда транспонирование матрицы , где

 (10)

является стохастическим. Поэтому существует [20] стационарное распределение , которое является единственным решением Уравнения 8, удовлетворяющим условию .

 

4. ОБУЧЕНИЕ

В этом разделе представлено теоретическое обоснование для параметрической оптимизации метода SNP, который мы ввели в 3.2. Во-первых, мы опишем линейные уравнения, которые определяют производные стационарного распределения π. Во-вторых, мы представим алгоритм решения этих уравнений.

4.1 Вычисление производных

Рассмотрим граф G и задачи 1…, R, которые определены в Разделе 3.1. Напомним, что компоненты стационарного распределения марковского процесса π, введенного в Разделе 3.2, определяют решение задачи q (в некоторых случаях свойства узлов и ребер независимы от нее, а в некоторых – зависимы, в этих случаях , где π — стационарное распределение, а b^q — исходная весовая функция, зависимая от задачи). Подчеркнем, что  зависит от вектора параметров , где согласно Разделу 3.2 χ – вектор, состоящий из компонентов ω, компонентов φ, и α, μ¹, μ². Мы минимизируем целевую функцию F, определенную в Разделе 3.1 градиентным методом оптимизации. Согласно Уравнению 4, функция F является композицией H и π^q, так что

Очевидно, что производные H относительно всех ее аргументов легко вычисляются, т.к. для среднеквадратической ошибки измерений . Таким образом, главную трудность представляет вычисление производных  . В SSP производные  и  существуют и могут быть определены на основе следующих систем уравнений:

Чтобы найти производные для нашей методологии, введенной в Разделе 3.2, перепишем Уравнение 3 в матричной форме:

 (11)

где  и

(12)

Подчеркнем, что мы убрали одно уравнение  π(i) из (3), которое соответствует случаю i = n. Фактически, (3) эквивалентно системе , тогда сумма первых уравнений (3) i = 1, 2..., n равна последнему уравнению  из той же системы. Теперь введем системы линейных уравнений для вычисления производных . Аналогичные системы для других производных можно построить таким же способом.

ЛЕММА 1. Функции π(i) дифференцируемы относительно . Кроме того, производные  являются решениями следующих систем линейных уравнений:

(13)

(14)

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

 (15)

Доказательство. Т.к. функции  — полиномы первой степени, решение  (11) состоит из вещественных функций α. Таким образом, π(i) дифференцируемы относительно α в любой точке (0, 1). Рассмотрим левую и правую части Уравнения 3 как две функции от α, заданные в неявном виде. Если π — решение системы, то значения этих двух функций равны для любого α из (0, 1). Поэтому производные этих функций относительно α также равны. Т.к. функции  и  независимы от α, мы получаем Уравнение 13.

Аналогично можно доказать, что  вещественная функция от μ¹. Таким образом, она дифференцируема относительно μ¹ в каждой точке (0, 1), и мы получаем Уравнение 15. Кроме того, вектор π состоит из вещественных функций , которые при этом являются и вещественными функциями от μ¹. Таким образом π(i) также дифференцируемы относительно μ¹ в каждой точке (0, 1).

Рассмотрим левую и правую части Уравнения 3 как две функции от μ¹. Согласно (3) производные этих функций относительно μ¹ равны. Т.к. функция  независима от μ¹, мы получаем Уравнение 14. Таким образом, существование производных   доказано.

Лемма 1 описывает уравнения, которые определяют производные π относительно параметров α, μ¹. Отметим, что все другие производные  могут быть найдены аналогичным способом, и мы не приводим соответствующие уравнения и доказательства, чтобы не загромождать статью.

В Разделе 4.2 представлен алгоритм численного решения систем (Лемма 1),  выходом которого являются производные . Насколько нам известно, мы первые, кто получил градиенты стационарных распределений вложенных марковских процессов относительно их параметров.

4.2 Обучающий алгоритм

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

Запишем Уравнение 3 в следующей форме: , где

 (16)

Согласно эргодической теореме [16], для любого начального распределения π₀ для множества вершин V, стационарное распределение π, определенное Уравнением 3, равняется . Выразим  через π_j. Очевидно

 (17)

Пусть . Из Леммы 1 следует, что существует производная . Найдем производные обеих частей Уравнения 17 относительно :

(18),

где

Рассмотрим также Уравнение 8 и перепишем его в следующей форме: , где  , и для каждой  определяются Уравнением 10.

Согласно эргодической теореме, для любого  и любого распределения  выполняется равенство . Выразим  через . Получим

 (19)

Найдем производные обеих частей Уравнения 19 для случая k = 1 относительно μ¹:

 (20),

где

 (21)

ТЕОРЕМА 1. Для любого  справедливо

.

Доказательство теоремы приведено в Приложении A. На ее основе при помощи (18) можно найти приблизительные значения  и . Фактически мы можем использовать следующую последовательность действий. Во-первых, мы итеративно вычисляем значения  при помощи Уравнений 19–21. Затем мы находим элементы матриц , используя

(22).

Наконец, после того, как получены значения , рекурсивно используем Уравнения 17–18, чтобы вычислить . Согласно Теореме 1 полученные значения являются приближением . Данный алгоритм представлен в Таблице 1.

Таблица 1: Итеративный алгоритм вычисления производных μ1 стационарного распределения Supervised Nested PageRank.

Вход: Выход: Алгоритм: 1. Вычислить 2. Вычислить  при помощи Уравнений 10, 21. 3. Установить 4. Обновить 5. Если  и , то на выход , иначе  и переход на шаг 4. 6. Установить 7. Вычислить  при помощи Уравнений 16, 22. 8. Установить 9. Обновить 10. Если  и , то на выход , иначе  и переход к шагу 9.

 

5. ИСХОДНЫЕ ДАННЫЕ ДЛЯ ЭКСПЕРИМЕНТОВ

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

5.1 Целевая функция

Данные, которые используются для настройки параметров  (см. Раздел 4) представляют собой коллекцию запросов пользователей Yandex. Для каждого запроса q существуют наборы страниц, оцененные вручную и сгруппированные по релевантностям. Обозначим эти группы как  в порядке убывания их релевантностей. Пусть для любых двух страниц   будет штрафной функцией, которая используется в случае, если позиция страницы p₂ согласно нашей ранжирующей функции d_q будет выше позиции страницы p₁, и при этом i<j. Будем рассматривать штраф h с ограничением b_ij>0, где , то есть . Согласно Разделу 3.1, цель оптимизации — минимизация функции

(23)

где

Мы предлагаем сделать это при помощи градиентного метода оптимизации, описанного в [25]. Используем алгоритм, описанный в Разделе 4.2, для вычисления производных. Наш метод оптимизации достаточно эффективен: его сложность равна числу итераций градиентного спуска, умноженному на сложность алгоритма PageRank.

В следующих двух разделах будут описаны свойства, которые влияют на веса узлов во вложенных марковских процессах (скалярные величины ). Все эти характеристики и конечные веса не зависят от запросов. Тогда чтобы сравнить работу алгоритмов для исследования задачи ранжирования, зависимого от запроса, как в [7], будем рассматривать линейную комбинацию независимых весов π со значениями BM25 страниц b^q, которые являются запросозависимыми (см. Уравнение 5). Оценивать полученные результаты будем на основе метрики Normalized Discounted Cumulative Gain (NDCG). Параметр линейной комбинации λ выбирается на первой итерации градиентного спуска из условия максимизации NDCG на обучающей выборке. На последующих итерациях новые значения параметра определяются по формуле: , где τ — постоянная величина шага градиентного спуска,  — номер итерации.

Отметим, что в [7] авторы используют другую целевую функцию,  , где π(i) равняется

Поскольку эта функция запросонезависимая, и решение задачи оптимизации не учитывает оценки релевантностей документов, авторы вводят ограничения на использованиЕ своей технологии. Подчеркнем, что для любого положительного ε мы можем найти вектор π, такой, что , используя итеративный алгоритм из Таблицы 1. Поэтому любой локальный минимум целевой функции является соответствующим минимумом функции  с ограничением вида , где С — некоторое положительное число. Таким образом, получено решение задачи оптимизации для алгоритмов SSP и SNP. Кроме того, вектор высокой размерности является параметром функции R, в то время как целевая функция F не зависит от него. Следовательно, предложенный метод оптимизации имеет значительно меньшую размерность, а потому является на порядки более быстрым с вычислительной точки зрения.

5.2 Параметры графов

В наших экспериментах будем использовать дискретные марковские процессы на основе ссылочного графа. Все эксперименты проводились на базе графа, состоящего из страниц и ссылок, составляющих индекс Яндекса на июнь 2013 года. Используемая коллекция документов собрана в доменном пространстве одной из крупнейших европейских стран. Множество данных содержит 2.52 миллиарда страниц и 21.12 миллиарда ссылок. Так как его размерность очень велика, мы использовали модель Pregel [24] для параллельных вычислений (граф был разбит случайным образом на 700 частей). Чтобы определить веса узлов и ребер, будем рассматривать два множества свойств страниц: используемые SSP в оригинальной статье [7] и временные свойства, представленные ниже.

Как было предположено в [7], для каждого ребра в графе используем десять свойств, включая тип ссылки (т.е., внутренняя или внешняя), количество входящих и исходящих ссылок для донора и акцептора (всего четыре свойства), уровень вложенности URL и длина URL для донора и акцептора (всего четыре свойства), и вес (количество ссылок) ребра. Для каждого узла мы используем 5 свойств, включая количество входящих и исходящих ссылок страницы, количество «двухшаговых» соседей страницы, уровень вложенности и длину URL страницы.

Используем данные из [26] (в которой обобщена модель из [5]) для временных свойств (см. Раздел 2). Пусть T — временной период, который начинается с 1 января 2013. Тогда , если страница p создана в период T, иначе .  и  количества ссылок  и соответственно, созданных в период T так, что по крайней мере одна из страниц p, ˜p появилась после 1 января 2013.  и  являются количеством ссылок  и соответственно, созданных в период T так, что страницы p, ˜p появились ранее 1 января 2013. Рассмотрим следующие временные веса узлов и ребер.

 (24)

Здесь h = 10, l = 5, где l — число свойств узлов, h — число свойств ребер (см. Раздел 3.1).

Для всех методов мы нашли оптимальные значения параметров, минимизирующие целевую функцию F (23) на основе градиентого метода оптимизации (см. Раздел 4.2 и Раздел 5.1). Для ранжирования было сформировано множество запросов, которые задают пользователи одной из европейских стран. Для каждого запроса было проведено оценивание множества страниц профессиональными асессорами, нанятыми Яндексом. Эксперт оценивает пару <запрос, URL> на основе новизны и релевантности страницы относительно запроса. Оценки релевантности выбираются по распространенной шкале: perfect, excellent, good, fair, bad. Данные, которые мы использовали, содержат 126.4 тысячи пар запрос-URL и 16.7 тысяч запросов. Мы выбрали 90% запросов в качестве обучающей выборки для оптимизации параметров. Далее мы сравнили методы на основе усредненной метрики NDCG, вычисленной по оставшимся 10% запросов (тестовая выборка). Подчеркнем, что NDCG вычислялась на обрезанном множестве документов, которое было получено из исходного множества, путем удаления всех неоцененных страниц. Данный подход является наилучшим в условиях неполных оценок [19]. Формат нашего экспериментального исследования более адекватен реальности и поисковой индустрии нежели применяемый авторами SSP, которые оценивали документы тестовой выборки, используя бинарную шкалу релевантностей, и обучали SSP на зашумленных неявных оценках, построенных непосредственно на базе подсчетов кликов на документ.

6. РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТОВ

Оценим алгоритм SNP и алгоритм SSP, используя свойства, описанные в предыдущем разделе. В качестве базы для обоих алгоритмов будем использовать PageRank (как в статье [7]). В Таблице 2 представлены результаты оценивания ранжирования алгоритмов на основе метрик NDCG@3 и NDCG@5.

Таблица 2. Сравнение SSP и SNP

 

Согласно NDCG@3 (@5) преимущество метода SNP по сравнению с SSP составляет 0.8% (0.4%) и 0.5% (0.5%) для временных свойств и свойств SSP соответственно. Это преимущество нельзя рассматривать как незначительное с точки зрения исследуемой задачи ранжирования. Действительно, по NDCG@3 (@5) преимущество метода SSP по сравнению с PageRank составляет 0.4% (0.8%) и для временных свойств и для свойств SSP на нашей коллекции веб-страниц (см. рисунок 1, рисунок 2). Т.е. превосходство SSP над PageRank имеет тот же самый порядок (1% для NDCG@3) в [7]. Кроме того, отранжированные в [7] документы могут быть переоценены, потому что каждый из них оценивался как “релевантный” или “нерелевантный”, в то время как в нашем исследовании использовалась 5-ти ступенчатая шкала релевантности. Также алгоритм BrowseRank [13], основанный на графе случайных блужданий пользователя, имеет преимущество в 1.6% (NDCG@3) по сравнению с PageRank (см. [13]).

Полученные результаты парных тестов для оценки различия между SNP и SSP (во всех случаях) на экспериментальных данных говорят о том, что SNP значительно выигрывает у SSP (см. строки в Таблице 2, соответствующие последним итерациям).

Первоначально PageRank вычислялся с коэффициентом затухания  α=0.15. Для демонстрации важности настройки параметров проведем следующие эксперименты. Во-первых, сравним результаты алгоритмов, использующих временные свойства, соответствующих оптимальным значениям параметров, с алгоритмами с теми же настройками за исключением α, который мы приравняем 0.15 (см. Таблицу 2 и Таблицу 3). Как видно, обучение дает лучшие результаты с точки зрения NDCG@3, @5 (обученные алгоритмы имеют статистически значимое превосходство по сравнению с вышеупомянутыми модификациями). Во-вторых, настройка коэффициента затухания α в классическом алгоритме PageRank (PR), дает лучший результат по сравнению с исходным вариантом (PR ++) (см. Таблицу 3, рисунок 1, рисунок 2). Полученный на основе обучения параметр равен 0.9514.

Таблица 3. Результаты алгоритмов SSP и SNP с α =0.15 и PageRank с α =0.15, α =0.9514

Algorithm	NDCG@3	NDCG@5
Temporal SSP, α = 0.15	0.76542	0.80215
Temporal SNP, α = 0.15	0.76938	0.80491
PageRank, α = 0.15	0.76256	0.79749
PageRank, α = 0.9514	0.76525	0.7998

 

Таблица 4. Результаты алгоритма дляSNP c μ¹ = μ² = 0

Algorithm, μ1 = μ2 = 0	NDCG@3	NDCG@5
Temporal SNP	0.76535	0.79929
SNP, features from [7]	0.75755	0.79465

 

Рисунок 1. Результаты для различных значений λ (используются временные свойства). Алгоритмы: SNP, SNP с начальными параметрами, SSP, SSP с начальными параметрами, PageRank (PR), PageRank c α=0.9514 (PR++)

Рисунок 2. Результаты для различных значений λ (используются свойства SSP). Алгоритмы: SNP, SNP с начальными параметрами, SSP, SSP с начальными параметрами, PageRank (PR), PageRank c α=0.9514 (PR++)

Отметим, что SNP сводится к SSP, если установить μ¹ = μ² = 1. Рассмотрим другой граничный случай μ¹ = μ² = 0, обучив остальные параметры. NDCG@3,5 этих “экстремальных алгоритмов” показаны в Таблице 4. Оценки качества ранжирования всех этих алгоритмов представлены на рисунках 1-2. Из графиков видно, что максимальные значения NDCG@3, @5 по всей области значений λ больше для SNP в обоих случаях (временные свойства и свойства SSP).

Далее в этом разделе мы покажем, как в алгоритме SNP решается проблема разреженности данных. Мы считаем, что только репрезентативная выборка исходного графа позволит ускорить вычисления в этой части экспериментов. Пусть для любого запроса q  H (q) — множество хостов, имеющих по крайней мере одну страницу p релевантную q. L (q) — количество внутренних ссылок на хостах из H(q). Выберем множество X, которое состоит из 12% запросов q с самыми маленькими значениями мощности |L(q)|. Построим начальный граф на основе всех страниц множества  и всех ссылок между ними.

Получим 0.11 миллиардов страниц (4.4% количества вершин в полном графе) и 2.1 миллиарда ссылок (9.9% количества ребер в полном графе). Обучающая выборка состоит из 8327 пар <запрос, URL> и 1990 запросов. Тестовая выборка состоит из 726 пар <запрос, URL> и 187 запросов. Сымитируем разреженность данных, выбирая для каждого временного свойства r% страниц, r ={10, 25, 50, 90}, и удаляя значения данного свойства у этих страниц. На полученном графе вычислим SNP и SSP, показав, что разреженность данных затрагивает SSP существенно сильнее, чем SNP (см. рисунок 3).

Рисунок 3: Разреженность данных.

Сравним SNP с его модификациями, которые не дожидаются выполнения условия остановки сглаживания весов вершин и ребер. Другими словами, рассмотрим измененный алгоритм из Таблицы 1, в котором производится  итераций шага 4, где  — небольшое число. После  итераций рассчитываются значения  по уравнениям шага 5. Отметим, что если приравнять  нулю и вычислить G¹ и G² на шаге 3, то мы получим обычный SSP. Попробуем показать, как значение  влияет на результаты SNP на разреженном множестве данных. Предположительно, стабильность результата тем выше, чем больше итераций производится. Сравним четыре алгоритма, SSP ( = 0), SNP1 ( = 1), SNP2 ( = 2) и SNP. На рисунке 3 представлены результаты ранжирования на их основе. Обучающий алгоритм для параметров  SNP1 и SNP2 такой же, что и SNP. Целевая функция, параметры настройки для метода градиентного спуска у них также одинаковые. Производные вычислены на базе алгоритма из Таблицы 1, но со следующими отличиями. Шаг 4 повторяется 1 раз для SNP1 и дважды для SNP2. Как видно, результаты SNP более стабильны, по сравнению с SSP, SNP1 и SNP2, что говорит о важности повторения итераций (шага 4) до выполнения условия остановки.

ЗАКЛЮЧЕНИЕ

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

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

 

8. ССЫЛКИ НА ЛИТЕРАТУРУ

[1] L. Backstrom, J. Leskovec, Supervised random walks: predicting and recommending links in social networks, WSDM’11.

[2] K. Berberich, M. Vazirgiannis, G. Weikum, Time-aware authority ranking, Int. Math., 2(3), pp. 301–332, 2005.

[3] S. Chakrabarti, A. Agarwal, Learning parameters in entity relationship graphs from ranking preferences, PKDD’06.

[4] H. Chang, D. Cohn, A. K. McCallum, Learning to create customized authority lists, ICML’00.

[5] Na Dai and Brian D. Davison, Freshness Matters: In Flowers, Food, and Web Authority, SIGIR’10.

[6] Nadav Eiron, Kevin S. McCurley, John A. Tomlin, Ranking the web frontier, WWW’04.

[7] B. Gao. Tie-Yan Liu, Wei Wei Huazhong, T. Wang, H. Li, Semi-supervised ranking on very large graphs with rich metadata, KDD’11.

[8] Taher H. Haveliwala, Efficient computation of PageRank, Stanford University Technical Report, 1999.

[9] Taher H. Haveliwala, Topic-Sensitive PageRank, WWW’2002.

[10] N. Kanhabua, K. Nørv°ag, Improving Temporal Language Models for Determining Time of Non-timestamped Documents, ECDL’08.

[11] J. M. Kleinberg, Authoritative sources in a hyperlinked environment, SODA’98.

[12] Ni Lao, William W. Cohen, Relational retrieval using a combination of path-constrained random walks, Journal Machine Learning archive, 81(1), pp. 53–67, 2010.

[13] Y. Liu, B. Gao, T.-Y. Liu, Y. Zhang, Z. Ma, S. He, H. Li, BrowseRank: Letting Web Users Vote for Page Importance, SIGIR’08.

[14] Y. Liu, M. Zhang, S. Ma, L. Ru, User Browsing Graph: Structure, Evolution and Application, WSDM’09.

[15] E. Minkov, William W. Cohen, Learning to rank typed graph walks: local and global approaches, KDD’07.

[16] J. R. Norris, Markov Chains, Cambridge University, 1998.

[17] L. Page, S. Brin, R. Motwani, and T. Winograd, The PageRank citation ranking: Bringing order to the web. https://dbpubs.stanford.edu/pub/1999-66, 1999.

[18] M. Richardson, P. Domingos, The intelligent surfer: Probabilistic combination of link and content information in PageRank, Neural Information Processing Systems, 14, pp. 1441–1448, 2002.

[19] T. Sakai, Alternatives to Bpref, SIGIR ’07.

[20] W. J. Stewart, Introduction to the Numerical Solution of Markov Chains, Princeton University, N.J., 1994.

[21] A. C. Tsoi, G. Morini, F. Scarselli, M. Hagenbuchner, M. Maggini, Adaptive ranking of Web pages, WWW’03.

[22] D. Zhou, J. Huang, B. Scholkopf, Learning from labeled and unlabeled data on a directed graph, ICML’05.

[23] J. Gao, W. Yuan, X. Li, K. Deng, J.-Y. Nie, Smoothing Clickthrough Data for Web Search Ranking, SIGIR’09.

[24] G. Malewicz, M. H. Austern, A. J. C. Bik, J. C. Dehnert, I. Horn, N. Leiser, G. Czajkowski, Pregel: A System for Large-Scale Graph Processing, SIGMOD’10.

[25] J. A. Snyman, Practical Mathematical Optimization: An Introduction to Basic Optimization Theory and Classical and New Gradient-Based Algorithms, Springer, 2005.

[26] M. Zhukovskii, D. Vinogradov, G. Gusev, P. Serdyukov, A. Raigorodkii, Recency-sensitive model of web page authority, CIKM’12.

[27] M. Zhukovskii, A. Khropov, G. Gusev, P. Serdyukov, Fresh BrowseRank, SIGIR’13.

 

ПРИЛОЖЕНИЕ A. ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ 1

Из Леммы 1 известно, что функции  дифференцируемы относительно α и μ¹ . Пусть  — произвольное число. Т.к. , то существует i, такое, что . Тогда существует  и столбец i₀ матрицы А^Т, такой, что . Поэтому сходимость равномерна для  (см. [16]) и, кроме того, существует число , такое, что для довольно большого j выполняется неравенство .

Положим . Из Уравнения 18 и Уравнения 13, которое можно переписать в виде , получим

.

Пусть γ — любое положительное число, а^* — максимальный по модулю элемент . Тогда  существует , такое, что модуль каждого элемента  меньше для всех . Т.к.   и  стохастические, то модуль каждого элемента  меньше .

Выберем j, такое, что . Отметим, что для любого n-мерного вектора ε, такого, что сумма его элементов равняется 0, мы имеем .

Действительно, если ε^* — максимальный модуль элементов ε, тогда разностью n-мерного вектора  и является некоторое распределение . Поэтому . Кроме того, . Так что

Поэтому существует k_0, такое, что для любого   любой элемент  меньше, чем γ/2. Наконец, для любого  любой элемент δ_j меньше, чем γ. Так мы получаем . Таким образом сходимость  доказана.

Аналогично существует , такое, что  и, следовательно, для некоторых δ>0 и любой  выполняется неравенство . Таким образом, для фиксированного  выполняется следующее свойство i₀-го столбца А^Т: .

Сходимость для любого  следует из равномерной сходимости  со скоростью p^j для .

Сходимость  доказывается таким же образом как сходимость .