Задача 07L. hmm_forward_backward ≡

Условие

Пусть задана скрытая марковская модель с множеством значений скрытой переменной X = 0,n − 1, множеством значений наблюдаемой переменной Y = 0,m − 1, матрицей вероятностей перехода p(x_t = i|x_t − 1 = j) = S_j,i и матрицей вероятности наблюдений p(o_t = i|x_t = j) = O_j,i. Для заданной последовательности y = (y₁,…,y_T) и начальными вероятностями p(x₀ = i) = q_i вычислить вероятности p(x_t = i|y) = P_t,i с использованием Forward-backward algorithm.

При решении задачи необходимо использовать библиотеку numpy.

Формат входных данных

Первая строка входного файла содержит 3 натуральных числа n, m, T. Следующие n строк содержат по n вещественных чисел — матрица S, далее n строк по m вещественных чисел — матрица O. Последние две строки содержат по n и t вещественных чисел соответственно — векторы y и q.

Формат выходных данных

Выходной файл должен содержать t + 1 строку по n вещественных чисел с точностью не менее 3-х знаков после запятой — матрицу P_t,i.

Примеры тестов

2 2 5
0.7 0.3
0.3 0.7
0.9 0.1
0.2 0.8
0.7 0.3
0 0 1 0 0

0.81  0.19
0.9   0.1
0.831 0.169
0.31  0.69
0.821 0.179
0.867 0.133