Итеративное декодирование Витерби

Итеративное декодирование Витерби — это алгоритм , который определяет подпоследовательность S наблюдения O = { o ₁ , ..., on _} , имеющую наибольшую среднюю вероятность (т. е. вероятность, масштабированную по длине S ) быть порожденной заданным скрытым Марковская модель M с m состояниями. Алгоритм использует модифицированный алгоритм Витерби в качестве внутреннего шага.

Масштабированная мера вероятности была впервые предложена Джоном С. Брайдлом . Ранний алгоритм решения этой проблемы, скользящее окно , был предложен Джеем Уилпоном и др., 1989, с постоянной стоимостью T = mn. ² /2.

Более быстрый алгоритм состоит из итерации вызовов алгоритма Витерби , переоценки оценки заполнителя до достижения сходимости.

Алгоритм

Базовая (неоптимизированная) версия поиска последовательности s с наименьшим нормализованным расстоянием от некоторой подпоследовательности t :

// input is placed in observation s[1..n], template t[1..m],
// and [[distance matrix]] d[1..n,1..m]
// remaining elements in matrices are solely for internal computations
(int, int, int) AverageSubmatchDistance(char s[0..(n+1)], char t[0..(m+1)], int d[1..n,0..(m+1)]) {
    // score, subsequence start, subsequence end
    declare int e, B, E
    t'[0] := t'[m+1] := s'[0] := s'[n+1] := 'e'

    e := random()
    do
        e' := e
	for i := 1 to n	do	d'[i,0] := d'[i,m+1] := e
	(e, B, E)  := ViterbiDistance(s', t', d')
        e := e/(E-B+1)
    until (e == e')

    return (e, B, E)
}

Процедура ViterbiDistance() возвращает кортеж ( e , B , E ), т. е. оценку Витерби « e » для соответствия t и выбранных точек входа ( B ) и выхода ( E ) из него. « Б » и « Е » нужно записать, используя простую модификацию Витерби.

Модификация, которую можно применить к таблицам CYK, предложенная Антуаном Розенкнопом, состоит в вычитании e из всех элементов исходной матрицы d .

Ссылки

• Силаги, М., «Выявление подпоследовательностей, соответствующих HMM, с использованием критериев средней вероятности наблюдения с применением к обнаружению ключевых слов», AAAI, 2005.
• Розенкноп, Антуан, и Силаги, Мариус; «Алгоритм решетчатого декодирования средней стоимости для распознавания речи», TALN 2001.

Дальнейшее чтение

• Ли, Хуан-Банг; Коно, Рюдзи (2006). Эффективная структура кода блочно-кодированных модуляций с итеративным алгоритмом декодирования Витерби . 3-й международный симпозиум по системам беспроводной связи. Валенсия, Испания: IEEE. дои : 10.1109/ISWCS.2006.4362391 . ISBN  978-1-4244-0397-4 .
• Ван, Ци; Вэй, Лей; Кеннеди, РА (январь 2002 г.). «Итеративное декодирование Витерби, формирование решетки и многоуровневая структура для высокоскоростного TCM с конкатенацией четности». Транзакции IEEE по коммуникациям . 50 (1): 48–55. дои : 10.1109/26.975743 . ISSN   0090-6778 .