[Народный анализ] Использование запаса воды в качестве примера для изучения скрытой марковской модели

0x00 сводка

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

0x01 Описание

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

В процессе объяснения и изложения я ставлю перед собой требования: найти пример в жизни или в известной книге, а затем объяснить его своими словами.

0x02 карта вероятностей

Вероятностная графическая модель - это теория, которая использует графики для представления зависимости переменных от вероятности.Сочетая знания теории вероятностей и теории графов, графики используются для представления совместного распределения вероятностей переменных, связанных с моделью. Разработано лауреатом премии Тьюринга Перлом.

Если есть одно слово для описания вероятностной графической модели, то это «элегантная». Для решения практической задачи мы хотим иметь возможность извлекать знания, неявно содержащиеся в данных. Вероятностная графическая модель строит такой граф, используя узлы наблюдения для представления наблюдаемых данных, скрытые узлы для представления потенциальных знаний и ребра для описания взаимосвязи между знаниями и данными.Наконец, на основе такого графика зависимости получается распределение вероятностей, что очень "элегантно" решает проблему.

Узлы в графе вероятностей делятся на скрытые узлы и узлы наблюдения, а ребра делятся на направленные ребра и неориентированные ребра. С точки зрения теории вероятностей узлы соответствуют случайным величинам, а ребра соответствуют зависимостям или корреляциям случайных величин, гдеНаправленные ребра представляют собой односторонние зависимости, а ненаправленные ребра представляют взаимные зависимости..

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

0x03 Разница между генеративными моделями и дискриминационными моделями

Теперь мы знаем, что графы вероятности можно разделить на модели ориентированного графа и модели неориентированного графа, как следует из названия, независимо от того, имеют ли ребра в графе направления. Итак, какая модель имеет направленные ребра, а какая не имеет направления? Это легко представить.Направленное выражение представляет собой дедуктивное отношение, то есть В появляется в предпосылке А. Эту модель также называют порождающей моделью. И нет указания на то, чтобы выразить отношение «это правильно», то есть правильно, что A и B существуют одновременно. Эта модель также называется дискриминантной моделью.

В зависимости от того, моделируете ли вы совместное распределение вероятностей P(x,y) или условное распределение вероятностей P(y|x). Выведены генеративные и дискриминационные модели.

1. Генеративные модели

В генеративной модели обычно используется совместный расчет вероятности (поскольку мы знаем посылку А, мы можем рассчитать совместную вероятность), то есть путем вычисления совместного распределения вероятности P(x, y) для значения наблюдения и помеченных данных для достичь цели суждения и оценки y.

Генеративная модель - это процесс имитации генерации данных.Существует причинно-следственная связь между двумя типами случайных величин.За фактором x следует результат y.Эта причинно-следственная связь моделируется совместным распределением:

P(x,y) = P(x)P(y|x)

Генеративные модели на самом деле косвенно моделируют P(x), совместно распределяя P(x,y):

P(x) = \sum_y P(x,y)

Следует отметить, что во время обучения модели я изучил совместную модель P(X,Y) X и Y, то естьЯ был прав только на этапе обучения P(X,Y)моделирование, мне нужно определить все информативные параметры, поддерживающие это совместное распределение вероятностей, для моделирования каждой метки (y). Таким образом, нет никаких дискриминационных границ.

После вывода вычислить P(Y|X) для новой выборки, вывести Y и, наконец, выбрать в качестве результата метку с оптимальной вероятностью, но это уже не на этапе моделирования.

Здесь есть два недостатка:

P(x) трудно точно оценить, потому что признаки не независимы друг от друга, а имеют сложные зависимости.
P(x) также не играет прямой роли в классификации.

Чтобы преодолеть эти две проблемы, появляются дискриминационные модели.

2. Дискриминантная модель

Дискриминантные модели обычно вычисляются с условными вероятностями (поскольку мы не знаем предпосылок, мы можем только «предполагать» вероятность B при A). То есть y предсказывается путем решения условного распределения вероятностей P(y|x) или прямого вычисления значения y.

Дискриминационная модель напрямую пропускает P(x) и напрямую моделирует условную вероятность P(y|x), то есть моделирует Y непосредственно на основе X признаков. Независимо от того, насколько сложна связь в x, она не влияет на оценку y дискриминантной моделью, поэтому ее можноС уверенностью пользуйтесь широким спектром полезных и актуальных функций.

В частности, мой процесс обучения состоит в том, чтобы определить параметры в «отношении комплексного отображения» в модели компонента P (Y | X), построить только одну модель для всех выборок и подтвердить общую дискриминантную границу. После этого переходим к выводу для новой партии образцов. Наиболее вероятная метка прогнозируется при наблюдении входных признаков.

3. Представитель

К представителям генеративных моделей относятся: n-граммная модель, скрытая марковская модель, наивная байесовская модель и др.

К дискриминационным моделям относятся: модель максимальной энтропии, машина опорных векторов, условное случайное поле, модель персептрона и др.

Разница между ними в следующем:

Генеративные модели имеют дело с совместными вероятностями P(Y, X) = P(Y|X) * P(X) = P(X|Y)*P(Y)
Дискриминантная модель вычисляет условную вероятность P(Y|X) = P(X|Y) / P(X)

Дискриминационная модель работает следующим образом: они напрямую изучают Y (или метку) данных в соответствии с предоставленными признаками и, наконец, проводят очевидную или очевидную границу (как это сделать? Через сложное отображение функций, или суперпозицию решений и т. д.). механизм), этот линейный LR, линейный SVM должен быть очевиден.

Генеративная модель работает следующим образом: сначала они понимают распределение всех данных из данных обучающей выборки, а затем, наконец, определяют распределение как распределение всех моих входных данных, и это совместное распределение P (X, Y) ( обратите внимание, что X содержит все функции x_i, а Y содержит все метки). Затем я пришел к данным новой выборки (вывод), ну, через совместное распределение P(X,Y) изученной модели, в сочетании с X, данным новой выборкой, я могу получить Y через условную вероятность
$P(категория|функция) = \frac {P(функция|категория)P(категория)}{P(функция)}$

0x04 Концепция серии Маркова

Упоминается, что марковское значение связано с предыдущими значениями n, поэтому это также условная вероятность, которая является генеративной моделью, которая является моделью ориентированного графа.

гипотеза Маркова: Вероятность возникновения каждого события зависит только от предыдущего события.

Цепь Маркова: Цепь Маркова формируется путем объединения нескольких последовательных событий, удовлетворяющих гипотезе Маркова. Узел цепи Маркова — это состояние, а ребро — это вероятность перехода, которая представляет собой направленное выражение перехода состояния шаблона CPD.

Два предположения о цепях Маркова

Однородная гипотеза Маркова: то есть на состояние в момент времени t влияет только состояние в момент времени t-1;
Предположение о независимости наблюдения: то есть наблюдение в любое время зависит только от состояния в это время;

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

Сила марковской модели в том, что она убирает причинно-следственную связь из байесовской модели, что позволяет ей сопоставлять множество одинаковых вещей. Например, все пиксели изображения одинаковы, но каждый пиксель может влиять друг на друга (небо вверху, земля внизу). Все марковские модели широко используются при обработке/понимании изображений.

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

0x05 Скрытая марковская модель

Скрытая марковская модель (HMM) — это статистическая модель, используемая для описания марковского процесса со скрытыми неизвестными параметрами. То есть описать переход рецессивного состояния системы и вероятность выполнения рецессивного состояния. Рецессивное состояние системы относится к некоторым состояниям, которые неудобны (или невидимы) для наблюдения внешним миром. Трудность состоит в том, чтобы определить неявные параметры процесса по наблюдаемым параметрам. Затем эти параметры используются для дальнейшего анализа.

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

Например, HMM — это вероятностная модель, описывающая совместное распределение p(x,y) двух временных рядов.

Последовательность x видна внешнему миру (внешний мир относится к наблюдателю), называемаяпоследовательность наблюдения(obsevation sequence);
Последовательность y невидима для внешнего мира и называетсяпоследовательность состояний(последовательность состояний).

Например, наблюдение x — это слово, а состояние y — часть речи, нам нужно угадать их часть речи по последовательности слов.

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

Скрытая марковская модель называется «скрытой», потому что извне последовательность состояний (например, часть речи) скрыта и невидима, и это искомая зависимая переменная. С этой точки зрения люди также называют состояние y скрытым состоянием, а наблюдение x видимым состоянием.

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

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

1. Три скрытые проблемы Маркова

Проблема расчета вероятности: Имея модель, как эффективно вычислить вероятность получения последовательности наблюдений? Другими словами, как вы оцениваете, насколько хорошо модель соответствует наблюдаемой последовательности?
проблема предсказания: Имея модель и последовательность наблюдений, как мне найти последовательность состояний, которая лучше всего соответствует этой последовательности наблюдений? Другими словами, как вывести скрытое состояние модели из последовательности наблюдений?
проблемы с обучением: Учитывая последовательность наблюдений, как настроить параметры модели, чтобы максимизировать вероятность появления последовательности? Другими словами, как можно обучить модель, чтобы она наилучшим образом описывала наблюдаемые данные?

Первые две задачи — это задачи распознавания образов: 1) Вероятность получения наблюдаемой последовательности состояний по скрытой марковской модели (Оценка), используется для измерения относительной пригодности модели; 2) найти последовательность скрытых состояний, которая максимизирует вероятность того, что эта последовательность создает наблюдаемую последовательность состояний (расшифровка), который используется для вывода о том, что делают скрытые части модели («что именно произошло»). Третья проблема заключается в создании скрытой марковской модели на основе наблюдаемого набора последовательностей состояний (учиться).

Вторая проблема - это ядро скрытой марковской модели. Применение скрытой марковской модели во многих областях будет в основном проблемой (2). Например, когда машинный перевод выполняет перевод с китайского на английский, перевод слов всегда имеет Значений много, и части речи часто играют очень важную роль.На первый взгляд, как последовательность частей речи похожа на упомянутую нами неявную последовательность состояний =()! Таких еще много.....

Три соответствующих решения:

Прямой алгоритм, обратный алгоритм
Алгоритм Витерби
Алгоритм Баума-Уэлча (примерно идентичен алгоритму EM)

Классический пример в Интернете

У Сяо Мина теперь три дня отпуска.Чтобы скоротать время, он может выбирать три дела каждый день.Эти три вещи: прогулка, шоппинг и уборка (соответствует наблюдаемой последовательности), но решения, которые мы принимаем в жизни, как правило, зависят от погоды.Может быть, мы хотим пройтись по магазинам или прогуляться, когда солнечно, может быть, мы не хотим выходить на улицу, когда идет дождь, и мы остаемся дома, чтобы очистить. Погода (солнечная, дождливая) — скрытое состояние.

Затем мы задаем три вопроса, соответствующие трем основным проблемам Маркова:

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

Я тоже знаю эту модель, те же три вещи, хочу угадать, какая погода в эти три дня.

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

2. Скрытые марковские трудности/моделирование

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

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

Мы моделируем эти примеры с помощью скрытой марковской модели (HMM). Эта модель содержит два набора состояний и три набора вероятностей:

Скрытое состояние: (истинное) состояние системы, которое можно описать марковским процессом.
Наблюдаемое состояние: состояние «видимости» во время этого процесса.
вектор пи: содержит вероятность (начальную вероятность) конкретного скрытого состояния (скрытой) модели в момент времени t=1.
Матрица перехода состояний: содержит вероятность перехода одного скрытого состояния в другое скрытое состояние.
Матрица путаницы: содержит вероятность наблюдаемого состояния при заданном скрытом состоянии скрытой марковской модели.

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

0x06 Скрытое марковское приложение в водной кромке

В Водной кромке Лян Чжуншу прорвался через Особняк Дамин.можно адаптировать для простоты объясненияСкрытый случай Маркова (HMM).

Однако он сказал, что Лян Чжуншу сидел пьяный перед офисом.Когда он впервые услышал сообщение, он не слишком запаниковал; Прежде чем я закончил говорить, я увидел Цуюнь наверху, пламя взметнулось в небо, и огонь поймал луну, которая была очень огромной. Когда Лян Чжуншу увидел это, он в спешке сел на лошадь, но когда он уже собирался это увидеть, то увидел двух больших мужчин, толкающих две машины и ставящих их на дорогу. Когда Лян Чжуншу собирался покинуть восточные ворота, два больших Ханькоу сказали: «Ли Ин и Ши Цзинь здесь!» Мужчины и армия были так напуганы, что ушли, и более дюжины были ранены. Ду Цянь и Сун Ван вышли рядом друг с другом, и все четверо объединились, чтобы удерживать восточные ворота. Увидев, что Лян Чжуншу не занимает доминирующего положения, он повел свою свиту и полетел к южным воротам. У Южных ворот есть легенда: «Толстый монах держит в руках железную посох для пения, ходячий с тигровым лицом вооружен двуручным мечом и кричит, чтобы он вошел в город». оставленный позади дивизии, только чтобы увидеть Чжэня и Цзебао, держа в руке стальную вилку, он столкнулся там друг с другом, он очень хотел вернуться в префектуру и не осмелился приблизиться. Однако префект Ван выздоровел, Лю Тан и Ян Сюн, два огненных и водяных жезла, были забиты до смерти на улице. Маркиз Ю арестовал Фаня, и каждый из них сбежал до конца жизни. Лян Чжуншу поспешил обратно к западным воротам Ма Бэнь, только чтобы услышать артиллерийский звук в Храме Бога Города, и небо содрогнулось. Цзоу Юань и Цзоу Ран держали в руках бамбуковые шесты и разожгли огонь под карнизом. На глазах у Нанвази Ван Айху и Ичжанцин убили будущее. Сунь Синь и невестка Гу вытащили спрятанное оружие и помогли там. Перед Медным храмом вошли Чжан Цин и Сунь Эрнян, поднялись на гору Ао и подожгли ее. В это время жители Пекина, Ли Минь, одичали от крыс и волков, и боги плакали. Но он сказал, что Лян Чжуншу бросился к западным воротам, сопровождаемый лошадью Ли Чэна, бросился к городу южных ворот, остановил лошадь, и когда он посмотрел на барабанную башню, он увидел, что город полон войск и лошадей, и знамя гласило: «Генерал Ху Яньчжо». , быть полным энергии, действовать храбро; слева Хань Тао, справа Пэн Вэй, Хуан Синь позади, подгоняя войска и лошадей, убивая будущее как крылья дикого гуся, и вслед за дверью. Лян Чжуншу не мог выбраться из города, и они с Ли Чэном спрятались под северными воротами города.Они увидели, что огонь яркий и количество боевых лошадей неизвестно, но это был Линь Чун с головой леопарда и гарцующим конь с копьем, слева Ма Линь, справа Дэн Фэй, сзади Хуа Жун, призывая людей и лошадей мчаться в будущее. Снова повернувшись к восточным воротам, среди череды факелов Му Хун не был заблокирован Ду Син слева и Чжэн Тяньшоу справа Трехуровневый герой-пехотинец взял на себя инициативу, держа в руке меч Пу. , в результате чего в город вошли более тысячи человек. Лян Чжуншу пробрался к южным воротам и пожертвовал своей жизнью, чтобы идти по дороге. Сбоку подвесного моста были факелы, а черный вихрь Ли Куй, Ли Ли слева и Цао Чжэн справа. Ли Куй слез со всего тела, стиснул зубы и с двумя топорами в руках вылетел из ратуши. Ли Ли и Цао Чжэн прибыли вместе. Ли Чэн взял на себя инициативу, открыл кровавый путь, бросился из города и ушел, защищая Лян Чжуншу. Я увидел звук убийства из левой руки, и среди факелов было бесчисленное количество солдат и лошадей, но это был большой меч Гуань Шэн, который хлопал лошадью красного кролика, танцевал саблю синего дракона и схватил Лян Чжуншу. Ли Чэн поднял мечи и вышел навстречу врагу. Тот Ли Чэн не собирался драться, поэтому повернул лошадь и ушел. Сюань Цзань слева и Хао Сивен справа столкнулись. Сунь Ли был позади, подгоняя войска и сражаясь с ними. В середине боя Сяо Ли Гуанхуа Жун догнал его сзади, взял лук и пустил стрелу, попал в Ли Чэна и упал с лошади. Когда Ли Чэн увидел это, летящая лошадь побежала, и прежде чем он успел дотянуться до половины стрелы, он увидел гонги и барабаны в своей правой руке, и огонь ослеплял. Ли Чэн сражался и шел, и большая часть армии была разбита, охраняя Лян Чжуншу и спеша уйти.

Есть четыре варианта прорыва: четверо ворот на юге, востоке и северо-западе. У каждой двери свой герой Ляншаня. Теперь герои Ляншаня, которых создала пара Лян Чжунвэнь, составляют цепочку имен.

Например, идите к Южным воротам, встретьтесь с Ву Сун, идите к Восточным воротам, встретите Ши Цзинь, идите к Северным воротам, встретите Линь Чуна, идите к западным воротам и встретите Сун Цзяна. Затем вы можете получить следующую серию имен героев: Ву Сун, Ши Цзинь, Линь Чун, Сун Цзян.

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

Далее мы сосредоточимся наЛян ЧжуншуПознакомьтесь со следующими героями, чтобы объяснить:У Сун, Ши Цзинь, Линь Чун, Сун Цзян

1. Матрица перехода состояний

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

Например, после того, как Лян Чжуншу не удалось прорваться через западные ворота, вероятность того, что следующим состоянием будут южные ворота, восточные ворота, северные ворота и западные ворота, равна 1/4. Эта настройка предназначена для простоты объяснения. Но на самом деле мы можем установить вероятность перехода по желанию. Например, мы можем определить такое правило:

* 顺时针如下：东门 ----> 南门 ----> 西门 ----> 北门 ---> 东门 ---> ...  

* 已经到达某门，再次选择此门的概率是1/8，比如 东门 ---> 东门 （不大可能再次原地突围）

* 已经到达某门，如果顺时针或者逆时针选择下一个门的概率是3/8, 比如 东门 ----> 南门 或者 东门 ----> 北门
  
* 已经到达某门，选择 正对门 的概率是1/8, 比如 东门 ----> 西门 （不大可能选择穿过大名府去对面城门突围）

Матрица перехода состояний выглядит следующим образом:

A= \left\{ \begin{matrix} \frac18 & \frac38 & \frac18 & \frac38\\ \frac38 & \frac18 & \frac38 & \frac18\\ \frac18 & \frac38 & \frac18 & \frac38\\ \frac38 & \frac18 & \frac38 & \frac18\\ \end{matrix} \right\}

2. Матрица путаницы

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

Герои Ляншаня, соответствующие четырем вратам, которые на самом деле подытожены Водным пределом, таковы:

 * 水浒传真实总结
   
 * 南门: 武松，鲁智深，呼延灼，韩滔，彭杞，黄信，李逵，李立，曹正，关胜，宣赞，郝思文，孙立，秦明，燕顺、欧鹏，杨志。
 * 东门：李应，史进，穆弘，杜兴，郑天寿
 * 北门：林冲，马麟，邓飞，花荣
 * 西门：梁山好汉大部军马。
   
 * 真实中，北门遇见林冲的概率是1/4， 南门遇见武松的概率是1/17。

Но это детерминированные вероятности, которые не учитывают нашу модель НММ.

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

Вот наша упрощенная версия, просто чтобы дать несколько героев:У Сун, Ши Цзинь, Линь Чун, Сун Цзян.

 * 以下为吴学究派兵时候，每个好汉分配到每个门的概率
   
 * 南门：武松 1/2，史进 1/4，林冲 1/8，宋江 1/8
 * 东门：武松 1/4，史进 1/2，林冲 1/8，宋江 1/8
 * 北门：武松 1/8，史进 1/8，林冲 1/2，宋江 1/4
 * 西门：武松 1/8，史进 1/8，林冲 1/4，宋江 1/2
   
 * 就我们的例子来说，梁中书在北门 遇到武松的概率是1/8,遇见史进的概率是1/8，遇见林冲的概率是1/2，......

Матрица путаницы выглядит следующим образом:

B = \left\{ \begin{matrix} \frac12 & \frac14 & \frac18 & \frac18\\ \frac14 & \frac12 & \frac18 & \frac18\\ \frac18 & \frac18 & \frac12 & \frac14\\ \frac18 & \frac18 & \frac14 & \frac12\\ \end{matrix} \right\}

Каждая вероятность в матрицах перехода состояний и путаницы не зависит от времени, то есть эти матрицы не меняются со временем по мере развития системы. На самом деле это одно из самых нереалистичных предположений марковской модели о реальном мире.

3. пи-вектор (начальная вероятность)

Большая часть армии и лошадей Ляншаня атаковала Ли Чэна у западных ворот.

* 南门: 1/4
* 东门：7/16
* 北门：1/4
* 西门：1/16

Пи-вектор выглядит следующим образом:

pi= \left\{ \begin{matrix} \frac14 \\ \frac7{16} \\ \frac14 \\ \frac1{16} \\ \end{matrix} \right\}

0x07 Три типа проблем, соответствующих Water Margin HMM

1. Процесс вероятности последовательности --- Оценка (Оценка)

Проблема расчета вероятности: Учитывая модель, как эффективно вычислить вероятность создания последовательности наблюдений. То есть вероятность получения наблюдаемой последовательности состояний по скрытой марковской модели (Оценка).

结合我们水浒传的例子，就是已经知道门有几种（隐含状态数量），每种门是什么（转换概率），根据"选门之后看到哪位好汉"的结果（可见状态链），我想知道看到这个结果的概率。

比如连续三次，看到的人分别是：武松，史进，林冲。那么根据模型，计算产生这些行为的概率是多少。

1.1 Метод прямого расчета (полный перебор)

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

1.2 Прямой алгоритм (основная идея динамического программирования)

Мы используем прямой алгоритм для расчета вероятности последовательности наблюдений с учетом скрытой марковской модели (СММ) и, таким образом, выбираем наиболее подходящую скрытую марковскую модель (СММ).

Этот алгоритм принимает идею DP для уменьшения объема вычислений, то есть каждый раз, когда результат вычисления предыдущего момента напрямую ссылается, чтобы избежать повторных вычислений.Соответственно, временная сложность линейно связана с T с той же техникой, что и Витерби.

Учитывая скрытую марковскую модель (HMM), мы рассмотрим рекурсивное вычисление вероятности последовательности наблюдений. Сначала мы определяем частичную вероятность, которая представляет собой вероятность достижения некоторого промежуточного состояния в сетке. Для последнего наблюдаемого состояния его локальные вероятности включают вероятность достижения этих состояний всеми возможными путями. Можно видеть, что суммирование этих окончательных локальных вероятностей эквивалентно суммированию всех возможных вероятностей пути в сетке, и также получается вероятность последовательности наблюдений с учетом скрытой марковской модели (СММ).

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

2. Процесс маркировки последовательностей --- Декодирование

проблема предсказания: Имея модель и последовательность наблюдений, как мне найти последовательность состояний, которая лучше всего соответствует этой последовательности наблюдений? Другими словами, как вывести скрытое состояние модели из последовательности наблюдений? Для конкретной скрытой марковской модели (СММ) и соответствующей последовательности наблюдений мы часто хотим найти наиболее вероятную последовательность скрытых состояний, которая генерирует эту последовательность.

结合我们水浒传的例子就是，知道门有几种（隐含状态数量），每种门是什么（转换概率），根据"选门之后看到哪位好汉"的结果（可见状态链），我想知道每次选中的是哪个门（隐含状态链）。

比如连续三次，看到的人分别是：武松，史进，林冲。那么这三次每次选的是哪个门？

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

2.1 Алгоритм Витерби

Алгоритм Витерби можно использовать для определения (поиска) последовательности известных наблюдений и наиболее вероятной последовательности скрытых состояний в рамках НММ.

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

Pr (последовательность наблюдений|комбинация скрытых состояний)

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

В частности, в приложении алгоритм Витерби вычисляет локальную вероятность для каждой ячейки в сетке и включает обратный указатель для указания наиболее вероятного пути к ячейке. Сначала мы определяем локальную вероятность, которая представляет собой вероятность достижения определенного промежуточного состояния в сетке. Эти локальные вероятности отличаются от локальных вероятностей, вычисленных в прямом алгоритме, потому что они представляют вероятность наиболее вероятного пути к состоянию в момент времени t, а не сумму всех вероятностей пути. Когда весь процесс расчета завершен, сначала найдите наиболее вероятное состояние в момент завершения, а затем вернитесь к моменту времени t=1 через обратный указатель (этот указатель указывает на оптимальное состояние в предыдущий момент, вызвавшее текущее состояние), поэтому возврат. Последовательность состояний на пути является наиболее вероятной скрытой последовательностью состояний.

3. Проблемы с обучением (Обучение)

проблемы с обучением: Учитывая последовательность наблюдений, как настроить параметры модели, чтобы максимизировать вероятность появления последовательности? Другими словами, как можно обучить модель, чтобы она наилучшим образом описывала наблюдаемые данные? То есть скрытая марковская модель генерируется в соответствии с наблюдаемым набором последовательностей состояний (учиться).

结合我们水浒传的例子就是，知道门有几种（隐含状态数量），不知道每种门是什么（转换概率），观测到很多次"选门之后看到哪位好汉"的结果（可见状态链），我想反推出每种门是什么（转换概率）。

比如连续三次，梁中书看到的人分别是：武松，史进，林冲。而其他什么信息都没有。要建立一个模型，找出各种门之间转换概率，当然也有这些门外他遇到好汉的概率分布。

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

Эта и самая сложная проблема, связанная с HMM, оценивает наиболее подходящую скрытую марковскую модель (HMM) по последовательности наблюдений (из известного набора) и набору связанных с ней скрытых состояний, то есть для определения наиболее подходящая (pi, A, B) тройка, описывающая известную последовательность.

3.1 Алгоритмы обучения с учителем — частота/сумма — это вероятность

Сначала алгоритм обучения с учителем означает, что данных достаточно, а затем они размечаются вручную, по сути нужно только считать различные частоты. Например, когда причастие: Можно рассчитать частоту от B до E, можно рассчитать частоту от B до M, и доступна матрица перехода A. Каждое слово является частотой BEMS, а матрица наблюдения B имеет Вероятность того, что первым словом в выборке будет B и S соответственно. Начальная вероятность PI. Тогда проблема решена.На самом деле сегментация слов такова.Хорошо рассчитывать на размеченный вручную набор данных.

3.2 Алгоритм обучения без учителя — алгоритм Баума-Уэлча

В отсутствие меток у вас есть только набор предложений (при условии, что предложения имеют одинаковую длину, все слова T), в это время матрицы A и B не могут быть напрямую (оценочно) измерены.Чтобы узнать эти параметры, вы необходимо использовать алгоритм EM для HMM.Адаптированный вариант задачи обучения параметра - алгоритм Баума-Уэлча.

Алгоритм обучения параметра также называется алгоритмом прямого-обратного направления.. Если рассчитывается вероятность всей последовательности, решается форвард. Если вы хотите вычислить вероятность подпоследовательности всей последовательности, вы должны вычислить их вместе.

0x08 ссылочный код

UMDHMM (набор инструментов скрытой марковской модели):

Программное обеспечение для скрытой марковской модели (HMM): реализация алгоритмов прямого-обратного, Витерби и Баума-Уэлча. Это облегченная версия HMM. Домашняя страница UMDHMM:Woohoo.KanuNGO.com/software/so…

Программа прямого алгоритма (forward.c)

/* 函数参数说明：
　 *phmm：已知的HMM模型；T：观察符号序列长度；
　 *O：观察序列；**alpha：局部概率；*pprob：最终的观察概率
 */
void Forward(HMM *phmm, int T, int *O, double **alpha, double *pprob) {
　　int i, j; 　　/* 状态索引 */
　　int t; 　　 /* 时间索引 */
　　double sum; /*求局部概率时的中间值 */

　　/* 1. 初始化：计算t=1时刻所有状态的局部概率alpha： */
　　for (i = 1; i <= phmm->N; i++)
　　　　alpha[1][i] = phmm->pi[i]* phmm->B[i][O[1]];
　　
　　/* 2. 归纳：递归计算每个时间点，t=2，... ，T时的局部概率 */
　　for (t = 1; t < T; t++) { 　　　　
      for (j = 1; j <= phmm->N; j++) {
　　　　　　sum = 0.0;
　　　　　　for (i = 1; i <= phmm->N; i++)
　　　　　　　　sum += alpha[t][i]* (phmm->A[i][j]);
　　　　　　alpha[t+1][j] = sum*(phmm->B[j][O[t+1]]);
　　　　}
　　}

　　/* 3. 终止：观察序列的概率等于T时刻所有局部概率之和*/
　　*pprob = 0.0;
　　for (i = 1; i <= phmm->N; i++)
　　　　*pprob += alpha[T][i];
}

Программа алгоритма Витерби (viterbi.c)

void Viterbi(HMM *phmm, int T, int *O, double **delta, int **psi,int *q, double *pprob)
{
　　int i, j; /* state indices */
　　int t; /* time index */
　　int maxvalind;
　　double maxval, val;

　　/* 1. Initialization */
　　for (i = 1; i <= phmm->N; i++){
　　　　delta[1][i] = phmm->pi[i] * (phmm->B[i][O[1]]);
　　　　psi[1][i] = 0;
　　}

　　/* 2. Recursion */
　　for (t = 2; t <= T; t++) 　　{ 　　　　
       for (j = 1; j <= phmm->N; j++){
　　　　　　maxval = 0.0;
　　　　　　maxvalind = 1;
　　　　　　for (i = 1; i <= phmm->N; i++)　{
　　　　　　　　val = delta[t-1][i]*(phmm->A[i][j]);
　　　　　　　　if (val > maxval){
　　　　　　　　　　maxval = val;
　　　　　　　　　　maxvalind = i;
　　　　　　　　}
　　　　　　}
　　　　　　delta[t][j] = maxval*(phmm->B[j][O[t]]);
　　　　　　psi[t][j] = maxvalind;
　　　　}
　　}

　　/* 3. Termination */
　　*pprob = 0.0;
　　q[T] = 1;
　　for (i = 1; i <= phmm->N; i++){
　　　　if (delta[T][i] > *pprob){
　　　　　　*pprob = delta[T][i];
　　　　　　q[T] = i;
　　　　}
　　}

　　/* 4. Path (state sequence) backtracking */
　　for (t = T - 1; t >= 1; t--)
　　　　q[t] = psi[t+1][q[t+1]];
}

0xEE Личная информация

★★★★★★Думая о жизни и технологиях★★★★★★

Публичный аккаунт WeChat:мысли Росси

Если вы хотите получать своевременные новости о статьях, написанных отдельными лицами, или хотите видеть технические материалы, рекомендованные отдельными лицами, обратите внимание.