Created
October 26, 2025 20:34
-
-
Save raitonoberu/44f9f72cca30ce90469809c469318635 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import numpy as np | |
| def viterbi(observations, states, start_p, trans_p, emit_p): | |
| obs_map = {"Тишина": 0, "Разговор": 1, "Клавиатура": 2} | |
| obs_indices = [obs_map[obs] for obs in observations] | |
| T = len(observations) # количество наблюдений | |
| N = len(states) # количество состояний | |
| # Матрицы для алгоритма Витерби | |
| delta = np.zeros((T, N)) # максимальные вероятности | |
| psi = np.zeros((T, N), dtype=int) # обратные указатели | |
| # Шаг 1: Инициализация (t=0) | |
| for i in range(N): | |
| delta[0, i] = start_p[i] * emit_p[i, obs_indices[0]] | |
| psi[0, i] = 0 | |
| # Шаг 2: Рекурсия (t=1 до T-1) | |
| for t in range(1, T): | |
| for j in range(N): | |
| # Находим максимальную вероятность и состояние-предшественник | |
| max_prob = 0 | |
| best_prev_state = 0 | |
| for i in range(N): | |
| prob = delta[t - 1, i] * trans_p[i, j] | |
| if prob > max_prob: | |
| max_prob = prob | |
| best_prev_state = i | |
| delta[t, j] = max_prob * emit_p[j, obs_indices[t]] | |
| psi[t, j] = best_prev_state | |
| # Шаг 3: Завершение - находим наиболее вероятное конечное состояние | |
| best_path_prob = 0 | |
| best_last_state = 0 | |
| for i in range(N): | |
| if delta[T - 1, i] > best_path_prob: | |
| best_path_prob = delta[T - 1, i] | |
| best_last_state = i | |
| # Шаг 4: Обратный ход - восстанавливаем путь | |
| best_path = [best_last_state] | |
| for t in range(T - 1, 0, -1): | |
| best_path.insert(0, psi[t, best_path[0]]) | |
| return best_path, best_path_prob, delta, psi | |
| def main(): | |
| states = ["Чтение", "Звонок", "Работа"] | |
| observations = ["Тишина", "Разговор", "Тишина", "Клавиатура", "Разговор"] | |
| # Начальные вероятности | |
| start_p = np.array([0.4, 0.1, 0.5]) | |
| # Матрица переходов | |
| trans_p = np.array([[0.9, 0.1, 0.0], [0.2, 0.0, 0.8], [0.2, 0.7, 0.1]]) | |
| # Матрица эмиссии (Тишина, Разговор, Клавиатура) | |
| emit_p = np.array( | |
| [ | |
| [0.8, 0.1, 0.1], # Чтение | |
| [0.3, 0.6, 0.1], # Звонок | |
| [0.3, 0.2, 0.5], # Работа | |
| ] | |
| ) | |
| best_path, best_prob, delta, psi = viterbi( | |
| observations, states, start_p, trans_p, emit_p | |
| ) | |
| print("Наблюдения:", " -> ".join(observations)) | |
| print("\nМатрица delta (вероятности):") | |
| for t in range(len(observations)): | |
| print(f"t={t + 1}: ", end="") | |
| for i in range(len(states)): | |
| print(f"{delta[t, i]:.6f} ", end="") | |
| print() | |
| print("\nМатрица psi (обратные указатели):") | |
| for t in range(len(observations)): | |
| print(f"t={t + 1}: ", end="") | |
| for i in range(len(states)): | |
| print(f"{psi[t, i]} ", end="") | |
| print() | |
| print("\nНаиболее вероятная последовательность состояний:") | |
| path_names = [states[i] for i in best_path] | |
| for t, state in enumerate(path_names): | |
| print(f"t={t + 1}: {state}") | |
| print(f"\nВероятность этой последовательности: {best_prob:.10f}") | |
| if __name__ == "__main__": | |
| main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment