Це́пь Ма́ркова — последовательность случайных событий с конечным или счётным числом исходов, где вероятность наступления каждого события зависит только от состояния, достигнутого в предыдущем событии. Характеризуется тем свойством, что, говоря нестрого, при фиксированном настоящем будущее независимо от прошлого. Названа в честь А. А. Маркова (старшего), который впервые ввёл это понятие в работе 1906 года.
Последовательность случайных величин $\{X_n\}_{n \geqslant 0}$ называется простой цепью Маркова (с дискретным временем), если:
$$\mathbb{P}(X_{n+1} = i_{n+1} \mid X_n = i_n, X_{n-1} = i_{n-1},\ldots, X_0 = i_0) = \mathbb{P}(X_{n+1} = i_{n+1} \mid X_n = i_n).$$Таким образом, в простейшем случае условное распределение последующего состояния цепи Маркова зависит только от текущего состояния и не зависит от всех предыдущих состояний (в отличие от цепей Маркова высших порядков).
Область значений случайных величин $\{X_n\}$ называется простра́нством состоя́ний цепи, а номер $n$ — номером шага.
Матрица $P{(n)}$, где: $P_{ij}{(n)} \equiv \mathbb{P}(X_{n+1} = j \mid X_n = i)$ называется ма́трицей перехо́дных вероя́тностей на $n$-м шаге, а вектор $\mathbf{p} = (p_1,p_2,\ldots)^{\top}$, где: $p_i \equiv \mathbb{P}(X_0 = i)$ — нача́льным распределе́нием цепи Маркова.
Очевидно, матрица переходных вероятностей является стохастической справа, то есть: $\sum\limits_{j} P_{ij}(n) = 1, \quad \forall n \in \mathbb{N}$.
Цепь Маркова называется одноро́дной, если матрица переходных вероятностей не зависит от номера шага, то есть: $P_{ij}{(n)} = P_{ij},\quad \forall n \in \mathbb{N}$. В противном случае цепь Маркова называется неоднородной. В дальнейшем будем предполагать, что имеем дело с однородными цепями Маркова.
Из свойств условной вероятности и определения однородной цепи Маркова получаем:
$$\mathbb{P}(X_{n} = i_{n} , \ldots, X_0 = i_0) = P_{i_{n-1},i_n} \cdots P_{i_0,i_1} P_{i_0},$$откуда вытекает специальный случай уравнения Колмогорова — Чепмена:
$$\mathbb{P}(X_n = i_n \mid X_0 = i_0) = (P^n)_{i_0,i_n},$$то есть матрица переходных вероятностей за $n$ шагов однородной цепи Маркова есть $n$ - я степень матрицы переходных вероятностей за 1 шаг. Наконец:
$$\mathbb{P}(X_n = i_n) = \left((P^T)^n \mathbf{p}\right)_{i_n}.$$Генерация текста на основе данных - модель, основанная на Марковской цепи при помощи Python.
Логика программы:
Выбираем слово для старта. Чтобы было совсем непредсказуемо, начальное слово тоже будем выбирать случайным образом. Главное требование к начальному слову — первая заглавная буква. Выполним это условие так:
Опытные программисты абсолютно справедливо сделают нам замечание: не нужно писать новый алгоритм для обработки цепей Маркова, а использовать какую-нибудь готовую библиотеку типа Markovify.
import random
import backoff
class DictogramKeyException(BaseException):
pass
class MarkovModel(dict):
"""
MarkovModel(dict) будет отображать зависимость между звеньями и их частотой появления в тексте,
то есть их распределение. Но при этом она будет обладать нужным свойством словаря —
время выполнения программы не будет зависеть от объема входных данных, а это значит,
мы создаем эффективный алгоритм.
В конструктор структуре MarkovModel можно передать любой объект, по которому можно итерироваться.
Элементами этого объекта будут слова для инициализации MarkovModel,
например, все слова из какой-нибудь книги.
В данном случае мы ведем подсчет элементов,
чтобы для обращения к какому-либо из них не нужно было пробегать каждый раз по всему набору данных.
Реализовано две функции для возврата случайного слова.
get_random_word() - выбирает случайный ключ в словаре и возвращает нужное нам слово,
get_weighted_random_word() - учитывает число появлений каждого слова в тексте и возвращает нужное нам слово.
"""
def __init__(self, iterable=None):
super(MarkovModel, self).__init__()
self._unique_tokens = 0
self._tokens = 0
if iterable:
self.update(iterable)
def update(self, iterable):
for item in iterable:
if item in self:
self[item] += 1
self._tokens += 1
else:
self[item] = 1
self._unique_tokens += 1
self._tokens += 1
@property
def count(self, item):
return self[item] if item in self else 0
def get_random_word(self):
return random.sample([*self], 1)[0]
def get_weighted_random_word(self):
random_int = random.randint(0, self._tokens-1)
index = 0
list_of_keys = [*self]
for i in range(0, self._unique_tokens):
index += self[list_of_keys[i]]
if index > random_int:
return list_of_keys[i]
@backoff.on_exception(backoff.expo, [DictogramKeyException])
def get_random_text(self, *, words=10):
if not self:
return ""
current_word = random.choice(list(self))
while current_word[0].islower():
current_word = random.choice(list(self))
sentence = [word for word in current_word]
for i in range(0, words):
current_dictogram = self.get(current_word)
if current_dictogram is None:
raise DictogramKeyException
new_tup = list(current_word[1:])
new_tup.append(current_dictogram.get_weighted_random_word())
current_word = tuple(new_tup)
sentence.append(new_tup[-1])
return " ".join(sentence)
def generate_markov_model(data, *, order=1):
"""
Храним кортеж в качестве ключа в паре «(ключ, значение)» в словаре.
Используем его вместо списка, так как кортеж защищен от любых изменений,
а для нас это важно — ведь ключи в словаре меняться не должны.
"""
markov_model = MarkovModel()
for i in range(0, len(data)-order):
window = tuple(data[i: i+order])
if window in markov_model:
markov_model[window].update([data[i+order]])
else:
markov_model[window] = MarkovModel([data[i+order]])
return markov_model
tolstoy_text_data = open("./war_and_peace.txt", "r", encoding="utf-8").read().split()
chehov_text_data = open("./chehov.txt", "r", encoding="utf-8").read().split()
tolstoy_markov_model = generate_markov_model(tolstoy_text_data, order=2)
chehov_markov_model = generate_markov_model(chehov_text_data, order=2)
tolstoy_and_chehov_markov_model = generate_markov_model(tolstoy_text_data+chehov_text_data, order=2)
tolstoy_markov_model.get_random_text(words=100)
'Свидание с Пьером тоже вышли на крыльцо занимаемого государем дома. С крыльца широкая лестница вела прямо наверх; направо видна была одна какая то гордость мысли, – сказала княжна Марья мечтала, как мечтают всегда девушки, выдать за своего воспитанника. Вот как все колонны еще собрались, ваше величество. – Французы успели сделать три картечные выстрела, прежде чем итти вперед; но что он разумел под словами всё кончится , – серьезно и взволнованно, остановились на молодой княгине. Молодая княгиня испытывала в то время, как Ростов подъехал к нему. – Ругай! На, на, – крикнул он, стоя на коленях, обдергивая платье и прическу. – Право, ей'
chehov_markov_model.get_random_text(words=100)
'Да, ты никогда не писал непосредственно с натуры. Мне нужно, чтобы память моя процедила сюжет и чтобы она и посмотрела на Полю. Самый жалкий и преступный вид имели два пирожка на тарелочке. «Сегодня нас унесут обратно в дом. Было тихо, и в этих краях, узнавала теперь в толпе то своего покойного отца, ради моего покоя, будь с ним изъявляли радость. И этот человек, который, казалось, своею святостью оградил себя от голода, холода, физического напряжения, — от самого себя. — Что же? Он прав. Я завтра уеду отсюда, — сказала Анна Акимовна вошла во двор входил жид Мойсейка, возвращавшийся с добычи. Он был'
tolstoy_and_chehov_markov_model.get_random_text(words=100)
'Доктор, с засученными рукавами рубашки, без сюртука, бледный и испуганный обер гофмаршал граф Толстой, выехавший с другими эскадронами. На другой день, сильно озяб и, дождавшись потемок, тайком, как вор, пробрался к себе и стала смотреть. – Вот это какой человек, и не приходила мне в глаза ему. И Аустерлиц с высоким небом, и мертвое, укоризненное лицо жены, которая продолжала стоять к нему вместе с своим чувством к Сперанскому, прощаясь с дяденькой, вспоминала Соня. Да это верно, действительно… А сам силен, здоров, весел и оживлен; но это лучше. Лучше, мой друг. Ты помни, Катишь, что всё это время почувствовал, что весь свет потерял'
В эих текстах нет смысла, хотя все слова связаны друг с другом. Чтобы результат был более читабельным, нужно увеличить количество слов и оптимизировать алгоритм.