Схема Бернулли. Цепи Маркова (стр. 10 из 11)
Таблица 3
| c1 | t(F(·)) | t(G(·)) | e(F(·)) | e(G(·)) |
| 0 | 57 | 69 | 1 | 2 |
| 1 | 4 | 3 | 8 | 8 |
| 2 | 4 | 2 | 7 | 13 |
| 3 | 4 | 1 | 2 | 2 |
| 4 | 0 | 0 | 3 | 7 |
| 5 | 13 | 7 | 61 | 50 |
| Среднее | 3.50 | 2.35 | 13.95 | 12.37 |
Сделаем два вывода на основании данных последней таблицы. Во-первых, частотный анализ (метод, основанный на схеме Бернулли) работает плохо (имеется максимум два точных ответа). Однако, он все-таки дает какую-то информацию об авторе, ибо в случае совершенно случайного выбора истинного автора средний результат в последних двух столбцах был бы около 40. Во-вторых, выбрасывание слов, начинающихся с заглавной буквы, заметно улучшает результаты (даже при частотном анализе). Действительно, столбцы с функцией G(·) заметно лучше столбцов с функцией F(·).
Заключение проведенного опыта
Из данных таблицы 3 хорошо видно, что оценка (2.1), основанная на анализе числа употреблений диад (двухбуквенных сочетаний), значительно эффективней оценки (2.2), основанной на частотном анализе одиночных букв, и правильно указывает автора с большой долей уверенности (84% против 3%). Можно было бы ожидать превосходство оценки (2.1), поскольку она использует больше информации об исходном тексте. Следует подчеркнуть удивительную точность (2.1) при распознавании истинного автора произведения (например, метод авторского инварианта принципиально не может различить более 10 писателей, а здесь рассмотрено свыше 80). Такая точность несомненно должна привлечь внимание к изложенному методу.
Отмечается существенное улучшение качества распознавания автора текста при выбрасывании слов, начинающихся с заглавной буквы. Этот феномен еще требует своего объяснения.
Как уже говорилось, А.А. Марков весьма интересовался задачей определения авторства текста (об этом свидетельствует его статья). Знаменательно, что его собственная идея о "связи испытаний в цепь", опробованная им же на литературном материале, привносит прогресс в решение этой задачи.
3.2 Применение PageRank
На данный момент Google является одной из самых популярных поисковых систем Интернет. При поиске и ранжировании документов Google основывается на содержании страницы, ключевых словах в заголовке и описании. Но так же система опирается на значения PageRank. PageRank является числом, отображающим важность страницы. Таким образом, после того как учтено содержание страницы, ключевые слова на ее положение влияет значение PageRank.
Если рассматривать поведение абстрактного пользователя сети, который нажимает на ссылки случайным образом и при этом в любой момент может закрыть браузер и прекратить просмотр по каким-либо причинам, то здесь естественным образом возникает вопрос, с какой вероятностью случайный пользователь попадет на ту или иную страницу и от чего эта вероятность зависит. Очевидно, что если на страницу нет ни одной ссылки, то ни уйти с нее, ни попасть на нее практически невозможно. Также если все страницы сети ссылаются на какую-то одну, то вероятность просмотра такой страницы пользователем значительно повышается. При этом вероятность посещения страниц, на которые в свою очередь будет ссылаться эта, тоже повысится. Таким образом, вероятность просмотра страницы зависит от количества ссылок на нее и от вероятности просмотра страниц ссылающихся на нее. Видимо, именно для расчета вероятности посещения страницы был разработан алгоритм PageRank.
Реализация алгоритма расчета PageRank неизвестна наверняка, но общий принцип самого алгоритма был опубликован в статье «The Anatomy of a Large-Scale Hypertextual Web Search Engine».
Для расчета PageRank используется следующая формула:
PR(A) = (1-d) + d∙ ( PR(T1)/C(T1) + … + PR(TN)/C(TN)) (1),
где PR(A) – PageRank страницы А;
T1… Tn – страницы, ссылающиеся на А;
C(T1) – количество ссылок страницы T1;
d – коэффициент затухания, находится в пределах от 0 до 1, обычно равен 0,85.
Также на PageRank наложено ограничение:
∑PRj = N, j=1…N (2),
где N – количество страниц в сети.
Данное условие следует из того, что сумма всех вероятностей не может превышать единицу, т.е. вероятность пребывания на данной странице равна отношению значения PageRank к числу всех страниц.
Для учета вероятности того, что пользователь закроет страницу, введен коэффициент затухания d.
Расчет PageRank помогает учитывать индивидуальность каждой страницы сети. Также один из плюсов PageRank заключается в том, что в связи со сложностью алгоритма его расчета на него практически невозможно влиять искусственным образом.
Рассмотрим расчет PageRank для простейшей сети, состоящей из четырех страниц (рис. 1).
Рис. 1.
Пусть изначально PageRank всех страниц равен 1.
Теперь посчитаем значения PageRank на первом шаге, используя (1):
PR(A) = (1-0,85) + 0,85∙ ( PR(B)/1 + PR(C)/1).
Затем подставим в формулу PR(B) и PR(C) равные 1:
PR(A) = 0,15 + 0,85∙ ( 1/1 + 1/1) = 1,85.
Для B:
PR(B) = (1-0,85) + 0,85∙ ( PR(A)/3 + PR(D)/1) = 0,15 + 0,85∙ ( 1/3 + 1/1) =
1,28333.
Для C:
PR(C) = (1-0,85) + 0,85∙ ( PR(A)/3) = 0,15 + 0,85∙ ( 1/3) = 0,43333.
Для D:
PR(D) = (1-0,85) + 0,85∙ ( PR(A)/3) = 0,15 + 0,85∙ ( 1/3) = 0,43333.
В результате мы получили новые значения PageRank для всех страниц.
Теперь посчитаем значения PageRank на втором этапе:
PR(A) = 0,15 + 0,85∙ ( PR(B)/1 + PR(C)/1)
Здесь мы опять подставим PR(B) и PR(C), но уже равные не 1, а их значения, полученные на предыдущем шаге:
PR(A) = 0,15 + 0,85∙ (1,28333/1 + 0,43333/1) = 1,609.
Для остальных страниц:
PR(B) = 0,15 + 0,85∙ ( PR(A)/3 + PR(D)/1) = 0,15 + 0,85∙ (1,85/3 +
0,43333/1) = 1,425.
PR(C) = 0,15 + 0,85∙ ( PR(A)/3) = 0,15 + 0,85∙ ( 1,85/3) = 0,674.
PR(D) = 0,15 + 0,85∙ ( PR(A)/3) = 0,15 + 0,85∙ ( 1,85/3) = 0,674.
Таким образом, мы получили значения PageRank на втором шаге, которые будут использоваться при расчете значений PageRank на третьем шаге. Затем необходимо проделывать эту операцию снова и снова, используя каждый раз значения PageRank рассчитанные на предыдущем этапе.
Смысл заключается в том, что нам придется проделать достаточно большое количество шагов (чем больше страниц в системе, тем больше будет количество шагов) и в результате после какого-то шага n на всех последующих шагах, начиная с n+1, значения PageRank будут неизменными. Для нашего примера достаточно проделать 10 шагов, чтобы значения PageRank выглядели следующим образом:
PR(A) = 1,637;
PR(B) = 1,136;
PR(C) = 0,614;
PR(D) = 0,614.
На 11 шаге, используя эти значения, мы получим новые PR, которые будут равны этим. На 12, 13, …,т.е. на всех последующих этапах произойдет тоже самое. Таким образом, можно сказать, что это и есть значения PageRank для данной системы. Сумма всех PR равна 4, т.е. условие (2) выполняется.
Также PageRank можно рассчитать не итерационным методом, как это сделано выше, а матричным.
Для этого составляется матрица следующего вида:
Данная матрица соответствует нашей простейшей сети (Рис.1.), т. е. страница A ссылается на B, C, D. Страница B ссылается на A. Страница C ссылается на А и D ссылается на В. При этом значения каждой строки делятся на количество ссылок данной страницы. Т.е. значения строки А поделены на 3, а значения всех остальных строк поделены на 1.
Данную матрицу необходимо умножить на значения PR предыдущего шага, полученный вектор умножить на единичный вектор, умноженный на d, и прибавить к результату единичный вектор, умноженный на (1-d).
После расчета мы видим, что страница A имеет самый высокий PR в нашей сети, страница B – более низкий, т.е. вероятность попасть на страницу A больше всего. Поэтому если все четыре страницы, будут по содержанию соответствовать какому-то запросу поиска, то несмотря на достаточно похожее содержание страниц, после учета значений PR, страница A окажется на первом месте, B – на втором, а C и D – на третьем.Поскольку PageRank, имеет отношение к вероятности просмотра страниц, то для лучшего понимания, стоит обратиться к такому разделу теории случайных процессов как теории Марковских процессов.
Под Марковским процессом подразумевается процесс, для которого вероятность находиться в данном состоянии, на данном этапе процесса можно вывести из информации о предшествующем состоянии. Цепью Маркова называется Марковский процесс, для которого каждое конкретное состояние зависит только от непосредственно предыдущего. Число состояний цепи Маркова конечно, а вероятности перехода из одного состояния в другое не зависят от времени.
Следуя из определения можно сказать, что рассматриваемый нами процесс поведения абстрактного пользователя сети является Марковским, и даже более того, является Цепью Маркова.
Теперь рассмотрим, какие условия определяют цепь Маркова:
Во-первых, у цепи имеется матрица вероятностей перехода:
где 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) и определяются только матрицей вероятностей перехода.