21 #define GRT_DLL_EXPORTS
27 DiscreteHiddenMarkovModel::DiscreteHiddenMarkovModel(){
31 numRandomTrainingIterations = 5;
34 modelType = HMM_LEFTRIGHT;
38 debugLog.setProceedingText(
"[DEBUG DiscreteHiddenMarkovModel]");
39 errorLog.setProceedingText(
"[ERROR DiscreteHiddenMarkovModel]");
40 warningLog.setProceedingText(
"[WARNING DiscreteHiddenMarkovModel]");
41 trainingLog.setProceedingText(
"[TRAINING DiscreteHiddenMarkovModel]");
45 DiscreteHiddenMarkovModel::DiscreteHiddenMarkovModel(
const UINT numStates,
const UINT numSymbols,
const UINT modelType,
const UINT delta){
46 this->numStates = numStates;
47 this->numSymbols = numSymbols;
48 this->modelType = modelType;
51 numRandomTrainingIterations = 5;
55 debugLog.setProceedingText(
"[DEBUG DiscreteHiddenMarkovModel]");
56 errorLog.setProceedingText(
"[ERROR DiscreteHiddenMarkovModel]");
57 warningLog.setProceedingText(
"[WARNING DiscreteHiddenMarkovModel]");
58 trainingLog.setProceedingText(
"[TRAINING DiscreteHiddenMarkovModel]");
60 randomizeMatrices(numStates,numSymbols);
68 numRandomTrainingIterations = 5;
74 debugLog.setProceedingText(
"[DEBUG DiscreteHiddenMarkovModel]");
75 errorLog.setProceedingText(
"[ERROR DiscreteHiddenMarkovModel]");
76 warningLog.setProceedingText(
"[WARNING DiscreteHiddenMarkovModel]");
77 trainingLog.setProceedingText(
"[TRAINING DiscreteHiddenMarkovModel]");
83 this->modelType = modelType;
89 errorLog <<
"DiscreteHiddenMarkovModel(...) - The a,b,pi sizes are invalid!" << std::endl;
94 this->numStates = rhs.numStates;
95 this->numSymbols = rhs.numSymbols;
96 this->delta = rhs.delta;
97 this->numRandomTrainingIterations = rhs.numRandomTrainingIterations;
98 this->cThreshold = rhs.cThreshold;
99 this->modelType = rhs.modelType;
100 this->logLikelihood = rhs.logLikelihood;
104 this->trainingLog = rhs.trainingLog;
106 debugLog.setProceedingText(
"[DEBUG DiscreteHiddenMarkovModel]");
107 errorLog.setProceedingText(
"[ERROR DiscreteHiddenMarkovModel]");
108 warningLog.setProceedingText(
"[WARNING DiscreteHiddenMarkovModel]");
109 trainingLog.setProceedingText(
"[TRAINING DiscreteHiddenMarkovModel]");
113 DiscreteHiddenMarkovModel::~DiscreteHiddenMarkovModel(){
118 bool DiscreteHiddenMarkovModel::resetModel(
const UINT numStates,
const UINT numSymbols,
const UINT modelType,
const UINT delta){
119 this->numStates = numStates;
120 this->numSymbols = numSymbols;
121 this->modelType = modelType;
123 return randomizeMatrices(numStates,numSymbols);
126 bool DiscreteHiddenMarkovModel::randomizeMatrices(
const UINT numStates,
const UINT numSymbols){
133 this->numStates = numStates;
134 this->numSymbols = numSymbols;
135 a.
resize(numStates,numStates);
136 b.
resize(numStates,numSymbols);
152 for(UINT i=0; i<numStates; i++)
162 for(UINT i=0; i<numStates; i++)
163 for(UINT j=0; j<numStates; j++)
164 if((j<i) || (j>i+delta)) a[i][j] = 0.0;
167 for(UINT i=0; i<numStates; i++){
168 pi[i] = i==0 ? 1 : 0;
172 throw(
"HMM_ERROR: Unkown model type!");
179 for (UINT i=0; i<numStates; i++) {
181 for (UINT j=0; j<numStates; j++) sum += a[i][j];
182 for (UINT j=0; j<numStates; j++) a[i][j] /= sum;
184 for (UINT i=0; i<numStates; i++) {
186 for (UINT k=0; k<numSymbols; k++) sum += b[i][k];
187 for (UINT k=0; k<numSymbols; k++) b[i][k] /= sum;
192 for (UINT i=0; i<numStates; i++) sum += pi[i];
193 for (UINT i=0; i<numStates; i++) pi[i] /= sum;
198 Float DiscreteHiddenMarkovModel::predict(
const UINT newSample){
204 observationSequence.
push_back( newSample );
214 Float DiscreteHiddenMarkovModel::predict(
const Vector<UINT> &obs){
216 const int N = (int)numStates;
217 const int T = (int)obs.size();
227 alpha[t][i] = pi[i]*b[i][ obs[t] ];
235 for(i=0; i<N; i++) alpha[t][i] *= c[t];
243 alpha[t][j] += alpha[t-1][i] * a[i][j];
245 alpha[t][j] *= b[j][obs[t]];
253 for(j=0; j<N; j++) alpha[t][j] *= c[t];
256 if(
int(estimatedStates.size()) != T ) estimatedStates.
resize(T);
260 if( alpha[t][i] > maxValue ){
261 maxValue = alpha[t][i];
262 estimatedStates[t] = i;
268 Float loglikelihood = 0.0;
269 for(t=0; t<T; t++) loglikelihood += log( c[t] );
270 return -loglikelihood;
276 Float DiscreteHiddenMarkovModel::predictLogLikelihood(
const Vector<UINT> &obs){
278 const UINT T = (
unsigned int)obs.size();
279 UINT t,i,j,minState = 0;
286 for(i=0; i<numStates; i++){
287 alpha[t][i] = (-1.0 * log(pi[i])) - log(b[i][ obs[t] ]);
292 for (j=0; j<numStates; j++){
294 minWeight = alpha[t-1][j] - log(a[0][j]);
296 for (i=1; i<numStates; i++){
297 weight = alpha[t-1][i] - log(a[i][j]);
299 if (weight < minWeight)
306 alpha[t][j] = minWeight - log(b[j][ obs[t] ]);
312 minWeight = alpha[T - 1][0];
314 for(i=1; i<numStates; i++)
316 if (alpha[T-1][i] < minWeight)
319 minWeight = alpha[T-1][i];
324 return exp(-minWeight);
332 const int N = (int)numStates;
333 const int T = (int)obs.size();
341 hmm.alpha[t][i] = pi[i]*b[i][ obs[t] ];
342 hmm.c[t] += hmm.alpha[t][i];
346 hmm.c[t] = 1.0/hmm.c[t];
349 for(i=0; i<N; i++) hmm.alpha[t][i] *= hmm.c[t];
355 hmm.alpha[t][j] = 0.0;
357 hmm.alpha[t][j] += hmm.alpha[t-1][i] * a[i][j];
359 hmm.alpha[t][j] *= b[j][obs[t]];
360 hmm.c[t] += hmm.alpha[t][j];
364 hmm.c[t] = 1.0/hmm.c[t];
367 for(j=0; j<N; j++) hmm.alpha[t][j] *= hmm.c[t];
372 for(t=0; t<T; t++) hmm.pk += log( hmm.c[t] );
375 if( grt_isinf(hmm.pk) ){
382 for(i=0; i<N; i++) hmm.beta[t][i] = 1.0;
385 for(i=0; i<N; i++) hmm.beta[t][i] *= hmm.c[t];
388 for(t=T-2; t>=0; t--){
393 hmm.beta[t][i] += a[i][j] * b[j][ obs[t+1] ] * hmm.beta[t+1][j];
396 hmm.beta[t][i] *= hmm.c[t];
410 observationSequence.
clear();
411 estimatedStates.clear();
412 trainingIterationLog.clear();
414 UINT n,currentIter, bestIndex = 0;
415 Float newLoglikelihood, bestLogValue = 0;
417 if( numRandomTrainingIterations > 1 ){
424 UINT maxNumTestIter = maxNumEpochs > 10 ? 10 : maxNumEpochs;
427 for(n=0; n<numRandomTrainingIterations; n++){
429 randomizeMatrices(numStates,numSymbols);
431 if( !train_(trainingData,maxNumTestIter,currentIter,newLoglikelihood) ){
436 loglikelihoodTracker[n] = newLoglikelihood;
441 bestLogValue = loglikelihoodTracker[0];
442 for(n=1; n<numRandomTrainingIterations; n++){
443 if(bestLogValue < loglikelihoodTracker[n]){
444 bestLogValue = loglikelihoodTracker[n];
450 a = aTracker[bestIndex];
451 b = bTracker[bestIndex];
454 randomizeMatrices(numStates,numSymbols);
458 if( !train_(trainingData,maxNumEpochs,currentIter,newLoglikelihood) ){
463 const UINT numObs = (
unsigned int)trainingData.size();
465 UINT averageObsLength = 0;
466 for(k=0; k<numObs; k++){
467 const UINT T = (
unsigned int)trainingData[k].size();
468 averageObsLength += T;
471 averageObsLength = (UINT)floor( averageObsLength/Float(numObs) );
472 observationSequence.
resize( averageObsLength );
473 estimatedStates.
resize( averageObsLength );
481 bool DiscreteHiddenMarkovModel::train_(
const Vector<
Vector<UINT> > &obs,
const UINT maxIter, UINT ¤tIter,Float &newLoglikelihood){
483 const UINT numObs = (
unsigned int)obs.size();
485 Float num,denom,oldLoglikelihood = 0;
486 bool keepTraining =
true;
487 trainingIterationLog.clear();
497 for(k=0; k<numObs; k++){
498 const UINT T = (UINT)obs[k].size();
499 gamma[k].
resize(T,numStates);
500 epsilon[k].resize(T);
501 for(t=0; t<T; t++) epsilon[k][t].resize(numStates,numStates);
504 hmms[k].alpha.resize(T,numStates);
505 hmms[k].beta.resize(T,numStates);
511 oldLoglikelihood = 0;
512 newLoglikelihood = 0;
516 newLoglikelihood = 0.0;
519 for(k=0; k<numObs; k++){
520 if( !forwardBackward(hmms[k],obs[k]) ){
523 newLoglikelihood += hmms[k].pk;
527 newLoglikelihood /= numObs;
529 trainingIterationLog.push_back( newLoglikelihood );
531 if( ++currentIter >= maxIter ){ keepTraining =
false; trainingLog <<
"Max Iter Reached! Stopping Training" << std::endl; }
532 if( fabs(newLoglikelihood-oldLoglikelihood) < minChange && currentIter > 1 ){ keepTraining =
false; trainingLog <<
"Min Improvement Reached! Stopping Training" << std::endl; }
535 trainingLog <<
"Iter: " << currentIter <<
" logLikelihood: " << newLoglikelihood <<
" change: " << oldLoglikelihood - newLoglikelihood << std::endl;
540 oldLoglikelihood = newLoglikelihood;
546 for(i=0; i<numStates; i++){
550 for(k=0; k<numObs; k++){
551 for(t=0; t<obs[k].size()-1; t++){
552 denom += hmms[k].alpha[t][i] * hmms[k].beta[t][i] / hmms[k].c[t];
558 for(j=0; j<numStates; j++){
560 for(k=0; k<numObs; k++){
561 for(t=0; t<obs[k].size()-1; t++){
562 num += hmms[k].alpha[t][i] * a[i][j] * b[j][ obs[k][t+1] ] * hmms[k].beta[t+1][j];
570 errorLog <<
"Denom is zero for A!" << std::endl;
576 bool renormB =
false;
577 for(i=0; i<numStates; i++){
578 for(j=0; j<numSymbols; j++){
581 for(k=0; k<numObs; k++){
582 const UINT T = (
unsigned int)obs[k].size();
584 if( obs[k][t] == j ){
585 num += hmms[k].alpha[t][i] * hmms[k].beta[t][i] / hmms[k].c[t];
587 denom += hmms[k].alpha[t][i] * hmms[k].beta[t][i] / hmms[k].c[t];
592 errorLog <<
"Denominator is zero for B!" << std::endl;
598 if( num > 0 ) b[i][j] = denom > 0 ? num/denom : 1.0e-5;
599 else{ b[i][j] = 0; renormB =
true; }
605 for (UINT i=0; i<numStates; i++) {
607 for (UINT k=0; k<numSymbols; k++){
608 b[i][k] += 1.0/numSymbols;
611 for (UINT k=0; k<numSymbols; k++) b[i][k] /= sum;
616 if (modelType==HMM_ERGODIC ){
617 for(k=0; k<numObs; k++){
618 const UINT T = (
unsigned int)obs[k].size();
620 for(t=0; t<T-1; t++){
622 for(i=0; i<numStates; i++){
623 for(j=0; j<numStates; j++){
624 epsilon[k][t][i][j] = hmms[k].alpha[t][i] * a[i][j] * b[j][ obs[k][t+1] ] * hmms[k].beta[t+1][j];
625 denom += epsilon[k][t][i][j];
629 for(i=0; i<numStates; i++){
630 for(j=0; j<numStates; j++){
631 if(denom!=0) epsilon[k][t][i][j] /= denom;
632 else{ epsilon[k][t][i][j] = 0; }
638 for(t=0; t<T-1; t++){
639 for(i=0; i<numStates; i++){
641 for(j=0; j<numStates; j++)
642 gamma[k][t][i] += epsilon[k][t][i][j];
648 for(i=0; i<numStates; i++){
650 for(k=0; k<numObs; k++){
651 sum += gamma[k][0][i];
653 pi[i] = sum / numObs;
658 }
while(keepTraining);
666 for(UINT i=0; i<observationSequence.
getSize(); i++){
677 errorLog <<
"save( fstream &file ) - File is not open!" << std::endl;
682 file <<
"DISCRETE_HMM_MODEL_FILE_V1.0\n";
686 errorLog <<
"save(fstream &file) - Failed to save classifier base settings to file!" << std::endl;
690 file <<
"NumStates: " << numStates << std::endl;
691 file <<
"NumSymbols: " << numSymbols << std::endl;
692 file <<
"ModelType: " << modelType << std::endl;
693 file <<
"Delta: " << delta << std::endl;
694 file <<
"Threshold: " << cThreshold << std::endl;
695 file <<
"NumRandomTrainingIterations: " << numRandomTrainingIterations << std::endl;
698 for(UINT i=0; i<numStates; i++){
699 for(UINT j=0; j<numStates; j++){
701 if( j+1 < numStates ) file <<
"\t";
706 for(UINT i=0; i<numStates; i++){
707 for(UINT j=0; j<numSymbols; j++){
709 if( j+1 < numSymbols ) file <<
"\t";
714 for(UINT i=0; i<numStates; i++){
716 if( i+1 < numStates ) file <<
"\t";
729 errorLog <<
"load( fstream &file ) - File is not open!" << std::endl;
738 if(word !=
"DISCRETE_HMM_MODEL_FILE_V1.0"){
739 errorLog <<
"load( fstream &file ) - Could not find Model File Header!" << std::endl;
745 errorLog <<
"load(string filename) - Failed to load base settings from file!" << std::endl;
750 if(word !=
"NumStates:"){
751 errorLog <<
"load( fstream &file ) - Could not find the NumStates header." << std::endl;
757 if(word !=
"NumSymbols:"){
758 errorLog <<
"load( fstream &file ) - Could not find the NumSymbols header." << std::endl;
764 if(word !=
"ModelType:"){
765 errorLog <<
"load( fstream &file ) - Could not find the modelType for the header." << std::endl;
771 if(word !=
"Delta:"){
772 errorLog <<
"load( fstream &file ) - Could not find the Delta for the header." << std::endl;
778 if(word !=
"Threshold:"){
779 errorLog <<
"load( fstream &file ) - Could not find the Threshold for the header." << std::endl;
785 if(word !=
"NumRandomTrainingIterations:"){
786 errorLog <<
"load( fstream &file ) - Could not find the numRandomTrainingIterations header." << std::endl;
789 file >> numRandomTrainingIterations;
791 a.
resize(numStates,numStates);
792 b.
resize(numStates,numSymbols);
798 errorLog <<
"load( fstream &file ) - Could not find the A matrix header." << std::endl;
803 for(UINT i=0; i<numStates; i++){
804 for(UINT j=0; j<numStates; j++){
811 errorLog <<
"load( fstream &file ) - Could not find the B matrix header." << std::endl;
816 for(UINT i=0; i<numStates; i++){
817 for(UINT j=0; j<numSymbols; j++){
824 errorLog <<
"load( fstream &file ) - Could not find the Pi matrix header." << std::endl;
829 for(UINT i=0; i<numStates; i++){
838 trainingLog <<
"A: " << std::endl;
841 trainingLog << a[i][j] <<
"\t";
843 trainingLog << std::endl;
846 trainingLog <<
"B: " << std::endl;
849 trainingLog << b[i][j] <<
"\t";
851 trainingLog << std::endl;
854 trainingLog <<
"Pi: ";
855 for(UINT i=0; i<pi.size(); i++){
856 trainingLog << pi[i] <<
"\t";
858 trainingLog << std::endl;
865 for(UINT j=0; j<a.
getNumCols(); j++) sum += a[i][j];
866 if( sum <= 0.99 || sum >= 1.01 ) warningLog <<
"WARNING: A Row " << i <<
" Sum: "<< sum << std::endl;
871 for(UINT j=0; j<b.
getNumCols(); j++) sum += b[i][j];
872 if( sum <= 0.99 || sum >= 1.01 ) warningLog <<
"WARNING: B Row " << i <<
" Sum: " << sum << std::endl;
879 VectorFloat DiscreteHiddenMarkovModel::getTrainingIterationLog()
const{
880 return trainingIterationLog;
bool saveBaseSettingsToFile(std::fstream &file) const
bool push_back(const T &value)
virtual bool save(std::fstream &file) const
virtual bool resize(const unsigned int size)
unsigned int getNumRows() const
unsigned int getNumCols() const
bool loadBaseSettingsFromFile(std::fstream &file)
This class implements a discrete Hidden Markov Model.
virtual bool print() const
Float getRandomNumberUniform(Float minRange=0.0, Float maxRange=1.0)
virtual bool resize(const unsigned int r, const unsigned int c)
virtual bool load(std::fstream &file)
Vector< T > getData(const bool rawBuffer=false) const
unsigned int getSize() const
bool resize(const unsigned int newBufferSize)