PageRank и Цепи Маркова. Часть II.

Учите матчасть.

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

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

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

Теперь рассмотрим, какие условия определяют цепь Маркова:

Во-первых, у цепи имеется матрица вероятностей перехода:

         (3).

где pij – вероятность перехода из состояния i в состояние j за один шаг процесса.

Матрица (3) обладает следующими свойствами:

         а) ∑pij = 1 j=1…N.  (свойство, вытекающее из замкнутости системы);

         б) pij ³ 0 " i,j.

Во-вторых, у цепи Маркова имеется вектор начальных вероятностей, который описывает начальное состояние системы:

P(0) = < P01, P02,..,P0n >         (4)

Обозначим шаги (этапы) процесса за t = 0, 1,…..

Если P(0) это вектор начальных вероятностей, то P(t) – это вероятностный вектор на шаге t. Значение P(t+1) зависит от P(t). Формула расчета в матричном виде выглядит следующим образом:

P(t+1) = P(t) ∙P       (5).

Отсюда следует, что:

P(t) = P(0) ∙Pt         (6).

В теории цепей Маркова показано, что в пределе, при t стремящемся к бесконечности, вероятности состояний стремятся к определенным предельным значениям, которые удовлетворяют соотношению:

P(*)=P(*)∙P         (7).

Из (7) становится очевидным, следующее важное свойство предельных векторов вероятностей P(*). Заключается оно в том, что P(*) является единственным и не зависит от вектора начальных вероятностей P(0) и определяются только матрицей вероятностей перехода.

Теперь рассмотрим применение данной теории для системы из нашего примера (Рис. 1. Часть I).

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

(9)

 Первая строка матрицы свидетельствует о следующем: со страницы A можно перейти на B, C, и D. Вероятность того, что после A пользователь выберет C равна 1/3. Вероятность выбора D или C тоже равна 1/3.

Вторая строка значит, что со страницы B можно попасть только на A, вероятность этого перехода равна 1. Третья строка – с C можно попасть только на A, вероятность перехода равна 1. Четвертая строка – с D можно попасть только на  B, вероятность перехода равна 1.

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

P(0) = < 1/4, 1/4, 1/4, 1/4>.

Для расчета вектора P(1) применим формулу (5), т.е. P(0) умножим на матрицу вероятностей перехода. Получим P(1) = <0,5; 0,3333; 0,0833; 0,0833>.

Для вектора P(2) формула (5) имеет следующий вид: P(2) = P(1) ∙P. После расчета получаем значения P(2) = <0,4167; 0,25; 0,167; 0,167>.

Рассчитывая значения P(t) по формуле (5) мы найдем t, для которого выполняется равенство (7). Т.е. мы рассчитаем значение предельного вектора вероятностей P(*), который не зависит от вектора начальных вероятностей P(0) и определяется только матрицей вероятностей перехода.

В нашем случае P(*) = <0,429; 0,286; 0,143; 0,143>.

Таким образом, после достаточно большого количества переходов со страницы на страницу уже не имеет значения с какой страницы пользователь начал просмотр, поскольку в результате он окажется на странице A с вероятностью 0,429, на странице B с вероятностью 0,286, на страницах C и D с вероятностями 0,143 (или можно сказать, что 42% пользователей будут на странице A, 29% будут на странице B и на страницах C и D будет по 14% посетителей).

Теперь с полученным вектором P(*)  произведем следующие действия:

0.85∙4P(*) + (1-0,85)

Проведем расчеты:

Для А:         0,85∙4∙0,429 + 0,15 = 1,607.

Для B:         0,85∙4∙0,286 + 0,15 = 1,12.

Для C:         0,85∙4∙0,143 + 0,15 = 0,635.

Для D: 0,85∙4∙0,143 + 0,15 = 0,635.

Получается что, рассчитав предельный вектор вероятностей P(*), умножив его на единичный вектор, умноженный на 4d, и прибавив к нему единичный вектор, умноженный на (1-d), мы получили значении практически равные значениям PR, рассчитанным в первой части статьи.

Сравним два алгоритма (расчет PageRank матричным способом и нахождение предельного вектора P(*) Цепи Маркова) в общем случае. Различие заключается лишь в том, что при расчете значений PR за начальный берется единичный вектор и вводится зависимость PR от коэффициента затухания. А  для расчета P(*) начальный вектор состоит из значений 1/N, где N – количество страниц. Именно поэтому, умножив полученный вектор P(*) на N и d, а также прибавив (1-d) мы получили значения близкие к значениям PR.

Статья любезно предоставлена mediacraft.ru