Guest User

Untitled

a guest
Feb 1st, 2013
310
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][0] = pi[i] * b[i][o[0]];
  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. }
RAW Paste Data