Марковские цепи, стохастические матрицы и их роль в поисковых и рекомендательных системах

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

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

Основы марковских цепей

Марковское свойство

Марковская цепь — это последовательность случайных величин $\{X_0,X_1,\dots\}${X0​,X1​,…} на конечном (или счётном) множестве состояний $\mathcal{S}$S, для которой вероятность перехода в следующее состояние зависит только от текущего состояния, а не от всей прошлой истории. Формально, условие Маркова записывают так:
$$\Pr(X_{n+1}=j\mid X_n=i, X_{n-1}=i_{n-1},\dots,X_0=i_0) = \Pr(X_{n+1}=j\mid X_n=i)$$

для всех $i,i_0,\dots,i_{n-1},j\in\mathcal{S}$i,i0​,…,in−1​,j∈S.

Если переходные вероятности не зависят от времени (цепь однородна), то цепь полностью определяется матрицей переходов $P$P, где $P_{i,j}=\Pr(X_{n+1}=j\mid X_n=i)$Pi,j​=Pr(Xn+1​=j∣Xn​=i) для всех $i,j$i,j.
Требования нормировки для $P$P таковы: каждая строка матрицы содержит неотрицательные числа, а сумма по строке равна единице. Такие матрицы называют строчно-стохастическими.

Пример простого случайного блуждания

Рассмотрим простой граф $G=(V,E)$G=(V,E), где $V$V — множество вершин, а $E$E — множество неориентированных рёбер. Пусть $X_n$Xn​ — вершина, в которой находится случайный блуждающий «шарик» на шаге $n$n. Если на каждом шаге шарик выбирает одну из соседних вершин с равной вероятностью, то это случайное блуждание — простейшая однородная марковская цепь.
Матрица $P$P такой цепи имеет вид: $P_{i,j}=1/\deg(i)$Pi,j​=1/deg(i), если $\{i,j\}\in E${i,j}∈E, и 0 иначе.

Такое блуждание используется, например, в качестве базовой модели для ранжирования узлов графа.
Заметим, что в неорентированном связном графе при отсутствии периодичности стационарное распределение этой цепи пропорционально степеням вершин: $\pi(v) = \deg(v)/(2|E|)$π(v)=deg(v)/(2∣E∣).

Важные свойства марковских цепей

Марковские цепи обладают рядом свойств, критически важных для практических алгоритмов:

1. Связность (неприводимость). Цепь называется неприводимой, если для любых состояний $i$i и $j$j существует ненулевая вероятность попасть из $i$i в $j$j за конечное число шагов. Эквивалентно, в графовом представлении матрицы переходов сильная связность означает наличие пути между любыми двумя вершинами.
2. Периодичность. Состояние имеет период d>1d>1d>1, если возвращение в него возможно только на шагах, кратных $d$d. Цепь считается апериодичной, если период каждого состояния равен 1. В противном случае цепь периодична. Периодичность приводит к колебаниям вероятностей, что важно учитывать при анализе сходимости.
3. Положительная рекуррентность. Состояние называют положительно рекуррентным, если матожидание времени возврата в него конечно. Для конечных неприводимых марковских цепей все состояния автоматически положительно рекуррентны.

Эти свойства определяют существование и форму стационарного распределения.

Стационарное распределение и фундаментальная теорема

Стационарным (инвариантным) распределением $\pi$π для марковской цепи с матрицей переходов $P$P называется вероятностный вектор ($\pi_i\ge 0, \sum_i \pi_i =1$πi​≥0,∑i​πi​=1), удовлетворяющий уравнению $\pi P=\pi$πP=π. Геометрически это означает, что после применения $P$P распределение не меняется.

Фундаментальный результат гласит: для конечной, неприводимой и апериодичной марковской цепи существует уникальное стационарное распределение. Более того, начиная из любой начальной вероятности, распределение состояний $X_t$Xt​ стремится к $\pi$π при $t\to\infty$t→∞. Этот факт формулируется как Фундаментальная теорема марковских цепей.

Стационарное распределение является левой собственный вектор матрицы $P$P с собственным значением 1; наличие этого вектора гарантируется, поскольку $P$P — стохастическая матрица.

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

Свойство существования единственного стационарного распределения обеспечивает стабильность ранжирования: длительное поведение алгоритма становится независимым от начального состояния и определяется только структурой $P$P.

Стохастические матрицы

В практических алгоритмах, таких как PageRank, часто работают с переходными (или стохастическими) матрицами, определяющими вероятности перехода между состояниями.

Строчно-стохастическая матрица $P$P имеет строки, каждая из которых суммируется к 1. Обратимся к формальному определению. В учебнике по марковским цепям из университета Чикаго подчёркивается, что матрица $P$P называется стохастической, если $P_{ij}\ge 0$Pij​≥0 и $\sum_j P_{ij}=1$∑j​Pij​=1 для каждой строки i. Такие матрицы описывают закон вероятности переходов при стационарном процессе.

Левый и правый собственные векторы

Стохастические матрицы имеют по крайней мере одну собственную пару $(\lambda=1, \pi)$(λ=1,π), где $\pi$π — стационарное распределение.
Кроме левого собственного вектора, часто интересует правый собственный вектор $v$v с собственным значением 1: $Pv=v$Pv=v. Такой вектор отражает ожидание количества посещений состояний при неограниченно долгом отслеживании и часто нормируется иначе (например, по сумме или по инфинити-норме).

Марковские цепи в поисковых системах: PageRank и его вариации

Проблема ранжирования страниц

Ранжирование документов на основе ссылочной структуры — важная задача в информационном поиске.
Простейший подход — считать количество входящих ссылок (in-degree) каждой страницы. Однако такой метод легко обмануть и он не учитывает «качество» страниц-ссылок.

Google в конце 1990-х годов предложил алгоритм PageRank, который моделирует «случайного веб-сёрфера» на графе ссылок. Этот алгоритм интерпретирует важность страницы как стационарное распределение марковской цепи, соответствующей блужданию по гиперссылкам.

Основная модель PageRank

Пусть веб-граф представляет собой ориентированный граф с вершинами-страницами и ребрами-ссылками. По классической модели случайный сёрфер, находясь на странице $i$i, выбирает одну из исходящих ссылок с равной вероятностью.
Если страница не имеет исходящих ссылок (висячая вершина), то сёрфер застрянет. Чтобы избежать «провалов», используются разные ухищрения: например, к каждой такой странице добавляют ссылки на все страницы в графе (равномерно), делают «ленту перезапуска» или используют телепортацию.

Телепортация и Google matrix

Для обеспечения неприводимости и апериодичности вводится телепортация: сёрфер с вероятностью $1-\alpha$1−α (обычно $\alpha\approx 0.85$α≈0.85) внезапно «прыгает» на произвольную страницу согласно фиксированному распределению (обычно — равномерному), и с вероятностью $\alpha$α следует по ссылке.

Формально можно определить Google matrix $M$M как линейную комбинацию матрицы переходов $W$W по ссылкам и матрицы $R$R, описывающей телепортацию: $M = \alpha W + (1-\alpha)R$M=αW+(1−α)R.
Типичный выбор $\alpha=0.85$α=0.85 обеспечивает умеренную вероятность телепортации и гарантирует, что цепь апериодична и неприводима, следовательно, имеет уникальное стационарное распределение.

Вычисление PageRank

Стационарное распределение $\pi$π удовлетворяет уравнению $\pi M = \pi$πM=π. Вектор $\pi$π можно вычислять методом итераций: начиная с произвольного распределения, повторять умножение на $M$M, пока $\pi$π не стабилизируется. При конечном графе и выбранном $\alpha\in(0,1)$α∈(0,1) этот процесс сходится.

Интуитивно PageRank можно интерпретировать как вероятность того, что случайный сёрфер посещает данную страницу в бесконечно длинном блуждании. Более качественные ссылки передают «вес» своим исходящим ссылкам, поэтому страницы, на которые ссылаются авторитетные страницы, получают более высокое значение PageRank.

Ленивая случайная прогулка и периодичность

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

Персонализированный PageRank (Personalized PageRank)

В классическом PageRank все страницы одинаково важны для телепортации. В реальных системах хочется учитывать индивидуальные предпочтения пользователя, его историю переходов, интересующие тематики и т.д.
Персонализированный PageRank (PPR) вводит в модель произвольный вектор телепортации $t$t, задающий распределение, куда телепортируется случайный сёрфер.
Пусть $P$P — нормализованная матрица ссылок, $\alpha$α — коэффициент затухания. Тогда уравнение персонализированного PageRank:$$\mathbf{r}_u = \alpha P^T \mathbf{r}_u + (1-\alpha) \mathbf{t},$$

где $\mathbf{t}$t имеет единицы на позициях, соответствующих интересующим узлам (например, страницам, отмеченным пользователем), и нули на остальных.
Итеративно решая эту систему, получаем вектор $\mathbf{r}_u$ru​, ранжирующий узлы в соответствии с предпочтениями.
Персонализированный PageRank используется, например, для персонализации поиска: если пользователь часто посещает некоторые сайты, то ранжирование можно сместить в их пользу.

Связь PageRank с марковскими цепями: взгляд через эволюцию распределения

Персонализированный и классический PageRank можно интерпретировать как вычисление стационарного распределения марковской цепи с матрицей переходов $M$M.
Если $x(0)$x(0) — начальный вектор распределения, то после $n$n переходов $x(n) = M^n x(0)$x(n)=Mnx(0). Для ленивой прогулки получают $x(n) = 0.5 (A^n + I) x(0)$x(n)=0.5(An+I)x(0), где $A$A — матрица переходов без учёта телепортации. В случае персонализации добавляют телепортацию $E$E, и получаем$$\mathbf{x}(n) = (1-\alpha) A^n \mathbf{x}(0) + \alpha E.$$

При $n\to\infty$n→∞ этот вектор сходится к стационарному распределению, которое и есть искомый PageRank или персонализированный ранг.

Марковские цепи в рекомендательных системах

Мотивация: проблема качества и контекста

Рекомендации товаров, контента и друзей — одна из ключевых задач в e‑commerce и социальных сетях.
Классические методы — контентные (content-based) и коллаборативные (collaborative filtering) — анализируют схожесть между пользователями и товарами, основываясь на атрибутах и истории покупок. Однако эти подходы имеют ограничения: проблемы холодного старта, высокую размерность данных, необходимость согласовывать различные источники информации и т.д.

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

Общая идея: граф, случайное блуждание и стационарное распределение

Рассмотрим гетерогенный граф, где вершины — это пользователи, товары, теги, локации и т.д., а рёбра отражают взаимодействия (покупки, оценки, friendship‑связи).
Мы можем определить матрицу переходов $P$P так, чтобы случайный блуждающий «агент» переходил по рёбрам согласно выбранным вероятностям (равномерно или взвешенно).
Затем на каждом шаге с некоторой вероятностью $\alpha$α агент телепортируется обратно к исходной вершине (пользователю) — это random walk with restart (RWR).

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

Random Walk with Restart в системе рекомендаций

RWR — один из самых распространённых алгоритмов случайных блужданий в рекомендательных системах.
Процесс выглядит так:

1. Строим граф из пользователей, предметов и других сущностей (тегов, локаций, событий).
2. Задаём матрицу переходов $P$P, которая определяет вероятности переходов между вершинами. В простейшем случае из вершины выходит 1/$\deg(i)$deg(i) на каждое ребро; возможны и взвешенные варианты.
3. Определяем коэффициент перезапуска $\alpha\in(0,1)$α∈(0,1). На каждом шаге с вероятностью $\alpha$α агент «возвращается» на узел источника (как правило, представленный одним пользователем), а с вероятностью $1-\alpha$1−α переходит на соседнюю вершину.
4. Итеративно вычисляем stationary distribution $r$r из уравнения $\mathbf{r} = \alpha P^T \mathbf{r} + (1-\alpha) \mathbf{e}_u$r=αPTr+(1−α)eu​, где $\mathbf{e}_u$eu​ — вектор, единичный на позиции узла‑источника.
5. После сходимости сортируем вершины (например, товары) по убыванию компонентов $r$r и выдаём топ‑$k$k рекомендаций.

Ключевое преимущество RWR — способность учитывать не только прямые связи между пользователями и товарами, но и опосредованные связи через другие сущности; кроме того, вероятность перезапуска подавляет влияние длинных путей, вызывая экспоненциальное затухание влияния отдалённых узлов.

Примеры применения RWR

Рекомендации точек интереса (POI) в социальных сетях

В исследовании для социальных сетей с привязкой к местоположению пользователи, локации и связи «друзей» были представлены как вершины графа, а ребра отражали отношения «посетил», «дружит» и т.п.
Для каждого пользователя $i$i определяли RWR: на каждом шаге с вероятностью перезапуска возвращались на узел пользователя $i$i. Стационарное распределение использовалось для ранжирования локаций: локации с более высокой вероятностью считались более подходящими. При этом учитывались как социальные связи, так и посещения друзей.
Авторитетные локации оказывались те, которые были связаны по множества путей через друзей, посещённые места и комбинации этих факторов.
Исследование также показало, что взвешенные варианты переходов (учитывающие частоту посещений) могут изменять результаты; в некоторых сценариях RWR уступал коллаборативным методам из‑за разных предпочтений пользователей в сети.

Фолксономии и музыкальные рекомендации

Другой пример — фолксономии: пользователи, теги и предметы (например, фотографии) образуют три типа узлов. Рёбра связывают пользователей с тегами, теги с предметами и т.д.
Применение RWR позволяет совместно учитывать теги, социальные связи и действия пользователей. Так в работе I. Cantador и коллег RWR использовали для ранжирования предметов, комбинируя связи «user–tag», «tag–item» и «item–user».
Аналогичный подход применили I. Konstas и соавторы для музыкальных рекомендаций: они совместили информацию о прослушиваниях, социальные связи и теги и получили RWR‑ранг для музыкальных треков.
Особенность RWR — возможность легко расширять граф дополнительными сущностями и связями, что помогает учитывать богатый контекст.

Поддержка многомерных запросов

В работе Lee и соавторов персонализированный PageRank был расширен до поддержки многомерных запросов. Вместо одного источника использовался вектор запроса $\mathbf{q}$q, задающий несколько доменов (например, пользователь, местоположение, погода). Результатом была модифицированная формула:$$\mathbf{r} = \alpha P^T \mathbf{r} + (1-\alpha)\mathbf{q},$$

где $\mathbf{q}$q нормируется так, чтобы сумма его компонент равнялась единице. Такой подход позволял учесть взаимодействие между несколькими факторами запроса, а стационарное распределение давало релевантность узлов относительно сразу нескольких условий (например, рекомендации песен, учитывая пользователя, местоположение и погоду).

Преимущества и ограничения методов случайных блужданий

Преимущества:

• Учет глобальной структуры. Случайные блуждания рассматривают весь граф, а не только локальные связи. Это позволяет находить релевантные объекты даже при отсутствии прямой связи с пользователем.
• Борьба со спарсностью. RWR эффективно распространяет информацию по графу; вероятность телепортации делает алгоритм устойчивым к отсутствию связей.
• Унификация разных факторов. Различные типы сущностей и отношений (социальные связи, теги, контент) легко включить в один граф и обработать общим методом.
• Возможность предварительного вычисления. Стационарные распределения можно предрассчитать для каждого узла, что ускоряет выдачу рекомендаций в онлайне.

Ограничения и вызовы:

• Большие графы. Веб‑граф и графы в рекомендательных системах могут включать миллионы узлов. Вычисление стационарного распределения требует итераций и может быть ресурсоёмким.
• Выбор коэффициента α\alphaα. Слишком высокая вероятность перезапуска делает процесс почти случайным, а слишком низкая — заставляет сёрфера застревать в локальных кластерах. Подбор $\alpha$α и матрицы телепортации влияет на качество результатов.
• Интерпретация результата. Вектор стационарного распределения показывает относительные вероятности, но не всегда очевидно, как переводить их в пользовательские рейтинги или оценки.

Стохастические модели динамики ранжирования в App Store Optimization (ASO)

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

Аппарат марковских цепей помогает понять, что позиция в выдаче — это не путь к вершине, а случайная величина, флуктуирующая вокруг некоторого стационарного уровня (определяемого конверсией, удержанием, рейтингом, релевантностью и др.).
Если процесс ранжирования формализовать как блуждание по состояниям $S$S, где каждое состояние соответствует диапазону позиций, то вероятности переходов $P_{ij}$Pij​ будут зависеть от текущих метрик (CTR, CVR, retention) и действий конкурентов. При фиксированном $P$P цепь придёт к стационарному распределению по позициям.

Это даёт важный практический вывод: разовые всплески позиции (например, скачок с 80‑го места на 50‑е) сами по себе не свидетельствуют о поступательном движении к топ‑1. Такие скачки могут быть просто реализациями случайного блуждания, распределённого вокруг определённого среднего.

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

Короче

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

Благодаря фундаментальной теореме о существовании и единственности стационарного распределения для неприводимых апериодичных цепей, алгоритмы типа PageRank, персонализированный PageRank и Random Walk with Restart обладают детерминированным «предельным» поведением: их результат не зависит от начального состояния и стабильный при длительном выполнении.

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

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