-
Notifications
You must be signed in to change notification settings - Fork 0
/
hmm.cpp
87 lines (69 loc) · 2.61 KB
/
hmm.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
using namespace std;
//Recursive function for foward algorithm
float forward(int pos, vector<int>in, int st, vector<vector<float> >trans, vector<vector<float> >emat){
//Termination condition - when reaches the first observation
if(!pos){
if(st == 0)
return emat[0][in[pos]] * trans[0][1];
else
return emat[1][in[pos]] * trans[0][2];
}
//State 2
if(st){
return emat[1][in[pos]] * (trans[1][2] * forward(pos-1, in, 0, trans, emat) + trans[2][2] * forward(pos-1, in, 1, trans, emat));
}
//State 1
else{
return emat[0][in[pos]] * (trans[1][1] * forward(pos-1, in, 0, trans, emat) + trans[2][1] * forward(pos-1, in, 1, trans, emat));
}
}
//Recursive function for backward algorithm
float backward(int pos, vector<int>in, int st, vector<vector<float> >trans, vector<vector<float> >emat){
//Termination condition - when reaches the final observation
if(pos == (in.size()-1))
return 1;
//State 1
if(!st){
return trans[1][1] * emat[0][in[pos+1]] * backward(pos+1, in, 0, trans, emat) + trans[1][2] * emat[1][in[pos+1]] * backward(pos+1, in, 1, trans, emat);
}
//State 2
else{
return trans[2][1] * emat[0][in[pos+1]] * backward(pos+1, in, 0, trans, emat) + trans[2][2] * emat[1][in[pos+1]] * backward(pos+1, in, 1, trans, emat);
}
}
int main(){
vector<vector<float> >trans(3, vector<float>(3,0.0)); //Transition matrix
vector<vector<float> >emat(2, vector<float>(2,0.0)); //Symbol emission probability matrix
vector<int>in; //Observations, H -> 0 and T -> 1
int ob, n;
float val, prob, bprob;
cout<<"Enter the number of observations: ";
cin>>ob;
cout<<"Enter the sequence of observations: ";
while(ob){
cin>>n;
in.push_back(n);
--ob;
}
cout<<"Enter the transition matrix: ";
for(int i = 0; i <= 2; i++){
for(int j = 0; j <= 2; j++){
cin>>val;
trans[i][j] = val;
}
}
cout<<"Enter the symbol emission probabilities: ";
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
cin>>val;
emat[i][j] = val;
}
}
n = in.size() - 1;
prob = forward(n, in, 0, trans, emat) + forward(n, in, 1, trans, emat);
cout<<"Probability of the sequence: "<<prob<<"\n";
bprob = trans[0][1] * emat[0][in[0]] * backward(0, in, 0, trans, emat) + trans[0][2] * emat[1][in[0]] * backward(0, in, 1, trans, emat);
cout<<"Using backward algorithm: "<<bprob<<"\n";
return 0;
}