Схема Бернулли. Цепи Маркова

Цепи Маркова как обобщение схемы Бернулли, описание последовательности случайных событий с конечным или счётным бесконечным числом исходов; свойство цепей, их актуальность в информатике; применение: определение авторства текста, использование PageRank.

Рубрика Математика
Вид дипломная работа
Язык русский
Дата добавления 19.05.2011
Размер файла 348,5 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

Анализ частот употреблений букв (схема Бернулли)

Схемой Бернулли в теории вероятностей называется последовательность независимых одинаково распределенных случайных величин. Формально мы можем предположить, что последовательности fi,j и x являются реализациями последовательности независимых одинаково распределенных случайных величин, принимающих значения в A, а x распределен как величины класса ?, где ? - неизвестный параметр. Тогда оценка (2.1) принимает вид

e(x) = argmini Gi(x), (2.2)

где

Gi(x) = ? ?k ?k ln((?kЧhi)/(hi,kЧ?)),

где сумма вычисляется по таким k, что ?k > 0, а ? = ?k?k, hi = ?k hi,k и. Грубо говоря, производя оценку ?(x) мы производим частотный анализ текста. Статистический эксперимент показывает, что оценка e(x) существенно хуже оценки t(x).

Модельный эксперимент

Сначала проведем проверку нашей методики на следующем примере. Рассмотрим следующие произведения К. Булычева, А. Волкова, Н.В. Гоголя и В. Набокова.

Мы хотим проверить эффективность оценки t(F(y)). Предлагается следующий способ: выбрать каждого автора i (i = 0,1,2,3) по одному контрольному произведению y i, оценить матрицы ?i по другим произведениям fi,j, а затем найти t(F(yi)). Если оценка работает хорошо, то для каждого автора i должно быть t(F(yi)) = i.

0) К. Булычев: Умение кидать мяч ( y0); Белое платье золушки (g0,1); Великий дух и беглецы (g0,2); Глубокоуважаемый микроб (g0,3); Закон для дракона (g0,4); Любимец [Спонсоры] (g0,5); Марсианское зелье (g0,6); Миниатюры (g0,7); "Можно попросить Нину?" (g0,8); На днях землетрясение в Лигоне (g0,9); Перевал (g0,10); Показания Оли Н. (g0,11); Поминальник XX века (g0,12); Раскопки курганов в долине Репеделкинок (g0,13); Тринадцать лет пути (g0,14); Смерть этажом ниже (g0,15);

1) А. Волков: Семь подземных королей ( y1); Волшебник изумрудного города (g1,1); Урфин Джюс и его деревянные солдаты (g1,2); Огненный бог Марранов (g1,3); Гениальный пень (g1,4); На войне, как на войне (g1,5); О чем молчали газеты... (g1,6); Преступление и наказание (g1,7); Эпилог (g1,8); Желтый Туман (g1,9); Тайна заброшенного замка (g1,10);

2) Н.В. Гоголь: Рассказы и повести (y2, названия повестей: "Повесть о том, как поссорился Иван Иванович с Иваном Никифоровичем", "Старосветские помещики", "Вий", "Записки сумасшедшего"); Ревизор (g2,1); Тарас Бульба (g2,2); Вечера на хуторе близ Диканьки (g2,3);

3) В. Набоков: Другие берега (y3); Король, дама, валет (g3,1); Лолита (g3,2); Машенька (g3,3); Рассказы (g3,4); Незавершенный роман (g3,5).

Например, у А. Волкова контрольным произведением является y1, т.е. "Семь подземных королей" Все остальные произведения используются для вычисления ?i. Результаты вычислений представляются следующей таблицей.

Таблица 1

N

Автор

c1

c2

c3

c4

0

К. Булычев

0

15

2345689

75161

1

А. Волков

0

8

1733165

233418

2

Н.В. Гоголь

0

3

723812

243767

3

В. Набоков

0

5

1658626

367179

Столбец c2 содержит общее число файлов, в которых хранятся произведения автора. Заметим, что число файлов может не совпадать с числом произведений по двум причинам: во-первых, несколько произведений одного автора могут находится в одном файле (здесь такое произошло с А. Волковым - три повести "Желтый Туман", "Тайна заброшенного замка" и "Огненный бог Марранов" были в одном файле); во-вторых, одно большое произведение может разбиваться на несколько частей (последнее необходимо учитывать при изучении таблицы 2).

В колонке c3 содержится суммарное число символов (букв и пробелов) в F(gi,j): c3 = ?j ?F(gi,j)?. В колонке c4 содержится число символов в F(yi), т.е. c4 = ?F( yi)?. Например, для К. Булычева общий объем текстов ?jF(g0,j) составляет 2'345'689. Общий объем F(y1), т.е. число символов A в повести "Умение кидать мяч", выбранной в качестве контрольного текста, равно 75'161.

В столбце c1 в строке j находится ранг числа Lj(F( yj)) среди чисел {Li(F( yj)) ? i = 0,1,2,3}. Под рангом мы подразумеваем номер Lj(F(yj)) среди чисел {Li(F( yj)) ? i = 0,1,2,3}, расположенных в порядке невозрастания. Например, если j = 1 и Li расположились в порядке L0 ? L3 ? L2 ? L1, то рангом L1 будет 3. А если j = 0 и Li расположились в том же порядке L0 ? L3 ? L2 ? L1, то рангом L0 будет 0. Ранг Lj(F(yj)), среди чисел {Li(F( yj) ? i = 0,1,2,3} совпадает с рангом Lj(F(yj))/?F(yj)?, среди чисел {Li(F(yj))/?F(yj)? | i = 0,1,2,3}. Расположим в строках j = 0,1,2,3 следующей матрицы по 4 числа Li(F( yj))/?F( yj)?, i = 0,1,2,3:

В каждой строке найдем ранги чисел Li:

R--=

жззззи--

_

3

2

1

2

_

3

1

2

3

_

1

2

1

3

_

цччччш--

.

Искомые числа столбца c1 стоят на диагонали. Вспоминая формулу (2.1), мы заключаем, что t(F( yj)) = j тогда и только тогда, когда ранг Lj(F(yj))/?F( yj)? среди чисел {Li(F( yj))/?F( yj)? ?i = 0,1,2,3} просто равен 0. Следовательно, если в какой-либо строке в столбце c1 таблицы 1 стоит 0, то авторство контрольного текста определено правильно. Из таблицы 1 мы видим, что у всех писателей авторство определено верно.

Прежде, чем обсудить этот результат, поясним, почему столбец c1 задан таким образом. Дело в том, что если авторство определено неверно (т.е., оказалось t(F(yj)) ? j), то нас может интересовать, насколько мы были близки к правильному ответу. Если ранг Lj(F(yj))/?F( yj)? среди чисел {Li(F( yj))/?F( yj)? ?i = 0,1,2,3} равен 1, то мы ошиблись всего на одного писателя. Такой случай существенно лучше случая ранга Lj(F( yj))/?F( yj)? равного 3, поскольку тут правильный писатель оказывается в списке претендентов на его собственное произведение последним, что свидетельствует о большей ошибке.

Кроме того, матрица R сама по себе допускает интересные интерпретации. Например, из первой строки мы видим, что контрольное произведение К. Булычева "Умение кидать мяч" после самого К. Булычева больше походит на В. Набокова, затем на Н. Гоголя, и в последнюю очередь на произведения А. Волкова. Из последующих двух строк можно сделать вывод, что контрольные произведения А. Волкова и Н. Гоголя также в первую очередь походят на произведения В. Набокова. Может быть, это вызвано тем, что сам Набоков исторически находится между Н. Гоголем и парой писателей: А. Волковым и К. Булычевым? Если эта гипотеза верна, то наша метод чувствителен к исторической эпохе, в которую создано произведение. Некоторое подтверждение тому мы находим в последней строке матрицы R: контрольное произведение В. Набокова похоже в первую очередь на пару А. Волкова и К. Булычева, и лишь затем - на Н. Гоголя. Если бы пара А. Волкова и К. Булычева разбивалась Н. Гоголем. то мы имели бы аргумент против нашей гипотезы. Впрочем, возможны другие интерпретации матрицы R, и автор нисколько не настаивает на выше приведенной.

Можно интересоваться зависимостью матрицы R от

а) числа и объема текстов обучающих выборок;

б) однородности по жанру;

в) однородности по тематике;

г) длины контрольного текста;

д) единицы анализа (на уровне букв, слов и предложений)

и многих других параметров. Ниже мы приводим информацию относительно пункта а). Вкратце вывод таков: методика работает удовлетворительно (то есть, на диагонали матрицы R в основном стоят 0) при объеме обучающей выборки свыше 100 тысяч символов ASCII, и объеме контрольного текста свыше 100 тысяч символов ASCII.

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

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

В электронной библиотеке "Самые любимые книжки" нашлось n = 82 различных автора, которые творили в XIX-XX веках. Количество произведений разных авторов колебалось от 1 до 30 (например, у Аркадия и Бориса Стругацких). У немногих авторов, у которых нашлось лишь одно произведение (например, у Бориса Стругацкого), оно было поделено на две части, одна из которых использовалась в качестве контрольного текста. При отборе произведений учитывался объем: выбирались авторы, суммарный объем произведений которых превышал 100000 символов ASCII. Общее число произведений (романов, повестей, рассказов и т.п.) превысило 1000. Они были представлены в 386 файлах. Общий объем данных составил 128Ч106 символов ASCII.

Для каждого автора мы составили список gi,j текстов, из которых были получены оценки ?i, и оставили один текст yi, подлежащий распознаванию и не используемый при оценке ?i. Следуя схеме, описанной в предыдущем разделе, мы провели эксперименты для проверки качества оценок t(F(·)), t(G(·)), e(F(·)), e(G(·)) на этих 82 писателях. Для экономии места мы приведем лишь таблицу, отображающую информацию об эффективности оценки t(G(·)). Эта таблица составлялась подобно таблице 1. Ради экономии места соответствующие таблицы L и R не приведены.

Таблица 2

N

Автор

c1

c2

c3

c4

0

К. Булычев

0

15

2007724

64741

1

О. Авраменко

0

6

1733113

223718

2

А. Больных

0

6

1294721

373611

3

А. Волков

0

8

1478932

202495

4

Г. Глазов

0

5

1398323

184593

5

М. и С. Дяченко

0

5

1754213

197039

6

А. Етоев

0

5

267096

80358

7

А. Кабаков

0

4

905502

222278

8

В. Каплан

0

6

515029

129608

9

С. Казменко

3

4

1846161

156768

10

В. Климов

0

3

250231

179903

11

И. Крашевский

0

2

1183722

481795

12

И. Кублицкая

0

1

282377

170469

13

Л. Кудрявцев

1

3

583239

179093

14

А. Курков

0

6

628041

218726

15

Ю. Латынина

10

2

2628781

283565

16

А. Лазаревич

46

3

310553

94629

17

А. Лазарчук

0

5

2395669

210151

18

С. Лем

0

7

1568013

343519

19

Н. Леонов

0

2

568854

279377

20

С. Логинов

14

13

1998543

159247

21

Е. Лукин

0

4

602216

125694

22

В. Черняк

0

2

920056

201636

23

А.П. Чехов

0

2

662801

343694

24

И. Хмелевская

0

4

1524905

203684

25

Л. и Е. Лукины

0

3

837198

122999

26

С. Лукьяненко

0

14

3682298

483503

27

Н. Маркина

0

1

266297

93647

28

М. Наумова

0

3

306514

337821

29

С. Павлов

0

2

751836

453448

30

Б. Райнов

0

4

1405994

420256

31

Н. Рерих

0

3

1011285

211047

32

Н. Романецкий

2

6

1305096

117147

33

А. Ромашов

0

1

88434

87744

34

В. Рыбаков

0

6

715406

121497

35

К. Серафимов

0

1

186424

75276

36

И. Сергиевская

0

1

109118

50786

37

С. Щеглов

10

2

253732

55188

38

А. Щеголев

0

2

848730

105577

39

В. Шинкарев

29

2

156667

80405

40

К. Ситников

0

7

419872

109116

41

С. Снегов

0

2

824423

408984

42

А. Степанов

0

5

1223980

93707

43

А. Столяров

11

1

350053

137135

44

Р. Светлов

0

2

454638

268472

45

А. Свиридов

63

3

660413

235439

46

Е. Тильман

0

2

705352

464685

47

Д. Трускиновская

0

8

2005238

118351

48

А. Тюрин

0

18

4109050

110237

49

В. Югов

0

5

829209

66657

50

А. Молчанов

0

1

398487

206541

51

Ф.М. Достоевский

1

3

613825

88582

52

Н.В. Гоголь

0

3

638339

215540

53

Д. Хармс

0

2

199449

114889

54

А. Житинский

0

2

2137325

543037

55

Е. Хаецкая

2

2

723167

204091

56

В. Хлумов

0

3

788562

183358

57

В. Кунин

0

3

1335918

296463

58

А. Мелихов

0

1

615548

458086

59

В. Набоков

0

5

1522633

342774

60

Ю. Никитин

0

2

1342176

702383

61

В. Сегаль

0

2

320218

75917

62

В. Ян

0

1

507502

600636

63

А. Толстой

0

1

129664

97842

64

И. Ефремов

0

1

536604

256521

65

Е. Федоров

0

1

1120665

221388

66

О. Гриневский

0

1

158762

96085

67

Н. Гумилев

0

1

70181

71042

68

Л.Н. Толстой

0

1

1225242

199903

69

В. Михайлов

0

1

254464

84135

70

Ю. Нестеренко

0

1

352988

71075

71

А.С. Пушкин

0

1

170380

57143

72

Л. Резник

0

1

115925

79628

73

М.Е. Салтыков-Щедрин

0

1

239289

101845

74

В. Шукшин

0

1

309524

66756

75

С. М. Соловьев

0

1

2345807

160002

76

А. Кац

0

1

841898

81830

77

Е. Козловский

1

1

849038

889560

78

С. Есенин

0

1

219208

44855

79

А. Стругацкий

0

1

151246

51930

80

А. и Б. Стругацкие

0

29

6571689

345582

81

Б. Стругацкий

0

1

298832

261206

Первый вывод из данных этой таблицы состоит в том, что количество правильных ответов (нулей в колонке c1) очень велико - 69. Истинный автор произведения оказывается на втором месте в списке претендентов всего в трех случаях (в колонке c1 стоит 1): Л. Кудрявцев, Ф.М. Достоевский и Е. Козловский. На третьем месте (c1 = 2) - в двух случаях: Н. Романецкий и Е. Хаецкая. На четвертом месте оказывается лишь один автор (c1 = 3) - С. Казменко. Для остальных 7 авторов ошибка очень велика (Ю. Латынина, А. Лазаревич, С. Логинов, С. Щеглов, В. Шинкарев, А. Столяров, А. Свиридов). Они не оказываются даже в десятке претендентов на их собственные произведения.

Мерой неточности оценки t(G(·)) может служить средний ранг, равный сумме чисел в колонке c1, деленной на общее число писателей 82. Здесь средний ранг равен

2.35 ? (3Ч1+2Ч2+1Ч3+2Ч10+1Ч11+1Ч14+1Ч29+1Ч46+1Ч63) / 82

Все эти числа приведены в таблице 3 в колонке t(G(·)). Если выбросить семерых плохо определяемых авторов, средний ранг окажется равным

0.13 ? 2/15 = (3Ч1+2Ч2+1Ч3) / 75.

Второй вывод из данных таблицы 2 состоит в том, что метод работает и на стихотворных произведениях (А.С. Пушкина, С. Есенина и Н. Гумилева). В-третьих, правильно определяются писатели, чьи произведения переводились с польского языка (С. Лем и И. Хмелевская). В-четвертых, среди плохо распознаваемых авторов нет общепризнанных классиков русской литературы.

Для сравнения, в следующей таблице приведены результаты аналогичного исследования с оценками t(F(x)), e(F(x)), e(G(x)) на тех же текстах.

Таблица 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) и определяются только матрицей вероятностей перехода.

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

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

Первая строка матрицы свидетельствует о следующем: со страницы 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.

Заключение

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

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

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

Список литературы

1. Андрухаев Х.М. Курс по Теории вероятности

2. Гмурман «Теория вероятности и математической статистике» 1999г.

3. Гнеденко «Курс теории вероятности», 1954г.

4. Гунир П.С. Овчинский Б.В. «Основы Теории Вероятности»

5. Емельянов «Задачник по теории вероятности»

6. Прохоров, Розанов. Справочная математическая библиотека «Теория вероятности» 1967г.

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

8. Http://www.erudition.ru

9. http://nplit.ru

Размещено на Allbest.ru


Подобные документы

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

    курсовая работа [126,8 K], добавлен 20.04.2011

  • Основные понятия теории марковских цепей. Теория о предельных вероятностях. Области применения цепей Маркова. Управляемые цепи Маркова. Выбор стратегии. Оптимальная стратегия является марковской - может зависеть еще и от момента времени принятия решения.

    реферат [75,6 K], добавлен 08.03.2004

  • Сущность вероятностной задачи-схемы независимых испытаний швейцарского профессора математики Я. Бернулли. Пример решения задачи по формуле Бернулли. Применение методов теории вероятностей в различных отраслях естествознания, техники и прикладных науках.

    презентация [301,3 K], добавлен 10.03.2011

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

    презентация [96,2 K], добавлен 11.12.2012

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

    курсовая работа [134,2 K], добавлен 31.05.2010

  • Правила применения уравнения Бернулли для определения возможности наступления события. Использование формул Муавра-Лапласа и Пуассона при неограниченном возрастании числа испытаний. Примеры решения задач с помощью теоремы Бернулли о частоте вероятности.

    курсовая работа [265,6 K], добавлен 21.01.2011

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

    курсовая работа [107,2 K], добавлен 06.11.2011

  • Распределение дискретной случайной величины по геометрическому закону распределения, проверка теоремы Бернулли на примере моделирования электрической схемы. Математическое моделирование в среде Turbo Pascal. Теоретический расчёт вероятности работы цепи.

    контрольная работа [109,2 K], добавлен 31.05.2010

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

    практическая работа [55,0 K], добавлен 23.08.2015

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

    презентация [422,7 K], добавлен 02.06.2013

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.