Поиск наиболее вероятной последовательности
Предположим, что [ true, true, false, true, true] — последовательность истинностных значений с результатами наблюдений за появлением директора с зонтиком, которые проводил охранник в течение первых пяти дней своей работы. Какая последовательность состояний погоды может стать наиболее вероятным объяснением для этих данных? Означает ли отсутствие зонтика в день 3, что не было дождя или директор забыл его взять? А если в день 3 не было дождя, то, возможно, дождь не шел и в день 4 (поскольку погода обычно является устойчивой), однако директор захватил с собой зонтик просто на всякий случай. В целом существуют 25 возможных последовательностей состояний погоды, которые могут быть приняты в качестве объяснения. Но есть ли способ найти наиболее вероятную из этих последовательностей, не перебирая их все?
Один из подходов, который может быть опробован, состоит в использовании следующей процедуры с линейными затратами времени: с помощью алгоритма сглаживания найти распределения апостериорных вероятностей погоды на каждом временном интервале; после этого составить последовательность, используя на каждом этапе наиболее вероятное состояние погоды, соответствующее этим апостериорным вероятностям. Но такой подход должен вызвать у читателя сомнения, поскольку апостериорные вероятности, вычисленные с помощью сглаживания, представляют собой распределения вероятностей для отдельных временнь/х интервалов, тогда как, чтобы найти наиболее вероятную последовательность, необходимо рассматривать совместные вероятности по всем временнь/м интервалам. Соответствующие результаты фактически могут оказаться довольно различными (см. упр. 15.4).
Тем не менее алгоритм поиска наиболее вероятной последовательности с линейными затратами времени существует, но чтобы его найти, необходимо продумать все обстоятельства немного более тщательно. Алгоритм должен быть основан на том же свойстве марковости (неизменности порядка марковской цепи), которое позволило создать эффективные алгоритмы фильтрации и сглаживания. Проще всего можно подойти к решению этой задачи, рассматривая каждую последовательность как путь в графе, узлами которого являются возможные состояния на каждом временном интервале. Такой граф показан для мира задачи с зонтиком на рис. 15.4, а. Теперь рассмотрим задачу поиска наиболее вероятного пути через этот граф, где значение правдоподобия любого пути представляет собой произведение вероятностей перехода вдоль этого пути и вероятностей конкретных наблюдений в каждом состоянии. В частности, сосредоточимся на тех путях, которые достигают состояния Rain5= true. Ввиду наличия свойства марковости можно прийти к заключению, что наиболее вероятный путь к состоянию Rain5=true состоит из наиболее вероятного пути к некоторому состоянию, достигнутому во время 4, за которым следует переход в состояние Rain5= true, а состоянием во время 4, которое станет частью пути к состоянию Rain5=true, является именно то состояние, которое максимизирует значение правдоподобия этого пути. Иными словами, существует рекурсивная связь между наиболее вероятными путями в каждое состояние xt+1 и наиболее вероятными путями в каждое состояние xt. Эту связь можно записать в виде уравнения, соединяющего вероятности путей, следующим образом:
max P(xi,...,xt,Xt+i I ei:t+i ) Xi ...xt
= a P(et+i I Xt+i) max P(Xt+i | xt) max P(xi,...,xt-i,xt | ei:t)
xt ' Xi...Xt-l
(15.9)
Уравнение 15.9 идентично уравнению фильтрации 15.3, за исключением описанных ниже отличий.
1. Прямое сообщение f1:t = p(Xt|e1:t) заменяется следующим сообщением,
т.е. вероятностями наиболее правдоподобного пути в каждое состояние xt:
mi:t = max Р (xi,..., xt-i, Xt | ei:t)
Xi...Xt_i
2. Суммирование по переменным xt в уравнении 15.3 заменяется максимизаци-
ей по переменным xt в уравнении 15.9.
Таким образом, алгоритм вычисления наиболее вероятной последовательности аналогичен алгоритму фильтрации: он проходит в прямом направлении вдоль последовательности, вычисляя сообщение m на каждом временном интервале с помощью уравнения 15.9. Ход этих вычислений показан на рис. 15.4, б. В конечном итоге этот алгоритм позволяет получить вероятность наиболее правдоподобной последовательности, достигающей каждого из заключительных состояний. Поэтому с его помощью можно легко выбрать последовательность, которая является наиболее правдоподобной среди всех прочих (соответствующие ей состояния обозначены на рисунке жирными контурами). Для того чтобы иметь возможность определить фактически наблюдаемую последовательность, а не просто вычислить ее вероятность, в этом алгоритме необходимо также сопровождать указатели от каждого состояния обратно к наилучшему состоянию, приведшему к нему (эти указатели показаны на рисунке жирными стрелками); соответствующую последовательность можно найти, проследовав по указателям в обратном направлении от наилучшего заключительного состояния.
Только что описанный алгоритм называется алгоритмом Витерби в честь его разработчика. Временная сложность этого алгоритма, как и алгоритма фильтрации, линейно зависит от t, от длины последовательности. Но в отличие от алгоритма фильтрации его потребность в пространстве также линейно зависит от t. Это связано с тем, что в алгоритме Витерби необходимо следить за указателями, которые обозначают наилучшую последовательность, ведущую к каждому состоянию.