CODEWITHSUNDEEP
matlab
Ellie
Ellie

Reputation: 53

backward algorithm gives a different answer

I tried to solve the outcome likelihood problem implement both forward and backward algorithm in Matlab, but they give different answers. I don't know what I did wrong in my backward code (the forward one matches the answer). Can anyone help me?

%Forward Algorithm for HMM Problem
clc;clear;

states=['A','B']; %The N "hidden" states
N=length(states);
emmision_letters=['x','y','z']; % the emission letters.

%Initial Probabilities of states has equalized probablity.
I_prob=repelem(1/N, N)';
% Transition probabilities of states
T_prob=[0.303   0.697; 
       0.831   0.169 ]; 
% Emission prob( Prob of emission letters from given the state)
E_prob=[0.533   0.065   0.402; 
       0.342   0.334   0.324];
input_em='xzyyzzyzyy'; % emission letters
emlist=zeros(1,length(input_em)); %generate the list of the emission letters.

for i =1:length(input_em)
    if input_em(i)=='x'
        emlist(i)=1;
    elseif input_em(i)=='y'
        emlist(i)=2;
    elseif input_em(i)=='z'
        emlist(i)=3;
    end
end

 lem=length(emlist);

 Fq=zeros(N,lem);
 Bq=zeros(N,lem);% the table hold the values

 %Forward 
 for i=1:lem
    if i==1  
        %for i=1, Fq(1)=a_qstart*eq(x1)
        Fq(:,i)=I_prob.*E_prob(:,emlist(i)); 
    else
        % for i=2...n, for each q in Q, Fq(i)=sum(Fq(i-1)*a_qq'*e_q(xi))
        for j=1:N
            %Fq(i)=sum{fq(i-1)*Aqq'*Eq(xi)}
            Fq(j,i)=sum(Fq(:,i-1).*T_prob(:,j)).*E_prob(j,emlist(i)); 
        end
    end
 end
sum(Fq(:,lem)) % the last one represent the whole sequence


% Backward Algorithm for HMM Problem
    for i=lem:-1:1
        if i==lem
            % for i =n, Bq(n)=1
            Bq(:,i)=1;
        else
            % for i=n-1...1, for each q in Q
            for j=1:N
                % instead of calculate transition into A/B in i, 
                % calculate which jump out of A/B in step i+1
                % Bq(i)=sum(Bq(i+1)*a_qq'*e_q(x_i+1))
                Bq(j,i)=sum(Bq(:,i+1).*T_prob(j,:)').* E_prob(j,emlist(i+1));
            end 
        end
    end

    sum(Bq(:,1))

I can't see what is wrong. Thanks everyone for your help!

Upvotes: 0

Views: 71

Answers (1)

DeltaMethod
DeltaMethod

Reputation: 28

$$B_q(i) = \sum_{q^\prime \in Q}(a_{qq^\prime}e_{q^\prime x_{i+1}} B_{q^{\prime}}(i+1))$$

In your for loop:

Bq(j,i)=sum(Bq(:,i+1).*T_prob(j,:)').* E_prob(:,emlist(i+1));

I think this will work.

Upvotes: 1

Related Questions