Алгоритм обучения точной скрытой марковской модели

Быстрый поиск находит в http://www.cs.tau.ac.il/~rshamir/algmb/98/scribe/html/lec06/node6.html "В этом случае задача нахождения оптимального набора параметров $\Theta^{ \ast}$, как известно, NP-полный. Алгоритм Баума-Уэлча [2], который является частным случаем метода EM (ожидание и максимизация), может быть использован для эвристического нахождения решения задачи". Поэтому Я предполагаю, что вариант EM, который гарантированно найдет глобальный оптимум за полиномиальное время, докажет, что P = NP, и он неизвестен и на самом деле, вероятно, не существует.

Эта проблема почти наверняка не выпуклая, потому что на самом деле будет несколько глобально оптимальных решений с одинаковыми оценками — учитывая любое предложенное решение, которое обычно дает распределение вероятностей для наблюдений с учетом базового состояния, вы можете , например, переименовать скрытое состояние 0 в скрытое состояние 1 и наоборот, настроив распределения вероятностей так, чтобы наблюдаемое поведение, генерируемое двумя разными решениями, было идентичным. Таким образом, если есть N скрытых состояний, то их как минимум N! локальные оптимумы, полученные путем перестановки скрытых состояний между собой.

В другом приложении ЭМ, https://www.math.ias.edu/csdm/files/11-12/amoitra_disentangling_gaussians.pdf содержит алгоритм поиска глобально оптимальной гауссовой смешанной модели. Он отмечает, что алгоритм EM часто используется для этой задачи, но указывает, что он не гарантирует нахождение глобального оптимума, и не ссылается как связанная работа на любую версию EM, которая могла бы (это также говорит, что алгоритм EM медленный) .

Если вы пытаетесь провести какой-то тест отношения правдоподобия между, например. модель с 4 состояниями и модель с 5 состояниями, было бы явно неловко, если бы из-за локальных оптимумов подобранная модель с 5 состояниями имела более низкую вероятность, чем модель с 4 состояниями. Одним из способов избежать этого или оправиться от него было бы запустить EM с 5 состояниями с начальной точки, очень близкой к начальной точке лучших найденных моделей с 4 состояниями. Например, вы можете создать 5-е состояние с вероятностью эпсилон и с выходным распределением, отражающим среднее выходных распределений с 4 состояниями, сохраняя распределения с 4 состояниями как другие 4 распределения в новой модели с 5 состояниями, умножая в множитель (1-эпсилон) где-то так, чтобы все еще складывалось в единицу.

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

Например, предположим, что в примере у меня есть две независимые переменные (x, y) и одна зависимая переменная (z), и предположим, что задан локальный минимум z_1 и пара начальных точек, которые сходятся к z_1 = (x_1, y_1) , P_1 = (x_2, y_1) и p_2 = (x_1, y_3), то я мог бы доказать, что тогда весь треугольник z_1, p_1, p_2 находится в области сходимости.

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