Parameter Estimation for Partially Observed Discrete-Time Semi-Markov Chains


It is now usual that the null-hypothesis for a finite-state stochastic process is conveniently taken to be the standard Markov chain. In the absence of any other system knowledge this is the model that is often used. Some reasons for this are; Markov chains are relatively simple, they have been well studied and much is known about these processes. Added to this there are now decades of history applying the standard Hidden Markov Model (HMM) to: defence science, gene sequencing, health science, machine learning, artificial intelligence and many other areas. In this seminar we will briefly recall two common application domains of estimation with latent Markov processes, 1) parts-of-speech tagging (POS) in natural language processing and 2) tracking a maneuvering object with a Jump Markov System. Semi-Markov models relax an implicit feature of every state in a first-order time-homogeneous Markov chains, that is, the sojourn random variables of such states are geometrically distributed and are therefore, (uniquely) memoryless random variables. In contrast, semi-Markov chains allow arbitrary sojourn models. Consequently, a Hidden semi-Markov Model (HsMM) offers a richer class of model, but retains the classical HMM as a special degenerate case.

The main task we address in this seminar concerns model calibration, or parameter estimation of a HsMM. We develop an Expectation Maximization (EM) algorithm to compute the best fitting (in the Maximum Likelihood sense) HsMM for a given set of observation data. There are several parts to this task, the first is to derive a recursive filter and smoother for a partially observed semi-Markov chain. The second and more challenging part of the task is to derive filters and smoothers for various processes derived from the latent semi-Markov chain, for example, a counting process that counts the number of transitions between two distinct states labelled "i" and "j", up to an including time k. We will see that estimators for such quantities are non-trivial, largely because of the sojourn dependence in transition probabilities.

The estimators we present are all for partially observed joint events, that is, the state of the semi-Markov chain at time "k" and the cumulative time it has remained in this state. This means we are assured of exponential forgetting of initial conditions in our estimators. Separate estimators for individual quantities such as the semi-Markov state alone are easily computed via marginalization.


W. P. Malcolm received his PhD from the ANU in 1999.

His PhD advisors were Professor Matthew James (Electrical Engineering ANU), Dr. Daryl Daley (Mathematics ANU) and Professor Robert Elliott (Mathematics University of Alberta, Canada). The title of his Thesis was "Robust Filtering and Estimation with Poisson Observations".

W P Malcolm has worked in DST for approximately 20 years, mostly on estimation tasks such as filtering, tracking, optimal resource allocation, natural language processing and the aggregation of quantified expert opinion. He was also employed as a senior researcher in the National ICT Australia (NICTA) for a period of 5 years and spent the year of June 2003 to June 2004 at the University of Calgary as a Postdoc with Professor Robert Elliott.

He is currently employed in Canberra by DST within the Cyber Electronic Warfare Division (CEWD).

Talk Slides:

Talk slides (PDF 739 KB)

Zoom Details:

Topic: Mathematics and Computational Sciences Seminar Series 
Time: This is a recurring meeting Meet anytime

Join Zoom Meeting

Meeting ID: 880 8490 0678
Password: 971872
One tap mobile
+61731853730,,88084900678#,,,,0#,,971872# Australia
+61861193900,,88084900678#,,,,0#,,971872# Australia

Dial by your location
        +61 7 3185 3730 Australia
        +61 8 6119 3900 Australia
        +61 8 7150 1149 Australia
        +61 2 8015 6011 Australia
        +61 3 7018 2005 Australia
Meeting ID: 880 8490 0678
Password: 971872
Find your local number:

Or an H.323/SIP room system:
    Dial: +61262227588 (AUCX)
    Meeting ID: 88084900678
    H323/SIP Password: 971872

Join by Skype for Business