Просмотр

Материал из MachineLearning.

У вас нет прав на выполнение этой операции по следующим причинам:

• Запрошенное действие могут выполнять только участники из групп emailconfirmed, Администраторы.
• Вы должны подтвердить ваш адрес электронной почты перед правкой страниц. Пожалуйста, введите и подтвердите ваш адрес эл. почты на странице настроек.

Вы можете просмотреть и скопировать исходный текст этой страницы:

{{well|Статья написана с использованием LLM '''GPT-5.5 Thinking''' и проверена участником [[Участник:Andrei Blinov|Andrei Blinov]] 18:09, 28 июня 2026 (MSD)}} '''Марковский процесс''' — это [[стохастический процесс]], для которого условное распределение будущего при известном настоящем не зависит от прошлого. Это свойство называется [[марковское свойство|марковским свойством]]. Неформально говорят, что процесс «не имеет памяти», если текущее состояние содержит всю информацию, необходимую для описания дальнейшей эволюции. Марковские процессы используются в [[теория вероятностей|теории вероятностей]], [[математическая статистика|математической статистике]], [[машинное обучение|машинном обучении]], [[обучение с подкреплением|обучении с подкреплением]], [[байесовский вывод|байесовском выводе]], [[анализ временных рядов|анализе временных рядов]] и [[теория массового обслуживания|теории массового обслуживания]]. == Определение == Пусть <tex>{X_t}_{t\in T}</tex> — [[стохастический процесс]] со значениями в [[пространство состояний|пространстве состояний]] <tex>E</tex>. Процесс называется '''марковским''', если для любых моментов времени <tex>s<t</tex> условное распределение <tex>X_t</tex> при известной истории процесса до момента <tex>s</tex> зависит только от текущего состояния <tex>X_s</tex>. В дискретном времени это свойство записывается как :<tex>\mathbb{P}(X_{n+1}=x_{n+1}\mid X_n=x_n,\ldots,X_0=x_0)=\mathbb{P}(X_{n+1}=x_{n+1}\mid X_n=x_n).</tex> Для произвольного измеримого множества <tex>B\subseteq E</tex>: :<tex>\mathbb{P}(X_{n+1}\in B\mid X_0,\ldots,X_n)=\mathbb{P}(X_{n+1}\in B\mid X_n).</tex> Марковское свойство не означает независимости случайных величин <tex>X_0,X_1,\ldots</tex>. Оно означает [[условная независимость|условную независимость]] будущего от прошлого при известном настоящем. == Переходные вероятности == Основным объектом, задающим марковский процесс, является [[переходная функция]] или [[переходное ядро]]. В дискретном времени переходная вероятность имеет вид :<tex>P(x,B)=\mathbb{P}(X_{n+1}\in B\mid X_n=x).</tex> Если пространство состояний конечно, <tex>E={1,\ldots,m}</tex>, то переходы задаются [[матрица переходных вероятностей|матрицей переходных вероятностей]] :<tex>P_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i),\quad i,j\in E.</tex> Элементы матрицы удовлетворяют условиям :<tex>P_{ij}\geq 0,\qquad \sum_j P_{ij}=1.</tex> Если начальное распределение задано строковым вектором <tex>\mu_0</tex>, то распределение через <tex>n</tex> шагов равно :<tex>\mu_n=\mu_0P^n.</tex> Элемент <tex>(P^n)_{ij}</tex> равен вероятности перейти из состояния <tex>i</tex> в состояние <tex>j</tex> за <tex>n</tex> шагов. == Однородные и неоднородные процессы == Марковский процесс называется '''однородным по времени''', если вероятности перехода зависят только от длины временного интервала, но не от начального момента времени: :<tex>\mathbb{P}(X_{s+t}\in B\mid X_s=x)=P_t(x,B).</tex> Если это условие не выполняется, процесс называется '''неоднородным по времени'''. В этом случае переходное ядро обычно записывают как :<tex>P(s,x;t,B)=\mathbb{P}(X_t\in B\mid X_s=x).</tex> Для однородного марковского процесса переходные функции удовлетворяют [[уравнение Чепмена — Колмогорова|уравнению Чепмена — Колмогорова]] :<tex>P_{t+u}(x,B)=\int_E P_t(x,dy)P_u(y,B).</tex> В конечном дискретном случае это уравнение сводится к умножению матриц: :<tex>P^{n+m}=P^nP^m.</tex> == Цепь Маркова == '''[[Цепь Маркова]]''' — частный случай марковского процесса с дискретным временем. Если пространство состояний конечно или счётно, цепь удобно описывать матрицей переходных вероятностей. Пример процесса с двумя состояниями <tex>0</tex> и <tex>1</tex>: :<tex>P=\begin{pmatrix}1-a & a\ b & 1-b\end{pmatrix},\qquad 0\leq a,b\leq 1.</tex> Такая модель может описывать переходы между двумя режимами, например «исправен» и «неисправен» или «активен» и «неактивен». == Марковские процессы в непрерывном времени == Если множество моментов времени непрерывно, например <tex>T=[0,\infty)</tex>, говорят о [[марковский процесс в непрерывном времени|марковском процессе в непрерывном времени]]. Для конечного пространства состояний такой процесс часто задаётся [[инфинитезимальный генератор|инфинитезимальным генератором]] <tex>Q=(q_{ij})</tex>, где :<tex>q_{ij}\geq 0,\quad i\neq j,\qquad q_{ii}=-\sum_{j\neq i}q_{ij}.</tex> Число <tex>q_{ij}</tex> интерпретируется как интенсивность перехода из состояния <tex>i</tex> в состояние <tex>j</tex>. Матрица переходных вероятностей за время <tex>t</tex> выражается через матричную экспоненту: :<tex>P_t=e^{tQ}.</tex> Если <tex>\mu_t</tex> — распределение процесса в момент <tex>t</tex>, то для конечной непрерывновременной цепи выполняется прямое [[уравнения Колмогорова|уравнение Колмогорова]] :<tex>\frac{d\mu_t}{dt}=\mu_t Q.</tex> == Стационарное распределение == [[Стационарное распределение]] — это распределение <tex>\pi</tex>, которое не меняется при применении переходного оператора. Для дискретной цепи Маркова оно удовлетворяет уравнению :<tex>\pi=\pi P.</tex> В координатах: :<tex>\pi_j=\sum_i \pi_iP_{ij},\qquad \sum_j\pi_j=1,\qquad \pi_j\geq 0.</tex> Если цепь запущена из стационарного распределения, то распределение <tex>X_n</tex> остаётся равным <tex>\pi</tex> для всех <tex>n</tex>. Для непрерывновременной конечной цепи стационарное распределение удовлетворяет :<tex>\pi Q=0.</tex> Стационарное распределение важно в [[MCMC|методах Монте-Карло по схеме марковских цепей]], где цепь строится так, чтобы её стационарное распределение совпадало с заданным целевым распределением. == Классификация состояний == === Достижимость и неприводимость === Состояние <tex>j</tex> называется достижимым из состояния <tex>i</tex>, если существует <tex>n\geq 0</tex>, такое что :<tex>(P^n)_{ij}>0.</tex> Цепь Маркова называется [[неприводимая цепь Маркова|неприводимой]], если любые два состояния сообщаются друг с другом, то есть из каждого состояния можно попасть в любое другое за конечное число шагов с положительной вероятностью. === Рекуррентность и транзиентность === Состояние называется [[рекуррентное состояние|рекуррентным]], если процесс, стартовав из него, возвращается в него с вероятностью <tex>1</tex>. Состояние называется [[транзиентное состояние|транзиентным]], если вероятность когда-либо вернуться в него меньше <tex>1</tex>. В конечной неприводимой цепи все состояния рекуррентны. В бесконечных пространствах состояний возможны оба варианта. Например, [[случайное блуждание]] на <tex>\mathbb{Z}</tex> рекуррентно, а на <tex>\mathbb{Z}^3</tex> транзиентно. === Периодичность === Период состояния <tex>i</tex> в дискретной цепи Маркова определяется как :<tex>d(i)=\operatorname{gcd}\left\{\,n\geq 1:\; \mathbb{P}(X_n=i\mid X_0=i)>0\,\right\}.</tex> Если <tex>d(i)=1</tex>, состояние называется [[апериодическая цепь Маркова|апериодическим]]. Периодичность влияет на сходимость распределения <tex>\mu_0P^n</tex> к стационарному распределению. === Эргодичность === Для конечной цепи Маркова часто используется следующий достаточный набор условий сходимости к стационарному распределению: неприводимость и апериодичность. В этом случае существует единственное стационарное распределение <tex>\pi</tex>, и :<tex>\mu_0P^n\to\pi,\qquad n\to\infty.</tex> Сходимость может нарушаться, если цепь периодична или пространство состояний бесконечно и не выполнены дополнительные условия положительной рекуррентности. == Обратимость и детальный баланс == Цепь Маркова называется [[обратимая цепь Маркова|обратимой]] относительно распределения <tex>\pi</tex>, если выполнено условие [[детальный баланс|детального баланса]] :<tex>\pi_iP_{ij}=\pi_jP_{ji}.</tex> Из детального баланса следует стационарность распределения <tex>\pi</tex>. Это условие часто используется при построении MCMC-алгоритмов, поскольку его обычно проще проверить, чем стационарность напрямую. == Сильное марковское свойство == [[Сильное марковское свойство]] распространяет марковское свойство с фиксированных моментов времени на случайные моменты, называемые [[момент остановки|моментами остановки]]. Смысл свойства состоит в том, что после момента остановки процесс, условно на текущем состоянии, развивается как новый марковский процесс и не зависит от предыдущей траектории. Сильное марковское свойство используется при изучении [[время достижения|времён достижения]], [[случайное блуждание|случайных блужданий]], [[диффузионный процесс|диффузионных процессов]] и задач [[оптимальная остановка|оптимальной остановки]]. == Примеры == === Случайное блуждание === [[Случайное блуждание]] — один из простейших примеров цепи Маркова. В одномерном случае процесс на <tex>\mathbb{Z}</tex> может задаваться переходами :<tex>\mathbb{P}(X_{n+1}=X_n+1)=p,\qquad \mathbb{P}(X_{n+1}=X_n-1)=1-p.</tex> Случайные блуждания применяются в [[теория графов|теории графов]], [[спектральная кластеризация|спектральной кластеризации]], [[PageRank]] и моделировании диффузии. === Пуассоновский процесс === [[Пуассоновский процесс]] с интенсивностью <tex>\lambda</tex> — марковский процесс в непрерывном времени на множестве <tex>\mathbb{N}</tex>. Если <tex>X_t</tex> — число событий к моменту <tex>t</tex>, то переходы возможны только из <tex>n</tex> в <tex>n+1</tex>. Его генератор имеет вид :<tex>q_{n,n+1}=\lambda,\qquad q_{nn}=-\lambda.</tex> === Процесс рождения и гибели === [[Процесс рождения и гибели]] — непрерывновременная цепь Маркова на <tex>\mathbb{N}</tex>, в которой переходы возможны только между соседними состояниями: :<tex>n\to n+1,\qquad n\to n-1.</tex> Такие процессы применяются в [[теория массового обслуживания|теории массового обслуживания]], популяционной динамике и моделировании очередей. === Винеровский процесс === [[Винеровский процесс]], или [[броуновское движение]], — марковский процесс с непрерывными траекториями и независимыми приращениями. Он является базовой моделью для [[диффузионный процесс|диффузионных процессов]] и [[стохастическое дифференциальное уравнение|стохастических дифференциальных уравнений]]. == Марковские процессы в машинном обучении == === Скрытые марковские модели === [[Скрытая марковская модель]] — это вероятностная модель, в которой скрытые состояния <tex>Z_1,\ldots,Z_T</tex> образуют цепь Маркова, а наблюдения <tex>X_1,\ldots,X_T</tex> зависят от текущих скрытых состояний. Типичная факторизация совместного распределения имеет вид :<tex>p(z_{1:T},x_{1:T})=p(z_1)p(x_1\mid z_1)\prod_{t=2}^T p(z_t\mid z_{t-1})p(x_t\mid z_t).</tex> Основные алгоритмы для скрытых марковских моделей: * [[алгоритм Витерби]] — поиск наиболее вероятной последовательности скрытых состояний; * [[алгоритм прямого-обратного хода]] — вычисление апостериорных вероятностей скрытых состояний; * [[алгоритм Баума — Велша]] — частный случай [[EM-алгоритм|EM-алгоритма]] для оценки параметров. === Марковские процессы принятия решений === [[Марковский процесс принятия решений]] — управляемое обобщение марковского процесса. В нём переход зависит не только от состояния, но и от действия: :<tex>P(s'\mid s,a).</tex> Обычно MDP задаётся набором :<tex>(S,A,P,R,\gamma),</tex> где <tex>S</tex> — множество состояний, <tex>A</tex> — множество действий, <tex>P</tex> — переходная функция, <tex>R</tex> — функция награды, <tex>\gamma</tex> — коэффициент дисконтирования. Если [[политика]] <tex>\pi(a\mid s)</tex> фиксирована, то MDP индуцирует марковский процесс по состояниям. Теория MDP лежит в основе [[обучение с подкреплением|обучения с подкреплением]], [[динамическое программирование|динамического программирования]] и [[уравнение Беллмана|уравнений Беллмана]]. === MCMC === [[Метод Монте-Карло по схеме марковских цепей]] строит цепь Маркова, стационарным распределением которой является заданное целевое распределение <tex>\pi(x)</tex>. После начального участка траектории, называемого [[burn-in]], состояния цепи используются как зависимая выборка из <tex>\pi</tex>. В [[алгоритм Метрополиса — Гастингса|алгоритме Метрополиса — Гастингса]] из текущего состояния <tex>x</tex> предлагается новое состояние <tex>y\sim q(y\mid x)</tex>, которое принимается с вероятностью :<tex>\alpha(x,y)=\min\left{1,\frac{\pi(y)q(x\mid y)}{\pi(x)q(y\mid x)}\right}.</tex> Целевое распределение <tex>\pi</tex> достаточно знать с точностью до нормировочной константы, что делает MCMC удобным инструментом [[байесовский вывод|байесовского вывода]]. === Марковские модели последовательностей === Марковское предположение часто применяется к [[временной ряд|временным рядам]] и последовательностям. Модель первого порядка задаётся факторизацией :<tex>p(x_{1:T})=p(x_1)\prod_{t=2}^T p(x_t\mid x_{t-1}).</tex> Модель порядка <tex>k</tex> предполагает, что :<tex>p(x_t\mid x_{t-1},\ldots,x_1)=p(x_t\mid x_{t-1},\ldots,x_{t-k}).</tex> Любой процесс порядка <tex>k</tex> можно представить как процесс первого порядка, расширив состояние: :<tex>Y_t=(X_{t-k+1},\ldots,X_t).</tex> == Оценивание параметров == Для конечной однородной цепи Маркова параметры матрицы переходов можно оценить по наблюдаемой траектории. Пусть <tex>N_{ij}</tex> — число наблюдавшихся переходов из состояния <tex>i</tex> в состояние <tex>j</tex>. Тогда [[метод максимального правдоподобия|оценка максимального правдоподобия]] имеет вид :<tex>\widehat P_{ij}=\frac{N_{ij}}{\sum_k N_{ik}}.</tex> Если некоторые переходы не наблюдались, применяют сглаживание. Например, при [[априорное распределение Дирихле|априорном распределении Дирихле]] можно использовать апостериорное среднее :<tex>\widehat P_{ij}=\frac{N_{ij}+\alpha_{ij}}{\sum_k(N_{ik}+\alpha_{ik})}.</tex> В [[скрытая марковская модель|скрытых марковских моделях]] состояния не наблюдаются напрямую, поэтому параметры обычно оцениваются с помощью [[EM-алгоритм|EM-алгоритма]], [[вариационный вывод|вариационного вывода]] или [[MCMC]]. == Типичные замечания == * Марковское свойство зависит от выбора состояния. Если состояние содержит недостаточно информации о прошлом, наблюдаемый процесс может оказаться немарковским. * Марковость не равна независимости. Соседние состояния цепи обычно зависимы. * Стационарность и марковость — разные свойства. Марковский процесс может быть нестационарным. * Наличие стационарного распределения не всегда означает сходимость к нему из любого начального состояния. * В MCMC последовательные состояния зависимы, поэтому число итераций не совпадает с эффективным размером выборки. == См. также == * [[Стохастический процесс]] * [[Цепь Маркова]] * [[Скрытая марковская модель]] * [[Марковский процесс принятия решений]] * [[Метод Монте-Карло по схеме марковских цепей]] * [[Обучение с подкреплением]] == Литература == * Markov A. A. Extension of the law of large numbers to quantities, depending on each other. — 1906. * Norris J. R. Markov Chains. — Cambridge University Press, 1997. * Levin D. A., Peres Y., Wilmer E. L. Markov Chains and Mixing Times. — American Mathematical Society, 2009; 2nd ed., 2017. * Puterman M. L. Markov Decision Processes: Discrete Stochastic Dynamic Programming. — Wiley, 1994. * Sutton R. S., Barto A. G. Reinforcement Learning: An Introduction. — 2nd ed. — MIT Press, 2018. * Rabiner L. R. A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition // Proceedings of the IEEE. — 1989. * Metropolis N., Rosenbluth A. W., Rosenbluth M. N., Teller A. H., Teller E. Equation of State Calculations by Fast Computing Machines // Journal of Chemical Physics. — 1953. * Hastings W. K. Monte Carlo Sampling Methods Using Markov Chains and Their Applications // Biometrika. — 1970. == Ссылки == * [https://encyclopediaofmath.org/wiki/Transition_function Transition function] — Encyclopedia of Mathematics. * [https://ocw.mit.edu/courses/6-041-probabilistic-systems-analysis-and-applied-probability-fall-2010/resources/lecture-16-markov-chains-i/ Markov Chains I] — MIT OpenCourseWare. * [https://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf Markov Chains and Mixing Times] — электронная версия книги Levin, Peres, Wilmer. * [https://incompleteideas.net/book/the-book-2nd.html Reinforcement Learning: An Introduction] — страница книги Sutton, Barto. * [https://www.cs.ubc.ca/~murphyk/Bayes/rabiner.pdf A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition] — Rabiner, 1989. [[Категория:Теория вероятностей]] [[Категория:Математическая статистика]] [[Категория:Стохастические процессы]] [[Категория:Машинное обучение]] [[Категория:Обучение с подкреплением]]

• Шаблон:Mbox
• Шаблон:Well

Возврат к странице Марковский процесс.