Как работает цепь Моркова и что такое отсутствие памяти?
Как работают цепи Маркова? Я прочитал Википедию для Марковской Цепи, но то, что я не получаю, это отсутствие памяти. Без памяти утверждает, что:
Следующее состояние зависит только от текущего состояния, а не от последовательности событий, предшествовавших ему.
Если цепь Маркова обладает таким свойством, то какая польза от цепи в модели Маркова?
Объясните это свойство.
2 ответа
Вы можете визуализировать цепи Маркова, как лягушка, прыгающая с лилии на лилию на пруду. Лягушка не помнит, какую лилию (ы) она посетила ранее. Он также имеет заданную вероятность для прыжка от лилии Ai к лилии Aj для всех возможных комбинаций i и j. Цепочка Маркова позволяет рассчитать вероятность того, что лягушка окажется на определенной лилии в любой момент.
Если лягушка была вегетарианкой и кусала лилию каждый раз, когда приземлялась на нее, то вероятность того, что она приземлится на лилию Ai из лилии Aj, также будет зависеть от того, сколько раз Ai посещали ранее. Тогда вы не сможете использовать цепь Маркова, чтобы смоделировать поведение и таким образом предсказать местоположение лягушки.
Идея отсутствия памяти является основой успеха цепей Маркова. Это не значит, что мы не заботимся о прошлом. Напротив, это означает, что мы сохраняем только самую актуальную информацию из прошлого для прогнозирования будущего и используем эту информацию для определения настоящего. Эта хорошая статья дает хорошую справочную информацию по этому вопросу http://www.americanscientist.org/issues/pub/first-links-in-the-markov-chain
Существует компромисс между точностью вашего описания прошлого и размером соответствующего пространства состояний. Скажем, по соседству есть три паба, и каждый вечер вы выбираете один. Если вы выбираете эти пабы случайным образом, это не цепочка Маркова (или тривиальная, нулевого порядка) - результат случайный. Точнее, это независимая случайная величина (модельная зависимость была фундаментальной для марковских идей, лежащих в основе цепей Маркова).
Выбирая пабы, вы можете учитывать свой последний выбор, т. Е. Какой паб вы посещали прошлой ночью. Например, вы можете не ходить в один и тот же паб два дня подряд. В то время как на самом деле это означает, что вы помните, где вы были вчера (и, следовательно, вспоминаете прошлое!), На вашем уровне моделирования ваша единица времени составляет один день, поэтому ваше текущее состояние - это паб, в который вы ходили вчера. Это ваша классическая модель Маркова (первого порядка) с тремя состояниями и матрицей переходов 3 на 3, которая обеспечивает условные вероятности для каждой перестановки (если вчера вы ходили в паб I, что за изменение вы сегодня "перепрыгиваете" в паб J),
Однако вы можете определить модель, в которой вы "помните" последние два дня. В этом "нынешнем" состоянии марковской модели второго порядка будут учитываться знания паба с прошлой ночи и с предыдущей ночи. Теперь у вас есть 9 возможных состояний, описывающих ваше текущее состояние, и, следовательно, у вас есть матрица переходов 9 на 9. К счастью, эта матрица не полностью заполнена.
Чтобы понять, почему, рассмотрите немного другую схему, когда вы настолько хорошо организованы, что вы строите четкие планы на ваш выбор пабов на сегодня и завтра, основываясь на двух последних посещениях. Затем вы можете выбрать любые возможные перестановки пабов, посещаемых в течение двух дней подряд. В результате получается полностью заполненная матрица 9 на 9, которая отображает ваш выбор за последние два дня на выбор следующих двух дней. Тем не менее, в нашей первоначальной проблеме мы принимаем решение каждый день, поэтому наше будущее состояние ограничено тем, что произошло сегодня: на следующем временном шаге (завтра) сегодня становится вчера, но оно все равно будет частью вашего определения "сегодня" на этом временном шаге и имеет отношение к тому, что происходит на следующий день. Ситуация аналогична скользящим средним или процедурам отступающего горизонта. В результате из заданного состояния вы можете перейти только к трем возможным состояниям (что указывает на ваш сегодняшний выбор пабов), что означает, что в каждой строке матрицы перехода будет только три ненулевых элемента.
Давайте подсчитаем количество параметров, которые характеризуют каждую проблему: модель Маркова нулевого порядка с тремя состояниями имеет два независимых параметра (вероятность попадания в первый и второй паб, так как вероятность посещения третьего паба является дополнением к первые два). Марковская модель первого порядка имеет полностью заполненную матрицу 3 на 3, в которой каждый столбец суммирует до одного (опять же, это указывает на то, что один из пабов всегда будет посещаться в любой конкретный день), поэтому мы получаем шесть независимых параметров. Модель Маркова второго порядка имеет матрицу 9 на 9, в каждой строке только 3 ненулевых элемента и все столбцы добавляются к одному, поэтому у нас есть 18 независимых параметров. Мы можем продолжить определение моделей более высокого порядка, и наше пространство состояний будет соответственно расти.
Важно отметить, что мы можем дополнительно уточнить концепцию, идентифицируя важные черты прошлого и использовать только те черты, чтобы определить настоящее, то есть сжать информацию о прошлом. Это то, что я упоминал в начале. Например, вместо запоминания всей истории мы можем отслеживать только некоторые запоминающиеся события, которые влияют на наш выбор, и использовать эту "достаточную статистику" для построения модели.
Все сводится к тому, как вы определяете соответствующие переменные (пространство состояний), и марковские понятия естественно вытекают из основополагающих фундаментальных математических понятий. Связи первого порядка (линейные) (и связанные с ними операции линейной алгебры) лежат в основе большинства современных математических приложений. Вы можете посмотреть на полиномиальное уравнение n-го числа с одной переменной или определить эквивалентную (линейную) систему n уравнений первого порядка, определив вспомогательные переменные. Точно так же в классической механике вы можете использовать уравнения Лагранжа второго порядка или выбрать канонические координаты, которые приводят к гамильтоновой формулировке (первого порядка) http://en.wikipedia.org/wiki/Hamiltonian_mechanics
Наконец, заметка об установившихся и переходных решениях марковских задач. Подавляющее количество практических приложений (например, Page rank) опирается на поиск стационарных решений. Действительно, наличие такой сходимости к устойчивому состоянию было первоначальной мотивацией для А. Маркова для создания его цепей в попытке расширить применение центральной предельной теоремы на зависимые переменные. Переходные эффекты (такие как время удара) марковских процессов значительно менее изучены и более неясны. Однако совершенно справедливо рассмотреть марковское предсказание результатов в конкретный момент в будущем (а не только конвергентное "равновесное" решение).