% consult example markov model first!

% Forward algorithm
% forward(+Words,-Probability)
% The variable alpha is represented by a list of alpha/2-terms:
% alpha(State,AccumulatedProbabilityOfState)

forward([W1|Words], P) :-
	init_alpha(W1, Alpha1),                    % Eq. F1
	induct_alpha(Words, Alpha1, Alpha_T),      % Eq. F2
	final_probability(Alpha_T, P).             % Eq. F3



% Initialization of Alpha (Equation 2.1)
% init_alpha(FirstWord, Alpha1)
init_alpha(W1, Alpha) :-
	findall(alpha(S,P), (a(s0,S,P1),b(S,W1,P2),P is P1*P2), Alpha).


% Induction of Alpha (Equation 2.2)
% induct_alpha(Words,Alpha_t,Alpha_T)
% Compute recursively the variable alpha_t+1 from alpha_t
induct_alpha([], Alpha, Alpha).
induct_alpha([W_t|Words], Alpha_t, Alpha_T) :-
  findall(alpha(S,P),
     (s(S),
      findall(P1,
        (member(alpha(S_Bar,P_S_Bar), Alpha_t),
         a(S_Bar,S,P2), P1 is P2 * P_S_Bar),
        P1List),
      sum_list(P1List, SumP1),
      b(S, W_t, P3),
      P is SumP1 * P3),
     Alpha_t_plus_1),
  induct_alpha(Words, Alpha_t_plus_1, Alpha_T).

% Final Probability (Equation 2.3)
% final_probability(+Alpha_T,-Probability)
final_probability(Alpha_T,Probability) :-
	findall(P2,
			(
			  member(alpha(S,P_Q), Alpha_T),
			  a(S, se, P1),
			  P2 is P_Q * P1
			),
			P2_List),
	sum_list(P2_List, Probability).
	


:- ensure_loaded(library(lists)).
