предисловие
Предыдущая работа по маркировке частей речи, связанная с обработкой естественного языка, Скрытая марковская модель (HMM) обычно используется для реализации маркировки частей речи, а алгоритм реализации декодирования модели HMM обычно использует алгоритм Витерби.
Об исчерпывающем законе
Есть много приложений модели HMM, и вот одно из распространенных приложений, которое заключается в поиске наиболее вероятной последовательности скрытых состояний на основе последовательности наблюдений. Простейшая идея состоит в том, чтобы непосредственно перечислить все возможные последовательности скрытых состояний и вычислить вероятность каждой последовательности объединенных состояний.Последовательность комбинаций с наибольшей вероятностью является наиболее вероятной последовательностью скрытых состояний. Возьмем в качестве примера водоросли и погоду и перечислим вероятности всех возможных последовательностей скрытых состояний следующим образом:
P(сухо, сыро, сыро | солнечно, солнечно, солнечно), P(сухо, сыро, сыро | солнечно, солнечно, облачно), P(сухо, сыро, сыро | солнечно, солнечно, дождливо), . . . . P (сухо, сыро, сыро | дождливо, дождливо, дождливо), последовательность, соответствующая максимальному значению, является наиболее вероятной скрытой последовательностью состояний. Исчерпывающий путь имеет в общей сложности 3 t-х полосы мощности.Можно видеть, что по мере увеличения последовательности и количества состояний объем вычислений очень велик.
Алгоритм Витерби
Вышеупомянутый исчерпывающий метод требует большого объема вычислений.Чтобы уменьшить сложность, вводится алгоритм Витерби.Проблема декодирования, которую должен решить алгоритм Витерби, состоит в оптимальном выборе нескольких шагов и нескольких выборов на каждом шаге. Согласно следующему рисунку вы можете ясно увидеть основную идею Витерби.По мере увеличения времени каждый узел сохраняет подпуть от всех узлов до оптимального значения узла в предыдущий момент времени, как показано красным стрелка на рисунке, текущее время Возможными путями узла являются пути от всех узлов к этому узлу в предыдущий момент, но мы оставляем только один из оптимальных путей. После вычисления всех шагов по очереди оптимальный путь всего процесса окончательно получается путем возврата.
Ниже приведен пример, иллюстрирующий весь процесс. Предположим, что есть 3 состояния, последовательность - это время t, p(a1) представляет значение узла a1, p(b1) представляет значение узла b1, и то же самое справедливо для других узлов. В разное время вероятность перехода между состояниями неизменна, поэтому p(aa) представляет собой вероятность перехода из состояния а в состояние а, будь то из времени 1 во время 2 или из времени 2 во время 3, оно идентично . Точно так же есть p(ab), p(ac), p(ba)... .
Формула расчета значения узла в момент времени t+1:
Среди них x и y принадлежат состояниям a, b и c.
Вычисляем значение p(a) в момент времени t=2, оно может быть от a1 до a2, b1 до a2 или c1 до a2, если вычисленное p(a) пути от a1 до a2 наибольшее, то держи путь. Таким же образом вычислите максимальное значение p(b) и p(c) соответственно и сохраните путь от b1 до b2 и путь от b1 до c2. Затем вычислить p(a), p(b) и p(c) в момент времени t=3 и, наконец, прийти к моменту времени t, вычислить наибольшее значение p(a), p(b) и p(c) в это время, и выберите их узел с наибольшим значением, а затем вернитесь вперед в соответствии с зарезервированным путем в предыдущий момент, чтобы получить оптимальную последовательность. Например, ct — самый большой узел, т. е.
То есть наиболее вероятная последовательность — bcb...cc.
========Время рекламы========
Моя новая книга «Анализ дизайна ядра Tomcat» продана на Jingdong, нуждающиеся друзья могут перейти кitem.JD.com/12185360.Контракт…Зарезервировать. Спасибо друзья.
Зачем писать «Анализ проектирования ядра Tomcat»
=========================
Добро пожаловать, чтобы следовать: