Дискретная оптимизация на цепи Маркова

[mac23]

Здравствуйте. Мой вопрос возник в связи с применением цепей Маркова в компьютерной лингвистике.

Пусть дана однородная цепь Маркова

$$ X_{0}, X_{1}, X_{2}, \ldots $$

c $ N $ состояниями $ S_{1}, \ldots, S_{N}, $ вектором начальных вероятностей $ \pi=(\pi_{1}, \ldots, \pi_{N}), $ где $ \pi_{i}=\mathbb{P}(X_{0}=S_{i}), $ и матрицей вероятностей перехода $ A=(a_{ij}), $ где $ a_{ij}=\mathbb{P}(X_{n}=S_{j} | X_{n-1}=S_{i}), $ $ a_{ij} $ не зависит от $ n. $

Требуется найти несколько (например, $ r=10 $ штук) наиболее вероятных конечных последовательностей событий-состояний цепи (пусть для начала, для простоты, событий-состояний цепи данной фиксированной длины $ m $ и стартующих из начального состояния, пусть даже они будут различными; дальше уже можно обобщать на случай конечных последовательностей переменной длины, начинающихся с некоторого $ k $-го состояния и т.п.). Опишу подробнее, что имеется в виду. Вероятность цепочки событий

$$ \mathbb{P}(X_{0}=S_{i_{0}}, X_{1}=S_{i_{1}}, \ldots, X_{m-1}=S_{i_{m-1}})=\pi_{i_{0}}a_{i_{0}i_{1}}a_{i_{1}i_{2}}\ldots a_{i_{m-2}i_{m-1}}. $$

Пусть состояния в вышеприведённой цепочке $ S_{i_{0}}, S_{i_{1}}, \ldots, S_{i_{m-1}} $ попарно различны (для простоты).
В принципе, можно тупо сосчитать все такие вероятности, отсортировать их по убыванию и выдать в качестве ответа несколько первых таких (скажем, $ r=10 $ штук) конечных последовательностей длины $ m. $ Но это очень "расточительное" решение, это тупой полный перебор. Нельзя ли его оптимизировать?

Мои соображения таковы. Прологарифмируем (по любому основанию большему единицы), тогда произведение превратится в сумму:

$$ \log\mathbb{P}(X_{0}=S_{i_{0}}, X_{1}=S_{i_{1}}, \ldots, X_{m-1}=S_{i_{m-1}})=\log\pi_{i_{0}}+\log a_{i_{0}i_{1}}+\log a_{i_{1}i_{2}}+\ldots+\log a_{i_{m-2}i_{m-1}}. $$

Тогда считая, что в ориентированном графе с петлями рассматриваемой однородной цепи Маркова дуги нагружены этими логарифмами вероятностей, получаем задачу о нахождении "длиннейшего" пути данной длины $ m-1 $ в таком графе, точнее, нескольких "наиболее длинных" путей данной длины $ m-1 $ (в том самом количестве $ r=10 $ штук). Умножая все эти логарифмы на минус единицу, получаем задачу уже о кратчайшем пути данной длины в графе, ну или нескольких кратчайших путей. Выходит, нужно решать задачу о кратчайшем пути заданной длины в ориентированном графе с петлями? Как можно эффективно решать такие задачи?

[пианист]

Брать, например, самый вероятный (-ые) переход на каждом шаге.
Или что Вы имеете в виду?

[arseniiv]

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

А вот если можно, чтобы в этом куске были дырки (не получены какие-нибудь строки, более вероятные, чем другая полученная) — например, просто чтобы составить впечатление — то подход прекрасно подойдёт без изменений.