Алгоритм Витерби кратко

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

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

Является алгоритмом динамического программирования. Применяется в алгоритме сверточного декодирования Витерби.

Алгоритм был предложен Эндрю Витерби в 1967 году как алгоритм декодирования сверточного кода, передаваемого по сетям с наличием шума. Алгоритм получил широкое применение в декодировании сверточных кодов мобильных телефонов стандартов GSM и CDMA, dial-up модемах и беспроводных сетях стандарта 802.11. Также он широко используется в распознавании речи, синтезе речи, компьютерной лингвистике и биоинформатике. К примеру, при распознавании речи звуковой сигнал воспринимается как последовательность событий и строка текста есть «скрытый смысл» акустического сигнала. Алгоритм Витерби находит наиболее вероятную строку текста по данному сигналу.

Алгоритм делает несколько предположений:

• наблюдаемые и скрытые события должны быть последовательностью. Последовательность чаще всего упорядочена по времени.
• две последовательности должны быть выровнены: каждое наблюдаемое событие должно соответствовать ровно одному скрытому событию
• вычисление наиболее вероятной скрытой последовательности до момента t должно зависеть только от наблюдаемого события в момент времени t, и наиболее вероятной последовательности до момента t − 1.

Алгоритм

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

Пусть на выходе сети наблюдается последовательность . Тогда наиболее вероятная последовательность состояний сети для наблюдаемой последовательности может быть определена с помощью следующих рекуррентных соотношений

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

Здесь мы используем стандартное определение arg max.
Сложность этого алгоритма равна .

Расширения

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

С помощью алгоритма, называемого итеративным декодированием Витерби, можно найти подпоследовательность наблюдения, которая лучше всего (в среднем) соответствует заданной скрытой марковской модели. Этот алгоритм предложен Qi Wang et al. разобраться с турбокодом . Итеративное декодирование Витерби работает путем итеративного вызова модифицированного алгоритма Витерби, переоценивая оценку для наполнителя до сходимости.

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

Псевдокод

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

Две двумерные таблицы размераК×Т строятся:

• Каждый элемент из хранит вероятность наиболее вероятного пути на данный момент с который генерирует .
• Каждый элемент изТ2 магазины из наиболее вероятного пути на данный момент

Записи таблицы заполняются в порядке возрастания :

,

,

и как определено ниже. Об этом говорит сайт https://intellect.icu . Обратите внимание, что не обязательно должно появляться в последнем выражении, так как оно неотрицательно и не зависит от и, таким образом, не влияет на argmax.

Вход

• Пространство наблюдения ,
• государственное пространство ,
• массив начальных вероятностей такой, что хранит вероятность того, что ,
• последовательность наблюдений такой, что если наблюдение во времени является ,
• матрица перехода A размера К×К такой, что хранит вероятность перехода из состояния констатировать ,
• матрица выбросов B размера К×N такой, что хранит вероятность наблюдения из штата .

Выход

• Наиболее вероятная последовательность скрытых состояний

Переформулировано в кратком близком к Python :

Объяснение

Предположим, нам дана скрытая марковская модель (HMM) с пространством состояний , начальные вероятности находиться в скрытом состояниияи вероятности перехода перехода из состояния констатировать . Скажем, мы наблюдаем выходы . Наиболее вероятная последовательность состоянийИкс1,…,ИксТкоторая производит наблюдения, задается рекуррентными соотношениями

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

Здесь мы используем стандартное определение arg max .

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

Пример

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

Врач считает, что состояние здоровья пациентов работает как дискретная цепь Маркова . Есть два состояния: «Здоров» и «Лихорадка», но врач не может наблюдать их непосредственно; они скрыты от врача. Каждый день есть определенный шанс, что пациент скажет врачу «Я чувствую себя нормально», «Мне холодно» или «У меня кружится голова», в зависимости от состояния здоровья пациента.

Наблюдения (нормальное, холодное , головокружение) вместе со скрытым состоянием (здоров, лихорадка) образуют скрытую марковскую модель (HMM) и могут быть представлены следующим образом на языке программирования Python :

obs = ("normal", "cold", "dizzy")
states = ("Healthy", "Fever")
start_p = {"Healthy": 0.6, "Fever": 0.4}
trans_p = {
    "Healthy": {"Healthy": 0.7, "Fever": 0.3},
    "Fever": {"Healthy": 0.4, "Fever": 0.6},
}
emit_p = {
    "Healthy": {"normal": 0.5, "cold": 0.4, "dizzy": 0.1},
    "Fever": {"normal": 0.1, "cold": 0.3, "dizzy": 0.6},
}

В этом фрагменте кода start_pпредставляет мнение врача о том, в каком состоянии находится НММ при первом посещении пациента (все, что знает врач, это то, что пациент, как правило, здоров). Используемое здесь конкретное распределение вероятностей не является равновесным, которое (с учетом переходных вероятностей) приблизительно равно {'Healthy': 0.57, 'Fever': 0.43}. Представляет собой transition_pизменение состояния здоровья в основной цепи Маркова. В этом примере у пациента, который здоров сегодня, есть только 30%-ная вероятность того, что завтра у него будет жар. Представляет emit_p, насколько вероятно каждое возможное наблюдение (нормальное, простуда или головокружение) с учетом основного состояния (здорового или лихорадочного). Здоровый пациент имеет 50% шанс чувствовать себя нормально; у того, у кого есть лихорадка, есть 60%-ая вероятность чувствовать головокружение.

Графическое представление данного HMM

Пациент посещает его три дня подряд, и врач обнаруживает, что в первый день пациент чувствует себя нормально, на второй — холодно, а на третий — кружится голова. У врача возникает вопрос: какова наиболее вероятная последовательность состояний здоровья больного, которая могла бы объяснить эти наблюдения? На это отвечает алгоритм Витерби.

Функция viterbiпринимает следующие аргументы: obsпоследовательность наблюдений, например ['normal', 'cold', 'dizzy']; statesмножество скрытых состояний; start_pвероятность старта; trans_p– переходные вероятности; и emit_p– вероятности эмиссии. Для простоты кода мы предполагаем, что последовательность наблюдений obsнепуста и trans_p[i] [j]определена emit_p[i] [j]для всех состояний i,j.

В рабочем примере алгоритм прямого/Витерби используется следующим образом:

viterbi(obs,
        states,
        start_p,
        trans_p,
        emit_p)

Вывод скрипта

$ python  viterbi_example.py
          0 1 2 
Здоров: 0,30000 0,08400 0,00588 
Лихорадка: 0,04000 0,02700 0,01512 
Шаги состояний: Здорово Здорово Лихорадка с наибольшей вероятностью 0,01512

Это показывает, что наблюдения, ['normal', 'cold', 'dizzy']скорее всего, были созданы государствами ['Healthy', 'Healthy', 'Fever']. Другими словами, учитывая наблюдаемую активность, пациент, скорее всего, был здоров в первый день, а также во второй день (несмотря на то, что в этот день чувствовал холод), и только на третий день заболел лихорадкой.

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

Вау!! 😲 Ты еще не читал? Это зря!

• алгоритм свёрточного декодирования витерби ,
• EM-алгоритм
• Скрытая марковская модель
• Алгоритм ожидания-максимизации
• Алгоритм Баума – Велча
• Алгоритм «вперед-назад»
• Форвардный алгоритм
• Код исправления ошибок
• Скрытая марковская модель
• Маркировка частями речи
• Алгоритм поиска A*

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