Цепи Маркова простыми словами
EXPLAIN для запроса по пользователю вы видите Index Scan using orders_user_id_idx on orders. Какой вывод наиболее корректен?Зачем это знать
Путь пользователя, моделирование атрибуции, прогноз оттока на основе состояний — всё это можно моделировать цепями Маркова. В MarTech и веб-аналитике Markov chains — рабочий инструмент.
На собесах в FAANG и топовых компаниях могут спросить: «как бы вы моделировали атрибуцию пути пользователя?» — Markov chains один из лучших ответов.
Короткое объяснение
Цепь Маркова — система состояний с вероятностями переходов между ними. Ключевое свойство: будущее зависит только от текущего состояния, а не от истории. Memoryless.
Пример
Пользователь на сайте: состояния Home, Catalog, Product, Checkout, Exit.
Переходы (с какой вероятностью из Home идут куда):
- Home → Catalog: 0.6
- Home → Product: 0.1
- Home → Exit: 0.3
Сумма вероятностей из каждого состояния равна 1.
Матрица переходов
Home Catalog Product Checkout Exit
Home 0.0 0.6 0.1 0.0 0.3
Catalog 0.1 0.0 0.7 0.0 0.2
Product 0.05 0.1 0.0 0.6 0.25
Checkout 0.0 0.0 0.0 0.0 1.0 (absorbing)
Exit 0.0 0.0 0.0 0.0 1.0 (absorbing)Checkout и Exit — absorbing states (не выходят).
Markov property
P(Xt+1 | X1, X2, ..., Xt) = P(Xt+1 | Xt)Где бы user ни был раньше — следующий шаг определяется только текущим состоянием.
Это сильное допущение. В реальности часто нарушается (память есть).
Стационарное распределение
При большом N user «оседает» в распределении состояний. Это steady state.
Вычисляется через eigenvectors матрицы.
Использование: долгосрочные пропорции времени в каждом состоянии.
Использование
Атрибуция
Маркетинговые каналы — как состояния. Конверсия — поглощающее состояние.
Removal effect: убираем канал из матрицы и смотрим, насколько упадёт конверсия. Это и есть его вклад.
Прогноз оттока
Пользователь в состояниях: Active, Inactive, Returning, Churned (поглощающее).
Вероятность оттока за N периодов рассчитывается из матрицы.
Рекомендации
Предсказание следующего состояния: «если сейчас смотрит X, что будет дальше?».
NLP
Текст как цепь слов. Почему после «the» чаще встречается существительное.
В Python
import numpy as np
# Матрица переходов
P = np.array([
[0.0, 0.6, 0.1, 0.0, 0.3],
[0.1, 0.0, 0.7, 0.0, 0.2],
[0.05, 0.1, 0.0, 0.6, 0.25],
[0.0, 0.0, 0.0, 1.0, 0.0],
[0.0, 0.0, 0.0, 0.0, 1.0]
])
# Через 2 шага
P2 = P @ P # matrix multiplication
# Стартовое состояние: Home
start = np.array([1, 0, 0, 0, 0])
# Распределение после 5 шагов
dist = start @ np.linalg.matrix_power(P, 5)Higher-order chains
Если Markov property нарушено (память важна) — используют цепи n-го порядка, где следующее состояние зависит от последних n состояний.
На практике редко — растёт число параметров, требуется больше данных.
Hidden Markov Models
Расширение: настоящие состояния скрыты, видны только наблюдения. Применяется в распознавании речи и биоинформатике.
На собесе
«Что такое Markov chain?» Система состояний с вероятностями переходов, memoryless.
«Где используется в аналитике?» Атрибуция, отток, предсказание следующего состояния.
«Memoryless — это что?» Будущее зависит только от текущего состояния.
«Как найти стационарное распределение?» Собственный вектор матрицы переходов с собственным значением 1.
Частые ошибки
Memoryless — сильное допущение
В реальности пользователи обычно имеют «память» — если посещали каталог 5 раз, шанс покупки выше. Простая цепь Маркова это игнорирует.
Мало данных — шумные переходы
На редких переходах оценки нестабильны. Нужна регуляризация или группировка похожих состояний.
Забыли поглощающие состояния
Checkout и Exit — поглощающие. Без них матрица не сходится и стационарное распределение не считается.
Слишком много состояний
Каждое состояние даёт N переходов — 50 состояний требуют 2500 оценок. На маленьком трафике почти все будут нулями.
Связанные темы
FAQ
Как отличить от другой модели?
Markov chain — дискретные состояния с переходами. Регрессия — непрерывные значения.
Для больших state spaces?
Трудно оценить все вероятности. Используют аппроксимации или нейронные сети.
Библиотеки в Python?
pomegranate, hmmlearn или вручную через numpy.