Шаг первый к пониманию MDP: марковский процесс

С возвращением в мой блог об искусственном интеллекте! В моем последнем посте я дал краткое введение в обучение с подкреплением. Сегодня я помогу вам продолжить ваше путешествие, представив Марковский процесс, который нам нужно будет понять, прежде чем обсуждать Марковский процесс принятия решений (MDP), используемый в обучении с подкреплением.

К концу вы получите базовые знания о:

  • Что такое свойство Маркова и цепь Маркова;
  • Как работает свойство Маркова;
  • Как цепь Маркова приводит в действие свойство Маркова.

Знакомство с марковским процессом

Чтобы начать обсуждение, давайте сначала выложим некоторые ключевые термины с их определениями из Википедии. Потом копнем немного глубже.

Марковское свойство: В теории вероятностей и статистике термин марковское свойство относится к свойству без памяти стохастического - или случайно определенного - процесса.

Цепь Маркова: Цепь Маркова - это стохастическая модель, описывающая последовательность возможных событий, в которой вероятность каждого события зависит только от состояния, достигнутого в предыдущем событии.

Расширение марковского свойства

Чтобы углубить наше понимание свойства Маркова, мы можем рассматривать его следующим образом:

P(X(t+1)=j|X(0)=i0,X(1)=i1,…,X(t)=i)=P(X(t+1)=j|X(t)=i)

Проще говоря, формула представляет ситуацию, в которой состояние X в момент t + 1 зависит только от одного предыдущего состояния X в время t и не зависит от прошлых состояний X (t − 1),…, X (1).

Теперь давайте проясним это на простом примере.

В строке easy, согласно свойству Маркова, мы имеем:

  • P (x3 = y | x0 = e, x1 = a, x2 = s) представляет собой вероятность того, что y появляется в момент времени 3, когда e появляется в момент времени 0, a появляется в момент 1, а s появляется во время 2
  • P (x3 = y | x2 = s) представляет вероятность того, что y появляется в момент 3, когда s появляется во время 2

Итак, в приведенном выше уравнении свойство Маркова упрощает вычисление P (easy) с предположением, что y зависит только от предыдущего соседнего состояния s и не зависит от e и a. Это означает, что при генерации y в «easy» нас заботит только вероятность перехода от s на y вместо вероятности перехода от eas к y.

Конечно, мы знаем, что в реальном мире это может не работать так, но, тем не менее, гипотеза полезна. Он помогает нам делать сложные ситуации вычислимыми и в большинстве случаев работает достаточно хорошо.

Понимание цепи Маркова

Когда мы используем свойство Маркова в случайном процессе, мы называем его цепью Маркова.

Вот сформулированное определение цепи Маркова:

Используя рисунок 1 выше, мы можем продемонстрировать, как цепь Маркова может генерировать слова.

Предположим, мы начинаем отдельно от состояний e, a и t, с соответствующей вероятностью 40%, 30% и 30%. Согласно свойству Маркова, строка может быть сгенерирована буква за буквой, принимая во внимание только букву непосредственно перед ней.

Например, у нас есть 40% -ная вероятность начать с e в момент времени 0. Затем мы переходим из состояния e в состояние a во время 1. чтобы получить ea. Чтобы прийти к слову есть, мы переходим непосредственно из состояния a в состояние t во время 2, без учета более раннего состояния е.

С помощью приведенных выше вычислений мы видим, что эта цепь Маркова дает eat и tea одинаково высокий балл, а aet - самый низкий балл. Формула показывает, что есть и чай больше похожи на слова, а aet вовсе не одно и то же.

Резюме

Из этого краткого введения Маркова мы узнали:

  • Как определяются свойство Маркова и цепь.
  • Как свойство Маркова может вычислить вероятность слова.
  • Как цепь Маркова может генерировать слова.

Теперь мы готовы к обсуждению Марковского процесса принятия решений. На следующей неделе; не пропустите!