Цепь Маркова – это просто: подробно разбираем принцип. Расширяем словарную базу

Просматривал форумы в поисках вопросов, которые задают python-программистам на собеседованиях и наткнулся на один очень замечательный. Вольно его процитирую: ”Попросили написать генератор бреда на основе марковской цепи n-го порядка”. “А ведь у меня ещё нет такого генератора!” - прокричал мой внутренний голос - “Скорей открывай sublime и пиши!” - продолжал он настойчиво. Что же, пришлось подчиниться.

А здесь я расскажу, как я его сделал.

Сразу было решено, что генератор будет все свои мысли излагать в Твиттер и свой сайт. В качестве основных технологий я выбрал Flask и PostgreSQL. Связываться друг с другом они будут через SQLAlchemy.

Структура.

И так. Следующим образом выглядят модели:
class Srt(db.Model): id = db.Column(db.Integer, primary_key = True) set_of_words = db.Column(db.Text()) list_of_words = db.Column(db.Text()) class UpperWords(db.Model): word = db.Column(db.String(40), index = True, primary_key = True, unique = True) def __repr__(self): return self.word class Phrases(db.Model): id = db.Column(db.Integer, primary_key = True) created = db.Column(db.DateTime, default=datetime.datetime.now) phrase = db.Column(db.String(140), index = True) def __repr__(self): return str(self.phrase)
В качестве исходных текстов решено было взять субтитры из популярных сериалов. Класс Srt хранит упорядоченный набор всех слов из переработанных субтитров к одному эпизоду и уникальный набор этих же самых слов(без повторений). Так боту проще будет искать фразу в конкретных субтитрах. Сначала он проверит, содержится ли множество слов в множестве слов субтитров, а затем посмотрит, лежат ли они там в нужном порядке.

Первым словом фразы из текста выбирается случайное слово, начинающееся с большой буквы. Для хранения таких слов и служит UpperWords. Слова туда записываются так же без повторений.

Ну и класс Phrases нужен для хранения уже сгенерированных твитов.
Структура отчаянно простая.

Парсер субтитров формата.srt выведен в отдельный модуль add_srt.py. Там нет ничего экстраординарного, но если кому интересно, все исходники есть на GitHub .

Генератор.

Для начала нужно выбрать первое слово для твита. Как говорилось раньше, это будет любое слово из модели UpperWords. Его выбор реализован в функции:
def add_word(word_list, n): if not word_list: word = db.session.query(models.UpperWords).order_by(func.random()).first().word #postgre elif len(word_list) <= n: word = get_word(word_list, len(word_list)) else: word = get_word(word_list, n) if word: word_list.append(word) return True else: return False
Выбор этого слова реализуется непосредственно строкой:

Word = db.session.query(models.UpperWords).order_by(func.random()).first().word

Если Вы используете MySQL, то нужно использовать func.rand() вместо func.random(). Это единственное отличие в данной реализации, всё остальное будет работать полностью идентично.

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

А следующее слово мы получаем в функции get_word:
def get_word(word_list, n): queries = models.Srt.query.all() query_list = list() for query in queries: if set(word_list) <= set(query.set_of_words.split()): query_list.append(query.list_of_words.split()) if query_list: text = list() for lst in query_list: text.extend(lst) indexies = ) if text == word_list] word = text return word else: return False
Первым делом скрипт пробегает по всем загруженным субтитрам и проверяет, входит ли наше множество слов в множество слов конкретных субтитров. Затем тексты отсеянных субтитров складываются в один список и в нём ищутся совпадения фраз целиком и возвращаются позиции слов, следующими за этими фразами. Всё заканчивается слепым выбором(random) слова. Всё как в жизни.
Так добавляются слова в список. Сам же твит собирается в функции:
def get_twit(): word_list = list() n = N while len(" ".join(word_list))<140: if not add_word(word_list, n): break if len(" ".join(word_list))>140: word_list.pop() break while word_list[-1][-1] not in ".?!": word_list.pop() return " ".join(word_list)
Всё очень просто – необходимо, чтобы твит не превышал 140 символов и заканчивался завершающим предложение знаком препинания. Всё. Генератор выполнил свою работу.

Отображение на сайте.

Отображением на сайте занимается модуль views.py.
@app.route("/") def index(): return render_template("main/index.html")
Просто отображает шаблон. Все твиты будут подтягиваться из него при помощи js.
@app.route("/page") def page(): page = int(request.args.get("page")) diff = int(request.args.get("difference")) limit = 20 phrases = models.Phrases.query.order_by(-models.Phrases.id).all() pages = math.ceil(len(phrases)/float(limit)) count = len(phrases) phrases = phrases return json.dumps({"phrases":phrases, "pages":pages, "count":count}, cls=controllers.AlchemyEncoder)
Возвращает твиты определённой страницы. Это нужно для бесконечного скрола. Всё довольно обыденно. diff – количество твитов, добавленных после загрузки сайта при апдейте. На это количество нужно смещать выборку твитов для страницы.

И непосредственно сам апдейт:
@app.route("/update") def update(): last_count = int(request.args.get("count")) phrases = models.Phrases.query.order_by(-models.Phrases.id).all() count = len(phrases) if count > last_count: phrases = phrases[:count-last_count] return json.dumps({"phrases":phrases, "count":count}, cls=controllers.AlchemyEncoder) else: return json.dumps({"count":count})
На клиентской стороне он вызывается каждые n секунд и догружает в реальном времени вновь добавленные твиты. Так работает отображение нашего твита. (Если кому-то интересно, то можно посмотреть класс AlchemyEncoder в controllers.py, с его помощью производится сериализация твитов, полученных от SQLAlchemy)

Добавление твитов в базу и постинг в Твиттер.

Для постинга в Твиттер я использовал tweepy. Очень удобная батарейка, заводится сразу.

Как это выглядит:
def twit(): phrase = get_twit() twited = models.Phrases(phrase=phrase) db.session.add(twited) db.session.commit() auth = tweepy.OAuthHandler(CONSUMER_KEY, CONSUMER_SECRET) auth.set_access_token(ACCESS_TOKEN, ACCESS_TOKEN_SECRET) api = tweepy.API(auth) api.update_status(status=phrase)
Вызов этой функции я вынес в cron.py в корне проекта, и, как можно догадаться, оно запускается по крону. Каждые полчаса добавляется новый твит в базу и Твиттер.

Всё заработало!

В заключение.

В данный момент я подгрузил все субтитры для сериала “Друзья” и “Теория большого взрыва”. Степень марковской цепи пока что выбрал равной двум(при увеличении базы субтитров степень будет увеличиваться). Как это работает можно посмотреть в

Было описано как обучить нейтронную сеть так, чтобы она играла в Марио или управляла роботом. Но может ли нейронная сеть генерировать текст? В этом вполне могут помочь цепи Маркова.

Вот за что я "люблю" русскоязычную википедию, так это за то, что любое простое явление/уравнение/правило, особенно из математики описывается сходу настолько обобщенно, настолько зубодробительными формулами, что без пол литра не разберешься. Притом составители статей не утруждают себя дать описание (хотя-бы на пару предложений) простым человеческим языком, а сразу переходят к формулам.

Если кто-то захочет узнать что такое цепи Маркова, то в первом переложении он узнает, что:
"Це́пь Ма́ркова — последовательность случайных событий с конечным или счётным числом исходов, характеризующаяся тем свойством, что, говоря нестрого, при фиксированном настоящем будущее независимо от прошлого. Названа в честь А. А. Маркова (старшего)."

И это при всем при том, что основная идея цепей Маркова очень проста, но понять это из википедии просто невозможно без математического образования.

Цепи маркова - это всего-лишь описание вероятностей перехода системы из одного состояния в другое. Все состояния можно описать вершинами графа. Например, такими вершинами могут быть положения человека: [лежит], [сидит], [стоит], [идет]

Здесь видно, что граф ориентированный, это значит, что не из всякого состояния можно попасть в другое. Например, если вы лежите, то невозможно сразу пойти. Нудно сначала сесть, потом встать, а только потом пойти. Но упасть и оказаться лежачим можно из любого положения))
Каждая связь имеет некую вероятность. Так, например, вероятность упасть из стоячего положения очень маленькая, гораздо вероятнее стоять дальше, пойти или сесть. Сумма всех вероятностей равна 1.

Кроме всего прочего цепи Маркова позволяют генерировать события. Так или иначе на цепях Маркова построены все большинство генераторов текстов.

Попробуем написать генератор пирожков.

Пирожки

Пирожки - четверостишия без рифмы, знаков препинания, цифр, без прописных букв. Количество слогов должно быть 9-8-9-8.

Большинство генераторов текстов используют морфологические анализаторы. Но мы сделаем проще. Просто разобьем слова на слоги и посчитаем вероятность того, что один слог находится после другого слога. То есть узлами графа у нас будут слоги, ребрами, и их весами - частота того, что второй слог идет за первым.
Дальше скормим программе полсотни пирожков .

Например, после слога "при", могут идти такие слоги (ребра и их веса):
"чем"(1) "хо"(4) "ме"(1) "ду"(2) "чи"(4) "ятель"(4) "шёл"(5) "ку"(1) " "(9) "су"(1) "выч"(3) "ми"(1) "кос"(1) "об"(1) "дёт"(2) "ехал"(1) "учи"(1) "му"(1) "би"(1) "це"(1) "цел"(2) "том"(1) "ко"(1) "вал"(1) "нес"(1) "дет"(1) "но"(1) "вез"(1) "мет"(1) "вет"(1) "дя"(1) "вы"(1)

Теперь все что нужно - это взять случайный слог (например, "при"). Сумма всех слогов, которые идут после него равна 58. Теперь нужно взять следующий слог с учетом частоты (количества) этих слогов:

size_t nth = rand() % count;

size_t all = 0 ;

for (const auto &n: next) {

All += n.count;

if (all >= nth)

return n.word;

Таким образом генерируем строки так, чтобы в первой строке было 9 слогов, во второй - 8, далее 9 и 8, получаем:

Жил шутить будильник до что ком
похищен он поку это
тебе афаначальник здесь да
онегин эффекты диван

Пока на особо связный текст не похоже. Часто встречаются несуществующие слова ("поку"). В качестве ключа сейчас только один слог. Но на основании одного слога сложно строить предложение. Увеличим количество слогов, на основании которых будем генерировать следующий слог хотя-бы до 3:

Асфальта для ума довольно
на часах семь разделить на
стол выносят чёрный ящик а
он вырос отомстил нашёл
Вот и первый пирожек, который более-менее можно принять за написаный человеком.
Чтобы текст вышел более осмысленным, то нужно использовать морфологические анализаторы , и тогда в качестве узлов будут не слоги, а метаописания слов (например "глагол, множественного числа, прошедшего времени").

Такие программы уже позволяют писать более "осмысленный" текст. Например корчеватель - статья, написаная генератором наукообразного текста, которая прошла рецензию и даже была опубликована в научном журнале.

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

Для начала выпишем нужные, но пока не очень понятные нам определения со страницы в Википедии , чтобы хотя бы примерно представлять, с чем мы имеем дело:

Марковский процесс t t

Марковская цепь

Что все это значит? Давайте разбираться.

Основы

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

Это предложение и есть корпус , то есть база, на основе которой в дальнейшем будет генерироваться текст. Оно состоит из восьми слов, но при этом уникальных слов только пять - это звенья (мы ведь говорим о марковской цепи ). Для наглядности окрасим каждое звено в свой цвет:

И выпишем количество появлений каждого из звеньев в тексте:

На картинке выше видно, что слово «fish» появляется в тексте в 4 раза чаще, чем каждое из других слов («One», «two», «red», «blue» ). То есть вероятность встретить в нашем корпусе слово «fish» в 4 раза выше, чем вероятность встретить каждое другое слово из приведенных на рисунке. Говоря на языке математики, мы можем определить закон распределения случайной величины и вычислить, с какой вероятностью одно из слов появится в тексте после текущего. Вероятность считается так: нужно разделить число появлений нужного нам слова в корпусе на общее число всех слов в нем. Для слова «fish» эта вероятность - 50%, так как оно появляется 4 раза в предложении из 8 слов. Для каждого из остальных звеньев эта вероятность равна 12,5% (1/8).

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

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

Суть определения

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

Любое предложение содержит эти невидимые «начало» и «конец», добавим их в качестве звеньев к нашему распределению:

Вернемся к определению, данному в начале статьи:

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

Марковская цепь - частный случай марковского процесса, когда пространство его состояний дискретно (т.е. не более чем счетно).

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

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

Таким образом, формируются пары слов (даже у конца предложения есть своя пара - пустое значение):

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

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

Разберем подробнее. Мы видим, что у каждого звена есть слова, которые могут стоять после него в предложении. Если бы мы показали схему выше кому-то еще, этот человек с некоторой вероятностью мог бы реконструировать наше начальное предложение, то есть корпус.

Пример. Начнем со слова «Start» . Далее выбираем слово «One» , так как по нашей схеме это единственное слово, которое может следовать за началом предложения. За словом «One» тоже может следовать только одно слово - «fish» . Теперь новое предложение в промежуточном варианте выглядит как «One fish» . Дальше ситуация усложняется - за «fish» могут с равной вероятностью в 25% идти слова «two», «red», «blue» и конец предложения «End» . Если мы предположим, что следующее слово - «two» , реконструкция продолжится. Но мы можем выбрать и звено «End» . В таком случае на основе нашей схемы будет случайно сгенерировано предложение, сильно отличающееся от корпуса - «One fish» .

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

Отлично! Мы усвоили необходимую информацию, чтобы двигаться дальше и разбирать более сложные модели.

Расширяем словарную базу

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

Возьмем еще четыре цитаты того же автора (также на английском, нам это не помешает):

«Today you are you. That is truer than true. There is no one alive who is you-er than you.»

«You have brains in your head. You have feet in your shoes. You can steer yourself any direction you choose. You’re on your own.»

«The more that you read, the more things you will know. The more that you learn, the more places you’ll go.»

«Think left and think right and think low and think high. Oh, the thinks you can think up if only you try.»

Сложность корпуса увеличилась, но в нашем случае это только плюс - теперь генератор текста сможет выдавать более осмысленные предложения. Дело в том, что в любом языке есть слова, которые встречаются в речи чаще, чем другие (например, предлог «в» мы используем гораздо чаще, чем слово «криогенный»). Чем больше слов в нашем корпусе (а значит, и зависимостей между ними), тем больше у генератора информации о том, какое слово вероятнее всего должно появиться в тексте после текущего.

Проще всего это объясняется с точки зрения программы. Мы знаем, что для каждого звена существует набор слов, которые могут за ним следовать. А также, каждое слово характеризуется числом его появлений в тексте. Нам нужно каким-то образом зафиксировать всю эту информацию в одном месте; для этой цели лучше всего подойдет словарь, хранящий пары «(ключ, значение)». В ключе словаря будет записано текущее состояние системы, то есть одно из звеньев корпуса (например, «the» на картинке ниже); а в значении словаря будет храниться еще один словарь. Во вложенном словаре ключами будут слова, которые могут идти в тексте после текущего звена корпуса («thinks» и «more» могут идти в тексте после «the» ), а значениями - число появлений этих слов в тексте после нашего звена (слово «thinks» появляется в тексте после слова «the» 1 раз, слово «more» после слова «the» - 4 раза):

Перечитайте абзац выше несколько раз, чтобы точно разобраться. Обратите внимание, что вложенный словарь в данном случае - это та же гистограмма, он помогает нам отслеживать звенья и частоту их появления в тексте относительно других слов. Надо заметить, что даже такая словарная база очень мала для надлежащей генерации текстов на естественном языке - она должна содержать более 20 000 слов, а лучше более 100 000. А еще лучше - более 500 000. Но давайте рассмотрим ту словарную базу, которая получилась у нас.

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

То есть если текущим словом является слово «more» , после него могут с равной вероятностью в 25% идти слова «things» и «places» , и с вероятностью 50% - слово «that» . Но вероятности могут быть и все равны между собой:

Think:

Работа с окнами

До настоящего момента мы с вами рассматривали только окна размером в одно слово. Можно увеличить размер окна, чтобы генератор текста выдавал более «выверенные» предложения. Это значит, что чем больше окно, тем меньше будет отклонений от корпуса при генерации. Увеличение размера окна соответствует переходу цепи Маркова к более высокому порядку. Ранее мы строили цепь первого порядка, для окна из двух слов получится цепь второго порядка, из трех - третьего, и так далее.

Окно - это те данные в текущем состоянии системы, которые используются для принятия решений. Если мы совместим большое окно и маленький набор данных, то, скорее всего, каждый раз будем получать одно и то же предложение. Давайте возьмем словарную базу из нашего первого примера и расширим окно до размера 2:

Расширение привело к тому, что у каждого окна теперь только один вариант следующего состояния системы - что бы мы ни делали, мы всегда будем получать одно и то же предложение, идентичное нашему корпусу. Поэтому, чтобы экспериментировать с окнами, и чтобы генератор текста возвращал уникальный контент, запаситесь словарной базой от 500 000 слов.

Реализация на Python

Структура данных Dictogram

Dictogram (dict - встроенный тип данных словарь в Python) будет отображать зависимость между звеньями и их частотой появления в тексте, то есть их распределение. Но при этом она будет обладать нужным нам свойством словаря - время выполнения программы не будет зависеть от объема входных данных, а это значит, мы создаем эффективный алгоритм.

Import random class Dictogram(dict): def __init__(self, iterable=None): # Инициализируем наше распределение как новый объект класса, # добавляем имеющиеся элементы super(Dictogram, self).__init__() self.types = 0 # число уникальных ключей в распределении self.tokens = 0 # общее количество всех слов в распределении if iterable: self.update(iterable) def update(self, iterable): # Обновляем распределение элементами из имеющегося # итерируемого набора данных for item in iterable: if item in self: self += 1 self.tokens += 1 else: self = 1 self.types += 1 self.tokens += 1 def count(self, item): # Возвращаем значение счетчика элемента, или 0 if item in self: return self return 0 def return_random_word(self): random_key = random.sample(self, 1) # Другой способ: # random.choice(histogram.keys()) return random_key def return_weighted_random_word(self): # Сгенерировать псевдослучайное число между 0 и (n-1), # где n - общее число слов random_int = random.randint(0, self.tokens-1) index = 0 list_of_keys = self.keys() # вывести "случайный индекс:", random_int for i in range(0, self.types): index += self] # вывести индекс if(index > random_int): # вывести list_of_keys[i] return list_of_keys[i]

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

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

Структура цепи Маркова

from histograms import Dictogram def make_markov_model(data): markov_model = dict() for i in range(0, len(data)-1): if data[i] in markov_model: # Просто присоединяем к уже существующему распределению markov_model].update(]) else: markov_model] = Dictogram(]) return markov_model

В реализации выше у нас есть словарь, который хранит окна в качестве ключа в паре «(ключ, значение)» и распределения в качестве значений в этой паре.

Структура цепи Маркова N-го порядка

from histograms import Dictogram def make_higher_order_markov_model(order, data): markov_model = dict() for i in range(0, len(data)-order): # Создаем окно window = tuple(data) # Добавляем в словарь if window in markov_model: # Присоединяем к уже существующему распределению markov_model.update(]) else: markov_model = Dictogram(]) return markov_model

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

Парсинг модели

Отлично, мы реализовали словарь. Но как теперь совершить генерацию контента, основываясь на текущем состоянии и шаге к следующему состоянию? Пройдемся по нашей модели:

From histograms import Dictogram import random from collections import deque import re def generate_random_start(model): # Чтобы сгенерировать любое начальное слово, раскомментируйте строку: # return random.choice(model.keys()) # Чтобы сгенерировать "правильное" начальное слово, используйте код ниже: # Правильные начальные слова - это те, что являлись началом предложений в корпусе if "END" in model: seed_word = "END" while seed_word == "END": seed_word = model["END"].return_weighted_random_word() return seed_word return random.choice(model.keys()) def generate_random_sentence(length, markov_model): current_word = generate_random_start(markov_model) sentence = for i in range(0, length): current_dictogram = markov_model random_weighted_word = current_dictogram.return_weighted_random_word() current_word = random_weighted_word sentence.append(current_word) sentence = sentence.capitalize() return " ".join(sentence) + "." return sentence

Что дальше?

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

В web-строительстве и SEO цепи Маркова используются для генерации псевдоосмысленных текстов на основании исходных текстов. Это используется для штамповки дорвеев с заданными ключевыми словами, для набора контентной текстовой массы и тому подобным "черным" трюкам. К счастью, поисковые системы научились эффективно определять контент, созданный на основе цепей Маркова и отправляет таких умников в бан. Учить вас подобным технологиям я не собираюсь, для этого есть специальные говносайты, меня интересует только программная реализация алгоритма.

Цепью Маркова называется последовательность испытаний, в каждом из которых появляется только одно из k несовместных событий Ai из полной группы. При этом условная вероятность pij(s) того, что в s-ом испытании наступит событие Aj при условии, что в (s - 1) - ом испытании наступило событие Ai, не зависит от результатов предшествующих испытаний.

Желающие повзрывать свой головной мозг могут почитать про математическую модель. На человеческом языке все эти формулы сводятся к следующему. В исходном тексте определяются слова и сохраняется последовательность, какие слова идут за какими. Затем на основании этих данных создается новый текст, в котором сами слова выбраны случайно, но сохранены связи между ними. Для примера возьмем детский стишок:

Из-за леса, из-за гор
едет дедушка Егор:
сам на лошадке,
жена на коровке,
дети на телятках,
внуки на козлятках.

Разберем текст на звенья и связки

Из-за [леса, гор]
леса [из-за]
гор [едет]
едет [дедушка]
дедушка [Егор]
Егор [сам]
сам [на]
на [лошадке, коровке, телятках, козлятках]
лошадке [жена]
жена [на]
коровке [дети]
дети [на]
телятках [внуки]
внуки [на]

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

При генерации текста из списка звеньев на первой итерации выбирается случайное звено, определяются его связи, из списка связей выбирается случайная и принимается уже как новое звено. Затем действие повторяется до достижения нужного размера текста. В результате, например, может получиться что-то подобное:

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

// Прочитать исходный текст, на основе которого будет генерироваться новый
$str = file_get_contents ("markov.txt" );
// Установить кодировку системы
setlocale (LC_ALL , "ru_RU.CP1251" );
// Убрать из текста символы кроме цифр, букв и некоторых знаков препинания
$str = eregi_replace ("[^-a-zа-я0-9 !\?\.\,]" , " " , $str );
// Подчистить пробелы перед окончаниями предложений
$str = eregi_replace (" {1,}([!\?\.\,])" , "\\1" , $str );
// Поделить текст на слова
$tmp = preg_split ("/[[:space:]]+/is" , $str );
// Массив "звеньев"
$words =Array();
// Заполнить звенья
for($i = 0 ; $i < count ($tmp ); $i ++) {
if ($tmp [ $i + 1 ]!= "" ) {
$words [ $tmp [ $i ]]= $tmp [ $i + 1 ];
$words = array_map ("array_unique" , $words );
// Массив начальных слов в предложениях
$start =Array();
foreach($words as $word => $links ) {
if (ereg ("^[А-Я][а-я]+" , $word )) {
$start = $word ;
// Сгененировать 100 предложений на основе исходного текста
for ($i = 0 ; $i < 100 ; $i ++) {
while (true ) {
$w = $start [ rand (0 ,(count ($start )- 1 ))];
if (ereg ("[\.!\?]$" , $w )) { continue; }
$sentence = $w . " " ;
// Количество слов в предложении
$cnt = 1 ;
// Сгенерировать предложение
while(true ) {
$links = $words [ $w ];
// Переключить цепочку
$w = $words [ $w ][ rand (0 ,(count ($words [ $w ])- 1 ))];
$sentence .= $w . " " ;
// Если слово находилось в конце предложения
if (ereg ("[\.!\?]$" , $w )) { break; }
$cnt ++;
// Если генератор зациклился, то принудительно выйти
if ($cnt > 19 ) { break; }
// Удачным считать предложение длиной 5-20 слов
if ($cnt > 5 && $cnt < 20 ) { break; }
// Сгенерированное предложение
echo $sentence ;

Небольшие пояснения, как это все работает. Сперва загружается файл "markov.txt", он должен быть в кодировке win-1251. Затем из него удаляются все символы, кроме букв и некоторых знаков препинания, потом вырезаются излишние пробелы. Получается чистый текст, который затем разделяется на отдельные слова. Все, у нас есть отдельные звенья цепи. Теперь надо определить связи слов, то есть какие слова и за какими могут располагаться. Это самый ресурсоемкий процесс, так что на больших файлах придется запастись терпением. Если генерация требуется часто, то, наверное, имеет смысл сохранять массив звеньев и связок в какой-нибудь базе, чтобы иметь к нему быстрый доступ. Следующий шаг - определение слов, с которых начинаются предложения. Я принял условие, что у таких слов первая буква должна быть заглавной, вы можете сделать более точное определение. Генерация текста выполняется по описанному выше алгоритму, я только добавил к нему несколько проверок от зацикливания.

Рабочий пример генератора текстов на основе цепей Маркова и приведенного выше скрипта, можете посмотреть