Марковские модели

Марковское свойство

Здравствуйте и вновь добро пожаловать на занятия по теме «Машинное обучение без учителя: скрытые марковские модели на языке Python».

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

Эта лекция посвящена марковскому свойству – свойству, которое и делает модели марковскими.

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

Как видим, такого рода модели имеют широкое распространение в многих сферах. К примеру, в обработке естественных языков мы можем создать автоматическую систему письма путём создания вероятностных моделей. Например, если мы начнём последовательность «Макбук придумал…», то следующим словом может быть Apple, или Стив Джобс, или ещё что-то в этом роде.

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

Итак, что же такое марковское свойство. Марковское свойство – это когда завтрашняя погода зависит только от погоды сегодняшней, но никак не вчерашней. Это когда следующее слово в предложении зависит исключительно от предыдущего слова, но никакого другого. Когда завтрашние котировки акций зависят только от сегодняшних котировок, но никак не вчерашних или любого другого прошедшего дня.

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

Обобщая, можно сказать, что погода, биржевые котировки или слово могут рассматриваться как состояние; при этом марковское предположение состоит в том, что текущее состояние зависит только от предыдущего состояния, или что следующее состояние зависит только от текущего состояния. Другими словами, распределение состояния в момент t зависит только от состояния в момент t-1:

p(s(t)|s(t-1), s(t-2), ..., s(0)) = p (s(t)|s(t-1)).

Это противоречит более общему утверждению, когда постулируется, что распределение состояния в момент t зависит от всех предыдущих состояний.

Тогда зачем оно нам нужно? Суть в том, чтобы смоделировать совместную вероятность или, другими словами, вероятность всей данной последовательности. Так, используя цепное правило вычисления вероятностей

p(s4,s3,s2,s1) = p(s4|s3,s2,s1)p(s3,s2,s1) = p(s4|s3,s2,s1)p(s3|s2,s1)p(s2,s1) = p(s4|s3,s2,s1)p(s3|s2,s1)p(s2|s1)p(s1) = p(s4|s3) p(s3|s2)p(s2|s1)p(s1) -  если принять марковское свойство.

Как можно убедиться, получается очень большое выражение, если его полностью раскрыть, но которое становится куда проще, если использовать марковское свойство. Подумайте, как часто имеет место последовательность s1, s2, s3? А даже если встречается часто – как точно измерить вероятность s4 при данных s3, s2, s1? Чуть далее мы рассмотрим конкретный пример.

Обратите внимание, что если бы мы приняли более общее утверждение, когда состояние в момент t зависит от всех предыдущих состояний, то было бы крайне трудно измерить все эти распределения вероятностей. Представим, например, статью из Википедии, в которой мы пытаемся предсказать следующее слово. Предположим, в ней 1000 слов. Получается, мы должны получить распределение 1000-го слова при заданных последних 999 словах. Можно также с уверенностью предположить, что это единственная статья в Википедии с именно такой последовательностью из 999 слов. Тогда наша мера вероятности будет равна 1 из 1 – то есть это единичное измерение. Разумеется, хорошей языковой моделью это назвать сложно.

И наоборот, предположим, мы начинаем с начала статьи, и у нас есть только одно предыдущее слово. Скажем, это слово «О». Тогда у нас есть бесчисленное количество возможных последующих слов, ибо речь может идти о чём угодно.

Таким образом, мы можем захотеть сделать обучение на последовательностях из трёх или четырёх слов, когда наше текущее слово будет зависеть от двух или трёх предыдущих. Обобщая эту идею, если наше текущее состояние зависит от предыдущих двух состояний, то это называется марковской моделью второго порядка, если зависит от трёх предыдущих состояний – то марковской моделью третьего порядка.

В данном случае мы сосредоточимся исключительно на марковских моделях первого порядка.

Марковские модели

Итак, вернёмся к нашему примеру с погодой. Предположим, мы хотим смоделировать три состояния – дождливо, облачно и солнечно.

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

Это значит, что у нас есть три весовых коэффициента для каждого из трёх состояний. А сколько будет всего весовых коэффициентов для M состояний? У нас всегда будет M2 весовых коэффициентов. Как правило, они записываются в матрицу размерностью MxM и обозначаемую A. Она называется матрицей переходов состояний, или, проще, вероятностями переходов. Каждый элемент A(i, j) в матрице A представляет собой вероятность перехода в состояние j из состояния i.

Это накладывает определённые ограничения. Поскольку всякий раз, находясь в состоянии i, мы обязательно должны перейти в одно из трёх состояний, то сумма значений в i-м ряду должна быть равна 1, где i пробегает значения от 1 до M.

Ещё одно важное понятие в марковских моделях – стартовая точка. Пусть, к примеру, мы стараемся смоделировать первое слово предложения «За какую сумму вы покупаете дом?». Это то, что называется начальным распределением состояний. Оно характеризуется вектором размерности M и обозначается π. Как правило, его представляют в виде вектора-строки размерностью 1xM. Разумеется, сумма всех значений должна быть равна 1, поскольку это вероятности, что мы начинаем с каждого из M состояний.

Вооружившись этими понятиями, мы можем начать использовать модель. Мы можем ставить вопросы вроде «Какова вероятность последовательности (солнечно, солнечно, дождливо, облачно)?» Данная вероятность равна

p(солнечно,солнечно, дождливо, облачно) = p(солнечно) * p(солнечно|солнечно)*p(солнечно|дождливо)*p(облачно|дождливо).

В общем случае вероятность любой последовательности может быть рассчитана следующим образом:

p(s(0), \;...\;, s(T)) = \pi (s(0)) \;* \prod_{t=1 ... T} p(s(t)|s(t-1)).

При этом мы можем ставить вопросы вроде «Какая последовательность более вероятна в данной модели?» Имея две последовательности, мы можем рассчитать, какая из них вероятнее.

Тут у вас может возникнуть вопрос: а как обучать марковскую модель? Это очень просто, если использовать максимум правдоподобия. К примеру, предположим, что в качестве обучающих данных у нас есть три предложения: «Я люблю собак», «Я люблю котов» и «Я обожаю кенгуру». Мы можем рассматривать каждое состояние как слово. Таким образом, у нас есть 6 состояний: «я», «люблю», «обожаю», «собак», «котов», «кенгуру». Каждому из них мы можем присвоить индексы в векторе, так чтобы они принимали значения от 0 до 5 включительно. Используя максимум правдоподобия, получим, что наше начальное распределение состояний имеет 100-процентную вероятность начаться со слова «я», поскольку нет предложений, которые бы начинались с какого-либо другого слова. Таким образом, π = [1,0,0,0,0,0], или, другими словами, π(я) = 1.

Далее, если текущее слово – «я», то существует два возможных следующих слова – «люблю» и «обожаю». Следовательно, p(люблю|я) = 2/3, p(обожаю|я) = 1/3.

И наконец, p(собак|люблю) = p(котов|люблю) = 1/2, а p(кенгуру|обожаю) = 1. Все же другие вероятности перехода состояний равны нулю.

Но нужно отдавать себе отчёт в том, что, например, в английском языке более миллиона слов, так что словарь получится огромным. Даже имея большое количество данных, вряд ли нам удастся охватить все возможные предложения. В связи с этим иногда вместо максимума правдоподобия используются сглаженные оценки. Для этого к числителю просто добавляется малое число ε, а к знаменателю добавляется произведение ε*V, где V – размер словаря:

A(i,j) = \frac{c(i \rightarrow j) + \varepsilon}{c(i)+\varepsilon V}.

Случай, когда ε = 1, называется add-1-сглаживанием.

А в качестве упражнения попытайтесь доказать, что сумма по строкам по-прежнему будет равна 1.

Математика марковских цепей

Марковские цепи, в действительности являются всего лишь марковскими моделями. При этом, как правило, в случае марковских цепей обсуждаются стохастические процессы с дискретным временем. Судя по названию, можно понять, что тут больше математики, но лежащая в основе модель – это, конечно же, марковская модель.

Зададимся вопросом: какова вероятность пяти солнечных дней подряд, начиная с сегодняшнего? Мы можем рассчитать её, пользуясь правилами теории вероятностей. Сначала рассмотрим вероятность того, что завтра будет солнечно, то есть вероятность p(солнечно) в момент t = 1. Она равна совместной вероятности солнечной погоды в момент t = 1 и всех других состояний в момент t = 0, отбрасывая все другие состояния:

Использовав теорему Байеса, мы получим условные вероятности и начальное распределение состояний, то есть матрицу переходов A и π, определяющих марковскую модель. В общем случае мы умножаем π на матрицу A и получаем новый вектор-строку с новым распределением состояний в момент t = 1. Далее умножаем ещё раз на A, получая распределение состояний в момент t = 2 и так далее, пока не дойдём до момента t = 5:

p(s(1))=\pi A,

p(s(2))=\pi AA,

Таким образом, распределение состояний в момент t равно

p(s(t))=\pi A^{t}.

Предположим теперь, что мы начали с распределения состояний p(s), умножили его на A и получили первоначальное распределение p(s). В таком случае мы получили так называемое стационарное распределение, поскольку независимо от того, сколько раз мы осуществляем переход, мы всё равно получаем исходное распределение состояний.

Как же найти стационарное распределение? Вы можете заметить, что это задача похожа на нахождение собственных значений, в частности, когда собственное значение равно 1. Но не забывайте, что собственные векторы не уникальны, так что после нахождения собственного вектора, для которого собственное значение равно 1, необходимо нормализовать его, так что их сумма равнялась 1. Имейте также в виду, что это не обычная задача нахождения собственных значений, к которой мы привыкли, поскольку вектор π является вектором-строкой. Так его обозначают в учебниках и руководствах, так что в действительности это лишь условность. Но она значит, что на самом деле мы должны решить задачу нахождения собственных значений для транспонированной матрицы A, но не для самой A.

Возникает ещё один вопрос: в каком состоянии мы ожидаем оказаться в конце концов? Этот вопрос можно рассматривать как вопрос финального распределения состояний или распределения состояний в момент  По сути, он решается перемножением π на A бесконечное количество раз:

\pi_{\infty} = \pi A^{\infty}.

Переформулировав, вопрос можно поставить так: независимо от того, сколько раз мы делаем переход после некоторой данной точки, мы всё равно ожидаем получить то же самое распределение состояний. Это называется равновесным, или предельным, распределением, поскольку такого распределения состояний можно достичь лишь по истечении очень долгого времени. Такое распределение состояний можно умножить на ещё одно A, и это даст нам прежнее распределение состояний.

Это кажется очень похожим на предыдущую задачу, но это не совсем так. По определению, взяв равновесное распределение и умножив на A, мы получим то же распределение –значит, это стационарное распределение. Следовательно, все равновесные распределения являются стационарными.

Но верно ли обратное утверждение? Нет, не верно. Поэтому, отыскав стационарное распределение, как можно доказать, что оно является также и равновесным, или предельным? Этот вопрос выходит за рамки данного курса, но если вам интересно, рекомендую обратиться к материалам по стохастическим процессам. Мы ещё будем обращаться к этой теме при обсуждении ранжирования страниц, но не будем углубляться в то, как это работает. Данная тема может также помочь в ответе на вопрос, в каких случаях марковская цепь вообще имеет равновесное распределение и как первоначальное состояние влияет на конечное распределение. Но нас в этом курсе больше интересуют практические задачи, нежели сугубо математические вопросы, и математика нам нужна лишь для понимания или помощи в том или ином деле.

Итак, о чём же нам говорит равновесное распределение?

Предположим, вероятности того, что будет солнечно, дождливо и облачно равны соответственно 5/10, 1/10 и 4/10. Это значит, что в целом, если мы возьмём, скажем, 1000 дней, то ожидается, что 500 из этих дней будут солнечными, 100 дней будет идти дождь, а ещё 400 дней будет облачно. Это позволяет нам со временем собрать статистику, несмотря на то что это случайный и меняющийся со временем процесс.

Но это неприменимо, например, к ценам на акции. Собранные, скажем, среднегодовые цены на акции Apple в течение 20 лет будут полностью отличаться от среднегодовой цены акций Apple в год, когда вышел 6-й айфон.

Андрей Никитенко
Андрей Никитенко
Задать вопрос эксперту
Понравилась статья? Поделить с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!:

Share via
Copy link