Эта статья охватывает самое базовое понимание цепей Маркова и ключевых терминов и объектов, связанных с ними.
Цепи Маркова относятся к числу наиболее важных случайных процессов. Это стохастические процессы, для которых описание текущего состояния полностью охватывает всю информацию, которая может повлиять на будущее развитие процесса. Прогнозирование транспортных потоков, коммуникационных сетей, генетических проблем и очередей — примеры того, как цепи Маркова можно использовать для моделирования производительности. Google использует цепь Маркова в своем алгоритме ранжирования страниц для определения порядка поиска.
Цепь Маркова или Марковский процесс — это стохастическая модель, описывающая последовательность возможных событий, в которой вероятность каждого события зависит только от состояния, достигнутого в предыдущем событие
Обычно мы используем данные как «измерения», строим «модель», чтобы делать «прогнозы». Если этот процесс осуществляется в контексте временной зависимости, мы можем разделить время на прошлое, настоящее и будущее. Мы можем рассматривать прошлые и настоящие наблюдения как измерения и предсказывать будущее на их основе. Последовательность событий образует цепь Маркова.
Ключевые термины
Состояния.Возможности определяются как состояния. Например, если событие бросает монету, пространство состояний равно {H,T}. Для броска костей пространство состояний равно {1,2,3,4,5,6}.
Случайная переменная:переменная, значение которой неизвестно, или функция, которая присваивает значения каждому результату эксперимента. В случае броска 2 костей допустимой случайной величиной являются: сумма/произведение результатов, количество нечетных результатов. По сути, все, что поддается измерению и может быть рассчитано на основе определенного события.
Случайный процесс:серия результатов случайной величины. Для цепей Маркова это ряд, соответствующий времени t.
Вероятность перехода: представляет собой вероятность получения состояния i в момент времени t данного состояния как j в момент времени t-1. Эти значения представлены матрицей N X N, где N — количество состояний в пространстве состояний.
Учтите, что в данный день может быть солнечно, облачно или дождливо, что обозначается буквами A, B и C соответственно. Вероятность состояния зависит только от состояния в предыдущий день. Обычно это матрица N X N, где N — количество состояний в модели, 3 в данном конкретном примере. Это может быть представлено графом, а также с взвешенными ребрами, например,
Матрица перехода, соответствующая этому, будет,
Следуя свойству полноты вероятности, еще одна важная особенность заключается в том, что все элементы должны быть неотрицательными, а все строки должны суммарно давать 1.
Если элементы переходной матрицы не зависят от времени, она называется однородной по времени цепью Маркова.
Начальная вероятность:это матрица N X 1, представляющая вероятность запуска определенного процесса.
Распределение:иногда мы не знаем точного состояния в любой момент времени, а знаем только вероятности. В этом случае состояние в момент времени t задается матрицей строк, где i-й элемент представляет вероятность пребывания в i-м состоянии. Это матрица N X 1, которая называется «распределение». В случае, если известно точное состояние, распределение может быть: H(t)= (0,0,1,0,0,0), когда система находится в 3-м состоянии в момент времени t.
Свойство без памяти
Это одно из наиболее важных свойств, также называемое свойством Маркова. Рассмотрите подбрасывание монеты, допустим, мы сначала получаем решку, вероятность выпадения орла/решки при следующем подбрасывании по-прежнему равна 0,5 (учитывая, что монета беспристрастна).
Таким образом, вероятность будущего для марковского процесса зависит не от части наблюдений, а только от настоящего. Математически это выражается как
Установка цепи Маркова
Это обратная задача для реализации цепей Маркова. Как их построить? Или как вы находите матрицу перехода по существу?
Должны быть некоторые данные, которые используются для создания матрицы, которая затем используется для прогнозирования. Учитывая наш предыдущий пример для A = солнечно, B = облачно, C = дождливо, предположим, что нам даны данные за 10 дней (просто для примера. В общем, нам нужен больший набор данных, чтобы сделать осмысленный прогноз) как:
E= ABBAACBCAC
Тогда (i,j)-й элемент матрицы перехода задается выражением
Это очень интуитивно понятно. Например, у нас есть A 4 раза, которому предшествует A один раз, B один раз и C дважды. Таким образом, вероятность перехода A в A, B, C равна 1/4, 1/4 и 2/4 соответственно. Таким образом, переходная матрица, основанная на заданной цепи Маркова, имеет вид
Обратите внимание, что сумма каждой строки равна 1.
На этом заканчивается самое основное введение в базовую цепь Маркова и связанные с ней ключевые термины.
