Home // ICCGI 2012, The Seventh International Multi-Conference on Computing in the Global Information Technology // View article

State Complexity of Hidden Markov Model

Authors:
Jamil Ahmed
Stephen M. Watt
Sherjil Ahmed

Keywords: State complexity; Hidden Markov Model

Abstract:
A Classification problem can be viewed as a problem of assigning a category or class to a given input. The Hidden Markov model is a well known stochastic model that is used to solve classification problems and has been widely exploited in diverse computing applications ranging from speech, acoustics, gesture recognition to part-of-speech tagging, cryptography to Google page rank and the list goes on. State Complexity of Deterministic Finite automata is now a well established research area. State complexity of Deterministic Finite Automata defines the total number of states in the minimal Deterministic Finite Automata. State complexity, if known, of a given automata helps to realize how expensive the application would be that will exploit that automata. Similarly, if known, the state complexity of the Hidden Markov Model will help to know the complexity of a computing application that exploits that Hidden Markov Model. In this paper, we have explored several, yet unpublished, important facts about the Hidden Markov Model including the state complexity of Hidden Markov Model and the diagram of 2nd order Hidden Markov Model (Fig. 3). Our discussion of the Hidden Markov Model is unique in the sense that we present a complete diagram of the 1st order Hidden Markov Model (Fig. 2) with all estimated parameters for a given input sequence. We explicitly define a generalized rule to give “Dimension of Transition probability matrix of HMM” which is also not available in the literature yet. We present a generalized rule to draw the Mth order Hidden Markov Model diagram for M greater than 1. We present the generalized state complexity of the Mth Order HMM, the state complexity of the diagram for the “Training of Mth Order HMM” and also present the diagram for second order Hidden Markov Model.

Pages: 46 to 51

Copyright: Copyright (c) IARIA, 2012

Publication date: June 24, 2012

Published in: conference

ISSN: 2308-4529

ISBN: 978-1-61208-202-8

Location: Venice, Italy

Dates: from June 24, 2012 to June 29, 2012