Лучшие k лучших путей в HMM с k > количеством скрытых состояний
Я реализовал алгоритм k-best Viterbi для извлечения k-best путей через HMM, как описано здесь. Тем не менее, я получаю ошибку, если k больше, чем количество скрытых состояний.
Рассмотрим следующее: при первом наблюдении в момент времени t каждое k для каждого состояния j одинаково (т. Е. Все пути к этому состоянию одинаковы, поскольку это первое наблюдение). Затем я хочу вычислить k-лучших путей для состояния i в момент времени t + 1. Для этого я извлекаю k лучших путей предшественника в момент времени t. Однако, поскольку все пути для каждого состояния в момент времени t одинаковы, я получаю одно и то же лучшее состояние предшественника k раз для моего состояния i (то же самое относится ко всем состояниям в момент времени t + 1). Это эффективно приводит к тому, что все пути будут одним и тем же (1-й лучший).
Как предлагается в литературе, я игнорировал пути, которые уже были взяты при поиске k-лучших состояний предшественника. Однако это фактически оставляет меня с N различными путями в момент времени t, где N относится к числу скрытых состояний. Таким образом, выбор k больше N приводит к ошибке при поиске k лучших путей предшественника в момент времени t.
Я надеюсь, что смысл, который я пытаюсь донести, дошел до конца. Очевидно, я что-то здесь упускаю, но я не могу понять, что.