 # Untitled

a guest
Feb 1st, 2013
353
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import java.text.*;
2.
3. /** This class implements a Hidden Markov Model, as well as
4. the Baum-Welch Algorithm for training HMMs.
5. @author Holger Wunsch (wunsch@sfs.nphil.uni-tuebingen.de)
6. */
7. public class HMM {
8. /** number of states */
9. public int numStates;
10.
11. /** size of output vocabulary */
12. public int sigmaSize;
13.
14. /** initial state probabilities */
15. public double pi[];
16.
17. /** transition probabilities */
18. public double a[][];
19.
20. /** emission probabilities */
21. public double b[][];
22.
23. /** initializes an HMM.
24. @param numStates number of states
25. @param sigmaSize size of output vocabulary
26. */
27.
28. public HMM(int numStates, int sigmaSize) {
29. this.numStates = numStates;
30. this.sigmaSize = sigmaSize;
31.
32. pi = new double[numStates];
33. a = new double[numStates][numStates];
34. b = new double[numStates][sigmaSize];
35. }
36.
37. /** implementation of the Baum-Welch Algorithm for HMMs.
38. @param o the training set
39. @param steps the number of steps
40. */
41. public void train(int[] o, int steps) {
42. int T = o.length;
43. double[][] fwd;
44. double[][] bwd;
45.
46. double pi1[] = new double[numStates];
47. double a1[][] = new double[numStates][numStates];
48. double b1[][] = new double[numStates][sigmaSize];
49.
50. for (int s = 0; s < steps; s++) {
51. /* calculation of Forward- und Backward Variables from the
52. current model */
53. fwd = forwardProc(o);
54. bwd = backwardProc(o);
55.
56. /* re-estimation of initial state probabilities */
57. for (int i = 0; i < numStates; i++)
58. pi1[i] = gamma(i, 0, o, fwd, bwd);
59.
60. /* re-estimation of transition probabilities */
61. for (int i = 0; i < numStates; i++) {
62. for (int j = 0; j < numStates; j++) {
63. double num = 0;
64. double denom = 0;
65. for (int t = 0; t <= T - 1; t++) {
66. num += p(t, i, j, o, fwd, bwd);
67. denom += gamma(i, t, o, fwd, bwd);
68. }
69. a1[i][j] = divide(num, denom);
70. }
71. }
72.
73. /* re-estimation of emission probabilities */
74. for (int i = 0; i < numStates; i++) {
75. for (int k = 0; k < sigmaSize; k++) {
76. double num = 0;
77. double denom = 0;
78.
79. for (int t = 0; t <= T - 1; t++) {
80. double g = gamma(i, t, o, fwd, bwd);
81. num += g * (k == o[t] ? 1 : 0);
82. denom += g;
83. }
84. b1[i][k] = divide(num, denom);
85. }
86. }
87. pi = pi1;
88. a = a1;
89. b = b1;
90. }
91. }
92.
93.
94. /** calculation of Forward-Variables f(i,t) for state i at time
95. t for output sequence O with the current HMM parameters
96. @param o the output sequence O
97. @return an array f(i,t) over states and times, containing
98. the Forward-variables.
99. */
100.
101. public double[][] forwardProc(int[] o) {
102. int T = o.length;
103. double[][] fwd = new double[numStates][T];
104.
105. /* initialization (time 0) */
106. for (int i = 0; i < numStates; i++)
107. fwd[i] = pi[i] * b[i][o];
108.
109. /* induction */
110. for (int t = 0; t <= T-2; t++) {
111. for (int j = 0; j < numStates; j++) {
112. fwd[j][t+1] = 0;
113. for (int i = 0; i < numStates; i++)
114. fwd[j][t+1] += (fwd[i][t] * a[i][j]);
115. fwd[j][t+1] *= b[j][o[t+1]];
116. }
117. }
118.
119. return fwd;
120. }