第11章 条件随机场 - 实现前向-后向算法

import numpy as np

def forward_algorithm(transition_matrix, emission_matrix, start_prob, observations):
    num_states = len(start_prob)
    seq_len = len(observations)
    alpha = np.zeros((seq_len, num_states))
    
    alpha[0] = start_prob * emission_matrix[:, observations[0]]
    
    for t in range(1, seq_len):
        for s in range(num_states):
            alpha[t, s] = np.sum(alpha[t-1] * transition_matrix[:, s]) * emission_matrix[s, observations[t]]
    
    return alpha, np.sum(alpha[-1])

def backward_algorithm(transition_matrix, emission_matrix, end_prob, observations):
    num_states = len(end_prob)
    seq_len = len(observations)
    beta = np.zeros((seq_len, num_states))
    
    beta[-1] = end_prob
    
    for t in range(seq_len - 2, -1, -1):
        for s in range(num_states):
            beta[t, s] = np.sum(transition_matrix[s, :] * emission_matrix[:, observations[t+1]] * beta[t+1])
    
    return beta