Введение
Цепь Маркова — последовательность случайных событийс конечным или счётным бесконечным числом исходов, характеризующаяся тем свойством,что при фиксированном настоящем будущее независимо от прошлого.
Цепи Маркова – одна из основныхи актуальных тем в нынешнее время в современной математике. Цепи Маркова являютсяобобщением схемы Бернулли, которая была написана в XVII, а Марковские цепи получили сравнительно недавно своепризнание. Очень много процессов в нынешнее время решаются с помощью схем Бернуллиили цепей Маркова. Вся поисковая система Интернета основана на этих процессах.
Эта была одна из основныхпричин выбора мною этой темы для выпускной квалификационной работы (ВКР). Мне былоочень интересно, по какому принципу происходит выборка по рассылке, или по поискув Интернете. Рассылка спам-ботов основана тоже на этих же процессах.
Цель моей работы – Ознакомитьсяи как можно подробнее рассмотреть заинтересовавший меня материал. Особенно интереснойдля меня была эта тема по той причине, что она не рассматривалась в курсе моегообучения в институте, а является частью пройденного материала по теории вероятности.
Свою работу «Приложение схемыБернулли. Обобщение. Цепи Маркова» я начинаю с введения понятий касающихся разделасхемы Бернулли. Из этого и состоят моя первая глава ВКР — Биография Якоба Бернуллии схема Бернулли. Я рассматриваю различные варианты схем Бернулли, как она по-разномуприменятся, различные формы записи, обобщения.
Во второй главе своей работыя уже по выше рассмотренным понятиям схем Бернулли ввожу понятие Цепь Маркова, котораябыла так названа в честь нашего соотечественника, великого математика, Андрея АндреевичаМаркова. Для лучшего понятия темы Цепи Маркова в этой главе я рассматриваю введениепонятия цепь Маркова с помощью примера.
Третья глава дает нам представлениео том, какой объем работы может выполнять человек, который владеет цепями Маркова.Подробно рассматриваю на примере по определению авторства текста. Я посчитал этотпример очень удачным применением Цепей Маркова.
Глава 1. СхемаБернулли
1.1 Историческийкурс. Биография Якоба Бернулли
Якоб Бернуллиродился 27 декабря 1654 г. По желанию отца готовился к званию протестантского священника.Окончил Базельский университет, где изучал философию, богословие и языки. Владелнемецким, французским, английским, итальянским, латинским и греческим языками. Испытываянепреодолимое влечение к математике, изучал ее тайком от отца. В 1671 г. получилстепень магистра философии. С большим успехом читал проповеди на немецком и французскомязыках. В то же время продолжал пополнять свои знания по математике без учителя,почти без учебников.
В октябре 1686г. оказывается вакантной должность профессора математики в Базельском университете.Успехи Якоба в математике хорошо известны, и Сенат университета единодушно выдвинулна вакантную должность Якоба Бернулли. Вступление в должность состоялось 15 февраля1687 г. Вряд ли присутствовавшие при этом скромном акте представляли, что они являютсясвидетелями начала беспримерного в истории математики события: отныне кафедру будутзанимать Бернулли на протяжении ста лет. Члены же этой семьи будут профессорамиродного университета в течение четверти тысячелетия, вплоть до второй половины XXв.
В том же годуЯкоб Бернулли прочитал в «Асtа Eruditirum» за 1684 г. «Новый метод» Лейбница и,обнаружив трудные места, письменно обратился к Лейбницу за разъяснением. Лейбниц,находившийся в длительной служебной поездке, получил письмо только через три года,когда надобность в консультации отпала: Якоб совместно Иоганном овладели дифференциальными интегральным исчислениями настолько, что вскоре смогли приступить систематическомуразвитию метода. Образовавшийся триумвират — Лейбниц, Якоб и Иоганн Бернулли — менеечем за двадцать лет чрезвычайно обогатил анализ бесконечно малых.
С 1677 г. Я. Бернуллистал вести записные книжки, куда вносил различного рода заметки научного содержания.Первые записи посвящены теологии, сделаны под влиянием распространенного в то времяв Базеле сборника спорных теологических вопросов.
Основное местов записных книжках занимает решение задач. Уже по ранним записям можно судить опроявленном Я. Бернулли интересе к прикладной математике. Математические заметкипоказывают, как постепенно Я. Бернулли овладевал методами Валлиса, Декарта, инфинитезимальнымиметодами, как развивал и совершенствовал их. Решенные им задачи служили отправнымипунктами для дальнейших более глубоких исследований.
В январе 1684г. Я. Бернулли провел в Базельском университете открытый диспут, на котором защищал100 тезисов, из них 34 логических, 18 диалектических и 48 смешанных. Некоторые тезисыкрайне любопытны. Вот примеры:
78. Иногда существуетнесколько кратчайших путей из точки в точку
83. Среди изопериметрическихфигур одна может быть в бесконечное число раз больше другой
85. Не в каждомтреугольнике сумма внутренних углов равна двум прямым
89. Квадратуракруга еще не найдена, но не потому, что между искривленным и прямолинейным нет никакойсвязи; в действительности кривую можно спрямить, а криволинейную фигуру квадрировать
В мае 1690 г.Я. Бернулли опубликовал в «Асtа Eruditirum» первую работу, связанную с исчислениембесконечно малых. В ней он дал решение поставленной Лейбницем в 1687 г. задачи опарацентрической изохроне. Необходимо было найти кривую, по которой материальнаяточка опускалась бы в равные промежутки времени на равные высоты. Я. Бернулли вывелдифференциальное уравнение кривой и проинтегрировал его. При этом он впервые употребилв печати термин «интеграл», указав, что из равенства двух выражений, связывающихдифференциалы, следует равенство интегралов.
В лекциях, читанныхЛопиталю, И. Бернулли ход решения излагает так. Пусть искомой кривой будет АDС.Материальная точка за время ∆t перемещается из точки D в точку d и из точкиС в точку с. По условию задачи проекции дуг Dd Сс на вертикаль одинаковы. Проведемчерез D и С касательные к кривой до пересечения с продолжением АF. Отрезки касательныхбудут DK и CL. Напишем тождество
Вв.Сс=Вв.Рс •Рс.Ссю
Дуги Dd и Сс малы,поэтому фигуры GDd и НСс можно считать треугольниками.
Из подобия треугольниковGDd и DEK, НСс и СFL получим
Вв.ВП=ВЛ.ВУбСс.Нс=СД.САю
С помощью этихпропорций найдем
Вв.Сс=ВП1Нс •ВК.ВЕ • СА.СДю
По условиям задачиdG/Нс=1, поэтому
Вв1Сс=ВК.ВЕ •СА.СДю
Проведем черезточку С прямую СМ, параллельную DК. Тогда
DК/DЕ=СМ/СF, Dd/Сс=СМ/СL.
Но отношение Dd/Ссравно отношению скоростей (интервал ∆t один и тот же), квадраты же скоростей,по найденному Галилеем закону, относятся как пройденные высоты; это дает
Dd2/Сс2=СМ2/СL2=DЕ/CF,СМ2/СL2 =DЕ/СF.
Последнее равенствоозначает, что если через две произвольные точки кривой провести касательные СL иDК и через точку С провести СМ параллельно DК, то должна выполняться указанная пропорция.Таким свойством обладает искомая кривая.
Задача оказаласьсведенной к классу обратных задач на касательные: найти кривую, касательные к которойудовлетворяют некоторому требованию. Подобную задачу впервые предложил Декарту Дебон,и Декарт с ней не справился. Разработанный Лейбницем метод позволяет решать и обратныезадачи на касательные.
Выберем началокоординат в точке А. Обозначим АЕ=х, ЕD=у. Тогда GD=dх, Gd=dу. Обозначим также СF=а,СL=b. Треугольники FСМ и СdD подобны, отсюда
Gd/Dd=FС/СМ.
Но Dd = √dx2+dy2,поэтому
dy/√ dx2+dy2=а/СМ, откуда
CM2=(a2dx2+a2dy2)/dy2.
Подставим найденноевыражение в пропорцию СL2/СM2=СF/СЕ и получим дифференциальноеуравнение
и2вн2.(ф2вч2+ф2вн2)=ф.нби2нвн2-ф3вн2=ф3вч2б(и2н-а3)ву2 = а3вч2б
√b2y-a3dy=√a3 dx.
В уравнении переменныеразделены, интегрирование его дает искомую кривую
2b2у— 2а3/3b2 √b2у — а3 == х√а3.
Парацентрическаяизохрона оказалась полукубической параболой. Вид кривой раньше Я. Бернулли определилиЛейбниц и Гюйгенс, но лишь Я. Бернулли дал решение средствами анализа бесконечномалых.
В приложении кдругой работе о рядах (1694 г.) Я. Бернулли сформулировал несколько тезисов.
1. Существуютспирали, которые совершают бесконечное число витков вокруг полюса, но имеют конечнуюдлину.
2. Существуюткривые, которые, подобно эллипсу, замкнуты и, подобно параболе, уходят в бесконечность,например ay2=х2(b+х).
3. Существуюткривые, состоящие из двух ветвей, например ау2=х(а2—х2),
4. Существуютнеограниченные поверхности с конечной площадью.
5. Существуютнеограниченные поверхности с бесконечной площадью, но такие, что соответствующиеим тела вращения обладают конечным объемом.
Я. Бернулли увлекалсятакже и изопериметрическими задачами. Древнейшая из них—задача легендарной основательницыКарфагена и его первой царицы Дидоны. Легенда такова. Дидона бежала от отца, тирскогоцаря, и достигла Африки, где купила у туземцев участок земли на берегу моря «небольше, чем можно окружить воловьей шкурой». Она разрезала шкуру на узкие полоскии связала из них длинную ленту. Спрашивается, какой формы должна быть фигура, оцепленнаялентой данной длины, чтобы площадь фигуры была наибольшей?
Ван-дер-Варденпишет, что Зенодор, живший вскоре после Архимеда, высказал 14 предложений относительноизопериметрических фигур. Он утверждал, что из всех фигур (кругов и многоугольников),имеющих одинаковый периметр, круг будет наибольшим, а также и то, что из всех пространственныхтел с одинаковой поверхностью наибольшим будет шар.
Решение задачисодержится в записных книжках Я. Бернулли и помещено в майском номере «Acta Eruditorum»за 1701 г. Я. Бернулли и здесь применил высказанный ранее принцип: поскольку площадьдолжна быть экстремальной, этим же свойством должна обладать и любая ее элементарнаячасть. Он получил дифференциальное уравнение третьего порядка и впоследствии проинтегрировалего.
К.А. Рыбниковпишет: «Таким образом, решение изопериметрической задачи означало очень важный,принципиально новый этап в истории вариационного исчисления; оно дало возможностьрешать более сложные вариационные задачи, им был сделан важный шаг на пути решениявариационных задач».
При изучении свойствсочетаний и фигурных чисел Я. Бернулли встретился с суммированием степеней натуральныхчисел Sm = å km
Эти вопросы интересовалиматематиков и ранее. Я. Бернулли составил таблицу фигурных чисел, указал их свойстваи на основании отмеченных свойств нашел формулы для сумм степеней натуральных чисел.Он привел формулы сумм от S(n) до S(n10):
S (n)= n2/2 +n/2
S (n2)= n3/3 + n2/2+ n/6
S (n3)= n4/4 + n3/2 + n2/4
S (n4)= n5/5 + n4/2 + n3/3 – n/30
S (n5)= n6/6 + n5/2 + 5n4/12 — n2/12
S (n6)= n7/7 + n6/2 + n5/2 — n3/6 + n/42
S (n7)= n8/8 + n7/2 + 7n6/12 — 7n4/24 + n2/12
S (n8)= n9/9 + n8/2 + 2n7/3 — 7n5/15 + 2n3/9– n/30
S (n9)= n10/10 + n9/2 + 3n8/4 — 7n6/10 + n4/2- n2/12
S (n10) = n11/11 + n10/2 + 5n9/9– n7 + n5 — n3/2 + 5n/66
Затем Я. Бернуллиуказал общую формулу
S(nc)= nc+1/c+1 + 1/2*nc + 1/2*( )Anc-1 + 1/4*( )Bnc-3+ 1/6*( )Cnc-5 +
+1/8*( )Dnc-7+ …
Здесь ( ), ( )… — числа сочетаний; показатели степени n убывают, последний член в правой частисодержит n или n2.
Числа A, B, C,D … — коэффициенты при n в выражениях S(n2), S(n4), S(n6),…
Именно: А=1/6,В=-1/30, С=1/42, D=-1/30,
Бернулли формулируетобщее правило для вычисления этих чисел: сумма коэффициентов в выражениях S(n),S(n2), S(n3), … равна единице. Например, 1/9+1/2+2/3-7/15+2/9+D=1.Отсюда D=-1/30.
Я. Бернулли подчеркиваетудобство таблицы фигурных чисел и заявляет, что с ее помощью в течение «половинычетверти часа» нашел сумму десятых степеней первой тысячи натуральных чисел. Онаоказалась равной
91 409 924 241424 243 424 241 924 242 500.
1.2 Схема Бернулли.Обобщение
Определение1. Схемой Бернулли называется последовательность независимыхв совокупности испытаний, в каждом из которых возможны лишь два исхода — «успех»и «неудача», при этом успех в одном испытании происходит с вероятностью/>а неудача — с вероятностью />.
Под независимостью в совокупности испытаний понимается независимостьв совокупности любых событий, относящихся к разным испытаниям. В испытаниях схемыБернулли, когда с одним испытанием можно связать только два взаимоисключающих события,независимость в совокупности испытаний означает, что при любом />независимы в совокупности события />успех в первомиспытании/>успех в />-миспытании/>. Эти события принадлежатодному и тому же пространству элементарных исходов, полученному декартовым произведениембесконечного числа двухэлементных множеств />:
/>
Здесь буквами «у»и «н» обозначены успешный и неудачный результаты испытаний соответственно.
Обозначим через/>число успехов,случившихся в />испытаниях схемыБернулли. Эта величина может принимать целые значения от нуля до />в зависимости от результата />испытаний.Например, если все />испытаний завершилисьнеудачей, то величина />равна нулю.
Теорема 1 (формулаБернулли). При любом/>имеет место равенство:
/>
Доказательство. Событие />означает, что в />испытанияхсхемы Бернулли произошло ровно />успехов. Рассмотримодин из благоприятствующих событию />элементарных исходов:
/>
когда первые />испытаний завершились успехом, остальные неудачей. Поскольку испытаниянезависимы, вероятность такого элементарного исхода равна />. Другие благоприятствующие событию />элементарные исходы отличаются лишь расположением />успехов на />местах. Есть ровно/>способов расположить/>успехов на />местах. Поэтому событие />состоитиз />элементарныхисходов, вероятность каждого из которых также равна />.
Определение2. Набор чисел />называетсябиномиальным распределением вероятностей./> 1.2.1Номер первого успешного испытания
Рассмотрим схемуБернулли с вероятностью успеха />в одном испытании.Введем величину />со значениями/>равнуюномеру первого успешного испытания.
Теорема 2. Вероятность того, что первый успех произойдетв испытании с номером />равна
/>.
Доказательство. Вероятность первым />испытаниям завершиться неудачей, а последнему — успехом, равна
/>
Определение3. Набор чисел />называется геометрическимраспределением вероятностей.
Геометрическоераспределение вероятностей обладает интересным свойством, которое можно назватьсвойством «нестарения».
Теорема 3. Пусть />для любого />. Тогда для любых неотрицательных целых />и />имеет место равенство:
/>
Если, например,считать величину />временем безотказнойработы (измеряемым целым числом часов) некоторого устройства, то данному равенствуможно придать следующее звучание: вероятность работающемуустройству проработать еще сколько-то часов не зависит от того момента, когда мыначали отсчет времени, или от того, сколько уже работает устройство. Общепринятоеназвание этого свойства — свойство отсутствия последействия.
Доказательство. По определению условной вероятности,
/> (1)
Последнее равенство следуетиз того, что событие />влечетсобытие />поэтомупересечение этих событий есть />. Найдемдля целого />вероятность/>:
/>
Можно получить />еще проще: событие />означает в точности, что в схеме Бернулли первые />испытаний завершились неудачами, т.е. его вероятность равна />. Возвращаясь к (1), получим
/>
Теорема 3 доказана.
1.2.2Независимые испытания с несколькими исходами
Рассмотрим схемунезависимых испытаний уже не с двумя, а с большим количеством возможных результатовв каждом испытании.
Пример 1. Игральная кость подбрасывается 15 раз.Найти вероятность того, что выпадет ровно десять троек и три единицы.
Здесь каждое испытаниеимеет три, а не два исхода: выпадение тройки, выпадение единицы, выпадение любойдругой грани. Поэтому воспользоваться формулой для числа успехов в схеме Бернуллине удаcтся.
Попробуем вывестиподходящую формулу. Пусть в одном испытании возможны />исходов:/>,и />-й исход в одномиспытании случается с вероятностью />, где />.
Обозначим через/>вероятность того, что в />независимых испытаниях первый исход случится />раз, второй исход — />раз, и т.д., наконец,/>-й исход — />раз.
Теорема 4 (Обобщеннаяформула Бернулли). Длялюбого />и любых неотрицательныхцелых чисел />суммакоторых равна />верна формула
/>
Доказательство. Рассмотрим один элементарный исход, благоприятствующийвыпадению />единиц, />двоек и т.д.:
/>
Это результат />экспериментов, когда все нужные исходы появились в некотором заранеезаданном порядке. Вероятность такого результата равна произведению вероятностей/>.Остальные благоприятные исходы отличаются лишь расположением чисел />на />местах. Число такихисходов равно числу способов расположить на />местах/>единиц, />двоек, и т.д. Это число равно
/>
Теперь мы можемвернуться к примеру 1 и выписать ответ: вероятность получить десять троек, три единицыи еще два других очка равна
/>
так как вероятности выпадениятройки и единицы равны по />, а вероятностьтретьего исхода (выпала любая другая грань) равна />/> 1.2.3Теорема Пуассона для схемы Бернулли
Предположим, намнужна вероятность получить не менее семи успехов в тысяче испытаний схемы Бернуллис вероятностью успеха />. Вероятностьэтого события равна любому из следующих выражений, вычислить которые довольно сложно:
/>
Сформулируем теоремуо приближенном вычислении вероятности иметь />успеховв большом числе испытаний Бернулли с маленькой вероятностью успеха />. Термин «большое число» должен означать />. Если при этом />остаетсянеизменной, то вероятность получить любое заданное число успехов уменьшается донуля. Необходимо чтобы вероятность успеха />уменьшалась одновременно с ростом числа испытаний. Но от испытанияк испытанию вероятность успеха меняться не может (см. определение схемы Бернулли).Поэтому нам придется рассмотреть так называемую «схему серий»: если испытаниеодно, то вероятность успеха в нем равна />если испытанийдва, то вероятность успеха в каждом равна />ит.д. Если испытаний />то в каждом из нихвероятность успеха равна />. Вероятность успехаменяется не внутри одной серии испытаний, а от серии к серии, когда меняется общеечисло испытаний. Обозначим через />число успеховв />-й серии испытаний.
Теорема 5 (теоремаПуассона). Пусть />и />так, что /> Тогдадля любого />вероятностьполучить />успехов в />испытаниях схемы Бернулли с вероятностью успеха />стремится к величине />
/>
Доказательство. Положим />. По условию />. Подставим />в формулу Бернулли:
/> (2)
В соотношении (2) мы воспользовалисьтем, что />и замечательным пределом />.Докажем последнее свойство:
/>
Определение4. Набор чисел />называетсяраспределением Пуассона с параметром />.
По теореме 17можно приближенно посчитать вероятность получить не менее семи успехов в тысячеиспытаний схемы Бернулли с вероятностью успеха />с вычисления которой мы начали. Поскольку />«велико», а />«мало», то, взяв />можно записать приближенное равенство
/>(3)
Осталось решить,а достаточно ли />велико, а />мало, чтобы заменить точную вероятность на ее приближенноезначение. Для этого нужно уметь оценивать разницу между этими вероятностями.
Следующую оченьполезную теорему мы, исключительно из экономии времени, доказывать не станем.
Теорема 6 (уточненнаятеорема Пуассона). Пусть/> — произвольное множествоцелых неотрицательных чисел, /> — число успеховв />испытаниях схемыБернулли с вероятностью успеха />/>. Cправедливо неравенство
/>
Таким образом,теорема 6 предоставляет нам возможность самим решать, достаточно ли />велико, а />мало, руководствуясьполученной величиной погрешности. Какова же погрешность в формуле (3)? Взяв />имеем
/>
Таким образом,можно утверждать, что искомая вероятность заключена в границах />.
Пример 2. В урне 20 белых и 10 черных шаров. Вынули4 шара, причем каждый вынутый шар возвращают в урну перед извлечением следующегои шары в урне перемешивают. Найти вероятность того, что из четырех вынутых шаровокажется 2 белых.
Решение. Событие А – достали белый шар. Тогдавероятности/>, />. По формуле Бернулли требуемая вероятность равна
/>.
Пример 3. Определить вероятность того, что в семье,имеющей 5 деталей, будет не больше трех девочек. Вероятности рождения мальчика идевочки предполагаются одинаковыми.
Решение. Вероятность рождения девочки />, тогда />.
Найдем вероятноститого, что в семье нет девочек, родилась одна, две или три девочки:
/>, />,
/>, />.
Следовательно,искомая вероятность
/>.
Пример 4. Среди деталей, обрабатываемых рабочим,бывает в среднем 4% нестандартных. Найти вероятность того, что среди взятых на испытание30 деталей две будут нестандартными.
Решение. Здесь опыт заключается в проверке каждойиз 30 деталей на качество. Событие А — «появление нестандартной детали», его вероятность/>, тогда />. Отсюда по формуле Бернулли находим/>.
Пример 5. При каждом отдельном выстреле из орудиявероятность поражения цели равна 0,9. Найти вероятность того, что из 20 выстреловчисло удачных будет не менее 16 и не более 19.
Решение. Вычисляем по формуле Бернулли:
/>
Пример 6. Независимые испытания продолжаются дотех пор, пока событие А не произойдет k раз. Найти вероятность того, что потребуетсяn испытаний (n .
Решение. Событие В – ровно n испытаний до k-гопоявления события А – есть произведение двух следующий событий:
D – в n-ом испытанииА произошло;
С – в первых (n–1)-омиспытаниях А появилось (к-1) раз.
Теорема умноженияи формула Бернулли дают требуемую вероятность:
/>
цепь марков бернулли информатика
Глава 2. ЦепиМаркова
2.1 БиографияМаркова
Марков АндрейАндреевич. 2 (14) июня 1856—20 июля 1922 — русский математик, специалист по теориичисел, теории вероятностей и математическому анализу.
С 1886 — адъюнкт, с 1890 —экстраординарный, а с 1896 — ординарный академик Императорской Санкт-ПетербургскойАкадемии Наук.
Андрей Марков родился в семьемелкого чиновника в Рязанской губернии. В 1878 окончил Петербургский университетсо степенью кандидата и в том же году получил золотую медаль за работу «Обинтегрировании дифференциальных уравнений при помощи непрерывных дробей». С1880 — приват-доцент, с 1886 — профессор, а с 1905 — заслуженный профессор Петербургскогоуниверситета.
Научные исследования Марковтесно примыкают по своей тематике к работам старших представителей Петербургскойматематической школы — П.Л. Чебышева, Е.И. Золотарева и А.Н. Коркина. Блестящихрезультатов в области теории чисел Марков достиг в магистерской диссертации «Обинарных квадратичных формах положительного определителя» (1880). Результаты,полученные им в этой работе, послужили основой дальнейших исследований в этой областив СССР и за рубежом. В 1905 вышел в отставку. В этом же году ему присвоено званиезаслуженного профессора Петербургского университета. Написал около 70 работ по теориичисел, теории приближения функций, теории дифференциальных уравнений, теории вероятностей,в т. ч. и 2 классических произведения — «Исчисление конечных разностей»и «Исчисление вероятностей». Труды Маркова по теории чисел касаются главнымобразом теории неопределенных квадратичных форм. Почти все они посвящены нахождениюэкстремальных квадратичных форм данного определителя.
Марков внес важный вклад всвоеобразную область геометрии чисел, которая в настоящее время интенсивно развивается.Обогатил важными открытиями и методами также теорию вероятностей: развил метод моментовП.Л. Чебышева настолько, что стало возможным доказательство центральной предельнойтеоремы, существенно расширил сферу применения закона больших чисел и центральнойпредельной теоремы, распространив их не только на независимые, но и на зависимыеопыты.
В цикле работ, опубликованныхв 1906-1912, заложил основы одной из общих схем естественных процессов, которыеможно изучать методами математического анализа. Впоследствии эта схема была названацепями Маркова и привела к развитию нового раздела теории вероятностей — теориислучайных процессов, которые играют важную роль в современной науке. В качествепримера случайных процессов можно назвать диффузию газов, химические реакции, лавинныепроцессы и т. д. Важное место в творчестве Маркова занимают вопросы математическойстатистики. Он вывел принцип, эквивалентный понятиям несмещенных и эффективных статистик,которые получили теперь широкое применение.
В математическом анализе Марковразвил теорию моментов и теорию приближения функций, а также аналитическую теориюнепрерывных дробей. Ученый широко использовал непрерывные дроби для приближенныхвычислений в теории конечных разностей, интерполировании и т. д. Актуальность всехэтих вопросов особенно возросла в связи с развитием вычислительной техники. Марковпользовался большим авторитетом среди студентов.
Он был материалистом и убежденныматеистом, бескомпромиссным борцом против религии. 12.02.1912 Марков подал в Синодпрошение об отлучении его от церкви. Марков протестовал против решения царскогоправительства, отказывавшегося утвердить избрание А.М. Горького почетным членомПетербургской Академии Наук. АН СССР учредила премию им. А.А. Маркова за лучшиеработы по математике. Именем Маркова назван кратер краевой зоны Луны.
Свой последний мемуар он представилАкадемии наук всего лишь за несколько месяцев до смерти. Тяжелый недуг свалил егов постель, и 20 июля 1922 г. он умер.2.2 ЦепиМаркова
Определение 5. Процесс, протекающий в физической системе,называется марковским, если в любой момент времени вероятность любого состояниясистемы в будущем зависит только от состояния системы в текущий момент и не зависитот того, каким образом система пришла в это состояние.
Определение 6. Цепью Маркова называется последовательностьиспытаний, в каждом из которых появляется только одно из k несовместных событийAi из полной группы. При этом условная вероятность pij(s)того, что в s –ом испытании наступит событие Aj при условии, что в (s– 1) – ом испытании наступило событие Ai, не зависит от результатов предшествующихиспытаний.
Независимые испытания являютсячастным случаем цепи Маркова. События называются состояниями системы, а испытания– изменениями состояний системы. По характеру изменений состояний цепи Маркова можноразделить на две группы.
Определение 7. Цепью Маркова с дискретным временем называетсяцепь, изменение состояний которой происходит в определенные фиксированные моментывремени. Цепью Маркова с непрерывным временем называется цепь, изменение состоянийкоторой возможно в любые случайные моменты времени.
Определение 8. Однородной называется цепь Маркова, еслиусловная вероятность pij перехода системы из состояния i в состояние j не зависитот номера испытания. Вероятность pij называется переходной вероятностью.
Допустим, число состоянийконечно и равно k. Тогда матрица, составленная из условных вероятностей переходабудет иметь вид:
/>
Эта матрица называется матрицейперехода системы. Т.к. в каждой строке содержаться вероятности событий, которыеобразуют полную группу, то, очевидно, что сумма элементов каждой строки матрицыравна единице. На основе матрицы перехода системы можно построить так называемыйграф состояний системы, его еще называют размеченный граф состояний. Это удобнодля наглядного представления цепи. Порядок построения граф рассмотрим на примере.
Пример 7. По заданной матрице перехода построитьграф состояний
/>
Т. к. матрица четвертого порядка,то, соответственно, система имеет 4 возможных состояния. S1 0,2 0,7 S2 0,4 S4 0,60,5 0,1 0,5 S3.
На графе не отмечаются вероятностиперехода системы из одного состояния в то же самое. При рассмотрении конкретныхсистем удобно сначала построить граф состояний, затем определить вероятность переходовсистемы из одного состояния в то же самое (исходя из требования равенства единицесуммы элементов строк матрицы), а потом составить матрицу переходов системы. ПустьPij(n) – вероятность того, что в результате n испытаний система перейдет из состоянияi в состояние j, r – некоторое промежуточное состояние между состояниями i и j.Вероятности перехода из одного состояния в другое pij(1) = pij. Тогда вероятностьPij(n) может быть найдена по формуле, называемой равенством Маркова:
/>
Здесь т – число шагов (испытаний),за которое система перешла из состояния i в состояние r. В принципе, равенство Марковаесть ни что иное как несколько видоизменная формула полной вероятности. Зная переходныевероятности (т.е. зная матрицу перехода Р1), можно найти вероятности перехода изсостояния в состояние за два шага Pij(2), т.е. матрицу Р2, зная ее – найти матрицуР3, и т.д. Непосредственное применений полученной выше формулы не очень удобно,поэтому, можно воспользоваться приемами матричного исчисления (ведь эта формулапо сути – не что иное как формула перемножения двух матриц). Тогда в общем видеможно записать:
/>
Вообще-то этот факт обычноформулируется в виде теоремы, однако, ее доказательство достаточно простое, поэтомуприводить его не буду.
Орграфы возникаютво многих жизненных ситуациях. Не пытаясь охватить большое число таких ситуаций,ограничимся рассмотрением одной из них.
Задача, которую мы рассмотрим, интересна самапо себе, а отчасти рассматриваем мы ее из-за того, что ее изложение не требует введениябольшого количества новых терминов.
Рассмотрим задачуоб осле, стоящем точно между двумя копнами: соломы ржи и соломы пшеницы (рис. 1).
Осел стоит междудвумя копнами: «Рожь» и «Пшеница» (рис. 1). Каждую минуту онлибо передвигается на десять метров в сторону первой копны (с вероятностью />), либо в сторону второй копны (с вероятностью />), либо остается там, где стоял (с вероятностью />); такое поведение называется одномерным случайным блужданием. Будем предполагать, что обе копны являются«поглощающими» в том смысле, что если осел подойдет к одной из копен,то он там и останется. Зная расстояние между двумя копнами и начальное положениеосла, можно поставить несколько вопросов, например: у какой копны он очутится сбольшей вероятностью и какое наиболее вероятное время ему понадобится, чтобы попастьтуда?
/>/>
Рис. 1
Чтобы исследоватьэту задачу подробнее, предположим, что расстояние между копнами равно пятидесятиметрам и что наш осел находится в двадцати метрах от копны «Пшеницы».Если места, где можно остановиться, обозначить через />( />— самикопны), то его начальное положение />можно задатьвектором />, />-я компонента которого равна вероятности того, что он первоначальнонаходится в />. Далее, по прошествииодной минуты вероятности его местоположения описываются вектором />,а через две минуты — вектором />. Ясно, что непосредственное вычислениевероятности его нахождения в заданном месте по прошествии />минут становится затруднительным. Оказалось, что удобнее всеговвести для этого матрицу перехода.
/>
/>
Рис. 2
Пусть />— вероятность того, что он переместится из />в />за одну минуту.Например, />и />. Эти вероятности />называются вероятностями перехода,а />-матрицу/>называютматрицей перехода (рис. 2). Заметим, что каждый элементматрицы />неотрицателен и чтосумма элементов любой из строк равна единице. Из всего этого следует, что />— начальный вектор-строка, определенный выше, местоположение ослапо прошествии одной минуты описывается вектором-строкой />, а после />минут — вектором/>. Другими словами,/>-я компонента вектора/>определяет вероятностьтого, что по истечении />минут осел оказалсяв />.
Можно обобщитьэти понятия. Назовем вектором вероятностей вектор-строку,все компоненты которого неотрицательны и дают в сумме единицу. Тогда матрица перехода определяется как квадратная матрица, в которойкаждая строка является вектором вероятностей. Теперь можно определить цепь Маркова(или просто цепь) как пару />, где />есть />-матрицаперехода, а />есть />-вектор-строка. Если каждый элемент />из />рассматривать каквероятность перехода из позиции />в позицию />, а />— как начальный векторвероятностей, то придем к классическому понятию дискретной стационарнойцепи Маркова. Позиция />обычно называетсясостоянием цепи. Опишем различные способы их классификации.
Нас будет интересоватьследующее: можно ли попасть из одного данного состояния в другое, и если да, тоза какое наименьшее время. Например, в задаче об осле из />в />можно попастьза три минуты и вообще нельзя попасть из />в />. Следовательно,в основном мы будем интересоваться не самими вероятностями />, а тем, положительны они или нет. Тогда появляется надежда,что все эти данные удастся представить в виде орграфа, вершины которого соответствуютсостояниям, а дуги указывают на то, можно ли перейти из одного состояния в другоеза одну минуту. Более точно, если каждое состояние />представлено соответствующей ему вершиной />, то, проводя из />в />для тех и только тех вершин, для которых />, мы и получим требуемый орграф. Кроме того, этот орграфможно определить при помощи его матрицы смежности, если заменить каждый ненулевойэлемент матрицы />на единицу. Мы будемназывать этот орграф ассоциированным орграфом данной цепи Маркова.Ассоциированный орграф одномерного случайного блуждания, связанного с задачей обосле, изображен на (рис. 3).
Другой пример:если цепь Маркова имеет матрицу перехода, приведенную на рис. 4, то ассоциированныйорграф этой цепи выглядит так, как показано на (рис. 5).
/>
/>
Рис. 3
/>
/>
Рис. 4
/>/>
Рис. 5
Теперь ясно, чтов цепи Маркова из состояния />в состояние />можно попасть в том и только в том случае, если в ассоциированноморграфе существует орцепь из />в />, и что наименьшее возможное время попадания равно длине кратчайшейиз таких орцепей. Цепь Маркова, в которой из любого состояния можно попасть в любоедругое, называется неприводимой. Ясно, что цепь Маркованеприводима тогда и только тогда, если ее ассоциированный орграф сильно связан.Заметим, что ни одна из описанных выше цепей не является неприводимой.
При дальнейшихисследованиях принято различать те состояния, в которые мы продолжаем возвращатьсянезависимо от продолжительности процесса, и те, в которые мы попадаем несколькораз и никогда не возвращаемся. Более точно это выглядит так: если начальное состояниеесть />и вероятностьвозвращения в />на некоторомболее позднем шаге равна единице, то />называется возвратным (или рекурсивным) состоянием. В противном случаесостояние />называется невозвратным. В задаче об осле, например, очевидно,что состояния />и />являются возвратными, тогда как все другие состояния — невозвратными.В более сложных примерах вычисление нужных вероятностей становится очень хитрымделом, и поэтому проще бывает классифицировать состояния, анализируя ассоциированныйорграф цепи. Нетрудно понять, что состояние />возвратно тогда и только тогда, если существование простойорцепи из />в />в ассоциированном орграфе влечет за собой существование простойорцепи из />в />. В орграфе, изображенном на (рис. 3), существует простаяорцепь из />в />, но нет ни одной орцепи из />в />. Следовательно,состояния />и, аналогично,/>невозвратны (/>возвратны). Состояние (такое, как />), из которого нельзя попасть ни в какое другое, называетсяпоглощающим состоянием.
Другой прием классификациисостояний опирается на понятие периодичности состояний. Состояние/>цепи Маркованазывается периодическим с периодом />/>, если в />можно вернуться только по истечении времени, кратного />. Если такого />не существует, тосостояние />называется непериодическим. Очевидно, что каждое состояние />, для которого />, непериодическое.Следовательно, каждое поглощающее состояние — непериодическое. В задаче об ослене только поглощающее состояние />, но ивсе остальные являются непериодическими. С другой стороны, во втором примере (рис.5) поглощающее состояние />— единственноенепериодическое состояние, поскольку />имеют периоддва, а />—период три. Используя терминологию орграфов, легко показать, что состояние />является периодическим с периодом />тогда и только тогда, если в ассоциированном орграфе длина каждойзамкнутой орцепи, проходящей через />, кратна />.
И, наконец, дляполноты изложения введем еще одно понятие: назовем состояниецепи Маркова эргодическим, если оно одновременно возвратнои непериодично. Если любое состояние цепи Маркова является эргодическим, то назовемее эргодической цепью.
Пример 8. Частица, находящаяся на прямой, движетсяпо этой прямой под влиянием случайных толчков, происходящих в моменты t1, t2, t3,… Частица может находиться в точках с целочисленными координатами1, 2, 3, 4, 5; в точках 1 и 5 находятся отражающие стенки. Каждый толчок перемещаетчастицу вправо с вероятностью и влево с вероятностью q, если частицы не находятся у стенки. Если же частица находитсяу стенки, то любой толчок переводит ее на единицу внутрь промежутка [1,5]. Найтиматрицу перехода P и ей соответствующий граф.
Решение. ПустьEi=(t) ,i = 1, 2, 3, 4, 5. Тогдаграф перехода выглядит следующим образом:
/>
Рис. 6
а матрица перехода–
/>
Пример 9. Вероятности перехода за один шаг в цепяхМаркова задаются матрицей:
/>
Требуется:
а) найти числосостояний;
б) установить,сколько среди них существенных и несущественных;
в) построить граф,соответствующий матрице P.
Решение.
а) 4 состояния.
б) состояния E1, E2 несущественны, поскольку остальные состояниядостижимы из них, но E1 недостижимо из E4, а E2 недостижимо из E3; состояния E3 и E4 являются существенными.
/>
Рис. 7. в)
Пример 10 (задача о скрещивании). В близко родственномскрещивании две особи, и среди их прямых потомков случайным образом выбираются двеособи разного пола. Они вновь скрещиваются, и процесс этот продолжается бесконечно.Каждый родительский ген может передаваться с вероятностью 1/2, и последовательныеиспытания независимые. Имея три генотипа AA, Aа, аа для каждого родителя, мы можемразличать шесть комбинаций родителей, которые пометим следующим образом:
У1=ФФ*ФФбУ2= ФФ*Фаб У3 = ФФ*ааб У4 = Фа*Фаб У5=Фа*ааб У6=
аа*ааю
Найдите граф иматрицу перехода.
Решение.
/>
Рассмотрим, какоепотомство и с какой вероятностью может быть у особей разного пола, если они выбираютсяиз E2.
Пусть Bi= {i-й потомок}, i= 1, 2и B1,B2 — разного пола, тогда варианты потомкови их вероятности можно найти по следующему графу:
/>
Рис. 8
Получаем, что
/> /> />
Аналогично, находими вероятности других переходов:
/>
Тогда искомый граф переходавыглядит следующим образом:
/>
Рис. 9
а матрица перехода–
/>
/>Пример 11. Матрица вероятностей перехода цепи Марковаимеет вид:
/>
Распределениепо состояниям в момент времени t= 0 определяетсявектором />. Найти распределения по состояниямв момент t= 2.
Решение. Построимграф, соответствующий вектору начальных вероятностей и матрице перехода:
/>
Рис. 10
По этому графунаходим распределение по состояниям в момент t= 2:
P(E1)= (0,6*(0,2)2+ 0,6*0,3*0,5+0,6*0,5*0,6)+(0,1*0,5*0,2+0,1*0,2*0,5
+0,1*0,3*0,6)+(0,3*0,6*0,2+(0,3)2*0,6)+(0,3*0,1*0,5)=0,437;
P(E2)= (0,1*(0,2)2+0,1*0,5*0,3+0,1*0,3*0,1)+0,6*0,3*0,2+0,6*0,2*0,3
+0,6*0,5*0,1)+(0,3*0,1*0,2+(0,3)2*0,1+0,3*0,6*0,3)=0,193;
P(E3)= 0,37.
Пример 12. Доказать, что P(n)= Pn для двух состояний цепи Маркова.
Решение. Пустьцепь Маркова с двумя состояниями E1 и E2 задана своей матрицей перехода P:
/>
Докажем утверждениеметодом математической индукции.
Пусть n= 2. Тогда
/>
Вероятности переходаза два шага удобно находить по графу перехода:
/>
Рис. 11
/>
Следовательно, P(2)= P2, и первый шаг метода математической индукции выполняется.Предположим далее, что при проверяемое утверждение истинно, т.е. P(k)= Pk, тогда матрица перехода за k+1 шаг P(k+1)= P(k)*P = Pk *P = P, что и требовалось доказать.
Глава 3. Применениецепей Маркова
3.1 Определениеавторства текста
В статье посредством формальногоанализа текста решается задача определения авторства текста. Новый метод основываетсяна формальной математической модели последовательности букв текста как реализациицепи А.А. Маркова. Оказывается, частоты употребления пар букв очень хорошо характеризуютавтора. Последнее утверждение проверено в объемном статистическом эксперименте напроизведениях 82 писателей.Введение опыта
В последние десятилетия наметиласьтенденция поиска и выявления характерных структур авторского языка путем примененияформально-количественных, статистических методов. Первые пробные шаги на этом путипредпринял еще в начале XIX века Н.А. Морозов. Интересно, что тогда же известныйматематик А.А. Марков выступил с критикой Н.А. Морозова. А.А. Марковкритиковал Н.А. Морозова за то, что он не произвел тщательной статистической проверкиутверждений относительно устойчивости некоторых элементов авторского стиля (например,частицы «не»). Примером правильного статистического подхода А.А. Марковсчитал свое исследование в статье, где он изучал распределениедоли гласных и согласных среди первых 20000 букв «Евгения Онегина». Отметим,что работа посвящена первому применению «испытаний, связанных в цепь»,получивших впоследствии название цепей А.А. Маркова. Работа удивительным образомпредоставляет историческую основу методу определения авторства, изложенному в настоящейстатье.
Истории вопросаопределения авторства текста посвящена первая глава книги. Несмотряна то, что среди перечисленных в присутствуют весьма изощренные методики определенияструктуры авторского стиля, все они страдают, на взгляд автора настоящей статьи,одним общим недостатком. Ни одна из этих методик не проходила проверку на большомчисле писателей. Дело в том, что многие из методик имеют трудно формализуемый этапсведения естественно-литературного произведения к предлагаемой математической модели.Например, для некоторых из них необходима классификация всех слов текста по грамматическимклассам, что требует участия человека. При таком подходе большой вычислительныйэксперимент с целью проверки методики на большом числе авторов практически неосуществим.Поэтому все такие методики пытались использовать на небольшом числе авторов.
Другого подхода придерживались авторы статьи. Они исследовали несколько простых параметровавторского стиля и на огромном числе произведений писателей XVIII-XX веков статистическидоказали, что доля всех служебных слов в длинном прозаическом произведении являетсят.н. авторским инвариантом.
В настоящей статьепредложен новый, независимый от, а также всех методик, перечисленных в, формальныйметод установления автора текста. Наша постановка задачи отличается от. Мы предполагаем,что в нашем распоряжении имеются достаточно длинные фрагменты прозаических произведенийряда авторов на русском языке. Про некоторый анонимный фрагмент текста известно,что он принадлежит одному из этих авторов, но какому — неизвестно. Требуется узнать- кому именно.
Новый метод основываетсяна формальной математической модели последовательности букв текста как реализациицепи А.А. Маркова. По тем произведениям автора, которые достоверно им созданы, вычисляетсяматрица переходных частот употреблений пар букв. Она служит оценкой матрицы вероятностейперехода из буквы в букву. Матрица переходных частот строится для каждого из авторов.Для каждого автора оценивается вероятность того, что именно он написал анонимныйфрагмент текста. Автором анонимного текста полагается тот, у которого вычисленнаяоценка вероятности больше.
Такой метод оказываетсяудивительно точным для естественно-языковых текстов. Мы обсуждаем здесь особенностиприменения метода и сравниваем его с методом определения автора на основе частотупотребления каждой из букв в отдельности. Проверка метода проводилась на произведениях82 писателей, среди которых есть русские писатели как XIX, так и XX века.Математические основанияМарковскаямодель
Обозначим через A некотороемножество букв. Через Ak обозначим множество слов длины k над алфавитомA. Пусть A* = k > 0Ak. Обозначим длинуслова f A* через f.
Задачу определенияавтора текста можно сформулировать следующим образом. Пусть заданы n классов Ci,где i = 0, ..., n1. В каждом классе Ci находятся последовательностиfi,j A*, где j = 1, ..., mi, т.е. Ci= { fi,j j = 1,,mi}. Наша задача состоитв том, чтобы отнести x A* к одному из классов Ci.
Предположим, чтопоследовательности букв fi,j являются реализациями цепи Маркова с переходнойматрицей i. Построим оценку Pi. Обозначим через hi,j,klчисло переходов букв k l в фрагменте fi,j, положим hi,kl= jhi,j,kl, а hi,k = lhi,kl.Положим Pikl = hi,kl/hi,k. Возможно,некоторые Pikl равны нулю. Обозначим через Zi множествотаких упорядоченных пар (k,l), что Pikl > 0.
Предположим, чтоx также является реализацией цепи Маркова с матрицей переходных вероятностей P, где неизвестный параметр, который принимает одно из значений 1, ...,n.
Обозначим черезk,l число переходов k l в x. Пусть также k= l k,l. Обозначим через
Li(x) = (k,l) k,l×ln(k,l /(Pikl×k)),
где сумма беретсяпо парам (k,l) Zi. Грубо говоря, Li(x) равно минуслогарифму вероятности x при условии, что x — реализация цепи Маркова с матрицейпереходных вероятностей Pi. Назовем t(x) оценкой максимального правдоподобиядля неизвестного параметра
t(x) = argmini= 0,...,n1 Li(x). (2.1)
Мы не будем обсуждатьи доказывать какие-либо математические свойства оценки (2.1), хотя это и представляетинтересную задачу математической статистики (более подробно см.). Зато мы покажемудивительную эффективность оценки (2.1) при установлении автора текста.Схемаэксперимента
Возьмем A = {маленькие буквыкириллицы}{символ пробела}. Предположим, что у нас имеются в распоряжениидостаточно длинные фрагменты произведений n авторов на русском языке. Обозначимj-тый фрагмент i-того автора через gi,j. Можно считать, что фрагментgi,j является последовательностью символов некоторого расширенного алфавитаB, который включает, например, знаки пунктуации, большие буквы, латинские буквыи т.д. (на персональном компьютере B обычно совпадает с расширенным множеством символовASCII).
Каждый фрагментgi,j B* можно отобразить в A* посредствомнекоторой функции F: B* A*. Пусть, например, F превращаетвсе заглавные буквы в маленькие, склеивает перенесенные слова, выбрасывает все знакипунктуации и излишние знаки пробела, оставляя их по одному между словами, а такжевставляет один пробел в начале и один пробел в конце фрагмента в случае отсутствиятаковых.
Кроме того, мыбудем рассматривать функцию G, которая устроена так же, как и функция F, с тем дополнением,что все слова, которые в фрагменте gi,j начинались с заглавной буквы,отбрасываются. Например, если
y = «Крометого, мыбудемрассматриватьфункциюG,»,то
F(y) = "крометогомыбудемрассматриватьфункцию",а
G(y) = "тогомыбудемрассматриватьфункцию".
Теперь предположим,что некий фрагмент текста y B* принадлежит одному из n авторов,и нам неизвестно, кому именно. Наша задача: определить автора фрагмента y. Мы можемнайти автора, применяя оценку (2.1) к последовательности x = F(y) или к x = G(y).Следовательно, мы получаем два способа определения автора:
1) истинный автор- t(F(y)),
2) истинный автор- t(G(y)).
Важно отметить,что оценки t(F(y)) и t(G(y)) вычисляются на основе информации о частотах употребленияпар букв. Поскольку между словами вставлены пробелы, оценки t(F(y)) и t(G(y)) никакне зависят от порядка самих слов. По-видимому, t(F(y)) и t(G(y)) характеризуют последовательностиморфем в словоформах русского языка, но, конечно, совсем не учитывают синтаксисическуюинформацию (на основе последней пытались устанавливать авторство в).
Обычно ни дляодного из естественно-языковых текстов гипотеза о том, что он является реализациейсоответствующей цепи А.А. Маркова, не выдерживает статистической проверки. Междутем, мы можем формально произвести все вычисления и найти оценку (2.1). Статистическийэксперимент показывает, что авторы определяются очень уверенно.Анализчастот употреблений букв (схема Бернулли)
Схемой Бернулли в теории вероятностейназывается последовательность независимых одинаково распределенных случайных величин.Формально мы можем предположить, что последовательности fi,j и x являютсяреализациями последовательности независимых одинаково распределенных случайных величин,принимающих значения в A, а x распределен как величины класса , где - неизвестный параметр. Тогда оценка (2.1) принимает вид
e(x) = argminiGi(x), (2.2)
где
Gi(x) = k kln((k×hi)/(hi,k×)),
где сумма вычисляется по такимk, что k > 0, а = kk,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.Результаты вычислений представляются следующей таблицей.
Таблица 1N Автор
c1
c2
c3
c4 К. Булычев 15 2345689 75161 1 А. Волков 8 1733165 233418 2 Н.В. Гоголь 3 723812 243767 3 В. Набоков 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 К. Булычев 15 2007724 64741 1 О. Авраменко 6 1733113 223718 2 А. Больных 6 1294721 373611 3 А. Волков 8 1478932 202495 4 Г. Глазов 5 1398323 184593 5 М. и С. Дяченко 5 1754213 197039 6 А. Етоев 5 267096 80358 7 А. Кабаков 4 905502 222278 8 В. Каплан 6 515029 129608 9 С. Казменко 3 4 1846161 156768 10 В. Климов 3 250231 179903 11 И. Крашевский 2 1183722 481795 12 И. Кублицкая 1 282377 170469 13 Л. Кудрявцев 1 3 583239 179093 14 А. Курков 6 628041 218726 15 Ю. Латынина 10 2 2628781 283565 16 А. Лазаревич 46 3 310553 94629 17 А. Лазарчук 5 2395669 210151 18 С. Лем 7 1568013 343519 19 Н. Леонов 2 568854 279377 20 С. Логинов 14 13 1998543 159247 21 Е. Лукин 4 602216 125694 22 В. Черняк 2 920056 201636 23 А.П. Чехов 2 662801 343694 24 И. Хмелевская 4 1524905 203684 25 Л. и Е. Лукины 3 837198 122999 26 С. Лукьяненко 14 3682298 483503 27 Н. Маркина 1 266297 93647 28 М. Наумова 3 306514 337821 29 С. Павлов 2 751836 453448 30 Б. Райнов 4 1405994 420256 31 Н. Рерих 3 1011285 211047 32 Н. Романецкий 2 6 1305096 117147 33 А. Ромашов 1 88434 87744 34 В. Рыбаков 6 715406 121497 35 К. Серафимов 1 186424 75276 36 И. Сергиевская 1 109118 50786 37 С. Щеглов 10 2 253732 55188 38 А. Щеголев 2 848730 105577 39 В. Шинкарев 29 2 156667 80405 40 К. Ситников 7 419872 109116 41 С. Снегов 2 824423 408984 42 А. Степанов 5 1223980 93707 43 А. Столяров 11 1 350053 137135 44 Р. Светлов 2 454638 268472 45 А. Свиридов 63 3 660413 235439 46 Е. Тильман 2 705352 464685 47 Д. Трускиновская 8 2005238 118351 48 А. Тюрин 18 4109050 110237 49 В. Югов 5 829209 66657 50 А. Молчанов 1 398487 206541 51 Ф.М. Достоевский 1 3 613825 88582 52 Н.В. Гоголь 3 638339 215540 53 Д. Хармс 2 199449 114889 54 А. Житинский 2 2137325 543037 55 Е. Хаецкая 2 2 723167 204091 56 В. Хлумов 3 788562 183358 57 В. Кунин 3 1335918 296463 58 А. Мелихов 1 615548 458086 59 В. Набоков 5 1522633 342774 60 Ю. Никитин 2 1342176 702383 61 В. Сегаль 2 320218 75917 62 В. Ян 1 507502 600636 63 А. Толстой 1 129664 97842 64 И. Ефремов 1 536604 256521 65 Е. Федоров 1 1120665 221388 66 О. Гриневский 1 158762 96085 67 Н. Гумилев 1 70181 71042 68 Л.Н. Толстой 1 1225242 199903 69 В. Михайлов 1 254464 84135 70 Ю. Нестеренко 1 352988 71075 71 А.С. Пушкин 1 170380 57143 72 Л. Резник 1 115925 79628 73 М.Е. Салтыков-Щедрин 1 239289 101845 74 В. Шукшин 1 309524 66756 75 С. М. Соловьев 1 2345807 160002 76 А. Кац 1 841898 81830 77 Е. Козловский 1 1 849038 889560 78 С. Есенин 1 219208 44855 79 А. Стругацкий 1 151246 51930 80 А. и Б. Стругацкие 29 6571689 345582 81 Б. Стругацкий 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(·)) 57 69 1 2 1 4 3 8 8 2 4 2 7 13 3 4 1 2 2 4 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) = (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) = .
Для расчета вектораP(1) применим формулу (5), т.е. P(0) умножим на матрицу вероятностей перехода. ПолучимP(1) = .
Для вектора P(2)формула (5) имеет следующий вид: P(2) = P(1) ∙P. После расчета получаем значенияP(2) = .
Рассчитывая значенияP(t) по формуле (5) мы найдем t, для которого выполняется равенство (7). Т.е. мырассчитаем значение предельного вектора вероятностей P(*), который не зависит отвектора начальных вероятностей P(0) и определяется только матрицей вероятностейперехода.
В нашем случаеP(*) = .
Таким образом,после достаточно большого количества переходов со страницы на страницу уже не имеетзначения с какой страницы пользователь начал просмотр, поскольку в результате онокажется на странице 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. nplit.ru